ihash

The Engine Internals: Hash Tables

This module provides simple, fixed-size hash tables.

Data Structures

:::C
typedef struct _hashnode_t {
    node_t      node;
    size_t      key_len;
    void*       key;
    void*       data;
} hashnode_t;

The hash node is the hash entry data structure. Nodes with the same hash value are linked in lists. See [ilists].

The hash node consists of a node_t for linkage, a binary string as a key, which can be anything, and an arbitrary non-null data pointer supplied by the user.

:::C
#define HTSIZE  16384U

typedef struct _hash_t {
    list_t      lists[HTSIZE];
} hash_t;

A hash table consists of HTSIZE (16384) lists. This means, the hash value must be between 0 and HTSIZE-1U. Nodes with the same hash value are grouped in lists. See [ilists].

Functions

:::C
void initHash( hash_t* h );

Initializes the hash table by initializing all the lists.

:::C
void cleanupHash( hash_t* h );

Cleans up the hash table by erasing all hashnodes from it.

:::C
hashnode_t* createHashNode( const void* key, size_t keysz, void* data );

Creates a new hash node.

:::C
void deleteHashNode( hashnode_t* n );

Deletes a hash node. Removes it from its list, if it was in a list.

:::C
size_t computeHashValue( const void* key, size_t keysz );

Computes a hash value for a given key.

:::C
hashnode_t* findInHash_HK( hash_t* h, size_t hashval, const void* key, 
    size_t keysz );

Finds a hash node given a hash value and a key. Returns 0 if not found.

:::C
hashnode_t* findInHash_K( hash_t* h, const void* key, size_t keysz );

Finds a hash node given a key. Returns 0 if not found.

:::C
void enterIntoHash_HN( hash_t* h, size_t hashval, hashnode_t* n );

Enter a hash node into a hash table given a hash value and a node.

:::C
void* findInHash_DHK( hash_t* h, size_t hashval, const void* key, 
    size_t keysz );

Finds a hash node's data pointer given a hash value and a key. Returns 0 if not found.

:::C
void* findInHash_DK( hash_t* h, const void* key, size_t keysz );

Finds a hash node's data pointer given a key. Returns 0 if not found.

:::C
void enterIntoHash_DHK( hash_t* h, void* data, size_t hashval, 
    const void* key, size_t keysz );

Enter a hash node into a hash table given a non-null data pointer, a hash value and a key.

:::C
void enterIntoHash_DK( hash_t* h, void* data, const void* key, 
    size_t keysz );

Enter a hash node into a hash table given a non-null data pointer and a key.

---

See Also

[ilists] -- Lists

---

Project Admins:

• Ekkehard Morgenstern