commit ee6384813a8c2101d4fb24364aaada40c4d28d04
parent 6bab880600341a7d8b7740e098dab8d5c278bdd5
Author: Robert Russell <robertrussell.72001@gmail.com>
Date: Sun, 24 Sep 2023 21:37:45 -0700
Add generic dict implementation
Same interface as before, but now using table internally.
Diffstat:
9 files changed, 192 insertions(+), 0 deletions(-)
diff --git a/Makefile b/Makefile
@@ -6,6 +6,7 @@ SRC =\
src/alloc.c\
src/bench.c\
src/debug.c\
+ src/dict/impl/table.c\
src/log.c\
src/rand.c\
src/str.c\
@@ -16,6 +17,24 @@ SRC =\
src/vmem.c
# src/opt.c needs work
+TABLE_DEPS =\
+ inc/alloc.h\
+ inc/bits.h\
+ inc/debug.h\
+ inc/def.h\
+ inc/internal/util.h\
+ inc/rand.h\
+ inc/simd.h\
+ inc/string.h\
+ inc/table/declare.h\
+ inc/table/define.h\
+ inc/table/impl/common.h\
+ inc/table/impl/declare.h\
+ inc/table/impl/define.h\
+ inc/table/impl/macro.h\
+ inc/table/impl/unmacro.h\
+ inc/table/static.h
+
librcx.a: $(SRC:.c=.o)
$(AR) -rcs $@ $(SRC:.c=.o)
@@ -25,6 +44,7 @@ librcx.a: $(SRC:.c=.o)
src/alloc.o: src/alloc.c inc/alloc.h inc/def.h inc/log.h inc/rcx.h inc/internal/util.h config.mk
src/bench.o: src/bench.c inc/bench.h inc/def.h inc/log.h inc/rcx.h config.mk
src/debug.o: src/debug.c inc/debug.h inc/def.h inc/rcx.h config.mk
+src/dict/impl/table.o: src/dict/impl/table.c inc/dict/impl/table.h $(TABLE_DEPS) config.mk
src/log.o: src/log.c inc/def.h inc/log.h inc/rcx.h config.mk
src/opt.o: src/opt.c inc/def.h inc/opt.h inc/rcx.h config.mk
src/rand.o: src/rand.c inc/bits.h inc/def.h inc/rand.h inc/rcx.h inc/unix.h config.mk
diff --git a/inc/dict/declare.h b/inc/dict/declare.h
@@ -0,0 +1,11 @@
+#include <stdbool.h>
+#include <string.h>
+
+#include "../alloc.h"
+#include "../def.h"
+#include "../rand.h"
+
+#include "impl/macro.h"
+#include "impl/table.h"
+#include "impl/declare.h"
+#include "impl/unmacro.h"
diff --git a/inc/dict/define.h b/inc/dict/define.h
@@ -0,0 +1,11 @@
+#include <stdbool.h>
+#include <string.h>
+
+#include "../alloc.h"
+#include "../def.h"
+#include "../rand.h"
+
+#include "impl/macro.h"
+#include "impl/table.h"
+#include "impl/declare.h"
+#include "impl/unmacro.h"
diff --git a/inc/dict/impl/declare.h b/inc/dict/impl/declare.h
@@ -0,0 +1,90 @@
+typedef struct {
+ RTable table;
+ DICT_V default_val;
+} DICT_D;
+
+#define DICT_SPEC &(RDictTableSpec){ \
+ .ksize = sizeof(DICT_K), \
+ .vsize = sizeof(DICT_V), \
+ .eq = (RTableEqFunc)(DICT_EQ), \
+ .hash = (RTableHashFunc)(DICT_HASH), \
+ .allocz = (RTableAlloczFunc)(DICT_ALLOCZ), \
+ .free = (RTableFreeFunc)(DICT_FREE), \
+ }
+
+static inline UNUSED int
+DICT_METHOD(init)(DICT_D *d, usize hint) {
+ memset(&d->default_val, 0, sizeof(DICT_V));
+ return r_dict_table_init(&d->table, hint, DICT_SPEC);
+}
+
+static inline UNUSED void
+DICT_METHOD(free)(DICT_D *d) {
+ r_dict_table_free(&d->table, DICT_SPEC);
+}
+
+static inline UNUSED usize
+DICT_METHOD(len)(DICT_D *d) {
+ return r_dict_table_len(&d->table, DICT_SPEC);
+}
+
+static inline UNUSED void
+DICT_METHOD(set_default)(DICT_D *d, DICT_V v) {
+ d->default_val = v;
+}
+
+static inline UNUSED DICT_V
+DICT_METHOD(get_default)(DICT_D *d) {
+ return d->default_val;
+}
+
+static inline UNUSED DICT_V *
+DICT_METHOD(ptr)(DICT_D *d, DICT_K k) {
+ u64 h = DICT_HASH(&k, d->table.seed, sizeof(DICT_K));
+ void *vp = 0;
+ r_dict_table_acc(&d->table, &vp, &k, h, DICT_SPEC);
+ return vp;
+}
+
+static inline UNUSED bool
+DICT_METHOD(get)(DICT_D *d, DICT_V *v, DICT_K k) {
+ u64 h = DICT_HASH(&k, d->table.seed, sizeof(DICT_K));
+ void *vp;
+ int r = r_dict_table_acc(&d->table, &vp, &k, h, DICT_SPEC);
+ if (v) *v = r > 0 ? *(DICT_V *)vp : d->default_val;
+ return r > 0;
+}
+
+static inline UNUSED bool
+DICT_METHOD(set)(DICT_D *d, DICT_K k, DICT_V v) {
+ u64 h = DICT_HASH(&k, d->table.seed, sizeof(DICT_K));
+ void *vp;
+ int r = r_dict_table_acc(&d->table, &vp, &k, h, DICT_SPEC);
+ if (r > 0) *(DICT_V *)vp = v;
+ return r > 0;
+}
+
+static inline UNUSED int
+DICT_METHOD(put)(DICT_D *d, DICT_K k, DICT_V v) {
+ u64 h = DICT_HASH(&k, d->table.seed, sizeof(DICT_K));
+ void *vp;
+ int r = r_dict_table_ins(&d->table, &vp, &k, h, DICT_SPEC);
+ if (r >= 0) *(DICT_V *)vp = v;
+ return r;
+}
+
+static inline UNUSED bool
+DICT_METHOD(del)(DICT_D *d, DICT_V *v, DICT_K k) {
+ u64 h = DICT_HASH(&k, d->table.seed, sizeof(DICT_K));
+ void *vp;
+ int r = r_dict_table_del(&d->table, &vp, &k, h, DICT_SPEC);
+ if (v) *v = r > 0 ? *(DICT_V *)vp : d->default_val;
+ return r > 0;
+}
+
+static inline UNUSED void
+DICT_METHOD(clr)(DICT_D *d) {
+ r_dict_table_clr(&d->table, DICT_SPEC);
+}
+
+#undef DICT_SPEC
diff --git a/inc/dict/impl/macro.h b/inc/dict/impl/macro.h
@@ -0,0 +1,31 @@
+#ifndef DICT_D
+#error "rcx/dict: DICT_D must be defined"
+#endif
+
+#ifndef DICT_K
+#error "rcx/dict: DICT_K must be defined"
+#endif
+
+#ifndef DICT_V
+#error "rcx/dict: DICT_V must be defined"
+#endif
+
+#ifndef DICT_EQ
+#define DICT_EQ r_table_mem_eq
+#endif
+
+#ifndef DICT_HASH
+#define DICT_HASH r_table_mem_hash
+#endif
+
+#ifndef DICT_ALLOCZ
+#define DICT_ALLOCZ r_eallocz
+#endif
+
+#ifndef DICT_FREE
+#define DICT_FREE free
+#endif
+
+#ifndef DICT_METHOD
+#define DICT_METHOD(name) name
+#endif
diff --git a/inc/dict/impl/table.h b/inc/dict/impl/table.h
@@ -0,0 +1,3 @@
+#define TABLE_S RDictTableSpec
+#define TABLE_METHOD(name) r_dict_table_##name
+#include "../../table/declare.h"
+\ No newline at end of file
diff --git a/inc/dict/impl/unmacro.h b/inc/dict/impl/unmacro.h
@@ -0,0 +1,8 @@
+#undef DICT_METHOD
+#undef DICT_FREE
+#undef DICT_ALLOCZ
+#undef DICT_HASH
+#undef DICT_EQ
+#undef DICT_V
+#undef DICT_K
+#undef DICT_D
diff --git a/inc/dict/static.h b/inc/dict/static.h
@@ -0,0 +1,11 @@
+#include <stdbool.h>
+#include <string.h>
+
+#include "../alloc.h"
+#include "../def.h"
+#include "../rand.h"
+
+#include "impl/macro.h"
+#include "impl/table.h"
+#include "impl/declare.h"
+#include "impl/unmacro.h"
diff --git a/src/dict/impl/table.c b/src/dict/impl/table.c
@@ -0,0 +1,5 @@
+#include "dict/impl/table.h"
+
+#define TABLE_S RDictTableSpec
+#define TABLE_METHOD(name) r_dict_table_##name
+#include "table/define.h"
+\ No newline at end of file
