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

Subsections


4.10.3 dch

The dch class implements dynamic chained hashing. The dch class is a wrapper around the ch class that enforces fullness/emptiness constraints and rebuilds the hash table when necessary. Other than this added functionality, the dch class behaves almost exactly like the ch class. See the ch class documentation for additional information.

4.10.3.1 API

dch_new(cw_dch_t *a_dch, cw_mema_t *a_mema, uint32_t a_base_table, uint32_t a_base_grow, uint32_t a_base_shrink, cw_ch_hash_t *a_hash, cw_ch_key_comp_t *a_key_comp):

Input(s):
a_dch:
Pointer to space for a dch, or NULL.
a_mema:
Pointer to a memory allocator.
a_base_table:
Number of slots in the initial hash table.
a_base_grow:
Maximum number of items to allow in a_dch before doubling the hash table size. The same proportions (in relation to a_base_table) are used to decide when to double the table additional times.
a_base_shrink:
Minimum proportional (with respect to a_base_table) emptiness to allow in the hash table before cutting the hash table size in half.
a_hash:
Pointer to a hashing function.
a_key_comp:
Pointer to a key comparison function.
Output(s):
retval:
Pointer to a dch.
Exception(s):
CW_ONYXX_OOM.
Description:
Constructor.
void dch_delete(cw_dch_t *a_dch):

Input(s):
a_dch:
Pointer to a dch.
Output(s):
None.
Exception(s):
None.
Description:
Destructor.
uint32_t dch_count(cw_dch_t *a_dch):

Input(s):
a_dch:
Pointer to a dch.
Output(s):
retval:
Number of items in a_dch.
Exception(s):
None.
Description:
Return the number of items in a_dch.
bool dch_shrinkable_get(cw_dch_t *a_dch):

Input(s):
a_dch:
Pointer to a dch.
Output(s):
retval:
true:
a_dch is currently shrinkable (initial default).
false:
a_dch is not currently shrinkable, so no attempt will be made to shrink the hash table in dch_remove() or dch_remove_iterate().
Exception(s):
None.
Description:
Return whether a_dch is currently shrinkable.
void dch_shrinkable_set(cw_dch_t *a_dch, bool a_shrinkable):

Input(s):
a_dch:
Pointer to a dch.
a_shrinkable:
true:
Set a_dch to be shrinkable.
false:
Set a_dch to not be shrinkable. No attempt will be made to shrink the hash table in dch_remove() or dch_remove_iterate() while in this state.
Output(s):
None.
Exception(s):
None.
Description:
Set whether a_dch should try to shrink the hash table in dch_remove() and dch_remove_iterate().
void dch_insert(cw_dch_t *a_dch, const void *a_key, const void *a_data, cw_chi_t *a_chi):

Input(s):
a_dch:
Pointer to a dch.
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_dch, using key a_key. Use a_chi for the internal chi container if non-NULL.
bool dch_remove(cw_dch_t *a_dch, const void *a_search_key, void **r_key, void **r_data, cw_chi_t **r_chi):

Input(s):
a_dch:
Pointer to a dch.
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_dch 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.
bool dch_chi_remove(cw_dch_t *a_dch, cw_chi_t *a_chi):

Input(s):
a_dch:
Pointer to a dch.
a_chi:
Pointer to a chi.
Output(s):
None.
Exception(s):
None.
Description:
Remove the item from a_dch that was inserted using a_chi.
bool dch_search(cw_dch_t *a_dch, const void *a_key, void **r_data):

Input(s):
a_dch:
Pointer to a dch.
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_dch.
*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.


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