aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore16
-rw-r--r--allocator.c75
-rw-r--r--allocator.h31
-rw-r--r--avl.c453
-rw-r--r--deque.c125
-rw-r--r--dlist.c539
-rw-r--r--hashtab.c198
-rw-r--r--heap.c152
-rw-r--r--list.c203
-rw-r--r--makefile51
-rw-r--r--queue.c86
-rw-r--r--quicksort.c666
-rw-r--r--random.h47
-rw-r--r--rb.c661
-rw-r--r--rc4.c463
-rw-r--r--readme.md12
-rw-r--r--ringbuff.c72
-rw-r--r--stack.c98
-rw-r--r--stack2.c100
-rw-r--r--tree.c466
-rw-r--r--treeutil.h45
-rw-r--r--util.h32
22 files changed, 4591 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..d6748cb
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,16 @@
1tags
2allocator
3avl
4deque
5dlist
6hashtab
7heap
8list
9queue
10quicksort
11rb
12ringbuff
13stack
14stack2
15tree
16
diff --git a/allocator.c b/allocator.c
new file mode 100644
index 0000000..c498bc7
--- /dev/null
+++ b/allocator.c
@@ -0,0 +1,75 @@
1#include <stdlib.h>
2#include "allocator.h"
3
4/* Interface Code */
5static void *
6default_allocate(struct its1_allocator *allocator, size_t n)
7{
8 (void) allocator;
9 return malloc(n);
10}
11
12static void
13default_deallocate(struct its1_allocator *allocator, void *ptr)
14{
15 (void) allocator;
16 free(ptr);
17}
18
19struct its1_allocator its1_default_allocator = {
20 .allocate = &default_allocate,
21 .deallocate = &default_deallocate
22};
23
24/* Libary Code */
25#include <string.h>
26
27void *
28its1_malloc(struct its1_allocator *allocator, size_t n)
29{
30 if (allocator == NULL) {
31 allocator = &its1_default_allocator;
32 }
33
34 return allocator->allocate(allocator, n);
35}
36
37void
38its1_free(struct its1_allocator *allocator, void *ptr)
39{
40 if (allocator == NULL) {
41 allocator = &its1_default_allocator;
42 }
43
44 allocator->deallocate(allocator, ptr);
45}
46
47char *
48its1_strdup(struct its1_allocator *allocator, const char *str)
49{
50 size_t n;
51 char *dest;
52
53 n = strlen(str) + 1;
54 dest = its1_malloc(allocator, n);
55 if (dest != NULL) {
56 memcpy(dest, str, n);
57 }
58
59 return dest;
60}
61
62void *
63its1_malloc_zero(struct its1_allocator *allocator, size_t n)
64{
65 void *ptr;
66
67 ptr = its1_malloc(allocator, n);
68 if (ptr != NULL) {
69 memset(ptr, 0, n);
70 }
71
72 return ptr;
73}
74
75int 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 @@
1#ifndef ITS1_ALLOCATOR_H_INCLUDED
2#define ITS1_ALLOCATOR_H_INCLUDED
3
4struct its1_allocator {
5 void *(*allocate)(struct its1_allocator *allocator, size_t n);
6 void (*deallocate)(struct its1_allocator *allocator, void *ptr);
7};
8
9extern struct its1_allocator its1_default_allocator;
10
11/* allocator interface */
12void *its1_malloc(struct its1_allocator *allocator, size_t n);
13void its1_free(struct its1_allocator *allocator, void *ptr);
14
15/* helper functions */
16char *its1_strdup(struct its1_allocator *allocator, const char *str);
17void *its1_malloc_zero(struct its1_allocator *allocator, size_t n);
18
19#define ALLOCATE(n) \
20 its1_malloc(&its1_default_allocator, (n))
21
22#define ALLOCATE_ZERO(n) \
23 its1_malloc_zero(&its1_default_allocator, (n))
24
25#define FREE(ptr) \
26 (its1_free(&its1_default_allocator, (ptr)), (ptr) = NULL)
27
28#define NEW(ptr) ((ptr) = ALLOCATE(sizeof *(ptr)))
29#define NEW0(ptr) ((ptr) = ALLOCATE_ZERO(sizeof *(ptr)))
30
31#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 @@
1// AVL Tree
2#include <stdio.h>
3#include <stdlib.h>
4#include <stdbool.h>
5#include <time.h>
6
7/* utils */
8#include "util.h"
9
10// TODO: [x] Review: http://www.inr.ac.ru/~info21/ADen/
11// [x] Tests: https://stackoverflow.com/q/3955680
12
13typedef int T;
14
15struct tree_node {
16 struct tree_node *left, *right;
17 int bal;
18 T key;
19 int count; /* collision counter */
20 /* ggf. weitere Felder... */
21};
22
23static struct tree_node *
24insert_r(T x, struct tree_node *p, bool *h)
25{
26 struct tree_node *p1, *p2;
27
28 if ( p == NULL ) {
29 *h = true;
30
31 p = malloc(sizeof *p);
32 if ( p != NULL ) {
33 p->left = NULL;
34 p->right = NULL;
35 p->bal = 0;
36
37 p->key = x;
38 p->count = 1; /* hit counter */
39 }
40 else
41 ERROR("out of memory");
42 }
43 else if ( x < p->key ) {
44 p->left = insert_r(x, p->left, h);
45
46 if ( *h ) {
47 if ( p->bal == +1 ) {
48 p->bal = 0;
49 *h = false;
50 }
51 else if ( p->bal == 0 ) {
52 p->bal = -1;
53 }
54 else /* if ( p->bal == -1 ) */ {
55 p1 = p->left;
56 if ( p1->bal == -1 ) { /* single LL rotation */
57 p->left = p1->right; p1->right = p;
58 p->bal = 0; p = p1;
59 }
60 else { /* double LR rotation */
61 p2 = p1->right;
62 p1->right = p2->left; p2->left = p1;
63 p->left = p2->right; p2->right = p;
64 p->bal = ( p2->bal == -1 ) ? +1 : 0;
65 p1->bal = ( p2->bal == +1 ) ? -1 : 0;
66 p = p2;
67 }
68 p->bal = 0;
69 *h = false;
70 }
71 }
72 }
73 else if ( x > p->key ) {
74 p->right = insert_r(x, p->right, h);
75
76 if ( *h ) {
77 if ( p->bal == -1 ) {
78 p->bal = 0;
79 *h = false;
80 }
81 else if ( p->bal == 0 ) {
82 p->bal = +1;
83 }
84 else /* if ( p->bal == +1 ) */ {
85 p1 = p->right;
86 if ( p1->bal == +1 ) { /* single RR rotation */
87 p->right = p1->left; p1->left = p;
88 p->bal = 0; p = p1;
89 }
90 else { /* double RL rotation */
91 p2 = p1->left;
92 p1->left = p2->right; p2->right = p1;
93 p->right = p2->left; p2->left = p;
94 p->bal = ( p2->bal == +1 ) ? -1 : 0;
95 p1->bal = ( p2->bal == -1 ) ? +1 : 0;
96 p = p2;
97 }
98 p->bal = 0;
99 *h = false;
100 }
101 }
102 }
103 else {
104 /* handle collision! */
105 p->count++; /* hit counter */
106 *h = false;
107 }
108 if ( p == NULL )
109 ERROR("das hier sollte niemals passieren");
110 return p;
111}
112
113struct tree_node *
114insert(struct tree_node *tree, T data)
115{
116 bool h = false;
117 return insert_r(data, tree, &h);
118}
119
120static struct tree_node *
121balanceL(struct tree_node *p, bool *h)
122{
123 if ( p->bal == -1 ) {
124 p->bal = 0;
125 }
126 else if ( p->bal == 0 ) {
127 p->bal = +1;
128 *h = false;
129 }
130 else /* if ( p->bal == +1 ) */ { /* rebalance */
131 struct tree_node *p1 = p->right;
132 if ( p1->bal >= 0 ) { /* singla RR rotation */
133 p->right = p1->left;
134 p1->left = p;
135 if ( p1->bal == 0 ) {
136 p->bal = +1;
137 p1->bal = -1;
138 *h = false;
139 }
140 else {
141 p->bal = 0;
142 p1->bal = 0;
143 }
144 p = p1;
145 }
146 else { /* double RL rotation */
147 struct tree_node *p2 = p1->left;
148 p1->left = p2->right;
149 p2->right = p1;
150 p->right = p2->left;
151 p2->left = p;
152 p->bal = ( p2->bal == +1 ) ? -1 : 0;
153 p1->bal = ( p2->bal == -1 ) ? +1 : 0;
154 p = p2;
155 p2->bal = 0;
156 }
157 }
158 return p;
159}
160
161static struct tree_node *
162balanceR(struct tree_node *p, bool *h)
163{
164 if ( p->bal == +1 ) {
165 p->bal = 0;
166 }
167 else if ( p->bal == 0 ) {
168 p->bal = -1;
169 *h = false;
170 }
171 else /* p->bal == -1 */ { /* rebalance */
172 struct tree_node *p1 = p->left;
173 if ( p1->bal <= 0 ) { /* single LL rotation */
174 p->left = p1->right;
175 p1->right = p;
176 if ( p1->bal == 0 ) {
177 p->bal = -1;
178 p1->bal = +1;
179 *h = false;
180 }
181 else {
182 p->bal = 0;
183 p1->bal = 0;
184 }
185 p = p1;
186 }
187 else { /* double LR rotation */
188 struct tree_node *p2 = p1->right;
189 p1->right = p2->left;
190 p2->left = p1;
191 p->left = p2->right;
192 p2->right = p;
193 p->bal = ( p2->bal == -1 ) ? +1 : 0;
194 p1->bal = ( p2->bal == +1 ) ? -1 : 0;
195 p = p2;
196 p2->bal = 0;
197 }
198 }
199 return p;
200}
201
202static void
203del(struct tree_node **q, struct tree_node **r, bool *h)
204{
205 if ( (*r)->right != NULL ) {
206 del(q, &(*r)->right, h);
207 if ( *h )
208 *r = balanceR(*r, h);
209 }
210 else {
211 /* copy data */
212 (*q)->key = (*r)->key;
213 (*q)->count = (*r)->count;
214
215 *q = *r;
216 *r = (*r)->left;
217 *h = true;
218 }
219}
220
221static struct tree_node *
222delete_r(T x, struct tree_node *p, bool *h)
223{
224 if ( p == NULL ) {
225 ERROR("key not found");
226 }
227 else if ( x < p->key ) {
228 p->left = delete_r(x, p->left, h);
229 if ( *h )
230 p = balanceL(p, h);
231 }
232 else if ( x > p->key ) {
233 p->right = delete_r(x, p->right, h);
234 if ( *h )
235 p = balanceR(p, h);
236 }
237 else /* if ( x == p->key ) */ {
238 struct tree_node *q = p;
239 if ( q->right == NULL ) {
240 p = q->left;
241 *h = true;
242 }
243 else if ( q->left == NULL ) {
244 p = q->right;
245 *h = true;
246 }
247 else {
248 del(&q, &q->left, h);
249 if ( *h )
250 p = balanceL(p, h);
251 }
252 free(q);
253 }
254 return p;
255}
256
257struct tree_node *
258delete(struct tree_node *tree, T data)
259{
260 bool h = false;
261 return delete_r(data, tree, &h);
262}
263
264
265// aux display and verification routines, helpful but not essential
266struct trunk {
267 struct trunk *prev;
268 char * str;
269};
270
271void show_trunks(struct trunk *p)
272{
273 if (!p) return;
274 show_trunks(p->prev);
275 printf("%s", p->str);
276}
277
278// this is very haphazzard
279void show_tree(struct tree_node *root, struct trunk *prev, int is_left)
280{
281 if (root == NULL) return;
282
283 struct trunk this_disp = { prev, " " };
284 char *prev_str = this_disp.str;
285 show_tree(root->right, &this_disp, 1);
286
287 if (!prev)
288 this_disp.str = "---";
289 else if (is_left) {
290 this_disp.str = ".--";
291 prev_str = " |";
292 } else {
293 this_disp.str = "`--";
294 prev->str = prev_str;
295 }
296
297 show_trunks(&this_disp);
298 if ( root->key >= 'A' && root->key <= 'Z' )
299 printf("%c\n", root->key);
300 else
301 printf("%d\n", root->key);
302
303 if (prev) prev->str = prev_str;
304 this_disp.str = " |";
305
306 show_tree(root->left, &this_disp, 0);
307 if (!prev) puts("");
308}
309
310void
311print(struct tree_node *tree)
312{
313 if ( tree ) {
314 print(tree->left);
315 printf("%d (%d)\n", tree->key, tree->bal);
316 print(tree->right);
317 }
318}
319
320int
321main()
322{
323
324
325#if 0 /* 1a/b */
326 tree = insert(tree, 20);
327 tree = insert(tree, 4);
328 show_tree(tree, 0, 0);
329
330 //tree = insert(tree, 15);
331 tree = insert(tree, 8);
332 show_tree(tree, 0, 0);
333#endif
334
335#if 0 /* 2a/b */
336 tree = insert(tree, 20);
337 tree = insert(tree, 4);
338 tree = insert(tree, 26);
339 tree = insert(tree, 3);
340 tree = insert(tree, 9);
341 show_tree(tree, 0, 0);
342
343 //tree = insert(tree, 15);
344 tree = insert(tree, 8);
345 show_tree(tree, 0, 0);
346#endif
347
348#if 0 /* 3a/b */
349 tree = insert(tree, 20);
350 tree = insert(tree, 4);
351 tree = insert(tree, 26);
352 tree = insert(tree, 3);
353 tree = insert(tree, 9);
354 tree = insert(tree, 21);
355 tree = insert(tree, 30);
356 tree = insert(tree, 2);
357 tree = insert(tree, 7);
358 tree = insert(tree, 11);
359 show_tree(tree, 0, 0);
360
361 //tree = insert(tree, 15);
362 tree = insert(tree, 8);
363 show_tree(tree, 0, 0);
364#endif
365
366#if 0
367 tree = insert(tree, 2);
368 tree = insert(tree, 1);
369 tree = insert(tree, 4);
370 tree = insert(tree, 3);
371 tree = insert(tree, 5);
372 show_tree(tree, 0, 0);
373
374 tree = delete(tree, 1);
375 show_tree(tree, 0, 0);
376#endif
377
378#if 0
379 tree = insert(tree, 6);
380 tree = insert(tree, 2);
381 tree = insert(tree, 9);
382 tree = insert(tree, 1);
383 tree = insert(tree, 4);
384 tree = insert(tree, 8);
385 tree = insert(tree, 'B');
386 tree = insert(tree, 3);
387 tree = insert(tree, 5);
388 tree = insert(tree, 7);
389 tree = insert(tree, 'A');
390 tree = insert(tree, 'C');
391 tree = insert(tree, 'D');
392 show_tree(tree, 0, 0);
393
394 tree = delete(tree, 1);
395 show_tree(tree, 0, 0);
396#endif
397
398
399#if 0
400 tree = insert(tree, 5);
401 tree = insert(tree, 2);
402 tree = insert(tree, 8);
403 tree = insert(tree, 1);
404 tree = insert(tree, 3);
405 tree = insert(tree, 7);
406 tree = insert(tree, 'A');
407 tree = insert(tree, 4);
408 tree = insert(tree, 6);
409 tree = insert(tree, 9);
410 tree = insert(tree, 'B');
411 tree = insert(tree, 'C');
412 show_tree(tree, 0, 0);
413
414 tree = delete(tree, 1);
415 show_tree(tree, 0, 0);
416#endif
417
418
419#if 0
420 tree = insert(tree, 5);
421 tree = insert(tree, 3);
422 tree = insert(tree, 8);
423 tree = insert(tree, 2);
424 tree = insert(tree, 4);
425 tree = insert(tree, 7);
426 tree = insert(tree, 10);
427 tree = insert(tree, 1);
428 tree = insert(tree, 6);
429 tree = insert(tree, 9);
430 tree = insert(tree, 11);
431
432 tree = delete(tree, 4);
433 tree = delete(tree, 8);
434 tree = delete(tree, 6);
435 tree = delete(tree, 5);
436 tree = delete(tree, 2);
437 tree = delete(tree, 1);
438 tree = delete(tree, 7);
439
440 show_tree(tree, 0, 0);
441#endif
442
443 struct tree_node *tree = NULL;
444
445 srand(time(NULL));
446 for ( int i = 0; i != 300000; ++i )
447 tree = insert(tree, rand());
448
449 //show_tree(tree, 0, 0);
450
451 return EXIT_SUCCESS;
452}
453
diff --git a/deque.c b/deque.c
new file mode 100644
index 0000000..7125764
--- /dev/null
+++ b/deque.c
@@ -0,0 +1,125 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define NELEM(x) (sizeof(x) / sizeof(x[0]))
6
7typedef int T;
8
9struct chunk {
10 int head, tail;
11 T array[8];
12};
13
14static void
15chunk_init(struct chunk *c)
16{
17 c->head = 0;
18 c->tail = 0;
19}
20
21static bool
22chunk_put(struct chunk *c, T data)
23{
24 const int next = (c->head + 1) % NELEM(c->array);
25
26 if ( next == c->tail ) /* full? */
27 return false;
28
29 c->array[c->head] = data;
30 c->head = next;
31
32 return true;
33}
34
35static bool
36chunk_get(struct chunk *c, T *data)
37{
38 if ( c->head == c->tail ) /* empty? */
39 return false;
40
41 const int next = (c->tail + 1) % NELEM(c->array);
42
43 *data = c->array[c->tail];
44 c->tail = next;
45
46 return true;
47}
48
49static int
50chunk_size(struct chunk *c)
51{
52 return (c->head + NELEM(c->array) - c->tail) % NELEM(c->array);
53}
54
55static bool
56chunk_full(struct chunk *c)
57{
58 return ((c->head + 1) % NELEM(c->array)) == c->tail;
59}
60
61static bool
62chunk_empty(struct chunk *c)
63{
64 return c->head == c->tail;
65}
66
67static T*
68chunk_at(struct chunk *c, int idx)
69{
70 if ( idx < 0 || idx >= chunk_size(c) ) /* invalid index? */
71 return NULL;
72
73 return &c->array[(c->head + idx) % NELEM(c->array)];
74}
75
76/* ================= */
77
78struct deque {
79 int head, tail, capacity;
80
81 struct chunk **chunks;
82};
83
84void
85deque_init(struct deque *d)
86{
87 int i;
88
89 d->head = 0;
90 d->tail = 0;
91 d->capacity = 1;
92
93 d->chunks = calloc(d->capacity, sizeof(struct chunk *));
94
95 for ( i = 0; i != d->capacity; ++i ) {
96 d->chunks[i] = malloc(sizeof(struct chunk));
97 chunk_init(d->chunks[i]);
98 }
99}
100
101
102int main(void)
103{
104 struct chunk c;
105 int data;
106
107 chunk_init(&c);
108
109 chunk_put(&c, '0');
110 chunk_put(&c, '0');
111 chunk_get(&c, &data);
112 chunk_get(&c, &data);
113
114 chunk_put(&c, 'A');
115 chunk_put(&c, 'B');
116 chunk_put(&c, 'C');
117 chunk_put(&c, 'D');
118 chunk_put(&c, 'E');
119 chunk_put(&c, 'F');
120 chunk_put(&c, 'G');
121
122 printf("head: %d -- tail: %d -- size: %d\n", c.head, c.tail, chunk_size(&c));
123 return 0;
124}
125
diff --git a/dlist.c b/dlist.c
new file mode 100644
index 0000000..140d3a3
--- /dev/null
+++ b/dlist.c
@@ -0,0 +1,539 @@
1/* dlist -- double linked list */
2
3/* Standard C */
4#include <stdio.h>
5#include <stdlib.h>
6#include <stdbool.h>
7#include <assert.h>
8#include <time.h>
9
10/* Project */
11#include "util.h"
12
13typedef int T;
14
15struct dlist {
16 struct dlist_element *head, *tail;
17};
18
19struct dlist_element {
20 struct dlist_element *prev, *next;
21 T data;
22};
23
24void
25dlist_init(struct dlist *dlist)
26{
27 dlist->head = NULL;
28 dlist->tail = NULL;
29}
30
31static struct dlist_element *
32create_element(T data)
33{
34 struct dlist_element *element;
35
36 element = malloc(sizeof *element);
37 if ( element != NULL ) {
38 element->data = data;
39 }
40
41 return element;
42}
43
44struct dlist_element *
45dlist_push_front(struct dlist *dlist, T data)
46{
47 struct dlist_element *element;
48
49 element = create_element(data);
50 if ( element != NULL ) {
51 element->prev = NULL; /* Vorgänger ist in jedem Fall NULL */
52
53 if ( dlist->head == NULL ) { /* empty list */
54 element->next = NULL;
55 dlist->tail = element;
56 }
57 else { /* non empty list */
58 element->next = dlist->head;
59 element->next->prev = element;
60 }
61
62 dlist->head = element; /* Neues Element ist in jedem Fall der neue Anfang! */
63 }
64 else
65 ERROR("out of memory");
66
67 return element;
68}
69
70struct dlist_element *
71dlist_push_back(struct dlist *dlist, T data)
72{
73 struct dlist_element *element;
74
75 element = create_element(data);
76 if ( element != NULL ) {
77 element->next = NULL; /* Nachfolger ist in jedem Fall NULL */
78
79 if ( dlist->head == NULL ) { /* empty list */
80 element->prev = NULL;
81 dlist->head = element;
82 }
83 else { /* non empty list */
84 element->prev = dlist->tail;
85 element->prev->next = element;
86 }
87
88 dlist->tail = element; /* Neues Element ist in jedem Fall das neue Ende! */
89 }
90 else
91 ERROR("out of memory");
92
93 return element;
94}
95
96bool
97dlist_pop_front(struct dlist *dlist, T *data)
98{
99 if ( dlist->head != NULL ) {
100 struct dlist_element *element = dlist->head;
101
102 dlist->head = element->next;
103
104 if ( dlist->head == NULL )
105 dlist->tail = NULL;
106 else
107 element->next->prev = NULL;
108
109 *data = element->data;
110 free(element);
111
112 return true;
113 }
114 else
115 return false;
116}
117
118bool
119dlist_pop_back(struct dlist *dlist, T *data)
120{
121 if ( dlist->head != NULL ) {
122 struct dlist_element *element = dlist->tail;
123
124 dlist->tail = element->prev;
125
126 if ( dlist->tail == NULL )
127 dlist->head = NULL;
128 else
129 element->prev->next = NULL;
130
131 *data = element->data;
132 free(element);
133
134 return true;
135 }
136 else
137 return false;
138}
139
140struct dlist_element *
141dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data)
142{
143 struct dlist_element *new_element;
144
145 new_element = create_element(data);
146 if ( new_element != NULL ) {
147 if ( dlist->head == NULL ) {
148 dlist->head = new_element;
149 dlist->head->prev = NULL;
150 dlist->head->next = NULL;
151 dlist->tail = new_element;
152 }
153 else {
154 new_element->next = element->next;
155 new_element->prev = element;
156
157 if ( element->next == NULL )
158 dlist->tail = new_element;
159 else
160 element->next->prev = new_element;
161
162 element->next = new_element;
163 }
164 }
165 else
166 ERROR("out of memory");
167
168 return new_element;
169}
170
171struct dlist_element *
172dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data)
173{
174 struct dlist_element *new_element;
175
176 new_element = create_element(data);
177 if ( new_element != NULL ) {
178 if ( dlist->head == NULL ) {
179 dlist->head = new_element;
180 dlist->head->prev = NULL;
181 dlist->head->next = NULL;
182 dlist->tail = new_element;
183 }
184 else {
185 new_element->next = element;
186 new_element->prev = element->prev;
187
188 if ( element->prev == NULL )
189 dlist->head = new_element;
190 else
191 element->prev->next = new_element;
192
193 element->prev = new_element;
194 }
195 }
196 else
197 ERROR("out of memory");
198
199 return new_element;
200}
201
202void
203dlist_remove(struct dlist *dlist, struct dlist_element *element)
204{
205 if ( element == dlist->head ) {
206 dlist->head = element->next;
207
208 if ( dlist->head == NULL )
209 dlist->tail = NULL;
210 else
211 element->next->prev = NULL;
212 }
213 else {
214 element->prev->next = element->next;
215
216 if ( element->next == NULL )
217 dlist->tail = element->prev;
218 else
219 element->next->prev = element->prev;
220 }
221
222 free(element);
223}
224
225void
226dlist_free(struct dlist *dlist)
227{
228 struct dlist_element *elem, *next;
229
230 for ( elem = dlist->head; elem; elem = next ) {
231 next = elem->next;
232 free(elem);
233 }
234
235 dlist_init(dlist);
236}
237
238void
239dlist_apply_rev(struct dlist *dlist, void (*visit)(T data, void *cl), void *cl)
240{
241 for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev )
242 visit(elem->data, cl);
243}
244
245void
246print_list(const char *msg, struct dlist *dlist)
247{
248 printf("%s:", msg);
249
250 for ( struct dlist_element *elem = dlist->head; elem; elem = elem->next )
251 printf(" %d", elem->data);
252
253 putchar('\n');
254}
255
256void
257print_list_rev(const char *msg, struct dlist *dlist)
258{
259 printf("%s:", msg);
260
261 for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev )
262 printf(" %d", elem->data);
263
264 putchar('\n');
265}
266
267void
268remove_if(struct dlist *list)
269{
270 struct dlist_element *elem, *next;
271
272 for ( elem = list->head; elem; elem = next ) {
273 next = elem->next;
274
275 if ( (elem->data & 1) == 1 )
276 dlist_remove(list, elem);
277 }
278}
279
280void
281dlist_sort_xxx(struct dlist *list)
282{
283 if ( list->head == NULL )
284 return;
285
286 int insize = 1;
287
288 while (1) {
289 struct dlist_element *p;
290
291 p = list->head;
292 list->head = NULL;
293 list->tail = NULL;
294
295 int nmerges = 0; /* count number of merges we do in this pass */
296
297 while (p) {
298
299 struct dlist_element *q;
300
301 nmerges++; /* there exists a merge to be done */
302 /* step `insize' places along from p */
303 q = p;
304 int psize = 0;
305 for (int i = 0; i < insize; i++) {
306 psize++;
307 q = q->next;
308 if (!q) break;
309 }
310
311 /* if q hasn't fallen off end, we have two lists to merge */
312 int qsize = insize;
313
314 /* now we have two lists; merge them */
315 while (psize > 0 || (qsize > 0 && q)) {
316
317 struct dlist_element *e;
318
319 /* decide whether next element of merge comes from p or q */
320 if (psize == 0) {
321 /* p is empty; e must come from q. */
322 e = q; q = q->next; qsize--;
323 } else if (qsize == 0 || !q) {
324 /* q is empty; e must come from p. */
325 e = p; p = p->next; psize--;
326 } else if (p->data < q->data) {
327 /* First element of p is lower ;
328 * e must come from p. */
329 e = p; p = p->next; psize--;
330 } else {
331 /* First element of q is lower; e must come from q. */
332 e = q; q = q->next; qsize--;
333 }
334
335 /* add the next element to the merged list */
336 if (list->tail) {
337 list->tail->next = e;
338 } else {
339 list->head = e;
340 }
341 e->prev = list->tail;
342 list->tail = e;
343 }
344
345 /* now p has stepped `insize' places along, and q has too */
346 p = q;
347 }
348 list->tail->next = NULL;
349
350 /* If we have done only one merge, we're finished. */
351 if (nmerges <= 1) /* allow for nmerges==0, the empty list case */
352 return; // list;
353
354 /* Otherwise repeat, merging lists twice the size */
355 insize *= 2;
356 }
357}
358
359struct dlist *
360dlist_merge(struct dlist *list1, struct dlist *list2)
361{
362 struct dlist_element *head = NULL,
363 *cur = NULL,
364 *e1 = list1->head,
365 *e2 = list2->head;
366
367 while ( e1 != NULL && e2 != NULL ) // Solange in e1 UND e2 Elemente sind...
368 {
369 if ( e1->data < e2->data )
370 {
371 e1->prev = cur;
372 if ( cur != NULL )
373 cur->next = e1;
374 else
375 head = e1;
376 cur = e1;
377 e1 = e1->next;
378 }
379 else
380 {
381 e2->prev = cur;
382 if ( cur != NULL )
383 cur->next = e2;
384 else
385 head = e2;
386 cur = e2;
387 e2 = e2->next;
388 }
389 }
390
391 if ( e1 != NULL ) // in e1 sind noch Elemente vorhanden!
392 {
393 assert(e2 == NULL);
394
395 e1->prev = cur;
396 if ( cur != NULL )
397 cur->next = e1;
398 else
399 head = e1;
400
401 // list1->tail zeigt bereits auf das letzte Element in list1
402 }
403 else /* if ( e2 != NULL ) */
404 {
405 assert(e1 == NULL);
406 assert(e2 != NULL);
407
408 e2->prev = cur;
409 if ( cur != NULL )
410 cur->next = e2;
411 else
412 head = e2;
413
414 list1->tail = list2->tail; // list2->tail ist das Ende der Liste
415 }
416
417 // Kopf neu setzen...
418 list1->head = head;
419
420 // Liste2 ist leer
421 list2->head = NULL;
422 list2->tail = NULL;
423
424 // Zeiger auf Liste1 zurückliefern
425 return list1;
426}
427
428struct dlist *
429dlist_sort(struct dlist *list)
430{
431 if ( list->head == NULL || list->head->next == NULL ) // Leer oder nur ein Element? => Fertig
432 return list;
433
434 struct dlist_element *slow = list->head,
435 *fast = list->head->next;
436
437 while ( fast != NULL && fast->next != NULL )
438 slow = slow->next, fast = fast->next->next;
439
440 struct dlist list1 = { .head = list->head, .tail = slow },
441 list2 = { .head = slow->next, .tail = list->tail };
442
443 list1.tail->next = list2.head->prev = NULL;
444
445 dlist_merge(dlist_sort(&list1), dlist_sort(&list2));
446
447 list->head = list1.head;
448 list->tail = list1.tail;
449
450 return list;
451}
452
453void merge_test(void)
454{
455 struct dlist l1, l2;
456
457 dlist_init(&l1);
458 dlist_init(&l2);
459
460 dlist_push_back(&l1, 7);
461 dlist_push_back(&l1, 10);
462 dlist_push_back(&l1, 11);
463 dlist_push_back(&l1, 19);
464 dlist_push_back(&l1, 23);
465
466 dlist_push_back(&l2, 4);
467 dlist_push_back(&l2, 14);
468 dlist_push_back(&l2, 15);
469
470 struct dlist *ptr;
471 ptr = dlist_merge(&l1, &l2);
472
473 struct dlist_element *cur;
474 for ( cur = ptr->head; cur; cur = cur->next ) {
475 if ( cur->prev ) printf("%4d", cur->prev->data); else printf("xxx ");
476 printf("%4d", cur->data);
477 if ( cur->next ) printf("%4d", cur->next->data); else printf(" xxx");
478
479 puts("");
480 }
481
482 dlist_free(&l1);
483 dlist_free(&l2);
484}
485
486void ls()
487{
488 struct dlist list;
489
490 dlist_init(&list);
491
492 for ( int i = 0; i != 30000000; ++i )
493 dlist_insert_prev(&list, list.tail, rand() % 9999);
494
495 //print_list("Unsortiert:", &list);
496 printf("start\n");
497 clock_t start = clock();
498 dlist_sort(&list);
499 clock_t ende = clock();
500
501 printf("Dauer: %.3fsec\n", ((double) ende-start)/CLOCKS_PER_SEC);
502 //print_list("Sortiert:", &list);
503 //print_list_rev("Sortiert:", &list);
504
505 dlist_free(&list);
506}
507
508
509int
510main(void)
511{
512 ls();
513
514#if 0
515 merge_test();
516#endif
517
518#if 0
519 struct dlist list;
520
521 dlist_init(&list);
522
523 for ( int i = 0; i != 10; ++i )
524 dlist_insert_prev(&list, list.tail, i);
525
526 print_list("Ausgabe: ", &list);
527
528 remove_if(&list);
529
530 print_list("Ausgabe: ", &list);
531
532 dlist_free(&list);
533
534 ls();
535
536 return EXIT_SUCCESS;
537#endif
538}
539
diff --git a/hashtab.c b/hashtab.c
new file mode 100644
index 0000000..6b35c89
--- /dev/null
+++ b/hashtab.c
@@ -0,0 +1,198 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <stdbool.h>
5#include <ctype.h>
6
7#include "util.h"
8
9typedef int T;
10
11struct hash_item {
12 struct hash_item *next;
13 char *key;
14 T data;
15};
16
17struct hash_tab {
18 struct hash_item *table[251]; // fit for your needs...
19};
20
21static unsigned long
22hash_key(const unsigned char *str)
23{
24 unsigned long hash = 5381;
25 int c;
26
27 while ( (c = *str++) != '\0' )
28 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
29
30 return hash;
31}
32
33void
34hash_init(struct hash_tab *ht)
35{
36 for ( int i = 0; i != NELEM(ht->table); ++i )
37 ht->table[i] = NULL;
38}
39
40static struct hash_item *
41hash_add(struct hash_item *next, const char *key, T data)
42{
43 struct hash_item *new_item;
44 char *new_key;
45
46 new_key = strdup(key); // strdup: not standard but commonly used...
47 new_item = malloc(sizeof(*new_item));
48
49 if ( new_key == NULL || new_item == NULL ) {
50 free(new_key);
51 free(new_item);
52 ERROR("out of memory");
53 return NULL;
54 }
55
56 new_item->next = next;
57 new_item->key = new_key;
58 new_item->data = data;
59
60 return new_item;
61}
62
63T *
64hash_lookup(struct hash_tab *ht, const char *key, T data, int create)
65{
66 unsigned long h;
67 struct hash_item *item;
68
69 h = hash_key((const unsigned char *) key) % NELEM(ht->table);
70 for ( item = ht->table[h]; item; item = item->next )
71 if ( strcmp(key, item->key) == 0 )
72 return &item->data;
73
74 // not found! create?
75 if ( create ) {
76 item = hash_add(ht->table[h], key, data);
77 if ( item != NULL )
78 ht->table[h] = item;
79 else
80 ERROR("can't create item");
81 }
82
83 return item ? &item->data : NULL;
84}
85
86bool
87hash_delete(struct hash_tab *ht, const char *key)
88{
89 unsigned long h;
90 struct hash_item *prev, *p;
91
92 h = hash_key((const unsigned char *) key) % NELEM(ht->table);
93 prev = NULL;
94 for ( p = ht->table[h]; p; p = p->next ) {
95 if ( strcmp(key, p->key) == 0 ) {
96 if ( prev == NULL )
97 ht->table[h] = p->next;
98 else
99 prev->next = p->next;
100
101 free(p->key);
102 free(p);
103
104 return true; // successfully removed!
105 }
106 prev = p;
107 }
108
109 return false;
110}
111
112void
113hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl)
114{
115 struct hash_item *item;
116
117 for ( int i = 0; i != NELEM(ht->table); ++i )
118 for ( item = ht->table[i]; item; item = item->next )
119 visit(item->key, item->data, cl);
120}
121
122void
123hash_free(struct hash_tab *ht)
124{
125 struct hash_item *p, *next;
126
127 for ( int i = 0; i != NELEM(ht->table); ++i ) {
128 for ( p = ht->table[i]; p; p = next ) {
129 next = p->next;
130 free(p->key);
131 free(p);
132 }
133 ht->table[i] = NULL;
134 }
135}
136
137int getword(FILE *fp, char *buf, int size, int first(int c), int rest(int c))
138{
139 int i = 0, c;
140
141 c = getc(fp);
142 for ( ; c != EOF; c = getc(fp) )
143 if ( first(c) ) {
144 if ( i < size-1 )
145 buf[i++] = c;
146 c = getc(fp);
147 break;
148 }
149
150 for ( ; c != EOF && rest(c); c = getc(fp) )
151 if ( i < size-1)
152 buf[i++] = c;
153
154 if ( i < size )
155 buf[i] = 0;
156 else
157 buf[size-1] = 0;
158
159 if ( c != EOF )
160 ungetc(c, fp);
161
162 return c > 0;
163}
164
165int first(int c) {
166 return isalpha(c);
167}
168
169int rest(int c) {
170 return isalpha(c) || c == '_';
171}
172
173void print(const char *key, T data, void *cl)
174{
175 fprintf(cl, "%s: %d\n", key, data);
176}
177
178int
179main()
180{
181 struct hash_tab ht[1];
182 char word[100];
183
184 hash_init(ht);
185
186 while ( getword(stdin, word, sizeof word, first, rest) ) {
187 int *p = hash_lookup(ht, word, 0, 1);
188 if ( p != NULL )
189 ++(*p);
190 }
191
192 hash_delete(ht, "new_item");
193
194 hash_apply(ht, print, stdout);
195
196 hash_free(ht);
197}
198
diff --git a/heap.c b/heap.c
new file mode 100644
index 0000000..365d925
--- /dev/null
+++ b/heap.c
@@ -0,0 +1,152 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include "util.h"
5
6typedef int T;
7
8// https://stackoverflow.com/a/22900767
9
10#define LEFT(idx) (idx*2+1)
11#define RIGHT(idx) (idx*2+2)
12#define PARENT(idx) ((idx-1)/2)
13
14static void
15swap(T heap[], int i, int j)
16{
17 T temp = heap[i];
18 heap[i] = heap[j];
19 heap[j] = temp;
20}
21
22static void
23fixup(T heap[], int i)
24{
25 int p = PARENT(i);
26
27 while ( i > 0 && heap[p] < heap[i] ) {
28 swap(heap, i, p);
29
30 i = p;
31 p = PARENT(i);
32 }
33}
34
35static void
36fixdown(T heap[], int i, int n)
37{
38 for ( ;; ) {
39 const int l = LEFT(i);
40 const int r = RIGHT(i);
41 int m = i;
42
43 if ( l < n && heap[m] < heap[l] )
44 m = l;
45
46 if ( r < n && heap[m] < heap[r] )
47 m = r;
48
49 if ( m == i )
50 break;
51
52 swap(heap, m, i);
53
54 i = m;
55 }
56}
57
58static void
59heapify(T heap[], int n)
60{
61 for ( int i = n / 2 - 1; i >= 0; --i )
62 fixdown(heap, i, n);
63}
64
65static void
66my_heapsort(T a[], int n)
67{
68 heapify(a, n);
69
70 for ( int i = n - 1; i >= 0; --i ) {
71 swap(a, 0, i);
72 fixdown(a, 0, i);
73 }
74}
75
76// -------------------------------------------
77
78struct pq { // Priority Queue
79 T heap[251];
80 int sz;
81};
82
83void
84pq_init(struct pq *pq)
85{
86 pq->sz = 0;
87}
88
89bool
90pq_push(struct pq *pq, T data)
91{
92 if ( pq->sz == NELEM(pq->heap) )
93 return false;
94
95 pq->heap[pq->sz] = data;
96 fixup(pq->heap, pq->sz);
97 ++pq->sz;
98 return true;
99}
100
101bool
102pq_pop(struct pq *pq, T* data)
103{
104 if ( pq->sz == 0 )
105 return false;
106
107 *data = pq->heap[0];
108 --pq->sz;
109 pq->heap[0] = pq->heap[pq->sz];
110 fixdown(pq->heap, 0, pq->sz);
111 return true;
112}
113
114// -------------------------------------------
115
116
117void print_heap(T heap[], int n)
118{
119 if ( n ) {
120 printf("%d", heap[0]);
121 for ( int i = 1; i != n; ++i )
122 printf(", %d", heap[i]);
123 putchar('\n');
124 }
125}
126
127int main(void)
128{
129#if 0 // Heap-Testprogramm
130 T heap[20] = { 18, 18, 16, 9, 7, 1, 9, 3, 7, 5 };
131
132 print_heap(heap, 10);
133
134 //heap[10] = 13; fixup(heap, 10);
135 swap(heap, 0, 9); fixdown(heap, 0, 9);
136
137 print_heap(heap, 9);
138#endif
139
140 struct pq pq[1];
141
142 pq_init(pq);
143
144 for ( int i = 0; i != 10; ++i )
145 pq_push(pq, rand());
146
147 T data;
148 while ( pq_pop(pq, &data) )
149 printf("%d\n", data);
150}
151
152
diff --git a/list.c b/list.c
new file mode 100644
index 0000000..8b18de8
--- /dev/null
+++ b/list.c
@@ -0,0 +1,203 @@
1/* simple Implementation of single linked lists */
2/* written and placed in the public domain by Thomas Schmucker */
3
4/* Standard C */
5#include <stdio.h>
6#include <stdlib.h>
7#include <time.h>
8
9/* Project */
10#include "util.h"
11
12typedef int T;
13
14struct list_item {
15 struct list_item *next;
16 T data;
17};
18
19struct list_item *
20list_add(struct list_item *next, T data)
21{
22 struct list_item *new_item;
23
24 new_item = malloc(sizeof *new_item);
25 if ( new_item != NULL ) {
26 new_item->next = next;
27 new_item->data = data;
28 }
29 else
30 ERROR("out of memory");
31
32 return new_item;
33}
34
35struct list_item *
36list_delete(struct list_item *list, T data)
37{
38 struct list_item *prev = NULL;
39
40 for ( struct list_item *p = list; p; p = p->next ) {
41 if ( p->data == data ) {
42 if ( prev == NULL ) { /* first element in list? */
43 list = p->next;
44 }
45 else {
46 prev->next = p->next;
47 }
48
49 free(p);
50
51 return list;
52 }
53 prev = p;
54 }
55 //ERROR("data not found"); /* uncomment, if this case should be reported as an error */
56 return list;
57}
58
59size_t
60list_length(struct list_item *list)
61{
62 size_t len = 0;
63
64 for ( ; list; list = list->next )
65 ++len;
66
67 return len;
68}
69
70struct list_item *
71list_copy(struct list_item *list)
72{
73 struct list_item *head, **p = &head;
74
75 for ( ; list; list = list->next ) {
76 *p = malloc(sizeof **p);
77 if ( *p != NULL ) {
78 (*p)->data = list->data; // copy elements
79 p = &(*p)->next;
80 }
81 else
82 ERROR("out of memory");
83 }
84 *p = NULL;
85 return head;
86}
87
88struct list_item *
89list_reverse(struct list_item *list)
90{
91 struct list_item *head = NULL, *next;
92
93 for ( ; list; list = next ) {
94 next = list->next;
95 list->next = head;
96 head = list;
97 }
98 return head;
99}
100
101void
102list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl)
103{
104 for ( ; list; list = list->next ) {
105 visit(list->data, cl);
106 }
107}
108
109struct list_item *
110list_merge(struct list_item *a, struct list_item *b)
111{
112 struct list_item dummy = { .next = NULL };
113 struct list_item *head = &dummy, *c = head;
114
115 while ( a != NULL && b != NULL )
116 if ( a->data < b->data )
117 c->next = a, c = a, a = a->next;
118 else
119 c->next = b, c = b, b = b->next;
120
121 c->next = ( a != NULL ) ? a : b;
122
123 return head->next;
124}
125
126struct list_item *
127list_sort(struct list_item *c)
128{
129 if ( c == NULL || c->next == NULL )
130 return c;
131
132 struct list_item *a = c,
133 *b = c->next;
134
135 while ( b != NULL && b->next != NULL )
136 c = c->next, b = b->next->next;
137
138 b = c->next, c->next = NULL;
139
140 return list_merge(list_sort(a), list_sort(b));
141}
142
143void
144list_free(struct list_item *list)
145{
146 struct list_item *next;
147
148 for ( ; list; list = next ) {
149 next = list->next;
150 free(list);
151 }
152}
153
154static void print_data(T data, void *cl) { fprintf(cl, "%d\n", data); }
155
156int
157main()
158{
159 clock_t start;
160
161 /*
162 struct list_item *mylist = NULL;
163
164 mylist = list_add(mylist, 42);
165 mylist = list_add(mylist, 43);
166 mylist = list_add(mylist, 44);
167
168 mylist = list_delete(mylist, 45);
169
170 list_apply(mylist, print_data, stdout);
171
172 struct list_item *mylist2 = list_reverse(list_copy(mylist));
173
174 list_free(mylist);
175 list_apply(mylist2, print_data);
176 list_free(mylist2);
177 */
178
179 srand(time(NULL));
180
181 static const int COUNT = 10000000;
182
183 struct list_item *x = NULL;
184 for ( int i = 0; i != COUNT; ++i ) {
185 int r = rand();
186 x = list_add(x, r);
187 }
188
189 puts("start");
190 start = clock();
191 x = list_sort(x);
192 printf("Fertig: %.3lf sec\n", (double)(clock() - start) / CLOCKS_PER_SEC);
193
194 //list_apply(x, print_data);
195 printf("Len: %zu\n", list_length(x));
196
197 list_free(x);
198
199 return EXIT_SUCCESS;
200}
201
202
203
diff --git a/makefile b/makefile
new file mode 100644
index 0000000..0c229d6
--- /dev/null
+++ b/makefile
@@ -0,0 +1,51 @@
1.PHONY: all clean
2
3CFLAGS=-O3 -Wall -Werror -Wno-unused-function -pedantic -std=c99 -g
4
5all: list dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque
6
7list: list.c util.h
8 cc $(CFLAGS) $< -o $@
9
10dlist: dlist.c util.h
11 cc $(CFLAGS) $< -o $@
12
13stack: stack.c util.h
14 cc $(CFLAGS) $< -o $@
15
16stack2: stack2.c util.h
17 cc $(CFLAGS) $< -o $@
18
19queue: queue.c util.h
20 cc $(CFLAGS) $< -o $@
21
22ringbuff: ringbuff.c util.h
23 cc $(CFLAGS) $< -o $@
24
25hashtab: hashtab.c util.h
26 cc $(CFLAGS) $< -o $@
27
28tree: tree.c util.h
29 cc $(CFLAGS) $< -o $@
30
31avl: avl.c util.h
32 cc $(CFLAGS) $< -o $@
33
34rb: rb.c util.h
35 cc $(CFLAGS) $< -o $@
36
37deque: deque.c util.h
38 cc $(CFLAGS) $< -o $@
39
40heap: heap.c util.h
41 cc $(CFLAGS) $< -o $@
42
43quicksort: quicksort.c util.h
44 cc $(CFLAGS) $< -o $@
45
46allocator: allocator.c allocator.h
47 cc $(CFLAGS) $< -o $@
48
49clean:
50 rm -f list dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque
51
diff --git a/queue.c b/queue.c
new file mode 100644
index 0000000..fdacca5
--- /dev/null
+++ b/queue.c
@@ -0,0 +1,86 @@
1/* Standard C */
2#include <stdio.h>
3#include <stdlib.h>
4#include <stdbool.h>
5
6/* Project */
7#include "util.h"
8
9typedef int T;
10
11struct queue_item {
12 struct queue_item *next;
13 T data;
14};
15
16struct queue {
17 struct queue_item *head, *tail;
18};
19
20void
21queue_init(struct queue *queue)
22{
23 queue->head = NULL;
24}
25
26void
27queue_put(struct queue *queue, T data)
28{
29 struct queue_item *new_item;
30
31 if ( (new_item = malloc(sizeof(*new_item))) != NULL ) {
32 struct queue_item *tmp = queue->tail;
33 new_item->data = data;
34 queue->tail = new_item;
35 if ( queue->head == NULL )
36 queue->head = queue->tail;
37 else
38 tmp->next = queue->tail;
39 }
40 else
41 ERROR("out of memory");
42}
43
44bool
45queue_get(struct queue *queue, T *data)
46{
47 if ( queue->head != NULL ) {
48 struct queue_item *next = queue->head->next;
49 *data = queue->head->data;
50 free(queue->head);
51 queue->head = next;
52
53 return true;
54 }
55 else
56 return false;
57}
58
59bool
60queue_empty(struct queue *queue)
61{
62 return queue->head == NULL;
63}
64
65int
66main()
67{
68 struct queue queue[1];
69
70 queue_init(queue);
71
72 for ( int i = 0; i != 10; ++i )
73 queue_put(queue, i);
74
75 while ( !queue_empty(queue) ) {
76 int i;
77 if ( queue_get(queue, &i) )
78 printf("%d\n", i);
79 else
80 ERROR("this shouldn't happen!");
81 }
82 return EXIT_SUCCESS;
83}
84
85
86
diff --git a/quicksort.c b/quicksort.c
new file mode 100644
index 0000000..fa219e9
--- /dev/null
+++ b/quicksort.c
@@ -0,0 +1,666 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <assert.h>
4#include <time.h>
5#include "util.h"
6
7static int bigrand(void)
8{
9 int x = (rand() << 24) | (rand() << 16) | (rand() << 8) | rand();
10 if ( x < 0 )
11 return -x;
12 return x;
13}
14
15static int randint(int l, int u)
16{
17 return l + bigrand() % (u-l+1);
18}
19
20typedef int T;
21
22static const int CUTOFF = 128;
23
24static inline void
25swap(T a[], int i, int j)
26{
27 T t = a[i];
28 a[i] = a[j];
29 a[j] = t;
30}
31
32static void
33insertsort(T a[], int n)
34{
35 int i, j;
36 for ( i = 1; i < n; ++i )
37 {
38 T t = a[i];
39 for ( j = i; j > 0 && a[j-1] > t; --j )
40 a[j] = a[j-1];
41 a[j] = t;
42 }
43}
44
45static void
46quicksort(T a[], int n)
47{
48 int i, last;
49
50 if ( n <= CUTOFF )
51 return;
52
53 swap(a, 0, bigrand() % n);
54
55 last = 0;
56 for ( i = 1; i < n; ++i )
57 if ( a[i] < a[0] )
58 swap(a, ++last, i);
59
60 swap(a, 0, last);
61
62 quicksort(a, last);
63 quicksort(a+last+1, n-last-1);
64}
65
66void
67my_quicksort(T a[], int n)
68{
69 quicksort(a, n);
70 insertsort(a, n);
71}
72
73
74static int
75cmp(const void *a, const void *b)
76{
77 const int *pa = (const T *) a;
78 const int *pb = (const T *) b;
79
80 if ( *pa < *pb ) return -1;
81 if ( *pa > *pb ) return 1;
82 return 0;
83}
84
85void
86c_quicksort(T a[], int n)
87{
88 qsort(a, n, sizeof(T), cmp);
89}
90
91/* This function takes last element as pivot, places
92 the pivot element at its correct position in sorted
93 array, and places all smaller (smaller than pivot)
94 to left of pivot and all greater elements to right
95 of pivot */
96int partition (int arr[], int low, int high)
97{
98 int pivot = arr[high]; // pivot
99 int i = (low - 1); // Index of smaller element
100
101 for (int j = low; j <= high- 1; j++)
102 {
103 // If current element is smaller than or
104 // equal to pivot
105 if (arr[j] <= pivot)
106 {
107 i++; // increment index of smaller element
108 swap(arr, i, j);
109 }
110 }
111 swap(arr, i + 1, high);
112 return (i + 1);
113}
114
115/* The main function that implements QuickSort
116 arr[] --> Array to be sorted,
117 low --> Starting index,
118 high --> Ending index */
119void quickSort(int arr[], int low, int high)
120{
121 while (low < high)
122 {
123 /* pi is partitioning index, arr[p] is now
124 at right place */
125 int pi = partition(arr, low, high);
126
127 if (pi - low < high - pi)
128 {
129 quickSort(arr, low, pi - 1);
130 low = pi + 1;
131 }
132 else
133 {
134 quickSort(arr, pi + 1, high);
135 high = pi - 1;
136 }
137 }
138}
139
140void g4g_quicksort(T a[], int n)
141{
142 quickSort(a, 0, n-1);
143}
144
145
146static void three_way_quicksort(int a[], int l, int r)
147{
148 int k;
149 T v = a[r];
150
151 if ( r <= l )
152 return;
153
154 int i = l-1, j = r, p = l-1, q = r;
155
156 for ( ;; ) {
157 while ( a[++i] < v )
158 ;
159 while ( v < a[--j] )
160 if ( j == l )
161 break;
162 if ( i >= j )
163 break;
164
165 swap(a, i, j);
166
167 if ( a[i] == v )
168 swap(a, ++p, i);
169 if ( v == a[j] )
170 swap(a, --q, j);
171 }
172 swap(a, i, r); j = i-1; i = i+1;
173
174 for ( k = l ; k <= p; ++k, --j )
175 swap(a, k, j);
176 for ( k = r-1; k >= q; --k, ++i )
177 swap(a, k, i);
178
179 three_way_quicksort(a, l, j);
180 three_way_quicksort(a, i, r);
181}
182
183void sed_quicksort(int a[], int n)
184{
185 three_way_quicksort(a, 0, n-1);
186}
187
188/* ====================== HEAPSORT ======================= */
189
190#define LEFT(idx) (idx*2+1)
191#define RIGHT(idx) (idx*2+2)
192#define PARENT(idx) ((idx-1)/2)
193
194static void
195fixdown(T heap[], int i, int n)
196{
197 for ( ;; ) {
198 const int l = LEFT(i);
199 const int r = RIGHT(i);
200 int m = i;
201
202 if ( l < n && heap[m] < heap[l] )
203 m = l;
204
205 if ( r < n && heap[m] < heap[r] )
206 m = r;
207
208 if ( m == i )
209 break;
210
211 swap(heap, m, i);
212
213 i = m;
214 }
215}
216
217static void
218heapify(T heap[], int n)
219{
220 for ( int i = n / 2 - 1; i >= 0; --i )
221 fixdown(heap, i, n);
222}
223
224void
225my_heapsort(T a[], int n)
226{
227 heapify(a, n);
228
229 for ( int i = n-1; i >= 0; --i ) {
230 swap(a, 0, i);
231 fixdown(a, 0, i);
232 }
233}
234
235void
236heapsort_bu( T * data, int n ) // zu sortierendes Feld und seine Länge
237{
238 T val;
239 int parent, child;
240 int root= n >> 1; // erstes Blatt im Baum
241 int count= 0; // Zähler für Anzahl der Vergleiche
242
243 for ( ; ; )
244 {
245 if ( root ) { // Teil 1: Konstruktion des Heaps
246 parent= --root;
247 val= data[root]; // zu versickernder Wert
248 }
249 else
250 if ( --n ) { // Teil 2: eigentliche Sortierung
251 val= data[n]; // zu versickernder Wert vom Heap-Ende
252 data[n]= data[0]; // Spitze des Heaps hinter den Heap in
253 parent= 0; // den sortierten Bereich verschieben
254 }
255 else // Heap ist leer; Sortierung beendet
256 break;
257
258 while ( (child= (parent + 1) << 1) < n ) // zweites (!) Kind;
259 { // Abbruch am Ende des Heaps
260 if ( ++count, data[child-1] > data[child] ) // größeres Kind wählen
261 --child;
262
263 data[parent]= data[child]; // größeres Kind nach oben rücken
264 parent= child; // in der Ebene darunter weitersuchen
265 }
266
267 if ( child == n ) // ein einzelnes Kind am Heap-Ende
268 { // ist übersprungen worden
269 if ( ++count, data[--child] >= val ) { // größer als der zu versick-
270 data[parent]= data[child]; // ernde Wert, also noch nach oben
271 data[child]= val; // versickerten Wert eintragen
272 continue;
273 }
274
275 child= parent; // 1 Ebene nach oben zurück
276 }
277 else
278 {
279 if ( ++count, data[parent] >= val ) { // das Blatt ist größer als der
280 data[parent]= val; // zu versickernde Wert, der damit
281 continue; // direkt eingetragen werden kann
282 }
283
284 child= (parent - 1) >> 1; // 2 Ebenen nach oben zurück
285 }
286
287 while ( child != root ) // maximal zum Ausgangspunkt zurück
288 {
289 parent= (child - 1) >> 1; // den Vergleichswert haben wir bereits
290 // nach oben verschoben
291 if ( ++count, data[parent] >= val ) // größer als der zu versickernde
292 break; // Wert, also Position gefunden
293
294 data[child]= data[parent]; // Rückverschiebung nötig
295 child= parent; // 1 Ebene nach oben zurück
296 }
297
298 data[child]= val; // versickerten Wert eintragen
299 }
300}
301
302/*----------------------------------------------------------------------*/
303/* BOTTOM-UP HEAPSORT */
304/* Written by J. Teuhola <teuhola@cs.utu.fi>; the original idea is */
305/* probably due to R.W. Floyd. Thereafter it has been used by many */
306/* authors, among others S. Carlsson and I. Wegener. Building the heap */
307/* bottom-up is also due to R. W. Floyd: Treesort 3 (Algorithm 245), */
308/* Communications of the ACM 7, p. 701, 1964. */
309/*----------------------------------------------------------------------*/
310
311#define element float
312
313/*-----------------------------------------------------------------------*/
314/* The sift-up procedure sinks a hole from v[i] to leaf and then sifts */
315/* the original v[i] element from the leaf level up. This is the main */
316/* idea of bottom-up heapsort. */
317/*-----------------------------------------------------------------------*/
318static void siftup(T v[], int i, int n)
319{
320 int j, start;
321 T x;
322
323 start = i;
324 x = v[i];
325 j = i<<1;
326 while (j<=n)
327 {
328 if (j<n)
329 if (v[j]<v[j+1])
330 j++;
331 v[i] = v[j];
332 i = j; j = i<<1;
333 }
334 j = i>>1;
335 while (j>=start)
336 { if (v[j]<x)
337 { v[i] = v[j];
338 i = j; j = i>>1;
339 }
340 else break;
341 }
342 v[i] = x;
343} /* End of siftup */
344
345/*----------------------------------------------------------------------*/
346/* The heapsort procedure; the original array is r[0..n-1], but here */
347/* it is shifted to vector v[1..n], for convenience. */
348/*----------------------------------------------------------------------*/
349void bottom_up_heapsort(T r[], int n)
350{
351 int k;
352 T x;
353 T *v;
354
355 v = r-1; /* The address shift */
356
357/* Build the heap bottom-up, using siftup. */
358 for (k=n>>1; k>1; k--) siftup(v, k, n);
359
360/* The main loop of sorting follows. The root is swapped with the last */
361/* leaf after each sift-up. */
362 for (k=n; k>1; k--)
363 {
364 siftup(v, 1, k);
365 x = v[k]; v[k] = v[1]; v[1] = x;
366 }
367} /* End of bottom_up_heapsort */
368
369
370
371/* ====================== HEAPSORT ======================= */
372
373/* ====================== INTROSORT ======================= */
374
375
376
377static void
378introsort(T a[], int n, int h)
379{
380 int i, last;
381
382 if ( n <= CUTOFF )
383 return;
384
385 if ( --h == 1 ) {
386 my_heapsort(a, n);
387 return;
388 }
389
390 swap(a, 0, bigrand() % n);
391
392 last = 0;
393 for ( i = 1; i < n; ++i )
394 if ( a[i] < a[0] )
395 swap(a, ++last, i);
396
397 swap(a, 0, last);
398
399 introsort(a, last, h);
400 introsort(a+last+1, n-last-1, h);
401}
402
403void
404my_introsort(T a[], int n)
405{
406 int h = 1;
407
408 for ( int nn = 1; nn < n; nn <<= 1 )
409 ++h;
410
411 introsort(a, n, h);
412 insertsort(a, n);
413}
414
415static void pp_quicksort_impl(T a[], int l, int u)
416{
417 if ( u - l < CUTOFF )
418 return;
419
420 swap(a, l, randint(l, u));
421
422 T t = a[l];
423 int i = l;
424 int j = u+1;
425 for (;;) {
426 do i++; while ( /*i <= u &&*/ a[i] < t );
427 do j--; while ( a[j] > t );
428 if ( i > j )
429 break;
430 swap(a, i, j);
431 }
432 swap(a, l, j);
433 pp_quicksort_impl(a, l, j-1);
434 pp_quicksort_impl(a, j+1, u);
435}
436
437void
438pp_quicksort(T a[], int n)
439{
440 pp_quicksort_impl(a, 0, n-1);
441 insertsort(a, n);
442}
443
444static void pp_quicksort_impl_it(T a[], int l, int u, int h)
445{
446 if ( --h == 1 ) {
447 my_heapsort(a+l, u-l+1);
448 return;
449 }
450
451 while ( u-l >= CUTOFF )
452 {
453 swap(a, l, randint(l, u));
454
455 T t = a[l];
456 int i = l;
457 int j = u+1;
458
459 for (;;) {
460 do i++; while ( /*i <= u && */ a[i] < t );
461 do j--; while ( a[j] > t );
462 if ( i > j )
463 break;
464 swap(a, i, j);
465 }
466 swap(a, l, j);
467
468 if ( j - l < u - j )
469 {
470 pp_quicksort_impl_it(a, l, j-1, h);
471 l = j + 1;
472 }
473 else
474 {
475 pp_quicksort_impl_it(a, j+1, u, h);
476 u = j - 1;
477 }
478 }
479}
480
481void
482pp_quicksort_it(T a[], int n)
483{
484 int h = 1;
485
486 for ( int nn = 1; nn < n; nn <<= 1 )
487 ++h;
488
489 pp_quicksort_impl_it(a, 0, n-1, h);
490 insertsort(a, n);
491}
492
493int
494binary_search(T x, T v[], int n)
495{
496 int low, high;
497
498 low = 0;
499 high = n-1;
500 while ( low <= high ) {
501 int mid = low + ((high - low) / 2);
502 if ( x > v[mid] )
503 low = mid + 1;
504 else if ( x < v[mid] )
505 high = mid - 1;
506 else
507 return mid;
508 }
509 return -1;
510}
511
512int
513lower_bound(T x, T v[], int n)
514{
515 int low, high;
516
517 low = 0;
518 high = n;
519 while ( low < high ) {
520 int mid = low + ((high - low) / 2);
521
522 if ( x > v[mid] )
523 low = mid + 1;
524 else
525 high = mid;
526 }
527 return x == v[low] ? low : -1;
528}
529
530int
531upper_bound(T x, T v[], int n)
532{
533 int low, high;
534
535 low = 0;
536 high = n;
537 while ( low < high ) {
538 int mid = low + ((high - low) / 2);
539
540 if ( x >= v[mid] )
541 low = mid + 1;
542 else
543 high = mid;
544 }
545 return ( low > 0 && x == v[low-1] ) ? low-1 : -1;
546}
547
548/* TESTTREIBER */
549
550
551void gen_testset_random(T a[], int n)
552{
553 for ( int i = 0; i < n; ++i )
554 a[i] = bigrand();
555}
556
557void gen_testset_random2(T a[], int n)
558{
559 for ( int i = 0; i < n; ++i )
560 a[i] = bigrand() % 100;
561}
562
563void gen_testset_asc(T a[], int n)
564{
565 for ( int i = 0; i < n; ++i )
566 a[i] = i;
567}
568
569void gen_testset_desc(T a[], int n)
570{
571 for ( int i = n; i >= 0; --i )
572 a[i] = i;
573}
574
575void gen_testset_unique(T a[], int n)
576{
577 for ( int i = 0; i < n; ++i )
578 a[i] = 1;
579}
580
581void test_sorting(T a[], int n)
582{
583 for ( int i = 1; i < n; ++i )
584 if ( a[i-1] > a[i] ) {
585 puts("Fehler!");
586 exit(EXIT_SUCCESS);
587 }
588}
589
590void do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[], int n))
591{
592 T *a;
593 clock_t start, ende;
594
595 a = malloc(sizeof(T) * n);
596
597 (*gen_testset)(a, n);
598
599 start = clock();
600 (*do_sort)(a, n);
601 ende = clock();
602
603 test_sorting(a, n);
604
605 free(a);
606
607 printf("%10.3lf sec", ((double) ende - start) / CLOCKS_PER_SEC);
608 fflush(stdout);
609}
610
611void do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n))
612{
613 printf("%-15.15s n=%-10d: ", msg, n);
614 do_one_test(n, do_sort, gen_testset_random);
615 do_one_test(n, do_sort, gen_testset_random2);
616 do_one_test(n, do_sort, gen_testset_asc);
617 do_one_test(n, do_sort, gen_testset_desc);
618 do_one_test(n, do_sort, gen_testset_unique);
619 putchar('\n');
620}
621
622/* ENDE TESTTREIBER */
623
624int main(void)
625{
626 const int n = 20000000;
627
628 srand(time(0));
629 do_all_tests("my_heapsort", n, my_heapsort);
630 do_all_tests("heapsort_bu", n, heapsort_bu);
631 do_all_tests("bottom_up_heapsort", n, bottom_up_heapsort);
632 do_all_tests("c_quicksort", n, c_quicksort);
633 //do_all_tests("g4g_quicksort", n, g4g_quicksort);
634 //do_all_tests("sed_quicksort", n, sed_quicksort);
635 do_all_tests("my_introsort", n, my_introsort);
636 //do_all_tests("my_quicksort", n, my_quicksort);
637 do_all_tests("pp_quicksort", n, pp_quicksort);
638 do_all_tests("pp_quicksort_it", n, pp_quicksort_it);
639
640 return 0;
641}
642
643#if 0
644int _main(void)
645{
646 T array[20];
647
648 for ( int i = 0; i != NELEM(array); ++i )
649 array[i] = rand() % 10;
650
651 sort(array, NELEM(array));
652 print(array, NELEM(array));
653
654 int value;
655 while ( scanf("%d", &value) == 1 && value != -1 ) {
656 int bs = binary_search(value, array, NELEM(array));
657 int lb = lower_bound(value, array, NELEM(array));
658 int ub = upper_bound(value, array, NELEM(array));
659
660 printf("bs: %d - lb: %d - ub: %d\n", bs, lb, ub);
661 }
662
663 return EXIT_SUCCESS;
664}
665#endif
666
diff --git a/random.h b/random.h
new file mode 100644
index 0000000..9094d5b
--- /dev/null
+++ b/random.h
@@ -0,0 +1,47 @@
1#ifndef ITS1_RANDOM_H_INCLUDED
2#define ITS1_RANDOM_H_INCLUDED
3
4#ifdef __cplusplus
5extern "C" {
6#endif
7
8struct random_ctx {
9 unsigned char (*get_byte)(struct random_ctx *ctx);
10};
11
12static unsigned char
13random_get_byte(struct random_ctx *ctx)
14{
15 return ctx->get_byte(ctx);
16}
17
18static unsigned short
19random_get_word(struct random_ctx *ctx)
20{
21 return (ctx->get_byte(ctx) << 8)
22 | ctx->get_byte(ctx)
23 ;
24}
25
26static unsigned long
27random_get_dword(struct random_ctx *ctx)
28{
29 return (ctx->get_byte(ctx) << 24)
30 | (ctx->get_byte(ctx) << 16)
31 | (ctx->get_byte(ctx) << 8)
32 | ctx->get_byte(ctx)
33 ;
34}
35
36static unsigned long
37random_get_dword_range(struct random_ctx *ctx, unsigned long l, unsigned long u)
38{
39 return l + random_get_dword(ctx) % (u - l + 1);
40}
41
42#ifdef __cplusplus
43}
44#endif
45
46#endif /* ITS1_RANDOM_H_INCLUDED */
47
diff --git a/rb.c b/rb.c
new file mode 100644
index 0000000..c95ab83
--- /dev/null
+++ b/rb.c
@@ -0,0 +1,661 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <time.h>
4#include "util.h"
5
6typedef int T;
7
8#if 0
9struct rbtree {
10 T data;
11 enum { RED, BLACK } color;
12 struct rbtree *left, *right, *p;
13};
14
15struct rbtree *
16rb_alloc(T data)
17{
18 struct rbtree *node = malloc(sizeof *node);
19 if ( node )
20 {
21 node->data = data;
22 node->left = NULL;
23 node->right = NULL;
24 node->p = NULL;
25 }
26 return node;
27}
28
29void
30rb_left_rotate(struct rbtree **root, struct rbtree *x)
31{
32 struct rbtree *y = x->right;
33 x->right = y->left;
34 if ( y->left )
35 y->left->p = x;
36
37 y->p = x->p;
38 if ( x->p == NULL )
39 *root = y;
40 else if ( x == x->p->left )
41 x->p->left = y;
42 else
43 x->p->right = y;
44
45 y->left = x;
46 x->p = y;
47}
48
49void
50rb_right_rotate(struct rbtree **root, struct rbtree *y)
51{
52 struct rbtree *x = y->left;
53 y->left = x->right;
54 if ( x->right )
55 x->right->p = y;
56
57 x->p = y->p;
58 if ( y->p == NULL )
59 *root = x;
60 else if ( y == y->p->left )
61 y->p->left = x;
62 else
63 y->p->right = x;
64
65 x->right = y;
66 y->p = x;
67}
68
69void
70rb_insert_fixup(struct rbtree **root, struct rbtree **z)
71{
72 struct rbtree *y;
73
74 while ( z->p->color == RED ) {
75 if ( z->p == z->p->p->left ) {
76 y = z->p->p->right;
77 if ( y->color == RED ) {
78 z->p->color = BLACK;
79 y->color = BLACK;
80 z->p->p->color = RED;
81 z = z->p->p;
82 }
83 else {
84 if ( z == z->p->right ) {
85 z = z->p;
86 rb_left_rotate(root, z);
87 }
88 z->p->color = BLACK;
89 z->p->p->color = RED;
90 rb_right_rotate(root, z->p->p);
91 }
92 }
93 else {
94 y = z->p->p->left;
95 if ( y->color == RED ) {
96 z->p->color = BLACK;
97 y->color = BLACK;
98 z->p->p->color = RED;
99 z = z->p->p;
100 }
101 else {
102 if ( z == z->p->left ) {
103 z = z->p;
104 rb_right_rotate(root, z);
105 }
106 z->p->color = BLACK;
107 z->p->p->color = RED;
108 rb_left_rotate(root, z->p->p);
109 }
110 }
111 }
112
113 (*root)->color = BLACK;
114}
115
116void
117rb_insert_node(struct rbtree **root, T data)
118{
119 struct rbtree *z = rb_alloc(data);
120
121 if ( *root == NULL ) {
122 z->color = BLACK;
123 *root = z;
124 }
125 else {
126 struct rbtree *y = NULL;
127 struct rbtree *x = *root;
128
129 while ( x ) {
130 y = x;
131 if ( z->data < x->data )
132 x = x->left;
133 else
134 x = x->right;
135 }
136 z->p = y;
137
138 if ( y == NULL ) // kann entfallen!
139 *root = z;
140 else if ( z->data < y->data )
141 y->left = z;
142 else
143 y->right = z;
144
145 z->left = NULL; // kann entfallen!
146 z->right = NULL; // kann entfallen!
147 z->color = RED;
148
149 rb_insert_fixup(root, &z);
150 }
151}
152
153#endif
154
155
156
157/* The authors of this work have released all rights to it and placed it
158in the public domain under the Creative Commons CC0 1.0 waiver
159(http://creativecommons.org/publicdomain/zero/1.0/).
160
161THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
162EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
163MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
164IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
165CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
166TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
167SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
168
169Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
170*/
171
172enum rbtree_node_color { RED, BLACK };
173
174typedef struct rbtree_node_t {
175void* key;
176void* value;
177struct rbtree_node_t* left;
178struct rbtree_node_t* right;
179struct rbtree_node_t* parent;
180enum rbtree_node_color color;
181} *rbtree_node;
182
183typedef struct rbtree_t {
184rbtree_node root;
185} *rbtree;
186
187typedef int (*compare_func)(void* left, void* right);
188
189rbtree rbtree_create();
190void* rbtree_lookup(rbtree t, void* key, compare_func compare);
191void rbtree_insert(rbtree t, void* key, void* value, compare_func compare);
192void rbtree_delete(rbtree t, void* key, compare_func compare);
193
194
195#include <assert.h>
196#include <stdlib.h>
197
198typedef rbtree_node node;
199typedef enum rbtree_node_color color;
200
201static node grandparent(node n);
202static node sibling(node n);
203static node uncle(node n);
204static void verify_properties(rbtree t);
205static void verify_property_1(node root);
206static void verify_property_2(node root);
207static color node_color(node n);
208static void verify_property_4(node root);
209static void verify_property_5(node root);
210static void verify_property_5_helper(node n, int black_count, int* black_count_path);
211
212static node new_node(void* key, void* value, color node_color, node left, node right);
213static node lookup_node(rbtree t, void* key, compare_func compare);
214static void rotate_left(rbtree t, node n);
215static void rotate_right(rbtree t, node n);
216
217static void replace_node(rbtree t, node oldn, node newn);
218static void insert_case1(rbtree t, node n);
219static void insert_case2(rbtree t, node n);
220static void insert_case3(rbtree t, node n);
221static void insert_case4(rbtree t, node n);
222static void insert_case5(rbtree t, node n);
223static node maximum_node(node root);
224static void delete_case1(rbtree t, node n);
225static void delete_case2(rbtree t, node n);
226static void delete_case3(rbtree t, node n);
227static void delete_case4(rbtree t, node n);
228static void delete_case5(rbtree t, node n);
229static void delete_case6(rbtree t, node n);
230
231node grandparent(node n) {
232 assert (n != NULL);
233 assert (n->parent != NULL); /* Not the root node */
234 assert (n->parent->parent != NULL); /* Not child of root */
235 return n->parent->parent;
236}
237node sibling(node n) {
238 assert (n != NULL);
239 assert (n->parent != NULL); /* Root node has no sibling */
240 if (n == n->parent->left)
241 return n->parent->right;
242 else
243 return n->parent->left;
244}
245node uncle(node n) {
246 assert (n != NULL);
247 assert (n->parent != NULL); /* Root node has no uncle */
248 assert (n->parent->parent != NULL); /* Children of root have no uncle */
249 return sibling(n->parent);
250}
251void verify_properties(rbtree t) {
252#ifdef VERIFY_RBTREE
253 verify_property_1(t->root);
254 verify_property_2(t->root);
255 /* Property 3 is implicit */
256 verify_property_4(t->root);
257 verify_property_5(t->root);
258#endif
259}
260void verify_property_1(node n) {
261 assert(node_color(n) == RED || node_color(n) == BLACK);
262 if (n == NULL) return;
263 verify_property_1(n->left);
264 verify_property_1(n->right);
265}
266void verify_property_2(node root) {
267 assert(node_color(root) == BLACK);
268}
269color node_color(node n) {
270 return n == NULL ? BLACK : n->color;
271}
272void verify_property_4(node n) {
273 if (node_color(n) == RED) {
274 assert (node_color(n->left) == BLACK);
275 assert (node_color(n->right) == BLACK);
276 assert (node_color(n->parent) == BLACK);
277 }
278 if (n == NULL) return;
279 verify_property_4(n->left);
280 verify_property_4(n->right);
281}
282void verify_property_5(node root) {
283 int black_count_path = -1;
284 verify_property_5_helper(root, 0, &black_count_path);
285}
286
287void verify_property_5_helper(node n, int black_count, int* path_black_count) {
288 if (node_color(n) == BLACK) {
289 black_count++;
290 }
291 if (n == NULL) {
292 if (*path_black_count == -1) {
293 *path_black_count = black_count;
294 } else {
295 assert (black_count == *path_black_count);
296 }
297 return;
298 }
299 verify_property_5_helper(n->left, black_count, path_black_count);
300 verify_property_5_helper(n->right, black_count, path_black_count);
301}
302rbtree rbtree_create() {
303 rbtree t = malloc(sizeof(struct rbtree_t));
304 t->root = NULL;
305 verify_properties(t);
306 return t;
307}
308node new_node(void* key, void* value, color node_color, node left, node right) {
309 node result = malloc(sizeof(struct rbtree_node_t));
310 result->key = key;
311 result->value = value;
312 result->color = node_color;
313 result->left = left;
314 result->right = right;
315 if (left != NULL) left->parent = result;
316 if (right != NULL) right->parent = result;
317 result->parent = NULL;
318 return result;
319}
320node lookup_node(rbtree t, void* key, compare_func compare) {
321 node n = t->root;
322 while (n != NULL) {
323 int comp_result = compare(key, n->key);
324 if (comp_result == 0) {
325 return n;
326 } else if (comp_result < 0) {
327 n = n->left;
328 } else {
329 assert(comp_result > 0);
330 n = n->right;
331 }
332 }
333 return n;
334}
335void* rbtree_lookup(rbtree t, void* key, compare_func compare) {
336 node n = lookup_node(t, key, compare);
337 return n == NULL ? NULL : n->value;
338}
339void rotate_left(rbtree t, node n) {
340 node r = n->right;
341 replace_node(t, n, r);
342 n->right = r->left;
343 if (r->left != NULL) {
344 r->left->parent = n;
345 }
346 r->left = n;
347 n->parent = r;
348}
349
350void rotate_right(rbtree t, node n) {
351 node L = n->left;
352 replace_node(t, n, L);
353 n->left = L->right;
354 if (L->right != NULL) {
355 L->right->parent = n;
356 }
357 L->right = n;
358 n->parent = L;
359}
360void replace_node(rbtree t, node oldn, node newn) {
361 if (oldn->parent == NULL) {
362 t->root = newn;
363 } else {
364 if (oldn == oldn->parent->left)
365 oldn->parent->left = newn;
366 else
367 oldn->parent->right = newn;
368 }
369 if (newn != NULL) {
370 newn->parent = oldn->parent;
371 }
372}
373void rbtree_insert(rbtree t, void* key, void* value, compare_func compare) {
374 node inserted_node = new_node(key, value, RED, NULL, NULL);
375 if (t->root == NULL) {
376 t->root = inserted_node;
377 } else {
378 node n = t->root;
379 while (1) {
380 int comp_result = compare(key, n->key);
381 if (comp_result == 0) {
382 n->value = value;
383 return;
384 } else if (comp_result < 0) {
385 if (n->left == NULL) {
386 n->left = inserted_node;
387 break;
388 } else {
389 n = n->left;
390 }
391 } else {
392 assert (comp_result > 0);
393 if (n->right == NULL) {
394 n->right = inserted_node;
395 break;
396 } else {
397 n = n->right;
398 }
399 }
400 }
401 inserted_node->parent = n;
402 }
403 insert_case1(t, inserted_node);
404 verify_properties(t);
405}
406void insert_case1(rbtree t, node n) {
407 if (n->parent == NULL)
408 n->color = BLACK;
409 else
410 insert_case2(t, n);
411}
412void insert_case2(rbtree t, node n) {
413 if (node_color(n->parent) == BLACK)
414 return; /* Tree is still valid */
415 else
416 insert_case3(t, n);
417}
418void insert_case3(rbtree t, node n) {
419 if (node_color(uncle(n)) == RED) {
420 n->parent->color = BLACK;
421 uncle(n)->color = BLACK;
422 grandparent(n)->color = RED;
423 insert_case1(t, grandparent(n));
424 } else {
425 insert_case4(t, n);
426 }
427}
428void insert_case4(rbtree t, node n) {
429 if (n == n->parent->right && n->parent == grandparent(n)->left) {
430 rotate_left(t, n->parent);
431 n = n->left;
432 } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
433 rotate_right(t, n->parent);
434 n = n->right;
435 }
436 insert_case5(t, n);
437}
438void insert_case5(rbtree t, node n) {
439 n->parent->color = BLACK;
440 grandparent(n)->color = RED;
441 if (n == n->parent->left && n->parent == grandparent(n)->left) {
442 rotate_right(t, grandparent(n));
443 } else {
444 assert (n == n->parent->right && n->parent == grandparent(n)->right);
445 rotate_left(t, grandparent(n));
446 }
447}
448void rbtree_delete(rbtree t, void* key, compare_func compare) {
449 node child;
450 node n = lookup_node(t, key, compare);
451 if (n == NULL) return; /* Key not found, do nothing */
452 if (n->left != NULL && n->right != NULL) {
453 /* Copy key/value from predecessor and then delete it instead */
454 node pred = maximum_node(n->left);
455 n->key = pred->key;
456 n->value = pred->value;
457 n = pred;
458 }
459
460 assert(n->left == NULL || n->right == NULL);
461 child = n->right == NULL ? n->left : n->right;
462 if (node_color(n) == BLACK) {
463 n->color = node_color(child);
464 delete_case1(t, n);
465 }
466 replace_node(t, n, child);
467 if (n->parent == NULL && child != NULL) // root should be black
468 child->color = BLACK;
469 free(n);
470
471 verify_properties(t);
472}
473static node maximum_node(node n) {
474 assert (n != NULL);
475 while (n->right != NULL) {
476 n = n->right;
477 }
478 return n;
479}
480void delete_case1(rbtree t, node n) {
481 if (n->parent == NULL)
482 return;
483 else
484 delete_case2(t, n);
485}
486void delete_case2(rbtree t, node n) {
487 if (node_color(sibling(n)) == RED) {
488 n->parent->color = RED;
489 sibling(n)->color = BLACK;
490 if (n == n->parent->left)
491 rotate_left(t, n->parent);
492 else
493 rotate_right(t, n->parent);
494 }
495 delete_case3(t, n);
496}
497void delete_case3(rbtree t, node n) {
498 if (node_color(n->parent) == BLACK &&
499 node_color(sibling(n)) == BLACK &&
500 node_color(sibling(n)->left) == BLACK &&
501 node_color(sibling(n)->right) == BLACK)
502 {
503 sibling(n)->color = RED;
504 delete_case1(t, n->parent);
505 }
506 else
507 delete_case4(t, n);
508}
509void delete_case4(rbtree t, node n) {
510 if (node_color(n->parent) == RED &&
511 node_color(sibling(n)) == BLACK &&
512 node_color(sibling(n)->left) == BLACK &&
513 node_color(sibling(n)->right) == BLACK)
514 {
515 sibling(n)->color = RED;
516 n->parent->color = BLACK;
517 }
518 else
519 delete_case5(t, n);
520}
521void delete_case5(rbtree t, node n) {
522 if (n == n->parent->left &&
523 node_color(sibling(n)) == BLACK &&
524 node_color(sibling(n)->left) == RED &&
525 node_color(sibling(n)->right) == BLACK)
526 {
527 sibling(n)->color = RED;
528 sibling(n)->left->color = BLACK;
529 rotate_right(t, sibling(n));
530 }
531 else if (n == n->parent->right &&
532 node_color(sibling(n)) == BLACK &&
533 node_color(sibling(n)->right) == RED &&
534 node_color(sibling(n)->left) == BLACK)
535 {
536 sibling(n)->color = RED;
537 sibling(n)->right->color = BLACK;
538 rotate_left(t, sibling(n));
539 }
540 delete_case6(t, n);
541}
542void delete_case6(rbtree t, node n) {
543 sibling(n)->color = node_color(n->parent);
544 n->parent->color = BLACK;
545 if (n == n->parent->left) {
546 assert (node_color(sibling(n)->right) == RED);
547 sibling(n)->right->color = BLACK;
548 rotate_left(t, n->parent);
549 }
550 else
551 {
552 assert (node_color(sibling(n)->left) == RED);
553 sibling(n)->left->color = BLACK;
554 rotate_right(t, n->parent);
555 }
556}
557
558
559
560/* The authors of this work have released all rights to it and placed it
561in the public domain under the Creative Commons CC0 1.0 waiver
562(http://creativecommons.org/publicdomain/zero/1.0/).
563
564THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
565EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
566MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
567IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
568CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
569TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
570SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
571
572Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
573*/
574
575#include <stdio.h>
576#include <assert.h>
577#include <stdlib.h> /* rand() */
578
579static int compare_int(void* left, void* right);
580static void print_tree(rbtree t);
581static void print_tree_helper(rbtree_node n, int indent);
582
583int compare_int(void* leftp, void* rightp) {
584 int left = (int)leftp;
585 int right = (int)rightp;
586 if (left < right)
587 return -1;
588 else if (left > right)
589 return 1;
590 else {
591 assert (left == right);
592 return 0;
593 }
594}
595
596#define INDENT_STEP 4
597
598void print_tree_helper(rbtree_node n, int indent);
599
600void print_tree(rbtree t) {
601 print_tree_helper(t->root, 0);
602 puts("");
603}
604
605void print_tree_helper(rbtree_node n, int indent) {
606 int i;
607 if (n == NULL) {
608 fputs("<empty tree>", stdout);
609 return;
610 }
611 if (n->right != NULL) {
612 print_tree_helper(n->right, indent + INDENT_STEP);
613 }
614 for(i=0; i<indent; i++)
615 fputs(" ", stdout);
616 if (n->color == BLACK)
617 printf("%d\n", (int)n->key);
618 else
619 printf("<%d>\n", (int)n->key);
620 if (n->left != NULL) {
621 print_tree_helper(n->left, indent + INDENT_STEP);
622 }
623}
624
625int main() {
626 int i;
627 rbtree t = rbtree_create();
628 print_tree(t);
629
630 for(i=0; i<5000; i++) {
631 long x = rand() % 10000;
632 long y = rand() % 10000;
633#ifdef TRACE
634 print_tree(t);
635 printf("Inserting %d -> %d\n\n", x, y);
636#endif
637 rbtree_insert(t, (void*)x, (void*)y, compare_int);
638 assert(rbtree_lookup(t, (void*)x, compare_int) == (void*)y);
639 }
640 for(i=0; i<60000; i++) {
641 long x = rand() % 10000;
642#ifdef TRACE
643 print_tree(t);
644 printf("Deleting key %d\n\n", x);
645#endif
646 rbtree_delete(t, (void*)x, compare_int);
647 }
648 return 0;
649}
650
651#if 0
652int main__(void)
653{
654 struct rbtree *tree = NULL;
655
656 srand(time(NULL));
657 for ( int i = 0; i != 10; ++i )
658 rb_insert_node(&tree, rand());
659
660}
661#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 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h> /* memset() */
4#include "util.h"
5
6#include "random.h"
7
8struct rc4_ctx {
9 struct random_ctx ctx;
10
11 unsigned int i;
12 unsigned int j;
13 unsigned char S[256];
14};
15
16static void
17swap(unsigned char a[], unsigned int i, unsigned int j)
18{
19 unsigned char t = a[i]; a[i] = a[j]; a[j] = t;
20}
21
22unsigned char
23rc4_get_byte(struct rc4_ctx *ctx)
24{
25 ctx->i = (ctx->i + 1) % 256;
26 ctx->j = (ctx->j + ctx->S[ctx->i]) % 256;
27 swap(ctx->S, ctx->i, ctx->j);
28
29 return ctx->S[(ctx->S[ctx->i] + ctx->S[ctx->j]) % 256];
30}
31
32void
33rc4_init(struct rc4_ctx *ctx, void *key, size_t sz)
34{
35 const unsigned char *K = key;
36 unsigned int i, j;
37
38 for ( i = 0; i != 256; ++i )
39 ctx->S[i] = i;
40
41 for ( i = j = 0; i != 256; ++i ) {
42 j = (j + ctx->S[i] + K[i % sz]) % 256;
43 swap(ctx->S, i, j);
44 }
45
46 ctx->i = 0;
47 ctx->j = 0;
48 ctx->ctx.get_byte = (unsigned char (*)(struct random_ctx *)) rc4_get_byte;
49}
50
51void
52rc4_clear(struct rc4_ctx *ctx)
53{
54 memset(ctx, 0, sizeof *ctx);
55}
56
57struct random_ctx *
58rc4_create(void *key, size_t sz)
59{
60 struct rc4_ctx *ctx;
61
62 ctx = malloc(sizeof(*ctx));
63 if ( ctx != NULL ) {
64 rc4_init(ctx, key, sz);
65
66 return &(ctx->ctx);
67 }
68
69 return NULL;
70}
71
72void
73rc4_free(struct random_ctx *ctx)
74{
75 rc4_clear((struct rc4_ctx *) ctx);
76 free(ctx);
77}
78
79void
80rc4_test(void)
81{
82 static struct {
83 char *key;
84 unsigned int sz;
85 struct {
86 unsigned int pos;
87 unsigned char bytes[16];
88 } test[18];
89 } cases[] = {
90 {
91 "\x01\x02\x03\x04\x05", 5,
92 {
93 { 0, "\xb2\x39\x63\x05\xf0\x3d\xc0\x27\xcc\xc3\x52\x4a\x0a\x11\x18\xa8" },
94 { 16, "\x69\x82\x94\x4f\x18\xfc\x82\xd5\x89\xc4\x03\xa4\x7a\x0d\x09\x19" },
95 { 240, "\x28\xcb\x11\x32\xc9\x6c\xe2\x86\x42\x1d\xca\xad\xb8\xb6\x9e\xae" },
96 { 256, "\x1c\xfc\xf6\x2b\x03\xed\xdb\x64\x1d\x77\xdf\xcf\x7f\x8d\x8c\x93" },
97 { 496, "\x42\xb7\xd0\xcd\xd9\x18\xa8\xa3\x3d\xd5\x17\x81\xc8\x1f\x40\x41" },
98 { 512, "\x64\x59\x84\x44\x32\xa7\xda\x92\x3c\xfb\x3e\xb4\x98\x06\x61\xf6" },
99 { 752, "\xec\x10\x32\x7b\xde\x2b\xee\xfd\x18\xf9\x27\x76\x80\x45\x7e\x22" },
100 { 768, "\xeb\x62\x63\x8d\x4f\x0b\xa1\xfe\x9f\xca\x20\xe0\x5b\xf8\xff\x2b" },
101 { 1008, "\x45\x12\x90\x48\xe6\xa0\xed\x0b\x56\xb4\x90\x33\x8f\x07\x8d\xa5" },
102 { 1024, "\x30\xab\xbc\xc7\xc2\x0b\x01\x60\x9f\x23\xee\x2d\x5f\x6b\xb7\xdf" },
103 { 1520, "\x32\x94\xf7\x44\xd8\xf9\x79\x05\x07\xe7\x0f\x62\xe5\xbb\xce\xea" },
104 { 1536, "\xd8\x72\x9d\xb4\x18\x82\x25\x9b\xee\x4f\x82\x53\x25\xf5\xa1\x30" },
105 { 2032, "\x1e\xb1\x4a\x0c\x13\xb3\xbf\x47\xfa\x2a\x0b\xa9\x3a\xd4\x5b\x8b" },
106 { 2048, "\xcc\x58\x2f\x8b\xa9\xf2\x65\xe2\xb1\xbe\x91\x12\xe9\x75\xd2\xd7" },
107 { 3056, "\xf2\xe3\x0f\x9b\xd1\x02\xec\xbf\x75\xaa\xad\xe9\xbc\x35\xc4\x3c" },
108 { 3072, "\xec\x0e\x11\xc4\x79\xdc\x32\x9d\xc8\xda\x79\x68\xfe\x96\x56\x81" },
109 { 4080, "\x06\x83\x26\xa2\x11\x84\x16\xd2\x1f\x9d\x04\xb2\xcd\x1c\xa0\x50" },
110 { 4096, "\xff\x25\xb5\x89\x95\x99\x67\x07\xe5\x1f\xbd\xf0\x8b\x34\xd8\x75" }
111 }
112 },
113 {
114 "\x01\x02\x03\x04\x05\x06\x07", 7,
115 {
116 { 0, "\x29\x3f\x02\xd4\x7f\x37\xc9\xb6\x33\xf2\xaf\x52\x85\xfe\xb4\x6b" },
117 { 16, "\xe6\x20\xf1\x39\x0d\x19\xbd\x84\xe2\xe0\xfd\x75\x20\x31\xaf\xc1" },
118 { 240, "\x91\x4f\x02\x53\x1c\x92\x18\x81\x0d\xf6\x0f\x67\xe3\x38\x15\x4c" },
119 { 256, "\xd0\xfd\xb5\x83\x07\x3c\xe8\x5a\xb8\x39\x17\x74\x0e\xc0\x11\xd5" },
120 { 496, "\x75\xf8\x14\x11\xe8\x71\xcf\xfa\x70\xb9\x0c\x74\xc5\x92\xe4\x54" },
121 { 512, "\x0b\xb8\x72\x02\x93\x8d\xad\x60\x9e\x87\xa5\xa1\xb0\x79\xe5\xe4" },
122 { 752, "\xc2\x91\x12\x46\xb6\x12\xe7\xe7\xb9\x03\xdf\xed\xa1\xda\xd8\x66" },
123 { 768, "\x32\x82\x8f\x91\x50\x2b\x62\x91\x36\x8d\xe8\x08\x1d\xe3\x6f\xc2" },
124 { 1008, "\xf3\xb9\xa7\xe3\xb2\x97\xbf\x9a\xd8\x04\x51\x2f\x90\x63\xef\xf1" },
125 { 1024, "\x8e\xcb\x67\xa9\xba\x1f\x55\xa5\xa0\x67\xe2\xb0\x26\xa3\x67\x6f" },
126 { 1520, "\xd2\xaa\x90\x2b\xd4\x2d\x0d\x7c\xfd\x34\x0c\xd4\x58\x10\x52\x9f" },
127 { 1536, "\x78\xb2\x72\xc9\x6e\x42\xea\xb4\xc6\x0b\xd9\x14\xe3\x9d\x06\xe3" },
128 { 2032, "\xf4\x33\x2f\xd3\x1a\x07\x93\x96\xee\x3c\xee\x3f\x2a\x4f\xf0\x49" },
129 { 2048, "\x05\x45\x97\x81\xd4\x1f\xda\x7f\x30\xc1\xbe\x7e\x12\x46\xc6\x23" },
130 { 3056, "\xad\xfd\x38\x68\xb8\xe5\x14\x85\xd5\xe6\x10\x01\x7e\x3d\xd6\x09" },
131 { 3072, "\xad\x26\x58\x1c\x0c\x5b\xe4\x5f\x4c\xea\x01\xdb\x2f\x38\x05\xd5" },
132 { 4080, "\xf3\x17\x2c\xef\xfc\x3b\x3d\x99\x7c\x85\xcc\xd5\xaf\x1a\x95\x0c" },
133 { 4096, "\xe7\x4b\x0b\x97\x31\x22\x7f\xd3\x7c\x0e\xc0\x8a\x47\xdd\xd8\xb8" }
134 }
135 },
136 {
137 "\x01\x02\x03\x04\x05\x06\x07\x08", 8,
138 {
139 { 0, "\x97\xab\x8a\x1b\xf0\xaf\xb9\x61\x32\xf2\xf6\x72\x58\xda\x15\xa8" },
140 { 16, "\x82\x63\xef\xdb\x45\xc4\xa1\x86\x84\xef\x87\xe6\xb1\x9e\x5b\x09" },
141 { 240, "\x96\x36\xeb\xc9\x84\x19\x26\xf4\xf7\xd1\xf3\x62\xbd\xdf\x6e\x18" },
142 { 256, "\xd0\xa9\x90\xff\x2c\x05\xfe\xf5\xb9\x03\x73\xc9\xff\x4b\x87\x0a" },
143 { 496, "\x73\x23\x9f\x1d\xb7\xf4\x1d\x80\xb6\x43\xc0\xc5\x25\x18\xec\x63" },
144 { 512, "\x16\x3b\x31\x99\x23\xa6\xbd\xb4\x52\x7c\x62\x61\x26\x70\x3c\x0f" },
145 { 752, "\x49\xd6\xc8\xaf\x0f\x97\x14\x4a\x87\xdf\x21\xd9\x14\x72\xf9\x66" },
146 { 768, "\x44\x17\x3a\x10\x3b\x66\x16\xc5\xd5\xad\x1c\xee\x40\xc8\x63\xd0" },
147 { 1008, "\x27\x3c\x9c\x4b\x27\xf3\x22\xe4\xe7\x16\xef\x53\xa4\x7d\xe7\xa4" },
148 { 1024, "\xc6\xd0\xe7\xb2\x26\x25\x9f\xa9\x02\x34\x90\xb2\x61\x67\xad\x1d" },
149 { 1520, "\x1f\xe8\x98\x67\x13\xf0\x7c\x3d\x9a\xe1\xc1\x63\xff\x8c\xf9\xd3" },
150 { 1536, "\x83\x69\xe1\xa9\x65\x61\x0b\xe8\x87\xfb\xd0\xc7\x91\x62\xaa\xfb" },
151 { 2032, "\x0a\x01\x27\xab\xb4\x44\x84\xb9\xfb\xef\x5a\xbc\xae\x1b\x57\x9f" },
152 { 2048, "\xc2\xcd\xad\xc6\x40\x2e\x8e\xe8\x66\xe1\xf3\x7b\xdb\x47\xe4\x2c" },
153 { 3056, "\x26\xb5\x1e\xa3\x7d\xf8\xe1\xd6\xf7\x6f\xc3\xb6\x6a\x74\x29\xb3" },
154 { 3072, "\xbc\x76\x83\x20\x5d\x4f\x44\x3d\xc1\xf2\x9d\xda\x33\x15\xc8\x7b" },
155 { 4080, "\xd5\xfa\x5a\x34\x69\xd2\x9a\xaa\xf8\x3d\x23\x58\x9d\xb8\xc8\x5b" },
156 { 4096, "\x3f\xb4\x6e\x2c\x8f\x0f\x06\x8e\xdc\xe8\xcd\xcd\x7d\xfc\x58\x62" }
157 }
158 },
159 {
160 "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a", 10,
161 {
162 { 0, "\xed\xe3\xb0\x46\x43\xe5\x86\xcc\x90\x7d\xc2\x18\x51\x70\x99\x02" },
163 { 16, "\x03\x51\x6b\xa7\x8f\x41\x3b\xeb\x22\x3a\xa5\xd4\xd2\xdf\x67\x11" },
164 { 240, "\x3c\xfd\x6c\xb5\x8e\xe0\xfd\xde\x64\x01\x76\xad\x00\x00\x04\x4d" },
165 { 256, "\x48\x53\x2b\x21\xfb\x60\x79\xc9\x11\x4c\x0f\xfd\x9c\x04\xa1\xad" },
166 { 496, "\x3e\x8c\xea\x98\x01\x71\x09\x97\x90\x84\xb1\xef\x92\xf9\x9d\x86" },
167 { 512, "\xe2\x0f\xb4\x9b\xdb\x33\x7e\xe4\x8b\x8d\x8d\xc0\xf4\xaf\xef\xfe" },
168 { 752, "\x5c\x25\x21\xea\xcd\x79\x66\xf1\x5e\x05\x65\x44\xbe\xa0\xd3\x15" },
169 { 768, "\xe0\x67\xa7\x03\x19\x31\xa2\x46\xa6\xc3\x87\x5d\x2f\x67\x8a\xcb" },
170 { 1008, "\xa6\x4f\x70\xaf\x88\xae\x56\xb6\xf8\x75\x81\xc0\xe2\x3e\x6b\x08" },
171 { 1024, "\xf4\x49\x03\x1d\xe3\x12\x81\x4e\xc6\xf3\x19\x29\x1f\x4a\x05\x16" },
172 { 1520, "\xbd\xae\x85\x92\x4b\x3c\xb1\xd0\xa2\xe3\x3a\x30\xc6\xd7\x95\x99" },
173 { 1536, "\x8a\x0f\xed\xdb\xac\x86\x5a\x09\xbc\xd1\x27\xfb\x56\x2e\xd6\x0a" },
174 { 2032, "\xb5\x5a\x0a\x5b\x51\xa1\x2a\x8b\xe3\x48\x99\xc3\xe0\x47\x51\x1a" },
175 { 2048, "\xd9\xa0\x9c\xea\x3c\xe7\x5f\xe3\x96\x98\x07\x03\x17\xa7\x13\x39" },
176 { 3056, "\x55\x22\x25\xed\x11\x77\xf4\x45\x84\xac\x8c\xfa\x6c\x4e\xb5\xfc" },
177 { 3072, "\x7e\x82\xcb\xab\xfc\x95\x38\x1b\x08\x09\x98\x44\x21\x29\xc2\xf8" },
178 { 4080, "\x1f\x13\x5e\xd1\x4c\xe6\x0a\x91\x36\x9d\x23\x22\xbe\xf2\x5e\x3c" },
179 { 4096, "\x08\xb6\xbe\x45\x12\x4a\x43\xe2\xeb\x77\x95\x3f\x84\xdc\x85\x53" }
180 }
181 },
182 {
183 "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10", 16,
184 {
185 { 0, "\x9a\xc7\xcc\x9a\x60\x9d\x1e\xf7\xb2\x93\x28\x99\xcd\xe4\x1b\x97" },
186 { 16, "\x52\x48\xc4\x95\x90\x14\x12\x6a\x6e\x8a\x84\xf1\x1d\x1a\x9e\x1c" },
187 { 240, "\x06\x59\x02\xe4\xb6\x20\xf6\xcc\x36\xc8\x58\x9f\x66\x43\x2f\x2b" },
188 { 256, "\xd3\x9d\x56\x6b\xc6\xbc\xe3\x01\x07\x68\x15\x15\x49\xf3\x87\x3f" },
189 { 496, "\xb6\xd1\xe6\xc4\xa5\xe4\x77\x1c\xad\x79\x53\x8d\xf2\x95\xfb\x11" },
190 { 512, "\xc6\x8c\x1d\x5c\x55\x9a\x97\x41\x23\xdf\x1d\xbc\x52\xa4\x3b\x89" },
191 { 752, "\xc5\xec\xf8\x8d\xe8\x97\xfd\x57\xfe\xd3\x01\x70\x1b\x82\xa2\x59" },
192 { 768, "\xec\xcb\xe1\x3d\xe1\xfc\xc9\x1c\x11\xa0\xb2\x6c\x0b\xc8\xfa\x4d" },
193 { 1008, "\xe7\xa7\x25\x74\xf8\x78\x2a\xe2\x6a\xab\xcf\x9e\xbc\xd6\x60\x65" },
194 { 1024, "\xbd\xf0\x32\x4e\x60\x83\xdc\xc6\xd3\xce\xdd\x3c\xa8\xc5\x3c\x16" },
195 { 1520, "\xb4\x01\x10\xc4\x19\x0b\x56\x22\xa9\x61\x16\xb0\x01\x7e\xd2\x97" },
196 { 1536, "\xff\xa0\xb5\x14\x64\x7e\xc0\x4f\x63\x06\xb8\x92\xae\x66\x11\x81" },
197 { 2032, "\xd0\x3d\x1b\xc0\x3c\xd3\x3d\x70\xdf\xf9\xfa\x5d\x71\x96\x3e\xbd" },
198 { 2048, "\x8a\x44\x12\x64\x11\xea\xa7\x8b\xd5\x1e\x8d\x87\xa8\x87\x9b\xf5" },
199 { 3056, "\xfa\xbe\xb7\x60\x28\xad\xe2\xd0\xe4\x87\x22\xe4\x6c\x46\x15\xa3" },
200 { 3072, "\xc0\x5d\x88\xab\xd5\x03\x57\xf9\x35\xa6\x3c\x59\xee\x53\x76\x23" },
201 { 4080, "\xff\x38\x26\x5c\x16\x42\xc1\xab\xe8\xd3\xc2\xfe\x5e\x57\x2b\xf8" },
202 { 4096, "\xa3\x6a\x4c\x30\x1a\xe8\xac\x13\x61\x0c\xcb\xc1\x22\x56\xca\xcc" }
203 }
204 },
205 {
206 "\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,
207 {
208 { 0, "\x05\x95\xe5\x7f\xe5\xf0\xbb\x3c\x70\x6e\xda\xc8\xa4\xb2\xdb\x11" },
209 { 16, "\xdf\xde\x31\x34\x4a\x1a\xf7\x69\xc7\x4f\x07\x0a\xee\x9e\x23\x26" },
210 { 240, "\xb0\x6b\x9b\x1e\x19\x5d\x13\xd8\xf4\xa7\x99\x5c\x45\x53\xac\x05" },
211 { 256, "\x6b\xd2\x37\x8e\xc3\x41\xc9\xa4\x2f\x37\xba\x79\xf8\x8a\x32\xff" },
212 { 496, "\xe7\x0b\xce\x1d\xf7\x64\x5a\xdb\x5d\x2c\x41\x30\x21\x5c\x35\x22" },
213 { 512, "\x9a\x57\x30\xc7\xfc\xb4\xc9\xaf\x51\xff\xda\x89\xc7\xf1\xad\x22" },
214 { 752, "\x04\x85\x05\x5f\xd4\xf6\xf0\xd9\x63\xef\x5a\xb9\xa5\x47\x69\x82" },
215 { 768, "\x59\x1f\xc6\x6b\xcd\xa1\x0e\x45\x2b\x03\xd4\x55\x1f\x6b\x62\xac" },
216 { 1008, "\x27\x53\xcc\x83\x98\x8a\xfa\x3e\x16\x88\xa1\xd3\xb4\x2c\x9a\x02" },
217 { 1024, "\x93\x61\x0d\x52\x3d\x1d\x3f\x00\x62\xb3\xc2\xa3\xbb\xc7\xc7\xf0" },
218 { 1520, "\x96\xc2\x48\x61\x0a\xad\xed\xfe\xaf\x89\x78\xc0\x3d\xe8\x20\x5a" },
219 { 1536, "\x0e\x31\x7b\x3d\x1c\x73\xb9\xe9\xa4\x68\x8f\x29\x6d\x13\x3a\x19" },
220 { 2032, "\xbd\xf0\xe6\xc3\xcc\xa5\xb5\xb9\xd5\x33\xb6\x9c\x56\xad\xa1\x20" },
221 { 2048, "\x88\xa2\x18\xb6\xe2\xec\xe1\xe6\x24\x6d\x44\xc7\x59\xd1\x9b\x10" },
222 { 3056, "\x68\x66\x39\x7e\x95\xc1\x40\x53\x4f\x94\x26\x34\x21\x00\x6e\x40" },
223 { 3072, "\x32\xcb\x0a\x1e\x95\x42\xc6\xb3\xb8\xb3\x98\xab\xc3\xb0\xf1\xd5" },
224 { 4080, "\x29\xa0\xb8\xae\xd5\x4a\x13\x23\x24\xc6\x2e\x42\x3f\x54\xb4\xc8" },
225 { 4096, "\x3c\xb0\xf3\xb5\x02\x0a\x98\xb8\x2a\xf9\xfe\x15\x44\x84\xa1\x68" }
226 }
227 },
228 {
229 "\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,
230 {
231 { 0, "\xea\xa6\xbd\x25\x88\x0b\xf9\x3d\x3f\x5d\x1e\x4c\xa2\x61\x1d\x91" },
232 { 16, "\xcf\xa4\x5c\x9f\x7e\x71\x4b\x54\xbd\xfa\x80\x02\x7c\xb1\x43\x80" },
233 { 240, "\x11\x4a\xe3\x44\xde\xd7\x1b\x35\xf2\xe6\x0f\xeb\xad\x72\x7f\xd8" },
234 { 256, "\x02\xe1\xe7\x05\x6b\x0f\x62\x39\x00\x49\x64\x22\x94\x3e\x97\xb6" },
235 { 496, "\x91\xcb\x93\xc7\x87\x96\x4e\x10\xd9\x52\x7d\x99\x9c\x6f\x93\x6b" },
236 { 512, "\x49\xb1\x8b\x42\xf8\xe8\x36\x7c\xbe\xb5\xef\x10\x4b\xa1\xc7\xcd" },
237 { 752, "\x87\x08\x4b\x3b\xa7\x00\xba\xde\x95\x56\x10\x67\x27\x45\xb3\x74" },
238 { 768, "\xe7\xa7\xb9\xe9\xec\x54\x0d\x5f\xf4\x3b\xdb\x12\x79\x2d\x1b\x35" },
239 { 1008, "\xc7\x99\xb5\x96\x73\x8f\x6b\x01\x8c\x76\xc7\x4b\x17\x59\xbd\x90" },
240 { 1024, "\x7f\xec\x5b\xfd\x9f\x9b\x89\xce\x65\x48\x30\x90\x92\xd7\xe9\x58" },
241 { 1520, "\x40\xf2\x50\xb2\x6d\x1f\x09\x6a\x4a\xfd\x4c\x34\x0a\x58\x88\x15" },
242 { 1536, "\x3e\x34\x13\x5c\x79\xdb\x01\x02\x00\x76\x76\x51\xcf\x26\x30\x73" },
243 { 2032, "\xf6\x56\xab\xcc\xf8\x8d\xd8\x27\x02\x7b\x2c\xe9\x17\xd4\x64\xec" },
244 { 2048, "\x18\xb6\x25\x03\xbf\xbc\x07\x7f\xba\xbb\x98\xf2\x0d\x98\xab\x34" },
245 { 3056, "\x8a\xed\x95\xee\x5b\x0d\xcb\xfb\xef\x4e\xb2\x1d\x3a\x3f\x52\xf9" },
246 { 3072, "\x62\x5a\x1a\xb0\x0e\xe3\x9a\x53\x27\x34\x6b\xdd\xb0\x1a\x9c\x18" },
247 { 4080, "\xa1\x3a\x7c\x79\xc7\xe1\x19\xb5\xab\x02\x96\xab\x28\xc3\x00\xb9" },
248 { 4096, "\xf3\xe4\xc0\xa2\xe0\x2d\x1d\x01\xf7\xf0\xa7\x46\x18\xaf\x2b\x48" }
249 }
250 },
251 {
252 "\x83\x32\x22\x77\x2a", 5,
253 {
254 { 0, "\x80\xad\x97\xbd\xc9\x73\xdf\x8a\x2e\x87\x9e\x92\xa4\x97\xef\xda" },
255 { 16, "\x20\xf0\x60\xc2\xf2\xe5\x12\x65\x01\xd3\xd4\xfe\xa1\x0d\x5f\xc0" },
256 { 240, "\xfa\xa1\x48\xe9\x90\x46\x18\x1f\xec\x6b\x20\x85\xf3\xb2\x0e\xd9" },
257 { 256, "\xf0\xda\xf5\xba\xb3\xd5\x96\x83\x98\x57\x84\x6f\x73\xfb\xfe\x5a" },
258 { 496, "\x1c\x7e\x2f\xc4\x63\x92\x32\xfe\x29\x75\x84\xb2\x96\x99\x6b\xc8" },
259 { 512, "\x3d\xb9\xb2\x49\x40\x6c\xc8\xed\xff\xac\x55\xcc\xd3\x22\xba\x12" },
260 { 752, "\xe4\xf9\xf7\xe0\x06\x61\x54\xbb\xd1\x25\xb7\x45\x56\x9b\xc8\x97" },
261 { 768, "\x75\xd5\xef\x26\x2b\x44\xc4\x1a\x9c\xf6\x3a\xe1\x45\x68\xe1\xb9" },
262 { 1008, "\x6d\xa4\x53\xdb\xf8\x1e\x82\x33\x4a\x3d\x88\x66\xcb\x50\xa1\xe3" },
263 { 1024, "\x78\x28\xd0\x74\x11\x9c\xab\x5c\x22\xb2\x94\xd7\xa9\xbf\xa0\xbb" },
264 { 1520, "\xad\xb8\x9c\xea\x9a\x15\xfb\xe6\x17\x29\x5b\xd0\x4b\x8c\xa0\x5c" },
265 { 1536, "\x62\x51\xd8\x7f\xd4\xaa\xae\x9a\x7e\x4a\xd5\xc2\x17\xd3\xf3\x00" },
266 { 2032, "\xe7\x11\x9b\xd6\xdd\x9b\x22\xaf\xe8\xf8\x95\x85\x43\x28\x81\xe2" },
267 { 2048, "\x78\x5b\x60\xfd\x7e\xc4\xe9\xfc\xb6\x54\x5f\x35\x0d\x66\x0f\xab" },
268 { 3056, "\xaf\xec\xc0\x37\xfd\xb7\xb0\x83\x8e\xb3\xd7\x0b\xcd\x26\x83\x82" },
269 { 3072, "\xdb\xc1\xa7\xb4\x9d\x57\x35\x8c\xc9\xfa\x6d\x61\xd7\x3b\x7c\xf0" },
270 { 4080, "\x63\x49\xd1\x26\xa3\x7a\xfc\xba\x89\x79\x4f\x98\x04\x91\x4f\xdc" },
271 { 4096, "\xbf\x42\xc3\x01\x8c\x2f\x7c\x66\xbf\xde\x52\x49\x75\x76\x81\x15" }
272 }
273 },
274 {
275 "\x19\x10\x83\x32\x22\x77\x2a", 7,
276 {
277 { 0, "\xbc\x92\x22\xdb\xd3\x27\x4d\x8f\xc6\x6d\x14\xcc\xbd\xa6\x69\x0b" },
278 { 16, "\x7a\xe6\x27\x41\x0c\x9a\x2b\xe6\x93\xdf\x5b\xb7\x48\x5a\x63\xe3" },
279 { 240, "\x3f\x09\x31\xaa\x03\xde\xfb\x30\x0f\x06\x01\x03\x82\x6f\x2a\x64" },
280 { 256, "\xbe\xaa\x9e\xc8\xd5\x9b\xb6\x81\x29\xf3\x02\x7c\x96\x36\x11\x81" },
281 { 496, "\x74\xe0\x4d\xb4\x6d\x28\x64\x8d\x7d\xee\x8a\x00\x64\xb0\x6c\xfe" },
282 { 512, "\x9b\x5e\x81\xc6\x2f\xe0\x23\xc5\x5b\xe4\x2f\x87\xbb\xf9\x32\xb8" },
283 { 752, "\xce\x17\x8f\xc1\x82\x6e\xfe\xcb\xc1\x82\xf5\x79\x99\xa4\x61\x40" },
284 { 768, "\x8b\xdf\x55\xcd\x55\x06\x1c\x06\xdb\xa6\xbe\x11\xde\x4a\x57\x8a" },
285 { 1008, "\x62\x6f\x5f\x4d\xce\x65\x25\x01\xf3\x08\x7d\x39\xc9\x2c\xc3\x49" },
286 { 1024, "\x42\xda\xac\x6a\x8f\x9a\xb9\xa7\xfd\x13\x7c\x60\x37\x82\x56\x82" },
287 { 1520, "\xcc\x03\xfd\xb7\x91\x92\xa2\x07\x31\x2f\x53\xf5\xd4\xdc\x33\xd9" },
288 { 1536, "\xf7\x0f\x14\x12\x2a\x1c\x98\xa3\x15\x5d\x28\xb8\xa0\xa8\xa4\x1d" },
289 { 2032, "\x2a\x3a\x30\x7a\xb2\x70\x8a\x9c\x00\xfe\x0b\x42\xf9\xc2\xd6\xa1" },
290 { 2048, "\x86\x26\x17\x62\x7d\x22\x61\xea\xb0\xb1\x24\x65\x97\xca\x0a\xe9" },
291 { 3056, "\x55\xf8\x77\xce\x4f\x2e\x1d\xdb\xbf\x8e\x13\xe2\xcd\xe0\xfd\xc8" },
292 { 3072, "\x1b\x15\x56\xcb\x93\x5f\x17\x33\x37\x70\x5f\xbb\x5d\x50\x1f\xc1" },
293 { 4080, "\xec\xd0\xe9\x66\x02\xbe\x7f\x8d\x50\x92\x81\x6c\xcc\xf2\xc2\xe9" },
294 { 4096, "\x02\x78\x81\xfa\xb4\x99\x3a\x1c\x26\x20\x24\xa9\x4f\xff\x3f\x61" }
295 }
296 },
297 {
298 "\x64\x19\x10\x83\x32\x22\x77\x2a", 8,
299 {
300 { 0, "\xbb\xf6\x09\xde\x94\x13\x17\x2d\x07\x66\x0c\xb6\x80\x71\x69\x26" },
301 { 16, "\x46\x10\x1a\x6d\xab\x43\x11\x5d\x6c\x52\x2b\x4f\xe9\x36\x04\xa9" },
302 { 240, "\xcb\xe1\xff\xf2\x1c\x96\xf3\xee\xf6\x1e\x8f\xe0\x54\x2c\xbd\xf0" },
303 { 256, "\x34\x79\x38\xbf\xfa\x40\x09\xc5\x12\xcf\xb4\x03\x4b\x0d\xd1\xa7" },
304 { 496, "\x78\x67\xa7\x86\xd0\x0a\x71\x47\x90\x4d\x76\xdd\xf1\xe5\x20\xe3" },
305 { 512, "\x8d\x3e\x9e\x1c\xae\xfc\xcc\xb3\xfb\xf8\xd1\x8f\x64\x12\x0b\x32" },
306 { 752, "\x94\x23\x37\xf8\xfd\x76\xf0\xfa\xe8\xc5\x2d\x79\x54\x81\x06\x72" },
307 { 768, "\xb8\x54\x8c\x10\xf5\x16\x67\xf6\xe6\x0e\x18\x2f\xa1\x9b\x30\xf7" },
308 { 1008, "\x02\x11\xc7\xc6\x19\x0c\x9e\xfd\x12\x37\xc3\x4c\x8f\x2e\x06\xc4" },
309 { 1024, "\xbd\xa6\x4f\x65\x27\x6d\x2a\xac\xb8\xf9\x02\x12\x20\x3a\x80\x8e" },
310 { 1520, "\xbd\x38\x20\xf7\x32\xff\xb5\x3e\xc1\x93\xe7\x9d\x33\xe2\x7c\x73" },
311 { 1536, "\xd0\x16\x86\x16\x86\x19\x07\xd4\x82\xe3\x6c\xda\xc8\xcf\x57\x49" },
312 { 2032, "\x97\xb0\xf0\xf2\x24\xb2\xd2\x31\x71\x14\x80\x8f\xb0\x3a\xf7\xa0" },
313 { 2048, "\xe5\x96\x16\xe4\x69\x78\x79\x39\xa0\x63\xce\xea\x9a\xf9\x56\xd1" },
314 { 3056, "\xc4\x7e\x0d\xc1\x66\x09\x19\xc1\x11\x01\x20\x8f\x9e\x69\xaa\x1f" },
315 { 3072, "\x5a\xe4\xf1\x28\x96\xb8\x37\x9a\x2a\xad\x89\xb5\xb5\x53\xd6\xb0" },
316 { 4080, "\x6b\x6b\x09\x8d\x0c\x29\x3b\xc2\x99\x3d\x80\xbf\x05\x18\xb6\xd9" },
317 { 4096, "\x81\x70\xcc\x3c\xcd\x92\xa6\x98\x62\x1b\x93\x9d\xd3\x8f\xe7\xb9" }
318 }
319 },
320 {
321 "\x8b\x37\x64\x19\x10\x83\x32\x22\x77\x2a", 10,
322 {
323 { 0, "\xab\x65\xc2\x6e\xdd\xb2\x87\x60\x0d\xb2\xfd\xa1\x0d\x1e\x60\x5c" },
324 { 16, "\xbb\x75\x90\x10\xc2\x96\x58\xf2\xc7\x2d\x93\xa2\xd1\x6d\x29\x30" },
325 { 240, "\xb9\x01\xe8\x03\x6e\xd1\xc3\x83\xcd\x3c\x4c\x4d\xd0\xa6\xab\x05" },
326 { 256, "\x3d\x25\xce\x49\x22\x92\x4c\x55\xf0\x64\x94\x33\x53\xd7\x8a\x6c" },
327 { 496, "\x12\xc1\xaa\x44\xbb\xf8\x7e\x75\xe6\x11\xf6\x9b\x2c\x38\xf4\x9b" },
328 { 512, "\x28\xf2\xb3\x43\x4b\x65\xc0\x98\x77\x47\x00\x44\xc6\xea\x17\x0d" },
329 { 752, "\xbd\x9e\xf8\x22\xde\x52\x88\x19\x61\x34\xcf\x8a\xf7\x83\x93\x04" },
330 { 768, "\x67\x55\x9c\x23\xf0\x52\x15\x84\x70\xa2\x96\xf7\x25\x73\x5a\x32" },
331 { 1008, "\x8b\xab\x26\xfb\xc2\xc1\x2b\x0f\x13\xe2\xab\x18\x5e\xab\xf2\x41" },
332 { 1024, "\x31\x18\x5a\x6d\x69\x6f\x0c\xfa\x9b\x42\x80\x8b\x38\xe1\x32\xa2" },
333 { 1520, "\x56\x4d\x3d\xae\x18\x3c\x52\x34\xc8\xaf\x1e\x51\x06\x1c\x44\xb5" },
334 { 1536, "\x3c\x07\x78\xa7\xb5\xf7\x2d\x3c\x23\xa3\x13\x5c\x7d\x67\xb9\xf4" },
335 { 2032, "\xf3\x43\x69\x89\x0f\xcf\x16\xfb\x51\x7d\xca\xae\x44\x63\xb2\xdd" },
336 { 2048, "\x02\xf3\x1c\x81\xe8\x20\x07\x31\xb8\x99\xb0\x28\xe7\x91\xbf\xa7" },
337 { 3056, "\x72\xda\x64\x62\x83\x22\x8c\x14\x30\x08\x53\x70\x17\x95\x61\x6f" },
338 { 3072, "\x4e\x0a\x8c\x6f\x79\x34\xa7\x88\xe2\x26\x5e\x81\xd6\xd0\xc8\xf4" },
339 { 4080, "\x43\x8d\xd5\xea\xfe\xa0\x11\x1b\x6f\x36\xb4\xb9\x38\xda\x2a\x68" },
340 { 4096, "\x5f\x6b\xfc\x73\x81\x58\x74\xd9\x71\x00\xf0\x86\x97\x93\x57\xd8" }
341 }
342 },
343 {
344 "\xeb\xb4\x62\x27\xc6\xcc\x8b\x37\x64\x19\x10\x83\x32\x22\x77\x2a", 16,
345 {
346 { 0, "\x72\x0c\x94\xb6\x3e\xdf\x44\xe1\x31\xd9\x50\xca\x21\x1a\x5a\x30" },
347 { 16, "\xc3\x66\xfd\xea\xcf\x9c\xa8\x04\x36\xbe\x7c\x35\x84\x24\xd2\x0b" },
348 { 240, "\xb3\x39\x4a\x40\xaa\xbf\x75\xcb\xa4\x22\x82\xef\x25\xa0\x05\x9f" },
349 { 256, "\x48\x47\xd8\x1d\xa4\x94\x2d\xbc\x24\x9d\xef\xc4\x8c\x92\x2b\x9f" },
350 { 496, "\x08\x12\x8c\x46\x9f\x27\x53\x42\xad\xda\x20\x2b\x2b\x58\xda\x95" },
351 { 512, "\x97\x0d\xac\xef\x40\xad\x98\x72\x3b\xac\x5d\x69\x55\xb8\x17\x61" },
352 { 752, "\x3c\xb8\x99\x93\xb0\x7b\x0c\xed\x93\xde\x13\xd2\xa1\x10\x13\xac" },
353 { 768, "\xef\x2d\x67\x6f\x15\x45\xc2\xc1\x3d\xc6\x80\xa0\x2f\x4a\xdb\xfe" },
354 { 1008, "\xb6\x05\x95\x51\x4f\x24\xbc\x9f\xe5\x22\xa6\xca\xd7\x39\x36\x44" },
355 { 1024, "\xb5\x15\xa8\xc5\x01\x17\x54\xf5\x90\x03\x05\x8b\xdb\x81\x51\x4e" },
356 { 1520, "\x3c\x70\x04\x7e\x8c\xbc\x03\x8e\x3b\x98\x20\xdb\x60\x1d\xa4\x95" },
357 { 1536, "\x11\x75\xda\x6e\xe7\x56\xde\x46\xa5\x3e\x2b\x07\x56\x60\xb7\x70" },
358 { 2032, "\x00\xa5\x42\xbb\xa0\x21\x11\xcc\x2c\x65\xb3\x8e\xbd\xba\x58\x7e" },
359 { 2048, "\x58\x65\xfd\xbb\x5b\x48\x06\x41\x04\xe8\x30\xb3\x80\xf2\xae\xde" },
360 { 3056, "\x34\xb2\x1a\xd2\xad\x44\xe9\x99\xdb\x2d\x7f\x08\x63\xf0\xd9\xb6" },
361 { 3072, "\x84\xa9\x21\x8f\xc3\x6e\x8a\x5f\x2c\xcf\xbe\xae\x53\xa2\x7d\x25" },
362 { 4080, "\xa2\x22\x1a\x11\xb8\x33\xcc\xb4\x98\xa5\x95\x40\xf0\x54\x5f\x4a" },
363 { 4096, "\x5b\xbe\xb4\x78\x7d\x59\xe5\x37\x3f\xdb\xea\x6c\x6f\x75\xc2\x9b" }
364 }
365 },
366 {
367 "\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,
368 {
369 { 0, "\x54\xb6\x4e\x6b\x5a\x20\xb5\xe2\xec\x84\x59\x3d\xc7\x98\x9d\xa7" },
370 { 16, "\xc1\x35\xee\xe2\x37\xa8\x54\x65\xff\x97\xdc\x03\x92\x4f\x45\xce" },
371 { 240, "\xcf\xcc\x92\x2f\xb4\xa1\x4a\xb4\x5d\x61\x75\xaa\xbb\xf2\xd2\x01" },
372 { 256, "\x83\x7b\x87\xe2\xa4\x46\xad\x0e\xf7\x98\xac\xd0\x2b\x94\x12\x4f" },
373 { 496, "\x17\xa6\xdb\xd6\x64\x92\x6a\x06\x36\xb3\xf4\xc3\x7a\x4f\x46\x94" },
374 { 512, "\x4a\x5f\x9f\x26\xae\xee\xd4\xd4\xa2\x5f\x63\x2d\x30\x52\x33\xd9" },
375 { 752, "\x80\xa3\xd0\x1e\xf0\x0c\x8e\x9a\x42\x09\xc1\x7f\x4e\xeb\x35\x8c" },
376 { 768, "\xd1\x5e\x7d\x5f\xfa\xaa\xbc\x02\x07\xbf\x20\x0a\x11\x77\x93\xa2" },
377 { 1008, "\x34\x96\x82\xbf\x58\x8e\xaa\x52\xd0\xaa\x15\x60\x34\x6a\xea\xfa" },
378 { 1024, "\xf5\x85\x4c\xdb\x76\xc8\x89\xe3\xad\x63\x35\x4e\x5f\x72\x75\xe3" },
379 { 1520, "\x53\x2c\x7c\xec\xcb\x39\xdf\x32\x36\x31\x84\x05\xa4\xb1\x27\x9c" },
380 { 1536, "\xba\xef\xe6\xd9\xce\xb6\x51\x84\x22\x60\xe0\xd1\xe0\x5e\x3b\x90" },
381 { 2032, "\xe8\x2d\x8c\x6d\xb5\x4e\x3c\x63\x3f\x58\x1c\x95\x2b\xa0\x42\x07" },
382 { 2048, "\x4b\x16\xe5\x0a\xbd\x38\x1b\xd7\x09\x00\xa9\xcd\x9a\x62\xcb\x23" },
383 { 3056, "\x36\x82\xee\x33\xbd\x14\x8b\xd9\xf5\x86\x56\xcd\x8f\x30\xd9\xfb" },
384 { 3072, "\x1e\x5a\x0b\x84\x75\x04\x5d\x9b\x20\xb2\x62\x86\x24\xed\xfd\x9e" },
385 { 4080, "\x63\xed\xd6\x84\xfb\x82\x62\x82\xfe\x52\x8f\x9c\x0e\x92\x37\xbc" },
386 { 4096, "\xe4\xdd\x2e\x98\xd6\x96\x0f\xae\x0b\x43\x54\x54\x56\x74\x33\x91" }
387 }
388 },
389 {
390 "\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,
391 {
392 { 0, "\xdd\x5b\xcb\x00\x18\xe9\x22\xd4\x94\x75\x9d\x7c\x39\x5d\x02\xd3" },
393 { 16, "\xc8\x44\x6f\x8f\x77\xab\xf7\x37\x68\x53\x53\xeb\x89\xa1\xc9\xeb" },
394 { 240, "\xaf\x3e\x30\xf9\xc0\x95\x04\x59\x38\x15\x15\x75\xc3\xfb\x90\x98" },
395 { 256, "\xf8\xcb\x62\x74\xdb\x99\xb8\x0b\x1d\x20\x12\xa9\x8e\xd4\x8f\x0e" },
396 { 496, "\x25\xc3\x00\x5a\x1c\xb8\x5d\xe0\x76\x25\x98\x39\xab\x71\x98\xab" },
397 { 512, "\x9d\xcb\xc1\x83\xe8\xcb\x99\x4b\x72\x7b\x75\xbe\x31\x80\x76\x9c" },
398 { 752, "\xa1\xd3\x07\x8d\xfa\x91\x69\x50\x3e\xd9\xd4\x49\x1d\xee\x4e\xb2" },
399 { 768, "\x85\x14\xa5\x49\x58\x58\x09\x6f\x59\x6e\x4b\xcd\x66\xb1\x06\x65" },
400 { 1008, "\x5f\x40\xd5\x9e\xc1\xb0\x3b\x33\x73\x8e\xfa\x60\xb2\x25\x5d\x31" },
401 { 1024, "\x34\x77\xc7\xf7\x64\xa4\x1b\xac\xef\xf9\x0b\xf1\x4f\x92\xb7\xcc" },
402 { 1520, "\xac\x4e\x95\x36\x8d\x99\xb9\xeb\x78\xb8\xda\x8f\x81\xff\xa7\x95" },
403 { 1536, "\x8c\x3c\x13\xf8\xc2\x38\x8b\xb7\x3f\x38\x57\x6e\x65\xb7\xc4\x46" },
404 { 2032, "\x13\xc4\xb9\xc1\xdf\xb6\x65\x79\xed\xdd\x8a\x28\x0b\x9f\x73\x16" },
405 { 2048, "\xdd\xd2\x78\x20\x55\x01\x26\x69\x8e\xfa\xad\xc6\x4b\x64\xf6\x6e" },
406 { 3056, "\xf0\x8f\x2e\x66\xd2\x8e\xd1\x43\xf3\xa2\x37\xcf\x9d\xe7\x35\x59" },
407 { 3072, "\x9e\xa3\x6c\x52\x55\x31\xb8\x80\xba\x12\x43\x34\xf5\x7b\x0b\x70" },
408 { 4080, "\xd5\xa3\x9e\x3d\xfc\xc5\x02\x80\xba\xc4\xa6\xb5\xaa\x0d\xca\x7d" },
409 { 4096, "\x37\x0b\x1c\x1f\xe6\x55\x91\x6d\x97\xfd\x0d\x47\xca\x1d\x72\xb8" }
410 }
411 }
412 };
413
414 struct rc4_ctx ctx;
415
416 for ( size_t i = 0; i != NELEM(cases); ++i ) {
417 rc4_init(&ctx, cases[i].key, cases[i].sz);
418
419 unsigned int pos = 0;
420
421 for ( int j = 0; j != 18; ++j ) {
422 while ( pos != cases[i].test[j].pos ) {
423 rc4_get_byte(&ctx);
424 ++pos;
425 }
426
427 unsigned char bytes[16];
428 for ( unsigned int k = 0; k != 16; ++k ) {
429 bytes[k] = rc4_get_byte(&ctx);
430 ++pos;
431 }
432
433 if ( memcmp(bytes, cases[i].test[j].bytes, 16) != 0 ) {
434 ERROR("Fehler");
435 exit(EXIT_FAILURE);
436 }
437 }
438
439 printf("Test #%zu : OK\n", i);
440
441 rc4_clear(&ctx);
442 }
443}
444
445int
446main()
447{
448 rc4_test();
449
450 struct random_ctx *random = rc4_create("\x01\x02\x03\x04\x05\x06\x07", 7);
451
452 for ( int j = 0; j != 18; ++j ) {
453 for ( int i = 0; i != 16; ++i ) {
454 printf("%02X ", random_get_byte(random));
455 }
456 puts("");
457 }
458
459 rc4_free(random);
460
461 return 0;
462}
463
diff --git a/readme.md b/readme.md
new file mode 100644
index 0000000..5f25333
--- /dev/null
+++ b/readme.md
@@ -0,0 +1,12 @@
1# Weitere Links
2
3- 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)
4 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)
5
6- Eine Implementierung einer Thread-Safe Queue ist hier zu finden: [Concurrent queue – C++11](https://juanchopanzacpp.wordpress.com/2013/02/26/concurrent-queue-c11/);
7 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)
8
9- 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/)
10
11
12
diff --git a/ringbuff.c b/ringbuff.c
new file mode 100644
index 0000000..99dc0d8
--- /dev/null
+++ b/ringbuff.c
@@ -0,0 +1,72 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include "util.h"
5
6typedef int T;
7
8struct ring_buffer {
9 int head, tail;
10 T array[8]; /* fit for your needs... */
11};
12
13void
14ring_init(struct ring_buffer *rb)
15{
16 rb->head = rb->tail = 0;
17}
18
19bool
20ring_put(struct ring_buffer *rb, T data)
21{
22 const int next = (rb->head + 1) % NELEM(rb->array);
23
24 if ( next == rb->tail )
25 return false;
26
27 rb->array[rb->head] = data;
28 rb->head = next;
29
30 return true;
31}
32
33bool
34ring_get(struct ring_buffer *rb, T *data)
35{
36 if ( rb->head == rb->tail )
37 return false;
38
39 const int next = (rb->tail + 1) % NELEM(rb->array);
40
41 *data = rb->array[rb->tail];
42 rb->tail = next;
43
44 return true;
45}
46
47void f() { ERROR(""); }
48
49int
50main(void)
51{
52#if 0
53 struct ring_buffer rb;
54 ring_init(&rb);
55#else
56 struct ring_buffer rb = { .head = 0, .tail = 0 };
57#endif
58
59 for ( int i = 0; i != 30; ++i ) {
60 if ( !ring_put(&rb, i) )
61 break;
62 }
63
64 int j;
65 while ( ring_get(&rb, &j) ) {
66 printf("%d\n", j);
67 }
68
69 return EXIT_SUCCESS;
70}
71
72
diff --git a/stack.c b/stack.c
new file mode 100644
index 0000000..fa89974
--- /dev/null
+++ b/stack.c
@@ -0,0 +1,98 @@
1/* Standard C */
2#include <stdio.h>
3#include <stdlib.h>
4#include <stdbool.h>
5
6/* Project */
7#include "util.h"
8
9typedef int T;
10
11struct stack_item {
12 struct stack_item *next;
13 T data;
14};
15
16struct stack {
17 struct stack_item *head;
18};
19
20void
21stack_init(struct stack *stack)
22{
23 stack->head = NULL;
24}
25
26void
27stack_push(struct stack *stack, T data)
28{
29 struct stack_item *new_item;
30
31 if ( (new_item = malloc(sizeof(*new_item))) != NULL ) {
32 new_item->data = data;
33 new_item->next = stack->head;
34 stack->head = new_item;
35 }
36 else
37 ERROR("out of memory");
38}
39
40bool
41stack_pop(struct stack *stack, T *data)
42{
43 if ( stack->head != NULL ) {
44 struct stack_item *next = stack->head->next;
45 *data = stack->head->data;
46 free(stack->head);
47 stack->head = next;
48
49 return true;
50 }
51 else
52 return false;
53}
54
55bool
56stack_empty(struct stack *stack)
57{
58 return stack->head == NULL;
59}
60
61void
62stack_free(struct stack *stack)
63{
64 struct stack_item *item, *next;
65
66 for ( item = stack->head; item; item = next ) {
67 next = item->next;
68 free(item);
69 }
70}
71
72int
73main()
74{
75 struct stack stack[1];
76
77 stack_init(stack);
78
79 for ( int i = 0; i != 10; ++i )
80 stack_push(stack, i);
81
82 /*
83 while ( !stack_empty(stack) ) {
84 int i;
85 if ( stack_pop(stack, &i) )
86 printf("%d\n", i);
87 else
88 ERROR("this shouldn't happen!");
89 }
90 */
91
92 stack_free(stack);
93
94 return EXIT_SUCCESS;
95}
96
97
98
diff --git a/stack2.c b/stack2.c
new file mode 100644
index 0000000..57dce4f
--- /dev/null
+++ b/stack2.c
@@ -0,0 +1,100 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#include "util.h"
6
7typedef int T;
8
9struct stack {
10 T *array;
11 size_t sz, p;
12};
13
14void
15stack_init(struct stack *stack)
16{
17 stack->array = NULL;
18 stack->sz = 0;
19 stack->p = 0;
20}
21
22bool
23stack_push(struct stack *stack, T data)
24{
25 if ( stack->array == NULL ) {
26 if ( (stack->array = malloc(10 * sizeof(*stack->array))) != NULL ) {
27 stack->sz = 10;
28 stack->p = 0;
29 }
30 else {
31 ERROR("out of memory");
32 return false;
33 }
34 }
35
36 if ( stack->p == stack->sz ) {
37 size_t new_sz;
38 T *new_array;
39
40 if ( (new_array = realloc(stack->array, (new_sz = (stack->sz * 3 / 2)) * sizeof(*stack->array))) != NULL ) {
41 stack->array = new_array;
42 stack->sz = new_sz;
43 }
44 else {
45 ERROR("out of memory");
46 return false;
47 }
48 }
49
50 stack->array[stack->p++] = data;
51 return true;
52}
53
54bool
55stack_pop(struct stack *stack, T *data)
56{
57 if ( stack->p != 0 ) {
58 *data = stack->array[--stack->p];
59 return true;
60 }
61 else
62 return false;
63}
64
65bool
66stack_empty(struct stack *stack)
67{
68 return stack->p == 0;
69}
70
71void
72stack_free(struct stack *stack)
73{
74 free(stack->array);
75}
76
77int
78main()
79{
80 struct stack stack[1];
81
82 stack_init(stack);
83
84 for ( int i = 0; i != 20; ++i )
85 stack_push(stack, i);
86
87 while ( !stack_empty(stack) ) {
88 int i;
89
90 if ( stack_pop(stack, &i) )
91 printf("%d\n", i);
92 else
93 ERROR("this shouldn't happen!");
94 }
95
96 stack_free(stack);
97
98 return EXIT_SUCCESS;
99}
100
diff --git a/tree.c b/tree.c
new file mode 100644
index 0000000..7b0bc61
--- /dev/null
+++ b/tree.c
@@ -0,0 +1,466 @@
1// Binary Search Tree
2#include <stdio.h>
3#include <stdlib.h>
4#include <stdbool.h>
5#include <time.h>
6#include <limits.h>
7
8#include "util.h"
9
10typedef int T;
11
12struct tree_node {
13 struct tree_node *left, *right;
14 T key;
15 int count; /* collision counter */
16 /* ggf. weitere Felder... */
17};
18
19static bool tree_isBstUntil(struct tree_node *tree, int min, int max);
20
21bool
22tree_isBst(struct tree_node *tree)
23{
24 return tree_isBstUntil(tree, INT_MIN, INT_MAX);
25}
26
27bool
28tree_isBstUntil(struct tree_node *tree, int min, int max)
29{
30 if ( tree == NULL )
31 return true;
32
33 if ( tree->key < min || tree->key > max )
34 return false;
35
36 return tree_isBstUntil(tree->left, min, tree->key - 1) &&
37 tree_isBstUntil(tree->right, tree->key + 1, max);
38}
39
40struct tree_node *
41tree_insert(struct tree_node *tree, T key)
42{
43 if ( tree == NULL ) {
44 tree = malloc(sizeof *tree);
45 if ( tree != NULL ) {
46 tree->key = key;
47 tree->count = 1;
48 tree->left = tree->right = NULL;
49 }
50 else
51 ERROR("out of memory");
52 }
53 else if ( key < tree->key )
54 tree->left = tree_insert(tree->left, key);
55 else if ( key > tree->key )
56 tree->right = tree_insert(tree->right, key);
57 else /* key == tree->key */
58 tree->count++; /* handle collision */
59
60 return tree;
61}
62
63static struct tree_node *
64tree_detach_min(struct tree_node **ptree)
65{
66 struct tree_node *tree = *ptree;
67
68 if ( tree == NULL )
69 return NULL;
70 else if ( tree->left != NULL )
71 return tree_detach_min(&tree->left);
72 else {
73 *ptree = tree->right;
74 return tree;
75 }
76}
77
78struct tree_node *
79tree_remove(struct tree_node *tree, T key)
80{
81 if ( tree == NULL )
82 return NULL;
83
84 if ( key < tree->key )
85 tree->left = tree_remove(tree->left, key);
86 else if ( key > tree->key )
87 tree->right = tree_remove(tree->right, key);
88 else { /* key == tree->key */
89 /* TODO: Handle Collision */
90
91 struct tree_node *temp = tree;
92
93 if ( tree->left == NULL ) {
94 tree = tree->right;
95 }
96 else if ( tree->right == NULL ) {
97 tree = tree->left;
98 }
99 else {
100 struct tree_node *min = tree_detach_min(&tree->right);
101
102 min->left = tree->left;
103 min->right = tree->right;
104
105 tree = min;
106 }
107
108 free(temp);
109 }
110 return tree;
111}
112
113void
114tree_clear(struct tree_node *tree)
115{
116 if ( tree ) {
117 tree_clear(tree->left);
118 tree_clear(tree->right);
119 free(tree);
120 }
121}
122
123struct tree_node *
124tree_lookup(struct tree_node *tree, T key)
125{
126 while ( tree )
127 if ( key < tree->key )
128 tree = tree->left;
129 else if ( key > tree->key )
130 tree = tree->right;
131 else /* key == tree->key */
132 return tree;
133
134 return NULL;
135}
136
137struct tree_node *
138tree_minimum(struct tree_node *tree)
139{
140 if ( tree )
141 while ( tree->left )
142 tree = tree->left;
143
144 return tree;
145}
146
147struct tree_node *
148tree_maximum(struct tree_node *tree)
149{
150 if ( tree )
151 while ( tree->right )
152 tree = tree->right;
153
154 return tree;
155}
156
157size_t
158tree_height(struct tree_node *tree)
159{
160 if ( tree ) {
161 size_t hl = tree_height(tree->left);
162 size_t hr = tree_height(tree->right);
163
164 return (( hl > hr ) ? hl : hr) + 1;
165 }
166
167 return 0;
168}
169
170size_t
171tree_count(struct tree_node *tree)
172{
173 if ( tree )
174 return tree_count(tree->left) + tree_count(tree->right) + 1;
175
176 return 0;
177}
178
179void
180tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
181{
182 if ( tree ) {
183 visit(tree->key, cl);
184 tree_apply_preorder(tree->left, visit, cl);
185 tree_apply_preorder(tree->right, visit, cl);
186 }
187}
188
189void
190tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
191{
192 if ( tree ) {
193 tree_apply_inorder(tree->left, visit, cl);
194 visit(tree->key, cl);
195 tree_apply_inorder(tree->right, visit, cl);
196 }
197}
198
199void
200tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
201{
202 if ( tree ) {
203 tree_apply_postorder(tree->left, visit, cl);
204 tree_apply_postorder(tree->right, visit, cl);
205 visit(tree->key, cl);
206 }
207}
208
209/* ===== */
210
211struct stack_item {
212 struct stack_item *next;
213 struct tree_node *data;
214};
215
216struct stack {
217 struct stack_item *head;
218};
219
220static void
221stack_init(struct stack *stack)
222{
223 stack->head = NULL;
224}
225
226static void
227stack_push(struct stack *stack, struct tree_node *data)
228{
229 struct stack_item *new_item;
230
231 if ( (new_item = malloc(sizeof(*new_item))) != NULL ) {
232 new_item->data = data;
233 new_item->next = stack->head;
234 stack->head = new_item;
235 }
236 else
237 ERROR("out of memory");
238}
239
240static bool
241stack_pop(struct stack *stack, struct tree_node **data)
242{
243 if ( stack->head != NULL ) {
244 struct stack_item *next = stack->head->next;
245 *data = stack->head->data;
246 free(stack->head);
247 stack->head = next;
248
249 return true;
250 }
251 else
252 return false;
253}
254
255static bool
256stack_empty(struct stack *stack)
257{
258 return stack->head == NULL;
259}
260
261void
262stack_free(struct stack *stack)
263{
264 struct stack_item *item, *next;
265
266 for ( item = stack->head; item; item = next ) {
267 next = item->next;
268 free(item);
269 }
270}
271
272void
273tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
274{
275 if ( tree != NULL ) {
276 struct stack stack;
277
278 stack_init(&stack);
279
280 stack_push(&stack, tree);
281
282 while ( stack_pop(&stack, &tree) ) {
283 visit(tree->key, cl);
284
285 if ( tree->right != NULL ) stack_push(&stack, tree->right);
286 if ( tree->left != NULL ) stack_push(&stack, tree->left );
287 }
288
289 stack_free(&stack);
290 }
291}
292
293void
294tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
295{
296 if ( tree != NULL ) {
297 struct stack stack;
298
299 stack_init(&stack);
300
301 while ( !stack_empty(&stack) || tree != NULL ) {
302 if ( tree != NULL ) {
303 stack_push(&stack, tree);
304 tree = tree->left;
305 }
306 else {
307 stack_pop(&stack, &tree);
308 visit(tree->key, cl);
309 tree = tree->right;
310 }
311 }
312
313 stack_free(&stack);
314 }
315}
316
317/* ======================== */
318
319struct tree_iterator {
320 struct stack stack;
321};
322
323static void
324tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node)
325{
326 for ( ; node; node = node->left ) {
327 stack_push(stack, node);
328 }
329}
330
331struct tree_node *
332tree_iterator_next(struct tree_iterator *it)
333{
334 struct tree_node *node = NULL;
335
336 if ( stack_pop(&it->stack, &node) ) {
337 tree_iterator_push_leftmost(&it->stack, node->right);
338 }
339
340 return node;
341}
342
343struct tree_node *
344tree_iterator_first(struct tree_iterator *it, struct tree_node *tree)
345{
346 stack_init(&it->stack);
347
348 tree_iterator_push_leftmost(&it->stack, tree);
349
350 return tree_iterator_next(it);
351}
352
353void
354tree_iterator_free(struct tree_iterator *it)
355{
356 stack_free(&it->stack);
357}
358
359/* ===== */
360
361
362void
363print(T data, void *cl)
364{
365 (void) cl;
366 printf("%d\n", data);
367}
368
369#include "treeutil.h"
370
371int
372main_(void)
373{
374 // Teste den Fall von mycodeschool
375
376 struct tree_node *tree = NULL;
377
378 tree = tree_insert(tree, 12);
379 tree = tree_insert(tree, 5);
380 tree = tree_insert(tree, 15);
381 tree = tree_insert(tree, 3);
382 tree = tree_insert(tree, 7);
383 tree = tree_insert(tree, 13);
384 tree = tree_insert(tree, 17);
385 tree = tree_insert(tree, 1);
386 tree = tree_insert(tree, 9);
387 tree = tree_insert(tree, 14);
388 tree = tree_insert(tree, 20);
389 tree = tree_insert(tree, 8);
390 tree = tree_insert(tree, 11);
391 tree = tree_insert(tree, 18);
392
393 tree = tree_remove(tree, 15);
394
395 if ( !tree_isBst(tree) ) {
396 fprintf(stderr, "Tree ist kein BST!!\n");
397 return EXIT_FAILURE;
398 }
399
400 show_tree(tree, 0, 0);
401
402 tree_clear(tree);
403
404 return EXIT_SUCCESS;
405}
406
407int
408main__(void)
409{
410 struct tree_node *tree = NULL;
411
412 tree = tree_insert(tree, 5);
413 tree = tree_insert(tree, 3);
414 tree = tree_insert(tree, 7);
415 tree = tree_insert(tree, 2);
416 tree = tree_insert(tree, 4);
417 tree = tree_insert(tree, 6);
418 tree = tree_insert(tree, 8);
419
420 tree = tree_remove(tree, 2);
421 tree = tree_remove(tree, 3);
422 tree = tree_remove(tree, 5);
423
424 if ( !tree_isBst(tree) ) {
425 fprintf(stderr, "Tree ist kein BST!!\n");
426 return EXIT_FAILURE;
427 }
428
429 show_tree(tree, 0, 0);
430
431 tree_clear(tree);
432
433 return EXIT_SUCCESS;
434}
435
436
437int
438main(void)
439{
440 struct tree_node *tree = NULL;
441
442 tree = tree_insert(tree, 10);
443 tree = tree_insert(tree, 5);
444 tree = tree_insert(tree, 20);
445 tree = tree_insert(tree, 1);
446 tree = tree_insert(tree, 7);
447 tree = tree_insert(tree, 15);
448 tree = tree_insert(tree, 18);
449
450 tree_apply_preorder(tree, print, NULL);
451
452 show_tree(tree, 0, 0);
453
454 struct tree_iterator it;
455 struct tree_node *node = tree_iterator_first(&it, tree);
456 while ( node ) {
457 fprintf(stdout, "%d\n", node->key);
458
459 node = tree_iterator_next(&it);
460 }
461 tree_iterator_free(&it);
462
463 tree_clear(tree);
464
465 return EXIT_SUCCESS;
466}
diff --git a/treeutil.h b/treeutil.h
new file mode 100644
index 0000000..302a6e3
--- /dev/null
+++ b/treeutil.h
@@ -0,0 +1,45 @@
1// aux display and verification routines, helpful but not essential
2struct trunk {
3 struct trunk *prev;
4 char * str;
5};
6
7static void show_trunks(struct trunk *p)
8{
9 if (!p) return;
10 show_trunks(p->prev);
11 printf("%s", p->str);
12}
13
14// this is very haphazzard
15static void show_tree(struct tree_node *root, struct trunk *prev, int is_left)
16{
17 if (root == NULL) return;
18
19 struct trunk this_disp = { prev, " " };
20 char *prev_str = this_disp.str;
21 show_tree(root->right, &this_disp, 1);
22
23 if (!prev)
24 this_disp.str = "---";
25 else if (is_left) {
26 this_disp.str = ".--";
27 prev_str = " |";
28 } else {
29 this_disp.str = "`--";
30 prev->str = prev_str;
31 }
32
33 show_trunks(&this_disp);
34 if ( root->key >= 'A' && root->key <= 'Z' )
35 printf("%c\n", root->key);
36 else
37 printf("%d\n", root->key);
38
39 if (prev) prev->str = prev_str;
40 this_disp.str = " |";
41
42 show_tree(root->left, &this_disp, 0);
43 if (!prev) puts("");
44}
45
diff --git a/util.h b/util.h
new file mode 100644
index 0000000..eb250ae
--- /dev/null
+++ b/util.h
@@ -0,0 +1,32 @@
1#ifndef ITS1_UTIL_H_INCLUDED
2#define ITS1_UTIL_H_INCLUDED
3
4#include <stdio.h>
5#include <stdlib.h>
6#include <stdarg.h>
7
8#ifndef NDEBUG
9static void
10error(const char *msg, ...)
11{
12 va_list ap;
13
14 va_start(ap, msg);
15 fprintf(stderr, "Error: ");
16 vfprintf(stderr, msg, ap);
17 va_end(ap);
18 fprintf(stderr, "\n");
19 exit(EXIT_FAILURE);
20}
21
22#define ERROR(msg) error(msg " in \"%s()\" (%s:%d)", __func__, __FILE__, __LINE__)
23#else
24#define ERROR(msg) /**/
25#endif
26
27#ifndef NELEM
28#define NELEM(x) (sizeof(x) / sizeof(x[0]))
29#endif
30
31#endif
32