add scene lighting constructs; real stdin support
[chaz/rasterize] / 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
This page took 0.044865 seconds and 4 git commands to generate.