From 3f1f021680c1ec85ed76896be7d617425f6ed073 Mon Sep 17 00:00:00 2001 From: rsiddharth Date: Sun, 29 Sep 2019 19:07:22 -0400 Subject: nserver: Add darray.h --- nserver/src/darray.c | 192 +++++++++++++++++++++++++++++++++++++++++++++++++++ nserver/src/darray.h | 120 ++++++++++++++++++++++++++++++++ 2 files changed, 312 insertions(+) create mode 100644 nserver/src/darray.c create mode 100644 nserver/src/darray.h (limited to 'nserver') diff --git a/nserver/src/darray.c b/nserver/src/darray.c new file mode 100644 index 0000000..6dc3839 --- /dev/null +++ b/nserver/src/darray.c @@ -0,0 +1,192 @@ +#include +#include +#include + +DArray *DArray_create(size_t element_size, size_t initial_max) +{ + DArray *array = malloc(sizeof(DArray)); + check_mem(array); + array->max = initial_max; + check(array->max > 0, "You must set initial_max > 0."); + + array->contents = calloc(initial_max, sizeof(void *)); + check_mem(array->contents); + + array->end = 0; + array->element_size = element_size; + array->expand_rate = DEFAULT_EXPAND_RATE; + + return array; + + error: + if (array) + free(array); + return NULL; +} + +void DArray_clear(DArray *array) +{ + check(array != NULL, "array cannot be NULL"); + + int i = 0; + if (array->element_size > 0) { + for (i = 0; i < array->max; i++) { + if (array->contents[i] != NULL) { + free(array->contents[i]); + } + } + } + + error: + return; +} + +static inline int DArray_resize(DArray *array, size_t newsize) +{ + check(array != NULL, "array cannot be NULL"); + check((int) newsize >= array->end, "newsize must be >= end."); + + array->max = newsize; + check(array->max > 0, "The newsize must be > 0."); + + void *contents = realloc(array->contents, + array->max * sizeof(void *)); + // Check contents and assume realloc doesn't harm the original on error. + + check_mem(contents); + + array->contents = contents; + + return 0; + error: + return -1; +} + +int DArray_expand(DArray *array) +{ + size_t old_max = array->max; + check(DArray_resize(array, array->max + array->expand_rate) == 0, + "Failed to expand array to new size: %d", + array->max + (int) array->expand_rate); + + memset(array->contents + old_max, 0, (array->expand_rate) * sizeof(void *)); + + return 0; + + error: + return -1; +} + +int DArray_contract(DArray *array) +{ + check(array != NULL, "array cannot be NULL"); + + int new_size = array->end < (int) array->expand_rate ? + (int) array->expand_rate : array->end; + + return DArray_resize(array, new_size + 1); + error: + return -1; +} + +void DArray_destroy(DArray *array) +{ + if (array) { + if (array->contents) + free(array->contents); + free(array); + } +} + +void DArray_clear_destroy(DArray *array) +{ + DArray_clear(array); + DArray_destroy(array); +} + +int DArray_push(DArray *array, void *el) +{ + check(array != NULL, "array cannot be NULL"); + + array->contents[array->end] = el; + array->end++; + + if (DArray_end(array) >= DArray_max(array)) { + return DArray_expand(array); + } else { + return 0; + } + + error: + return -1; +} + +void *DArray_pop(DArray *array) +{ + check(array != NULL, "array cannot be NULL"); + check(array->end - 1 >= 0, "Attempt to pop from empty array."); + + void *el = DArray_remove(array, array->end - 1); + array->end--; + + if (DArray_end(array) > (int)array->expand_rate + && DArray_end(array) % array->expand_rate) { + DArray_contract(array); + } + + return el; + error: + return NULL; +} + +int DArray_sort_add(DArray *array, void *el, DArray_compare cmp) +{ + int rc; + rc = DArray_push(array, el); + check(rc == 0, "Error pushing element."); + + // sort the array. + rc = DArray_heapsort(array, cmp); + check(rc == 0, "Error sorting array."); + + return 0; + error: + return -1; +} + +DArray *DArray_shallow_copy(DArray *array) +{ + DArray *copy = DArray_create(array->element_size, array->max); + check(copy != NULL, "Error creating DArray copy."); + + int i = 0; + for (i = 0; i < array->max; i++) { + copy->contents[i] = array->contents[i]; + } + + return copy; + error: + return NULL; +} + +int DArray_find(DArray *array, void *el, DArray_compare cmp) +{ + int low = 0; + int high = DArray_end(array) - 1; + void *c = NULL; + + while (low <= high) { + int middle = low + (high - low) / 2; + c = DArray_get(array, middle); + + if (cmp(&el, &c) < 0) { + high = middle - 1; + } else if (cmp(&el, &c) > 0) { + low = middle + 1; + } else { + return middle; + } + } + + return -1; +} diff --git a/nserver/src/darray.h b/nserver/src/darray.h new file mode 100644 index 0000000..d262d39 --- /dev/null +++ b/nserver/src/darray.h @@ -0,0 +1,120 @@ +#ifndef _DArray_h +#define _DArray_h +#include +#include +#include + +typedef struct DArray { + int end; + int max; + size_t element_size; + size_t expand_rate; + void **contents; +} DArray; + +typedef int (*DArray_compare) (const void *a, const void *b); + +DArray *DArray_create(size_t element_size, size_t initial_max); + +void DArray_destroy(DArray *array); + +void DArray_clear(DArray *array); + +int DArray_expand(DArray *array); + +int DArray_contract(DArray *array); + +int DArray_push(DArray *array, void *el); + +void *DArray_pop(DArray *array); + +int DArray_sort_add(DArray *array, void *el, DArray_compare cmp); + +int DArray_find(DArray *array, void *el, DArray_compare cmp); + +void DArray_clear_destroy(DArray *array); + +/** + * Creates a new DArray using `DArray_create` and copies the + * `contents` from array to the newly created DArray. + * + * Returns newly created DArray. + */ +DArray *DArray_shallow_copy(DArray *array); + +#define DArray_last(A) ((A)->contents[(A)->end - 1]) +#define DArray_first(A) ((A)->contents[0]) +#define DArray_end(A) ((A)->end) +#define DArray_count(A) DArray_end(A) +#define DArray_max(A) ((A)->max) + +#define DEFAULT_EXPAND_RATE 300 + +static inline int DArray_set(DArray *array, int i, void *el) +{ + check(array != NULL, "array cannot be NULL"); + check(i >= 0, "i cannot be lesser than 0"); + +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wstrict-overflow" + check(i < array->max, "darray attempt to set past max"); +#pragma GCC diagnostic pop + + if (i > array->end) + array->end = i; + + array->contents[i] = el; + return i; + error: + return -1; +} + +static inline void *DArray_get(DArray *array, int i) +{ + check(array != NULL, "array cannot be NULL"); + check(i >= 0, "i cannot be lesser than 0"); + +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wstrict-overflow" + check(i < array->max, "darray attempt to get past max"); +#pragma GCC diagnostic pop + + return array->contents[i]; + error: + return NULL; +} + +static inline void *DArray_remove(DArray *array, int i) +{ + check(array != NULL, "array cannot be NULL"); + check(i >= 0, "i cannot be lesser than 0"); + +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wstrict-overflow" + check(i < array->max, "darray attempt to get past max"); +#pragma GCC diagnostic pop + + void *el = array->contents[i]; + + array->contents[i] = NULL; + + return el; + error: + return NULL; +} + +static inline void *DArray_new(DArray *array) +{ + check(array != NULL, "array cannot be NULL"); + check(array->element_size > 0, + "Can't use DArray_new on 0 size darrays."); + + return calloc(1, array->element_size); + + error: + return NULL; +} + +#define DArray_free(E) free((E)) + +#endif -- cgit v1.2.3