Merge branch 'rework-directory-structure'

23 files changed, 5888 insertions, 0 deletions

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 <stdlib.h> /* 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 <string.h>
+
+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 <stddef.h> /* 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 <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+#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 <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+/* 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 <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#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 <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+/* 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 <ctype.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#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 <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#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 <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#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 <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/* 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 <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+/* 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 <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/* 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 <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#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 <teuhola@cs.utu.fi>; 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 <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#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 <assert.h>
+#include <stdlib.h>
+
+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 <assert.h>
+#include <stdio.h>
+#include <stdlib.h> /* 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("<empty tree>", 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 <stdio.h>
+#include <stdlib.h>
+#include <string.h> /* 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 <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#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 <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#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 <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/* 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 <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#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 <limits.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#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 <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+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