Slotmap

LfIdMap is an open-addressed map from uint64_t keys to inline uint32_t values. LfSlots is a table of generational ids for caller-owned void * payloads; it does not free those payloads.

Usage#

LfSlots allocates an id for a payload it does not copy. Generation starts at 1. lf_slots_get on a freed id returns 1 and leaves the output unchanged. Allocating that index again bumps the generation, so the old id does not name the new occupant.

LfSlots slots;
int payload = 1;
int replacement = 2;
if (lf_slots_init(&slots, 8) == 0) {
    LfSlotId id;
    void *found = NULL;
    if (lf_slots_alloc(&slots, &payload, &id) == 0 &&
        lf_slots_get(&slots, id, &found) == 0 &&
        lf_slots_free(&slots, id) == 0) {
        LfSlotId again;
        void *stale = &payload;
        if (lf_slots_alloc(&slots, &replacement, &again) == 0 &&
            lf_slots_get(&slots, id, &stale) == 1) {
            /* found == &payload */
            /* again.index == id.index */
            /* again.generation == id.generation + 1 */
            /* stale is still &payload */
        }
    }
    lf_slots_destroy(&slots);
}

The caller owns the handle and every payload. lf_slots_destroy frees the slot array, not the handle and not the payloads. destroy(NULL) is safe. A failed init of a non-NULL handle leaves it destroyable, with a NULL slot pointer and cap 0. An id is an index plus a generation, not a pointer into the slot array, so it stays valid when that array grows. The struct fields are private. Do not read or write them. Concurrent use is not supported. LfIdMap uses the same handle rules. Its value is the inline uint32_t, and destroy frees only the entry array.

Structs#

LfIdMap#

typedef struct LfIdMap {
    void *slots;
    size_t cap, len, tombs;
} LfIdMap;

After a successful init, cap is a power of two. len is the number of live keys. tombs counts removed slots that still occupy a probe chain. The fields are private and are not a supported API. Do not read or write them.

LfSlotId#

typedef struct {
    uint32_t index;
    uint32_t generation;
} LfSlotId;

index and generation together name one occupant. Generation 0 is never issued. Do not invent an id. Take it from lf_slots_alloc.

LfSlots#

typedef struct LfSlots {
    void *slots;
    uint32_t free_head;
    uint32_t cap;
    uint32_t high; /* indexes ever issued */
} LfSlots;

Free indexes form an intrusive list. free_head is UINT32_MAX when that list is empty, so index 0 can be free. high is the number of indexes ever issued. The fields are private and are not a supported API. Do not read or write them.

Functions#

lf_idmap_init#

Capacity is rounded up to a power of two, at least 8. Returns 0 on success. Returns -1 on a NULL handle, when rounding the hint up would overflow size_t, or on allocation failure. Failure leaves slots NULL, cap 0, len 0, and tombs 0. lf_idmap_destroy on that handle is safe. Do not initialize a live map. Init overwrites the handle and does not free the previous array.

int lf_idmap_init(LfIdMap *m, size_t cap_hint);

lf_idmap_destroy#

Frees the entry array and zeros the handle. Does not free the handle. A NULL handle is safe, as is a second destroy.

void lf_idmap_destroy(LfIdMap *m);

lf_idmap_insert#

Returns 0 if the key was inserted, 1 if it was already present, and -1 if m is NULL, slots is NULL, cap is 0, or allocation fails. A duplicate keeps the original value and does not allocate or grow. On -1 nothing is written. Value 0, key 0, and key UINT64_MAX are ordinary stored values.

A new key grows the table to cap * 2 when len >= cap - cap/4, before the load would pass 3/4. When that test is false and len + tombs >= cap - 1, insert rehashes at the same capacity so a probe still ends on an empty slot. Rehash allocates the new buffer and frees the old one only after the copy succeeds. Equal keys share one probe sequence. There is no seed and no cursor. Bucket order is unspecified.

int lf_idmap_insert(LfIdMap *m, uint64_t key, uint32_t value);

lf_idmap_replace#

Returns 0 if an existing value was replaced, 1 if the key is absent, and -1 if m is NULL, slots is NULL, or cap is 0. An absent key is not inserted. Nothing is written on 1 or -1.

int lf_idmap_replace(LfIdMap *m, uint64_t key, uint32_t value);

lf_idmap_find#

Returns 0 if the key is present, 1 if it is absent, and -1 if m is NULL, slots is NULL, cap is 0, or value is NULL. *value is written only when the key is found. On 1 and -1 it is unchanged. The probe starts at a mix of the key masked to cap - 1, walks linearly, skips tombstones, and stops at an empty slot. A live slot matches with uint64_t equality.

int lf_idmap_find(const LfIdMap *m, uint64_t key, uint32_t *value);

lf_idmap_remove#

Returns 0 if a live key was removed, 1 if it is absent, and -1 if m is NULL, slots is NULL, or cap is 0. On success, a non-NULL old_value receives the previous value. A NULL old_value skips that write. On 1 and -1, a non-NULL old_value is left unchanged. The slot becomes a tombstone and len decreases only on success. Later lookups skip that tombstone and still stop at an empty slot, so the removal does not hide a key placed further along the probe.

int lf_idmap_remove(LfIdMap *m, uint64_t key, uint32_t *old_value);

lf_idmap_len#

Returns the number of live keys. A NULL map returns 0.

size_t lf_idmap_len(const LfIdMap *m);

lf_slots_init#

Returns 0 on success. Returns -1 on a NULL handle, a cap_hint above UINT32_MAX, or allocation failure. Failure on a non-NULL handle leaves slots NULL and cap 0, and lf_slots_destroy on that handle is safe. cap_hint < 1 selects capacity 8. A larger hint is the capacity and is not rounded to a power of two. Do not initialize a live table. Init overwrites the handle and does not free the previous array.

int lf_slots_init(LfSlots *s, size_t cap_hint);

lf_slots_destroy#

Frees the slot array and zeros the handle. Does not free payloads and does not free the handle. A NULL handle is safe, as is a second destroy.

void lf_slots_destroy(LfSlots *s);

lf_slots_alloc#

Returns 0 on success and writes *id. Returns -1 if s is NULL, slots is NULL, cap is 0, id is NULL, allocation fails, or no index can be issued. On -1, *id and the existing slots are unchanged. A NULL value is a successful payload, not an error.

A fresh index uses generation 1. A reused free index uses its previous generation plus one. Generation 0 is never written. An index whose generation is already UINT32_MAX stays on the free list and is not recycled. If no other index can be allocated, that retired index stays linked and the table is otherwise unchanged.

When cap <= UINT32_MAX / 2, growth sets the new capacity to cap * 2. A larger cap grows to UINT32_MAX, and a table already at UINT32_MAX cannot grow. The largest index that can be issued is UINT32_MAX - 1.

int lf_slots_alloc(LfSlots *s, void *value, LfSlotId *id);

lf_slots_get#

Returns 0 if id names the live occupant of that index, 1 if the id is stale, free, generation 0, or an index that was never issued, and -1 if s is NULL, slots is NULL, cap is 0, or value is NULL. *value is written only on a hit and may be NULL. On 1 and -1 it is unchanged. The pointer written is the caller's payload, not an address in the slot array.

int lf_slots_get(const LfSlots *s, LfSlotId id, void **value);

lf_slots_free#

Returns 0 if the live id was freed, 1 if it is stale, already free, generation 0, or an index that was never issued, and -1 if s is NULL, slots is NULL, or cap is 0. A stale id does not free the current occupant. The second free of a live id returns 1. Free does not change the generation and does not free the payload. After a successful free the caller may release the payload. The table does not dereference it.

int lf_slots_free(LfSlots *s, LfSlotId id);