Likewise Base Runtime Library
Hash tables

Embedded-node hash tables. More...

Data Structures

struct  PLW_HASHTABLE_NODE
 Hash table node structure. More...
 
struct  PLW_HASHTABLE_ITER
 Hash table iterator. More...
 

Macros

#define LW_HASHTABLE_ITER_INIT
 Hash table iterator initializer. More...
 

Typedefs

typedef struct _LW_HASHTABLE * PLW_HASHTABLE
 Hash table structure. More...
 
typedef struct _LW_HASHTABLE
const * 
PCLW_HASHTABLE
 
typedef LW_PCVOID(* LW_HASH_GET_KEY_FUNCTION )(PLW_HASHTABLE_NODE pNode, LW_PVOID pUserData)
 Key fetch function. More...
 
typedef LW_ULONG(* LW_HASH_DIGEST_FUNCTION )(LW_PCVOID pKey, LW_PVOID pUserData)
 Key digest function. More...
 
typedef LW_BOOLEAN(* LW_HASH_EQUAL_FUNCTION )(LW_PCVOID pKey1, LW_PCVOID pKey2, LW_PVOID pUserData)
 Key equality function. More...
 
typedef VOID(* LW_HASHNODE_FREE_FUNCTION )(PLW_HASHTABLE_NODE pNode, LW_PVOID pUserData)
 Node free function. More...
 

Functions

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...
 

Detailed Description

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:

Drawbacks:

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.

Macro Definition Documentation

#define LW_HASHTABLE_ITER_INIT

A suitable value for statically initializing #LW_HASH_ITER structures

Typedef Documentation

typedef struct _LW_HASHTABLE* PLW_HASHTABLE

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]pNodethe hash node
[in]pUserDataarbitrary 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]pKeythe key
[in]pUserDataarbitrary 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]pKey1the first key
[in]pKey2the second key
[in]pUserDataarbitrary user data
Return values
TRUEthe keys are equal
FALSEthe 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]pNodea node
[in]pUserDataarbitrary user data

Function Documentation

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 
)

Creates a new hash table with the specified callback functions and initial size.

Parameters
[out]ppTablethe created table
[in]pfnGetKeythe key fetch function
[in]pfnDigestthe key digest function
[in]pfnEqualthe key equality function
[in]pUserDataarbitrary user data to pass to callback functions
[in]ulSizethe initial size of the table
Return values
LW_STATUS_SUCCESSsuccess
LW_STATUS_INSUFFICIENT_RESOURCESout 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]pTablethe hash table
[in]pNodethe node to insert
[out]ppPrevNodeif 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]pTablethe hash table
[in]pNodethe node to insert
[out]ppPrevNodeif 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]pTablethe hash table
[in]pNodethe node to remove
Return values
LW_STATUS_SUCCESSsuccess
LW_STATUS_NOT_FOUNDthe 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]pTablethe hash table
[out]ppNodeset to the node which was found, or NULL on failure
[in]pKeythe key to search for
Return values
LW_STATUS_SUCCESSthe node was found
LW_STATUS_NOT_FOUNDno 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]pIterthe 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]pTablethe hash table
[in,out]pIteran iterator which tracks the current position in the table
Returns
the next node
VOID LwRtlHashTableClear ( LW_IN LW_OUT PLW_HASHTABLE  pTable,
LW_IN LW_HASHNODE_FREE_FUNCTION  pFree,
LW_IN LW_PVOID  pUserData 
)

Removes all nodes from the given hash table. If provided, a free function is called on each removed node.

Parameters
[in,out]pTablethe hash table
[in]pFreean optional callback to invoke on each removed node
[in]pUserDataarbitrary user data to pass to pFree
ULONG LwRtlHashTableGetSize ( LW_IN PCLW_HASHTABLE  pTable)

Returns the current size of the given hash table.

Parameters
[in]pTablethe hash table
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
[in]pTablethe hash table
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]pTablethe hash table
[in]ulSizethe new size of the table
Return values
LW_STATUS_SUCCESSsuccess
LW_STATUS_INSUFFICIENT_RESOURCESout of memory
VOID LwRtlFreeHashTable ( LW_IN LW_OUT PLW_HASHTABLE ppTable)

Frees the given hash table and sets the pointer to NULL. If *ppTable is already NULL, no action is taken.

Parameters
[in,out]ppTablehash table pointer to free and set to NULL