sofia-sip/rbtree.h

Go to the documentation of this file.
00001 /*
00002  * This file is part of the Sofia-SIP package
00003  *
00004  * Copyright (C) 2005 Nokia Corporation.
00005  *
00006  * Contact: Pekka Pessi <pekka.pessi@nokia-email.address.hidden>
00007  *
00008  * This library is free software; you can redistribute it and/or
00009  * modify it under the terms of the GNU Lesser General Public License
00010  * as published by the Free Software Foundation; either version 2.1 of
00011  * the License, or (at your option) any later version.
00012  *
00013  * This library is distributed in the hope that it will be useful, but
00014  * WITHOUT ANY WARRANTY; without even the implied warranty of
00015  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
00016  * Lesser General Public License for more details.
00017  *
00018  * You should have received a copy of the GNU Lesser General Public
00019  * License along with this library; if not, write to the Free Software
00020  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
00021  * 02110-1301 USA
00022  *
00023  */
00024 
00025 #ifndef RBTREE_H
00026 
00027 #define RBTREE_H 
00028 
00052 #if DOCUMENTATION_ONLY
00053 
00054 typedef struct node Type;
00055 #endif
00056 
00057   /*               x                c
00058    *              / \              / \
00059    * Convert     a   c    into    x   d
00060    *                / \          / \
00061    *               b   d        a   b
00062    */
00063 
00064 #define RBTREE_LEFT_ROTATE(prefix, Type, left, right, parent)   \
00065 static inline \
00066 void prefix ## _left_rotate(Type **top, Type *x)   \
00067 {                                                  \
00068   Type *c = right(x), *dad = parent(x); assert(c); \
00069                                                    \
00070   if ((right(x) = left(c)))                        \
00071     parent(right(x)) = x;                          \
00072                                                    \
00073   if (!(parent(c) = dad))                          \
00074     *top = c;                                      \
00075   else if (left(dad) == x)                         \
00076     left(dad) = c;                                 \
00077   else                                             \
00078     assert(right(dad) == x), right(dad) = c;       \
00079                                                    \
00080   left(c) = x;                                     \
00081   parent(x) = c;                                   \
00082 } \
00083 extern int const prefix##_dummy 
00084 
00085   /*               x                c
00086    *              / \              / \
00087    * Convert     c   f    into    a   x
00088    *            / \                  / \
00089    *           a   d                d   f
00090    */
00091 
00092 #define RBTREE_RIGHT_ROTATE(prefix, Type, left, right, parent)  \
00093 static inline \
00094 void prefix ## _right_rotate(Type **top, Type *x)       \
00095 {                                                       \
00096   Type *c = left(x), *dad = parent(x); assert(c);       \
00097                                                         \
00098   if ((left(x) = right(c)))                             \
00099     parent(left(x)) = x;                                \
00100                                                         \
00101   if (!(parent(c) = dad))                               \
00102     *top = c;                                           \
00103   else if (right(dad) == x)                             \
00104     right(dad) = c;                                     \
00105   else                                                  \
00106     assert(left(dad) == x), left(dad) = c;              \
00107                                                         \
00108   right(c) = x;                                         \
00109   parent(x) = c;                                        \
00110 } \
00111 extern int const prefix##_dummy
00112 
00113 #define RBTREE_BALANCE_INSERT1(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK)                         \
00114 static inline                                                           \
00115 void prefix ## _balance_insert(Type **top, Type *node)                  \
00116 {                                                                       \
00117   Type *dad, *uncle, *granddad;                                         \
00118 } \
00119 extern int const prefix##_dummy
00120 
00121 
00122 /* Balance Red-Black binary tree after inserting node @a n.
00123  *
00124  * The function red_black_balance_insert() balances a red-black tree after
00125  * insertion.
00126  *
00127  * RED(node) - set node as red
00128  */
00129 #define RBTREE_BALANCE_INSERT(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK)                          \
00130 static inline                                                           \
00131 void prefix ## _balance_insert(Type **top, Type *node)                  \
00132 {                                                                       \
00133   Type *dad, *uncle, *granddad;                                         \
00134                                                                         \
00135   SET_RED(node);                                                        \
00136                                                                         \
00137   for (dad = parent(node); node != *top && IS_RED(dad); dad = parent(node)) { \
00138     /* Repeat until we are parent or we have a black dad */             \
00139     granddad = parent(dad); assert(granddad);                           \
00140     if (dad == left(granddad)) {                                        \
00141       uncle = right(granddad);                                          \
00142       if (IS_RED(uncle)) {                                              \
00143         SET_BLACK(dad); SET_BLACK(uncle); SET_RED(granddad);            \
00144         node = granddad;                                                \
00145       } else {                                                          \
00146         if (node == right(dad)) {                                       \
00147           prefix##_left_rotate(top, node = dad);                        \
00148           dad = parent(node); assert(dad);                              \
00149           granddad = parent(dad); assert(granddad);                     \
00150         }                                                               \
00151         SET_BLACK(dad);                                                 \
00152         SET_RED(granddad);                                              \
00153         prefix##_right_rotate(top, granddad);                           \
00154       }                                                                 \
00155     } else { assert(dad == right(granddad));                            \
00156       uncle = left(granddad);                                           \
00157       if (IS_RED(uncle)) {                                              \
00158         SET_BLACK(dad); SET_BLACK(uncle); SET_RED(granddad);            \
00159         node = granddad;                                                \
00160       } else {                                                          \
00161         if (node == left(dad)) {                                        \
00162           prefix##_right_rotate(top, node = dad);                       \
00163           dad = parent(node); assert(dad);                              \
00164           granddad = parent(dad); assert(granddad);                     \
00165         }                                                               \
00166         SET_BLACK(dad);                                                 \
00167         SET_RED(granddad);                                              \
00168         prefix##_left_rotate(top, granddad);                            \
00169       }                                                                 \
00170     }                                                                   \
00171   }                                                                     \
00172                                                                         \
00173   assert(*top);                                                         \
00174                                                                         \
00175   SET_BLACK((*top));                                                    \
00176 } \
00177 extern int const prefix##_dummy
00178 
00179 #define RBTREE_BALANCE_DELETE(prefix, Type, left, right, parent,        \
00180                               IS_RED, SET_RED, IS_BLACK, SET_BLACK,     \
00181                               COPY_COLOR)                               \
00182 static inline                                                           \
00183 void prefix##_balance_delete(Type **top, Type *node)                    \
00184 {                                                                       \
00185   Type *dad, *brother;                                                  \
00186                                                                         \
00187   for (dad = parent(node); node != *top && IS_RED(dad); dad = parent(node)) { \
00188     if (node == left(dad)) {                                            \
00189       brother = right(dad);                                             \
00190                                                                         \
00191       if (!brother) {                                                   \
00192         node = dad;                                                     \
00193         continue;                                                       \
00194       }                                                                 \
00195                                                                         \
00196       assert(IS_BLACK(brother));                                        \
00197                                                                         \
00198       if (IS_BLACK(left(brother)) && IS_BLACK(right(brother))) {        \
00199         SET_RED(brother);                                               \
00200         node = dad;                                                     \
00201         continue;                                                       \
00202       }                                                                 \
00203                                                                         \
00204       if (IS_BLACK(right(brother))) {                                   \
00205         SET_RED(brother);                                               \
00206         SET_BLACK(left(brother));                                       \
00207         prefix##_right_rotate(top, brother);                            \
00208         brother = right(dad);                                           \
00209       }                                                                 \
00210                                                                         \
00211       COPY_COLOR(brother, dad);                                         \
00212       SET_BLACK(dad);                                                   \
00213       if (right(brother))                                               \
00214         SET_BLACK(right(brother));                                      \
00215       prefix##_left_rotate(top, dad);                                   \
00216       node = *top;                                                      \
00217       break;                                                            \
00218     } else {                                                            \
00219       assert(node == right(dad));                                       \
00220                                                                         \
00221       brother = left(dad);                                              \
00222                                                                         \
00223       if (!brother) {                                                   \
00224         node = dad;                                                     \
00225         continue;                                                       \
00226       }                                                                 \
00227                                                                         \
00228       assert(IS_BLACK(brother));                                        \
00229                                                                         \
00230       if (IS_BLACK(left(brother)) && IS_BLACK(right(brother))) {        \
00231         SET_RED(brother);                                               \
00232         node = dad;                                                     \
00233         continue;                                                       \
00234       }                                                                 \
00235                                                                         \
00236       if (IS_BLACK(left(brother))) {                                    \
00237         SET_BLACK(right(brother));                                      \
00238         SET_RED(brother);                                               \
00239         prefix##_left_rotate(top, brother);                             \
00240         brother = left(dad);                                            \
00241       }                                                                 \
00242                                                                         \
00243       COPY_COLOR(brother, parent(node));                                \
00244       SET_BLACK(parent(node));                                          \
00245       if (left(brother))                                                \
00246         SET_BLACK(left(brother));                                       \
00247       prefix##_right_rotate(top, dad);                                  \
00248       node = *top;                                                      \
00249       break;                                                            \
00250     }                                                                   \
00251   }                                                                     \
00252                                                                         \
00253   SET_BLACK(node);                                                      \
00254 }  \
00255 extern int const prefix##_dummy
00256 
00257 #if DOCUMENTATION_ONLY
00258 
00269 int rbtree_insert(Type **tree, Type *node, Type **return_old);
00270 #endif
00271 
00272 /* Insert node into tree. */
00273 #define RBTREE_INSERT(SCOPE, prefix, Type, left, right, parent,         \
00274                       IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
00275                       CMP, REMOVE, INSERT)                              \
00276 SCOPE                                                                   \
00277 int prefix ## _insert(Type **const tree,                                \
00278                       Type * const node,                                \
00279                       Type **return_old)                                \
00280 {                                                                       \
00281   Type *old, *dad, **slot;                                              \
00282                                                                         \
00283   if (tree == NULL || node == NULL) return -1;                          \
00284                                                                         \
00285   for (slot = tree, old = *slot, dad = NULL; old; old = *slot) {        \
00286     int result = CMP(node, old);                                        \
00287     if (result < 0)                                                     \
00288       dad = old, slot = &(left(old));                                   \
00289     else if (result > 0)                                                \
00290       dad = old, slot = &(right(old));                                  \
00291     else                                                                \
00292       break;                                                            \
00293   }                                                                     \
00294                                                                         \
00295   if (old == node)                                                      \
00296     old = NULL;                                                         \
00297   else if (old) {                                                       \
00298     if (!return_old) return -1;                                         \
00299                                                                         \
00300     if ((left(node) = left(old)))                                       \
00301       parent(left(node)) = node;                                        \
00302     if ((right(node) = right(old)))                                     \
00303       parent(right(node)) = node;                                       \
00304                                                                         \
00305     if (!(parent(node) = parent(old)))                                  \
00306       *tree = node;                                                     \
00307     else if (left(parent(node)) == old)                                 \
00308       left(parent(node)) = node;                                        \
00309     else assert(right(parent(node)) == old),                            \
00310       right(parent(node)) = node;                                       \
00311                                                                         \
00312     COPY_COLOR(node, old);                                              \
00313                                                                         \
00314     REMOVE(old);                                                        \
00315                                                                         \
00316   } else {                                                              \
00317     *slot = node;                                                       \
00318     parent(node) = dad;                                                 \
00319                                                                         \
00320     if (tree != slot) {                                                 \
00321       prefix##_balance_insert(tree, node);                              \
00322     } else {                                                            \
00323       SET_BLACK(node);                                                  \
00324     }                                                                   \
00325   }                                                                     \
00326                                                                         \
00327   INSERT(node);                                                         \
00328                                                                         \
00329   if (return_old)                                                       \
00330     *return_old = old;                                                  \
00331                                                                         \
00332   return 0;                                                             \
00333 }  \
00334 extern int const prefix##_dummy
00335 
00336 #if DOCUMENTATION_ONLY
00337 
00344 int rbtree_append(Type ** tree,
00345                   Type *  node);
00346 #endif
00347 
00348 /* Define function appending a node into the tree */
00349 #define RBTREE_APPEND(SCOPE, prefix, Type, left, right, parent,         \
00350                       IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
00351                       CMP, REMOVE, INSERT)                              \
00352 SCOPE                                                                   \
00353 int prefix ## _append(Type **const tree,                                \
00354                       Type * const node)                                \
00355 {                                                                       \
00356   Type *old, *dad, **slot;                                              \
00357                                                                         \
00358   if (tree == NULL || node == NULL) return -1;                          \
00359                                                                         \
00360   for (slot = tree, old = *slot, dad = NULL; old; old = *slot) {        \
00361     if (old == node)                                                    \
00362       return 0;                                                         \
00363     if (CMP(node, old) < 0)                                             \
00364       dad = old, slot = &(left(old));                                   \
00365     else                                                                \
00366       dad = old, slot = &(right(old));                                  \
00367   }                                                                     \
00368                                                                         \
00369   *slot = node;                                                         \
00370   parent(node) = dad;                                                   \
00371                                                                         \
00372   if (tree != slot) {                                                   \
00373     prefix##_balance_insert(tree, node);                                \
00374   } else {                                                              \
00375     SET_BLACK(node);                                                    \
00376   }                                                                     \
00377                                                                         \
00378   INSERT(node);                                                         \
00379                                                                         \
00380   return 0;                                                             \
00381 }  \
00382 extern int const prefix##_dummy
00383 
00384 #if DOCUMENTATION_ONLY
00385 
00390 void rbtree_remove(Type **tree, Type *node);                            
00391 #endif
00392 
00393 #define RBTREE_REMOVE(SCOPE, prefix, Type, left, right, parent,         \
00394                       IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
00395                       REMOVE, INSERT)                                   \
00396 SCOPE                                                                   \
00397 void prefix##_remove(Type **top, Type *node)                            \
00398 {                                                                       \
00399   Type *kid, *dad;                                                      \
00400   int need_to_balance;                                                  \
00401                                                                         \
00402   if (top == NULL || node == NULL)                                      \
00403     return;                                                             \
00404                                                                         \
00405   /* Make sure that node is in tree */                                  \
00406   for (dad = node; dad; dad = parent(dad))                              \
00407     if (dad == *top)                                                    \
00408       break;                                                            \
00409                                                                         \
00410   if (!dad) return;                                                     \
00411                                                                         \
00412   /* Find a successor node with a free branch */                        \
00413   if (!left(node) || !right(node))                                      \
00414     dad = node;                                                         \
00415   else for (dad = right(node); left(dad); dad = left(dad))              \
00416     ;                                                                   \
00417   /* Dad has a free branch => kid is dad's only child */                \
00418   kid = left(dad) ? left(dad) : right(dad);                             \
00419                                                                         \
00420   /* Remove dad from tree */                                            \
00421   if (!(parent(dad)))                                                   \
00422     *top = kid;                                                         \
00423   else if (left(parent(dad)) == dad)                                    \
00424     left(parent(dad)) = kid;                                            \
00425   else assert(right(parent(dad)) == dad),                               \
00426     right(parent(dad)) = kid;                                           \
00427   if (kid)                                                              \
00428     parent(kid) = parent(dad);                                          \
00429                                                                         \
00430   need_to_balance = kid && IS_BLACK(dad);                               \
00431                                                                         \
00432   /* Put dad in place of node */                                        \
00433   if (node != dad) {                                                    \
00434     if (!(parent(dad) = parent(node)))                                  \
00435       *top = dad;                                                       \
00436     else if (left(parent(dad)) == node)                                 \
00437       left(parent(dad)) = dad;                                          \
00438     else assert(right(parent(dad)) == node),                            \
00439       right(parent(dad)) = dad;                                         \
00440                                                                         \
00441     COPY_COLOR(dad, node);                                              \
00442                                                                         \
00443     if ((left(dad) = left(node)))                                       \
00444       parent(left(dad)) = dad;                                          \
00445                                                                         \
00446     if ((right(dad) = right(node)))                                     \
00447       parent(right(dad)) = dad;                                         \
00448   }                                                                     \
00449                                                                         \
00450   REMOVE(node);                                                         \
00451   SET_RED(node);                                                        \
00452                                                                         \
00453   if (need_to_balance)                                                  \
00454     prefix##_balance_delete(top, kid);                                  \
00455 } \
00456 extern int const prefix##_dummy
00457 
00458 #if DOCUMENTATION_ONLY
00459 
00465 Type *rbtree_succ(Type const *node);
00466 #endif
00467 
00468 /* Define function returning inorder successor of node @a node. */
00469 #define RBTREE_SUCC(SCOPE, prefix, Type, left, right, parent)   \
00470 SCOPE Type *prefix##_succ(Type const *node)                             \
00471 {                                                                       \
00472   Type const *dad;                                                      \
00473                                                                         \
00474   if (right(node)) {                                                    \
00475     for (node = right(node); left(node); node = left(node))             \
00476       ;                                                                 \
00477     return (Type *)node;                                                \
00478   }                                                                     \
00479                                                                         \
00480   for (dad = parent(node); dad && node == right(dad); dad = parent(node)) \
00481     node = dad;                                                         \
00482                                                                         \
00483   return (Type *)dad;                                                   \
00484 } \
00485 extern int const prefix##_dummy
00486 
00487 #if DOCUMENTATION_ONLY
00488 
00494 Type *rbtree_prec(Type const *node);
00495 #endif
00496 
00497 /* Define function returning inorder precedessor of node @a node. */
00498 #define RBTREE_PREC(SCOPE, prefix, Type, left, right, parent)   \
00499   SCOPE Type *prefix##_prec(Type const *node)                           \
00500 {                                                                       \
00501   Type const *dad;                                                      \
00502                                                                         \
00503   if (left(node)) {                                                     \
00504     for (node = left(node); right(node); node = right(node))            \
00505       ;                                                                 \
00506     return (Type *)node;                                                \
00507   }                                                                     \
00508                                                                         \
00509   for (dad = parent(node); dad && node == left(dad); dad = parent(node)) \
00510     node = dad;                                                         \
00511                                                                         \
00512   return (Type *)dad;                                                   \
00513 } \
00514 extern int const prefix##_dummy
00515 
00516 #if DOCUMENTATION_ONLY
00517 
00523 Type *rbtree_first(Type const *node);
00524 #endif
00525 
00526 /* Define function returning first node in tree @a node. */
00527 #define RBTREE_FIRST(SCOPE, prefix, Type, left, right, parent)  \
00528 SCOPE Type *prefix##_first(Type const *node)    \
00529 {                                               \
00530   while (node && left(node))                    \
00531     node = left(node);                          \
00532                                                 \
00533   return (Type *)node;                          \
00534 } \
00535 extern int const prefix##_dummy
00536 
00537 #if DOCUMENTATION_ONLY
00538 
00544 Type *rbtree_last(Type const *node);
00545 #endif
00546 
00547 /* Define function returning last node in tree @a node. */
00548 #define RBTREE_LAST(SCOPE, prefix, Type, left, right, parent)   \
00549 SCOPE Type *prefix##_last(Type const *node)     \
00550 {                                               \
00551   while (node && right(node))                   \
00552     node = right(node);                         \
00553                                                 \
00554   return (Type *)node;                          \
00555 } \
00556 extern int const prefix##_dummy
00557 
00558 #if DOCUMENTATION_ONLY
00559 
00565 int rbtree_height(Type const *node);
00566 #endif
00567 
00568 /* Define function returning height of the tree from the @a node. */
00569 #define RBTREE_HEIGHT(SCOPE, prefix, Type, getleft, getright, getparent)        \
00570 SCOPE int prefix##_height(Type const *node)                     \
00571 {                                                               \
00572   int left, right;                                              \
00573                                                                 \
00574   if (!node)                                                    \
00575     return 0;                                                   \
00576                                                                 \
00577   left = getleft(node) ? prefix##_height(getleft(node)) : 0;    \
00578   right = getright(node) ? prefix##_height(getright(node)) : 0; \
00579                                                                 \
00580   if (left > right)                                             \
00581     return left + 1;                                            \
00582   else                                                          \
00583     return right + 1;                                           \
00584 } \
00585 extern int const prefix##_dummy
00586 
00598 #define RBTREE_PROTOS(SCOPE, prefix, Type)                              \
00599   SCOPE int prefix ## _insert(Type **, Type *, Type **return_old);      \
00600   SCOPE int prefix ## _append(Type **, Type *);                         \
00601   SCOPE void prefix ## _remove(Type **, Type *);                        \
00602   SCOPE Type *prefix ## _succ(Type const *);                            \
00603   SCOPE Type *prefix ## _prec(Type const *);                            \
00604   SCOPE Type *prefix ## _first(Type const *);                           \
00605   SCOPE Type *prefix ## _last(Type const *);                            \
00606   SCOPE int prefix ## _height(Type const *)
00607 
00647 #define RBTREE_BODIES(SCOPE, prefix, Type,                              \
00648                       left, right, parent,                              \
00649                       IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
00650                       CMP, INSERT, REMOVE)                              \
00651   RBTREE_LEFT_ROTATE(prefix, Type, left, right, parent);                \
00652   RBTREE_RIGHT_ROTATE(prefix, Type, left, right, parent);               \
00653   RBTREE_BALANCE_INSERT(prefix, Type, left, right, parent,              \
00654                         IS_RED, SET_RED, IS_BLACK, SET_BLACK);          \
00655   RBTREE_BALANCE_DELETE(prefix, Type, left, right, parent,              \
00656                         IS_RED, SET_RED, IS_BLACK, SET_BLACK,           \
00657                         COPY_COLOR);                                    \
00658   RBTREE_INSERT(SCOPE, prefix, Type, left, right, parent,               \
00659                 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR,       \
00660                 CMP, REMOVE, INSERT);                                   \
00661   RBTREE_APPEND(SCOPE, prefix, Type, left, right, parent,               \
00662                 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR,       \
00663                 CMP, REMOVE, INSERT);                                   \
00664   RBTREE_REMOVE(SCOPE, prefix, Type, left, right, parent,               \
00665                 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR,       \
00666                 REMOVE, INSERT);                                        \
00667   RBTREE_SUCC(SCOPE, prefix, Type, left, right, parent);                \
00668   RBTREE_PREC(SCOPE, prefix, Type, left, right, parent);                \
00669   RBTREE_FIRST(SCOPE, prefix, Type, left, right, parent);               \
00670   RBTREE_LAST(SCOPE, prefix, Type, left, right, parent);                \
00671   RBTREE_HEIGHT(SCOPE, prefix, Type, left, right, parent)
00672 
00673 #endif /* !define(RBTREE_H) */

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