Dogcows Code - chaz/rasterize/blob - rbtree.h

   1
   2 /*
   3  * CS5600 University of Utah
   4  * Charles McGarvey
   5  * mcgarvey@eng.utah.edu
   6  */
   7
   8 #ifndef _RBTREE_H_
   9 #define _RBTREE_H_
  10
  11 #include "common.h"
  12
  13
  14 #define RBTREE_BLACK (0)
  15 #define RBTREE_RED   (1)
  16
  17
  18 /*
  19  * A single node of the red-black tree.
  20  */
  21 struct rbtree_node
  22 {
  23     struct rbtree_node* parent;
  24     struct rbtree_node* left;
  25     struct rbtree_node* right;
  26     char                color;
  27 };
  28 typedef struct rbtree_node rbtree_node_t;
  29
  30 /*
  31  * Get a pointer to the data stored in a node.
  32  */
  33 #define RBTREE_NODE_DATA(N) ((void*)((char*)N + sizeof(rbtree_node_t)))
  34
  35 /*
  36  * A pointer to the global sentinel node.
  37  */
  38 extern rbtree_node_t* rbtree_sentinel;
  39
  40
  41 /*
  42  * In order to search the tree, you need a function matching this protocol.
  43  */
  44 typedef int (*rbtree_search_fn_t)(rbtree_node_t** np, void* data);
  45
  46
  47 /*
  48  * The famous and well-loved red and black tree structure.
  49  */
  50 struct rbtree
  51 {
  52     rbtree_node_t*      root;
  53     size_t              size;
  54     rbtree_search_fn_t  search;
  55 };
  56 typedef struct rbtree rbtree_t;
  57
  58 /*
  59  * Allocate a new red-black tree.  It takes the size of the data to be stored
  60  * in each node and a search function.
  61  */
  62 rbtree_t* rbtree_alloc(size_t size, rbtree_search_fn_t search);
  63
  64 /*
  65  * Destroy a red-black tree, returning its memory to the allocator.
  66  */
  67 void rbtree_destroy(rbtree_t* t);
  68
  69
  70 /*
  71  * The common actions which can be invoked on a tree.
  72  * These are O(logn) operations.
  73  */
  74 rbtree_node_t* rbtree_delete(rbtree_t* t, void* data);
  75 rbtree_node_t* rbtree_insert(rbtree_t* t, void* data);
  76 rbtree_node_t* rbtree_search(rbtree_t* t, void* data);
  77
  78 /*
  79  * If you already have a pointer to a node, you can delete it directly.
  80  * This is a O(1) operation.
  81  */
  82 rbtree_node_t* rbtree_delete_node(rbtree_t* t, rbtree_node_t* n);
  83
  84
  85 /*
  86  * Determine whether or not the tree is empty.
  87  */
  88 INLINE_MAYBE
  89 bool rbtree_empty(rbtree_t* t)
  90 {
  91     return (t->root == rbtree_sentinel);
  92 }
  93
  94 /*
  95  * Clear the tree of all of its nodes.
  96  */
  97 void rbtree_clear(rbtree_t* t);
  98
  99
 100 /*
 101  * Get the node with the minimum data in the tree.
 102  * This is a O(logn) operation.
 103  */
 104 INLINE_MAYBE
 105 rbtree_node_t* rbtree_node_min(rbtree_node_t* n)
 106 {
 107     while (n->left != rbtree_sentinel) {
 108         n = n->left;
 109     }
 110     return n;
 111 }
 112
 113 /*
 114  * Get the node with the maximum data in the tree.
 115  * This is a O(logn) operation.
 116  */
 117 INLINE_MAYBE
 118 rbtree_node_t* rbtree_node_max(rbtree_node_t* n)
 119 {
 120     while (n->right != rbtree_sentinel) {
 121         n = n->right;
 122     }
 123     return n;
 124 }
 125
 126
 127 /*
 128  * A function that can be used as a callback for handling tree data.
 129  */
 130 typedef void (*rbtree_call_fn_t)(void* e);
 131
 132 /*
 133  * Call a function for each node in the tree, from smallest to greatest.
 134  */
 135 void rbtree_call(const rbtree_t* t, rbtree_call_fn_t fn);
 136
 137
 138 #endif // _RBTREE_H_
 139