From df31600e08952b5911e0669da98491593997c623 Mon Sep 17 00:00:00 2001 From: Elias Fleckenstein Date: Tue, 24 Aug 2021 16:21:27 +0200 Subject: [PATCH] Extract source from dragonblocks alpha --- README.md | 7 +++ array.c | 54 ++++++++++++++++++++ array.h | 21 ++++++++ bintree.c | 61 ++++++++++++++++++++++ bintree.h | 27 ++++++++++ implementation.c | 7 +++ list.c | 100 ++++++++++++++++++++++++++++++++++++ list.h | 39 +++++++++++++++ number.c | 128 +++++++++++++++++++++++++++++++++++++++++++++++ number.h | 55 ++++++++++++++++++++ queue.c | 47 +++++++++++++++++ queue.h | 19 +++++++ 12 files changed, 565 insertions(+) create mode 100644 README.md create mode 100644 array.c create mode 100644 array.h create mode 100644 bintree.c create mode 100644 bintree.h create mode 100644 implementation.c create mode 100644 list.c create mode 100644 list.h create mode 100644 number.c create mode 100644 number.h create mode 100644 queue.c create mode 100644 queue.h diff --git a/README.md b/README.md new file mode 100644 index 0000000..035fc7b --- /dev/null +++ b/README.md @@ -0,0 +1,7 @@ +# Dragontype +Dragontype is a small C library providing the types that [dragonblocks_alpha](https://github.com/dragonblocks/dragonblocks_alpha) uses. +It serves a similar purpose as the C++ standard library would, but C++ is just bloated af. +This library is only capable of what dragonblocks needs, and it does not intend to be general purpose. + +Included are Array, Bintree, List and Queue as well as numeric types and (de-)serialisation for them. +To use this in your project, just compile the implementation.c file into your project's binary. diff --git a/array.c b/array.c new file mode 100644 index 0000000..c3d4724 --- /dev/null +++ b/array.c @@ -0,0 +1,54 @@ +#include +#include +#include "array.h" + +Array array_create(size_t membsiz) +{ + return (Array) { + .membsiz = membsiz, + .siz = 0, + .cap = 0, + .ptr = NULL, + }; +} + + +static void array_realloc(Array *array) +{ + if (array->siz > array->cap) { + array->cap = array->siz + DRAGONTYPE_ARRAY_REALLOC_EXTRA; + array->ptr = realloc(array->ptr, array->cap * array->membsiz); + } +} + +static void array_alloc(Array *array, size_t siz) +{ + array->siz += siz; + array_realloc(array); +} + +void array_insert(Array *array, void *elem, size_t idx) +{ + size_t oldsiz = array->siz; + array_alloc(array, 1); + + char *iptr = (char *) array->ptr + idx * array->membsiz; + memmove(iptr + array->membsiz, iptr, (oldsiz - idx) * array->membsiz); + memcpy(iptr, elem, array->membsiz); +} + +void array_append(Array *array, void *elem) +{ + size_t oldsiz = array->siz; + array_alloc(array, 1); + + memcpy((char *) array->ptr + oldsiz * array->membsiz, elem, array->membsiz); +} + +void array_copy(Array *array, void **ptr, size_t *count) +{ + *count = array->siz; + size_t size = array->siz * array->membsiz; + *ptr = malloc(size); + memcpy(*ptr, array->ptr, size); +} diff --git a/array.h b/array.h new file mode 100644 index 0000000..9cbca5b --- /dev/null +++ b/array.h @@ -0,0 +1,21 @@ +#ifndef _DRAGONTYPE_ARRAY_H_ +#define _DRAGONTYPE_ARRAY_H_ + +#define DRAGONTYPE_ARRAY_REALLOC_EXTRA 25 + +#include +#include + +typedef struct +{ + size_t membsiz; + size_t siz, cap; + void *ptr; +} Array; + +Array array_create(size_t membsiz); +void array_insert(Array *array, void *elem, size_t idx); +void array_append(Array *array, void *elem); +void array_copy(Array *array, void **ptr, size_t *count); + +#endif diff --git a/bintree.c b/bintree.c new file mode 100644 index 0000000..f68fa1e --- /dev/null +++ b/bintree.c @@ -0,0 +1,61 @@ +#include +#include +#include "bintree.h" + +Bintree bintree_create(size_t key_size) +{ + return (Bintree) { + .root = NULL, + .key_size = key_size, + }; +} + +static BintreeNode **search_recursive(Bintree *tree, BintreeNode **nodeptr, void *key) +{ + if (*nodeptr) { + int cond; + + if ((cond = memcmp((*nodeptr)->key, key, tree->key_size)) == 0) + return nodeptr; + else if (cond > 0) + return search_recursive(tree, &(*nodeptr)->left, key); + else + return search_recursive(tree, &(*nodeptr)->right, key); + } else { + return nodeptr; + } +} + +BintreeNode **bintree_search(Bintree *tree, void *key) +{ + return search_recursive(tree, &tree->root, key); +} + +void bintree_add_node(Bintree *tree, BintreeNode **nodeptr, void *key, void *value) +{ + *nodeptr = malloc(sizeof(BintreeNode)); + (*nodeptr)->key = malloc(tree->key_size); + memcpy((*nodeptr)->key, key, tree->key_size); + (*nodeptr)->value = value; + (*nodeptr)->left = (*nodeptr)->right = NULL; +} + +static void free_recursive(BintreeNode *node, BintreeFreeFunction func, void *arg) +{ + if (node) { + free_recursive(node->left, func, arg); + free_recursive(node->right, func, arg); + free(node->key); + if (func) + func(node->value, arg); + free(node); + } +} + +void bintree_clear(Bintree *tree, BintreeFreeFunction func, void *arg) +{ + if (tree) { + free_recursive(tree->root, func, arg); + tree->root = NULL; + } +} diff --git a/bintree.h b/bintree.h new file mode 100644 index 0000000..0e6e877 --- /dev/null +++ b/bintree.h @@ -0,0 +1,27 @@ +#ifndef _DRAGONTYPE_BINTREE_H_ +#define _DRAGONTYPE_BINTREE_H_ + +#include + +typedef struct BintreeNode +{ + void *key; + void *value; + struct BintreeNode *left; + struct BintreeNode *right; +} BintreeNode; + +typedef struct +{ + BintreeNode *root; + size_t key_size; +} Bintree; + +typedef void (*BintreeFreeFunction)(void *value, void *arg); + +Bintree bintree_create(size_t key_size); +BintreeNode **bintree_search(Bintree *tree, void *key); +void bintree_add_node(Bintree *tree, BintreeNode **nodeptr, void *key, void *value); +void bintree_clear(Bintree *tree, BintreeFreeFunction func, void *arg); + +#endif diff --git a/implementation.c b/implementation.c new file mode 100644 index 0000000..793594b --- /dev/null +++ b/implementation.c @@ -0,0 +1,7 @@ +// include *.c files + +#include "array.c" +#include "bintree.c" +#include "list.c" +#include "number.c" +#include "queue.c" diff --git a/list.c b/list.c new file mode 100644 index 0000000..7388eaf --- /dev/null +++ b/list.c @@ -0,0 +1,100 @@ +#include +#include +#include "list.h" + +bool list_compare_default(void *v1, void *v2) +{ + return v1 == v2; +} + +bool list_compare_string(void *v1, void *v2) +{ + return strcmp(v1, v2) == 0; +} + +List list_create(ListComparator cmp) +{ + return (List) { + .cmp = cmp ? cmp : list_compare_default, + .first = NULL, + }; +} + +void list_clear(List *list) +{ + list_clear_func(list, NULL, NULL); +} + +void list_clear_func(List *list, void (*func)(void *key, void *value, void *arg), void *arg) +{ + for (ListPair *pair = list->first; pair != NULL;) { + ListPair *next = pair->next; + if (func) + func(pair->key, pair->value, arg); + free(pair); + pair = next; + } + list->first = NULL; +} + +static ListPair *make_pair(void *key, void *value) +{ + ListPair *pair = malloc(sizeof(ListPair)); + pair->key = key; + pair->value = value; + pair->next = NULL; + return pair; +} + +bool list_put(List *list, void *key, void *value) +{ + ListPair **pairptr; + for (pairptr = &list->first; *pairptr != NULL; pairptr = &(*pairptr)->next) { + if (list->cmp((*pairptr)->key, key)) + return false; + } + *pairptr = make_pair(key, value); + return true; +} + +void *list_get_cached(List *list, void *key, void *(*provider)(void *key)) +{ + ListPair **pairptr; + for (pairptr = &list->first; *pairptr != NULL; pairptr = &(*pairptr)->next) { + if (list->cmp((*pairptr)->key, key)) + return (*pairptr)->value; + } + return (*pairptr = make_pair(key, provider(key)))->value; +} + +void list_set(List *list, void *key, void *value) +{ + ListPair **pairptr; + for (pairptr = &list->first; *pairptr != NULL; pairptr = &(*pairptr)->next) { + if (list->cmp((*pairptr)->key, key)) + break; + } + *pairptr = make_pair(key, value); +} + +void *list_delete(List *list, void *key) +{ + for (ListPair **pairptr = &list->first; *pairptr != NULL; pairptr = &(*pairptr)->next) { + if (list->cmp((*pairptr)->key, key)) { + ListPair *pair = *pairptr; + void *value = (*pairptr)->value; + *pairptr = pair->next; + free(pair); + return value; + } + } + return NULL; +} + +void *list_get(List *list, void *key) +{ + for (ListPair *pair = list->first; pair != NULL; pair = pair->next) + if (list->cmp(pair->key, key)) + return pair->value; + return NULL; +} diff --git a/list.h b/list.h new file mode 100644 index 0000000..8e4d844 --- /dev/null +++ b/list.h @@ -0,0 +1,39 @@ +#ifndef _DRAGONTYPE_LIST_H_ +#define _DRAGONTYPE_LIST_H_ + +#include + +#define ITERATE_LIST(list, pair) for (ListPair *pair = (list)->first; pair != NULL; pair = pair->next) + +typedef struct ListPair +{ + struct ListPair *next; + void *key; + void *value; +} ListPair; + +typedef bool (*ListComparator)(void *v1, void *v2); + +typedef struct +{ + ListComparator cmp; + ListPair *first; +} List; + +bool list_compare_default(void *v1, void *v2); +bool list_compare_string(void *v1, void *v2); + +List list_create(ListComparator cmp); +void list_clear(List *list); +void list_clear_func(List *list, void (*func)(void *key, void *value, void *arg), void *arg); + +bool list_put(List *list, void *key, void *value); +void *list_get_cached(List *list, void *key, void *(*provider)(void *key)); +void list_set(List *list, void *key, void *value); +void *list_get(List *list, void *key); +void *list_delete(List *list, void *key); + +bool list_serialize(int fd, List *list); // ToDo +bool list_deserialize(int fd, List *list); // ToDo + +#endif diff --git a/number.c b/number.c new file mode 100644 index 0000000..5835e9a --- /dev/null +++ b/number.c @@ -0,0 +1,128 @@ +#include +#include +#include +#include +#include "number.h" + +bool read_full(int fd, char *buffer, size_t size) +{ + size_t n_read_total = 0; + int n_read; + while (n_read_total < size) { + if ((n_read = read(fd, buffer + n_read_total, size - n_read_total)) == -1) { + perror("read"); + return false; + } + n_read_total += n_read; + } + return true; +} + +#define htobe8(x) x +#define be8toh(x) x + +#define READVEC(type, n) \ + type buf[n]; \ + for (int i = 0; i < n; i++) { \ + if (! read_ ## type(fd, &buf[i])) \ + return false; \ + } + +#define WRITEVEC(type, n) \ + for (int i = 0; i < n; i++) { \ + if (! write_ ## type(fd, vec[i])) \ + return false; \ + } \ + return true; + +#define DEFVEC(type) \ + bool read_v2 ## type(int fd, v2 ## type *ptr) \ + { \ + READVEC(type, 2) \ + ptr->x = buf[0]; \ + ptr->y = buf[1]; \ + return true; \ + } \ + bool write_v2 ## type(int fd, v2 ## type val) \ + { \ + type vec[2] = {val.x, val.y}; \ + WRITEVEC(type, 2) \ + } \ + bool v2 ## type ## _equals(v2 ## type a, v2 ## type b) \ + { \ + return a.x == b.x && a.y == b.y; \ + } \ + v2 ## type v2 ## type ## _add(v2 ## type a, v2 ## type b) \ + { \ + return (v2 ## type) {a.x + b.x, a.y + b.y}; \ + } \ + bool read_v3 ## type(int fd, v3 ## type *ptr) \ + { \ + READVEC(type, 3) \ + ptr->x = buf[0]; \ + ptr->y = buf[1]; \ + ptr->z = buf[2]; \ + return true; \ + } \ + bool write_v3 ## type(int fd, v3 ## type val) \ + { \ + type vec[3] = {val.x, val.y, val.z}; \ + WRITEVEC(type, 3) \ + } \ + bool v3 ## type ## _equals(v3 ## type a, v3 ## type b) \ + { \ + return a.x == b.x && a.y == b.y && a.z == b.z; \ + } \ + v3 ## type v3 ## type ## _add(v3 ## type a, v3 ## type b) \ + { \ + return (v3 ## type) {a.x + b.x, a.y + b.y, a.z + b.z}; \ + } + +#define DEFTYP(type, bits) \ + bool read_ ## type(int fd, type *buf) \ + { \ + u ## bits encoded; \ + if (! read_full(fd, (char *) &encoded, sizeof(type))) \ + return false; \ + *buf = be ## bits ## toh(encoded); \ + return true; \ + } \ + bool write_ ## type(int fd, type val) \ + { \ + u ## bits encoded = htobe ## bits(val); \ + if (write(fd, &encoded, sizeof(encoded)) == -1) { \ + perror("write"); \ + return false; \ + } \ + return true; \ + } \ + DEFVEC(type) + +#define DEFTYPES(bits) \ + DEFTYP(s ## bits, bits) \ + DEFTYP(u ## bits, bits) + +DEFTYPES(8) +DEFTYPES(16) +DEFTYPES(32) +DEFTYPES(64) + +#define DEFFLOAT(type) \ + bool read_ ## type(int fd, type *buf) \ + { \ + if (! read_full(fd, (char *) buf, sizeof(type))) \ + return false; \ + return true; \ + } \ + bool write_ ## type(int fd, type val) \ + { \ + if (write(fd, &val, sizeof(val)) == -1) { \ + perror("write"); \ + return false; \ + } \ + return true; \ + } \ + DEFVEC(type) + +DEFFLOAT(f32) +DEFFLOAT(f64) diff --git a/number.h b/number.h new file mode 100644 index 0000000..57a000b --- /dev/null +++ b/number.h @@ -0,0 +1,55 @@ +#ifndef _DRAGONTYPE_NUMBER_H_ +#define _DRAGONTYPE_NUMBER_H_ + +#include +#include +#include + +bool read_full(int fd, char *buffer, size_t size); + +#define DEFRW(type) \ + bool read_ ## type(int fd, type *ptr); \ + bool write_ ## type(int fd, type val); + +#define DEFBOX(type) \ + typedef struct {v ## type min; v ## type max;} aabb ## type; + +#define DEFVEC(type) \ + typedef struct {type x, y;} v2 ## type; \ + DEFRW(v2 ## type) \ + DEFBOX(2 ## type) \ + bool v2 ## type ## _equals(v2 ## type a, v2 ## type b); \ + v2 ## type v2 ## type ## _add(v2 ## type a, v2 ## type b); \ + typedef struct {type x, y, z;} v3 ## type; \ + DEFRW(v3 ## type) \ + DEFBOX(3 ## type) \ + bool v3 ## type ## _equals(v3 ## type a, v3 ## type b); \ + v3 ## type v3 ## type ## _add(v3 ## type a, v3 ## type b); + +#define DEFTYP(from, to) \ + typedef from to; \ + DEFRW(to) \ + DEFVEC(to) + +#define DEFTYPES(bits) \ + DEFTYP(int ## bits ## _t, s ## bits) \ + DEFTYP(uint ## bits ## _t, u ## bits) + +DEFTYPES(8) +DEFTYPES(16) +DEFTYPES(32) +DEFTYPES(64) + +typedef float f32; +typedef double f64; + +DEFTYP(float, f32) +DEFTYP(double, f64) + +#undef DEFRW +#undef DEFBOX +#undef DEFVEC +#undef DEFTYP +#undef DEFTYPES + +#endif diff --git a/queue.c b/queue.c new file mode 100644 index 0000000..04aaccd --- /dev/null +++ b/queue.c @@ -0,0 +1,47 @@ +#include +#include "queue.h" + +Queue *queue_create() +{ + Queue *queue = malloc(sizeof(Queue)); + queue->list = list_create(NULL); + pthread_mutex_init(&queue->mtx, NULL); + return queue; +} + +void queue_delete(Queue *queue) +{ + pthread_mutex_destroy(&queue->mtx); + list_clear(&queue->list); + free(queue); +} + +void queue_enqueue(Queue *queue, void *elem) +{ + pthread_mutex_lock(&queue->mtx); + list_put(&queue->list, elem, NULL); + pthread_mutex_unlock(&queue->mtx); +} + +void *dequeue(Queue *queue) +{ + return queue_dequeue_callback(queue, NULL); +} + +void *queue_dequeue_callback(Queue *queue, void (*callback)(void *elem)) +{ + pthread_mutex_lock(&queue->mtx); + void *elem = NULL; + ListPair **lptr = &queue->list.first; + if (*lptr) { + elem = (*lptr)->key; + ListPair *next = (*lptr)->next; + free(*lptr); + *lptr = next; + + if (callback) + callback(elem); + } + pthread_mutex_unlock(&queue->mtx); + return elem; +} diff --git a/queue.h b/queue.h new file mode 100644 index 0000000..da69686 --- /dev/null +++ b/queue.h @@ -0,0 +1,19 @@ +#ifndef _DRAGONTYPE_QUEUE_H_ +#define _DRAGONTYPE_QUEUE_H_ + +#include +#include "list.h" + +typedef struct +{ + List list; + pthread_mutex_t mtx; +} Queue; + +Queue *queue_create(); +void queue_delete(Queue *queue); +void queue_enqueue(Queue *queue, void *elem); +void *queue_dequeue(Queue *queue); +void *queue_dequeue_callback(Queue *queue, void (*callback)(void *elem)); + +#endif -- 2.44.0