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.
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: 4.10.2 cnd
Up: 4.10 Classes
Previous: 4.10 Classes
Contents
Index
Jason Evans
2005-03-16