X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Frasterize;a=blobdiff_plain;f=rbtree.c;fp=rbtree.c;h=ad24a17f4b5606711667c84b96ad4cf1dc7101b3;hp=0000000000000000000000000000000000000000;hb=c875478cdd823c7df8fdc859941bd9e5948c9315;hpb=82087d9bb9e28c2375008bde4453f6c019419697

diff --git a/rbtree.c b/rbtree.c
new file mode 100644
index 0000000..ad24a17
--- /dev/null
+++ b/rbtree.c
@@ -0,0 +1,375 @@
+
+/*
+ * CS5600 University of Utah
+ * Charles McGarvey
+ * mcgarvey@eng.utah.edu
+ */
+
+#include "rbtree.h"
+
+
+#define BLACK       (RBTREE_BLACK)
+#define RED         (RBTREE_RED)
+#define SENTINEL    (rbtree_sentinel)
+
+
+rbtree_node_t _rbtree_sentinel = {
+    &_rbtree_sentinel, &_rbtree_sentinel, &_rbtree_sentinel,
+    BLACK
+};
+rbtree_node_t* rbtree_sentinel = &_rbtree_sentinel;
+
+
+/*
+ * Allocate and initialize a new node for the tree.
+ */
+INLINE_MAYBE
+rbtree_node_t* rbtree_node_alloc(rbtree_t* t)
+{
+    rbtree_node_t* n = mem_alloc(sizeof(rbtree_node_t) + t->size);
+    n->parent = NULL;
+    n->left = n->right = rbtree_sentinel;
+    n->color = RBTREE_BLACK;
+    return n;
+}
+
+
+INLINE_MAYBE
+void rbtree_init(rbtree_t* t, size_t size, rbtree_search_fn_t search)
+{
+    t->root = rbtree_sentinel;
+    t->size = size;
+    t->search = search;
+}
+
+rbtree_t* rbtree_alloc(size_t size, rbtree_search_fn_t search)
+{
+    rbtree_t* t = mem_alloc(sizeof(rbtree_t));
+    rbtree_init(t, size, search);
+    return t;
+}
+
+
+void rbtree_destroy(rbtree_t* t)
+{
+    rbtree_clear(t);
+    mem_free(t);
+}
+
+
+INLINE_MAYBE
+void _rotate_left(rbtree_node_t** r, rbtree_node_t* n)
+{
+    rbtree_node_t* t = n->right;
+    n->right = t->left;
+
+    if (t->left != SENTINEL) {
+        t->left->parent = n;
+    }
+    t->parent = n->parent;
+
+    if (n == *r) {
+        *r = t;
+    }
+    else if (n == n->parent->left) {
+        n->parent->left = t;
+    }
+    else {
+        n->parent->right = t;
+    }
+
+    t->left = n;
+    n->parent = t;
+}
+
+INLINE_MAYBE
+void _rotate_right(rbtree_node_t** r, rbtree_node_t* n)
+{
+    rbtree_node_t* t = n->left;
+    n->left = t->right;
+
+    if (t->right != SENTINEL) {
+        t->right->parent = n;
+    }
+    t->parent = n->parent;
+
+    if (n == *r) {
+        *r = t;
+    }
+    else if (n == n->parent->right) {
+        n->parent->right = t;
+    }
+    else {
+        n->parent->left = t;
+    }
+
+    t->right = n;
+    n->parent = t;
+}
+
+
+rbtree_node_t* rbtree_insert(rbtree_t* t, void* data)
+{
+    rbtree_node_t* r = t->root;
+    rbtree_node_t* n = r;
+
+    int c = t->search(&n, data);
+    if (c == 0) {
+        memcpy(RBTREE_NODE_DATA(n), data, t->size);
+        return n;
+    }
+    else if (n == SENTINEL) {
+        r = rbtree_node_alloc(t);
+        memcpy(RBTREE_NODE_DATA(r), data, t->size);
+        t->root = r;
+        return r;
+    }
+
+    rbtree_node_t* m = rbtree_node_alloc(t);
+    m->parent = n;
+    m->color = RED;
+    memcpy(RBTREE_NODE_DATA(m), data, t->size);
+    if (c < 0) {
+        n->left = m;
+    }
+    else {
+        n->right = m;
+    }
+
+    n = m;
+    while (n != r && n->parent->color == RED) {
+        if (n->parent == n->parent->parent->left) {
+            rbtree_node_t* t = n->parent->parent->right;
+            if (t->color == RED) {
+                n->parent->color = BLACK;
+                t->color = BLACK;
+                n->parent->parent->color = RED;
+                n = n->parent->parent;
+            }
+            else {
+                if (n == n->parent->right) {
+                    n = n->parent;
+                    _rotate_left(&r, n);
+                }
+                n->parent->color = BLACK;
+                n->parent->parent->color = RED;
+                _rotate_right(&r, n->parent->parent);
+            }
+        }
+        else {
+            rbtree_node_t* t = n->parent->parent->left;
+            if (t->color == RED) {
+                n->parent->color = BLACK;
+                t->color = BLACK;
+                n->parent->parent->color = RED;
+                n = n->parent->parent;
+            }
+            else {
+                if (n == n->parent->left) {
+                    n = n->parent;
+                    _rotate_right(&r, n);
+                }
+                n->parent->color = BLACK;
+                n->parent->parent->color = RED;
+                _rotate_left(&r, n->parent->parent);
+            }
+        }
+    }
+    t->root = r;
+    r->color = BLACK;
+
+    return m;
+}
+
+rbtree_node_t* rbtree_delete(rbtree_t* t, void* data)
+{
+    rbtree_node_t* n = t->root;
+    if (t->search(&n, data) == 0) {
+        return rbtree_delete_node(t, n);
+    }
+    return NULL;
+}
+
+rbtree_node_t* rbtree_search(rbtree_t* t, void* data)
+{
+    rbtree_node_t* n = t->root;
+    if (t->search(&n, data) == 0) {
+        return n;
+    }
+    return NULL;
+}
+
+
+rbtree_node_t* rbtree_delete_node(rbtree_t* t, rbtree_node_t* n)
+{
+    rbtree_node_t* r = t->root;
+    rbtree_node_t* u;
+    rbtree_node_t* v;
+
+    if (n->left == SENTINEL) {
+        u = n->right;
+        v = n;
+    }
+    else if (n->right == SENTINEL) {
+        u = n->left;
+        v = n;
+    }
+    else {
+        v = rbtree_node_min(n->right);
+        if (v->left != SENTINEL) {
+            u = v->left;
+        }
+        else {
+            u = v->right;
+        }
+    }
+
+    if (v == r) {
+        r = u;
+        u->color = BLACK;
+        goto done;
+    }
+
+    int isred = (v->color == RED);
+
+    if (v == v->parent->left) {
+        v->parent->left = u;
+    }
+    else {
+        v->parent->right = u;
+    }
+
+    if (v == n) {
+        u->parent = v->parent;
+    }
+    else {
+        if (v->parent == n) {
+            u->parent = v;
+        }
+        else {
+            u->parent = v->parent;
+        }
+
+        *v = *n;
+
+        if (n == r) {
+            r = v;
+        }
+        else if (n == n->parent->left) {
+            n->parent->left = v;
+        }
+        else {
+            n->parent->right = v;
+        }
+
+        if (v->left != SENTINEL) {
+            v->left->parent = v;
+        }
+        if (v->right != SENTINEL) {
+            v->right->parent = v;
+        }
+    }
+
+    if (isred) {
+        goto done;
+    }
+
+    while (u != r && u->color == BLACK) {
+        if (u == u->parent->left) {
+            rbtree_node_t* w = u->parent->right;
+            if (w->color == RED) {
+                w->color = BLACK;
+                w->parent->color = RED;
+                _rotate_left(&r, u->parent);
+                w = u->parent->right;
+            }
+            if (w->left->color == BLACK && w->right->color == BLACK) {
+                w->color = RED;
+                u = u->parent;
+            }
+            else {
+                if (w->right->color == BLACK) {
+                    w->left->color = BLACK;
+                    w->color = RED;
+                    _rotate_right(&r, w);
+                    w = u->parent->right;
+                }
+                w->color = u->parent->color;
+                u->parent->color = BLACK;
+                w->right->color = BLACK;
+                _rotate_left(&r, u->parent);
+                u = r;
+            }
+        }
+        else {
+            rbtree_node_t* w = u->parent->left;
+            if (w->color == RED) {
+                w->color = BLACK;
+                w->parent->color = RED;
+                _rotate_right(&r, u->parent);
+                w = u->parent->left;
+            }
+            if (w->left->color == BLACK && w->right->color == BLACK) {
+                w->color = RED;
+                u = u->parent;
+            }
+            else {
+                if (w->left->color == BLACK) {
+                    w->right->color = BLACK;
+                    w->color = RED;
+                    _rotate_left(&r, w);
+                    w = u->parent->left;
+                }
+                w->color = u->parent->color;
+                u->parent->color = BLACK;
+                w->left->color = BLACK;
+                _rotate_right(&r, u->parent);
+                u = r;
+            }
+        }
+    }
+    
+done:
+    t->root = r;
+    n->parent = n->left = n->right = NULL;
+    return n;
+}
+
+
+void node_call(rbtree_node_t* n, rbtree_call_fn_t fn)
+{
+    if (n == SENTINEL) {
+        return;
+    }
+    node_call(n->left, fn);
+    fn(RBTREE_NODE_DATA(n));
+    node_call(n->right, fn);
+}
+
+void rbtree_call(const rbtree_t* t, rbtree_call_fn_t fn)
+{
+    node_call(t->root, fn);
+}
+
+
+/*
+ * Prune off a branch of the tree.
+ */
+static void _node_prune(rbtree_node_t* n)
+{
+    if (n == SENTINEL) {
+        return;
+    }
+    _node_prune(n->left);
+    _node_prune(n->right);
+    mem_free(n);
+}
+
+void rbtree_clear(rbtree_t* t)
+{
+    if (t == NULL) {
+        return;
+    }
+    _node_prune(t->root);
+}
+