TscHash

TscHash

TscHash is a generic chained hash-table library for C. It stores application-supplied key and element pointers while keeping the bucket table, chaining information, node allocation details, and hash-table management private.

The API is designed to follow the same general style as the other TSC support libraries, including TscList and TscTree.

Features

Public Objects

The hash table itself is opaque:

typedef struct TscHash TscHash;

A hash node exposes only the application data:

typedef struct TscHashNode
{
    void *key;
    void *element;
} TscHashNode;

Bucket linkage, ownership information, stored hash values, bucket indexes, and pool-management fields are private implementation details.

Applications may read node->key and node->element. The key should not be changed directly because doing so could invalidate the node’s position in the hash table.

Creating a Hash Table

A hash table requires both a hash callback and a key comparison callback:

size_t hashFunction(const void *key);

int compare(const void *key1, const void *key2);

The hash callback computes a size_t hash value from a key.

The comparison callback returns:

Keys that compare equal must produce the same hash value. The hash and comparison callbacks therefore form a matched pair.

For example:

static size_t hashInt(const void *key)
{
    unsigned int value =
        (unsigned int)*(const int *)key;

    return (size_t)value;
}

static int compareInt(const void *a, const void *b)
{
    int av = *(const int *)a;
    int bv = *(const int *)b;

    return (av > bv) - (av < bv);
}

Create the hash table with:

TscHash *hash =
    tscHashCreate(hashInt, compareInt, freeKey, freeElement);

The key and element free callbacks are optional and may independently be NULL.

This is useful when, for example, the key points into storage owned by the element. In that case the key free callback can be NULL and the element callback can release the complete object.

The library also provides matched hash and comparison functions for common key types, so applications normally do not need to write callbacks for those types.

For example, a hash table using NUL-terminated string keys can be created with:

TscHash *hash =
    tscHashCreate(
        tscHashString,
        tscHashCompareString,
        freeKey,
        freeElement);

Node Allocation

Hash nodes are allocated internally in blocks rather than with a separate malloc() for every node.

The default block size is:

TSC_HASH_DEFAULT_BLOCK_NODES

which is currently 64 nodes.

An application that knows its expected usage may change the block size before the first node block is allocated:

tscHashSetBlockSize(hash, 256);

Once the first node block has been allocated, the block size is locked for the lifetime of the hash table.

tscHashClear() returns nodes to the hash table’s internal free pool and retains the allocated blocks for reuse.

Bucket Allocation and Growth

The bucket table is allocated independently from the node blocks.

The default initial bucket count is:

TSC_HASH_DEFAULT_BUCKETS

which is currently 64 buckets.

The bucket count is maintained as a power of two.

The table automatically grows before an insertion would cause the load factor to exceed 75 percent. When automatic growth is required, the bucket count is doubled and the active nodes are rehashed into the new bucket table.

Rehashing does not change the application key or element pointers and does not require allocating new hash nodes.

Because rehashing may change bucket placement, applications must not depend on hash enumeration order remaining unchanged after the bucket table is resized.

Reserving Capacity

An application that knows approximately how many entries it expects can reserve bucket capacity in advance:

tscHashReserve(hash, expectedElements);

The library ensures that sufficient buckets are available for at least the requested number of elements without exceeding the normal 75 percent growth threshold.

For example:

tscHashReserve(hash, 10000);

may be useful before loading a large known data set because it can avoid several intermediate bucket-table reallocations and rehash operations.

tscHashReserve() may be called before or after entries have been inserted.

It never shrinks the table.

Calling:

tscHashReserve(hash, 0);

is permitted and succeeds without allocating a bucket table.

Inserting Nodes

Insert a key and element with:

TscHashNode *node =
    tscHashInsert(hash, key, element);

Keys must not be NULL. Elements may be NULL.

Duplicate keys are rejected with:

TSC_HASH_ERROR_DUPLICATE_KEY

A duplicate is determined using both the configured hash and comparison functions.

Successful insertion may cause the bucket table to be allocated or enlarged.

Finding Nodes

Find a node by key with:

TscHashNode *node =
    tscHashFind(hash, key);

If an equal key is present, the corresponding node is returned.

If no matching key exists, NULL is returned. This is a normal search result and does not set a NOT_FOUND error.

The key passed to tscHashFind() does not need to be the same pointer as the stored key. It only needs to produce the same hash value and compare equal according to the configured callbacks.

Enumeration

The first active node is available with:

TscHashNode *node = tscHashFirst(hash);

The remaining nodes can be enumerated with:

for (node = tscHashFirst(hash);
     node != NULL;
     node = tscHashNext(node))
{
    /* use node->key and node->element */
}

Every active node is returned once.

Hash enumeration order is unspecified. It is not sorted, stable, or semantically significant.

The order is determined by the current bucket layout and collision chains and may change when the bucket table is resized.

Applications should therefore use enumeration only when the order of the entries does not matter.

Walking the Hash Table

The library can walk every active node using a callback:

typedef int (*TscHashWalkFunction)(
    TscHashNode *node,
    void *context);

Call:

tscHashWalk(hash, callback, context);

The callback returns zero to continue or nonzero to stop the walk successfully.

The library determines the next node before calling the callback. This means the callback may safely delete the current node.

Deleting or modifying unrelated nodes during the walk is not supported.

As with direct enumeration, callback order is unspecified and must not be treated as meaningful.

Replace and Upsert

tscHashReplace() replaces an existing entry:

node = tscHashReplace(hash, newKey, newElement);

The replacement key must identify an existing entry according to the configured hash and comparison callbacks.

Both the key pointer and element pointer are replaced.

The configured free callbacks are invoked for the old key and element after the replacement has been installed.

The implementation reuses the existing internal node, so replacing an existing entry does not require allocating another node.

If no matching entry exists, the operation fails with:

TSC_HASH_ERROR_NOT_FOUND

tscHashUpsert() combines insert and replace:

node = tscHashUpsert(hash, key, element);

If the key does not exist, it is inserted. If an equal key already exists, the existing entry is replaced.

Removing and Deleting

A remove operation removes an entry from the hash table without calling the configured free callbacks:

TscHashStatus status =
    tscHashRemove(hash, node, &key, &element);

or:

TscHashStatus status =
    tscHashRemoveKey(hash, searchKey, &key, &element);

This transfers responsibility for the returned key and element pointers back to the application.

Either output pointer may be NULL if the application does not need that value.

A delete operation removes the entry and invokes the configured free callbacks:

tscHashDelete(hash, node);

or:

tscHashDeleteKey(hash, searchKey);

Attempting to remove or delete a node that belongs to another hash table fails with:

TSC_HASH_ERROR_WRONG_HASH

Clearing and Destroying

To empty a hash table while retaining its allocated node blocks and current bucket table:

tscHashClear(hash);

The configured key and element free callbacks are invoked for all active entries.

The node blocks remain allocated and their nodes are returned to the internal free pool for reuse.

The bucket table also remains allocated, allowing a cleared hash table to be reused without returning to its original bucket capacity.

To destroy the complete hash table:

tscHashDestroy(hash);

This deletes all remaining entries, invokes the configured callbacks, releases the node blocks, releases the bucket table, and releases the hash object.

Passing NULL to tscHashDestroy() is permitted.

Statistics

The current number of active entries is returned by:

size_t count = tscHashCount(hash);

The current number of allocated buckets is returned by:

size_t buckets = tscHashBucketCount(hash);

A newly created hash table may have zero buckets because the initial bucket table is allocated when it is first needed.

The number of buckets currently containing at least one entry is returned by:

size_t used = tscHashUsedBuckets(hash);

The length of the longest current collision chain is returned by:

size_t maximum = tscHashMaxChain(hash);

For an empty hash table, the maximum chain length is zero.

These statistics can be useful when evaluating the distribution produced by an application’s hash function.

For example, a table with many entries but relatively few used buckets or a very long maximum chain may indicate a poorly distributed application-supplied hash function.

Status

Operations retain their completion status in the hash object:

TscHashStatus status = tscHashGetStatus(hash);

A printable description is available with:

const char *message = tscHashStatusString(status);

Status values currently include:

TSC_HASH_STATUS_OK
TSC_HASH_ERROR_INVALID_ARGUMENT
TSC_HASH_ERROR_OUT_OF_MEMORY
TSC_HASH_ERROR_WRONG_HASH
TSC_HASH_ERROR_DUPLICATE_KEY
TSC_HASH_ERROR_NOT_FOUND
TSC_HASH_ERROR_BLOCK_SIZE_LOCKED

A failed tscHashFind() caused simply by the absence of a matching key is not an error and leaves the hash status as:

TSC_HASH_STATUS_OK

Built-In Key Helpers

The library provides hash and comparison functions for several commonly used key types.

The functions are intended to be used as matched pairs.

Case-Sensitive Strings

For NUL-terminated, case-sensitive strings:

tscHashString
tscHashCompareString

Strings such as "Tape001" and "tape001" are different keys.

Case-Insensitive Strings

For NUL-terminated, case-insensitive strings:

tscHashStringCI
tscHashCompareStringCI

Strings such as "Tape001" and "tape001" compare as the same key.

Signed Integers

For int keys:

tscHashInt
tscHashCompareInt

Unsigned Integers

For unsigned int keys:

tscHashUInt
tscHashCompareUInt

Signed 64-Bit Integers

For int64_t keys:

tscHashInt64
tscHashCompareInt64

Unsigned 64-Bit Integers

For uint64_t keys:

tscHashUInt64
tscHashCompareUInt64

size_t Keys

For size_t keys:

tscHashSize
tscHashCompareSize

Binary Keys

Arbitrary binary data can be used as a key through:

typedef struct TscHashBinaryKey
{
    const void *data;
    size_t length;
} TscHashBinaryKey;

with the matched helper functions:

tscHashBinary
tscHashCompareBinary

Two binary keys compare equal only when their lengths are equal and all bytes are equal.

A zero-length binary key is valid. Its data pointer may be NULL.

For a nonzero-length binary key, the data pointer must refer to the binary data for the lifetime of the stored key.

As with all hash keys, the TscHashBinaryKey structure and the data it references must remain valid while the key is stored unless the application arranges ownership through its free callbacks.

Example

#include "tsc_hash.h"

#include <stdio.h>

int main(void)
{
    TscHash *hash;
    TscHashNode *node;

    char key1[] = "TAPE001";
    char key2[] = "TAPE002";
    char key3[] = "TAPE003";

    int value1 = 100;
    int value2 = 200;
    int value3 = 300;

    hash = tscHashCreate(
        tscHashString,
        tscHashCompareString,
        NULL,
        NULL);

    if (hash == NULL)
        return 1;

    tscHashInsert(hash, key1, &value1);
    tscHashInsert(hash, key2, &value2);
    tscHashInsert(hash, key3, &value3);

    node = tscHashFind(hash, "TAPE002");

    if (node != NULL)
    {
        printf(
            "%s = %d\n",
            (char *)node->key,
            *(int *)node->element);
    }

    printf("Nodes:        %zu\n", tscHashCount(hash));
    printf("Buckets:      %zu\n", tscHashBucketCount(hash));
    printf("Used buckets: %zu\n", tscHashUsedBuckets(hash));
    printf("Max chain:    %zu\n", tscHashMaxChain(hash));

    tscHashDestroy(hash);
    return 0;
}

The exact bucket statistics depend on the hash values and the current implementation, but the program will report three active nodes and find the "TAPE002" entry.

Notes

TscHash is intended as a general-purpose associative container for applications that need efficient lookup by key without requiring an ordered key space.

The library deliberately hides the bucket table and collision-chain structure so applications depend on the supported search and enumeration operations rather than implementation details.

Keys must remain logically unchanged while stored in the hash table. Modifying data that affects either the configured hash value or comparison result can make an entry unreachable or otherwise invalidate the table.

Hash and comparison callbacks must agree on key equality. If two keys compare equal, they must produce the same hash value. The library cannot provide correct lookup or duplicate detection when this requirement is violated.

Enumeration order is deliberately unspecified. Applications requiring sorted traversal or nearest-key searches should use an ordered container such as TscTree instead.

The current implementation is not designed to provide synchronization between threads. Applications requiring concurrent access should provide appropriate external locking.