su  1.12.11devel
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
26 
27 #define RBTREE_H
28 
52 #if DOCUMENTATION_ONLY
53 
54 typedef 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) \
65 su_inline \
66 void 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 } \
83 extern 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) \
93 su_inline \
94 void 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 } \
111 extern int const prefix##_dummy
112 
113 #define RBTREE_BALANCE_INSERT1(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK) \
114 su_inline \
115 void prefix ## _balance_insert(Type **top, Type *node) \
116 { \
117  Type *dad, *uncle, *granddad; \
118 } \
119 extern 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) \
130 su_inline \
131 void 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 } \
177 extern 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) \
182 su_inline \
183 void 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 } \
255 extern int const prefix##_dummy
256 
257 #if DOCUMENTATION_ONLY
258 
269 int 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) \
276 SCOPE \
277 int 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 } \
334 extern int const prefix##_dummy
335 
336 #if DOCUMENTATION_ONLY
337 
344 int 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) \
352 SCOPE \
353 int 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 } \
382 extern int const prefix##_dummy
383 
384 #if DOCUMENTATION_ONLY
385 
390 void 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) \
396 SCOPE \
397 void 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 } \
456 extern int const prefix##_dummy
457 
458 #if DOCUMENTATION_ONLY
459 
465 Type *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) \
470 SCOPE 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 } \
485 extern int const prefix##_dummy
486 
487 #if DOCUMENTATION_ONLY
488 
494 Type *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 } \
514 extern int const prefix##_dummy
515 
516 #if DOCUMENTATION_ONLY
517 
523 Type *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) \
528 SCOPE Type *prefix##_first(Type const *node) \
529 { \
530  while (node && left(node)) \
531  node = left(node); \
532  \
533  return (Type *)node; \
534 } \
535 extern int const prefix##_dummy
536 
537 #if DOCUMENTATION_ONLY
538 
544 Type *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) \
549 SCOPE Type *prefix##_last(Type const *node) \
550 { \
551  while (node && right(node)) \
552  node = right(node); \
553  \
554  return (Type *)node; \
555 } \
556 extern int const prefix##_dummy
557 
558 #if DOCUMENTATION_ONLY
559 
565 int 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) \
570 SCOPE 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 } \
585 extern 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) */
Type * rbtree_first(Type const *node)
Return first node in the tree to which node belongs to.
Type * rbtree_succ(Type const *node)
Return inorder successor of node node.
int rbtree_height(Type const *node)
Return height of the tree below node.
void rbtree_remove(Type **tree, Type *node)
Remove a node from the tree.
int rbtree_append(Type **tree, Type *node)
Append a node into the tree.
Type * rbtree_last(Type const *node)
Return last node in the tree to which node belongs to.
int rbtree_insert(Type **tree, Type *node, Type **return_old)
Insert a node into the tree.
struct node Type
Type used for rbtree nodes.
Definition: rbtree.h:54
Type * rbtree_prec(Type const *node)
Return inorder precedessor of node node.

Sofia-SIP 1.12.11devel - Copyright (C) 2006 Nokia Corporation. All rights reserved. Licensed under the terms of the GNU Lesser General Public License.