Anonymous avatar Anonymous committed 5d55955

add bstree.h, add _for_each to list and vector

Comments (0)

Files changed (4)

+#ifndef _BSTREE_H_
+#define _BSTREE_H_
+
+#include <stdlib.h>
+#define bstree_def(Name, Type, Cmp)                       \
+typedef struct Name##_ Name;                              \
+struct Name##_ {                                          \
+    Type  data;                                           \
+    Name *left;                                           \
+    Name *right;                                          \
+    Name *parent;                                         \
+};                                                        \
+static inline int Name##_cmp(Type a, Type b)              \
+{                                                         \
+    return Cmp;                                           \
+}                                                         \
+Name *Name##_new(Type t)                                  \
+{                                                         \
+    Name *n = malloc(sizeof(Name));                       \
+    if (!n)                                               \
+        return NULL;                                      \
+    *n = (Name){ t, NULL, NULL, NULL };                   \
+    return n;                                             \
+}                                                         \
+Name *Name##_find(Name *n, Type t)                        \
+{                                                         \
+    while (n) {                                           \
+        int c = Name##_cmp(t, n->data);                   \
+        if      (c < 0) n = n->left;                      \
+        else if (c > 0) n = n->right;                     \
+        else            return n;                         \
+    }                                                     \
+    return NULL;                                          \
+}                                                         \
+void Name##_for_each(Name *n, void (*act)(Type*))         \
+{                                                         \
+    if (!n)                                               \
+        return;                                           \
+    Name##_for_each(n->left , act);                       \
+    act(&n->data);                                        \
+    Name##_for_each(n->right, act);                       \
+}                                                         \
+Name *Name##_insert(Name **q, Type t)                     \
+{                                                         \
+    Name *n, *p;                                          \
+    if (!q)                                               \
+        return NULL;                                      \
+    if (!*q)                                              \
+        return *q = Name##_new(t);                        \
+    for (n = *q; n; p = n, n = *q) {                      \
+        int c = Name##_cmp(t, n->data);                   \
+        if      (c < 0) q = &n->left;                     \
+        else if (c > 0) q = &n->right;                    \
+        else {                                            \
+            n->data = t;                                  \
+            return n;                                     \
+        }                                                 \
+    }                                                     \
+    n = *q = Name##_new(t);                               \
+    n->parent = p;                                        \
+    return n;                                             \
+}                                                         \
+void Name##_del(Name **q)                                 \
+{                                                         \
+    Name *n, *d;                                          \
+    if (!q || !*q)                                        \
+        return;                                           \
+    n = *q;                                               \
+    if (n->parent)                                        \
+        q = (n->parent->left == n) ? &n->parent->left     \
+                                   : &n->parent->right;   \
+    switch (!!n->left + !!n->right) {                     \
+        case 0: *q = NULL;                                \
+                free(n);                                  \
+                break;                                    \
+        case 1: *q = n->left ? n->left : n->right;        \
+                (*q)->parent = n->parent;                 \
+                free(n);                                  \
+                break;                                    \
+        case 2: for (d = n->left; d->right; d = d->right) \
+                    ;                                     \
+                n->data = d->data;                        \
+                Name##_del(&d);                           \
+                break;                                    \
+    }                                                     \
+}                                                         \
+void Name##_del_all(Name **q)                             \
+{                                                         \
+    if (!q || !*q)                                        \
+        return;                                           \
+    Name##_del_all(&(*q)->left);                          \
+    Name##_del_all(&(*q)->right);                         \
+    free(*q);                                             \
+    *q = NULL;                                            \
+}
+#endif
 #include "vector.h"
 #include "list.h"
 #include "heap.h"
+#include "bstree.h"
 
 vector_def(Stack, int) // use vector as stack
 list_def  (Listn, int) // use list node as list
 heap_def  (Max_heap, int, a < b)
+bstree_def(Btree, int, (a > b) - (a < b))
 
+void print_int(int *i) { printf("%d,", *i); }
 #define LENGTH(x) (sizeof(x) / sizeof(*x))
 int main(void)
 {
     int   i = 20;
     while (i--)
         Stack_push(s, i);
+    Stack_for_each(s, print_int);
+    printf("\n");
     while (s->size)
-        printf("%d\n", Stack_pop(s));
+        printf("%d,", Stack_pop(s));
+    printf("\n");
     Stack_del(s);
 
     /* List demo */
-    // dummy node for use as head, not strictly necessary
-    // but I like that way it works out better.
-    Listn *head = Listn_new(-1);
+    Listn *head = NULL;
     i = 5;
     while (i--)
-        Listn_insert(head, i);
-    for (Listn *p = head->next; p != head; p = p->next)
-        printf("%d\n", p->data);
-    Listn_del(head->prev);
-    for (Listn *p = head->prev; p != head; p = p->prev)
-        printf("%d\n", p->data);
-    Listn_del_all(head);
+        Listn_insert(&head, i);
+    Listn_for_each(head, print_int);
+    printf("\n");
+    Listn_del(&head->prev->prev);
+
+    // reverse traversal
+    Listn *p = head->prev;
+    do {
+        printf("%d,",p->data);
+        p = p->prev;
+    } while (p != head->prev);
+    printf("\n");
+    Listn_del_all(&head);
 
     /* Heap demo */
     size_t j;
         Max_heap_push(v->data, v->size - 1, rand() % j); // place the member
     }
     while (v->size) {
-        printf("%d\n", Max_heap_pop(v->data, v->size)); // get the member
+        printf("%d,", Max_heap_pop(v->data, v->size)); // get the member
         Stack_pop(v); // remove it's place
     }
-    printf("empty size:%zu\n", v->size);
+    printf("\nempty size:%zu\n", v->size);
     Stack_del(v);
 
+    /* bstree demo */
+    Btree *root = NULL;
+    printf("Btree inserting: ");
+    for (i = 20; i; i--) {
+        printf("%zu,", j = rand() % 20);
+        Btree_insert(&root, j);
+    }
+    printf("\n");
+    Btree_for_each(root, print_int);
+    printf("\n");
+    Btree_del_all(&root);
+
     return 0;
 }
 
 #include <stdlib.h>
 
-#define list_def(Name, Type)         \
-typedef struct Name##_ Name;         \
-struct Name##_ {                     \
-    Type  data;                      \
-    Name *next;                      \
-    Name *prev;                      \
-};                                   \
-Name *Name##_new(Type t)             \
-{                                    \
-    Name *n = malloc(sizeof(Name));  \
-    if (!n)                          \
-        return NULL;                 \
-    n->data = t;                     \
-    n->next = n->prev = n;           \
-    return n;                        \
-}                                    \
-void Name##_del(Name *l)             \
-{                                    \
-    if (!l)                          \
-        return;                      \
-    l->next->prev = l->prev;         \
-    l->prev->next = l->next;         \
-    free(l);                         \
-}                                    \
-void Name##_del_all(Name *l)         \
-{                                    \
-    Name *p = l->next;               \
-    if (!l)                          \
-        return;                      \
-    while (p != l) {                 \
-        p = p->next;                 \
-        free(p->prev);               \
-    }                                \
-    free(p);                         \
-}                                    \
-Name *Name##_append(Name *l, Type t) \
-{                                    \
-    Name *n;                         \
-    if (!l || !(n = Name##_new(t)))  \
-        return NULL;                 \
-    n->prev = l;                     \
-    n->next = l->next;               \
-    l->next = n;                     \
-    n->next->prev = n;               \
-    return n;                        \
-}                                    \
-Name *Name##_insert(Name *l, Type t) \
-{                                    \
-    Name *n;                         \
-    if (!l || !(n = Name##_new(t)))  \
-        return NULL;                 \
-    n->next = l;                     \
-    n->prev = l->prev;               \
-    l->prev = n;                     \
-    n->prev->next = n;               \
-    return n;                        \
+#define list_def(Name, Type)                      \
+typedef struct Name##_ Name;                      \
+struct Name##_ {                                  \
+    Type  data;                                   \
+    Name *next;                                   \
+    Name *prev;                                   \
+};                                                \
+void Name##_for_each(Name *l, void (*act)(Type*)) \
+{                                                 \
+    Name *p = l;                                  \
+    if (!l)                                       \
+        return;                                   \
+    do {                                          \
+        act(&p->data);                            \
+        p = p->next;                              \
+    } while (p != l);                             \
+}                                                 \
+Name *Name##_new(Type t)                          \
+{                                                 \
+    Name *n = malloc(sizeof(Name));               \
+    if (!n)                                       \
+        return NULL;                              \
+    *n = (Name){ t, n, n };                       \
+    return n;                                     \
+}                                                 \
+void Name##_del(Name **l)                         \
+{                                                 \
+    Name *p;                                      \
+    if (!l || !*l)                                \
+        return;                                   \
+    p = *l;                                       \
+    p->next->prev = p->prev;                      \
+    p->prev->next = p->next;                      \
+    if (p->next == p)                             \
+        *l = NULL;                                \
+    free(p);                                      \
+}                                                 \
+void Name##_del_all(Name **l)                     \
+{                                                 \
+    Name *p;                                      \
+    if (!l || !*l)                                \
+        return;                                   \
+    for (p = (*l)->next; p != *l;) {              \
+        p = p->next;                              \
+        free(p->prev);                            \
+    }                                             \
+    free(p);                                      \
+    *l = NULL;                                    \
+}                                                 \
+Name *Name##_append(Name **l, Type t)             \
+{                                                 \
+    Name *n;                                      \
+    if (!l || !(n = Name##_new(t)))               \
+        return NULL;                              \
+    if (!*l)                                      \
+        return *l = n;                            \
+    n   ->prev = *l;                              \
+    n   ->next = (*l)->next;                      \
+    (*l)->next = n;                               \
+    n->next->prev = n;                            \
+    return n;                                     \
+}                                                 \
+Name *Name##_insert(Name **l, Type t)             \
+{                                                 \
+    Name *n;                                      \
+    if (!l || !(n = Name##_new(t)))               \
+        return NULL;                              \
+    if (!*l)                                      \
+        return *l = n;                            \
+    n   ->next = *l;                              \
+    n   ->prev = (*l)->prev;                      \
+    (*l)->prev = n;                               \
+    n->prev->next = n;                            \
+    return n;                                     \
 }
 
 #endif
     size_t capacity;                                                 \
     size_t min_capacity;                                             \
 } Name;                                                              \
+void Name##_for_each(Name *v, void (*act)(Type*))                    \
+{                                                                    \
+    size_t i;                                                        \
+    if (!v)                                                          \
+        return;                                                      \
+    for (i = 0; i < v->size; i++)                                    \
+        act(v->data + i);                                            \
+}                                                                    \
 ssize_t Name##_resize(Name *v, size_t capacity)                      \
 {                                                                    \
     Type *t = realloc(v->data, capacity * sizeof(Type));             \
     v->capacity = capacity;                                          \
     return capacity;                                                 \
 }                                                                    \
-Type *Name##_push(Name *v, Type m)                                   \
+Type *Name##_push(Name *v, Type t)                                   \
 {                                                                    \
     if (v->size == v->capacity)                                      \
         if (Name##_resize(v, size_t_max(v->capacity * 2, 1)) < 0)    \
             return NULL;                                             \
-    v->data[v->size] = m;                                            \
+    v->data[v->size] = t;                                            \
     return v->data + v->size++;                                      \
 }                                                                    \
 Type Name##_pop(Name *v)                                             \
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.