From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 9 Apr 2022 09:43:53 +0200 Subject: neue Verzeichnisstruktur --- src/arraylist.c | 368 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 368 insertions(+) create mode 100644 src/arraylist.c (limited to 'src/arraylist.c') diff --git a/src/arraylist.c b/src/arraylist.c new file mode 100644 index 0000000..f010d07 --- /dev/null +++ b/src/arraylist.c @@ -0,0 +1,368 @@ +/* arraylist */ +#include +#include +#include +#include +#include +#include + +#include "util.h" + +typedef int T; + +struct ArrayList { + T ** array; + size_t size; + size_t capacity; +}; + +static T ** +ArrayList_allocateArray(void *ptr, size_t nelem) +{ + T **new_ptr = reallocarray(ptr, nelem, sizeof *new_ptr); + + if ( new_ptr == NULL ) { + ERROR("out of memory"); + } + + return new_ptr; +} + +void +ArrayList_init(struct ArrayList *arrayList) +{ + assert(arrayList); + + arrayList->array = NULL; + arrayList->size = 0; + arrayList->capacity = 0; +} + +struct ArrayList * +ArrayList_new(void) +{ + struct ArrayList *arrayList = malloc(sizeof *arrayList); + if ( arrayList ) { + ArrayList_init(arrayList); + } + return arrayList; +} + +void +ArrayList_free(struct ArrayList *arrayList) +{ + assert(arrayList); + + free(arrayList->array); + ArrayList_init(arrayList); +} + +void +ArrayList_delete(struct ArrayList *arrayList) +{ + assert(arrayList); + + ArrayList_free(arrayList); + free(arrayList); +} + +static void +ArrayList_growIfNeeded(struct ArrayList *arrayList) +{ + assert(arrayList); + + if ( arrayList->size == arrayList->capacity ) { + if ( arrayList->array == NULL ) { // leere Liste + assert(arrayList->size == 0); + assert(arrayList->capacity == 0); + + static const size_t DEFAULT_CAPACITY = 10; + + arrayList->capacity = DEFAULT_CAPACITY; + arrayList->array = ArrayList_allocateArray(NULL, DEFAULT_CAPACITY); + } + else { + size_t new_capacity = (arrayList->capacity * 3) / 2; // *= 1.5 + T ** new_arrayList = ArrayList_allocateArray(arrayList->array, new_capacity); + + arrayList->capacity = new_capacity; + arrayList->array = new_arrayList; + } + + assert(arrayList->array); + } + + assert(arrayList->capacity > arrayList->size); +} + +void +ArrayList_append(struct ArrayList *arrayList, T *ptr) +{ + assert(arrayList); + + ArrayList_growIfNeeded(arrayList); + + arrayList->array[arrayList->size++] = ptr; +} + +void +ArrayList_insertAt(struct ArrayList *arrayList, size_t idx, T *ptr) +{ + assert(arrayList); + assert(idx <= arrayList->size); // allow last position + + ArrayList_growIfNeeded(arrayList); + + memmove(&arrayList->array[idx + 1], + &arrayList->array[idx], + (arrayList->size - idx) * sizeof arrayList->array[0]); + arrayList->array[idx] = ptr; + ++arrayList->size; +} + +T * +ArrayList_getAt(struct ArrayList *arrayList, size_t idx) +{ + assert(arrayList); + assert(idx < arrayList->size); + + return arrayList->array[idx]; +} + +size_t +ArrayList_size(struct ArrayList *arrayList) +{ + assert(arrayList); + + return arrayList->size; +} + +bool +ArrayList_empty(struct ArrayList *arrayList) +{ + assert(arrayList); + + return arrayList->size == 0; +} + +void +ArrayList_removeAt(struct ArrayList *arrayList, size_t idx, void clear_func(T *, void *), void *args) +{ + assert(arrayList); + assert(idx < arrayList->size); + + if ( clear_func ) { + clear_func(arrayList->array[idx], args); + } + +#if defined(ARRAYLIST_KEEP_ORDER) + memmove(&arrayList->arrayList[idx], + &arrayList->arrayList[idx + 1], + (arrayList->size - (idx + 1)) * sizeof arrayList->arrayList[0]); +#else + arrayList->array[idx] = arrayList->array[arrayList->size - 1]; +#endif + + --arrayList->size; +} + +struct qsortHelper_context { + int (*cmp)(const T *, const T *, void *); + void *args; +}; + +typedef const T *const_T_ptr; + +static int +ArrayList_qsortHelper(void *ctx, const void *a, const void *b) +{ + const const_T_ptr *aa = a; + const const_T_ptr *bb = b; + + const struct qsortHelper_context *context = ctx; + + return context->cmp(*aa, *bb, context->args); +} + +void +ArrayList_sort(struct ArrayList *arrayList, int cmp(const T *, const T *, void *), void *args) +{ + assert(arrayList); + assert(cmp); + + struct qsortHelper_context context = { + .cmp = cmp, + .args = args + }; + + // Das vollständige qsort_x()-Drama: https://stackoverflow.com/a/46042467 + qsort_r(arrayList->array, arrayList->size, sizeof arrayList->array[0], &context, ArrayList_qsortHelper); +} + +bool +ArrayList_linearSearch(struct ArrayList *arrayList, void *key, int cmp(void *, const T *, void *), void *args, size_t *loc) +{ + assert(arrayList); + assert(cmp); + assert(loc); + + for ( size_t idx = 0; idx != arrayList->size; ++idx ) { + if ( cmp(key, arrayList->array[idx], args) == 0 ) { + *loc = idx; + return true; + } + } + return false; +} + +struct bsearchHelper_context { + void *key; + int (*cmp)(void *, const T *, void *); + void *args; +}; + +static int +ArrayList_bsearchHelper(const void *ctx, const void *el) +{ + const struct bsearchHelper_context *context = ctx; + const const_T_ptr * element = el; + + return context->cmp(context->key, *element, context->args); +} + +bool +ArrayList_binarySearch(struct ArrayList *arrayList, void *key, int cmp(void *, const T *, void *), void *args, size_t *loc) +{ + assert(arrayList); + assert(cmp); + assert(loc); + + struct bsearchHelper_context context = { + .key = key, + .cmp = cmp, + .args = args + }; + + T **pos = bsearch(&context, arrayList->array, arrayList->size, sizeof arrayList->array[0], ArrayList_bsearchHelper); + if ( pos ) { + *loc = (size_t)(pos - arrayList->array); + return true; + } + else { + return false; + } +} + +void +ArrayList_shuffle(struct ArrayList *arrayList, size_t rng(size_t, void *), void *args) +{ + assert(arrayList); + assert(rng); + + if ( arrayList->size > 1 ) { + for ( size_t i = arrayList->size - 1; i > 0; --i ) { + size_t j = rng(i + 1, args); + + // swap + T *t = arrayList->array[j]; + arrayList->array[j] = arrayList->array[i]; + arrayList->array[i] = t; + } + } +} + +static void +ArrayList_debugPrint(struct ArrayList *arrayList) +{ + for ( size_t idx = 0; idx != ArrayList_size(arrayList); ++idx ) { + T *ptr = ArrayList_getAt(arrayList, idx); + printf("%d, ", *ptr); + } + putchar('\n'); +} + +static int +my_compare(const T *a, const T *b, void *args) +{ + (void) args; + + if ( *a > *b ) + return 1; + else if ( *a < *b ) + return -1; + else + return 0; +} + +static int +my_search_compare(void *key, const T *element, void *args) +{ + (void) args; + + int *a = key; + + if ( *a < *element ) + return -1; + else if ( *a > *element ) + return 1; + else + return 0; +} + +static size_t +my_rng(size_t max, void *args) +{ + (void) args; + return (size_t) rand() % max; +} + +static void +ArrayList_testSort(struct ArrayList *arrayList) +{ + for ( size_t i = 1; i < arrayList->size; ++i ) { + if ( *arrayList->array[i - 1] > *arrayList->array[i] ) { + fprintf(stderr, "Fehler: %zu (%d, %d)\n", i, *arrayList->array[i - 1], *arrayList->array[i]); + exit(EXIT_FAILURE); + } + } +} + +int +main(void) +{ + srand(time(NULL)); + + int a = 11, b = 22, c = 33, d = 44; + + struct ArrayList *arrayList = ArrayList_new(); + + ArrayList_append(arrayList, &a); + ArrayList_append(arrayList, &b); + ArrayList_append(arrayList, &c); + ArrayList_append(arrayList, &d); + ArrayList_debugPrint(arrayList); // 11, 22, 33, 44 + + ArrayList_removeAt(arrayList, 0, NULL, NULL); + ArrayList_debugPrint(arrayList); // 44, 22, 33 + + ArrayList_insertAt(arrayList, 3, &a); + ArrayList_debugPrint(arrayList); // 44, 22, 33, 11 + + ArrayList_sort(arrayList, my_compare, NULL); + ArrayList_testSort(arrayList); + + ArrayList_debugPrint(arrayList); // 11, 22, 33, 44 + + size_t loc; + int dummy = 44; + if ( ArrayList_binarySearch(arrayList, &dummy, my_search_compare, NULL, &loc) ) { + printf("Gefunden: %zu\n", loc); + } + + ArrayList_shuffle(arrayList, my_rng, NULL); + ArrayList_debugPrint(arrayList); // ?? + + ArrayList_delete(arrayList); + + return EXIT_SUCCESS; +} -- cgit v1.3