8. Generic Hash Table

This is a reasonably high performance hash table implementation. The API is provided in two layers: one layer specialised for storing strings, and a more abstract layer where the management of keys is under user specified control.

The functionality described here is defined in the header file hashtable.h.

8.1. High Level API

The simple API consists of the following.

struct hash_table

This is an opaque type representing a hash table. A hash_table can be created by calling hash_table_create() or hash_table_create_generic(), and should be deleted, if required, by calling hash_table_destroy().

struct hash_table *hash_table_create(bool copy_keys)

This creates an empty hash table for storing string to void * mappings. If copy_keys is false then keys must have lifetime at least equal to that of the associated value, otherwise every inserted key will be copied and the hash table will manage the lifetime of the copy.

void hash_table_destroy(struct hash_table *table)

Releases all resources associated with the hash table. If keys are under hash table control they will be released.

void *hash_table_insert(struct hash_table *table, const void *key, void *value)

Inserts mapping from key to value in table. If an existing value is replaced it is returned, otherwise NULL is returned.

void *hash_table_lookup(struct hash_table *table, const void *key)

bool hash_table_lookup_bool(struct hash_table *table, const void *key, void **value)

Looks up key in table and returns the value or NULL if not found. If it is possible for the associated value to be NULL then hash_table_lookup_bool() can be used to check whether the value is present; in this case the value is returned in *value.

void *hash_table_delete(struct hash_table *table, const void *key)

Deletes entry associated with key from table, returns the deleted entry if found, otherwise returns NULL.

size_t hash_table_count(struct hash_table *table)

Returns the number of entris in table.

void hash_table_resize(struct hash_table *table, size_t min_size)

The hash table will automatically resize itself as necessary as entries are added, but it is not normally resized after entries are deleted, though this can happen as a consequence of subsequent entries. This function will forcibly resize table to have at least min_size entries (plus room).

bool hash_table_walk(struct hash_table *table, int *ix, const void **key, void **value)

This function is used to iterate through all of the entries in the table. Note that table must not be modified during the iteration, as otherwise entries may be skipped or repeated. The following code will walk the given table calling the given function for each key & value pair in turn:

const void *key;
const void *value;
int ix = 0;
while (hash_table_walk(table, &ix, &key, &value))
    process_entry(key, value);

Actually, it probably is safe to delete entries during a walk, but this is not guaranteed without close inspection of the code!

void hash_table_validate(struct hash_table *table)

This performs a sanity check on the structure of table and raised an assertion failure if the check fails.

8.2. Abstract API

The fuller API including the more abstract layer adds the following.

struct hash_table *hash_table_create_ptrs(void)

Creates a hash table with pointers or integers (of uintptr_t compatible size) as keys. In this case keys are never copied.

struct hash_table *hash_table_create_generic(const struct hash_table_ops *ops)

This constructs an empty hash table using given ops structure to define the handling of keys. The ops structure must have lifetime at least equal to that of the created table.

hash_t

This is an alias for unsigned long int. All hash functions use this type.

struct hash_table_ops

This structure contains the following fields defining the abstract interface to keys.

hash_t (*hash)(const void *key)

Computes the hash value from a key.

bool (*compare)(const void *key1, const void *key2)

Compares two keys, returns true if equal.

void *(*copy_key)(const void *key)

If NULL then key lifetime is under control of the user of the hash table, who must ensure that the key is valid for the entire time it is present in the table. Otherwise this function is called when keys are added to the table.

void (*release_key)(void *key)

Also can be NULL if key lifetime is under user control, otherwise is called when keys are removed from the table.

Note that value lifetime is not automatically managed through this interface, instead this can be done through the return values from hash_table_insert() and hash_table_delete().