aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--avl.c25
-rw-r--r--deque.c38
-rw-r--r--dlist.c28
-rw-r--r--hashtab.c16
-rw-r--r--list-tail-node.c20
-rw-r--r--list.c30
-rw-r--r--queue.c12
-rw-r--r--quicksort.c370
-rw-r--r--rb.c1
-rw-r--r--ringbuff.c16
-rw-r--r--stack.c12
-rw-r--r--stack2.c12
-rw-r--r--tree.c80
13 files changed, 477 insertions, 183 deletions
diff --git a/avl.c b/avl.c
index 201dc5b..13a3d5f 100644
--- a/avl.c
+++ b/avl.c
@@ -1,15 +1,18 @@
1// AVL Tree 1// AVL Tree
2#include <stdbool.h>
2#include <stdio.h> 3#include <stdio.h>
3#include <stdlib.h> 4#include <stdlib.h>
4#include <stdbool.h>
5#include <time.h> 5#include <time.h>
6 6
7/* utils */ 7/* utils */
8#include "util.h" 8#include "util.h"
9 9
10// TODO: [x] Review: http://www.inr.ac.ru/~info21/ADen/ 10// clang-format off
11// [x] Tests: https://stackoverflow.com/q/3955680
12 11
12// Review: http://www.inr.ac.ru/~info21/ADen/
13// Tests: https://stackoverflow.com/q/3955680
14
15/* --8<-- avl_type */
13typedef int T; 16typedef int T;
14 17
15struct tree_node { 18struct tree_node {
@@ -19,7 +22,9 @@ struct tree_node {
19 int count; /* collision counter */ 22 int count; /* collision counter */
20 /* ggf. weitere Felder... */ 23 /* ggf. weitere Felder... */
21}; 24};
25/* -->8-- */
22 26
27/* --8<-- avl_insert_r */
23static struct tree_node * 28static struct tree_node *
24insert_r(T x, struct tree_node *p, bool *h) 29insert_r(T x, struct tree_node *p, bool *h)
25{ 30{
@@ -109,14 +114,18 @@ insert_r(T x, struct tree_node *p, bool *h)
109 ERROR("das hier sollte niemals passieren"); 114 ERROR("das hier sollte niemals passieren");
110 return p; 115 return p;
111} 116}
117/* -->8-- */
112 118
119/* --8<-- avl_insert */
113struct tree_node * 120struct tree_node *
114insert(struct tree_node *tree, T data) 121insert(struct tree_node *tree, T data)
115{ 122{
116 bool h = false; 123 bool h = false;
117 return insert_r(data, tree, &h); 124 return insert_r(data, tree, &h);
118} 125}
126/* -->8-- */
119 127
128/* --8<-- avl_balanceL */
120static struct tree_node * 129static struct tree_node *
121balanceL(struct tree_node *p, bool *h) 130balanceL(struct tree_node *p, bool *h)
122{ 131{
@@ -157,7 +166,9 @@ balanceL(struct tree_node *p, bool *h)
157 } 166 }
158 return p; 167 return p;
159} 168}
169/* -->8-- */
160 170
171/* --8<-- avl_balanceR */
161static struct tree_node * 172static struct tree_node *
162balanceR(struct tree_node *p, bool *h) 173balanceR(struct tree_node *p, bool *h)
163{ 174{
@@ -198,7 +209,9 @@ balanceR(struct tree_node *p, bool *h)
198 } 209 }
199 return p; 210 return p;
200} 211}
212/* -->8-- */
201 213
214/* --8<-- avl_del */
202static void 215static void
203del(struct tree_node **q, struct tree_node **r, bool *h) 216del(struct tree_node **q, struct tree_node **r, bool *h)
204{ 217{
@@ -217,7 +230,9 @@ del(struct tree_node **q, struct tree_node **r, bool *h)
217 *h = true; 230 *h = true;
218 } 231 }
219} 232}
233/* -->8-- */
220 234
235/* --8<-- avl_delete_r */
221static struct tree_node * 236static struct tree_node *
222delete_r(T x, struct tree_node *p, bool *h) 237delete_r(T x, struct tree_node *p, bool *h)
223{ 238{
@@ -253,14 +268,16 @@ delete_r(T x, struct tree_node *p, bool *h)
253 } 268 }
254 return p; 269 return p;
255} 270}
271/* -->8-- */
256 272
273/* --8<-- avl_delete */
257struct tree_node * 274struct tree_node *
258delete(struct tree_node *tree, T data) 275delete(struct tree_node *tree, T data)
259{ 276{
260 bool h = false; 277 bool h = false;
261 return delete_r(data, tree, &h); 278 return delete_r(data, tree, &h);
262} 279}
263 280/* -->8-- */
264 281
265// aux display and verification routines, helpful but not essential 282// aux display and verification routines, helpful but not essential
266struct trunk { 283struct trunk {
diff --git a/deque.c b/deque.c
index 93cbe92..eec6f42 100644
--- a/deque.c
+++ b/deque.c
@@ -5,11 +5,12 @@
5 5
6#include "util.h" 6#include "util.h"
7 7
8typedef int T;
9
10#define START_MAP_CAPACITY 4 8#define START_MAP_CAPACITY 4
11#define CHUNK_CAPACITY 17 9#define CHUNK_CAPACITY 17
12 10
11/* --8<-- deque_type */
12typedef int T;
13
13struct deque { 14struct deque {
14 T **map; 15 T **map;
15 16
@@ -20,7 +21,9 @@ struct deque {
20 size_t offset; 21 size_t offset;
21 size_t size; 22 size_t size;
22}; 23};
24/* -->8-- */
23 25
26/* --8<-- deque_allocate */
24static void * 27static void *
25allocate(size_t n, size_t sz) 28allocate(size_t n, size_t sz)
26{ 29{
@@ -30,7 +33,9 @@ allocate(size_t n, size_t sz)
30 } 33 }
31 return ptr; 34 return ptr;
32} 35}
36/* -->8-- */
33 37
38/* --8<-- deque_init */
34void 39void
35deque_init(struct deque *d) 40deque_init(struct deque *d)
36{ 41{
@@ -51,7 +56,9 @@ deque_init(struct deque *d)
51 } 56 }
52 } 57 }
53} 58}
59/* -->8-- */
54 60
61/* --8<-- deque_free */
55void 62void
56deque_free(struct deque *d) 63deque_free(struct deque *d)
57{ 64{
@@ -66,7 +73,9 @@ deque_free(struct deque *d)
66 free(d->map); 73 free(d->map);
67 d->map = NULL; 74 d->map = NULL;
68} 75}
76/* -->8-- */
69 77
78/* --8<-- deque_size */
70size_t 79size_t
71deque_size(struct deque *d) 80deque_size(struct deque *d)
72{ 81{
@@ -74,7 +83,9 @@ deque_size(struct deque *d)
74 83
75 return d->size; 84 return d->size;
76} 85}
86/* -->8-- */
77 87
88/* --8<-- deque_is_empty */
78bool 89bool
79deque_is_empty(struct deque *d) 90deque_is_empty(struct deque *d)
80{ 91{
@@ -82,7 +93,9 @@ deque_is_empty(struct deque *d)
82 93
83 return d->map_begin == d->map_end; 94 return d->map_begin == d->map_end;
84} 95}
96/* -->8-- */
85 97
98/* --8<-- deque_grow_map */
86static void 99static void
87grow_map(struct deque *d) 100grow_map(struct deque *d)
88{ 101{
@@ -116,7 +129,9 @@ grow_map(struct deque *d)
116 // set new map_capacity 129 // set new map_capacity
117 d->map_capacity = capacity; 130 d->map_capacity = capacity;
118} 131}
132/* -->8-- */
119 133
134/* --8<-- deque_map_append_chunk */
120static void 135static void
121map_append_chunk(struct deque *d) 136map_append_chunk(struct deque *d)
122{ 137{
@@ -133,7 +148,9 @@ map_append_chunk(struct deque *d)
133 d->map[d->map_end] = allocate(CHUNK_CAPACITY, sizeof **d->map); 148 d->map[d->map_end] = allocate(CHUNK_CAPACITY, sizeof **d->map);
134 d->map_end = next; 149 d->map_end = next;
135} 150}
151/* -->8-- */
136 152
153/* --8<-- deque_map_prepend_chunk */
137static void 154static void
138map_prepend_chunk(struct deque *d) 155map_prepend_chunk(struct deque *d)
139{ 156{
@@ -150,7 +167,9 @@ map_prepend_chunk(struct deque *d)
150 d->map[prev] = allocate(CHUNK_CAPACITY, sizeof **d->map); 167 d->map[prev] = allocate(CHUNK_CAPACITY, sizeof **d->map);
151 d->map_begin = prev; 168 d->map_begin = prev;
152} 169}
170/* -->8-- */
153 171
172/* --8<-- deque_map_remove_front_chunk */
154static void 173static void
155map_remove_front_chunk(struct deque *d) 174map_remove_front_chunk(struct deque *d)
156{ 175{
@@ -167,7 +186,9 @@ map_remove_front_chunk(struct deque *d)
167 186
168 d->map_begin = next; 187 d->map_begin = next;
169} 188}
189/* -->8-- */
170 190
191/* --8<-- deque_remove_tail_chunk */
171static void 192static void
172map_remove_tail_chunk(struct deque *d) 193map_remove_tail_chunk(struct deque *d)
173{ 194{
@@ -184,7 +205,9 @@ map_remove_tail_chunk(struct deque *d)
184 205
185 d->map_end = prev; 206 d->map_end = prev;
186} 207}
208/* -->8-- */
187 209
210/* --8<-- deque_get_at */
188bool 211bool
189deque_get_at(struct deque *d, size_t idx, T *data) 212deque_get_at(struct deque *d, size_t idx, T *data)
190{ 213{
@@ -204,7 +227,9 @@ deque_get_at(struct deque *d, size_t idx, T *data)
204 227
205 return true; 228 return true;
206} 229}
230/* -->8-- */
207 231
232/* --8<-- deque_set_at */
208bool 233bool
209deque_set_at(struct deque *d, size_t idx, T data) 234deque_set_at(struct deque *d, size_t idx, T data)
210{ 235{
@@ -223,7 +248,9 @@ deque_set_at(struct deque *d, size_t idx, T data)
223 248
224 return true; 249 return true;
225} 250}
251/* -->8-- */
226 252
253/* --8<-- deque_push_back */
227void 254void
228deque_push_back(struct deque *d, T data) 255deque_push_back(struct deque *d, T data)
229{ 256{
@@ -241,7 +268,9 @@ deque_push_back(struct deque *d, T data)
241 d->map[chunk_num][chunk_off] = data; 268 d->map[chunk_num][chunk_off] = data;
242 ++d->size; 269 ++d->size;
243} 270}
271/* -->8-- */
244 272
273/* --8<-- deque_push_front */
245void 274void
246deque_push_front(struct deque *d, T data) 275deque_push_front(struct deque *d, T data)
247{ 276{
@@ -259,7 +288,9 @@ deque_push_front(struct deque *d, T data)
259 d->map[chunk_num][d->offset] = data; 288 d->map[chunk_num][d->offset] = data;
260 ++d->size; 289 ++d->size;
261} 290}
291/* -->8-- */
262 292
293/* --8<-- deque_pop_back */
263bool 294bool
264deque_pop_back(struct deque *d, T *data) 295deque_pop_back(struct deque *d, T *data)
265{ 296{
@@ -284,7 +315,9 @@ deque_pop_back(struct deque *d, T *data)
284 315
285 return true; 316 return true;
286} 317}
318/* -->8-- */
287 319
320/* --8<-- deque_pop_front */
288bool 321bool
289deque_pop_front(struct deque *d, T *data) 322deque_pop_front(struct deque *d, T *data)
290{ 323{
@@ -310,6 +343,7 @@ deque_pop_front(struct deque *d, T *data)
310 343
311 return true; 344 return true;
312} 345}
346/* -->8-- */
313 347
314static void 348static void
315deque_show(struct deque *d) 349deque_show(struct deque *d)
diff --git a/dlist.c b/dlist.c
index 32258e8..bb0ead9 100644
--- a/dlist.c
+++ b/dlist.c
@@ -10,6 +10,7 @@
10/* Project */ 10/* Project */
11#include "util.h" 11#include "util.h"
12 12
13/* --8<-- dlist_type */
13typedef int T; 14typedef int T;
14 15
15struct dlist { 16struct dlist {
@@ -20,20 +21,26 @@ struct dlist_element {
20 struct dlist_element *prev, *next; 21 struct dlist_element *prev, *next;
21 T data; 22 T data;
22}; 23};
24/* -->8-- */
23 25
26/* --8<-- dlist_init */
24void 27void
25dlist_init(struct dlist *dlist) 28dlist_init(struct dlist *dlist)
26{ 29{
27 dlist->head = NULL; 30 dlist->head = NULL;
28 dlist->tail = NULL; 31 dlist->tail = NULL;
29} 32}
33/* -->8-- */
30 34
35/* --8<-- dlist_empty */
31bool 36bool
32dlist_empty(struct dlist *dlist) 37dlist_empty(struct dlist *dlist)
33{ 38{
34 return dlist->head == NULL; 39 return dlist->head == NULL;
35} 40}
41/* -->8-- */
36 42
43/* --8<-- dlist_create_element */
37static struct dlist_element * 44static struct dlist_element *
38create_element(T data) 45create_element(T data)
39{ 46{
@@ -46,7 +53,9 @@ create_element(T data)
46 53
47 return element; 54 return element;
48} 55}
56/* -->8-- */
49 57
58/* --8<-- dlist_push_front */
50struct dlist_element * 59struct dlist_element *
51dlist_push_front(struct dlist *dlist, T data) 60dlist_push_front(struct dlist *dlist, T data)
52{ 61{
@@ -72,7 +81,9 @@ dlist_push_front(struct dlist *dlist, T data)
72 81
73 return element; 82 return element;
74} 83}
84/* -->8-- */
75 85
86/* --8<-- dlist_push_back */
76struct dlist_element * 87struct dlist_element *
77dlist_push_back(struct dlist *dlist, T data) 88dlist_push_back(struct dlist *dlist, T data)
78{ 89{
@@ -98,7 +109,9 @@ dlist_push_back(struct dlist *dlist, T data)
98 109
99 return element; 110 return element;
100} 111}
112/* -->8-- */
101 113
114/* --8<-- dlist_pop_front */
102bool 115bool
103dlist_pop_front(struct dlist *dlist, T *data) 116dlist_pop_front(struct dlist *dlist, T *data)
104{ 117{
@@ -122,7 +135,9 @@ dlist_pop_front(struct dlist *dlist, T *data)
122 else 135 else
123 return false; 136 return false;
124} 137}
138/* -->8-- */
125 139
140/* --8<-- dlist_pop_back */
126bool 141bool
127dlist_pop_back(struct dlist *dlist, T *data) 142dlist_pop_back(struct dlist *dlist, T *data)
128{ 143{
@@ -146,7 +161,9 @@ dlist_pop_back(struct dlist *dlist, T *data)
146 else 161 else
147 return false; 162 return false;
148} 163}
164/* -->8-- */
149 165
166/* --8<-- dlist_insert_next */
150struct dlist_element * 167struct dlist_element *
151dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data) 168dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data)
152{ 169{
@@ -177,7 +194,9 @@ dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data)
177 194
178 return new_element; 195 return new_element;
179} 196}
197/* -->8-- */
180 198
199/* --8<-- dlist_insert_prev */
181struct dlist_element * 200struct dlist_element *
182dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data) 201dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data)
183{ 202{
@@ -208,7 +227,9 @@ dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data)
208 227
209 return new_element; 228 return new_element;
210} 229}
230/* -->8-- */
211 231
232/* --8<-- dlist_remove */
212void 233void
213dlist_remove(struct dlist *dlist, struct dlist_element *element) 234dlist_remove(struct dlist *dlist, struct dlist_element *element)
214{ 235{
@@ -231,7 +252,9 @@ dlist_remove(struct dlist *dlist, struct dlist_element *element)
231 252
232 free(element); 253 free(element);
233} 254}
255/* -->8-- */
234 256
257/* --8<-- dlist_free */
235void 258void
236dlist_free(struct dlist *dlist) 259dlist_free(struct dlist *dlist)
237{ 260{
@@ -244,6 +267,7 @@ dlist_free(struct dlist *dlist)
244 267
245 dlist_init(dlist); 268 dlist_init(dlist);
246} 269}
270/* -->8-- */
247 271
248void 272void
249dlist_apply_rev(struct dlist *dlist, void (*visit)(T data, void *cl), void *cl) 273dlist_apply_rev(struct dlist *dlist, void (*visit)(T data, void *cl), void *cl)
@@ -289,6 +313,7 @@ remove_if(struct dlist *list)
289 } 313 }
290} 314}
291 315
316/* --8<-- dlist_merge */
292struct dlist * 317struct dlist *
293dlist_merge(struct dlist *list1, struct dlist *list2) 318dlist_merge(struct dlist *list1, struct dlist *list2)
294{ 319{
@@ -355,7 +380,9 @@ dlist_merge(struct dlist *list1, struct dlist *list2)
355 // Zeiger auf Liste1 zurückliefern 380 // Zeiger auf Liste1 zurückliefern
356 return list1; 381 return list1;
357} 382}
383/* -->8-- */
358 384
385/* --8<-- dlist_sort */
359struct dlist * 386struct dlist *
360dlist_sort(struct dlist *list) 387dlist_sort(struct dlist *list)
361{ 388{
@@ -380,6 +407,7 @@ dlist_sort(struct dlist *list)
380 407
381 return list; 408 return list;
382} 409}
410/* -->8-- */
383 411
384void 412void
385merge_test(void) 413merge_test(void)
diff --git a/hashtab.c b/hashtab.c
index 8a49baf..9f4e4a8 100644
--- a/hashtab.c
+++ b/hashtab.c
@@ -6,6 +6,7 @@
6 6
7#include "util.h" 7#include "util.h"
8 8
9/* --8<-- hash_type */
9typedef int T; 10typedef int T;
10 11
11struct hash_item { 12struct hash_item {
@@ -17,7 +18,9 @@ struct hash_item {
17struct hash_tab { 18struct hash_tab {
18 struct hash_item *table[251]; // fit for your needs... 19 struct hash_item *table[251]; // fit for your needs...
19}; 20};
21/* -->8-- */
20 22
23/* --8<-- hash_key */
21static unsigned long 24static unsigned long
22hash_key(const unsigned char *str) 25hash_key(const unsigned char *str)
23{ 26{
@@ -29,14 +32,18 @@ hash_key(const unsigned char *str)
29 32
30 return hash; 33 return hash;
31} 34}
35/* -->8-- */
32 36
37/* --8<-- hash_init */
33void 38void
34hash_init(struct hash_tab *ht) 39hash_init(struct hash_tab *ht)
35{ 40{
36 for ( size_t i = 0; i != NELEM(ht->table); ++i ) 41 for ( size_t i = 0; i != NELEM(ht->table); ++i )
37 ht->table[i] = NULL; 42 ht->table[i] = NULL;
38} 43}
44/* -->8-- */
39 45
46/* --8<-- hash_add */
40static struct hash_item * 47static struct hash_item *
41hash_add(struct hash_item *next, const char *key, T data) 48hash_add(struct hash_item *next, const char *key, T data)
42{ 49{
@@ -59,7 +66,9 @@ hash_add(struct hash_item *next, const char *key, T data)
59 66
60 return new_item; 67 return new_item;
61} 68}
69/* -->8-- */
62 70
71/* --8<-- hash_lookup */
63T * 72T *
64hash_lookup(struct hash_tab *ht, const char *key, T data, int create) 73hash_lookup(struct hash_tab *ht, const char *key, T data, int create)
65{ 74{
@@ -82,7 +91,9 @@ hash_lookup(struct hash_tab *ht, const char *key, T data, int create)
82 91
83 return item ? &item->data : NULL; 92 return item ? &item->data : NULL;
84} 93}
94/* -->8-- */
85 95
96/* --8<-- hash_delete */
86bool 97bool
87hash_delete(struct hash_tab *ht, const char *key) 98hash_delete(struct hash_tab *ht, const char *key)
88{ 99{
@@ -108,7 +119,9 @@ hash_delete(struct hash_tab *ht, const char *key)
108 119
109 return false; 120 return false;
110} 121}
122/* -->8-- */
111 123
124/* --8<-- hash_apply */
112void 125void
113hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl) 126hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl)
114{ 127{
@@ -118,7 +131,9 @@ hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl)
118 for ( item = ht->table[i]; item; item = item->next ) 131 for ( item = ht->table[i]; item; item = item->next )
119 visit(item->key, item->data, cl); 132 visit(item->key, item->data, cl);
120} 133}
134/* -->8-- */
121 135
136/* --8<-- hash_free */
122void 137void
123hash_free(struct hash_tab *ht) 138hash_free(struct hash_tab *ht)
124{ 139{
@@ -133,6 +148,7 @@ hash_free(struct hash_tab *ht)
133 ht->table[i] = NULL; 148 ht->table[i] = NULL;
134 } 149 }
135} 150}
151/* -->8-- */
136 152
137static int 153static int
138getword(FILE *fp, char *buf, size_t size, int first(int), int rest(int)) 154getword(FILE *fp, char *buf, size_t size, int first(int), int rest(int))
diff --git a/list-tail-node.c b/list-tail-node.c
index 158fae8..4e40912 100644
--- a/list-tail-node.c
+++ b/list-tail-node.c
@@ -6,6 +6,7 @@
6/* Project */ 6/* Project */
7#include "util.h" 7#include "util.h"
8 8
9/* --8<-- list_tail_type */
9typedef int T; 10typedef int T;
10 11
11struct list_node { 12struct list_node {
@@ -16,13 +17,17 @@ struct list_node {
16struct list { 17struct list {
17 struct list_node *head, *tail; 18 struct list_node *head, *tail;
18}; 19};
20/* -->8-- */
19 21
22/* --8<-- list_tail_init */
20void 23void
21list_init(struct list *list) 24list_init(struct list *list)
22{ 25{
23 list->head = NULL; 26 list->head = NULL;
24} 27}
28/* -->8-- */
25 29
30/* --8<-- list_tail_create_node */
26static struct list_node * 31static struct list_node *
27create_node(struct list_node *next, T data) 32create_node(struct list_node *next, T data)
28{ 33{
@@ -34,7 +39,9 @@ create_node(struct list_node *next, T data)
34 } 39 }
35 return node; 40 return node;
36} 41}
42/* -->8-- */
37 43
44/* --8<-- list_tail_push_back */
38void 45void
39list_push_back(struct list *list, T data) 46list_push_back(struct list *list, T data)
40{ 47{
@@ -53,7 +60,9 @@ list_push_back(struct list *list, T data)
53 ERROR("out of memory"); 60 ERROR("out of memory");
54 } 61 }
55} 62}
63/* -->8-- */
56 64
65/* --8<-- list_tail_front */
57void 66void
58list_push_front(struct list *list, T data) 67list_push_front(struct list *list, T data)
59{ 68{
@@ -69,7 +78,9 @@ list_push_front(struct list *list, T data)
69 ERROR("out of memory"); 78 ERROR("out of memory");
70 } 79 }
71} 80}
81/* -->8-- */
72 82
83/* --8<-- list_tail_pop_front */
73bool 84bool
74list_pop_front(struct list *list, T *data) 85list_pop_front(struct list *list, T *data)
75{ 86{
@@ -88,7 +99,9 @@ list_pop_front(struct list *list, T *data)
88 return false; 99 return false;
89 } 100 }
90} 101}
102/* -->8-- */
91 103
104/* --8<-- list_tail_insert_next */
92void 105void
93list_insert_next(struct list *list, struct list_node *node, T data) 106list_insert_next(struct list *list, struct list_node *node, T data)
94{ 107{
@@ -109,7 +122,9 @@ list_insert_next(struct list *list, struct list_node *node, T data)
109 } 122 }
110 } 123 }
111} 124}
125/* -->8-- */
112 126
127/* --8<-- list_tail_delete_next */
113void 128void
114list_delete_next(struct list *list, struct list_node *node, T *data) 129list_delete_next(struct list *list, struct list_node *node, T *data)
115{ 130{
@@ -132,13 +147,17 @@ list_delete_next(struct list *list, struct list_node *node, T *data)
132 } 147 }
133 } 148 }
134} 149}
150/* -->8-- */
135 151
152/* --8<-- list_tail_empty */
136bool 153bool
137list_empty(struct list *list) 154list_empty(struct list *list)
138{ 155{
139 return list->head == NULL; 156 return list->head == NULL;
140} 157}
158/* -->8-- */
141 159
160/* --8<-- list_tail_free */
142void 161void
143list_free(struct list *list) 162list_free(struct list *list)
144{ 163{
@@ -149,6 +168,7 @@ list_free(struct list *list)
149 free(item); 168 free(item);
150 } 169 }
151} 170}
171/* -->8-- */
152 172
153int 173int
154main() 174main()
diff --git a/list.c b/list.c
index da0c702..24024da 100644
--- a/list.c
+++ b/list.c
@@ -9,13 +9,16 @@
9/* Project */ 9/* Project */
10#include "util.h" 10#include "util.h"
11 11
12/* --8<-- list_type */
12typedef int T; 13typedef int T;
13 14
14struct list_item { 15struct list_item {
15 struct list_item *next; 16 struct list_item *next;
16 T data; 17 T data;
17}; 18};
19/* -->8-- */
18 20
21/* --8<-- list_add */
19struct list_item * 22struct list_item *
20list_add(struct list_item *next, T data) 23list_add(struct list_item *next, T data)
21{ 24{
@@ -31,7 +34,9 @@ list_add(struct list_item *next, T data)
31 34
32 return new_item; 35 return new_item;
33} 36}
37/* -->8-- */
34 38
39/* --8<-- list_insert_next */
35void 40void
36list_insert_next(struct list_item *list, T data) 41list_insert_next(struct list_item *list, T data)
37{ 42{
@@ -47,7 +52,9 @@ list_insert_next(struct list_item *list, T data)
47 else 52 else
48 ERROR("out of memory"); 53 ERROR("out of memory");
49} 54}
55/* -->8-- */
50 56
57/* --8<-- list_delete */
51struct list_item * 58struct list_item *
52list_delete(struct list_item *list, T data) 59list_delete(struct list_item *list, T data)
53{ 60{
@@ -68,10 +75,14 @@ list_delete(struct list_item *list, T data)
68 } 75 }
69 prev = p; 76 prev = p;
70 } 77 }
71 //ERROR("data not found"); /* uncomment, if this case should be reported as an error */ 78#if LIST_REPORT_ERROR
79 ERROR("data not found");
80#endif
72 return list; 81 return list;
73} 82}
83/* -->8-- */
74 84
85/* --8<-- list_delete_next */
75void 86void
76list_delete_next(struct list_item *list) 87list_delete_next(struct list_item *list)
77{ 88{
@@ -83,7 +94,9 @@ list_delete_next(struct list_item *list)
83 free(temp); 94 free(temp);
84 } 95 }
85} 96}
97/* -->8-- */
86 98
99/* --8<-- list_length */
87size_t 100size_t
88list_length(struct list_item *list) 101list_length(struct list_item *list)
89{ 102{
@@ -94,7 +107,9 @@ list_length(struct list_item *list)
94 107
95 return len; 108 return len;
96} 109}
110/* -->8-- */
97 111
112/* --8<-- list_copy */
98struct list_item * 113struct list_item *
99list_copy(struct list_item *list) 114list_copy(struct list_item *list)
100{ 115{
@@ -112,7 +127,9 @@ list_copy(struct list_item *list)
112 *p = NULL; 127 *p = NULL;
113 return head; 128 return head;
114} 129}
130/* -->8-- */
115 131
132/* --8<-- list_reverse */
116struct list_item * 133struct list_item *
117list_reverse(struct list_item *list) 134list_reverse(struct list_item *list)
118{ 135{
@@ -125,7 +142,9 @@ list_reverse(struct list_item *list)
125 } 142 }
126 return head; 143 return head;
127} 144}
145/* -->8-- */
128 146
147/* --8<-- list_apply */
129void 148void
130list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl) 149list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl)
131{ 150{
@@ -133,7 +152,9 @@ list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl)
133 visit(list->data, cl); 152 visit(list->data, cl);
134 } 153 }
135} 154}
155/* -->8-- */
136 156
157/* --8<-- list_merge */
137struct list_item * 158struct list_item *
138list_merge(struct list_item *a, struct list_item *b) 159list_merge(struct list_item *a, struct list_item *b)
139{ 160{
@@ -150,7 +171,9 @@ list_merge(struct list_item *a, struct list_item *b)
150 171
151 return head->next; 172 return head->next;
152} 173}
174/* -->8-- */
153 175
176/* --8<-- list_sort */
154struct list_item * 177struct list_item *
155list_sort(struct list_item *c) 178list_sort(struct list_item *c)
156{ 179{
@@ -167,7 +190,9 @@ list_sort(struct list_item *c)
167 190
168 return list_merge(list_sort(a), list_sort(b)); 191 return list_merge(list_sort(a), list_sort(b));
169} 192}
193/* -->8-- */
170 194
195/* --8<-- list_free */
171void 196void
172list_free(struct list_item *list) 197list_free(struct list_item *list)
173{ 198{
@@ -178,12 +203,15 @@ list_free(struct list_item *list)
178 free(list); 203 free(list);
179 } 204 }
180} 205}
206/* -->8-- */
181 207
208/* --8<-- list_apply_sample */
182static void 209static void
183print_data(T data, void *cl) 210print_data(T data, void *cl)
184{ 211{
185 fprintf(cl, "%d\n", data); 212 fprintf(cl, "%d\n", data);
186} 213}
214/* -->8-- */
187 215
188int 216int
189main() 217main()
diff --git a/queue.c b/queue.c
index 2fb9c72..dab5bfb 100644
--- a/queue.c
+++ b/queue.c
@@ -6,6 +6,7 @@
6/* Project */ 6/* Project */
7#include "util.h" 7#include "util.h"
8 8
9/* --8<-- queue_type */
9typedef int T; 10typedef int T;
10 11
11struct queue_item { 12struct queue_item {
@@ -16,13 +17,17 @@ struct queue_item {
16struct queue { 17struct queue {
17 struct queue_item *head, *tail; 18 struct queue_item *head, *tail;
18}; 19};
20/* -->8-- */
19 21
22/* --8<-- queue_init */
20void 23void
21queue_init(struct queue *queue) 24queue_init(struct queue *queue)
22{ 25{
23 queue->head = NULL; 26 queue->head = NULL;
24} 27}
28/* -->8-- */
25 29
30/* --8<-- queue_put */
26void 31void
27queue_put(struct queue *queue, T data) 32queue_put(struct queue *queue, T data)
28{ 33{
@@ -41,7 +46,9 @@ queue_put(struct queue *queue, T data)
41 else 46 else
42 ERROR("out of memory"); 47 ERROR("out of memory");
43} 48}
49/* -->8-- */
44 50
51/* --8<-- queue_get */
45bool 52bool
46queue_get(struct queue *queue, T *data) 53queue_get(struct queue *queue, T *data)
47{ 54{
@@ -59,13 +66,17 @@ queue_get(struct queue *queue, T *data)
59 else 66 else
60 return false; 67 return false;
61} 68}
69/* -->8-- */
62 70
71/* --8<-- queue_empty */
63bool 72bool
64queue_empty(struct queue *queue) 73queue_empty(struct queue *queue)
65{ 74{
66 return queue->head == NULL; 75 return queue->head == NULL;
67} 76}
77/* -->8-- */
68 78
79/* --8<-- queue_free */
69void 80void
70queue_free(struct queue *queue) 81queue_free(struct queue *queue)
71{ 82{
@@ -76,6 +87,7 @@ queue_free(struct queue *queue)
76 free(item); 87 free(item);
77 } 88 }
78} 89}
90/* -->8-- */
79 91
80int 92int
81main() 93main()
diff --git a/quicksort.c b/quicksort.c
index fa219e9..4657dcd 100644
--- a/quicksort.c
+++ b/quicksort.c
@@ -1,10 +1,12 @@
1#include <assert.h>
1#include <stdio.h> 2#include <stdio.h>
2#include <stdlib.h> 3#include <stdlib.h>
3#include <assert.h>
4#include <time.h> 4#include <time.h>
5
5#include "util.h" 6#include "util.h"
6 7
7static int bigrand(void) 8static int
9bigrand(void)
8{ 10{
9 int x = (rand() << 24) | (rand() << 16) | (rand() << 8) | rand(); 11 int x = (rand() << 24) | (rand() << 16) | (rand() << 8) | rand();
10 if ( x < 0 ) 12 if ( x < 0 )
@@ -12,9 +14,10 @@ static int bigrand(void)
12 return x; 14 return x;
13} 15}
14 16
15static int randint(int l, int u) 17static int
18randint(int l, int u)
16{ 19{
17 return l + bigrand() % (u-l+1); 20 return l + bigrand() % (u - l + 1);
18} 21}
19 22
20typedef int T; 23typedef int T;
@@ -24,7 +27,7 @@ static const int CUTOFF = 128;
24static inline void 27static inline void
25swap(T a[], int i, int j) 28swap(T a[], int i, int j)
26{ 29{
27 T t = a[i]; 30 T t = a[i];
28 a[i] = a[j]; 31 a[i] = a[j];
29 a[j] = t; 32 a[j] = t;
30} 33}
@@ -33,11 +36,10 @@ static void
33insertsort(T a[], int n) 36insertsort(T a[], int n)
34{ 37{
35 int i, j; 38 int i, j;
36 for ( i = 1; i < n; ++i ) 39 for ( i = 1; i < n; ++i ) {
37 {
38 T t = a[i]; 40 T t = a[i];
39 for ( j = i; j > 0 && a[j-1] > t; --j ) 41 for ( j = i; j > 0 && a[j - 1] > t; --j )
40 a[j] = a[j-1]; 42 a[j] = a[j - 1];
41 a[j] = t; 43 a[j] = t;
42 } 44 }
43} 45}
@@ -60,7 +62,7 @@ quicksort(T a[], int n)
60 swap(a, 0, last); 62 swap(a, 0, last);
61 63
62 quicksort(a, last); 64 quicksort(a, last);
63 quicksort(a+last+1, n-last-1); 65 quicksort(a + last + 1, n - last - 1);
64} 66}
65 67
66void 68void
@@ -70,22 +72,24 @@ my_quicksort(T a[], int n)
70 insertsort(a, n); 72 insertsort(a, n);
71} 73}
72 74
73
74static int 75static int
75cmp(const void *a, const void *b) 76cmp(const void *a, const void *b)
76{ 77{
77 const int *pa = (const T *) a; 78 const int *pa = (const T *) a;
78 const int *pb = (const T *) b; 79 const int *pb = (const T *) b;
79 80
80 if ( *pa < *pb ) return -1; 81 if ( *pa < *pb )
81 if ( *pa > *pb ) return 1; 82 return -1;
83 if ( *pa > *pb )
84 return 1;
82 return 0; 85 return 0;
83} 86}
84 87
85void 88void
86c_quicksort(T a[], int n) 89c_quicksort(T a[], int n)
87{ 90{
88 qsort(a, n, sizeof(T), cmp); 91 assert(n >= 0);
92 qsort(a, (size_t) n, sizeof(T), cmp);
89} 93}
90 94
91/* This function takes last element as pivot, places 95/* This function takes last element as pivot, places
@@ -93,65 +97,63 @@ c_quicksort(T a[], int n)
93 array, and places all smaller (smaller than pivot) 97 array, and places all smaller (smaller than pivot)
94 to left of pivot and all greater elements to right 98 to left of pivot and all greater elements to right
95 of pivot */ 99 of pivot */
96int partition (int arr[], int low, int high) 100int
101partition(int arr[], int low, int high)
97{ 102{
98 int pivot = arr[high]; // pivot 103 int pivot = arr[high]; // pivot
99 int i = (low - 1); // Index of smaller element 104 int i = (low - 1); // Index of smaller element
100 105
101 for (int j = low; j <= high- 1; j++) 106 for ( int j = low; j <= high - 1; j++ ) {
102 { 107 // If current element is smaller than or
103 // If current element is smaller than or 108 // equal to pivot
104 // equal to pivot 109 if ( arr[j] <= pivot ) {
105 if (arr[j] <= pivot) 110 i++; // increment index of smaller element
106 { 111 swap(arr, i, j);
107 i++; // increment index of smaller element 112 }
108 swap(arr, i, j); 113 }
109 } 114 swap(arr, i + 1, high);
110 } 115 return (i + 1);
111 swap(arr, i + 1, high);
112 return (i + 1);
113} 116}
114 117
115/* The main function that implements QuickSort 118/* The main function that implements QuickSort
116 arr[] --> Array to be sorted, 119 arr[] --> Array to be sorted,
117 low --> Starting index, 120 low --> Starting index,
118 high --> Ending index */ 121 high --> Ending index */
119void quickSort(int arr[], int low, int high) 122void
123quickSort(int arr[], int low, int high)
120{ 124{
121 while (low < high) 125 while ( low < high ) {
122 { 126 /* pi is partitioning index, arr[p] is now
123 /* pi is partitioning index, arr[p] is now
124 at right place */ 127 at right place */
125 int pi = partition(arr, low, high); 128 int pi = partition(arr, low, high);
126 129
127 if (pi - low < high - pi) 130 if ( pi - low < high - pi ) {
128 {
129 quickSort(arr, low, pi - 1); 131 quickSort(arr, low, pi - 1);
130 low = pi + 1; 132 low = pi + 1;
131 } 133 }
132 else 134 else {
133 {
134 quickSort(arr, pi + 1, high); 135 quickSort(arr, pi + 1, high);
135 high = pi - 1; 136 high = pi - 1;
136 } 137 }
137 } 138 }
138} 139}
139 140
140void g4g_quicksort(T a[], int n) 141void
142g4g_quicksort(T a[], int n)
141{ 143{
142 quickSort(a, 0, n-1); 144 quickSort(a, 0, n - 1);
143} 145}
144 146
145 147static void
146static void three_way_quicksort(int a[], int l, int r) 148three_way_quicksort(int a[], int l, int r)
147{ 149{
148 int k; 150 int k;
149 T v = a[r]; 151 T v = a[r];
150 152
151 if ( r <= l ) 153 if ( r <= l )
152 return; 154 return;
153 155
154 int i = l-1, j = r, p = l-1, q = r; 156 int i = l - 1, j = r, p = l - 1, q = r;
155 157
156 for ( ;; ) { 158 for ( ;; ) {
157 while ( a[++i] < v ) 159 while ( a[++i] < v )
@@ -169,27 +171,30 @@ static void three_way_quicksort(int a[], int l, int r)
169 if ( v == a[j] ) 171 if ( v == a[j] )
170 swap(a, --q, j); 172 swap(a, --q, j);
171 } 173 }
172 swap(a, i, r); j = i-1; i = i+1; 174 swap(a, i, r);
175 j = i - 1;
176 i = i + 1;
173 177
174 for ( k = l ; k <= p; ++k, --j ) 178 for ( k = l; k <= p; ++k, --j )
175 swap(a, k, j); 179 swap(a, k, j);
176 for ( k = r-1; k >= q; --k, ++i ) 180 for ( k = r - 1; k >= q; --k, ++i )
177 swap(a, k, i); 181 swap(a, k, i);
178 182
179 three_way_quicksort(a, l, j); 183 three_way_quicksort(a, l, j);
180 three_way_quicksort(a, i, r); 184 three_way_quicksort(a, i, r);
181} 185}
182 186
183void sed_quicksort(int a[], int n) 187void
188sed_quicksort(int a[], int n)
184{ 189{
185 three_way_quicksort(a, 0, n-1); 190 three_way_quicksort(a, 0, n - 1);
186} 191}
187 192
188/* ====================== HEAPSORT ======================= */ 193/* ====================== HEAPSORT ======================= */
189 194
190#define LEFT(idx) (idx*2+1) 195#define LEFT(idx) (idx * 2 + 1)
191#define RIGHT(idx) (idx*2+2) 196#define RIGHT(idx) (idx * 2 + 2)
192#define PARENT(idx) ((idx-1)/2) 197#define PARENT(idx) ((idx - 1) / 2)
193 198
194static void 199static void
195fixdown(T heap[], int i, int n) 200fixdown(T heap[], int i, int n)
@@ -197,7 +202,7 @@ fixdown(T heap[], int i, int n)
197 for ( ;; ) { 202 for ( ;; ) {
198 const int l = LEFT(i); 203 const int l = LEFT(i);
199 const int r = RIGHT(i); 204 const int r = RIGHT(i);
200 int m = i; 205 int m = i;
201 206
202 if ( l < n && heap[m] < heap[l] ) 207 if ( l < n && heap[m] < heap[l] )
203 m = l; 208 m = l;
@@ -226,76 +231,73 @@ my_heapsort(T a[], int n)
226{ 231{
227 heapify(a, n); 232 heapify(a, n);
228 233
229 for ( int i = n-1; i >= 0; --i ) { 234 for ( int i = n - 1; i >= 0; --i ) {
230 swap(a, 0, i); 235 swap(a, 0, i);
231 fixdown(a, 0, i); 236 fixdown(a, 0, i);
232 } 237 }
233} 238}
234 239
235void 240void
236heapsort_bu( T * data, int n ) // zu sortierendes Feld und seine Länge 241heapsort_bu(T *data, int n) // zu sortierendes Feld und seine Länge
237{ 242{
238 T val; 243 T val;
239 int parent, child; 244 int parent, child;
240 int root= n >> 1; // erstes Blatt im Baum 245 int root = n >> 1; // erstes Blatt im Baum
241 int count= 0; // Zähler für Anzahl der Vergleiche 246 int count = 0; // Zähler für Anzahl der Vergleiche
242 247
243 for ( ; ; ) 248 for ( ;; ) {
244 { 249 if ( root ) { // Teil 1: Konstruktion des Heaps
245 if ( root ) { // Teil 1: Konstruktion des Heaps 250 parent = --root;
246 parent= --root; 251 val = data[root]; // zu versickernder Wert
247 val= data[root]; // zu versickernder Wert
248 } 252 }
249 else 253 else if ( --n ) { // Teil 2: eigentliche Sortierung
250 if ( --n ) { // Teil 2: eigentliche Sortierung 254 val = data[n]; // zu versickernder Wert vom Heap-Ende
251 val= data[n]; // zu versickernder Wert vom Heap-Ende 255 data[n] = data[0]; // Spitze des Heaps hinter den Heap in
252 data[n]= data[0]; // Spitze des Heaps hinter den Heap in 256 parent = 0; // den sortierten Bereich verschieben
253 parent= 0; // den sortierten Bereich verschieben 257 }
254 } 258 else // Heap ist leer; Sortierung beendet
255 else // Heap ist leer; Sortierung beendet 259 break;
256 break;
257 260
258 while ( (child= (parent + 1) << 1) < n ) // zweites (!) Kind; 261 while ( (child = (parent + 1) << 1) < n ) // zweites (!) Kind;
259 { // Abbruch am Ende des Heaps 262 { // Abbruch am Ende des Heaps
260 if ( ++count, data[child-1] > data[child] ) // größeres Kind wählen 263 if ( ++count, data[child - 1] > data[child] ) // größeres Kind wählen
261 --child; 264 --child;
262 265
263 data[parent]= data[child]; // größeres Kind nach oben rücken 266 data[parent] = data[child]; // größeres Kind nach oben rücken
264 parent= child; // in der Ebene darunter weitersuchen 267 parent = child; // in der Ebene darunter weitersuchen
265 } 268 }
266 269
267 if ( child == n ) // ein einzelnes Kind am Heap-Ende 270 if ( child == n ) // ein einzelnes Kind am Heap-Ende
268 { // ist übersprungen worden 271 { // ist übersprungen worden
269 if ( ++count, data[--child] >= val ) { // größer als der zu versick- 272 if ( ++count, data[--child] >= val ) { // größer als der zu versick-
270 data[parent]= data[child]; // ernde Wert, also noch nach oben 273 data[parent] = data[child]; // ernde Wert, also noch nach oben
271 data[child]= val; // versickerten Wert eintragen 274 data[child] = val; // versickerten Wert eintragen
272 continue; 275 continue;
273 } 276 }
274 277
275 child= parent; // 1 Ebene nach oben zurück 278 child = parent; // 1 Ebene nach oben zurück
276 } 279 }
277 else 280 else {
278 { 281 if ( ++count, data[parent] >= val ) { // das Blatt ist größer als der
279 if ( ++count, data[parent] >= val ) { // das Blatt ist größer als der 282 data[parent] = val; // zu versickernde Wert, der damit
280 data[parent]= val; // zu versickernde Wert, der damit 283 continue; // direkt eingetragen werden kann
281 continue; // direkt eingetragen werden kann
282 } 284 }
283 285
284 child= (parent - 1) >> 1; // 2 Ebenen nach oben zurück 286 child = (parent - 1) >> 1; // 2 Ebenen nach oben zurück
285 } 287 }
286 288
287 while ( child != root ) // maximal zum Ausgangspunkt zurück 289 while ( child != root ) // maximal zum Ausgangspunkt zurück
288 { 290 {
289 parent= (child - 1) >> 1; // den Vergleichswert haben wir bereits 291 parent = (child - 1) >> 1; // den Vergleichswert haben wir bereits
290 // nach oben verschoben 292 // nach oben verschoben
291 if ( ++count, data[parent] >= val ) // größer als der zu versickernde 293 if ( ++count, data[parent] >= val ) // größer als der zu versickernde
292 break; // Wert, also Position gefunden 294 break; // Wert, also Position gefunden
293 295
294 data[child]= data[parent]; // Rückverschiebung nötig 296 data[child] = data[parent]; // Rückverschiebung nötig
295 child= parent; // 1 Ebene nach oben zurück 297 child = parent; // 1 Ebene nach oben zurück
296 } 298 }
297 299
298 data[child]= val; // versickerten Wert eintragen 300 data[child] = val; // versickerten Wert eintragen
299 } 301 }
300} 302}
301 303
@@ -315,65 +317,67 @@ heapsort_bu( T * data, int n ) // zu sortierendes Feld und seine Länge
315/* the original v[i] element from the leaf level up. This is the main */ 317/* the original v[i] element from the leaf level up. This is the main */
316/* idea of bottom-up heapsort. */ 318/* idea of bottom-up heapsort. */
317/*-----------------------------------------------------------------------*/ 319/*-----------------------------------------------------------------------*/
318static void siftup(T v[], int i, int n) 320static void
321siftup(T v[], int i, int n)
319{ 322{
320 int j, start; 323 int j, start;
321 T x; 324 T x;
322 325
323 start = i; 326 start = i;
324 x = v[i]; 327 x = v[i];
325 j = i<<1; 328 j = i << 1;
326 while (j<=n) 329 while ( j <= n ) {
327 { 330 if ( j < n )
328 if (j<n) 331 if ( v[j] < v[j + 1] )
329 if (v[j]<v[j+1])
330 j++; 332 j++;
331 v[i] = v[j]; 333 v[i] = v[j];
332 i = j; j = i<<1; 334 i = j;
335 j = i << 1;
333 } 336 }
334 j = i>>1; 337 j = i >> 1;
335 while (j>=start) 338 while ( j >= start ) {
336 { if (v[j]<x) 339 if ( v[j] < x ) {
337 { v[i] = v[j]; 340 v[i] = v[j];
338 i = j; j = i>>1; 341 i = j;
342 j = i >> 1;
339 } 343 }
340 else break; 344 else
345 break;
341 } 346 }
342 v[i] = x; 347 v[i] = x;
343} /* End of siftup */ 348} /* End of siftup */
344 349
345/*----------------------------------------------------------------------*/ 350/*----------------------------------------------------------------------*/
346/* The heapsort procedure; the original array is r[0..n-1], but here */ 351/* The heapsort procedure; the original array is r[0..n-1], but here */
347/* it is shifted to vector v[1..n], for convenience. */ 352/* it is shifted to vector v[1..n], for convenience. */
348/*----------------------------------------------------------------------*/ 353/*----------------------------------------------------------------------*/
349void bottom_up_heapsort(T r[], int n) 354void
355bottom_up_heapsort(T r[], int n)
350{ 356{
351 int k; 357 int k;
352 T x; 358 T x;
353 T *v; 359 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
360/* The main loop of sorting follows. The root is swapped with the last */ 361 v = r - 1; /* The address shift */
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 362
363 /* Build the heap bottom-up, using siftup. */
364 for ( k = n >> 1; k > 1; k-- )
365 siftup(v, k, n);
369 366
367 /* The main loop of sorting follows. The root is swapped with the last */
368 /* leaf after each sift-up. */
369 for ( k = n; k > 1; k-- ) {
370 siftup(v, 1, k);
371 x = v[k];
372 v[k] = v[1];
373 v[1] = x;
374 }
375} /* End of bottom_up_heapsort */
370 376
371/* ====================== HEAPSORT ======================= */ 377/* ====================== HEAPSORT ======================= */
372 378
373/* ====================== INTROSORT ======================= */ 379/* ====================== INTROSORT ======================= */
374 380
375
376
377static void 381static void
378introsort(T a[], int n, int h) 382introsort(T a[], int n, int h)
379{ 383{
@@ -397,7 +401,7 @@ introsort(T a[], int n, int h)
397 swap(a, 0, last); 401 swap(a, 0, last);
398 402
399 introsort(a, last, h); 403 introsort(a, last, h);
400 introsort(a+last+1, n-last-1, h); 404 introsort(a + last + 1, n - last - 1, h);
401} 405}
402 406
403void 407void
@@ -412,67 +416,74 @@ my_introsort(T a[], int n)
412 insertsort(a, n); 416 insertsort(a, n);
413} 417}
414 418
415static void pp_quicksort_impl(T a[], int l, int u) 419static void
420pp_quicksort_impl(T a[], int l, int u)
416{ 421{
417 if ( u - l < CUTOFF ) 422 if ( u - l < CUTOFF )
418 return; 423 return;
419 424
420 swap(a, l, randint(l, u)); 425 swap(a, l, randint(l, u));
421 426
422 T t = a[l]; 427 T t = a[l];
423 int i = l; 428 int i = l;
424 int j = u+1; 429 int j = u + 1;
425 for (;;) { 430 for ( ;; ) {
426 do i++; while ( /*i <= u &&*/ a[i] < t ); 431 do
427 do j--; while ( a[j] > t ); 432 i++;
433 while ( /*i <= u &&*/ a[i] < t );
434 do
435 j--;
436 while ( a[j] > t );
428 if ( i > j ) 437 if ( i > j )
429 break; 438 break;
430 swap(a, i, j); 439 swap(a, i, j);
431 } 440 }
432 swap(a, l, j); 441 swap(a, l, j);
433 pp_quicksort_impl(a, l, j-1); 442 pp_quicksort_impl(a, l, j - 1);
434 pp_quicksort_impl(a, j+1, u); 443 pp_quicksort_impl(a, j + 1, u);
435} 444}
436 445
437void 446void
438pp_quicksort(T a[], int n) 447pp_quicksort(T a[], int n)
439{ 448{
440 pp_quicksort_impl(a, 0, n-1); 449 pp_quicksort_impl(a, 0, n - 1);
441 insertsort(a, n); 450 insertsort(a, n);
442} 451}
443 452
444static void pp_quicksort_impl_it(T a[], int l, int u, int h) 453static void
454pp_quicksort_impl_it(T a[], int l, int u, int h)
445{ 455{
446 if ( --h == 1 ) { 456 if ( --h == 1 ) {
447 my_heapsort(a+l, u-l+1); 457 my_heapsort(a + l, u - l + 1);
448 return; 458 return;
449 } 459 }
450 460
451 while ( u-l >= CUTOFF ) 461 while ( u - l >= CUTOFF ) {
452 {
453 swap(a, l, randint(l, u)); 462 swap(a, l, randint(l, u));
454 463
455 T t = a[l]; 464 T t = a[l];
456 int i = l; 465 int i = l;
457 int j = u+1; 466 int j = u + 1;
458 467
459 for (;;) { 468 for ( ;; ) {
460 do i++; while ( /*i <= u && */ a[i] < t ); 469 do
461 do j--; while ( a[j] > t ); 470 i++;
471 while ( /*i <= u && */ a[i] < t );
472 do
473 j--;
474 while ( a[j] > t );
462 if ( i > j ) 475 if ( i > j )
463 break; 476 break;
464 swap(a, i, j); 477 swap(a, i, j);
465 } 478 }
466 swap(a, l, j); 479 swap(a, l, j);
467 480
468 if ( j - l < u - j ) 481 if ( j - l < u - j ) {
469 { 482 pp_quicksort_impl_it(a, l, j - 1, h);
470 pp_quicksort_impl_it(a, l, j-1, h);
471 l = j + 1; 483 l = j + 1;
472 } 484 }
473 else 485 else {
474 { 486 pp_quicksort_impl_it(a, j + 1, u, h);
475 pp_quicksort_impl_it(a, j+1, u, h);
476 u = j - 1; 487 u = j - 1;
477 } 488 }
478 } 489 }
@@ -486,7 +497,7 @@ pp_quicksort_it(T a[], int n)
486 for ( int nn = 1; nn < n; nn <<= 1 ) 497 for ( int nn = 1; nn < n; nn <<= 1 )
487 ++h; 498 ++h;
488 499
489 pp_quicksort_impl_it(a, 0, n-1, h); 500 pp_quicksort_impl_it(a, 0, n - 1, h);
490 insertsort(a, n); 501 insertsort(a, n);
491} 502}
492 503
@@ -495,8 +506,8 @@ binary_search(T x, T v[], int n)
495{ 506{
496 int low, high; 507 int low, high;
497 508
498 low = 0; 509 low = 0;
499 high = n-1; 510 high = n - 1;
500 while ( low <= high ) { 511 while ( low <= high ) {
501 int mid = low + ((high - low) / 2); 512 int mid = low + ((high - low) / 2);
502 if ( x > v[mid] ) 513 if ( x > v[mid] )
@@ -514,7 +525,7 @@ lower_bound(T x, T v[], int n)
514{ 525{
515 int low, high; 526 int low, high;
516 527
517 low = 0; 528 low = 0;
518 high = n; 529 high = n;
519 while ( low < high ) { 530 while ( low < high ) {
520 int mid = low + ((high - low) / 2); 531 int mid = low + ((high - low) / 2);
@@ -532,7 +543,7 @@ upper_bound(T x, T v[], int n)
532{ 543{
533 int low, high; 544 int low, high;
534 545
535 low = 0; 546 low = 0;
536 high = n; 547 high = n;
537 while ( low < high ) { 548 while ( low < high ) {
538 int mid = low + ((high - low) / 2); 549 int mid = low + ((high - low) / 2);
@@ -542,57 +553,63 @@ upper_bound(T x, T v[], int n)
542 else 553 else
543 high = mid; 554 high = mid;
544 } 555 }
545 return ( low > 0 && x == v[low-1] ) ? low-1 : -1; 556 return (low > 0 && x == v[low - 1]) ? low - 1 : -1;
546} 557}
547 558
548/* TESTTREIBER */ 559/* TESTTREIBER */
549 560
550 561void
551void gen_testset_random(T a[], int n) 562gen_testset_random(T a[], int n)
552{ 563{
553 for ( int i = 0; i < n; ++i ) 564 for ( int i = 0; i < n; ++i )
554 a[i] = bigrand(); 565 a[i] = bigrand();
555} 566}
556 567
557void gen_testset_random2(T a[], int n) 568void
569gen_testset_random2(T a[], int n)
558{ 570{
559 for ( int i = 0; i < n; ++i ) 571 for ( int i = 0; i < n; ++i )
560 a[i] = bigrand() % 100; 572 a[i] = bigrand() % 100;
561} 573}
562 574
563void gen_testset_asc(T a[], int n) 575void
576gen_testset_asc(T a[], int n)
564{ 577{
565 for ( int i = 0; i < n; ++i ) 578 for ( int i = 0; i < n; ++i )
566 a[i] = i; 579 a[i] = i;
567} 580}
568 581
569void gen_testset_desc(T a[], int n) 582void
583gen_testset_desc(T a[], int n)
570{ 584{
571 for ( int i = n; i >= 0; --i ) 585 for ( int i = n; i >= 0; --i )
572 a[i] = i; 586 a[i] = i;
573} 587}
574 588
575void gen_testset_unique(T a[], int n) 589void
590gen_testset_unique(T a[], int n)
576{ 591{
577 for ( int i = 0; i < n; ++i ) 592 for ( int i = 0; i < n; ++i )
578 a[i] = 1; 593 a[i] = 1;
579} 594}
580 595
581void test_sorting(T a[], int n) 596void
597test_sorting(T a[], int n)
582{ 598{
583 for ( int i = 1; i < n; ++i ) 599 for ( int i = 1; i < n; ++i )
584 if ( a[i-1] > a[i] ) { 600 if ( a[i - 1] > a[i] ) {
585 puts("Fehler!"); 601 puts("Fehler!");
586 exit(EXIT_SUCCESS); 602 exit(EXIT_SUCCESS);
587 } 603 }
588} 604}
589 605
590void do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[], int n)) 606void
607do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[], int n))
591{ 608{
592 T *a; 609 T * a;
593 clock_t start, ende; 610 clock_t start, ende;
594 611
595 a = malloc(sizeof(T) * n); 612 a = malloc(sizeof(T) * (size_t) n);
596 613
597 (*gen_testset)(a, n); 614 (*gen_testset)(a, n);
598 615
@@ -608,7 +625,8 @@ void do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[]
608 fflush(stdout); 625 fflush(stdout);
609} 626}
610 627
611void do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n)) 628void
629do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n))
612{ 630{
613 printf("%-15.15s n=%-10d: ", msg, n); 631 printf("%-15.15s n=%-10d: ", msg, n);
614 do_one_test(n, do_sort, gen_testset_random); 632 do_one_test(n, do_sort, gen_testset_random);
@@ -621,7 +639,8 @@ void do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n))
621 639
622/* ENDE TESTTREIBER */ 640/* ENDE TESTTREIBER */
623 641
624int main(void) 642int
643main(void)
625{ 644{
626 const int n = 20000000; 645 const int n = 20000000;
627 646
@@ -663,4 +682,3 @@ int _main(void)
663 return EXIT_SUCCESS; 682 return EXIT_SUCCESS;
664} 683}
665#endif 684#endif
666
diff --git a/rb.c b/rb.c
index 1a9e873..ac21ec8 100644
--- a/rb.c
+++ b/rb.c
@@ -114,6 +114,7 @@ uncle(node n)
114void 114void
115verify_properties(rbtree t) 115verify_properties(rbtree t)
116{ 116{
117 (void) t;
117#ifdef VERIFY_RBTREE 118#ifdef VERIFY_RBTREE
118 verify_property_1(t->root); 119 verify_property_1(t->root);
119 verify_property_2(t->root); 120 verify_property_2(t->root);
diff --git a/ringbuff.c b/ringbuff.c
index a963beb..c800f62 100644
--- a/ringbuff.c
+++ b/ringbuff.c
@@ -5,19 +5,24 @@
5 5
6#include "util.h" 6#include "util.h"
7 7
8/* --8<-- ring_type */
8typedef int T; 9typedef int T;
9 10
10struct ring_buffer { 11struct ring_buffer {
11 size_t head, tail; 12 size_t head, tail;
12 T array[8]; /* fit for your needs... */ 13 T array[8]; /* fit for your needs... */
13}; 14};
15/* -->8-- */
14 16
17/* --8<-- ring_init */
15void 18void
16ring_init(struct ring_buffer *rb) 19ring_init(struct ring_buffer *rb)
17{ 20{
18 rb->head = rb->tail = 0; 21 rb->head = rb->tail = 0;
19} 22}
23/* -->8-- */
20 24
25/* --8<-- ring_push_front */
21bool 26bool
22ring_push_front(struct ring_buffer *rb, T data) 27ring_push_front(struct ring_buffer *rb, T data)
23{ 28{
@@ -31,7 +36,9 @@ ring_push_front(struct ring_buffer *rb, T data)
31 36
32 return true; 37 return true;
33} 38}
39/* -->8-- */
34 40
41/* --8<-- ring_push_back */
35bool 42bool
36ring_push_back(struct ring_buffer *rb, T data) 43ring_push_back(struct ring_buffer *rb, T data)
37{ 44{
@@ -45,7 +52,9 @@ ring_push_back(struct ring_buffer *rb, T data)
45 52
46 return true; 53 return true;
47} 54}
55/* -->8-- */
48 56
57/* --8<-- ring_pop_front */
49bool 58bool
50ring_pop_front(struct ring_buffer *rb, T *data) 59ring_pop_front(struct ring_buffer *rb, T *data)
51{ 60{
@@ -59,7 +68,9 @@ ring_pop_front(struct ring_buffer *rb, T *data)
59 68
60 return true; 69 return true;
61} 70}
71/* -->8-- */
62 72
73/* --8<-- ring_pop_back */
63bool 74bool
64ring_pop_back(struct ring_buffer *rb, T *data) 75ring_pop_back(struct ring_buffer *rb, T *data)
65{ 76{
@@ -73,18 +84,23 @@ ring_pop_back(struct ring_buffer *rb, T *data)
73 84
74 return true; 85 return true;
75} 86}
87/* -->8-- */
76 88
89/* --8<-- ring_put */
77bool 90bool
78ring_put(struct ring_buffer *rb, T data) 91ring_put(struct ring_buffer *rb, T data)
79{ 92{
80 return ring_push_back(rb, data); 93 return ring_push_back(rb, data);
81} 94}
95/* -->8-- */
82 96
97/* --8<-- ring_get */
83bool 98bool
84ring_get(struct ring_buffer *rb, T *data) 99ring_get(struct ring_buffer *rb, T *data)
85{ 100{
86 return ring_pop_front(rb, data); 101 return ring_pop_front(rb, data);
87} 102}
103/* -->8-- */
88 104
89void 105void
90f() 106f()
diff --git a/stack.c b/stack.c
index 775269d..f594775 100644
--- a/stack.c
+++ b/stack.c
@@ -6,6 +6,7 @@
6/* Project */ 6/* Project */
7#include "util.h" 7#include "util.h"
8 8
9/* --8<-- stack_type */
9typedef int T; 10typedef int T;
10 11
11struct stack_item { 12struct stack_item {
@@ -16,13 +17,17 @@ struct stack_item {
16struct stack { 17struct stack {
17 struct stack_item *head; 18 struct stack_item *head;
18}; 19};
20/* -->8-- */
19 21
22/* --8<-- stack_init */
20void 23void
21stack_init(struct stack *stack) 24stack_init(struct stack *stack)
22{ 25{
23 stack->head = NULL; 26 stack->head = NULL;
24} 27}
28/* -->8-- */
25 29
30/* --8<-- stack_push */
26void 31void
27stack_push(struct stack *stack, T data) 32stack_push(struct stack *stack, T data)
28{ 33{
@@ -36,7 +41,9 @@ stack_push(struct stack *stack, T data)
36 else 41 else
37 ERROR("out of memory"); 42 ERROR("out of memory");
38} 43}
44/* -->8-- */
39 45
46/* --8<-- stack_pop */
40bool 47bool
41stack_pop(struct stack *stack, T *data) 48stack_pop(struct stack *stack, T *data)
42{ 49{
@@ -54,13 +61,17 @@ stack_pop(struct stack *stack, T *data)
54 else 61 else
55 return false; 62 return false;
56} 63}
64/* -->8-- */
57 65
66/* --8<-- stack_empty */
58bool 67bool
59stack_empty(struct stack *stack) 68stack_empty(struct stack *stack)
60{ 69{
61 return stack->head == NULL; 70 return stack->head == NULL;
62} 71}
72/* -->8-- */
63 73
74/* --8<-- stack_free */
64void 75void
65stack_free(struct stack *stack) 76stack_free(struct stack *stack)
66{ 77{
@@ -71,6 +82,7 @@ stack_free(struct stack *stack)
71 free(item); 82 free(item);
72 } 83 }
73} 84}
85/* -->8-- */
74 86
75int 87int
76main() 88main()
diff --git a/stack2.c b/stack2.c
index 4c77ac2..b4b8afd 100644
--- a/stack2.c
+++ b/stack2.c
@@ -4,13 +4,16 @@
4 4
5#include "util.h" 5#include "util.h"
6 6
7/* --8<-- stack2_type */
7typedef int T; 8typedef int T;
8 9
9struct stack { 10struct stack {
10 T * array; 11 T * array;
11 size_t sz, p; 12 size_t sz, p;
12}; 13};
14/* -->8-- */
13 15
16/* --8<-- stack2_init */
14void 17void
15stack_init(struct stack *stack) 18stack_init(struct stack *stack)
16{ 19{
@@ -18,7 +21,9 @@ stack_init(struct stack *stack)
18 stack->sz = 0; 21 stack->sz = 0;
19 stack->p = 0; 22 stack->p = 0;
20} 23}
24/* -->8-- */
21 25
26/* --8<-- stack2_push */
22bool 27bool
23stack_push(struct stack *stack, T data) 28stack_push(struct stack *stack, T data)
24{ 29{
@@ -50,7 +55,9 @@ stack_push(struct stack *stack, T data)
50 stack->array[stack->p++] = data; 55 stack->array[stack->p++] = data;
51 return true; 56 return true;
52} 57}
58/* -->8-- */
53 59
60/* --8<-- stack2_pop */
54bool 61bool
55stack_pop(struct stack *stack, T *data) 62stack_pop(struct stack *stack, T *data)
56{ 63{
@@ -65,18 +72,23 @@ stack_pop(struct stack *stack, T *data)
65 else 72 else
66 return false; 73 return false;
67} 74}
75/* -->8-- */
68 76
77/* --8<-- stack2_empty */
69bool 78bool
70stack_empty(struct stack *stack) 79stack_empty(struct stack *stack)
71{ 80{
72 return stack->p == 0; 81 return stack->p == 0;
73} 82}
83/* -->8-- */
74 84
85/* --8<-- stack2_free */
75void 86void
76stack_free(struct stack *stack) 87stack_free(struct stack *stack)
77{ 88{
78 free(stack->array); 89 free(stack->array);
79} 90}
91/* -->8-- */
80 92
81int 93int
82main() 94main()
diff --git a/tree.c b/tree.c
index cc2ae53..f6ccc5a 100644
--- a/tree.c
+++ b/tree.c
@@ -7,6 +7,7 @@
7 7
8#include "util.h" 8#include "util.h"
9 9
10/* --8<-- tree_type */
10typedef int T; 11typedef int T;
11 12
12struct tree_node { 13struct tree_node {
@@ -15,7 +16,9 @@ struct tree_node {
15 int count; /* collision counter */ 16 int count; /* collision counter */
16 /* ggf. weitere Felder... */ 17 /* ggf. weitere Felder... */
17}; 18};
19/* -->8-- */
18 20
21/* --8<-- tree_isBst */
19static bool 22static bool
20tree_isBstUntil(struct tree_node *tree, T min, T max) 23tree_isBstUntil(struct tree_node *tree, T min, T max)
21{ 24{
@@ -34,7 +37,9 @@ tree_isBst(struct tree_node *tree)
34{ 37{
35 return tree_isBstUntil(tree, INT_MIN, INT_MAX); 38 return tree_isBstUntil(tree, INT_MIN, INT_MAX);
36} 39}
40/* -->8-- */
37 41
42/* --8<-- tree_insert */
38struct tree_node * 43struct tree_node *
39tree_insert(struct tree_node *tree, T key) 44tree_insert(struct tree_node *tree, T key)
40{ 45{
@@ -58,7 +63,9 @@ tree_insert(struct tree_node *tree, T key)
58 63
59 return tree; 64 return tree;
60} 65}
66/* -->8-- */
61 67
68/* --8<-- tree_insert_it */
62struct tree_node * 69struct tree_node *
63tree_insert_it(struct tree_node *tree, T key) 70tree_insert_it(struct tree_node *tree, T key)
64{ 71{
@@ -104,7 +111,9 @@ tree_insert_it(struct tree_node *tree, T key)
104 111
105 return tree; 112 return tree;
106} 113}
114/* -->8-- */
107 115
116/* --8<-- tree_detach_min */
108static struct tree_node * 117static struct tree_node *
109tree_detach_min(struct tree_node **ptree) 118tree_detach_min(struct tree_node **ptree)
110{ 119{
@@ -119,7 +128,9 @@ tree_detach_min(struct tree_node **ptree)
119 return tree; 128 return tree;
120 } 129 }
121} 130}
131/* -->8-- */
122 132
133/* --8<-- tree_remove */
123struct tree_node * 134struct tree_node *
124tree_remove(struct tree_node *tree, T key) 135tree_remove(struct tree_node *tree, T key)
125{ 136{
@@ -154,7 +165,9 @@ tree_remove(struct tree_node *tree, T key)
154 } 165 }
155 return tree; 166 return tree;
156} 167}
168/* -->8-- */
157 169
170/* --8<-- tree_clear */
158void 171void
159tree_clear(struct tree_node *tree) 172tree_clear(struct tree_node *tree)
160{ 173{
@@ -164,7 +177,9 @@ tree_clear(struct tree_node *tree)
164 free(tree); 177 free(tree);
165 } 178 }
166} 179}
180/* -->8-- */
167 181
182/* --8<-- tree_lookup */
168struct tree_node * 183struct tree_node *
169tree_lookup(struct tree_node *tree, T key) 184tree_lookup(struct tree_node *tree, T key)
170{ 185{
@@ -178,7 +193,9 @@ tree_lookup(struct tree_node *tree, T key)
178 193
179 return tree; 194 return tree;
180} 195}
196/* -->8-- */
181 197
198/* --8<-- tree_minimum */
182struct tree_node * 199struct tree_node *
183tree_minimum(struct tree_node *tree) 200tree_minimum(struct tree_node *tree)
184{ 201{
@@ -188,7 +205,9 @@ tree_minimum(struct tree_node *tree)
188 205
189 return tree; 206 return tree;
190} 207}
208/* -->8-- */
191 209
210/* --8<-- tree_maximum */
192struct tree_node * 211struct tree_node *
193tree_maximum(struct tree_node *tree) 212tree_maximum(struct tree_node *tree)
194{ 213{
@@ -198,7 +217,9 @@ tree_maximum(struct tree_node *tree)
198 217
199 return tree; 218 return tree;
200} 219}
220/* -->8-- */
201 221
222/* --8<-- tree_height */
202size_t 223size_t
203tree_height(struct tree_node *tree) 224tree_height(struct tree_node *tree)
204{ 225{
@@ -211,7 +232,9 @@ tree_height(struct tree_node *tree)
211 232
212 return 0; 233 return 0;
213} 234}
235/* -->8-- */
214 236
237/* --8<-- tree_count */
215size_t 238size_t
216tree_count(struct tree_node *tree) 239tree_count(struct tree_node *tree)
217{ 240{
@@ -220,13 +243,17 @@ tree_count(struct tree_node *tree)
220 243
221 return 0; 244 return 0;
222} 245}
246/* -->8-- */
223 247
248/* --8<-- tree_isleaf */
224bool 249bool
225tree_isleaf(struct tree_node *tree) 250tree_isleaf(struct tree_node *tree)
226{ 251{
227 return tree->left == NULL && tree->right == NULL; 252 return tree->left == NULL && tree->right == NULL;
228} 253}
254/* -->8-- */
229 255
256/* --8<-- tree_apply_preorder */
230void 257void
231tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 258tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
232{ 259{
@@ -236,7 +263,9 @@ tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void
236 tree_apply_preorder(tree->right, visit, cl); 263 tree_apply_preorder(tree->right, visit, cl);
237 } 264 }
238} 265}
266/* -->8-- */
239 267
268/* --8<-- tree_apply_inorder */
240void 269void
241tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 270tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
242{ 271{
@@ -246,7 +275,9 @@ tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void
246 tree_apply_inorder(tree->right, visit, cl); 275 tree_apply_inorder(tree->right, visit, cl);
247 } 276 }
248} 277}
278/* -->8-- */
249 279
280/* --8<-- tree_apply_postorder */
250void 281void
251tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 282tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
252{ 283{
@@ -256,9 +287,11 @@ tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), voi
256 visit(tree->key, cl); 287 visit(tree->key, cl);
257 } 288 }
258} 289}
290/* -->8-- */
259 291
260/* ===== */ 292/* ===== */
261 293
294/* --8<-- tree_stack_type */
262struct stack_item { 295struct stack_item {
263 struct stack_item *next; 296 struct stack_item *next;
264 struct tree_node * data; 297 struct tree_node * data;
@@ -267,13 +300,17 @@ struct stack_item {
267struct stack { 300struct stack {
268 struct stack_item *head; 301 struct stack_item *head;
269}; 302};
303/* -->8-- */
270 304
305/* --8<-- tree_stack_init */
271static void 306static void
272stack_init(struct stack *stack) 307stack_init(struct stack *stack)
273{ 308{
274 stack->head = NULL; 309 stack->head = NULL;
275} 310}
311/* -->8-- */
276 312
313/* --8<-- tree_stack_push */
277static void 314static void
278stack_push(struct stack *stack, struct tree_node *data) 315stack_push(struct stack *stack, struct tree_node *data)
279{ 316{
@@ -287,7 +324,9 @@ stack_push(struct stack *stack, struct tree_node *data)
287 else 324 else
288 ERROR("out of memory"); 325 ERROR("out of memory");
289} 326}
327/* -->8-- */
290 328
329/* --8<-- tree_stack_pop */
291static bool 330static bool
292stack_pop(struct stack *stack, struct tree_node **data) 331stack_pop(struct stack *stack, struct tree_node **data)
293{ 332{
@@ -305,19 +344,25 @@ stack_pop(struct stack *stack, struct tree_node **data)
305 else 344 else
306 return false; 345 return false;
307} 346}
347/* -->8-- */
308 348
349/* --8<-- tree_stack_peek */
309static struct tree_node * 350static struct tree_node *
310stack_peek(struct stack *stack) 351stack_peek(struct stack *stack)
311{ 352{
312 return (stack->head != NULL) ? stack->head->data : NULL; 353 return (stack->head != NULL) ? stack->head->data : NULL;
313} 354}
355/* -->8-- */
314 356
357/* --8<-- tree_stack_empty */
315static bool 358static bool
316stack_empty(struct stack *stack) 359stack_empty(struct stack *stack)
317{ 360{
318 return stack->head == NULL; 361 return stack->head == NULL;
319} 362}
363/* -->8-- */
320 364
365/* --8<-- tree_stack_free */
321void 366void
322stack_free(struct stack *stack) 367stack_free(struct stack *stack)
323{ 368{
@@ -328,9 +373,11 @@ stack_free(struct stack *stack)
328 free(item); 373 free(item);
329 } 374 }
330} 375}
376/* -->8-- */
331 377
332/* ===== */ 378/* ===== */
333 379
380/* --8<-- tree_queue_type */
334struct queue_item { 381struct queue_item {
335 struct queue_item *next; 382 struct queue_item *next;
336 struct tree_node * data; 383 struct tree_node * data;
@@ -339,13 +386,17 @@ struct queue_item {
339struct queue { 386struct queue {
340 struct queue_item *head, *tail; 387 struct queue_item *head, *tail;
341}; 388};
389/* -->8-- */
342 390
391/* --8<-- tree_queue_init */
343void 392void
344queue_init(struct queue *queue) 393queue_init(struct queue *queue)
345{ 394{
346 queue->head = NULL; 395 queue->head = NULL;
347} 396}
397/* -->8-- */
348 398
399/* --8<-- tree_queue_put */
349void 400void
350queue_put(struct queue *queue, struct tree_node *data) 401queue_put(struct queue *queue, struct tree_node *data)
351{ 402{
@@ -367,7 +418,9 @@ queue_put(struct queue *queue, struct tree_node *data)
367 else 418 else
368 ERROR("out of memory"); 419 ERROR("out of memory");
369} 420}
421/* -->8-- */
370 422
423/* --8<-- tree_queue_get */
371bool 424bool
372queue_get(struct queue *queue, struct tree_node **data) 425queue_get(struct queue *queue, struct tree_node **data)
373{ 426{
@@ -385,13 +438,17 @@ queue_get(struct queue *queue, struct tree_node **data)
385 else 438 else
386 return false; 439 return false;
387} 440}
441/* -->8-- */
388 442
443/* --8<-- tree_queue_empty */
389bool 444bool
390queue_empty(struct queue *queue) 445queue_empty(struct queue *queue)
391{ 446{
392 return queue->head == NULL; 447 return queue->head == NULL;
393} 448}
449/* -->8-- */
394 450
451/* --8<-- tree_queue_free */
395void 452void
396queue_free(struct queue *queue) 453queue_free(struct queue *queue)
397{ 454{
@@ -402,9 +459,11 @@ queue_free(struct queue *queue)
402 free(item); 459 free(item);
403 } 460 }
404} 461}
462/* -->8-- */
405 463
406/* ===== */ 464/* ===== */
407 465
466/* --8<-- tree_apply_preorder_it */
408void 467void
409tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 468tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
410{ 469{
@@ -427,7 +486,9 @@ tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), v
427 stack_free(&stack); 486 stack_free(&stack);
428 } 487 }
429} 488}
489/* -->8-- */
430 490
491/* --8<-- tree_apply_inorder_it */
431void 492void
432tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 493tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
433{ 494{
@@ -451,10 +512,12 @@ tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), vo
451 stack_free(&stack); 512 stack_free(&stack);
452 } 513 }
453} 514}
515/* -->8-- */
454 516
455// Hier eine Version für PostOrder-Iterativ: 517// Hier eine Version für PostOrder-Iterativ:
456// Quelle: https://stackoverflow.com/a/16092333 518// Quelle: https://stackoverflow.com/a/16092333
457 519
520/* --8<-- tree_apply_postorder_it */
458void 521void
459tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 522tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
460{ 523{
@@ -488,7 +551,9 @@ tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl),
488 stack_free(&stack); 551 stack_free(&stack);
489 } 552 }
490} 553}
554/* -->8-- */
491 555
556/* --8<-- tree_apply_levelorder_it */
492void 557void
493tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 558tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
494{ 559{
@@ -511,13 +576,17 @@ tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl),
511 queue_free(&queue); 576 queue_free(&queue);
512 } 577 }
513} 578}
579/* -->8-- */
514 580
515/* ======================== */ 581/* ======================== */
516 582
583/* --8<-- tree_iterator_type */
517struct tree_iterator { 584struct tree_iterator {
518 struct stack stack; 585 struct stack stack;
519}; 586};
587/* -->8-- */
520 588
589/* --8<-- tree_iterator_push_leftmost */
521static void 590static void
522tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node) 591tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node)
523{ 592{
@@ -525,7 +594,9 @@ tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node)
525 stack_push(stack, node); 594 stack_push(stack, node);
526 } 595 }
527} 596}
597/* -->8-- */
528 598
599/* --8<-- tree_iterator_next */
529struct tree_node * 600struct tree_node *
530tree_iterator_next(struct tree_iterator *it) 601tree_iterator_next(struct tree_iterator *it)
531{ 602{
@@ -537,7 +608,9 @@ tree_iterator_next(struct tree_iterator *it)
537 608
538 return node; 609 return node;
539} 610}
611/* -->8-- */
540 612
613/* --8<-- tree_iterator_first */
541struct tree_node * 614struct tree_node *
542tree_iterator_first(struct tree_iterator *it, struct tree_node *tree) 615tree_iterator_first(struct tree_iterator *it, struct tree_node *tree)
543{ 616{
@@ -547,13 +620,17 @@ tree_iterator_first(struct tree_iterator *it, struct tree_node *tree)
547 620
548 return tree_iterator_next(it); 621 return tree_iterator_next(it);
549} 622}
623/* -->8-- */
550 624
625/* --8<-- tree_iterator_free */
551void 626void
552tree_iterator_free(struct tree_iterator *it) 627tree_iterator_free(struct tree_iterator *it)
553{ 628{
554 stack_free(&it->stack); 629 stack_free(&it->stack);
555} 630}
631/* -->8-- */
556 632
633/* --8<-- tree_preorder_iterator_next */
557struct tree_node * 634struct tree_node *
558tree_preorder_iterator_next(struct tree_iterator *it) 635tree_preorder_iterator_next(struct tree_iterator *it)
559{ 636{
@@ -570,7 +647,9 @@ tree_preorder_iterator_next(struct tree_iterator *it)
570 647
571 return node; 648 return node;
572} 649}
650/* -->8-- */
573 651
652/* --8<-- tree_preorder_iterator_first */
574struct tree_node * 653struct tree_node *
575tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree) 654tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree)
576{ 655{
@@ -585,6 +664,7 @@ tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree)
585 return NULL; 664 return NULL;
586 } 665 }
587} 666}
667/* -->8-- */
588 668
589/* ===== */ 669/* ===== */
590 670