From 7221289477ba80bfbb9c2c37e43a9d6b1d0e6d17 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sun, 10 Apr 2022 09:01:17 +0200 Subject: feat: rename files --- makefile | 19 +- src/avl-tree.c | 471 +++++++++++++++++++++++++++ src/avl.c | 471 --------------------------- src/binary-search-tree.c | 806 +++++++++++++++++++++++++++++++++++++++++++++++ src/dlist.c | 504 ----------------------------- src/double-linked-list.c | 504 +++++++++++++++++++++++++++++ src/hash-table.c | 220 +++++++++++++ src/hashtab.c | 220 ------------- src/list.c | 264 ---------------- src/rb.c | 614 ------------------------------------ src/red-black-tree.c | 614 ++++++++++++++++++++++++++++++++++++ src/ring-buffer.c | 156 +++++++++ src/ringbuff.c | 156 --------- src/single-linked-list.c | 264 ++++++++++++++++ src/stack-array.c | 115 +++++++ src/stack-linked-list.c | 110 +++++++ src/stack.c | 110 ------- src/stack2.c | 115 ------- src/tree.c | 806 ----------------------------------------------- 19 files changed, 3278 insertions(+), 3261 deletions(-) create mode 100644 src/avl-tree.c delete mode 100644 src/avl.c create mode 100644 src/binary-search-tree.c delete mode 100644 src/dlist.c create mode 100644 src/double-linked-list.c create mode 100644 src/hash-table.c delete mode 100644 src/hashtab.c delete mode 100644 src/list.c delete mode 100644 src/rb.c create mode 100644 src/red-black-tree.c create mode 100644 src/ring-buffer.c delete mode 100644 src/ringbuff.c create mode 100644 src/single-linked-list.c create mode 100644 src/stack-array.c create mode 100644 src/stack-linked-list.c delete mode 100644 src/stack.c delete mode 100644 src/stack2.c delete mode 100644 src/tree.c diff --git a/makefile b/makefile index 4b6f5b8..dc2f464 100644 --- a/makefile +++ b/makefile @@ -1,6 +1,23 @@ .PHONY: all clean -BINS=bin/list bin/list-tail-node bin/dlist bin/stack bin/stack2 bin/queue bin/ringbuff bin/hashtab bin/tree bin/avl bin/heap bin/quicksort bin/allocator bin/rb bin/deque bin/arraylist bin/insertsort bin/shellsort +BINS=bin/allocator \ + bin/arraylist \ + bin/avl-tree \ + bin/binary-search-tree \ + bin/deque \ + bin/double-linked-list \ + bin/hash-table \ + bin/heap \ + bin/insertsort \ + bin/list-tail-node \ + bin/queue \ + bin/quicksort \ + bin/red-black-tree \ + bin/ring-buffer \ + bin/shellsort \ + bin/single-linked-list \ + bin/stack-array \ + bin/stack-linked-list CFLAGS=-Wall -Werror -Wextra -Wno-unused-function -Wsign-conversion -pedantic -std=c99 -g diff --git a/src/avl-tree.c b/src/avl-tree.c new file mode 100644 index 0000000..874cc6c --- /dev/null +++ b/src/avl-tree.c @@ -0,0 +1,471 @@ +// AVL Tree +#include +#include +#include +#include +#include + +/* utils */ +#include "util.h" + +// clang-format off + +// Review: http://www.inr.ac.ru/~info21/ADen/ +// Tests: https://stackoverflow.com/q/3955680 + +/* --8<-- avl_type */ +typedef int T; + +struct tree_node { + struct tree_node *left, *right; + int bal; + T key; + int count; /* collision counter */ + /* ggf. weitere Felder... */ +}; +/* -->8-- */ + +/* --8<-- avl_insert_r */ +static struct tree_node * +insert_r(T x, struct tree_node *p, bool *h) +{ + struct tree_node *p1, *p2; + + if ( p == NULL ) { + *h = true; + + p = malloc(sizeof *p); + if ( p ) { + p->left = NULL; + p->right = NULL; + p->bal = 0; + + p->key = x; + p->count = 1; /* hit counter */ + } + else + ERROR("out of memory"); + } + else if ( x < p->key ) { + p->left = insert_r(x, p->left, h); + + if ( *h ) { + if ( p->bal == +1 ) { + p->bal = 0; + *h = false; + } + else if ( p->bal == 0 ) { + p->bal = -1; + } + else /* if ( p->bal == -1 ) */ { + p1 = p->left; + if ( p1->bal == -1 ) { /* single LL rotation */ + p->left = p1->right; p1->right = p; + p->bal = 0; p = p1; + } + else { /* double LR rotation */ + p2 = p1->right; + p1->right = p2->left; p2->left = p1; + p->left = p2->right; p2->right = p; + p->bal = ( p2->bal == -1 ) ? +1 : 0; + p1->bal = ( p2->bal == +1 ) ? -1 : 0; + p = p2; + } + p->bal = 0; + *h = false; + } + } + } + else if ( x > p->key ) { + p->right = insert_r(x, p->right, h); + + if ( *h ) { + if ( p->bal == -1 ) { + p->bal = 0; + *h = false; + } + else if ( p->bal == 0 ) { + p->bal = +1; + } + else /* if ( p->bal == +1 ) */ { + p1 = p->right; + if ( p1->bal == +1 ) { /* single RR rotation */ + p->right = p1->left; p1->left = p; + p->bal = 0; p = p1; + } + else { /* double RL rotation */ + p2 = p1->left; + p1->left = p2->right; p2->right = p1; + p->right = p2->left; p2->left = p; + p->bal = ( p2->bal == +1 ) ? -1 : 0; + p1->bal = ( p2->bal == -1 ) ? +1 : 0; + p = p2; + } + p->bal = 0; + *h = false; + } + } + } + else { + /* handle collision! */ + p->count++; /* hit counter */ + *h = false; + } + assert(p != NULL); + + return p; +} +/* -->8-- */ + +/* --8<-- avl_insert */ +struct tree_node * +insert(struct tree_node *tree, T data) +{ + bool h = false; + return insert_r(data, tree, &h); +} +/* -->8-- */ + +/* --8<-- avl_balanceL */ +static struct tree_node * +balanceL(struct tree_node *p, bool *h) +{ + if ( p->bal == -1 ) { + p->bal = 0; + } + else if ( p->bal == 0 ) { + p->bal = +1; + *h = false; + } + else /* if ( p->bal == +1 ) */ { /* rebalance */ + struct tree_node *p1 = p->right; + if ( p1->bal >= 0 ) { /* singla RR rotation */ + p->right = p1->left; + p1->left = p; + if ( p1->bal == 0 ) { + p->bal = +1; + p1->bal = -1; + *h = false; + } + else { + p->bal = 0; + p1->bal = 0; + } + p = p1; + } + else { /* double RL rotation */ + struct tree_node *p2 = p1->left; + p1->left = p2->right; + p2->right = p1; + p->right = p2->left; + p2->left = p; + p->bal = ( p2->bal == +1 ) ? -1 : 0; + p1->bal = ( p2->bal == -1 ) ? +1 : 0; + p = p2; + p2->bal = 0; + } + } + return p; +} +/* -->8-- */ + +/* --8<-- avl_balanceR */ +static struct tree_node * +balanceR(struct tree_node *p, bool *h) +{ + if ( p->bal == +1 ) { + p->bal = 0; + } + else if ( p->bal == 0 ) { + p->bal = -1; + *h = false; + } + else /* p->bal == -1 */ { /* rebalance */ + struct tree_node *p1 = p->left; + if ( p1->bal <= 0 ) { /* single LL rotation */ + p->left = p1->right; + p1->right = p; + if ( p1->bal == 0 ) { + p->bal = -1; + p1->bal = +1; + *h = false; + } + else { + p->bal = 0; + p1->bal = 0; + } + p = p1; + } + else { /* double LR rotation */ + struct tree_node *p2 = p1->right; + p1->right = p2->left; + p2->left = p1; + p->left = p2->right; + p2->right = p; + p->bal = ( p2->bal == -1 ) ? +1 : 0; + p1->bal = ( p2->bal == +1 ) ? -1 : 0; + p = p2; + p2->bal = 0; + } + } + return p; +} +/* -->8-- */ + +/* --8<-- avl_del */ +static void +del(struct tree_node **q, struct tree_node **r, bool *h) +{ + if ( (*r)->right ) { + del(q, &(*r)->right, h); + if ( *h ) + *r = balanceR(*r, h); + } + else { + /* copy data */ + (*q)->key = (*r)->key; + (*q)->count = (*r)->count; + + *q = *r; + *r = (*r)->left; + *h = true; + } +} +/* -->8-- */ + +/* --8<-- avl_delete_r */ +static struct tree_node * +delete_r(T x, struct tree_node *p, bool *h) +{ + if ( p == NULL ) { + ERROR("key not found"); + } + else if ( x < p->key ) { + p->left = delete_r(x, p->left, h); + if ( *h ) + p = balanceL(p, h); + } + else if ( x > p->key ) { + p->right = delete_r(x, p->right, h); + if ( *h ) + p = balanceR(p, h); + } + else /* if ( x == p->key ) */ { + struct tree_node *q = p; + if ( q->right == NULL ) { + p = q->left; + *h = true; + } + else if ( q->left == NULL ) { + p = q->right; + *h = true; + } + else { + del(&q, &q->left, h); + if ( *h ) + p = balanceL(p, h); + } + free(q); + } + return p; +} +/* -->8-- */ + +/* --8<-- avl_delete */ +struct tree_node * +delete(struct tree_node *tree, T data) +{ + bool h = false; + return delete_r(data, tree, &h); +} +/* -->8-- */ + +// aux display and verification routines, helpful but not essential +struct trunk { + struct trunk *prev; + char * str; +}; + +void show_trunks(struct trunk *p) +{ + if (!p) return; + show_trunks(p->prev); + printf("%s", p->str); +} + +// this is very haphazzard +void show_tree(struct tree_node *root, struct trunk *prev, int is_left) +{ + if (root == NULL) return; + + struct trunk this_disp = { prev, " " }; + char *prev_str = this_disp.str; + show_tree(root->right, &this_disp, 1); + + if (!prev) + this_disp.str = "---"; + else if (is_left) { + this_disp.str = ".--"; + prev_str = " |"; + } else { + this_disp.str = "`--"; + prev->str = prev_str; + } + + show_trunks(&this_disp); + if ( root->key >= 'A' && root->key <= 'Z' ) + printf("%c\n", root->key); + else + printf("%d\n", root->key); + + if (prev) prev->str = prev_str; + this_disp.str = " |"; + + show_tree(root->left, &this_disp, 0); + if (!prev) puts(""); +} + +void +print(struct tree_node *tree) +{ + if ( tree ) { + print(tree->left); + printf("%d (%d)\n", tree->key, tree->bal); + print(tree->right); + } +} + +int +main() +{ + + +#if 0 /* 1a/b */ + tree = insert(tree, 20); + tree = insert(tree, 4); + show_tree(tree, 0, 0); + + //tree = insert(tree, 15); + tree = insert(tree, 8); + show_tree(tree, 0, 0); +#endif + +#if 0 /* 2a/b */ + tree = insert(tree, 20); + tree = insert(tree, 4); + tree = insert(tree, 26); + tree = insert(tree, 3); + tree = insert(tree, 9); + show_tree(tree, 0, 0); + + //tree = insert(tree, 15); + tree = insert(tree, 8); + show_tree(tree, 0, 0); +#endif + +#if 0 /* 3a/b */ + tree = insert(tree, 20); + tree = insert(tree, 4); + tree = insert(tree, 26); + tree = insert(tree, 3); + tree = insert(tree, 9); + tree = insert(tree, 21); + tree = insert(tree, 30); + tree = insert(tree, 2); + tree = insert(tree, 7); + tree = insert(tree, 11); + show_tree(tree, 0, 0); + + //tree = insert(tree, 15); + tree = insert(tree, 8); + show_tree(tree, 0, 0); +#endif + +#if 0 + tree = insert(tree, 2); + tree = insert(tree, 1); + tree = insert(tree, 4); + tree = insert(tree, 3); + tree = insert(tree, 5); + show_tree(tree, 0, 0); + + tree = delete(tree, 1); + show_tree(tree, 0, 0); +#endif + +#if 0 + tree = insert(tree, 6); + tree = insert(tree, 2); + tree = insert(tree, 9); + tree = insert(tree, 1); + tree = insert(tree, 4); + tree = insert(tree, 8); + tree = insert(tree, 'B'); + tree = insert(tree, 3); + tree = insert(tree, 5); + tree = insert(tree, 7); + tree = insert(tree, 'A'); + tree = insert(tree, 'C'); + tree = insert(tree, 'D'); + show_tree(tree, 0, 0); + + tree = delete(tree, 1); + show_tree(tree, 0, 0); +#endif + + +#if 0 + tree = insert(tree, 5); + tree = insert(tree, 2); + tree = insert(tree, 8); + tree = insert(tree, 1); + tree = insert(tree, 3); + tree = insert(tree, 7); + tree = insert(tree, 'A'); + tree = insert(tree, 4); + tree = insert(tree, 6); + tree = insert(tree, 9); + tree = insert(tree, 'B'); + tree = insert(tree, 'C'); + show_tree(tree, 0, 0); + + tree = delete(tree, 1); + show_tree(tree, 0, 0); +#endif + + +#if 0 + tree = insert(tree, 5); + tree = insert(tree, 3); + tree = insert(tree, 8); + tree = insert(tree, 2); + tree = insert(tree, 4); + tree = insert(tree, 7); + tree = insert(tree, 10); + tree = insert(tree, 1); + tree = insert(tree, 6); + tree = insert(tree, 9); + tree = insert(tree, 11); + + tree = delete(tree, 4); + tree = delete(tree, 8); + tree = delete(tree, 6); + tree = delete(tree, 5); + tree = delete(tree, 2); + tree = delete(tree, 1); + tree = delete(tree, 7); + + show_tree(tree, 0, 0); +#endif + + struct tree_node *tree = NULL; + + srand(time(NULL)); + for ( int i = 0; i != 300000; ++i ) + tree = insert(tree, rand()); + + //show_tree(tree, 0, 0); + + return EXIT_SUCCESS; +} + diff --git a/src/avl.c b/src/avl.c deleted file mode 100644 index 874cc6c..0000000 --- a/src/avl.c +++ /dev/null @@ -1,471 +0,0 @@ -// AVL Tree -#include -#include -#include -#include -#include - -/* utils */ -#include "util.h" - -// clang-format off - -// Review: http://www.inr.ac.ru/~info21/ADen/ -// Tests: https://stackoverflow.com/q/3955680 - -/* --8<-- avl_type */ -typedef int T; - -struct tree_node { - struct tree_node *left, *right; - int bal; - T key; - int count; /* collision counter */ - /* ggf. weitere Felder... */ -}; -/* -->8-- */ - -/* --8<-- avl_insert_r */ -static struct tree_node * -insert_r(T x, struct tree_node *p, bool *h) -{ - struct tree_node *p1, *p2; - - if ( p == NULL ) { - *h = true; - - p = malloc(sizeof *p); - if ( p ) { - p->left = NULL; - p->right = NULL; - p->bal = 0; - - p->key = x; - p->count = 1; /* hit counter */ - } - else - ERROR("out of memory"); - } - else if ( x < p->key ) { - p->left = insert_r(x, p->left, h); - - if ( *h ) { - if ( p->bal == +1 ) { - p->bal = 0; - *h = false; - } - else if ( p->bal == 0 ) { - p->bal = -1; - } - else /* if ( p->bal == -1 ) */ { - p1 = p->left; - if ( p1->bal == -1 ) { /* single LL rotation */ - p->left = p1->right; p1->right = p; - p->bal = 0; p = p1; - } - else { /* double LR rotation */ - p2 = p1->right; - p1->right = p2->left; p2->left = p1; - p->left = p2->right; p2->right = p; - p->bal = ( p2->bal == -1 ) ? +1 : 0; - p1->bal = ( p2->bal == +1 ) ? -1 : 0; - p = p2; - } - p->bal = 0; - *h = false; - } - } - } - else if ( x > p->key ) { - p->right = insert_r(x, p->right, h); - - if ( *h ) { - if ( p->bal == -1 ) { - p->bal = 0; - *h = false; - } - else if ( p->bal == 0 ) { - p->bal = +1; - } - else /* if ( p->bal == +1 ) */ { - p1 = p->right; - if ( p1->bal == +1 ) { /* single RR rotation */ - p->right = p1->left; p1->left = p; - p->bal = 0; p = p1; - } - else { /* double RL rotation */ - p2 = p1->left; - p1->left = p2->right; p2->right = p1; - p->right = p2->left; p2->left = p; - p->bal = ( p2->bal == +1 ) ? -1 : 0; - p1->bal = ( p2->bal == -1 ) ? +1 : 0; - p = p2; - } - p->bal = 0; - *h = false; - } - } - } - else { - /* handle collision! */ - p->count++; /* hit counter */ - *h = false; - } - assert(p != NULL); - - return p; -} -/* -->8-- */ - -/* --8<-- avl_insert */ -struct tree_node * -insert(struct tree_node *tree, T data) -{ - bool h = false; - return insert_r(data, tree, &h); -} -/* -->8-- */ - -/* --8<-- avl_balanceL */ -static struct tree_node * -balanceL(struct tree_node *p, bool *h) -{ - if ( p->bal == -1 ) { - p->bal = 0; - } - else if ( p->bal == 0 ) { - p->bal = +1; - *h = false; - } - else /* if ( p->bal == +1 ) */ { /* rebalance */ - struct tree_node *p1 = p->right; - if ( p1->bal >= 0 ) { /* singla RR rotation */ - p->right = p1->left; - p1->left = p; - if ( p1->bal == 0 ) { - p->bal = +1; - p1->bal = -1; - *h = false; - } - else { - p->bal = 0; - p1->bal = 0; - } - p = p1; - } - else { /* double RL rotation */ - struct tree_node *p2 = p1->left; - p1->left = p2->right; - p2->right = p1; - p->right = p2->left; - p2->left = p; - p->bal = ( p2->bal == +1 ) ? -1 : 0; - p1->bal = ( p2->bal == -1 ) ? +1 : 0; - p = p2; - p2->bal = 0; - } - } - return p; -} -/* -->8-- */ - -/* --8<-- avl_balanceR */ -static struct tree_node * -balanceR(struct tree_node *p, bool *h) -{ - if ( p->bal == +1 ) { - p->bal = 0; - } - else if ( p->bal == 0 ) { - p->bal = -1; - *h = false; - } - else /* p->bal == -1 */ { /* rebalance */ - struct tree_node *p1 = p->left; - if ( p1->bal <= 0 ) { /* single LL rotation */ - p->left = p1->right; - p1->right = p; - if ( p1->bal == 0 ) { - p->bal = -1; - p1->bal = +1; - *h = false; - } - else { - p->bal = 0; - p1->bal = 0; - } - p = p1; - } - else { /* double LR rotation */ - struct tree_node *p2 = p1->right; - p1->right = p2->left; - p2->left = p1; - p->left = p2->right; - p2->right = p; - p->bal = ( p2->bal == -1 ) ? +1 : 0; - p1->bal = ( p2->bal == +1 ) ? -1 : 0; - p = p2; - p2->bal = 0; - } - } - return p; -} -/* -->8-- */ - -/* --8<-- avl_del */ -static void -del(struct tree_node **q, struct tree_node **r, bool *h) -{ - if ( (*r)->right ) { - del(q, &(*r)->right, h); - if ( *h ) - *r = balanceR(*r, h); - } - else { - /* copy data */ - (*q)->key = (*r)->key; - (*q)->count = (*r)->count; - - *q = *r; - *r = (*r)->left; - *h = true; - } -} -/* -->8-- */ - -/* --8<-- avl_delete_r */ -static struct tree_node * -delete_r(T x, struct tree_node *p, bool *h) -{ - if ( p == NULL ) { - ERROR("key not found"); - } - else if ( x < p->key ) { - p->left = delete_r(x, p->left, h); - if ( *h ) - p = balanceL(p, h); - } - else if ( x > p->key ) { - p->right = delete_r(x, p->right, h); - if ( *h ) - p = balanceR(p, h); - } - else /* if ( x == p->key ) */ { - struct tree_node *q = p; - if ( q->right == NULL ) { - p = q->left; - *h = true; - } - else if ( q->left == NULL ) { - p = q->right; - *h = true; - } - else { - del(&q, &q->left, h); - if ( *h ) - p = balanceL(p, h); - } - free(q); - } - return p; -} -/* -->8-- */ - -/* --8<-- avl_delete */ -struct tree_node * -delete(struct tree_node *tree, T data) -{ - bool h = false; - return delete_r(data, tree, &h); -} -/* -->8-- */ - -// aux display and verification routines, helpful but not essential -struct trunk { - struct trunk *prev; - char * str; -}; - -void show_trunks(struct trunk *p) -{ - if (!p) return; - show_trunks(p->prev); - printf("%s", p->str); -} - -// this is very haphazzard -void show_tree(struct tree_node *root, struct trunk *prev, int is_left) -{ - if (root == NULL) return; - - struct trunk this_disp = { prev, " " }; - char *prev_str = this_disp.str; - show_tree(root->right, &this_disp, 1); - - if (!prev) - this_disp.str = "---"; - else if (is_left) { - this_disp.str = ".--"; - prev_str = " |"; - } else { - this_disp.str = "`--"; - prev->str = prev_str; - } - - show_trunks(&this_disp); - if ( root->key >= 'A' && root->key <= 'Z' ) - printf("%c\n", root->key); - else - printf("%d\n", root->key); - - if (prev) prev->str = prev_str; - this_disp.str = " |"; - - show_tree(root->left, &this_disp, 0); - if (!prev) puts(""); -} - -void -print(struct tree_node *tree) -{ - if ( tree ) { - print(tree->left); - printf("%d (%d)\n", tree->key, tree->bal); - print(tree->right); - } -} - -int -main() -{ - - -#if 0 /* 1a/b */ - tree = insert(tree, 20); - tree = insert(tree, 4); - show_tree(tree, 0, 0); - - //tree = insert(tree, 15); - tree = insert(tree, 8); - show_tree(tree, 0, 0); -#endif - -#if 0 /* 2a/b */ - tree = insert(tree, 20); - tree = insert(tree, 4); - tree = insert(tree, 26); - tree = insert(tree, 3); - tree = insert(tree, 9); - show_tree(tree, 0, 0); - - //tree = insert(tree, 15); - tree = insert(tree, 8); - show_tree(tree, 0, 0); -#endif - -#if 0 /* 3a/b */ - tree = insert(tree, 20); - tree = insert(tree, 4); - tree = insert(tree, 26); - tree = insert(tree, 3); - tree = insert(tree, 9); - tree = insert(tree, 21); - tree = insert(tree, 30); - tree = insert(tree, 2); - tree = insert(tree, 7); - tree = insert(tree, 11); - show_tree(tree, 0, 0); - - //tree = insert(tree, 15); - tree = insert(tree, 8); - show_tree(tree, 0, 0); -#endif - -#if 0 - tree = insert(tree, 2); - tree = insert(tree, 1); - tree = insert(tree, 4); - tree = insert(tree, 3); - tree = insert(tree, 5); - show_tree(tree, 0, 0); - - tree = delete(tree, 1); - show_tree(tree, 0, 0); -#endif - -#if 0 - tree = insert(tree, 6); - tree = insert(tree, 2); - tree = insert(tree, 9); - tree = insert(tree, 1); - tree = insert(tree, 4); - tree = insert(tree, 8); - tree = insert(tree, 'B'); - tree = insert(tree, 3); - tree = insert(tree, 5); - tree = insert(tree, 7); - tree = insert(tree, 'A'); - tree = insert(tree, 'C'); - tree = insert(tree, 'D'); - show_tree(tree, 0, 0); - - tree = delete(tree, 1); - show_tree(tree, 0, 0); -#endif - - -#if 0 - tree = insert(tree, 5); - tree = insert(tree, 2); - tree = insert(tree, 8); - tree = insert(tree, 1); - tree = insert(tree, 3); - tree = insert(tree, 7); - tree = insert(tree, 'A'); - tree = insert(tree, 4); - tree = insert(tree, 6); - tree = insert(tree, 9); - tree = insert(tree, 'B'); - tree = insert(tree, 'C'); - show_tree(tree, 0, 0); - - tree = delete(tree, 1); - show_tree(tree, 0, 0); -#endif - - -#if 0 - tree = insert(tree, 5); - tree = insert(tree, 3); - tree = insert(tree, 8); - tree = insert(tree, 2); - tree = insert(tree, 4); - tree = insert(tree, 7); - tree = insert(tree, 10); - tree = insert(tree, 1); - tree = insert(tree, 6); - tree = insert(tree, 9); - tree = insert(tree, 11); - - tree = delete(tree, 4); - tree = delete(tree, 8); - tree = delete(tree, 6); - tree = delete(tree, 5); - tree = delete(tree, 2); - tree = delete(tree, 1); - tree = delete(tree, 7); - - show_tree(tree, 0, 0); -#endif - - struct tree_node *tree = NULL; - - srand(time(NULL)); - for ( int i = 0; i != 300000; ++i ) - tree = insert(tree, rand()); - - //show_tree(tree, 0, 0); - - return EXIT_SUCCESS; -} - diff --git a/src/binary-search-tree.c b/src/binary-search-tree.c new file mode 100644 index 0000000..93690e2 --- /dev/null +++ b/src/binary-search-tree.c @@ -0,0 +1,806 @@ +// Binary Search Tree +#include +#include +#include +#include +#include + +#include "util.h" + +/* --8<-- tree_type */ +typedef int T; + +struct tree_node { + struct tree_node *left, *right; + T key; + int count; /* collision counter */ + /* ggf. weitere Felder... */ +}; +/* -->8-- */ + +/* --8<-- tree_isBst */ +static bool +tree_isBstUntil(struct tree_node *tree, T min, T max) +{ + if ( tree == NULL ) + return true; + + if ( tree->key < min || tree->key > max ) + return false; + + return tree_isBstUntil(tree->left, min, tree->key - 1) && + tree_isBstUntil(tree->right, tree->key + 1, max); +} + +bool +tree_isBst(struct tree_node *tree) +{ + return tree_isBstUntil(tree, INT_MIN, INT_MAX); +} +/* -->8-- */ + +/* --8<-- tree_insert */ +struct tree_node * +tree_insert(struct tree_node *tree, T key) +{ + if ( tree == NULL ) { + tree = malloc(sizeof *tree); + if ( tree ) { + tree->key = key; + tree->count = 1; + tree->left = NULL; + tree->right = NULL; + } + else + ERROR("out of memory"); + } + else if ( key < tree->key ) + tree->left = tree_insert(tree->left, key); + else if ( key > tree->key ) + tree->right = tree_insert(tree->right, key); + else /* key == tree->key */ + tree->count++; /* handle collision */ + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_insert_it */ +struct tree_node * +tree_insert_it(struct tree_node *tree, T key) +{ + struct tree_node *parent = NULL; + + for ( struct tree_node *curr = tree; curr; ) { + parent = curr; + + if ( key < curr->key ) { + curr = curr->left; + } + else if ( key > curr->key ) { + curr = curr->right; + } + else { /* key == current->key */ + curr->count++; + return tree; + } + } + + struct tree_node *new_node; + + new_node = malloc(sizeof *new_node); + if ( new_node ) { + new_node->key = key; + new_node->count = 1; + new_node->left = NULL; + new_node->right = NULL; + + if ( parent == NULL ) { + tree = new_node; + } + else if ( key < parent->key ) { + parent->left = new_node; + } + else { + parent->right = new_node; + } + } + else { + ERROR("out of memory"); + } + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_detach_min */ +static struct tree_node * +tree_detach_min(struct tree_node **ptree) +{ + struct tree_node *tree = *ptree; + + if ( tree == NULL ) + return NULL; + else if ( tree->left ) + return tree_detach_min(&tree->left); + else { + *ptree = tree->right; + return tree; + } +} +/* -->8-- */ + +/* --8<-- tree_remove */ +struct tree_node * +tree_remove(struct tree_node *tree, T key) +{ + if ( tree == NULL ) + return NULL; + + if ( key < tree->key ) + tree->left = tree_remove(tree->left, key); + else if ( key > tree->key ) + tree->right = tree_remove(tree->right, key); + else { /* key == tree->key */ + if ( --tree->count == 0 ) { /* Handle Collision */ + struct tree_node *temp = tree; + + if ( tree->left == NULL ) { + tree = tree->right; + } + else if ( tree->right == NULL ) { + tree = tree->left; + } + else { + struct tree_node *min = tree_detach_min(&tree->right); + + min->left = tree->left; + min->right = tree->right; + + tree = min; + } + + free(temp); + } + } + return tree; +} +/* -->8-- */ + +/* --8<-- tree_clear */ +void +tree_clear(struct tree_node *tree) +{ + if ( tree ) { + tree_clear(tree->left); + tree_clear(tree->right); + free(tree); + } +} +/* -->8-- */ + +/* --8<-- tree_lookup */ +struct tree_node * +tree_lookup(struct tree_node *tree, T key) +{ + while ( tree ) + if ( key < tree->key ) + tree = tree->left; + else if ( key > tree->key ) + tree = tree->right; + else /* key == tree->key */ + break; + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_minimum */ +struct tree_node * +tree_minimum(struct tree_node *tree) +{ + if ( tree ) + while ( tree->left ) + tree = tree->left; + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_maximum */ +struct tree_node * +tree_maximum(struct tree_node *tree) +{ + if ( tree ) + while ( tree->right ) + tree = tree->right; + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_height */ +size_t +tree_height(struct tree_node *tree) +{ + if ( tree ) { + size_t hl = tree_height(tree->left); + size_t hr = tree_height(tree->right); + + return ((hl > hr) ? hl : hr) + 1; + } + + return 0; +} +/* -->8-- */ + +/* --8<-- tree_count */ +size_t +tree_count(struct tree_node *tree) +{ + if ( tree ) + return tree_count(tree->left) + tree_count(tree->right) + 1; + + return 0; +} +/* -->8-- */ + +/* --8<-- tree_copy */ +struct tree_node * +tree_copy(struct tree_node *tree) +{ + if ( tree ) { + struct tree_node *new_node; + + new_node = malloc(sizeof *new_node); + if ( new_node ) { + new_node->key = tree->key; + new_node->count = tree->count; + new_node->left = tree_copy(tree->left); + new_node->right = tree_copy(tree->right); + } + else { + ERROR("out of memory"); + } + + return new_node; + } + return NULL; +} +/* -->8-- */ + +/* --8<-- tree_isleaf */ +bool +tree_isleaf(struct tree_node *tree) +{ + return tree->left == NULL && tree->right == NULL; +} +/* -->8-- */ + +/* --8<-- tree_apply_preorder */ +void +tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + visit(tree->key, cl); + tree_apply_preorder(tree->left, visit, cl); + tree_apply_preorder(tree->right, visit, cl); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_inorder */ +void +tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + tree_apply_inorder(tree->left, visit, cl); + visit(tree->key, cl); + tree_apply_inorder(tree->right, visit, cl); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_postorder */ +void +tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + tree_apply_postorder(tree->left, visit, cl); + tree_apply_postorder(tree->right, visit, cl); + visit(tree->key, cl); + } +} +/* -->8-- */ + +/* ===== */ + +/* --8<-- tree_stack_type */ +struct stack_item { + struct stack_item *next; + struct tree_node * data; +}; + +struct stack { + struct stack_item *head; +}; +/* -->8-- */ + +/* --8<-- tree_stack_init */ +static void +stack_init(struct stack *stack) +{ + stack->head = NULL; +} +/* -->8-- */ + +/* --8<-- tree_stack_push */ +static void +stack_push(struct stack *stack, struct tree_node *data) +{ + struct stack_item *new_item; + + if ( (new_item = malloc(sizeof *new_item)) ) { + new_item->data = data; + new_item->next = stack->head; + stack->head = new_item; + } + else + ERROR("out of memory"); +} +/* -->8-- */ + +/* --8<-- tree_stack_pop */ +static bool +stack_pop(struct stack *stack, struct tree_node **data) +{ + if ( stack->head ) { + struct stack_item *next; + + next = stack->head->next; + *data = stack->head->data; + + free(stack->head); + stack->head = next; + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- tree_stack_peek */ +static struct tree_node * +stack_peek(struct stack *stack) +{ + return (stack->head) ? stack->head->data : NULL; +} +/* -->8-- */ + +/* --8<-- tree_stack_empty */ +static bool +stack_empty(struct stack *stack) +{ + return stack->head == NULL; +} +/* -->8-- */ + +/* --8<-- tree_stack_free */ +void +stack_free(struct stack *stack) +{ + struct stack_item *item, *next; + + for ( item = stack->head; item; item = next ) { + next = item->next; + free(item); + } +} +/* -->8-- */ + +/* ===== */ + +/* --8<-- tree_queue_type */ +struct queue_item { + struct queue_item *next; + struct tree_node * data; +}; + +struct queue { + struct queue_item *head, *tail; +}; +/* -->8-- */ + +/* --8<-- tree_queue_init */ +void +queue_init(struct queue *queue) +{ + queue->head = NULL; +} +/* -->8-- */ + +/* --8<-- tree_queue_put */ +void +queue_put(struct queue *queue, struct tree_node *data) +{ + struct queue_item *new_item; + + if ( (new_item = malloc(sizeof *new_item)) ) { + struct queue_item *tail; + + tail = queue->tail; + new_item->data = data; + new_item->next = NULL; + queue->tail = new_item; + + if ( queue->head == NULL ) + queue->head = queue->tail; + else + tail->next = queue->tail; + } + else + ERROR("out of memory"); +} +/* -->8-- */ + +/* --8<-- tree_queue_get */ +bool +queue_get(struct queue *queue, struct tree_node **data) +{ + if ( queue->head ) { + struct queue_item *next; + + next = queue->head->next; + *data = queue->head->data; + + free(queue->head); + queue->head = next; + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- tree_queue_empty */ +bool +queue_empty(struct queue *queue) +{ + return queue->head == NULL; +} +/* -->8-- */ + +/* --8<-- tree_queue_free */ +void +queue_free(struct queue *queue) +{ + struct queue_item *item, *next; + + for ( item = queue->head; item; item = next ) { + next = item->next; + free(item); + } +} +/* -->8-- */ + +/* ===== */ + +/* --8<-- tree_apply_preorder_it */ +void +tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct stack stack; + + stack_init(&stack); + + stack_push(&stack, tree); + + while ( stack_pop(&stack, &tree) ) { + visit(tree->key, cl); + + if ( tree->right ) + stack_push(&stack, tree->right); + if ( tree->left ) + stack_push(&stack, tree->left); + } + + stack_free(&stack); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_inorder_it */ +void +tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct stack stack; + + stack_init(&stack); + + while ( !stack_empty(&stack) || tree ) { + if ( tree ) { + stack_push(&stack, tree); + tree = tree->left; + } + else { + stack_pop(&stack, &tree); + visit(tree->key, cl); + tree = tree->right; + } + } + + stack_free(&stack); + } +} +/* -->8-- */ + +// Hier eine Version für PostOrder-Iterativ: +// Quelle: https://stackoverflow.com/a/16092333 + +/* --8<-- tree_apply_postorder_it */ +void +tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct stack stack; + + stack_init(&stack); + stack_push(&stack, tree); + + while ( !stack_empty(&stack) ) { + struct tree_node *next = stack_peek(&stack); + + bool finishedSubtrees = (next->left == tree || next->right == tree); + + if ( finishedSubtrees || tree_isleaf(next) ) { + stack_pop(&stack, &next); + + visit(next->key, cl); + + tree = next; + } + else { + if ( next->right ) { + stack_push(&stack, next->right); + } + if ( next->left ) { + stack_push(&stack, next->left); + } + } + } + stack_free(&stack); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_levelorder_it */ +void +tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct queue queue; + + queue_init(&queue); + + queue_put(&queue, tree); + + while ( queue_get(&queue, &tree) ) { + visit(tree->key, cl); + + if ( tree->left ) + queue_put(&queue, tree->left); + if ( tree->right ) + queue_put(&queue, tree->right); + } + + queue_free(&queue); + } +} +/* -->8-- */ + +/* ======================== */ + +/* --8<-- tree_iterator_type */ +struct tree_iterator { + struct stack stack; +}; +/* -->8-- */ + +/* --8<-- tree_iterator_push_leftmost */ +static void +tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node) +{ + for ( ; node; node = node->left ) { + stack_push(stack, node); + } +} +/* -->8-- */ + +/* --8<-- tree_iterator_next */ +struct tree_node * +tree_iterator_next(struct tree_iterator *it) +{ + struct tree_node *node = NULL; + + if ( stack_pop(&it->stack, &node) ) { + tree_iterator_push_leftmost(&it->stack, node->right); + } + + return node; +} +/* -->8-- */ + +/* --8<-- tree_iterator_first */ +struct tree_node * +tree_iterator_first(struct tree_iterator *it, struct tree_node *tree) +{ + stack_init(&it->stack); + + tree_iterator_push_leftmost(&it->stack, tree); + + return tree_iterator_next(it); +} +/* -->8-- */ + +/* --8<-- tree_iterator_free */ +void +tree_iterator_free(struct tree_iterator *it) +{ + stack_free(&it->stack); +} +/* -->8-- */ + +/* --8<-- tree_preorder_iterator_next */ +struct tree_node * +tree_preorder_iterator_next(struct tree_iterator *it) +{ + struct tree_node *node = NULL; + + if ( stack_pop(&it->stack, &node) ) { + if ( node->right ) { + stack_push(&it->stack, node->right); + } + if ( node->left ) { + stack_push(&it->stack, node->left); + } + } + + return node; +} +/* -->8-- */ + +/* --8<-- tree_preorder_iterator_first */ +struct tree_node * +tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree) +{ + stack_init(&it->stack); + + if ( tree ) { + stack_push(&it->stack, tree); + + return tree_preorder_iterator_next(it); + } + else { + return NULL; + } +} +/* -->8-- */ + +/* ===== */ + +void +print(T data, void *cl) +{ + (void) cl; + printf("%d\n", data); +} + +#include "treeutil.h" + +int +main_(void) +{ + // Teste den Fall von mycodeschool + + struct tree_node *tree = NULL; + + tree = tree_insert(tree, 12); + tree = tree_insert(tree, 5); + tree = tree_insert(tree, 15); + tree = tree_insert(tree, 3); + tree = tree_insert(tree, 7); + tree = tree_insert(tree, 13); + tree = tree_insert(tree, 17); + tree = tree_insert(tree, 1); + tree = tree_insert(tree, 9); + tree = tree_insert(tree, 14); + tree = tree_insert(tree, 20); + tree = tree_insert(tree, 8); + tree = tree_insert(tree, 11); + tree = tree_insert(tree, 18); + + tree = tree_remove(tree, 15); + + if ( !tree_isBst(tree) ) { + fprintf(stderr, "Tree ist kein BST!!\n"); + return EXIT_FAILURE; + } + + show_tree(tree, 0, 0); + + tree_clear(tree); + + return EXIT_SUCCESS; +} + +int +main__(void) +{ + struct tree_node *tree = NULL; + + tree = tree_insert(tree, 5); + tree = tree_insert(tree, 3); + tree = tree_insert(tree, 7); + tree = tree_insert(tree, 2); + tree = tree_insert(tree, 4); + tree = tree_insert(tree, 6); + tree = tree_insert(tree, 8); + + tree = tree_remove(tree, 2); + tree = tree_remove(tree, 3); + tree = tree_remove(tree, 5); + + if ( !tree_isBst(tree) ) { + fprintf(stderr, "Tree ist kein BST!!\n"); + return EXIT_FAILURE; + } + + show_tree(tree, 0, 0); + + tree_clear(tree); + + return EXIT_SUCCESS; +} + +int +main(void) +{ + struct tree_node *tree = NULL; + + tree = tree_insert_it(tree, 10); + tree = tree_insert_it(tree, 5); + tree = tree_insert_it(tree, 20); + tree = tree_insert_it(tree, 1); + tree = tree_insert_it(tree, 7); + tree = tree_insert_it(tree, 15); + tree = tree_insert_it(tree, 18); + + tree_apply_preorder(tree, print, NULL); + puts("postorder:"); + tree_apply_postorder(tree, print, NULL); + puts("postorder_it:"); + tree_apply_postorder_it(tree, print, NULL); + show_tree(tree, 0, 0); + + puts("levelorder_it:"); + tree_apply_levelorder_it(tree, print, NULL); + + show_tree(tree, 0, 0); + + struct tree_iterator it; + struct tree_node * node = tree_preorder_iterator_first(&it, tree); + while ( node ) { + fprintf(stdout, "%d\n", node->key); + + node = tree_preorder_iterator_next(&it); + } + tree_iterator_free(&it); + + tree_clear(tree); + + return EXIT_SUCCESS; +} diff --git a/src/dlist.c b/src/dlist.c deleted file mode 100644 index 55e42d7..0000000 --- a/src/dlist.c +++ /dev/null @@ -1,504 +0,0 @@ -/* dlist -- double linked list */ - -/* Standard C */ -#include -#include -#include -#include -#include - -/* Project */ -#include "util.h" - -/* --8<-- dlist_type */ -typedef int T; - -struct dlist { - struct dlist_element *head, *tail; -}; - -struct dlist_element { - struct dlist_element *prev, *next; - T data; -}; -/* -->8-- */ - -/* --8<-- dlist_init */ -void -dlist_init(struct dlist *dlist) -{ - dlist->head = NULL; - dlist->tail = NULL; -} -/* -->8-- */ - -/* --8<-- dlist_empty */ -bool -dlist_empty(struct dlist *dlist) -{ - return dlist->head == NULL; -} -/* -->8-- */ - -/* --8<-- dlist_create_element */ -static struct dlist_element * -create_element(T data) -{ - struct dlist_element *element; - - element = malloc(sizeof *element); - if ( element ) { - element->data = data; - } - - return element; -} -/* -->8-- */ - -/* --8<-- dlist_push_front */ -struct dlist_element * -dlist_push_front(struct dlist *dlist, T data) -{ - struct dlist_element *element; - - element = create_element(data); - if ( element ) { - element->prev = NULL; /* Vorgänger ist in jedem Fall NULL */ - - if ( dlist_empty(dlist) ) { - element->next = NULL; - dlist->tail = element; - } - else { - element->next = dlist->head; - element->next->prev = element; - } - - dlist->head = element; /* Neues Element ist in jedem Fall der neue Anfang! */ - } - else - ERROR("out of memory"); - - return element; -} -/* -->8-- */ - -/* --8<-- dlist_push_back */ -struct dlist_element * -dlist_push_back(struct dlist *dlist, T data) -{ - struct dlist_element *element; - - element = create_element(data); - if ( element ) { - element->next = NULL; /* Nachfolger ist in jedem Fall NULL */ - - if ( dlist_empty(dlist) ) { - element->prev = NULL; - dlist->head = element; - } - else { - element->prev = dlist->tail; - element->prev->next = element; - } - - dlist->tail = element; /* Neues Element ist in jedem Fall das neue Ende! */ - } - else - ERROR("out of memory"); - - return element; -} -/* -->8-- */ - -/* --8<-- dlist_pop_front */ -bool -dlist_pop_front(struct dlist *dlist, T *data) -{ - if ( dlist->head ) { - struct dlist_element *element = dlist->head; - - dlist->head = element->next; - - if ( dlist->head == NULL ) - dlist->tail = NULL; - else - element->next->prev = NULL; - - if ( data ) { - *data = element->data; - } - free(element); - - return true; - } - else - return false; -} -/* -->8-- */ - -/* --8<-- dlist_pop_back */ -bool -dlist_pop_back(struct dlist *dlist, T *data) -{ - if ( dlist->head ) { - struct dlist_element *element = dlist->tail; - - dlist->tail = element->prev; - - if ( dlist->tail == NULL ) - dlist->head = NULL; - else - element->prev->next = NULL; - - if ( data ) { - *data = element->data; - } - free(element); - - return true; - } - else - return false; -} -/* -->8-- */ - -/* --8<-- dlist_insert_next */ -struct dlist_element * -dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data) -{ - struct dlist_element *new_element; - - new_element = create_element(data); - if ( new_element ) { - if ( dlist->head == NULL ) { - dlist->head = new_element; - dlist->head->prev = NULL; - dlist->head->next = NULL; - dlist->tail = new_element; - } - else { - new_element->next = element->next; - new_element->prev = element; - - if ( element->next == NULL ) - dlist->tail = new_element; - else - element->next->prev = new_element; - - element->next = new_element; - } - } - else - ERROR("out of memory"); - - return new_element; -} -/* -->8-- */ - -/* --8<-- dlist_insert_prev */ -struct dlist_element * -dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data) -{ - struct dlist_element *new_element; - - new_element = create_element(data); - if ( new_element ) { - if ( dlist->head == NULL ) { - dlist->head = new_element; - dlist->head->prev = NULL; - dlist->head->next = NULL; - dlist->tail = new_element; - } - else { - new_element->next = element; - new_element->prev = element->prev; - - if ( element->prev == NULL ) - dlist->head = new_element; - else - element->prev->next = new_element; - - element->prev = new_element; - } - } - else - ERROR("out of memory"); - - return new_element; -} -/* -->8-- */ - -/* --8<-- dlist_remove */ -void -dlist_remove(struct dlist *dlist, struct dlist_element *element) -{ - if ( element == dlist->head ) { - dlist->head = element->next; - - if ( dlist->head == NULL ) - dlist->tail = NULL; - else - element->next->prev = NULL; - } - else { - element->prev->next = element->next; - - if ( element->next == NULL ) - dlist->tail = element->prev; - else - element->next->prev = element->prev; - } - - free(element); -} -/* -->8-- */ - -/* --8<-- dlist_free */ -void -dlist_free(struct dlist *dlist) -{ - struct dlist_element *elem, *next; - - for ( elem = dlist->head; elem; elem = next ) { - next = elem->next; - free(elem); - } - - dlist_init(dlist); -} -/* -->8-- */ - -void -dlist_apply_rev(struct dlist *dlist, void (*visit)(T data, void *cl), void *cl) -{ - for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev ) { - visit(elem->data, cl); - } -} - -void -print_list(const char *msg, struct dlist *dlist) -{ - printf("%s:", msg); - - for ( struct dlist_element *elem = dlist->head; elem; elem = elem->next ) - printf(" %d", elem->data); - - putchar('\n'); -} - -void -print_list_rev(const char *msg, struct dlist *dlist) -{ - printf("%s:", msg); - - for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev ) - printf(" %d", elem->data); - - putchar('\n'); -} - -void -remove_if(struct dlist *list) -{ - struct dlist_element *elem, *next; - - for ( elem = list->head; elem; elem = next ) { - next = elem->next; - - if ( (elem->data & 1) == 1 ) { - dlist_remove(list, elem); - } - } -} - -/* --8<-- dlist_merge */ -struct dlist * -dlist_merge(struct dlist *list1, struct dlist *list2) -{ - struct dlist_element *head = NULL, - *cur = NULL, - *e1 = list1->head, - *e2 = list2->head; - - while ( e1 && e2 ) // Solange in e1 UND e2 Elemente sind... - { - if ( e1->data < e2->data ) { - e1->prev = cur; - if ( cur ) - cur->next = e1; - else - head = e1; - cur = e1; - e1 = e1->next; - } - else { - e2->prev = cur; - if ( cur ) - cur->next = e2; - else - head = e2; - cur = e2; - e2 = e2->next; - } - } - - if ( e1 ) // in e1 sind noch Elemente vorhanden! - { - assert(e2 == NULL); - - e1->prev = cur; - if ( cur ) - cur->next = e1; - else - head = e1; - - // list1->tail zeigt bereits auf das letzte Element in list1 - } - else /* if ( e2 ) */ - { - assert(e1 == NULL); - assert(e2); - - e2->prev = cur; - if ( cur ) - cur->next = e2; - else - head = e2; - - list1->tail = list2->tail; // list2->tail ist das Ende der Liste - } - - // Kopf neu setzen... - list1->head = head; - - // Liste2 ist leer - list2->head = NULL; - list2->tail = NULL; - - // Zeiger auf Liste1 zurückliefern - return list1; -} -/* -->8-- */ - -/* --8<-- dlist_sort */ -struct dlist * -dlist_sort(struct dlist *list) -{ - if ( list->head == NULL || list->head->next == NULL ) // Leer oder nur ein Element? => Fertig - return list; - - struct dlist_element *slow = list->head, - *fast = list->head->next; - - while ( fast && fast->next ) - slow = slow->next, fast = fast->next->next; - - struct dlist list1 = { .head = list->head, .tail = slow }, - list2 = { .head = slow->next, .tail = list->tail }; - - list1.tail->next = list2.head->prev = NULL; - - dlist_merge(dlist_sort(&list1), dlist_sort(&list2)); - - list->head = list1.head; - list->tail = list1.tail; - - return list; -} -/* -->8-- */ - -void -merge_test(void) -{ - struct dlist l1, l2; - - dlist_init(&l1); - dlist_init(&l2); - - dlist_push_back(&l1, 7); - dlist_push_back(&l1, 10); - dlist_push_back(&l1, 11); - dlist_push_back(&l1, 19); - dlist_push_back(&l1, 23); - - dlist_push_back(&l2, 4); - dlist_push_back(&l2, 14); - dlist_push_back(&l2, 15); - - struct dlist *ptr; - ptr = dlist_merge(&l1, &l2); - - struct dlist_element *cur; - for ( cur = ptr->head; cur; cur = cur->next ) { - if ( cur->prev ) - printf("%4d", cur->prev->data); - else - printf("xxx "); - printf("%4d", cur->data); - if ( cur->next ) - printf("%4d", cur->next->data); - else - printf(" xxx"); - - puts(""); - } - - dlist_free(&l1); - dlist_free(&l2); -} - -void -ls() -{ - struct dlist list; - - dlist_init(&list); - - for ( int i = 0; i != 30000000; ++i ) - dlist_insert_prev(&list, list.tail, rand() % 9999); - - //print_list("Unsortiert:", &list); - printf("start\n"); - clock_t start = clock(); - dlist_sort(&list); - clock_t ende = clock(); - - printf("Dauer: %.3fsec\n", ((double) ende - start) / CLOCKS_PER_SEC); - //print_list("Sortiert:", &list); - //print_list_rev("Sortiert:", &list); - - dlist_free(&list); -} - -int -main(void) -{ - ls(); - -#if 0 - merge_test(); -#endif - -#if 0 - struct dlist list; - - dlist_init(&list); - - for ( int i = 0; i != 10; ++i ) - dlist_insert_prev(&list, list.tail, i); - - print_list("Ausgabe: ", &list); - - remove_if(&list); - - print_list("Ausgabe: ", &list); - - dlist_free(&list); - - ls(); - - return EXIT_SUCCESS; -#endif -} diff --git a/src/double-linked-list.c b/src/double-linked-list.c new file mode 100644 index 0000000..55e42d7 --- /dev/null +++ b/src/double-linked-list.c @@ -0,0 +1,504 @@ +/* dlist -- double linked list */ + +/* Standard C */ +#include +#include +#include +#include +#include + +/* Project */ +#include "util.h" + +/* --8<-- dlist_type */ +typedef int T; + +struct dlist { + struct dlist_element *head, *tail; +}; + +struct dlist_element { + struct dlist_element *prev, *next; + T data; +}; +/* -->8-- */ + +/* --8<-- dlist_init */ +void +dlist_init(struct dlist *dlist) +{ + dlist->head = NULL; + dlist->tail = NULL; +} +/* -->8-- */ + +/* --8<-- dlist_empty */ +bool +dlist_empty(struct dlist *dlist) +{ + return dlist->head == NULL; +} +/* -->8-- */ + +/* --8<-- dlist_create_element */ +static struct dlist_element * +create_element(T data) +{ + struct dlist_element *element; + + element = malloc(sizeof *element); + if ( element ) { + element->data = data; + } + + return element; +} +/* -->8-- */ + +/* --8<-- dlist_push_front */ +struct dlist_element * +dlist_push_front(struct dlist *dlist, T data) +{ + struct dlist_element *element; + + element = create_element(data); + if ( element ) { + element->prev = NULL; /* Vorgänger ist in jedem Fall NULL */ + + if ( dlist_empty(dlist) ) { + element->next = NULL; + dlist->tail = element; + } + else { + element->next = dlist->head; + element->next->prev = element; + } + + dlist->head = element; /* Neues Element ist in jedem Fall der neue Anfang! */ + } + else + ERROR("out of memory"); + + return element; +} +/* -->8-- */ + +/* --8<-- dlist_push_back */ +struct dlist_element * +dlist_push_back(struct dlist *dlist, T data) +{ + struct dlist_element *element; + + element = create_element(data); + if ( element ) { + element->next = NULL; /* Nachfolger ist in jedem Fall NULL */ + + if ( dlist_empty(dlist) ) { + element->prev = NULL; + dlist->head = element; + } + else { + element->prev = dlist->tail; + element->prev->next = element; + } + + dlist->tail = element; /* Neues Element ist in jedem Fall das neue Ende! */ + } + else + ERROR("out of memory"); + + return element; +} +/* -->8-- */ + +/* --8<-- dlist_pop_front */ +bool +dlist_pop_front(struct dlist *dlist, T *data) +{ + if ( dlist->head ) { + struct dlist_element *element = dlist->head; + + dlist->head = element->next; + + if ( dlist->head == NULL ) + dlist->tail = NULL; + else + element->next->prev = NULL; + + if ( data ) { + *data = element->data; + } + free(element); + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- dlist_pop_back */ +bool +dlist_pop_back(struct dlist *dlist, T *data) +{ + if ( dlist->head ) { + struct dlist_element *element = dlist->tail; + + dlist->tail = element->prev; + + if ( dlist->tail == NULL ) + dlist->head = NULL; + else + element->prev->next = NULL; + + if ( data ) { + *data = element->data; + } + free(element); + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- dlist_insert_next */ +struct dlist_element * +dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data) +{ + struct dlist_element *new_element; + + new_element = create_element(data); + if ( new_element ) { + if ( dlist->head == NULL ) { + dlist->head = new_element; + dlist->head->prev = NULL; + dlist->head->next = NULL; + dlist->tail = new_element; + } + else { + new_element->next = element->next; + new_element->prev = element; + + if ( element->next == NULL ) + dlist->tail = new_element; + else + element->next->prev = new_element; + + element->next = new_element; + } + } + else + ERROR("out of memory"); + + return new_element; +} +/* -->8-- */ + +/* --8<-- dlist_insert_prev */ +struct dlist_element * +dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data) +{ + struct dlist_element *new_element; + + new_element = create_element(data); + if ( new_element ) { + if ( dlist->head == NULL ) { + dlist->head = new_element; + dlist->head->prev = NULL; + dlist->head->next = NULL; + dlist->tail = new_element; + } + else { + new_element->next = element; + new_element->prev = element->prev; + + if ( element->prev == NULL ) + dlist->head = new_element; + else + element->prev->next = new_element; + + element->prev = new_element; + } + } + else + ERROR("out of memory"); + + return new_element; +} +/* -->8-- */ + +/* --8<-- dlist_remove */ +void +dlist_remove(struct dlist *dlist, struct dlist_element *element) +{ + if ( element == dlist->head ) { + dlist->head = element->next; + + if ( dlist->head == NULL ) + dlist->tail = NULL; + else + element->next->prev = NULL; + } + else { + element->prev->next = element->next; + + if ( element->next == NULL ) + dlist->tail = element->prev; + else + element->next->prev = element->prev; + } + + free(element); +} +/* -->8-- */ + +/* --8<-- dlist_free */ +void +dlist_free(struct dlist *dlist) +{ + struct dlist_element *elem, *next; + + for ( elem = dlist->head; elem; elem = next ) { + next = elem->next; + free(elem); + } + + dlist_init(dlist); +} +/* -->8-- */ + +void +dlist_apply_rev(struct dlist *dlist, void (*visit)(T data, void *cl), void *cl) +{ + for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev ) { + visit(elem->data, cl); + } +} + +void +print_list(const char *msg, struct dlist *dlist) +{ + printf("%s:", msg); + + for ( struct dlist_element *elem = dlist->head; elem; elem = elem->next ) + printf(" %d", elem->data); + + putchar('\n'); +} + +void +print_list_rev(const char *msg, struct dlist *dlist) +{ + printf("%s:", msg); + + for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev ) + printf(" %d", elem->data); + + putchar('\n'); +} + +void +remove_if(struct dlist *list) +{ + struct dlist_element *elem, *next; + + for ( elem = list->head; elem; elem = next ) { + next = elem->next; + + if ( (elem->data & 1) == 1 ) { + dlist_remove(list, elem); + } + } +} + +/* --8<-- dlist_merge */ +struct dlist * +dlist_merge(struct dlist *list1, struct dlist *list2) +{ + struct dlist_element *head = NULL, + *cur = NULL, + *e1 = list1->head, + *e2 = list2->head; + + while ( e1 && e2 ) // Solange in e1 UND e2 Elemente sind... + { + if ( e1->data < e2->data ) { + e1->prev = cur; + if ( cur ) + cur->next = e1; + else + head = e1; + cur = e1; + e1 = e1->next; + } + else { + e2->prev = cur; + if ( cur ) + cur->next = e2; + else + head = e2; + cur = e2; + e2 = e2->next; + } + } + + if ( e1 ) // in e1 sind noch Elemente vorhanden! + { + assert(e2 == NULL); + + e1->prev = cur; + if ( cur ) + cur->next = e1; + else + head = e1; + + // list1->tail zeigt bereits auf das letzte Element in list1 + } + else /* if ( e2 ) */ + { + assert(e1 == NULL); + assert(e2); + + e2->prev = cur; + if ( cur ) + cur->next = e2; + else + head = e2; + + list1->tail = list2->tail; // list2->tail ist das Ende der Liste + } + + // Kopf neu setzen... + list1->head = head; + + // Liste2 ist leer + list2->head = NULL; + list2->tail = NULL; + + // Zeiger auf Liste1 zurückliefern + return list1; +} +/* -->8-- */ + +/* --8<-- dlist_sort */ +struct dlist * +dlist_sort(struct dlist *list) +{ + if ( list->head == NULL || list->head->next == NULL ) // Leer oder nur ein Element? => Fertig + return list; + + struct dlist_element *slow = list->head, + *fast = list->head->next; + + while ( fast && fast->next ) + slow = slow->next, fast = fast->next->next; + + struct dlist list1 = { .head = list->head, .tail = slow }, + list2 = { .head = slow->next, .tail = list->tail }; + + list1.tail->next = list2.head->prev = NULL; + + dlist_merge(dlist_sort(&list1), dlist_sort(&list2)); + + list->head = list1.head; + list->tail = list1.tail; + + return list; +} +/* -->8-- */ + +void +merge_test(void) +{ + struct dlist l1, l2; + + dlist_init(&l1); + dlist_init(&l2); + + dlist_push_back(&l1, 7); + dlist_push_back(&l1, 10); + dlist_push_back(&l1, 11); + dlist_push_back(&l1, 19); + dlist_push_back(&l1, 23); + + dlist_push_back(&l2, 4); + dlist_push_back(&l2, 14); + dlist_push_back(&l2, 15); + + struct dlist *ptr; + ptr = dlist_merge(&l1, &l2); + + struct dlist_element *cur; + for ( cur = ptr->head; cur; cur = cur->next ) { + if ( cur->prev ) + printf("%4d", cur->prev->data); + else + printf("xxx "); + printf("%4d", cur->data); + if ( cur->next ) + printf("%4d", cur->next->data); + else + printf(" xxx"); + + puts(""); + } + + dlist_free(&l1); + dlist_free(&l2); +} + +void +ls() +{ + struct dlist list; + + dlist_init(&list); + + for ( int i = 0; i != 30000000; ++i ) + dlist_insert_prev(&list, list.tail, rand() % 9999); + + //print_list("Unsortiert:", &list); + printf("start\n"); + clock_t start = clock(); + dlist_sort(&list); + clock_t ende = clock(); + + printf("Dauer: %.3fsec\n", ((double) ende - start) / CLOCKS_PER_SEC); + //print_list("Sortiert:", &list); + //print_list_rev("Sortiert:", &list); + + dlist_free(&list); +} + +int +main(void) +{ + ls(); + +#if 0 + merge_test(); +#endif + +#if 0 + struct dlist list; + + dlist_init(&list); + + for ( int i = 0; i != 10; ++i ) + dlist_insert_prev(&list, list.tail, i); + + print_list("Ausgabe: ", &list); + + remove_if(&list); + + print_list("Ausgabe: ", &list); + + dlist_free(&list); + + ls(); + + return EXIT_SUCCESS; +#endif +} diff --git a/src/hash-table.c b/src/hash-table.c new file mode 100644 index 0000000..256fac9 --- /dev/null +++ b/src/hash-table.c @@ -0,0 +1,220 @@ +#include +#include +#include +#include +#include + +#include "util.h" + +/* --8<-- hash_type */ +typedef int T; + +struct hash_item { + struct hash_item *next; + char * key; + T data; +}; + +struct hash_tab { + struct hash_item *table[251]; // fit for your needs... +}; +/* -->8-- */ + +/* --8<-- hash_key */ +static unsigned long +hash_key(const unsigned char *str) +{ + unsigned long hash = 5381; + unsigned int c; + + while ( (c = *str++) != '\0' ) + hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + + return hash; +} +/* -->8-- */ + +/* --8<-- hash_init */ +void +hash_init(struct hash_tab *ht) +{ + for ( size_t i = 0; i != NELEM(ht->table); ++i ) + ht->table[i] = NULL; +} +/* -->8-- */ + +/* --8<-- hash_add */ +static struct hash_item * +hash_add(struct hash_item *next, const char *key, T data) +{ + struct hash_item *new_item; + char * new_key; + + new_key = strdup(key); // strdup: not standard but commonly used... + new_item = malloc(sizeof *new_item); + + if ( new_key == NULL || new_item == NULL ) { + free(new_key); + free(new_item); + ERROR("out of memory"); + return NULL; + } + + new_item->next = next; + new_item->key = new_key; + new_item->data = data; + + return new_item; +} +/* -->8-- */ + +/* --8<-- hash_lookup */ +T * +hash_lookup(struct hash_tab *ht, const char *key, T data, int create) +{ + unsigned long h; + struct hash_item *item; + + h = hash_key((const unsigned char *) key) % NELEM(ht->table); + for ( item = ht->table[h]; item; item = item->next ) + if ( strcmp(key, item->key) == 0 ) + return &item->data; + + // not found! create? + if ( create ) { + item = hash_add(ht->table[h], key, data); + if ( item ) + ht->table[h] = item; + else + ERROR("can't create item"); + } + + return item ? &item->data : NULL; +} +/* -->8-- */ + +/* --8<-- hash_delete */ +bool +hash_delete(struct hash_tab *ht, const char *key) +{ + unsigned long h; + struct hash_item *prev, *p; + + h = hash_key((const unsigned char *) key) % NELEM(ht->table); + prev = NULL; + for ( p = ht->table[h]; p; p = p->next ) { + if ( strcmp(key, p->key) == 0 ) { + if ( prev == NULL ) + ht->table[h] = p->next; + else + prev->next = p->next; + + free(p->key); + free(p); + + return true; // successfully removed! + } + prev = p; + } + + return false; +} +/* -->8-- */ + +/* --8<-- hash_apply */ +void +hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl) +{ + struct hash_item *item; + + for ( size_t i = 0; i != NELEM(ht->table); ++i ) + for ( item = ht->table[i]; item; item = item->next ) + visit(item->key, item->data, cl); +} +/* -->8-- */ + +/* --8<-- hash_free */ +void +hash_free(struct hash_tab *ht) +{ + struct hash_item *p, *next; + + for ( size_t i = 0; i != NELEM(ht->table); ++i ) { + for ( p = ht->table[i]; p; p = next ) { + next = p->next; + free(p->key); + free(p); + } + ht->table[i] = NULL; + } +} +/* -->8-- */ + +static int +getword(FILE *fp, char *buf, size_t size, int first(int), int rest(int)) +{ + size_t i = 0; + int c; + + c = getc(fp); + for ( ; c != EOF; c = getc(fp) ) + if ( first(c) ) { + if ( i < size - 1 ) + buf[i++] = c; + c = getc(fp); + break; + } + + for ( ; c != EOF && rest(c); c = getc(fp) ) + if ( i < size - 1 ) + buf[i++] = c; + + if ( i < size ) + buf[i] = 0; + else + buf[size - 1] = 0; + + if ( c != EOF ) + ungetc(c, fp); + + return c > 0; +} + +static int +first(int c) +{ + return isalpha(c); +} + +static int +rest(int c) +{ + return isalpha(c) || c == '_'; +} + +static void +print(const char *key, T data, void *cl) +{ + fprintf(cl, "%s: %d\n", key, data); +} + +int +main() +{ + struct hash_tab ht[1]; + char word[100]; + + hash_init(ht); + + while ( getword(stdin, word, sizeof word, first, rest) ) { + T *p = hash_lookup(ht, word, 0, 1); + if ( p ) + ++(*p); + } + + hash_delete(ht, "new_item"); + + hash_apply(ht, print, stdout); + + hash_free(ht); +} diff --git a/src/hashtab.c b/src/hashtab.c deleted file mode 100644 index 256fac9..0000000 --- a/src/hashtab.c +++ /dev/null @@ -1,220 +0,0 @@ -#include -#include -#include -#include -#include - -#include "util.h" - -/* --8<-- hash_type */ -typedef int T; - -struct hash_item { - struct hash_item *next; - char * key; - T data; -}; - -struct hash_tab { - struct hash_item *table[251]; // fit for your needs... -}; -/* -->8-- */ - -/* --8<-- hash_key */ -static unsigned long -hash_key(const unsigned char *str) -{ - unsigned long hash = 5381; - unsigned int c; - - while ( (c = *str++) != '\0' ) - hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ - - return hash; -} -/* -->8-- */ - -/* --8<-- hash_init */ -void -hash_init(struct hash_tab *ht) -{ - for ( size_t i = 0; i != NELEM(ht->table); ++i ) - ht->table[i] = NULL; -} -/* -->8-- */ - -/* --8<-- hash_add */ -static struct hash_item * -hash_add(struct hash_item *next, const char *key, T data) -{ - struct hash_item *new_item; - char * new_key; - - new_key = strdup(key); // strdup: not standard but commonly used... - new_item = malloc(sizeof *new_item); - - if ( new_key == NULL || new_item == NULL ) { - free(new_key); - free(new_item); - ERROR("out of memory"); - return NULL; - } - - new_item->next = next; - new_item->key = new_key; - new_item->data = data; - - return new_item; -} -/* -->8-- */ - -/* --8<-- hash_lookup */ -T * -hash_lookup(struct hash_tab *ht, const char *key, T data, int create) -{ - unsigned long h; - struct hash_item *item; - - h = hash_key((const unsigned char *) key) % NELEM(ht->table); - for ( item = ht->table[h]; item; item = item->next ) - if ( strcmp(key, item->key) == 0 ) - return &item->data; - - // not found! create? - if ( create ) { - item = hash_add(ht->table[h], key, data); - if ( item ) - ht->table[h] = item; - else - ERROR("can't create item"); - } - - return item ? &item->data : NULL; -} -/* -->8-- */ - -/* --8<-- hash_delete */ -bool -hash_delete(struct hash_tab *ht, const char *key) -{ - unsigned long h; - struct hash_item *prev, *p; - - h = hash_key((const unsigned char *) key) % NELEM(ht->table); - prev = NULL; - for ( p = ht->table[h]; p; p = p->next ) { - if ( strcmp(key, p->key) == 0 ) { - if ( prev == NULL ) - ht->table[h] = p->next; - else - prev->next = p->next; - - free(p->key); - free(p); - - return true; // successfully removed! - } - prev = p; - } - - return false; -} -/* -->8-- */ - -/* --8<-- hash_apply */ -void -hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl) -{ - struct hash_item *item; - - for ( size_t i = 0; i != NELEM(ht->table); ++i ) - for ( item = ht->table[i]; item; item = item->next ) - visit(item->key, item->data, cl); -} -/* -->8-- */ - -/* --8<-- hash_free */ -void -hash_free(struct hash_tab *ht) -{ - struct hash_item *p, *next; - - for ( size_t i = 0; i != NELEM(ht->table); ++i ) { - for ( p = ht->table[i]; p; p = next ) { - next = p->next; - free(p->key); - free(p); - } - ht->table[i] = NULL; - } -} -/* -->8-- */ - -static int -getword(FILE *fp, char *buf, size_t size, int first(int), int rest(int)) -{ - size_t i = 0; - int c; - - c = getc(fp); - for ( ; c != EOF; c = getc(fp) ) - if ( first(c) ) { - if ( i < size - 1 ) - buf[i++] = c; - c = getc(fp); - break; - } - - for ( ; c != EOF && rest(c); c = getc(fp) ) - if ( i < size - 1 ) - buf[i++] = c; - - if ( i < size ) - buf[i] = 0; - else - buf[size - 1] = 0; - - if ( c != EOF ) - ungetc(c, fp); - - return c > 0; -} - -static int -first(int c) -{ - return isalpha(c); -} - -static int -rest(int c) -{ - return isalpha(c) || c == '_'; -} - -static void -print(const char *key, T data, void *cl) -{ - fprintf(cl, "%s: %d\n", key, data); -} - -int -main() -{ - struct hash_tab ht[1]; - char word[100]; - - hash_init(ht); - - while ( getword(stdin, word, sizeof word, first, rest) ) { - T *p = hash_lookup(ht, word, 0, 1); - if ( p ) - ++(*p); - } - - hash_delete(ht, "new_item"); - - hash_apply(ht, print, stdout); - - hash_free(ht); -} diff --git a/src/list.c b/src/list.c deleted file mode 100644 index d18dae4..0000000 --- a/src/list.c +++ /dev/null @@ -1,264 +0,0 @@ -/* simple Implementation of single linked lists */ -/* written and placed in the public domain by Thomas Schmucker */ - -/* Standard C */ -#include -#include -#include - -/* Project */ -#include "util.h" - -/* --8<-- list_type */ -typedef int T; - -struct list_item { - struct list_item *next; - T data; -}; -/* -->8-- */ - -/* --8<-- list_add */ -struct list_item * -list_add(struct list_item *next, T data) -{ - struct list_item *new_item; - - new_item = malloc(sizeof *new_item); - if ( new_item ) { - new_item->data = data; - new_item->next = next; - } - else { - ERROR("out of memory"); - } - - return new_item; -} -/* -->8-- */ - -/* --8<-- list_insert_next */ -void -list_insert_next(struct list_item *list, T data) -{ - struct list_item *new_item; - - new_item = list_add(list->next, data); - if ( new_item ) { - list->next = new_item; - } - else { - ERROR("out of memory"); - } -} -/* -->8-- */ - -/* --8<-- list_delete */ -struct list_item * -list_delete(struct list_item *list, T data) -{ - struct list_item *prev = NULL; - - for ( struct list_item *p = list; p; p = p->next ) { - if ( p->data == data ) { - if ( prev == NULL ) { /* first element in list? */ - list = p->next; - } - else { - prev->next = p->next; - } - - free(p); - - return list; - } - prev = p; - } -#ifdef LIST_REPORT_ERROR - ERROR("data not found"); -#endif - return list; -} -/* -->8-- */ - -/* --8<-- list_delete_next */ -void -list_delete_next(struct list_item *list) -{ - if ( list->next ) { - struct list_item *temp = list->next; - - list->next = list->next->next; - - free(temp); - } -} -/* -->8-- */ - -/* --8<-- list_length */ -size_t -list_length(struct list_item *list) -{ - size_t len = 0; - - for ( ; list; list = list->next ) { - ++len; - } - - return len; -} -/* -->8-- */ - -/* --8<-- list_copy */ -struct list_item * -list_copy(struct list_item *list) -{ - struct list_item *head = NULL, **p = &head; - - for ( ; list; list = list->next ) { - *p = malloc(sizeof **p); - if ( *p ) { - (*p)->data = list->data; // copy elements - p = &(*p)->next; - } - else { - ERROR("out of memory"); - } - } - *p = NULL; - return head; -} -/* -->8-- */ - -/* --8<-- list_reverse */ -struct list_item * -list_reverse(struct list_item *list) -{ - struct list_item *head = NULL, *next; - - for ( ; list; list = next ) { - next = list->next; - list->next = head; - head = list; - } - return head; -} -/* -->8-- */ - -/* --8<-- list_apply */ -void -list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl) -{ - for ( ; list; list = list->next ) { - visit(list->data, cl); - } -} -/* -->8-- */ - -/* --8<-- list_merge */ -struct list_item * -list_merge(struct list_item *a, struct list_item *b) -{ - struct list_item dummy = { .next = NULL }; - struct list_item *head = &dummy, *c = head; - - while ( a && b ) - if ( a->data < b->data ) { - c->next = a, c = a, a = a->next; - } - else { - c->next = b, c = b, b = b->next; - } - - c->next = a ? a : b; - - return head->next; -} -/* -->8-- */ - -/* --8<-- list_sort */ -struct list_item * -list_sort(struct list_item *c) -{ - if ( c == NULL || c->next == NULL ) - return c; - - struct list_item *a = c, - *b = c->next; - - while ( b && b->next ) { - c = c->next, b = b->next->next; - } - - b = c->next, c->next = NULL; - - return list_merge(list_sort(a), list_sort(b)); -} -/* -->8-- */ - -/* --8<-- list_free */ -void -list_free(struct list_item *list) -{ - struct list_item *next; - - for ( ; list; list = next ) { - next = list->next; - free(list); - } -} -/* -->8-- */ - -/* --8<-- list_apply_sample */ -static void -print_data(T data, void *cl) -{ - fprintf(cl, "%d\n", data); -} -/* -->8-- */ - -int -main() -{ - clock_t start; - - /* - struct list_item *mylist = NULL; - - mylist = list_add(mylist, 42); - mylist = list_add(mylist, 43); - mylist = list_add(mylist, 44); - - mylist = list_delete(mylist, 45); - - list_apply(mylist, print_data, stdout); - - struct list_item *mylist2 = list_reverse(list_copy(mylist)); - - list_free(mylist); - list_apply(mylist2, print_data); - list_free(mylist2); - */ - - srand(time(NULL)); - - static const int COUNT = 10000000; - - struct list_item *x = NULL; - for ( int i = 0; i != COUNT; ++i ) { - int r = rand(); - x = list_add(x, r); - } - - puts("start"); - start = clock(); - x = list_sort(x); - printf("Fertig: %.3lf sec\n", (double) (clock() - start) / CLOCKS_PER_SEC); - - //list_apply(x, print_data); - printf("Len: %zu\n", list_length(x)); - - list_free(x); - - return EXIT_SUCCESS; -} diff --git a/src/rb.c b/src/rb.c deleted file mode 100644 index 7c2d2c1..0000000 --- a/src/rb.c +++ /dev/null @@ -1,614 +0,0 @@ -/* - Implementierung übernommen von: https://web.archive.org/web/20140328232325/http://en.literateprograms.org/Red-black_tree_(C) - */ - -#include -#include -#include - -#include "util.h" - -/* The authors of this work have released all rights to it and placed it -in the public domain under the Creative Commons CC0 1.0 waiver -(http://creativecommons.org/publicdomain/zero/1.0/). - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, -EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF -MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. -IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY -CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, -TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE -SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - -Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567 -*/ - -enum rbtree_node_color { RED, - BLACK }; - -typedef struct rbtree_node_t { - void * key; - void * value; - struct rbtree_node_t * left; - struct rbtree_node_t * right; - struct rbtree_node_t * parent; - enum rbtree_node_color color; -} * rbtree_node; - -typedef struct rbtree_t { - rbtree_node root; -} * rbtree; - -typedef int (*compare_func)(void *left, void *right); - -rbtree rbtree_create(); -void * rbtree_lookup(rbtree t, void *key, compare_func compare); -void rbtree_insert(rbtree t, void *key, void *value, compare_func compare); -void rbtree_delete(rbtree t, void *key, compare_func compare); - -#include -#include - -typedef rbtree_node node; -typedef enum rbtree_node_color color; - -static node grandparent(node n); -static node sibling(node n); -static node uncle(node n); -static void verify_properties(rbtree t); -static void verify_property_1(node root); -static void verify_property_2(node root); -static color node_color(node n); -static void verify_property_4(node root); -static void verify_property_5(node root); -static void verify_property_5_helper(node n, int black_count, int *black_count_path); - -static node new_node(void *key, void *value, color node_color, node left, node right); -static node lookup_node(rbtree t, void *key, compare_func compare); -static void rotate_left(rbtree t, node n); -static void rotate_right(rbtree t, node n); - -static void replace_node(rbtree t, node oldn, node newn); -static void insert_case1(rbtree t, node n); -static void insert_case2(rbtree t, node n); -static void insert_case3(rbtree t, node n); -static void insert_case4(rbtree t, node n); -static void insert_case5(rbtree t, node n); -static node maximum_node(node root); -static void delete_case1(rbtree t, node n); -static void delete_case2(rbtree t, node n); -static void delete_case3(rbtree t, node n); -static void delete_case4(rbtree t, node n); -static void delete_case5(rbtree t, node n); -static void delete_case6(rbtree t, node n); - -node -grandparent(node n) -{ - assert(n != NULL); - assert(n->parent != NULL); /* Not the root node */ - assert(n->parent->parent != NULL); /* Not child of root */ - return n->parent->parent; -} - -node -sibling(node n) -{ - assert(n != NULL); - assert(n->parent != NULL); /* Root node has no sibling */ - if ( n == n->parent->left ) - return n->parent->right; - else - return n->parent->left; -} - -node -uncle(node n) -{ - assert(n != NULL); - assert(n->parent != NULL); /* Root node has no uncle */ - assert(n->parent->parent != NULL); /* Children of root have no uncle */ - return sibling(n->parent); -} - -void -verify_properties(rbtree t) -{ - (void) t; -#ifdef VERIFY_RBTREE - verify_property_1(t->root); - verify_property_2(t->root); - /* Property 3 is implicit */ - verify_property_4(t->root); - verify_property_5(t->root); -#endif -} - -void -verify_property_1(node n) -{ - assert(node_color(n) == RED || node_color(n) == BLACK); - if ( n == NULL ) - return; - verify_property_1(n->left); - verify_property_1(n->right); -} - -void -verify_property_2(node root) -{ - assert(node_color(root) == BLACK); -} - -color -node_color(node n) -{ - return n == NULL ? BLACK : n->color; -} - -void -verify_property_4(node n) -{ - if ( node_color(n) == RED ) { - assert(node_color(n->left) == BLACK); - assert(node_color(n->right) == BLACK); - assert(node_color(n->parent) == BLACK); - } - if ( n == NULL ) - return; - verify_property_4(n->left); - verify_property_4(n->right); -} - -void -verify_property_5(node root) -{ - int black_count_path = -1; - verify_property_5_helper(root, 0, &black_count_path); -} - -void -verify_property_5_helper(node n, int black_count, int *path_black_count) -{ - if ( node_color(n) == BLACK ) { - black_count++; - } - if ( n == NULL ) { - if ( *path_black_count == -1 ) { - *path_black_count = black_count; - } - else { - assert(black_count == *path_black_count); - } - return; - } - verify_property_5_helper(n->left, black_count, path_black_count); - verify_property_5_helper(n->right, black_count, path_black_count); -} - -rbtree -rbtree_create() -{ - rbtree t = malloc(sizeof *t); - t->root = NULL; - verify_properties(t); - return t; -} - -node -new_node(void *key, void *value, color node_color, node left, node right) -{ - node result = malloc(sizeof *result); - result->key = key; - result->value = value; - result->color = node_color; - result->left = left; - result->right = right; - if ( left != NULL ) - left->parent = result; - if ( right != NULL ) - right->parent = result; - result->parent = NULL; - return result; -} - -node -lookup_node(rbtree t, void *key, compare_func compare) -{ - node n = t->root; - while ( n != NULL ) { - int comp_result = compare(key, n->key); - if ( comp_result == 0 ) { - return n; - } - else if ( comp_result < 0 ) { - n = n->left; - } - else { - assert(comp_result > 0); - n = n->right; - } - } - return n; -} - -void * -rbtree_lookup(rbtree t, void *key, compare_func compare) -{ - node n = lookup_node(t, key, compare); - return n == NULL ? NULL : n->value; -} - -void -rotate_left(rbtree t, node n) -{ - node r = n->right; - replace_node(t, n, r); - n->right = r->left; - if ( r->left != NULL ) { - r->left->parent = n; - } - r->left = n; - n->parent = r; -} - -void -rotate_right(rbtree t, node n) -{ - node L = n->left; - replace_node(t, n, L); - n->left = L->right; - if ( L->right != NULL ) { - L->right->parent = n; - } - L->right = n; - n->parent = L; -} - -void -replace_node(rbtree t, node oldn, node newn) -{ - if ( oldn->parent == NULL ) { - t->root = newn; - } - else { - if ( oldn == oldn->parent->left ) - oldn->parent->left = newn; - else - oldn->parent->right = newn; - } - if ( newn != NULL ) { - newn->parent = oldn->parent; - } -} - -void -rbtree_insert(rbtree t, void *key, void *value, compare_func compare) -{ - node inserted_node = new_node(key, value, RED, NULL, NULL); - if ( t->root == NULL ) { - t->root = inserted_node; - } - else { - node n = t->root; - while ( 1 ) { - int comp_result = compare(key, n->key); - if ( comp_result == 0 ) { - n->value = value; - return; - } - else if ( comp_result < 0 ) { - if ( n->left == NULL ) { - n->left = inserted_node; - break; - } - else { - n = n->left; - } - } - else { - assert(comp_result > 0); - if ( n->right == NULL ) { - n->right = inserted_node; - break; - } - else { - n = n->right; - } - } - } - inserted_node->parent = n; - } - insert_case1(t, inserted_node); - verify_properties(t); -} - -void -insert_case1(rbtree t, node n) -{ - if ( n->parent == NULL ) - n->color = BLACK; - else - insert_case2(t, n); -} - -void -insert_case2(rbtree t, node n) -{ - if ( node_color(n->parent) == BLACK ) - return; /* Tree is still valid */ - else - insert_case3(t, n); -} - -void -insert_case3(rbtree t, node n) -{ - if ( node_color(uncle(n)) == RED ) { - n->parent->color = BLACK; - uncle(n)->color = BLACK; - grandparent(n)->color = RED; - insert_case1(t, grandparent(n)); - } - else { - insert_case4(t, n); - } -} - -void -insert_case4(rbtree t, node n) -{ - if ( n == n->parent->right && n->parent == grandparent(n)->left ) { - rotate_left(t, n->parent); - n = n->left; - } - else if ( n == n->parent->left && n->parent == grandparent(n)->right ) { - rotate_right(t, n->parent); - n = n->right; - } - insert_case5(t, n); -} - -void -insert_case5(rbtree t, node n) -{ - n->parent->color = BLACK; - grandparent(n)->color = RED; - if ( n == n->parent->left && n->parent == grandparent(n)->left ) { - rotate_right(t, grandparent(n)); - } - else { - assert(n == n->parent->right && n->parent == grandparent(n)->right); - rotate_left(t, grandparent(n)); - } -} - -void -rbtree_delete(rbtree t, void *key, compare_func compare) -{ - node child; - node n = lookup_node(t, key, compare); - if ( n == NULL ) - return; /* Key not found, do nothing */ - if ( n->left != NULL && n->right != NULL ) { - /* Copy key/value from predecessor and then delete it instead */ - node pred = maximum_node(n->left); - n->key = pred->key; - n->value = pred->value; - n = pred; - } - - assert(n->left == NULL || n->right == NULL); - child = n->right == NULL ? n->left : n->right; - if ( node_color(n) == BLACK ) { - n->color = node_color(child); - delete_case1(t, n); - } - replace_node(t, n, child); - if ( n->parent == NULL && child != NULL ) // root should be black - child->color = BLACK; - free(n); - - verify_properties(t); -} - -static node -maximum_node(node n) -{ - assert(n != NULL); - while ( n->right != NULL ) { - n = n->right; - } - return n; -} - -void -delete_case1(rbtree t, node n) -{ - if ( n->parent == NULL ) - return; - else - delete_case2(t, n); -} - -void -delete_case2(rbtree t, node n) -{ - if ( node_color(sibling(n)) == RED ) { - n->parent->color = RED; - sibling(n)->color = BLACK; - if ( n == n->parent->left ) - rotate_left(t, n->parent); - else - rotate_right(t, n->parent); - } - delete_case3(t, n); -} - -void -delete_case3(rbtree t, node n) -{ - if ( node_color(n->parent) == BLACK && - node_color(sibling(n)) == BLACK && - node_color(sibling(n)->left) == BLACK && - node_color(sibling(n)->right) == BLACK ) { - sibling(n)->color = RED; - delete_case1(t, n->parent); - } - else - delete_case4(t, n); -} - -void -delete_case4(rbtree t, node n) -{ - if ( node_color(n->parent) == RED && - node_color(sibling(n)) == BLACK && - node_color(sibling(n)->left) == BLACK && - node_color(sibling(n)->right) == BLACK ) { - sibling(n)->color = RED; - n->parent->color = BLACK; - } - else - delete_case5(t, n); -} - -void -delete_case5(rbtree t, node n) -{ - if ( n == n->parent->left && - node_color(sibling(n)) == BLACK && - node_color(sibling(n)->left) == RED && - node_color(sibling(n)->right) == BLACK ) { - sibling(n)->color = RED; - sibling(n)->left->color = BLACK; - rotate_right(t, sibling(n)); - } - else if ( n == n->parent->right && - node_color(sibling(n)) == BLACK && - node_color(sibling(n)->right) == RED && - node_color(sibling(n)->left) == BLACK ) { - sibling(n)->color = RED; - sibling(n)->right->color = BLACK; - rotate_left(t, sibling(n)); - } - delete_case6(t, n); -} - -void -delete_case6(rbtree t, node n) -{ - sibling(n)->color = node_color(n->parent); - n->parent->color = BLACK; - if ( n == n->parent->left ) { - assert(node_color(sibling(n)->right) == RED); - sibling(n)->right->color = BLACK; - rotate_left(t, n->parent); - } - else { - assert(node_color(sibling(n)->left) == RED); - sibling(n)->left->color = BLACK; - rotate_right(t, n->parent); - } -} - -/* The authors of this work have released all rights to it and placed it -in the public domain under the Creative Commons CC0 1.0 waiver -(http://creativecommons.org/publicdomain/zero/1.0/). - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, -EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF -MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. -IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY -CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, -TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE -SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - -Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567 -*/ - -#include -#include -#include /* rand() */ - -static int compare_int(void *left, void *right); -static void print_tree(rbtree t); -static void print_tree_helper(rbtree_node n, int indent); - -int -compare_int(void *leftp, void *rightp) -{ - int left = (int) leftp; - int right = (int) rightp; - if ( left < right ) - return -1; - else if ( left > right ) - return 1; - else { - assert(left == right); - return 0; - } -} - -#define INDENT_STEP 4 - -void print_tree_helper(rbtree_node n, int indent); - -void -print_tree(rbtree t) -{ - print_tree_helper(t->root, 0); - puts(""); -} - -void -print_tree_helper(rbtree_node n, int indent) -{ - int i; - if ( n == NULL ) { - fputs("", stdout); - return; - } - if ( n->right != NULL ) { - print_tree_helper(n->right, indent + INDENT_STEP); - } - for ( i = 0; i < indent; i++ ) - fputs(" ", stdout); - if ( n->color == BLACK ) - printf("%d\n", (int) n->key); - else - printf("<%d>\n", (int) n->key); - if ( n->left != NULL ) { - print_tree_helper(n->left, indent + INDENT_STEP); - } -} - -int -main() -{ - int i; - rbtree t = rbtree_create(); - - for ( i = 0; i < 50; i++ ) { - long x = rand() % 10000; - long y = rand() % 10000; -#ifdef TRACE - print_tree(t); - printf("Inserting %ld -> %ld\n\n", x, y); -#endif - rbtree_insert(t, (void *) x, (void *) y, compare_int); - assert(rbtree_lookup(t, (void *) x, compare_int) == (void *) y); - } - - print_tree(t); - - for ( i = 0; i < 60000; i++ ) { - long x = rand() % 10000; -#ifdef TRACE - print_tree(t); - printf("Deleting key %ld\n\n", x); -#endif - rbtree_delete(t, (void *) x, compare_int); - } - return 0; -} diff --git a/src/red-black-tree.c b/src/red-black-tree.c new file mode 100644 index 0000000..7c2d2c1 --- /dev/null +++ b/src/red-black-tree.c @@ -0,0 +1,614 @@ +/* + Implementierung übernommen von: https://web.archive.org/web/20140328232325/http://en.literateprograms.org/Red-black_tree_(C) + */ + +#include +#include +#include + +#include "util.h" + +/* The authors of this work have released all rights to it and placed it +in the public domain under the Creative Commons CC0 1.0 waiver +(http://creativecommons.org/publicdomain/zero/1.0/). + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567 +*/ + +enum rbtree_node_color { RED, + BLACK }; + +typedef struct rbtree_node_t { + void * key; + void * value; + struct rbtree_node_t * left; + struct rbtree_node_t * right; + struct rbtree_node_t * parent; + enum rbtree_node_color color; +} * rbtree_node; + +typedef struct rbtree_t { + rbtree_node root; +} * rbtree; + +typedef int (*compare_func)(void *left, void *right); + +rbtree rbtree_create(); +void * rbtree_lookup(rbtree t, void *key, compare_func compare); +void rbtree_insert(rbtree t, void *key, void *value, compare_func compare); +void rbtree_delete(rbtree t, void *key, compare_func compare); + +#include +#include + +typedef rbtree_node node; +typedef enum rbtree_node_color color; + +static node grandparent(node n); +static node sibling(node n); +static node uncle(node n); +static void verify_properties(rbtree t); +static void verify_property_1(node root); +static void verify_property_2(node root); +static color node_color(node n); +static void verify_property_4(node root); +static void verify_property_5(node root); +static void verify_property_5_helper(node n, int black_count, int *black_count_path); + +static node new_node(void *key, void *value, color node_color, node left, node right); +static node lookup_node(rbtree t, void *key, compare_func compare); +static void rotate_left(rbtree t, node n); +static void rotate_right(rbtree t, node n); + +static void replace_node(rbtree t, node oldn, node newn); +static void insert_case1(rbtree t, node n); +static void insert_case2(rbtree t, node n); +static void insert_case3(rbtree t, node n); +static void insert_case4(rbtree t, node n); +static void insert_case5(rbtree t, node n); +static node maximum_node(node root); +static void delete_case1(rbtree t, node n); +static void delete_case2(rbtree t, node n); +static void delete_case3(rbtree t, node n); +static void delete_case4(rbtree t, node n); +static void delete_case5(rbtree t, node n); +static void delete_case6(rbtree t, node n); + +node +grandparent(node n) +{ + assert(n != NULL); + assert(n->parent != NULL); /* Not the root node */ + assert(n->parent->parent != NULL); /* Not child of root */ + return n->parent->parent; +} + +node +sibling(node n) +{ + assert(n != NULL); + assert(n->parent != NULL); /* Root node has no sibling */ + if ( n == n->parent->left ) + return n->parent->right; + else + return n->parent->left; +} + +node +uncle(node n) +{ + assert(n != NULL); + assert(n->parent != NULL); /* Root node has no uncle */ + assert(n->parent->parent != NULL); /* Children of root have no uncle */ + return sibling(n->parent); +} + +void +verify_properties(rbtree t) +{ + (void) t; +#ifdef VERIFY_RBTREE + verify_property_1(t->root); + verify_property_2(t->root); + /* Property 3 is implicit */ + verify_property_4(t->root); + verify_property_5(t->root); +#endif +} + +void +verify_property_1(node n) +{ + assert(node_color(n) == RED || node_color(n) == BLACK); + if ( n == NULL ) + return; + verify_property_1(n->left); + verify_property_1(n->right); +} + +void +verify_property_2(node root) +{ + assert(node_color(root) == BLACK); +} + +color +node_color(node n) +{ + return n == NULL ? BLACK : n->color; +} + +void +verify_property_4(node n) +{ + if ( node_color(n) == RED ) { + assert(node_color(n->left) == BLACK); + assert(node_color(n->right) == BLACK); + assert(node_color(n->parent) == BLACK); + } + if ( n == NULL ) + return; + verify_property_4(n->left); + verify_property_4(n->right); +} + +void +verify_property_5(node root) +{ + int black_count_path = -1; + verify_property_5_helper(root, 0, &black_count_path); +} + +void +verify_property_5_helper(node n, int black_count, int *path_black_count) +{ + if ( node_color(n) == BLACK ) { + black_count++; + } + if ( n == NULL ) { + if ( *path_black_count == -1 ) { + *path_black_count = black_count; + } + else { + assert(black_count == *path_black_count); + } + return; + } + verify_property_5_helper(n->left, black_count, path_black_count); + verify_property_5_helper(n->right, black_count, path_black_count); +} + +rbtree +rbtree_create() +{ + rbtree t = malloc(sizeof *t); + t->root = NULL; + verify_properties(t); + return t; +} + +node +new_node(void *key, void *value, color node_color, node left, node right) +{ + node result = malloc(sizeof *result); + result->key = key; + result->value = value; + result->color = node_color; + result->left = left; + result->right = right; + if ( left != NULL ) + left->parent = result; + if ( right != NULL ) + right->parent = result; + result->parent = NULL; + return result; +} + +node +lookup_node(rbtree t, void *key, compare_func compare) +{ + node n = t->root; + while ( n != NULL ) { + int comp_result = compare(key, n->key); + if ( comp_result == 0 ) { + return n; + } + else if ( comp_result < 0 ) { + n = n->left; + } + else { + assert(comp_result > 0); + n = n->right; + } + } + return n; +} + +void * +rbtree_lookup(rbtree t, void *key, compare_func compare) +{ + node n = lookup_node(t, key, compare); + return n == NULL ? NULL : n->value; +} + +void +rotate_left(rbtree t, node n) +{ + node r = n->right; + replace_node(t, n, r); + n->right = r->left; + if ( r->left != NULL ) { + r->left->parent = n; + } + r->left = n; + n->parent = r; +} + +void +rotate_right(rbtree t, node n) +{ + node L = n->left; + replace_node(t, n, L); + n->left = L->right; + if ( L->right != NULL ) { + L->right->parent = n; + } + L->right = n; + n->parent = L; +} + +void +replace_node(rbtree t, node oldn, node newn) +{ + if ( oldn->parent == NULL ) { + t->root = newn; + } + else { + if ( oldn == oldn->parent->left ) + oldn->parent->left = newn; + else + oldn->parent->right = newn; + } + if ( newn != NULL ) { + newn->parent = oldn->parent; + } +} + +void +rbtree_insert(rbtree t, void *key, void *value, compare_func compare) +{ + node inserted_node = new_node(key, value, RED, NULL, NULL); + if ( t->root == NULL ) { + t->root = inserted_node; + } + else { + node n = t->root; + while ( 1 ) { + int comp_result = compare(key, n->key); + if ( comp_result == 0 ) { + n->value = value; + return; + } + else if ( comp_result < 0 ) { + if ( n->left == NULL ) { + n->left = inserted_node; + break; + } + else { + n = n->left; + } + } + else { + assert(comp_result > 0); + if ( n->right == NULL ) { + n->right = inserted_node; + break; + } + else { + n = n->right; + } + } + } + inserted_node->parent = n; + } + insert_case1(t, inserted_node); + verify_properties(t); +} + +void +insert_case1(rbtree t, node n) +{ + if ( n->parent == NULL ) + n->color = BLACK; + else + insert_case2(t, n); +} + +void +insert_case2(rbtree t, node n) +{ + if ( node_color(n->parent) == BLACK ) + return; /* Tree is still valid */ + else + insert_case3(t, n); +} + +void +insert_case3(rbtree t, node n) +{ + if ( node_color(uncle(n)) == RED ) { + n->parent->color = BLACK; + uncle(n)->color = BLACK; + grandparent(n)->color = RED; + insert_case1(t, grandparent(n)); + } + else { + insert_case4(t, n); + } +} + +void +insert_case4(rbtree t, node n) +{ + if ( n == n->parent->right && n->parent == grandparent(n)->left ) { + rotate_left(t, n->parent); + n = n->left; + } + else if ( n == n->parent->left && n->parent == grandparent(n)->right ) { + rotate_right(t, n->parent); + n = n->right; + } + insert_case5(t, n); +} + +void +insert_case5(rbtree t, node n) +{ + n->parent->color = BLACK; + grandparent(n)->color = RED; + if ( n == n->parent->left && n->parent == grandparent(n)->left ) { + rotate_right(t, grandparent(n)); + } + else { + assert(n == n->parent->right && n->parent == grandparent(n)->right); + rotate_left(t, grandparent(n)); + } +} + +void +rbtree_delete(rbtree t, void *key, compare_func compare) +{ + node child; + node n = lookup_node(t, key, compare); + if ( n == NULL ) + return; /* Key not found, do nothing */ + if ( n->left != NULL && n->right != NULL ) { + /* Copy key/value from predecessor and then delete it instead */ + node pred = maximum_node(n->left); + n->key = pred->key; + n->value = pred->value; + n = pred; + } + + assert(n->left == NULL || n->right == NULL); + child = n->right == NULL ? n->left : n->right; + if ( node_color(n) == BLACK ) { + n->color = node_color(child); + delete_case1(t, n); + } + replace_node(t, n, child); + if ( n->parent == NULL && child != NULL ) // root should be black + child->color = BLACK; + free(n); + + verify_properties(t); +} + +static node +maximum_node(node n) +{ + assert(n != NULL); + while ( n->right != NULL ) { + n = n->right; + } + return n; +} + +void +delete_case1(rbtree t, node n) +{ + if ( n->parent == NULL ) + return; + else + delete_case2(t, n); +} + +void +delete_case2(rbtree t, node n) +{ + if ( node_color(sibling(n)) == RED ) { + n->parent->color = RED; + sibling(n)->color = BLACK; + if ( n == n->parent->left ) + rotate_left(t, n->parent); + else + rotate_right(t, n->parent); + } + delete_case3(t, n); +} + +void +delete_case3(rbtree t, node n) +{ + if ( node_color(n->parent) == BLACK && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->left) == BLACK && + node_color(sibling(n)->right) == BLACK ) { + sibling(n)->color = RED; + delete_case1(t, n->parent); + } + else + delete_case4(t, n); +} + +void +delete_case4(rbtree t, node n) +{ + if ( node_color(n->parent) == RED && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->left) == BLACK && + node_color(sibling(n)->right) == BLACK ) { + sibling(n)->color = RED; + n->parent->color = BLACK; + } + else + delete_case5(t, n); +} + +void +delete_case5(rbtree t, node n) +{ + if ( n == n->parent->left && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->left) == RED && + node_color(sibling(n)->right) == BLACK ) { + sibling(n)->color = RED; + sibling(n)->left->color = BLACK; + rotate_right(t, sibling(n)); + } + else if ( n == n->parent->right && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->right) == RED && + node_color(sibling(n)->left) == BLACK ) { + sibling(n)->color = RED; + sibling(n)->right->color = BLACK; + rotate_left(t, sibling(n)); + } + delete_case6(t, n); +} + +void +delete_case6(rbtree t, node n) +{ + sibling(n)->color = node_color(n->parent); + n->parent->color = BLACK; + if ( n == n->parent->left ) { + assert(node_color(sibling(n)->right) == RED); + sibling(n)->right->color = BLACK; + rotate_left(t, n->parent); + } + else { + assert(node_color(sibling(n)->left) == RED); + sibling(n)->left->color = BLACK; + rotate_right(t, n->parent); + } +} + +/* The authors of this work have released all rights to it and placed it +in the public domain under the Creative Commons CC0 1.0 waiver +(http://creativecommons.org/publicdomain/zero/1.0/). + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567 +*/ + +#include +#include +#include /* rand() */ + +static int compare_int(void *left, void *right); +static void print_tree(rbtree t); +static void print_tree_helper(rbtree_node n, int indent); + +int +compare_int(void *leftp, void *rightp) +{ + int left = (int) leftp; + int right = (int) rightp; + if ( left < right ) + return -1; + else if ( left > right ) + return 1; + else { + assert(left == right); + return 0; + } +} + +#define INDENT_STEP 4 + +void print_tree_helper(rbtree_node n, int indent); + +void +print_tree(rbtree t) +{ + print_tree_helper(t->root, 0); + puts(""); +} + +void +print_tree_helper(rbtree_node n, int indent) +{ + int i; + if ( n == NULL ) { + fputs("", stdout); + return; + } + if ( n->right != NULL ) { + print_tree_helper(n->right, indent + INDENT_STEP); + } + for ( i = 0; i < indent; i++ ) + fputs(" ", stdout); + if ( n->color == BLACK ) + printf("%d\n", (int) n->key); + else + printf("<%d>\n", (int) n->key); + if ( n->left != NULL ) { + print_tree_helper(n->left, indent + INDENT_STEP); + } +} + +int +main() +{ + int i; + rbtree t = rbtree_create(); + + for ( i = 0; i < 50; i++ ) { + long x = rand() % 10000; + long y = rand() % 10000; +#ifdef TRACE + print_tree(t); + printf("Inserting %ld -> %ld\n\n", x, y); +#endif + rbtree_insert(t, (void *) x, (void *) y, compare_int); + assert(rbtree_lookup(t, (void *) x, compare_int) == (void *) y); + } + + print_tree(t); + + for ( i = 0; i < 60000; i++ ) { + long x = rand() % 10000; +#ifdef TRACE + print_tree(t); + printf("Deleting key %ld\n\n", x); +#endif + rbtree_delete(t, (void *) x, compare_int); + } + return 0; +} diff --git a/src/ring-buffer.c b/src/ring-buffer.c new file mode 100644 index 0000000..1294b3b --- /dev/null +++ b/src/ring-buffer.c @@ -0,0 +1,156 @@ +#include +#include +#include +#include + +#include "util.h" + +/* --8<-- ring_type */ +typedef int T; + +struct ring_buffer { + size_t head, tail; + T array[8]; /* fit for your needs... */ +}; +/* -->8-- */ + +/* --8<-- ring_init */ +void +ring_init(struct ring_buffer *rb) +{ + rb->head = rb->tail = 0; +} +/* -->8-- */ + +/* --8<-- ring_push_front */ +bool +ring_push_front(struct ring_buffer *rb, T data) +{ + const size_t prev = (rb->tail + NELEM(rb->array) - 1) % NELEM(rb->array); + + if ( prev == rb->head ) { + return false; + } + + rb->array[prev] = data; + rb->tail = prev; + + return true; +} +/* -->8-- */ + +/* --8<-- ring_push_back */ +bool +ring_push_back(struct ring_buffer *rb, T data) +{ + const size_t next = (rb->head + 1) % NELEM(rb->array); + + if ( next == rb->tail ) { + return false; + } + + rb->array[rb->head] = data; + rb->head = next; + + return true; +} +/* -->8-- */ + +/* --8<-- ring_pop_front */ +bool +ring_pop_front(struct ring_buffer *rb, T *data) +{ + if ( rb->head == rb->tail ) { + return false; + } + + const size_t next = (rb->tail + 1) % NELEM(rb->array); + + *data = rb->array[rb->tail]; + rb->tail = next; + + return true; +} +/* -->8-- */ + +/* --8<-- ring_pop_back */ +bool +ring_pop_back(struct ring_buffer *rb, T *data) +{ + if ( rb->head == rb->tail ) { + return false; + } + + const size_t prev = (rb->head + NELEM(rb->array) - 1) % NELEM(rb->array); + + *data = rb->array[prev]; + rb->head = prev; + + return true; +} +/* -->8-- */ + +/* --8<-- ring_put */ +bool +ring_put(struct ring_buffer *rb, T data) +{ + return ring_push_back(rb, data); +} +/* -->8-- */ + +/* --8<-- ring_get */ +bool +ring_get(struct ring_buffer *rb, T *data) +{ + return ring_pop_front(rb, data); +} +/* -->8-- */ + +void +debug_print(const char *msg, struct ring_buffer *rb) +{ + printf("%s: head: %zu, tail: %zu\n", msg, rb->head, rb->tail); +} + +int +main(void) +{ +#if 0 + struct ring_buffer rb; + ring_init(&rb); +#else + struct ring_buffer rb = { .head = 0, .tail = 0 }; +#endif + + assert(ring_push_back(&rb, 1) == true); // 1 + assert(ring_push_back(&rb, 2) == true); // 1, 2 + assert(ring_push_back(&rb, 3) == true); // 1, 2, 3 + assert(ring_push_back(&rb, 4) == true); // 1, 2, 3, 4 + + debug_print("Stand", &rb); + + assert(ring_push_front(&rb, 0) == true); // 0, 1, 2, 3, 4 + assert(ring_push_front(&rb, -1) == true); // -1, 0, 1, 2, 3, 4 + + debug_print("Stand", &rb); + + T temp; + assert(ring_pop_back(&rb, &temp) == true); // -1, 0, 1, 2, 3 + assert(ring_pop_front(&rb, &temp) == true); // 0, 1, 2, 3 + + debug_print("Stand", &rb); + + assert(ring_push_back(&rb, 4) == true); // 0, 1, 2, 3, 4 + assert(ring_push_back(&rb, 5) == true); // 0, 1, 2, 3, 4, 5 + assert(ring_push_back(&rb, 6) == true); // 0, 1, 2, 3, 4, 5, 6 + assert(ring_push_back(&rb, 7) == false); // 0, 1, 2, 3, 4, 5, 6 + assert(ring_push_front(&rb, 7) == false); // 0, 1, 2, 3, 4, 5, 6 + + while ( ring_pop_back(&rb, &temp) ) { + printf("temp: %d\n", temp); + } + + debug_print("Stand", &rb); + + return EXIT_SUCCESS; +} diff --git a/src/ringbuff.c b/src/ringbuff.c deleted file mode 100644 index 1294b3b..0000000 --- a/src/ringbuff.c +++ /dev/null @@ -1,156 +0,0 @@ -#include -#include -#include -#include - -#include "util.h" - -/* --8<-- ring_type */ -typedef int T; - -struct ring_buffer { - size_t head, tail; - T array[8]; /* fit for your needs... */ -}; -/* -->8-- */ - -/* --8<-- ring_init */ -void -ring_init(struct ring_buffer *rb) -{ - rb->head = rb->tail = 0; -} -/* -->8-- */ - -/* --8<-- ring_push_front */ -bool -ring_push_front(struct ring_buffer *rb, T data) -{ - const size_t prev = (rb->tail + NELEM(rb->array) - 1) % NELEM(rb->array); - - if ( prev == rb->head ) { - return false; - } - - rb->array[prev] = data; - rb->tail = prev; - - return true; -} -/* -->8-- */ - -/* --8<-- ring_push_back */ -bool -ring_push_back(struct ring_buffer *rb, T data) -{ - const size_t next = (rb->head + 1) % NELEM(rb->array); - - if ( next == rb->tail ) { - return false; - } - - rb->array[rb->head] = data; - rb->head = next; - - return true; -} -/* -->8-- */ - -/* --8<-- ring_pop_front */ -bool -ring_pop_front(struct ring_buffer *rb, T *data) -{ - if ( rb->head == rb->tail ) { - return false; - } - - const size_t next = (rb->tail + 1) % NELEM(rb->array); - - *data = rb->array[rb->tail]; - rb->tail = next; - - return true; -} -/* -->8-- */ - -/* --8<-- ring_pop_back */ -bool -ring_pop_back(struct ring_buffer *rb, T *data) -{ - if ( rb->head == rb->tail ) { - return false; - } - - const size_t prev = (rb->head + NELEM(rb->array) - 1) % NELEM(rb->array); - - *data = rb->array[prev]; - rb->head = prev; - - return true; -} -/* -->8-- */ - -/* --8<-- ring_put */ -bool -ring_put(struct ring_buffer *rb, T data) -{ - return ring_push_back(rb, data); -} -/* -->8-- */ - -/* --8<-- ring_get */ -bool -ring_get(struct ring_buffer *rb, T *data) -{ - return ring_pop_front(rb, data); -} -/* -->8-- */ - -void -debug_print(const char *msg, struct ring_buffer *rb) -{ - printf("%s: head: %zu, tail: %zu\n", msg, rb->head, rb->tail); -} - -int -main(void) -{ -#if 0 - struct ring_buffer rb; - ring_init(&rb); -#else - struct ring_buffer rb = { .head = 0, .tail = 0 }; -#endif - - assert(ring_push_back(&rb, 1) == true); // 1 - assert(ring_push_back(&rb, 2) == true); // 1, 2 - assert(ring_push_back(&rb, 3) == true); // 1, 2, 3 - assert(ring_push_back(&rb, 4) == true); // 1, 2, 3, 4 - - debug_print("Stand", &rb); - - assert(ring_push_front(&rb, 0) == true); // 0, 1, 2, 3, 4 - assert(ring_push_front(&rb, -1) == true); // -1, 0, 1, 2, 3, 4 - - debug_print("Stand", &rb); - - T temp; - assert(ring_pop_back(&rb, &temp) == true); // -1, 0, 1, 2, 3 - assert(ring_pop_front(&rb, &temp) == true); // 0, 1, 2, 3 - - debug_print("Stand", &rb); - - assert(ring_push_back(&rb, 4) == true); // 0, 1, 2, 3, 4 - assert(ring_push_back(&rb, 5) == true); // 0, 1, 2, 3, 4, 5 - assert(ring_push_back(&rb, 6) == true); // 0, 1, 2, 3, 4, 5, 6 - assert(ring_push_back(&rb, 7) == false); // 0, 1, 2, 3, 4, 5, 6 - assert(ring_push_front(&rb, 7) == false); // 0, 1, 2, 3, 4, 5, 6 - - while ( ring_pop_back(&rb, &temp) ) { - printf("temp: %d\n", temp); - } - - debug_print("Stand", &rb); - - return EXIT_SUCCESS; -} diff --git a/src/single-linked-list.c b/src/single-linked-list.c new file mode 100644 index 0000000..d18dae4 --- /dev/null +++ b/src/single-linked-list.c @@ -0,0 +1,264 @@ +/* simple Implementation of single linked lists */ +/* written and placed in the public domain by Thomas Schmucker */ + +/* Standard C */ +#include +#include +#include + +/* Project */ +#include "util.h" + +/* --8<-- list_type */ +typedef int T; + +struct list_item { + struct list_item *next; + T data; +}; +/* -->8-- */ + +/* --8<-- list_add */ +struct list_item * +list_add(struct list_item *next, T data) +{ + struct list_item *new_item; + + new_item = malloc(sizeof *new_item); + if ( new_item ) { + new_item->data = data; + new_item->next = next; + } + else { + ERROR("out of memory"); + } + + return new_item; +} +/* -->8-- */ + +/* --8<-- list_insert_next */ +void +list_insert_next(struct list_item *list, T data) +{ + struct list_item *new_item; + + new_item = list_add(list->next, data); + if ( new_item ) { + list->next = new_item; + } + else { + ERROR("out of memory"); + } +} +/* -->8-- */ + +/* --8<-- list_delete */ +struct list_item * +list_delete(struct list_item *list, T data) +{ + struct list_item *prev = NULL; + + for ( struct list_item *p = list; p; p = p->next ) { + if ( p->data == data ) { + if ( prev == NULL ) { /* first element in list? */ + list = p->next; + } + else { + prev->next = p->next; + } + + free(p); + + return list; + } + prev = p; + } +#ifdef LIST_REPORT_ERROR + ERROR("data not found"); +#endif + return list; +} +/* -->8-- */ + +/* --8<-- list_delete_next */ +void +list_delete_next(struct list_item *list) +{ + if ( list->next ) { + struct list_item *temp = list->next; + + list->next = list->next->next; + + free(temp); + } +} +/* -->8-- */ + +/* --8<-- list_length */ +size_t +list_length(struct list_item *list) +{ + size_t len = 0; + + for ( ; list; list = list->next ) { + ++len; + } + + return len; +} +/* -->8-- */ + +/* --8<-- list_copy */ +struct list_item * +list_copy(struct list_item *list) +{ + struct list_item *head = NULL, **p = &head; + + for ( ; list; list = list->next ) { + *p = malloc(sizeof **p); + if ( *p ) { + (*p)->data = list->data; // copy elements + p = &(*p)->next; + } + else { + ERROR("out of memory"); + } + } + *p = NULL; + return head; +} +/* -->8-- */ + +/* --8<-- list_reverse */ +struct list_item * +list_reverse(struct list_item *list) +{ + struct list_item *head = NULL, *next; + + for ( ; list; list = next ) { + next = list->next; + list->next = head; + head = list; + } + return head; +} +/* -->8-- */ + +/* --8<-- list_apply */ +void +list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl) +{ + for ( ; list; list = list->next ) { + visit(list->data, cl); + } +} +/* -->8-- */ + +/* --8<-- list_merge */ +struct list_item * +list_merge(struct list_item *a, struct list_item *b) +{ + struct list_item dummy = { .next = NULL }; + struct list_item *head = &dummy, *c = head; + + while ( a && b ) + if ( a->data < b->data ) { + c->next = a, c = a, a = a->next; + } + else { + c->next = b, c = b, b = b->next; + } + + c->next = a ? a : b; + + return head->next; +} +/* -->8-- */ + +/* --8<-- list_sort */ +struct list_item * +list_sort(struct list_item *c) +{ + if ( c == NULL || c->next == NULL ) + return c; + + struct list_item *a = c, + *b = c->next; + + while ( b && b->next ) { + c = c->next, b = b->next->next; + } + + b = c->next, c->next = NULL; + + return list_merge(list_sort(a), list_sort(b)); +} +/* -->8-- */ + +/* --8<-- list_free */ +void +list_free(struct list_item *list) +{ + struct list_item *next; + + for ( ; list; list = next ) { + next = list->next; + free(list); + } +} +/* -->8-- */ + +/* --8<-- list_apply_sample */ +static void +print_data(T data, void *cl) +{ + fprintf(cl, "%d\n", data); +} +/* -->8-- */ + +int +main() +{ + clock_t start; + + /* + struct list_item *mylist = NULL; + + mylist = list_add(mylist, 42); + mylist = list_add(mylist, 43); + mylist = list_add(mylist, 44); + + mylist = list_delete(mylist, 45); + + list_apply(mylist, print_data, stdout); + + struct list_item *mylist2 = list_reverse(list_copy(mylist)); + + list_free(mylist); + list_apply(mylist2, print_data); + list_free(mylist2); + */ + + srand(time(NULL)); + + static const int COUNT = 10000000; + + struct list_item *x = NULL; + for ( int i = 0; i != COUNT; ++i ) { + int r = rand(); + x = list_add(x, r); + } + + puts("start"); + start = clock(); + x = list_sort(x); + printf("Fertig: %.3lf sec\n", (double) (clock() - start) / CLOCKS_PER_SEC); + + //list_apply(x, print_data); + printf("Len: %zu\n", list_length(x)); + + list_free(x); + + return EXIT_SUCCESS; +} diff --git a/src/stack-array.c b/src/stack-array.c new file mode 100644 index 0000000..5f4ba41 --- /dev/null +++ b/src/stack-array.c @@ -0,0 +1,115 @@ +#include +#include +#include + +#include "util.h" + +/* --8<-- stack2_type */ +typedef int T; + +struct stack { + T * array; + size_t sz, p; +}; +/* -->8-- */ + +/* --8<-- stack2_init */ +void +stack_init(struct stack *stack) +{ + stack->array = NULL; + stack->sz = 0; + stack->p = 0; +} +/* -->8-- */ + +/* --8<-- stack2_push */ +bool +stack_push(struct stack *stack, T data) +{ + if ( stack->array == NULL ) { + if ( (stack->array = malloc(10 * sizeof *stack->array)) != NULL ) { + stack->sz = 10; + stack->p = 0; + } + else { + ERROR("out of memory"); + return false; + } + } + + if ( stack->p == stack->sz ) { + size_t new_sz; + T * new_array; + + if ( (new_array = realloc(stack->array, (new_sz = (stack->sz * 3 / 2)) * sizeof *stack->array)) != NULL ) { + stack->array = new_array; + stack->sz = new_sz; + } + else { + ERROR("out of memory"); + return false; + } + } + + stack->array[stack->p++] = data; + return true; +} +/* -->8-- */ + +/* --8<-- stack2_pop */ +bool +stack_pop(struct stack *stack, T *data) +{ + if ( stack->p != 0 ) { + --stack->p; + + if ( data ) { + *data = stack->array[stack->p]; + } + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- stack2_empty */ +bool +stack_empty(struct stack *stack) +{ + return stack->p == 0; +} +/* -->8-- */ + +/* --8<-- stack2_free */ +void +stack_free(struct stack *stack) +{ + free(stack->array); +} +/* -->8-- */ + +int +main() +{ + struct stack stack[1]; + + stack_init(stack); + + for ( int i = 0; i != 20; ++i ) + stack_push(stack, i); + + while ( !stack_empty(stack) ) { + int i; + + if ( stack_pop(stack, &i) ) + printf("%d\n", i); + else + ERROR("this shouldn't happen!"); + } + + stack_free(stack); + + return EXIT_SUCCESS; +} diff --git a/src/stack-linked-list.c b/src/stack-linked-list.c new file mode 100644 index 0000000..48b9eba --- /dev/null +++ b/src/stack-linked-list.c @@ -0,0 +1,110 @@ +/* Standard C */ +#include +#include +#include + +/* Project */ +#include "util.h" + +/* --8<-- stack_type */ +typedef int T; + +struct stack_item { + struct stack_item *next; + T data; +}; + +struct stack { + struct stack_item *head; +}; +/* -->8-- */ + +/* --8<-- stack_init */ +void +stack_init(struct stack *stack) +{ + stack->head = NULL; +} +/* -->8-- */ + +/* --8<-- stack_push */ +void +stack_push(struct stack *stack, T data) +{ + struct stack_item *new_item; + + if ( (new_item = malloc(sizeof *new_item)) != NULL ) { + new_item->data = data; + new_item->next = stack->head; + stack->head = new_item; + } + else + ERROR("out of memory"); +} +/* -->8-- */ + +/* --8<-- stack_pop */ +bool +stack_pop(struct stack *stack, T *data) +{ + if ( stack->head ) { + struct stack_item *next = stack->head->next; + + if ( data ) { + *data = stack->head->data; + } + free(stack->head); + stack->head = next; + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- stack_empty */ +bool +stack_empty(struct stack *stack) +{ + return stack->head == NULL; +} +/* -->8-- */ + +/* --8<-- stack_free */ +void +stack_free(struct stack *stack) +{ + struct stack_item *item, *next; + + for ( item = stack->head; item; item = next ) { + next = item->next; + free(item); + } +} +/* -->8-- */ + +int +main() +{ + struct stack stack[1]; + + stack_init(stack); + + for ( int i = 0; i != 10; ++i ) + stack_push(stack, i); + + /* + while ( !stack_empty(stack) ) { + int i; + if ( stack_pop(stack, &i) ) + printf("%d\n", i); + else + ERROR("this shouldn't happen!"); + } + */ + + stack_free(stack); + + return EXIT_SUCCESS; +} diff --git a/src/stack.c b/src/stack.c deleted file mode 100644 index 48b9eba..0000000 --- a/src/stack.c +++ /dev/null @@ -1,110 +0,0 @@ -/* Standard C */ -#include -#include -#include - -/* Project */ -#include "util.h" - -/* --8<-- stack_type */ -typedef int T; - -struct stack_item { - struct stack_item *next; - T data; -}; - -struct stack { - struct stack_item *head; -}; -/* -->8-- */ - -/* --8<-- stack_init */ -void -stack_init(struct stack *stack) -{ - stack->head = NULL; -} -/* -->8-- */ - -/* --8<-- stack_push */ -void -stack_push(struct stack *stack, T data) -{ - struct stack_item *new_item; - - if ( (new_item = malloc(sizeof *new_item)) != NULL ) { - new_item->data = data; - new_item->next = stack->head; - stack->head = new_item; - } - else - ERROR("out of memory"); -} -/* -->8-- */ - -/* --8<-- stack_pop */ -bool -stack_pop(struct stack *stack, T *data) -{ - if ( stack->head ) { - struct stack_item *next = stack->head->next; - - if ( data ) { - *data = stack->head->data; - } - free(stack->head); - stack->head = next; - - return true; - } - else - return false; -} -/* -->8-- */ - -/* --8<-- stack_empty */ -bool -stack_empty(struct stack *stack) -{ - return stack->head == NULL; -} -/* -->8-- */ - -/* --8<-- stack_free */ -void -stack_free(struct stack *stack) -{ - struct stack_item *item, *next; - - for ( item = stack->head; item; item = next ) { - next = item->next; - free(item); - } -} -/* -->8-- */ - -int -main() -{ - struct stack stack[1]; - - stack_init(stack); - - for ( int i = 0; i != 10; ++i ) - stack_push(stack, i); - - /* - while ( !stack_empty(stack) ) { - int i; - if ( stack_pop(stack, &i) ) - printf("%d\n", i); - else - ERROR("this shouldn't happen!"); - } - */ - - stack_free(stack); - - return EXIT_SUCCESS; -} diff --git a/src/stack2.c b/src/stack2.c deleted file mode 100644 index 5f4ba41..0000000 --- a/src/stack2.c +++ /dev/null @@ -1,115 +0,0 @@ -#include -#include -#include - -#include "util.h" - -/* --8<-- stack2_type */ -typedef int T; - -struct stack { - T * array; - size_t sz, p; -}; -/* -->8-- */ - -/* --8<-- stack2_init */ -void -stack_init(struct stack *stack) -{ - stack->array = NULL; - stack->sz = 0; - stack->p = 0; -} -/* -->8-- */ - -/* --8<-- stack2_push */ -bool -stack_push(struct stack *stack, T data) -{ - if ( stack->array == NULL ) { - if ( (stack->array = malloc(10 * sizeof *stack->array)) != NULL ) { - stack->sz = 10; - stack->p = 0; - } - else { - ERROR("out of memory"); - return false; - } - } - - if ( stack->p == stack->sz ) { - size_t new_sz; - T * new_array; - - if ( (new_array = realloc(stack->array, (new_sz = (stack->sz * 3 / 2)) * sizeof *stack->array)) != NULL ) { - stack->array = new_array; - stack->sz = new_sz; - } - else { - ERROR("out of memory"); - return false; - } - } - - stack->array[stack->p++] = data; - return true; -} -/* -->8-- */ - -/* --8<-- stack2_pop */ -bool -stack_pop(struct stack *stack, T *data) -{ - if ( stack->p != 0 ) { - --stack->p; - - if ( data ) { - *data = stack->array[stack->p]; - } - return true; - } - else - return false; -} -/* -->8-- */ - -/* --8<-- stack2_empty */ -bool -stack_empty(struct stack *stack) -{ - return stack->p == 0; -} -/* -->8-- */ - -/* --8<-- stack2_free */ -void -stack_free(struct stack *stack) -{ - free(stack->array); -} -/* -->8-- */ - -int -main() -{ - struct stack stack[1]; - - stack_init(stack); - - for ( int i = 0; i != 20; ++i ) - stack_push(stack, i); - - while ( !stack_empty(stack) ) { - int i; - - if ( stack_pop(stack, &i) ) - printf("%d\n", i); - else - ERROR("this shouldn't happen!"); - } - - stack_free(stack); - - return EXIT_SUCCESS; -} diff --git a/src/tree.c b/src/tree.c deleted file mode 100644 index 93690e2..0000000 --- a/src/tree.c +++ /dev/null @@ -1,806 +0,0 @@ -// Binary Search Tree -#include -#include -#include -#include -#include - -#include "util.h" - -/* --8<-- tree_type */ -typedef int T; - -struct tree_node { - struct tree_node *left, *right; - T key; - int count; /* collision counter */ - /* ggf. weitere Felder... */ -}; -/* -->8-- */ - -/* --8<-- tree_isBst */ -static bool -tree_isBstUntil(struct tree_node *tree, T min, T max) -{ - if ( tree == NULL ) - return true; - - if ( tree->key < min || tree->key > max ) - return false; - - return tree_isBstUntil(tree->left, min, tree->key - 1) && - tree_isBstUntil(tree->right, tree->key + 1, max); -} - -bool -tree_isBst(struct tree_node *tree) -{ - return tree_isBstUntil(tree, INT_MIN, INT_MAX); -} -/* -->8-- */ - -/* --8<-- tree_insert */ -struct tree_node * -tree_insert(struct tree_node *tree, T key) -{ - if ( tree == NULL ) { - tree = malloc(sizeof *tree); - if ( tree ) { - tree->key = key; - tree->count = 1; - tree->left = NULL; - tree->right = NULL; - } - else - ERROR("out of memory"); - } - else if ( key < tree->key ) - tree->left = tree_insert(tree->left, key); - else if ( key > tree->key ) - tree->right = tree_insert(tree->right, key); - else /* key == tree->key */ - tree->count++; /* handle collision */ - - return tree; -} -/* -->8-- */ - -/* --8<-- tree_insert_it */ -struct tree_node * -tree_insert_it(struct tree_node *tree, T key) -{ - struct tree_node *parent = NULL; - - for ( struct tree_node *curr = tree; curr; ) { - parent = curr; - - if ( key < curr->key ) { - curr = curr->left; - } - else if ( key > curr->key ) { - curr = curr->right; - } - else { /* key == current->key */ - curr->count++; - return tree; - } - } - - struct tree_node *new_node; - - new_node = malloc(sizeof *new_node); - if ( new_node ) { - new_node->key = key; - new_node->count = 1; - new_node->left = NULL; - new_node->right = NULL; - - if ( parent == NULL ) { - tree = new_node; - } - else if ( key < parent->key ) { - parent->left = new_node; - } - else { - parent->right = new_node; - } - } - else { - ERROR("out of memory"); - } - - return tree; -} -/* -->8-- */ - -/* --8<-- tree_detach_min */ -static struct tree_node * -tree_detach_min(struct tree_node **ptree) -{ - struct tree_node *tree = *ptree; - - if ( tree == NULL ) - return NULL; - else if ( tree->left ) - return tree_detach_min(&tree->left); - else { - *ptree = tree->right; - return tree; - } -} -/* -->8-- */ - -/* --8<-- tree_remove */ -struct tree_node * -tree_remove(struct tree_node *tree, T key) -{ - if ( tree == NULL ) - return NULL; - - if ( key < tree->key ) - tree->left = tree_remove(tree->left, key); - else if ( key > tree->key ) - tree->right = tree_remove(tree->right, key); - else { /* key == tree->key */ - if ( --tree->count == 0 ) { /* Handle Collision */ - struct tree_node *temp = tree; - - if ( tree->left == NULL ) { - tree = tree->right; - } - else if ( tree->right == NULL ) { - tree = tree->left; - } - else { - struct tree_node *min = tree_detach_min(&tree->right); - - min->left = tree->left; - min->right = tree->right; - - tree = min; - } - - free(temp); - } - } - return tree; -} -/* -->8-- */ - -/* --8<-- tree_clear */ -void -tree_clear(struct tree_node *tree) -{ - if ( tree ) { - tree_clear(tree->left); - tree_clear(tree->right); - free(tree); - } -} -/* -->8-- */ - -/* --8<-- tree_lookup */ -struct tree_node * -tree_lookup(struct tree_node *tree, T key) -{ - while ( tree ) - if ( key < tree->key ) - tree = tree->left; - else if ( key > tree->key ) - tree = tree->right; - else /* key == tree->key */ - break; - - return tree; -} -/* -->8-- */ - -/* --8<-- tree_minimum */ -struct tree_node * -tree_minimum(struct tree_node *tree) -{ - if ( tree ) - while ( tree->left ) - tree = tree->left; - - return tree; -} -/* -->8-- */ - -/* --8<-- tree_maximum */ -struct tree_node * -tree_maximum(struct tree_node *tree) -{ - if ( tree ) - while ( tree->right ) - tree = tree->right; - - return tree; -} -/* -->8-- */ - -/* --8<-- tree_height */ -size_t -tree_height(struct tree_node *tree) -{ - if ( tree ) { - size_t hl = tree_height(tree->left); - size_t hr = tree_height(tree->right); - - return ((hl > hr) ? hl : hr) + 1; - } - - return 0; -} -/* -->8-- */ - -/* --8<-- tree_count */ -size_t -tree_count(struct tree_node *tree) -{ - if ( tree ) - return tree_count(tree->left) + tree_count(tree->right) + 1; - - return 0; -} -/* -->8-- */ - -/* --8<-- tree_copy */ -struct tree_node * -tree_copy(struct tree_node *tree) -{ - if ( tree ) { - struct tree_node *new_node; - - new_node = malloc(sizeof *new_node); - if ( new_node ) { - new_node->key = tree->key; - new_node->count = tree->count; - new_node->left = tree_copy(tree->left); - new_node->right = tree_copy(tree->right); - } - else { - ERROR("out of memory"); - } - - return new_node; - } - return NULL; -} -/* -->8-- */ - -/* --8<-- tree_isleaf */ -bool -tree_isleaf(struct tree_node *tree) -{ - return tree->left == NULL && tree->right == NULL; -} -/* -->8-- */ - -/* --8<-- tree_apply_preorder */ -void -tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) -{ - if ( tree ) { - visit(tree->key, cl); - tree_apply_preorder(tree->left, visit, cl); - tree_apply_preorder(tree->right, visit, cl); - } -} -/* -->8-- */ - -/* --8<-- tree_apply_inorder */ -void -tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) -{ - if ( tree ) { - tree_apply_inorder(tree->left, visit, cl); - visit(tree->key, cl); - tree_apply_inorder(tree->right, visit, cl); - } -} -/* -->8-- */ - -/* --8<-- tree_apply_postorder */ -void -tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) -{ - if ( tree ) { - tree_apply_postorder(tree->left, visit, cl); - tree_apply_postorder(tree->right, visit, cl); - visit(tree->key, cl); - } -} -/* -->8-- */ - -/* ===== */ - -/* --8<-- tree_stack_type */ -struct stack_item { - struct stack_item *next; - struct tree_node * data; -}; - -struct stack { - struct stack_item *head; -}; -/* -->8-- */ - -/* --8<-- tree_stack_init */ -static void -stack_init(struct stack *stack) -{ - stack->head = NULL; -} -/* -->8-- */ - -/* --8<-- tree_stack_push */ -static void -stack_push(struct stack *stack, struct tree_node *data) -{ - struct stack_item *new_item; - - if ( (new_item = malloc(sizeof *new_item)) ) { - new_item->data = data; - new_item->next = stack->head; - stack->head = new_item; - } - else - ERROR("out of memory"); -} -/* -->8-- */ - -/* --8<-- tree_stack_pop */ -static bool -stack_pop(struct stack *stack, struct tree_node **data) -{ - if ( stack->head ) { - struct stack_item *next; - - next = stack->head->next; - *data = stack->head->data; - - free(stack->head); - stack->head = next; - - return true; - } - else - return false; -} -/* -->8-- */ - -/* --8<-- tree_stack_peek */ -static struct tree_node * -stack_peek(struct stack *stack) -{ - return (stack->head) ? stack->head->data : NULL; -} -/* -->8-- */ - -/* --8<-- tree_stack_empty */ -static bool -stack_empty(struct stack *stack) -{ - return stack->head == NULL; -} -/* -->8-- */ - -/* --8<-- tree_stack_free */ -void -stack_free(struct stack *stack) -{ - struct stack_item *item, *next; - - for ( item = stack->head; item; item = next ) { - next = item->next; - free(item); - } -} -/* -->8-- */ - -/* ===== */ - -/* --8<-- tree_queue_type */ -struct queue_item { - struct queue_item *next; - struct tree_node * data; -}; - -struct queue { - struct queue_item *head, *tail; -}; -/* -->8-- */ - -/* --8<-- tree_queue_init */ -void -queue_init(struct queue *queue) -{ - queue->head = NULL; -} -/* -->8-- */ - -/* --8<-- tree_queue_put */ -void -queue_put(struct queue *queue, struct tree_node *data) -{ - struct queue_item *new_item; - - if ( (new_item = malloc(sizeof *new_item)) ) { - struct queue_item *tail; - - tail = queue->tail; - new_item->data = data; - new_item->next = NULL; - queue->tail = new_item; - - if ( queue->head == NULL ) - queue->head = queue->tail; - else - tail->next = queue->tail; - } - else - ERROR("out of memory"); -} -/* -->8-- */ - -/* --8<-- tree_queue_get */ -bool -queue_get(struct queue *queue, struct tree_node **data) -{ - if ( queue->head ) { - struct queue_item *next; - - next = queue->head->next; - *data = queue->head->data; - - free(queue->head); - queue->head = next; - - return true; - } - else - return false; -} -/* -->8-- */ - -/* --8<-- tree_queue_empty */ -bool -queue_empty(struct queue *queue) -{ - return queue->head == NULL; -} -/* -->8-- */ - -/* --8<-- tree_queue_free */ -void -queue_free(struct queue *queue) -{ - struct queue_item *item, *next; - - for ( item = queue->head; item; item = next ) { - next = item->next; - free(item); - } -} -/* -->8-- */ - -/* ===== */ - -/* --8<-- tree_apply_preorder_it */ -void -tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) -{ - if ( tree ) { - struct stack stack; - - stack_init(&stack); - - stack_push(&stack, tree); - - while ( stack_pop(&stack, &tree) ) { - visit(tree->key, cl); - - if ( tree->right ) - stack_push(&stack, tree->right); - if ( tree->left ) - stack_push(&stack, tree->left); - } - - stack_free(&stack); - } -} -/* -->8-- */ - -/* --8<-- tree_apply_inorder_it */ -void -tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) -{ - if ( tree ) { - struct stack stack; - - stack_init(&stack); - - while ( !stack_empty(&stack) || tree ) { - if ( tree ) { - stack_push(&stack, tree); - tree = tree->left; - } - else { - stack_pop(&stack, &tree); - visit(tree->key, cl); - tree = tree->right; - } - } - - stack_free(&stack); - } -} -/* -->8-- */ - -// Hier eine Version für PostOrder-Iterativ: -// Quelle: https://stackoverflow.com/a/16092333 - -/* --8<-- tree_apply_postorder_it */ -void -tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) -{ - if ( tree ) { - struct stack stack; - - stack_init(&stack); - stack_push(&stack, tree); - - while ( !stack_empty(&stack) ) { - struct tree_node *next = stack_peek(&stack); - - bool finishedSubtrees = (next->left == tree || next->right == tree); - - if ( finishedSubtrees || tree_isleaf(next) ) { - stack_pop(&stack, &next); - - visit(next->key, cl); - - tree = next; - } - else { - if ( next->right ) { - stack_push(&stack, next->right); - } - if ( next->left ) { - stack_push(&stack, next->left); - } - } - } - stack_free(&stack); - } -} -/* -->8-- */ - -/* --8<-- tree_apply_levelorder_it */ -void -tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) -{ - if ( tree ) { - struct queue queue; - - queue_init(&queue); - - queue_put(&queue, tree); - - while ( queue_get(&queue, &tree) ) { - visit(tree->key, cl); - - if ( tree->left ) - queue_put(&queue, tree->left); - if ( tree->right ) - queue_put(&queue, tree->right); - } - - queue_free(&queue); - } -} -/* -->8-- */ - -/* ======================== */ - -/* --8<-- tree_iterator_type */ -struct tree_iterator { - struct stack stack; -}; -/* -->8-- */ - -/* --8<-- tree_iterator_push_leftmost */ -static void -tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node) -{ - for ( ; node; node = node->left ) { - stack_push(stack, node); - } -} -/* -->8-- */ - -/* --8<-- tree_iterator_next */ -struct tree_node * -tree_iterator_next(struct tree_iterator *it) -{ - struct tree_node *node = NULL; - - if ( stack_pop(&it->stack, &node) ) { - tree_iterator_push_leftmost(&it->stack, node->right); - } - - return node; -} -/* -->8-- */ - -/* --8<-- tree_iterator_first */ -struct tree_node * -tree_iterator_first(struct tree_iterator *it, struct tree_node *tree) -{ - stack_init(&it->stack); - - tree_iterator_push_leftmost(&it->stack, tree); - - return tree_iterator_next(it); -} -/* -->8-- */ - -/* --8<-- tree_iterator_free */ -void -tree_iterator_free(struct tree_iterator *it) -{ - stack_free(&it->stack); -} -/* -->8-- */ - -/* --8<-- tree_preorder_iterator_next */ -struct tree_node * -tree_preorder_iterator_next(struct tree_iterator *it) -{ - struct tree_node *node = NULL; - - if ( stack_pop(&it->stack, &node) ) { - if ( node->right ) { - stack_push(&it->stack, node->right); - } - if ( node->left ) { - stack_push(&it->stack, node->left); - } - } - - return node; -} -/* -->8-- */ - -/* --8<-- tree_preorder_iterator_first */ -struct tree_node * -tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree) -{ - stack_init(&it->stack); - - if ( tree ) { - stack_push(&it->stack, tree); - - return tree_preorder_iterator_next(it); - } - else { - return NULL; - } -} -/* -->8-- */ - -/* ===== */ - -void -print(T data, void *cl) -{ - (void) cl; - printf("%d\n", data); -} - -#include "treeutil.h" - -int -main_(void) -{ - // Teste den Fall von mycodeschool - - struct tree_node *tree = NULL; - - tree = tree_insert(tree, 12); - tree = tree_insert(tree, 5); - tree = tree_insert(tree, 15); - tree = tree_insert(tree, 3); - tree = tree_insert(tree, 7); - tree = tree_insert(tree, 13); - tree = tree_insert(tree, 17); - tree = tree_insert(tree, 1); - tree = tree_insert(tree, 9); - tree = tree_insert(tree, 14); - tree = tree_insert(tree, 20); - tree = tree_insert(tree, 8); - tree = tree_insert(tree, 11); - tree = tree_insert(tree, 18); - - tree = tree_remove(tree, 15); - - if ( !tree_isBst(tree) ) { - fprintf(stderr, "Tree ist kein BST!!\n"); - return EXIT_FAILURE; - } - - show_tree(tree, 0, 0); - - tree_clear(tree); - - return EXIT_SUCCESS; -} - -int -main__(void) -{ - struct tree_node *tree = NULL; - - tree = tree_insert(tree, 5); - tree = tree_insert(tree, 3); - tree = tree_insert(tree, 7); - tree = tree_insert(tree, 2); - tree = tree_insert(tree, 4); - tree = tree_insert(tree, 6); - tree = tree_insert(tree, 8); - - tree = tree_remove(tree, 2); - tree = tree_remove(tree, 3); - tree = tree_remove(tree, 5); - - if ( !tree_isBst(tree) ) { - fprintf(stderr, "Tree ist kein BST!!\n"); - return EXIT_FAILURE; - } - - show_tree(tree, 0, 0); - - tree_clear(tree); - - return EXIT_SUCCESS; -} - -int -main(void) -{ - struct tree_node *tree = NULL; - - tree = tree_insert_it(tree, 10); - tree = tree_insert_it(tree, 5); - tree = tree_insert_it(tree, 20); - tree = tree_insert_it(tree, 1); - tree = tree_insert_it(tree, 7); - tree = tree_insert_it(tree, 15); - tree = tree_insert_it(tree, 18); - - tree_apply_preorder(tree, print, NULL); - puts("postorder:"); - tree_apply_postorder(tree, print, NULL); - puts("postorder_it:"); - tree_apply_postorder_it(tree, print, NULL); - show_tree(tree, 0, 0); - - puts("levelorder_it:"); - tree_apply_levelorder_it(tree, print, NULL); - - show_tree(tree, 0, 0); - - struct tree_iterator it; - struct tree_node * node = tree_preorder_iterator_first(&it, tree); - while ( node ) { - fprintf(stdout, "%d\n", node->key); - - node = tree_preorder_iterator_next(&it); - } - tree_iterator_free(&it); - - tree_clear(tree); - - return EXIT_SUCCESS; -} -- cgit v1.3