commit 3c353795c023458efe6466af0e15e090ed3501f9
parent b0e120dd5dbafa7230ce7ca9c7b46c32f7ccbb47
Author: Robert Russell <robertrussell.72001@gmail.com>
Date: Thu, 8 Jun 2023 20:16:27 -0700
Finish dict
...for now.
Diffstat:
| M | inc/dict.h | | | 18 | +++++++++--------- |
| M | src/dict.c | | | 194 | +++++++++++++++++++++++++++++++++++++++++-------------------------------------- |
2 files changed, 109 insertions(+), 103 deletions(-)
diff --git a/inc/dict.h b/inc/dict.h
@@ -30,7 +30,7 @@ struct r_dict {
usize count;
usize ntombs;
void *mem;
- u8 *data; /* Cache-aligned pointer into mem */
+ 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; }
@@ -46,7 +46,7 @@ static inline u64 r_dict_rstr_hash(Str *k, u64 seed, RDictSpec *spec) { return r
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_create(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);
@@ -84,32 +84,32 @@ static inline UNUSED int R_DICT_METHOD(init,##__VA_ARGS__)(D *d, usize hint) { \
static inline UNUSED void R_DICT_METHOD(free,##__VA_ARGS__)(D *d) { r_dict_free(&d->d, R_DICT_SPEC_(K,V)); } \
static inline UNUSED V *R_DICT_METHOD(ptr,##__VA_ARGS__)(D *d, K k) { \
u64 h = R_DICT_HASH(&k, d->d.seed, R_DICT_SPEC_(K,V)); /* Allow hash to be inlined. */ \
- void *vp; r_dict_access(&d->d, &vp, &k, h, R_DICT_SPEC_(K,V)); \
+ void *vp = 0; r_dict_access(&d->d, &vp, &k, h, R_DICT_SPEC_(K,V)); \
return vp; \
} \
static inline UNUSED bool R_DICT_METHOD(get,##__VA_ARGS__)(D *d, V *v, K k) { \
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_access(&d->d, &vp, &k, h, R_DICT_SPEC_(K,V)); \
- if (v) *v = vp ? *(V *)vp : d->default_val; \
+ if (v) *v = r > 0 ? *(V *)vp : d->default_val; \
return r > 0; \
} \
static inline UNUSED bool R_DICT_METHOD(set,##__VA_ARGS__)(D *d, K k, V v) { \
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_access(&d->d, &vp, &k, h, R_DICT_SPEC_(K,V)); \
- if (vp) *(V *)vp = v; \
+ if (r > 0) *(V *)vp = v; \
return r > 0; \
} \
static inline UNUSED int R_DICT_METHOD(put,##__VA_ARGS__)(D *d, K k, V v) { \
- assert(d->d.niter == 0, "can not create new dict entry while iterating"); \
+ 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_create(&d->d, &vp, &k, h, R_DICT_SPEC_(K,V)); \
- if (vp) *(V *)vp = v; \
+ void *vp; int r = r_dict_insert(&d->d, &vp, &k, h, R_DICT_SPEC_(K,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) { \
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_delete(&d->d, &vp, &k, h, R_DICT_SPEC_(K,V)); \
- if (v) *v = vp ? *(V *)vp : d->default_val; \
+ if (v) *v = r > 0 ? *(V *)vp : d->default_val; \
return r > 0; \
} \
static inline UNUSED void R_DICT_METHOD(clr,##__VA_ARGS__)(D *d) { r_dict_clear((void *)d, R_DICT_SPEC_(K,V)); }
diff --git a/src/dict.c b/src/dict.c
@@ -35,7 +35,7 @@ typedef u8 Page; /* For readability only; a page isn't really a u8. */
enum scan_mode {
ACCESS = 0,
- CREATE = 1,
+ INSERT = 1,
DELETE = 2,
};
@@ -52,90 +52,105 @@ exceeds_lf(u64 n, u8 b) {
return LF_DEN * n > LF_NUM * (U64_C(1) << b);
}
-static void
-insert(Page *pages, u8 b, void *k, void *v, u64 h, RDictSpec *spec) {
- assert(false);
-#if 0
- usize h0 = hash0(h, b);
- u8 h1 = hash1(h, b);
+static int
+alloc_and_align(void **mem, void **data, u8 b, RDictSpec *spec) {
+ 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 (dsize > USIZE_MAX - (R_CACHE_LINE_SIZE - 1)) goto fail;
+ *mem = spec->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));
- usize pn = h0;
- for (usize i = 1;; i++) {
- Page *p = (void *)((u8 *)pages + pn*spec->psize);
+ return 0;
- /* TODO: this is wrong. Should probably just generalize scan and
- * replace insert with scan. Otherwise we need a bunch of #ifs here. */
+fail:
+ errno = ENOMEM;
+ return -1;
+}
- usize j = h1;
- do {
- if (p->meta[j] < MIN_HASH1) {
- p->meta[j] = h1;
- memcpy(key(p, j, spec), k, spec->ksize);
- memcpy(val(p, j, spec), v, spec->vsize);
- return;
- }
+/* 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) {
+ usize meta_mask = (USIZE_C(1) << (b - PROBE_LEN_BITS)) - 1u;
+
+ usize h0 = h & meta_mask;
+ u8 h1 = hash1(h, b);
- j = (j + 1) & (PROBE_LEN - 1);
- } while (j != h1);
+#ifdef USE_SIMD
+ v16u8 vempty = v16u8_fill(EMPTY);
+#endif
- pn = (pn + i) & ((USIZE_C(1) << b) - 1u);
- }
+ usize insert_idx;
+ for (usize mvi = h0, jump = 1;; mvi = (mvi + jump) & meta_mask, jump++) {
+ usize i = mvi * PROBE_LEN;
+
+#ifdef USE_SIMD
+ v16u8 vmeta; memcpy(&vmeta, meta+i, sizeof vmeta);
+ u16 m0 = v16u8_msb(v16u8_cmpeq(vmeta, vempty));
+ if (m0 != 0) {
+ insert_idx = i + r_ctz16(m0);
+ break;
+ }
+#else
+ u64 vmeta = r_readl64(meta+i);
+ int j0 = r_r8search64(vmeta);
+ if (j0 != 8) {
+ insert_idx = i + j0;
+ break;
+ }
#endif
+ }
+
+ 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);
}
static int
grow(RDict *d, RDictSpec *spec) {
- assert(false);
-#if 0
u8 oldb = d->b;
- u8 newb = oldb + 1;
- assert(newb < USIZE_BITS);
-
usize oldlen = USIZE_C(1) << oldb;
- Page *old = d->pages;
+ void *oldmem = d->mem;
+ u8 *oldmeta = d->data;
+ Page *oldpages = (u8 *)d->data + oldlen;
+ u8 newb = oldb + 1;
+ assert(newb < USIZE_BITS);
usize newlen = USIZE_C(1) << newb;
- if (r_mul_will_overflow_(newlen, spec->psize)) {
- errno = ENOMEM;
- return -1;
- }
- Page *new = spec->allocz(newlen * spec->psize);
- if (!new) return -1;
+ void *newmem, *newdata;
+ if (alloc_and_align(&newmem, &newdata, newb, spec) < 0) return -1;
+ u8 *newmeta = newdata;
+ Page *newpages = (u8 *)d->data + newlen;
for (usize i = 0; i < oldlen; i++) {
- Page *p = (void *)((u8 *)old + i*spec->psize);
-
- for (usize j = 0; j < PROBE_LEN; j++) {
- if (p->meta[j] < MIN_HASH1) continue;
- void *k = key(p, j, spec);
- void *v = val(p, j, spec);
- u64 h = spec->hash(k, d->seed, spec);
- insert(new, newb, k, v, h, spec);
- }
+ 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);
}
d->b = newb;
- d->pages = new;
d->ntombs = 0;
- spec->free(old);
-#endif
+ 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) {
- *v = 0;
-
- if (mode == CREATE && exceeds_lf(d->count + d->ntombs, d->b)) {
- if (grow(d, spec) < 0)
- return -1;
- }
-
/* 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;
- Page *pages = d->data + (USIZE_C(1) << d->b);
+ Page *pages = (u8 *)d->data + (USIZE_C(1) << d->b);
usize h0 = h & meta_mask;
u8 h1 = hash1(h, d->b);
@@ -147,9 +162,9 @@ scan(RDict *d, void **v, void *k, u64 h, int mode, RDictSpec *spec) {
u64 vh1; memset(&vh1, h1, sizeof vh1);
#endif
- bool create_slot_found = false;
- usize create_idx;
- bool create_replacing_tomb;
+ bool insert_slot_found = false;
+ usize insert_idx;
+ bool insert_replacing_tomb;
/* mvi is the metadata vector index (where each metadata vector is a
* u8[PROBE_LEN]), and i is the corresponding index in the meta table.
* Note that mvi is increased quadratically. */
@@ -208,34 +223,34 @@ scan(RDict *d, void **v, void *k, u64 h, int mode, RDictSpec *spec) {
int j0 = r_r8search64(vmeta);
#endif
- /* In mode CREATE, we need to look for an EMPTY or TOMBSTONE slot in
+ /* In mode INSERT, we need to look for an EMPTY or TOMBSTONE slot in
* case we don't find an existing slot with the given key. We
* prioritize filling TOMBSTONE slots to decrease the load factor. */
- if (mode == CREATE && !create_slot_found) {
+ if (mode == INSERT && !insert_slot_found) {
#ifdef USE_SIMD
v16u8 vtomb = v16u8_fill(TOMBSTONE);
u16 m1 = v16u8_msb(v16u8_cmpeq(vmeta, vtomb));
if (m1 != 0) {
- create_slot_found = true;
- create_idx = i + r_ctz16(m1);
- create_replacing_tomb = true;
+ insert_slot_found = true;
+ insert_idx = i + r_ctz16(m1);
+ insert_replacing_tomb = true;
} else if (m0 != 0) {
- create_slot_found = true;
- create_idx = i + r_ctz16(m0);
- create_replacing_tomb = false;
+ insert_slot_found = true;
+ insert_idx = i + r_ctz16(m0);
+ insert_replacing_tomb = false;
break;
}
#else
u64 vtomb; memset(&vtomb, TOMBSTONE, sizeof vtomb);
int j1 = r_r8search64(vmeta ^ vtomb);
if (j1 != 8) {
- create_slot_found = true;
- create_idx = i + j1;
- create_replacing_tomb = true;
+ insert_slot_found = true;
+ insert_idx = i + j1;
+ insert_replacing_tomb = true;
} else if (j0 != 8) {
- create_slot_found = true;
- create_idx = i + j0;
- create_replacing_tomb = false;
+ insert_slot_found = true;
+ insert_idx = i + j0;
+ insert_replacing_tomb = false;
break;
}
#endif
@@ -249,12 +264,12 @@ scan(RDict *d, void **v, void *k, u64 h, int mode, RDictSpec *spec) {
#endif
}
- if (mode == CREATE) {
+ if (mode == INSERT) {
d->count += 1;
- if (create_replacing_tomb) d->ntombs -= 1;
- meta[create_idx] = h1;
- usize page_idx = create_idx % PAGE_LEN;
- Page *p = pages + (create_idx - page_idx) * (spec->ksize + spec->vsize);
+ 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;
}
@@ -274,24 +289,11 @@ r_dict_init(RDict *d, usize hint, RDictSpec *spec) {
assert(b < USIZE_BITS);
d->b = b;
- usize len = USIZE_C(1) << b;
- if (r_mul_will_overflow_(len, 1u + spec->ksize + spec->vsize))
- goto alloc_error;
- usize dsize = len * (1u + spec->ksize + spec->vsize);
- if (dsize > USIZE_MAX - (R_CACHE_LINE_SIZE - 1))
- goto alloc_error;
- d->mem = spec->allocz((R_CACHE_LINE_SIZE - 1) + dsize);
- if (!d->mem)
- goto alloc_error;
- d->data = (void *)(((uptr)d->mem + (R_CACHE_LINE_SIZE - 1)) & -((uptr)R_CACHE_LINE_SIZE));
+ if (alloc_and_align(&d->mem, &d->data, b, spec) < 0) return -1;
d->seed = r_prand64();
return 0;
-
-alloc_error:
- errno = ENOMEM;
- return -1;
}
void
@@ -308,8 +310,12 @@ r_dict_access(RDict *d, void **v, void *k, u64 h, RDictSpec *spec) {
}
int
-r_dict_create(RDict *d, void **v, void *k, u64 h, RDictSpec *spec) {
- return scan(d, v, k, h, CREATE, spec);
+r_dict_insert(RDict *d, void **v, void *k, u64 h, RDictSpec *spec) {
+ if (exceeds_lf(d->count + d->ntombs, d->b)) {
+ if (grow(d, spec) < 0)
+ return -1;
+ }
+ return scan(d, v, k, h, INSERT, spec);
}
int
