Hashset

A set of unique void * values with hashed membership. Use set when you want union, intersection, and difference, or when the collection stays small.

match is the same equality callback as Set (0 means equal). hash is required. There is no algebra API on this type.

Usage#

Initialize the set with equality and hash callbacks. Equal values must have equal hashes, and values must remain unchanged in ways that affect either callback while stored. The optional destructor runs on remaining members when the set is destroyed.

int int_match(const void *a, const void *b) {
    return *(const int *)a == *(const int *)b ? 0 : 1;
}

size_t int_hash(const void *p) {
    return (size_t)*(const int *)p;
}

LfHashSet set = {0};
if (lf_hashset_init(&set, 16, int_match, int_hash, NULL) == 0) {
    int value = 42;
    lf_hashset_insert(&set, &value);

    int key = 42;
    void *removed = &key;
    lf_hashset_remove(&set, &removed);
    lf_hashset_destroy(&set);
}

The example uses stack allocated data, so it passes NULL for the destructor. Removal returns the stored pointer without destroying it. The LfHashSet handle remains yours to free if you allocated it.

Structs#

LfHashSet#

typedef struct {
    void **slots;
    unsigned char *state;
    size_t cap;
    size_t len;
    size_t tombs;
    int (*match)(const void *a, const void *b);
    size_t (*hash)(const void *data);
    void (*destroy)(void *data);
} LfHashSet;

Capacity is a power of two, at least 8. The table grows when live entries plus the new insert would exceed a 3/4 load. Deleted slots are reclaimed without increasing capacity. Duplicate inserts do not allocate or grow the table.

Functions#

lf_hashset_init#

cap is a hint and is rounded up. match and hash are required. Returns 0 on success, -1 on error. Failed initialization leaves the handle unchanged; zero-initialize it if you need to call destroy after failure. Do not initialize a live set.

int lf_hashset_init(LfHashSet *set, size_t cap,
                    int (*match)(const void *a, const void *b),
                    size_t (*hash)(const void *data),
                    void (*destroy)(void *data));

lf_hashset_destroy#

Calls destroy on remaining live members, frees the tables, and zeros the handle.

void lf_hashset_destroy(LfHashSet *set);

lf_hashset_insert#

Returns 0 if inserted, 1 if already a member, -1 on error. Duplicate and failed inserts leave the payload with the caller.

int lf_hashset_insert(LfHashSet *set, const void *data);

lf_hashset_remove#

Removes the member matching *data and writes the stored payload back through data. Does not call destroy. Returns 0 on success, -1 if missing or if the arguments are invalid.

int lf_hashset_remove(LfHashSet *set, void **data);

lf_hashset_is_member#

Returns 1 if data is present, 0 otherwise.

int lf_hashset_is_member(const LfHashSet *set, const void *data);

Macros#

#define lf_hashset_size(s) ((s)->len)