3 * CS5600 University of Utah
5 * mcgarvey@eng.utah.edu
11 #define BLACK (RBTREE_BLACK)
12 #define RED (RBTREE_RED)
13 #define SENTINEL (rbtree_sentinel)
16 rbtree_node_t _rbtree_sentinel
= {
17 &_rbtree_sentinel
, &_rbtree_sentinel
, &_rbtree_sentinel
,
20 rbtree_node_t
* rbtree_sentinel
= &_rbtree_sentinel
;
24 * Allocate and initialize a new node for the tree.
27 rbtree_node_t
* rbtree_node_alloc(rbtree_t
* t
)
29 rbtree_node_t
* n
= mem_alloc(sizeof(rbtree_node_t
) + t
->size
);
31 n
->left
= n
->right
= rbtree_sentinel
;
32 n
->color
= RBTREE_BLACK
;
38 void rbtree_init(rbtree_t
* t
, size_t size
, rbtree_search_fn_t search
)
40 t
->root
= rbtree_sentinel
;
45 rbtree_t
* rbtree_alloc(size_t size
, rbtree_search_fn_t search
)
47 rbtree_t
* t
= mem_alloc(sizeof(rbtree_t
));
48 rbtree_init(t
, size
, search
);
53 void rbtree_destroy(rbtree_t
* t
)
61 void _rotate_left(rbtree_node_t
** r
, rbtree_node_t
* n
)
63 rbtree_node_t
* t
= n
->right
;
66 if (t
->left
!= SENTINEL
) {
69 t
->parent
= n
->parent
;
74 else if (n
== n
->parent
->left
) {
86 void _rotate_right(rbtree_node_t
** r
, rbtree_node_t
* n
)
88 rbtree_node_t
* t
= n
->left
;
91 if (t
->right
!= SENTINEL
) {
94 t
->parent
= n
->parent
;
99 else if (n
== n
->parent
->right
) {
100 n
->parent
->right
= t
;
111 rbtree_node_t
* rbtree_insert(rbtree_t
* t
, void* data
)
113 rbtree_node_t
* r
= t
->root
;
114 rbtree_node_t
* n
= r
;
116 int c
= t
->search(&n
, data
);
118 memcpy(RBTREE_NODE_DATA(n
), data
, t
->size
);
121 else if (n
== SENTINEL
) {
122 r
= rbtree_node_alloc(t
);
123 memcpy(RBTREE_NODE_DATA(r
), data
, t
->size
);
128 rbtree_node_t
* m
= rbtree_node_alloc(t
);
131 memcpy(RBTREE_NODE_DATA(m
), data
, t
->size
);
140 while (n
!= r
&& n
->parent
->color
== RED
) {
141 if (n
->parent
== n
->parent
->parent
->left
) {
142 rbtree_node_t
* t
= n
->parent
->parent
->right
;
143 if (t
->color
== RED
) {
144 n
->parent
->color
= BLACK
;
146 n
->parent
->parent
->color
= RED
;
147 n
= n
->parent
->parent
;
150 if (n
== n
->parent
->right
) {
154 n
->parent
->color
= BLACK
;
155 n
->parent
->parent
->color
= RED
;
156 _rotate_right(&r
, n
->parent
->parent
);
160 rbtree_node_t
* t
= n
->parent
->parent
->left
;
161 if (t
->color
== RED
) {
162 n
->parent
->color
= BLACK
;
164 n
->parent
->parent
->color
= RED
;
165 n
= n
->parent
->parent
;
168 if (n
== n
->parent
->left
) {
170 _rotate_right(&r
, n
);
172 n
->parent
->color
= BLACK
;
173 n
->parent
->parent
->color
= RED
;
174 _rotate_left(&r
, n
->parent
->parent
);
184 rbtree_node_t
* rbtree_delete(rbtree_t
* t
, void* data
)
186 rbtree_node_t
* n
= t
->root
;
187 if (t
->search(&n
, data
) == 0) {
188 return rbtree_delete_node(t
, n
);
193 rbtree_node_t
* rbtree_search(rbtree_t
* t
, void* data
)
195 rbtree_node_t
* n
= t
->root
;
196 if (t
->search(&n
, data
) == 0) {
203 rbtree_node_t
* rbtree_delete_node(rbtree_t
* t
, rbtree_node_t
* n
)
205 rbtree_node_t
* r
= t
->root
;
209 if (n
->left
== SENTINEL
) {
213 else if (n
->right
== SENTINEL
) {
218 v
= rbtree_node_min(n
->right
);
219 if (v
->left
!= SENTINEL
) {
233 int isred
= (v
->color
== RED
);
235 if (v
== v
->parent
->left
) {
239 v
->parent
->right
= u
;
243 u
->parent
= v
->parent
;
246 if (v
->parent
== n
) {
250 u
->parent
= v
->parent
;
258 else if (n
== n
->parent
->left
) {
262 n
->parent
->right
= v
;
265 if (v
->left
!= SENTINEL
) {
268 if (v
->right
!= SENTINEL
) {
269 v
->right
->parent
= v
;
277 while (u
!= r
&& u
->color
== BLACK
) {
278 if (u
== u
->parent
->left
) {
279 rbtree_node_t
* w
= u
->parent
->right
;
280 if (w
->color
== RED
) {
282 w
->parent
->color
= RED
;
283 _rotate_left(&r
, u
->parent
);
284 w
= u
->parent
->right
;
286 if (w
->left
->color
== BLACK
&& w
->right
->color
== BLACK
) {
291 if (w
->right
->color
== BLACK
) {
292 w
->left
->color
= BLACK
;
294 _rotate_right(&r
, w
);
295 w
= u
->parent
->right
;
297 w
->color
= u
->parent
->color
;
298 u
->parent
->color
= BLACK
;
299 w
->right
->color
= BLACK
;
300 _rotate_left(&r
, u
->parent
);
305 rbtree_node_t
* w
= u
->parent
->left
;
306 if (w
->color
== RED
) {
308 w
->parent
->color
= RED
;
309 _rotate_right(&r
, u
->parent
);
312 if (w
->left
->color
== BLACK
&& w
->right
->color
== BLACK
) {
317 if (w
->left
->color
== BLACK
) {
318 w
->right
->color
= BLACK
;
323 w
->color
= u
->parent
->color
;
324 u
->parent
->color
= BLACK
;
325 w
->left
->color
= BLACK
;
326 _rotate_right(&r
, u
->parent
);
334 n
->parent
= n
->left
= n
->right
= NULL
;
339 void node_call(rbtree_node_t
* n
, rbtree_call_fn_t fn
)
344 node_call(n
->left
, fn
);
345 fn(RBTREE_NODE_DATA(n
));
346 node_call(n
->right
, fn
);
349 void rbtree_call(const rbtree_t
* t
, rbtree_call_fn_t fn
)
351 node_call(t
->root
, fn
);
356 * Prune off a branch of the tree.
358 static void _node_prune(rbtree_node_t
* n
)
363 _node_prune(n
->left
);
364 _node_prune(n
->right
);
368 void rbtree_clear(rbtree_t
* t
)
373 _node_prune(t
->root
);