commit b5311852537e210aa4da7463f8d5dd972d4952b6
Author: olikru <olikru@tkruger.se>
Date: Mon, 8 Jan 2024 15:25:08 +0100
initial
Diffstat:
| A | Makefile | | | 43 | +++++++++++++++++++++++++++++++++++++++++++ |
| A | README | | | 4 | ++++ |
| A | TODO | | | 2 | ++ |
| A | dict.c | | | 82 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | dict.h | | | 33 | +++++++++++++++++++++++++++++++++ |
| A | test_dict.c | | | 8 | ++++++++ |
6 files changed, 172 insertions(+), 0 deletions(-)
diff --git a/Makefile b/Makefile
@@ -0,0 +1,43 @@
+.SUFFIXES: .c .o .so
+CC=clang
+CFLAGS+=-std=c99 -pedantic -Wall -Werror -Wstrict-prototypes
+CFLAGS+=-Wmissing-prototypes -Wmissing-declarations -Wshadow
+CFLAGS+=-Wpointer-arith -Wcast-qual -Wsign-compare
+CFLAGS+=-O2 -g
+CFLAGS+=-fstack-protector-all -Wtype-limits -fno-common
+CFLAGS+=-fno-builtin
+CFLAGS+=-I/usr/local/include
+
+CFLAGS+=-I$(HOME)/.local/include
+LFLAGS+=-L$(HOME)/.local/lib -lstack_sd -lsd
+
+INSTALL_PATH=$(HOME)/.local
+BUILD=build
+
+TEST_SOURCE=test_dict.c
+HEADER=dict.h
+OBJS=dict.o
+SHARED=dict.so
+LIBSHARED=libdict.so
+
+all: build $(OBJS) $(SHARED) test
+
+.c.o:
+ $(CC) $(CFLAGS) -c $< -o $(BUILD)/$@
+
+.o.so:
+ $(CC) -shared -fPIC $(BUILD)/$< -o $(BUILD)/$@ $(LFLAGS)
+
+test: $(TEST_SOURCE)
+ $(CC) $(CFLAGS) -o $(BUILD)/test $(TEST_SOURCE) $(BUILD)/$(OBJS) $(LFLAGS)
+
+build:
+ mkdir -p $(BUILD)
+
+install:
+ cp $(BUILD)/$(SHARED) $(INSTALL_PATH)/lib/$(LIBSHARED)
+ chmod 644 $(INSTALL_PATH)/lib/$(LIBSHARED)
+ cp $(HEADER) $(INSTALL_PATH)/include/
+
+clean:
+ rm -rf $(BUILD)
diff --git a/README b/README
@@ -0,0 +1,4 @@
+dict
+====
+
+Small dictionary type for sd_t's.
diff --git a/TODO b/TODO
@@ -0,0 +1,2 @@
+* Implement unit tests
+* Documentation
diff --git a/dict.c b/dict.c
@@ -0,0 +1,82 @@
+#include "dict.h"
+
+static inline void stack_ptr_init_size(stack_ptr *d, const size_t alloc) {
+ d->nmemb = 0;
+ d->alloc = alloc;
+
+ d->data = calloc(d->alloc, sizeof(*(d->data)));
+}
+
+static inline void stack_ptr_clear(stack_ptr *d) {
+ d->nmemb = 0;
+ free(d->data);
+ d->data = NULL;
+}
+
+static inline void stack_ptr_push(stack_ptr *d, void *x) {
+ if (d->alloc <= d->nmemb) {
+ d->alloc <<= 1;
+ d->data = realloc(d->data, d->alloc * sizeof(*(d->data)));
+ }
+
+ d->data[d->nmemb] = x;
+ d->nmemb++;
+}
+
+void dict_init_size(dict_t *d, const size_t alloc) {
+ d->nalloc = alloc;
+ d->nelts = 0;
+ d->keys = calloc(d->nalloc, sizeof(*d->keys));
+ d->values = calloc(d->nalloc, sizeof(*d->values));
+
+ size_t i;
+ for (i = 0; i < d->nalloc; i++) {
+ stack_sd_init_size(&d->keys[i], DICT_DEFAULT_STACK_SIZE);
+ stack_ptr_init_size(&d->values[i], DICT_DEFAULT_STACK_SIZE);
+ }
+}
+
+void dict_init(dict_t *d) { dict_init_size(d, DICT_DEFAULT_SIZE); }
+
+void dict_clear(dict_t *d) {
+ size_t i;
+ for (i = 0; i < d->nalloc; i++) {
+ stack_sd_clear(&d->keys[i]);
+ stack_ptr_clear(&d->values[i]);
+ }
+
+ d->nalloc = 0;
+ d->nelts = 0;
+ free(d->keys);
+ free(d->values);
+ d->keys = NULL;
+ d->values = NULL;
+}
+
+void *dict_lookup(dict_t *d, sd_t k) {
+ uint64_t h = sd_hash(&k);
+ size_t i = h % d->nalloc;
+ int stack_idx = stack_sd_lookup(&d->keys[i], k);
+
+ if (stack_idx == STACK_SD_LOOKUP_NOT_FOUND) {
+ return NULL;
+ }
+
+ return (d->values[i]).data[stack_idx];
+}
+
+#include <stdio.h>
+
+void dict_insert(dict_t *d, sd_t k, void *value) {
+ uint64_t h = sd_hash(&k);
+ size_t i = h % d->nalloc;
+ int stack_idx = stack_sd_lookup(&d->keys[i], k);
+
+ if (stack_idx == STACK_SD_LOOKUP_NOT_FOUND) {
+ stack_sd_push(&(d->keys[i]), k);
+ stack_ptr_push(&(d->values[i]), value);
+ d->nelts++;
+ } else {
+ (d->values[i]).data[stack_idx] = value;
+ }
+}
diff --git a/dict.h b/dict.h
@@ -0,0 +1,33 @@
+#ifndef DICT_H
+#define DICT_H
+
+#include "stack_sd.h"
+
+#define DICT_DEFAULT_SIZE 255
+#define DICT_DEFAULT_STACK_SIZE 2
+#define STACK_PTR_EMPTY_POP (NULL)
+#define DICT_LOOKUP_NOT_FOUND (STACK_SD_LOOKUP_NOT_FOUND) // == -1
+
+typedef struct {
+ size_t nmemb;
+ size_t alloc;
+
+ void **data;
+} stack_ptr;
+
+typedef struct {
+ size_t nelts;
+ size_t nalloc;
+
+ stack_sd_t *keys;
+ stack_ptr *values;
+} dict_t;
+
+void dict_init_size(dict_t *d, const size_t alloc);
+void dict_init(dict_t *d);
+void dict_clear(dict_t *d);
+void *dict_lookup(dict_t *d, sd_t k);
+void dict_insert(dict_t *t, sd_t k, void *v);
+void print_dict(dict_t *d);
+
+#endif
diff --git a/test_dict.c b/test_dict.c
@@ -0,0 +1,8 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include "fheap.h"
+
+int main() {
+ printf("test unimplemented\n");
+}
