-# Prerequisites
-*.d
-
-# Object files
-*.o
-*.ko
-*.obj
-*.elf
-
-# Linker output
-*.ilk
-*.map
-*.exp
-
-# Precompiled Headers
-*.gch
-*.pch
-
-# Libraries
-*.lib
+CMakeLists.txt.user
+CMakeCache.txt
+CMakeFiles
+CMakeScripts
+Testing
+Makefile
+cmake_install.cmake
+install_manifest.txt
+compile_commands.json
+CTestTestfile.cmake
+_deps
*.a
-*.la
-*.lo
-
-# Shared objects (inc. Windows DLLs)
-*.dll
-*.so
-*.so.*
-*.dylib
-
-# Executables
-*.exe
-*.out
-*.app
-*.i*86
-*.x86_64
-*.hex
-
-# Debug files
-*.dSYM/
-*.su
-*.idb
-*.pdb
-
-# Kernel Module Compile Results
-*.mod*
-*.cmd
-.tmp_versions/
-modules.order
-Module.symvers
-Mkfile.old
-dkms.conf
--- /dev/null
+cmake_minimum_required(VERSION 3.14)
+project(Dragonstd)
+
+add_compile_options(
+ -Wall
+ -Wextra
+ -Werror
+)
+
+add_library(dragonstd
+ dragonstd/array.c
+ dragonstd/flag.c
+ dragonstd/map.c
+ dragonstd/list.c
+ dragonstd/queue.c
+ dragonstd/refcount.c
+ dragonstd/tree.c
+ dragonstd/bits/compare.c
+)
+
+target_link_libraries(dragonstd
+ pthread
+)
+
+target_include_directories(dragonstd
+ PUBLIC "${CMAKE_CURRENT_SOURCE_DIR}"
+)
+++ /dev/null
-#include <stdlib.h> // for malloc, realloc, free, qsort
-#include <string.h> // for memmove, memcpy, memcmp
-#include "array.h"
-#include "bits/callback.h" // for Comparator
-
-void array_ini(Array *array, size_t mbs, size_t ext)
-{
- array->mbs = mbs;
- array->ext = ext;
- array->siz = 0;
- array->cap = 0;
- array->ptr = NULL;
-}
-
-void array_rlc(Array *array)
-{
- array->ptr = realloc(array->ptr, array->cap * array->mbs);
-}
-
-void array_grw(Array *array, size_t n)
-{
- array->siz += n;
-
- if (array->siz > array->cap) {
- array->cap = array->siz + array->ext;
- array_rlc(array);
- }
-}
-
-void array_shr(Array *array, size_t n)
-{
- array->siz -= n;
-
- if (array->cap > array->siz) {
- array->cap = array->siz;
- array_rlc(array);
- }
-}
-
-void array_put(Array *array, const void *ptr, size_t n)
-{
- size_t oldsiz = array->siz;
- array_grw(array, 1);
-
- char *iptr = array->ptr + n * array->mbs;
- memmove(iptr + array->mbs, iptr, (oldsiz - n) * array->mbs);
- memcpy(iptr, ptr, array->mbs);
-}
-
-void array_apd(Array *array, const void *ptr)
-{
- size_t oldsiz = array->siz;
- array_grw(array, 1);
-
- memcpy(array->ptr + oldsiz * array->mbs, ptr, array->mbs);
-}
-
-ssize_t array_idx(Array *array, const void *ptr)
-{
- for (size_t i = 0; i < array->siz; i++)
- if (memcmp(array->ptr + i * array->mbs, ptr, array->mbs) == 0)
- return i;
-
- return -1;
-}
-
-void array_cpy(Array *array, void **ptr, size_t *n)
-{
- *n = array->siz;
- size_t size = array->siz * array->mbs;
- *ptr = malloc(size);
- memcpy(*ptr, array->ptr, size);
-}
-
-void array_cln(Array *dst, Array *src)
-{
- array_ini(dst, src->mbs, src->ext);
- array_cpy(src, &dst->ptr, &dst->siz);
- dst->cap = dst->siz;
-}
-
-void array_rcy(Array *array)
-{
- array->siz = 0;
-}
-
-void array_clr(Array *array)
-{
- if (array->ptr)
- free(array->ptr);
- array_ini(array, array->mbs, array->ext);
-}
-
-void array_srt(Array *array, void *cmp)
-{
- qsort(array->ptr, array->siz, array->mbs, cmp);
-}
-
-ssize_t array_fnd(Array *array, const void *ptr, size_t *idx, void *cmp)
-{
- size_t low, high, mid;
-
- low = 0;
- high = array->siz;
-
- while (low < high) {
- mid = (low + high) / 2;
-
- int rel = ((Comparator) cmp)(ptr, array->ptr + mid * array->mbs);
-
- if (rel == 0)
- return idx ? (*idx = mid) : mid;
- else if (rel < 0)
- high = mid;
- else // (rel > 0)
- low = mid + 1;
- }
-
- if (idx)
- *idx = low;
-
- return -1;
-}
-
-size_t array_ins(Array *array, const void *ptr, void *cmp)
-{
- size_t n;
-
- array_fnd(array, ptr, &n, cmp);
- array_put(array, ptr, n);
-
- return n;
-}
+++ /dev/null
-/*
- Array
- -----
-
- Data structure where all elements (members) have the same size and are
- located consecutively in memory.
-
-*/
-
-#ifndef _DRAGONSTD_ARRAY_H_ // include guard
-#define _DRAGONSTD_ARRAY_H_
-
-#include <stddef.h> // for size_t
-#include <sys/types.h> // for ssize_t
-#include "bits/compare.h" // for cmp_ref (not used in file)
-
-typedef struct {
- /* public */
- void *ptr; // memory
- size_t ext; // extra space
- /* private */
- 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);
-/*
- 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.
-
- 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 has a capacity of 0. Otherwise a memory leak will occur.
-*/
-
-void array_rlc(Array *array);
-/*
- Reallocates the array's memory to match it's capacity.
-
- This function should be called every time the capacity has changed.
-*/
-
-void array_grw(Array *array, size_t n);
-/*
- Grows the array by n bytes.
-
- This function increases the arrays size by n bytes. If this exceeds the capacity of
- the array, the capacity set to the size and the extra space ext is added to it.
-
- If the capacity is changed, the array is reallocated.
-
- If n is zero, the array's capacity may still grow by extra space if it exactly
- matches the current size.
-*/
-
-void array_shr(Array *array, size_t n);
-/*
- Shrinks the array by n bytes.
-
- This function decreases the arrays size by n bytes.
-
- If the array has additional capacity left after it has been shrunk, the capacity
- is set to the new size and the array is reallocated to fit the new capacity.
- For n > 0, this is always the case, for n = 0, this may be the case.
-
- Note that calling this function with n = 0 is useful to shrink the array's memory to
- exactly fit it's used size.
-*/
-
-void array_put(Array *array, const void *ptr, size_t n);
-/*
- Grows the array by 1 and inserts ptr at the index n.
-
- This function inserts the memory pointed to by ptr before the array member at
- index n, moving all elements from that index to the end of the array.
-
- After this operation, the inserted element will be _at_ the index n.
-
- The memory that ptr points to, which's size is assumed to be at least as big as the
- array's member size is copied into the arrays memory.
-
- n should be in the range from 0 to the array's size.
-*/
-
-void array_apd(Array *array, const void *ptr);
-/*
- Grows the array by 1 and appends ptr at the end of the array.
-
- This function's result is equivalent to calling array_put(array, ptr, array->siz),
- but it is slightly faster since it saves unnecessary calls.
-*/
-
-ssize_t array_idx(Array *array, const void *ptr);
-/*
- Returns the index of the first element that equals ptr, or none if no matches.
-
- Uses memcmp to compare the elements.
-*/
-
-void array_cpy(Array *array, void **ptr, size_t *n);
-/*
- Allocates a buffer big enough to fit the array's used size.
- Copies the array's contents into the allocated buffer.
- Returns the buffer in ptr and the size in n.
-
- Note that the returned size is the number of elements, not the number of bytes.
-*/
-
-void array_cln(Array *dst, Array *src);
-/*
- Clones the array src to the array dst.
-
- 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 size of dst and src (which might not equal the capacity of src).
-
- Since array_ini is called on dst, it should be uninitialized, empty or deleted.
-*/
-
-void array_rcy(Array *array);
-/*
- Recycles the array.
-
- This function sets the used size of the array to 0 but leaves the capacity unchanged.
- The array's memory is not free'd and the array can be reused.
-*/
-
-void array_clr(Array *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 is empty and can be reused.
-*/
-
-void array_srt(Array *array, void *cmp);
-/*
- Sorts the array using the quicksort algorithm.
-
- 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, void *cmp);
-/*
- Searches the sorted array for the element ptr.
- Returns the index of the element, or -1 if it wasn't found.
-
- If idx is not NULL, a pointer to the last searched index is saved to where it
- 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 same comparator is used.
-*/
-
-size_t array_ins(Array *array, const void *ptr, void *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 same comparator is used.
-*/
-
-#endif // _DRAGONSTD_ARRAY_H_
+++ /dev/null
-#ifndef _DRAGONSTD_CALLBACK_H_ // include guard
-#define _DRAGONSTD_CALLBACK_H_
-
-typedef void (*SingleCallback)(void *dat);
-typedef void (*Callback)(void *dat, void *arg);
-typedef void *(*Transformer)(void *dat);
-typedef int (*Comparator)(const void *dat, const void *key);
-
-#endif // _DRAGONSTD_CALLBACK_H_
+++ /dev/null
-#include "compare.h"
-
-int cmp_ref(const void *va, const void *vb)
-{
- return
- va < vb ? -1 :
- va > vb ? +1 :
- 0;
-}
+++ /dev/null
-#ifndef _DRAGONSTD_COMPARE_H_
-#define _DRAGONSTD_COMPARE_H_
-
-int cmp_ref(const void *pa, const void *pb);
-
-#endif // _DRAGONSTD_COMPARE_H_
+++ /dev/null
-#include "callback.h" // for Transformer, Callback
-
-#define WRAP_NODE_FUNCTIONS(Type, prefix) \
- bool prefix ## add(Type *self, void *key, void *dat, void *cmp, void *trans) \
- { \
- Type ## Node **node = prefix ## nfd(self, key, cmp); \
- \
- if (*node) \
- return false; \
- \
- prefix ## nmk(self, node, trans ? ((Transformer) trans)(dat) : dat); \
- return true; \
- } \
- \
- void *prefix ## get(Type *self, void *key, void *cmp, void *trans) \
- { \
- Type ## Node **node = prefix ## nfd(self, key, cmp); \
- \
- if (!*node) \
- return NULL; \
- \
- return trans ? ((Transformer) trans)((*node)->dat) : (*node)->dat; \
- } \
- \
- bool prefix ## del(Type *self, void *key, void *cmp, void *call, void *arg, void *trans) \
- { \
- Type ## Node **node = prefix ## nfd(self, key, cmp); \
- \
- if (!*node) \
- return false; \
- \
- if (call) \
- ((Callback) call)(trans ? ((Transformer) trans)((*node)->dat) : (*node)->dat, arg); \
- \
- prefix ## nrm(self, node); \
- return true; \
- }
--- /dev/null
+#include <stdlib.h> // for malloc, realloc, free, qsort
+#include <string.h> // for memmove, memcpy, memcmp
+#include "array.h"
+#include "bits/callback.h" // for Comparator
+
+void array_ini(Array *array, size_t mbs, size_t ext)
+{
+ array->mbs = mbs;
+ array->ext = ext;
+ array->siz = 0;
+ array->cap = 0;
+ array->ptr = NULL;
+}
+
+void array_rlc(Array *array)
+{
+ array->ptr = realloc(array->ptr, array->cap * array->mbs);
+}
+
+void array_grw(Array *array, size_t n)
+{
+ array->siz += n;
+
+ if (array->siz > array->cap) {
+ array->cap = array->siz + array->ext;
+ array_rlc(array);
+ }
+}
+
+void array_shr(Array *array, size_t n)
+{
+ array->siz -= n;
+
+ if (array->cap > array->siz) {
+ array->cap = array->siz;
+ array_rlc(array);
+ }
+}
+
+void array_put(Array *array, const void *ptr, size_t n)
+{
+ size_t oldsiz = array->siz;
+ array_grw(array, 1);
+
+ char *iptr = array->ptr + n * array->mbs;
+ memmove(iptr + array->mbs, iptr, (oldsiz - n) * array->mbs);
+ memcpy(iptr, ptr, array->mbs);
+}
+
+void array_apd(Array *array, const void *ptr)
+{
+ size_t oldsiz = array->siz;
+ array_grw(array, 1);
+
+ memcpy(array->ptr + oldsiz * array->mbs, ptr, array->mbs);
+}
+
+ssize_t array_idx(Array *array, const void *ptr)
+{
+ for (size_t i = 0; i < array->siz; i++)
+ if (memcmp(array->ptr + i * array->mbs, ptr, array->mbs) == 0)
+ return i;
+
+ return -1;
+}
+
+void array_cpy(Array *array, void **ptr, size_t *n)
+{
+ *n = array->siz;
+ size_t size = array->siz * array->mbs;
+ *ptr = malloc(size);
+ memcpy(*ptr, array->ptr, size);
+}
+
+void array_cln(Array *dst, Array *src)
+{
+ array_ini(dst, src->mbs, src->ext);
+ array_cpy(src, &dst->ptr, &dst->siz);
+ dst->cap = dst->siz;
+}
+
+void array_rcy(Array *array)
+{
+ array->siz = 0;
+}
+
+void array_clr(Array *array)
+{
+ if (array->ptr)
+ free(array->ptr);
+ array_ini(array, array->mbs, array->ext);
+}
+
+void array_srt(Array *array, void *cmp)
+{
+ qsort(array->ptr, array->siz, array->mbs, cmp);
+}
+
+ssize_t array_fnd(Array *array, const void *ptr, size_t *idx, void *cmp)
+{
+ size_t low, high, mid;
+
+ low = 0;
+ high = array->siz;
+
+ while (low < high) {
+ mid = (low + high) / 2;
+
+ int rel = ((Comparator) cmp)(ptr, array->ptr + mid * array->mbs);
+
+ if (rel == 0)
+ return idx ? (*idx = mid) : mid;
+ else if (rel < 0)
+ high = mid;
+ else // (rel > 0)
+ low = mid + 1;
+ }
+
+ if (idx)
+ *idx = low;
+
+ return -1;
+}
+
+size_t array_ins(Array *array, const void *ptr, void *cmp)
+{
+ size_t n;
+
+ array_fnd(array, ptr, &n, cmp);
+ array_put(array, ptr, n);
+
+ return n;
+}
--- /dev/null
+/*
+ Array
+ -----
+
+ Data structure where all elements (members) have the same size and are
+ located consecutively in memory.
+
+*/
+
+#ifndef _DRAGONSTD_ARRAY_H_ // include guard
+#define _DRAGONSTD_ARRAY_H_
+
+#include <stddef.h> // for size_t
+#include <sys/types.h> // for ssize_t
+#include "bits/compare.h" // for cmp_ref (not used in file)
+
+typedef struct {
+ /* public */
+ void *ptr; // memory
+ size_t ext; // extra space
+ /* private */
+ 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);
+/*
+ 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.
+
+ 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 has a capacity of 0. Otherwise a memory leak will occur.
+*/
+
+void array_rlc(Array *array);
+/*
+ Reallocates the array's memory to match it's capacity.
+
+ This function should be called every time the capacity has changed.
+*/
+
+void array_grw(Array *array, size_t n);
+/*
+ Grows the array by n bytes.
+
+ This function increases the arrays size by n bytes. If this exceeds the capacity of
+ the array, the capacity set to the size and the extra space ext is added to it.
+
+ If the capacity is changed, the array is reallocated.
+
+ If n is zero, the array's capacity may still grow by extra space if it exactly
+ matches the current size.
+*/
+
+void array_shr(Array *array, size_t n);
+/*
+ Shrinks the array by n bytes.
+
+ This function decreases the arrays size by n bytes.
+
+ If the array has additional capacity left after it has been shrunk, the capacity
+ is set to the new size and the array is reallocated to fit the new capacity.
+ For n > 0, this is always the case, for n = 0, this may be the case.
+
+ Note that calling this function with n = 0 is useful to shrink the array's memory to
+ exactly fit it's used size.
+*/
+
+void array_put(Array *array, const void *ptr, size_t n);
+/*
+ Grows the array by 1 and inserts ptr at the index n.
+
+ This function inserts the memory pointed to by ptr before the array member at
+ index n, moving all elements from that index to the end of the array.
+
+ After this operation, the inserted element will be _at_ the index n.
+
+ The memory that ptr points to, which's size is assumed to be at least as big as the
+ array's member size is copied into the arrays memory.
+
+ n should be in the range from 0 to the array's size.
+*/
+
+void array_apd(Array *array, const void *ptr);
+/*
+ Grows the array by 1 and appends ptr at the end of the array.
+
+ This function's result is equivalent to calling array_put(array, ptr, array->siz),
+ but it is slightly faster since it saves unnecessary calls.
+*/
+
+ssize_t array_idx(Array *array, const void *ptr);
+/*
+ Returns the index of the first element that equals ptr, or none if no matches.
+
+ Uses memcmp to compare the elements.
+*/
+
+void array_cpy(Array *array, void **ptr, size_t *n);
+/*
+ Allocates a buffer big enough to fit the array's used size.
+ Copies the array's contents into the allocated buffer.
+ Returns the buffer in ptr and the size in n.
+
+ Note that the returned size is the number of elements, not the number of bytes.
+*/
+
+void array_cln(Array *dst, Array *src);
+/*
+ Clones the array src to the array dst.
+
+ 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 size of dst and src (which might not equal the capacity of src).
+
+ Since array_ini is called on dst, it should be uninitialized, empty or deleted.
+*/
+
+void array_rcy(Array *array);
+/*
+ Recycles the array.
+
+ This function sets the used size of the array to 0 but leaves the capacity unchanged.
+ The array's memory is not free'd and the array can be reused.
+*/
+
+void array_clr(Array *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 is empty and can be reused.
+*/
+
+void array_srt(Array *array, void *cmp);
+/*
+ Sorts the array using the quicksort algorithm.
+
+ 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, void *cmp);
+/*
+ Searches the sorted array for the element ptr.
+ Returns the index of the element, or -1 if it wasn't found.
+
+ If idx is not NULL, a pointer to the last searched index is saved to where it
+ 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 same comparator is used.
+*/
+
+size_t array_ins(Array *array, const void *ptr, void *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 same comparator is used.
+*/
+
+#endif // _DRAGONSTD_ARRAY_H_
--- /dev/null
+#ifndef _DRAGONSTD_CALLBACK_H_ // include guard
+#define _DRAGONSTD_CALLBACK_H_
+
+typedef void (*SingleCallback)(void *dat);
+typedef void (*Callback)(void *dat, void *arg);
+typedef void *(*Transformer)(void *dat);
+typedef int (*Comparator)(const void *dat, const void *key);
+
+#endif // _DRAGONSTD_CALLBACK_H_
--- /dev/null
+#include "compare.h"
+
+int cmp_ref(const void *va, const void *vb)
+{
+ return
+ va < vb ? -1 :
+ va > vb ? +1 :
+ 0;
+}
--- /dev/null
+#ifndef _DRAGONSTD_COMPARE_H_
+#define _DRAGONSTD_COMPARE_H_
+
+int cmp_ref(const void *pa, const void *pb);
+
+#endif // _DRAGONSTD_COMPARE_H_
--- /dev/null
+#include "callback.h" // for Transformer, Callback
+
+#define WRAP_NODE_FUNCTIONS(Type, prefix) \
+ bool prefix ## add(Type *self, void *key, void *dat, void *cmp, void *trans) \
+ { \
+ Type ## Node **node = prefix ## nfd(self, key, cmp); \
+ \
+ if (*node) \
+ return false; \
+ \
+ prefix ## nmk(self, node, trans ? ((Transformer) trans)(dat) : dat); \
+ return true; \
+ } \
+ \
+ void *prefix ## get(Type *self, void *key, void *cmp, void *trans) \
+ { \
+ Type ## Node **node = prefix ## nfd(self, key, cmp); \
+ \
+ if (!*node) \
+ return NULL; \
+ \
+ return trans ? ((Transformer) trans)((*node)->dat) : (*node)->dat; \
+ } \
+ \
+ bool prefix ## del(Type *self, void *key, void *cmp, void *call, void *arg, void *trans) \
+ { \
+ Type ## Node **node = prefix ## nfd(self, key, cmp); \
+ \
+ if (!*node) \
+ return false; \
+ \
+ if (call) \
+ ((Callback) call)(trans ? ((Transformer) trans)((*node)->dat) : (*node)->dat, arg); \
+ \
+ prefix ## nrm(self, node); \
+ return true; \
+ }
--- /dev/null
+#include "flag.h"
+
+void flag_ini(Flag *flag)
+{
+ flag->set = false;
+ pthread_cond_init(&flag->cnd, NULL);
+ pthread_mutex_init(&flag->mtx, NULL);
+ list_ini(&flag->cvs);
+ flag_sub(flag, &flag->cnd);
+}
+
+void flag_dst(Flag *flag)
+{
+ pthread_cond_destroy(&flag->cnd);
+ pthread_mutex_destroy(&flag->mtx);
+ list_clr(&flag->cvs, NULL, NULL, NULL);
+}
+
+void flag_sub(Flag *flag, pthread_cond_t *cnd)
+{
+ pthread_mutex_lock(&flag->mtx);
+ list_add(&flag->cvs, cnd, cnd, &cmp_ref, NULL);
+ pthread_mutex_unlock(&flag->mtx);
+}
+
+void flag_uns(Flag *flag, pthread_cond_t *cnd)
+{
+ pthread_mutex_lock(&flag->mtx);
+ list_del(&flag->cvs, cnd, &cmp_ref, NULL, NULL, NULL);
+ pthread_mutex_unlock(&flag->mtx);
+}
+
+void flag_set(Flag *flag)
+{
+ pthread_mutex_lock(&flag->mtx);
+ flag->set = true;
+
+ LIST_ITERATE(&flag->cvs, node)
+ pthread_cond_broadcast(node->dat);
+
+ pthread_mutex_unlock(&flag->mtx);
+}
+
+void flag_slp(Flag *flag)
+{
+ pthread_mutex_lock(&flag->mtx);
+ if (!flag->set)
+ pthread_cond_wait(&flag->cnd, &flag->mtx);
+ pthread_mutex_unlock(&flag->mtx);
+}
--- /dev/null
+/*
+ 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 <pthread.h> // for pthread_mutex_t, pthread_cond_t
+#include <stdatomic.h> // for atomic_bool
+#include <stdbool.h> // for bool
+#include "list.h" // for List
+
+typedef struct {
+ /* protected */
+ atomic_bool set; // whether the flag is set
+ /* private */
+ pthread_cond_t cnd; // main condition variable
+ pthread_mutex_t mtx; // mutex to protect the main condition variable
+ List cvs; // condition variables
+} 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_sub(Flag *flag, pthread_cond_t *cnd);
+/*
+ [Thread Safe]
+ Subscribe condition variable cnd to flag.
+
+ The condition variable will be triggered when the flag is set.
+*/
+
+void flag_uns(Flag *flag, pthread_cond_t *cnd);
+/*
+ [Thread Safe]
+ Unsubscribe condition variable cnd from flag.
+
+ The condition variable will no longer be triggered when the flag is set.
+*/
+
+void flag_set(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 // _DRAGONSTD_FLAG_H_
--- /dev/null
+#include <stdlib.h> // for malloc, free
+#include <string.h> // for strcmp
+#include "bits/callback.h" // for Callback, Comparator, Transformer
+#include "bits/wrappers.h"
+#include "list.h"
+
+#define ITER_REFS node = &list->fst; *node != NULL; node = &(*node)->nxt
+
+void list_ini(List *list)
+{
+ list->fst = NULL;
+ list->end = &list->fst;
+}
+
+WRAP_NODE_FUNCTIONS(List, list_)
+
+void list_apd(List *list, void *dat)
+{
+ list_nmk(list, list->end, dat);
+}
+
+void list_ppd(List *list, void *dat)
+{
+ ListNode *fst = list->fst;
+ list_nmk(list, &list->fst, dat);
+ list->fst->nxt = fst;
+}
+
+ListNode **list_nfd(List *list, void *key, void *cmp)
+{
+ ListNode **node;
+
+ for (ITER_REFS)
+ if (((Comparator) cmp)((*node)->dat, key) == 0)
+ return node;
+
+ return node;
+}
+
+void list_nmk(List *list, ListNode **node, void *dat)
+{
+ *node = malloc(sizeof **node);
+ (*node)->dat = dat;
+ (*node)->nxt = NULL;
+
+ if (list->end == node)
+ list->end = &(*node)->nxt;
+}
+
+void list_nrm(List *list, ListNode **node)
+{
+ ListNode *old = *node;
+ *node = old->nxt;
+
+ if (list->end == &old->nxt)
+ list->end = node;
+
+ free(old);
+}
+
+void list_itr(List *list, void *iter, void *arg, void *trans)
+{
+ LIST_ITERATE(list, node)
+ ((Callback) iter)(trans ? ((Transformer) trans)(node->dat) : node->dat, arg);
+}
+
+void list_clr(List *list, void *iter, void *arg, void *trans)
+{
+ for (ListNode *node = list->fst; node != NULL;) {
+ ListNode *next = node->nxt;
+
+ if (iter)
+ ((Callback) iter)(trans ? ((Transformer) trans)(node->dat) : node->dat, arg);
+
+ free(node);
+ node = next;
+ }
+
+ list_ini(list);
+}
--- /dev/null
+/*
+ List
+ ----
+
+ A linked list.
+*/
+
+#ifndef _DRAGONSTD_LIST_H_ // include guard
+#define _DRAGONSTD_LIST_H_
+
+#include <stdbool.h> // for bool
+#include "bits/compare.h" // for cmp_ref (not used in file)
+
+#define LIST_ITERATE(list, node) for (ListNode *node = (list)->fst; node != NULL; node = node->nxt)
+
+typedef struct ListNode {
+ /* public */
+ void *dat; // pointer to data
+ /* private */
+ struct ListNode *nxt; // next node
+} ListNode;
+
+typedef struct {
+ /* private */
+ ListNode *fst; // first element
+ ListNode **end; // where address of next node will be stored
+} List;
+
+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.
+*/
+
+bool list_add(List *list, void *key, void *dat, void *cmp, void *trans);
+/*
+ Add an element to the list.
+
+ If an equal element is already in the list, don't add anything.
+ Return whether an element has been added.
+*/
+
+void *list_get(List *list, void *key, void *cmp, void *trans);
+/*
+ Get an element from the list.
+
+ The first matching element is returned, or NULL if none found.
+*/
+
+bool list_del(List *list, void *key, void *cmp, void *call, void *arg, void *trans);
+/*
+ Delete an element from the list if it is found.
+ Return whether an element has been deleted.
+
+ The first matching element is deleted.
+*/
+
+void list_apd(List *list, void *dat);
+/*
+ Append an element at the end of the list.
+*/
+
+void list_ppd(List *list, void *dat);
+/*
+ Prepend an element at the start of the list.
+*/
+
+ListNode **list_nfd(List *list, void *key, void *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, void *iter, void *arg, void *trans);
+/*
+ Iterate over the list.
+ Calls iter on every element, with the extra argument arg.
+
+ Note: the LIST_ITERATE macro can be used to do this without function calls.
+*/
+
+void list_clr(List *list, void *iter, void *arg, void *trans);
+/*
+ Iterates over the list and deletes all elements.
+ Calls iter on every element, with the extra argument arg.
+
+ The list is empty afterwards.
+*/
+
+#endif // _DRAGONSTD_LIST_H_
--- /dev/null
+#include "bits/callback.h" // for Transformer
+#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, void *iter, void *arg, void *trans, TreeTraversionOrder order)
+{
+ pthread_rwlock_wrlock(&map->clk);
+ map->cnl = true;
+
+ pthread_rwlock_wrlock(&map->tlk);
+ pthread_rwlock_unlock(&map->clk);
+
+ tree_clr(&map->tre, iter, arg, trans, order);
+
+ pthread_rwlock_unlock(&map->tlk);
+}
+
+bool map_add(Map *map, void *key, void *dat, void *cmp, void *trans)
+{
+ if (!get_lock(map, true))
+ return false;
+
+ bool ret = tree_add(&map->tre, key, dat, cmp, trans);
+ pthread_rwlock_unlock(&map->tlk);
+ return ret;
+}
+
+void *map_get(Map *map, void *key, void *cmp, void *trans)
+{
+ if (!get_lock(map, false))
+ return NULL;
+
+ void *ret = tree_get(&map->tre, key, cmp, trans);
+ pthread_rwlock_unlock(&map->tlk);
+ return ret;
+}
+
+bool map_del(Map *map, void *key, void *cmp, void *call, void *arg, void *trans)
+{
+ if (!get_lock(map, true))
+ return false;
+
+ bool ret = tree_del(&map->tre, key, cmp, call, arg, trans);
+ pthread_rwlock_unlock(&map->tlk);
+ return ret;
+}
+
+void map_trv(Map *map, void *iter, void *arg, void *trans, TreeTraversionOrder order)
+{
+ if (!get_lock(map, false))
+ return;
+
+ tree_trv(&map->tre, iter, arg, trans, order);
+ pthread_rwlock_unlock(&map->tlk);
+}
--- /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 "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, void *iter, void *arg, void *trans, 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.
+*/
+
+bool map_add(Map *map, void *key, void *dat, void *cmp, void *trans);
+/*
+ [Thread Safe]
+ Add an element to the map.
+
+ If an equal element is already in the map, don't add anything.
+ Return whether an element has been added.
+*/
+
+void *map_get(Map *map, void *key, void *cmp, void *trans);
+/*
+ [Thread Safe]
+ Get an element from the map, or return NULL if none found.
+*/
+
+bool map_del(Map *map, void *key, void *cmp, void *call, void *arg, void *trans);
+/*
+ [Thread Safe]
+ Delete an element from the map if it is found.
+ Return whether an element has been deleted.
+*/
+
+void map_trv(Map *map, void *iter, void *arg, void *trans, TreeTraversionOrder order);
+/*
+ [Thread Safe]
+ Traverse the map.
+ Calls iter on every element, with the extra argument arg.
+*/
+
+
+#endif
--- /dev/null
+#include <sched.h> // for sched_yield
+#include "bits/callback.h" // for Transformer
+#include "queue.h"
+
+void queue_ini(Queue *queue)
+{
+ list_ini(&queue->lst);
+ queue->cnl = queue->fin = 0;
+ pthread_cond_init(&queue->cnd, NULL);
+ pthread_mutex_init(&queue->mtx, NULL);
+}
+
+void queue_dst(Queue *queue)
+{
+ pthread_cond_destroy(&queue->cnd);
+ pthread_mutex_destroy(&queue->mtx);
+}
+
+void queue_clr(Queue *queue, void *iter, void *arg, void *trans)
+{
+ list_clr(&queue->lst, iter, arg, trans);
+}
+
+#define ENQUEUE(queue_fun, list_fun) \
+ bool queue_fun(Queue *queue, void *dat) \
+ { \
+ bool success = false; \
+ \
+ pthread_mutex_lock(&queue->mtx); \
+ if (!queue->fin) { \
+ success = true; \
+ list_fun(&queue->lst, dat); \
+ pthread_cond_signal(&queue->cnd); \
+ } \
+ pthread_mutex_unlock(&queue->mtx); \
+ \
+ return success; \
+ }
+
+ENQUEUE(queue_enq, list_apd)
+ENQUEUE(queue_ppd, list_ppd)
+
+#undef ENQUEUE
+
+void *queue_deq(Queue *queue, void *trans)
+{
+ void *dat = NULL;
+
+ 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 (trans)
+ dat = ((Transformer) trans)(dat);
+ } else {
+ pthread_cond_wait(&queue->cnd, &queue->mtx);
+ }
+ }
+ pthread_mutex_unlock(&queue->mtx);
+
+ return dat;
+}
+
+void queue_cnl(Queue *queue)
+{
+ pthread_mutex_lock(&queue->mtx);
+ queue->cnl = 1;
+ pthread_cond_broadcast(&queue->cnd);
+ pthread_mutex_unlock(&queue->mtx);
+}
+
+void queue_fin(Queue *queue)
+{
+ pthread_mutex_lock(&queue->mtx);
+ queue->fin = 1;
+ pthread_mutex_unlock(&queue->mtx);
+
+ for (;;) {
+ pthread_mutex_lock(&queue->mtx);
+ ListNode *node = queue->lst.fst;
+ pthread_mutex_unlock(&queue->mtx);
+
+ if (node)
+ sched_yield();
+ else
+ break;
+ }
+}
--- /dev/null
+/*
+ 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> // for pthread_cond_t, pthread_mutex_t
+#include <stdbool.h> // for bool
+#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;
+
+void queue_ini(Queue *queue);
+/*
+ Initializes the queue.
+
+ The queue should be uninitialized or deleted when passed to this function.
+*/
+
+void queue_dst(Queue *queue);
+/*
+ Destroy 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, void *iter, void *arg, void *trans);
+/*
+ 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.
+*/
+
+bool queue_ppd(Queue *queue, void *dat);
+/*
+ [Thread Safe]
+ Enqueues an element at the front 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, void *trans);
+/*
+ [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 // _DRAGONSTD_QUEUE_H_
--- /dev/null
+#include "bits/callback.h" // for SingleCallback
+#include "refcount.h"
+
+void refcount_ini(Refcount *refcount, void *obj, void *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(Refcount *refcount)
+{
+ pthread_mutex_lock(&refcount->mtx);
+ refcount->cnt++;
+ pthread_mutex_unlock(&refcount->mtx);
+ return refcount;
+}
+
+void *refcount_grb(Refcount *refcount)
+{
+ return refcount_obj(refcount_inc(refcount));
+}
+
+void refcount_drp(Refcount *refcount)
+{
+ pthread_mutex_lock(&refcount->mtx);
+ unsigned short count = --refcount->cnt;
+ pthread_mutex_unlock(&refcount->mtx);
+
+ if (!count)
+ ((SingleCallback) refcount->del)(refcount->obj);
+}
+
+void *refcount_obj(Refcount *refcount)
+{
+ return refcount->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
+
+typedef struct {
+ /* private */
+ void *obj;
+ void *del;
+ unsigned short cnt; // counter
+ pthread_mutex_t mtx; // lock to protect count
+} Refcount;
+
+void refcount_ini(Refcount *refcount, void *obj, void *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(Refcount *refcount);
+/*
+ [Thread Safe]
+ Grab a reference to the refcount.
+
+ Returns the refcount.
+*/
+
+void *refcount_grb(Refcount *rc);
+/*
+ [Thread Safe]
+ Does the same as refcount_inc, except it returns the referenced object instead of the
+ refcount.
+*/
+
+void refcount_drp(Refcount *refcount);
+/*
+ [Thread Safe]
+ Drop a reference to the object.
+
+ May delete the object using the del function if the counter gets down to zero.
+*/
+
+void *refcount_obj(Refcount *refcount);
+/*
+ [Thread Safe]
+ Return referenced object.
+*/
+
+#endif // _DRAGONSTD_REFCOUNT_H_
--- /dev/null
+test_array
+test_list
+test_tree
+test_queue
+test_map
+test_flag
+test_refcount_map
+!Makefile
--- /dev/null
+CC=cc -g -Wall -Wextra -Werror -fmax-errors=1
+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_%: test_%.c ../*.h ../*.c ../bits/*.h ../bits/*.c
+ $(CC) $< ../*.c ../bits/*.c -o $@ -lpthread
+
+clean:
+ rm -rf test_array test_list test_tree test_queue test_flag test_refcount_map
--- /dev/null
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <time.h>
+#include "../array.h"
+
+int cmp_int(const int *pa, const int *pb)
+{
+ return *pa - *pb;
+}
+
+void assert_in_order(Array *arr)
+{
+ for (size_t i = 1; i < arr->siz; i++)
+ assert(((int *) arr->ptr)[i - 1] <= ((int *) arr->ptr)[i]);
+}
+
+void dump(Array *arr)
+{
+ for (size_t i = 0; i < arr->siz; i++) {
+ printf("%d", ((int *) arr->ptr)[i]);
+
+ if (i != arr->siz - 1)
+ printf(",");
+ }
+}
+
+int main()
+{
+ printf("-------------\n");
+ printf("Testing Array\n");
+ printf("-------------\n");
+
+ int i;
+ Array arr, arr2;
+ srand(time(NULL));
+
+ printf("testing ini\n");
+ array_ini(&arr, sizeof(int), 0);
+
+ printf("testing add\n");
+ i = 1; array_apd(&arr, &i);
+ i = 3; array_apd(&arr, &i);
+ i = 4; array_apd(&arr, &i);
+
+ printf("testing put\n");
+ i = 2; array_put(&arr, &i, 1);
+ i = 5; array_put(&arr, &i, arr.siz);
+
+ printf("testing siz: exp: 5 got: %zu\n", arr.siz);
+ assert(arr.siz == 5);
+
+ printf("testing cap: exp: 5 got: %zu\n", arr.cap);
+ assert(arr.cap == 5);
+
+ printf("testing contents: exp: 1,2,3,4,5 got: "); dump(&arr); printf("\n");
+ for (size_t j = 0; j < arr.siz; j++)
+ assert((size_t) ((int *) arr.ptr)[j] == j + 1);
+
+ printf("testing cln\n");
+ array_cln(&arr2, &arr);
+
+ printf("testing equality: exp: "); dump(&arr); printf(" got: "); dump(&arr2);
+ printf("\n");
+
+ for (size_t j = 0; j < arr.siz; j++)
+ assert(((int *) arr.ptr)[j] == ((int *) arr2.ptr)[j]);
+
+ printf("testing clr\n");
+ array_clr(&arr);
+ array_clr(&arr2);
+
+ printf("testing ini after clr\n");
+ array_ini(&arr, sizeof(int), 5);
+
+ printf("testing cap: exp: 0 got: %zu\n", arr.cap);
+ assert(arr.cap == 0);
+
+ printf("testing overallocation\n");
+ i = 50; array_apd(&arr, &i);
+
+ printf("testing cap: exp: 0 got: %zu\n", arr.cap);
+ assert(arr.siz == 1);
+
+ printf("testing cap: exp: 6 got: %zu\n", arr.cap);
+ assert(arr.cap == 6);
+
+ for (int j = 0; j < 7; j++) {
+ i = rand() % 100; array_apd(&arr, &i);
+ }
+
+ printf("testing siz: exp: 8 got: %zu\n", arr.cap);
+ assert(arr.siz == 8);
+
+ printf("testing cap: exp: 12 got: %zu\n", arr.cap);
+ assert(arr.cap == 12);
+
+ printf("testing grw\n");
+ array_grw(&arr, 5);
+
+ printf("testing siz: exp: 13 got: %zu\n", arr.cap);
+ assert(arr.siz == 13);
+
+ printf("testing cap: exp: 18 got: %zu\n", arr.cap);
+ assert(arr.cap == 18);
+
+ printf("testing shr\n");
+ array_shr(&arr, 5);
+
+ printf("testing siz: exp: 8 got: %zu\n", arr.cap);
+ assert(arr.siz == 8);
+
+ printf("testing cap: exp: 8 got: %zu\n", arr.cap);
+ assert(arr.cap == 8);
+
+ printf("testing srt\n");
+ array_srt(&arr, &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, &cmp_int);
+
+ printf("testing fnd at index %zu: exp: >=0 got: %ld\n", j, s);
+ assert(s >= 0);
+
+ int k = ((int *) arr.ptr)[s];
+
+ printf("testing fnd at index %zu: exp: %d got: %d\n", j, i, k);
+ assert(k == i);
+ }
+
+ printf("testing ins\n");
+ for (int j = 0; j < 10; j++) {
+ i = rand() % 100; array_ins(&arr, &i, &cmp_int);
+ }
+
+ printf("testing order: exp: (sorted) got: "); dump(&arr); printf("\n");
+ assert_in_order(&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 int *ia, const int *ib)
+{
+ return *ia - *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, &a, &cmp_int, NULL));
+ assert(list_add(&list, &b, &b, &cmp_int, NULL));
+ assert(list_add(&list, &c, &c, &cmp_int, NULL));
+ assert(!list_add(&list, &d, &d, &cmp_int, NULL));
+
+ 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, NULL, NULL));
+ assert(list_get(&list, &a, &cmp_int, NULL) == NULL);
+
+ printf("testing clr\n");
+ list_clr(&list, NULL, 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_dst(&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;
+
+int rand_id()
+{
+ return rand() % 1000;
+}
+
+void delete_obj(DataObject *obj)
+{
+ refcount_dst(&obj->rc);
+ free(obj);
+}
+
+int cmp_obj(const Refcount *rc, const int *id)
+{
+ return ((DataObject *) rc->obj)->id - *id;
+}
+
+static void *thread_create(unsigned int *result)
+{
+ while (!cancel) {
+ DataObject *obj = malloc(sizeof *obj);
+ obj->id = rand_id();
+
+ refcount_ini(&obj->rc, obj, &delete_obj);
+
+ if (map_add(&map, &obj->id, &obj->rc, &cmp_obj, &refcount_inc))
+ (*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, &cmp_obj, &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, &cmp_obj, &refcount_drp, NULL, NULL))
+ (*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(1);
+
+ 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, &refcount_drp, NULL, NULL, 0);
+ map_dst(&map);
+
+ printf("Time: 1 second\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 int *ia, const int *ib)
+{
+ return *ia - *ib;
+}
+
+void clear_callback(int *ia, int *ib)
+{
+ assert(*ia >= *ib);
+ *ib = *ia;
+ 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, &a, &cmp_int, NULL));
+ assert(tree_add(&tree, &b, &b, &cmp_int, NULL));
+ assert(tree_add(&tree, &c, &c, &cmp_int, NULL));
+ assert(!tree_add(&tree, &d, &d, &cmp_int, NULL));
+
+ 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, NULL, NULL));
+ assert(tree_get(&tree, &a, &cmp_int, NULL) == NULL);
+
+ printf("testing clr\n");
+ tree_clr(&tree, NULL, 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, n, &cmp_int, NULL))
+ free(n);
+ }
+
+ int last = -1;
+ tree_clr(&tree, &clear_callback, &last, NULL, TRAVERSION_INORDER);
+}
--- /dev/null
+#include <stdlib.h> // for malloc, free
+#include "bits/callback.h" // for Callback, Comparator, Transformer
+#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, Callback iter, void *arg, Transformer trans, TreeTraversionOrder order, int delete)
+{
+ if (!node)
+ return;
+
+ if (iter && order == TRAVERSION_PREORDER ) iter(trans ? trans(node->dat) : node->dat, arg);
+ traverse(node->lft, iter, arg, trans, order, delete);
+ if (iter && order == TRAVERSION_INORDER ) iter(trans ? trans(node->dat) : node->dat, arg);
+ traverse(node->rgt, iter, arg, trans, order, delete);
+ if (iter && order == TRAVERSION_POSTORDER) iter(trans ? trans(node->dat) : 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, void *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, void *iter, void *arg, void *trans, TreeTraversionOrder order)
+{
+ traverse(tree->rot, iter, arg, trans, order, 0);
+}
+
+void tree_clr(Tree *tree, void *iter, void *arg, void *trans, TreeTraversionOrder order)
+{
+ traverse(tree->rot, iter, arg, trans, 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 <stdbool.h> // for bool
+#include "bits/compare.h" // for cmp_ref (not used in file)
+
+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.
+*/
+
+bool tree_add(Tree *tree, void *key, void *dat, void *cmp, void *trans);
+/*
+ Add an element to the tree.
+
+ If an equal element is already in the tree, don't add anything.
+ Return whether an element has been added.
+*/
+
+void *tree_get(Tree *tree, void *key, void *cmp, void *trans);
+/*
+ Get an element from the tree, or return NULL if none found.
+*/
+
+bool tree_del(Tree *tree, void *key, void *cmp, void *call, void *arg, void *trans);
+/*
+ Delete an element from the tree if it is found.
+ Return whether an element has been deleted.
+*/
+
+TreeNode **tree_nfd(Tree *tree, void *key, void *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, void *iter, void *arg, void *trans, TreeTraversionOrder order);
+/*
+ Traverse the tree.
+ Calls iter on every element, with the extra argument arg.
+*/
+
+void tree_clr(Tree *tree, void *iter, void *arg, void *trans, TreeTraversionOrder order);
+/*
+ Traverses the tree and deletes all elements.
+ Calls iter 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_
+++ /dev/null
-#include "flag.h"
-
-void flag_ini(Flag *flag)
-{
- flag->set = false;
- pthread_cond_init(&flag->cnd, NULL);
- pthread_mutex_init(&flag->mtx, NULL);
- list_ini(&flag->cvs);
- flag_sub(flag, &flag->cnd);
-}
-
-void flag_dst(Flag *flag)
-{
- pthread_cond_destroy(&flag->cnd);
- pthread_mutex_destroy(&flag->mtx);
- list_clr(&flag->cvs, NULL, NULL, NULL);
-}
-
-void flag_sub(Flag *flag, pthread_cond_t *cnd)
-{
- pthread_mutex_lock(&flag->mtx);
- list_add(&flag->cvs, cnd, cnd, &cmp_ref, NULL);
- pthread_mutex_unlock(&flag->mtx);
-}
-
-void flag_uns(Flag *flag, pthread_cond_t *cnd)
-{
- pthread_mutex_lock(&flag->mtx);
- list_del(&flag->cvs, cnd, &cmp_ref, NULL, NULL, NULL);
- pthread_mutex_unlock(&flag->mtx);
-}
-
-void flag_set(Flag *flag)
-{
- pthread_mutex_lock(&flag->mtx);
- flag->set = true;
-
- LIST_ITERATE(&flag->cvs, node)
- pthread_cond_broadcast(node->dat);
-
- pthread_mutex_unlock(&flag->mtx);
-}
-
-void flag_slp(Flag *flag)
-{
- pthread_mutex_lock(&flag->mtx);
- if (!flag->set)
- pthread_cond_wait(&flag->cnd, &flag->mtx);
- pthread_mutex_unlock(&flag->mtx);
-}
+++ /dev/null
-/*
- 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 <pthread.h> // for pthread_mutex_t, pthread_cond_t
-#include <stdatomic.h> // for atomic_bool
-#include <stdbool.h> // for bool
-#include "list.h" // for List
-
-typedef struct {
- /* protected */
- atomic_bool set; // whether the flag is set
- /* private */
- pthread_cond_t cnd; // main condition variable
- pthread_mutex_t mtx; // mutex to protect the main condition variable
- List cvs; // condition variables
-} 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_sub(Flag *flag, pthread_cond_t *cnd);
-/*
- [Thread Safe]
- Subscribe condition variable cnd to flag.
-
- The condition variable will be triggered when the flag is set.
-*/
-
-void flag_uns(Flag *flag, pthread_cond_t *cnd);
-/*
- [Thread Safe]
- Unsubscribe condition variable cnd from flag.
-
- The condition variable will no longer be triggered when the flag is set.
-*/
-
-void flag_set(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 // _DRAGONSTD_FLAG_H_
+++ /dev/null
-#include <stdlib.h> // for malloc, free
-#include <string.h> // for strcmp
-#include "bits/callback.h" // for Callback, Comparator, Transformer
-#include "bits/wrappers.h"
-#include "list.h"
-
-#define ITER_REFS node = &list->fst; *node != NULL; node = &(*node)->nxt
-
-void list_ini(List *list)
-{
- list->fst = NULL;
- list->end = &list->fst;
-}
-
-WRAP_NODE_FUNCTIONS(List, list_)
-
-void list_apd(List *list, void *dat)
-{
- list_nmk(list, list->end, dat);
-}
-
-void list_ppd(List *list, void *dat)
-{
- ListNode *fst = list->fst;
- list_nmk(list, &list->fst, dat);
- list->fst->nxt = fst;
-}
-
-ListNode **list_nfd(List *list, void *key, void *cmp)
-{
- ListNode **node;
-
- for (ITER_REFS)
- if (((Comparator) cmp)((*node)->dat, key) == 0)
- return node;
-
- return node;
-}
-
-void list_nmk(List *list, ListNode **node, void *dat)
-{
- *node = malloc(sizeof **node);
- (*node)->dat = dat;
- (*node)->nxt = NULL;
-
- if (list->end == node)
- list->end = &(*node)->nxt;
-}
-
-void list_nrm(List *list, ListNode **node)
-{
- ListNode *old = *node;
- *node = old->nxt;
-
- if (list->end == &old->nxt)
- list->end = node;
-
- free(old);
-}
-
-void list_itr(List *list, void *iter, void *arg, void *trans)
-{
- LIST_ITERATE(list, node)
- ((Callback) iter)(trans ? ((Transformer) trans)(node->dat) : node->dat, arg);
-}
-
-void list_clr(List *list, void *iter, void *arg, void *trans)
-{
- for (ListNode *node = list->fst; node != NULL;) {
- ListNode *next = node->nxt;
-
- if (iter)
- ((Callback) iter)(trans ? ((Transformer) trans)(node->dat) : node->dat, arg);
-
- free(node);
- node = next;
- }
-
- list_ini(list);
-}
+++ /dev/null
-/*
- List
- ----
-
- A linked list.
-*/
-
-#ifndef _DRAGONSTD_LIST_H_ // include guard
-#define _DRAGONSTD_LIST_H_
-
-#include <stdbool.h> // for bool
-#include "bits/compare.h" // for cmp_ref (not used in file)
-
-#define LIST_ITERATE(list, node) for (ListNode *node = (list)->fst; node != NULL; node = node->nxt)
-
-typedef struct ListNode {
- /* public */
- void *dat; // pointer to data
- /* private */
- struct ListNode *nxt; // next node
-} ListNode;
-
-typedef struct {
- /* private */
- ListNode *fst; // first element
- ListNode **end; // where address of next node will be stored
-} List;
-
-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.
-*/
-
-bool list_add(List *list, void *key, void *dat, void *cmp, void *trans);
-/*
- Add an element to the list.
-
- If an equal element is already in the list, don't add anything.
- Return whether an element has been added.
-*/
-
-void *list_get(List *list, void *key, void *cmp, void *trans);
-/*
- Get an element from the list.
-
- The first matching element is returned, or NULL if none found.
-*/
-
-bool list_del(List *list, void *key, void *cmp, void *call, void *arg, void *trans);
-/*
- Delete an element from the list if it is found.
- Return whether an element has been deleted.
-
- The first matching element is deleted.
-*/
-
-void list_apd(List *list, void *dat);
-/*
- Append an element at the end of the list.
-*/
-
-void list_ppd(List *list, void *dat);
-/*
- Prepend an element at the start of the list.
-*/
-
-ListNode **list_nfd(List *list, void *key, void *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, void *iter, void *arg, void *trans);
-/*
- Iterate over the list.
- Calls iter on every element, with the extra argument arg.
-
- Note: the LIST_ITERATE macro can be used to do this without function calls.
-*/
-
-void list_clr(List *list, void *iter, void *arg, void *trans);
-/*
- Iterates over the list and deletes all elements.
- Calls iter on every element, with the extra argument arg.
-
- The list is empty afterwards.
-*/
-
-#endif // _DRAGONSTD_LIST_H_
+++ /dev/null
-#include "bits/callback.h" // for Transformer
-#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, void *iter, void *arg, void *trans, TreeTraversionOrder order)
-{
- pthread_rwlock_wrlock(&map->clk);
- map->cnl = true;
-
- pthread_rwlock_wrlock(&map->tlk);
- pthread_rwlock_unlock(&map->clk);
-
- tree_clr(&map->tre, iter, arg, trans, order);
-
- pthread_rwlock_unlock(&map->tlk);
-}
-
-bool map_add(Map *map, void *key, void *dat, void *cmp, void *trans)
-{
- if (!get_lock(map, true))
- return false;
-
- bool ret = tree_add(&map->tre, key, dat, cmp, trans);
- pthread_rwlock_unlock(&map->tlk);
- return ret;
-}
-
-void *map_get(Map *map, void *key, void *cmp, void *trans)
-{
- if (!get_lock(map, false))
- return NULL;
-
- void *ret = tree_get(&map->tre, key, cmp, trans);
- pthread_rwlock_unlock(&map->tlk);
- return ret;
-}
-
-bool map_del(Map *map, void *key, void *cmp, void *call, void *arg, void *trans)
-{
- if (!get_lock(map, true))
- return false;
-
- bool ret = tree_del(&map->tre, key, cmp, call, arg, trans);
- pthread_rwlock_unlock(&map->tlk);
- return ret;
-}
-
-void map_trv(Map *map, void *iter, void *arg, void *trans, TreeTraversionOrder order)
-{
- if (!get_lock(map, false))
- return;
-
- tree_trv(&map->tre, iter, arg, trans, order);
- pthread_rwlock_unlock(&map->tlk);
-}
+++ /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 "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, void *iter, void *arg, void *trans, 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.
-*/
-
-bool map_add(Map *map, void *key, void *dat, void *cmp, void *trans);
-/*
- [Thread Safe]
- Add an element to the map.
-
- If an equal element is already in the map, don't add anything.
- Return whether an element has been added.
-*/
-
-void *map_get(Map *map, void *key, void *cmp, void *trans);
-/*
- [Thread Safe]
- Get an element from the map, or return NULL if none found.
-*/
-
-bool map_del(Map *map, void *key, void *cmp, void *call, void *arg, void *trans);
-/*
- [Thread Safe]
- Delete an element from the map if it is found.
- Return whether an element has been deleted.
-*/
-
-void map_trv(Map *map, void *iter, void *arg, void *trans, TreeTraversionOrder order);
-/*
- [Thread Safe]
- Traverse the map.
- Calls iter on every element, with the extra argument arg.
-*/
-
-
-#endif
+++ /dev/null
-#include <sched.h> // for sched_yield
-#include "bits/callback.h" // for Transformer
-#include "queue.h"
-
-void queue_ini(Queue *queue)
-{
- list_ini(&queue->lst);
- queue->cnl = queue->fin = 0;
- pthread_cond_init(&queue->cnd, NULL);
- pthread_mutex_init(&queue->mtx, NULL);
-}
-
-void queue_dst(Queue *queue)
-{
- pthread_cond_destroy(&queue->cnd);
- pthread_mutex_destroy(&queue->mtx);
-}
-
-void queue_clr(Queue *queue, void *iter, void *arg, void *trans)
-{
- list_clr(&queue->lst, iter, arg, trans);
-}
-
-#define ENQUEUE(queue_fun, list_fun) \
- bool queue_fun(Queue *queue, void *dat) \
- { \
- bool success = false; \
- \
- pthread_mutex_lock(&queue->mtx); \
- if (!queue->fin) { \
- success = true; \
- list_fun(&queue->lst, dat); \
- pthread_cond_signal(&queue->cnd); \
- } \
- pthread_mutex_unlock(&queue->mtx); \
- \
- return success; \
- }
-
-ENQUEUE(queue_enq, list_apd)
-ENQUEUE(queue_ppd, list_ppd)
-
-#undef ENQUEUE
-
-void *queue_deq(Queue *queue, void *trans)
-{
- void *dat = NULL;
-
- 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 (trans)
- dat = ((Transformer) trans)(dat);
- } else {
- pthread_cond_wait(&queue->cnd, &queue->mtx);
- }
- }
- pthread_mutex_unlock(&queue->mtx);
-
- return dat;
-}
-
-void queue_cnl(Queue *queue)
-{
- pthread_mutex_lock(&queue->mtx);
- queue->cnl = 1;
- pthread_cond_broadcast(&queue->cnd);
- pthread_mutex_unlock(&queue->mtx);
-}
-
-void queue_fin(Queue *queue)
-{
- pthread_mutex_lock(&queue->mtx);
- queue->fin = 1;
- pthread_mutex_unlock(&queue->mtx);
-
- for (;;) {
- pthread_mutex_lock(&queue->mtx);
- ListNode *node = queue->lst.fst;
- pthread_mutex_unlock(&queue->mtx);
-
- if (node)
- sched_yield();
- else
- break;
- }
-}
+++ /dev/null
-/*
- 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> // for pthread_cond_t, pthread_mutex_t
-#include <stdbool.h> // for bool
-#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;
-
-void queue_ini(Queue *queue);
-/*
- Initializes the queue.
-
- The queue should be uninitialized or deleted when passed to this function.
-*/
-
-void queue_dst(Queue *queue);
-/*
- Destroy 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, void *iter, void *arg, void *trans);
-/*
- 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.
-*/
-
-bool queue_ppd(Queue *queue, void *dat);
-/*
- [Thread Safe]
- Enqueues an element at the front 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, void *trans);
-/*
- [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 // _DRAGONSTD_QUEUE_H_
+++ /dev/null
-#include "bits/callback.h" // for SingleCallback
-#include "refcount.h"
-
-void refcount_ini(Refcount *refcount, void *obj, void *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(Refcount *refcount)
-{
- pthread_mutex_lock(&refcount->mtx);
- refcount->cnt++;
- pthread_mutex_unlock(&refcount->mtx);
- return refcount;
-}
-
-void *refcount_grb(Refcount *refcount)
-{
- return refcount_obj(refcount_inc(refcount));
-}
-
-void refcount_drp(Refcount *refcount)
-{
- pthread_mutex_lock(&refcount->mtx);
- unsigned short count = --refcount->cnt;
- pthread_mutex_unlock(&refcount->mtx);
-
- if (!count)
- ((SingleCallback) refcount->del)(refcount->obj);
-}
-
-void *refcount_obj(Refcount *refcount)
-{
- return refcount->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
-
-typedef struct {
- /* private */
- void *obj;
- void *del;
- unsigned short cnt; // counter
- pthread_mutex_t mtx; // lock to protect count
-} Refcount;
-
-void refcount_ini(Refcount *refcount, void *obj, void *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(Refcount *refcount);
-/*
- [Thread Safe]
- Grab a reference to the refcount.
-
- Returns the refcount.
-*/
-
-void *refcount_grb(Refcount *rc);
-/*
- [Thread Safe]
- Does the same as refcount_inc, except it returns the referenced object instead of the
- refcount.
-*/
-
-void refcount_drp(Refcount *refcount);
-/*
- [Thread Safe]
- Drop a reference to the object.
-
- May delete the object using the del function if the counter gets down to zero.
-*/
-
-void *refcount_obj(Refcount *refcount);
-/*
- [Thread Safe]
- Return referenced object.
-*/
-
-#endif // _DRAGONSTD_REFCOUNT_H_
+++ /dev/null
-test_array
-test_list
-test_tree
-test_queue
-test_map
-test_flag
-test_refcount_map
+++ /dev/null
-CC=cc -g -Wall -Wextra -Werror -fmax-errors=1
-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_%: test_%.c ../*.h ../*.c ../bits/*.h ../bits/*.c
- $(CC) $< ../*.c ../bits/*.c -o $@ -lpthread
-
-clean:
- rm -rf test_array test_list test_tree test_queue test_flag test_refcount_map
+++ /dev/null
-#include <stdio.h>
-#include <stdlib.h>
-#include <assert.h>
-#include <time.h>
-#include "../array.h"
-
-int cmp_int(const int *pa, const int *pb)
-{
- return *pa - *pb;
-}
-
-void assert_in_order(Array *arr)
-{
- for (size_t i = 1; i < arr->siz; i++)
- assert(((int *) arr->ptr)[i - 1] <= ((int *) arr->ptr)[i]);
-}
-
-void dump(Array *arr)
-{
- for (size_t i = 0; i < arr->siz; i++) {
- printf("%d", ((int *) arr->ptr)[i]);
-
- if (i != arr->siz - 1)
- printf(",");
- }
-}
-
-int main()
-{
- printf("-------------\n");
- printf("Testing Array\n");
- printf("-------------\n");
-
- int i;
- Array arr, arr2;
- srand(time(NULL));
-
- printf("testing ini\n");
- array_ini(&arr, sizeof(int), 0);
-
- printf("testing add\n");
- i = 1; array_apd(&arr, &i);
- i = 3; array_apd(&arr, &i);
- i = 4; array_apd(&arr, &i);
-
- printf("testing put\n");
- i = 2; array_put(&arr, &i, 1);
- i = 5; array_put(&arr, &i, arr.siz);
-
- printf("testing siz: exp: 5 got: %zu\n", arr.siz);
- assert(arr.siz == 5);
-
- printf("testing cap: exp: 5 got: %zu\n", arr.cap);
- assert(arr.cap == 5);
-
- printf("testing contents: exp: 1,2,3,4,5 got: "); dump(&arr); printf("\n");
- for (size_t j = 0; j < arr.siz; j++)
- assert((size_t) ((int *) arr.ptr)[j] == j + 1);
-
- printf("testing cln\n");
- array_cln(&arr2, &arr);
-
- printf("testing equality: exp: "); dump(&arr); printf(" got: "); dump(&arr2);
- printf("\n");
-
- for (size_t j = 0; j < arr.siz; j++)
- assert(((int *) arr.ptr)[j] == ((int *) arr2.ptr)[j]);
-
- printf("testing clr\n");
- array_clr(&arr);
- array_clr(&arr2);
-
- printf("testing ini after clr\n");
- array_ini(&arr, sizeof(int), 5);
-
- printf("testing cap: exp: 0 got: %zu\n", arr.cap);
- assert(arr.cap == 0);
-
- printf("testing overallocation\n");
- i = 50; array_apd(&arr, &i);
-
- printf("testing cap: exp: 0 got: %zu\n", arr.cap);
- assert(arr.siz == 1);
-
- printf("testing cap: exp: 6 got: %zu\n", arr.cap);
- assert(arr.cap == 6);
-
- for (int j = 0; j < 7; j++) {
- i = rand() % 100; array_apd(&arr, &i);
- }
-
- printf("testing siz: exp: 8 got: %zu\n", arr.cap);
- assert(arr.siz == 8);
-
- printf("testing cap: exp: 12 got: %zu\n", arr.cap);
- assert(arr.cap == 12);
-
- printf("testing grw\n");
- array_grw(&arr, 5);
-
- printf("testing siz: exp: 13 got: %zu\n", arr.cap);
- assert(arr.siz == 13);
-
- printf("testing cap: exp: 18 got: %zu\n", arr.cap);
- assert(arr.cap == 18);
-
- printf("testing shr\n");
- array_shr(&arr, 5);
-
- printf("testing siz: exp: 8 got: %zu\n", arr.cap);
- assert(arr.siz == 8);
-
- printf("testing cap: exp: 8 got: %zu\n", arr.cap);
- assert(arr.cap == 8);
-
- printf("testing srt\n");
- array_srt(&arr, &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, &cmp_int);
-
- printf("testing fnd at index %zu: exp: >=0 got: %ld\n", j, s);
- assert(s >= 0);
-
- int k = ((int *) arr.ptr)[s];
-
- printf("testing fnd at index %zu: exp: %d got: %d\n", j, i, k);
- assert(k == i);
- }
-
- printf("testing ins\n");
- for (int j = 0; j < 10; j++) {
- i = rand() % 100; array_ins(&arr, &i, &cmp_int);
- }
-
- printf("testing order: exp: (sorted) got: "); dump(&arr); printf("\n");
- assert_in_order(&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 int *ia, const int *ib)
-{
- return *ia - *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, &a, &cmp_int, NULL));
- assert(list_add(&list, &b, &b, &cmp_int, NULL));
- assert(list_add(&list, &c, &c, &cmp_int, NULL));
- assert(!list_add(&list, &d, &d, &cmp_int, NULL));
-
- 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, NULL, NULL));
- assert(list_get(&list, &a, &cmp_int, NULL) == NULL);
-
- printf("testing clr\n");
- list_clr(&list, NULL, 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_dst(&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;
-
-int rand_id()
-{
- return rand() % 1000;
-}
-
-void delete_obj(DataObject *obj)
-{
- refcount_dst(&obj->rc);
- free(obj);
-}
-
-int cmp_obj(const Refcount *rc, const int *id)
-{
- return ((DataObject *) rc->obj)->id - *id;
-}
-
-static void *thread_create(unsigned int *result)
-{
- while (!cancel) {
- DataObject *obj = malloc(sizeof *obj);
- obj->id = rand_id();
-
- refcount_ini(&obj->rc, obj, &delete_obj);
-
- if (map_add(&map, &obj->id, &obj->rc, &cmp_obj, &refcount_inc))
- (*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, &cmp_obj, &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, &cmp_obj, &refcount_drp, NULL, NULL))
- (*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(1);
-
- 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, &refcount_drp, NULL, NULL, 0);
- map_dst(&map);
-
- printf("Time: 1 second\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 int *ia, const int *ib)
-{
- return *ia - *ib;
-}
-
-void clear_callback(int *ia, int *ib)
-{
- assert(*ia >= *ib);
- *ib = *ia;
- 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, &a, &cmp_int, NULL));
- assert(tree_add(&tree, &b, &b, &cmp_int, NULL));
- assert(tree_add(&tree, &c, &c, &cmp_int, NULL));
- assert(!tree_add(&tree, &d, &d, &cmp_int, NULL));
-
- 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, NULL, NULL));
- assert(tree_get(&tree, &a, &cmp_int, NULL) == NULL);
-
- printf("testing clr\n");
- tree_clr(&tree, NULL, 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, n, &cmp_int, NULL))
- free(n);
- }
-
- int last = -1;
- tree_clr(&tree, &clear_callback, &last, NULL, TRAVERSION_INORDER);
-}
+++ /dev/null
-#include <stdlib.h> // for malloc, free
-#include "bits/callback.h" // for Callback, Comparator, Transformer
-#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, Callback iter, void *arg, Transformer trans, TreeTraversionOrder order, int delete)
-{
- if (!node)
- return;
-
- if (iter && order == TRAVERSION_PREORDER ) iter(trans ? trans(node->dat) : node->dat, arg);
- traverse(node->lft, iter, arg, trans, order, delete);
- if (iter && order == TRAVERSION_INORDER ) iter(trans ? trans(node->dat) : node->dat, arg);
- traverse(node->rgt, iter, arg, trans, order, delete);
- if (iter && order == TRAVERSION_POSTORDER) iter(trans ? trans(node->dat) : 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, void *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, void *iter, void *arg, void *trans, TreeTraversionOrder order)
-{
- traverse(tree->rot, iter, arg, trans, order, 0);
-}
-
-void tree_clr(Tree *tree, void *iter, void *arg, void *trans, TreeTraversionOrder order)
-{
- traverse(tree->rot, iter, arg, trans, 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 <stdbool.h> // for bool
-#include "bits/compare.h" // for cmp_ref (not used in file)
-
-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.
-*/
-
-bool tree_add(Tree *tree, void *key, void *dat, void *cmp, void *trans);
-/*
- Add an element to the tree.
-
- If an equal element is already in the tree, don't add anything.
- Return whether an element has been added.
-*/
-
-void *tree_get(Tree *tree, void *key, void *cmp, void *trans);
-/*
- Get an element from the tree, or return NULL if none found.
-*/
-
-bool tree_del(Tree *tree, void *key, void *cmp, void *call, void *arg, void *trans);
-/*
- Delete an element from the tree if it is found.
- Return whether an element has been deleted.
-*/
-
-TreeNode **tree_nfd(Tree *tree, void *key, void *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, void *iter, void *arg, void *trans, TreeTraversionOrder order);
-/*
- Traverse the tree.
- Calls iter on every element, with the extra argument arg.
-*/
-
-void tree_clr(Tree *tree, void *iter, void *arg, void *trans, TreeTraversionOrder order);
-/*
- Traverses the tree and deletes all elements.
- Calls iter 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