commit d7a5af492d1e69145f0cc2330145dc9f000f81e6
Author: olikru <olikru@tkruger.se>
Date: Mon, 8 Jan 2024 14:33:08 +0100
initial
Diffstat:
| A | Makefile | | | 43 | +++++++++++++++++++++++++++++++++++++++++++ |
| A | README | | | 5 | +++++ |
| A | ht.c | | | 40 | ++++++++++++++++++++++++++++++++++++++++ |
| A | ht.h | | | 73 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | test_ht.c | | | 86 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
5 files changed, 247 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_ht.c
+HEADER=ht.h
+OBJS=ht.o
+SHARED=ht.so
+LIBSHARED=libht.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,5 @@
+ht
+==
+
+Small hashtable implementation. Here a hash table is just a set of
+sd_t's.
diff --git a/ht.c b/ht.c
@@ -0,0 +1,40 @@
+#include "ht.h"
+
+void ht_init_size(ht_t *t, const size_t alloc) {
+ t->nalloc = alloc;
+ t->nelts = 0;
+ t->entries = calloc(t->nalloc, sizeof(*t->entries));
+
+ size_t i;
+ for (i = 0; i < t->nalloc; i++)
+ stack_sd_init_size(&t->entries[i], HT_DEFAULT_STACK_SIZE);
+}
+
+void ht_init(ht_t *t) { ht_init_size(t, HT_DEFAULT_SIZE); }
+
+void ht_clear(ht_t *t) {
+ size_t i;
+ for (i = 0; i < t->nalloc; i++)
+ stack_sd_clear(&t->entries[i]);
+
+ t->nalloc = 0;
+ t->nelts = 0;
+ free(t->entries);
+ t->entries = NULL;
+}
+
+int ht_lookup(ht_t *t, sd_t d) {
+ uint64_t h = sd_hash(&d);
+ size_t i = h % t->nalloc;
+ return stack_sd_lookup(&t->entries[i], d);
+}
+
+void ht_insert(ht_t *t, sd_t d) {
+ if (ht_lookup(t, d) != STACK_SD_LOOKUP_NOT_FOUND)
+ return;
+
+ size_t i = sd_hash(&d) % t->nalloc;
+ stack_sd_push(&t->entries[i], d);
+
+ t->nelts++;
+}
diff --git a/ht.h b/ht.h
@@ -0,0 +1,73 @@
+#ifndef HT_H
+#define HT_H
+
+#include <stack_sd.h>
+
+#define HT_DEFAULT_SIZE 255
+#define HT_DEFAULT_STACK_SIZE 2
+#define HT_LOOKUP_NOT_FOUND (STACK_SD_LOOKUP_NOT_FOUND) // == -1
+
+typedef struct {
+ size_t nelts;
+ size_t nalloc;
+
+ stack_sd_t *entries;
+} ht_t;
+
+/**
+ * Intitialize a hash table.
+ *
+ * This initializes a hash table of <<alloc>> buckets, at the address
+ * pointed to by <<t>>. Note that this memory needs to be cleared.
+ *
+ * @param t pointer to the ht_t to be initialized
+ * @param alloc the number of buckets to allocate for
+ */
+void ht_init_size(ht_t *t, const size_t alloc);
+
+/**
+ * Initialize a hash table.
+ *
+ * This initializes a hash table of the default size which is
+ * HT_DEFAULT_SIZE number of buckets. Note that this allocates memory
+ * that needs to be ht_clear'd.
+ *
+ * @param t pointer to the th to initialized
+ */
+void ht_init(ht_t *t);
+
+/**
+ * Clear a stack.
+ *
+ * @param t the stack to clear
+ */
+void ht_clear(ht_t *t);
+
+/**
+ * Lookup a sd_t in the hashtable.
+ *
+ * Returns a nonnegative value if the sd_t is in the hash table (by value
+ * comparison rather than pointer comparison of data). The value is the
+ * index of the stack_sd_t in the hash bucket where the sd_t is found. If
+ * the sd_t cannot be found in the stack the value
+ * HT_LOOKUP_NOT_FOUND == -1
+ * is returned.
+ *
+ * @param t pointer to the hash table too look up in
+ * @param d the sd_t to look up
+ */
+int ht_lookup(ht_t *t, sd_t d);
+
+/**
+ * Insert a as into the hashtable.
+ *
+ * Inserts a sd_t into the hash table. Note that this does not copy the
+ * sd_t data, but only pushes the pointer onto the stack. The sd_t should
+ * therefore not be cleared until ht_t has been cleared.
+ *
+ * @param t pointer to the hash table to insert into
+ * @param d the sd_t to insert
+ */
+void ht_insert(ht_t *t, sd_t d);
+
+#endif
diff --git a/test_ht.c b/test_ht.c
@@ -0,0 +1,86 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include "ht.h"
+
+static void test_ht_init() {
+ ht_t h;
+
+ ht_init(&h);
+ assert(h.nelts == 0);
+ assert(h.nalloc == HT_DEFAULT_SIZE);
+ assert(h.entries != NULL);
+
+ ht_clear(&h);
+
+ ht_init_size(&h, 23);
+ assert(h.nelts == 0);
+ assert(h.nalloc == 23);
+ assert(h.entries != NULL);
+
+ ht_clear(&h);
+}
+
+static void test_ht_insert() {
+ ht_t h;
+ ht_init_size(&h, 16);
+
+ sd_t elts[17];
+
+ size_t i;
+ for (i = 0; i < 17; i++) {
+ sd_init_u64(&elts[i], i);
+ ht_insert(&h, elts[i]);
+ assert(h.nelts == i + 1);
+ }
+
+ sd_t tmp;
+ sd_init_u64(&tmp, 12);
+ ht_insert(&h, tmp);
+ assert(h.nelts == 17);
+
+ for (i = 0; i < 17; i++)
+ sd_clear(&elts[i]);
+
+ ht_clear(&h);
+}
+
+static void test_ht_lookup() {
+ ht_t h;
+ ht_init_size(&h, 32);
+
+ sd_t elts[17];
+
+ size_t i;
+ for (i = 0; i < 17; i++) {
+ sd_init_u64(&elts[i], 2 * i);
+ ht_insert(&h, elts[i]);
+ }
+
+ sd_t nelts[2 * 17];
+ for (i = 0; i < 2 * 17; i++) {
+ sd_init_u64(&nelts[i], i);
+ if (i % 2 == 0) {
+ int index = ht_lookup(&h, nelts[i]);
+ assert(index <= 17);
+ assert(index >= 0);
+ } else {
+ assert(ht_lookup(&h, nelts[i]) == HT_LOOKUP_NOT_FOUND);
+ }
+ }
+
+ for (i = 0; i < 17; i++)
+ sd_clear(&elts[i]);
+ for (i = 0; i < 2 * 17; i++)
+ sd_clear(&nelts[i]);
+
+ ht_clear(&h);
+}
+
+int main() {
+ test_ht_init();
+ test_ht_insert();
+ test_ht_lookup();
+
+ printf("test ok\n");
+}
