From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 9 Apr 2022 09:43:53 +0200 Subject: neue Verzeichnisstruktur --- arraylist.c | 368 ------------------------------------------------------------ 1 file changed, 368 deletions(-) delete mode 100644 arraylist.c (limited to 'arraylist.c') diff --git a/arraylist.c b/arraylist.c deleted file mode 100644 index f010d07..0000000 --- a/arraylist.c +++ /dev/null @@ -1,368 +0,0 @@ -/* 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