From 195b0c7d812811287996c3f39cbf5e9ec63da482 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Tue, 18 Mar 2025 19:23:38 +0200 Subject: use generic conts --- .gitmodules | 3 + README.md | 7 + deps/conts | 1 + include/fwd/conts.h | 14 -- include/fwd/sptree.h | 419 --------------------------------------------------- include/fwd/vec.h | 47 ------ scripts/makefile | 2 +- src/ast.c | 44 +++--- src/lower.c | 1 - src/move.c | 6 +- src/vec.c | 68 --------- 11 files changed, 41 insertions(+), 571 deletions(-) create mode 100644 .gitmodules create mode 160000 deps/conts delete mode 100644 include/fwd/conts.h delete mode 100644 include/fwd/sptree.h delete mode 100644 include/fwd/vec.h delete mode 100644 src/vec.c diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..bf47852 --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "deps/conts"] + path = deps/conts + url = https://metanimi.dy.fi/git/conts diff --git a/README.md b/README.md index c3ecf85..00636b5 100644 --- a/README.md +++ b/README.md @@ -4,6 +4,13 @@ return values, instead all computation happens "forward" by heavily utilizing closures. +## Building + +``` +git submodule update --init --recursive +make +``` + ## Why? Informally: Objects have a lot of context to keep track of, are all references diff --git a/deps/conts b/deps/conts new file mode 160000 index 0000000..4f647dc --- /dev/null +++ b/deps/conts @@ -0,0 +1 @@ +Subproject commit 4f647dc8520a9186b367400c5a337b681aec5565 diff --git a/include/fwd/conts.h b/include/fwd/conts.h deleted file mode 100644 index c1e4d24..0000000 --- a/include/fwd/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/fwd/sptree.h b/include/fwd/sptree.h deleted file mode 100644 index e305c0f..0000000 --- a/include/fwd/sptree.h +++ /dev/null @@ -1,419 +0,0 @@ -#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) -{ - 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 diff --git a/include/fwd/vec.h b/include/fwd/vec.h deleted file mode 100644 index 1b78c59..0000000 --- a/include/fwd/vec.h +++ /dev/null @@ -1,47 +0,0 @@ -/* SPDX-License-Identifier: copyleft-next-0.3.1 */ -/* Copyright 2024 Kim Kuparinen < kimi.h.kuparinen@gmail.com > */ - -#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 */ diff --git a/scripts/makefile b/scripts/makefile index 9b5ed1f..db66d6d 100644 --- a/scripts/makefile +++ b/scripts/makefile @@ -48,7 +48,7 @@ WARNFLAGS := -Wall -Wextra COMPILE_FLAGS := $(CFLAGS) $(WARNFLAGS) $(OPTFLAGS) $(OBFLAGS) $(ASSERTFLAGS) \ $(DEBUGFLAGS) -INCLUDE_FLAGS := -I include +INCLUDE_FLAGS := -I include -I deps/conts/include COMPILE = $(COMPILER) \ $(COMPILE_FLAGS) $(DEPFLAGS) $(INCLUDE_FLAGS) diff --git a/src/ast.c b/src/ast.c index f491b55..7c0225d 100644 --- a/src/ast.c +++ b/src/ast.c @@ -15,11 +15,18 @@ #include #include -#include #include -static struct vec nodes = {0}; -static struct vec types = {0}; +#define VEC_NAME ast_vec +#define VEC_TYPE struct ast * +#include + +#define VEC_NAME type_vec +#define VEC_TYPE struct type * +#include + +static struct ast_vec nodes; +static struct type_vec types; static void destroy_ast_node(struct ast *n) { @@ -45,22 +52,20 @@ static void destroy_type(struct type *n) static void destroy_ast_nodes() { - foreach_vec(ni, nodes) { - struct ast *n = vect_at(struct ast *, nodes, ni); - destroy_ast_node(n); + foreach(ast_vec, n, &nodes) { + destroy_ast_node(*n); } - vec_destroy(&nodes); + ast_vec_destroy(&nodes); } static void destroy_types() { - foreach_vec(ti, types) { - struct type *t = vect_at(struct type *, types, ti); - destroy_type(t); + foreach(type_vec, t, &types) { + destroy_type(*t); } - vec_destroy(&types); + type_vec_destroy(&types); } void destroy_allocs() @@ -71,9 +76,8 @@ void destroy_allocs() static struct ast *create_empty_ast() { - if (vec_uninit(nodes)) { - nodes = vec_create(sizeof(struct ast *)); - } + if (ast_vec_uninit(&nodes)) + nodes = ast_vec_create(1); struct ast *n = calloc(1, sizeof(struct ast)); if (!n) @@ -81,18 +85,17 @@ static struct ast *create_empty_ast() /* just to be safe */ n->k = AST_EMPTY; - vect_append(struct ast *, nodes, &n); + ast_vec_append(&nodes, n); return n; } static struct type *create_empty_type() { - if (vec_uninit(types)) { - types = vec_create(sizeof(struct type *)); - } + if (type_vec_uninit(&types)) + types = type_vec_create(1); struct type *n = calloc(1, sizeof(struct type)); - vect_append(struct ast *, types, &n); + type_vec_append(&types, n); return n; } @@ -130,6 +133,9 @@ struct type *tgen_type(enum type_kind kind, struct src_loc loc) { struct type *n = create_empty_type(); + if (!n) + return NULL; + n->k = kind; n->t0 = t0; n->id = id; diff --git a/src/lower.c b/src/lower.c index 8d3e4ea..8849bd1 100644 --- a/src/lower.c +++ b/src/lower.c @@ -9,7 +9,6 @@ #include #include -#include /** @todo semantics in this file are a bit unclear, should probably do some kind * of "each function starts and ends on an indented empty line" or something */ diff --git a/src/move.c b/src/move.c index e11c2be..dc50cac 100644 --- a/src/move.c +++ b/src/move.c @@ -8,7 +8,7 @@ struct ast_pair { #define SPTREE_TYPE struct ast_pair #define SPTREE_CMP(a, b) ((a).def - (b).def) #define SPTREE_NAME moved -#include +#include struct state { struct moved moved; @@ -63,7 +63,9 @@ static struct rm_move remove_move(struct state *state, struct ast *def) struct ast_pair *found = moved_find(&state->moved, search); if (found) { moved_remove_found(&state->moved, found); - return (struct rm_move){.data = *found, .owner = state}; + struct rm_move r = {.data = *found, .owner = state}; + moved_free_found(&state->moved, found); + return r; } return remove_move(state->parent, def); diff --git a/src/vec.c b/src/vec.c deleted file mode 100644 index be413a0..0000000 --- a/src/vec.c +++ /dev/null @@ -1,68 +0,0 @@ -/* SPDX-License-Identifier: copyleft-next-0.3.1 */ -/* Copyright 2024 Kim Kuparinen < kimi.h.kuparinen@gmail.com > */ - -#include -#include -#include - -#include - -struct vec vec_create(size_t ns) -{ - return (struct vec) { - .n = 0, - .s = 1, - .ns = ns, - .buf = malloc(ns), - }; -} - -size_t vec_len(struct vec *v) -{ - return v->n; -} - -void *vec_at(struct vec *v, size_t i) -{ - assert(i < v->n && "out of vector bounds"); - return v->buf + i * v->ns; -} - -void *vec_back(struct vec *v) -{ - assert(v->n); - return v->buf + (v->n - 1) * v->ns; -} - -void *vec_pop(struct vec *v) -{ - assert(v->n && "attempting to pop empty vector"); - v->n--; - return v->buf + v->n * v->ns; -} - -void vec_append(struct vec *v, void *n) -{ - v->n++; - if (v->n >= v->s) { - v->s *= 2; - v->buf = realloc(v->buf, v->s * v->ns); - } - - void *p = vec_at(v, v->n - 1); - memcpy(p, n, v->ns); -} - -void vec_reset(struct vec *v) -{ - v->n = 0; -} - -void vec_destroy(struct vec *v) { - free(v->buf); -} - -void vec_sort(struct vec *v, vec_comp_t comp) -{ - qsort(v->buf, v->n, v->ns, comp); -} -- cgit v1.2.3