---

Hash tables

Operations for hash tables. More...

Defines
#define	HASH_FLAG_AUTOGROW
	Flag permitting a hash table to automatically grow. More...
#define	HASH_FLAG_AUTOSHRINK
	Flag permitting a hash table to automatically shrink. More...
#define	HASH_TABLE_INIT(flags, func, comp, resize, extra)
	Hash table static initializer. More...
#define	ht_verify(table)
	Hash table verification macro. More...
#define	ht_flags(table)
	Hash table flags. More...
#define	ht_frozen(table)
	Determine if a hash table is frozen. More...
#define	ht_modulus(table)
	Hash table modulus. More...
#define	ht_count(table)
	Hash table count. More...
#define	ht_func(table)
	Hash table hash function. More...
#define	ht_comp(table)
	Hash table comparison function. More...
#define	ht_rsize(table)
	Hash table resize callback function. More...
#define	ht_extra(table)
	Extra pointer data in a hash table. More...
#define	ht_size(table)
	Hash table memory size. More...
#define	HASH_ENTRY_INIT(value)
	Hash table entry static initializer. More...
#define	he_verify(entry)
	Hash table entry verification macro. More...
#define	he_link(entry)
	Hash table entry linked list element. More...
#define	he_flags(entry)
	Hash table entry flags. More...
#define	he_table(entry)
	Hash table entry table pointer. More...
#define	he_hash(entry)
	Hash table entry hash value. More...
#define	he_key(entry)
	Hash table entry key pointer. More...
#define	he_value(entry)
	Hash table entry value pointer. More...
#define	st_rsize(table)
	Sparse matrix table resize callback function. More...
Typedefs
typedef struct _hash_table_s	hash_table_t
	Hash table. More...
typedef struct _hash_entry_s	hash_entry_t
	Hash table entry. More...
typedef unsigned long (*	hash_iter_t )(hash_table_t *, hash_entry_t *, void *)
	Hash table iteration callback. More...
typedef unsigned long (*	hash_func_t )(hash_table_t *, db_key_t *)
	Hash function callback. More...
typedef unsigned long (*	hash_comp_t )(hash_table_t *, db_key_t *, db_key_t *)
	Hash table comparison callback. More...
typedef unsigned long (*	hash_resize_t )(hash_table_t *, unsigned long)
	Hash table resize callback. More...
Functions
unsigned long	ht_init (hash_table_t *table, unsigned long flags, hash_func_t func, hash_comp_t comp, hash_resize_t resize, void *extra, unsigned long init_mod)
	Dynamically initialize a hash table. More...
unsigned long	ht_add (hash_table_t *table, hash_entry_t *entry, db_key_t *key)
	Add an entry to a hash table. More...
unsigned long	ht_move (hash_table_t *table, hash_entry_t *entry, db_key_t *key)
	Move an entry in the hash table. More...
unsigned long	ht_remove (hash_table_t *table, hash_entry_t *entry)
	Remove an element from a hash table. More...
unsigned long	ht_find (hash_table_t *table, hash_entry_t **entry_p, db_key_t *key)
	Find an entry in a hash table. More...
unsigned long	ht_iter (hash_table_t *table, hash_iter_t iter_func, void *extra)
	Iterate over each entry in a hash table. More...
unsigned long	ht_flush (hash_table_t *table, hash_iter_t flush_func, void *extra)
	Flush a hash table. More...
unsigned long	ht_resize (hash_table_t *table, unsigned long new_size)
	Resize a hash table. More...
unsigned long	ht_free (hash_table_t *table)
	Free memory used by an empty hash table. More...
unsigned long	he_init (hash_entry_t *entry, void *value)
	Dynamically initialize a hash table entry. More...

---

Detailed Description

Hash tables are a basic data structure used in building databases. Hash tables provide a means of storing data such that an arbitrary entry may be looked up efficiently. This library implements a hash table that may optionally grow and shrink to provide maximum efficiency. The implementation is with two kinds of caller-allocated structures--a hash_table_t structure that describes the table and a hash_entry_t structure for each entry in the table. The library allocates a bucket array which must be released with the ht_free() function when the hash table has been emptied. Additionally, the hash table may be manually resized with the ht_resize() function.

Entries may be added to and removed from the table using the ht_add() and ht_remove() functions. Additionally, the key on a given entry may be changed using the ht_move() function. Of course, any given entry may be looked up using the ht_find() function, and ht_iter() will execute a user-defined function for each entry in the hash table (in an unspecified order). The ht_flush() function will remove all entries from the hash table, optionally executing a user-specified clean-up function.

---

Define Documentation

#define HASH_ENTRY_INIT( value )

This macro statically initializes a hash_entry_t. Parameters: value   A pointer to void representing the object associated with the entry.

#define HASH_FLAG_AUTOGROW

If passed in to HASH_TABLE_INIT() or ht_init(), allows the hash table to grow automatically.

#define HASH_FLAG_AUTOSHRINK

If passed in to HASH_TABLE_INIT() or ht_init(), allows the hash table to shrink automatically.

#define HASH_TABLE_INIT( flags, func, comp, resize, extra )

This macro statically initializes a hash_table_t. Parameters: flags   A bit-wise OR of HASH_FLAG_AUTOGROW and HASH_FLAG_AUTOSHRINK. If neither behavior is desired, use 0. func   A hash_func_t function pointer for a hash function. comp   A hash_comp_t function pointer for a comparison function. resize   A hash_resize_t function pointer for determining whether resizing is permitted and/or for notification of the resize. extra   Extra pointer data that should be associated with the hash table.

#define he_flags( entry )

This macro retrieves a set of user-defined flags associated with the entry. It may be used as an lvalue to set those flags. Parameters: entry   A pointer to a hash_entry_t. Returns: An unsigned long containing the flags associated with the entry.

#define he_hash( entry )

This macro retrieves the hash value of the given hash entry. If the hash table has been resized, this value may not be the same as a previous value. Parameters: entry   A pointer to a hash_entry_t. Returns: An unsigned long containing the hash code for the entry.

#define he_key( entry )

This macro retrieves the key associated with the hash table entry. Parameters: entry   A pointer to a hash_entry_t. Returns: A pointer to a db_key_t.

#define he_link( entry )

This macro provides access to the linked list element buried in the hash table entry. It should *not* be used on entries currently in a hash table. The purpose of this macro is to allow an object containing a hash table entry to be placed upon a free list. Parameters: entry   A pointer to a hash_entry_t. Returns: A pointer to a link_elem_t.

#define he_table( entry )

This macro retrieves a pointer to the hash table the entry is in. Parameters: entry   A pointer to a hash_entry_t. Returns: A pointer to a hash_table_t.

#define he_value( entry )

This macro retrieves the value associated with the hash table entry. It may be treated as an lvalue to change that value. Care should be taken when using this option. Parameters: entry   A pointer to a hash_entry_t. Returns: A pointer to void representing the value associated with this entry.

#define he_verify( entry )

This macro verifies that a given pointer actually does point to a hash table entry. Parameters: entry   A pointer to a hash_entry_t. Returns: Boolean true if entry is a valid hash table entry or false otherwise.

#define ht_comp( table )

This macro retrieves the comparison function pointer. Parameters: table   A pointer to a hash_table_t. Returns: A hash_comp_t.

#define ht_count( table )

This macro retrieves the total number of items actually in the hash table. Parameters: table   A pointer to a hash_table_t. Returns: An unsigned long containing a count of the number of items in the hash table.

#define ht_extra( table )

This macro retrieves the extra pointer data associated with a particular hash table. Parameters: table   A pointer to a hash_table_t. Returns: A pointer to void.

#define ht_flags( table )

This macro retrieves the flags associated with the hash table. Only HASH_FLAG_AUTOGROW and HASH_FLAG_AUTOSHRINK have any meaning to the application; all other bits are reserved for use in the library. This macro may be used as an lvalue, but care must be taken to avoid modifying the library-specific bits. Parameters: table   A pointer to a hash_table_t. Returns: An unsigned long containing the flags for the hash table.

#define ht_frozen( table )

This macro returns a non-zero value if the table is currently frozen. The hash table may be frozen if there is an iteration in progress. Parameters: table   A pointer to a hash_table_t. Returns: A zero value if the table is not frozen or a non-zero value if the table is frozen.

#define ht_func( table )

This macro retrieves the hash function pointer. Parameters: table   A pointer to a hash_table_t. Returns: A hash_func_t.

#define ht_modulus( table )

This macro retrieves the number of buckets allocated for the hash table. An application may wish to save this value between invocations to avoid the overhead of growing the table while filling it with data. Parameters: table   A pointer to a hash_table_t. Returns: An unsigned long containing the number of buckets allocated for the hash table.

#define ht_rsize( table )

This macro retrieves the resize callback function pointer. Parameters: table   A pointer to a hash_table_t. Returns: A hash_resize_t.

#define ht_size( table )

This macro returns the physical size of the bucket array allocated by the library for this hash table. Parameters: table   A pointer to a hash_table_t. Returns: A size_t.

#define ht_verify( table )

This macro verifies that a given pointer actually does point to a hash table. Parameters: table   A pointer to a hash_table_t. Returns: Boolean true if table is a valid hash table or false otherwise.

#define st_rsize( table )

This macro retrieves the resize callback function pointer. Parameters: table   A pointer to a smat_table_t. Returns: A smat_resize_t.

---

Typedef Documentation

typedef unsigned long(* hash_comp_t)(hash_table_t *, db_key_t *, db_key_t *)

This function pointer references a callback used to compare entries in a hash table. It should return 0 for identical entries and non-zero otherwise. No assumptions should be made about the order in which the two keys are passed to this function.

typedef struct _hash_entry_s hash_entry_t

This structure represents a single entry of a hash table.

typedef unsigned long(* hash_func_t)(hash_table_t *, db_key_t *)

This function is associated with a hash table, and is responsible for generating a hash value. The full 32-bit range of an unsigned long should be used--do *not* reduce the hash value by the modulus of the hash table.

typedef unsigned long(* hash_iter_t)(hash_table_t *, hash_entry_t *, void *)

This function pointer references a callback used by ht_iter() and ht_flush(). It should return 0 for success. A non-zero return value will terminate the operation and will become the return value of the ht_iter() or ht_flush() call.

typedef unsigned long(* hash_resize_t)(hash_table_t *, unsigned long)

This function pointer references a callback that will be called with both the old and new hash table sizes whenever a hash table is resized. It should return non-zero only when the resize should be inhibited.

typedef struct _hash_table_s hash_table_t

This structure is the basis of all hash tables maintained by this library.

---

Function Documentation

unsigned long he_init ( hash_entry_t * entry, void * value )

This function dynamically initializes a hash table entry. Parameters: entry   A pointer to a hash_entry_t to be initialized. value   A pointer to void which will be the value of the hash table entry. Return values: DB_ERR_BADARGS   A NULL pointer was passed for entry.

unsigned long ht_add ( hash_table_t * table, hash_entry_t * entry, db_key_t * key )

This function adds an entry to a hash table. Parameters: table   A pointer to a hash_table_t. entry   A pointer to a hash_entry_t to be added to the table. key   A pointer to a db_key_t containing the key for the entry. Return values: DB_ERR_BADARGS   An invalid argument was given. DB_ERR_BUSY   The entry is already in a table. DB_ERR_FROZEN   The table is currently frozen. DB_ERR_NOTABLE   The bucket table has not been allocated and automatic growth is not enabled. DB_ERR_DUPLICATE   The entry is a duplicate of an existing entry. DB_ERR_UNRECOVERABLE   An unrecoverable error occurred while resizing the table.

unsigned long ht_find ( hash_table_t * table, hash_entry_t ** entry_p, db_key_t * key )

This function looks up an entry matching the given key. Parameters: table   A pointer to a hash_table_t. entry_p   A pointer to a pointer to a hash_entry_t. This is a result parameter. If NULL is passed, the lookup will be performed and an appropriate error code returned. key   A pointer to a db_key_t describing the item to find. Return values: DB_ERR_BADARGS   An argument was invalid. DB_ERR_NOENTRY   No matching entry was found.

unsigned long ht_flush ( hash_table_t * table, hash_iter_t flush_func, void * extra )

This function flushes a hash table--that is, it removes each entry from the table. If a flush_func is specified, it will be called on the entry after it has been removed from the table, and may safely call free(). Parameters: table   A pointer to a hash_table_t. flush_func   A pointer to a callback function used to perform user-specified actions on an entry after removing it from the table. May be NULL. See the documentation for hash_iter_t for more information. extra   A void pointer that will be passed to flush_func. Return values: DB_ERR_BADARGS   An argument was invalid. DB_ERR_FROZEN   The hash table is frozen.

unsigned long ht_free ( hash_table_t * table )

This function releases the memory used by the bucket table in an empty hash table. Parameters: table   A pointer to a hash_table_t. Return values: DB_ERR_BADARGS   An invalid argument was given. DB_ERR_FROZEN   The table is frozen. DB_ERR_NOTEMPTY   The table is not empty.

unsigned long ht_init ( hash_table_t * table, unsigned long flags, hash_func_t func, hash_comp_t comp, hash_resize_t resize, void * extra, unsigned long init_mod )

This function dynamically initializes a hash table. Parameters: table   A pointer to a hash_table_t to be initialized. flags   A bit-wise OR of HASH_FLAG_AUTOGROW and HASH_FLAG_AUTOSHRINK. If neither behavior is desired, use 0. func   A hash_func_t function pointer for a hash function. comp   A hash_comp_t function pointer for a comparison function. resize   A hash_resize_t function pointer for determining whether resizing is permitted and/or for notification of the resize. extra   Extra pointer data that should be associated with the hash table. init_mod   An initial modulus for the table. This will presumably be extracted by ht_modulus() in a previous invocation of the application. A 0 value is valid. Return values: DB_ERR_BADARGS   An invalid argument was given. ENOMEM   Unable to allocate memory.

unsigned long ht_iter ( hash_table_t * table, hash_iter_t iter_func, void * extra )

This function iterates over every entry in a hash table (in an unspecified order), executing the given iter_func on each entry. Parameters: table   A pointer to a hash_table_t. iter_func   A pointer to a callback function used to perform user-specified actions on an entry in a hash table. NULL is an invalid value. See the documentation for hash_iter_t for more information. extra   A void pointer that will be passed to iter_func. Return values: DB_ERR_BADARGS   An argument was invalid. DB_ERR_FROZEN   The hash table is frozen.

unsigned long ht_move ( hash_table_t * table, hash_entry_t * entry, db_key_t * key )

This function moves an existing entry in the hash table to correspond to the new key. Parameters: table   A pointer to a hash_table_t. entry   A pointer to a hash_entry_t to be moved. It must already be in the hash table. key   A pointer to a db_key_t describing the new key for the entry. Return values: DB_ERR_BADARGS   An invalid argument was given. DB_ERR_UNUSED   Entry is not in a hash table. DB_ERR_WRONGTABLE   Entry is not in this hash table. DB_ERR_FROZEN   Hash table is frozen. DB_ERR_DUPLICATE   New key is a duplicate of an existing key. DB_ERR_READDFAILED   Unable to re-add entry to table.

unsigned long ht_remove ( hash_table_t * table, hash_entry_t * entry )

This function removes the given element from the specified hash table. Parameters: table   A pointer to a hash_table_t. entry   A pointer to a hash_entry_t to be removed from the table. Return values: DB_ERR_BADARGS   An invalid argument was given. DB_ERR_UNUSED   Entry is not in a hash table. DB_ERR_WRONGTABLE   Entry is not in this hash table. DB_ERR_FROZEN   Hash table is frozen. DB_ERR_UNRECOVERABLE   An unrecoverable error occurred while resizing the table.

unsigned long ht_resize ( hash_table_t * table, unsigned long new_size )

This function resizes a hash table to the given new_size. If new_size is 0, then an appropriate new size based on the current number of items in the hash table will be selected. Parameters: table   A pointer to a hash_table_t. new_size   A new size value for the table. Return values: DB_ERR_BADARGS   An argument was invalid. DB_ERR_FROZEN   The table is currently frozen. DB_ERR_UNRECOVERABLE   A catastrophic error was encountered. The table is now unusable. ENOMEM   No memory could be allocated for the new bucket table.

---