1 /*
2 * rb.c
3 * (C)2000-2011 by Marc Huber <Marc.Huber@web.de>
4 *
5 * The RB routines are quite heavily based on sample code published in:
6 *
7 * Introduction to Algorithms
8 * Chapter 14: Red-Black Trees
9 * Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
10 * ISBN 0-262-0314108 (MIT Press)
11 * ISBN 0-07-013143-0 (McGraw-Hill)
12 *
13 *
14 * $Id: rb.c,v 1.30 2019/03/17 08:57:45 marc Exp marc $
15 *
16 */
17
18 #include "misc/sysconf.h"
19
20 static const char rcsid[] __attribute__ ((used)) = "$Id: rb.c,v 1.30 2019/03/17 08:57:45 marc Exp marc $";
21
22 #include <stdio.h>
23 #include <sys/types.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include "misc/memops.h"
27 #include "misc/rb.h"
28 #define BLACK 0
29 #define RED 1
30
31 struct rb_node {
32 void *payload;
33 rb_node_t *left;
34 rb_node_t *right;
35 rb_node_t *prev;
36 rb_node_t *next;
37 rb_node_t *parent;
38 u_int color:1;
39 };
40
41 struct rb_nodearray {
42 #define RB_ARRSIZE 1024
43 rb_node_t array[RB_ARRSIZE];
44 struct rb_nodearray *next;
45 };
46
47 struct rb_tree {
48 int count;
49 rb_node_t *root;
50 rb_node_t *first;
51 int (*compare) (const void *, const void *);
52 void (*free) (void *);
53 };
54
55 static rb_node_t *rb_nil = NULL;
56 static int rb_tree_count = 0;
57 static struct rb_nodearray *rb_nodes = NULL;
58 static rb_node_t *nextfree = NULL;
59
rb_alloc(void)60 static rb_node_t *rb_alloc(void)
61 {
62 rb_node_t *n;
63 #ifdef DEBUG_RB
64 rb_count++;
65 #endif
66 if (!nextfree) {
67 struct rb_nodearray *a = Xcalloc(1, sizeof(struct rb_nodearray));
68 int i;
69 a->next = rb_nodes;
70 rb_nodes = a;
71 for (i = 0; i < RB_ARRSIZE - 1; i++)
72 a->array[i].next = &a->array[i + 1];
73 nextfree = &a->array[0];
74 }
75 n = nextfree;
76 nextfree = nextfree->next;
77 n->left = rb_nil;
78 n->right = rb_nil;
79 n->parent = rb_nil;
80 n->prev = rb_nil;
81 n->next = rb_nil;
82 #ifdef DEBUG_RB
83 fprintf(stderr, "rb_alloc: %p (%d in use)\n", n, rb_count);
84 #endif
85 return n;
86 }
87
rb_free(rb_node_t * n)88 static void rb_free(rb_node_t * n)
89 {
90 #ifdef DEBUG_RB
91 rb_count--;
92 fprintf(stderr, "rb_free: %p (%d in use)\n", n, rb_count);
93 #endif
94 memset(n, 0, sizeof(rb_node_t));
95 n->next = nextfree;
96 nextfree = n;
97 }
98
tree_minimum(rb_node_t * x)99 static rb_node_t *tree_minimum(rb_node_t * x)
100 {
101 while (x->left != rb_nil)
102 x = x->left;
103 return x;
104 }
105
tree_maximum(rb_node_t * x)106 static rb_node_t *tree_maximum(rb_node_t * x)
107 {
108 while (x->right != rb_nil)
109 x = x->right;
110 return x;
111 }
112
tree_successor(rb_node_t * x)113 static rb_node_t *tree_successor(rb_node_t * x)
114 {
115 rb_node_t *y;
116
117 if (x->right != rb_nil)
118 return tree_minimum(x->right);
119 y = x->parent;
120 while (y != rb_nil && x == y->right) {
121 x = y;
122 y = y->parent;
123 }
124 return y;
125 }
126
tree_predecessor(rb_node_t * x)127 static rb_node_t *tree_predecessor(rb_node_t * x)
128 {
129 rb_node_t *y;
130
131 if (x->left != rb_nil)
132 return tree_maximum(x->left);
133 y = x->parent;
134 while (y != rb_nil && x == y->left) {
135 x = y;
136 y = y->parent;
137 }
138 return y;
139 }
140
left_rotate(rb_tree_t * T,rb_node_t * x)141 static void left_rotate(rb_tree_t * T, rb_node_t * x)
142 {
143 rb_node_t *y;
144
145 y = x->right;
146 x->right = y->left;
147 if (y->left != rb_nil)
148 y->left->parent = x;
149 y->parent = x->parent;
150 if (x->parent == rb_nil)
151 T->root = y;
152 else {
153 if (x == x->parent->left)
154 x->parent->left = y;
155 else
156 x->parent->right = y;
157 }
158 y->left = x;
159 x->parent = y;
160 }
161
right_rotate(rb_tree_t * T,rb_node_t * x)162 static void right_rotate(rb_tree_t * T, rb_node_t * x)
163 {
164 rb_node_t *y;
165
166 y = x->left;
167 x->left = y->right;
168 if (y->right != rb_nil)
169 y->right->parent = x;
170 y->parent = x->parent;
171 if (x->parent == rb_nil)
172 T->root = y;
173 else {
174 if (x == x->parent->right)
175 x->parent->right = y;
176 else
177 x->parent->left = y;
178 }
179 y->right = x;
180 x->parent = y;
181 }
182
tree_insert(rb_tree_t * T,rb_node_t * z)183 static int tree_insert(rb_tree_t * T, rb_node_t * z)
184 {
185 rb_node_t *x, *y;
186 y = rb_nil;
187 x = T->root;
188 while (x != rb_nil) {
189 y = x;
190 if (T->compare(z->payload, x->payload) < 0)
191 x = x->left;
192 else
193 x = x->right;
194 }
195 z->parent = y;
196 if (y == rb_nil)
197 T->root = z;
198 else {
199 int i = T->compare(z->payload, y->payload);
200 if (i < 0)
201 y->left = z;
202 else if (i > 0)
203 y->right = z;
204 else {
205 return 0; /* Duplicate! */
206 #ifdef DEBUG_RB
207 fprintf(stderr, "dupe! %p\n", z->payload);
208 #endif
209 }
210 }
211 z->prev = tree_predecessor(z);
212 if (z->prev != rb_nil) {
213 z->next = z->prev->next;
214 z->prev->next = z;
215 if (z->next != rb_nil)
216 z->next->prev = z;
217 } else {
218 T->first = z;
219 z->next = tree_successor(z);
220 if (z->next != rb_nil)
221 z->next->prev = z;
222 }
223 T->count++;
224 return -1;
225 }
226
RB_tree_new(int (* compare)(const void *,const void *),void (* freenode)(void *))227 rb_tree_t *RB_tree_new(int (*compare) (const void *, const void *), void (*freenode) (void *))
228 {
229 rb_tree_t *T = Xcalloc(1, sizeof(rb_tree_t));
230 #ifdef DEBUG_RB
231 fprintf(stderr, "RB_tree_new = %p\n", T);
232 #endif
233 if (!rb_nil) {
234 rb_nil = rb_alloc();
235 #ifdef DEBUG_RB
236 fprintf(stderr, "rb_nil = %p\n", rb_nil);
237 #endif
238 rb_nil->color = BLACK;
239 rb_nil->payload = NULL;
240 }
241 rb_tree_count++;
242
243 if (compare)
244 T->compare = compare;
245 else
246 T->compare = (int (*)(const void *, const void *)) strcmp;
247 T->free = freenode;
248 T->root = T->first = rb_nil;
249 return T;
250 }
251
rb_insert(rb_tree_t * T,rb_node_t * x)252 static int rb_insert(rb_tree_t * T, rb_node_t * x)
253 {
254 rb_node_t *y;
255
256 if (!tree_insert(T, x))
257 return 0;
258
259 x->color = RED;
260 while (x != T->root && x->parent->color == RED) {
261 if (x->parent == x->parent->parent->left) {
262 y = x->parent->parent->right;
263 if (y->color == RED) {
264 x->parent->color = BLACK;
265 y->color = BLACK;
266 x->parent->parent->color = RED;
267 x = x->parent->parent;
268 } else {
269 if (x == x->parent->right) {
270 x = x->parent;
271 left_rotate(T, x);
272 }
273 x->parent->color = BLACK;
274 x->parent->parent->color = RED;
275 right_rotate(T, x->parent->parent);
276 }
277 } else {
278 y = x->parent->parent->left;
279 if (y->color == RED) {
280 x->parent->color = BLACK;
281 y->color = BLACK;
282 x->parent->parent->color = RED;
283 x = x->parent->parent;
284 } else {
285 if (x == x->parent->left) {
286 x = x->parent;
287 right_rotate(T, x);
288 }
289 x->parent->color = BLACK;
290 x->parent->parent->color = RED;
291 left_rotate(T, x->parent->parent);
292 }
293 }
294 }
295 T->root->color = BLACK;
296 return -1;
297 }
298
RB_insert(rb_tree_t * T,void * payload)299 rb_node_t *RB_insert(rb_tree_t * T, void *payload)
300 {
301 rb_node_t *x = rb_alloc();
302 #ifdef DEBUG_RB
303 fprintf(stderr, "RB_insert(%p, %p)\n", T, x);
304 #endif
305 x->payload = payload;
306 if (!rb_insert(T, x)) {
307 rb_free(x);
308 return NULL;
309 }
310 return x;
311 }
312
rb_delete_fixup(rb_tree_t * T,rb_node_t * x)313 static void rb_delete_fixup(rb_tree_t * T, rb_node_t * x)
314 {
315 while (x != T->root && x->color == BLACK) {
316 if (x == x->parent->left) {
317 rb_node_t *w;
318 w = x->parent->right;
319 if (w->color == RED) {
320 w->color = BLACK;
321 x->parent->color = RED;
322 left_rotate(T, x->parent);
323 w = x->parent->right;
324 }
325 if (w->left->color == BLACK && w->right->color == BLACK) {
326 w->color = RED;
327 x = x->parent;
328 } else {
329 if (w->right->color == BLACK) {
330 w->left->color = BLACK;
331 w->color = RED;
332 right_rotate(T, w);
333 w = x->parent->right;
334 }
335 w->color = x->parent->color;
336 x->parent->color = BLACK;
337 w->right->color = BLACK;
338 left_rotate(T, x->parent);
339 x = T->root;
340 }
341 } else {
342 rb_node_t *w;
343 w = x->parent->left;
344 if (w->color == RED) {
345 w->color = BLACK;
346 x->parent->color = RED;
347 right_rotate(T, x->parent);
348 w = x->parent->left;
349 }
350 if (w->right->color == BLACK && w->left->color == BLACK) {
351 w->color = RED;
352 x = x->parent;
353 } else {
354 if (w->left->color == BLACK) {
355 w->right->color = BLACK;
356 w->color = RED;
357 left_rotate(T, w);
358 w = x->parent->left;
359 }
360 w->color = x->parent->color;
361 x->parent->color = BLACK;
362 w->left->color = BLACK;
363 right_rotate(T, x->parent);
364 x = T->root;
365 }
366 }
367 }
368 x->color = BLACK;
369 }
370
RB_delete(rb_tree_t * T,rb_node_t * z)371 void RB_delete(rb_tree_t * T, rb_node_t * z)
372 {
373 rb_node_t *x, *y;
374
375 #ifdef DEBUG_RB
376 fprintf(stderr, "RB_delete(%p, %p)\n", T, z);
377 #endif
378
379 if (z->left == rb_nil || z->right == rb_nil)
380 y = z;
381 else
382 y = z->prev;
383
384 if (y->left != rb_nil)
385 x = y->left;
386 else
387 x = y->right;
388 x->parent = y->parent;
389 if (y->parent == rb_nil)
390 T->root = x;
391 else {
392 if (y == y->parent->left)
393 y->parent->left = x;
394 else
395 y->parent->right = x;
396 }
397 if (y != z) {
398 if (T->free)
399 T->free(z->payload);
400 z->payload = y->payload;
401 y->payload = NULL;
402 }
403 if (y->color == BLACK)
404 rb_delete_fixup(T, x);
405
406 if (y->next != rb_nil)
407 y->next->prev = y->prev;
408 if (y->prev != rb_nil)
409 y->prev->next = y->next;
410 else
411 T->first = y->next;
412 if (T->free && y->payload)
413 T->free(y->payload);
414 rb_free(y);
415 T->count--;
416 }
417
RB_search(rb_tree_t * T,void * payload)418 rb_node_t *RB_search(rb_tree_t * T, void *payload)
419 {
420 rb_node_t *x = T->root;
421 int count = 0;
422
423 while (x != rb_nil) {
424 int i = T->compare(payload, x->payload);
425 #if 1 //#ifdef DEBUG_RB
426 if (count++ > T->count) {
427 fprintf(stderr, "RB_search: possible loop detected, returning NULL\n");
428 return NULL;
429 }
430 #endif
431
432 if (i < 0)
433 x = x->left;
434 else if (i > 0)
435 x = x->right;
436 else
437 return x;
438 }
439 return NULL;
440 }
441
RB_first(rb_tree_t * T)442 rb_node_t *RB_first(rb_tree_t * T)
443 {
444 if (T && T->first != rb_nil)
445 return T->first;
446 return NULL;
447 }
448
RB_next(rb_node_t * z)449 rb_node_t *RB_next(rb_node_t * z)
450 {
451 if (z && z->next != rb_nil)
452 return z->next;
453 return NULL;
454 }
455
rb_tree_delete(rb_tree_t * T,rb_node_t * z)456 static void rb_tree_delete(rb_tree_t * T, rb_node_t * z)
457 {
458 #ifdef DEBUG_RB
459 fprintf(stderr, "# rb_tree_delete(%p, %p)\n", T, z);
460 #endif
461 if (z->left != rb_nil)
462 rb_tree_delete(T, z->left);
463 if (z->right != rb_nil)
464 rb_tree_delete(T, z->right);
465 if (T->free && z->payload)
466 T->free(z->payload);
467 rb_free(z);
468 }
469
RB_tree_delete(rb_tree_t * T)470 void RB_tree_delete(rb_tree_t * T)
471 {
472 #ifdef DEBUG_RB
473 fprintf(stderr, "RB_tree_delete(%p)\n", T);
474 #endif
475 if (T) {
476 if (T->root != rb_nil)
477 rb_tree_delete(T, T->root);
478 free(T);
479 if (!--rb_tree_count) {
480 rb_nil = NULL;
481 while (rb_nodes) {
482 struct rb_nodearray *a = rb_nodes->next;
483 free(rb_nodes);
484 rb_nodes = a;
485 }
486 }
487 }
488 }
489
RB_empty(rb_tree_t * T)490 int RB_empty(rb_tree_t * T)
491 {
492 return T == NULL || T->count == 0;
493 }
494
RB_count(rb_tree_t * T)495 int RB_count(rb_tree_t * T)
496 {
497 return T ? T->count : 0;
498 }
499
RB_search_and_delete(rb_tree_t * t,void * q)500 void RB_search_and_delete(rb_tree_t * t, void *q)
501 {
502 rb_node_t *rbn;
503 if ((rbn = RB_search(t, q)))
504 RB_delete(t, rbn);
505 }
506
RB_lookup(rb_tree_t * t,void * q)507 void *RB_lookup(rb_tree_t * t, void *q)
508 {
509 rb_node_t *rbn = RB_search(t, q);
510 if (rbn)
511 return rbn->payload;
512 return NULL;
513 }
514
RB_payload_get(rb_node_t * rbn)515 void *RB_payload_get(rb_node_t * rbn)
516 {
517 return rbn->payload;
518 }
519
RB_payload_unlink(rb_node_t * rbn)520 void RB_payload_unlink(rb_node_t * rbn)
521 {
522 rbn->payload = NULL;
523 }
524