diff options
| -rw-r--r-- | Makefile | 37 | ||||
| -rw-r--r-- | include/conts/conts.h | 26 | ||||
| -rw-r--r-- | include/conts/htrie.h | 199 | ||||
| -rw-r--r-- | include/conts/map.h | 104 | ||||
| -rw-r--r-- | include/conts/sptree.h | 413 | ||||
| -rw-r--r-- | include/conts/vec.h | 24 | ||||
| -rw-r--r-- | tests/map.c | 33 | ||||
| -rw-r--r-- | tests/sptree.c | 37 | ||||
| -rw-r--r-- | tests/vec.c | 13 |
9 files changed, 659 insertions, 227 deletions
@@ -1,16 +1,37 @@ -check: +CFLAGS = -g -std=c23 -Wall -Wextra +check: check-vec check-sptree check-map + +check-vec: mkdir -p build - $(CC) -g -Iinclude tests/vec.c -o build/vec - $(CC) -g -Iinclude tests/htrie.c -o build/htrie + $(CC) $(CFLAGS) -Iinclude tests/vec.c -o build/vec valgrind -q --error-exitcode=1 ./build/vec - valgrind -q --error-exitcode=1 ./build/htrie -bench: +check-sptree: + mkdir -p build + $(CC) $(CFLAGS) -Iinclude tests/sptree.c -o build/sptree + valgrind -q --error-exitcode=1 ./build/sptree + +check-map: + mkdir -p build + $(CC) $(CFLAGS) -Iinclude tests/map.c -o build/map + valgrind -q --error-exitcode=1 ./build/map + +bench: bench-vec bench-sptree bench-map + +bench-vec: 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 + $(CC) $(CFLAGS) -O2 -Iinclude tests/vec.c -o build/vec_opt time ./build/vec_opt 2> build/vec_bench.txt - time ./build/htrie_opt 2> build/htrie_bench.txt + +bench-sptree: + mkdir -p build + $(CC) $(CFLAGS) -O2 -Iinclude tests/sptree.c -o build/sptree_opt + time ./build/sptree_opt 2> build/sptree_bench.txt + +bench-map: + mkdir -p build + $(CC) $(CFLAGS) -O2 -Iinclude tests/map.c -o build/map_opt + time ./build/map_opt 2> build/map_bench.txt clean: rm -rf build diff --git a/include/conts/conts.h b/include/conts/conts.h index d965aeb..862bd31 100644 --- a/include/conts/conts.h +++ b/include/conts/conts.h @@ -4,25 +4,11 @@ #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; -} +#define CONTAINER_OF(ptr, type, member) \ + (type *)((char *)(ptr) - offsetof(type, member)) +#define foreach(name, i, s)\ + for (auto i = CONTS_JOIN(name, begin)(s);\ + !CONTS_JOIN(name, end)(s, i);\ + i = CONTS_JOIN(name, next)(i)) #endif /* CONTS_H */ diff --git a/include/conts/htrie.h b/include/conts/htrie.h deleted file mode 100644 index 26482b2..0000000 --- a/include/conts/htrie.h +++ /dev/null @@ -1,199 +0,0 @@ -#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/map.h b/include/conts/map.h new file mode 100644 index 0000000..d24ab06 --- /dev/null +++ b/include/conts/map.h @@ -0,0 +1,104 @@ +#ifndef MAP_KEY +#error "Need map key" +#endif + +#ifndef MAP_TYPE +#error "Need map type" +#endif + +#ifndef MAP_CMP +#error "Need map cmp" +#endif + +#ifndef MAP_NAME +#error "Need map name" +#endif + +#include "conts.h" + +#define MAP(a) CONTS_JOIN(MAP_NAME, a) + +#define MAP_NODE MAP(node) +#define MAP_ROOT MAP_NAME + +struct MAP_NODE { + MAP_KEY key; + MAP_TYPE data; +}; + +static inline int MAP(cmp)(struct MAP_NODE a, struct MAP_NODE b) +{ + return MAP_CMP(a.key, b.key); +} + +#define BASE(a) CONTS_JOIN(MAP(map_base), a) + +#define SPTREE_TYPE struct MAP_NODE +#define SPTREE_CMP MAP(cmp) +#define SPTREE_NAME MAP(map_base) +#include "sptree.h" + +struct MAP_ROOT { + struct MAP(map_base) root; +}; + +static inline struct MAP_ROOT MAP(create)() +{ + return (struct MAP_ROOT){.root = BASE(create)()}; +} + +static inline void MAP(destroy)(struct MAP_ROOT *root) +{ + BASE(destroy)(&root->root); +} + +static inline MAP_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY key, MAP_TYPE data) +{ + struct MAP_NODE node = {.key = key, .data = data}; + struct MAP_NODE *res = BASE(insert)(&root->root, node); + if (!res) + return NULL; + + return &res->data; +} + +static inline MAP_TYPE *MAP(find)(struct MAP_ROOT *root, MAP_KEY key) +{ + struct MAP_NODE node = {.key = key}; + struct MAP_NODE *res = BASE(find)(&root->root, node); + if (!res) + return NULL; + + return &res->data; +} + +static inline void MAP(remove)(struct MAP_ROOT *root, MAP_KEY key) +{ + struct MAP_NODE node = {.key = key}; + BASE(remove)(&root->root, node); +} + +static inline struct MAP_NODE *MAP(begin)(struct MAP_ROOT *root) +{ + return BASE(begin)(&root->root); +} + +static inline struct MAP_NODE *MAP(next)(struct MAP_NODE *n) +{ + return BASE(next)(n); +} + +static inline bool MAP(end)(struct MAP_ROOT *root, struct MAP_NODE *n) +{ + return BASE(end)(&root->root, n); +} + +static inline size_t MAP(len)(struct MAP_ROOT *root) +{ + return BASE(len)(&root->root); +} + +#undef MAP_KEY +#undef MAP_TYPE +#undef MAP_CMP +#undef MAP_NAME diff --git a/include/conts/sptree.h b/include/conts/sptree.h new file mode 100644 index 0000000..75b88fc --- /dev/null +++ b/include/conts/sptree.h @@ -0,0 +1,413 @@ +#include <stdint.h> +#include <stdlib.h> +#include <stddef.h> +#include <stdbool.h> + +#ifndef SPTREE_TYPE +#error "Need sptree type" +#endif + +#ifndef SPTREE_CMP +#error "Need sptree cmp" +#endif + +#ifndef SPTREE_NAME +#error "Need sptree name" +#endif + +#include "conts.h" + +#define SPTREE(a) CONTS_JOIN(SPTREE_NAME, a) + +#define SPNODE SPTREE(node) +#define SPROOT SPTREE_NAME + +#ifndef SPTREE_H +#define SPTREE_H + +#define sp_left(n) ((n)->left) +#define sp_right(n) ((n)->right) +#define sp_paren(n) ((n)->parent) +#define sp_lparen(n) (sp_left(n)->parent) +#define sp_rparen(n) (sp_right(n)->parent) + +#endif /* SPTREE_H */ + +struct SPNODE { + int_fast16_t hint; + struct SPNODE *left, *right, *parent; + SPTREE_TYPE data; +}; + +struct SPROOT { + size_t n; + struct SPNODE *root; +}; + +static inline struct SPROOT SPTREE(create)() +{ + return (struct SPROOT){.n = 0, .root = NULL}; +} + +static inline size_t SPTREE(len)(struct SPROOT *s) +{ + return s->n; +} + +static inline struct SPNODE *SPTREE(first)(struct SPNODE *n) +{ + while (sp_left(n)) + n = sp_left(n); + + return n; +} + +static inline struct SPNODE *SPTREE(last)(struct SPNODE *n) +{ + while (sp_right(n)) + n = sp_right(n); + + return n; +} + +static inline SPTREE_TYPE *SPTREE(begin)(struct SPROOT *s) +{ + return &SPTREE(first)(s->root)->data; +} + +static inline SPTREE_TYPE *SPTREE(next)(SPTREE_TYPE *prev) +{ + struct SPNODE *n = CONTAINER_OF(prev, struct SPNODE, data); + if (sp_right(n)) { + n = sp_right(n); + while (sp_left(n)) + n = sp_left(n); + + return &n->data; + } + + while (n) { + struct SPNODE *p = sp_paren(n); + if (!p) + return NULL; + + if (sp_left(p) == n) + return &p->data; + + n = p; + } + + return NULL; +} + +static inline bool SPTREE(end)(struct SPROOT *s, SPTREE_TYPE *prev) +{ + (void)s; + return prev == NULL; +} + +static inline void SPTREE(turn_left)(struct SPNODE *n) +{ + struct SPNODE *l = sp_left(n); + struct SPNODE *p = sp_paren(n); + + assert(l); + + sp_paren(l) = sp_paren(n); + sp_left(n) = sp_right(l); + sp_paren(n) = l; + sp_right(l) = n; + + if (p && sp_left(p) == n) + sp_left(p) = l; + else if (p) + sp_right(p) = l; + + if (sp_left(n)) + sp_lparen(n) = n; +} + +static inline void SPTREE(turn_right)(struct SPNODE *n) +{ + struct SPNODE *r = sp_right(n); + struct SPNODE *p = sp_paren(n); + + assert(r); + + sp_paren(r) = sp_paren(n); + sp_right(n) = sp_left(r); + sp_paren(n) = r; + sp_left(r) = n; + + if (p && sp_left(p) == n) + sp_left(p) = r; + else if (p) + sp_right(p) = r; + + if (sp_right(n)) + sp_rparen(n) = n; +} + +static inline int_fast16_t SPTREE(leaning)(struct SPNODE *n) +{ + int_fast16_t l = 0; + int_fast16_t r = 0; + + if (sp_left(n)) + l = sp_left(n)->hint + 1; + + if (sp_right(n)) + r = sp_right(n)->hint + 1; + + return l - r; +} + +static inline int_fast16_t SPTREE(max_hint)(struct SPNODE *n) +{ + int_fast16_t l = 0; + int_fast16_t r = 0; + + if (sp_left(n)) + l = sp_left(n)->hint + 1; + + if (sp_right(n)) + r = sp_right(n)->hint + 1; + + if (l > r) + return l; + else + return r; +} + +static inline void SPTREE(update)(struct SPROOT *r, struct SPNODE *n) +{ + while (n) { + int b = SPTREE(leaning)(n); + int prev_hint = n->hint; + struct SPNODE *p = sp_paren(n); + + if (b < -1) { + /* leaning to the right */ + if (n == r->root) + r->root = sp_right(n); + + SPTREE(turn_right)(n); + } + + else if (b > 1) { + /* leaning to the left */ + if (n == r->root) + r->root = sp_left(n); + + SPTREE(turn_left)(n); + } + + n->hint = SPTREE(max_hint)(n); + if (n->hint == 0 || n->hint != prev_hint) + n = p; + else + return; + } +} + +static inline SPTREE_TYPE *SPTREE(insert)(struct SPROOT *s, SPTREE_TYPE data) +{ + if (!s->root) { + assert(s->n == 0); + struct SPNODE *new = malloc(sizeof(struct SPNODE)); + if (!new) + return NULL; + + new->left = new->right = new->parent = NULL; + new->data = data; + new->hint = 0; + + s->root = new; + s->n = 1; + return &new->data; + } + + bool insert_left = false; + + struct SPNODE *n = s->root; + struct SPNODE *p = NULL; + while (n) { + p = n; + int c = SPTREE_CMP(n->data, data); + if (c < 0) { + n = sp_left(n); + insert_left = true; + continue; + } + if (c > 0) { + n = sp_right(n); + insert_left = false; + continue; + } + + /* we already have a node like this */ + return &n->data; + } + + struct SPNODE *new = malloc(sizeof(struct SPNODE)); + if (!new) + return NULL; + + new->left = new->right = NULL; + new->parent = p; + new->data = data; + new->hint = 0; + + if (insert_left) + sp_left(p) = new; + else + sp_right(p) = new; + + SPTREE(update)(s, new); + s->n++; + return &new->data; +} + +static inline void SPTREE(replace_right)(struct SPNODE *n, struct SPNODE *r) +{ + struct SPNODE *p = sp_paren(n); + struct SPNODE *rp = sp_paren(r); + + if (sp_left(rp) == r) { + sp_left(rp) = sp_right(r); + if (sp_right(r)) + sp_rparen(r) = rp; + } + + if (sp_paren(rp) == n) + sp_paren(rp) = r; + + sp_paren(r) = p; + sp_left(r) = sp_left(n); + + if (sp_right(n) != r) { + sp_right(r) = sp_right(n); + sp_rparen(n) = r; + } + + if (p && sp_left(p) == n) + sp_left(p) = r; + else if (p) + sp_right(p) = r; + + if (sp_left(n)) + sp_lparen(n) = r; +} + +static inline void SPTREE(replace_left)(struct SPNODE *n, struct SPNODE *l) +{ + struct SPNODE *p = sp_paren(n); + struct SPNODE *lp = sp_paren(l); + + if (sp_right(lp) == l) { + sp_right(lp) = sp_left(l); + if (sp_left(l)) + sp_lparen(l) = lp; + } + + if (sp_paren(lp) == n) + sp_paren(lp) = l; + + sp_paren(l) = p; + sp_right(l) = sp_right(n); + + if (sp_left(n) != l) { + sp_left(l) = sp_left(n); + sp_lparen(n) = l; + } + + if (p && sp_left(p) == n) + sp_left(p) = l; + else if (p) + sp_right(p) = l; + + if (sp_right(n)) + sp_rparen(n) = l; +} + +static inline SPTREE_TYPE *SPTREE(find)(struct SPROOT *s, SPTREE_TYPE data) +{ + struct SPNODE *n = s->root; + while (n) { + int c = SPTREE_CMP(n->data, data); + if (c < 0) { + n = n->left; + continue; + } + + if (c > 0) { + n = n->right; + continue; + } + + return &n->data; + } + + return NULL; +} + +static inline void SPTREE(remove_found)(struct SPROOT *s, SPTREE_TYPE *found) +{ + s->n--; + struct SPNODE *del = CONTAINER_OF(found, struct SPNODE, data); + if (sp_right(del)) { + struct SPNODE *least = SPTREE(first)(sp_right(del)); + + if (del == s->root) + s->root = least; + + SPTREE(replace_right)(del, least); + SPTREE(update)(s, sp_right(least)); + return; + } + + if (sp_left(del)) { + struct SPNODE *most = SPTREE(last)(sp_left(del)); + + if (del == s->root) + s->root = most; + + SPTREE(replace_left)(del, most); + SPTREE(update)(s, sp_left(most)); + return; + } + + if (del == s->root) { + s->root = NULL; + return; + } + + /* empty node */ + struct SPNODE *paren = sp_paren(del); + + if (sp_left(paren) == del) + sp_left(paren) = NULL; + else + sp_right(paren) = NULL; + + SPTREE(update)(s, paren); +} + +static inline void SPTREE(remove)(struct SPROOT *s, SPTREE_TYPE data) +{ + SPTREE_TYPE *found = SPTREE(find)(s, data); + if (!found) + return; + + SPTREE(remove_found)(s, found); +} + +static inline void SPTREE(destroy)(struct SPROOT *s) +{ + while (s->root) + SPTREE(remove_found)(s, &s->root->data); +} + +#undef SPTREE +#undef SPNODE +#undef SPROOT diff --git a/include/conts/vec.h b/include/conts/vec.h index ccdfe81..a11927f 100644 --- a/include/conts/vec.h +++ b/include/conts/vec.h @@ -7,6 +7,7 @@ #endif #include <stdbool.h> +#include <string.h> #include <stdlib.h> #include <assert.h> @@ -111,6 +112,29 @@ static inline void VEC(shrink)(struct VEC_STRUCT *v, size_t n) v->n = n; } +static inline void VEC(remove)(struct VEC_STRUCT *v, size_t i) +{ + assert(v->n > i); + size_t c = sizeof(VEC_TYPE) * (v->n - i); + memcpy(&v->buf[i], &v->buf[i + 1], c); + v->n--; +} + +static inline VEC_TYPE *VEC(begin)(struct VEC_STRUCT *v) +{ + return &v->buf[0]; +} + +static inline bool VEC(end)(struct VEC_STRUCT *v, VEC_TYPE *i) +{ + return &v->buf[v->n - 1] == i; +} + +static inline VEC_TYPE *VEC(next)(VEC_TYPE *i) +{ + return i + 1; +} + #undef VEC #undef VEC_TYPE #undef VEC_NAME diff --git a/tests/map.c b/tests/map.c new file mode 100644 index 0000000..e9362ab --- /dev/null +++ b/tests/map.c @@ -0,0 +1,33 @@ +#include <assert.h> +#include <stdio.h> + +#define MAP_KEY int +#define MAP_TYPE int +#define MAP_CMP(a, b) ((a) - (b)) +#define MAP_NAME ints +#include <conts/map.h> + +int main() +{ + struct ints ints = ints_create(); + for (int i = 0; i < 1000000; ++i) { + ints_insert(&ints, i, i); + } + assert(ints_len(&ints) == 1000000); + + for (int i = 0; i < 1000000; ++i) { + int *v = ints_find(&ints, i); + assert(v && *v == i); + } + + foreach(ints, iter, &ints) { + assert(iter->key == iter->data); + } + + for (int i = 0; i < 1000000; ++i) { + ints_remove(&ints, i); + } + + assert(ints_len(&ints) == 0); + ints_destroy(&ints); +} diff --git a/tests/sptree.c b/tests/sptree.c new file mode 100644 index 0000000..b8d1e5a --- /dev/null +++ b/tests/sptree.c @@ -0,0 +1,37 @@ +#include <assert.h> +#include <stdio.h> + +#define SPTREE_TYPE int +#define SPTREE_CMP(a, b) ((b) - (a)) +#define SPTREE_NAME ints +#include <conts/sptree.h> + +int main() +{ + struct ints ints = ints_create(); + for (int i = 0; i < 1000000; ++i) { + ints_insert(&ints, i); + } + assert(ints_len(&ints) == 1000000); + + for (int i = 0; i < 1000000; ++i) { + int *v = ints_find(&ints, i); + assert(v && *v == i); + } + + int i = 0; + foreach(ints, iter, &ints) { + /* since my trees are ordered, this must hold, although you + * might consider it an implementation detail that shouldn't be + * relied on */ + assert(iter && *iter == i); + i++; + } + + for (int i = 0; i < 1000000; ++i) { + ints_remove(&ints, i); + } + + assert(ints_len(&ints) == 0); + ints_destroy(&ints); +} diff --git a/tests/vec.c b/tests/vec.c index 4bc06e7..a84096c 100644 --- a/tests/vec.c +++ b/tests/vec.c @@ -10,10 +10,23 @@ int main() for (int i = 0; i < 1000000; ++i) { ints_append(&ints, i); } + assert(ints_len(&ints) == 1000000); for (int i = 0; i < 1000000; ++i) { int *v = ints_at(&ints, i); assert(v && *v == i); } + + int i = 0; + foreach(ints, iter, &ints) { + assert(iter && *iter == i); + i++; + } + + for (int i = 1000000 - 1; i >= 0; --i) { + ints_remove(&ints, i); + } + assert(ints_len(&ints) == 0); + ints_destroy(&ints); } |