Hanson's table interface, analyzed!

As shipped by the author:

#ifndef TABLE_INCLUDED
#define TABLE_INCLUDED
#define T Table_T
typedef struct T *T;
extern T    Table_new (int hint,
    int cmp(const void *x, const void *y),
    unsigned hash(const void *key));
extern void  Table_free(T *table);
extern int   Table_length(T table);
extern void *Table_put   (T table, const void *key, void *value);
extern void *Table_get   (T table, const void *key);
extern void *Table_remove(T table, const void *key);
extern void  Table_map    (T table,
    void apply(const void *key, void **value, void *cl),
    void *cl);
extern void **Table_toArray(T table, void *end);
#undef T
#endif

Protection against multiple definitions (illegal C):

#ifndef TABLE_INCLUDED
#define TABLE_INCLUDED

  ...

#endif

Within the protection, a Hanson idiom for abbreviation:

#define T Table_T
typedef struct T *T;
  ...
#undef T

Expands to

typedef <something> Table_T

Where something is struct Table_T *

Lots going on here:

This is C's mechanism for abstraction: all members are private


The core idea of tableness:

extern void *Table_put(T table, const void *key, void *value);
extern void *Table_get(T table, const void *key);

Let's make it clearer:

typedef void key_t; // key   type is unknown
typedef void val_t; // value type is unknown

extern val_t *Table_put(T table, const key_t *key, val_t *value);
extern val_t *Table_get(T table, const key_t *key);

Lessons:


Building on this core

typedef struct T *T;

typedef void key_t;
typedef void val_t;

extern val_t *Table_put(T table, const key_t *key, val_t *value);
extern val_t *Table_get(T table, const key_t *key);

Are we commited to an implementation yet?

What data structures can we use for a table?

To make these data structures, do we need to know anything about keys or values?

What?


For a binary search tree:

For a hash table:

Hanson requires both!

int cmp(const key_t *x, const key_t *y),
unsigned hash(const key_t *key)

Why?


Hanson's required functions are passed at table-creation time:

extern T Table_new (int hint,
    int cmp(const key_t *x, const key_t *y),
    unsigned hash(const key_t *key));

[Note: First use of function pointers]

Why?


What are the contracts of new, put, and get?

What other operations do you expect on a table?


Hanson's table operations

typedef struct T *T;

typedef void key_t;
typedef void val_t;

For every allocation, a deallocation:

extern void  Table_free(T *table);

Deletion:

extern void *Table_remove(T table, const key_t *key);

How many elements?

extern int   Table_length(T table);

What's missing?


Iteration --- the overlooked abstraction

Idea: visit every key-value pair in the table.

But what is a visitor?

Consider iteration over array elements:

for (i = 0; i < n; i++ ) { ... } 

Or even over elements of a list:

for (p = list; p != NULL; p = p->rest) { ... }

How would you generalize the iteration, without exposing the representation?


The body of a for loop includes

Example: number of strings in a list that begin with a capital letter.

What would you write?

for (p = list; p != NULL; p = p->next) {



}

What is the state? (that persists between iterations)

What is the code? (that runs at every iteration)


Counting capitals, abstracted

Persistent state (between iterations): number of capitals

struct cap_state {
  int ncapitals;
}

Code that runs:

typedef void state_t;

void add_capital(val_t *value, state_t *cl) {
  const char *s       = value; // idiom for void* parameters
  struct cap_state *c = cl;    
  assert(s);
  if (isupper(*s)) {
    c->ncapitals++;
  }
}

Combination of code and state is known by two names:

Why is the state type unknown (polymorphic)?


Counting capitals, abstracted

Persistent state (between iterations): number of capitals

struct cap_state {
  int ncapitals;
}

Code that runs:

typedef void state_t;

void add_capital(val_t *value, state_t *cl) {
  const char *s       = value; // idiom for void* parameters
  struct cap_state *c = cl;    
  assert(s);
  if (isupper(*s)) {
    cl->ncapitals++;
  }
}

Combination of code and state is known by two names:

Why is the state type unknown (polymorphic)?

So we can iterate using any closure!


Creating and using the closure:

struct cap_state state = { .ncapitals = 0 };
List_map(l, add_capital, &state);

N.B. add_capital stands for a function pointer


Iteration abstraction for Hanson's Table_T

State is named cl (short for closure)

Code is named apply

Table iterator provides both keys and values:

typedef void key_t;
typedef void val_t;

typedef void state_t;

extern void Table_map(T table,
void apply(const key_t *key, val_t **value, state_t *cl),
state_t *cl);

A call to Table_map visits every key-value pair in the table.

Why is there an extra level of indirection in the value parameter?

Why not also in the key parameter?


Review: void * points to an unknown type

For our sanity, name the unknown types:

typedef void key_t;   // type parameters
typedef void val_t;

typedef void state_t; // state part of a closure

And the interface:

#define T Table_T
typedef struct T *T;

extern T      Table_new (int hint,
    int cmp(const key_t *x, const key_t *y),
    unsigned hash(const key_t *key));
extern void   Table_free(T *table);

extern int    Table_length(T table);

extern val_t *Table_put   (T table, const key_t *key, val_t *value);
extern val_t *Table_get   (T table, const key_t *key);
extern val_t *Table_remove(T table, const key_t *key);

extern void   Table_map   (T table,
    void apply(const key_t *key, val_t **value, state_t *cl),
    state_t *cl);

#undef T

Back to the beginning again

Bad Hanson! He makes us keep meaning of void in our heads!

The code, again:

#ifndef TABLE_INCLUDED
#define TABLE_INCLUDED

#define T Table_T
typedef struct T *T;

extern T    Table_new (int hint,
    int cmp(const void *x, const void *y),
    unsigned hash(const void *key));
extern void  Table_free(T *table);

extern int   Table_length(T table);

extern void *Table_put   (T table, const void *key, void *value);
extern void *Table_get   (T table, const void *key);
extern void *Table_remove(T table, const void *key);

extern void  Table_map    (T table,
    void apply(const void *key, void **value, void *cl),
    void *cl);

extern void **Table_toArray(T table, void *end);

#undef T

#endif


Back to class home page