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

diff --git a/rbtree.h b/rbtree.h
new file mode 100644
index 0000000..4f72632
--- /dev/null
+++ b/rbtree.h
@@ -0,0 +1,139 @@
+
+/*
+ * CS5600 University of Utah
+ * Charles McGarvey
+ * mcgarvey@eng.utah.edu
+ */
+
+#ifndef _RBTREE_H_
+#define _RBTREE_H_
+
+#include "common.h"
+
+
+#define RBTREE_BLACK (0)
+#define RBTREE_RED   (1)
+
+
+/*
+ * A single node of the red-black tree.
+ */
+struct rbtree_node
+{
+    struct rbtree_node* parent;
+    struct rbtree_node* left;
+    struct rbtree_node* right;
+    char                color;          
+};
+typedef struct rbtree_node rbtree_node_t;
+
+/*
+ * Get a pointer to the data stored in a node.
+ */
+#define RBTREE_NODE_DATA(N) ((void*)((char*)N + sizeof(rbtree_node_t)))
+
+/*
+ * A pointer to the global sentinel node.
+ */
+extern rbtree_node_t* rbtree_sentinel;
+
+
+/*
+ * In order to search the tree, you need a function matching this protocol.
+ */
+typedef int (*rbtree_search_fn_t)(rbtree_node_t** np, void* data);
+
+
+/*
+ * The famous and well-loved red and black tree structure.
+ */
+struct rbtree
+{
+    rbtree_node_t*      root;
+    size_t              size;
+    rbtree_search_fn_t  search;
+};
+typedef struct rbtree rbtree_t;
+
+/*
+ * Allocate a new red-black tree.  It takes the size of the data to be stored
+ * in each node and a search function.
+ */
+rbtree_t* rbtree_alloc(size_t size, rbtree_search_fn_t search);
+
+/*
+ * Destroy a red-black tree, returning its memory to the allocator.
+ */
+void rbtree_destroy(rbtree_t* t);
+
+
+/*
+ * The common actions which can be invoked on a tree.
+ * These are O(logn) operations.
+ */
+rbtree_node_t* rbtree_delete(rbtree_t* t, void* data);
+rbtree_node_t* rbtree_insert(rbtree_t* t, void* data);
+rbtree_node_t* rbtree_search(rbtree_t* t, void* data);
+
+/*
+ * If you already have a pointer to a node, you can delete it directly.
+ * This is a O(1) operation.
+ */
+rbtree_node_t* rbtree_delete_node(rbtree_t* t, rbtree_node_t* n);
+
+
+/*
+ * Determine whether or not the tree is empty.
+ */
+INLINE_MAYBE
+bool rbtree_empty(rbtree_t* t)
+{
+    return (t->root == rbtree_sentinel);
+}
+
+/*
+ * Clear the tree of all of it's nodes.
+ */
+void rbtree_clear(rbtree_t* t);
+
+
+/*
+ * Get the node with the minimum data in the tree.
+ * This is a O(logn) operation.
+ */
+INLINE_MAYBE
+rbtree_node_t* rbtree_node_min(rbtree_node_t* n)
+{
+    while (n->left != rbtree_sentinel) {
+        n = n->left;
+    }
+    return n;
+}
+
+/*
+ * Get the node with the maximum data in the tree.
+ * This is a O(logn) operation.
+ */
+INLINE_MAYBE
+rbtree_node_t* rbtree_node_max(rbtree_node_t* n)
+{
+    while (n->right != rbtree_sentinel) {
+        n = n->right;
+    }
+    return n;
+}
+
+
+/*
+ * A function that can be used as a callback for handling tree data.
+ */
+typedef void (*rbtree_call_fn_t)(void* e);
+
+/*
+ * Call a function for each node in the tree, from smallest to greatest.
+ */
+void rbtree_call(const rbtree_t* t, rbtree_call_fn_t fn);
+
+
+#endif // _RBTREE_H_
+