summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore1
-rw-r--r--Makefile16
-rw-r--r--include/conts/conts.h28
-rw-r--r--include/conts/htrie.h199
-rw-r--r--include/conts/vec.h117
-rw-r--r--tests/htrie.c22
-rw-r--r--tests/vec.c19
7 files changed, 402 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..378eac2
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+build
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..48e8cb8
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,16 @@
+check:
+ mkdir -p build
+ $(CC) -g -Iinclude tests/vec.c -o build/vec
+ $(CC) -g -Iinclude tests/htrie.c -o build/htrie
+ valgrind -q --error-exitcode=1 ./build/vec
+ valgrind -q --error-exitcode=1 ./build/htrie
+
+bench:
+ mkdir -p build
+ $(CC) -g -O2 -Iinclude tests/vec.c -o build/vec_opt
+ $(CC) -g -O2 -Iinclude tests/htrie.c -o build/htrie_opt
+ time ./build/vec_opt 2> build/vec_bench.txt
+ time ./build/htrie_opt 2> build/htrie_bench.txt
+
+clean:
+ rm -rf build
diff --git a/include/conts/conts.h b/include/conts/conts.h
new file mode 100644
index 0000000..d965aeb
--- /dev/null
+++ b/include/conts/conts.h
@@ -0,0 +1,28 @@
+#ifndef CONTS_H
+#define CONTS_H
+
+#define CONTS_JOIN2(a, b) a##_##b
+#define CONTS_JOIN(a, b) CONTS_JOIN2(a, b)
+
+static inline unsigned long conts_strhash(const char *str)
+{
+ /* http://www.cse.yorku.ca/%7Eoz/hash.html, djb2 */
+ unsigned long hash = 5381;
+ int c;
+
+ while (c = *str++)
+ hash = ((hash << 5) + hash) + c;
+
+ return hash;
+}
+
+static inline unsigned long conts_inthash(unsigned long x)
+{
+ /* https://xorshift.di.unimi.it/splitmix64.c */
+ x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
+ x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
+ x = (x ^ (x >> 31));
+ return x;
+}
+
+#endif /* CONTS_H */
diff --git a/include/conts/htrie.h b/include/conts/htrie.h
new file mode 100644
index 0000000..26482b2
--- /dev/null
+++ b/include/conts/htrie.h
@@ -0,0 +1,199 @@
+#ifndef HTRIE_KEY
+#error "Need htrie key"
+#endif
+
+#ifndef HTRIE_CMP
+#error "Need htrie cmp"
+#endif
+
+#ifndef HTRIE_HASH
+#error "Need htrie hash"
+#endif
+
+#ifndef HTRIE_TYPE
+#error "Need htrie type"
+#endif
+
+#ifndef HTRIE_NAME
+#error "Need htrie name"
+#endif
+
+#include <stdlib.h>
+#include <stdbool.h>
+#include "conts.h"
+
+#define HTRIE(a) CONTS_JOIN(HTRIE_NAME, a)
+
+#define HTRIE_STRUCT HTRIE_NAME
+#define HTRIE_NODE CONTS_JOIN(HTRIE_NAME, node)
+
+struct HTRIE_NODE {
+ unsigned long hash;
+ HTRIE_KEY key;
+ struct HTRIE_NODE *left, *right;
+ HTRIE_TYPE data;
+};
+
+struct HTRIE_STRUCT {
+ size_t n;
+ struct HTRIE_NODE *root;
+};
+
+static inline struct HTRIE_STRUCT HTRIE(create)()
+{
+ return (struct HTRIE_STRUCT){.n = 0, .root = NULL};
+}
+
+static inline bool HTRIE(empty)(struct HTRIE_STRUCT *h)
+{
+ return h->n == 0;
+}
+
+static inline size_t HTRIE(len)(struct HTRIE_STRUCT *h)
+{
+ return h->n;
+}
+
+static inline HTRIE_TYPE *HTRIE(insert)(struct HTRIE_STRUCT *h, HTRIE_KEY key, HTRIE_TYPE data)
+{
+ unsigned long hash = HTRIE_HASH(key);
+ if (!h->root) {
+ assert(h->n == 0);
+ struct HTRIE_NODE *new = malloc(sizeof(struct HTRIE_NODE));
+ if (!new)
+ return NULL;
+
+ new->hash = hash;
+ new->key = key;
+ new->data = data;
+ new->left = NULL;
+ new->right = NULL;
+
+ h->root = new;
+ h->n = 1;
+ return &new->data;
+ }
+
+ bool insert_left = true;
+ struct HTRIE_NODE *n = h->root;
+ while (n) {
+ if (n->hash < hash) {
+ if (!n->left) {
+ insert_left = true;
+ break;
+ }
+
+ n = n->left;
+ continue;
+ }
+
+ if (n->hash > hash) {
+ if (!n->right) {
+ insert_left = false;
+ break;
+ }
+
+ n = n->right;
+ continue;
+ }
+
+ /* n->hash == hash */
+ int c = HTRIE_CMP(n->key, key);
+
+ /* already exists */
+ if (c < 0) {
+ if (!n->left) {
+ insert_left = true;
+ break;
+ }
+
+ n = n->left;
+ continue;
+ }
+
+ if (c > 0) {
+ if (!n->right) {
+ insert_left = false;
+ break;
+ }
+
+ n = n->right;
+ continue;
+ }
+
+ /* otherwise, node already exists */
+ return &n->data;
+
+ }
+
+ struct HTRIE_NODE *new = malloc(sizeof(struct HTRIE_NODE));
+ if (!new)
+ return NULL;
+
+ new->hash = hash;
+ new->key = key;
+ new->data = data;
+ new->left = NULL;
+ new->right = NULL;
+
+ if (insert_left)
+ n->left = new;
+ else
+ n->right = new;
+
+ h->n++;
+ return &new->data;
+}
+
+static inline HTRIE_TYPE *HTRIE(at)(struct HTRIE_STRUCT *h, HTRIE_KEY key)
+{
+ unsigned long hash = HTRIE_HASH(key);
+
+ struct HTRIE_NODE *n = h->root;
+ while (n) {
+ if (n->hash < hash) {
+ n = n->left;
+ continue;
+ }
+
+ if (n->hash > hash) {
+ n = n->right;
+ continue;
+ }
+
+ int c = HTRIE_CMP(n->key, key);
+ if (c < 0) {
+ n = n->left;
+ continue;
+ }
+
+ if (c > 0) {
+ n = n->right;
+ continue;
+ }
+
+ /* otherwise, we found our node */
+ break;
+ }
+
+ if (!n)
+ return NULL;
+
+ return &n->data;
+}
+
+static inline void HTRIE(destroy_node)(struct HTRIE_NODE *n)
+{
+ if (n->left)
+ HTRIE(destroy_node)(n->left);
+
+ if (n->right)
+ HTRIE(destroy_node)(n->right);
+
+ free(n);
+}
+
+static inline void HTRIE(destroy)(struct HTRIE_STRUCT *h)
+{
+ HTRIE(destroy_node)(h->root);
+}
diff --git a/include/conts/vec.h b/include/conts/vec.h
new file mode 100644
index 0000000..ccdfe81
--- /dev/null
+++ b/include/conts/vec.h
@@ -0,0 +1,117 @@
+#ifndef VEC_TYPE
+#error "Need vector type"
+#endif
+
+#ifndef VEC_NAME
+#error "Need vector name"
+#endif
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include "conts.h"
+
+#define VEC(a) CONTS_JOIN(VEC_NAME, a)
+
+#define VEC_STRUCT VEC_NAME
+struct VEC_STRUCT {
+ size_t n;
+ size_t s;
+ VEC_TYPE *buf;
+};
+
+#ifndef CONTS_VEC_H
+#define CONTS_VEC_H
+
+#define foreach_vec(iter, v) \
+ for (size_t iter = 0; iter < (v)->n; ++iter)
+
+#endif /* CONTS_VEC_H */
+
+static inline struct VEC_STRUCT VEC(create)(size_t reserve)
+{
+ return (struct VEC_STRUCT) {
+ .n = 0,
+ .s = reserve,
+ .buf = malloc(reserve * sizeof(VEC_TYPE)),
+ };
+}
+
+static inline bool VEC(uninit)(struct VEC_STRUCT *v)
+{
+ return v->buf == NULL;
+}
+
+static inline size_t VEC(len)(struct VEC_STRUCT *v)
+{
+ return v->n;
+}
+
+static inline VEC_TYPE *VEC(at)(struct VEC_STRUCT *v, size_t i)
+{
+ assert(i < v->n && "out of vector bounds");
+ return &v->buf[i];
+}
+
+static inline VEC_TYPE *VEC(back)(struct VEC_STRUCT *v)
+{
+ assert(v->n);
+ return &v->buf[v->n - 1];
+}
+
+static inline VEC_TYPE *VEC(pop)(struct VEC_STRUCT *v)
+{
+ assert(v->n && "attempting to pop empty vector");
+ v->n--;
+ return &v->buf[v->n];
+}
+
+static inline void VEC(append)(struct VEC_STRUCT *v, VEC_TYPE n)
+{
+ v->n++;
+ if (v->n >= v->s) {
+ v->s = v->s == 0 ? 1 : 2 * v->s;
+ v->buf = realloc(v->buf, v->s * sizeof(VEC_TYPE));
+ }
+
+ v->buf[v->n - 1] = n;
+}
+
+static inline void VEC(reset)(struct VEC_STRUCT *v)
+{
+ v->n = 0;
+}
+
+static inline void VEC(destroy)(struct VEC_STRUCT *v) {
+ free(v->buf);
+}
+
+typedef int (*VEC(comp_t))(VEC_TYPE *a, VEC_TYPE *b);
+static inline void VEC(sort)(struct VEC_STRUCT *v, VEC(comp_t) comp)
+{
+ qsort(v->buf, v->n, sizeof(VEC_TYPE), (__compar_fn_t)comp);
+}
+
+static inline void VEC(reserve)(struct VEC_STRUCT *v, size_t n)
+{
+ if (v->n >= n)
+ return;
+
+ v->n = n;
+ if (v->s < v->n) {
+ v->s *= 2;
+ v->buf = realloc(v->buf, v->s * sizeof(VEC_TYPE));
+ }
+}
+
+static inline void VEC(shrink)(struct VEC_STRUCT *v, size_t n)
+{
+ assert(v->n >= n);
+ v->n = n;
+}
+
+#undef VEC
+#undef VEC_TYPE
+#undef VEC_NAME
+#undef VEC_STRUCT
diff --git a/tests/htrie.c b/tests/htrie.c
new file mode 100644
index 0000000..2c70b38
--- /dev/null
+++ b/tests/htrie.c
@@ -0,0 +1,22 @@
+#include <assert.h>
+
+#define HTRIE_TYPE int
+#define HTRIE_KEY int
+#define HTRIE_HASH conts_inthash
+#define HTRIE_CMP(a, b) ((a) - (b))
+#define HTRIE_NAME ints
+#include <conts/htrie.h>
+
+int main()
+{
+ struct ints ints = ints_create();
+ for (int i = 0; i < 1000000; ++i) {
+ ints_insert(&ints, i, i);
+ }
+
+ for (int i = 0; i < 1000000; ++i) {
+ int *v = ints_at(&ints, i);
+ assert(v && *v == i);
+ }
+ ints_destroy(&ints);
+}
diff --git a/tests/vec.c b/tests/vec.c
new file mode 100644
index 0000000..4bc06e7
--- /dev/null
+++ b/tests/vec.c
@@ -0,0 +1,19 @@
+#include <assert.h>
+
+#define VEC_TYPE int
+#define VEC_NAME ints
+#include <conts/vec.h>
+
+int main()
+{
+ struct ints ints = ints_create(0);
+ for (int i = 0; i < 1000000; ++i) {
+ ints_append(&ints, i);
+ }
+
+ for (int i = 0; i < 1000000; ++i) {
+ int *v = ints_at(&ints, i);
+ assert(v && *v == i);
+ }
+ ints_destroy(&ints);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-05 13:32:35 +0000