25 #define LOG(...) printf(__VA_ARGS__)
32 static bool insert(
int *buckets,
void **values,
33 size_t mask,
size_t max_fill,
34 int key,
void *value,
void **old_value);
42 if (sz2 == 0) { sz2 =
DEF_SZ2; }
43 size_t size = 1 << sz2;
44 struct yacht *y = calloc(1,
sizeof(*y));
45 int *
buckets = calloc(size,
sizeof(*buckets));
46 void **
values = calloc(size,
sizeof(*values));
47 if (y && buckets && values) {
52 LOG(
" -- init with size %zd\n", size);
53 for (
size_t i = 0; i <
size; i++) {
59 if (buckets) { free(buckets); }
60 if (values) { free(values); }
66 #define LARGE_PRIME (4294967291L )
69 static size_t hash(
int key) {
75 LOG(
" -- getting key %d with bucket %zd\n", key, b);
77 for (
size_t o = 0; o < y->
size; o++) {
78 size_t i = (b + o) & y->
mask;
81 if (value) { *value = y->
values[i]; }
92 LOG(
" -- checking membership for %d\n", key);
98 LOG(
" -- setting key %d\n", key);
101 size_t max = y->
size / 2;
106 if (!
grow(y)) {
return false; }
112 size_t mask,
size_t max_fill,
113 int key,
void *value,
void **old_value) {
116 for (
size_t o = 0; o < max_fill; o++) {
117 if (o > 0) {
LOG(
" -- o %zd (max_fill %zd)\n", o, max_fill); }
118 size_t i = (b + o) & mask;
120 LOG(
" -- b %zd: %d\n", i, bv);
122 if (old_value) { *old_value = values[i]; }
135 size_t nsize = 2 * y->
size;
136 LOG(
" -- growing %zd => %zd\n", y->
size, nsize);
137 size_t nmask = nsize - 1;
138 int *nbuckets = NULL;
139 void **nvalues = NULL;
140 nbuckets = malloc(nsize *
sizeof(*nbuckets));
141 if (nbuckets == NULL) {
return false; }
142 for (
size_t i = 0; i < nsize; i++) {
145 nvalues = calloc(nsize,
sizeof(*nvalues));
146 if (nvalues == NULL) {
151 for (
size_t i = 0; i < y->
size; i++) {
154 if (!
insert(nbuckets, nvalues, nmask, nsize, key, y->
values[i], NULL)) {
167 if (nbuckets) { free(nbuckets); }
168 if (nvalues) { free(nvalues); }
176 LOG(
" -- removing %d with bucket %zd\n", key, b);
178 for (
size_t o = 0; o < y->
size; o++) {
179 size_t i = (b + o) & y->
mask;
181 LOG(
" -- b %zd: %d\n", i, bv);
189 *old_value = y->
values[i];
204 for (
size_t i = 0; i < y->
size; i++) {
struct yacht * Yacht_Init(uint8_t sz2)
Init a hash table with approx.
size_t mask
Mask for hash table bucket array.
bool Yacht_Member(struct yacht *y, int key)
Check if KEY is in the table.
int * buckets
Hash table buckets (keys).
static size_t hash(int key)
bool Yacht_Set(struct yacht *y, int key, void *value, void **old_value)
Set KEY to VALUE in the table.
static bool grow(struct yacht *y)
void ** values
Values associated with keys, if any.
bool Yacht_Get(struct yacht *y, int key, void **value)
Get KEY from the table, setting *value if found.
static bool insert(int *buckets, void **values, size_t mask, size_t max_fill, int key, void *value, void **old_value)
void( Yacht_Free_cb)(void *value, void *udata)
Callback to free values associated with keys.
bool Yacht_Remove(struct yacht *y, int key, void **old_value)
Remove KEY from the table.
size_t size
Size of bucket array.
#define YACHT_DELETED
Special placeholder for a deleted key in a hash bucket.
void Yacht_Free(struct yacht *y, Yacht_Free_cb *cb, void *udata)
Free the table.
#define YACHT_NO_KEY
Special value for no key in a hash bucket.