From ac55496d881e0a17b3eff85f1faae5aafbc53b50 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Wed, 22 Jul 2020 17:30:45 +0200 Subject: erster Commit --- .gitignore | 16 ++ allocator.c | 75 +++++++ allocator.h | 31 +++ avl.c | 453 +++++++++++++++++++++++++++++++++++++++++ deque.c | 125 ++++++++++++ dlist.c | 539 ++++++++++++++++++++++++++++++++++++++++++++++++ hashtab.c | 198 ++++++++++++++++++ heap.c | 152 ++++++++++++++ list.c | 203 ++++++++++++++++++ makefile | 51 +++++ queue.c | 86 ++++++++ quicksort.c | 666 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ random.h | 47 +++++ rb.c | 661 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ rc4.c | 463 ++++++++++++++++++++++++++++++++++++++++++ readme.md | 12 ++ ringbuff.c | 72 +++++++ stack.c | 98 +++++++++ stack2.c | 100 +++++++++ tree.c | 466 ++++++++++++++++++++++++++++++++++++++++++ treeutil.h | 45 ++++ util.h | 32 +++ 22 files changed, 4591 insertions(+) create mode 100644 .gitignore create mode 100644 allocator.c create mode 100644 allocator.h create mode 100644 avl.c create mode 100644 deque.c create mode 100644 dlist.c create mode 100644 hashtab.c create mode 100644 heap.c create mode 100644 list.c create mode 100644 makefile create mode 100644 queue.c create mode 100644 quicksort.c create mode 100644 random.h create mode 100644 rb.c create mode 100644 rc4.c create mode 100644 readme.md create mode 100644 ringbuff.c create mode 100644 stack.c create mode 100644 stack2.c create mode 100644 tree.c create mode 100644 treeutil.h create mode 100644 util.h diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..d6748cb --- /dev/null +++ b/.gitignore @@ -0,0 +1,16 @@ +tags +allocator +avl +deque +dlist +hashtab +heap +list +queue +quicksort +rb +ringbuff +stack +stack2 +tree + diff --git a/allocator.c b/allocator.c new file mode 100644 index 0000000..c498bc7 --- /dev/null +++ b/allocator.c @@ -0,0 +1,75 @@ +#include +#include "allocator.h" + +/* Interface Code */ +static void * +default_allocate(struct its1_allocator *allocator, size_t n) +{ + (void) allocator; + return malloc(n); +} + +static void +default_deallocate(struct its1_allocator *allocator, void *ptr) +{ + (void) allocator; + free(ptr); +} + +struct its1_allocator its1_default_allocator = { + .allocate = &default_allocate, + .deallocate = &default_deallocate +}; + +/* Libary Code */ +#include + +void * +its1_malloc(struct its1_allocator *allocator, size_t n) +{ + if (allocator == NULL) { + allocator = &its1_default_allocator; + } + + return allocator->allocate(allocator, n); +} + +void +its1_free(struct its1_allocator *allocator, void *ptr) +{ + if (allocator == NULL) { + allocator = &its1_default_allocator; + } + + allocator->deallocate(allocator, ptr); +} + +char * +its1_strdup(struct its1_allocator *allocator, const char *str) +{ + size_t n; + char *dest; + + n = strlen(str) + 1; + dest = its1_malloc(allocator, n); + if (dest != NULL) { + memcpy(dest, str, n); + } + + return dest; +} + +void * +its1_malloc_zero(struct its1_allocator *allocator, size_t n) +{ + void *ptr; + + ptr = its1_malloc(allocator, n); + if (ptr != NULL) { + memset(ptr, 0, n); + } + + return ptr; +} + +int main() {} diff --git a/allocator.h b/allocator.h new file mode 100644 index 0000000..3cff385 --- /dev/null +++ b/allocator.h @@ -0,0 +1,31 @@ +#ifndef ITS1_ALLOCATOR_H_INCLUDED +#define ITS1_ALLOCATOR_H_INCLUDED + +struct its1_allocator { + void *(*allocate)(struct its1_allocator *allocator, size_t n); + void (*deallocate)(struct its1_allocator *allocator, void *ptr); +}; + +extern struct its1_allocator its1_default_allocator; + +/* allocator interface */ +void *its1_malloc(struct its1_allocator *allocator, size_t n); +void its1_free(struct its1_allocator *allocator, void *ptr); + +/* helper functions */ +char *its1_strdup(struct its1_allocator *allocator, const char *str); +void *its1_malloc_zero(struct its1_allocator *allocator, size_t n); + +#define ALLOCATE(n) \ + its1_malloc(&its1_default_allocator, (n)) + +#define ALLOCATE_ZERO(n) \ + its1_malloc_zero(&its1_default_allocator, (n)) + +#define FREE(ptr) \ + (its1_free(&its1_default_allocator, (ptr)), (ptr) = NULL) + +#define NEW(ptr) ((ptr) = ALLOCATE(sizeof *(ptr))) +#define NEW0(ptr) ((ptr) = ALLOCATE_ZERO(sizeof *(ptr))) + +#endif diff --git a/avl.c b/avl.c new file mode 100644 index 0000000..201dc5b --- /dev/null +++ b/avl.c @@ -0,0 +1,453 @@ +// AVL Tree +#include +#include +#include +#include + +/* utils */ +#include "util.h" + +// TODO: [x] Review: http://www.inr.ac.ru/~info21/ADen/ +// [x] Tests: https://stackoverflow.com/q/3955680 + +typedef int T; + +struct tree_node { + struct tree_node *left, *right; + int bal; + T key; + int count; /* collision counter */ + /* ggf. weitere Felder... */ +}; + +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 != NULL ) { + 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; + } + if ( p == NULL ) + ERROR("das hier sollte niemals passieren"); + return p; +} + +struct tree_node * +insert(struct tree_node *tree, T data) +{ + bool h = false; + return insert_r(data, tree, &h); +} + +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; +} + +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; +} + +static void +del(struct tree_node **q, struct tree_node **r, bool *h) +{ + if ( (*r)->right != NULL ) { + 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; + } +} + +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; +} + +struct tree_node * +delete(struct tree_node *tree, T data) +{ + bool h = false; + return delete_r(data, tree, &h); +} + + +// 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/deque.c b/deque.c new file mode 100644 index 0000000..7125764 --- /dev/null +++ b/deque.c @@ -0,0 +1,125 @@ +#include +#include +#include + +#define NELEM(x) (sizeof(x) / sizeof(x[0])) + +typedef int T; + +struct chunk { + int head, tail; + T array[8]; +}; + +static void +chunk_init(struct chunk *c) +{ + c->head = 0; + c->tail = 0; +} + +static bool +chunk_put(struct chunk *c, T data) +{ + const int next = (c->head + 1) % NELEM(c->array); + + if ( next == c->tail ) /* full? */ + return false; + + c->array[c->head] = data; + c->head = next; + + return true; +} + +static bool +chunk_get(struct chunk *c, T *data) +{ + if ( c->head == c->tail ) /* empty? */ + return false; + + const int next = (c->tail + 1) % NELEM(c->array); + + *data = c->array[c->tail]; + c->tail = next; + + return true; +} + +static int +chunk_size(struct chunk *c) +{ + return (c->head + NELEM(c->array) - c->tail) % NELEM(c->array); +} + +static bool +chunk_full(struct chunk *c) +{ + return ((c->head + 1) % NELEM(c->array)) == c->tail; +} + +static bool +chunk_empty(struct chunk *c) +{ + return c->head == c->tail; +} + +static T* +chunk_at(struct chunk *c, int idx) +{ + if ( idx < 0 || idx >= chunk_size(c) ) /* invalid index? */ + return NULL; + + return &c->array[(c->head + idx) % NELEM(c->array)]; +} + +/* ================= */ + +struct deque { + int head, tail, capacity; + + struct chunk **chunks; +}; + +void +deque_init(struct deque *d) +{ + int i; + + d->head = 0; + d->tail = 0; + d->capacity = 1; + + d->chunks = calloc(d->capacity, sizeof(struct chunk *)); + + for ( i = 0; i != d->capacity; ++i ) { + d->chunks[i] = malloc(sizeof(struct chunk)); + chunk_init(d->chunks[i]); + } +} + + +int main(void) +{ + struct chunk c; + int data; + + chunk_init(&c); + + chunk_put(&c, '0'); + chunk_put(&c, '0'); + chunk_get(&c, &data); + chunk_get(&c, &data); + + chunk_put(&c, 'A'); + chunk_put(&c, 'B'); + chunk_put(&c, 'C'); + chunk_put(&c, 'D'); + chunk_put(&c, 'E'); + chunk_put(&c, 'F'); + chunk_put(&c, 'G'); + + printf("head: %d -- tail: %d -- size: %d\n", c.head, c.tail, chunk_size(&c)); + return 0; +} + diff --git a/dlist.c b/dlist.c new file mode 100644 index 0000000..140d3a3 --- /dev/null +++ b/dlist.c @@ -0,0 +1,539 @@ +/* dlist -- double linked list */ + +/* Standard C */ +#include +#include +#include +#include +#include + +/* Project */ +#include "util.h" + +typedef int T; + +struct dlist { + struct dlist_element *head, *tail; +}; + +struct dlist_element { + struct dlist_element *prev, *next; + T data; +}; + +void +dlist_init(struct dlist *dlist) +{ + dlist->head = NULL; + dlist->tail = NULL; +} + +static struct dlist_element * +create_element(T data) +{ + struct dlist_element *element; + + element = malloc(sizeof *element); + if ( element != NULL ) { + element->data = data; + } + + return element; +} + +struct dlist_element * +dlist_push_front(struct dlist *dlist, T data) +{ + struct dlist_element *element; + + element = create_element(data); + if ( element != NULL ) { + element->prev = NULL; /* Vorgänger ist in jedem Fall NULL */ + + if ( dlist->head == NULL ) { /* empty list */ + element->next = NULL; + dlist->tail = element; + } + else { /* non empty list */ + 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; +} + +struct dlist_element * +dlist_push_back(struct dlist *dlist, T data) +{ + struct dlist_element *element; + + element = create_element(data); + if ( element != NULL ) { + element->next = NULL; /* Nachfolger ist in jedem Fall NULL */ + + if ( dlist->head == NULL ) { /* empty list */ + element->prev = NULL; + dlist->head = element; + } + else { /* non empty list */ + 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; +} + +bool +dlist_pop_front(struct dlist *dlist, T *data) +{ + if ( dlist->head != NULL ) { + struct dlist_element *element = dlist->head; + + dlist->head = element->next; + + if ( dlist->head == NULL ) + dlist->tail = NULL; + else + element->next->prev = NULL; + + *data = element->data; + free(element); + + return true; + } + else + return false; +} + +bool +dlist_pop_back(struct dlist *dlist, T *data) +{ + if ( dlist->head != NULL ) { + struct dlist_element *element = dlist->tail; + + dlist->tail = element->prev; + + if ( dlist->tail == NULL ) + dlist->head = NULL; + else + element->prev->next = NULL; + + *data = element->data; + free(element); + + return true; + } + else + return false; +} + +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 != NULL ) { + 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; +} + +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 != NULL ) { + 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; +} + +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); +} + +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); +} + +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); + } +} + +void +dlist_sort_xxx(struct dlist *list) +{ + if ( list->head == NULL ) + return; + + int insize = 1; + + while (1) { + struct dlist_element *p; + + p = list->head; + list->head = NULL; + list->tail = NULL; + + int nmerges = 0; /* count number of merges we do in this pass */ + + while (p) { + + struct dlist_element *q; + + nmerges++; /* there exists a merge to be done */ + /* step `insize' places along from p */ + q = p; + int psize = 0; + for (int i = 0; i < insize; i++) { + psize++; + q = q->next; + if (!q) break; + } + + /* if q hasn't fallen off end, we have two lists to merge */ + int qsize = insize; + + /* now we have two lists; merge them */ + while (psize > 0 || (qsize > 0 && q)) { + + struct dlist_element *e; + + /* decide whether next element of merge comes from p or q */ + if (psize == 0) { + /* p is empty; e must come from q. */ + e = q; q = q->next; qsize--; + } else if (qsize == 0 || !q) { + /* q is empty; e must come from p. */ + e = p; p = p->next; psize--; + } else if (p->data < q->data) { + /* First element of p is lower ; + * e must come from p. */ + e = p; p = p->next; psize--; + } else { + /* First element of q is lower; e must come from q. */ + e = q; q = q->next; qsize--; + } + + /* add the next element to the merged list */ + if (list->tail) { + list->tail->next = e; + } else { + list->head = e; + } + e->prev = list->tail; + list->tail = e; + } + + /* now p has stepped `insize' places along, and q has too */ + p = q; + } + list->tail->next = NULL; + + /* If we have done only one merge, we're finished. */ + if (nmerges <= 1) /* allow for nmerges==0, the empty list case */ + return; // list; + + /* Otherwise repeat, merging lists twice the size */ + insize *= 2; + } +} + +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 != NULL && e2 != NULL ) // Solange in e1 UND e2 Elemente sind... + { + if ( e1->data < e2->data ) + { + e1->prev = cur; + if ( cur != NULL ) + cur->next = e1; + else + head = e1; + cur = e1; + e1 = e1->next; + } + else + { + e2->prev = cur; + if ( cur != NULL ) + cur->next = e2; + else + head = e2; + cur = e2; + e2 = e2->next; + } + } + + if ( e1 != NULL ) // in e1 sind noch Elemente vorhanden! + { + assert(e2 == NULL); + + e1->prev = cur; + if ( cur != NULL ) + cur->next = e1; + else + head = e1; + + // list1->tail zeigt bereits auf das letzte Element in list1 + } + else /* if ( e2 != NULL ) */ + { + assert(e1 == NULL); + assert(e2 != NULL); + + e2->prev = cur; + if ( cur != NULL ) + 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; +} + +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 != NULL && fast->next != NULL ) + 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; +} + +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/hashtab.c b/hashtab.c new file mode 100644 index 0000000..6b35c89 --- /dev/null +++ b/hashtab.c @@ -0,0 +1,198 @@ +#include +#include +#include +#include +#include + +#include "util.h" + +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... +}; + +static unsigned long +hash_key(const unsigned char *str) +{ + unsigned long hash = 5381; + int c; + + while ( (c = *str++) != '\0' ) + hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + + return hash; +} + +void +hash_init(struct hash_tab *ht) +{ + for ( int i = 0; i != NELEM(ht->table); ++i ) + ht->table[i] = NULL; +} + +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; +} + +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 != NULL ) + ht->table[h] = item; + else + ERROR("can't create item"); + } + + return item ? &item->data : NULL; +} + +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; +} + +void +hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl) +{ + struct hash_item *item; + + for ( int i = 0; i != NELEM(ht->table); ++i ) + for ( item = ht->table[i]; item; item = item->next ) + visit(item->key, item->data, cl); +} + +void +hash_free(struct hash_tab *ht) +{ + struct hash_item *p, *next; + + for ( int 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; + } +} + +int getword(FILE *fp, char *buf, int size, int first(int c), int rest(int c)) +{ + int i = 0, 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; +} + +int first(int c) { + return isalpha(c); +} + +int rest(int c) { + return isalpha(c) || c == '_'; +} + +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) ) { + int *p = hash_lookup(ht, word, 0, 1); + if ( p != NULL ) + ++(*p); + } + + hash_delete(ht, "new_item"); + + hash_apply(ht, print, stdout); + + hash_free(ht); +} + diff --git a/heap.c b/heap.c new file mode 100644 index 0000000..365d925 --- /dev/null +++ b/heap.c @@ -0,0 +1,152 @@ +#include +#include +#include +#include "util.h" + +typedef int T; + +// https://stackoverflow.com/a/22900767 + +#define LEFT(idx) (idx*2+1) +#define RIGHT(idx) (idx*2+2) +#define PARENT(idx) ((idx-1)/2) + +static void +swap(T heap[], int i, int j) +{ + T temp = heap[i]; + heap[i] = heap[j]; + heap[j] = temp; +} + +static void +fixup(T heap[], int i) +{ + int p = PARENT(i); + + while ( i > 0 && heap[p] < heap[i] ) { + swap(heap, i, p); + + i = p; + p = PARENT(i); + } +} + +static void +fixdown(T heap[], int i, int n) +{ + for ( ;; ) { + const int l = LEFT(i); + const int r = RIGHT(i); + int m = i; + + if ( l < n && heap[m] < heap[l] ) + m = l; + + if ( r < n && heap[m] < heap[r] ) + m = r; + + if ( m == i ) + break; + + swap(heap, m, i); + + i = m; + } +} + +static void +heapify(T heap[], int n) +{ + for ( int i = n / 2 - 1; i >= 0; --i ) + fixdown(heap, i, n); +} + +static void +my_heapsort(T a[], int n) +{ + heapify(a, n); + + for ( int i = n - 1; i >= 0; --i ) { + swap(a, 0, i); + fixdown(a, 0, i); + } +} + +// ------------------------------------------- + +struct pq { // Priority Queue + T heap[251]; + int sz; +}; + +void +pq_init(struct pq *pq) +{ + pq->sz = 0; +} + +bool +pq_push(struct pq *pq, T data) +{ + if ( pq->sz == NELEM(pq->heap) ) + return false; + + pq->heap[pq->sz] = data; + fixup(pq->heap, pq->sz); + ++pq->sz; + return true; +} + +bool +pq_pop(struct pq *pq, T* data) +{ + if ( pq->sz == 0 ) + return false; + + *data = pq->heap[0]; + --pq->sz; + pq->heap[0] = pq->heap[pq->sz]; + fixdown(pq->heap, 0, pq->sz); + return true; +} + +// ------------------------------------------- + + +void print_heap(T heap[], int n) +{ + if ( n ) { + printf("%d", heap[0]); + for ( int i = 1; i != n; ++i ) + printf(", %d", heap[i]); + putchar('\n'); + } +} + +int main(void) +{ +#if 0 // Heap-Testprogramm + T heap[20] = { 18, 18, 16, 9, 7, 1, 9, 3, 7, 5 }; + + print_heap(heap, 10); + + //heap[10] = 13; fixup(heap, 10); + swap(heap, 0, 9); fixdown(heap, 0, 9); + + print_heap(heap, 9); +#endif + + struct pq pq[1]; + + pq_init(pq); + + for ( int i = 0; i != 10; ++i ) + pq_push(pq, rand()); + + T data; + while ( pq_pop(pq, &data) ) + printf("%d\n", data); +} + + diff --git a/list.c b/list.c new file mode 100644 index 0000000..8b18de8 --- /dev/null +++ b/list.c @@ -0,0 +1,203 @@ +/* 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" + +typedef int T; + +struct list_item { + struct list_item *next; + T data; +}; + +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 != NULL ) { + new_item->next = next; + new_item->data = data; + } + else + ERROR("out of memory"); + + return new_item; +} + +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; + } + //ERROR("data not found"); /* uncomment, if this case should be reported as an error */ + return list; +} + +size_t +list_length(struct list_item *list) +{ + size_t len = 0; + + for ( ; list; list = list->next ) + ++len; + + return len; +} + +struct list_item * +list_copy(struct list_item *list) +{ + struct list_item *head, **p = &head; + + for ( ; list; list = list->next ) { + *p = malloc(sizeof **p); + if ( *p != NULL ) { + (*p)->data = list->data; // copy elements + p = &(*p)->next; + } + else + ERROR("out of memory"); + } + *p = NULL; + return head; +} + +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; +} + +void +list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl) +{ + for ( ; list; list = list->next ) { + visit(list->data, cl); + } +} + +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 != NULL && b != NULL ) + 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 != NULL ) ? a : b; + + return head->next; +} + +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 != NULL && b->next != NULL ) + c = c->next, b = b->next->next; + + b = c->next, c->next = NULL; + + return list_merge(list_sort(a), list_sort(b)); +} + +void +list_free(struct list_item *list) +{ + struct list_item *next; + + for ( ; list; list = next ) { + next = list->next; + free(list); + } +} + +static void print_data(T data, void *cl) { fprintf(cl, "%d\n", data); } + +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/makefile b/makefile new file mode 100644 index 0000000..0c229d6 --- /dev/null +++ b/makefile @@ -0,0 +1,51 @@ +.PHONY: all clean + +CFLAGS=-O3 -Wall -Werror -Wno-unused-function -pedantic -std=c99 -g + +all: list dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque + +list: list.c util.h + cc $(CFLAGS) $< -o $@ + +dlist: dlist.c util.h + cc $(CFLAGS) $< -o $@ + +stack: stack.c util.h + cc $(CFLAGS) $< -o $@ + +stack2: stack2.c util.h + cc $(CFLAGS) $< -o $@ + +queue: queue.c util.h + cc $(CFLAGS) $< -o $@ + +ringbuff: ringbuff.c util.h + cc $(CFLAGS) $< -o $@ + +hashtab: hashtab.c util.h + cc $(CFLAGS) $< -o $@ + +tree: tree.c util.h + cc $(CFLAGS) $< -o $@ + +avl: avl.c util.h + cc $(CFLAGS) $< -o $@ + +rb: rb.c util.h + cc $(CFLAGS) $< -o $@ + +deque: deque.c util.h + cc $(CFLAGS) $< -o $@ + +heap: heap.c util.h + cc $(CFLAGS) $< -o $@ + +quicksort: quicksort.c util.h + cc $(CFLAGS) $< -o $@ + +allocator: allocator.c allocator.h + cc $(CFLAGS) $< -o $@ + +clean: + rm -f list dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque + diff --git a/queue.c b/queue.c new file mode 100644 index 0000000..fdacca5 --- /dev/null +++ b/queue.c @@ -0,0 +1,86 @@ +/* Standard C */ +#include +#include +#include + +/* Project */ +#include "util.h" + +typedef int T; + +struct queue_item { + struct queue_item *next; + T data; +}; + +struct queue { + struct queue_item *head, *tail; +}; + +void +queue_init(struct queue *queue) +{ + queue->head = NULL; +} + +void +queue_put(struct queue *queue, T data) +{ + struct queue_item *new_item; + + if ( (new_item = malloc(sizeof(*new_item))) != NULL ) { + struct queue_item *tmp = queue->tail; + new_item->data = data; + queue->tail = new_item; + if ( queue->head == NULL ) + queue->head = queue->tail; + else + tmp->next = queue->tail; + } + else + ERROR("out of memory"); +} + +bool +queue_get(struct queue *queue, T *data) +{ + if ( queue->head != NULL ) { + struct queue_item *next = queue->head->next; + *data = queue->head->data; + free(queue->head); + queue->head = next; + + return true; + } + else + return false; +} + +bool +queue_empty(struct queue *queue) +{ + return queue->head == NULL; +} + +int +main() +{ + struct queue queue[1]; + + queue_init(queue); + + for ( int i = 0; i != 10; ++i ) + queue_put(queue, i); + + while ( !queue_empty(queue) ) { + int i; + if ( queue_get(queue, &i) ) + printf("%d\n", i); + else + ERROR("this shouldn't happen!"); + } + return EXIT_SUCCESS; +} + + + diff --git a/quicksort.c b/quicksort.c new file mode 100644 index 0000000..fa219e9 --- /dev/null +++ b/quicksort.c @@ -0,0 +1,666 @@ +#include +#include +#include +#include +#include "util.h" + +static int bigrand(void) +{ + int x = (rand() << 24) | (rand() << 16) | (rand() << 8) | rand(); + if ( x < 0 ) + return -x; + return x; +} + +static int randint(int l, int u) +{ + return l + bigrand() % (u-l+1); +} + +typedef int T; + +static const int CUTOFF = 128; + +static inline void +swap(T a[], int i, int j) +{ + T t = a[i]; + a[i] = a[j]; + a[j] = t; +} + +static void +insertsort(T a[], int n) +{ + int i, j; + for ( i = 1; i < n; ++i ) + { + T t = a[i]; + for ( j = i; j > 0 && a[j-1] > t; --j ) + a[j] = a[j-1]; + a[j] = t; + } +} + +static void +quicksort(T a[], int n) +{ + int i, last; + + if ( n <= CUTOFF ) + return; + + swap(a, 0, bigrand() % n); + + last = 0; + for ( i = 1; i < n; ++i ) + if ( a[i] < a[0] ) + swap(a, ++last, i); + + swap(a, 0, last); + + quicksort(a, last); + quicksort(a+last+1, n-last-1); +} + +void +my_quicksort(T a[], int n) +{ + quicksort(a, n); + insertsort(a, n); +} + + +static int +cmp(const void *a, const void *b) +{ + const int *pa = (const T *) a; + const int *pb = (const T *) b; + + if ( *pa < *pb ) return -1; + if ( *pa > *pb ) return 1; + return 0; +} + +void +c_quicksort(T a[], int n) +{ + qsort(a, n, sizeof(T), cmp); +} + +/* This function takes last element as pivot, places + the pivot element at its correct position in sorted + array, and places all smaller (smaller than pivot) + to left of pivot and all greater elements to right + of pivot */ +int partition (int arr[], int low, int high) +{ + int pivot = arr[high]; // pivot + int i = (low - 1); // Index of smaller element + + for (int j = low; j <= high- 1; j++) + { + // If current element is smaller than or + // equal to pivot + if (arr[j] <= pivot) + { + i++; // increment index of smaller element + swap(arr, i, j); + } + } + swap(arr, i + 1, high); + return (i + 1); +} + +/* The main function that implements QuickSort + arr[] --> Array to be sorted, + low --> Starting index, + high --> Ending index */ +void quickSort(int arr[], int low, int high) +{ + while (low < high) + { + /* pi is partitioning index, arr[p] is now + at right place */ + int pi = partition(arr, low, high); + + if (pi - low < high - pi) + { + quickSort(arr, low, pi - 1); + low = pi + 1; + } + else + { + quickSort(arr, pi + 1, high); + high = pi - 1; + } + } +} + +void g4g_quicksort(T a[], int n) +{ + quickSort(a, 0, n-1); +} + + +static void three_way_quicksort(int a[], int l, int r) +{ + int k; + T v = a[r]; + + if ( r <= l ) + return; + + int i = l-1, j = r, p = l-1, q = r; + + for ( ;; ) { + while ( a[++i] < v ) + ; + while ( v < a[--j] ) + if ( j == l ) + break; + if ( i >= j ) + break; + + swap(a, i, j); + + if ( a[i] == v ) + swap(a, ++p, i); + if ( v == a[j] ) + swap(a, --q, j); + } + swap(a, i, r); j = i-1; i = i+1; + + for ( k = l ; k <= p; ++k, --j ) + swap(a, k, j); + for ( k = r-1; k >= q; --k, ++i ) + swap(a, k, i); + + three_way_quicksort(a, l, j); + three_way_quicksort(a, i, r); +} + +void sed_quicksort(int a[], int n) +{ + three_way_quicksort(a, 0, n-1); +} + +/* ====================== HEAPSORT ======================= */ + +#define LEFT(idx) (idx*2+1) +#define RIGHT(idx) (idx*2+2) +#define PARENT(idx) ((idx-1)/2) + +static void +fixdown(T heap[], int i, int n) +{ + for ( ;; ) { + const int l = LEFT(i); + const int r = RIGHT(i); + int m = i; + + if ( l < n && heap[m] < heap[l] ) + m = l; + + if ( r < n && heap[m] < heap[r] ) + m = r; + + if ( m == i ) + break; + + swap(heap, m, i); + + i = m; + } +} + +static void +heapify(T heap[], int n) +{ + for ( int i = n / 2 - 1; i >= 0; --i ) + fixdown(heap, i, n); +} + +void +my_heapsort(T a[], int n) +{ + heapify(a, n); + + for ( int i = n-1; i >= 0; --i ) { + swap(a, 0, i); + fixdown(a, 0, i); + } +} + +void +heapsort_bu( T * data, int n ) // zu sortierendes Feld und seine Länge +{ + T val; + int parent, child; + int root= n >> 1; // erstes Blatt im Baum + int count= 0; // Zähler für Anzahl der Vergleiche + + for ( ; ; ) + { + if ( root ) { // Teil 1: Konstruktion des Heaps + parent= --root; + val= data[root]; // zu versickernder Wert + } + else + if ( --n ) { // Teil 2: eigentliche Sortierung + val= data[n]; // zu versickernder Wert vom Heap-Ende + data[n]= data[0]; // Spitze des Heaps hinter den Heap in + parent= 0; // den sortierten Bereich verschieben + } + else // Heap ist leer; Sortierung beendet + break; + + while ( (child= (parent + 1) << 1) < n ) // zweites (!) Kind; + { // Abbruch am Ende des Heaps + if ( ++count, data[child-1] > data[child] ) // größeres Kind wählen + --child; + + data[parent]= data[child]; // größeres Kind nach oben rücken + parent= child; // in der Ebene darunter weitersuchen + } + + if ( child == n ) // ein einzelnes Kind am Heap-Ende + { // ist übersprungen worden + if ( ++count, data[--child] >= val ) { // größer als der zu versick- + data[parent]= data[child]; // ernde Wert, also noch nach oben + data[child]= val; // versickerten Wert eintragen + continue; + } + + child= parent; // 1 Ebene nach oben zurück + } + else + { + if ( ++count, data[parent] >= val ) { // das Blatt ist größer als der + data[parent]= val; // zu versickernde Wert, der damit + continue; // direkt eingetragen werden kann + } + + child= (parent - 1) >> 1; // 2 Ebenen nach oben zurück + } + + while ( child != root ) // maximal zum Ausgangspunkt zurück + { + parent= (child - 1) >> 1; // den Vergleichswert haben wir bereits + // nach oben verschoben + if ( ++count, data[parent] >= val ) // größer als der zu versickernde + break; // Wert, also Position gefunden + + data[child]= data[parent]; // Rückverschiebung nötig + child= parent; // 1 Ebene nach oben zurück + } + + data[child]= val; // versickerten Wert eintragen + } +} + +/*----------------------------------------------------------------------*/ +/* BOTTOM-UP HEAPSORT */ +/* Written by J. Teuhola ; the original idea is */ +/* probably due to R.W. Floyd. Thereafter it has been used by many */ +/* authors, among others S. Carlsson and I. Wegener. Building the heap */ +/* bottom-up is also due to R. W. Floyd: Treesort 3 (Algorithm 245), */ +/* Communications of the ACM 7, p. 701, 1964. */ +/*----------------------------------------------------------------------*/ + +#define element float + +/*-----------------------------------------------------------------------*/ +/* The sift-up procedure sinks a hole from v[i] to leaf and then sifts */ +/* the original v[i] element from the leaf level up. This is the main */ +/* idea of bottom-up heapsort. */ +/*-----------------------------------------------------------------------*/ +static void siftup(T v[], int i, int n) +{ + int j, start; + T x; + + start = i; + x = v[i]; + j = i<<1; + while (j<=n) + { + if (j>1; + while (j>=start) + { if (v[j]>1; + } + else break; + } + v[i] = x; +} /* End of siftup */ + +/*----------------------------------------------------------------------*/ +/* The heapsort procedure; the original array is r[0..n-1], but here */ +/* it is shifted to vector v[1..n], for convenience. */ +/*----------------------------------------------------------------------*/ +void bottom_up_heapsort(T r[], int n) +{ + int k; + T x; + T *v; + + v = r-1; /* The address shift */ + +/* Build the heap bottom-up, using siftup. */ + for (k=n>>1; k>1; k--) siftup(v, k, n); + +/* The main loop of sorting follows. The root is swapped with the last */ +/* leaf after each sift-up. */ + for (k=n; k>1; k--) + { + siftup(v, 1, k); + x = v[k]; v[k] = v[1]; v[1] = x; + } +} /* End of bottom_up_heapsort */ + + + +/* ====================== HEAPSORT ======================= */ + +/* ====================== INTROSORT ======================= */ + + + +static void +introsort(T a[], int n, int h) +{ + int i, last; + + if ( n <= CUTOFF ) + return; + + if ( --h == 1 ) { + my_heapsort(a, n); + return; + } + + swap(a, 0, bigrand() % n); + + last = 0; + for ( i = 1; i < n; ++i ) + if ( a[i] < a[0] ) + swap(a, ++last, i); + + swap(a, 0, last); + + introsort(a, last, h); + introsort(a+last+1, n-last-1, h); +} + +void +my_introsort(T a[], int n) +{ + int h = 1; + + for ( int nn = 1; nn < n; nn <<= 1 ) + ++h; + + introsort(a, n, h); + insertsort(a, n); +} + +static void pp_quicksort_impl(T a[], int l, int u) +{ + if ( u - l < CUTOFF ) + return; + + swap(a, l, randint(l, u)); + + T t = a[l]; + int i = l; + int j = u+1; + for (;;) { + do i++; while ( /*i <= u &&*/ a[i] < t ); + do j--; while ( a[j] > t ); + if ( i > j ) + break; + swap(a, i, j); + } + swap(a, l, j); + pp_quicksort_impl(a, l, j-1); + pp_quicksort_impl(a, j+1, u); +} + +void +pp_quicksort(T a[], int n) +{ + pp_quicksort_impl(a, 0, n-1); + insertsort(a, n); +} + +static void pp_quicksort_impl_it(T a[], int l, int u, int h) +{ + if ( --h == 1 ) { + my_heapsort(a+l, u-l+1); + return; + } + + while ( u-l >= CUTOFF ) + { + swap(a, l, randint(l, u)); + + T t = a[l]; + int i = l; + int j = u+1; + + for (;;) { + do i++; while ( /*i <= u && */ a[i] < t ); + do j--; while ( a[j] > t ); + if ( i > j ) + break; + swap(a, i, j); + } + swap(a, l, j); + + if ( j - l < u - j ) + { + pp_quicksort_impl_it(a, l, j-1, h); + l = j + 1; + } + else + { + pp_quicksort_impl_it(a, j+1, u, h); + u = j - 1; + } + } +} + +void +pp_quicksort_it(T a[], int n) +{ + int h = 1; + + for ( int nn = 1; nn < n; nn <<= 1 ) + ++h; + + pp_quicksort_impl_it(a, 0, n-1, h); + insertsort(a, n); +} + +int +binary_search(T x, T v[], int n) +{ + int low, high; + + low = 0; + high = n-1; + while ( low <= high ) { + int mid = low + ((high - low) / 2); + if ( x > v[mid] ) + low = mid + 1; + else if ( x < v[mid] ) + high = mid - 1; + else + return mid; + } + return -1; +} + +int +lower_bound(T x, T v[], int n) +{ + int low, high; + + low = 0; + high = n; + while ( low < high ) { + int mid = low + ((high - low) / 2); + + if ( x > v[mid] ) + low = mid + 1; + else + high = mid; + } + return x == v[low] ? low : -1; +} + +int +upper_bound(T x, T v[], int n) +{ + int low, high; + + low = 0; + high = n; + while ( low < high ) { + int mid = low + ((high - low) / 2); + + if ( x >= v[mid] ) + low = mid + 1; + else + high = mid; + } + return ( low > 0 && x == v[low-1] ) ? low-1 : -1; +} + +/* TESTTREIBER */ + + +void gen_testset_random(T a[], int n) +{ + for ( int i = 0; i < n; ++i ) + a[i] = bigrand(); +} + +void gen_testset_random2(T a[], int n) +{ + for ( int i = 0; i < n; ++i ) + a[i] = bigrand() % 100; +} + +void gen_testset_asc(T a[], int n) +{ + for ( int i = 0; i < n; ++i ) + a[i] = i; +} + +void gen_testset_desc(T a[], int n) +{ + for ( int i = n; i >= 0; --i ) + a[i] = i; +} + +void gen_testset_unique(T a[], int n) +{ + for ( int i = 0; i < n; ++i ) + a[i] = 1; +} + +void test_sorting(T a[], int n) +{ + for ( int i = 1; i < n; ++i ) + if ( a[i-1] > a[i] ) { + puts("Fehler!"); + exit(EXIT_SUCCESS); + } +} + +void do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[], int n)) +{ + T *a; + clock_t start, ende; + + a = malloc(sizeof(T) * n); + + (*gen_testset)(a, n); + + start = clock(); + (*do_sort)(a, n); + ende = clock(); + + test_sorting(a, n); + + free(a); + + printf("%10.3lf sec", ((double) ende - start) / CLOCKS_PER_SEC); + fflush(stdout); +} + +void do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n)) +{ + printf("%-15.15s n=%-10d: ", msg, n); + do_one_test(n, do_sort, gen_testset_random); + do_one_test(n, do_sort, gen_testset_random2); + do_one_test(n, do_sort, gen_testset_asc); + do_one_test(n, do_sort, gen_testset_desc); + do_one_test(n, do_sort, gen_testset_unique); + putchar('\n'); +} + +/* ENDE TESTTREIBER */ + +int main(void) +{ + const int n = 20000000; + + srand(time(0)); + do_all_tests("my_heapsort", n, my_heapsort); + do_all_tests("heapsort_bu", n, heapsort_bu); + do_all_tests("bottom_up_heapsort", n, bottom_up_heapsort); + do_all_tests("c_quicksort", n, c_quicksort); + //do_all_tests("g4g_quicksort", n, g4g_quicksort); + //do_all_tests("sed_quicksort", n, sed_quicksort); + do_all_tests("my_introsort", n, my_introsort); + //do_all_tests("my_quicksort", n, my_quicksort); + do_all_tests("pp_quicksort", n, pp_quicksort); + do_all_tests("pp_quicksort_it", n, pp_quicksort_it); + + return 0; +} + +#if 0 +int _main(void) +{ + T array[20]; + + for ( int i = 0; i != NELEM(array); ++i ) + array[i] = rand() % 10; + + sort(array, NELEM(array)); + print(array, NELEM(array)); + + int value; + while ( scanf("%d", &value) == 1 && value != -1 ) { + int bs = binary_search(value, array, NELEM(array)); + int lb = lower_bound(value, array, NELEM(array)); + int ub = upper_bound(value, array, NELEM(array)); + + printf("bs: %d - lb: %d - ub: %d\n", bs, lb, ub); + } + + return EXIT_SUCCESS; +} +#endif + diff --git a/random.h b/random.h new file mode 100644 index 0000000..9094d5b --- /dev/null +++ b/random.h @@ -0,0 +1,47 @@ +#ifndef ITS1_RANDOM_H_INCLUDED +#define ITS1_RANDOM_H_INCLUDED + +#ifdef __cplusplus +extern "C" { +#endif + +struct random_ctx { + unsigned char (*get_byte)(struct random_ctx *ctx); +}; + +static unsigned char +random_get_byte(struct random_ctx *ctx) +{ + return ctx->get_byte(ctx); +} + +static unsigned short +random_get_word(struct random_ctx *ctx) +{ + return (ctx->get_byte(ctx) << 8) + | ctx->get_byte(ctx) + ; +} + +static unsigned long +random_get_dword(struct random_ctx *ctx) +{ + return (ctx->get_byte(ctx) << 24) + | (ctx->get_byte(ctx) << 16) + | (ctx->get_byte(ctx) << 8) + | ctx->get_byte(ctx) + ; +} + +static unsigned long +random_get_dword_range(struct random_ctx *ctx, unsigned long l, unsigned long u) +{ + return l + random_get_dword(ctx) % (u - l + 1); +} + +#ifdef __cplusplus +} +#endif + +#endif /* ITS1_RANDOM_H_INCLUDED */ + diff --git a/rb.c b/rb.c new file mode 100644 index 0000000..c95ab83 --- /dev/null +++ b/rb.c @@ -0,0 +1,661 @@ +#include +#include +#include +#include "util.h" + +typedef int T; + +#if 0 +struct rbtree { + T data; + enum { RED, BLACK } color; + struct rbtree *left, *right, *p; +}; + +struct rbtree * +rb_alloc(T data) +{ + struct rbtree *node = malloc(sizeof *node); + if ( node ) + { + node->data = data; + node->left = NULL; + node->right = NULL; + node->p = NULL; + } + return node; +} + +void +rb_left_rotate(struct rbtree **root, struct rbtree *x) +{ + struct rbtree *y = x->right; + x->right = y->left; + if ( y->left ) + y->left->p = x; + + y->p = x->p; + if ( x->p == NULL ) + *root = y; + else if ( x == x->p->left ) + x->p->left = y; + else + x->p->right = y; + + y->left = x; + x->p = y; +} + +void +rb_right_rotate(struct rbtree **root, struct rbtree *y) +{ + struct rbtree *x = y->left; + y->left = x->right; + if ( x->right ) + x->right->p = y; + + x->p = y->p; + if ( y->p == NULL ) + *root = x; + else if ( y == y->p->left ) + y->p->left = x; + else + y->p->right = x; + + x->right = y; + y->p = x; +} + +void +rb_insert_fixup(struct rbtree **root, struct rbtree **z) +{ + struct rbtree *y; + + while ( z->p->color == RED ) { + if ( z->p == z->p->p->left ) { + y = z->p->p->right; + if ( y->color == RED ) { + z->p->color = BLACK; + y->color = BLACK; + z->p->p->color = RED; + z = z->p->p; + } + else { + if ( z == z->p->right ) { + z = z->p; + rb_left_rotate(root, z); + } + z->p->color = BLACK; + z->p->p->color = RED; + rb_right_rotate(root, z->p->p); + } + } + else { + y = z->p->p->left; + if ( y->color == RED ) { + z->p->color = BLACK; + y->color = BLACK; + z->p->p->color = RED; + z = z->p->p; + } + else { + if ( z == z->p->left ) { + z = z->p; + rb_right_rotate(root, z); + } + z->p->color = BLACK; + z->p->p->color = RED; + rb_left_rotate(root, z->p->p); + } + } + } + + (*root)->color = BLACK; +} + +void +rb_insert_node(struct rbtree **root, T data) +{ + struct rbtree *z = rb_alloc(data); + + if ( *root == NULL ) { + z->color = BLACK; + *root = z; + } + else { + struct rbtree *y = NULL; + struct rbtree *x = *root; + + while ( x ) { + y = x; + if ( z->data < x->data ) + x = x->left; + else + x = x->right; + } + z->p = y; + + if ( y == NULL ) // kann entfallen! + *root = z; + else if ( z->data < y->data ) + y->left = z; + else + y->right = z; + + z->left = NULL; // kann entfallen! + z->right = NULL; // kann entfallen! + z->color = RED; + + rb_insert_fixup(root, &z); + } +} + +#endif + + + +/* 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) { +#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(struct rbtree_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(struct rbtree_node_t)); + 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; icolor == 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(); + print_tree(t); + + for(i=0; i<5000; i++) { + long x = rand() % 10000; + long y = rand() % 10000; +#ifdef TRACE + print_tree(t); + printf("Inserting %d -> %d\n\n", x, y); +#endif + rbtree_insert(t, (void*)x, (void*)y, compare_int); + assert(rbtree_lookup(t, (void*)x, compare_int) == (void*)y); + } + for(i=0; i<60000; i++) { + long x = rand() % 10000; +#ifdef TRACE + print_tree(t); + printf("Deleting key %d\n\n", x); +#endif + rbtree_delete(t, (void*)x, compare_int); + } + return 0; +} + +#if 0 +int main__(void) +{ + struct rbtree *tree = NULL; + + srand(time(NULL)); + for ( int i = 0; i != 10; ++i ) + rb_insert_node(&tree, rand()); + +} +#endif diff --git a/rc4.c b/rc4.c new file mode 100644 index 0000000..119711c --- /dev/null +++ b/rc4.c @@ -0,0 +1,463 @@ +#include +#include +#include /* memset() */ +#include "util.h" + +#include "random.h" + +struct rc4_ctx { + struct random_ctx ctx; + + unsigned int i; + unsigned int j; + unsigned char S[256]; +}; + +static void +swap(unsigned char a[], unsigned int i, unsigned int j) +{ + unsigned char t = a[i]; a[i] = a[j]; a[j] = t; +} + +unsigned char +rc4_get_byte(struct rc4_ctx *ctx) +{ + ctx->i = (ctx->i + 1) % 256; + ctx->j = (ctx->j + ctx->S[ctx->i]) % 256; + swap(ctx->S, ctx->i, ctx->j); + + return ctx->S[(ctx->S[ctx->i] + ctx->S[ctx->j]) % 256]; +} + +void +rc4_init(struct rc4_ctx *ctx, void *key, size_t sz) +{ + const unsigned char *K = key; + unsigned int i, j; + + for ( i = 0; i != 256; ++i ) + ctx->S[i] = i; + + for ( i = j = 0; i != 256; ++i ) { + j = (j + ctx->S[i] + K[i % sz]) % 256; + swap(ctx->S, i, j); + } + + ctx->i = 0; + ctx->j = 0; + ctx->ctx.get_byte = (unsigned char (*)(struct random_ctx *)) rc4_get_byte; +} + +void +rc4_clear(struct rc4_ctx *ctx) +{ + memset(ctx, 0, sizeof *ctx); +} + +struct random_ctx * +rc4_create(void *key, size_t sz) +{ + struct rc4_ctx *ctx; + + ctx = malloc(sizeof(*ctx)); + if ( ctx != NULL ) { + rc4_init(ctx, key, sz); + + return &(ctx->ctx); + } + + return NULL; +} + +void +rc4_free(struct random_ctx *ctx) +{ + rc4_clear((struct rc4_ctx *) ctx); + free(ctx); +} + +void +rc4_test(void) +{ + static struct { + char *key; + unsigned int sz; + struct { + unsigned int pos; + unsigned char bytes[16]; + } test[18]; + } cases[] = { + { + "\x01\x02\x03\x04\x05", 5, + { + { 0, "\xb2\x39\x63\x05\xf0\x3d\xc0\x27\xcc\xc3\x52\x4a\x0a\x11\x18\xa8" }, + { 16, "\x69\x82\x94\x4f\x18\xfc\x82\xd5\x89\xc4\x03\xa4\x7a\x0d\x09\x19" }, + { 240, "\x28\xcb\x11\x32\xc9\x6c\xe2\x86\x42\x1d\xca\xad\xb8\xb6\x9e\xae" }, + { 256, "\x1c\xfc\xf6\x2b\x03\xed\xdb\x64\x1d\x77\xdf\xcf\x7f\x8d\x8c\x93" }, + { 496, "\x42\xb7\xd0\xcd\xd9\x18\xa8\xa3\x3d\xd5\x17\x81\xc8\x1f\x40\x41" }, + { 512, "\x64\x59\x84\x44\x32\xa7\xda\x92\x3c\xfb\x3e\xb4\x98\x06\x61\xf6" }, + { 752, "\xec\x10\x32\x7b\xde\x2b\xee\xfd\x18\xf9\x27\x76\x80\x45\x7e\x22" }, + { 768, "\xeb\x62\x63\x8d\x4f\x0b\xa1\xfe\x9f\xca\x20\xe0\x5b\xf8\xff\x2b" }, + { 1008, "\x45\x12\x90\x48\xe6\xa0\xed\x0b\x56\xb4\x90\x33\x8f\x07\x8d\xa5" }, + { 1024, "\x30\xab\xbc\xc7\xc2\x0b\x01\x60\x9f\x23\xee\x2d\x5f\x6b\xb7\xdf" }, + { 1520, "\x32\x94\xf7\x44\xd8\xf9\x79\x05\x07\xe7\x0f\x62\xe5\xbb\xce\xea" }, + { 1536, "\xd8\x72\x9d\xb4\x18\x82\x25\x9b\xee\x4f\x82\x53\x25\xf5\xa1\x30" }, + { 2032, "\x1e\xb1\x4a\x0c\x13\xb3\xbf\x47\xfa\x2a\x0b\xa9\x3a\xd4\x5b\x8b" }, + { 2048, "\xcc\x58\x2f\x8b\xa9\xf2\x65\xe2\xb1\xbe\x91\x12\xe9\x75\xd2\xd7" }, + { 3056, "\xf2\xe3\x0f\x9b\xd1\x02\xec\xbf\x75\xaa\xad\xe9\xbc\x35\xc4\x3c" }, + { 3072, "\xec\x0e\x11\xc4\x79\xdc\x32\x9d\xc8\xda\x79\x68\xfe\x96\x56\x81" }, + { 4080, "\x06\x83\x26\xa2\x11\x84\x16\xd2\x1f\x9d\x04\xb2\xcd\x1c\xa0\x50" }, + { 4096, "\xff\x25\xb5\x89\x95\x99\x67\x07\xe5\x1f\xbd\xf0\x8b\x34\xd8\x75" } + } + }, + { + "\x01\x02\x03\x04\x05\x06\x07", 7, + { + { 0, "\x29\x3f\x02\xd4\x7f\x37\xc9\xb6\x33\xf2\xaf\x52\x85\xfe\xb4\x6b" }, + { 16, "\xe6\x20\xf1\x39\x0d\x19\xbd\x84\xe2\xe0\xfd\x75\x20\x31\xaf\xc1" }, + { 240, "\x91\x4f\x02\x53\x1c\x92\x18\x81\x0d\xf6\x0f\x67\xe3\x38\x15\x4c" }, + { 256, "\xd0\xfd\xb5\x83\x07\x3c\xe8\x5a\xb8\x39\x17\x74\x0e\xc0\x11\xd5" }, + { 496, "\x75\xf8\x14\x11\xe8\x71\xcf\xfa\x70\xb9\x0c\x74\xc5\x92\xe4\x54" }, + { 512, "\x0b\xb8\x72\x02\x93\x8d\xad\x60\x9e\x87\xa5\xa1\xb0\x79\xe5\xe4" }, + { 752, "\xc2\x91\x12\x46\xb6\x12\xe7\xe7\xb9\x03\xdf\xed\xa1\xda\xd8\x66" }, + { 768, "\x32\x82\x8f\x91\x50\x2b\x62\x91\x36\x8d\xe8\x08\x1d\xe3\x6f\xc2" }, + { 1008, "\xf3\xb9\xa7\xe3\xb2\x97\xbf\x9a\xd8\x04\x51\x2f\x90\x63\xef\xf1" }, + { 1024, "\x8e\xcb\x67\xa9\xba\x1f\x55\xa5\xa0\x67\xe2\xb0\x26\xa3\x67\x6f" }, + { 1520, "\xd2\xaa\x90\x2b\xd4\x2d\x0d\x7c\xfd\x34\x0c\xd4\x58\x10\x52\x9f" }, + { 1536, "\x78\xb2\x72\xc9\x6e\x42\xea\xb4\xc6\x0b\xd9\x14\xe3\x9d\x06\xe3" }, + { 2032, "\xf4\x33\x2f\xd3\x1a\x07\x93\x96\xee\x3c\xee\x3f\x2a\x4f\xf0\x49" }, + { 2048, "\x05\x45\x97\x81\xd4\x1f\xda\x7f\x30\xc1\xbe\x7e\x12\x46\xc6\x23" }, + { 3056, "\xad\xfd\x38\x68\xb8\xe5\x14\x85\xd5\xe6\x10\x01\x7e\x3d\xd6\x09" }, + { 3072, "\xad\x26\x58\x1c\x0c\x5b\xe4\x5f\x4c\xea\x01\xdb\x2f\x38\x05\xd5" }, + { 4080, "\xf3\x17\x2c\xef\xfc\x3b\x3d\x99\x7c\x85\xcc\xd5\xaf\x1a\x95\x0c" }, + { 4096, "\xe7\x4b\x0b\x97\x31\x22\x7f\xd3\x7c\x0e\xc0\x8a\x47\xdd\xd8\xb8" } + } + }, + { + "\x01\x02\x03\x04\x05\x06\x07\x08", 8, + { + { 0, "\x97\xab\x8a\x1b\xf0\xaf\xb9\x61\x32\xf2\xf6\x72\x58\xda\x15\xa8" }, + { 16, "\x82\x63\xef\xdb\x45\xc4\xa1\x86\x84\xef\x87\xe6\xb1\x9e\x5b\x09" }, + { 240, "\x96\x36\xeb\xc9\x84\x19\x26\xf4\xf7\xd1\xf3\x62\xbd\xdf\x6e\x18" }, + { 256, "\xd0\xa9\x90\xff\x2c\x05\xfe\xf5\xb9\x03\x73\xc9\xff\x4b\x87\x0a" }, + { 496, "\x73\x23\x9f\x1d\xb7\xf4\x1d\x80\xb6\x43\xc0\xc5\x25\x18\xec\x63" }, + { 512, "\x16\x3b\x31\x99\x23\xa6\xbd\xb4\x52\x7c\x62\x61\x26\x70\x3c\x0f" }, + { 752, "\x49\xd6\xc8\xaf\x0f\x97\x14\x4a\x87\xdf\x21\xd9\x14\x72\xf9\x66" }, + { 768, "\x44\x17\x3a\x10\x3b\x66\x16\xc5\xd5\xad\x1c\xee\x40\xc8\x63\xd0" }, + { 1008, "\x27\x3c\x9c\x4b\x27\xf3\x22\xe4\xe7\x16\xef\x53\xa4\x7d\xe7\xa4" }, + { 1024, "\xc6\xd0\xe7\xb2\x26\x25\x9f\xa9\x02\x34\x90\xb2\x61\x67\xad\x1d" }, + { 1520, "\x1f\xe8\x98\x67\x13\xf0\x7c\x3d\x9a\xe1\xc1\x63\xff\x8c\xf9\xd3" }, + { 1536, "\x83\x69\xe1\xa9\x65\x61\x0b\xe8\x87\xfb\xd0\xc7\x91\x62\xaa\xfb" }, + { 2032, "\x0a\x01\x27\xab\xb4\x44\x84\xb9\xfb\xef\x5a\xbc\xae\x1b\x57\x9f" }, + { 2048, "\xc2\xcd\xad\xc6\x40\x2e\x8e\xe8\x66\xe1\xf3\x7b\xdb\x47\xe4\x2c" }, + { 3056, "\x26\xb5\x1e\xa3\x7d\xf8\xe1\xd6\xf7\x6f\xc3\xb6\x6a\x74\x29\xb3" }, + { 3072, "\xbc\x76\x83\x20\x5d\x4f\x44\x3d\xc1\xf2\x9d\xda\x33\x15\xc8\x7b" }, + { 4080, "\xd5\xfa\x5a\x34\x69\xd2\x9a\xaa\xf8\x3d\x23\x58\x9d\xb8\xc8\x5b" }, + { 4096, "\x3f\xb4\x6e\x2c\x8f\x0f\x06\x8e\xdc\xe8\xcd\xcd\x7d\xfc\x58\x62" } + } + }, + { + "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a", 10, + { + { 0, "\xed\xe3\xb0\x46\x43\xe5\x86\xcc\x90\x7d\xc2\x18\x51\x70\x99\x02" }, + { 16, "\x03\x51\x6b\xa7\x8f\x41\x3b\xeb\x22\x3a\xa5\xd4\xd2\xdf\x67\x11" }, + { 240, "\x3c\xfd\x6c\xb5\x8e\xe0\xfd\xde\x64\x01\x76\xad\x00\x00\x04\x4d" }, + { 256, "\x48\x53\x2b\x21\xfb\x60\x79\xc9\x11\x4c\x0f\xfd\x9c\x04\xa1\xad" }, + { 496, "\x3e\x8c\xea\x98\x01\x71\x09\x97\x90\x84\xb1\xef\x92\xf9\x9d\x86" }, + { 512, "\xe2\x0f\xb4\x9b\xdb\x33\x7e\xe4\x8b\x8d\x8d\xc0\xf4\xaf\xef\xfe" }, + { 752, "\x5c\x25\x21\xea\xcd\x79\x66\xf1\x5e\x05\x65\x44\xbe\xa0\xd3\x15" }, + { 768, "\xe0\x67\xa7\x03\x19\x31\xa2\x46\xa6\xc3\x87\x5d\x2f\x67\x8a\xcb" }, + { 1008, "\xa6\x4f\x70\xaf\x88\xae\x56\xb6\xf8\x75\x81\xc0\xe2\x3e\x6b\x08" }, + { 1024, "\xf4\x49\x03\x1d\xe3\x12\x81\x4e\xc6\xf3\x19\x29\x1f\x4a\x05\x16" }, + { 1520, "\xbd\xae\x85\x92\x4b\x3c\xb1\xd0\xa2\xe3\x3a\x30\xc6\xd7\x95\x99" }, + { 1536, "\x8a\x0f\xed\xdb\xac\x86\x5a\x09\xbc\xd1\x27\xfb\x56\x2e\xd6\x0a" }, + { 2032, "\xb5\x5a\x0a\x5b\x51\xa1\x2a\x8b\xe3\x48\x99\xc3\xe0\x47\x51\x1a" }, + { 2048, "\xd9\xa0\x9c\xea\x3c\xe7\x5f\xe3\x96\x98\x07\x03\x17\xa7\x13\x39" }, + { 3056, "\x55\x22\x25\xed\x11\x77\xf4\x45\x84\xac\x8c\xfa\x6c\x4e\xb5\xfc" }, + { 3072, "\x7e\x82\xcb\xab\xfc\x95\x38\x1b\x08\x09\x98\x44\x21\x29\xc2\xf8" }, + { 4080, "\x1f\x13\x5e\xd1\x4c\xe6\x0a\x91\x36\x9d\x23\x22\xbe\xf2\x5e\x3c" }, + { 4096, "\x08\xb6\xbe\x45\x12\x4a\x43\xe2\xeb\x77\x95\x3f\x84\xdc\x85\x53" } + } + }, + { + "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10", 16, + { + { 0, "\x9a\xc7\xcc\x9a\x60\x9d\x1e\xf7\xb2\x93\x28\x99\xcd\xe4\x1b\x97" }, + { 16, "\x52\x48\xc4\x95\x90\x14\x12\x6a\x6e\x8a\x84\xf1\x1d\x1a\x9e\x1c" }, + { 240, "\x06\x59\x02\xe4\xb6\x20\xf6\xcc\x36\xc8\x58\x9f\x66\x43\x2f\x2b" }, + { 256, "\xd3\x9d\x56\x6b\xc6\xbc\xe3\x01\x07\x68\x15\x15\x49\xf3\x87\x3f" }, + { 496, "\xb6\xd1\xe6\xc4\xa5\xe4\x77\x1c\xad\x79\x53\x8d\xf2\x95\xfb\x11" }, + { 512, "\xc6\x8c\x1d\x5c\x55\x9a\x97\x41\x23\xdf\x1d\xbc\x52\xa4\x3b\x89" }, + { 752, "\xc5\xec\xf8\x8d\xe8\x97\xfd\x57\xfe\xd3\x01\x70\x1b\x82\xa2\x59" }, + { 768, "\xec\xcb\xe1\x3d\xe1\xfc\xc9\x1c\x11\xa0\xb2\x6c\x0b\xc8\xfa\x4d" }, + { 1008, "\xe7\xa7\x25\x74\xf8\x78\x2a\xe2\x6a\xab\xcf\x9e\xbc\xd6\x60\x65" }, + { 1024, "\xbd\xf0\x32\x4e\x60\x83\xdc\xc6\xd3\xce\xdd\x3c\xa8\xc5\x3c\x16" }, + { 1520, "\xb4\x01\x10\xc4\x19\x0b\x56\x22\xa9\x61\x16\xb0\x01\x7e\xd2\x97" }, + { 1536, "\xff\xa0\xb5\x14\x64\x7e\xc0\x4f\x63\x06\xb8\x92\xae\x66\x11\x81" }, + { 2032, "\xd0\x3d\x1b\xc0\x3c\xd3\x3d\x70\xdf\xf9\xfa\x5d\x71\x96\x3e\xbd" }, + { 2048, "\x8a\x44\x12\x64\x11\xea\xa7\x8b\xd5\x1e\x8d\x87\xa8\x87\x9b\xf5" }, + { 3056, "\xfa\xbe\xb7\x60\x28\xad\xe2\xd0\xe4\x87\x22\xe4\x6c\x46\x15\xa3" }, + { 3072, "\xc0\x5d\x88\xab\xd5\x03\x57\xf9\x35\xa6\x3c\x59\xee\x53\x76\x23" }, + { 4080, "\xff\x38\x26\x5c\x16\x42\xc1\xab\xe8\xd3\xc2\xfe\x5e\x57\x2b\xf8" }, + { 4096, "\xa3\x6a\x4c\x30\x1a\xe8\xac\x13\x61\x0c\xcb\xc1\x22\x56\xca\xcc" } + } + }, + { + "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18", 24, + { + { 0, "\x05\x95\xe5\x7f\xe5\xf0\xbb\x3c\x70\x6e\xda\xc8\xa4\xb2\xdb\x11" }, + { 16, "\xdf\xde\x31\x34\x4a\x1a\xf7\x69\xc7\x4f\x07\x0a\xee\x9e\x23\x26" }, + { 240, "\xb0\x6b\x9b\x1e\x19\x5d\x13\xd8\xf4\xa7\x99\x5c\x45\x53\xac\x05" }, + { 256, "\x6b\xd2\x37\x8e\xc3\x41\xc9\xa4\x2f\x37\xba\x79\xf8\x8a\x32\xff" }, + { 496, "\xe7\x0b\xce\x1d\xf7\x64\x5a\xdb\x5d\x2c\x41\x30\x21\x5c\x35\x22" }, + { 512, "\x9a\x57\x30\xc7\xfc\xb4\xc9\xaf\x51\xff\xda\x89\xc7\xf1\xad\x22" }, + { 752, "\x04\x85\x05\x5f\xd4\xf6\xf0\xd9\x63\xef\x5a\xb9\xa5\x47\x69\x82" }, + { 768, "\x59\x1f\xc6\x6b\xcd\xa1\x0e\x45\x2b\x03\xd4\x55\x1f\x6b\x62\xac" }, + { 1008, "\x27\x53\xcc\x83\x98\x8a\xfa\x3e\x16\x88\xa1\xd3\xb4\x2c\x9a\x02" }, + { 1024, "\x93\x61\x0d\x52\x3d\x1d\x3f\x00\x62\xb3\xc2\xa3\xbb\xc7\xc7\xf0" }, + { 1520, "\x96\xc2\x48\x61\x0a\xad\xed\xfe\xaf\x89\x78\xc0\x3d\xe8\x20\x5a" }, + { 1536, "\x0e\x31\x7b\x3d\x1c\x73\xb9\xe9\xa4\x68\x8f\x29\x6d\x13\x3a\x19" }, + { 2032, "\xbd\xf0\xe6\xc3\xcc\xa5\xb5\xb9\xd5\x33\xb6\x9c\x56\xad\xa1\x20" }, + { 2048, "\x88\xa2\x18\xb6\xe2\xec\xe1\xe6\x24\x6d\x44\xc7\x59\xd1\x9b\x10" }, + { 3056, "\x68\x66\x39\x7e\x95\xc1\x40\x53\x4f\x94\x26\x34\x21\x00\x6e\x40" }, + { 3072, "\x32\xcb\x0a\x1e\x95\x42\xc6\xb3\xb8\xb3\x98\xab\xc3\xb0\xf1\xd5" }, + { 4080, "\x29\xa0\xb8\xae\xd5\x4a\x13\x23\x24\xc6\x2e\x42\x3f\x54\xb4\xc8" }, + { 4096, "\x3c\xb0\xf3\xb5\x02\x0a\x98\xb8\x2a\xf9\xfe\x15\x44\x84\xa1\x68" } + } + }, + { + "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x20", 32, + { + { 0, "\xea\xa6\xbd\x25\x88\x0b\xf9\x3d\x3f\x5d\x1e\x4c\xa2\x61\x1d\x91" }, + { 16, "\xcf\xa4\x5c\x9f\x7e\x71\x4b\x54\xbd\xfa\x80\x02\x7c\xb1\x43\x80" }, + { 240, "\x11\x4a\xe3\x44\xde\xd7\x1b\x35\xf2\xe6\x0f\xeb\xad\x72\x7f\xd8" }, + { 256, "\x02\xe1\xe7\x05\x6b\x0f\x62\x39\x00\x49\x64\x22\x94\x3e\x97\xb6" }, + { 496, "\x91\xcb\x93\xc7\x87\x96\x4e\x10\xd9\x52\x7d\x99\x9c\x6f\x93\x6b" }, + { 512, "\x49\xb1\x8b\x42\xf8\xe8\x36\x7c\xbe\xb5\xef\x10\x4b\xa1\xc7\xcd" }, + { 752, "\x87\x08\x4b\x3b\xa7\x00\xba\xde\x95\x56\x10\x67\x27\x45\xb3\x74" }, + { 768, "\xe7\xa7\xb9\xe9\xec\x54\x0d\x5f\xf4\x3b\xdb\x12\x79\x2d\x1b\x35" }, + { 1008, "\xc7\x99\xb5\x96\x73\x8f\x6b\x01\x8c\x76\xc7\x4b\x17\x59\xbd\x90" }, + { 1024, "\x7f\xec\x5b\xfd\x9f\x9b\x89\xce\x65\x48\x30\x90\x92\xd7\xe9\x58" }, + { 1520, "\x40\xf2\x50\xb2\x6d\x1f\x09\x6a\x4a\xfd\x4c\x34\x0a\x58\x88\x15" }, + { 1536, "\x3e\x34\x13\x5c\x79\xdb\x01\x02\x00\x76\x76\x51\xcf\x26\x30\x73" }, + { 2032, "\xf6\x56\xab\xcc\xf8\x8d\xd8\x27\x02\x7b\x2c\xe9\x17\xd4\x64\xec" }, + { 2048, "\x18\xb6\x25\x03\xbf\xbc\x07\x7f\xba\xbb\x98\xf2\x0d\x98\xab\x34" }, + { 3056, "\x8a\xed\x95\xee\x5b\x0d\xcb\xfb\xef\x4e\xb2\x1d\x3a\x3f\x52\xf9" }, + { 3072, "\x62\x5a\x1a\xb0\x0e\xe3\x9a\x53\x27\x34\x6b\xdd\xb0\x1a\x9c\x18" }, + { 4080, "\xa1\x3a\x7c\x79\xc7\xe1\x19\xb5\xab\x02\x96\xab\x28\xc3\x00\xb9" }, + { 4096, "\xf3\xe4\xc0\xa2\xe0\x2d\x1d\x01\xf7\xf0\xa7\x46\x18\xaf\x2b\x48" } + } + }, + { + "\x83\x32\x22\x77\x2a", 5, + { + { 0, "\x80\xad\x97\xbd\xc9\x73\xdf\x8a\x2e\x87\x9e\x92\xa4\x97\xef\xda" }, + { 16, "\x20\xf0\x60\xc2\xf2\xe5\x12\x65\x01\xd3\xd4\xfe\xa1\x0d\x5f\xc0" }, + { 240, "\xfa\xa1\x48\xe9\x90\x46\x18\x1f\xec\x6b\x20\x85\xf3\xb2\x0e\xd9" }, + { 256, "\xf0\xda\xf5\xba\xb3\xd5\x96\x83\x98\x57\x84\x6f\x73\xfb\xfe\x5a" }, + { 496, "\x1c\x7e\x2f\xc4\x63\x92\x32\xfe\x29\x75\x84\xb2\x96\x99\x6b\xc8" }, + { 512, "\x3d\xb9\xb2\x49\x40\x6c\xc8\xed\xff\xac\x55\xcc\xd3\x22\xba\x12" }, + { 752, "\xe4\xf9\xf7\xe0\x06\x61\x54\xbb\xd1\x25\xb7\x45\x56\x9b\xc8\x97" }, + { 768, "\x75\xd5\xef\x26\x2b\x44\xc4\x1a\x9c\xf6\x3a\xe1\x45\x68\xe1\xb9" }, + { 1008, "\x6d\xa4\x53\xdb\xf8\x1e\x82\x33\x4a\x3d\x88\x66\xcb\x50\xa1\xe3" }, + { 1024, "\x78\x28\xd0\x74\x11\x9c\xab\x5c\x22\xb2\x94\xd7\xa9\xbf\xa0\xbb" }, + { 1520, "\xad\xb8\x9c\xea\x9a\x15\xfb\xe6\x17\x29\x5b\xd0\x4b\x8c\xa0\x5c" }, + { 1536, "\x62\x51\xd8\x7f\xd4\xaa\xae\x9a\x7e\x4a\xd5\xc2\x17\xd3\xf3\x00" }, + { 2032, "\xe7\x11\x9b\xd6\xdd\x9b\x22\xaf\xe8\xf8\x95\x85\x43\x28\x81\xe2" }, + { 2048, "\x78\x5b\x60\xfd\x7e\xc4\xe9\xfc\xb6\x54\x5f\x35\x0d\x66\x0f\xab" }, + { 3056, "\xaf\xec\xc0\x37\xfd\xb7\xb0\x83\x8e\xb3\xd7\x0b\xcd\x26\x83\x82" }, + { 3072, "\xdb\xc1\xa7\xb4\x9d\x57\x35\x8c\xc9\xfa\x6d\x61\xd7\x3b\x7c\xf0" }, + { 4080, "\x63\x49\xd1\x26\xa3\x7a\xfc\xba\x89\x79\x4f\x98\x04\x91\x4f\xdc" }, + { 4096, "\xbf\x42\xc3\x01\x8c\x2f\x7c\x66\xbf\xde\x52\x49\x75\x76\x81\x15" } + } + }, + { + "\x19\x10\x83\x32\x22\x77\x2a", 7, + { + { 0, "\xbc\x92\x22\xdb\xd3\x27\x4d\x8f\xc6\x6d\x14\xcc\xbd\xa6\x69\x0b" }, + { 16, "\x7a\xe6\x27\x41\x0c\x9a\x2b\xe6\x93\xdf\x5b\xb7\x48\x5a\x63\xe3" }, + { 240, "\x3f\x09\x31\xaa\x03\xde\xfb\x30\x0f\x06\x01\x03\x82\x6f\x2a\x64" }, + { 256, "\xbe\xaa\x9e\xc8\xd5\x9b\xb6\x81\x29\xf3\x02\x7c\x96\x36\x11\x81" }, + { 496, "\x74\xe0\x4d\xb4\x6d\x28\x64\x8d\x7d\xee\x8a\x00\x64\xb0\x6c\xfe" }, + { 512, "\x9b\x5e\x81\xc6\x2f\xe0\x23\xc5\x5b\xe4\x2f\x87\xbb\xf9\x32\xb8" }, + { 752, "\xce\x17\x8f\xc1\x82\x6e\xfe\xcb\xc1\x82\xf5\x79\x99\xa4\x61\x40" }, + { 768, "\x8b\xdf\x55\xcd\x55\x06\x1c\x06\xdb\xa6\xbe\x11\xde\x4a\x57\x8a" }, + { 1008, "\x62\x6f\x5f\x4d\xce\x65\x25\x01\xf3\x08\x7d\x39\xc9\x2c\xc3\x49" }, + { 1024, "\x42\xda\xac\x6a\x8f\x9a\xb9\xa7\xfd\x13\x7c\x60\x37\x82\x56\x82" }, + { 1520, "\xcc\x03\xfd\xb7\x91\x92\xa2\x07\x31\x2f\x53\xf5\xd4\xdc\x33\xd9" }, + { 1536, "\xf7\x0f\x14\x12\x2a\x1c\x98\xa3\x15\x5d\x28\xb8\xa0\xa8\xa4\x1d" }, + { 2032, "\x2a\x3a\x30\x7a\xb2\x70\x8a\x9c\x00\xfe\x0b\x42\xf9\xc2\xd6\xa1" }, + { 2048, "\x86\x26\x17\x62\x7d\x22\x61\xea\xb0\xb1\x24\x65\x97\xca\x0a\xe9" }, + { 3056, "\x55\xf8\x77\xce\x4f\x2e\x1d\xdb\xbf\x8e\x13\xe2\xcd\xe0\xfd\xc8" }, + { 3072, "\x1b\x15\x56\xcb\x93\x5f\x17\x33\x37\x70\x5f\xbb\x5d\x50\x1f\xc1" }, + { 4080, "\xec\xd0\xe9\x66\x02\xbe\x7f\x8d\x50\x92\x81\x6c\xcc\xf2\xc2\xe9" }, + { 4096, "\x02\x78\x81\xfa\xb4\x99\x3a\x1c\x26\x20\x24\xa9\x4f\xff\x3f\x61" } + } + }, + { + "\x64\x19\x10\x83\x32\x22\x77\x2a", 8, + { + { 0, "\xbb\xf6\x09\xde\x94\x13\x17\x2d\x07\x66\x0c\xb6\x80\x71\x69\x26" }, + { 16, "\x46\x10\x1a\x6d\xab\x43\x11\x5d\x6c\x52\x2b\x4f\xe9\x36\x04\xa9" }, + { 240, "\xcb\xe1\xff\xf2\x1c\x96\xf3\xee\xf6\x1e\x8f\xe0\x54\x2c\xbd\xf0" }, + { 256, "\x34\x79\x38\xbf\xfa\x40\x09\xc5\x12\xcf\xb4\x03\x4b\x0d\xd1\xa7" }, + { 496, "\x78\x67\xa7\x86\xd0\x0a\x71\x47\x90\x4d\x76\xdd\xf1\xe5\x20\xe3" }, + { 512, "\x8d\x3e\x9e\x1c\xae\xfc\xcc\xb3\xfb\xf8\xd1\x8f\x64\x12\x0b\x32" }, + { 752, "\x94\x23\x37\xf8\xfd\x76\xf0\xfa\xe8\xc5\x2d\x79\x54\x81\x06\x72" }, + { 768, "\xb8\x54\x8c\x10\xf5\x16\x67\xf6\xe6\x0e\x18\x2f\xa1\x9b\x30\xf7" }, + { 1008, "\x02\x11\xc7\xc6\x19\x0c\x9e\xfd\x12\x37\xc3\x4c\x8f\x2e\x06\xc4" }, + { 1024, "\xbd\xa6\x4f\x65\x27\x6d\x2a\xac\xb8\xf9\x02\x12\x20\x3a\x80\x8e" }, + { 1520, "\xbd\x38\x20\xf7\x32\xff\xb5\x3e\xc1\x93\xe7\x9d\x33\xe2\x7c\x73" }, + { 1536, "\xd0\x16\x86\x16\x86\x19\x07\xd4\x82\xe3\x6c\xda\xc8\xcf\x57\x49" }, + { 2032, "\x97\xb0\xf0\xf2\x24\xb2\xd2\x31\x71\x14\x80\x8f\xb0\x3a\xf7\xa0" }, + { 2048, "\xe5\x96\x16\xe4\x69\x78\x79\x39\xa0\x63\xce\xea\x9a\xf9\x56\xd1" }, + { 3056, "\xc4\x7e\x0d\xc1\x66\x09\x19\xc1\x11\x01\x20\x8f\x9e\x69\xaa\x1f" }, + { 3072, "\x5a\xe4\xf1\x28\x96\xb8\x37\x9a\x2a\xad\x89\xb5\xb5\x53\xd6\xb0" }, + { 4080, "\x6b\x6b\x09\x8d\x0c\x29\x3b\xc2\x99\x3d\x80\xbf\x05\x18\xb6\xd9" }, + { 4096, "\x81\x70\xcc\x3c\xcd\x92\xa6\x98\x62\x1b\x93\x9d\xd3\x8f\xe7\xb9" } + } + }, + { + "\x8b\x37\x64\x19\x10\x83\x32\x22\x77\x2a", 10, + { + { 0, "\xab\x65\xc2\x6e\xdd\xb2\x87\x60\x0d\xb2\xfd\xa1\x0d\x1e\x60\x5c" }, + { 16, "\xbb\x75\x90\x10\xc2\x96\x58\xf2\xc7\x2d\x93\xa2\xd1\x6d\x29\x30" }, + { 240, "\xb9\x01\xe8\x03\x6e\xd1\xc3\x83\xcd\x3c\x4c\x4d\xd0\xa6\xab\x05" }, + { 256, "\x3d\x25\xce\x49\x22\x92\x4c\x55\xf0\x64\x94\x33\x53\xd7\x8a\x6c" }, + { 496, "\x12\xc1\xaa\x44\xbb\xf8\x7e\x75\xe6\x11\xf6\x9b\x2c\x38\xf4\x9b" }, + { 512, "\x28\xf2\xb3\x43\x4b\x65\xc0\x98\x77\x47\x00\x44\xc6\xea\x17\x0d" }, + { 752, "\xbd\x9e\xf8\x22\xde\x52\x88\x19\x61\x34\xcf\x8a\xf7\x83\x93\x04" }, + { 768, "\x67\x55\x9c\x23\xf0\x52\x15\x84\x70\xa2\x96\xf7\x25\x73\x5a\x32" }, + { 1008, "\x8b\xab\x26\xfb\xc2\xc1\x2b\x0f\x13\xe2\xab\x18\x5e\xab\xf2\x41" }, + { 1024, "\x31\x18\x5a\x6d\x69\x6f\x0c\xfa\x9b\x42\x80\x8b\x38\xe1\x32\xa2" }, + { 1520, "\x56\x4d\x3d\xae\x18\x3c\x52\x34\xc8\xaf\x1e\x51\x06\x1c\x44\xb5" }, + { 1536, "\x3c\x07\x78\xa7\xb5\xf7\x2d\x3c\x23\xa3\x13\x5c\x7d\x67\xb9\xf4" }, + { 2032, "\xf3\x43\x69\x89\x0f\xcf\x16\xfb\x51\x7d\xca\xae\x44\x63\xb2\xdd" }, + { 2048, "\x02\xf3\x1c\x81\xe8\x20\x07\x31\xb8\x99\xb0\x28\xe7\x91\xbf\xa7" }, + { 3056, "\x72\xda\x64\x62\x83\x22\x8c\x14\x30\x08\x53\x70\x17\x95\x61\x6f" }, + { 3072, "\x4e\x0a\x8c\x6f\x79\x34\xa7\x88\xe2\x26\x5e\x81\xd6\xd0\xc8\xf4" }, + { 4080, "\x43\x8d\xd5\xea\xfe\xa0\x11\x1b\x6f\x36\xb4\xb9\x38\xda\x2a\x68" }, + { 4096, "\x5f\x6b\xfc\x73\x81\x58\x74\xd9\x71\x00\xf0\x86\x97\x93\x57\xd8" } + } + }, + { + "\xeb\xb4\x62\x27\xc6\xcc\x8b\x37\x64\x19\x10\x83\x32\x22\x77\x2a", 16, + { + { 0, "\x72\x0c\x94\xb6\x3e\xdf\x44\xe1\x31\xd9\x50\xca\x21\x1a\x5a\x30" }, + { 16, "\xc3\x66\xfd\xea\xcf\x9c\xa8\x04\x36\xbe\x7c\x35\x84\x24\xd2\x0b" }, + { 240, "\xb3\x39\x4a\x40\xaa\xbf\x75\xcb\xa4\x22\x82\xef\x25\xa0\x05\x9f" }, + { 256, "\x48\x47\xd8\x1d\xa4\x94\x2d\xbc\x24\x9d\xef\xc4\x8c\x92\x2b\x9f" }, + { 496, "\x08\x12\x8c\x46\x9f\x27\x53\x42\xad\xda\x20\x2b\x2b\x58\xda\x95" }, + { 512, "\x97\x0d\xac\xef\x40\xad\x98\x72\x3b\xac\x5d\x69\x55\xb8\x17\x61" }, + { 752, "\x3c\xb8\x99\x93\xb0\x7b\x0c\xed\x93\xde\x13\xd2\xa1\x10\x13\xac" }, + { 768, "\xef\x2d\x67\x6f\x15\x45\xc2\xc1\x3d\xc6\x80\xa0\x2f\x4a\xdb\xfe" }, + { 1008, "\xb6\x05\x95\x51\x4f\x24\xbc\x9f\xe5\x22\xa6\xca\xd7\x39\x36\x44" }, + { 1024, "\xb5\x15\xa8\xc5\x01\x17\x54\xf5\x90\x03\x05\x8b\xdb\x81\x51\x4e" }, + { 1520, "\x3c\x70\x04\x7e\x8c\xbc\x03\x8e\x3b\x98\x20\xdb\x60\x1d\xa4\x95" }, + { 1536, "\x11\x75\xda\x6e\xe7\x56\xde\x46\xa5\x3e\x2b\x07\x56\x60\xb7\x70" }, + { 2032, "\x00\xa5\x42\xbb\xa0\x21\x11\xcc\x2c\x65\xb3\x8e\xbd\xba\x58\x7e" }, + { 2048, "\x58\x65\xfd\xbb\x5b\x48\x06\x41\x04\xe8\x30\xb3\x80\xf2\xae\xde" }, + { 3056, "\x34\xb2\x1a\xd2\xad\x44\xe9\x99\xdb\x2d\x7f\x08\x63\xf0\xd9\xb6" }, + { 3072, "\x84\xa9\x21\x8f\xc3\x6e\x8a\x5f\x2c\xcf\xbe\xae\x53\xa2\x7d\x25" }, + { 4080, "\xa2\x22\x1a\x11\xb8\x33\xcc\xb4\x98\xa5\x95\x40\xf0\x54\x5f\x4a" }, + { 4096, "\x5b\xbe\xb4\x78\x7d\x59\xe5\x37\x3f\xdb\xea\x6c\x6f\x75\xc2\x9b" } + } + }, + { + "\xc1\x09\x16\x39\x08\xeb\xe5\x1d\xeb\xb4\x62\x27\xc6\xcc\x8b\x37\x64\x19\x10\x83\x32\x22\x77\x2a", 24, + { + { 0, "\x54\xb6\x4e\x6b\x5a\x20\xb5\xe2\xec\x84\x59\x3d\xc7\x98\x9d\xa7" }, + { 16, "\xc1\x35\xee\xe2\x37\xa8\x54\x65\xff\x97\xdc\x03\x92\x4f\x45\xce" }, + { 240, "\xcf\xcc\x92\x2f\xb4\xa1\x4a\xb4\x5d\x61\x75\xaa\xbb\xf2\xd2\x01" }, + { 256, "\x83\x7b\x87\xe2\xa4\x46\xad\x0e\xf7\x98\xac\xd0\x2b\x94\x12\x4f" }, + { 496, "\x17\xa6\xdb\xd6\x64\x92\x6a\x06\x36\xb3\xf4\xc3\x7a\x4f\x46\x94" }, + { 512, "\x4a\x5f\x9f\x26\xae\xee\xd4\xd4\xa2\x5f\x63\x2d\x30\x52\x33\xd9" }, + { 752, "\x80\xa3\xd0\x1e\xf0\x0c\x8e\x9a\x42\x09\xc1\x7f\x4e\xeb\x35\x8c" }, + { 768, "\xd1\x5e\x7d\x5f\xfa\xaa\xbc\x02\x07\xbf\x20\x0a\x11\x77\x93\xa2" }, + { 1008, "\x34\x96\x82\xbf\x58\x8e\xaa\x52\xd0\xaa\x15\x60\x34\x6a\xea\xfa" }, + { 1024, "\xf5\x85\x4c\xdb\x76\xc8\x89\xe3\xad\x63\x35\x4e\x5f\x72\x75\xe3" }, + { 1520, "\x53\x2c\x7c\xec\xcb\x39\xdf\x32\x36\x31\x84\x05\xa4\xb1\x27\x9c" }, + { 1536, "\xba\xef\xe6\xd9\xce\xb6\x51\x84\x22\x60\xe0\xd1\xe0\x5e\x3b\x90" }, + { 2032, "\xe8\x2d\x8c\x6d\xb5\x4e\x3c\x63\x3f\x58\x1c\x95\x2b\xa0\x42\x07" }, + { 2048, "\x4b\x16\xe5\x0a\xbd\x38\x1b\xd7\x09\x00\xa9\xcd\x9a\x62\xcb\x23" }, + { 3056, "\x36\x82\xee\x33\xbd\x14\x8b\xd9\xf5\x86\x56\xcd\x8f\x30\xd9\xfb" }, + { 3072, "\x1e\x5a\x0b\x84\x75\x04\x5d\x9b\x20\xb2\x62\x86\x24\xed\xfd\x9e" }, + { 4080, "\x63\xed\xd6\x84\xfb\x82\x62\x82\xfe\x52\x8f\x9c\x0e\x92\x37\xbc" }, + { 4096, "\xe4\xdd\x2e\x98\xd6\x96\x0f\xae\x0b\x43\x54\x54\x56\x74\x33\x91" } + } + }, + { + "\x1a\xda\x31\xd5\xcf\x68\x82\x21\xc1\x09\x16\x39\x08\xeb\xe5\x1d\xeb\xb4\x62\x27\xc6\xcc\x8b\x37\x64\x19\x10\x83\x32\x22\x77\x2a", 32, + { + { 0, "\xdd\x5b\xcb\x00\x18\xe9\x22\xd4\x94\x75\x9d\x7c\x39\x5d\x02\xd3" }, + { 16, "\xc8\x44\x6f\x8f\x77\xab\xf7\x37\x68\x53\x53\xeb\x89\xa1\xc9\xeb" }, + { 240, "\xaf\x3e\x30\xf9\xc0\x95\x04\x59\x38\x15\x15\x75\xc3\xfb\x90\x98" }, + { 256, "\xf8\xcb\x62\x74\xdb\x99\xb8\x0b\x1d\x20\x12\xa9\x8e\xd4\x8f\x0e" }, + { 496, "\x25\xc3\x00\x5a\x1c\xb8\x5d\xe0\x76\x25\x98\x39\xab\x71\x98\xab" }, + { 512, "\x9d\xcb\xc1\x83\xe8\xcb\x99\x4b\x72\x7b\x75\xbe\x31\x80\x76\x9c" }, + { 752, "\xa1\xd3\x07\x8d\xfa\x91\x69\x50\x3e\xd9\xd4\x49\x1d\xee\x4e\xb2" }, + { 768, "\x85\x14\xa5\x49\x58\x58\x09\x6f\x59\x6e\x4b\xcd\x66\xb1\x06\x65" }, + { 1008, "\x5f\x40\xd5\x9e\xc1\xb0\x3b\x33\x73\x8e\xfa\x60\xb2\x25\x5d\x31" }, + { 1024, "\x34\x77\xc7\xf7\x64\xa4\x1b\xac\xef\xf9\x0b\xf1\x4f\x92\xb7\xcc" }, + { 1520, "\xac\x4e\x95\x36\x8d\x99\xb9\xeb\x78\xb8\xda\x8f\x81\xff\xa7\x95" }, + { 1536, "\x8c\x3c\x13\xf8\xc2\x38\x8b\xb7\x3f\x38\x57\x6e\x65\xb7\xc4\x46" }, + { 2032, "\x13\xc4\xb9\xc1\xdf\xb6\x65\x79\xed\xdd\x8a\x28\x0b\x9f\x73\x16" }, + { 2048, "\xdd\xd2\x78\x20\x55\x01\x26\x69\x8e\xfa\xad\xc6\x4b\x64\xf6\x6e" }, + { 3056, "\xf0\x8f\x2e\x66\xd2\x8e\xd1\x43\xf3\xa2\x37\xcf\x9d\xe7\x35\x59" }, + { 3072, "\x9e\xa3\x6c\x52\x55\x31\xb8\x80\xba\x12\x43\x34\xf5\x7b\x0b\x70" }, + { 4080, "\xd5\xa3\x9e\x3d\xfc\xc5\x02\x80\xba\xc4\xa6\xb5\xaa\x0d\xca\x7d" }, + { 4096, "\x37\x0b\x1c\x1f\xe6\x55\x91\x6d\x97\xfd\x0d\x47\xca\x1d\x72\xb8" } + } + } + }; + + struct rc4_ctx ctx; + + for ( size_t i = 0; i != NELEM(cases); ++i ) { + rc4_init(&ctx, cases[i].key, cases[i].sz); + + unsigned int pos = 0; + + for ( int j = 0; j != 18; ++j ) { + while ( pos != cases[i].test[j].pos ) { + rc4_get_byte(&ctx); + ++pos; + } + + unsigned char bytes[16]; + for ( unsigned int k = 0; k != 16; ++k ) { + bytes[k] = rc4_get_byte(&ctx); + ++pos; + } + + if ( memcmp(bytes, cases[i].test[j].bytes, 16) != 0 ) { + ERROR("Fehler"); + exit(EXIT_FAILURE); + } + } + + printf("Test #%zu : OK\n", i); + + rc4_clear(&ctx); + } +} + +int +main() +{ + rc4_test(); + + struct random_ctx *random = rc4_create("\x01\x02\x03\x04\x05\x06\x07", 7); + + for ( int j = 0; j != 18; ++j ) { + for ( int i = 0; i != 16; ++i ) { + printf("%02X ", random_get_byte(random)); + } + puts(""); + } + + rc4_free(random); + + return 0; +} + diff --git a/readme.md b/readme.md new file mode 100644 index 0000000..5f25333 --- /dev/null +++ b/readme.md @@ -0,0 +1,12 @@ +# Weitere Links + +- Eine Lock-Free-Queue kann man hier finden: [Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms](http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html) + Außerdem finden sich auf den Seiten noch der Link: [Nonblocking Concurrent Data Structures with Condition Synchronization](http://www.cs.rochester.edu/research/synchronization/pseudocode/duals.html) + +- Eine Implementierung einer Thread-Safe Queue ist hier zu finden: [Concurrent queue – C++11](https://juanchopanzacpp.wordpress.com/2013/02/26/concurrent-queue-c11/); + Der Author bezieht sich auf den exzelenten Code von Anthony Williams: [Implementing a Thread-Safe Queue using Condition Variables](https://www.justsoftwaresolutions.co.uk/threading/implementing-a-thread-safe-queue-using-condition-variables.html) + +- Im Embedded-Journal stellt ein Entwickler eine vernünftig aussehende Implementierung eines Ringbuffers vor: [Implementing Circular/Ring Buffer in Embedded C](https://embedjournal.com/implementing-circular-buffer-embedded-c/) + + + diff --git a/ringbuff.c b/ringbuff.c new file mode 100644 index 0000000..99dc0d8 --- /dev/null +++ b/ringbuff.c @@ -0,0 +1,72 @@ +#include +#include +#include +#include "util.h" + +typedef int T; + +struct ring_buffer { + int head, tail; + T array[8]; /* fit for your needs... */ +}; + +void +ring_init(struct ring_buffer *rb) +{ + rb->head = rb->tail = 0; +} + +bool +ring_put(struct ring_buffer *rb, T data) +{ + const int next = (rb->head + 1) % NELEM(rb->array); + + if ( next == rb->tail ) + return false; + + rb->array[rb->head] = data; + rb->head = next; + + return true; +} + +bool +ring_get(struct ring_buffer *rb, T *data) +{ + if ( rb->head == rb->tail ) + return false; + + const int next = (rb->tail + 1) % NELEM(rb->array); + + *data = rb->array[rb->tail]; + rb->tail = next; + + return true; +} + +void f() { ERROR(""); } + +int +main(void) +{ +#if 0 + struct ring_buffer rb; + ring_init(&rb); +#else + struct ring_buffer rb = { .head = 0, .tail = 0 }; +#endif + + for ( int i = 0; i != 30; ++i ) { + if ( !ring_put(&rb, i) ) + break; + } + + int j; + while ( ring_get(&rb, &j) ) { + printf("%d\n", j); + } + + return EXIT_SUCCESS; +} + + diff --git a/stack.c b/stack.c new file mode 100644 index 0000000..fa89974 --- /dev/null +++ b/stack.c @@ -0,0 +1,98 @@ +/* Standard C */ +#include +#include +#include + +/* Project */ +#include "util.h" + +typedef int T; + +struct stack_item { + struct stack_item *next; + T data; +}; + +struct stack { + struct stack_item *head; +}; + +void +stack_init(struct stack *stack) +{ + stack->head = NULL; +} + +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"); +} + +bool +stack_pop(struct stack *stack, T *data) +{ + if ( stack->head != NULL ) { + struct stack_item *next = stack->head->next; + *data = stack->head->data; + free(stack->head); + stack->head = next; + + return true; + } + else + return false; +} + +bool +stack_empty(struct stack *stack) +{ + return stack->head == NULL; +} + +void +stack_free(struct stack *stack) +{ + struct stack_item *item, *next; + + for ( item = stack->head; item; item = next ) { + next = item->next; + free(item); + } +} + +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/stack2.c b/stack2.c new file mode 100644 index 0000000..57dce4f --- /dev/null +++ b/stack2.c @@ -0,0 +1,100 @@ +#include +#include +#include + +#include "util.h" + +typedef int T; + +struct stack { + T *array; + size_t sz, p; +}; + +void +stack_init(struct stack *stack) +{ + stack->array = NULL; + stack->sz = 0; + stack->p = 0; +} + +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; +} + +bool +stack_pop(struct stack *stack, T *data) +{ + if ( stack->p != 0 ) { + *data = stack->array[--stack->p]; + return true; + } + else + return false; +} + +bool +stack_empty(struct stack *stack) +{ + return stack->p == 0; +} + +void +stack_free(struct stack *stack) +{ + free(stack->array); +} + +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/tree.c b/tree.c new file mode 100644 index 0000000..7b0bc61 --- /dev/null +++ b/tree.c @@ -0,0 +1,466 @@ +// Binary Search Tree +#include +#include +#include +#include +#include + +#include "util.h" + +typedef int T; + +struct tree_node { + struct tree_node *left, *right; + T key; + int count; /* collision counter */ + /* ggf. weitere Felder... */ +}; + +static bool tree_isBstUntil(struct tree_node *tree, int min, int max); + +bool +tree_isBst(struct tree_node *tree) +{ + return tree_isBstUntil(tree, INT_MIN, INT_MAX); +} + +bool +tree_isBstUntil(struct tree_node *tree, int min, int 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); +} + +struct tree_node * +tree_insert(struct tree_node *tree, T key) +{ + if ( tree == NULL ) { + tree = malloc(sizeof *tree); + if ( tree != NULL ) { + tree->key = key; + tree->count = 1; + tree->left = 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; +} + +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 != NULL ) + return tree_detach_min(&tree->left); + else { + *ptree = tree->right; + return tree; + } +} + +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 */ + /* TODO: 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; +} + +void +tree_clear(struct tree_node *tree) +{ + if ( tree ) { + tree_clear(tree->left); + tree_clear(tree->right); + free(tree); + } +} + +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 */ + return tree; + + return NULL; +} + +struct tree_node * +tree_minimum(struct tree_node *tree) +{ + if ( tree ) + while ( tree->left ) + tree = tree->left; + + return tree; +} + +struct tree_node * +tree_maximum(struct tree_node *tree) +{ + if ( tree ) + while ( tree->right ) + tree = tree->right; + + return tree; +} + +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; +} + +size_t +tree_count(struct tree_node *tree) +{ + if ( tree ) + return tree_count(tree->left) + tree_count(tree->right) + 1; + + return 0; +} + +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); + } +} + +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); + } +} + +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); + } +} + +/* ===== */ + +struct stack_item { + struct stack_item *next; + struct tree_node *data; +}; + +struct stack { + struct stack_item *head; +}; + +static void +stack_init(struct stack *stack) +{ + stack->head = NULL; +} + +static void +stack_push(struct stack *stack, struct tree_node *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"); +} + +static bool +stack_pop(struct stack *stack, struct tree_node **data) +{ + if ( stack->head != NULL ) { + struct stack_item *next = stack->head->next; + *data = stack->head->data; + free(stack->head); + stack->head = next; + + return true; + } + else + return false; +} + +static bool +stack_empty(struct stack *stack) +{ + return stack->head == NULL; +} + +void +stack_free(struct stack *stack) +{ + struct stack_item *item, *next; + + for ( item = stack->head; item; item = next ) { + next = item->next; + free(item); + } +} + +void +tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree != NULL ) { + struct stack stack; + + stack_init(&stack); + + stack_push(&stack, tree); + + while ( stack_pop(&stack, &tree) ) { + visit(tree->key, cl); + + if ( tree->right != NULL ) stack_push(&stack, tree->right); + if ( tree->left != NULL ) stack_push(&stack, tree->left ); + } + + stack_free(&stack); + } +} + +void +tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree != NULL ) { + struct stack stack; + + stack_init(&stack); + + while ( !stack_empty(&stack) || tree != NULL ) { + if ( tree != NULL ) { + stack_push(&stack, tree); + tree = tree->left; + } + else { + stack_pop(&stack, &tree); + visit(tree->key, cl); + tree = tree->right; + } + } + + stack_free(&stack); + } +} + +/* ======================== */ + +struct tree_iterator { + struct stack stack; +}; + +static void +tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node) +{ + for ( ; node; node = node->left ) { + stack_push(stack, node); + } +} + +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; +} + +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); +} + +void +tree_iterator_free(struct tree_iterator *it) +{ + stack_free(&it->stack); +} + +/* ===== */ + + +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(tree, 10); + tree = tree_insert(tree, 5); + tree = tree_insert(tree, 20); + tree = tree_insert(tree, 1); + tree = tree_insert(tree, 7); + tree = tree_insert(tree, 15); + tree = tree_insert(tree, 18); + + tree_apply_preorder(tree, print, NULL); + + show_tree(tree, 0, 0); + + struct tree_iterator it; + struct tree_node *node = tree_iterator_first(&it, tree); + while ( node ) { + fprintf(stdout, "%d\n", node->key); + + node = tree_iterator_next(&it); + } + tree_iterator_free(&it); + + tree_clear(tree); + + return EXIT_SUCCESS; +} diff --git a/treeutil.h b/treeutil.h new file mode 100644 index 0000000..302a6e3 --- /dev/null +++ b/treeutil.h @@ -0,0 +1,45 @@ +// aux display and verification routines, helpful but not essential +struct trunk { + struct trunk *prev; + char * str; +}; + +static void show_trunks(struct trunk *p) +{ + if (!p) return; + show_trunks(p->prev); + printf("%s", p->str); +} + +// this is very haphazzard +static void show_tree(struct tree_node *root, struct trunk *prev, int is_left) +{ + if (root == NULL) return; + + struct trunk this_disp = { prev, " " }; + char *prev_str = this_disp.str; + show_tree(root->right, &this_disp, 1); + + if (!prev) + this_disp.str = "---"; + else if (is_left) { + this_disp.str = ".--"; + prev_str = " |"; + } else { + this_disp.str = "`--"; + prev->str = prev_str; + } + + show_trunks(&this_disp); + if ( root->key >= 'A' && root->key <= 'Z' ) + printf("%c\n", root->key); + else + printf("%d\n", root->key); + + if (prev) prev->str = prev_str; + this_disp.str = " |"; + + show_tree(root->left, &this_disp, 0); + if (!prev) puts(""); +} + diff --git a/util.h b/util.h new file mode 100644 index 0000000..eb250ae --- /dev/null +++ b/util.h @@ -0,0 +1,32 @@ +#ifndef ITS1_UTIL_H_INCLUDED +#define ITS1_UTIL_H_INCLUDED + +#include +#include +#include + +#ifndef NDEBUG +static void +error(const char *msg, ...) +{ + va_list ap; + + va_start(ap, msg); + fprintf(stderr, "Error: "); + vfprintf(stderr, msg, ap); + va_end(ap); + fprintf(stderr, "\n"); + exit(EXIT_FAILURE); +} + +#define ERROR(msg) error(msg " in \"%s()\" (%s:%d)", __func__, __FILE__, __LINE__) +#else +#define ERROR(msg) /**/ +#endif + +#ifndef NELEM +#define NELEM(x) (sizeof(x) / sizeof(x[0])) +#endif + +#endif + -- cgit v1.3