From 7b5abecd2bef6b7441b0d850f95d451b441a6f76 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Tue, 18 Mar 2025 19:58:30 +0200 Subject: move to generic conts --- include/ek/conts.h | 14 -- include/ek/map.h | 105 ------------- include/ek/scope.h | 6 +- include/ek/sptree.h | 426 ---------------------------------------------------- include/ek/vec.h | 46 ------ 5 files changed, 3 insertions(+), 594 deletions(-) delete mode 100644 include/ek/conts.h delete mode 100644 include/ek/map.h delete mode 100644 include/ek/sptree.h delete mode 100644 include/ek/vec.h (limited to 'include') diff --git a/include/ek/conts.h b/include/ek/conts.h deleted file mode 100644 index c1e4d24..0000000 --- a/include/ek/conts.h +++ /dev/null @@ -1,14 +0,0 @@ -#ifndef CONTS_H -#define CONTS_H - -#define CONTS_JOIN2(a, b) a##_##b -#define CONTS_JOIN(a, b) CONTS_JOIN2(a, b) - -#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/ek/map.h b/include/ek/map.h deleted file mode 100644 index 5a6a22d..0000000 --- a/include/ek/map.h +++ /dev/null @@ -1,105 +0,0 @@ -#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/ek/scope.h b/include/ek/scope.h index 810f1cc..8c56640 100644 --- a/include/ek/scope.h +++ b/include/ek/scope.h @@ -33,7 +33,7 @@ struct visible_tuple { #define MAP_TYPE struct ast * #define MAP_CMP(a, b) strcmp((a), (b)) #define MAP_NAME visible -#include "map.h" +#include struct expanded_key { struct ast *def; @@ -54,12 +54,12 @@ static inline int expanded_key_cmp(struct expanded_key a, struct expanded_key b) #define MAP_TYPE struct ast * #define MAP_CMP(a, b) expanded_key_cmp((a), (b)) #define MAP_NAME expanded -#include "map.h" +#include #define SPTREE_TYPE struct ast * #define SPTREE_CMP(a, b) ((uintptr_t)(a) - (uintptr_t)(b)) #define SPTREE_NAME exported -#include "sptree.h" +#include /** * Scope. diff --git a/include/ek/sptree.h b/include/ek/sptree.h deleted file mode 100644 index 8ba6d6c..0000000 --- a/include/ek/sptree.h +++ /dev/null @@ -1,426 +0,0 @@ -#include -#include -#include -#include -#include - -#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) -{ - if (SPTREE(len)(s) == 0) - return NULL; - - 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); - struct SPNODE *del = CONTAINER_OF(found, struct SPNODE, data); - free(del); -} - -static inline void SPTREE(destroy)(struct SPROOT *s) -{ - while (s->root) { - SPTREE_TYPE *top = &s->root->data; - SPTREE(remove_found)(s, top); - struct SPNODE *del = CONTAINER_OF(top, struct SPNODE, data); - free(del); - } -} - -#undef SPTREE -#undef SPNODE -#undef SPROOT -#undef SPTREE_NAME -#undef SPTREE_TYPE -#undef SPTREE_CMP diff --git a/include/ek/vec.h b/include/ek/vec.h deleted file mode 100644 index 08a608a..0000000 --- a/include/ek/vec.h +++ /dev/null @@ -1,46 +0,0 @@ -/* SPDX-License-Identifier: copyleft-next-0.3.1 */ - -#ifndef VEC_H -#define VEC_H - -#include - -struct vec { - size_t n; - size_t s; - size_t ns; - void *buf; -}; - -struct vec vec_create(size_t s); -void vec_destroy(struct vec *v); -void vec_reset(struct vec *v); - -size_t vec_len(struct vec *v); -void *vec_at(struct vec *v, size_t i); -void *vec_back(struct vec *v); -void *vec_pop(struct vec *v); -void vec_append(struct vec *v, void *n); - -typedef int (*vec_comp_t)(const void *, const void *); -void vec_sort(struct vec *v, vec_comp_t comp); - -#define foreach_vec(iter, v) \ - for (size_t iter = 0; iter < vec_len(&v); ++iter) - -#define vect_at(type, v, i) \ - *(type *)vec_at(&v, i) - -#define vect_append(type, v, e) \ - vec_append(&v, (type *)(e)) - -#define vect_back(type, v) \ - *(type *)vec_back(&v) - -#define vect_pop(type, v) \ - *(type *)vec_pop(&v) - -#define vec_uninit(v) \ - (v.buf == NULL) - -#endif /* VEC_H */ -- cgit v1.3