Hash Tables

The utility library provides a set of functions to manage hash tables. Hash tables are key/value pairs where the location of the key is derived from the value of the key. This technique results in high performance random access. Hash tables can be created, and entries can be inserted, deleted, and traversed. Hash tables are created with these functions:

TutHashCreate — create a generic hash function based on a hash key calculation function provided.

TutHashCreateInt — create a hash table with integer keys.

TutHashCreateStr — create a hash table with string keys. These keys are case sensitive.

TutHashCreateStri — create a hash table with string keys that are not case sensitive.

TutHashCreatePtr — create a hash table with a key based on arbitrary pointer values.

When a hash table is created using TutHashCreate, two extra arguments are required: a test function and a calculation function. The test function is used to determine if two keys are equal and is defined as:

T_BOOL (*T_HASH_TEST_FUNC)(T_PTR key1, T_PTR key2);

It returns TRUE if the two keys are equal, and FALSE if they are different. The calculation function is used to calculate the hash table key for each entry in the hash table. It is defined as:

T_UINT4 (*T_HASH_CALC_FUNC) (T_PTR key);

This function returns a hash table key based on the value of the key. It is called whenever a new key/value pair is inserted into the hash table to calculate a key value, and when a lookup is performed using TutHashLookup.

The entries in a hash table are traversed using TutHashTraverse. This required traversal function is defined as:

T_PTR (*T_HASH_TRAV_FUNC)(T_PTR key, T_PTR value, T_PTR arg);

This function returns NULL to continue the traversal, and a non-null value to stop the traversal. All three arguments passed to the traversal function are of type T_PTR. They usually need to be cast to application-specific data structures.

Hash tables can also be sorted using TutHashSort. Because the order in which entries in a hash table are stored is not something you can control, it is sometimes useful to get a sorted list of these entries. TutHashSort provides this function by traversing the entries and selectively choosing the entries in the table (with the T_HASH_SORT_SELECT_FUNC), and then ordering them with the T_HASH_SORT_CMP_FUNC, both of which are provided to TutHashSort as arguments. The select function is defined as:

T_BOOL (*T_HASH_SORT_SELECT_FUNC)(T_PTR key, T_PTR value);

The select function is called for each entry of the hash table with the key and value part of the entry. This function must return TRUE if the entry is to be included, and FALSE if it is not to be selected.

T_INT4 (*T_HASH_SORT_CMP_FUNC)(T_PTR key1, T_PTR key2);

The return value of this function works like the strcmp standard library function, and returns a negative value if the first argument is before the second, a positive value (greater than zero) if the first argument is after the second, and zero if the values are equal.

Hash tables are destroyed using TutHashDestroy. This function takes a destroy function defined as:

void (*T_HASH_DESTROY_FUNC)(T_PTR key, T_PTR value, T_PTR arg);

This function is called as each entry of the hash table is destroyed, allowing the application to perform whatever cleanup, such as freeing memory, is required for that particular entry.

When the hash function is applied to a key value, an integer is returned that is used to identify the bucket that the key belongs to. When multiple keys hash to the same bucket, the individual values are stored in a list that is traversed during a look up operation. The hash table bucket data structure is an opaque data type defined as:

struct T_HASH_BUCKET_STRUCT T_HASH_BUCKET_STRUCT, *T_HASH_BUCKET;