Embedded-node hash tables.
More...
|
LW_NTSTATUS | LwRtlCreateHashTable (LW_OUT PLW_HASHTABLE *ppTable, LW_IN LW_HASH_GET_KEY_FUNCTION pfnGetKey, LW_IN LW_HASH_DIGEST_FUNCTION pfnDigest, LW_IN LW_HASH_EQUAL_FUNCTION pfnEqual, LW_IN LW_OPTIONAL LW_PVOID pUserData, LW_IN LW_ULONG ulSize) |
| Create a hash table. More...
|
|
VOID | LwRtlHashTableInsert (LW_IN LW_OUT PLW_HASHTABLE pTable, LW_IN PLW_HASHTABLE_NODE pNode, LW_OUT LW_OPTIONAL PLW_HASHTABLE_NODE *ppPrevNode) |
| Insert node into table. More...
|
|
VOID | LwRtlHashTableResizeAndInsert (LW_IN LW_OUT PLW_HASHTABLE pTable, LW_IN PLW_HASHTABLE_NODE pNode, LW_OUT LW_OPTIONAL PLW_HASHTABLE_NODE *ppPrevNode) |
| Insert node into table with automatic resizing. More...
|
|
LW_NTSTATUS | LwRtlHashTableRemove (LW_IN LW_OUT PLW_HASHTABLE pTable, LW_IN PLW_HASHTABLE_NODE pNode) |
| Remove node from table. More...
|
|
LW_NTSTATUS | LwRtlHashTableFindKey (LW_IN PCLW_HASHTABLE pTable, LW_OUT LW_OPTIONAL PLW_HASHTABLE_NODE *ppNode, LW_IN LW_PCVOID pKey) |
| Find node by key. More...
|
|
VOID | LwRtlHashTableResetIter (LW_OUT PLW_HASHTABLE_ITER pIter) |
| Reset hash table iterator. More...
|
|
PLW_HASHTABLE_NODE | LwRtlHashTableIterate (LW_IN PCLW_HASHTABLE pTable, LW_IN LW_OUT PLW_HASHTABLE_ITER pIter) |
| Iterate over nodes. More...
|
|
VOID | LwRtlHashTableClear (LW_IN LW_OUT PLW_HASHTABLE pTable, LW_IN LW_HASHNODE_FREE_FUNCTION pFree, LW_IN LW_PVOID pUserData) |
| Clear hash table. More...
|
|
ULONG | LwRtlHashTableGetSize (LW_IN PCLW_HASHTABLE pTable) |
| Query hash table size. More...
|
|
ULONG | LwRtlHashTableGetCount (LW_IN PCLW_HASHTABLE pTable) |
| Query hash table node countsize. More...
|
|
LW_NTSTATUS | LwRtlHashTableResize (LW_IN LW_OUT PLW_HASHTABLE pTable, LW_ULONG ulSize) |
| Resize hash table. More...
|
|
VOID | LwRtlFreeHashTable (LW_IN LW_OUT PLW_HASHTABLE *ppTable) |
| Free hash table. More...
|
|
The RTL hash table API provides a chained hash table implementation with hash chain nodes which are embedded directly into the user's data structures. This allows insertions and removals without allocating or freeing additional memory, which comes with several benefits:
- Insertions are guaranteed to succeed (no out-of-memory errors)
- Better cache locality because hash chain nodes are contiguous in memory with inserted elements
- Reduced memory overhead due to fewer discrete allocations
- Better performance when repeatedly inserting and removing the same elements since no malloc/free calls are necessary
Drawbacks:
- Not as intuitive to use as a hash map
- The structure to insert must contain its own key
- A structure can only be inserted into X tables at a time, where X is the number of node fields in the structure.
To use this API, add a LW_HASHTABLE_NODE field to your structure and insert a pointer to the field into your table. When given a node pointer, you can recover your original structure with #LW_STRUCT_FROM_FIELD(pNode, StructName, NodeFieldName). In addition to the usual digest and equality callback functions, you will need to provide a "get key" function that takes a node and returns the key from your structure.
If you need to insert your structure into multiple tables simultaneously, you will need a separate node field for each table.
If you don't care about the insertion guarantees or performance benefits and want to use an easier API, use Hash maps.
#define LW_HASHTABLE_ITER_INIT |
A suitable value for statically initializing #LW_HASH_ITER structures
An opaque hash table structure
typedef LW_PCVOID(* LW_HASH_GET_KEY_FUNCTION)(PLW_HASHTABLE_NODE pNode, LW_PVOID pUserData) |
A callback function that returns the key associated with a hash table node.
- Parameters
-
[in] | pNode | the hash node |
[in] | pUserData | arbitrary user data |
- Returns
- a constant pointer to the key
typedef LW_ULONG(* LW_HASH_DIGEST_FUNCTION)(LW_PCVOID pKey, LW_PVOID pUserData) |
A callback function that returns a digested form of a key
- Parameters
-
[in] | pKey | the key |
[in] | pUserData | arbitrary user data |
- Returns
- a suitable digest
typedef LW_BOOLEAN(* LW_HASH_EQUAL_FUNCTION)(LW_PCVOID pKey1, LW_PCVOID pKey2, LW_PVOID pUserData) |
A callback function which determines if two keys are equal
- Parameters
-
[in] | pKey1 | the first key |
[in] | pKey2 | the second key |
[in] | pUserData | arbitrary user data |
- Return values
-
TRUE | the keys are equal |
FALSE | the keys are not equal |
typedef VOID(* LW_HASHNODE_FREE_FUNCTION)(PLW_HASHTABLE_NODE pNode, LW_PVOID pUserData) |
A callback function used by LwRtlHashTableClear() to optionally free any nodes cleared from the table.
- Parameters
-
[in] | pNode | a node |
[in] | pUserData | arbitrary user data |
Creates a new hash table with the specified callback functions and initial size.
- Parameters
-
[out] | ppTable | the created table |
[in] | pfnGetKey | the key fetch function |
[in] | pfnDigest | the key digest function |
[in] | pfnEqual | the key equality function |
[in] | pUserData | arbitrary user data to pass to callback functions |
[in] | ulSize | the initial size of the table |
- Return values
-
LW_STATUS_SUCCESS | success |
LW_STATUS_INSUFFICIENT_RESOURCES | out of memory |
VOID LwRtlHashTableInsert |
( |
LW_IN LW_OUT PLW_HASHTABLE |
pTable, |
|
|
LW_IN PLW_HASHTABLE_NODE |
pNode, |
|
|
LW_OUT LW_OPTIONAL PLW_HASHTABLE_NODE * |
ppPrevNode |
|
) |
| |
Inserts a node into the hash table, potentially replacing an existing node with the same key.
- Parameters
-
[in,out] | pTable | the hash table |
[in] | pNode | the node to insert |
[out] | ppPrevNode | if provided, set to the node which was kicked out of the table or NULL if no node was evicted |
VOID LwRtlHashTableResizeAndInsert |
( |
LW_IN LW_OUT PLW_HASHTABLE |
pTable, |
|
|
LW_IN PLW_HASHTABLE_NODE |
pNode, |
|
|
LW_OUT LW_OPTIONAL PLW_HASHTABLE_NODE * |
ppPrevNode |
|
) |
| |
Identical to LwRtlHashTableInsert(), but first attempts to resize the table if the load factor exceeds some threshold (currently hard-coded at 80%) by calling LwRtlHashTableResize(). If the resize attempt fails, the node is inserted anyway.
- Parameters
-
[in,out] | pTable | the hash table |
[in] | pNode | the node to insert |
[out] | ppPrevNode | if provided, set to the node which was kicked out of the table or NULL if no node was evicted |
LW_NTSTATUS LwRtlHashTableRemove |
( |
LW_IN LW_OUT PLW_HASHTABLE |
pTable, |
|
|
LW_IN PLW_HASHTABLE_NODE |
pNode |
|
) |
| |
Removes the specified node from the table.
- Parameters
-
[in,out] | pTable | the hash table |
[in] | pNode | the node to remove |
- Return values
-
LW_STATUS_SUCCESS | success |
LW_STATUS_NOT_FOUND | the specified node was not present in the table |
LW_NTSTATUS LwRtlHashTableFindKey |
( |
LW_IN PCLW_HASHTABLE |
pTable, |
|
|
LW_OUT LW_OPTIONAL PLW_HASHTABLE_NODE * |
ppNode, |
|
|
LW_IN LW_PCVOID |
pKey |
|
) |
| |
Finds a node in a hash table by the specified key.
- Parameters
-
[in] | pTable | the hash table |
[out] | ppNode | set to the node which was found, or NULL on failure |
[in] | pKey | the key to search for |
- Return values
-
LW_STATUS_SUCCESS | the node was found |
LW_STATUS_NOT_FOUND | no node with the specified key was found |
VOID LwRtlHashTableResetIter |
( |
LW_OUT PLW_HASHTABLE_ITER |
pIter | ) |
|
Resets the specified hash table iterator to the start of the table.
- Parameters
-
[out] | pIter | the iterator to reset |
PLW_HASHTABLE_NODE LwRtlHashTableIterate |
( |
LW_IN PCLW_HASHTABLE |
pTable, |
|
|
LW_IN LW_OUT PLW_HASHTABLE_ITER |
pIter |
|
) |
| |
Returns the next node in the table, or NULL if the end of the table has been reached for the given iterator.
- Warning
- This function has undefined behavior if the table is modified in any way during iteration, with the following exception: a node just returned by this function may be safely removed with LwRtlHashTableRemove() as long as no other iterator is in active use for the given hash table.
- Parameters
-
[in] | pTable | the hash table |
[in,out] | pIter | an iterator which tracks the current position in the table |
- Returns
- the next node
Removes all nodes from the given hash table. If provided, a free function is called on each removed node.
- Parameters
-
[in,out] | pTable | the hash table |
[in] | pFree | an optional callback to invoke on each removed node |
[in] | pUserData | arbitrary user data to pass to pFree |
ULONG LwRtlHashTableGetSize |
( |
LW_IN PCLW_HASHTABLE |
pTable | ) |
|
Returns the current size of the given hash table.
- Parameters
-
- Returns
- the current size of the table
ULONG LwRtlHashTableGetCount |
( |
LW_IN PCLW_HASHTABLE |
pTable | ) |
|
Returns the current count of nodes in the the given hash table.
- Parameters
-
- Returns
- the current number of nodes in the table
LW_NTSTATUS LwRtlHashTableResize |
( |
LW_IN LW_OUT PLW_HASHTABLE |
pTable, |
|
|
LW_ULONG |
ulSize |
|
) |
| |
Resizes the specified table, rehashing all present nodes. This can be an expensive operation for a large table.
- Parameters
-
[in,out] | pTable | the hash table |
[in] | ulSize | the new size of the table |
- Return values
-
LW_STATUS_SUCCESS | success |
LW_STATUS_INSUFFICIENT_RESOURCES | out of memory |
Frees the given hash table and sets the pointer to NULL. If *ppTable is already NULL, no action is taken.
- Parameters
-
[in,out] | ppTable | hash table pointer to free and set to NULL |