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:
Namespace of typedefs vs namespace of structure tags
An incomplete structure type
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:
void
always stands for an unknown type
in practice, we are limited to pointer types
pointer types are convenient because we always have NULL
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?
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
Code
State, both mutable and immutable
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)
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:
Function closure or simply "closure"
"Object" (with at least one "method" or "member function")
Why is the state type unknown (polymorphic)?
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:
Function closure or simply "closure"
"Object" (with at least one "method" or "member function")
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
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?
void *
points to an unknown typeFor 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
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