diff options
Diffstat (limited to 'src/utils')
| -rw-r--r-- | src/utils/CMakeLists.txt | 11 | ||||
| -rw-r--r-- | src/utils/include/engine/utils.h | 43 | ||||
| -rw-r--r-- | src/utils/include/engine/utils/btree.h | 61 | ||||
| -rw-r--r-- | src/utils/include/engine/utils/fov.h | 28 | ||||
| -rw-r--r-- | src/utils/include/engine/utils/hashmap.h | 61 | ||||
| -rw-r--r-- | src/utils/include/engine/utils/list.h | 18 | ||||
| -rw-r--r-- | src/utils/include/engine/utils/stack.h | 33 | ||||
| -rw-r--r-- | src/utils/src/btree.c | 800 | ||||
| -rw-r--r-- | src/utils/src/fov.c | 95 | ||||
| -rw-r--r-- | src/utils/src/hashmap.c | 5 | ||||
| -rw-r--r-- | src/utils/src/misc.c | 86 | ||||
| -rw-r--r-- | src/utils/src/stack.c | 82 |
12 files changed, 0 insertions, 1323 deletions
diff --git a/src/utils/CMakeLists.txt b/src/utils/CMakeLists.txt deleted file mode 100644 index 6acdba1..0000000 --- a/src/utils/CMakeLists.txt +++ /dev/null @@ -1,11 +0,0 @@ -add_library(daw_utils - src/btree.c - src/fov.c - src/hashmap.c - src/misc.c - src/stack.c - ) - -target_compile_options(daw_utils PUBLIC ${BUILD_OPTS}) -target_include_directories(daw_utils PRIVATE ${DAW_INCLUDE_DIRS}) -target_link_libraries(daw_utils PRIVATE cglm) diff --git a/src/utils/include/engine/utils.h b/src/utils/include/engine/utils.h deleted file mode 100644 index 5096aa4..0000000 --- a/src/utils/include/engine/utils.h +++ /dev/null @@ -1,43 +0,0 @@ -#ifndef ENGINE_UTILS_H -#define ENGINE_UTILS_H - -#ifdef __cplusplus -extern "C" { -#endif - -#include <engine/core/types.h> -#include <cglm/ivec2.h> - -#define MIN(a, b) ((a < b) ? (a) : (b)) -#define MAX(a, b) ((a > b) ? (a) : (b)) - -#define MASK_TL (1 << 0) -#define MASK_T (1 << 1) -#define MASK_TR (1 << 2) -#define MASK_L (1 << 3) -#define MASK_C (1 << 4) -#define MASK_R (1 << 5) -#define MASK_BL (1 << 6) -#define MASK_B (1 << 7) -#define MASK_BR (1 << 8) - -/* Linear interpolate */ -f32 lerp(f32 dt, f32 a, f32 b); -i32 int_lerp(f32 dt, i32 a, i32 b); - -/* Hashes */ -u32 hash(char* str); - -/* Masks surrounding tiles of a kernel size of 3x3 */ -/* In reality we only need 9 bits for this, but I think I had a reason for using - * i32 */ -i32* kernmap(const void* map, i32* dstmap, const ivec2 mapsize, - predicate_t* predicate); - -/* Returns an index from the given weights. */ -i32 pick_from_sample(const i32* weights, i32 len); - -#ifdef __cplusplus -} -#endif -#endif diff --git a/src/utils/include/engine/utils/btree.h b/src/utils/include/engine/utils/btree.h deleted file mode 100644 index 1dd2023..0000000 --- a/src/utils/include/engine/utils/btree.h +++ /dev/null @@ -1,61 +0,0 @@ -#ifndef BTREE_H -#define BTREE_H - -#ifdef __cplusplus -extern "C" { -#endif - -#include <stddef.h> - -#define BTREE_DEGREE_DEFAULT 4 - -#define BTREE_SIZE_MIN 8 -#define BTREE_SIZE_MAX 4096 - -#define BTREE_CMP_LT (-1) -#define BTREE_CMP_EQ (0) -#define BTREE_CMP_GT (1) - -struct btree; -struct btree_iter_t; - -/* elem_size: the size of the elements, typically `sizeof(struct <your struct>)` - * t: degree of the btree, if you're in doubt, use `BTREE_SIZE_DEFAULT` - * cmp: comparison function, in order to support any operations on the tree. - * - * This function just calls `btree_new_with_allocator` with `free` and `malloc` - * as initializers. - */ -struct btree* btree_new(size_t elem_size, size_t t, - int (*cmp)(const void* a, const void* b)); - -/* Same as `btree_new`, except that it actually initializes a btree, but with - * the given allocators. - */ -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*)); - -void btree_free(struct btree** btree); - -void* btree_search(struct btree* btree, void* elem); -void btree_insert(struct btree* btree, void* elem); -int btree_delete(struct btree* btree, void* elem); - -void btree_print(struct btree* btree, void (*print_elem)(const void*)); - -void* btree_first(struct btree* btree); -void* btree_last(struct btree* btree); - -size_t btree_size(struct btree* btree); - -struct btree_iter_t* btree_iter_t_new(struct btree* tree); -void btree_iter_t_reset(struct btree* tree, struct btree_iter_t** it); - -void* btree_iter(struct btree* tree, struct btree_iter_t* iter); - -#ifdef __cplusplus -} -#endif -#endif diff --git a/src/utils/include/engine/utils/fov.h b/src/utils/include/engine/utils/fov.h deleted file mode 100644 index be64a9e..0000000 --- a/src/utils/include/engine/utils/fov.h +++ /dev/null @@ -1,28 +0,0 @@ -#ifndef ENGINE_FOV_H -#define ENGINE_FOV_H - -#ifdef __cplusplus -extern "C" { -#endif - -#include <engine/core/types.h> -#include <stdbool.h> -#include <cglm/ivec2.h> - -/* `fov_shadowcast`: */ -/* map: your 2D enum tile grid - * mapsize: x: width, y: height of the map - * visblocking: pointer to a function that returns `true` when receiving a - * pointer to a LOS blocking tile - * lightmap: [out] 2D lightmap, this is simply overwritten with the - * distance to the source. range: visibility range/radius. src: 2D - * point to calculate FOV from - * */ -void fov_shadowcast(const void* map, const ivec2 mapsize, - bool (*visblocking)(const void*), i32* lightmap, - const i32 range, const ivec2 src); - -#ifdef __cplusplus -} -#endif -#endif diff --git a/src/utils/include/engine/utils/hashmap.h b/src/utils/include/engine/utils/hashmap.h deleted file mode 100644 index 0113ce5..0000000 --- a/src/utils/include/engine/utils/hashmap.h +++ /dev/null @@ -1,61 +0,0 @@ -#ifndef ENGINE_HASHMAP_H -#define ENGINE_HASHMAP_H - -#ifdef __cplusplus -extern "C" { -#endif - -#include <stdlib.h> - -#include <engine/core/types.h> -#include <engine/core/memory.h> -#include <engine/utils/list.h> - -usize lolhash(const usize s, usize v); - -/* Define a linked list before using this */ -/* Example: DEFINE_LLIST(i32) */ -#define DEFINE_HASHMAP(type, lsize, cmp, type_to_int) \ - typedef DEFINE_LLIST(type); \ - typedef struct hashmap_##type { \ - usize size; \ - List_##type elems[64]; \ - } hashmap_##type; \ - \ - type* hashmap_##type##_lookup(hashmap_##type* hmap, const type* val) { \ - const usize idx = lolhash(64, type_to_int(val)); \ - List_##type* head = &hmap->elems[idx]; \ - while (head != NULL) { \ - if (!cmp(&(head->value), val)) return &(head->value); \ - head = head->next; \ - } \ - return NULL; \ - } \ - \ - void hashmap_##type##_insert(memory* m, hashmap_##type* hmap, \ - const type* val) { \ - const usize idx = lolhash(64, type_to_int(val)); \ - List_##type* head = &(hmap->elems[idx]); \ - \ - /* This is highly dependant on whether the memory is zero-initialized */ \ - if (!type_to_int(&(head->value))) { \ - memcpy(&(head->value), val, sizeof(type)); \ - return; \ - } \ - \ - while (head->next != NULL && cmp(&head->value, val)) { \ - head = head->next; \ - } \ - \ - if (!cmp(&head->value, val)) \ - memcpy(&(head->value), val, sizeof(type)); \ - else { \ - head->next = memory_allocate(m, sizeof(List_##type)); \ - memcpy(&(head->next->value), val, sizeof(type)); \ - } \ - } - -#ifdef __cplusplus -} -#endif -#endif diff --git a/src/utils/include/engine/utils/list.h b/src/utils/include/engine/utils/list.h deleted file mode 100644 index 04dda04..0000000 --- a/src/utils/include/engine/utils/list.h +++ /dev/null @@ -1,18 +0,0 @@ -#ifndef ENGINE_LIST_H -#define ENGINE_LIST_H - -#ifdef __cplusplus -extern "C" { -#endif - -#define DEFINE_LLIST(type) \ - struct List_##type { \ - type value; \ - struct List_##type* next; \ - /* Force the user to add `;` for style consistency */ \ - } List_##type - -#ifdef __cplusplus -} -#endif -#endif diff --git a/src/utils/include/engine/utils/stack.h b/src/utils/include/engine/utils/stack.h deleted file mode 100644 index b4caf5f..0000000 --- a/src/utils/include/engine/utils/stack.h +++ /dev/null @@ -1,33 +0,0 @@ -#ifndef STACK_H -#define STACK_H - -#ifdef __cplusplus -extern "C" { -#endif - -#include <engine/core/types.h> - -typedef struct { - usize head; /* current number of elements */ - const usize elem_size; /* size in bytes of each element */ - usize size; /* current memory size used by the stack */ - const usize chunk_size; /* size of which the stack increases when running out - of mem */ - void* data; /* memory buffer */ -} Stack; - -Stack stack_new_ex(const usize element_size, const usize size); - -Stack stack_new(const usize element_size); - -void stack_free(Stack* s); -void* stack_pop(Stack* s); -void stack_push(Stack* s, void* elem); -void* stack_peek(Stack* s); -usize stack_size(const Stack* s); -void stack_swap(Stack* s, Stack* t); - -#ifdef __cplusplus -} -#endif -#endif diff --git a/src/utils/src/btree.c b/src/utils/src/btree.c deleted file mode 100644 index 9411072..0000000 --- a/src/utils/src/btree.c +++ /dev/null @@ -1,800 +0,0 @@ -#include <engine/utils/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 { - size_t n; /* number of items/keys/elements */ - size_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; - size_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 size_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 size_t degree) { - const size_t max_children = 2 * degree + 1; - size_t 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))) { - size_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 size_t t, const size_t elem_size, - struct node* nonfull, size_t i) { - struct node* z = node_new(t, elem_size); - struct node* y = nonfull->children[i]; - size_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, size_t i, const size_t elem_size, - void (*dealloc)(void*)) { - struct node* y = x->children[i]; - struct node* z = x->children[i + 1]; - size_t 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, size_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)) { - size_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, size_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 size_t degree, - const size_t elem_size, - int (*cmp)(const void* a, const void* b)) { - - /* TODO check correctness */ - size_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 size_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 */ - size_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 (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 size_t degree, - const size_t elem_size, void* (*alloc)(size_t), - void (*dealloc)(void*)) { - /* Determine wether the key is in the node */ - size_t 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 */ - size_t 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; - size_t 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*)) { - size_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 size_t head = 0; - register size_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) && (size_t)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 ((size_t)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 * (((size_t)pos - 1) / 2); -} diff --git a/src/utils/src/fov.c b/src/utils/src/fov.c deleted file mode 100644 index 90df5af..0000000 --- a/src/utils/src/fov.c +++ /dev/null @@ -1,95 +0,0 @@ -#include <engine/utils/fov.h> -#include <engine/utils.h> -#include <math.h> -#include <stdint.h> - -void fov_shadowcast_rec(const void* map, const ivec2 mapsize, - bool (*visblocking)(const void*), i32* lightmap, - const i32 range, ivec2 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[0] + dx * xx + dy * xy; - const i32 mapy = src[1] + 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[0] && mapy >= 0 && - mapy < (long)mapsize[1]) { - // TODO: Calculate proper dist from source - i32 x_2 = (src[0] - mapx) * (src[0] - mapx); - i32 y_2 = (src[1] - mapy) * (src[1] - mapy); - lightmap[mapy * mapsize[0] + mapx] = - MAX(lightmap[mapy * mapsize[0] + mapx], - (i32)(range - sqrt((f64)(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 */ - * (usize)(mapsize[0] * 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 ivec2 mapsize, - bool (*visblocking)(const void*), i32* lightmap, - const i32 range, const ivec2 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[1] * mapsize[0] + src[0]] = range; -} diff --git a/src/utils/src/hashmap.c b/src/utils/src/hashmap.c deleted file mode 100644 index f7784d5..0000000 --- a/src/utils/src/hashmap.c +++ /dev/null @@ -1,5 +0,0 @@ -#include <engine/utils/hashmap.h> - -/* Currently, this is a "works, but very poorly" placeholder implementation. - * Should be avoided in practice */ -usize lolhash(const usize s, usize v) { return v % s; } diff --git a/src/utils/src/misc.c b/src/utils/src/misc.c deleted file mode 100644 index 063efbf..0000000 --- a/src/utils/src/misc.c +++ /dev/null @@ -1,86 +0,0 @@ -#include <stdint.h> -#include <stdlib.h> - -#include <string.h> - -#include <engine/core/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 (i32)((f32)a * (1.0f - dt)) + (i32)((f32)b * dt); -} - -u32 hash(char* str) { - u32 sum = 0; - while (*str != '\0') { - sum ^= (u32)(*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 ivec2 mapsize, - predicate_t* predicate) { - const usize w = (usize)mapsize[0]; - const usize h = (usize)mapsize[1]; - i32 mask[w * h]; - - if (w * h < 1) return NULL; - - for (usize i = 0; i < w * h; i++) { - mask[i] = predicate((void*)((u64)map + sizeof(i32) * i)) ? 1 : 0; - } - - for (usize y = 1; y < h - 1; y++) { - for (usize x = 1; x < w - 1; x++) { - const usize global_idx = (y * w) + x; - const usize 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 (usize yy = offs; yy <= offs + w + w; yy += w) { - for (usize 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/src/stack.c b/src/utils/src/stack.c deleted file mode 100644 index a7cb16d..0000000 --- a/src/utils/src/stack.c +++ /dev/null @@ -1,82 +0,0 @@ -#include <engine/core/logging.h> -#include <engine/utils/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); -} - -usize 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); - } - usize 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); -} |