summaryrefslogtreecommitdiff
path: root/src/utils
diff options
context:
space:
mode:
Diffstat (limited to 'src/utils')
-rw-r--r--src/utils/btree.c800
-rw-r--r--src/utils/fov.c94
-rw-r--r--src/utils/hashmap.c3
-rw-r--r--src/utils/misc.c86
-rw-r--r--src/utils/stack.c82
-rw-r--r--src/utils/vector.c32
6 files changed, 1097 insertions, 0 deletions
diff --git a/src/utils/btree.c b/src/utils/btree.c
new file mode 100644
index 0000000..c125564
--- /dev/null
+++ b/src/utils/btree.c
@@ -0,0 +1,800 @@
+#include <engine/btree.h>
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <sys/types.h>
+
+/* Definitions */
+typedef unsigned char byte;
+
+struct node {
+ ssize_t n; /* number of items/keys/elements */
+ ssize_t c; /* number of children */
+ byte* items;
+ struct node** children;
+};
+
+struct btree {
+ /* Memory stuffs */
+ void* (*alloc)(size_t);
+ void (*dealloc)(void*);
+
+ /* Size stuffs */
+ size_t elem_size;
+ ssize_t degree;
+
+ struct node* root;
+
+ /* comparison */
+ int (*cmp)(const void* a, const void* b);
+};
+
+struct btree_iter_t {
+ size_t head;
+ struct stack {
+ int pos;
+ struct node* node;
+ } stack[512];
+ /* This heavily relies on the assumption that a tree never grows deeper than
+ * 512 nodes */
+};
+
+/**********************/
+/* Node functionality */
+/**********************/
+#define node_leaf(node) (node->children == NULL)
+
+#define node_maxdegree(t) (2 * t - 1)
+
+#define node_mindegree(t) (t - 1)
+
+#define node_full(degree, t) (t->n >= 2 * degree - 1)
+
+/* Node memory */
+
+/* `node_new` allocates a new leaf node, children should be added and allocated
+ * when the node is no longer a leaf node */
+struct node* node_new(const ssize_t degree, const size_t elem_size) {
+ const size_t max_items = 2 * degree;
+ struct node* retval = calloc(1, sizeof(struct node));
+
+ retval->n = 0;
+ retval->c = 0;
+ retval->items = calloc(max_items, elem_size);
+ retval->children = NULL;
+
+ return retval;
+}
+
+/* `node_transition` turns a leaf node into a non-leaf. Children are not
+ * allocated.
+ * returnvalue: `false` if we we're unable to allocate space for the new
+ * children. */
+bool node_transition(struct node* node, const ssize_t degree) {
+ const int max_children = 2 * degree + 1;
+ int c;
+
+ if (!node_leaf(node)) {
+ perror("node_transition was called on an already non-leaf node?");
+ return false;
+ }
+
+ /* Allocate pointers for children */
+ node->children = calloc(max_children, sizeof(struct node*));
+
+ if (node->children == NULL) {
+ perror("could not allocate space for children pointers");
+ return false;
+ }
+
+ /* Allocate children */
+ for (c = 0; c < max_children; c++) {
+ node->children[c] = NULL;
+ }
+
+ return true;
+}
+
+void node_free(struct node** node, size_t elem_size, void (*dealloc)(void*)) {
+ if (*node == NULL) return;
+
+ if (!node_leaf((*node))) {
+ ssize_t i;
+ for (i = 0; i < (*node)->c; i++) {
+ node_free(&((*node)->children[i]), elem_size, dealloc);
+ }
+ dealloc((*node)->children);
+ }
+
+ dealloc((*node)->items);
+ (*node)->items = NULL;
+
+ dealloc(*node);
+ *node = NULL;
+}
+
+/* `node_tree_split_child` splits a _full_ node (c = 2t-1 items) into two nodes
+ * with t-1 items each.
+ * The median key/item/element moves up to the original nodes parent, to signify
+ * the split. If the parent is full too, we need to split it before inserting
+ * the median key.
+ * This can potentially split full nodes all the way up throughout the tree. */
+/* Instead of waiting to find out wether we should split the nodes, we split the
+ * full nodes we encounter on the way down, including the leafs themselves.
+ * By doing this, we are assured that whenever we split a node, its parent has
+ * room for the median key. */
+void node_tree_split_child(const ssize_t t, const size_t elem_size,
+ struct node* nonfull, ssize_t i) {
+ struct node* z = node_new(t, elem_size);
+ struct node* y = nonfull->children[i];
+ ssize_t j;
+
+ /* `z` should be a branching node if `y` is */
+ if (!node_leaf(y)) {
+ node_transition(z, t);
+ }
+
+ z->n = t - 1;
+
+ /* Move last `t-1` items to new node `z` */
+ /* TODO This can be done with one memcpy */
+ for (j = 0; j < t - 1; j++) {
+ const size_t offset_dst = elem_size * j;
+ const size_t offset_src = elem_size * (t + j);
+ memcpy((z->items) + offset_dst, (y->items) + offset_src, elem_size);
+ }
+ /* Set unused item-memory to zero? */
+
+ /* Move children t..2t, if applicable*/
+ if (!node_leaf(y)) {
+ for (j = 0; j < t + 1; j++) {
+ z->children[j] = y->children[j + t];
+ }
+ y->c = t;
+ z->c = t;
+ }
+
+ y->n = t - 1;
+
+ /* Move children +1 */
+ for (j = nonfull->n; j > i; j--) {
+ nonfull->children[j + 1] = nonfull->children[j];
+ }
+
+ /* new child */
+ nonfull->children[i + 1] = z;
+ nonfull->c++;
+
+ /* moving keys i..n + 1*/
+ /* TODO This can be done with one memcpy */
+ for (j = nonfull->n; j >= i; j--) {
+ const size_t offset = j * elem_size;
+ memcpy((nonfull->items) + offset + elem_size, (nonfull->items) + offset,
+ elem_size);
+ }
+
+ /* Lastly, copy the median element to nonfull-parent*/
+ memcpy((nonfull->items) + i * elem_size, (y->items) + (t - 1) * elem_size,
+ elem_size);
+
+ nonfull->n++;
+}
+
+/* `node_child_merge`: Merges two children around the key at index `i` (k)
+ * by appending k to the left child (y) followed by
+ * appending the right child (z) to y
+ *
+ * `x`: The parent node of y and z
+ * `i`: Index of the item that acts as the new median of the merged node
+ *
+ * WARNING: THIS FUNCTION ASSUMES THAT `i` IS A VALID INDEX
+ */
+void node_child_merge(struct node* x, ssize_t i, const size_t elem_size,
+ void (*dealloc)(void*)) {
+ struct node* y = x->children[i];
+ struct node* z = x->children[i + 1];
+ int j = 0;
+
+ /* append k to y */
+ memcpy(y->items + (elem_size * y->n++), x->items + (elem_size * i),
+ elem_size);
+
+ /* append keys in z to y */
+ memcpy(y->items + (elem_size * y->n), z->items, elem_size * z->n);
+ y->n += z->n;
+
+ /* Move children from z to y */
+ for (j = 0; j < z->c; j++) {
+ y->children[y->c + j] = z->children[j];
+ }
+ y->c += z->c;
+
+ /* Remove z from x */
+ for (j = i + 1; j < x->c; j++) {
+ x->children[j] = x->children[j + 1];
+ }
+ x->c--;
+
+ /* remove k from x */
+ /* TODO check if we need to use (x->n - 1 - i) instead */
+ memmove(x->items + (elem_size * i), x->items + (elem_size * (i + 1)),
+ elem_size * (x->n - i));
+ x->n--;
+
+ dealloc(z); /* DO NOT USE THE RECURSIVE ONE AS CHILDREN WILL BE LOST!!! */
+}
+
+/* ASSUME i < x->c */
+void node_shift_left(struct node* x, ssize_t i, const size_t elem_size) {
+ struct node* y = x->children[i];
+ struct node* z = x->children[i + 1];
+ byte* x_k = x->items + (elem_size * i);
+
+ /* Append x.k[i] to y */
+ memcpy(y->items + (elem_size * y->n++), x_k, elem_size);
+
+ /* Move first element of z to x.k[i] */
+ memcpy(x_k, z->items, elem_size);
+
+ /* Shift z's items left */
+ memmove(z->items, z->items + elem_size, elem_size * (z->n - 1));
+
+ if (!node_leaf(z)) {
+ ssize_t j;
+ /* append first child of z to y */
+ y->children[y->c++] = z->children[0];
+
+ /* Shift z's children left */
+ for (j = 0; j < z->c; j++) {
+ z->children[j] = z->children[j + 1];
+ }
+ z->c--;
+ }
+
+ z->n--;
+}
+
+void node_shift_right(struct node* x, ssize_t i, const size_t elem_size) {
+ struct node* y = x->children[i];
+ struct node* z = x->children[i + 1];
+ byte* x_k = x->items + (elem_size * i);
+
+ /* Shift z's items right */
+ memmove(z->items + elem_size, z->items, elem_size * z->n);
+
+ /* Prepend x.k[i] to z */
+ memcpy(z->items, x_k, elem_size);
+
+ /* Move last element of y to x.k[i] */
+ memcpy(x_k, y->items + (elem_size * --(y->n)), elem_size);
+
+ if (!node_leaf(z)) {
+ size_t j;
+ /* Shift z's children right */
+ for (j = z->c; j > 0; j--) {
+ z->children[j] = z->children[j - 1];
+ }
+ z->c++;
+
+ /* prepend last child of y to z */
+ z->children[0] = y->children[--(y->c)];
+ }
+
+ z->n++;
+}
+
+/* return: Returns the new root, if a split happens */
+void node_insert_nonfull(struct node* root, void* elem, const ssize_t degree,
+ const size_t elem_size,
+ int (*cmp)(const void* a, const void* b)) {
+
+ /* TODO check correctness */
+ ssize_t i = root->n - 1;
+
+ if (node_leaf(root)) {
+ size_t offset = elem_size * i;
+ while (i >= 0 && cmp(elem, root->items + offset) < 0) {
+ /* TODO This can be done with one memcpy */
+ memcpy(root->items + offset + elem_size, root->items + offset, elem_size);
+
+ i--;
+ offset = elem_size * i;
+ }
+ offset = elem_size * (++i);
+ memcpy(root->items + offset, elem, elem_size);
+ root->n++;
+
+ } else {
+ size_t offset = elem_size * i;
+ struct node* nextchild = NULL;
+ while (i >= 0 && cmp(elem, root->items + offset) < 0) {
+ i--;
+ offset = elem_size * i;
+ }
+ i++;
+ nextchild = root->children[i];
+ if (node_full(degree, nextchild)) {
+ /* TODO Check if the root has changed */
+ node_tree_split_child(degree, elem_size, root, i);
+ if (cmp(elem, root->items + elem_size * i) > 0) {
+ nextchild = root->children[++i];
+ }
+ }
+ node_insert_nonfull(nextchild, elem, degree, elem_size, cmp);
+ }
+}
+
+/* Returns the new root, if a split occurs */
+struct node* node_insert(struct node* root, void* elem, const ssize_t degree,
+ const size_t elem_size,
+ int (*cmp)(const void* a, const void* b)) {
+
+ struct node* s = root;
+
+ if (node_full(degree, root)) {
+ s = node_new(degree, elem_size);
+ if (s == NULL) {
+ fputs("BTree error: Failed to allocate new node for insertion!\n",
+ stderr);
+ return NULL;
+ }
+ node_transition(s, degree);
+ s->children[s->c++] = root;
+ /* TODO Check if the root has changed */
+ node_tree_split_child(degree, elem_size, s, 0);
+ node_insert_nonfull(s, elem, degree, elem_size, cmp);
+ } else {
+ node_insert_nonfull(s, elem, degree, elem_size, cmp);
+ }
+ return s;
+}
+
+void* node_search(struct node* x, void* key,
+ int (*cmp)(const void* a, const void* b),
+ const size_t elem_size) {
+ /* We set to one, since we pre-emptively do a comparison with the assumption
+ * that there's already one in the items */
+ ssize_t i = 0;
+ int last_cmp_res = 0;
+
+ while (i < x->n &&
+ (last_cmp_res = cmp(key, (const void*)(x->items + (i * elem_size)))) >
+ 0) {
+ i++;
+ }
+
+ if ((ssize_t)i < x->n && last_cmp_res == 0) {
+ return (void*)(x->items + (i * elem_size));
+ } else if (node_leaf(x)) {
+ return NULL;
+ }
+
+ /* Assumption: ¬node_leaf(x) → x.children is allocated */
+ return node_search(x->children[i], key, cmp, elem_size);
+}
+
+int node_delete(struct node* x, void* key,
+ int (*cmp)(const void* a, const void* b), const ssize_t degree,
+ const size_t elem_size, void* (*alloc)(size_t),
+ void (*dealloc)(void*)) {
+ /* Determine wether the key is in the node */
+ int i = 0; /* Index of `k`, if found */
+ int last_cmp_res = 0;
+
+ while (i < x->n &&
+ (last_cmp_res = cmp(key, (const void*)(x->items + (i * elem_size)))) >
+ 0) {
+ i++;
+ }
+
+ if (last_cmp_res == 0) {
+
+ if (node_leaf(x)) {
+ /* 1. k ϵ x && node_leaf(x) */
+ /* Delete k from x */
+ int j = i;
+ while (j + 1 < x->n) {
+ const size_t offset_dst = elem_size * j;
+ const size_t offset_src = elem_size * (j + 1);
+ memcpy((x->items) + offset_dst, (x->items) + offset_src, elem_size);
+ j++;
+ }
+ x->n--;
+ return 1;
+ } else {
+ /* 2. k ϵ x && !node_leaf(x) */
+ /* let i be the index of k in x */
+ /* 2a: if size(child[i]) >= t; find the largest k' in child[i] */
+ /* replace k with k' */
+ if (x->children[i]->n >= degree) {
+ struct node* y = x->children[i];
+ byte* kk = alloc(elem_size);
+
+ /* Find the predecessor, k' of k in y */
+ {
+ struct node* tmp = y;
+ while (!node_leaf(tmp)) {
+ tmp = tmp->children[tmp->n - 1];
+ }
+
+ /* copy kk */
+ memcpy(kk, tmp->items + elem_size * (tmp->n - 1), elem_size);
+ }
+
+ /* Recursively delete kk from y */
+ return node_delete(y, kk, cmp, degree, elem_size, alloc, dealloc);
+
+ /* replace k with kk */
+ memcpy(x->items + (elem_size * i), kk, elem_size);
+
+ dealloc(kk);
+
+ return 1;
+
+ } else if (x->children[i + 1]->n >= degree) {
+ struct node* z = x->children[i + 1];
+ byte* kk = alloc(elem_size);
+
+ /* Find the successor, k' of k in z */
+ {
+ struct node* tmp = z->children[0];
+ while (!node_leaf(tmp)) {
+ tmp = tmp->children[0];
+ }
+
+ /* copy kk */
+ memcpy(kk, tmp->items + elem_size * (tmp->n - 1), elem_size);
+ }
+
+ /* Recursively delete kk from y */
+ return node_delete(z, kk, cmp, degree, elem_size, alloc, dealloc);
+
+ /* replace k with kk */
+ memcpy(x->items + (elem_size * i), kk, elem_size);
+
+ dealloc(kk);
+
+ return 1;
+ } else {
+ /* Merge k and z into y */
+ node_child_merge(x, i, elem_size, dealloc);
+
+ /* recurse */
+ return node_delete(x->children[i], key, cmp, degree, elem_size, alloc,
+ dealloc);
+ }
+ }
+ } else if (node_leaf(x)) {
+ return 0;
+ } else {
+ /* 3. !(k ϵ x) */
+
+ /* if x is a leaf, then it is not in the tree */
+
+ struct node* y;
+ int ii; /* index of x.c[i] */
+
+ /* Determine x.c[i] that must contain k */
+ /* if last cmp < 0, then the child must be in the left child of x.items[i]*/
+ if (last_cmp_res < 0) ii = i;
+ /* Otherwise, it must be the very last child */
+ else if (i < x->n)
+ ii = i + 1;
+ else
+ ii = i;
+
+ y = x->children[ii];
+
+ if (y->n < degree) {
+ /* we are left biased */
+ if (ii > 0 && x->children[ii - 1]->n >= degree) {
+ node_shift_right(x, ii - 1, elem_size);
+
+ } else if (ii < x->c - 1 && x->children[ii + 1]->n >= degree) {
+ node_shift_left(x, ii, elem_size);
+
+ } else {
+ /* We need to determine wether we merge left or right, if possible */
+ if (ii > 0) {
+ node_child_merge(x, ii - 1, elem_size, dealloc);
+ y = x->children[ii - 1];
+ } else if (ii < x->c - 1) {
+ node_child_merge(x, ii, elem_size, dealloc);
+ } else {
+ perror("Cannot merge!");
+ }
+ }
+ }
+
+ return node_delete(y, key, cmp, degree, elem_size, alloc, dealloc);
+ }
+ return 0;
+}
+
+/***********************/
+/* Btree functionality */
+/***********************/
+struct btree* btree_new(size_t elem_size, size_t t,
+ int (*cmp)(const void* a, const void* b)) {
+ return btree_new_with_allocator(elem_size, t, cmp, malloc, free);
+}
+
+struct btree* btree_new_with_allocator(size_t elem_size, size_t t,
+ int (*cmp)(const void* a, const void* b),
+ void* (*alloc)(size_t),
+ void (*dealloc)(void*)) {
+ struct btree* new_tree = alloc(sizeof(struct btree));
+
+ new_tree->alloc = alloc;
+ new_tree->dealloc = dealloc;
+
+ new_tree->elem_size = elem_size;
+ new_tree->degree = t;
+
+ new_tree->root = NULL;
+
+ new_tree->cmp = cmp;
+
+ return new_tree;
+}
+
+void btree_free(struct btree** btree) {
+ node_free(&((*btree)->root), (*btree)->elem_size, (*btree)->dealloc);
+ (*btree)->dealloc(*btree);
+ *btree = NULL;
+}
+
+void btree_insert(struct btree* btree, void* elem) {
+ if (btree == NULL) {
+ fputs("BTree error: Inserting into a NULL ptr!\n", stderr);
+ return;
+ }
+ if (elem == NULL) {
+ fputs("BTree error: Inserting NULL into a tree!\n", stderr);
+ return;
+ }
+ if (btree->root == NULL) {
+ btree->root = node_new(btree->degree, btree->elem_size);
+ if (btree->root == NULL) {
+ fputs("BTree error: Failed to create new root node!\n", stderr);
+ return;
+ }
+ node_insert(btree->root, elem, btree->degree, btree->elem_size, btree->cmp);
+ } else {
+ btree->root = node_insert(btree->root, elem, btree->degree,
+ btree->elem_size, btree->cmp);
+ }
+}
+
+void* btree_search(struct btree* btree, void* elem) {
+ return node_search(btree->root, elem, btree->cmp, btree->elem_size);
+}
+
+int btree_delete(struct btree* btree, void* elem) {
+ struct node* newroot = btree->root;
+ int res = node_delete(btree->root, elem, btree->cmp, btree->degree,
+ btree->elem_size, btree->alloc, btree->dealloc);
+ if (newroot->n == 0) {
+ if (node_leaf(newroot)) return res;
+ /* shrink the tree */
+ struct node* newroot_p = newroot->children[0];
+ btree->dealloc(newroot);
+ btree->root = newroot_p;
+ }
+ return res;
+}
+
+void node_print(struct node* root, const size_t elem_size, const int indent,
+ void (*print_elem)(const void*)) {
+ ssize_t i;
+ int t;
+
+ for (t = 0; t < indent - 1; t++) {
+ fputs(" ┃ ", stdout);
+ }
+ if (indent > 0) {
+ fputs(" ┣┯", stdout);
+ }
+ printf("printing node \x1b[33m%0lx\x1b[0m,"
+ " c:%ld n:%ld\t\t"
+ "\x1b[30m%p\x1b[0m\n",
+ (unsigned long)((size_t)root % 0x10000), root->c, root->n,
+ (void*)root);
+
+ if (node_leaf(root)) {
+ for (i = 0; i < root->n - 1; i++) {
+ const size_t ofst = i * elem_size;
+ for (t = 0; t < indent; t++) {
+ fputs(" ┃├", stdout);
+ }
+ print_elem(root->items + ofst);
+ }
+ for (t = 0; t < indent; t++) {
+ fputs(" ┃└", stdout);
+ }
+ print_elem(root->items + i * elem_size);
+ } else {
+ size_t ofst = 0;
+ for (i = 0; i < root->c - 1; i++) {
+ node_print(root->children[i], elem_size, indent + 1, print_elem);
+ for (t = 0; t < indent; t++) {
+ fputs(" ┃ ", stdout);
+ }
+ print_elem(root->items + ofst);
+ ofst += elem_size;
+ }
+ node_print(root->children[i], elem_size, indent + 1, print_elem);
+ }
+}
+
+void btree_print(struct btree* btree, void (*print_elem)(const void*)) {
+ printf("BTRee: degree:%ld\n", btree->degree);
+ if (btree->root == NULL) return;
+ node_print(btree->root, btree->elem_size, 0, print_elem);
+}
+
+void* btree_first(struct btree* btree) {
+ struct node* root;
+ if (btree == NULL) return NULL;
+ root = btree->root;
+
+ if (root == NULL) return NULL;
+
+ while (!node_leaf(root)) root = root->children[0];
+
+ if (root->n == 0) return NULL;
+ return root->items; /* Return first element */
+}
+
+void* btree_last(struct btree* btree) {
+ struct node* root;
+
+ if (btree == NULL) return NULL;
+ root = btree->root;
+
+ if (root == NULL) return NULL;
+
+ while (!node_leaf(root)) root = root->children[root->c];
+
+ if (root->n == 0) return NULL;
+ return root->items +
+ btree->elem_size * (root->n - 1); /* Return first element */
+}
+
+size_t btree_height(struct btree* btree) {
+ struct node* root;
+ size_t height = 0;
+
+ if (btree == NULL) return 0;
+ root = btree->root;
+
+ if (root == NULL) return 0;
+
+ while (!node_leaf(root)) {
+ root = root->children[0];
+ height++;
+ }
+
+ return height;
+}
+
+size_t u32_pow(size_t base, size_t exponent) {
+ size_t res = 1;
+ while (exponent > 0) {
+ res *= base;
+ exponent--;
+ }
+ return res;
+}
+
+size_t btree_size(struct btree* btree) {
+ return u32_pow(2 * btree->degree, btree_height(btree)) - 1;
+}
+
+struct btree_iter_t* btree_iter_t_new(struct btree* tree) {
+ struct btree_iter_t* iter = NULL;
+
+ if (tree == NULL) return NULL;
+
+ iter = (struct btree_iter_t*)tree->alloc(sizeof(struct btree_iter_t));
+
+ if (tree != NULL) {
+ iter->head = 0;
+ memset(iter->stack, 0, 512 * sizeof(struct node*));
+
+ iter->stack[iter->head].pos = 0;
+ iter->stack[iter->head].node = tree->root;
+ } else {
+ perror("Cannot instantiate iterator from null-pointer tree");
+ }
+ return iter;
+}
+
+void btree_iter_t_reset(struct btree* tree, struct btree_iter_t** it) {
+ (*it)->head = 0;
+
+ (*it)->stack[0].pos = 0;
+ (*it)->stack[0].node = tree->root;
+}
+
+void* btree_iter(struct btree* tree, struct btree_iter_t* iter) {
+ register int pos = 0;
+ register ssize_t head = 0;
+ register ssize_t n = 0;
+
+ if (iter->stack[head].node == NULL) return NULL;
+
+ head = iter->head;
+ pos = iter->stack[head].pos;
+ n = iter->stack[head].node->n;
+
+#define BTREE_ITER_POP(it) \
+ { \
+ iter->stack[head].pos = 0; \
+ iter->stack[head].node = NULL; \
+ iter->head--; \
+ head--; \
+ iter->stack[head].pos++; \
+ \
+ pos = iter->stack[head].pos; \
+ n = iter->stack[head].node->n; \
+ }
+
+ /* Check if we have reached the end of a node.
+ * Take note of the difference of inequality in the if statement and
+ * following while */
+
+ /* Leafs are a special case, as, if the only node is the root node, we might
+ * want to exit */
+ if (node_leaf(iter->stack[iter->head].node) && pos >= 2 * n) {
+ if (head == 0) return NULL;
+
+ /* Pop, if so */
+ else
+ BTREE_ITER_POP(iter);
+ }
+
+ /* Otherwise, pop while we have reached the end of a node */
+ while (pos > 2 * n) {
+ if (head == 0) return NULL;
+
+ /* Pop, if so */
+ else
+ BTREE_ITER_POP(iter);
+ }
+
+#undef BTREE_ITER_POP
+
+ /* On evens, we decent into children */
+ if (!node_leaf(iter->stack[head].node)) {
+ if (pos % 2 == 0) {
+ /* push child node onto iter->stack */
+ iter->stack[head + 1].pos = 0;
+ iter->stack[head + 1].node = iter->stack[head].node->children[pos / 2];
+ iter->head++;
+ head++;
+
+ /* Decent all the way to the left, if pos == 0 */
+ while (!node_leaf(iter->stack[iter->head].node)) {
+ iter->stack[head + 1].pos = 0;
+ iter->stack[head + 1].node = iter->stack[head].node->children[0];
+ iter->head++;
+ head++;
+ }
+ }
+ }
+
+ /* Finally, update index and return a value */
+ if (node_leaf(iter->stack[head].node)) {
+ iter->stack[head].pos += 2;
+ pos = iter->stack[head].pos;
+ } else {
+ iter->stack[head].pos++;
+ pos = iter->stack[head].pos;
+ }
+
+ return iter->stack[head].node->items + tree->elem_size * ((pos - 1) / 2);
+}
diff --git a/src/utils/fov.c b/src/utils/fov.c
new file mode 100644
index 0000000..3d5ae16
--- /dev/null
+++ b/src/utils/fov.c
@@ -0,0 +1,94 @@
+#include <engine/fov.h>
+#include <engine/utils.h>
+#include <math.h>
+#include <stdint.h>
+
+void fov_shadowcast_rec(const void* map, const v2_i32 mapsize,
+ bool (*visblocking)(const void*), i32* lightmap,
+ const i32 range, v2_i32 src, const i32 row, f32 start,
+ const f32 end, const i8 xx, const i8 xy, const i8 yx,
+ const i8 yy) {
+
+ if (start < end) return;
+
+ const i32 range_2 = range * range;
+ f32 new_start = start;
+
+ for (i32 i = row; i <= range; i++) {
+ i32 dx = (-1 * i) - 1;
+ i32 dy = -1 * i;
+
+ bool blocked = false;
+
+ while (dx <= 0) {
+ dx += 1;
+
+ const i32 mapx = src.x + dx * xx + dy * xy;
+ const i32 mapy = src.y + dx * yx + dy * yy;
+
+ const f32 slope_l = (((f32)dx) - 0.5f) / (((f32)dy) + 0.5f);
+ const f32 slope_r = (((f32)dx) + 0.5f) / (((f32)dy) - 0.5f);
+
+ if (start < slope_r) continue;
+ if (end > slope_l) break;
+
+ if (dx * dx + dy * dy < range_2) {
+ /* set as visible */
+ if (mapx >= 0 && mapx < (long)mapsize.x && mapy >= 0 &&
+ mapy < (long)mapsize.y) {
+ // TODO: Calculate proper dist from source
+ f32 x_2 = (src.x - mapx) * (src.x - mapx);
+ f32 y_2 = (src.y - mapy) * (src.y - mapy);
+ lightmap[mapy * mapsize.x + mapx] =
+ MAX(lightmap[mapy * mapsize.x + mapx],
+ range - sqrt((f32)(x_2 + y_2)));
+ }
+ }
+
+ /* sizeof(i32) is the size of enums */
+ /* -- unless the compiler doesn't follow standard behaviour */
+ const bool is_blocked = visblocking(
+ (void*)((u64)map + sizeof(i32) /* ~ enum size */
+ * (mapsize.x * mapy + mapx) /* index */
+ ));
+
+ if (blocked) {
+ if (!is_blocked) {
+ new_start = slope_r;
+ } else {
+ blocked = false;
+ start = new_start;
+ }
+ } else if (!is_blocked && i < range) {
+ blocked = true;
+ fov_shadowcast_rec(map, mapsize, visblocking, lightmap, range, src,
+ i + 1, start, slope_l, xx, xy, yx, yy);
+ new_start = slope_r;
+ }
+ }
+
+ if (blocked) break;
+ }
+}
+
+/* http://www.roguebasin.com/index.php?title=FOV_using_recursive_shadowcasting
+ */
+void fov_shadowcast(const void* map, const v2_i32 mapsize,
+ bool (*visblocking)(const void*), i32* lightmap,
+ const i32 range, const v2_i32 src) {
+
+ const i8 m[4][8] = {
+ {1, 0, 0, -1, -1, 0, 0, 1},
+ {0, 1, -1, 0, 0, -1, 1, 0},
+ {0, 1, 1, 0, 0, -1, -1, 0},
+ {1, 0, 0, 1, -1, 0, 0, -1},
+ };
+
+ for (i32 oct = 0; oct < 8; oct++) {
+ fov_shadowcast_rec(map, mapsize, visblocking, lightmap, range, src, 1, 1.0,
+ 0.0, m[0][oct], m[1][oct], m[2][oct], m[3][oct]);
+ }
+
+ /* The center is the most lit square */
+ lightmap[src.y * mapsize.x + src.x] = range;
+}
diff --git a/src/utils/hashmap.c b/src/utils/hashmap.c
new file mode 100644
index 0000000..1652bb6
--- /dev/null
+++ b/src/utils/hashmap.c
@@ -0,0 +1,3 @@
+#include <engine/hashmap.h>
+
+i32 lolhash(const usize s, i32 v) { return v % s; }
diff --git a/src/utils/misc.c b/src/utils/misc.c
new file mode 100644
index 0000000..0f3d218
--- /dev/null
+++ b/src/utils/misc.c
@@ -0,0 +1,86 @@
+#include <stdint.h>
+#include <stdlib.h>
+
+#include <string.h>
+
+#include <engine/logging.h>
+#include <engine/utils.h>
+
+/* These should all be in some external facing module "tools" */
+
+f32 lerp(f32 dt, f32 a, f32 b) { return (a * (1.0f - dt)) + (b * dt); }
+
+i32 int_lerp(f32 dt, i32 a, i32 b) {
+ return ((f32)a * (1.0f - dt)) + ((f32)b * dt);
+}
+
+u32 hash(char* str) {
+ u32 sum = 0;
+ while (*str != '\0') {
+ sum ^= (*str) * 0xdeece66d + 0xb;
+ str++;
+ }
+ return sum;
+}
+
+/* Populates dstmap
+ * on success: return pointer to dstmap
+ * on failure: return NULL */
+i32* kernmap(const void* map, i32* dstmap, const v2_i32 mapsize,
+ predicate_t* predicate) {
+ const i32 w = mapsize.x;
+ const i32 h = mapsize.y;
+ i32 mask[w * h];
+
+ if (w * h < 1) return NULL;
+
+ for (i32 i = 0; i < w * h; i++) {
+ mask[i] = predicate((void*)((u64)map + sizeof(i32) * i)) ? 1 : 0;
+ }
+
+ for (i32 y = 1; y < h - 1; y++) {
+ for (i32 x = 1; x < w - 1; x++) {
+ const i32 global_idx = (y * w) + x;
+ const i32 offs = global_idx - w - 1;
+ i32 _sum = 0;
+
+ i32 shift = 0;
+
+ /* We go in the following order */
+ /* ....|0|1|2|....*/
+ /* ....|3|4|5|....*/
+ /* ....|6|7|8|....*/
+ /* Where `4` is in the center, MASK_C */
+ for (i32 yy = offs; yy <= offs + w + w; yy += w) {
+ for (i32 xx = yy; xx < yy + 3; xx++) {
+ _sum = _sum | (mask[xx] << shift++);
+ }
+ }
+
+ dstmap[global_idx] = _sum;
+ }
+ }
+ return dstmap;
+}
+
+/* Returns an index from the given weights. */
+i32 pick_from_sample(const i32* weights, i32 len) {
+ if (len <= 0) return 0;
+
+ /* Cumulative sum */
+ i32 cumweights[len];
+ i32 sum = 0;
+ for (i32 i = 0; i < len; i++) {
+ sum += weights[i];
+ cumweights[i] = sum;
+ }
+
+ if (sum == 0) return 0;
+
+ i32 pick = rand() % sum;
+
+ for (i32 i = 0; i < len; i++) {
+ if (pick < cumweights[i]) return i;
+ }
+ return -1;
+}
diff --git a/src/utils/stack.c b/src/utils/stack.c
new file mode 100644
index 0000000..ff195ba
--- /dev/null
+++ b/src/utils/stack.c
@@ -0,0 +1,82 @@
+#include <engine/logging.h>
+#include <engine/stack.h>
+#include <stdlib.h>
+
+Stack stack_new_ex(const usize element_size, const usize size) {
+ Stack s = {
+ .head = 0,
+ .elem_size = element_size,
+ .size = element_size * size,
+ .chunk_size = element_size * size,
+ .data = NULL,
+ };
+
+ s.data = (void*)calloc(element_size, size);
+ return s;
+}
+
+Stack stack_new(const usize element_size) {
+ return stack_new_ex(element_size, 512);
+}
+
+void stack_free(Stack* s) {
+ if (s->data == NULL) return;
+ free(s->data);
+ s->data = NULL;
+}
+
+void* stack_pop(Stack* s) {
+ if (s->head == 0) return NULL; /* Empty stack */
+ return (u8*)s->data + (--(s->head) * s->elem_size);
+}
+
+void stack_push(Stack* s, void* elem) {
+ if (elem == NULL) {
+ WARN("%s received a nullptr", __func__);
+ return;
+ }
+ if (s->head > 0 && s->head * s->elem_size >= s->size) {
+ WARN("Allocating more stack memory");
+ /* Reallocate more memory and update size */
+ void* ptr = realloc(s->data, s->size + s->chunk_size);
+ if (ptr == NULL) {
+ ERROR("Failed to resize memory for stack");
+ exit(EXIT_FAILURE);
+ }
+ s->data = ptr;
+ // memset((void*)((u64)s->data + (s->size - s->elem_size)), 0,
+ // s->chunk_size);
+ s->size += s->chunk_size;
+ }
+ memcpy((u8*)s->data + s->head * s->elem_size, elem, s->elem_size);
+ s->head++;
+}
+
+void* stack_peek(Stack* s) {
+ if (s->head <= 0) return NULL; /* Empty stack */
+ return (u8*)s->data + ((s->head - 1) * s->elem_size);
+}
+
+isize stack_size(const Stack* s) { return s->head; }
+
+void stack_swap(Stack* s, Stack* t) {
+ if (s->size > t->size) {
+ t->data = realloc(t->data, s->size);
+ } else if (t->size > s->size) {
+ s->data = realloc(s->data, t->size);
+ }
+ void* tmp = malloc(s->size);
+ if (tmp == NULL) {
+ ERROR("Failed to allocate memory for stack swapping!");
+ exit(EXIT_FAILURE);
+ }
+ isize shead = s->head;
+
+ memcpy(tmp, s->data, s->size);
+ memcpy(s->data, t->data, t->size);
+ memcpy(t->data, tmp, s->size);
+
+ s->head = t->head;
+ t->head = shead;
+ free(tmp);
+}
diff --git a/src/utils/vector.c b/src/utils/vector.c
new file mode 100644
index 0000000..3465df7
--- /dev/null
+++ b/src/utils/vector.c
@@ -0,0 +1,32 @@
+#include <engine/utils.h>
+#include <engine/vector.h>
+
+bool v2_i32_eq(const v2_i32 a, const v2_i32 b) {
+ return (a.x == b.x) && (a.y == b.y);
+}
+v2_i32 v2_i32_add(v2_i32 a, v2_i32 b) { return (v2_i32){a.x + b.x, a.y + b.y}; }
+v2_i32 v2_i32_add_i(v2_i32 a, i32 b) { return (v2_i32){a.x + b, a.y + b}; }
+v2_i32 v2_i32_sub(v2_i32 a, v2_i32 b) { return (v2_i32){a.x - b.x, a.y - b.y}; }
+v2_i32 v2_i32_sub_i(v2_i32 a, i32 b) { return (v2_i32){a.x - b, a.y - b}; }
+v2_i32 v2_i32_div(v2_i32 a, v2_i32 b) { return (v2_i32){a.x / b.x, a.y / b.y}; }
+v2_i32 v2_i32_div_i(v2_i32 a, i32 b) { return (v2_i32){a.x / b, a.y / b}; }
+v2_i32 v2_i32_mul(v2_i32 a, v2_i32 b) { return (v2_i32){a.x * b.x, a.y * b.y}; }
+v2_i32 v2_i32_mul_i(v2_i32 a, i32 b) { return (v2_i32){a.x * b, a.y * b}; }
+v2_i32 v2_i32_mod(v2_i32 a, v2_i32 b) { return (v2_i32){a.x % b.x, a.y % b.y}; }
+v2_i32 v2_i32_mod_i(v2_i32 a, i32 b) { return (v2_i32){a.x % b, a.y % b}; }
+v2_i32 v2_i32_max(v2_i32 a, v2_i32 b) {
+ return (v2_i32){MAX(a.x, b.x), MAX(a.y, b.y)};
+}
+v2_i32 v2_i32_min(v2_i32 a, v2_i32 b) {
+ return (v2_i32){MIN(a.x, b.x), MIN(a.y, b.y)};
+}
+v2_i32 v2_i32_lerp(f32 dt, v2_i32 a, v2_i32 b) {
+ return (v2_i32){
+ .x = lerp(dt, (f32)a.x, (f32)b.x),
+ .y = lerp(dt, (f32)a.y, (f32)b.y),
+ };
+}
+
+void v2_i32_fprintf(FILE* stream, v2_i32 a) {
+ fprintf(stream, "<%d,%d>", a.x, a.y);
+}
generated by cgit v1.3 (git 2.53.0) at 2026-05-23 21:51:04 +0000