Hashmap

A hash map of pointer keys to pointer values. Equal keys share one entry.

Usage#

Initialize a LfHashMap with equality and hash callbacks and optional key and value destructors. The equality callback returns 0 for equal keys. Equal keys must hash equally, and keys must remain stable while stored.

int int_match(const void *a, const void *b) {
    return *(const int *)a != *(const int *)b;
}
size_t int_hash(const void *p) { return (size_t)*(const int *)p; }

LfHashMap map;
if (lf_hashmap_init(&map, 16, int_match, int_hash, NULL, NULL) == 0) {
    int key = 42, value = 7;
    if (lf_hashmap_insert(&map, &key, &value) == 0) {
        void *found;
        if (lf_hashmap_find(&map, &key, &found) == 0) {
            /* found == &value */
        }
    }
    LfHashMapCursor cur;
    void *ck, *cv;
    if (lf_hashmap_cursor_init(&cur, &map) == 0) {
        while (lf_hashmap_cursor_next(&cur, &ck, &cv) == 0) {
            /* ck and cv borrow one live pair; order is unspecified */
        }
    }
    lf_hashmap_destroy(&map);
}

The example uses stack allocated keys and values, so it passes NULL for both destructors. Removal returns both stored pointers without destroying them. Destroy frees the table and calls the destructors on remaining pairs; the LfHashMap handle is yours to free if you allocated it.

NULL keys are allowed if both callbacks support them. Stored NULL values are distinct from a missing key. Owned keys and values must have independent lifetimes: do not share owned allocations across entries or between key and value roles. Callbacks must not mutate the map. Concurrent mutation of the map is not supported.

LfHashMapCursor walks each live pair once. Empty and tombstone slots are skipped. Order is unspecified. This is not a content-order iterator. Callers who need sorted keys sort a side array. insert, remove, replace, clear, and destroy invalidate the cursor. The walk does not detect use after invalidation.

Lookup and removal take expected O(1) time. Insertion takes amortized expected O(1) time; rehashing, clear, and destroy take O(capacity). A full cursor walk takes O(capacity).

Structs#

LfHashMapEntry#

typedef struct {
    void *key;
    void *value;
    unsigned char state;
} LfHashMapEntry;

LfHashMap#

typedef struct {
    LfHashMapEntry *entries;
    size_t cap, len, tombs;
    int (*match)(const void *, const void *);
    size_t (*hash)(const void *);
    void (*destroy_key)(void *);
    void (*destroy_value)(void *);
} LfHashMap;

LfHashMapCursor#

typedef struct {
    const LfHashMap *map;
    size_t index;
} LfHashMapCursor;

map is the table passed to lf_hashmap_cursor_init. index is the next slot to examine and starts at 0. The cursor does not own the map. Do not write the fields yourself.

Functions#

lf_hashmap_init#

Capacity is rounded up to a power of two, at least eight. Returns 0 on success, -1 on a NULL handle, invalid callbacks, size overflow, or allocation failure. Failed initialization leaves a non-NULL handle destroyable. Do not initialize a live map.

int lf_hashmap_init(LfHashMap *map, size_t cap,
                    int (*match)(const void *, const void *),
                    size_t (*hash)(const void *),
                    void (*destroy_key)(void *), void (*destroy_value)(void *));

lf_hashmap_insert#

Returns 0 on insertion, 1 on duplicate, -1 on error. A duplicate keeps the original pair and does not allocate. Failed insertion leaves contents and ownership unchanged.

int lf_hashmap_insert(LfHashMap *map, void *key, void *value);

lf_hashmap_replace#

Replaces only an existing pair. Returns 0 on replacement, 1 if absent, -1 on invalid arguments. Calls each destructor on the displaced pointer unless it is identical to the corresponding new pointer. Ownership of the new pair passes only on success.

int lf_hashmap_replace(LfHashMap *map, void *key, void *value);

lf_hashmap_find#

Returns 0 if found, 1 if absent, -1 on invalid arguments. The required output borrows the stored value, which may be NULL. The output is unchanged on failure and must not alias map storage.

int lf_hashmap_find(const LfHashMap *map, const void *key, void **value);

lf_hashmap_remove#

Returns the same statuses as find. Both distinct output pointers are required; success transfers the stored key and value without destruction. Outputs are unchanged on failure and must not alias map storage.

int lf_hashmap_remove(LfHashMap *map, const void *key,
                      void **stored_key, void **value);

lf_hashmap_clear / lf_hashmap_destroy#

Clear destroys all pairs and retains capacity. Destroy also releases the table and zeros the handle. Destructors are called even for NULL keys and values. Both functions accept a NULL handle.

void lf_hashmap_clear(LfHashMap *map);
void lf_hashmap_destroy(LfHashMap *map);

lf_hashmap_cursor_init / lf_hashmap_cursor_next#

lf_hashmap_cursor_init returns 0 on success and -1 if c or map is NULL. On success it stores map and sets index to 0. On failure c is unchanged. Init does not require an entries buffer.

lf_hashmap_cursor_next returns 0 when it yields a live pair, 1 when the walk is exhausted, and -1 if c, c->map, key, or value is NULL, or the map has no entries buffer. *key and *value are unchanged on 1 and -1. On 0 they borrow the stored pointers. A stored NULL value is a hit (*value is NULL and the return is 0), and a stored NULL key is also a hit when the callbacks allowed it. The cursor does not take ownership.

Each live pair is yielded once. Empty slots and tombstones are skipped. Order is unspecified. This is not a content-order iterator. insert, remove, replace, clear, and destroy invalidate the cursor. remove transfers the stored pointers, and replace, clear, and destroy may destroy them, so pointers from earlier yields do not outlive those calls. insert does not free existing pairs. It still invalidates the cursor, because it may rehash. The implementation does not detect use after invalidation. Callbacks must not mutate the map.

int lf_hashmap_cursor_init(LfHashMapCursor *c, const LfHashMap *map);
int lf_hashmap_cursor_next(LfHashMapCursor *c, void **key, void **value);

Macros#

#define lf_hashmap_size(m) ((m)->len)