commit fbf42beb9362e5d583019b33e968e76a6707fd2b
parent 3c353795c023458efe6466af0e15e090ed3501f9
Author: Robert Russell <robertrussell.72001@gmail.com>
Date: Thu, 8 Jun 2023 22:38:21 -0700
Fix bugs in dict
And rename spec to s to reduce line length.
Diffstat:
| M | inc/dict.h | | | 30 | +++++++++++++++--------------- |
| M | src/dict.c | | | 83 | +++++++++++++++++++++++++++++++++++++++++-------------------------------------- |
2 files changed, 58 insertions(+), 55 deletions(-)
diff --git a/inc/dict.h b/inc/dict.h
@@ -9,8 +9,8 @@
typedef struct r_dict_spec RDictSpec;
typedef struct r_dict RDict;
-typedef bool (*RDictEqFunc)(void *a, void *b, RDictSpec *spec);
-typedef u64 (*RDictHashFunc)(void *k, u64 seed, RDictSpec *spec);
+typedef bool (*RDictEqFunc)(void *a, void *b, RDictSpec *s);
+typedef u64 (*RDictHashFunc)(void *k, u64 seed, RDictSpec *s);
typedef void *(*RDictAlloczFunc)(usize size);
typedef void (*RDictFreeFunc)(void *p);
@@ -33,22 +33,22 @@ struct r_dict {
void *data; /* Cache-aligned pointer into mem */
};
-static inline bool r_dict_mem_eq(void *a, void *b, RDictSpec *spec) { return memcmp(a, b, spec->ksize) == 0; }
-static inline u64 r_dict_mem_hash(void *k, u64 seed, RDictSpec *spec) { return r_hash(k, spec->ksize, seed); }
+static inline bool r_dict_mem_eq(void *a, void *b, RDictSpec *s) { return memcmp(a, b, s->ksize) == 0; }
+static inline u64 r_dict_mem_hash(void *k, u64 seed, RDictSpec *s) { return r_hash(k, s->ksize, seed); }
-static inline bool r_dict_cstr_eq(char **a, char **b, RDictSpec *spec) { return strcmp(*a, *b) == 0; }
-static inline u64 r_dict_cstr_hash(char **k, u64 seed, RDictSpec *spec) { return r_hash(*k, strlen(*k), seed); }
+static inline bool r_dict_cstr_eq(char **a, char **b, RDictSpec *s) { return strcmp(*a, *b) == 0; }
+static inline u64 r_dict_cstr_hash(char **k, u64 seed, RDictSpec *s) { return r_hash(*k, strlen(*k), seed); }
-static inline bool r_dict_rstr_eq(Str *a, Str *b, RDictSpec *spec) { return str_eq(*a, *b); }
-static inline u64 r_dict_rstr_hash(Str *k, u64 seed, RDictSpec *spec) { return r_hash(str_bytes(*k), str_len(*k), seed); }
+static inline bool r_dict_rstr_eq(Str *a, Str *b, RDictSpec *s) { return str_eq(*a, *b); }
+static inline u64 r_dict_rstr_hash(Str *k, u64 seed, RDictSpec *s) { return r_hash(str_bytes(*k), str_len(*k), seed); }
/* TODO: add functions for shrinking dict and reserving space? */
-int r_dict_init(RDict *d, usize hint, RDictSpec *spec);
-void r_dict_free(RDict *d, RDictSpec *spec);
-int r_dict_access(RDict *d, void **v, void *k, u64 h, RDictSpec *spec);
-int r_dict_insert(RDict *d, void **v, void *k, u64 h, RDictSpec *spec);
-int r_dict_delete(RDict *d, void **v, void *k, u64 h, RDictSpec *spec);
-void r_dict_clear(RDict *d, RDictSpec *spec);
+int r_dict_init(RDict *d, usize hint, RDictSpec *s);
+void r_dict_free(RDict *d, RDictSpec *s);
+int r_dict_access(RDict *d, void **v, void *k, u64 h, RDictSpec *s);
+int r_dict_insert(RDict *d, void **v, void *k, u64 h, RDictSpec *s);
+int r_dict_delete(RDict *d, void **v, void *k, u64 h, RDictSpec *s);
+void r_dict_clear(RDict *d, RDictSpec *s);
/* Defaults */
#define R_DICT_STATIC
@@ -103,7 +103,7 @@ static inline UNUSED int R_DICT_METHOD(put,##__VA_ARGS__)(D *d, K k, V v) { \
assert(d->d.niter == 0, "can not call put while iterating through dict"); \
u64 h = R_DICT_HASH(&k, d->d.seed, R_DICT_SPEC_(K,V)); /* Allow hash to be inlined. */ \
void *vp; int r = r_dict_insert(&d->d, &vp, &k, h, R_DICT_SPEC_(K,V)); \
- if (r > 0) *(V *)vp = v; \
+ if (r >= 0) *(V *)vp = v; \
return r; \
} \
static inline UNUSED bool R_DICT_METHOD(del,##__VA_ARGS__)(D *d, V *v, K k) { \
diff --git a/src/dict.c b/src/dict.c
@@ -24,6 +24,7 @@
* PAGE_LEN == 1 causes no packing issues and would improve caching
* performance with very large keys or values. */
#define PAGE_LEN 8u
+#define PAGE_LEN_BITS 3u
#define LF_NUM 3u
#define LF_DEN 4u
@@ -41,9 +42,9 @@ enum scan_mode {
static inline u8
hash1(u64 h, u8 b) {
- u64 t = h >> 56;
- if (t < MIN_HASH1) t += MIN_HASH1;
- return t;
+ u64 h1 = h >> 56;
+ if (h1 < MIN_HASH1) h1 += MIN_HASH1;
+ return h1;
}
static inline bool
@@ -53,14 +54,14 @@ exceeds_lf(u64 n, u8 b) {
}
static int
-alloc_and_align(void **mem, void **data, u8 b, RDictSpec *spec) {
+alloc_and_align(void **mem, void **data, u8 b, RDictSpec *s) {
usize len = USIZE_C(1) << b;
- if (r_mul_will_overflow_(len, 1u + spec->ksize + spec->vsize)) goto fail;
- usize dsize = len * (1u + spec->ksize + spec->vsize);
+ if (r_mul_will_overflow_(len, 1u + s->ksize + s->vsize)) goto fail;
+ usize dsize = len * (1u + s->ksize + s->vsize);
if (dsize > USIZE_MAX - (R_CACHE_LINE_SIZE - 1)) goto fail;
- *mem = spec->allocz((R_CACHE_LINE_SIZE - 1) + dsize);
+ *mem = s->allocz((R_CACHE_LINE_SIZE - 1) + dsize);
if (!*mem) goto fail;
- *data = (void *)(((uptr)*mem + (R_CACHE_LINE_SIZE - 1)) & -((uptr)R_CACHE_LINE_SIZE));
+ *data = (void *)(((uptr)*mem + (R_CACHE_LINE_SIZE - 1)) & -(uptr)R_CACHE_LINE_SIZE);
return 0;
@@ -72,7 +73,7 @@ fail:
/* This is a version of scan specialized for inserting while growing.
* See the comments in scan for explanation. */
static void
-grow_insert(u8 b, u8 *meta, Page *pages, void *k, void *v, u64 h, RDictSpec *spec) {
+grow_insert(u8 b, u8 *meta, Page *pages, void *k, void *v, u64 h, RDictSpec *s) {
usize meta_mask = (USIZE_C(1) << (b - PROBE_LEN_BITS)) - 1u;
usize h0 = h & meta_mask;
@@ -105,13 +106,13 @@ grow_insert(u8 b, u8 *meta, Page *pages, void *k, void *v, u64 h, RDictSpec *spe
meta[insert_idx] = h1;
usize page_idx = insert_idx % PAGE_LEN;
- Page *p = pages + (insert_idx - page_idx) * (spec->ksize + spec->vsize);
- memcpy(p + page_idx * spec->ksize, k, spec->ksize);
- memcpy(p + PAGE_LEN * spec->ksize + page_idx * spec->vsize, v, spec->vsize);
+ Page *p = pages + (insert_idx - page_idx) * (s->ksize + s->vsize);
+ memcpy(p + page_idx * s->ksize, k, s->ksize);
+ memcpy(p + PAGE_LEN * s->ksize + page_idx * s->vsize, v, s->vsize);
}
static int
-grow(RDict *d, RDictSpec *spec) {
+grow(RDict *d, RDictSpec *s) {
u8 oldb = d->b;
usize oldlen = USIZE_C(1) << oldb;
void *oldmem = d->mem;
@@ -122,31 +123,32 @@ grow(RDict *d, RDictSpec *spec) {
assert(newb < USIZE_BITS);
usize newlen = USIZE_C(1) << newb;
void *newmem, *newdata;
- if (alloc_and_align(&newmem, &newdata, newb, spec) < 0) return -1;
+ if (alloc_and_align(&newmem, &newdata, newb, s) < 0) return -1;
u8 *newmeta = newdata;
- Page *newpages = (u8 *)d->data + newlen;
+ Page *newpages = (u8 *)newdata + newlen;
for (usize i = 0; i < oldlen; i++) {
if (oldmeta[i] < MIN_HASH1) continue;
usize page_idx = i % PAGE_LEN;
- Page *p = oldpages + (i - page_idx) * (spec->ksize + spec->vsize);
- void *k = p + page_idx * spec->ksize;
- void *v = p + PAGE_LEN * spec->ksize + page_idx * spec->vsize;
- u64 h = spec->hash(k, d->seed, spec);
- grow_insert(newb, newmeta, newpages, k, v, h, spec);
+ Page *p = oldpages + (i - page_idx) * (s->ksize + s->vsize);
+ void *k = p + page_idx * s->ksize;
+ void *v = p + PAGE_LEN * s->ksize + page_idx * s->vsize;
+ u64 h = s->hash(k, d->seed, s);
+ grow_insert(newb, newmeta, newpages, k, v, h, s);
}
+ s->free(oldmem);
+
d->b = newb;
d->ntombs = 0;
d->mem = newmem;
d->data = newdata;
- spec->free(oldmem);
return 0;
}
static inline int
-scan(RDict *d, void **v, void *k, u64 h, int mode, RDictSpec *spec) {
+scan(RDict *d, void **v, void *k, u64 h, int mode, RDictSpec *s) {
/* meta_mask is a mask for reducing modulo the table size. */
usize meta_mask = (USIZE_C(1) << (d->b - PROBE_LEN_BITS)) - 1u;
u8 *meta = d->data;
@@ -196,8 +198,8 @@ scan(RDict *d, void **v, void *k, u64 h, int mode, RDictSpec *spec) {
#endif
usize match_idx = i + j;
usize page_idx = match_idx % PAGE_LEN;
- Page *p = pages + (match_idx - page_idx) * (spec->ksize + spec->vsize);
- if likely (spec->eq(p + page_idx * spec->ksize, k, spec)) {
+ Page *p = pages + (match_idx - page_idx) * (s->ksize + s->vsize);
+ if likely (s->eq(p + page_idx * s->ksize, k, s)) {
if (mode == DELETE) {
#ifdef USE_SIMD
if (v16u8_msb(v16u8_cmpeq(vmeta, vempty)) != 0) {
@@ -211,7 +213,7 @@ scan(RDict *d, void **v, void *k, u64 h, int mode, RDictSpec *spec) {
}
d->count -= 1;
}
- *v = p + PAGE_LEN * spec->ksize + page_idx * spec->vsize;
+ *v = p + PAGE_LEN * s->ksize + page_idx * s->vsize;
return 1;
}
}
@@ -269,27 +271,28 @@ scan(RDict *d, void **v, void *k, u64 h, int mode, RDictSpec *spec) {
if (insert_replacing_tomb) d->ntombs -= 1;
meta[insert_idx] = h1;
usize page_idx = insert_idx % PAGE_LEN;
- Page *p = pages + (insert_idx - page_idx) * (spec->ksize + spec->vsize);
- memcpy(p + page_idx * spec->ksize, k, spec->ksize);
- *v = p + PAGE_LEN * spec->ksize + page_idx * spec->vsize;
+ Page *p = pages + (insert_idx - page_idx) * (s->ksize + s->vsize);
+ memcpy(p + page_idx * s->ksize, k, s->ksize);
+ *v = p + PAGE_LEN * s->ksize + page_idx * s->vsize;
}
return 0;
}
int
-r_dict_init(RDict *d, usize hint, RDictSpec *spec) {
+r_dict_init(RDict *d, usize hint, RDictSpec *s) {
memset(d, 0, sizeof *d);
/* Impose maximum on hint to prevent overflow and the following while
* loop from being infinite. See exceeds_lf. */
hint = MIN(hint, (U64_MAX / LF_DEN) >> 1);
u8 b = MAX(R_CACHE_LINE_BITS, PROBE_LEN_BITS);
+ b = MAX(b, PAGE_LEN_BITS);
while (exceeds_lf(hint, b)) b += 1;
assert(b < USIZE_BITS);
d->b = b;
- if (alloc_and_align(&d->mem, &d->data, b, spec) < 0) return -1;
+ if (alloc_and_align(&d->mem, &d->data, b, s) < 0) return -1;
d->seed = r_prand64();
@@ -297,34 +300,34 @@ r_dict_init(RDict *d, usize hint, RDictSpec *spec) {
}
void
-r_dict_free(RDict *d, RDictSpec *spec) {
+r_dict_free(RDict *d, RDictSpec *s) {
if (d->niter > 0)
r_warnf("dict freed with %"PRId32" iterators alive", d->niter);
- spec->free(d->mem);
+ s->free(d->mem);
d->data = 0; /* Ensure hard error on use after free. */
}
int
-r_dict_access(RDict *d, void **v, void *k, u64 h, RDictSpec *spec) {
- return scan(d, v, k, h, ACCESS, spec);
+r_dict_access(RDict *d, void **v, void *k, u64 h, RDictSpec *s) {
+ return scan(d, v, k, h, ACCESS, s);
}
int
-r_dict_insert(RDict *d, void **v, void *k, u64 h, RDictSpec *spec) {
+r_dict_insert(RDict *d, void **v, void *k, u64 h, RDictSpec *s) {
if (exceeds_lf(d->count + d->ntombs, d->b)) {
- if (grow(d, spec) < 0)
+ if (grow(d, s) < 0)
return -1;
}
- return scan(d, v, k, h, INSERT, spec);
+ return scan(d, v, k, h, INSERT, s);
}
int
-r_dict_delete(RDict *d, void **v, void *k, u64 h, RDictSpec *spec) {
- return scan(d, v, k, h, DELETE, spec);
+r_dict_delete(RDict *d, void **v, void *k, u64 h, RDictSpec *s) {
+ return scan(d, v, k, h, DELETE, s);
}
void
-r_dict_clear(RDict *d, RDictSpec *spec) {
+r_dict_clear(RDict *d, RDictSpec *s) {
memset(d->data, EMPTY, USIZE_C(1) << d->b);
d->count = 0;
d->ntombs = 0;
