commit c2dc972e6c157f5ea6c5e4b9a124d7a46c5d8145
Author: olikru <olikru@tkruger.se>
Date: Mon, 8 Jan 2024 14:56:20 +0100
initial
Diffstat:
| A | Makefile | | | 40 | ++++++++++++++++++++++++++++++++++++++++ |
| A | README | | | 5 | +++++ |
| A | TODO | | | 1 | + |
| A | set_u64.c | | | 70 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | set_u64.h | | | 28 | ++++++++++++++++++++++++++++ |
| A | test_set_u64.c | | | 28 | ++++++++++++++++++++++++++++ |
6 files changed, 172 insertions(+), 0 deletions(-)
diff --git a/Makefile b/Makefile
@@ -0,0 +1,40 @@
+.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
+
+INSTALL_PATH=$(HOME)/.local
+BUILD=build
+
+TEST_SOURCE=test_set_u64.c
+HEADER=set_u64.h
+OBJS=set_u64.o
+SHARED=set_u64.so
+LIBSHARED=libset_u64.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 @@
+set_u64
+=======
+
+Small library for some very basic functions for sets of uint64_t's. This
+is based on a hash-table implementation.
diff --git a/TODO b/TODO
@@ -0,0 +1 @@
+* Implement unit tests for the non-tested functions.
diff --git a/set_u64.c b/set_u64.c
@@ -0,0 +1,70 @@
+#include "set_u64.h"
+
+void set_u64_init_size(set_u64_t *s, const size_t size) {
+ size_t i;
+ s->nalloc = size;
+ s->nelts = 0;
+
+ s->head = malloc((s->nalloc) * sizeof(*(s->head)));
+
+ for (i = 0; i < s->nalloc; i++)
+ LIST_INIT(&(s->head[i]));
+}
+
+void set_u64_init(set_u64_t *s) { set_u64_init_size(s, SET_U64_DEFAULT_SIZE); }
+
+void set_u64_clear(set_u64_t *s) {
+ size_t i;
+ struct list_entry *n1;
+
+ for (i = 0; i < s->nalloc; i++) {
+ while (!LIST_EMPTY(&(s->head[i]))) {
+ n1 = LIST_FIRST(&(s->head[i]));
+ LIST_REMOVE(n1, entries);
+ free(n1);
+ }
+ }
+
+ free(s->head);
+ s->head = NULL;
+ s->nalloc = 0;
+ s->nelts = 0;
+}
+
+static inline size_t u64_hash(const uint64_t c) { return (size_t)c; }
+
+static inline le_t *list_lookup(struct listhead h, uint64_t v) {
+ le_t *np;
+ LIST_FOREACH(np, &h, entries) {
+ if (np->value == v)
+ return np;
+ }
+
+ return NULL;
+}
+
+size_t set_u64_lookup(le_t *r, set_u64_t *s, uint64_t v) {
+ size_t i = u64_hash(v) % s->nalloc;
+ le_t *elt = list_lookup(s->head[i], v);
+
+ if (elt != NULL) {
+ *r = *elt;
+ return i;
+ }
+
+ return SIZE_MAX;
+}
+
+int set_u64_insert(set_u64_t *s, uint64_t v) {
+ size_t i = u64_hash(v) % s->nalloc;
+
+ if (list_lookup(s->head[i], v) == NULL) {
+ le_t *new = malloc(sizeof(*new));
+ new->value = v;
+ LIST_INSERT_HEAD(&(s->head[i]), new, entries);
+ s->nelts++;
+ return 1;
+ }
+
+ return 0;
+}
diff --git a/set_u64.h b/set_u64.h
@@ -0,0 +1,28 @@
+#ifndef SET_U64_H
+#define SET_U64_H
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <sys/queue.h>
+
+#define SET_U64_DEFAULT_SIZE (255)
+
+typedef struct list_entry {
+ uint64_t value;
+ LIST_ENTRY(list_entry) entries;
+} le_t;
+
+typedef struct {
+ size_t nelts;
+ size_t nalloc;
+
+ LIST_HEAD(listhead, list_entry) * head;
+} set_u64_t;
+
+void set_u64_init_size(set_u64_t *s, const size_t size);
+void set_u64_init(set_u64_t *s);
+void set_u64_clear(set_u64_t *s);
+size_t set_u64_lookup(le_t *r, set_u64_t *s, uint64_t v);
+int set_u64_insert(set_u64_t *s, uint64_t v);
+
+#endif
diff --git a/test_set_u64.c b/test_set_u64.c
@@ -0,0 +1,28 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include "set_u64.h"
+
+static void test_set_u64_init() {
+ set_u64_t s;
+
+ set_u64_init(&s);
+ assert(s.nelts == 0);
+ assert(s.nalloc == SET_U64_DEFAULT_SIZE);
+ assert(LIST_EMPTY(&(s.head[0])));
+
+ set_u64_clear(&s);
+
+ set_u64_init_size(&s, 23);
+ assert(s.nelts == 0);
+ assert(s.nalloc == 23);
+ assert(LIST_EMPTY(&(s.head[0])));
+
+ set_u64_clear(&s);
+}
+
+int main() {
+ test_set_u64_init();
+
+ printf("test ok\n");
+}
