fwHash — Hash Tables

What It Does

fwHash provides open-addressing hash tables with Robin Hood probing. Robin Hood probing keeps the variance in probe sequence lengths low, which improves cache behavior and allows the lookup hot path to be structured so the CPU branch predictor almost always predicts correctly — the common case (key found on first probe) is fast and the slow path is genuinely rare.

fwHash is used wherever a GE needs O(1) keyed lookup at runtime:

• Subscription stores — fast dispatch on entity type + attribute changes
• Device registries — per-device state lookup in IoT Agent scenarios
• Token caches — bearer token validation without repeated DB round-trips
• Session stores — per-connection state in the fwHttp server
• @context term mappings — the dual name↔URI tables in fwJsonld

Trace Levels

fwHash uses trace levels 80–99 (reserved). See the full trace level table for all assignments across the fw-lib stack.

Types & Functions

Types

// Hash code function — calculates hash from a key name
typedef unsigned int (*KHashCodeFunction)(const char* name);

// Compare function — returns 0 if name matches the item
typedef int (*KHashCompareFunction)(const char* name, void* itemP);

typedef struct KHashTable KHashTable;  // Opaque

fwHashTableCreate

KHashTable* fwHashTableCreate(
    FaAlloc*               kaP,             // Memory allocator (NULL for malloc)
    KHashCodeFunction     hashFunction,    // User hash function
    KHashCompareFunction  compareFunction, // User compare function
    int                   slots            // Number of slots (power of 2 recommended)
);

Creates a new hash table. Returns NULL on allocation failure. Pass NULL for kaP to use malloc. Performance tip: use a power-of-2 value for slots (e.g., 64, 128, 256) to enable fast bitmask-based slot calculation instead of modulo.

Core Operations

Function	Returns	Description
fwHashItemAdd(ht, name, data)	0 / -1	Add item; head insertion, O(1)
fwHashItemLookup(ht, name)	void* / NULL	Find item by name, O(1) average
fwHashItemRemove(ht, name)	0 / -1	Remove item; caller frees data
fwHashRelease(ht)	void	Free all hash table structures (not item data)

Advanced Lookup

// Lookup with a custom compare function (different from table default)
void* fwHashItemCustomLookup(KHashTable* ht, const char* name,
                            KHashCompareFunction compareFunction);

// Scan all slots — O(n), use only when hash code is unknown
void* fwHashItemLookupInAllSlots(KHashTable* ht, const char* name,
                                KHashCompareFunction compareFunction);

Performance Optimizations

• Hash code caching — each stored item caches its hash code so lookup can do a fast integer comparison before invoking the (potentially expensive) string compare function
• Power-of-2 bitmask — when table size is a power of 2, slot calculation uses hash & mask instead of hash % size, eliminating a division instruction
• Branch prediction hints — __builtin_expect marks the hit path as the common case, keeping the CPU branch predictor happy
• Head insertion — new items are inserted at the head of collision chains for O(1) insert regardless of chain length

Example

unsigned int myHashCode(const char* name)
{
    unsigned int hash = 5381;
    while (*name)
        hash = ((hash << 5) + hash) + *name++;
    return hash;
}

int myCompare(const char* name, void* itemP)
{
    return strcmp(name, ((MyItem*)itemP)->name);
}

// Use 64 slots — power of 2 for best performance
KHashTable* ht = fwHashTableCreate(NULL, myHashCode, myCompare, 64);

MyItem* item = malloc(sizeof(MyItem));
item->name  = "key1";
item->value = 42;
fwHashItemAdd(ht, item->name, item);

MyItem* found = (MyItem*) fwHashItemLookup(ht, "key1");

fwHashItemRemove(ht, "key1");
free(item);   // Caller must free item data
fwHashRelease(ht);