su 1.13.18
Loading...
Searching...
No Matches
rbtree.h
Go to the documentation of this file.
1/*
2 * This file is part of the Sofia-SIP package
3 *
4 * Copyright (C) 2005 Nokia Corporation.
5 *
6 * Contact: Pekka Pessi <pekka.pessi@nokia-email.address.hidden>
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public License
10 * as published by the Free Software Foundation; either version 2.1 of
11 * the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
21 * 02110-1301 USA
22 *
23 */
24
25#ifndef RBTREE_H
27#define RBTREE_H
28
51
52#if DOCUMENTATION_ONLY
54typedef struct node Type;
55#endif
56
57 /* x c
58 * / \ / \
59 * Convert a c into x d
60 * / \ / \
61 * b d a b
62 */
63
64#define RBTREE_LEFT_ROTATE(prefix, Type, left, right, parent) \
65su_inline \
66void prefix ## _left_rotate(Type **top, Type *x) \
67{ \
68 Type *c = right(x), *dad = parent(x); assert(c); \
69 \
70 if ((right(x) = left(c))) \
71 parent(right(x)) = x; \
72 \
73 if (!(parent(c) = dad)) \
74 *top = c; \
75 else if (left(dad) == x) \
76 left(dad) = c; \
77 else \
78 assert(right(dad) == x), right(dad) = c; \
79 \
80 left(c) = x; \
81 parent(x) = c; \
82} \
83extern int const prefix##_dummy
84
85 /* x c
86 * / \ / \
87 * Convert c f into a x
88 * / \ / \
89 * a d d f
90 */
91
92#define RBTREE_RIGHT_ROTATE(prefix, Type, left, right, parent) \
93su_inline \
94void prefix ## _right_rotate(Type **top, Type *x) \
95{ \
96 Type *c = left(x), *dad = parent(x); assert(c); \
97 \
98 if ((left(x) = right(c))) \
99 parent(left(x)) = x; \
100 \
101 if (!(parent(c) = dad)) \
102 *top = c; \
103 else if (right(dad) == x) \
104 right(dad) = c; \
105 else \
106 assert(left(dad) == x), left(dad) = c; \
107 \
108 right(c) = x; \
109 parent(x) = c; \
110} \
111extern int const prefix##_dummy
112
113#define RBTREE_BALANCE_INSERT1(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK) \
114su_inline \
115void prefix ## _balance_insert(Type **top, Type *node) \
116{ \
117 Type *dad, *uncle, *granddad; \
118} \
119extern int const prefix##_dummy
120
121
122/* Balance Red-Black binary tree after inserting node @a n.
123 *
124 * The function red_black_balance_insert() balances a red-black tree after
125 * insertion.
126 *
127 * RED(node) - set node as red
128 */
129#define RBTREE_BALANCE_INSERT(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK) \
130su_inline \
131void prefix ## _balance_insert(Type **top, Type *node) \
132{ \
133 Type *dad, *uncle, *granddad; \
134 \
135 SET_RED(node); \
136 \
137 for (dad = parent(node); node != *top && IS_RED(dad); dad = parent(node)) { \
138 /* Repeat until we are parent or we have a black dad */ \
139 granddad = parent(dad); assert(granddad); \
140 if (dad == left(granddad)) { \
141 uncle = right(granddad); \
142 if (IS_RED(uncle)) { \
143 SET_BLACK(dad); SET_BLACK(uncle); SET_RED(granddad); \
144 node = granddad; \
145 } else { \
146 if (node == right(dad)) { \
147 prefix##_left_rotate(top, node = dad); \
148 dad = parent(node); assert(dad); \
149 granddad = parent(dad); assert(granddad); \
150 } \
151 SET_BLACK(dad); \
152 SET_RED(granddad); \
153 prefix##_right_rotate(top, granddad); \
154 } \
155 } else { assert(dad == right(granddad)); \
156 uncle = left(granddad); \
157 if (IS_RED(uncle)) { \
158 SET_BLACK(dad); SET_BLACK(uncle); SET_RED(granddad); \
159 node = granddad; \
160 } else { \
161 if (node == left(dad)) { \
162 prefix##_right_rotate(top, node = dad); \
163 dad = parent(node); assert(dad); \
164 granddad = parent(dad); assert(granddad); \
165 } \
166 SET_BLACK(dad); \
167 SET_RED(granddad); \
168 prefix##_left_rotate(top, granddad); \
169 } \
170 } \
171 } \
172 \
173 assert(*top); \
174 \
175 SET_BLACK((*top)); \
176} \
177extern int const prefix##_dummy
178
179#define RBTREE_BALANCE_DELETE(prefix, Type, left, right, parent, \
180 IS_RED, SET_RED, IS_BLACK, SET_BLACK, \
181 COPY_COLOR) \
182su_inline \
183void prefix##_balance_delete(Type **top, Type *node) \
184{ \
185 Type *dad, *brother; \
186 \
187 for (dad = parent(node); node != *top && IS_RED(dad); dad = parent(node)) { \
188 if (node == left(dad)) { \
189 brother = right(dad); \
190 \
191 if (!brother) { \
192 node = dad; \
193 continue; \
194 } \
195 \
196 assert(IS_BLACK(brother)); \
197 \
198 if (IS_BLACK(left(brother)) && IS_BLACK(right(brother))) { \
199 SET_RED(brother); \
200 node = dad; \
201 continue; \
202 } \
203 \
204 if (IS_BLACK(right(brother))) { \
205 SET_RED(brother); \
206 SET_BLACK(left(brother)); \
207 prefix##_right_rotate(top, brother); \
208 brother = right(dad); \
209 } \
210 \
211 COPY_COLOR(brother, dad); \
212 SET_BLACK(dad); \
213 if (right(brother)) \
214 SET_BLACK(right(brother)); \
215 prefix##_left_rotate(top, dad); \
216 node = *top; \
217 break; \
218 } else { \
219 assert(node == right(dad)); \
220 \
221 brother = left(dad); \
222 \
223 if (!brother) { \
224 node = dad; \
225 continue; \
226 } \
227 \
228 assert(IS_BLACK(brother)); \
229 \
230 if (IS_BLACK(left(brother)) && IS_BLACK(right(brother))) { \
231 SET_RED(brother); \
232 node = dad; \
233 continue; \
234 } \
235 \
236 if (IS_BLACK(left(brother))) { \
237 SET_BLACK(right(brother)); \
238 SET_RED(brother); \
239 prefix##_left_rotate(top, brother); \
240 brother = left(dad); \
241 } \
242 \
243 COPY_COLOR(brother, parent(node)); \
244 SET_BLACK(parent(node)); \
245 if (left(brother)) \
246 SET_BLACK(left(brother)); \
247 prefix##_right_rotate(top, dad); \
248 node = *top; \
249 break; \
250 } \
251 } \
252 \
253 SET_BLACK(node); \
254} \
255extern int const prefix##_dummy
256
257#if DOCUMENTATION_ONLY
269int rbtree_insert(Type **tree, Type *node, Type **return_old);
270#endif
271
272/* Insert node into tree. */
273#define RBTREE_INSERT(SCOPE, prefix, Type, left, right, parent, \
274 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
275 CMP, REMOVE, INSERT) \
276SCOPE \
277int prefix ## _insert(Type **const tree, \
278 Type * const node, \
279 Type **return_old) \
280{ \
281 Type *old, *dad, **slot; \
282 \
283 if (tree == NULL || node == NULL) return -1; \
284 \
285 for (slot = tree, old = *slot, dad = NULL; old; old = *slot) { \
286 int result = CMP(node, old); \
287 if (result < 0) \
288 dad = old, slot = &(left(old)); \
289 else if (result > 0) \
290 dad = old, slot = &(right(old)); \
291 else \
292 break; \
293 } \
294 \
295 if (old == node) \
296 old = NULL; \
297 else if (old) { \
298 if (!return_old) return -1; \
299 \
300 if ((left(node) = left(old))) \
301 parent(left(node)) = node; \
302 if ((right(node) = right(old))) \
303 parent(right(node)) = node; \
304 \
305 if (!(parent(node) = parent(old))) \
306 *tree = node; \
307 else if (left(parent(node)) == old) \
308 left(parent(node)) = node; \
309 else assert(right(parent(node)) == old), \
310 right(parent(node)) = node; \
311 \
312 COPY_COLOR(node, old); \
313 \
314 REMOVE(old); \
315 \
316 } else { \
317 *slot = node; \
318 parent(node) = dad; \
319 \
320 if (tree != slot) { \
321 prefix##_balance_insert(tree, node); \
322 } else { \
323 SET_BLACK(node); \
324 } \
325 } \
326 \
327 INSERT(node); \
328 \
329 if (return_old) \
330 *return_old = old; \
331 \
332 return 0; \
333} \
334extern int const prefix##_dummy
335
336#if DOCUMENTATION_ONLY
344int rbtree_append(Type ** tree,
345 Type * node);
346#endif
347
348/* Define function appending a node into the tree */
349#define RBTREE_APPEND(SCOPE, prefix, Type, left, right, parent, \
350 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
351 CMP, REMOVE, INSERT) \
352SCOPE \
353int prefix ## _append(Type **const tree, \
354 Type * const node) \
355{ \
356 Type *old, *dad, **slot; \
357 \
358 if (tree == NULL || node == NULL) return -1; \
359 \
360 for (slot = tree, old = *slot, dad = NULL; old; old = *slot) { \
361 if (old == node) \
362 return 0; \
363 if (CMP(node, old) < 0) \
364 dad = old, slot = &(left(old)); \
365 else \
366 dad = old, slot = &(right(old)); \
367 } \
368 \
369 *slot = node; \
370 parent(node) = dad; \
371 \
372 if (tree != slot) { \
373 prefix##_balance_insert(tree, node); \
374 } else { \
375 SET_BLACK(node); \
376 } \
377 \
378 INSERT(node); \
379 \
380 return 0; \
381} \
382extern int const prefix##_dummy
383
384#if DOCUMENTATION_ONLY
390void rbtree_remove(Type **tree, Type *node);
391#endif
392
393#define RBTREE_REMOVE(SCOPE, prefix, Type, left, right, parent, \
394 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
395 REMOVE, INSERT) \
396SCOPE \
397void prefix##_remove(Type **top, Type *node) \
398{ \
399 Type *kid, *dad; \
400 int need_to_balance; \
401 \
402 if (top == NULL || node == NULL) \
403 return; \
404 \
405 /* Make sure that node is in tree */ \
406 for (dad = node; dad; dad = parent(dad)) \
407 if (dad == *top) \
408 break; \
409 \
410 if (!dad) return; \
411 \
412 /* Find a successor node with a free branch */ \
413 if (!left(node) || !right(node)) \
414 dad = node; \
415 else for (dad = right(node); left(dad); dad = left(dad)) \
416 ; \
417 /* Dad has a free branch => kid is dad's only child */ \
418 kid = left(dad) ? left(dad) : right(dad); \
419 \
420 /* Remove dad from tree */ \
421 if (!(parent(dad))) \
422 *top = kid; \
423 else if (left(parent(dad)) == dad) \
424 left(parent(dad)) = kid; \
425 else assert(right(parent(dad)) == dad), \
426 right(parent(dad)) = kid; \
427 if (kid) \
428 parent(kid) = parent(dad); \
429 \
430 need_to_balance = kid && IS_BLACK(dad); \
431 \
432 /* Put dad in place of node */ \
433 if (node != dad) { \
434 if (!(parent(dad) = parent(node))) \
435 *top = dad; \
436 else if (left(parent(dad)) == node) \
437 left(parent(dad)) = dad; \
438 else assert(right(parent(dad)) == node), \
439 right(parent(dad)) = dad; \
440 \
441 COPY_COLOR(dad, node); \
442 \
443 if ((left(dad) = left(node))) \
444 parent(left(dad)) = dad; \
445 \
446 if ((right(dad) = right(node))) \
447 parent(right(dad)) = dad; \
448 } \
449 \
450 REMOVE(node); \
451 SET_RED(node); \
452 \
453 if (need_to_balance) \
454 prefix##_balance_delete(top, kid); \
455} \
456extern int const prefix##_dummy
457
458#if DOCUMENTATION_ONLY
465Type *rbtree_succ(Type const *node);
466#endif
467
468/* Define function returning inorder successor of node @a node. */
469#define RBTREE_SUCC(SCOPE, prefix, Type, left, right, parent) \
470SCOPE Type *prefix##_succ(Type const *node) \
471{ \
472 Type const *dad; \
473 \
474 if (right(node)) { \
475 for (node = right(node); left(node); node = left(node)) \
476 ; \
477 return (Type *)node; \
478 } \
479 \
480 for (dad = parent(node); dad && node == right(dad); dad = parent(node)) \
481 node = dad; \
482 \
483 return (Type *)dad; \
484} \
485extern int const prefix##_dummy
486
487#if DOCUMENTATION_ONLY
494Type *rbtree_prec(Type const *node);
495#endif
496
497/* Define function returning inorder precedessor of node @a node. */
498#define RBTREE_PREC(SCOPE, prefix, Type, left, right, parent) \
499 SCOPE Type *prefix##_prec(Type const *node) \
500{ \
501 Type const *dad; \
502 \
503 if (left(node)) { \
504 for (node = left(node); right(node); node = right(node)) \
505 ; \
506 return (Type *)node; \
507 } \
508 \
509 for (dad = parent(node); dad && node == left(dad); dad = parent(node)) \
510 node = dad; \
511 \
512 return (Type *)dad; \
513} \
514extern int const prefix##_dummy
515
516#if DOCUMENTATION_ONLY
523Type *rbtree_first(Type const *node);
524#endif
525
526/* Define function returning first node in tree @a node. */
527#define RBTREE_FIRST(SCOPE, prefix, Type, left, right, parent) \
528SCOPE Type *prefix##_first(Type const *node) \
529{ \
530 while (node && left(node)) \
531 node = left(node); \
532 \
533 return (Type *)node; \
534} \
535extern int const prefix##_dummy
536
537#if DOCUMENTATION_ONLY
544Type *rbtree_last(Type const *node);
545#endif
546
547/* Define function returning last node in tree @a node. */
548#define RBTREE_LAST(SCOPE, prefix, Type, left, right, parent) \
549SCOPE Type *prefix##_last(Type const *node) \
550{ \
551 while (node && right(node)) \
552 node = right(node); \
553 \
554 return (Type *)node; \
555} \
556extern int const prefix##_dummy
557
558#if DOCUMENTATION_ONLY
565int rbtree_height(Type const *node);
566#endif
567
568/* Define function returning height of the tree from the @a node. */
569#define RBTREE_HEIGHT(SCOPE, prefix, Type, getleft, getright, getparent) \
570SCOPE int prefix##_height(Type const *node) \
571{ \
572 int left, right; \
573 \
574 if (!node) \
575 return 0; \
576 \
577 left = getleft(node) ? prefix##_height(getleft(node)) : 0; \
578 right = getright(node) ? prefix##_height(getright(node)) : 0; \
579 \
580 if (left > right) \
581 return left + 1; \
582 else \
583 return right + 1; \
584} \
585extern int const prefix##_dummy
586
598#define RBTREE_PROTOS(SCOPE, prefix, Type) \
599 SCOPE int prefix ## _insert(Type **, Type *, Type **return_old); \
600 SCOPE int prefix ## _append(Type **, Type *); \
601 SCOPE void prefix ## _remove(Type **, Type *); \
602 SCOPE Type *prefix ## _succ(Type const *); \
603 SCOPE Type *prefix ## _prec(Type const *); \
604 SCOPE Type *prefix ## _first(Type const *); \
605 SCOPE Type *prefix ## _last(Type const *); \
606 SCOPE int prefix ## _height(Type const *)
607
647#define RBTREE_BODIES(SCOPE, prefix, Type, \
648 left, right, parent, \
649 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
650 CMP, INSERT, REMOVE) \
651 RBTREE_LEFT_ROTATE(prefix, Type, left, right, parent); \
652 RBTREE_RIGHT_ROTATE(prefix, Type, left, right, parent); \
653 RBTREE_BALANCE_INSERT(prefix, Type, left, right, parent, \
654 IS_RED, SET_RED, IS_BLACK, SET_BLACK); \
655 RBTREE_BALANCE_DELETE(prefix, Type, left, right, parent, \
656 IS_RED, SET_RED, IS_BLACK, SET_BLACK, \
657 COPY_COLOR); \
658 RBTREE_INSERT(SCOPE, prefix, Type, left, right, parent, \
659 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
660 CMP, REMOVE, INSERT); \
661 RBTREE_APPEND(SCOPE, prefix, Type, left, right, parent, \
662 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
663 CMP, REMOVE, INSERT); \
664 RBTREE_REMOVE(SCOPE, prefix, Type, left, right, parent, \
665 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
666 REMOVE, INSERT); \
667 RBTREE_SUCC(SCOPE, prefix, Type, left, right, parent); \
668 RBTREE_PREC(SCOPE, prefix, Type, left, right, parent); \
669 RBTREE_FIRST(SCOPE, prefix, Type, left, right, parent); \
670 RBTREE_LAST(SCOPE, prefix, Type, left, right, parent); \
671 RBTREE_HEIGHT(SCOPE, prefix, Type, left, right, parent)
672
673#endif /* !define(RBTREE_H) */
rbtree_insert
int rbtree_insert(Type **tree, Type *node, Type **return_old)
Insert a node into the tree.
rbtree_succ
Type * rbtree_succ(Type const *node)
Return inorder successor of node node.
rbtree_last
Type * rbtree_last(Type const *node)
Return last node in the tree to which node belongs to.
rbtree_prec
Type * rbtree_prec(Type const *node)
Return inorder precedessor of node node.
rbtree_first
Type * rbtree_first(Type const *node)
Return first node in the tree to which node belongs to.
rbtree_height
int rbtree_height(Type const *node)
Return height of the tree below node.
rbtree_remove
void rbtree_remove(Type **tree, Type *node)
Remove a node from the tree.
rbtree_append
int rbtree_append(Type **tree, Type *node)
Append a node into the tree.
Type
struct node Type
Type used for rbtree nodes.
Definition rbtree.h:54
Sofia-SIP 1.13.18 - Copyright (C) 2006 Nokia Corporation. All rights reserved. Licensed under the terms of the GNU Lesser General Public License.