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/allocator.c | 79 +++++ src/allocator.h | 30 ++ src/arraylist.c | 368 +++++++++++++++++++++++ src/avl.c | 471 ++++++++++++++++++++++++++++++ src/deque.c | 485 +++++++++++++++++++++++++++++++ src/dlist.c | 504 ++++++++++++++++++++++++++++++++ src/hashtab.c | 220 ++++++++++++++ src/heap.c | 291 +++++++++++++++++++ src/insertsort.c | 38 +++ src/list-tail-node.c | 197 +++++++++++++ src/list.c | 264 +++++++++++++++++ src/queue.c | 115 ++++++++ src/quicksort.c | 684 +++++++++++++++++++++++++++++++++++++++++++ src/random.h | 47 +++ src/rb.c | 614 +++++++++++++++++++++++++++++++++++++++ src/rc4.c | 156 ++++++++++ src/ringbuff.c | 156 ++++++++++ src/shellsort.c | 63 ++++ src/stack.c | 110 +++++++ src/stack2.c | 115 ++++++++ src/tree.c | 806 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/treeutil.h | 51 ++++ src/util.h | 24 ++ 23 files changed, 5888 insertions(+) create mode 100644 src/allocator.c create mode 100644 src/allocator.h create mode 100644 src/arraylist.c create mode 100644 src/avl.c create mode 100644 src/deque.c create mode 100644 src/dlist.c create mode 100644 src/hashtab.c create mode 100644 src/heap.c create mode 100644 src/insertsort.c create mode 100644 src/list-tail-node.c create mode 100644 src/list.c create mode 100644 src/queue.c create mode 100644 src/quicksort.c create mode 100644 src/random.h create mode 100644 src/rb.c create mode 100644 src/rc4.c create mode 100644 src/ringbuff.c create mode 100644 src/shellsort.c create mode 100644 src/stack.c create mode 100644 src/stack2.c create mode 100644 src/tree.c create mode 100644 src/treeutil.h create mode 100644 src/util.h (limited to 'src') diff --git a/src/allocator.c b/src/allocator.c new file mode 100644 index 0000000..98fa69f --- /dev/null +++ b/src/allocator.c @@ -0,0 +1,79 @@ +#include "allocator.h" + +#include /* malloc */ + +/* Interface Code */ +static void * +default_allocate(struct allocator *allocator, size_t n) +{ + (void) allocator; + return malloc(n); +} + +static void +default_deallocate(struct allocator *allocator, void *ptr) +{ + (void) allocator; + free(ptr); +} + +struct allocator allocator_default_allocator = { + .allocate = &default_allocate, + .deallocate = &default_deallocate +}; + +/* Libary Code */ +#include + +void * +allocator_malloc(struct allocator *allocator, size_t n) +{ + if ( !allocator ) { + allocator = &allocator_default_allocator; + } + + return allocator->allocate(allocator, n); +} + +void +allocator_free(struct allocator *allocator, void *ptr) +{ + if ( !allocator ) { + allocator = &allocator_default_allocator; + } + + allocator->deallocate(allocator, ptr); +} + +char * +allocator_strdup(struct allocator *allocator, const char *str) +{ + size_t n; + char * dest; + + n = strlen(str) + 1; + dest = allocator_malloc(allocator, n); + if ( dest ) { + memcpy(dest, str, n); + } + + return dest; +} + +void * +allocator_malloc_zero(struct allocator *allocator, size_t n) +{ + void *ptr; + + ptr = allocator_malloc(allocator, n); + if ( ptr ) { + memset(ptr, 0, n); + } + + return ptr; +} + +int +main() +{ +} diff --git a/src/allocator.h b/src/allocator.h new file mode 100644 index 0000000..dd9bb16 --- /dev/null +++ b/src/allocator.h @@ -0,0 +1,30 @@ +#pragma once + +#include /* size_t */ + +struct allocator { + void *(*allocate)(struct allocator *allocator, size_t n); + void (*deallocate)(struct allocator *allocator, void *ptr); +}; + +extern struct allocator default_allocator; + +/* allocator interface */ +void *allocator_malloc(struct allocator *allocator, size_t n); +void allocator_free(struct allocator *allocator, void *ptr); + +/* helper functions */ +char *allocator_strdup(struct allocator *allocator, const char *str); +void *allocator_malloc_zero(struct allocator *allocator, size_t n); + +#define ALLOCATE(n) \ + allocator_malloc(&allocator_default_allocator, (n)) + +#define ALLOCATE_ZERO(n) \ + allocator_malloc_zero(&allocator_default_allocator, (n)) + +#define FREE(ptr) \ + (allocator_free(&allocator_default_allocator, (ptr)), (ptr) = NULL) + +#define NEW(ptr) ((ptr) = ALLOCATE(sizeof *(ptr))) +#define NEW0(ptr) ((ptr) = ALLOCATE_ZERO(sizeof *(ptr))) 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; +} diff --git a/src/avl.c b/src/avl.c new file mode 100644 index 0000000..874cc6c --- /dev/null +++ b/src/avl.c @@ -0,0 +1,471 @@ +// AVL Tree +#include +#include +#include +#include +#include + +/* utils */ +#include "util.h" + +// clang-format off + +// Review: http://www.inr.ac.ru/~info21/ADen/ +// Tests: https://stackoverflow.com/q/3955680 + +/* --8<-- avl_type */ +typedef int T; + +struct tree_node { + struct tree_node *left, *right; + int bal; + T key; + int count; /* collision counter */ + /* ggf. weitere Felder... */ +}; +/* -->8-- */ + +/* --8<-- avl_insert_r */ +static struct tree_node * +insert_r(T x, struct tree_node *p, bool *h) +{ + struct tree_node *p1, *p2; + + if ( p == NULL ) { + *h = true; + + p = malloc(sizeof *p); + if ( p ) { + p->left = NULL; + p->right = NULL; + p->bal = 0; + + p->key = x; + p->count = 1; /* hit counter */ + } + else + ERROR("out of memory"); + } + else if ( x < p->key ) { + p->left = insert_r(x, p->left, h); + + if ( *h ) { + if ( p->bal == +1 ) { + p->bal = 0; + *h = false; + } + else if ( p->bal == 0 ) { + p->bal = -1; + } + else /* if ( p->bal == -1 ) */ { + p1 = p->left; + if ( p1->bal == -1 ) { /* single LL rotation */ + p->left = p1->right; p1->right = p; + p->bal = 0; p = p1; + } + else { /* double LR rotation */ + p2 = p1->right; + p1->right = p2->left; p2->left = p1; + p->left = p2->right; p2->right = p; + p->bal = ( p2->bal == -1 ) ? +1 : 0; + p1->bal = ( p2->bal == +1 ) ? -1 : 0; + p = p2; + } + p->bal = 0; + *h = false; + } + } + } + else if ( x > p->key ) { + p->right = insert_r(x, p->right, h); + + if ( *h ) { + if ( p->bal == -1 ) { + p->bal = 0; + *h = false; + } + else if ( p->bal == 0 ) { + p->bal = +1; + } + else /* if ( p->bal == +1 ) */ { + p1 = p->right; + if ( p1->bal == +1 ) { /* single RR rotation */ + p->right = p1->left; p1->left = p; + p->bal = 0; p = p1; + } + else { /* double RL rotation */ + p2 = p1->left; + p1->left = p2->right; p2->right = p1; + p->right = p2->left; p2->left = p; + p->bal = ( p2->bal == +1 ) ? -1 : 0; + p1->bal = ( p2->bal == -1 ) ? +1 : 0; + p = p2; + } + p->bal = 0; + *h = false; + } + } + } + else { + /* handle collision! */ + p->count++; /* hit counter */ + *h = false; + } + assert(p != NULL); + + return p; +} +/* -->8-- */ + +/* --8<-- avl_insert */ +struct tree_node * +insert(struct tree_node *tree, T data) +{ + bool h = false; + return insert_r(data, tree, &h); +} +/* -->8-- */ + +/* --8<-- avl_balanceL */ +static struct tree_node * +balanceL(struct tree_node *p, bool *h) +{ + if ( p->bal == -1 ) { + p->bal = 0; + } + else if ( p->bal == 0 ) { + p->bal = +1; + *h = false; + } + else /* if ( p->bal == +1 ) */ { /* rebalance */ + struct tree_node *p1 = p->right; + if ( p1->bal >= 0 ) { /* singla RR rotation */ + p->right = p1->left; + p1->left = p; + if ( p1->bal == 0 ) { + p->bal = +1; + p1->bal = -1; + *h = false; + } + else { + p->bal = 0; + p1->bal = 0; + } + p = p1; + } + else { /* double RL rotation */ + struct tree_node *p2 = p1->left; + p1->left = p2->right; + p2->right = p1; + p->right = p2->left; + p2->left = p; + p->bal = ( p2->bal == +1 ) ? -1 : 0; + p1->bal = ( p2->bal == -1 ) ? +1 : 0; + p = p2; + p2->bal = 0; + } + } + return p; +} +/* -->8-- */ + +/* --8<-- avl_balanceR */ +static struct tree_node * +balanceR(struct tree_node *p, bool *h) +{ + if ( p->bal == +1 ) { + p->bal = 0; + } + else if ( p->bal == 0 ) { + p->bal = -1; + *h = false; + } + else /* p->bal == -1 */ { /* rebalance */ + struct tree_node *p1 = p->left; + if ( p1->bal <= 0 ) { /* single LL rotation */ + p->left = p1->right; + p1->right = p; + if ( p1->bal == 0 ) { + p->bal = -1; + p1->bal = +1; + *h = false; + } + else { + p->bal = 0; + p1->bal = 0; + } + p = p1; + } + else { /* double LR rotation */ + struct tree_node *p2 = p1->right; + p1->right = p2->left; + p2->left = p1; + p->left = p2->right; + p2->right = p; + p->bal = ( p2->bal == -1 ) ? +1 : 0; + p1->bal = ( p2->bal == +1 ) ? -1 : 0; + p = p2; + p2->bal = 0; + } + } + return p; +} +/* -->8-- */ + +/* --8<-- avl_del */ +static void +del(struct tree_node **q, struct tree_node **r, bool *h) +{ + if ( (*r)->right ) { + del(q, &(*r)->right, h); + if ( *h ) + *r = balanceR(*r, h); + } + else { + /* copy data */ + (*q)->key = (*r)->key; + (*q)->count = (*r)->count; + + *q = *r; + *r = (*r)->left; + *h = true; + } +} +/* -->8-- */ + +/* --8<-- avl_delete_r */ +static struct tree_node * +delete_r(T x, struct tree_node *p, bool *h) +{ + if ( p == NULL ) { + ERROR("key not found"); + } + else if ( x < p->key ) { + p->left = delete_r(x, p->left, h); + if ( *h ) + p = balanceL(p, h); + } + else if ( x > p->key ) { + p->right = delete_r(x, p->right, h); + if ( *h ) + p = balanceR(p, h); + } + else /* if ( x == p->key ) */ { + struct tree_node *q = p; + if ( q->right == NULL ) { + p = q->left; + *h = true; + } + else if ( q->left == NULL ) { + p = q->right; + *h = true; + } + else { + del(&q, &q->left, h); + if ( *h ) + p = balanceL(p, h); + } + free(q); + } + return p; +} +/* -->8-- */ + +/* --8<-- avl_delete */ +struct tree_node * +delete(struct tree_node *tree, T data) +{ + bool h = false; + return delete_r(data, tree, &h); +} +/* -->8-- */ + +// aux display and verification routines, helpful but not essential +struct trunk { + struct trunk *prev; + char * str; +}; + +void show_trunks(struct trunk *p) +{ + if (!p) return; + show_trunks(p->prev); + printf("%s", p->str); +} + +// this is very haphazzard +void show_tree(struct tree_node *root, struct trunk *prev, int is_left) +{ + if (root == NULL) return; + + struct trunk this_disp = { prev, " " }; + char *prev_str = this_disp.str; + show_tree(root->right, &this_disp, 1); + + if (!prev) + this_disp.str = "---"; + else if (is_left) { + this_disp.str = ".--"; + prev_str = " |"; + } else { + this_disp.str = "`--"; + prev->str = prev_str; + } + + show_trunks(&this_disp); + if ( root->key >= 'A' && root->key <= 'Z' ) + printf("%c\n", root->key); + else + printf("%d\n", root->key); + + if (prev) prev->str = prev_str; + this_disp.str = " |"; + + show_tree(root->left, &this_disp, 0); + if (!prev) puts(""); +} + +void +print(struct tree_node *tree) +{ + if ( tree ) { + print(tree->left); + printf("%d (%d)\n", tree->key, tree->bal); + print(tree->right); + } +} + +int +main() +{ + + +#if 0 /* 1a/b */ + tree = insert(tree, 20); + tree = insert(tree, 4); + show_tree(tree, 0, 0); + + //tree = insert(tree, 15); + tree = insert(tree, 8); + show_tree(tree, 0, 0); +#endif + +#if 0 /* 2a/b */ + tree = insert(tree, 20); + tree = insert(tree, 4); + tree = insert(tree, 26); + tree = insert(tree, 3); + tree = insert(tree, 9); + show_tree(tree, 0, 0); + + //tree = insert(tree, 15); + tree = insert(tree, 8); + show_tree(tree, 0, 0); +#endif + +#if 0 /* 3a/b */ + tree = insert(tree, 20); + tree = insert(tree, 4); + tree = insert(tree, 26); + tree = insert(tree, 3); + tree = insert(tree, 9); + tree = insert(tree, 21); + tree = insert(tree, 30); + tree = insert(tree, 2); + tree = insert(tree, 7); + tree = insert(tree, 11); + show_tree(tree, 0, 0); + + //tree = insert(tree, 15); + tree = insert(tree, 8); + show_tree(tree, 0, 0); +#endif + +#if 0 + tree = insert(tree, 2); + tree = insert(tree, 1); + tree = insert(tree, 4); + tree = insert(tree, 3); + tree = insert(tree, 5); + show_tree(tree, 0, 0); + + tree = delete(tree, 1); + show_tree(tree, 0, 0); +#endif + +#if 0 + tree = insert(tree, 6); + tree = insert(tree, 2); + tree = insert(tree, 9); + tree = insert(tree, 1); + tree = insert(tree, 4); + tree = insert(tree, 8); + tree = insert(tree, 'B'); + tree = insert(tree, 3); + tree = insert(tree, 5); + tree = insert(tree, 7); + tree = insert(tree, 'A'); + tree = insert(tree, 'C'); + tree = insert(tree, 'D'); + show_tree(tree, 0, 0); + + tree = delete(tree, 1); + show_tree(tree, 0, 0); +#endif + + +#if 0 + tree = insert(tree, 5); + tree = insert(tree, 2); + tree = insert(tree, 8); + tree = insert(tree, 1); + tree = insert(tree, 3); + tree = insert(tree, 7); + tree = insert(tree, 'A'); + tree = insert(tree, 4); + tree = insert(tree, 6); + tree = insert(tree, 9); + tree = insert(tree, 'B'); + tree = insert(tree, 'C'); + show_tree(tree, 0, 0); + + tree = delete(tree, 1); + show_tree(tree, 0, 0); +#endif + + +#if 0 + tree = insert(tree, 5); + tree = insert(tree, 3); + tree = insert(tree, 8); + tree = insert(tree, 2); + tree = insert(tree, 4); + tree = insert(tree, 7); + tree = insert(tree, 10); + tree = insert(tree, 1); + tree = insert(tree, 6); + tree = insert(tree, 9); + tree = insert(tree, 11); + + tree = delete(tree, 4); + tree = delete(tree, 8); + tree = delete(tree, 6); + tree = delete(tree, 5); + tree = delete(tree, 2); + tree = delete(tree, 1); + tree = delete(tree, 7); + + show_tree(tree, 0, 0); +#endif + + struct tree_node *tree = NULL; + + srand(time(NULL)); + for ( int i = 0; i != 300000; ++i ) + tree = insert(tree, rand()); + + //show_tree(tree, 0, 0); + + return EXIT_SUCCESS; +} + diff --git a/src/deque.c b/src/deque.c new file mode 100644 index 0000000..881d1d3 --- /dev/null +++ b/src/deque.c @@ -0,0 +1,485 @@ +#include +#include +#include +#include + +#include "util.h" + +#define START_MAP_CAPACITY 4 +#define CHUNK_CAPACITY 17 + +/* --8<-- deque_type */ +typedef int T; + +struct deque { + T **map; + + size_t map_begin; + size_t map_end; + size_t map_capacity; + + size_t offset; + size_t size; +}; +/* -->8-- */ + +/* --8<-- deque_allocate */ +static void * +allocate(size_t n, size_t sz) +{ + void *ptr = calloc(n, sz); + if ( ptr == NULL ) { + ERROR("out of memory!"); + } + return ptr; +} +/* -->8-- */ + +/* --8<-- deque_init */ +void +deque_init(struct deque *d) +{ + assert(d); + + d->map_begin = 0; + d->map_end = 0; + d->offset = 0; + d->size = 0; + + // TODO: Error handling + d->map = allocate(START_MAP_CAPACITY, sizeof *d->map); + if ( d->map ) { + d->map_capacity = START_MAP_CAPACITY; + + for ( size_t i = 0; i != d->map_capacity; ++i ) { + d->map[i] = NULL; + } + } +} +/* -->8-- */ + +/* --8<-- deque_free */ +void +deque_free(struct deque *d) +{ + assert(d); + + // free all chunks + for ( size_t i = 0; i != d->map_capacity; ++i ) { + free(d->map[i]); + } + + // free the map itself + free(d->map); + d->map = NULL; +} +/* -->8-- */ + +/* --8<-- deque_size */ +size_t +deque_size(struct deque *d) +{ + assert(d); + + return d->size; +} +/* -->8-- */ + +/* --8<-- deque_is_empty */ +bool +deque_is_empty(struct deque *d) +{ + assert(d); + + return d->map_begin == d->map_end; +} +/* -->8-- */ + +/* --8<-- deque_grow_map */ +static void +grow_map(struct deque *d) +{ + assert(d); + + const size_t capacity = d->map_capacity + d->map_capacity / 2; + T ** map = allocate(capacity, sizeof *map); + + // copy elements + size_t i, j; + for ( i = 0, j = d->map_begin; i != d->map_capacity; ++i, ++j ) { + if ( j == d->map_capacity ) { + j = 0; + } + map[i] = d->map[j]; + } + + // initialize the rest (new) elements with NULL + for ( ; i != capacity; ++i ) { + map[i] = NULL; + } + + // free old & assign new map + free(d->map); + d->map = map; + + // adjust pointers + d->map_begin = 0; + d->map_end = d->map_capacity - 1; + + // set new map_capacity + d->map_capacity = capacity; +} +/* -->8-- */ + +/* --8<-- deque_map_append_chunk */ +static void +map_append_chunk(struct deque *d) +{ + assert(d); + + size_t next = (d->map_end + 1) % d->map_capacity; + + if ( next == d->map_begin ) { // Resize the map + grow_map(d); + + next = d->map_end + 1; + } + + d->map[d->map_end] = allocate(CHUNK_CAPACITY, sizeof **d->map); + d->map_end = next; +} +/* -->8-- */ + +/* --8<-- deque_map_prepend_chunk */ +static void +map_prepend_chunk(struct deque *d) +{ + assert(d); + + size_t prev = (d->map_begin + d->map_capacity - 1) % d->map_capacity; + + if ( prev == d->map_end ) { + grow_map(d); + + prev = d->map_capacity - 1; + } + + d->map[prev] = allocate(CHUNK_CAPACITY, sizeof **d->map); + d->map_begin = prev; +} +/* -->8-- */ + +/* --8<-- deque_map_remove_front_chunk */ +static void +map_remove_front_chunk(struct deque *d) +{ + assert(d); + + if ( d->map_begin == d->map_end ) { + return; + } + + const size_t next = (d->map_begin + 1) % d->map_capacity; + + free(d->map[d->map_begin]); + d->map[d->map_begin] = NULL; + + d->map_begin = next; +} +/* -->8-- */ + +/* --8<-- deque_remove_tail_chunk */ +static void +map_remove_tail_chunk(struct deque *d) +{ + assert(d); + + if ( d->map_begin == d->map_end ) { + return; + } + + const size_t prev = (d->map_end + d->map_capacity - 1) % d->map_capacity; + + free(d->map[prev]); + d->map[prev] = NULL; + + d->map_end = prev; +} +/* -->8-- */ + +/* --8<-- deque_get_at */ +bool +deque_get_at(struct deque *d, size_t idx, T *data) +{ + assert(d); + assert(idx < d->size); + assert(data); + + if ( idx >= d->size ) { + return false; + } + + const size_t pos = d->offset + idx; + const size_t chunk_off = pos % CHUNK_CAPACITY; + const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + + *data = d->map[chunk_num][chunk_off]; + + return true; +} +/* -->8-- */ + +/* --8<-- deque_set_at */ +bool +deque_set_at(struct deque *d, size_t idx, T data) +{ + assert(d); + assert(idx < d->size); + + if ( idx >= d->size ) { + return false; + } + + const size_t pos = d->offset + idx; + const size_t chunk_off = pos % CHUNK_CAPACITY; + const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + + d->map[chunk_num][chunk_off] = data; + + return true; +} +/* -->8-- */ + +/* --8<-- deque_push_back */ +void +deque_push_back(struct deque *d, T data) +{ + assert(d); + + const size_t pos = d->offset + d->size; + const size_t chunk_off = pos % CHUNK_CAPACITY; + size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + + if ( chunk_num == d->map_end ) { + map_append_chunk(d); + chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + } + + d->map[chunk_num][chunk_off] = data; + ++d->size; +} +/* -->8-- */ + +/* --8<-- deque_push_front */ +void +deque_push_front(struct deque *d, T data) +{ + assert(d); + + if ( d->offset == 0 ) { // Im ersten Element ist kein Platz mehr frei! + map_prepend_chunk(d); + d->offset = CHUNK_CAPACITY; + } + + --d->offset; + + const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + + d->map[chunk_num][d->offset] = data; + ++d->size; +} +/* -->8-- */ + +/* --8<-- deque_pop_back */ +bool +deque_pop_back(struct deque *d, T *data) +{ + assert(d); + assert(data); + + if ( d->size == 0 ) { + return false; + } + + --d->size; + + const size_t pos = d->offset + d->size; + const size_t chunk_off = pos % CHUNK_CAPACITY; + const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + + *data = d->map[chunk_num][chunk_off]; + + if ( d->size == 0 || chunk_off == 0 ) { + map_remove_tail_chunk(d); + } + + return true; +} +/* -->8-- */ + +/* --8<-- deque_pop_front */ +bool +deque_pop_front(struct deque *d, T *data) +{ + assert(d); + assert(data); + + if ( d->size == 0 ) { + return false; + } + + --d->size; + + const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + + *data = d->map[chunk_num][d->offset]; + + ++d->offset; + + if ( d->size == 0 || d->offset == CHUNK_CAPACITY ) { + map_remove_front_chunk(d); + d->offset = 0; + } + + return true; +} +/* -->8-- */ + +static void +deque_show(struct deque *d) +{ + assert(d); + + printf("first: %zu -- last: %zu -- size: %zu -- map_capacity: %zu -- offset: %zu\n", + d->map_begin, d->map_end, d->size, d->map_capacity, d->offset); + for ( size_t i = 0; i != d->map_capacity; ++i ) { + printf("%zu(%p) ", i, (void *) d->map[i]); + } + putchar('\n'); +} + +void +test_deque(void) +{ +#ifndef NDEBUG + struct deque d[1]; + + deque_init(d); + + const int N = 100000; + + for ( int i = 0; i != N; ++i ) { + deque_push_front(d, i); + } + + for ( int i = 0; i != N; ++i ) { + int data; + assert(deque_pop_back(d, &data) == true); + assert(data == i); + } + assert(deque_is_empty(d) == true); + assert(deque_size(d) == 0); + + deque_free(d); + + deque_init(d); + + for ( int i = 0; i != N; ++i ) { + deque_push_back(d, i); + } + + for ( int i = 0; i != N; ++i ) { + int data; + assert(deque_pop_front(d, &data) == true); + assert(data == i); + } + assert(deque_is_empty(d) == true); + assert(deque_size(d) == 0); + + deque_free(d); + + deque_init(d); + + for ( int i = 0; i != N; ++i ) { + deque_push_back(d, i); + } + + for ( int i = N - 1; i >= 0; --i ) { + int data; + assert(deque_pop_back(d, &data) == true); + assert(data == i); + } + assert(deque_is_empty(d) == true); + assert(deque_size(d) == 0); + + deque_free(d); + + deque_init(d); + + for ( int i = 0; i != N; ++i ) { + if ( i & 1 ) { + deque_push_front(d, i); + } + else { + deque_push_back(d, i); + } + } + + for ( int i = N - 1; i >= 0; --i ) { + int data; + if ( i & 1 ) { + assert(deque_pop_front(d, &data) == true); + } + else { + assert(deque_pop_back(d, &data) == true); + } + if ( data != i ) { + printf("i: %d - data: %d\n", i, data); + } + assert(data == i); + } + assert(deque_is_empty(d) == true); + assert(deque_size(d) == 0); + + deque_free(d); + + deque_init(d); + + for ( int i = 0; i != N; ++i ) { + deque_push_front(d, i); + } + + for ( int i = N - 1; i >= 0; --i ) { + int data; + assert(deque_pop_front(d, &data) == true); + assert(data == i); + } + assert(deque_is_empty(d) == true); + assert(deque_size(d) == 0); + + deque_free(d); + + puts("all tests passed."); +#endif +} + +int +main(void) +{ + test_deque(); + + struct deque c; + + deque_init(&c); + + T data; + while ( deque_pop_front(&c, &data) ) { + printf("%u, ", data); + } + putchar('\n'); + deque_show(&c); + + deque_free(&c); + + return 0; +} diff --git a/src/dlist.c b/src/dlist.c new file mode 100644 index 0000000..55e42d7 --- /dev/null +++ b/src/dlist.c @@ -0,0 +1,504 @@ +/* dlist -- double linked list */ + +/* Standard C */ +#include +#include +#include +#include +#include + +/* Project */ +#include "util.h" + +/* --8<-- dlist_type */ +typedef int T; + +struct dlist { + struct dlist_element *head, *tail; +}; + +struct dlist_element { + struct dlist_element *prev, *next; + T data; +}; +/* -->8-- */ + +/* --8<-- dlist_init */ +void +dlist_init(struct dlist *dlist) +{ + dlist->head = NULL; + dlist->tail = NULL; +} +/* -->8-- */ + +/* --8<-- dlist_empty */ +bool +dlist_empty(struct dlist *dlist) +{ + return dlist->head == NULL; +} +/* -->8-- */ + +/* --8<-- dlist_create_element */ +static struct dlist_element * +create_element(T data) +{ + struct dlist_element *element; + + element = malloc(sizeof *element); + if ( element ) { + element->data = data; + } + + return element; +} +/* -->8-- */ + +/* --8<-- dlist_push_front */ +struct dlist_element * +dlist_push_front(struct dlist *dlist, T data) +{ + struct dlist_element *element; + + element = create_element(data); + if ( element ) { + element->prev = NULL; /* Vorgänger ist in jedem Fall NULL */ + + if ( dlist_empty(dlist) ) { + element->next = NULL; + dlist->tail = element; + } + else { + element->next = dlist->head; + element->next->prev = element; + } + + dlist->head = element; /* Neues Element ist in jedem Fall der neue Anfang! */ + } + else + ERROR("out of memory"); + + return element; +} +/* -->8-- */ + +/* --8<-- dlist_push_back */ +struct dlist_element * +dlist_push_back(struct dlist *dlist, T data) +{ + struct dlist_element *element; + + element = create_element(data); + if ( element ) { + element->next = NULL; /* Nachfolger ist in jedem Fall NULL */ + + if ( dlist_empty(dlist) ) { + element->prev = NULL; + dlist->head = element; + } + else { + element->prev = dlist->tail; + element->prev->next = element; + } + + dlist->tail = element; /* Neues Element ist in jedem Fall das neue Ende! */ + } + else + ERROR("out of memory"); + + return element; +} +/* -->8-- */ + +/* --8<-- dlist_pop_front */ +bool +dlist_pop_front(struct dlist *dlist, T *data) +{ + if ( dlist->head ) { + struct dlist_element *element = dlist->head; + + dlist->head = element->next; + + if ( dlist->head == NULL ) + dlist->tail = NULL; + else + element->next->prev = NULL; + + if ( data ) { + *data = element->data; + } + free(element); + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- dlist_pop_back */ +bool +dlist_pop_back(struct dlist *dlist, T *data) +{ + if ( dlist->head ) { + struct dlist_element *element = dlist->tail; + + dlist->tail = element->prev; + + if ( dlist->tail == NULL ) + dlist->head = NULL; + else + element->prev->next = NULL; + + if ( data ) { + *data = element->data; + } + free(element); + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- dlist_insert_next */ +struct dlist_element * +dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data) +{ + struct dlist_element *new_element; + + new_element = create_element(data); + if ( new_element ) { + if ( dlist->head == NULL ) { + dlist->head = new_element; + dlist->head->prev = NULL; + dlist->head->next = NULL; + dlist->tail = new_element; + } + else { + new_element->next = element->next; + new_element->prev = element; + + if ( element->next == NULL ) + dlist->tail = new_element; + else + element->next->prev = new_element; + + element->next = new_element; + } + } + else + ERROR("out of memory"); + + return new_element; +} +/* -->8-- */ + +/* --8<-- dlist_insert_prev */ +struct dlist_element * +dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data) +{ + struct dlist_element *new_element; + + new_element = create_element(data); + if ( new_element ) { + if ( dlist->head == NULL ) { + dlist->head = new_element; + dlist->head->prev = NULL; + dlist->head->next = NULL; + dlist->tail = new_element; + } + else { + new_element->next = element; + new_element->prev = element->prev; + + if ( element->prev == NULL ) + dlist->head = new_element; + else + element->prev->next = new_element; + + element->prev = new_element; + } + } + else + ERROR("out of memory"); + + return new_element; +} +/* -->8-- */ + +/* --8<-- dlist_remove */ +void +dlist_remove(struct dlist *dlist, struct dlist_element *element) +{ + if ( element == dlist->head ) { + dlist->head = element->next; + + if ( dlist->head == NULL ) + dlist->tail = NULL; + else + element->next->prev = NULL; + } + else { + element->prev->next = element->next; + + if ( element->next == NULL ) + dlist->tail = element->prev; + else + element->next->prev = element->prev; + } + + free(element); +} +/* -->8-- */ + +/* --8<-- dlist_free */ +void +dlist_free(struct dlist *dlist) +{ + struct dlist_element *elem, *next; + + for ( elem = dlist->head; elem; elem = next ) { + next = elem->next; + free(elem); + } + + dlist_init(dlist); +} +/* -->8-- */ + +void +dlist_apply_rev(struct dlist *dlist, void (*visit)(T data, void *cl), void *cl) +{ + for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev ) { + visit(elem->data, cl); + } +} + +void +print_list(const char *msg, struct dlist *dlist) +{ + printf("%s:", msg); + + for ( struct dlist_element *elem = dlist->head; elem; elem = elem->next ) + printf(" %d", elem->data); + + putchar('\n'); +} + +void +print_list_rev(const char *msg, struct dlist *dlist) +{ + printf("%s:", msg); + + for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev ) + printf(" %d", elem->data); + + putchar('\n'); +} + +void +remove_if(struct dlist *list) +{ + struct dlist_element *elem, *next; + + for ( elem = list->head; elem; elem = next ) { + next = elem->next; + + if ( (elem->data & 1) == 1 ) { + dlist_remove(list, elem); + } + } +} + +/* --8<-- dlist_merge */ +struct dlist * +dlist_merge(struct dlist *list1, struct dlist *list2) +{ + struct dlist_element *head = NULL, + *cur = NULL, + *e1 = list1->head, + *e2 = list2->head; + + while ( e1 && e2 ) // Solange in e1 UND e2 Elemente sind... + { + if ( e1->data < e2->data ) { + e1->prev = cur; + if ( cur ) + cur->next = e1; + else + head = e1; + cur = e1; + e1 = e1->next; + } + else { + e2->prev = cur; + if ( cur ) + cur->next = e2; + else + head = e2; + cur = e2; + e2 = e2->next; + } + } + + if ( e1 ) // in e1 sind noch Elemente vorhanden! + { + assert(e2 == NULL); + + e1->prev = cur; + if ( cur ) + cur->next = e1; + else + head = e1; + + // list1->tail zeigt bereits auf das letzte Element in list1 + } + else /* if ( e2 ) */ + { + assert(e1 == NULL); + assert(e2); + + e2->prev = cur; + if ( cur ) + cur->next = e2; + else + head = e2; + + list1->tail = list2->tail; // list2->tail ist das Ende der Liste + } + + // Kopf neu setzen... + list1->head = head; + + // Liste2 ist leer + list2->head = NULL; + list2->tail = NULL; + + // Zeiger auf Liste1 zurückliefern + return list1; +} +/* -->8-- */ + +/* --8<-- dlist_sort */ +struct dlist * +dlist_sort(struct dlist *list) +{ + if ( list->head == NULL || list->head->next == NULL ) // Leer oder nur ein Element? => Fertig + return list; + + struct dlist_element *slow = list->head, + *fast = list->head->next; + + while ( fast && fast->next ) + slow = slow->next, fast = fast->next->next; + + struct dlist list1 = { .head = list->head, .tail = slow }, + list2 = { .head = slow->next, .tail = list->tail }; + + list1.tail->next = list2.head->prev = NULL; + + dlist_merge(dlist_sort(&list1), dlist_sort(&list2)); + + list->head = list1.head; + list->tail = list1.tail; + + return list; +} +/* -->8-- */ + +void +merge_test(void) +{ + struct dlist l1, l2; + + dlist_init(&l1); + dlist_init(&l2); + + dlist_push_back(&l1, 7); + dlist_push_back(&l1, 10); + dlist_push_back(&l1, 11); + dlist_push_back(&l1, 19); + dlist_push_back(&l1, 23); + + dlist_push_back(&l2, 4); + dlist_push_back(&l2, 14); + dlist_push_back(&l2, 15); + + struct dlist *ptr; + ptr = dlist_merge(&l1, &l2); + + struct dlist_element *cur; + for ( cur = ptr->head; cur; cur = cur->next ) { + if ( cur->prev ) + printf("%4d", cur->prev->data); + else + printf("xxx "); + printf("%4d", cur->data); + if ( cur->next ) + printf("%4d", cur->next->data); + else + printf(" xxx"); + + puts(""); + } + + dlist_free(&l1); + dlist_free(&l2); +} + +void +ls() +{ + struct dlist list; + + dlist_init(&list); + + for ( int i = 0; i != 30000000; ++i ) + dlist_insert_prev(&list, list.tail, rand() % 9999); + + //print_list("Unsortiert:", &list); + printf("start\n"); + clock_t start = clock(); + dlist_sort(&list); + clock_t ende = clock(); + + printf("Dauer: %.3fsec\n", ((double) ende - start) / CLOCKS_PER_SEC); + //print_list("Sortiert:", &list); + //print_list_rev("Sortiert:", &list); + + dlist_free(&list); +} + +int +main(void) +{ + ls(); + +#if 0 + merge_test(); +#endif + +#if 0 + struct dlist list; + + dlist_init(&list); + + for ( int i = 0; i != 10; ++i ) + dlist_insert_prev(&list, list.tail, i); + + print_list("Ausgabe: ", &list); + + remove_if(&list); + + print_list("Ausgabe: ", &list); + + dlist_free(&list); + + ls(); + + return EXIT_SUCCESS; +#endif +} diff --git a/src/hashtab.c b/src/hashtab.c new file mode 100644 index 0000000..256fac9 --- /dev/null +++ b/src/hashtab.c @@ -0,0 +1,220 @@ +#include +#include +#include +#include +#include + +#include "util.h" + +/* --8<-- hash_type */ +typedef int T; + +struct hash_item { + struct hash_item *next; + char * key; + T data; +}; + +struct hash_tab { + struct hash_item *table[251]; // fit for your needs... +}; +/* -->8-- */ + +/* --8<-- hash_key */ +static unsigned long +hash_key(const unsigned char *str) +{ + unsigned long hash = 5381; + unsigned int c; + + while ( (c = *str++) != '\0' ) + hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + + return hash; +} +/* -->8-- */ + +/* --8<-- hash_init */ +void +hash_init(struct hash_tab *ht) +{ + for ( size_t i = 0; i != NELEM(ht->table); ++i ) + ht->table[i] = NULL; +} +/* -->8-- */ + +/* --8<-- hash_add */ +static struct hash_item * +hash_add(struct hash_item *next, const char *key, T data) +{ + struct hash_item *new_item; + char * new_key; + + new_key = strdup(key); // strdup: not standard but commonly used... + new_item = malloc(sizeof *new_item); + + if ( new_key == NULL || new_item == NULL ) { + free(new_key); + free(new_item); + ERROR("out of memory"); + return NULL; + } + + new_item->next = next; + new_item->key = new_key; + new_item->data = data; + + return new_item; +} +/* -->8-- */ + +/* --8<-- hash_lookup */ +T * +hash_lookup(struct hash_tab *ht, const char *key, T data, int create) +{ + unsigned long h; + struct hash_item *item; + + h = hash_key((const unsigned char *) key) % NELEM(ht->table); + for ( item = ht->table[h]; item; item = item->next ) + if ( strcmp(key, item->key) == 0 ) + return &item->data; + + // not found! create? + if ( create ) { + item = hash_add(ht->table[h], key, data); + if ( item ) + ht->table[h] = item; + else + ERROR("can't create item"); + } + + return item ? &item->data : NULL; +} +/* -->8-- */ + +/* --8<-- hash_delete */ +bool +hash_delete(struct hash_tab *ht, const char *key) +{ + unsigned long h; + struct hash_item *prev, *p; + + h = hash_key((const unsigned char *) key) % NELEM(ht->table); + prev = NULL; + for ( p = ht->table[h]; p; p = p->next ) { + if ( strcmp(key, p->key) == 0 ) { + if ( prev == NULL ) + ht->table[h] = p->next; + else + prev->next = p->next; + + free(p->key); + free(p); + + return true; // successfully removed! + } + prev = p; + } + + return false; +} +/* -->8-- */ + +/* --8<-- hash_apply */ +void +hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl) +{ + struct hash_item *item; + + for ( size_t i = 0; i != NELEM(ht->table); ++i ) + for ( item = ht->table[i]; item; item = item->next ) + visit(item->key, item->data, cl); +} +/* -->8-- */ + +/* --8<-- hash_free */ +void +hash_free(struct hash_tab *ht) +{ + struct hash_item *p, *next; + + for ( size_t i = 0; i != NELEM(ht->table); ++i ) { + for ( p = ht->table[i]; p; p = next ) { + next = p->next; + free(p->key); + free(p); + } + ht->table[i] = NULL; + } +} +/* -->8-- */ + +static int +getword(FILE *fp, char *buf, size_t size, int first(int), int rest(int)) +{ + size_t i = 0; + int c; + + c = getc(fp); + for ( ; c != EOF; c = getc(fp) ) + if ( first(c) ) { + if ( i < size - 1 ) + buf[i++] = c; + c = getc(fp); + break; + } + + for ( ; c != EOF && rest(c); c = getc(fp) ) + if ( i < size - 1 ) + buf[i++] = c; + + if ( i < size ) + buf[i] = 0; + else + buf[size - 1] = 0; + + if ( c != EOF ) + ungetc(c, fp); + + return c > 0; +} + +static int +first(int c) +{ + return isalpha(c); +} + +static int +rest(int c) +{ + return isalpha(c) || c == '_'; +} + +static void +print(const char *key, T data, void *cl) +{ + fprintf(cl, "%s: %d\n", key, data); +} + +int +main() +{ + struct hash_tab ht[1]; + char word[100]; + + hash_init(ht); + + while ( getword(stdin, word, sizeof word, first, rest) ) { + T *p = hash_lookup(ht, word, 0, 1); + if ( p ) + ++(*p); + } + + hash_delete(ht, "new_item"); + + hash_apply(ht, print, stdout); + + hash_free(ht); +} diff --git a/src/heap.c b/src/heap.c new file mode 100644 index 0000000..091e761 --- /dev/null +++ b/src/heap.c @@ -0,0 +1,291 @@ +#include +#include +#include +#include +#include + +#include "util.h" + +typedef int T; + +// https://stackoverflow.com/a/22900767 + +#define LEFT(idx) (idx * 2 + 1) +#define RIGHT(idx) (idx * 2 + 2) +#define PARENT(idx) ((idx - 1) / 2) + +static void +swap(T heap[], size_t i, size_t j) +{ + T temp = heap[i]; + heap[i] = heap[j]; + heap[j] = temp; +} + +#define MAX_HEAP 1 + +#if defined(MAX_HEAP) +// MAX-HEAP Implementation +static void +fixup(T heap[], size_t i) +{ + size_t p = PARENT(i); + + while ( i > 0 && heap[p] < heap[i] ) { + swap(heap, p, i); + + i = p; + p = PARENT(i); + } +} + +static void +fixdown(T heap[], size_t i, size_t n) +{ + for ( ;; ) { + const size_t l = LEFT(i); + const size_t r = RIGHT(i); + size_t m = i; + + if ( l < n && heap[m] < heap[l] ) { + m = l; + } + + if ( r < n && heap[m] < heap[r] ) { + m = r; + } + + if ( m == i ) { + break; + } + + swap(heap, m, i); + + i = m; + } +} + +static bool +is_heap(T heap[], size_t n) +{ + for ( size_t i = 0; i < n / 2; ++i ) { + const size_t l = LEFT(i); + const size_t r = RIGHT(i); + + if ( l < n && heap[i] < heap[l] ) { + return false; + } + if ( r < n && heap[i] < heap[r] ) { + return false; + } + } + return true; +} + +#else +// MIN-HEAP Implementation +static void +fixup(T heap[], size_t i) +{ + size_t p = PARENT(i); + + while ( i > 0 && heap[i] < heap[p] ) { + swap(heap, i, p); + + i = p; + p = PARENT(i); + } +} + +static void +fixdown(T heap[], size_t i, size_t n) +{ + for ( ;; ) { + const size_t l = LEFT(i); + const size_t r = RIGHT(i); + size_t m = i; + + if ( l < n && heap[l] < heap[m] ) { + m = l; + } + + if ( r < n && heap[r] < heap[m] ) { + m = r; + } + + if ( m == i ) { + break; + } + + swap(heap, m, i); + + i = m; + } +} + +static bool +is_heap(T heap[], size_t n) +{ + for ( size_t i = 0; i < n / 2; ++i ) { + const size_t l = LEFT(i); + const size_t r = RIGHT(i); + + if ( l < n && heap[i] > heap[l] ) { + return false; + } + if ( r < n && heap[i] > heap[r] ) { + return false; + } + } + return true; +} +#endif + +static void +heapify(T heap[], size_t n) +{ + for ( size_t i = n / 2; i-- > 0; ) { + fixdown(heap, i, n); + } + + assert(is_heap(heap, n)); +} + +static void +my_heapsort(T a[], size_t n) +{ + heapify(a, n); + + while ( n-- ) { + swap(a, 0, n); + fixdown(a, 0, n); + } +} + +// ------------------------------------------- + +struct pq { // Priority Queue + T heap[251]; + size_t sz; +}; + +void +pq_init(struct pq *pq) +{ + pq->sz = 0; +} + +bool +pq_push(struct pq *pq, T data) +{ + if ( pq->sz == NELEM(pq->heap) ) { + return false; + } + + pq->heap[pq->sz] = data; + fixup(pq->heap, pq->sz); + ++pq->sz; + return true; +} + +bool +pq_pop(struct pq *pq, T *data) +{ + if ( pq->sz == 0 ) { + return false; + } + + *data = pq->heap[0]; + --pq->sz; + pq->heap[0] = pq->heap[pq->sz]; + fixdown(pq->heap, 0, pq->sz); + return true; +} + +// ------------------------------------------- + +void +print_heap(T heap[], size_t n) +{ + if ( n ) { + printf("%d", heap[0]); + for ( size_t i = 1; i != n; ++i ) { + printf(", %d", heap[i]); + } + putchar('\n'); + } +} + +void +test_heapsort(void) +{ + static const size_t N = 1000000; + T array[N]; + + puts("fülle...."); + srand(time(NULL)); + for ( size_t idx = 0; idx != NELEM(array); ++idx ) { + array[idx] = rand(); + } + + puts("sortiere...."); + clock_t start = clock(); + my_heapsort(array, NELEM(array)); + clock_t end = clock(); + + puts("teste..."); + for ( size_t idx = 1; idx != NELEM(array); ++idx ) { +#if defined(MAX_HEAP) + if ( array[idx - 1] > array[idx] ) { + fprintf(stderr, "Fehler an Pos: %zu\n", idx); + exit(EXIT_FAILURE); + } +#else + if ( array[idx - 1] < array[idx] ) { + fprintf(stderr, "Fehler an Pos: %zu\n", idx); + exit(EXIT_FAILURE); + } +#endif + } + printf("ok! (%.3lf sec)\n", ((double) end - start) / CLOCKS_PER_SEC); +} + +void +test_pq(void) +{ + struct pq pq[1]; + + pq_init(pq); + + for ( int i = 0; i != 10; ++i ) { + pq_push(pq, rand()); + } + + T data; + while ( pq_pop(pq, &data) ) { + printf("%d\n", data); + } +} + +int +main(void) +{ + test_heapsort(); + test_pq(); +#if 1 // Heap-Testprogramm + // Beispiel aus "Informatik - Datenstrukturen und Konzepte der Abstraktion" + // Kapitel 5.10, Seite 372 ff. + T heap[20] = { 18, 18, 16, 9, 7, 1, 9, 3, 7, 5 }; + + //heapify(heap, 10); + assert(is_heap(heap, 10)); + print_heap(heap, 10); + + //heap[10] = 13; fixup(heap, 10); + swap(heap, 0, 9); + fixdown(heap, 0, 9); + + assert(is_heap(heap, 9)); + print_heap(heap, 9); +#endif +} diff --git a/src/insertsort.c b/src/insertsort.c new file mode 100644 index 0000000..1a30a1a --- /dev/null +++ b/src/insertsort.c @@ -0,0 +1,38 @@ +#include +#include +#include + +#include "util.h" + +typedef int T; + +void +insertsort(T a[], size_t n) +{ + for ( size_t i = 1; i < n; ++i ) { + size_t j = i; + const T value = a[i]; + + for ( ; j > 0 && a[j - 1] > value; --j ) + a[j] = a[j - 1]; + + a[j] = value; + } +} + +int +main(void) +{ + T a[10]; + + srand(time(NULL)); + for ( size_t i = 0; i != NELEM(a); ++i ) + a[i] = rand() % 100; + + insertsort(a, NELEM(a)); + + for ( size_t i = 0; i != NELEM(a); ++i ) + printf("%d ", a[i]); + putchar('\n'); + return EXIT_SUCCESS; +} diff --git a/src/list-tail-node.c b/src/list-tail-node.c new file mode 100644 index 0000000..edfcf31 --- /dev/null +++ b/src/list-tail-node.c @@ -0,0 +1,197 @@ +/* Standard C */ +#include +#include +#include + +/* Project */ +#include "util.h" + +/* --8<-- list_tail_type */ +typedef int T; + +struct list_node { + struct list_node *next; + T data; +}; + +struct list { + struct list_node *head, *tail; +}; +/* -->8-- */ + +/* --8<-- list_tail_init */ +void +list_init(struct list *list) +{ + list->head = NULL; +} +/* -->8-- */ + +/* --8<-- list_tail_create_node */ +static struct list_node * +create_node(struct list_node *next, T data) +{ + struct list_node *node = malloc(sizeof *node); + + if ( node ) { + node->next = next; + node->data = data; + } + return node; +} +/* -->8-- */ + +/* --8<-- list_tail_push_back */ +void +list_push_back(struct list *list, T data) +{ + struct list_node *node = create_node(NULL, data); + + if ( node ) { + if ( list->head == NULL ) { + list->head = node; + } + else { + list->tail->next = node; + } + list->tail = node; + } + else { + ERROR("out of memory"); + } +} +/* -->8-- */ + +/* --8<-- list_tail_front */ +void +list_push_front(struct list *list, T data) +{ + struct list_node *node = create_node(list->head, data); + + if ( node ) { + if ( list->head == NULL ) { // Einfügen in eine leere Liste? + list->tail = node; + } + list->head = node; + } + else { + ERROR("out of memory"); + } +} +/* -->8-- */ + +/* --8<-- list_tail_pop_front */ +bool +list_pop_front(struct list *list, T *data) +{ + if ( list->head ) { + struct list_node *next = list->head->next; + + if ( data ) { + *data = list->head->data; + } + free(list->head); + list->head = next; + + return true; + } + else { + return false; + } +} +/* -->8-- */ + +/* --8<-- list_tail_insert_next */ +void +list_insert_next(struct list *list, struct list_node *node, T data) +{ + if ( node == NULL ) { // Am Anfang einfügen + list_push_front(list, data); + } + else { + struct list_node *new_node = create_node(node->next, data); + + if ( new_node ) { + if ( node->next == NULL ) { // Am Ende einfügen + list->tail = new_node; + } + node->next = new_node; + } + else { + ERROR("out of memory"); + } + } +} +/* -->8-- */ + +/* --8<-- list_tail_delete_next */ +void +list_delete_next(struct list *list, struct list_node *node, T *data) +{ + if ( node == NULL ) { // Am Anfang entfernen + list_pop_front(list, data); + } + else { + if ( node->next ) { + struct list_node *old_node = node->next; + node->next = node->next->next; + + if ( node->next == NULL ) { + list->tail = node; + } + + if ( data ) { + *data = old_node->data; + } + free(old_node); + } + } +} +/* -->8-- */ + +/* --8<-- list_tail_empty */ +bool +list_empty(struct list *list) +{ + return list->head == NULL; +} +/* -->8-- */ + +/* --8<-- list_tail_free */ +void +list_free(struct list *list) +{ + struct list_node *item, *next; + + for ( item = list->head; item; item = next ) { + next = item->next; + free(item); + } +} +/* -->8-- */ + +int +main() +{ + struct list list[1]; + + list_init(list); + + for ( int i = 0; i != 10; ++i ) + list_push_front(list, -i); + + for ( int i = 0; i != 10; ++i ) + list_push_back(list, i); + + while ( !list_empty(list) ) { + int i; + if ( list_pop_front(list, &i) ) + printf("%d\n", i); + else + ERROR("this shouldn't happen!"); + } + + list_free(list); + + return EXIT_SUCCESS; +} diff --git a/src/list.c b/src/list.c new file mode 100644 index 0000000..d18dae4 --- /dev/null +++ b/src/list.c @@ -0,0 +1,264 @@ +/* simple Implementation of single linked lists */ +/* written and placed in the public domain by Thomas Schmucker */ + +/* Standard C */ +#include +#include +#include + +/* Project */ +#include "util.h" + +/* --8<-- list_type */ +typedef int T; + +struct list_item { + struct list_item *next; + T data; +}; +/* -->8-- */ + +/* --8<-- list_add */ +struct list_item * +list_add(struct list_item *next, T data) +{ + struct list_item *new_item; + + new_item = malloc(sizeof *new_item); + if ( new_item ) { + new_item->data = data; + new_item->next = next; + } + else { + ERROR("out of memory"); + } + + return new_item; +} +/* -->8-- */ + +/* --8<-- list_insert_next */ +void +list_insert_next(struct list_item *list, T data) +{ + struct list_item *new_item; + + new_item = list_add(list->next, data); + if ( new_item ) { + list->next = new_item; + } + else { + ERROR("out of memory"); + } +} +/* -->8-- */ + +/* --8<-- list_delete */ +struct list_item * +list_delete(struct list_item *list, T data) +{ + struct list_item *prev = NULL; + + for ( struct list_item *p = list; p; p = p->next ) { + if ( p->data == data ) { + if ( prev == NULL ) { /* first element in list? */ + list = p->next; + } + else { + prev->next = p->next; + } + + free(p); + + return list; + } + prev = p; + } +#ifdef LIST_REPORT_ERROR + ERROR("data not found"); +#endif + return list; +} +/* -->8-- */ + +/* --8<-- list_delete_next */ +void +list_delete_next(struct list_item *list) +{ + if ( list->next ) { + struct list_item *temp = list->next; + + list->next = list->next->next; + + free(temp); + } +} +/* -->8-- */ + +/* --8<-- list_length */ +size_t +list_length(struct list_item *list) +{ + size_t len = 0; + + for ( ; list; list = list->next ) { + ++len; + } + + return len; +} +/* -->8-- */ + +/* --8<-- list_copy */ +struct list_item * +list_copy(struct list_item *list) +{ + struct list_item *head = NULL, **p = &head; + + for ( ; list; list = list->next ) { + *p = malloc(sizeof **p); + if ( *p ) { + (*p)->data = list->data; // copy elements + p = &(*p)->next; + } + else { + ERROR("out of memory"); + } + } + *p = NULL; + return head; +} +/* -->8-- */ + +/* --8<-- list_reverse */ +struct list_item * +list_reverse(struct list_item *list) +{ + struct list_item *head = NULL, *next; + + for ( ; list; list = next ) { + next = list->next; + list->next = head; + head = list; + } + return head; +} +/* -->8-- */ + +/* --8<-- list_apply */ +void +list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl) +{ + for ( ; list; list = list->next ) { + visit(list->data, cl); + } +} +/* -->8-- */ + +/* --8<-- list_merge */ +struct list_item * +list_merge(struct list_item *a, struct list_item *b) +{ + struct list_item dummy = { .next = NULL }; + struct list_item *head = &dummy, *c = head; + + while ( a && b ) + if ( a->data < b->data ) { + c->next = a, c = a, a = a->next; + } + else { + c->next = b, c = b, b = b->next; + } + + c->next = a ? a : b; + + return head->next; +} +/* -->8-- */ + +/* --8<-- list_sort */ +struct list_item * +list_sort(struct list_item *c) +{ + if ( c == NULL || c->next == NULL ) + return c; + + struct list_item *a = c, + *b = c->next; + + while ( b && b->next ) { + c = c->next, b = b->next->next; + } + + b = c->next, c->next = NULL; + + return list_merge(list_sort(a), list_sort(b)); +} +/* -->8-- */ + +/* --8<-- list_free */ +void +list_free(struct list_item *list) +{ + struct list_item *next; + + for ( ; list; list = next ) { + next = list->next; + free(list); + } +} +/* -->8-- */ + +/* --8<-- list_apply_sample */ +static void +print_data(T data, void *cl) +{ + fprintf(cl, "%d\n", data); +} +/* -->8-- */ + +int +main() +{ + clock_t start; + + /* + struct list_item *mylist = NULL; + + mylist = list_add(mylist, 42); + mylist = list_add(mylist, 43); + mylist = list_add(mylist, 44); + + mylist = list_delete(mylist, 45); + + list_apply(mylist, print_data, stdout); + + struct list_item *mylist2 = list_reverse(list_copy(mylist)); + + list_free(mylist); + list_apply(mylist2, print_data); + list_free(mylist2); + */ + + srand(time(NULL)); + + static const int COUNT = 10000000; + + struct list_item *x = NULL; + for ( int i = 0; i != COUNT; ++i ) { + int r = rand(); + x = list_add(x, r); + } + + puts("start"); + start = clock(); + x = list_sort(x); + printf("Fertig: %.3lf sec\n", (double) (clock() - start) / CLOCKS_PER_SEC); + + //list_apply(x, print_data); + printf("Len: %zu\n", list_length(x)); + + list_free(x); + + return EXIT_SUCCESS; +} diff --git a/src/queue.c b/src/queue.c new file mode 100644 index 0000000..6a472ee --- /dev/null +++ b/src/queue.c @@ -0,0 +1,115 @@ +/* Standard C */ +#include +#include +#include + +/* Project */ +#include "util.h" + +/* --8<-- queue_type */ +typedef int T; + +struct queue_item { + struct queue_item *next; + T data; +}; + +struct queue { + struct queue_item *head, *tail; +}; +/* -->8-- */ + +/* --8<-- queue_init */ +void +queue_init(struct queue *queue) +{ + queue->head = NULL; +} +/* -->8-- */ + +/* --8<-- queue_put */ +void +queue_put(struct queue *queue, T data) +{ + struct queue_item *new_item; + + if ( (new_item = malloc(sizeof *new_item)) != NULL ) { + struct queue_item *tmp = queue->tail; + new_item->data = data; + new_item->next = NULL; + queue->tail = new_item; + if ( queue->head == NULL ) + queue->head = queue->tail; + else + tmp->next = queue->tail; + } + else { + ERROR("out of memory"); + } +} +/* -->8-- */ + +/* --8<-- queue_get */ +bool +queue_get(struct queue *queue, T *data) +{ + if ( queue->head ) { + struct queue_item *next = queue->head->next; + + if ( data ) { + *data = queue->head->data; + } + free(queue->head); + queue->head = next; + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- queue_empty */ +bool +queue_empty(struct queue *queue) +{ + return queue->head == NULL; +} +/* -->8-- */ + +/* --8<-- queue_free */ +void +queue_free(struct queue *queue) +{ + struct queue_item *item, *next; + + for ( item = queue->head; item; item = next ) { + next = item->next; + free(item); + } +} +/* -->8-- */ + +int +main() +{ + struct queue queue[1]; + + queue_init(queue); + + for ( int i = 0; i != 10; ++i ) { + queue_put(queue, i); + } + + while ( !queue_empty(queue) ) { + int i; + if ( queue_get(queue, &i) ) + printf("%d\n", i); + else + ERROR("this shouldn't happen!"); + } + + queue_free(queue); + + return EXIT_SUCCESS; +} diff --git a/src/quicksort.c b/src/quicksort.c new file mode 100644 index 0000000..4657dcd --- /dev/null +++ b/src/quicksort.c @@ -0,0 +1,684 @@ +#include +#include +#include +#include + +#include "util.h" + +static int +bigrand(void) +{ + int x = (rand() << 24) | (rand() << 16) | (rand() << 8) | rand(); + if ( x < 0 ) + return -x; + return x; +} + +static int +randint(int l, int u) +{ + return l + bigrand() % (u - l + 1); +} + +typedef int T; + +static const int CUTOFF = 128; + +static inline void +swap(T a[], int i, int j) +{ + T t = a[i]; + a[i] = a[j]; + a[j] = t; +} + +static void +insertsort(T a[], int n) +{ + int i, j; + for ( i = 1; i < n; ++i ) { + T t = a[i]; + for ( j = i; j > 0 && a[j - 1] > t; --j ) + a[j] = a[j - 1]; + a[j] = t; + } +} + +static void +quicksort(T a[], int n) +{ + int i, last; + + if ( n <= CUTOFF ) + return; + + swap(a, 0, bigrand() % n); + + last = 0; + for ( i = 1; i < n; ++i ) + if ( a[i] < a[0] ) + swap(a, ++last, i); + + swap(a, 0, last); + + quicksort(a, last); + quicksort(a + last + 1, n - last - 1); +} + +void +my_quicksort(T a[], int n) +{ + quicksort(a, n); + insertsort(a, n); +} + +static int +cmp(const void *a, const void *b) +{ + const int *pa = (const T *) a; + const int *pb = (const T *) b; + + if ( *pa < *pb ) + return -1; + if ( *pa > *pb ) + return 1; + return 0; +} + +void +c_quicksort(T a[], int n) +{ + assert(n >= 0); + qsort(a, (size_t) n, sizeof(T), cmp); +} + +/* This function takes last element as pivot, places + the pivot element at its correct position in sorted + array, and places all smaller (smaller than pivot) + to left of pivot and all greater elements to right + of pivot */ +int +partition(int arr[], int low, int high) +{ + int pivot = arr[high]; // pivot + int i = (low - 1); // Index of smaller element + + for ( int j = low; j <= high - 1; j++ ) { + // If current element is smaller than or + // equal to pivot + if ( arr[j] <= pivot ) { + i++; // increment index of smaller element + swap(arr, i, j); + } + } + swap(arr, i + 1, high); + return (i + 1); +} + +/* The main function that implements QuickSort + arr[] --> Array to be sorted, + low --> Starting index, + high --> Ending index */ +void +quickSort(int arr[], int low, int high) +{ + while ( low < high ) { + /* pi is partitioning index, arr[p] is now + at right place */ + int pi = partition(arr, low, high); + + if ( pi - low < high - pi ) { + quickSort(arr, low, pi - 1); + low = pi + 1; + } + else { + quickSort(arr, pi + 1, high); + high = pi - 1; + } + } +} + +void +g4g_quicksort(T a[], int n) +{ + quickSort(a, 0, n - 1); +} + +static void +three_way_quicksort(int a[], int l, int r) +{ + int k; + T v = a[r]; + + if ( r <= l ) + return; + + int i = l - 1, j = r, p = l - 1, q = r; + + for ( ;; ) { + while ( a[++i] < v ) + ; + while ( v < a[--j] ) + if ( j == l ) + break; + if ( i >= j ) + break; + + swap(a, i, j); + + if ( a[i] == v ) + swap(a, ++p, i); + if ( v == a[j] ) + swap(a, --q, j); + } + swap(a, i, r); + j = i - 1; + i = i + 1; + + for ( k = l; k <= p; ++k, --j ) + swap(a, k, j); + for ( k = r - 1; k >= q; --k, ++i ) + swap(a, k, i); + + three_way_quicksort(a, l, j); + three_way_quicksort(a, i, r); +} + +void +sed_quicksort(int a[], int n) +{ + three_way_quicksort(a, 0, n - 1); +} + +/* ====================== HEAPSORT ======================= */ + +#define LEFT(idx) (idx * 2 + 1) +#define RIGHT(idx) (idx * 2 + 2) +#define PARENT(idx) ((idx - 1) / 2) + +static void +fixdown(T heap[], int i, int n) +{ + for ( ;; ) { + const int l = LEFT(i); + const int r = RIGHT(i); + int m = i; + + if ( l < n && heap[m] < heap[l] ) + m = l; + + if ( r < n && heap[m] < heap[r] ) + m = r; + + if ( m == i ) + break; + + swap(heap, m, i); + + i = m; + } +} + +static void +heapify(T heap[], int n) +{ + for ( int i = n / 2 - 1; i >= 0; --i ) + fixdown(heap, i, n); +} + +void +my_heapsort(T a[], int n) +{ + heapify(a, n); + + for ( int i = n - 1; i >= 0; --i ) { + swap(a, 0, i); + fixdown(a, 0, i); + } +} + +void +heapsort_bu(T *data, int n) // zu sortierendes Feld und seine Länge +{ + T val; + int parent, child; + int root = n >> 1; // erstes Blatt im Baum + int count = 0; // Zähler für Anzahl der Vergleiche + + for ( ;; ) { + if ( root ) { // Teil 1: Konstruktion des Heaps + parent = --root; + val = data[root]; // zu versickernder Wert + } + else if ( --n ) { // Teil 2: eigentliche Sortierung + val = data[n]; // zu versickernder Wert vom Heap-Ende + data[n] = data[0]; // Spitze des Heaps hinter den Heap in + parent = 0; // den sortierten Bereich verschieben + } + else // Heap ist leer; Sortierung beendet + break; + + while ( (child = (parent + 1) << 1) < n ) // zweites (!) Kind; + { // Abbruch am Ende des Heaps + if ( ++count, data[child - 1] > data[child] ) // größeres Kind wählen + --child; + + data[parent] = data[child]; // größeres Kind nach oben rücken + parent = child; // in der Ebene darunter weitersuchen + } + + if ( child == n ) // ein einzelnes Kind am Heap-Ende + { // ist übersprungen worden + if ( ++count, data[--child] >= val ) { // größer als der zu versick- + data[parent] = data[child]; // ernde Wert, also noch nach oben + data[child] = val; // versickerten Wert eintragen + continue; + } + + child = parent; // 1 Ebene nach oben zurück + } + else { + if ( ++count, data[parent] >= val ) { // das Blatt ist größer als der + data[parent] = val; // zu versickernde Wert, der damit + continue; // direkt eingetragen werden kann + } + + child = (parent - 1) >> 1; // 2 Ebenen nach oben zurück + } + + while ( child != root ) // maximal zum Ausgangspunkt zurück + { + parent = (child - 1) >> 1; // den Vergleichswert haben wir bereits + // nach oben verschoben + if ( ++count, data[parent] >= val ) // größer als der zu versickernde + break; // Wert, also Position gefunden + + data[child] = data[parent]; // Rückverschiebung nötig + child = parent; // 1 Ebene nach oben zurück + } + + data[child] = val; // versickerten Wert eintragen + } +} + +/*----------------------------------------------------------------------*/ +/* BOTTOM-UP HEAPSORT */ +/* Written by J. Teuhola ; the original idea is */ +/* probably due to R.W. Floyd. Thereafter it has been used by many */ +/* authors, among others S. Carlsson and I. Wegener. Building the heap */ +/* bottom-up is also due to R. W. Floyd: Treesort 3 (Algorithm 245), */ +/* Communications of the ACM 7, p. 701, 1964. */ +/*----------------------------------------------------------------------*/ + +#define element float + +/*-----------------------------------------------------------------------*/ +/* The sift-up procedure sinks a hole from v[i] to leaf and then sifts */ +/* the original v[i] element from the leaf level up. This is the main */ +/* idea of bottom-up heapsort. */ +/*-----------------------------------------------------------------------*/ +static void +siftup(T v[], int i, int n) +{ + int j, start; + T x; + + start = i; + x = v[i]; + j = i << 1; + while ( j <= n ) { + if ( j < n ) + if ( v[j] < v[j + 1] ) + j++; + v[i] = v[j]; + i = j; + j = i << 1; + } + j = i >> 1; + while ( j >= start ) { + if ( v[j] < x ) { + v[i] = v[j]; + i = j; + j = i >> 1; + } + else + break; + } + v[i] = x; +} /* End of siftup */ + +/*----------------------------------------------------------------------*/ +/* The heapsort procedure; the original array is r[0..n-1], but here */ +/* it is shifted to vector v[1..n], for convenience. */ +/*----------------------------------------------------------------------*/ +void +bottom_up_heapsort(T r[], int n) +{ + int k; + T x; + T * v; + + v = r - 1; /* The address shift */ + + /* Build the heap bottom-up, using siftup. */ + for ( k = n >> 1; k > 1; k-- ) + siftup(v, k, n); + + /* The main loop of sorting follows. The root is swapped with the last */ + /* leaf after each sift-up. */ + for ( k = n; k > 1; k-- ) { + siftup(v, 1, k); + x = v[k]; + v[k] = v[1]; + v[1] = x; + } +} /* End of bottom_up_heapsort */ + +/* ====================== HEAPSORT ======================= */ + +/* ====================== INTROSORT ======================= */ + +static void +introsort(T a[], int n, int h) +{ + int i, last; + + if ( n <= CUTOFF ) + return; + + if ( --h == 1 ) { + my_heapsort(a, n); + return; + } + + swap(a, 0, bigrand() % n); + + last = 0; + for ( i = 1; i < n; ++i ) + if ( a[i] < a[0] ) + swap(a, ++last, i); + + swap(a, 0, last); + + introsort(a, last, h); + introsort(a + last + 1, n - last - 1, h); +} + +void +my_introsort(T a[], int n) +{ + int h = 1; + + for ( int nn = 1; nn < n; nn <<= 1 ) + ++h; + + introsort(a, n, h); + insertsort(a, n); +} + +static void +pp_quicksort_impl(T a[], int l, int u) +{ + if ( u - l < CUTOFF ) + return; + + swap(a, l, randint(l, u)); + + T t = a[l]; + int i = l; + int j = u + 1; + for ( ;; ) { + do + i++; + while ( /*i <= u &&*/ a[i] < t ); + do + j--; + while ( a[j] > t ); + if ( i > j ) + break; + swap(a, i, j); + } + swap(a, l, j); + pp_quicksort_impl(a, l, j - 1); + pp_quicksort_impl(a, j + 1, u); +} + +void +pp_quicksort(T a[], int n) +{ + pp_quicksort_impl(a, 0, n - 1); + insertsort(a, n); +} + +static void +pp_quicksort_impl_it(T a[], int l, int u, int h) +{ + if ( --h == 1 ) { + my_heapsort(a + l, u - l + 1); + return; + } + + while ( u - l >= CUTOFF ) { + swap(a, l, randint(l, u)); + + T t = a[l]; + int i = l; + int j = u + 1; + + for ( ;; ) { + do + i++; + while ( /*i <= u && */ a[i] < t ); + do + j--; + while ( a[j] > t ); + if ( i > j ) + break; + swap(a, i, j); + } + swap(a, l, j); + + if ( j - l < u - j ) { + pp_quicksort_impl_it(a, l, j - 1, h); + l = j + 1; + } + else { + pp_quicksort_impl_it(a, j + 1, u, h); + u = j - 1; + } + } +} + +void +pp_quicksort_it(T a[], int n) +{ + int h = 1; + + for ( int nn = 1; nn < n; nn <<= 1 ) + ++h; + + pp_quicksort_impl_it(a, 0, n - 1, h); + insertsort(a, n); +} + +int +binary_search(T x, T v[], int n) +{ + int low, high; + + low = 0; + high = n - 1; + while ( low <= high ) { + int mid = low + ((high - low) / 2); + if ( x > v[mid] ) + low = mid + 1; + else if ( x < v[mid] ) + high = mid - 1; + else + return mid; + } + return -1; +} + +int +lower_bound(T x, T v[], int n) +{ + int low, high; + + low = 0; + high = n; + while ( low < high ) { + int mid = low + ((high - low) / 2); + + if ( x > v[mid] ) + low = mid + 1; + else + high = mid; + } + return x == v[low] ? low : -1; +} + +int +upper_bound(T x, T v[], int n) +{ + int low, high; + + low = 0; + high = n; + while ( low < high ) { + int mid = low + ((high - low) / 2); + + if ( x >= v[mid] ) + low = mid + 1; + else + high = mid; + } + return (low > 0 && x == v[low - 1]) ? low - 1 : -1; +} + +/* TESTTREIBER */ + +void +gen_testset_random(T a[], int n) +{ + for ( int i = 0; i < n; ++i ) + a[i] = bigrand(); +} + +void +gen_testset_random2(T a[], int n) +{ + for ( int i = 0; i < n; ++i ) + a[i] = bigrand() % 100; +} + +void +gen_testset_asc(T a[], int n) +{ + for ( int i = 0; i < n; ++i ) + a[i] = i; +} + +void +gen_testset_desc(T a[], int n) +{ + for ( int i = n; i >= 0; --i ) + a[i] = i; +} + +void +gen_testset_unique(T a[], int n) +{ + for ( int i = 0; i < n; ++i ) + a[i] = 1; +} + +void +test_sorting(T a[], int n) +{ + for ( int i = 1; i < n; ++i ) + if ( a[i - 1] > a[i] ) { + puts("Fehler!"); + exit(EXIT_SUCCESS); + } +} + +void +do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[], int n)) +{ + T * a; + clock_t start, ende; + + a = malloc(sizeof(T) * (size_t) n); + + (*gen_testset)(a, n); + + start = clock(); + (*do_sort)(a, n); + ende = clock(); + + test_sorting(a, n); + + free(a); + + printf("%10.3lf sec", ((double) ende - start) / CLOCKS_PER_SEC); + fflush(stdout); +} + +void +do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n)) +{ + printf("%-15.15s n=%-10d: ", msg, n); + do_one_test(n, do_sort, gen_testset_random); + do_one_test(n, do_sort, gen_testset_random2); + do_one_test(n, do_sort, gen_testset_asc); + do_one_test(n, do_sort, gen_testset_desc); + do_one_test(n, do_sort, gen_testset_unique); + putchar('\n'); +} + +/* ENDE TESTTREIBER */ + +int +main(void) +{ + const int n = 20000000; + + srand(time(0)); + do_all_tests("my_heapsort", n, my_heapsort); + do_all_tests("heapsort_bu", n, heapsort_bu); + do_all_tests("bottom_up_heapsort", n, bottom_up_heapsort); + do_all_tests("c_quicksort", n, c_quicksort); + //do_all_tests("g4g_quicksort", n, g4g_quicksort); + //do_all_tests("sed_quicksort", n, sed_quicksort); + do_all_tests("my_introsort", n, my_introsort); + //do_all_tests("my_quicksort", n, my_quicksort); + do_all_tests("pp_quicksort", n, pp_quicksort); + do_all_tests("pp_quicksort_it", n, pp_quicksort_it); + + return 0; +} + +#if 0 +int _main(void) +{ + T array[20]; + + for ( int i = 0; i != NELEM(array); ++i ) + array[i] = rand() % 10; + + sort(array, NELEM(array)); + print(array, NELEM(array)); + + int value; + while ( scanf("%d", &value) == 1 && value != -1 ) { + int bs = binary_search(value, array, NELEM(array)); + int lb = lower_bound(value, array, NELEM(array)); + int ub = upper_bound(value, array, NELEM(array)); + + printf("bs: %d - lb: %d - ub: %d\n", bs, lb, ub); + } + + return EXIT_SUCCESS; +} +#endif diff --git a/src/random.h b/src/random.h new file mode 100644 index 0000000..9094d5b --- /dev/null +++ b/src/random.h @@ -0,0 +1,47 @@ +#ifndef ITS1_RANDOM_H_INCLUDED +#define ITS1_RANDOM_H_INCLUDED + +#ifdef __cplusplus +extern "C" { +#endif + +struct random_ctx { + unsigned char (*get_byte)(struct random_ctx *ctx); +}; + +static unsigned char +random_get_byte(struct random_ctx *ctx) +{ + return ctx->get_byte(ctx); +} + +static unsigned short +random_get_word(struct random_ctx *ctx) +{ + return (ctx->get_byte(ctx) << 8) + | ctx->get_byte(ctx) + ; +} + +static unsigned long +random_get_dword(struct random_ctx *ctx) +{ + return (ctx->get_byte(ctx) << 24) + | (ctx->get_byte(ctx) << 16) + | (ctx->get_byte(ctx) << 8) + | ctx->get_byte(ctx) + ; +} + +static unsigned long +random_get_dword_range(struct random_ctx *ctx, unsigned long l, unsigned long u) +{ + return l + random_get_dword(ctx) % (u - l + 1); +} + +#ifdef __cplusplus +} +#endif + +#endif /* ITS1_RANDOM_H_INCLUDED */ + diff --git a/src/rb.c b/src/rb.c new file mode 100644 index 0000000..7c2d2c1 --- /dev/null +++ b/src/rb.c @@ -0,0 +1,614 @@ +/* + Implementierung übernommen von: https://web.archive.org/web/20140328232325/http://en.literateprograms.org/Red-black_tree_(C) + */ + +#include +#include +#include + +#include "util.h" + +/* The authors of this work have released all rights to it and placed it +in the public domain under the Creative Commons CC0 1.0 waiver +(http://creativecommons.org/publicdomain/zero/1.0/). + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567 +*/ + +enum rbtree_node_color { RED, + BLACK }; + +typedef struct rbtree_node_t { + void * key; + void * value; + struct rbtree_node_t * left; + struct rbtree_node_t * right; + struct rbtree_node_t * parent; + enum rbtree_node_color color; +} * rbtree_node; + +typedef struct rbtree_t { + rbtree_node root; +} * rbtree; + +typedef int (*compare_func)(void *left, void *right); + +rbtree rbtree_create(); +void * rbtree_lookup(rbtree t, void *key, compare_func compare); +void rbtree_insert(rbtree t, void *key, void *value, compare_func compare); +void rbtree_delete(rbtree t, void *key, compare_func compare); + +#include +#include + +typedef rbtree_node node; +typedef enum rbtree_node_color color; + +static node grandparent(node n); +static node sibling(node n); +static node uncle(node n); +static void verify_properties(rbtree t); +static void verify_property_1(node root); +static void verify_property_2(node root); +static color node_color(node n); +static void verify_property_4(node root); +static void verify_property_5(node root); +static void verify_property_5_helper(node n, int black_count, int *black_count_path); + +static node new_node(void *key, void *value, color node_color, node left, node right); +static node lookup_node(rbtree t, void *key, compare_func compare); +static void rotate_left(rbtree t, node n); +static void rotate_right(rbtree t, node n); + +static void replace_node(rbtree t, node oldn, node newn); +static void insert_case1(rbtree t, node n); +static void insert_case2(rbtree t, node n); +static void insert_case3(rbtree t, node n); +static void insert_case4(rbtree t, node n); +static void insert_case5(rbtree t, node n); +static node maximum_node(node root); +static void delete_case1(rbtree t, node n); +static void delete_case2(rbtree t, node n); +static void delete_case3(rbtree t, node n); +static void delete_case4(rbtree t, node n); +static void delete_case5(rbtree t, node n); +static void delete_case6(rbtree t, node n); + +node +grandparent(node n) +{ + assert(n != NULL); + assert(n->parent != NULL); /* Not the root node */ + assert(n->parent->parent != NULL); /* Not child of root */ + return n->parent->parent; +} + +node +sibling(node n) +{ + assert(n != NULL); + assert(n->parent != NULL); /* Root node has no sibling */ + if ( n == n->parent->left ) + return n->parent->right; + else + return n->parent->left; +} + +node +uncle(node n) +{ + assert(n != NULL); + assert(n->parent != NULL); /* Root node has no uncle */ + assert(n->parent->parent != NULL); /* Children of root have no uncle */ + return sibling(n->parent); +} + +void +verify_properties(rbtree t) +{ + (void) t; +#ifdef VERIFY_RBTREE + verify_property_1(t->root); + verify_property_2(t->root); + /* Property 3 is implicit */ + verify_property_4(t->root); + verify_property_5(t->root); +#endif +} + +void +verify_property_1(node n) +{ + assert(node_color(n) == RED || node_color(n) == BLACK); + if ( n == NULL ) + return; + verify_property_1(n->left); + verify_property_1(n->right); +} + +void +verify_property_2(node root) +{ + assert(node_color(root) == BLACK); +} + +color +node_color(node n) +{ + return n == NULL ? BLACK : n->color; +} + +void +verify_property_4(node n) +{ + if ( node_color(n) == RED ) { + assert(node_color(n->left) == BLACK); + assert(node_color(n->right) == BLACK); + assert(node_color(n->parent) == BLACK); + } + if ( n == NULL ) + return; + verify_property_4(n->left); + verify_property_4(n->right); +} + +void +verify_property_5(node root) +{ + int black_count_path = -1; + verify_property_5_helper(root, 0, &black_count_path); +} + +void +verify_property_5_helper(node n, int black_count, int *path_black_count) +{ + if ( node_color(n) == BLACK ) { + black_count++; + } + if ( n == NULL ) { + if ( *path_black_count == -1 ) { + *path_black_count = black_count; + } + else { + assert(black_count == *path_black_count); + } + return; + } + verify_property_5_helper(n->left, black_count, path_black_count); + verify_property_5_helper(n->right, black_count, path_black_count); +} + +rbtree +rbtree_create() +{ + rbtree t = malloc(sizeof *t); + t->root = NULL; + verify_properties(t); + return t; +} + +node +new_node(void *key, void *value, color node_color, node left, node right) +{ + node result = malloc(sizeof *result); + result->key = key; + result->value = value; + result->color = node_color; + result->left = left; + result->right = right; + if ( left != NULL ) + left->parent = result; + if ( right != NULL ) + right->parent = result; + result->parent = NULL; + return result; +} + +node +lookup_node(rbtree t, void *key, compare_func compare) +{ + node n = t->root; + while ( n != NULL ) { + int comp_result = compare(key, n->key); + if ( comp_result == 0 ) { + return n; + } + else if ( comp_result < 0 ) { + n = n->left; + } + else { + assert(comp_result > 0); + n = n->right; + } + } + return n; +} + +void * +rbtree_lookup(rbtree t, void *key, compare_func compare) +{ + node n = lookup_node(t, key, compare); + return n == NULL ? NULL : n->value; +} + +void +rotate_left(rbtree t, node n) +{ + node r = n->right; + replace_node(t, n, r); + n->right = r->left; + if ( r->left != NULL ) { + r->left->parent = n; + } + r->left = n; + n->parent = r; +} + +void +rotate_right(rbtree t, node n) +{ + node L = n->left; + replace_node(t, n, L); + n->left = L->right; + if ( L->right != NULL ) { + L->right->parent = n; + } + L->right = n; + n->parent = L; +} + +void +replace_node(rbtree t, node oldn, node newn) +{ + if ( oldn->parent == NULL ) { + t->root = newn; + } + else { + if ( oldn == oldn->parent->left ) + oldn->parent->left = newn; + else + oldn->parent->right = newn; + } + if ( newn != NULL ) { + newn->parent = oldn->parent; + } +} + +void +rbtree_insert(rbtree t, void *key, void *value, compare_func compare) +{ + node inserted_node = new_node(key, value, RED, NULL, NULL); + if ( t->root == NULL ) { + t->root = inserted_node; + } + else { + node n = t->root; + while ( 1 ) { + int comp_result = compare(key, n->key); + if ( comp_result == 0 ) { + n->value = value; + return; + } + else if ( comp_result < 0 ) { + if ( n->left == NULL ) { + n->left = inserted_node; + break; + } + else { + n = n->left; + } + } + else { + assert(comp_result > 0); + if ( n->right == NULL ) { + n->right = inserted_node; + break; + } + else { + n = n->right; + } + } + } + inserted_node->parent = n; + } + insert_case1(t, inserted_node); + verify_properties(t); +} + +void +insert_case1(rbtree t, node n) +{ + if ( n->parent == NULL ) + n->color = BLACK; + else + insert_case2(t, n); +} + +void +insert_case2(rbtree t, node n) +{ + if ( node_color(n->parent) == BLACK ) + return; /* Tree is still valid */ + else + insert_case3(t, n); +} + +void +insert_case3(rbtree t, node n) +{ + if ( node_color(uncle(n)) == RED ) { + n->parent->color = BLACK; + uncle(n)->color = BLACK; + grandparent(n)->color = RED; + insert_case1(t, grandparent(n)); + } + else { + insert_case4(t, n); + } +} + +void +insert_case4(rbtree t, node n) +{ + if ( n == n->parent->right && n->parent == grandparent(n)->left ) { + rotate_left(t, n->parent); + n = n->left; + } + else if ( n == n->parent->left && n->parent == grandparent(n)->right ) { + rotate_right(t, n->parent); + n = n->right; + } + insert_case5(t, n); +} + +void +insert_case5(rbtree t, node n) +{ + n->parent->color = BLACK; + grandparent(n)->color = RED; + if ( n == n->parent->left && n->parent == grandparent(n)->left ) { + rotate_right(t, grandparent(n)); + } + else { + assert(n == n->parent->right && n->parent == grandparent(n)->right); + rotate_left(t, grandparent(n)); + } +} + +void +rbtree_delete(rbtree t, void *key, compare_func compare) +{ + node child; + node n = lookup_node(t, key, compare); + if ( n == NULL ) + return; /* Key not found, do nothing */ + if ( n->left != NULL && n->right != NULL ) { + /* Copy key/value from predecessor and then delete it instead */ + node pred = maximum_node(n->left); + n->key = pred->key; + n->value = pred->value; + n = pred; + } + + assert(n->left == NULL || n->right == NULL); + child = n->right == NULL ? n->left : n->right; + if ( node_color(n) == BLACK ) { + n->color = node_color(child); + delete_case1(t, n); + } + replace_node(t, n, child); + if ( n->parent == NULL && child != NULL ) // root should be black + child->color = BLACK; + free(n); + + verify_properties(t); +} + +static node +maximum_node(node n) +{ + assert(n != NULL); + while ( n->right != NULL ) { + n = n->right; + } + return n; +} + +void +delete_case1(rbtree t, node n) +{ + if ( n->parent == NULL ) + return; + else + delete_case2(t, n); +} + +void +delete_case2(rbtree t, node n) +{ + if ( node_color(sibling(n)) == RED ) { + n->parent->color = RED; + sibling(n)->color = BLACK; + if ( n == n->parent->left ) + rotate_left(t, n->parent); + else + rotate_right(t, n->parent); + } + delete_case3(t, n); +} + +void +delete_case3(rbtree t, node n) +{ + if ( node_color(n->parent) == BLACK && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->left) == BLACK && + node_color(sibling(n)->right) == BLACK ) { + sibling(n)->color = RED; + delete_case1(t, n->parent); + } + else + delete_case4(t, n); +} + +void +delete_case4(rbtree t, node n) +{ + if ( node_color(n->parent) == RED && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->left) == BLACK && + node_color(sibling(n)->right) == BLACK ) { + sibling(n)->color = RED; + n->parent->color = BLACK; + } + else + delete_case5(t, n); +} + +void +delete_case5(rbtree t, node n) +{ + if ( n == n->parent->left && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->left) == RED && + node_color(sibling(n)->right) == BLACK ) { + sibling(n)->color = RED; + sibling(n)->left->color = BLACK; + rotate_right(t, sibling(n)); + } + else if ( n == n->parent->right && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->right) == RED && + node_color(sibling(n)->left) == BLACK ) { + sibling(n)->color = RED; + sibling(n)->right->color = BLACK; + rotate_left(t, sibling(n)); + } + delete_case6(t, n); +} + +void +delete_case6(rbtree t, node n) +{ + sibling(n)->color = node_color(n->parent); + n->parent->color = BLACK; + if ( n == n->parent->left ) { + assert(node_color(sibling(n)->right) == RED); + sibling(n)->right->color = BLACK; + rotate_left(t, n->parent); + } + else { + assert(node_color(sibling(n)->left) == RED); + sibling(n)->left->color = BLACK; + rotate_right(t, n->parent); + } +} + +/* The authors of this work have released all rights to it and placed it +in the public domain under the Creative Commons CC0 1.0 waiver +(http://creativecommons.org/publicdomain/zero/1.0/). + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567 +*/ + +#include +#include +#include /* rand() */ + +static int compare_int(void *left, void *right); +static void print_tree(rbtree t); +static void print_tree_helper(rbtree_node n, int indent); + +int +compare_int(void *leftp, void *rightp) +{ + int left = (int) leftp; + int right = (int) rightp; + if ( left < right ) + return -1; + else if ( left > right ) + return 1; + else { + assert(left == right); + return 0; + } +} + +#define INDENT_STEP 4 + +void print_tree_helper(rbtree_node n, int indent); + +void +print_tree(rbtree t) +{ + print_tree_helper(t->root, 0); + puts(""); +} + +void +print_tree_helper(rbtree_node n, int indent) +{ + int i; + if ( n == NULL ) { + fputs("", stdout); + return; + } + if ( n->right != NULL ) { + print_tree_helper(n->right, indent + INDENT_STEP); + } + for ( i = 0; i < indent; i++ ) + fputs(" ", stdout); + if ( n->color == BLACK ) + printf("%d\n", (int) n->key); + else + printf("<%d>\n", (int) n->key); + if ( n->left != NULL ) { + print_tree_helper(n->left, indent + INDENT_STEP); + } +} + +int +main() +{ + int i; + rbtree t = rbtree_create(); + + for ( i = 0; i < 50; i++ ) { + long x = rand() % 10000; + long y = rand() % 10000; +#ifdef TRACE + print_tree(t); + printf("Inserting %ld -> %ld\n\n", x, y); +#endif + rbtree_insert(t, (void *) x, (void *) y, compare_int); + assert(rbtree_lookup(t, (void *) x, compare_int) == (void *) y); + } + + print_tree(t); + + for ( i = 0; i < 60000; i++ ) { + long x = rand() % 10000; +#ifdef TRACE + print_tree(t); + printf("Deleting key %ld\n\n", x); +#endif + rbtree_delete(t, (void *) x, compare_int); + } + return 0; +} diff --git a/src/rc4.c b/src/rc4.c new file mode 100644 index 0000000..8a67303 --- /dev/null +++ b/src/rc4.c @@ -0,0 +1,156 @@ +#include +#include +#include /* memset() */ + +#include "random.h" +#include "util.h" + +struct rc4_ctx { + struct random_ctx ctx; + + unsigned int i; + unsigned int j; + unsigned char S[256]; +}; + +static void +swap(unsigned char a[], unsigned int i, unsigned int j) +{ + unsigned char t = a[i]; + a[i] = a[j]; + a[j] = t; +} + +unsigned char +rc4_get_byte(struct rc4_ctx *ctx) +{ + ctx->i = (ctx->i + 1) % 256; + ctx->j = (ctx->j + ctx->S[ctx->i]) % 256; + swap(ctx->S, ctx->i, ctx->j); + + return ctx->S[(ctx->S[ctx->i] + ctx->S[ctx->j]) % 256]; +} + +void +rc4_init(struct rc4_ctx *ctx, void *key, size_t sz) +{ + const unsigned char *K = key; + unsigned int i, j; + + for ( i = 0; i != 256; ++i ) + ctx->S[i] = i; + + for ( i = j = 0; i != 256; ++i ) { + j = (j + ctx->S[i] + K[i % sz]) % 256; + swap(ctx->S, i, j); + } + + ctx->i = 0; + ctx->j = 0; + ctx->ctx.get_byte = (unsigned char (*)(struct random_ctx *)) rc4_get_byte; +} + +void +rc4_clear(struct rc4_ctx *ctx) +{ + memset(ctx, 0, sizeof *ctx); +} + +struct random_ctx * +rc4_create(void *key, size_t sz) +{ + struct rc4_ctx *ctx; + + ctx = malloc(sizeof(*ctx)); + if ( ctx ) { + rc4_init(ctx, key, sz); + + return &(ctx->ctx); + } + + return NULL; +} + +void +rc4_free(struct random_ctx *ctx) +{ + rc4_clear((struct rc4_ctx *) ctx); + free(ctx); +} + +void +rc4_test(void) +{ + static struct { + char * key; + unsigned int sz; + struct { + unsigned int pos; + unsigned char bytes[16]; + } test[18]; + } cases[] = { + { "\x01\x02\x03\x04\x05", 5, { { 0, "\xb2\x39\x63\x05\xf0\x3d\xc0\x27\xcc\xc3\x52\x4a\x0a\x11\x18\xa8" }, { 16, "\x69\x82\x94\x4f\x18\xfc\x82\xd5\x89\xc4\x03\xa4\x7a\x0d\x09\x19" }, { 240, "\x28\xcb\x11\x32\xc9\x6c\xe2\x86\x42\x1d\xca\xad\xb8\xb6\x9e\xae" }, { 256, "\x1c\xfc\xf6\x2b\x03\xed\xdb\x64\x1d\x77\xdf\xcf\x7f\x8d\x8c\x93" }, { 496, "\x42\xb7\xd0\xcd\xd9\x18\xa8\xa3\x3d\xd5\x17\x81\xc8\x1f\x40\x41" }, { 512, "\x64\x59\x84\x44\x32\xa7\xda\x92\x3c\xfb\x3e\xb4\x98\x06\x61\xf6" }, { 752, "\xec\x10\x32\x7b\xde\x2b\xee\xfd\x18\xf9\x27\x76\x80\x45\x7e\x22" }, { 768, "\xeb\x62\x63\x8d\x4f\x0b\xa1\xfe\x9f\xca\x20\xe0\x5b\xf8\xff\x2b" }, { 1008, "\x45\x12\x90\x48\xe6\xa0\xed\x0b\x56\xb4\x90\x33\x8f\x07\x8d\xa5" }, { 1024, "\x30\xab\xbc\xc7\xc2\x0b\x01\x60\x9f\x23\xee\x2d\x5f\x6b\xb7\xdf" }, { 1520, "\x32\x94\xf7\x44\xd8\xf9\x79\x05\x07\xe7\x0f\x62\xe5\xbb\xce\xea" }, { 1536, "\xd8\x72\x9d\xb4\x18\x82\x25\x9b\xee\x4f\x82\x53\x25\xf5\xa1\x30" }, { 2032, "\x1e\xb1\x4a\x0c\x13\xb3\xbf\x47\xfa\x2a\x0b\xa9\x3a\xd4\x5b\x8b" }, { 2048, "\xcc\x58\x2f\x8b\xa9\xf2\x65\xe2\xb1\xbe\x91\x12\xe9\x75\xd2\xd7" }, { 3056, "\xf2\xe3\x0f\x9b\xd1\x02\xec\xbf\x75\xaa\xad\xe9\xbc\x35\xc4\x3c" }, { 3072, "\xec\x0e\x11\xc4\x79\xdc\x32\x9d\xc8\xda\x79\x68\xfe\x96\x56\x81" }, { 4080, "\x06\x83\x26\xa2\x11\x84\x16\xd2\x1f\x9d\x04\xb2\xcd\x1c\xa0\x50" }, { 4096, "\xff\x25\xb5\x89\x95\x99\x67\x07\xe5\x1f\xbd\xf0\x8b\x34\xd8\x75" } } }, + { "\x01\x02\x03\x04\x05\x06\x07", 7, { { 0, "\x29\x3f\x02\xd4\x7f\x37\xc9\xb6\x33\xf2\xaf\x52\x85\xfe\xb4\x6b" }, { 16, "\xe6\x20\xf1\x39\x0d\x19\xbd\x84\xe2\xe0\xfd\x75\x20\x31\xaf\xc1" }, { 240, "\x91\x4f\x02\x53\x1c\x92\x18\x81\x0d\xf6\x0f\x67\xe3\x38\x15\x4c" }, { 256, "\xd0\xfd\xb5\x83\x07\x3c\xe8\x5a\xb8\x39\x17\x74\x0e\xc0\x11\xd5" }, { 496, "\x75\xf8\x14\x11\xe8\x71\xcf\xfa\x70\xb9\x0c\x74\xc5\x92\xe4\x54" }, { 512, "\x0b\xb8\x72\x02\x93\x8d\xad\x60\x9e\x87\xa5\xa1\xb0\x79\xe5\xe4" }, { 752, "\xc2\x91\x12\x46\xb6\x12\xe7\xe7\xb9\x03\xdf\xed\xa1\xda\xd8\x66" }, { 768, "\x32\x82\x8f\x91\x50\x2b\x62\x91\x36\x8d\xe8\x08\x1d\xe3\x6f\xc2" }, { 1008, "\xf3\xb9\xa7\xe3\xb2\x97\xbf\x9a\xd8\x04\x51\x2f\x90\x63\xef\xf1" }, { 1024, "\x8e\xcb\x67\xa9\xba\x1f\x55\xa5\xa0\x67\xe2\xb0\x26\xa3\x67\x6f" }, { 1520, "\xd2\xaa\x90\x2b\xd4\x2d\x0d\x7c\xfd\x34\x0c\xd4\x58\x10\x52\x9f" }, { 1536, "\x78\xb2\x72\xc9\x6e\x42\xea\xb4\xc6\x0b\xd9\x14\xe3\x9d\x06\xe3" }, { 2032, "\xf4\x33\x2f\xd3\x1a\x07\x93\x96\xee\x3c\xee\x3f\x2a\x4f\xf0\x49" }, { 2048, "\x05\x45\x97\x81\xd4\x1f\xda\x7f\x30\xc1\xbe\x7e\x12\x46\xc6\x23" }, { 3056, "\xad\xfd\x38\x68\xb8\xe5\x14\x85\xd5\xe6\x10\x01\x7e\x3d\xd6\x09" }, { 3072, "\xad\x26\x58\x1c\x0c\x5b\xe4\x5f\x4c\xea\x01\xdb\x2f\x38\x05\xd5" }, { 4080, "\xf3\x17\x2c\xef\xfc\x3b\x3d\x99\x7c\x85\xcc\xd5\xaf\x1a\x95\x0c" }, { 4096, "\xe7\x4b\x0b\x97\x31\x22\x7f\xd3\x7c\x0e\xc0\x8a\x47\xdd\xd8\xb8" } } }, + { "\x01\x02\x03\x04\x05\x06\x07\x08", 8, { { 0, "\x97\xab\x8a\x1b\xf0\xaf\xb9\x61\x32\xf2\xf6\x72\x58\xda\x15\xa8" }, { 16, "\x82\x63\xef\xdb\x45\xc4\xa1\x86\x84\xef\x87\xe6\xb1\x9e\x5b\x09" }, { 240, "\x96\x36\xeb\xc9\x84\x19\x26\xf4\xf7\xd1\xf3\x62\xbd\xdf\x6e\x18" }, { 256, "\xd0\xa9\x90\xff\x2c\x05\xfe\xf5\xb9\x03\x73\xc9\xff\x4b\x87\x0a" }, { 496, "\x73\x23\x9f\x1d\xb7\xf4\x1d\x80\xb6\x43\xc0\xc5\x25\x18\xec\x63" }, { 512, "\x16\x3b\x31\x99\x23\xa6\xbd\xb4\x52\x7c\x62\x61\x26\x70\x3c\x0f" }, { 752, "\x49\xd6\xc8\xaf\x0f\x97\x14\x4a\x87\xdf\x21\xd9\x14\x72\xf9\x66" }, { 768, "\x44\x17\x3a\x10\x3b\x66\x16\xc5\xd5\xad\x1c\xee\x40\xc8\x63\xd0" }, { 1008, "\x27\x3c\x9c\x4b\x27\xf3\x22\xe4\xe7\x16\xef\x53\xa4\x7d\xe7\xa4" }, { 1024, "\xc6\xd0\xe7\xb2\x26\x25\x9f\xa9\x02\x34\x90\xb2\x61\x67\xad\x1d" }, { 1520, "\x1f\xe8\x98\x67\x13\xf0\x7c\x3d\x9a\xe1\xc1\x63\xff\x8c\xf9\xd3" }, { 1536, "\x83\x69\xe1\xa9\x65\x61\x0b\xe8\x87\xfb\xd0\xc7\x91\x62\xaa\xfb" }, { 2032, "\x0a\x01\x27\xab\xb4\x44\x84\xb9\xfb\xef\x5a\xbc\xae\x1b\x57\x9f" }, { 2048, "\xc2\xcd\xad\xc6\x40\x2e\x8e\xe8\x66\xe1\xf3\x7b\xdb\x47\xe4\x2c" }, { 3056, "\x26\xb5\x1e\xa3\x7d\xf8\xe1\xd6\xf7\x6f\xc3\xb6\x6a\x74\x29\xb3" }, { 3072, "\xbc\x76\x83\x20\x5d\x4f\x44\x3d\xc1\xf2\x9d\xda\x33\x15\xc8\x7b" }, { 4080, "\xd5\xfa\x5a\x34\x69\xd2\x9a\xaa\xf8\x3d\x23\x58\x9d\xb8\xc8\x5b" }, { 4096, "\x3f\xb4\x6e\x2c\x8f\x0f\x06\x8e\xdc\xe8\xcd\xcd\x7d\xfc\x58\x62" } } }, + { "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a", 10, { { 0, "\xed\xe3\xb0\x46\x43\xe5\x86\xcc\x90\x7d\xc2\x18\x51\x70\x99\x02" }, { 16, "\x03\x51\x6b\xa7\x8f\x41\x3b\xeb\x22\x3a\xa5\xd4\xd2\xdf\x67\x11" }, { 240, "\x3c\xfd\x6c\xb5\x8e\xe0\xfd\xde\x64\x01\x76\xad\x00\x00\x04\x4d" }, { 256, "\x48\x53\x2b\x21\xfb\x60\x79\xc9\x11\x4c\x0f\xfd\x9c\x04\xa1\xad" }, { 496, "\x3e\x8c\xea\x98\x01\x71\x09\x97\x90\x84\xb1\xef\x92\xf9\x9d\x86" }, { 512, "\xe2\x0f\xb4\x9b\xdb\x33\x7e\xe4\x8b\x8d\x8d\xc0\xf4\xaf\xef\xfe" }, { 752, "\x5c\x25\x21\xea\xcd\x79\x66\xf1\x5e\x05\x65\x44\xbe\xa0\xd3\x15" }, { 768, "\xe0\x67\xa7\x03\x19\x31\xa2\x46\xa6\xc3\x87\x5d\x2f\x67\x8a\xcb" }, { 1008, "\xa6\x4f\x70\xaf\x88\xae\x56\xb6\xf8\x75\x81\xc0\xe2\x3e\x6b\x08" }, { 1024, "\xf4\x49\x03\x1d\xe3\x12\x81\x4e\xc6\xf3\x19\x29\x1f\x4a\x05\x16" }, { 1520, "\xbd\xae\x85\x92\x4b\x3c\xb1\xd0\xa2\xe3\x3a\x30\xc6\xd7\x95\x99" }, { 1536, "\x8a\x0f\xed\xdb\xac\x86\x5a\x09\xbc\xd1\x27\xfb\x56\x2e\xd6\x0a" }, { 2032, "\xb5\x5a\x0a\x5b\x51\xa1\x2a\x8b\xe3\x48\x99\xc3\xe0\x47\x51\x1a" }, { 2048, "\xd9\xa0\x9c\xea\x3c\xe7\x5f\xe3\x96\x98\x07\x03\x17\xa7\x13\x39" }, { 3056, "\x55\x22\x25\xed\x11\x77\xf4\x45\x84\xac\x8c\xfa\x6c\x4e\xb5\xfc" }, { 3072, "\x7e\x82\xcb\xab\xfc\x95\x38\x1b\x08\x09\x98\x44\x21\x29\xc2\xf8" }, { 4080, "\x1f\x13\x5e\xd1\x4c\xe6\x0a\x91\x36\x9d\x23\x22\xbe\xf2\x5e\x3c" }, { 4096, "\x08\xb6\xbe\x45\x12\x4a\x43\xe2\xeb\x77\x95\x3f\x84\xdc\x85\x53" } } }, + { "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10", 16, { { 0, "\x9a\xc7\xcc\x9a\x60\x9d\x1e\xf7\xb2\x93\x28\x99\xcd\xe4\x1b\x97" }, { 16, "\x52\x48\xc4\x95\x90\x14\x12\x6a\x6e\x8a\x84\xf1\x1d\x1a\x9e\x1c" }, { 240, "\x06\x59\x02\xe4\xb6\x20\xf6\xcc\x36\xc8\x58\x9f\x66\x43\x2f\x2b" }, { 256, "\xd3\x9d\x56\x6b\xc6\xbc\xe3\x01\x07\x68\x15\x15\x49\xf3\x87\x3f" }, { 496, "\xb6\xd1\xe6\xc4\xa5\xe4\x77\x1c\xad\x79\x53\x8d\xf2\x95\xfb\x11" }, { 512, "\xc6\x8c\x1d\x5c\x55\x9a\x97\x41\x23\xdf\x1d\xbc\x52\xa4\x3b\x89" }, { 752, "\xc5\xec\xf8\x8d\xe8\x97\xfd\x57\xfe\xd3\x01\x70\x1b\x82\xa2\x59" }, { 768, "\xec\xcb\xe1\x3d\xe1\xfc\xc9\x1c\x11\xa0\xb2\x6c\x0b\xc8\xfa\x4d" }, { 1008, "\xe7\xa7\x25\x74\xf8\x78\x2a\xe2\x6a\xab\xcf\x9e\xbc\xd6\x60\x65" }, { 1024, "\xbd\xf0\x32\x4e\x60\x83\xdc\xc6\xd3\xce\xdd\x3c\xa8\xc5\x3c\x16" }, { 1520, "\xb4\x01\x10\xc4\x19\x0b\x56\x22\xa9\x61\x16\xb0\x01\x7e\xd2\x97" }, { 1536, "\xff\xa0\xb5\x14\x64\x7e\xc0\x4f\x63\x06\xb8\x92\xae\x66\x11\x81" }, { 2032, "\xd0\x3d\x1b\xc0\x3c\xd3\x3d\x70\xdf\xf9\xfa\x5d\x71\x96\x3e\xbd" }, { 2048, "\x8a\x44\x12\x64\x11\xea\xa7\x8b\xd5\x1e\x8d\x87\xa8\x87\x9b\xf5" }, { 3056, "\xfa\xbe\xb7\x60\x28\xad\xe2\xd0\xe4\x87\x22\xe4\x6c\x46\x15\xa3" }, { 3072, "\xc0\x5d\x88\xab\xd5\x03\x57\xf9\x35\xa6\x3c\x59\xee\x53\x76\x23" }, { 4080, "\xff\x38\x26\x5c\x16\x42\xc1\xab\xe8\xd3\xc2\xfe\x5e\x57\x2b\xf8" }, { 4096, "\xa3\x6a\x4c\x30\x1a\xe8\xac\x13\x61\x0c\xcb\xc1\x22\x56\xca\xcc" } } }, + { "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18", 24, { { 0, "\x05\x95\xe5\x7f\xe5\xf0\xbb\x3c\x70\x6e\xda\xc8\xa4\xb2\xdb\x11" }, { 16, "\xdf\xde\x31\x34\x4a\x1a\xf7\x69\xc7\x4f\x07\x0a\xee\x9e\x23\x26" }, { 240, "\xb0\x6b\x9b\x1e\x19\x5d\x13\xd8\xf4\xa7\x99\x5c\x45\x53\xac\x05" }, { 256, "\x6b\xd2\x37\x8e\xc3\x41\xc9\xa4\x2f\x37\xba\x79\xf8\x8a\x32\xff" }, { 496, "\xe7\x0b\xce\x1d\xf7\x64\x5a\xdb\x5d\x2c\x41\x30\x21\x5c\x35\x22" }, { 512, "\x9a\x57\x30\xc7\xfc\xb4\xc9\xaf\x51\xff\xda\x89\xc7\xf1\xad\x22" }, { 752, "\x04\x85\x05\x5f\xd4\xf6\xf0\xd9\x63\xef\x5a\xb9\xa5\x47\x69\x82" }, { 768, "\x59\x1f\xc6\x6b\xcd\xa1\x0e\x45\x2b\x03\xd4\x55\x1f\x6b\x62\xac" }, { 1008, "\x27\x53\xcc\x83\x98\x8a\xfa\x3e\x16\x88\xa1\xd3\xb4\x2c\x9a\x02" }, { 1024, "\x93\x61\x0d\x52\x3d\x1d\x3f\x00\x62\xb3\xc2\xa3\xbb\xc7\xc7\xf0" }, { 1520, "\x96\xc2\x48\x61\x0a\xad\xed\xfe\xaf\x89\x78\xc0\x3d\xe8\x20\x5a" }, { 1536, "\x0e\x31\x7b\x3d\x1c\x73\xb9\xe9\xa4\x68\x8f\x29\x6d\x13\x3a\x19" }, { 2032, "\xbd\xf0\xe6\xc3\xcc\xa5\xb5\xb9\xd5\x33\xb6\x9c\x56\xad\xa1\x20" }, { 2048, "\x88\xa2\x18\xb6\xe2\xec\xe1\xe6\x24\x6d\x44\xc7\x59\xd1\x9b\x10" }, { 3056, "\x68\x66\x39\x7e\x95\xc1\x40\x53\x4f\x94\x26\x34\x21\x00\x6e\x40" }, { 3072, "\x32\xcb\x0a\x1e\x95\x42\xc6\xb3\xb8\xb3\x98\xab\xc3\xb0\xf1\xd5" }, { 4080, "\x29\xa0\xb8\xae\xd5\x4a\x13\x23\x24\xc6\x2e\x42\x3f\x54\xb4\xc8" }, { 4096, "\x3c\xb0\xf3\xb5\x02\x0a\x98\xb8\x2a\xf9\xfe\x15\x44\x84\xa1\x68" } } }, + { "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x20", 32, { { 0, "\xea\xa6\xbd\x25\x88\x0b\xf9\x3d\x3f\x5d\x1e\x4c\xa2\x61\x1d\x91" }, { 16, "\xcf\xa4\x5c\x9f\x7e\x71\x4b\x54\xbd\xfa\x80\x02\x7c\xb1\x43\x80" }, { 240, "\x11\x4a\xe3\x44\xde\xd7\x1b\x35\xf2\xe6\x0f\xeb\xad\x72\x7f\xd8" }, { 256, "\x02\xe1\xe7\x05\x6b\x0f\x62\x39\x00\x49\x64\x22\x94\x3e\x97\xb6" }, { 496, "\x91\xcb\x93\xc7\x87\x96\x4e\x10\xd9\x52\x7d\x99\x9c\x6f\x93\x6b" }, { 512, "\x49\xb1\x8b\x42\xf8\xe8\x36\x7c\xbe\xb5\xef\x10\x4b\xa1\xc7\xcd" }, { 752, "\x87\x08\x4b\x3b\xa7\x00\xba\xde\x95\x56\x10\x67\x27\x45\xb3\x74" }, { 768, "\xe7\xa7\xb9\xe9\xec\x54\x0d\x5f\xf4\x3b\xdb\x12\x79\x2d\x1b\x35" }, { 1008, "\xc7\x99\xb5\x96\x73\x8f\x6b\x01\x8c\x76\xc7\x4b\x17\x59\xbd\x90" }, { 1024, "\x7f\xec\x5b\xfd\x9f\x9b\x89\xce\x65\x48\x30\x90\x92\xd7\xe9\x58" }, { 1520, "\x40\xf2\x50\xb2\x6d\x1f\x09\x6a\x4a\xfd\x4c\x34\x0a\x58\x88\x15" }, { 1536, "\x3e\x34\x13\x5c\x79\xdb\x01\x02\x00\x76\x76\x51\xcf\x26\x30\x73" }, { 2032, "\xf6\x56\xab\xcc\xf8\x8d\xd8\x27\x02\x7b\x2c\xe9\x17\xd4\x64\xec" }, { 2048, "\x18\xb6\x25\x03\xbf\xbc\x07\x7f\xba\xbb\x98\xf2\x0d\x98\xab\x34" }, { 3056, "\x8a\xed\x95\xee\x5b\x0d\xcb\xfb\xef\x4e\xb2\x1d\x3a\x3f\x52\xf9" }, { 3072, "\x62\x5a\x1a\xb0\x0e\xe3\x9a\x53\x27\x34\x6b\xdd\xb0\x1a\x9c\x18" }, { 4080, "\xa1\x3a\x7c\x79\xc7\xe1\x19\xb5\xab\x02\x96\xab\x28\xc3\x00\xb9" }, { 4096, "\xf3\xe4\xc0\xa2\xe0\x2d\x1d\x01\xf7\xf0\xa7\x46\x18\xaf\x2b\x48" } } }, + { "\x83\x32\x22\x77\x2a", 5, { { 0, "\x80\xad\x97\xbd\xc9\x73\xdf\x8a\x2e\x87\x9e\x92\xa4\x97\xef\xda" }, { 16, "\x20\xf0\x60\xc2\xf2\xe5\x12\x65\x01\xd3\xd4\xfe\xa1\x0d\x5f\xc0" }, { 240, "\xfa\xa1\x48\xe9\x90\x46\x18\x1f\xec\x6b\x20\x85\xf3\xb2\x0e\xd9" }, { 256, "\xf0\xda\xf5\xba\xb3\xd5\x96\x83\x98\x57\x84\x6f\x73\xfb\xfe\x5a" }, { 496, "\x1c\x7e\x2f\xc4\x63\x92\x32\xfe\x29\x75\x84\xb2\x96\x99\x6b\xc8" }, { 512, "\x3d\xb9\xb2\x49\x40\x6c\xc8\xed\xff\xac\x55\xcc\xd3\x22\xba\x12" }, { 752, "\xe4\xf9\xf7\xe0\x06\x61\x54\xbb\xd1\x25\xb7\x45\x56\x9b\xc8\x97" }, { 768, "\x75\xd5\xef\x26\x2b\x44\xc4\x1a\x9c\xf6\x3a\xe1\x45\x68\xe1\xb9" }, { 1008, "\x6d\xa4\x53\xdb\xf8\x1e\x82\x33\x4a\x3d\x88\x66\xcb\x50\xa1\xe3" }, { 1024, "\x78\x28\xd0\x74\x11\x9c\xab\x5c\x22\xb2\x94\xd7\xa9\xbf\xa0\xbb" }, { 1520, "\xad\xb8\x9c\xea\x9a\x15\xfb\xe6\x17\x29\x5b\xd0\x4b\x8c\xa0\x5c" }, { 1536, "\x62\x51\xd8\x7f\xd4\xaa\xae\x9a\x7e\x4a\xd5\xc2\x17\xd3\xf3\x00" }, { 2032, "\xe7\x11\x9b\xd6\xdd\x9b\x22\xaf\xe8\xf8\x95\x85\x43\x28\x81\xe2" }, { 2048, "\x78\x5b\x60\xfd\x7e\xc4\xe9\xfc\xb6\x54\x5f\x35\x0d\x66\x0f\xab" }, { 3056, "\xaf\xec\xc0\x37\xfd\xb7\xb0\x83\x8e\xb3\xd7\x0b\xcd\x26\x83\x82" }, { 3072, "\xdb\xc1\xa7\xb4\x9d\x57\x35\x8c\xc9\xfa\x6d\x61\xd7\x3b\x7c\xf0" }, { 4080, "\x63\x49\xd1\x26\xa3\x7a\xfc\xba\x89\x79\x4f\x98\x04\x91\x4f\xdc" }, { 4096, "\xbf\x42\xc3\x01\x8c\x2f\x7c\x66\xbf\xde\x52\x49\x75\x76\x81\x15" } } }, + { "\x19\x10\x83\x32\x22\x77\x2a", 7, { { 0, "\xbc\x92\x22\xdb\xd3\x27\x4d\x8f\xc6\x6d\x14\xcc\xbd\xa6\x69\x0b" }, { 16, "\x7a\xe6\x27\x41\x0c\x9a\x2b\xe6\x93\xdf\x5b\xb7\x48\x5a\x63\xe3" }, { 240, "\x3f\x09\x31\xaa\x03\xde\xfb\x30\x0f\x06\x01\x03\x82\x6f\x2a\x64" }, { 256, "\xbe\xaa\x9e\xc8\xd5\x9b\xb6\x81\x29\xf3\x02\x7c\x96\x36\x11\x81" }, { 496, "\x74\xe0\x4d\xb4\x6d\x28\x64\x8d\x7d\xee\x8a\x00\x64\xb0\x6c\xfe" }, { 512, "\x9b\x5e\x81\xc6\x2f\xe0\x23\xc5\x5b\xe4\x2f\x87\xbb\xf9\x32\xb8" }, { 752, "\xce\x17\x8f\xc1\x82\x6e\xfe\xcb\xc1\x82\xf5\x79\x99\xa4\x61\x40" }, { 768, "\x8b\xdf\x55\xcd\x55\x06\x1c\x06\xdb\xa6\xbe\x11\xde\x4a\x57\x8a" }, { 1008, "\x62\x6f\x5f\x4d\xce\x65\x25\x01\xf3\x08\x7d\x39\xc9\x2c\xc3\x49" }, { 1024, "\x42\xda\xac\x6a\x8f\x9a\xb9\xa7\xfd\x13\x7c\x60\x37\x82\x56\x82" }, { 1520, "\xcc\x03\xfd\xb7\x91\x92\xa2\x07\x31\x2f\x53\xf5\xd4\xdc\x33\xd9" }, { 1536, "\xf7\x0f\x14\x12\x2a\x1c\x98\xa3\x15\x5d\x28\xb8\xa0\xa8\xa4\x1d" }, { 2032, "\x2a\x3a\x30\x7a\xb2\x70\x8a\x9c\x00\xfe\x0b\x42\xf9\xc2\xd6\xa1" }, { 2048, "\x86\x26\x17\x62\x7d\x22\x61\xea\xb0\xb1\x24\x65\x97\xca\x0a\xe9" }, { 3056, "\x55\xf8\x77\xce\x4f\x2e\x1d\xdb\xbf\x8e\x13\xe2\xcd\xe0\xfd\xc8" }, { 3072, "\x1b\x15\x56\xcb\x93\x5f\x17\x33\x37\x70\x5f\xbb\x5d\x50\x1f\xc1" }, { 4080, "\xec\xd0\xe9\x66\x02\xbe\x7f\x8d\x50\x92\x81\x6c\xcc\xf2\xc2\xe9" }, { 4096, "\x02\x78\x81\xfa\xb4\x99\x3a\x1c\x26\x20\x24\xa9\x4f\xff\x3f\x61" } } }, + { "\x64\x19\x10\x83\x32\x22\x77\x2a", 8, { { 0, "\xbb\xf6\x09\xde\x94\x13\x17\x2d\x07\x66\x0c\xb6\x80\x71\x69\x26" }, { 16, "\x46\x10\x1a\x6d\xab\x43\x11\x5d\x6c\x52\x2b\x4f\xe9\x36\x04\xa9" }, { 240, "\xcb\xe1\xff\xf2\x1c\x96\xf3\xee\xf6\x1e\x8f\xe0\x54\x2c\xbd\xf0" }, { 256, "\x34\x79\x38\xbf\xfa\x40\x09\xc5\x12\xcf\xb4\x03\x4b\x0d\xd1\xa7" }, { 496, "\x78\x67\xa7\x86\xd0\x0a\x71\x47\x90\x4d\x76\xdd\xf1\xe5\x20\xe3" }, { 512, "\x8d\x3e\x9e\x1c\xae\xfc\xcc\xb3\xfb\xf8\xd1\x8f\x64\x12\x0b\x32" }, { 752, "\x94\x23\x37\xf8\xfd\x76\xf0\xfa\xe8\xc5\x2d\x79\x54\x81\x06\x72" }, { 768, "\xb8\x54\x8c\x10\xf5\x16\x67\xf6\xe6\x0e\x18\x2f\xa1\x9b\x30\xf7" }, { 1008, "\x02\x11\xc7\xc6\x19\x0c\x9e\xfd\x12\x37\xc3\x4c\x8f\x2e\x06\xc4" }, { 1024, "\xbd\xa6\x4f\x65\x27\x6d\x2a\xac\xb8\xf9\x02\x12\x20\x3a\x80\x8e" }, { 1520, "\xbd\x38\x20\xf7\x32\xff\xb5\x3e\xc1\x93\xe7\x9d\x33\xe2\x7c\x73" }, { 1536, "\xd0\x16\x86\x16\x86\x19\x07\xd4\x82\xe3\x6c\xda\xc8\xcf\x57\x49" }, { 2032, "\x97\xb0\xf0\xf2\x24\xb2\xd2\x31\x71\x14\x80\x8f\xb0\x3a\xf7\xa0" }, { 2048, "\xe5\x96\x16\xe4\x69\x78\x79\x39\xa0\x63\xce\xea\x9a\xf9\x56\xd1" }, { 3056, "\xc4\x7e\x0d\xc1\x66\x09\x19\xc1\x11\x01\x20\x8f\x9e\x69\xaa\x1f" }, { 3072, "\x5a\xe4\xf1\x28\x96\xb8\x37\x9a\x2a\xad\x89\xb5\xb5\x53\xd6\xb0" }, { 4080, "\x6b\x6b\x09\x8d\x0c\x29\x3b\xc2\x99\x3d\x80\xbf\x05\x18\xb6\xd9" }, { 4096, "\x81\x70\xcc\x3c\xcd\x92\xa6\x98\x62\x1b\x93\x9d\xd3\x8f\xe7\xb9" } } }, + { "\x8b\x37\x64\x19\x10\x83\x32\x22\x77\x2a", 10, { { 0, "\xab\x65\xc2\x6e\xdd\xb2\x87\x60\x0d\xb2\xfd\xa1\x0d\x1e\x60\x5c" }, { 16, "\xbb\x75\x90\x10\xc2\x96\x58\xf2\xc7\x2d\x93\xa2\xd1\x6d\x29\x30" }, { 240, "\xb9\x01\xe8\x03\x6e\xd1\xc3\x83\xcd\x3c\x4c\x4d\xd0\xa6\xab\x05" }, { 256, "\x3d\x25\xce\x49\x22\x92\x4c\x55\xf0\x64\x94\x33\x53\xd7\x8a\x6c" }, { 496, "\x12\xc1\xaa\x44\xbb\xf8\x7e\x75\xe6\x11\xf6\x9b\x2c\x38\xf4\x9b" }, { 512, "\x28\xf2\xb3\x43\x4b\x65\xc0\x98\x77\x47\x00\x44\xc6\xea\x17\x0d" }, { 752, "\xbd\x9e\xf8\x22\xde\x52\x88\x19\x61\x34\xcf\x8a\xf7\x83\x93\x04" }, { 768, "\x67\x55\x9c\x23\xf0\x52\x15\x84\x70\xa2\x96\xf7\x25\x73\x5a\x32" }, { 1008, "\x8b\xab\x26\xfb\xc2\xc1\x2b\x0f\x13\xe2\xab\x18\x5e\xab\xf2\x41" }, { 1024, "\x31\x18\x5a\x6d\x69\x6f\x0c\xfa\x9b\x42\x80\x8b\x38\xe1\x32\xa2" }, { 1520, "\x56\x4d\x3d\xae\x18\x3c\x52\x34\xc8\xaf\x1e\x51\x06\x1c\x44\xb5" }, { 1536, "\x3c\x07\x78\xa7\xb5\xf7\x2d\x3c\x23\xa3\x13\x5c\x7d\x67\xb9\xf4" }, { 2032, "\xf3\x43\x69\x89\x0f\xcf\x16\xfb\x51\x7d\xca\xae\x44\x63\xb2\xdd" }, { 2048, "\x02\xf3\x1c\x81\xe8\x20\x07\x31\xb8\x99\xb0\x28\xe7\x91\xbf\xa7" }, { 3056, "\x72\xda\x64\x62\x83\x22\x8c\x14\x30\x08\x53\x70\x17\x95\x61\x6f" }, { 3072, "\x4e\x0a\x8c\x6f\x79\x34\xa7\x88\xe2\x26\x5e\x81\xd6\xd0\xc8\xf4" }, { 4080, "\x43\x8d\xd5\xea\xfe\xa0\x11\x1b\x6f\x36\xb4\xb9\x38\xda\x2a\x68" }, { 4096, "\x5f\x6b\xfc\x73\x81\x58\x74\xd9\x71\x00\xf0\x86\x97\x93\x57\xd8" } } }, + { "\xeb\xb4\x62\x27\xc6\xcc\x8b\x37\x64\x19\x10\x83\x32\x22\x77\x2a", 16, { { 0, "\x72\x0c\x94\xb6\x3e\xdf\x44\xe1\x31\xd9\x50\xca\x21\x1a\x5a\x30" }, { 16, "\xc3\x66\xfd\xea\xcf\x9c\xa8\x04\x36\xbe\x7c\x35\x84\x24\xd2\x0b" }, { 240, "\xb3\x39\x4a\x40\xaa\xbf\x75\xcb\xa4\x22\x82\xef\x25\xa0\x05\x9f" }, { 256, "\x48\x47\xd8\x1d\xa4\x94\x2d\xbc\x24\x9d\xef\xc4\x8c\x92\x2b\x9f" }, { 496, "\x08\x12\x8c\x46\x9f\x27\x53\x42\xad\xda\x20\x2b\x2b\x58\xda\x95" }, { 512, "\x97\x0d\xac\xef\x40\xad\x98\x72\x3b\xac\x5d\x69\x55\xb8\x17\x61" }, { 752, "\x3c\xb8\x99\x93\xb0\x7b\x0c\xed\x93\xde\x13\xd2\xa1\x10\x13\xac" }, { 768, "\xef\x2d\x67\x6f\x15\x45\xc2\xc1\x3d\xc6\x80\xa0\x2f\x4a\xdb\xfe" }, { 1008, "\xb6\x05\x95\x51\x4f\x24\xbc\x9f\xe5\x22\xa6\xca\xd7\x39\x36\x44" }, { 1024, "\xb5\x15\xa8\xc5\x01\x17\x54\xf5\x90\x03\x05\x8b\xdb\x81\x51\x4e" }, { 1520, "\x3c\x70\x04\x7e\x8c\xbc\x03\x8e\x3b\x98\x20\xdb\x60\x1d\xa4\x95" }, { 1536, "\x11\x75\xda\x6e\xe7\x56\xde\x46\xa5\x3e\x2b\x07\x56\x60\xb7\x70" }, { 2032, "\x00\xa5\x42\xbb\xa0\x21\x11\xcc\x2c\x65\xb3\x8e\xbd\xba\x58\x7e" }, { 2048, "\x58\x65\xfd\xbb\x5b\x48\x06\x41\x04\xe8\x30\xb3\x80\xf2\xae\xde" }, { 3056, "\x34\xb2\x1a\xd2\xad\x44\xe9\x99\xdb\x2d\x7f\x08\x63\xf0\xd9\xb6" }, { 3072, "\x84\xa9\x21\x8f\xc3\x6e\x8a\x5f\x2c\xcf\xbe\xae\x53\xa2\x7d\x25" }, { 4080, "\xa2\x22\x1a\x11\xb8\x33\xcc\xb4\x98\xa5\x95\x40\xf0\x54\x5f\x4a" }, { 4096, "\x5b\xbe\xb4\x78\x7d\x59\xe5\x37\x3f\xdb\xea\x6c\x6f\x75\xc2\x9b" } } }, + { "\xc1\x09\x16\x39\x08\xeb\xe5\x1d\xeb\xb4\x62\x27\xc6\xcc\x8b\x37\x64\x19\x10\x83\x32\x22\x77\x2a", 24, { { 0, "\x54\xb6\x4e\x6b\x5a\x20\xb5\xe2\xec\x84\x59\x3d\xc7\x98\x9d\xa7" }, { 16, "\xc1\x35\xee\xe2\x37\xa8\x54\x65\xff\x97\xdc\x03\x92\x4f\x45\xce" }, { 240, "\xcf\xcc\x92\x2f\xb4\xa1\x4a\xb4\x5d\x61\x75\xaa\xbb\xf2\xd2\x01" }, { 256, "\x83\x7b\x87\xe2\xa4\x46\xad\x0e\xf7\x98\xac\xd0\x2b\x94\x12\x4f" }, { 496, "\x17\xa6\xdb\xd6\x64\x92\x6a\x06\x36\xb3\xf4\xc3\x7a\x4f\x46\x94" }, { 512, "\x4a\x5f\x9f\x26\xae\xee\xd4\xd4\xa2\x5f\x63\x2d\x30\x52\x33\xd9" }, { 752, "\x80\xa3\xd0\x1e\xf0\x0c\x8e\x9a\x42\x09\xc1\x7f\x4e\xeb\x35\x8c" }, { 768, "\xd1\x5e\x7d\x5f\xfa\xaa\xbc\x02\x07\xbf\x20\x0a\x11\x77\x93\xa2" }, { 1008, "\x34\x96\x82\xbf\x58\x8e\xaa\x52\xd0\xaa\x15\x60\x34\x6a\xea\xfa" }, { 1024, "\xf5\x85\x4c\xdb\x76\xc8\x89\xe3\xad\x63\x35\x4e\x5f\x72\x75\xe3" }, { 1520, "\x53\x2c\x7c\xec\xcb\x39\xdf\x32\x36\x31\x84\x05\xa4\xb1\x27\x9c" }, { 1536, "\xba\xef\xe6\xd9\xce\xb6\x51\x84\x22\x60\xe0\xd1\xe0\x5e\x3b\x90" }, { 2032, "\xe8\x2d\x8c\x6d\xb5\x4e\x3c\x63\x3f\x58\x1c\x95\x2b\xa0\x42\x07" }, { 2048, "\x4b\x16\xe5\x0a\xbd\x38\x1b\xd7\x09\x00\xa9\xcd\x9a\x62\xcb\x23" }, { 3056, "\x36\x82\xee\x33\xbd\x14\x8b\xd9\xf5\x86\x56\xcd\x8f\x30\xd9\xfb" }, { 3072, "\x1e\x5a\x0b\x84\x75\x04\x5d\x9b\x20\xb2\x62\x86\x24\xed\xfd\x9e" }, { 4080, "\x63\xed\xd6\x84\xfb\x82\x62\x82\xfe\x52\x8f\x9c\x0e\x92\x37\xbc" }, { 4096, "\xe4\xdd\x2e\x98\xd6\x96\x0f\xae\x0b\x43\x54\x54\x56\x74\x33\x91" } } }, + { "\x1a\xda\x31\xd5\xcf\x68\x82\x21\xc1\x09\x16\x39\x08\xeb\xe5\x1d\xeb\xb4\x62\x27\xc6\xcc\x8b\x37\x64\x19\x10\x83\x32\x22\x77\x2a", 32, { { 0, "\xdd\x5b\xcb\x00\x18\xe9\x22\xd4\x94\x75\x9d\x7c\x39\x5d\x02\xd3" }, { 16, "\xc8\x44\x6f\x8f\x77\xab\xf7\x37\x68\x53\x53\xeb\x89\xa1\xc9\xeb" }, { 240, "\xaf\x3e\x30\xf9\xc0\x95\x04\x59\x38\x15\x15\x75\xc3\xfb\x90\x98" }, { 256, "\xf8\xcb\x62\x74\xdb\x99\xb8\x0b\x1d\x20\x12\xa9\x8e\xd4\x8f\x0e" }, { 496, "\x25\xc3\x00\x5a\x1c\xb8\x5d\xe0\x76\x25\x98\x39\xab\x71\x98\xab" }, { 512, "\x9d\xcb\xc1\x83\xe8\xcb\x99\x4b\x72\x7b\x75\xbe\x31\x80\x76\x9c" }, { 752, "\xa1\xd3\x07\x8d\xfa\x91\x69\x50\x3e\xd9\xd4\x49\x1d\xee\x4e\xb2" }, { 768, "\x85\x14\xa5\x49\x58\x58\x09\x6f\x59\x6e\x4b\xcd\x66\xb1\x06\x65" }, { 1008, "\x5f\x40\xd5\x9e\xc1\xb0\x3b\x33\x73\x8e\xfa\x60\xb2\x25\x5d\x31" }, { 1024, "\x34\x77\xc7\xf7\x64\xa4\x1b\xac\xef\xf9\x0b\xf1\x4f\x92\xb7\xcc" }, { 1520, "\xac\x4e\x95\x36\x8d\x99\xb9\xeb\x78\xb8\xda\x8f\x81\xff\xa7\x95" }, { 1536, "\x8c\x3c\x13\xf8\xc2\x38\x8b\xb7\x3f\x38\x57\x6e\x65\xb7\xc4\x46" }, { 2032, "\x13\xc4\xb9\xc1\xdf\xb6\x65\x79\xed\xdd\x8a\x28\x0b\x9f\x73\x16" }, { 2048, "\xdd\xd2\x78\x20\x55\x01\x26\x69\x8e\xfa\xad\xc6\x4b\x64\xf6\x6e" }, { 3056, "\xf0\x8f\x2e\x66\xd2\x8e\xd1\x43\xf3\xa2\x37\xcf\x9d\xe7\x35\x59" }, { 3072, "\x9e\xa3\x6c\x52\x55\x31\xb8\x80\xba\x12\x43\x34\xf5\x7b\x0b\x70" }, { 4080, "\xd5\xa3\x9e\x3d\xfc\xc5\x02\x80\xba\xc4\xa6\xb5\xaa\x0d\xca\x7d" }, { 4096, "\x37\x0b\x1c\x1f\xe6\x55\x91\x6d\x97\xfd\x0d\x47\xca\x1d\x72\xb8" } } } + }; + + struct rc4_ctx ctx; + + for ( size_t i = 0; i != NELEM(cases); ++i ) { + rc4_init(&ctx, cases[i].key, cases[i].sz); + + unsigned int pos = 0; + + for ( int j = 0; j != 18; ++j ) { + while ( pos != cases[i].test[j].pos ) { + rc4_get_byte(&ctx); + ++pos; + } + + unsigned char bytes[16]; + for ( unsigned int k = 0; k != 16; ++k ) { + bytes[k] = rc4_get_byte(&ctx); + ++pos; + } + + if ( memcmp(bytes, cases[i].test[j].bytes, 16) != 0 ) { + ERROR("Fehler"); + exit(EXIT_FAILURE); + } + } + + printf("Test #%zu : OK\n", i); + + rc4_clear(&ctx); + } +} + +int +main() +{ + rc4_test(); + + struct random_ctx *random = rc4_create("\x01\x02\x03\x04\x05\x06\x07", 7); + + for ( int j = 0; j != 18; ++j ) { + for ( int i = 0; i != 16; ++i ) { + printf("%02X ", random_get_byte(random)); + } + puts(""); + } + + rc4_free(random); + + return 0; +} diff --git a/src/ringbuff.c b/src/ringbuff.c new file mode 100644 index 0000000..1294b3b --- /dev/null +++ b/src/ringbuff.c @@ -0,0 +1,156 @@ +#include +#include +#include +#include + +#include "util.h" + +/* --8<-- ring_type */ +typedef int T; + +struct ring_buffer { + size_t head, tail; + T array[8]; /* fit for your needs... */ +}; +/* -->8-- */ + +/* --8<-- ring_init */ +void +ring_init(struct ring_buffer *rb) +{ + rb->head = rb->tail = 0; +} +/* -->8-- */ + +/* --8<-- ring_push_front */ +bool +ring_push_front(struct ring_buffer *rb, T data) +{ + const size_t prev = (rb->tail + NELEM(rb->array) - 1) % NELEM(rb->array); + + if ( prev == rb->head ) { + return false; + } + + rb->array[prev] = data; + rb->tail = prev; + + return true; +} +/* -->8-- */ + +/* --8<-- ring_push_back */ +bool +ring_push_back(struct ring_buffer *rb, T data) +{ + const size_t next = (rb->head + 1) % NELEM(rb->array); + + if ( next == rb->tail ) { + return false; + } + + rb->array[rb->head] = data; + rb->head = next; + + return true; +} +/* -->8-- */ + +/* --8<-- ring_pop_front */ +bool +ring_pop_front(struct ring_buffer *rb, T *data) +{ + if ( rb->head == rb->tail ) { + return false; + } + + const size_t next = (rb->tail + 1) % NELEM(rb->array); + + *data = rb->array[rb->tail]; + rb->tail = next; + + return true; +} +/* -->8-- */ + +/* --8<-- ring_pop_back */ +bool +ring_pop_back(struct ring_buffer *rb, T *data) +{ + if ( rb->head == rb->tail ) { + return false; + } + + const size_t prev = (rb->head + NELEM(rb->array) - 1) % NELEM(rb->array); + + *data = rb->array[prev]; + rb->head = prev; + + return true; +} +/* -->8-- */ + +/* --8<-- ring_put */ +bool +ring_put(struct ring_buffer *rb, T data) +{ + return ring_push_back(rb, data); +} +/* -->8-- */ + +/* --8<-- ring_get */ +bool +ring_get(struct ring_buffer *rb, T *data) +{ + return ring_pop_front(rb, data); +} +/* -->8-- */ + +void +debug_print(const char *msg, struct ring_buffer *rb) +{ + printf("%s: head: %zu, tail: %zu\n", msg, rb->head, rb->tail); +} + +int +main(void) +{ +#if 0 + struct ring_buffer rb; + ring_init(&rb); +#else + struct ring_buffer rb = { .head = 0, .tail = 0 }; +#endif + + assert(ring_push_back(&rb, 1) == true); // 1 + assert(ring_push_back(&rb, 2) == true); // 1, 2 + assert(ring_push_back(&rb, 3) == true); // 1, 2, 3 + assert(ring_push_back(&rb, 4) == true); // 1, 2, 3, 4 + + debug_print("Stand", &rb); + + assert(ring_push_front(&rb, 0) == true); // 0, 1, 2, 3, 4 + assert(ring_push_front(&rb, -1) == true); // -1, 0, 1, 2, 3, 4 + + debug_print("Stand", &rb); + + T temp; + assert(ring_pop_back(&rb, &temp) == true); // -1, 0, 1, 2, 3 + assert(ring_pop_front(&rb, &temp) == true); // 0, 1, 2, 3 + + debug_print("Stand", &rb); + + assert(ring_push_back(&rb, 4) == true); // 0, 1, 2, 3, 4 + assert(ring_push_back(&rb, 5) == true); // 0, 1, 2, 3, 4, 5 + assert(ring_push_back(&rb, 6) == true); // 0, 1, 2, 3, 4, 5, 6 + assert(ring_push_back(&rb, 7) == false); // 0, 1, 2, 3, 4, 5, 6 + assert(ring_push_front(&rb, 7) == false); // 0, 1, 2, 3, 4, 5, 6 + + while ( ring_pop_back(&rb, &temp) ) { + printf("temp: %d\n", temp); + } + + debug_print("Stand", &rb); + + return EXIT_SUCCESS; +} diff --git a/src/shellsort.c b/src/shellsort.c new file mode 100644 index 0000000..29e6bf8 --- /dev/null +++ b/src/shellsort.c @@ -0,0 +1,63 @@ +#include +#include +#include + +#include "util.h" + +typedef int T; + +void +shellsort(T a[], size_t n) +{ + //static const size_t gaps[] = { 701, 301, 132, 57, 23, 10, 4, 1 }; + + // Wikipedia: + //static const size_t gaps[] = { 2147483647, 1131376761, 410151271, 157840433, 58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331, 84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1 }; + + // https://www.cs.princeton.edu/~rs/shell/paperF.pdf + static const size_t gaps[] = { 1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1 }; + + for ( size_t k = 0; k < NELEM(gaps); ++k ) { + const size_t gap = gaps[k]; + + for ( size_t i = gap; i < n; i++ ) { + size_t j = i; + T temp = a[i]; + + for ( ; j >= gap && a[j - gap] > temp; j -= gap ) + a[j] = a[j - gap]; + + a[j] = temp; + } + } +} + +static void +test(T a[], size_t n) +{ + for ( size_t i = 1; i < n; ++i ) { + if ( a[i - 1] > a[i] ) { + ERROR("sortierung passt nicht"); + } + } +} + +int +main(void) +{ + T a[1000000]; + + srand(time(NULL)); + for ( size_t i = 0; i != NELEM(a); ++i ) + a[i] = rand() % 1000; + + clock_t start = clock(); + shellsort(a, NELEM(a)); + clock_t end = clock(); + + test(a, NELEM(a)); + + printf("duration: %.3f sec\n", ((double) (end - start)) / CLOCKS_PER_SEC); + + return EXIT_SUCCESS; +} diff --git a/src/stack.c b/src/stack.c new file mode 100644 index 0000000..48b9eba --- /dev/null +++ b/src/stack.c @@ -0,0 +1,110 @@ +/* Standard C */ +#include +#include +#include + +/* Project */ +#include "util.h" + +/* --8<-- stack_type */ +typedef int T; + +struct stack_item { + struct stack_item *next; + T data; +}; + +struct stack { + struct stack_item *head; +}; +/* -->8-- */ + +/* --8<-- stack_init */ +void +stack_init(struct stack *stack) +{ + stack->head = NULL; +} +/* -->8-- */ + +/* --8<-- stack_push */ +void +stack_push(struct stack *stack, T data) +{ + struct stack_item *new_item; + + if ( (new_item = malloc(sizeof *new_item)) != NULL ) { + new_item->data = data; + new_item->next = stack->head; + stack->head = new_item; + } + else + ERROR("out of memory"); +} +/* -->8-- */ + +/* --8<-- stack_pop */ +bool +stack_pop(struct stack *stack, T *data) +{ + if ( stack->head ) { + struct stack_item *next = stack->head->next; + + if ( data ) { + *data = stack->head->data; + } + free(stack->head); + stack->head = next; + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- stack_empty */ +bool +stack_empty(struct stack *stack) +{ + return stack->head == NULL; +} +/* -->8-- */ + +/* --8<-- stack_free */ +void +stack_free(struct stack *stack) +{ + struct stack_item *item, *next; + + for ( item = stack->head; item; item = next ) { + next = item->next; + free(item); + } +} +/* -->8-- */ + +int +main() +{ + struct stack stack[1]; + + stack_init(stack); + + for ( int i = 0; i != 10; ++i ) + stack_push(stack, i); + + /* + while ( !stack_empty(stack) ) { + int i; + if ( stack_pop(stack, &i) ) + printf("%d\n", i); + else + ERROR("this shouldn't happen!"); + } + */ + + stack_free(stack); + + return EXIT_SUCCESS; +} diff --git a/src/stack2.c b/src/stack2.c new file mode 100644 index 0000000..5f4ba41 --- /dev/null +++ b/src/stack2.c @@ -0,0 +1,115 @@ +#include +#include +#include + +#include "util.h" + +/* --8<-- stack2_type */ +typedef int T; + +struct stack { + T * array; + size_t sz, p; +}; +/* -->8-- */ + +/* --8<-- stack2_init */ +void +stack_init(struct stack *stack) +{ + stack->array = NULL; + stack->sz = 0; + stack->p = 0; +} +/* -->8-- */ + +/* --8<-- stack2_push */ +bool +stack_push(struct stack *stack, T data) +{ + if ( stack->array == NULL ) { + if ( (stack->array = malloc(10 * sizeof *stack->array)) != NULL ) { + stack->sz = 10; + stack->p = 0; + } + else { + ERROR("out of memory"); + return false; + } + } + + if ( stack->p == stack->sz ) { + size_t new_sz; + T * new_array; + + if ( (new_array = realloc(stack->array, (new_sz = (stack->sz * 3 / 2)) * sizeof *stack->array)) != NULL ) { + stack->array = new_array; + stack->sz = new_sz; + } + else { + ERROR("out of memory"); + return false; + } + } + + stack->array[stack->p++] = data; + return true; +} +/* -->8-- */ + +/* --8<-- stack2_pop */ +bool +stack_pop(struct stack *stack, T *data) +{ + if ( stack->p != 0 ) { + --stack->p; + + if ( data ) { + *data = stack->array[stack->p]; + } + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- stack2_empty */ +bool +stack_empty(struct stack *stack) +{ + return stack->p == 0; +} +/* -->8-- */ + +/* --8<-- stack2_free */ +void +stack_free(struct stack *stack) +{ + free(stack->array); +} +/* -->8-- */ + +int +main() +{ + struct stack stack[1]; + + stack_init(stack); + + for ( int i = 0; i != 20; ++i ) + stack_push(stack, i); + + while ( !stack_empty(stack) ) { + int i; + + if ( stack_pop(stack, &i) ) + printf("%d\n", i); + else + ERROR("this shouldn't happen!"); + } + + stack_free(stack); + + return EXIT_SUCCESS; +} diff --git a/src/tree.c b/src/tree.c new file mode 100644 index 0000000..93690e2 --- /dev/null +++ b/src/tree.c @@ -0,0 +1,806 @@ +// Binary Search Tree +#include +#include +#include +#include +#include + +#include "util.h" + +/* --8<-- tree_type */ +typedef int T; + +struct tree_node { + struct tree_node *left, *right; + T key; + int count; /* collision counter */ + /* ggf. weitere Felder... */ +}; +/* -->8-- */ + +/* --8<-- tree_isBst */ +static bool +tree_isBstUntil(struct tree_node *tree, T min, T max) +{ + if ( tree == NULL ) + return true; + + if ( tree->key < min || tree->key > max ) + return false; + + return tree_isBstUntil(tree->left, min, tree->key - 1) && + tree_isBstUntil(tree->right, tree->key + 1, max); +} + +bool +tree_isBst(struct tree_node *tree) +{ + return tree_isBstUntil(tree, INT_MIN, INT_MAX); +} +/* -->8-- */ + +/* --8<-- tree_insert */ +struct tree_node * +tree_insert(struct tree_node *tree, T key) +{ + if ( tree == NULL ) { + tree = malloc(sizeof *tree); + if ( tree ) { + tree->key = key; + tree->count = 1; + tree->left = NULL; + tree->right = NULL; + } + else + ERROR("out of memory"); + } + else if ( key < tree->key ) + tree->left = tree_insert(tree->left, key); + else if ( key > tree->key ) + tree->right = tree_insert(tree->right, key); + else /* key == tree->key */ + tree->count++; /* handle collision */ + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_insert_it */ +struct tree_node * +tree_insert_it(struct tree_node *tree, T key) +{ + struct tree_node *parent = NULL; + + for ( struct tree_node *curr = tree; curr; ) { + parent = curr; + + if ( key < curr->key ) { + curr = curr->left; + } + else if ( key > curr->key ) { + curr = curr->right; + } + else { /* key == current->key */ + curr->count++; + return tree; + } + } + + struct tree_node *new_node; + + new_node = malloc(sizeof *new_node); + if ( new_node ) { + new_node->key = key; + new_node->count = 1; + new_node->left = NULL; + new_node->right = NULL; + + if ( parent == NULL ) { + tree = new_node; + } + else if ( key < parent->key ) { + parent->left = new_node; + } + else { + parent->right = new_node; + } + } + else { + ERROR("out of memory"); + } + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_detach_min */ +static struct tree_node * +tree_detach_min(struct tree_node **ptree) +{ + struct tree_node *tree = *ptree; + + if ( tree == NULL ) + return NULL; + else if ( tree->left ) + return tree_detach_min(&tree->left); + else { + *ptree = tree->right; + return tree; + } +} +/* -->8-- */ + +/* --8<-- tree_remove */ +struct tree_node * +tree_remove(struct tree_node *tree, T key) +{ + if ( tree == NULL ) + return NULL; + + if ( key < tree->key ) + tree->left = tree_remove(tree->left, key); + else if ( key > tree->key ) + tree->right = tree_remove(tree->right, key); + else { /* key == tree->key */ + if ( --tree->count == 0 ) { /* Handle Collision */ + struct tree_node *temp = tree; + + if ( tree->left == NULL ) { + tree = tree->right; + } + else if ( tree->right == NULL ) { + tree = tree->left; + } + else { + struct tree_node *min = tree_detach_min(&tree->right); + + min->left = tree->left; + min->right = tree->right; + + tree = min; + } + + free(temp); + } + } + return tree; +} +/* -->8-- */ + +/* --8<-- tree_clear */ +void +tree_clear(struct tree_node *tree) +{ + if ( tree ) { + tree_clear(tree->left); + tree_clear(tree->right); + free(tree); + } +} +/* -->8-- */ + +/* --8<-- tree_lookup */ +struct tree_node * +tree_lookup(struct tree_node *tree, T key) +{ + while ( tree ) + if ( key < tree->key ) + tree = tree->left; + else if ( key > tree->key ) + tree = tree->right; + else /* key == tree->key */ + break; + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_minimum */ +struct tree_node * +tree_minimum(struct tree_node *tree) +{ + if ( tree ) + while ( tree->left ) + tree = tree->left; + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_maximum */ +struct tree_node * +tree_maximum(struct tree_node *tree) +{ + if ( tree ) + while ( tree->right ) + tree = tree->right; + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_height */ +size_t +tree_height(struct tree_node *tree) +{ + if ( tree ) { + size_t hl = tree_height(tree->left); + size_t hr = tree_height(tree->right); + + return ((hl > hr) ? hl : hr) + 1; + } + + return 0; +} +/* -->8-- */ + +/* --8<-- tree_count */ +size_t +tree_count(struct tree_node *tree) +{ + if ( tree ) + return tree_count(tree->left) + tree_count(tree->right) + 1; + + return 0; +} +/* -->8-- */ + +/* --8<-- tree_copy */ +struct tree_node * +tree_copy(struct tree_node *tree) +{ + if ( tree ) { + struct tree_node *new_node; + + new_node = malloc(sizeof *new_node); + if ( new_node ) { + new_node->key = tree->key; + new_node->count = tree->count; + new_node->left = tree_copy(tree->left); + new_node->right = tree_copy(tree->right); + } + else { + ERROR("out of memory"); + } + + return new_node; + } + return NULL; +} +/* -->8-- */ + +/* --8<-- tree_isleaf */ +bool +tree_isleaf(struct tree_node *tree) +{ + return tree->left == NULL && tree->right == NULL; +} +/* -->8-- */ + +/* --8<-- tree_apply_preorder */ +void +tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + visit(tree->key, cl); + tree_apply_preorder(tree->left, visit, cl); + tree_apply_preorder(tree->right, visit, cl); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_inorder */ +void +tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + tree_apply_inorder(tree->left, visit, cl); + visit(tree->key, cl); + tree_apply_inorder(tree->right, visit, cl); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_postorder */ +void +tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + tree_apply_postorder(tree->left, visit, cl); + tree_apply_postorder(tree->right, visit, cl); + visit(tree->key, cl); + } +} +/* -->8-- */ + +/* ===== */ + +/* --8<-- tree_stack_type */ +struct stack_item { + struct stack_item *next; + struct tree_node * data; +}; + +struct stack { + struct stack_item *head; +}; +/* -->8-- */ + +/* --8<-- tree_stack_init */ +static void +stack_init(struct stack *stack) +{ + stack->head = NULL; +} +/* -->8-- */ + +/* --8<-- tree_stack_push */ +static void +stack_push(struct stack *stack, struct tree_node *data) +{ + struct stack_item *new_item; + + if ( (new_item = malloc(sizeof *new_item)) ) { + new_item->data = data; + new_item->next = stack->head; + stack->head = new_item; + } + else + ERROR("out of memory"); +} +/* -->8-- */ + +/* --8<-- tree_stack_pop */ +static bool +stack_pop(struct stack *stack, struct tree_node **data) +{ + if ( stack->head ) { + struct stack_item *next; + + next = stack->head->next; + *data = stack->head->data; + + free(stack->head); + stack->head = next; + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- tree_stack_peek */ +static struct tree_node * +stack_peek(struct stack *stack) +{ + return (stack->head) ? stack->head->data : NULL; +} +/* -->8-- */ + +/* --8<-- tree_stack_empty */ +static bool +stack_empty(struct stack *stack) +{ + return stack->head == NULL; +} +/* -->8-- */ + +/* --8<-- tree_stack_free */ +void +stack_free(struct stack *stack) +{ + struct stack_item *item, *next; + + for ( item = stack->head; item; item = next ) { + next = item->next; + free(item); + } +} +/* -->8-- */ + +/* ===== */ + +/* --8<-- tree_queue_type */ +struct queue_item { + struct queue_item *next; + struct tree_node * data; +}; + +struct queue { + struct queue_item *head, *tail; +}; +/* -->8-- */ + +/* --8<-- tree_queue_init */ +void +queue_init(struct queue *queue) +{ + queue->head = NULL; +} +/* -->8-- */ + +/* --8<-- tree_queue_put */ +void +queue_put(struct queue *queue, struct tree_node *data) +{ + struct queue_item *new_item; + + if ( (new_item = malloc(sizeof *new_item)) ) { + struct queue_item *tail; + + tail = queue->tail; + new_item->data = data; + new_item->next = NULL; + queue->tail = new_item; + + if ( queue->head == NULL ) + queue->head = queue->tail; + else + tail->next = queue->tail; + } + else + ERROR("out of memory"); +} +/* -->8-- */ + +/* --8<-- tree_queue_get */ +bool +queue_get(struct queue *queue, struct tree_node **data) +{ + if ( queue->head ) { + struct queue_item *next; + + next = queue->head->next; + *data = queue->head->data; + + free(queue->head); + queue->head = next; + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- tree_queue_empty */ +bool +queue_empty(struct queue *queue) +{ + return queue->head == NULL; +} +/* -->8-- */ + +/* --8<-- tree_queue_free */ +void +queue_free(struct queue *queue) +{ + struct queue_item *item, *next; + + for ( item = queue->head; item; item = next ) { + next = item->next; + free(item); + } +} +/* -->8-- */ + +/* ===== */ + +/* --8<-- tree_apply_preorder_it */ +void +tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct stack stack; + + stack_init(&stack); + + stack_push(&stack, tree); + + while ( stack_pop(&stack, &tree) ) { + visit(tree->key, cl); + + if ( tree->right ) + stack_push(&stack, tree->right); + if ( tree->left ) + stack_push(&stack, tree->left); + } + + stack_free(&stack); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_inorder_it */ +void +tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct stack stack; + + stack_init(&stack); + + while ( !stack_empty(&stack) || tree ) { + if ( tree ) { + stack_push(&stack, tree); + tree = tree->left; + } + else { + stack_pop(&stack, &tree); + visit(tree->key, cl); + tree = tree->right; + } + } + + stack_free(&stack); + } +} +/* -->8-- */ + +// Hier eine Version für PostOrder-Iterativ: +// Quelle: https://stackoverflow.com/a/16092333 + +/* --8<-- tree_apply_postorder_it */ +void +tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct stack stack; + + stack_init(&stack); + stack_push(&stack, tree); + + while ( !stack_empty(&stack) ) { + struct tree_node *next = stack_peek(&stack); + + bool finishedSubtrees = (next->left == tree || next->right == tree); + + if ( finishedSubtrees || tree_isleaf(next) ) { + stack_pop(&stack, &next); + + visit(next->key, cl); + + tree = next; + } + else { + if ( next->right ) { + stack_push(&stack, next->right); + } + if ( next->left ) { + stack_push(&stack, next->left); + } + } + } + stack_free(&stack); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_levelorder_it */ +void +tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct queue queue; + + queue_init(&queue); + + queue_put(&queue, tree); + + while ( queue_get(&queue, &tree) ) { + visit(tree->key, cl); + + if ( tree->left ) + queue_put(&queue, tree->left); + if ( tree->right ) + queue_put(&queue, tree->right); + } + + queue_free(&queue); + } +} +/* -->8-- */ + +/* ======================== */ + +/* --8<-- tree_iterator_type */ +struct tree_iterator { + struct stack stack; +}; +/* -->8-- */ + +/* --8<-- tree_iterator_push_leftmost */ +static void +tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node) +{ + for ( ; node; node = node->left ) { + stack_push(stack, node); + } +} +/* -->8-- */ + +/* --8<-- tree_iterator_next */ +struct tree_node * +tree_iterator_next(struct tree_iterator *it) +{ + struct tree_node *node = NULL; + + if ( stack_pop(&it->stack, &node) ) { + tree_iterator_push_leftmost(&it->stack, node->right); + } + + return node; +} +/* -->8-- */ + +/* --8<-- tree_iterator_first */ +struct tree_node * +tree_iterator_first(struct tree_iterator *it, struct tree_node *tree) +{ + stack_init(&it->stack); + + tree_iterator_push_leftmost(&it->stack, tree); + + return tree_iterator_next(it); +} +/* -->8-- */ + +/* --8<-- tree_iterator_free */ +void +tree_iterator_free(struct tree_iterator *it) +{ + stack_free(&it->stack); +} +/* -->8-- */ + +/* --8<-- tree_preorder_iterator_next */ +struct tree_node * +tree_preorder_iterator_next(struct tree_iterator *it) +{ + struct tree_node *node = NULL; + + if ( stack_pop(&it->stack, &node) ) { + if ( node->right ) { + stack_push(&it->stack, node->right); + } + if ( node->left ) { + stack_push(&it->stack, node->left); + } + } + + return node; +} +/* -->8-- */ + +/* --8<-- tree_preorder_iterator_first */ +struct tree_node * +tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree) +{ + stack_init(&it->stack); + + if ( tree ) { + stack_push(&it->stack, tree); + + return tree_preorder_iterator_next(it); + } + else { + return NULL; + } +} +/* -->8-- */ + +/* ===== */ + +void +print(T data, void *cl) +{ + (void) cl; + printf("%d\n", data); +} + +#include "treeutil.h" + +int +main_(void) +{ + // Teste den Fall von mycodeschool + + struct tree_node *tree = NULL; + + tree = tree_insert(tree, 12); + tree = tree_insert(tree, 5); + tree = tree_insert(tree, 15); + tree = tree_insert(tree, 3); + tree = tree_insert(tree, 7); + tree = tree_insert(tree, 13); + tree = tree_insert(tree, 17); + tree = tree_insert(tree, 1); + tree = tree_insert(tree, 9); + tree = tree_insert(tree, 14); + tree = tree_insert(tree, 20); + tree = tree_insert(tree, 8); + tree = tree_insert(tree, 11); + tree = tree_insert(tree, 18); + + tree = tree_remove(tree, 15); + + if ( !tree_isBst(tree) ) { + fprintf(stderr, "Tree ist kein BST!!\n"); + return EXIT_FAILURE; + } + + show_tree(tree, 0, 0); + + tree_clear(tree); + + return EXIT_SUCCESS; +} + +int +main__(void) +{ + struct tree_node *tree = NULL; + + tree = tree_insert(tree, 5); + tree = tree_insert(tree, 3); + tree = tree_insert(tree, 7); + tree = tree_insert(tree, 2); + tree = tree_insert(tree, 4); + tree = tree_insert(tree, 6); + tree = tree_insert(tree, 8); + + tree = tree_remove(tree, 2); + tree = tree_remove(tree, 3); + tree = tree_remove(tree, 5); + + if ( !tree_isBst(tree) ) { + fprintf(stderr, "Tree ist kein BST!!\n"); + return EXIT_FAILURE; + } + + show_tree(tree, 0, 0); + + tree_clear(tree); + + return EXIT_SUCCESS; +} + +int +main(void) +{ + struct tree_node *tree = NULL; + + tree = tree_insert_it(tree, 10); + tree = tree_insert_it(tree, 5); + tree = tree_insert_it(tree, 20); + tree = tree_insert_it(tree, 1); + tree = tree_insert_it(tree, 7); + tree = tree_insert_it(tree, 15); + tree = tree_insert_it(tree, 18); + + tree_apply_preorder(tree, print, NULL); + puts("postorder:"); + tree_apply_postorder(tree, print, NULL); + puts("postorder_it:"); + tree_apply_postorder_it(tree, print, NULL); + show_tree(tree, 0, 0); + + puts("levelorder_it:"); + tree_apply_levelorder_it(tree, print, NULL); + + show_tree(tree, 0, 0); + + struct tree_iterator it; + struct tree_node * node = tree_preorder_iterator_first(&it, tree); + while ( node ) { + fprintf(stdout, "%d\n", node->key); + + node = tree_preorder_iterator_next(&it); + } + tree_iterator_free(&it); + + tree_clear(tree); + + return EXIT_SUCCESS; +} diff --git a/src/treeutil.h b/src/treeutil.h new file mode 100644 index 0000000..76627c0 --- /dev/null +++ b/src/treeutil.h @@ -0,0 +1,51 @@ +// aux display and verification routines, helpful but not essential +struct trunk { + struct trunk *prev; + const char * str; +}; + +static void +show_trunks(struct trunk *p) +{ + if ( !p ) + return; + show_trunks(p->prev); + printf("%s", p->str); +} + +// this is very haphazzard +static void +show_tree(struct tree_node *root, struct trunk *prev, int is_left) +{ + if ( root == NULL ) + return; + + struct trunk this_disp = { prev, " " }; + const char * prev_str = this_disp.str; + show_tree(root->right, &this_disp, 1); + + if ( !prev ) + this_disp.str = "---"; + else if ( is_left ) { + this_disp.str = ".--"; + prev_str = " |"; + } + else { + this_disp.str = "`--"; + prev->str = prev_str; + } + + show_trunks(&this_disp); + if ( root->key >= 'A' && root->key <= 'Z' ) + printf("%c\n", root->key); + else + printf("%d\n", root->key); + + if ( prev ) + prev->str = prev_str; + this_disp.str = " |"; + + show_tree(root->left, &this_disp, 0); + if ( !prev ) + puts(""); +} diff --git a/src/util.h b/src/util.h new file mode 100644 index 0000000..7ede6fd --- /dev/null +++ b/src/util.h @@ -0,0 +1,24 @@ +#pragma once + +#include +#include +#include + +static void +error(const char *msg, ...) +{ + va_list ap; + + va_start(ap, msg); + fprintf(stderr, "Error: "); + vfprintf(stderr, msg, ap); + va_end(ap); + fprintf(stderr, "\n"); + exit(EXIT_FAILURE); +} + +#define ERROR(msg) error(msg " in \"%s()\" (%s:%d)", __func__, __FILE__, __LINE__) + +#ifndef NELEM +# define NELEM(x) (sizeof(x) / sizeof(x[0])) /* NOLINT */ +#endif -- cgit v1.3