From 6fb072f62c2f50118dd5cb377d10c76ece51e5fb Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sun, 4 Oct 2020 14:36:07 +0200 Subject: Setze srcut-Marker... --- avl.c | 25 +++- deque.c | 38 +++++- dlist.c | 28 ++++ hashtab.c | 16 +++ list-tail-node.c | 20 +++ list.c | 30 ++++- queue.c | 12 ++ quicksort.c | 380 +++++++++++++++++++++++++++++-------------------------- rb.c | 1 + ringbuff.c | 16 +++ stack.c | 12 ++ stack2.c | 12 ++ tree.c | 80 ++++++++++++ 13 files changed, 482 insertions(+), 188 deletions(-) diff --git a/avl.c b/avl.c index 201dc5b..13a3d5f 100644 --- a/avl.c +++ b/avl.c @@ -1,15 +1,18 @@ // AVL Tree +#include #include #include -#include #include /* utils */ #include "util.h" -// TODO: [x] Review: http://www.inr.ac.ru/~info21/ADen/ -// [x] Tests: https://stackoverflow.com/q/3955680 +// clang-format off +// Review: http://www.inr.ac.ru/~info21/ADen/ +// Tests: https://stackoverflow.com/q/3955680 + +/* --8<-- avl_type */ typedef int T; struct tree_node { @@ -19,7 +22,9 @@ struct tree_node { int count; /* collision counter */ /* ggf. weitere Felder... */ }; +/* -->8-- */ +/* --8<-- avl_insert_r */ static struct tree_node * insert_r(T x, struct tree_node *p, bool *h) { @@ -109,14 +114,18 @@ insert_r(T x, struct tree_node *p, bool *h) ERROR("das hier sollte niemals passieren"); return p; } +/* -->8-- */ +/* --8<-- avl_insert */ struct tree_node * insert(struct tree_node *tree, T data) { bool h = false; return insert_r(data, tree, &h); } +/* -->8-- */ +/* --8<-- avl_balanceL */ static struct tree_node * balanceL(struct tree_node *p, bool *h) { @@ -157,7 +166,9 @@ balanceL(struct tree_node *p, bool *h) } return p; } +/* -->8-- */ +/* --8<-- avl_balanceR */ static struct tree_node * balanceR(struct tree_node *p, bool *h) { @@ -198,7 +209,9 @@ balanceR(struct tree_node *p, bool *h) } return p; } +/* -->8-- */ +/* --8<-- avl_del */ static void del(struct tree_node **q, struct tree_node **r, bool *h) { @@ -217,7 +230,9 @@ del(struct tree_node **q, struct tree_node **r, bool *h) *h = true; } } +/* -->8-- */ +/* --8<-- avl_delete_r */ static struct tree_node * delete_r(T x, struct tree_node *p, bool *h) { @@ -253,14 +268,16 @@ delete_r(T x, struct tree_node *p, bool *h) } return p; } +/* -->8-- */ +/* --8<-- avl_delete */ struct tree_node * delete(struct tree_node *tree, T data) { bool h = false; return delete_r(data, tree, &h); } - +/* -->8-- */ // aux display and verification routines, helpful but not essential struct trunk { diff --git a/deque.c b/deque.c index 93cbe92..eec6f42 100644 --- a/deque.c +++ b/deque.c @@ -5,11 +5,12 @@ #include "util.h" -typedef int T; - #define START_MAP_CAPACITY 4 #define CHUNK_CAPACITY 17 +/* --8<-- deque_type */ +typedef int T; + struct deque { T **map; @@ -20,7 +21,9 @@ struct deque { size_t offset; size_t size; }; +/* -->8-- */ +/* --8<-- deque_allocate */ static void * allocate(size_t n, size_t sz) { @@ -30,7 +33,9 @@ allocate(size_t n, size_t sz) } return ptr; } +/* -->8-- */ +/* --8<-- deque_init */ void deque_init(struct deque *d) { @@ -51,7 +56,9 @@ deque_init(struct deque *d) } } } +/* -->8-- */ +/* --8<-- deque_free */ void deque_free(struct deque *d) { @@ -66,7 +73,9 @@ deque_free(struct deque *d) free(d->map); d->map = NULL; } +/* -->8-- */ +/* --8<-- deque_size */ size_t deque_size(struct deque *d) { @@ -74,7 +83,9 @@ deque_size(struct deque *d) return d->size; } +/* -->8-- */ +/* --8<-- deque_is_empty */ bool deque_is_empty(struct deque *d) { @@ -82,7 +93,9 @@ deque_is_empty(struct deque *d) return d->map_begin == d->map_end; } +/* -->8-- */ +/* --8<-- deque_grow_map */ static void grow_map(struct deque *d) { @@ -116,7 +129,9 @@ grow_map(struct deque *d) // set new map_capacity d->map_capacity = capacity; } +/* -->8-- */ +/* --8<-- deque_map_append_chunk */ static void map_append_chunk(struct deque *d) { @@ -133,7 +148,9 @@ map_append_chunk(struct deque *d) d->map[d->map_end] = allocate(CHUNK_CAPACITY, sizeof **d->map); d->map_end = next; } +/* -->8-- */ +/* --8<-- deque_map_prepend_chunk */ static void map_prepend_chunk(struct deque *d) { @@ -150,7 +167,9 @@ map_prepend_chunk(struct deque *d) d->map[prev] = allocate(CHUNK_CAPACITY, sizeof **d->map); d->map_begin = prev; } +/* -->8-- */ +/* --8<-- deque_map_remove_front_chunk */ static void map_remove_front_chunk(struct deque *d) { @@ -167,7 +186,9 @@ map_remove_front_chunk(struct deque *d) d->map_begin = next; } +/* -->8-- */ +/* --8<-- deque_remove_tail_chunk */ static void map_remove_tail_chunk(struct deque *d) { @@ -184,7 +205,9 @@ map_remove_tail_chunk(struct deque *d) d->map_end = prev; } +/* -->8-- */ +/* --8<-- deque_get_at */ bool deque_get_at(struct deque *d, size_t idx, T *data) { @@ -204,7 +227,9 @@ deque_get_at(struct deque *d, size_t idx, T *data) return true; } +/* -->8-- */ +/* --8<-- deque_set_at */ bool deque_set_at(struct deque *d, size_t idx, T data) { @@ -223,7 +248,9 @@ deque_set_at(struct deque *d, size_t idx, T data) return true; } +/* -->8-- */ +/* --8<-- deque_push_back */ void deque_push_back(struct deque *d, T data) { @@ -241,7 +268,9 @@ deque_push_back(struct deque *d, T data) d->map[chunk_num][chunk_off] = data; ++d->size; } +/* -->8-- */ +/* --8<-- deque_push_front */ void deque_push_front(struct deque *d, T data) { @@ -259,7 +288,9 @@ deque_push_front(struct deque *d, T data) d->map[chunk_num][d->offset] = data; ++d->size; } +/* -->8-- */ +/* --8<-- deque_pop_back */ bool deque_pop_back(struct deque *d, T *data) { @@ -284,7 +315,9 @@ deque_pop_back(struct deque *d, T *data) return true; } +/* -->8-- */ +/* --8<-- deque_pop_front */ bool deque_pop_front(struct deque *d, T *data) { @@ -310,6 +343,7 @@ deque_pop_front(struct deque *d, T *data) return true; } +/* -->8-- */ static void deque_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 @@ /* Project */ #include "util.h" +/* --8<-- dlist_type */ typedef int T; struct dlist { @@ -20,20 +21,26 @@ struct dlist_element { struct dlist_element *prev, *next; T data; }; +/* -->8-- */ +/* --8<-- dlist_init */ void dlist_init(struct dlist *dlist) { dlist->head = NULL; dlist->tail = NULL; } +/* -->8-- */ +/* --8<-- dlist_empty */ bool dlist_empty(struct dlist *dlist) { return dlist->head == NULL; } +/* -->8-- */ +/* --8<-- dlist_create_element */ static struct dlist_element * create_element(T data) { @@ -46,7 +53,9 @@ create_element(T data) return element; } +/* -->8-- */ +/* --8<-- dlist_push_front */ struct dlist_element * dlist_push_front(struct dlist *dlist, T data) { @@ -72,7 +81,9 @@ dlist_push_front(struct dlist *dlist, T data) return element; } +/* -->8-- */ +/* --8<-- dlist_push_back */ struct dlist_element * dlist_push_back(struct dlist *dlist, T data) { @@ -98,7 +109,9 @@ dlist_push_back(struct dlist *dlist, T data) return element; } +/* -->8-- */ +/* --8<-- dlist_pop_front */ bool dlist_pop_front(struct dlist *dlist, T *data) { @@ -122,7 +135,9 @@ dlist_pop_front(struct dlist *dlist, T *data) else return false; } +/* -->8-- */ +/* --8<-- dlist_pop_back */ bool dlist_pop_back(struct dlist *dlist, T *data) { @@ -146,7 +161,9 @@ dlist_pop_back(struct dlist *dlist, T *data) else return false; } +/* -->8-- */ +/* --8<-- dlist_insert_next */ struct dlist_element * dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data) { @@ -177,7 +194,9 @@ dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data) return new_element; } +/* -->8-- */ +/* --8<-- dlist_insert_prev */ struct dlist_element * dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data) { @@ -208,7 +227,9 @@ dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data) return new_element; } +/* -->8-- */ +/* --8<-- dlist_remove */ void dlist_remove(struct dlist *dlist, struct dlist_element *element) { @@ -231,7 +252,9 @@ dlist_remove(struct dlist *dlist, struct dlist_element *element) free(element); } +/* -->8-- */ +/* --8<-- dlist_free */ void dlist_free(struct dlist *dlist) { @@ -244,6 +267,7 @@ dlist_free(struct dlist *dlist) dlist_init(dlist); } +/* -->8-- */ void dlist_apply_rev(struct dlist *dlist, void (*visit)(T data, void *cl), void *cl) @@ -289,6 +313,7 @@ remove_if(struct dlist *list) } } +/* --8<-- dlist_merge */ struct dlist * dlist_merge(struct dlist *list1, struct dlist *list2) { @@ -355,7 +380,9 @@ dlist_merge(struct dlist *list1, struct dlist *list2) // Zeiger auf Liste1 zurückliefern return list1; } +/* -->8-- */ +/* --8<-- dlist_sort */ struct dlist * dlist_sort(struct dlist *list) { @@ -380,6 +407,7 @@ dlist_sort(struct dlist *list) return list; } +/* -->8-- */ void merge_test(void) diff --git a/hashtab.c b/hashtab.c index 8a49baf..9f4e4a8 100644 --- a/hashtab.c +++ b/hashtab.c @@ -6,6 +6,7 @@ #include "util.h" +/* --8<-- hash_type */ typedef int T; struct hash_item { @@ -17,7 +18,9 @@ struct hash_item { struct hash_tab { struct hash_item *table[251]; // fit for your needs... }; +/* -->8-- */ +/* --8<-- hash_key */ static unsigned long hash_key(const unsigned char *str) { @@ -29,14 +32,18 @@ hash_key(const unsigned char *str) return hash; } +/* -->8-- */ +/* --8<-- hash_init */ void hash_init(struct hash_tab *ht) { for ( size_t i = 0; i != NELEM(ht->table); ++i ) ht->table[i] = NULL; } +/* -->8-- */ +/* --8<-- hash_add */ static struct hash_item * hash_add(struct hash_item *next, const char *key, T data) { @@ -59,7 +66,9 @@ hash_add(struct hash_item *next, const char *key, T data) return new_item; } +/* -->8-- */ +/* --8<-- hash_lookup */ T * hash_lookup(struct hash_tab *ht, const char *key, T data, int create) { @@ -82,7 +91,9 @@ hash_lookup(struct hash_tab *ht, const char *key, T data, int create) return item ? &item->data : NULL; } +/* -->8-- */ +/* --8<-- hash_delete */ bool hash_delete(struct hash_tab *ht, const char *key) { @@ -108,7 +119,9 @@ hash_delete(struct hash_tab *ht, const char *key) return false; } +/* -->8-- */ +/* --8<-- hash_apply */ void hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl) { @@ -118,7 +131,9 @@ hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl) for ( item = ht->table[i]; item; item = item->next ) visit(item->key, item->data, cl); } +/* -->8-- */ +/* --8<-- hash_free */ void hash_free(struct hash_tab *ht) { @@ -133,6 +148,7 @@ hash_free(struct hash_tab *ht) ht->table[i] = NULL; } } +/* -->8-- */ static int getword(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 @@ /* Project */ #include "util.h" +/* --8<-- list_tail_type */ typedef int T; struct list_node { @@ -16,13 +17,17 @@ struct list_node { struct list { struct list_node *head, *tail; }; +/* -->8-- */ +/* --8<-- list_tail_init */ void list_init(struct list *list) { list->head = NULL; } +/* -->8-- */ +/* --8<-- list_tail_create_node */ static struct list_node * create_node(struct list_node *next, T data) { @@ -34,7 +39,9 @@ create_node(struct list_node *next, T data) } return node; } +/* -->8-- */ +/* --8<-- list_tail_push_back */ void list_push_back(struct list *list, T data) { @@ -53,7 +60,9 @@ list_push_back(struct list *list, T data) ERROR("out of memory"); } } +/* -->8-- */ +/* --8<-- list_tail_front */ void list_push_front(struct list *list, T data) { @@ -69,7 +78,9 @@ list_push_front(struct list *list, T data) ERROR("out of memory"); } } +/* -->8-- */ +/* --8<-- list_tail_pop_front */ bool list_pop_front(struct list *list, T *data) { @@ -88,7 +99,9 @@ list_pop_front(struct list *list, T *data) return false; } } +/* -->8-- */ +/* --8<-- list_tail_insert_next */ void list_insert_next(struct list *list, struct list_node *node, T data) { @@ -109,7 +122,9 @@ list_insert_next(struct list *list, struct list_node *node, T data) } } } +/* -->8-- */ +/* --8<-- list_tail_delete_next */ void list_delete_next(struct list *list, struct list_node *node, T *data) { @@ -132,13 +147,17 @@ list_delete_next(struct list *list, struct list_node *node, T *data) } } } +/* -->8-- */ +/* --8<-- list_tail_empty */ bool list_empty(struct list *list) { return list->head == NULL; } +/* -->8-- */ +/* --8<-- list_tail_free */ void list_free(struct list *list) { @@ -149,6 +168,7 @@ list_free(struct list *list) free(item); } } +/* -->8-- */ int main() diff --git a/list.c b/list.c index da0c702..24024da 100644 --- a/list.c +++ b/list.c @@ -9,13 +9,16 @@ /* Project */ #include "util.h" +/* --8<-- list_type */ typedef int T; struct list_item { struct list_item *next; T data; }; +/* -->8-- */ +/* --8<-- list_add */ struct list_item * list_add(struct list_item *next, T data) { @@ -31,7 +34,9 @@ list_add(struct list_item *next, T data) return new_item; } +/* -->8-- */ +/* --8<-- list_insert_next */ void list_insert_next(struct list_item *list, T data) { @@ -47,7 +52,9 @@ list_insert_next(struct list_item *list, T data) else ERROR("out of memory"); } +/* -->8-- */ +/* --8<-- list_delete */ struct list_item * list_delete(struct list_item *list, T data) { @@ -68,10 +75,14 @@ list_delete(struct list_item *list, T data) } prev = p; } - //ERROR("data not found"); /* uncomment, if this case should be reported as an error */ +#if LIST_REPORT_ERROR + ERROR("data not found"); +#endif return list; } +/* -->8-- */ +/* --8<-- list_delete_next */ void list_delete_next(struct list_item *list) { @@ -83,7 +94,9 @@ list_delete_next(struct list_item *list) free(temp); } } +/* -->8-- */ +/* --8<-- list_length */ size_t list_length(struct list_item *list) { @@ -94,7 +107,9 @@ list_length(struct list_item *list) return len; } +/* -->8-- */ +/* --8<-- list_copy */ struct list_item * list_copy(struct list_item *list) { @@ -112,7 +127,9 @@ list_copy(struct list_item *list) *p = NULL; return head; } +/* -->8-- */ +/* --8<-- list_reverse */ struct list_item * list_reverse(struct list_item *list) { @@ -125,7 +142,9 @@ list_reverse(struct list_item *list) } return head; } +/* -->8-- */ +/* --8<-- list_apply */ void list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl) { @@ -133,7 +152,9 @@ list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl) visit(list->data, cl); } } +/* -->8-- */ +/* --8<-- list_merge */ struct list_item * list_merge(struct list_item *a, struct list_item *b) { @@ -150,7 +171,9 @@ list_merge(struct list_item *a, struct list_item *b) return head->next; } +/* -->8-- */ +/* --8<-- list_sort */ struct list_item * list_sort(struct list_item *c) { @@ -167,7 +190,9 @@ list_sort(struct list_item *c) return list_merge(list_sort(a), list_sort(b)); } +/* -->8-- */ +/* --8<-- list_free */ void list_free(struct list_item *list) { @@ -178,12 +203,15 @@ list_free(struct list_item *list) free(list); } } +/* -->8-- */ +/* --8<-- list_apply_sample */ static void print_data(T data, void *cl) { fprintf(cl, "%d\n", data); } +/* -->8-- */ int main() diff --git a/queue.c b/queue.c index 2fb9c72..dab5bfb 100644 --- a/queue.c +++ b/queue.c @@ -6,6 +6,7 @@ /* Project */ #include "util.h" +/* --8<-- queue_type */ typedef int T; struct queue_item { @@ -16,13 +17,17 @@ struct queue_item { struct queue { struct queue_item *head, *tail; }; +/* -->8-- */ +/* --8<-- queue_init */ void queue_init(struct queue *queue) { queue->head = NULL; } +/* -->8-- */ +/* --8<-- queue_put */ void queue_put(struct queue *queue, T data) { @@ -41,7 +46,9 @@ queue_put(struct queue *queue, T data) else ERROR("out of memory"); } +/* -->8-- */ +/* --8<-- queue_get */ bool queue_get(struct queue *queue, T *data) { @@ -59,13 +66,17 @@ queue_get(struct queue *queue, T *data) else return false; } +/* -->8-- */ +/* --8<-- queue_empty */ bool queue_empty(struct queue *queue) { return queue->head == NULL; } +/* -->8-- */ +/* --8<-- queue_free */ void queue_free(struct queue *queue) { @@ -76,6 +87,7 @@ queue_free(struct queue *queue) free(item); } } +/* -->8-- */ int main() diff --git a/quicksort.c b/quicksort.c index fa219e9..4657dcd 100644 --- a/quicksort.c +++ b/quicksort.c @@ -1,10 +1,12 @@ +#include #include #include -#include #include + #include "util.h" -static int bigrand(void) +static int +bigrand(void) { int x = (rand() << 24) | (rand() << 16) | (rand() << 8) | rand(); if ( x < 0 ) @@ -12,9 +14,10 @@ static int bigrand(void) return x; } -static int randint(int l, int u) +static int +randint(int l, int u) { - return l + bigrand() % (u-l+1); + return l + bigrand() % (u - l + 1); } typedef int T; @@ -24,7 +27,7 @@ static const int CUTOFF = 128; static inline void swap(T a[], int i, int j) { - T t = a[i]; + T t = a[i]; a[i] = a[j]; a[j] = t; } @@ -33,11 +36,10 @@ static void insertsort(T a[], int n) { int i, j; - for ( i = 1; i < n; ++i ) - { + for ( i = 1; i < n; ++i ) { T t = a[i]; - for ( j = i; j > 0 && a[j-1] > t; --j ) - a[j] = a[j-1]; + for ( j = i; j > 0 && a[j - 1] > t; --j ) + a[j] = a[j - 1]; a[j] = t; } } @@ -60,7 +62,7 @@ quicksort(T a[], int n) swap(a, 0, last); quicksort(a, last); - quicksort(a+last+1, n-last-1); + quicksort(a + last + 1, n - last - 1); } void @@ -70,22 +72,24 @@ my_quicksort(T a[], int n) insertsort(a, n); } - static int cmp(const void *a, const void *b) { const int *pa = (const T *) a; const int *pb = (const T *) b; - if ( *pa < *pb ) return -1; - if ( *pa > *pb ) return 1; + if ( *pa < *pb ) + return -1; + if ( *pa > *pb ) + return 1; return 0; } void c_quicksort(T a[], int n) { - qsort(a, n, sizeof(T), cmp); + assert(n >= 0); + qsort(a, (size_t) n, sizeof(T), cmp); } /* This function takes last element as pivot, places @@ -93,65 +97,63 @@ c_quicksort(T a[], int n) array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ -int partition (int arr[], int low, int high) +int +partition(int arr[], int low, int high) { - int pivot = arr[high]; // pivot - int i = (low - 1); // Index of smaller element + int pivot = arr[high]; // pivot + int i = (low - 1); // Index of smaller element - for (int j = low; j <= high- 1; j++) - { - // If current element is smaller than or - // equal to pivot - if (arr[j] <= pivot) - { - i++; // increment index of smaller element - swap(arr, i, j); - } - } - swap(arr, i + 1, high); - return (i + 1); + for ( int j = low; j <= high - 1; j++ ) { + // If current element is smaller than or + // equal to pivot + if ( arr[j] <= pivot ) { + i++; // increment index of smaller element + swap(arr, i, j); + } + } + swap(arr, i + 1, high); + return (i + 1); } /* The main function that implements QuickSort arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */ -void quickSort(int arr[], int low, int high) +void +quickSort(int arr[], int low, int high) { - while (low < high) - { - /* pi is partitioning index, arr[p] is now + while ( low < high ) { + /* pi is partitioning index, arr[p] is now at right place */ - int pi = partition(arr, low, high); + int pi = partition(arr, low, high); - if (pi - low < high - pi) - { + if ( pi - low < high - pi ) { quickSort(arr, low, pi - 1); low = pi + 1; } - else - { + else { quickSort(arr, pi + 1, high); high = pi - 1; } - } + } } -void g4g_quicksort(T a[], int n) +void +g4g_quicksort(T a[], int n) { - quickSort(a, 0, n-1); + quickSort(a, 0, n - 1); } - -static void three_way_quicksort(int a[], int l, int r) +static void +three_way_quicksort(int a[], int l, int r) { int k; - T v = a[r]; + T v = a[r]; if ( r <= l ) return; - int i = l-1, j = r, p = l-1, q = r; + int i = l - 1, j = r, p = l - 1, q = r; for ( ;; ) { while ( a[++i] < v ) @@ -169,27 +171,30 @@ static void three_way_quicksort(int a[], int l, int r) if ( v == a[j] ) swap(a, --q, j); } - swap(a, i, r); j = i-1; i = i+1; + swap(a, i, r); + j = i - 1; + i = i + 1; - for ( k = l ; k <= p; ++k, --j ) + for ( k = l; k <= p; ++k, --j ) swap(a, k, j); - for ( k = r-1; k >= q; --k, ++i ) + for ( k = r - 1; k >= q; --k, ++i ) swap(a, k, i); three_way_quicksort(a, l, j); three_way_quicksort(a, i, r); } -void sed_quicksort(int a[], int n) +void +sed_quicksort(int a[], int n) { - three_way_quicksort(a, 0, n-1); + three_way_quicksort(a, 0, n - 1); } /* ====================== HEAPSORT ======================= */ -#define LEFT(idx) (idx*2+1) -#define RIGHT(idx) (idx*2+2) -#define PARENT(idx) ((idx-1)/2) +#define LEFT(idx) (idx * 2 + 1) +#define RIGHT(idx) (idx * 2 + 2) +#define PARENT(idx) ((idx - 1) / 2) static void fixdown(T heap[], int i, int n) @@ -197,7 +202,7 @@ fixdown(T heap[], int i, int n) for ( ;; ) { const int l = LEFT(i); const int r = RIGHT(i); - int m = i; + int m = i; if ( l < n && heap[m] < heap[l] ) m = l; @@ -226,76 +231,73 @@ my_heapsort(T a[], int n) { heapify(a, n); - for ( int i = n-1; i >= 0; --i ) { + for ( int i = n - 1; i >= 0; --i ) { swap(a, 0, i); fixdown(a, 0, i); } } void -heapsort_bu( T * data, int n ) // zu sortierendes Feld und seine Länge +heapsort_bu(T *data, int n) // zu sortierendes Feld und seine Länge { - T val; + T val; int parent, child; - int root= n >> 1; // erstes Blatt im Baum - int count= 0; // Zähler für Anzahl der Vergleiche - - for ( ; ; ) - { - if ( root ) { // Teil 1: Konstruktion des Heaps - parent= --root; - val= data[root]; // zu versickernder Wert + int root = n >> 1; // erstes Blatt im Baum + int count = 0; // Zähler für Anzahl der Vergleiche + + for ( ;; ) { + if ( root ) { // Teil 1: Konstruktion des Heaps + parent = --root; + val = data[root]; // zu versickernder Wert } - else - if ( --n ) { // Teil 2: eigentliche Sortierung - val= data[n]; // zu versickernder Wert vom Heap-Ende - data[n]= data[0]; // Spitze des Heaps hinter den Heap in - parent= 0; // den sortierten Bereich verschieben - } - else // Heap ist leer; Sortierung beendet - break; + else if ( --n ) { // Teil 2: eigentliche Sortierung + val = data[n]; // zu versickernder Wert vom Heap-Ende + data[n] = data[0]; // Spitze des Heaps hinter den Heap in + parent = 0; // den sortierten Bereich verschieben + } + else // Heap ist leer; Sortierung beendet + break; - while ( (child= (parent + 1) << 1) < n ) // zweites (!) Kind; - { // Abbruch am Ende des Heaps - if ( ++count, data[child-1] > data[child] ) // größeres Kind wählen + while ( (child = (parent + 1) << 1) < n ) // zweites (!) Kind; + { // Abbruch am Ende des Heaps + if ( ++count, data[child - 1] > data[child] ) // größeres Kind wählen --child; - data[parent]= data[child]; // größeres Kind nach oben rücken - parent= child; // in der Ebene darunter weitersuchen + data[parent] = data[child]; // größeres Kind nach oben rücken + parent = child; // in der Ebene darunter weitersuchen } - if ( child == n ) // ein einzelnes Kind am Heap-Ende - { // ist übersprungen worden - if ( ++count, data[--child] >= val ) { // größer als der zu versick- - data[parent]= data[child]; // ernde Wert, also noch nach oben - data[child]= val; // versickerten Wert eintragen + if ( child == n ) // ein einzelnes Kind am Heap-Ende + { // ist übersprungen worden + if ( ++count, data[--child] >= val ) { // größer als der zu versick- + data[parent] = data[child]; // ernde Wert, also noch nach oben + data[child] = val; // versickerten Wert eintragen continue; } - child= parent; // 1 Ebene nach oben zurück + child = parent; // 1 Ebene nach oben zurück } - else - { - if ( ++count, data[parent] >= val ) { // das Blatt ist größer als der - data[parent]= val; // zu versickernde Wert, der damit - continue; // direkt eingetragen werden kann + else { + if ( ++count, data[parent] >= val ) { // das Blatt ist größer als der + data[parent] = val; // zu versickernde Wert, der damit + continue; // direkt eingetragen werden kann } - child= (parent - 1) >> 1; // 2 Ebenen nach oben zurück + child = (parent - 1) >> 1; // 2 Ebenen nach oben zurück } - while ( child != root ) // maximal zum Ausgangspunkt zurück + while ( child != root ) // maximal zum Ausgangspunkt zurück { - parent= (child - 1) >> 1; // den Vergleichswert haben wir bereits + parent = (child - 1) >> 1; // den Vergleichswert haben wir bereits // nach oben verschoben - if ( ++count, data[parent] >= val ) // größer als der zu versickernde - break; // Wert, also Position gefunden + if ( ++count, data[parent] >= val ) // größer als der zu versickernde + break; // Wert, also Position gefunden - data[child]= data[parent]; // Rückverschiebung nötig - child= parent; // 1 Ebene nach oben zurück + data[child] = data[parent]; // Rückverschiebung nötig + child = parent; // 1 Ebene nach oben zurück } - data[child]= val; // versickerten Wert eintragen + data[child] = val; // versickerten Wert eintragen } } @@ -315,65 +317,67 @@ heapsort_bu( T * data, int n ) // zu sortierendes Feld und seine Länge /* the original v[i] element from the leaf level up. This is the main */ /* idea of bottom-up heapsort. */ /*-----------------------------------------------------------------------*/ -static void siftup(T v[], int i, int n) +static void +siftup(T v[], int i, int n) { int j, start; - T x; + T x; start = i; - x = v[i]; - j = i<<1; - while (j<=n) - { - if (j>1; - while (j>=start) - { if (v[j]>1; + j = i >> 1; + while ( j >= start ) { + if ( v[j] < x ) { + v[i] = v[j]; + i = j; + j = i >> 1; } - else break; + else + break; } v[i] = x; -} /* End of siftup */ +} /* End of siftup */ /*----------------------------------------------------------------------*/ /* The heapsort procedure; the original array is r[0..n-1], but here */ /* it is shifted to vector v[1..n], for convenience. */ /*----------------------------------------------------------------------*/ -void bottom_up_heapsort(T r[], int n) +void +bottom_up_heapsort(T r[], int n) { - int k; - T x; - T *v; - - v = r-1; /* The address shift */ - -/* Build the heap bottom-up, using siftup. */ - for (k=n>>1; k>1; k--) siftup(v, k, n); - -/* The main loop of sorting follows. The root is swapped with the last */ -/* leaf after each sift-up. */ - for (k=n; k>1; k--) - { - siftup(v, 1, k); - x = v[k]; v[k] = v[1]; v[1] = x; - } -} /* End of bottom_up_heapsort */ - - + int k; + T x; + T * v; + + v = r - 1; /* The address shift */ + + /* Build the heap bottom-up, using siftup. */ + for ( k = n >> 1; k > 1; k-- ) + siftup(v, k, n); + + /* The main loop of sorting follows. The root is swapped with the last */ + /* leaf after each sift-up. */ + for ( k = n; k > 1; k-- ) { + siftup(v, 1, k); + x = v[k]; + v[k] = v[1]; + v[1] = x; + } +} /* End of bottom_up_heapsort */ /* ====================== HEAPSORT ======================= */ /* ====================== INTROSORT ======================= */ - - static void introsort(T a[], int n, int h) { @@ -397,7 +401,7 @@ introsort(T a[], int n, int h) swap(a, 0, last); introsort(a, last, h); - introsort(a+last+1, n-last-1, h); + introsort(a + last + 1, n - last - 1, h); } void @@ -412,67 +416,74 @@ my_introsort(T a[], int n) insertsort(a, n); } -static void pp_quicksort_impl(T a[], int l, int u) +static void +pp_quicksort_impl(T a[], int l, int u) { if ( u - l < CUTOFF ) return; swap(a, l, randint(l, u)); - T t = a[l]; + T t = a[l]; int i = l; - int j = u+1; - for (;;) { - do i++; while ( /*i <= u &&*/ a[i] < t ); - do j--; while ( a[j] > t ); + int j = u + 1; + for ( ;; ) { + do + i++; + while ( /*i <= u &&*/ a[i] < t ); + do + j--; + while ( a[j] > t ); if ( i > j ) break; swap(a, i, j); } swap(a, l, j); - pp_quicksort_impl(a, l, j-1); - pp_quicksort_impl(a, j+1, u); + pp_quicksort_impl(a, l, j - 1); + pp_quicksort_impl(a, j + 1, u); } void pp_quicksort(T a[], int n) { - pp_quicksort_impl(a, 0, n-1); + pp_quicksort_impl(a, 0, n - 1); insertsort(a, n); } -static void pp_quicksort_impl_it(T a[], int l, int u, int h) +static void +pp_quicksort_impl_it(T a[], int l, int u, int h) { if ( --h == 1 ) { - my_heapsort(a+l, u-l+1); + my_heapsort(a + l, u - l + 1); return; } - while ( u-l >= CUTOFF ) - { + while ( u - l >= CUTOFF ) { swap(a, l, randint(l, u)); - T t = a[l]; + T t = a[l]; int i = l; - int j = u+1; - - for (;;) { - do i++; while ( /*i <= u && */ a[i] < t ); - do j--; while ( a[j] > t ); + int j = u + 1; + + for ( ;; ) { + do + i++; + while ( /*i <= u && */ a[i] < t ); + do + j--; + while ( a[j] > t ); if ( i > j ) break; swap(a, i, j); } swap(a, l, j); - if ( j - l < u - j ) - { - pp_quicksort_impl_it(a, l, j-1, h); + if ( j - l < u - j ) { + pp_quicksort_impl_it(a, l, j - 1, h); l = j + 1; } - else - { - pp_quicksort_impl_it(a, j+1, u, h); + else { + pp_quicksort_impl_it(a, j + 1, u, h); u = j - 1; } } @@ -486,7 +497,7 @@ pp_quicksort_it(T a[], int n) for ( int nn = 1; nn < n; nn <<= 1 ) ++h; - pp_quicksort_impl_it(a, 0, n-1, h); + pp_quicksort_impl_it(a, 0, n - 1, h); insertsort(a, n); } @@ -495,8 +506,8 @@ binary_search(T x, T v[], int n) { int low, high; - low = 0; - high = n-1; + low = 0; + high = n - 1; while ( low <= high ) { int mid = low + ((high - low) / 2); if ( x > v[mid] ) @@ -514,7 +525,7 @@ lower_bound(T x, T v[], int n) { int low, high; - low = 0; + low = 0; high = n; while ( low < high ) { int mid = low + ((high - low) / 2); @@ -532,7 +543,7 @@ upper_bound(T x, T v[], int n) { int low, high; - low = 0; + low = 0; high = n; while ( low < high ) { int mid = low + ((high - low) / 2); @@ -542,57 +553,63 @@ upper_bound(T x, T v[], int n) else high = mid; } - return ( low > 0 && x == v[low-1] ) ? low-1 : -1; + return (low > 0 && x == v[low - 1]) ? low - 1 : -1; } /* TESTTREIBER */ - -void gen_testset_random(T a[], int n) +void +gen_testset_random(T a[], int n) { for ( int i = 0; i < n; ++i ) a[i] = bigrand(); } -void gen_testset_random2(T a[], int n) +void +gen_testset_random2(T a[], int n) { for ( int i = 0; i < n; ++i ) a[i] = bigrand() % 100; } -void gen_testset_asc(T a[], int n) +void +gen_testset_asc(T a[], int n) { for ( int i = 0; i < n; ++i ) a[i] = i; } -void gen_testset_desc(T a[], int n) +void +gen_testset_desc(T a[], int n) { for ( int i = n; i >= 0; --i ) a[i] = i; } -void gen_testset_unique(T a[], int n) +void +gen_testset_unique(T a[], int n) { for ( int i = 0; i < n; ++i ) a[i] = 1; } -void test_sorting(T a[], int n) +void +test_sorting(T a[], int n) { for ( int i = 1; i < n; ++i ) - if ( a[i-1] > a[i] ) { + if ( a[i - 1] > a[i] ) { puts("Fehler!"); exit(EXIT_SUCCESS); } } -void do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[], int n)) +void +do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[], int n)) { - T *a; + T * a; clock_t start, ende; - a = malloc(sizeof(T) * n); + a = malloc(sizeof(T) * (size_t) n); (*gen_testset)(a, n); @@ -608,7 +625,8 @@ void do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[] fflush(stdout); } -void do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n)) +void +do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n)) { printf("%-15.15s n=%-10d: ", msg, n); do_one_test(n, do_sort, gen_testset_random); @@ -621,7 +639,8 @@ void do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n)) /* ENDE TESTTREIBER */ -int main(void) +int +main(void) { const int n = 20000000; @@ -663,4 +682,3 @@ int _main(void) return EXIT_SUCCESS; } #endif - 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) void verify_properties(rbtree t) { + (void) t; #ifdef VERIFY_RBTREE verify_property_1(t->root); 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 @@ #include "util.h" +/* --8<-- ring_type */ typedef int T; struct ring_buffer { size_t head, tail; T array[8]; /* fit for your needs... */ }; +/* -->8-- */ +/* --8<-- ring_init */ void ring_init(struct ring_buffer *rb) { rb->head = rb->tail = 0; } +/* -->8-- */ +/* --8<-- ring_push_front */ bool ring_push_front(struct ring_buffer *rb, T data) { @@ -31,7 +36,9 @@ ring_push_front(struct ring_buffer *rb, T data) return true; } +/* -->8-- */ +/* --8<-- ring_push_back */ bool ring_push_back(struct ring_buffer *rb, T data) { @@ -45,7 +52,9 @@ ring_push_back(struct ring_buffer *rb, T data) return true; } +/* -->8-- */ +/* --8<-- ring_pop_front */ bool ring_pop_front(struct ring_buffer *rb, T *data) { @@ -59,7 +68,9 @@ ring_pop_front(struct ring_buffer *rb, T *data) return true; } +/* -->8-- */ +/* --8<-- ring_pop_back */ bool ring_pop_back(struct ring_buffer *rb, T *data) { @@ -73,18 +84,23 @@ ring_pop_back(struct ring_buffer *rb, T *data) return true; } +/* -->8-- */ +/* --8<-- ring_put */ bool ring_put(struct ring_buffer *rb, T data) { return ring_push_back(rb, data); } +/* -->8-- */ +/* --8<-- ring_get */ bool ring_get(struct ring_buffer *rb, T *data) { return ring_pop_front(rb, data); } +/* -->8-- */ void f() diff --git a/stack.c b/stack.c index 775269d..f594775 100644 --- a/stack.c +++ b/stack.c @@ -6,6 +6,7 @@ /* Project */ #include "util.h" +/* --8<-- stack_type */ typedef int T; struct stack_item { @@ -16,13 +17,17 @@ struct stack_item { struct stack { struct stack_item *head; }; +/* -->8-- */ +/* --8<-- stack_init */ void stack_init(struct stack *stack) { stack->head = NULL; } +/* -->8-- */ +/* --8<-- stack_push */ void stack_push(struct stack *stack, T data) { @@ -36,7 +41,9 @@ stack_push(struct stack *stack, T data) else ERROR("out of memory"); } +/* -->8-- */ +/* --8<-- stack_pop */ bool stack_pop(struct stack *stack, T *data) { @@ -54,13 +61,17 @@ stack_pop(struct stack *stack, T *data) else return false; } +/* -->8-- */ +/* --8<-- stack_empty */ bool stack_empty(struct stack *stack) { return stack->head == NULL; } +/* -->8-- */ +/* --8<-- stack_free */ void stack_free(struct stack *stack) { @@ -71,6 +82,7 @@ stack_free(struct stack *stack) free(item); } } +/* -->8-- */ int main() diff --git a/stack2.c b/stack2.c index 4c77ac2..b4b8afd 100644 --- a/stack2.c +++ b/stack2.c @@ -4,13 +4,16 @@ #include "util.h" +/* --8<-- stack2_type */ typedef int T; struct stack { T * array; size_t sz, p; }; +/* -->8-- */ +/* --8<-- stack2_init */ void stack_init(struct stack *stack) { @@ -18,7 +21,9 @@ stack_init(struct stack *stack) stack->sz = 0; stack->p = 0; } +/* -->8-- */ +/* --8<-- stack2_push */ bool stack_push(struct stack *stack, T data) { @@ -50,7 +55,9 @@ stack_push(struct stack *stack, T data) stack->array[stack->p++] = data; return true; } +/* -->8-- */ +/* --8<-- stack2_pop */ bool stack_pop(struct stack *stack, T *data) { @@ -65,18 +72,23 @@ stack_pop(struct stack *stack, T *data) else return false; } +/* -->8-- */ +/* --8<-- stack2_empty */ bool stack_empty(struct stack *stack) { return stack->p == 0; } +/* -->8-- */ +/* --8<-- stack2_free */ void stack_free(struct stack *stack) { free(stack->array); } +/* -->8-- */ int main() diff --git a/tree.c b/tree.c index cc2ae53..f6ccc5a 100644 --- a/tree.c +++ b/tree.c @@ -7,6 +7,7 @@ #include "util.h" +/* --8<-- tree_type */ typedef int T; struct tree_node { @@ -15,7 +16,9 @@ struct tree_node { int count; /* collision counter */ /* ggf. weitere Felder... */ }; +/* -->8-- */ +/* --8<-- tree_isBst */ static bool tree_isBstUntil(struct tree_node *tree, T min, T max) { @@ -34,7 +37,9 @@ tree_isBst(struct tree_node *tree) { return tree_isBstUntil(tree, INT_MIN, INT_MAX); } +/* -->8-- */ +/* --8<-- tree_insert */ struct tree_node * tree_insert(struct tree_node *tree, T key) { @@ -58,7 +63,9 @@ tree_insert(struct tree_node *tree, T key) return tree; } +/* -->8-- */ +/* --8<-- tree_insert_it */ struct tree_node * tree_insert_it(struct tree_node *tree, T key) { @@ -104,7 +111,9 @@ tree_insert_it(struct tree_node *tree, T key) return tree; } +/* -->8-- */ +/* --8<-- tree_detach_min */ static struct tree_node * tree_detach_min(struct tree_node **ptree) { @@ -119,7 +128,9 @@ tree_detach_min(struct tree_node **ptree) return tree; } } +/* -->8-- */ +/* --8<-- tree_remove */ struct tree_node * tree_remove(struct tree_node *tree, T key) { @@ -154,7 +165,9 @@ tree_remove(struct tree_node *tree, T key) } return tree; } +/* -->8-- */ +/* --8<-- tree_clear */ void tree_clear(struct tree_node *tree) { @@ -164,7 +177,9 @@ tree_clear(struct tree_node *tree) free(tree); } } +/* -->8-- */ +/* --8<-- tree_lookup */ struct tree_node * tree_lookup(struct tree_node *tree, T key) { @@ -178,7 +193,9 @@ tree_lookup(struct tree_node *tree, T key) return tree; } +/* -->8-- */ +/* --8<-- tree_minimum */ struct tree_node * tree_minimum(struct tree_node *tree) { @@ -188,7 +205,9 @@ tree_minimum(struct tree_node *tree) return tree; } +/* -->8-- */ +/* --8<-- tree_maximum */ struct tree_node * tree_maximum(struct tree_node *tree) { @@ -198,7 +217,9 @@ tree_maximum(struct tree_node *tree) return tree; } +/* -->8-- */ +/* --8<-- tree_height */ size_t tree_height(struct tree_node *tree) { @@ -211,7 +232,9 @@ tree_height(struct tree_node *tree) return 0; } +/* -->8-- */ +/* --8<-- tree_count */ size_t tree_count(struct tree_node *tree) { @@ -220,13 +243,17 @@ tree_count(struct tree_node *tree) return 0; } +/* -->8-- */ +/* --8<-- tree_isleaf */ bool tree_isleaf(struct tree_node *tree) { return tree->left == NULL && tree->right == NULL; } +/* -->8-- */ +/* --8<-- tree_apply_preorder */ void tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) { @@ -236,7 +263,9 @@ tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void tree_apply_preorder(tree->right, visit, cl); } } +/* -->8-- */ +/* --8<-- tree_apply_inorder */ void tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) { @@ -246,7 +275,9 @@ tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void tree_apply_inorder(tree->right, visit, cl); } } +/* -->8-- */ +/* --8<-- tree_apply_postorder */ void tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) { @@ -256,9 +287,11 @@ tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), voi visit(tree->key, cl); } } +/* -->8-- */ /* ===== */ +/* --8<-- tree_stack_type */ struct stack_item { struct stack_item *next; struct tree_node * data; @@ -267,13 +300,17 @@ struct stack_item { struct stack { struct stack_item *head; }; +/* -->8-- */ +/* --8<-- tree_stack_init */ static void stack_init(struct stack *stack) { stack->head = NULL; } +/* -->8-- */ +/* --8<-- tree_stack_push */ static void stack_push(struct stack *stack, struct tree_node *data) { @@ -287,7 +324,9 @@ stack_push(struct stack *stack, struct tree_node *data) else ERROR("out of memory"); } +/* -->8-- */ +/* --8<-- tree_stack_pop */ static bool stack_pop(struct stack *stack, struct tree_node **data) { @@ -305,19 +344,25 @@ stack_pop(struct stack *stack, struct tree_node **data) else return false; } +/* -->8-- */ +/* --8<-- tree_stack_peek */ static struct tree_node * stack_peek(struct stack *stack) { return (stack->head != NULL) ? stack->head->data : NULL; } +/* -->8-- */ +/* --8<-- tree_stack_empty */ static bool stack_empty(struct stack *stack) { return stack->head == NULL; } +/* -->8-- */ +/* --8<-- tree_stack_free */ void stack_free(struct stack *stack) { @@ -328,9 +373,11 @@ stack_free(struct stack *stack) free(item); } } +/* -->8-- */ /* ===== */ +/* --8<-- tree_queue_type */ struct queue_item { struct queue_item *next; struct tree_node * data; @@ -339,13 +386,17 @@ struct queue_item { struct queue { struct queue_item *head, *tail; }; +/* -->8-- */ +/* --8<-- tree_queue_init */ void queue_init(struct queue *queue) { queue->head = NULL; } +/* -->8-- */ +/* --8<-- tree_queue_put */ void queue_put(struct queue *queue, struct tree_node *data) { @@ -367,7 +418,9 @@ queue_put(struct queue *queue, struct tree_node *data) else ERROR("out of memory"); } +/* -->8-- */ +/* --8<-- tree_queue_get */ bool queue_get(struct queue *queue, struct tree_node **data) { @@ -385,13 +438,17 @@ queue_get(struct queue *queue, struct tree_node **data) else return false; } +/* -->8-- */ +/* --8<-- tree_queue_empty */ bool queue_empty(struct queue *queue) { return queue->head == NULL; } +/* -->8-- */ +/* --8<-- tree_queue_free */ void queue_free(struct queue *queue) { @@ -402,9 +459,11 @@ queue_free(struct queue *queue) free(item); } } +/* -->8-- */ /* ===== */ +/* --8<-- tree_apply_preorder_it */ void tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) { @@ -427,7 +486,9 @@ tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), v stack_free(&stack); } } +/* -->8-- */ +/* --8<-- tree_apply_inorder_it */ void tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) { @@ -451,10 +512,12 @@ tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), vo stack_free(&stack); } } +/* -->8-- */ // Hier eine Version für PostOrder-Iterativ: // Quelle: https://stackoverflow.com/a/16092333 +/* --8<-- tree_apply_postorder_it */ void tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) { @@ -488,7 +551,9 @@ tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), stack_free(&stack); } } +/* -->8-- */ +/* --8<-- tree_apply_levelorder_it */ void tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) { @@ -511,13 +576,17 @@ tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), queue_free(&queue); } } +/* -->8-- */ /* ======================== */ +/* --8<-- tree_iterator_type */ struct tree_iterator { struct stack stack; }; +/* -->8-- */ +/* --8<-- tree_iterator_push_leftmost */ static void tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node) { @@ -525,7 +594,9 @@ tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node) stack_push(stack, node); } } +/* -->8-- */ +/* --8<-- tree_iterator_next */ struct tree_node * tree_iterator_next(struct tree_iterator *it) { @@ -537,7 +608,9 @@ tree_iterator_next(struct tree_iterator *it) return node; } +/* -->8-- */ +/* --8<-- tree_iterator_first */ struct tree_node * tree_iterator_first(struct tree_iterator *it, struct tree_node *tree) { @@ -547,13 +620,17 @@ tree_iterator_first(struct tree_iterator *it, struct tree_node *tree) return tree_iterator_next(it); } +/* -->8-- */ +/* --8<-- tree_iterator_free */ void tree_iterator_free(struct tree_iterator *it) { stack_free(&it->stack); } +/* -->8-- */ +/* --8<-- tree_preorder_iterator_next */ struct tree_node * tree_preorder_iterator_next(struct tree_iterator *it) { @@ -570,7 +647,9 @@ tree_preorder_iterator_next(struct tree_iterator *it) return node; } +/* -->8-- */ +/* --8<-- tree_preorder_iterator_first */ struct tree_node * tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree) { @@ -585,6 +664,7 @@ tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree) return NULL; } } +/* -->8-- */ /* ===== */ -- cgit v1.3