# Dragonstd
Dragonstd is a small C library providing the data structures 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.
+Included are Array, List, Tree, Queue, Map, Flag, Refcount.
-#include <string.h> // for memmove, memcpy
#include <stdlib.h> // for malloc, realloc, free, qsort
+#include <string.h> // for memmove, memcpy
#include "array.h"
-void array_ini(Array *array, size_t mbs, size_t ext, ArrayComparator cmp)
+void array_ini(Array *array, size_t mbs, size_t ext)
{
array->mbs = mbs;
array->ext = ext;
- array->cmp = cmp;
array->siz = 0;
array->cap = 0;
array->ptr = NULL;
void array_cln(Array *dst, Array *src)
{
- array_ini(dst, src->mbs, src->ext, src->cmp);
+ array_ini(dst, src->mbs, src->ext);
array_cpy(src, &dst->ptr, &dst->siz);
dst->cap = dst->siz;
}
array->siz = 0;
}
-void array_del(Array *array)
+void array_clr(Array *array)
{
if (array->ptr)
free(array->ptr);
+ array_ini(array, array->mbs, array->ext);
}
-void array_srt(Array *array)
+void array_srt(Array *array, Comparator cmp)
{
- qsort(array->ptr, array->siz, array->mbs, array->cmp);
+ qsort(array->ptr, array->siz, array->mbs, cmp);
}
-ssize_t array_fnd(Array *array, const void *ptr, size_t *idx)
+ssize_t array_fnd(Array *array, const void *ptr, size_t *idx, Comparator cmp)
{
size_t low, high, mid;
while (low < high) {
mid = (low + high) / 2;
- int cmp = array->cmp(ptr, array->ptr + mid * array->mbs);
+ int rel = cmp(ptr, array->ptr + mid * array->mbs);
- if (cmp == 0)
+ if (rel == 0)
return idx ? (*idx = mid) : mid;
- else if (cmp < 0)
+ else if (rel < 0)
high = mid;
- else // (cmp > 0)
+ else // (rel > 0)
low = mid + 1;
}
return -1;
}
-size_t array_ins(Array *array, const void *ptr)
+size_t array_ins(Array *array, const void *ptr, Comparator cmp)
{
size_t n;
- array_fnd(array, ptr, &n);
+ array_fnd(array, ptr, &n, cmp);
array_put(array, ptr, n);
return n;
Array
-----
- +-----------+--------------------+---------------------------------------+
- | Operation | Average complexity | Notes |
- +-----------+--------------------+-------------------------------------- +
- | Lookup | O(1) | |
- | Append | O(1) | unpredictable if capacity is exceeded |
- | Insert | O(n) | unpredictable if capacity is exceeded |
- | Sort | O(n log n) | |
- | Find | O(log n) | |
- +-----------+--------------------+---------------------------------------+
-
- An array is a data structure where all elements (members) have the same size and are
+ Data structure where all elements (members) have the same size and are
located consecutively in memory.
- Each array has a size which holds the number of current elements of the array.
- It also has a capacity, which is the number of elements that currently fit into
- the array, which may be bigger than size.
-
- The lookup complexity is O(1), which makes arrays well suited for fast lookups.
-
- The complexity for appending an element at the end of the array is O(1).
-
- The complexity for inserting an element at an arbitrary index of the array is O(n),
- where n is the length of the array. This is because memory may need to be moved.
-
- However, the insert/append complexity becomes unpredictable and largely depends on
- the implementation of the C library if the capacity is exceeded. If the capacity
- needs to be extended, the memory is reallocated. The mentioned complexity rules
- only apply as long as (cap > siz + 1). *Usually*, realloc will have a complexity
- of either O(1), if the memory block happens to be already big enough, or
- O(n) + X, if a new, bigger block needs to be allocated and the memory copied.
-
- Note that when the capacity is extended, it is possible to allocated more space space
- than needed, to prevent frequent calls to append/insert from having to reallocate
- the memory every time. If, and if yes how much additional space is allocated is
- determined by the extra space field. Extra space for ext elements is allocated
- whenever a growth reallocation happens.
-
- The array can be sorted. In this case, the array is expected to have a comparator cmp
- that is not NULL.
-
- The comparison function must return an integer less than, equal to, or greater than
- zero if the first argument is considered to be respectively less than, equal to,
- or greater than the second. If two members compare as equal, their order in the
- sorted array is undefined. [Copied from the Linux man-pages]
-
- The sorting function uses the quicksort algorithm from the C library, which has an
- average complexity of O(n log n).
-
- To maintain the order of a sorted array, add and put should not be used.
*/
#ifndef _DRAGONSTD_ARRAY_H_ // include guard
#include <stddef.h> // for size_t
#include <sys/types.h> // for ssize_t
-
-typedef int (*ArrayComparator)(const void *va, const void *vb);
+#include "bits/callback.h"
typedef struct {
/* public */
- void *ptr; // memory
- size_t ext; // extra space
- ArrayComparator cmp; // comparator
+ void *ptr; // memory
+ size_t ext; // extra space
/* private */
- size_t mbs; // member size
- size_t siz; // used space
- size_t cap; // available space
+ size_t mbs; // member size
+ size_t siz; // used space
+ size_t cap; // available space
} Array;
-void array_ini(Array *array, size_t mmb, size_t ext, ArrayComparator cmp);
+void array_ini(Array *array, size_t mmb, size_t ext);
/*
Initializes the array.
The array will have the member size of mmb and the extra space set to ext.
mmb should be bigger than 0 and may not be changed after the initialization.
ext can be 0 or bigger and may be changed any time.
- The comparator of the array is set to cmp and may be nil.
This function should be called before calling any other functions on the
array.
This function should not be called on an array that has been initialized before,
- unless the array either has a capacity of 0 or it has been deleted using
- array_del. Otherwise a memory leak will occur.
+ unless the array has a capacity of 0. Otherwise a memory leak will occur.
*/
void array_rlc(Array *array);
/*
Clones the array src to the array dst.
- dst is initialized to have the same configuration (member size, extra space,
- comparator) as src.
+ dst is initialized to have the same configuration (member size, extra space) as src.
After the operation, the contents of the array dst are be the same as those of src.
The size of dst and src are the same, the capacity of dst however is the same as
The array's memory is not free'd and the array can be reused.
*/
-void array_del(Array *array);
+void array_clr(Array *array);
/*
- Deletes the array.
+ Clears the array.
This function frees the arrays memory. If this is not called when the array's
reference is dropped, a memory leak occurs, unless the array is empty (capacity
of 0), in which case the function does not need to be called. The function works
fine on empty arrays however.
- After this, the array should no longer be used until reinitialized.
+ After this, the array is empty and can be reused.
*/
-void array_srt(Array *array);
+void array_srt(Array *array, Comparator cmp);
/*
Sorts the array using the quicksort algorithm.
- The array is assumed to have a non-NULL comparator.
+ Comparator must not be NULL.
Wraps the qsort C-library routine. Please refer to it's documentation.
*/
-ssize_t array_fnd(Array *array, const void *ptr, size_t *idx);
+ssize_t array_fnd(Array *array, const void *ptr, size_t *idx, Comparator cmp);
/*
Searches the sorted array for the element ptr.
Returns the index of the element, or -1 if it wasn't found.
points to. This is the index ptr would need to be inserted at to keep the order.
It is assumed that the array has been sorted by array_srt before (or was empty),
- and the order has been kept and the comparator has not been changed since.
+ and the order has been kept and the same comparator is used.
*/
-size_t array_ins(Array *array, const void *ptr);
+size_t array_ins(Array *array, const void *ptr, Comparator cmp);
/*
Inserts an element into a sorted array, keeping the order.
Returns the index the element has been inserted at.
Calls array_fnd and array_put.
It is assumed that the array has been sorted by array_srt before (or was empty),
- and the order has been kept and the comparator has not been changed since.
+ and the order has been kept and the same comparator is used.
*/
#endif // _DRAGONSTD_ARRAY_H_
+++ /dev/null
-#include <string.h>
-#include <stdlib.h>
-#include <stdbool.h>
-#include "bintree.h"
-
-typedef struct
-{
- BintreeTraversionFunction func;
- void *arg;
-} BintreeFreeData;
-
-static int bintree_compare_mem(void *v1, void *v2, Bintree *tree)
-{
- return memcmp(v1, v2, tree->key_size);
-}
-
-Bintree bintree_create(size_t key_size, BintreeComparator cmp)
-{
- return (Bintree) {
- .root = NULL,
- .key_size = key_size,
- .cmp = cmp ? cmp : &bintree_compare_mem,
- };
-}
-
-static BintreeNode **search_recursive(Bintree *tree, BintreeNode **nodeptr, void *key, bool return_existing)
-{
- if (*nodeptr) {
- int cond;
-
- if ((cond = tree->cmp((*nodeptr)->key, key, tree)) == 0 && return_existing)
- return nodeptr;
- else if (cond > 0)
- return search_recursive(tree, &(*nodeptr)->left, key, return_existing);
- else
- return search_recursive(tree, &(*nodeptr)->right, key, return_existing);
- } else {
- return nodeptr;
- }
-}
-
-BintreeNode **bintree_search(Bintree *tree, void *key)
-{
- return search_recursive(tree, &tree->root, key, true);
-}
-
-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;
-}
-
-void bintree_insert(Bintree *tree, void *key, void *value)
-{
- bintree_add_node(tree, search_recursive(tree, &tree->root, key, false), key, value);
-}
-
-static void bintree_free(BintreeNode *node, void *arg)
-{
- BintreeFreeData *fdata = arg;
-
- if (fdata->func)
- fdata->func(node, fdata->arg);
-
- free(node->key);
- free(node);
-}
-
-void bintree_clear(Bintree *tree, BintreeTraversionFunction func, void *arg)
-{
- if (tree) {
- BintreeFreeData fdata = {
- .func = func,
- .arg = arg,
- };
-
- bintree_traverse(tree, BTT_POSTORDER, &bintree_free, &fdata);
- tree->root = NULL;
- }
-}
-
-static void traverse_recursive(BintreeNode *node, BintreeTraversion traversion, BintreeTraversionFunction func, void *arg)
-{
- if (node) {
- if (traversion == BTT_PREORDER)
- func(node, arg);
-
- traverse_recursive(node->left, traversion, func, arg);
-
- if (traversion == BTT_INORDER)
- func(node, arg);
-
- traverse_recursive(node->right, traversion, func, arg);
-
- if (traversion == BTT_POSTORDER)
- func(node, arg);
- }
-}
-
-void bintree_traverse(Bintree *tree, BintreeTraversion traversion, BintreeTraversionFunction func, void *arg)
-{
- traverse_recursive(tree->root, traversion, func, arg);
-}
+++ /dev/null
-#ifndef _DRAGONSTD_BINTREE_H_
-#define _DRAGONSTD_BINTREE_H_
-
-#include <stddef.h>
-
-struct Bintree;
-
-typedef struct BintreeNode
-{
- void *key;
- void *value;
- struct BintreeNode *left;
- struct BintreeNode *right;
-} BintreeNode;
-
-typedef int (*BintreeComparator)(void *v1, void *v2, struct Bintree *tree);
-typedef void (*BintreeTraversionFunction)(BintreeNode *node, void *arg);
-
-typedef struct Bintree
-{
- BintreeNode *root;
- size_t key_size;
- BintreeComparator cmp;
-} Bintree;
-
-typedef enum
-{
- BTT_PREORDER,
- BTT_INORDER,
- BTT_POSTORDER,
-} BintreeTraversion;
-
-Bintree bintree_create(size_t key_size, BintreeComparator cmp);
-BintreeNode **bintree_search(Bintree *tree, void *key);
-void bintree_add_node(Bintree *tree, BintreeNode **nodeptr, void *key, void *value);
-void bintree_insert(Bintree *tree, void *key, void *value);
-void bintree_traverse(Bintree *tree, BintreeTraversion traversion, BintreeTraversionFunction func, void *arg);
-void bintree_clear(Bintree *tree, BintreeTraversionFunction func, void *arg);
-
-#endif
--- /dev/null
+#ifndef _DRAGONSTD_CALLBACK_H_ // include guard
+#define _DRAGONSTD_CALLBACK_H_
+
+typedef void *(*Transformer)(void *dat);
+typedef void (*Callback)(void *dat);
+typedef void (*Iterator)(void *dat, void *arg);
+typedef int (*Comparator)(const void *dat, const void *key);
+
+#endif // _DRAGONSTD_CALLBACK_H_
--- /dev/null
+#define WRAP_NODE_FUNCTIONS(Type, prefix) \
+ void *prefix ## add(Type *self, void *dat, Comparator cmp, Transformer func) \
+ { \
+ Type ## Node **node = prefix ## nfd(self, dat, cmp); \
+ \
+ if (! *node) \
+ prefix ## nmk(self, node, func ? func(dat) : dat); \
+ \
+ return (*node)->dat; \
+ } \
+ \
+ void *prefix ## get(Type *self, void *key, Comparator cmp, Transformer func) \
+ { \
+ Type ## Node **node = prefix ## nfd(self, key, cmp); \
+ \
+ if (! *node) \
+ return NULL; \
+ \
+ return func ? func((*node)->dat) : (*node)->dat; \
+ } \
+ \
+ void *prefix ## del(Type *self, void *key, Comparator cmp, Transformer func) \
+ { \
+ Type ## Node **node = prefix ## nfd(self, key, cmp); \
+ \
+ if (! *node) \
+ return NULL; \
+ \
+ void *dat = func ? func((*node)->dat) : (*node)->dat; \
+ prefix ## nrm(self, node); \
+ return dat; \
+ }
-#include <stdlib.h>
#include "flag.h"
-Flag *flag_create()
+void flag_ini(Flag *flag)
{
- Flag *flag = malloc(sizeof *flag);
- flag->done = false;
- pthread_cond_init(&flag->cv, NULL);
+ flag->set = false;
+ pthread_cond_init(&flag->cnd, NULL);
pthread_mutex_init(&flag->mtx, NULL);
- return flag;
}
-void flag_delete(Flag *flag)
+void flag_dst(Flag *flag)
{
- pthread_cond_destroy(&flag->cv);
+ pthread_cond_destroy(&flag->cnd);
pthread_mutex_destroy(&flag->mtx);
- free(flag);
}
-void flag_wait(Flag *flag)
+void flag_set(Flag *flag)
{
pthread_mutex_lock(&flag->mtx);
- if (! flag->done)
- pthread_cond_wait(&flag->cv, &flag->mtx);
+ flag->set = true;
+ pthread_cond_broadcast(&flag->cnd);
pthread_mutex_unlock(&flag->mtx);
}
-void flag_set(Flag *flag)
+void flag_slp(Flag *flag)
{
pthread_mutex_lock(&flag->mtx);
- flag->done = true;
- pthread_cond_broadcast(&flag->cv);
+ if (! flag->set)
+ pthread_cond_wait(&flag->cnd, &flag->mtx);
pthread_mutex_unlock(&flag->mtx);
}
-#ifndef _DRAGONSTD_FLAG_H_
+/*
+ Flag
+ ----
+
+ A flag is a data structure that can be used to syncronize a boolean across multiple
+ threads.
+
+ The flag's state can be set, read and waited for in a thread safe manner.
+*/
+
+#ifndef _DRAGONSTD_FLAG_H_ // include guard
#define _DRAGONSTD_FLAG_H_
-#include <stdbool.h>
-#include <stdatomic.h>
-#include <pthread.h>
+#include <pthread.h> // for pthread_mutex_t, pthread_cond_t
+#include <stdatomic.h> // for atomic_bool
+#include <stdbool.h> // for bool
typedef struct {
- atomic_bool done;
- pthread_cond_t cv;
- pthread_mutex_t mtx;
+ /* protected */
+ atomic_bool set; // whether the flag is set
+ /* private */
+ pthread_cond_t cnd; // condition variable used for waiting
+ pthread_mutex_t mtx; // mutex to protect the condition variable
} Flag;
-Flag *flag_create();
-void flag_delete(Flag *flag);
+void flag_ini(Flag *flag);
+/*
+ Initializes the flag.
+
+ The flag should be uninitialized or deleted before passed to this function.
+ This function should be called before any other function is called on the flag.
+*/
+
+void flag_dst(Flag *flag);
+/*
+ Destroy the flag.
+
+ The refcount is unusable until reinitialized afterwards.
+*/
+
void flag_set(Flag *flag);
-void flag_wait(Flag *flag);
+/*
+ [Thread Safe]
+ Sets the flag.
+
+ This changes the flag state to be true and wakes up any threads waiting for it.
+ Afterwards, **the state cannot be changed back**.
+
+ This function can be called multiple times.
+*/
+
+void flag_slp(Flag *flag);
+/*
+ [Thread Safe]
+ Waits for the flag to be true.
+
+ This will sleep until the flag's state is changed to true, unless it is already set to
+ true.
+*/
-#endif
+#endif // _DRAGONSTD_FLAG_H_
-#include <stdlib.h>
-#include <string.h>
+#include <stdlib.h> // for malloc, free
+#include <string.h> // for strcmp
+#include "bits/wrappers.h"
#include "list.h"
-bool list_compare_default(void *v1, void *v2)
-{
- return v1 == v2;
-}
+#define ITER_REFS node = &list->fst; *node != NULL; node = &(*node)->nxt
-bool list_compare_string(void *v1, void *v2)
+void list_ini(List *list)
{
- return strcmp(v1, v2) == 0;
+ list->fst = NULL;
+ list->end = &list->fst;
}
-List list_create(ListComparator cmp)
-{
- return (List) {
- .cmp = cmp ? cmp : list_compare_default,
- .first = NULL,
- };
-}
+WRAP_NODE_FUNCTIONS(List, list_)
-void list_clear(List *list)
+void list_apd(List *list, void *dat)
{
- list_clear_func(list, NULL, NULL);
+ list_nmk(list, list->end, dat);
}
-void list_clear_func(List *list, void (*func)(void *key, void *value, void *arg), void *arg)
+ListNode **list_nfd(List *list, void *key, Comparator cmp)
{
- 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;
-}
+ ListNode **node;
-static ListPair *make_pair(void *key, void *value)
-{
- ListPair *pair = malloc(sizeof(ListPair));
- pair->key = key;
- pair->value = value;
- pair->next = NULL;
- return pair;
+ for (ITER_REFS)
+ if (cmp((*node)->dat, key) == 0)
+ return node;
+
+ return node;
}
-bool list_put(List *list, void *key, void *value)
+void list_nmk(List *list, ListNode **node, void *dat)
{
- 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;
+ *node = malloc(sizeof **node);
+ (*node)->dat = dat;
+ (*node)->nxt = NULL;
+
+ if (list->end == node)
+ list->end = &(*node)->nxt;
}
-void *list_get_cached(List *list, void *key, void *(*provider)(void *key))
+void list_nrm(List *list, ListNode **node)
{
- 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;
+ ListNode *old = *node;
+ *node = old->nxt;
+
+ if (list->end == &old->nxt)
+ list->end = node;
+
+ free(old);
}
-void list_set(List *list, void *key, void *value)
+void list_itr(List *list, Iterator func, void *arg)
{
- ListPair **pairptr;
- for (pairptr = &list->first; *pairptr != NULL; pairptr = &(*pairptr)->next) {
- if (list->cmp((*pairptr)->key, key))
- break;
- }
- *pairptr = make_pair(key, value);
+ LIST_ITERATE(list, node)
+ func(node->dat, arg);
}
-void *list_delete(List *list, void *key)
+void list_clr(List *list, Iterator func, void *arg)
{
- 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;
- }
+ for (ListNode *node = list->fst; node != NULL;) {
+ ListNode *next = node->nxt;
+
+ if (func)
+ func(node->dat, arg);
+
+ free(node);
+ node = next;
}
- 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;
+ list_ini(list);
}
-#ifndef _DRAGONSTD_LIST_H_
-#define _DRAGONSTD_LIST_H_
+/*
+ List
+ ----
+
+ A linked list.
+*/
-#include <stdbool.h>
+#ifndef _DRAGONSTD_LIST_H_ // include guard
+#define _DRAGONSTD_LIST_H_
-#define ITERATE_LIST(list, pair) for (ListPair *pair = (list)->first; pair != NULL; pair = pair->next)
+#include "bits/callback.h" // for Iterator, Comparator
-typedef struct ListPair
-{
- struct ListPair *next;
- void *key;
- void *value;
-} ListPair;
+#define LIST_ITERATE(list, node) for (ListNode *node = (list)->fst; node != NULL; node = node->nxt)
-typedef bool (*ListComparator)(void *v1, void *v2);
+typedef struct ListNode {
+ /* public */
+ void *dat; // pointer to data
+ /* private */
+ struct ListNode *nxt; // next node
+} ListNode;
-typedef struct
-{
- ListComparator cmp;
- ListPair *first;
+typedef struct {
+ /* private */
+ ListNode *fst; // first element
+ ListNode **end; // where address of next node will be stored
} List;
-bool list_compare_default(void *v1, void *v2);
-bool list_compare_string(void *v1, void *v2);
+void list_ini(List *list);
+/*
+ Initializes the list.
+
+ The list should be uninitialized or empty before passed to this function.
+ This function should be called before any other function is called on the list.
+*/
+
+void *list_add(List *list, void *dat, Comparator cmp, Transformer func);
+/*
+ Add an element to the list.
+
+ If an equal element is already on the list, return it and don't add anything.
+ Otherwise, return added element.
+*/
+
+void *list_get(List *list, void *key, Comparator cmp, Transformer func);
+/*
+ Get an element from the list.
+
+ The first matching element is returned, or NULL if none found.
+*/
+
+void *list_del(List *list, void *key, Comparator cmp, Transformer func);
+/*
+ Delete an element from the list.
+
+ The first matching element is returned (after being removed from the list), or NULL
+ if none found.
+*/
+
+void list_apd(List *list, void *dat);
+/*
+ Append an element at the end of the list.
+*/
+
+ListNode **list_nfd(List *list, void *key, Comparator cmp);
+/*
+ Find the location of the first node matching key.
+
+ This can be either an existing node, or the location the next new node would need to
+ be stored.
+*/
+
+void list_nmk(List *list, ListNode **node, void *dat);
+/*
+ Create a node with dat as data and store it's pointer at the given location.
+*/
+
+void list_nrm(List *list, ListNode **node);
+/*
+ Remove the node at the given location.
+*/
+
+void list_itr(List *list, Iterator func, void *arg);
+/*
+ Iterate over the list.
+ Calls func on every element, with the extra argument arg.
-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);
+ Note: the LIST_ITERATE macro can be used to do this without function calls.
+*/
-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);
+void list_clr(List *list, Iterator func, void *arg);
+/*
+ Iterates over the list and deletes all elements.
+ Calls func on every element, with the extra argument arg.
-bool list_serialize(int fd, List *list); // ToDo
-bool list_deserialize(int fd, List *list); // ToDo
+ The list is empty afterwards.
+*/
-#endif
+#endif // _DRAGONSTD_LIST_H_
--- /dev/null
+#include "map.h"
+
+static bool get_lock(Map *map, bool write)
+{
+ bool success;
+
+ pthread_rwlock_rdlock(&map->clk);
+
+ if ((success = ! map->cnl)) {
+ if (write)
+ pthread_rwlock_wrlock(&map->tlk);
+ else
+ pthread_rwlock_rdlock(&map->tlk);
+ }
+
+ pthread_rwlock_unlock(&map->clk);
+
+ return success;
+}
+
+void map_ini(Map *map)
+{
+ tree_ini(&map->tre);
+ pthread_rwlock_init(&map->tlk, NULL);
+ map->cnl = false;
+ pthread_rwlock_init(&map->clk, NULL);
+}
+
+void map_dst(Map *map)
+{
+ pthread_rwlock_destroy(&map->tlk);
+ pthread_rwlock_destroy(&map->clk);
+}
+
+void map_cnl(Map *map, Iterator func, void *arg, TreeTraversionOrder order)
+{
+ pthread_rwlock_wrlock(&map->clk);
+ map->cnl = true;
+
+ pthread_rwlock_wrlock(&map->tlk);
+ pthread_rwlock_unlock(&map->clk);
+
+ tree_clr(&map->tre, func, arg, order);
+
+ pthread_rwlock_unlock(&map->tlk);
+}
+
+#define WRAP_TREE_FUNC(name, write) \
+ void *map_ ## name(Map *map, void *dat, Comparator cmp, Transformer func) \
+ { \
+ if (! get_lock(map, write)) \
+ return NULL; \
+ \
+ dat = tree_ ## name(&map->tre, dat, cmp, func); \
+ pthread_rwlock_unlock(&map->tlk); \
+ return dat; \
+ }
+
+WRAP_TREE_FUNC(add, true)
+WRAP_TREE_FUNC(get, false)
+WRAP_TREE_FUNC(del, true)
--- /dev/null
+/*
+ Map
+ ---
+
+ Thread safe map/set, using a Tree.
+ Useful for managing big amounts of objects with add, get and del access from multiple threads.
+*/
+
+#ifndef _DRAGONSTD_MAP_H_ // include guard
+#define _DRAGONSTD_MAP_H_
+
+#include <stdbool.h> // for bool
+#include <pthread.h> // for pthread_rwlock_t
+#include "bits/callback.h" // for Transformer, Comparator, Iterator
+#include "tree.h" // for Tree
+
+typedef struct {
+ /* private */
+ Tree tre; // search tree to manage data
+ pthread_rwlock_t tlk; // lock to protect tree
+ bool cnl; // cancel state
+ pthread_rwlock_t clk; // lock to protect cancel state
+} Map;
+
+void map_ini(Map *map);
+/*
+ Initializes the map.
+
+ The map should be uninitialized before passed to this function.
+ This function should be called before any other function is called on the tree.
+*/
+
+void map_dst(Map *map);
+/*
+ Destroys the map.
+
+ The map should not be used afterwards.
+ Make sure to cancel the map before destroying it, to avoid memory leaks.
+*/
+
+void map_cnl(Map *map, Iterator func, void *arg, TreeTraversionOrder order);
+/*
+ [Thread Safe]
+ Cancels and clears the map.
+
+ All subsequent calls to add, get and del have no effect and return NULL.
+
+ Traverses the map and deletes all elements.
+ Calls func on every element, with the extra argument arg.
+
+ The map is empty afterwards.
+ If no callback is given, the traversion order is irrelevant.
+*/
+
+void *map_add(Map *map, void *dat, Comparator cmp, Transformer func);
+/*
+ [Thread Safe]
+ Add an element to the map.
+
+ If an equal element is already in the tree, return it and don't add anything.
+ Otherwise, return added element.
+*/
+
+void *map_get(Map *map, void *key, Comparator cmp, Transformer func);
+/*
+ [Thread Safe]
+ Get an element from the map, or return NULL if none found.
+*/
+
+void *map_del(Map *map, void *key, Comparator cmp, Transformer func);
+/*
+ [Thread Safe]
+ Delete an element from the map and return it, or NULL if none found.
+*/
+
+#endif
-#include <stdio.h>
-#include <stdlib.h>
+#include <sched.h>
#include "queue.h"
-Queue *queue_create()
+void queue_ini(Queue *queue)
{
- Queue *queue = malloc(sizeof(Queue));
- queue->finish = false;
- queue->cancel = false;
- queue->list = list_create(NULL);
- pthread_cond_init(&queue->cv, NULL);
+ list_ini(&queue->lst);
+ queue->cnl = queue->fin = 0;
+ pthread_cond_init(&queue->cnd, NULL);
pthread_mutex_init(&queue->mtx, NULL);
- return queue;
}
-void queue_delete(Queue *queue)
+void queue_del(Queue *queue)
{
- pthread_cond_destroy(&queue->cv);
+ pthread_cond_destroy(&queue->cnd);
pthread_mutex_destroy(&queue->mtx);
- list_clear(&queue->list);
- free(queue);
}
-void queue_enqueue(Queue *queue, void *elem)
+void queue_clr(Queue *queue, Iterator func, void *arg)
{
+ list_clr(&queue->lst, func, arg);
+}
+
+bool queue_enq(Queue *queue, void *dat)
+{
+ bool success = false;
+
pthread_mutex_lock(&queue->mtx);
- if (! queue->finish) {
- list_put(&queue->list, elem, NULL);
- pthread_cond_signal(&queue->cv);
+ if (! queue->fin) {
+ success = true;
+ list_apd(&queue->lst, dat);
+ pthread_cond_signal(&queue->cnd);
}
pthread_mutex_unlock(&queue->mtx);
-}
-void *queue_dequeue(Queue *queue)
-{
- return queue_dequeue_callback(queue, NULL);
+ return success;
}
-void *queue_dequeue_callback(Queue *queue, void (*callback)(void *elem))
+void *queue_deq(Queue *queue, Transformer func)
{
- void *elem = NULL;
+ void *dat = NULL;
- while (! queue->cancel && ! elem) {
- pthread_mutex_lock(&queue->mtx);
-
- ListPair **lptr = &queue->list.first;
- if (*lptr) {
- elem = (*lptr)->key;
- ListPair *next = (*lptr)->next;
- free(*lptr);
- *lptr = next;
+ pthread_mutex_lock(&queue->mtx);
+ while (! queue->cnl && ! dat) {
+ ListNode **node = &queue->lst.fst;
+ if (*node) {
+ dat = (*node)->dat;
+ list_nrm(&queue->lst, node);
- if (callback)
- callback(elem);
+ if (func)
+ dat = func(dat);
} else {
- pthread_cond_wait(&queue->cv, &queue->mtx);
+ pthread_cond_wait(&queue->cnd, &queue->mtx);
}
-
- pthread_mutex_unlock(&queue->mtx);
}
+ pthread_mutex_unlock(&queue->mtx);
- return elem;
+ return dat;
}
-void queue_cancel(Queue *queue)
+void queue_cnl(Queue *queue)
{
- queue->cancel = true;
-
pthread_mutex_lock(&queue->mtx);
- pthread_cond_broadcast(&queue->cv);
+ queue->cnl = 1;
+ pthread_cond_broadcast(&queue->cnd);
pthread_mutex_unlock(&queue->mtx);
}
-void queue_finish(Queue *queue)
+void queue_fin(Queue *queue)
{
pthread_mutex_lock(&queue->mtx);
- queue->finish = true;
+ queue->fin = 1;
pthread_mutex_unlock(&queue->mtx);
- while (true) {
+ for (;;) {
pthread_mutex_lock(&queue->mtx);
- ListPair *first = queue->list.first;
+ ListNode *node = queue->lst.fst;
pthread_mutex_unlock(&queue->mtx);
- if (first)
+ if (node)
sched_yield();
else
break;
-#ifndef _DRAGONSTD_QUEUE_H_
+/*
+ Queue
+ -----
+
+ Thread safe FIFO data structure, using a List.
+ Useful for working with producer/consumer threads.
+*/
+
+#ifndef _DRAGONSTD_QUEUE_H_ // include guard
#define _DRAGONSTD_QUEUE_H_
-#include <pthread.h>
-#include <stdbool.h>
-#include <stdatomic.h>
-#include "list.h"
-
-typedef struct
-{
- atomic_bool cancel;
- bool finish;
- List list;
- pthread_cond_t cv;
- pthread_mutex_t mtx;
+#include <pthread.h> // for pthread_cond_t, pthread_mutex_t
+#include <stdbool.h> // for bool
+#include "bits/callback.h" // for Transformer
+#include "list.h" // for List
+
+typedef struct {
+ /* private */
+ List lst; // list containing data
+ unsigned int cnl: 1; // cancel state
+ unsigned int fin: 1; // finish state
+ pthread_cond_t cnd; // condition variable for notifying consumer
+ pthread_mutex_t mtx; // mutex to protect the condition variable
} 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));
-void queue_cancel(Queue *queue); // disallow dequeing
-void queue_finish(Queue *queue); // disallow enqueing, wait until consumption finished
+void queue_ini(Queue *queue);
+/*
+ Initializes the queue.
+
+ The queue should be uninitialized or deleted when passed to this function.
+*/
+
+void queue_del(Queue *queue);
+/*
+ Delete the queue.
+
+ Afterwards, the queue should no longer be used.
+
+ This does not clear the underling list. Use queue_fin or queue_clr to make sure the
+ list is cleared before calling this function.
+*/
+
+void queue_clr(Queue *queue, Iterator func, void *arg);
+/*
+ Clears the queue.
+
+ Calls list_clr on the underling list. This is not thread safe. Use queue_fin instead
+ to wait for consumer threads to finish processing the data.
+*/
+
+bool queue_enq(Queue *queue, void *dat);
+/*
+ [Thread Safe]
+ Enqueues an element to the back of the queue.
+ Returns true if the enqueueing was successful (this is always the case if queue_fin
+ has not been called)
+
+ Notifies waiting consumer threads.
+*/
+
+void *queue_deq(Queue *queue, Transformer func);
+/*
+ [Thread Safe]
+ Dequeue an element.
+
+ If no element is in the queue, wait until there is one.
+ The (optional) transformer is called once an element is available and has been
+ dequeued and while the queue mutex is still locked.
+
+ Note the the wait continues if the transformer returns NULL.
+*/
+
+void queue_cnl(Queue *queue);
+/*
+ [Thread Safe]
+ Cancels dequeueing.
+ Subsequent calls to queue_deq immediately return NULL.
+*/
+
+void queue_fin(Queue *queue); // disallow enqueing, wait until consumption finished
+/*
+ [Thread Safe]
+ Cancels enqueueing and waits for the queue to finish.
+ Subsequent calls to queue_enq have no effect and return false.
+
+ Before returning, this function waits for the queue to be empty.
+*/
-#endif
+#endif // _DRAGONSTD_QUEUE_H_
--- /dev/null
+#include "refcount.h"
+
+void refcount_ini(Refcount *refcount, void *obj, Transformer del)
+{
+ refcount->obj = obj;
+ refcount->del = del;
+ refcount->cnt = 1;
+ pthread_mutex_init(&refcount->mtx, NULL);
+}
+
+void refcount_dst(Refcount *refcount)
+{
+ pthread_mutex_destroy(&refcount->mtx);
+}
+
+void *refcount_inc(void *refcount)
+{
+ Refcount *rc = refcount;
+
+ pthread_mutex_lock(&rc->mtx);
+ rc->cnt++;
+ pthread_mutex_unlock(&rc->mtx);
+ return rc;
+}
+
+void *refcount_grb(void *refcount)
+{
+ return ((Refcount *) refcount_inc(refcount))->obj;
+}
+
+void *refcount_drp(void *refcount)
+{
+ Refcount *rc = refcount;
+
+ pthread_mutex_lock(&rc->mtx);
+ unsigned short count = --rc->cnt;
+ pthread_mutex_unlock(&rc->mtx);
+
+ if (! count)
+ return rc->del(rc->obj);
+
+ return rc->obj;
+}
--- /dev/null
+/*
+ Refcount
+ --------
+
+ An object that knows how and when to delete itself, using a reference counter.
+
+ Whenever a reference to an object like this is obtained/kept, it needs to be grabbed,
+ whenever a reference is discarded, it needs to be dropped.
+
+ Made for use with the List/Tree/Map types: refcount_inc, refcount_grb, refcount_drp
+ can be used as add, get, del callbacks.
+*/
+#ifndef _DRAGONSTD_REFCOUNT_H_ // include guard
+#define _DRAGONSTD_REFCOUNT_H_
+
+#include <pthread.h> // for pthread_mutex_t
+#include "bits/callback.h" // for Transformer
+
+typedef struct {
+ /* private */
+ void *obj;
+ Transformer del;
+ unsigned short cnt; // counter
+ pthread_mutex_t mtx; // lock to protect count
+} Refcount;
+
+void refcount_ini(Refcount *refcount, void *obj, Transformer del);
+/*
+ Initializes the refcount.
+
+ The refcount should be uninitialized or deleted before passed to this function.
+ This function should be called before any other function is called on the refcount.
+*/
+
+void refcount_dst(Refcount *refcount);
+/*
+ Destroy the refcount.
+
+ This does NOT mean delete the object that the reference counter is referring to-
+ This means delete the refcount structure itself (and is usually called from the
+ delete callback of the referenced object).
+
+ The refcount is unusable until reinitialized afterwards.
+*/
+
+void *refcount_inc(void *refcount);
+/*
+ [Thread Safe]
+ Grab a reference to the refcount.
+ This actually takes a Refcount * as argument, however void * is used to make it more
+ convenient to use the function as callback.
+
+ Returns the refcount.
+*/
+
+void *refcount_grb(void *refcount);
+/*
+ [Thread Safe]
+ Does the same as refcount_inc, except it returns the referenced object instead of the
+ refcount.
+*/
+
+void *refcount_drp(void *refcount);
+/*
+ [Thread Safe]
+ Drop a reference to the object.
+ This actually takes a Refcount * as argument, however void * is used to make it more
+ convenient to use the function as callback.
+
+ May delete the object using the del function if the counter gets down to zero.
+ Returns the return value of the del function if it has been called; returns the object
+ otherwise.
+*/
+
+#endif // _DRAGONSTD_REFCOUNT_H_
test_array
+test_list
+test_tree
+test_queue
+test_map
+test_flag
+test_refcount_map
-test_array: test_array.c ../array.c ../array.h
- cc -g -Wall -Wextra -Werror -o test_array test_array.c ../array.c
+CC=cc -g -Wall -Wextra -Werror -fmax-errors=1 -o
+TEST=valgrind --leak-check=full --show-leak-kinds=all --quiet
+
+run: test_array test_list test_tree test_queue test_flag test_refcount_map
+ $(TEST) ./test_array && \
+ $(TEST) ./test_list && \
+ $(TEST) ./test_tree && \
+ $(TEST) ./test_queue && \
+ $(TEST) ./test_flag && \
+ $(TEST) ./test_refcount_map
+
+test_array: test_array.c ../array.c ../array.h ../bits/callback.h
+ $(CC) test_array test_array.c ../array.c
+
+test_list: test_list.c ../list.c ../list.h ../bits/callback.h ../bits/wrappers.h
+ $(CC) test_list test_list.c ../list.c
+
+test_tree: test_tree.c ../tree.c ../tree.h ../bits/callback.h ../bits/wrappers.h
+ $(CC) test_tree test_tree.c ../tree.c
+
+test_queue: test_queue.c ../queue.c ../queue.h ../list.c ../list.h ../bits/callback.h ../bits/wrappers.h
+ $(CC) test_queue test_queue.c ../queue.c ../list.c -lpthread
+
+test_flag: test_flag.c ../flag.c ../flag.h
+ $(CC) test_flag test_flag.c ../flag.c -lpthread
+
+test_refcount_map: test_refcount_map.c ../refcount.c ../refcount.h ../map.c ../map.h ../tree.c ../tree.h ../bits/callback.h ../bits/wrappers.h
+ $(CC) test_refcount_map test_refcount_map.c ../refcount.c ../map.c ../tree.c -lpthread
+
+clean:
+ rm -rf test_array test_list test_tree test_queue test_flag test_refcount_map
int main()
{
+ printf("-------------\n");
+ printf("Testing Array\n");
+ printf("-------------\n");
+
int i;
Array arr, arr2;
- srand(time(0));
+ srand(time(NULL));
printf("testing ini\n");
- array_ini(&arr, sizeof(int), 0, NULL);
+ array_ini(&arr, sizeof(int), 0);
printf("testing add\n");
i = 1; array_add(&arr, &i);
for (size_t j = 0; j < arr.siz; j++)
assert(((int *) arr.ptr)[j] == ((int *) arr2.ptr)[j]);
- printf("testing del\n");
- array_del(&arr);
- array_del(&arr2);
+ printf("testing clr\n");
+ array_clr(&arr);
+ array_clr(&arr2);
- printf("testing ini after del\n");
- array_ini(&arr, sizeof(int), 5, (void *) &cmp_int);
+ printf("testing ini after clr\n");
+ array_ini(&arr, sizeof(int), 5);
printf("testing cap: exp: 0 got: %lu\n", arr.cap);
assert(arr.cap == 0);
assert(arr.cap == 8);
printf("testing srt\n");
- array_srt(&arr);
+ array_srt(&arr, (void *) &cmp_int);
printf("testing order: exp: (sorted) got: "); dump(&arr); printf("\n");
assert_in_order(&arr);
for (size_t j = 0; j < arr.siz; j++) {
- i = ((int *) arr.ptr)[j]; ssize_t s = array_fnd(&arr, &i, NULL);
+ i = ((int *) arr.ptr)[j];
+ ssize_t s = array_fnd(&arr, &i, NULL, (void *) &cmp_int);
printf("testing fnd at index %lu: exp: >=0 got: %ld\n", j, s);
assert(s >= 0);
printf("testing ins\n");
for (int j = 0; j < 10; j++) {
- i = rand() % 100; array_ins(&arr, &i);
+ i = rand() % 100; array_ins(&arr, &i, (void *) &cmp_int);
}
printf("testing order: exp: (sorted) got: "); dump(&arr); printf("\n");
assert_in_order(&arr);
- array_del(&arr);
+ array_clr(&arr);
}
--- /dev/null
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <time.h>
+#include "../flag.h"
+
+#define NUM_FLAGS 5
+#define ITER_FLAGS for (int i = 0; i < NUM_FLAGS; i++)
+
+Flag flags[NUM_FLAGS];
+
+void *start_thread(__attribute__((unused)) void *val)
+{
+ ITER_FLAGS {
+ printf("waiting for flag %d\n", i);
+ flag_slp(&flags[i]);
+ }
+
+ return NULL;
+}
+
+bool is_finished()
+{
+ ITER_FLAGS if (! flags[i].set)
+ return false;
+
+ return true;
+}
+
+int main()
+{
+ printf("------------\n");
+ printf("Testing Flag\n");
+ printf("------------\n");
+
+ srand(time(NULL));
+ ITER_FLAGS flag_ini(&flags[i]);
+
+ pthread_t thread;
+ pthread_create(&thread, NULL, &start_thread, NULL);
+
+ while (! is_finished()) {
+ int i = rand() % NUM_FLAGS;
+
+ printf("setting flag %d\n", i);
+ flag_set(&flags[i]);
+
+ nanosleep(&(struct timespec) {
+ .tv_sec = 0,
+ .tv_nsec = 1e7,
+ }, NULL);
+ }
+
+ pthread_join(thread, NULL);
+
+ ITER_FLAGS flag_dst(&flags[i]);
+}
--- /dev/null
+#include <assert.h>
+#include <stdio.h>
+#include "../list.h"
+
+int cmp_int(const void *ia, const void *ib)
+{
+ return *(const int *) ia - *(const int *) ib;
+}
+
+int main()
+{
+ printf("------------\n");
+ printf("Testing List\n");
+ printf("------------\n");
+
+ List list;
+
+ printf("testing ini\n");
+ list_ini(&list);
+
+ int a = 0;
+ int b = 1;
+ int c = 2;
+ int d = 2;
+ int e = 3;
+
+ printf("testing add\n");
+ assert(list_add(&list, &a, &cmp_int, NULL) == &a);
+ assert(list_add(&list, &b, &cmp_int, NULL) == &b);
+ assert(list_add(&list, &c, &cmp_int, NULL) == &c);
+ assert(list_add(&list, &d, &cmp_int, NULL) == &c);
+
+ printf("testing get\n");
+ assert(list_get(&list, &a, &cmp_int, NULL) == &a);
+ assert(list_get(&list, &b, &cmp_int, NULL) == &b);
+ assert(list_get(&list, &c, &cmp_int, NULL) == &c);
+ assert(list_get(&list, &d, &cmp_int, NULL) == &c);
+ assert(list_get(&list, &e, &cmp_int, NULL) == NULL);
+
+ printf("testing del\n");
+ assert(list_del(&list, &a, &cmp_int, NULL) == &a);
+ assert(list_get(&list, &a, &cmp_int, NULL) == NULL);
+
+ printf("testing clr\n");
+ list_clr(&list, NULL, NULL);
+ assert(list_get(&list, &b, &cmp_int, NULL) == NULL);
+}
--- /dev/null
+#include <stdatomic.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <time.h>
+#include "../queue.h"
+
+#define CHUNK_SIZE 1e5
+
+Queue queue;
+
+void *consumer(__attribute__((unused)) void *arg)
+{
+ char *data;
+
+ while ((data = queue_deq(&queue, NULL)) != NULL) {
+ // In a real world scenario, this would be something CPU intensive
+ char c = 0;
+
+ for (int i = 0; i < CHUNK_SIZE; i++)
+ c += data[i];
+
+ // How to convert char to int with zero-extend??? (MOVZX instruction on x86)
+ // I literally have no idea why cast/coersion doesn't work, union seems to work.
+ // But is it undefined behavior? And is there a better way to do it?
+ // I can't access StackOverflow rn so I'm leaving it like this, for now.
+ // I feel extremely stupid, feel free to make fun of me.
+ // Also, some cute stuff I found: 376825 (You can thank me later シ)
+ union {
+ int i;
+ char c;
+ } u;
+ u.i = 0;
+ u.c = c;
+
+ printf("%02x", u.i);
+ fflush(stdout);
+
+ free(data);
+ }
+
+ return NULL;
+}
+
+void *producer(__attribute__((unused)) void *arg)
+{
+ // In a real world scenario, this would be something with actual latency,
+ // e.g. a network connection
+ // In this example, I'm creating the latency by allocating huge chunks of memory.
+ // Sometimes I kinda get the feeling I've fallen pretty low, but then I remember
+ // JavaScript programmers exist
+ // (DERZOMBIIIE IF YOU READ THIS IM SORRY NOTHING PERSONAL LUV U <3)
+ FILE *file = fopen("/dev/random", "r");
+ void *buffer;
+
+ do
+ fread(buffer = malloc(CHUNK_SIZE), 1, CHUNK_SIZE, file);
+ while (queue_enq(&queue, buffer));
+
+ free(buffer);
+ fclose(file);
+
+ return NULL;
+}
+
+int main()
+{
+ printf("-------------\n");
+ printf("Testing Queue\n");
+ printf("-------------\n");
+
+ printf("Random bullshit go: ");
+ queue_ini(&queue);
+
+ pthread_t threads[17];
+
+ for (int i = 0; i < 17; i++)
+ pthread_create(&threads[i], NULL, i ? &consumer : &producer, NULL);
+
+ sleep(1);
+
+ queue_fin(&queue);
+ queue_cnl(&queue);
+
+ for (int i = 0; i < 17; i++)
+ pthread_join(threads[i], NULL);
+
+ queue_del(&queue);
+ printf("\n");
+}
+
+// Btw I figured out my MOVZX problem from earlier, but it's funny so I'm leaving it
+// I even figured it out without StackOverflow pls tell me you're proud of me
+// The reason why char -> int sometimes extends to 0 and sometimes to F is this:
+// char is signed by default, so if the first bit (sign bit) is on, it will extend that
+// to the first bit on the int (MOVSX instruction)
+// just use unsigned char to avoid it
+
+// ngl was even tempted to use inline assembly this is what happens to your brain when
+// you work offline
+
+// for real tho, why tf is char signed by default
+// its probably machine dependent (since there is the explicit signed qualifier for char)
+
+// This file is probably the biggest bogus I've ever published anyway
--- /dev/null
+#include <assert.h>
+#include <stdatomic.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <time.h>
+#include <unistd.h>
+#include <limits.h>
+#include "../map.h"
+#include "../refcount.h"
+
+Map map;
+atomic_bool cancel;
+
+typedef struct {
+ int id;
+ Refcount rc;
+} DataObject;
+
+void *data_object_delete(DataObject *obj)
+{
+ refcount_dst(&obj->rc);
+ free(obj);
+ return obj;
+}
+
+int rand_id()
+{
+ return rand() % 1000;
+}
+
+int data_object_compare(const void *pa, const void *pb)
+{
+ return
+ ((DataObject *) ((const Refcount *) pa)->obj)->id -
+ ((DataObject *) ((const Refcount *) pb)->obj)->id;
+}
+
+int data_object_compare_id(const void *pa, const void *pb)
+{
+ return
+ ((DataObject *) ((const Refcount *) pa)->obj)->id -
+ *(const int *) pb;
+}
+
+static void *thread_create(unsigned int *result)
+{
+ while (! cancel) {
+ DataObject *obj = malloc(sizeof *obj);
+ obj->id = rand_id();
+
+ refcount_ini(&obj->rc, obj, (void *) &data_object_delete);
+
+ if (map_add(&map, &obj->rc, &data_object_compare, &refcount_inc) == &obj->rc)
+ (*result)++;
+
+ refcount_drp(&obj->rc);
+ }
+
+ return NULL;
+}
+
+#define NUM_OBJS 100
+
+static void *thread_access(unsigned int *result)
+{
+ DataObject *objs[NUM_OBJS] = {NULL};
+
+ while (! cancel) {
+ int i = rand() % NUM_OBJS;
+
+ if (objs[i]) {
+ refcount_drp(&objs[i]->rc);
+ objs[i] = NULL;
+ }
+
+ while (! objs[i] && ! cancel) {
+ int id = rand_id();
+ objs[i] = map_get(&map, &id, &data_object_compare_id, &refcount_grb);
+ }
+
+ if (objs[i])
+ (*result)++;
+ }
+
+ for (int i = 0; i < NUM_OBJS; i++)
+ if (objs[i])
+ refcount_drp(&objs[i]->rc);
+
+ return NULL;
+}
+
+#undef NUM_OBJS
+
+static void *thread_delete(unsigned int *result)
+{
+ while (! cancel) {
+ unsigned int id = rand_id();
+
+ if (map_del(&map, &id, &data_object_compare_id, &refcount_drp))
+ (*result)++;
+ }
+
+ return NULL;
+}
+
+int main()
+{
+ srand(time(NULL));
+
+ printf("------------------------\n");
+ printf("Testing Map and Refcount\n");
+ printf("------------------------\n");
+
+ map_ini(&map);
+
+ void *(*funcs[3])(void *) = {
+ (void *) &thread_create,
+ (void *) &thread_access,
+ (void *) &thread_delete,
+ };
+
+ unsigned int results[3][5] = {0};
+ pthread_t threads[3][5] = {0};
+
+ for (int i = 0; i < 3; i++)
+ for (int j = 0; j < 5; j++)
+ pthread_create(&threads[i][j], NULL, funcs[i], &results[i][j]);
+
+ sleep(10);
+
+ cancel = true;
+ for (int i = 0; i < 3; i++)
+ for (int j = 0; j < 5; j++) {
+ pthread_join(threads[i][j], NULL);
+
+ if (j)
+ results[i][0] += results[i][j];
+ }
+
+ map_cnl(&map, (void *) &refcount_drp, NULL, 0);
+ map_dst(&map);
+
+ printf("Time: 10 seconds\n");
+ printf("Created objects: %u\n", results[0][0]);
+ printf("Accessed objects: %u\n", results[1][0]);
+ printf("Deleted objects: %u\n", results[2][0]);
+}
--- /dev/null
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include "../tree.h"
+
+#define NUM_ELEMENTS 1e5
+
+int cmp_int(const void *ia, const void *ib)
+{
+ return *(const int *) ia - *(const int *) ib;
+}
+
+void clear_callback(void *ia, void *ib)
+{
+ assert(*(int *) ia > *(int *) ib);
+ free(ia);
+}
+
+int main()
+{
+ srand(time(NULL));
+
+ printf("------------\n");
+ printf("Testing Tree\n");
+ printf("------------\n");
+
+ Tree tree;
+
+ printf("testing ini\n");
+ tree_ini(&tree);
+
+ int a = 0;
+ int b = 1;
+ int c = 2;
+ int d = 2;
+ int e = 3;
+
+ printf("testing add\n");
+ assert(tree_add(&tree, &a, &cmp_int, NULL) == &a);
+ assert(tree_add(&tree, &b, &cmp_int, NULL) == &b);
+ assert(tree_add(&tree, &c, &cmp_int, NULL) == &c);
+ assert(tree_add(&tree, &d, &cmp_int, NULL) == &c);
+
+ printf("testing get\n");
+ assert(tree_get(&tree, &a, &cmp_int, NULL) == &a);
+ assert(tree_get(&tree, &b, &cmp_int, NULL) == &b);
+ assert(tree_get(&tree, &c, &cmp_int, NULL) == &c);
+ assert(tree_get(&tree, &d, &cmp_int, NULL) == &c);
+ assert(tree_get(&tree, &e, &cmp_int, NULL) == NULL);
+
+ printf("testing del\n");
+ assert(tree_del(&tree, &a, &cmp_int, NULL) == &a);
+ assert(tree_get(&tree, &a, &cmp_int, NULL) == NULL);
+
+ printf("testing clr\n");
+ tree_clr(&tree, NULL, NULL, 0);
+ assert(tree_get(&tree, &b, &cmp_int, NULL) == NULL);
+
+ printf("testing order and speed with %d elements\n", (int) NUM_ELEMENTS);
+ for (int i = 0; i < NUM_ELEMENTS; i++) {
+ int *n = malloc(sizeof *n);
+ *n = rand();
+
+ if (tree_add(&tree, n, &cmp_int, NULL) != n)
+ free(n);
+ }
+
+ int last = -1;
+ tree_clr(&tree, &clear_callback, &last, TRAVERSION_INORDER);
+}
--- /dev/null
+#include <stdlib.h> // for malloc, free
+#include "bits/wrappers.h"
+#include "tree.h"
+
+static inline TreeNode **search(TreeNode **node, void *key, Comparator cmp)
+{
+ if (! *node)
+ return node;
+
+ int rel = cmp((*node)->dat, key);
+
+ if (rel == 0)
+ return node;
+ else if (rel > 0)
+ return search(&(*node)->lft, key, cmp);
+ else // (rel < 0)
+ return search(&(*node)->rgt, key, cmp);
+}
+
+static inline void traverse(TreeNode *node, Iterator func, void *arg, TreeTraversionOrder order, int delete)
+{
+ if (! node)
+ return;
+
+ if (func && order == TRAVERSION_PREORDER ) func(node->dat, arg);
+ traverse(node->lft, func, arg, order, delete);
+ if (func && order == TRAVERSION_INORDER ) func(node->dat, arg);
+ traverse(node->rgt, func, arg, order, delete);
+ if (func && order == TRAVERSION_POSTORDER) func(node->dat, arg);
+
+ if (delete)
+ free(node);
+}
+
+void tree_ini(Tree *tree)
+{
+ tree->rot = NULL;
+}
+
+WRAP_NODE_FUNCTIONS(Tree, tree_)
+
+TreeNode **tree_nfd(Tree *tree, void *key, Comparator cmp)
+{
+ return search(&tree->rot, key, cmp);
+}
+
+void tree_nmk(__attribute__((unused)) Tree *tree, TreeNode **node, void *dat)
+{
+ *node = malloc(sizeof **node);
+ (*node)->dat = dat;
+ (*node)->lft = (*node)->rgt = NULL;
+}
+
+void tree_nrm(__attribute__((unused)) Tree *tree, TreeNode **node)
+{
+ TreeNode *old = *node;
+ *node = old->lft;
+
+ if (old->rgt) {
+ TreeNode **rgt = node;
+
+ while (*rgt)
+ rgt = &(*rgt)->rgt;
+
+ *rgt = old->rgt;
+ }
+
+ free(old);
+}
+
+void tree_trv(Tree *tree, Iterator func, void *arg, TreeTraversionOrder order)
+{
+ traverse(tree->rot, func, arg, order, 0);
+}
+
+void tree_clr(Tree *tree, Iterator func, void *arg, TreeTraversionOrder order)
+{
+ traverse(tree->rot, func, arg, order, 1);
+ tree_ini(tree);
+}
--- /dev/null
+/*
+ Tree
+ ----
+
+ A binary search tree.
+
+ Note: This structure is included in <search.h> the C library as of POSIX.1-2001 and
+ POSIX.1-2008. However, the standard does not contain functions to delete the tree
+ and to traverse it with an additional argument. Glibc provides these functions,
+ but dragonstd conforms to the POSIX standard and does not use GNU extensions.
+ Therefore, this implementation is used to provide the missing features.
+*/
+
+#ifndef _DRAGONSTD_TREE_H_ // include guard
+#define _DRAGONSTD_TREE_H_
+
+#include "bits/callback.h" // for Iterator, Comparator
+
+typedef struct TreeNode {
+ /* public */
+ void *dat; // pointer to data
+ /* private */
+ struct TreeNode *lft; // left branch (data is "smaller")
+ struct TreeNode *rgt; // right branch (data is "bigger")
+} TreeNode;
+
+typedef struct {
+ /* private */
+ TreeNode *rot; // root node
+} Tree;
+
+typedef enum {
+ TRAVERSION_PREORDER,
+ TRAVERSION_INORDER,
+ TRAVERSION_POSTORDER,
+} TreeTraversionOrder;
+
+void tree_ini(Tree *tree);
+/*
+ Initializes the tree.
+
+ The tree should be uninitialized or empty before passed to this function.
+ This function should be called before any other function is called on the tree.
+*/
+
+void *tree_add(Tree *tree, void *dat, Comparator cmp, Transformer func);
+/*
+ Add an element to the tree.
+
+ If an equal element is already in the tree, return it and don't add anything.
+ Otherwise, return added element.
+*/
+
+void *tree_get(Tree *tree, void *key, Comparator cmp, Transformer func);
+/*
+ Get an element from the tree, or return NULL if none found.
+*/
+
+void *tree_del(Tree *tree, void *key, Comparator cmp, Transformer func);
+/*
+ Delete an element from the tree and return it, or NULL if none found.
+*/
+
+TreeNode **tree_nfd(Tree *tree, void *key, Comparator cmp);
+/*
+ Find the location of a node matching key.
+
+ This can be the location of an an existing node, or the location where a node matching
+ that key would need to be stored.
+*/
+
+void tree_nmk(Tree *tree, TreeNode **node, void *dat);
+/*
+ Create a node with dat as data and store it's pointer at the given location.
+*/
+
+void tree_nrm(Tree *tree, TreeNode **node);
+/*
+ Remove the node at the given location.
+*/
+
+void tree_trv(Tree *tree, Iterator func, void *arg, TreeTraversionOrder order);
+/*
+ Traverse the tree.
+ Calls func on every element, with the extra argument arg.
+*/
+
+void tree_clr(Tree *tree, Iterator func, void *arg, TreeTraversionOrder order);
+/*
+ Traverses the tree and deletes all elements.
+ Calls func on every element, with the extra argument arg.
+
+ The tree is empty afterwards.
+ If no callback is given, the traversion order is irrelevant.
+*/
+
+#endif // _DRAGONSTD_TREE_H_
projects / dragonstd.git / commitdiff