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 su_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 su_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 su_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 su_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 su_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) */