next up previous contents index
Next: 4.10.2 cnd Up: 4.10 Classes Previous: 4.10 Classes   Contents   Index

Subsections


4.10.1 ch

The ch class implements chained hashing. It uses a simple bucket chaining hash table implementation. Table size is set at creation time, and cannot be changed, so performance will suffer if a ch object is over-filled. The main cw_ch_t data structure and the table are contiguously allocated, which means that care must be taken when manually pre-allocating space for the structure. Each item that is inserted into the ch object is encapsulated by a chi object, for which space can optionally be passed in as a parameter to ch_insert(). If no space for the chi object is passed in, an opaque allocator function is used internally for allocation.

Multiple entries with the same key are allowed and are stored in LIFO order.

The ch class is meant to be small and simple without compromising performance. Note that it is not well suited for situations where the number of items can vary wildly; the dch class is designed for such situations.

4.10.1.1 API

uint32_t CW_CH_TABLE2SIZEOF(uint32_t a_table_size):

Input(s):
a_table_size:
Number of slots in the hash table.
Output(s):
retval:
Size of a ch object with a_table_size slots.
Exception(s):
None.
Description:
Calculate the size of a ch object with a_table_size slots.
ch_new(cw_ch_t *a_ch, cw_mema_t *a_mema, uint32_t a_table_size, cw_ch_hash_t *a_hash, cw_ch_key_comp_t *a_key_comp):

Input(s):
a_ch:
Pointer to space for a ch with a_table_size slots, or NULL. Use the CW_CH_TABLE2SIZEOF() macro to calculate the total space needed for a given table size.
a_mema:
Pointer to a memory allocator.
a_table_size:
Number of slots in the hash table.
a_hash:
Pointer to a hashing function.
a_key_comp:
Pointer to a key comparison function.
Output(s):
retval:
Pointer to a ch.
Exception(s):
CW_ONYXX_OOM.
Description:
Constructor.
void ch_delete(cw_ch_t *a_ch):

Input(s):
a_ch:
Pointer to a ch.
Output(s):
None.
Exception(s):
None.
Description:
Destructor.
uint32_t ch_count(cw_ch_t *a_ch):

Input(s):
a_ch:
Pointer to a ch.
Output(s):
retval:
Number of items in a_ch.
Exception(s):
None.
Description:
Return the number of items in a_ch.
void ch_insert(cw_ch_t *a_ch, const void *a_key, const void *a_data, cw_chi_t *a_chi):

Input(s):
a_ch:
Pointer to a ch.
a_key:
Pointer to a key.
a_data:
Pointer to data associated with a_key.
a_chi:
Pointer to space for a chi, or NULL.
Output(s):
None.
Exception(s):
CW_ONYXX_OOM.
Description:
Insert a_data into a_ch, using key a_key. Use a_chi for the internal chi container if non-NULL.
bool ch_remove(cw_ch_t *a_ch, const void *a_search_key, void **r_key, void **r_data, cw_chi_t **r_chi):

Input(s):
a_ch:
Pointer to a ch.
a_search_key:
Pointer to the key to search with.
r_key:
Pointer to a key pointer, or NULL.
r_data:
Pointer to a data pointer, or NULL.
r_chi:
Pointer to a chi pointer, or NULL.
Output(s):
retval:
false:
Success.
true:
Item with key a_search_key not found.
*r_key:
If (r_key != NULL) and (retval == false), pointer to a key. Otherwise, undefined.
*r_data:
If (r_data != NULL) and (retval == false), pointer to data. Otherwise, undefined.
*r_chi:
If (r_chi != NULL) and (retval == false), pointer to space for a chi, or NULL. Otherwise, undefined.
Exception(s):
None.
Description:
Remove the item from a_ch that was most recently inserted with key a_search_key. If successful, set *r_key and *r_data to point to the key, data, and externally allocated chi, respectively.
void ch_chi_remove(cw_ch_t *a_ch, cw_chi_t *a_chi):

Input(s):
a_ch:
Pointer to a ch.
a_chi:
Pointer to a chi.
Output(s):
None.
Exception(s):
None.
Description:
Remove the item from a_ch that was inserted using a_chi.
bool ch_search(cw_ch_t *a_ch, const void *a_key, void **r_data):

Input(s):
a_ch:
Pointer to a ch.
a_key:
Pointer to a key.
r_data:
Pointer to a data pointer, or NULL.
Output(s):
retval:
false:
Success.
true:
Item with key a_key not found in a_ch.
*r_data:
If (r_data != NULL) and (retval == false), pointer to data.
Exception(s):
None.
Description:
Search for the most recently inserted item with key a_key. If found, *r_data to point to the associated data.
uint32_t ch_string_hash(const void *a_key):

Input(s):
a_key:
Pointer to a key.
Output(s):
retval:
Hash result.
Exception(s):
None.
Description:
NULL-terminated string hashing function.
uint32_t ch_direct_hash(const void *a_key):

Input(s):
a_key:
Pointer to a key.
Output(s):
retval:
Hash result.
Exception(s):
None.
Description:
Direct (pointer) hashing function.
bool ch_string_key_comp(const void *a_k1, const void *a_k2):

Input(s):
a_k1:
Pointer to a key.
a_k2:
Pointer to a key.
Output(s):
retval:
false:
Not equal.
true:
Equal.
Exception(s):
None.
Description:
Test two keys (NULL-terminated strings) for equality.
bool ch_direct_key_comp(const void *a_k1, const void *a_k2):

Input(s):
a_k1:
Pointer to a key.
a_k2:
Pointer to a key.
Output(s):
retval:
false:
Not equal.
true:
Equal.
Exception(s):
None.
Description:
Test two keys (pointers) for equality.


next up previous contents index
Next: 4.10.2 cnd Up: 4.10 Classes Previous: 4.10 Classes   Contents   Index
Jason Evans 2005-03-16