Hashset
A set of unique void * values with hashed membership and no algebra API. Use set for union, intersection, difference, or a small collection; match returns 0 for equal values, the same convention as Set, and hash is required.
Usage#
Initialize with equality and hash callbacks. Equal values must hash equally, and stored values must not change in any way either callback observes. The optional destructor runs on members still present at destroy.
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;
if (lf_hashset_init(&set, 16, int_match, int_hash, NULL) == 0) {
int value = 42;
if (lf_hashset_insert(&set, &value) == 0) {
int key = 42;
void *removed = &key;
if (lf_hashset_remove(&set, &removed) == 0) {
/* removed == &value; the set did not free it */
(void)removed;
}
}
lf_hashset_destroy(&set);
}
The payloads here live on the stack, so the destructor is NULL. Remove writes the stored pointer back and does not call destroy. Free the LfHashSet handle only when the caller 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;
After a successful init, cap is a power of two and at least 8. The table doubles before an insert when len >= cap - cap / 4, which is when that insert would push the live count past 3/4 of cap. When len is still below that threshold but len + tombs + 1 >= cap, the set rehashes at the same cap and clears tombstones. Doubling fails when cap > SIZE_MAX / 2. A duplicate insert does not allocate or grow the table.
Functions#
lf_hashset_init#
cap is a hint and is rounded up. match and hash are required; destroy may be NULL. Returns 0 on success and -1 on a NULL handle, a missing callback, a hint that cannot be rounded to a power of two, or allocation failure. Failure leaves the handle unchanged. Zero-initialize the handle if it must be destroyed after a failed init. Do not initialize a live set; the previous tables are leaked.
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 each live member when a destructor is set, frees the tables, and zeros the handle. Does not free the handle. A NULL handle is ignored, and a second destroy is safe.
void lf_hashset_destroy(LfHashSet *set);lf_hashset_insert#
Returns 0 when inserted, 1 when the value is already a member, and -1 on error. A duplicate or a failed insert does not store the pointer and leaves the table unchanged.
int lf_hashset_insert(LfHashSet *set, const void *data);lf_hashset_remove#
Removes the member matching *data and writes the stored pointer through data. Does not call destroy. Returns 0 on success. Returns -1 when the arguments are invalid, the set has no table, or no live member matches. Failure does not write through data.
int lf_hashset_remove(LfHashSet *set, void **data);lf_hashset_is_member#
Returns 1 when a live member matches data. Returns 0 when it is absent, or when set is NULL, a callback is missing, or cap is 0.
int lf_hashset_is_member(const LfHashSet *set, const void *data);Macros#
#define lf_hashset_size(s) ((s)->len)
s must be non-NULL. The value is the live count, not the capacity.