|
nfs-ganesha 1.4
|
00001 /* 00002 * $Id: rbt_tree.h,v 1.3 2004/10/13 13:02:53 deniel Exp $ 00003 */ 00004 00005 /* 00006 * Implementation of RedBlack trees 00007 * Macros and algorithms 00008 */ 00009 00010 /* 00011 * This implementation of RedBlack trees was copied from 00012 * the STL library and adapted to a C environment. 00013 */ 00014 00015 /* 00016 * RB tree implementation -*- C++ -*- 00017 00018 * Copyright (C) 2001 Free Software Foundation, Inc. 00019 * 00020 * This file is part of the GNU ISO C++ Library. This library is free 00021 * software; you can redistribute it and/or modify it under the 00022 * terms of the GNU General Public License as published by the 00023 * Free Software Foundation; either version 2, or (at your option) 00024 * any later version. 00025 00026 * This library is distributed in the hope that it will be useful, 00027 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00028 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00029 * GNU General Public License for more details. 00030 00031 * You should have received a copy of the GNU General Public License along 00032 * with this library; see the file COPYING. If not, write to the Free 00033 * Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00034 * USA. 00035 00036 * As a special exception, you may use this file as part of a free software 00037 * library without restriction. Specifically, if other files instantiate 00038 * templates or use macros or inline functions from this file, or you compile 00039 * this file and link it with other files to produce an executable, this 00040 * file does not by itself cause the resulting executable to be covered by 00041 * the GNU General Public License. This exception does not however 00042 * invalidate any other reasons why the executable file might be covered by 00043 * the GNU General Public License. 00044 */ 00045 00046 /* 00047 * 00048 * Copyright (c) 1996,1997 00049 * Silicon Graphics Computer Systems, Inc. 00050 * 00051 * Permission to use, copy, modify, distribute and sell this software 00052 * and its documentation for any purpose is hereby granted without fee, 00053 * provided that the above copyright notice appear in all copies and 00054 * that both that copyright notice and this permission notice appear 00055 * in supporting documentation. Silicon Graphics makes no 00056 * representations about the suitability of this software for any 00057 * purpose. It is provided "as is" without express or implied warranty. 00058 * 00059 * 00060 * Copyright (c) 1994 00061 * Hewlett-Packard Company 00062 * 00063 * Permission to use, copy, modify, distribute and sell this software 00064 * and its documentation for any purpose is hereby granted without fee, 00065 * provided that the above copyright notice appear in all copies and 00066 * that both that copyright notice and this permission notice appear 00067 * in supporting documentation. Hewlett-Packard Company makes no 00068 * representations about the suitability of this software for any 00069 * purpose. It is provided "as is" without express or implied warranty. 00070 * 00071 * 00072 */ 00073 00074 /* NOTE: This is an internal header file, included by other STL headers. 00075 * You should not attempt to use it directly. 00076 */ 00077 00078 /* 00079 00080 Red-black tree class, designed for use in implementing STL 00081 associative containers (set, multiset, map, and multimap). The 00082 insertion and deletion algorithms are based on those in Cormen, 00083 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), 00084 except that 00085 00086 (1) the header cell is maintained with links not only to the root 00087 but also to the leftmost node of the tree, to enable constant time 00088 begin(), and to the rightmost node of the tree, to enable linear time 00089 performance when used with the generic set algorithms (set_union, 00090 etc.); 00091 00092 (2) when a node being deleted has two children its successor node is 00093 relinked into its place, rather than copied, so that the only 00094 iterators invalidated are those referring to the deleted node. 00095 00096 */ 00097 00098 #ifndef _RBT_TREE_H 00099 #define _RDT_TREE_H 00100 00101 /* 00102 * For RBT_HEAD_INIT, RBT_COUNT, RBT_RIGHTMOST and RBT_LEFTMOST : 00103 * __header is the header 00104 */ 00105 #define RBT_HEAD_INIT(__header) \ 00106 ((__header)->root = 0, \ 00107 (__header)->leftmost = 0, \ 00108 (__header)->rightmost = 0, \ 00109 (__header)->rbt_num_node = 0) 00110 00111 #define RBT_COUNT(__header) ((__header)->rbt_num_node) 00112 00113 #define RBT_RIGHTMOST(__header) ((__header)->rightmost) 00114 00115 #define RBT_LEFTMOST(__header) ((__header)->leftmost) 00116 00117 /* 00118 * For RBT_VALUE : 00119 * __node is any node 00120 */ 00121 #define RBT_VALUE(__node) ((__node)->rbt_value) 00122 00123 /* 00124 * For RBT_OPAQ : 00125 * __node is any node 00126 */ 00127 #define RBT_OPAQ(__node) ((__node)->rbt_opaq) 00128 00129 /* 00130 * For RBT_INCREMENT and RBT_DECREMENT : 00131 * __node is the starting node 00132 * __x is a temporary variable 00133 * __node is modified to point to the next/previous node 00134 */ 00135 #define RBT_INCREMENT(__node) \ 00136 { \ 00137 if ((__node)->next) { \ 00138 __node = (__node)->next; \ 00139 while ((__node)->left) \ 00140 (__node) = (__node)->left; \ 00141 } else { \ 00142 struct rbt_node *__x; \ 00143 do { \ 00144 __x = (__node); \ 00145 } while ((((__node) = (__node)->parent)) && ((__node)->next == __x)); \ 00146 } \ 00147 } 00148 00149 #define RBT_DECREMENT(__node) \ 00150 { \ 00151 if ((__node)->left) { \ 00152 __node = (__node)->left; \ 00153 while ((__node)->next) \ 00154 (__node) = (__node)->next; \ 00155 } else { \ 00156 struct rbt_node *__x; \ 00157 do { \ 00158 __x = (__node); \ 00159 } while ((((__node) = (__node)->parent)) && ((__node)->left == __x)); \ 00160 } \ 00161 } 00162 00163 /* 00164 * For RBT_LOOP and RBT_LOOP_REVERSE : 00165 * __header is the header 00166 * __it is the iterator (type rbt_node *) 00167 * 00168 * These macros must be used with, respectively, 00169 * RBT_INCREMENT and RBT_DECREMENT. 00170 */ 00171 #define RBT_LOOP(__header, __it) \ 00172 for ((__it) = (__header)->leftmost; (__it);) 00173 00174 #define RBT_LOOP_REVERSE(__header, __it) \ 00175 for ((__it) = (__header)->rightmost; (__it);) 00176 00177 /* 00178 * For RBT_ROTATE_LEFT and RBT_ROTATE_RIGHT : 00179 * __xx is pointer to the pivotal node 00180 * __yy is a temporary variable 00181 * the pivotal node is not modified except its links in the tree 00182 * For RBT_ROTATE_LEFT, (__xx)->next must not be zero. 00183 * For RBT_ROTATE_RIGHT, (__xx)->left must not be zero. 00184 */ 00185 #define RBT_ROTATE_LEFT(__xx) \ 00186 { \ 00187 struct rbt_node *__yy; \ 00188 __yy = (__xx)->next; \ 00189 if (((__xx)->next = __yy->left)) { \ 00190 __yy->left->parent = (__xx); \ 00191 __yy->left->anchor = &(__xx)->next; \ 00192 } \ 00193 __yy->parent = (__xx)->parent; \ 00194 __yy->left = (__xx); \ 00195 __yy->anchor = (__xx)->anchor; \ 00196 (__xx)->parent = __yy; \ 00197 (__xx)->anchor = &__yy->left; \ 00198 *__yy->anchor = __yy; \ 00199 } 00200 00201 #define RBT_ROTATE_RIGHT(__xx) \ 00202 { \ 00203 struct rbt_node *__yy; \ 00204 __yy = (__xx)->left; \ 00205 if (((__xx)->left = __yy->next)) { \ 00206 __yy->next->parent = (__xx); \ 00207 __yy->next->anchor = &(__xx)->left; \ 00208 } \ 00209 __yy->parent = (__xx)->parent; \ 00210 __yy->next = (__xx); \ 00211 __yy->anchor = (__xx)->anchor; \ 00212 (__xx)->parent = __yy; \ 00213 (__xx)->anchor = &__yy->next; \ 00214 *__yy->anchor = __yy; \ 00215 } 00216 00217 /* 00218 * For RBT_INSERT : 00219 * __node is the new node to be inserted 00220 * __par is the node which will be the first parent of __node 00221 * __node and __par are not modified 00222 * *__node and *__par are modified 00223 * __header is the header node 00224 * __x and __y are temporary variables 00225 * 00226 * __par must have been returned by RBT_FIND (successful or not). 00227 * If RBT_FIND was not successful, __par cannot have two children : 00228 * - If __node->rbt_value > __par->rbt_value, then __par->next is NULL. 00229 * __node will be installed at __par->next. 00230 * - If __node->rbt_value < __par->rbt_value, then __par->left is NULL. 00231 * __node will be installed at __par->next. 00232 * If RBT_FIND was successful : 00233 * - If __par has two children, search the previous node and replace 00234 * __par by this previous node. Then insert __node at __par->next. 00235 * - If __par->left is free, install __node at __par->left. 00236 * - Otherwise, install __node at __par->next. 00237 * 00238 * If this insertion unbalances the tree, __node may end in a different 00239 * position. 00240 */ 00241 #define RBT_INSERT(__header, __node, __par) \ 00242 { \ 00243 struct rbt_node *__x, *__y; \ 00244 (__header)->rbt_num_node++; /* increment number of nodes */ \ 00245 __y = (__par); \ 00246 if (__y == 0) { \ 00247 (__node)->anchor = &(__header)->root; /* initialize anchor */ \ 00248 (__header)->root = (__node); /* __node is root */ \ 00249 (__header)->rightmost = (__node); /* __node is rightmost */ \ 00250 (__header)->leftmost = (__node); /* __node is leftmost */ \ 00251 } else if (((__node)->rbt_value == __y->rbt_value) && \ 00252 __y->next && __y->left) { \ 00253 /* __y has two children and its value is equal to the value of node */ \ 00254 __y = __y->left; \ 00255 while (__y->next) \ 00256 __y = __y->next; \ 00257 __y->next = (__node); \ 00258 (__node)->anchor = &__y->next; \ 00259 } else if (((__node)->rbt_value > __y->rbt_value) || \ 00260 (((__node)->rbt_value == __y->rbt_value) && __y->left)) { \ 00261 __y->next = (__node); \ 00262 (__node)->anchor = &__y->next; \ 00263 if (__y == (__header)->rightmost) { \ 00264 /* rightmost points again to max node */ \ 00265 (__header)->rightmost = (__node); \ 00266 } \ 00267 } else { \ 00268 __y->left = (__node); \ 00269 (__node)->anchor = &__y->left; \ 00270 if (__y == (__header)->leftmost) { \ 00271 /* leftmost points again to min node */ \ 00272 (__header)->leftmost = (__node); \ 00273 } \ 00274 } \ 00275 (__node)->rbt_flags = 0; \ 00276 (__node)->parent = __y; \ 00277 (__node)->left = 0; \ 00278 (__node)->next = 0; \ 00279 __x = (__node); \ 00280 while (__x->parent) { \ 00281 __x->rbt_flags |= RBT_RED; \ 00282 if ((__x->parent->rbt_flags & RBT_RED) == 0) \ 00283 break; \ 00284 /* both __x and __x->parent are RED, need to change the tree */ \ 00285 /* __x->parent->parent is not NULL because __x->parent is RED */ \ 00286 if (__x->parent == __x->parent->parent->left) { \ 00287 __y = __x->parent->parent->next; \ 00288 /* __y is the uncle of __x */ \ 00289 if ((__y == 0) || ((__y->rbt_flags & RBT_RED) == 0)) { \ 00290 if (__x == __x->parent->next) { \ 00291 __x = __x->parent; \ 00292 RBT_ROTATE_LEFT(__x); \ 00293 } \ 00294 /* __x->parent will become the parent, with two children : */ \ 00295 /* __x and __x->parent->parent. */ \ 00296 /* __x->parent will be BLACK and both children RED */ \ 00297 __x->parent->rbt_flags &= ~RBT_RED; \ 00298 __x = __x->parent->parent; \ 00299 __x->rbt_flags |= RBT_RED; \ 00300 RBT_ROTATE_RIGHT(__x); \ 00301 break; \ 00302 } \ 00303 } else { \ 00304 __y = __x->parent->parent->left; \ 00305 /* __y is the uncle of __x */ \ 00306 if ((__y == 0) || ((__y->rbt_flags & RBT_RED) == 0)) { \ 00307 if (__x == __x->parent->left) { \ 00308 __x = __x->parent; \ 00309 RBT_ROTATE_RIGHT(__x); \ 00310 } \ 00311 /* __x->parent will become the parent, with two children : */ \ 00312 /* __x and __x->parent->parent. */ \ 00313 /* __x->parent will be BLACK and both children RED */ \ 00314 __x->parent->rbt_flags &= ~RBT_RED; \ 00315 __x = __x->parent->parent; \ 00316 __x->rbt_flags |= RBT_RED; \ 00317 RBT_ROTATE_LEFT(__x); \ 00318 break; \ 00319 } \ 00320 } \ 00321 /* color the parent and the uncle of __x into black */ \ 00322 __x->parent->rbt_flags &= ~RBT_RED; \ 00323 __y->rbt_flags &= ~RBT_RED; \ 00324 /* skip a generation and loop again because the colors have changed */ \ 00325 __x = __x->parent->parent; \ 00326 } \ 00327 } 00328 00329 /* 00330 * For RBT_UNLINK : 00331 * __node is the node to unlink 00332 * __header is the header node 00333 * __x, __z and __y are temporary variables 00334 * __node->rbt_flags may be modified 00335 * otherwise, __node is not modified 00336 */ 00337 #define RBT_UNLINK(__header, __node) \ 00338 { \ 00339 struct rbt_node *__x, *__y, *__z; \ 00340 (__header)->rbt_num_node--; /* decrement the number of nodes */ \ 00341 if ((__node)->left && (__node)->next) { \ 00342 /* __node has two children */ \ 00343 /* must introduce a node with less children : __y */ \ 00344 __y = (__node)->next; /* set __y to __node's successor */ \ 00345 while (__y->left) \ 00346 __y = __y->left; \ 00347 /* switch __y and __node completely, including colors */ \ 00348 if (((__node)->rbt_flags & RBT_RED) != (__y->rbt_flags & RBT_RED)) { \ 00349 (__node)->rbt_flags ^= RBT_RED; \ 00350 __y->rbt_flags ^= RBT_RED; \ 00351 } \ 00352 __x = __y->next; /* __x is NULL or the only child of __y */ \ 00353 /* relink __x in place of __y */ \ 00354 (__node)->left->parent = __y; \ 00355 (__node)->left->anchor = &__y->left; \ 00356 __y->left = (__node)->left; \ 00357 if (__y == (__node)->next) { \ 00358 __z = __y; \ 00359 } else { \ 00360 __z = __y->parent; \ 00361 if (__x) { \ 00362 __x->parent = __z; \ 00363 __x->anchor = &__z->left; \ 00364 } \ 00365 __z->left = __x; /* __y was a child of left */ \ 00366 __y->next = (__node)->next; \ 00367 (__node)->next->parent = __y; \ 00368 (__node)->next->anchor = &__y->next; \ 00369 } \ 00370 __y->parent = (__node)->parent; \ 00371 __y->anchor = (__node)->anchor; \ 00372 *(__node)->anchor = __y; \ 00373 } else { \ 00374 /* __node has at most one non-NULL child */ \ 00375 /* replace __node with this child */ \ 00376 __z = (__node)->parent; \ 00377 __x = (__node)->next; /* __x might be NULL */ \ 00378 if (__x == 0) \ 00379 __x = (__node)->left; /* __x is NULL or the only child of __node */ \ 00380 if (__x) { \ 00381 __x->parent = __z; \ 00382 __x->anchor = (__node)->anchor; \ 00383 } \ 00384 if ((__header)->leftmost == (__node)) { \ 00385 /* if __node is leftmost, __node->left is NULL */ \ 00386 if (__x) { \ 00387 __y = __x; \ 00388 while (__y->left) \ 00389 __y = __y->left; \ 00390 (__header)->leftmost = __y; \ 00391 } else { \ 00392 (__header)->leftmost = __z; \ 00393 /* makes leftmost = NULL if __node is root */ \ 00394 } \ 00395 } \ 00396 if ((__header)->rightmost == (__node)) { \ 00397 /* if __node is rightmost, __node->next is NULL */ \ 00398 if (__x) { \ 00399 __y = __x; \ 00400 while (__y->next) \ 00401 __y = __y->next; \ 00402 (__header)->rightmost = __y; \ 00403 } else { \ 00404 (__header)->rightmost = __z; \ 00405 /* makes rightmost = NULL if __node is root */ \ 00406 } \ 00407 } \ 00408 *(__node)->anchor = __x; \ 00409 } \ 00410 /* __z is set, __y is a new temporary */ \ 00411 if (!((__node)->rbt_flags & RBT_RED)) { \ 00412 /* __node was a black node, need to rebalance the tree */ \ 00413 /* if __node had two children, it was replaced by __y : */ \ 00414 /* __y was a black node, need to rebalance the tree */ \ 00415 while ((__z) && \ 00416 ((__x == 0) || !(__x->rbt_flags & RBT_RED))) { \ 00417 if (__x == __z->left) { \ 00418 __y = __z->next; \ 00419 if (__y->rbt_flags & RBT_RED) { \ 00420 __y->rbt_flags &= ~RBT_RED; \ 00421 __z->rbt_flags |= RBT_RED; \ 00422 RBT_ROTATE_LEFT(__z); \ 00423 __y = __z->next; \ 00424 } \ 00425 if ((__y->left == 0 || !(__y->left->rbt_flags & RBT_RED)) && \ 00426 (__y->next == 0 || !(__y->next->rbt_flags & RBT_RED))) { \ 00427 __y->rbt_flags |= RBT_RED; \ 00428 __x = __z; \ 00429 __z = __z->parent; \ 00430 } else { \ 00431 if (__y->next == 0 || !(__y->next->rbt_flags & RBT_RED)) { \ 00432 if (__y->left) \ 00433 __y->left->rbt_flags &= ~RBT_RED; \ 00434 __y->rbt_flags |= RBT_RED; \ 00435 RBT_ROTATE_RIGHT(__y); \ 00436 __y = __z->next; \ 00437 } \ 00438 __y->rbt_flags &= ~RBT_RED; \ 00439 __y->rbt_flags |= __z->rbt_flags & RBT_RED; \ 00440 __z->rbt_flags &= ~RBT_RED; \ 00441 if (__y->next) \ 00442 __y->next->rbt_flags &= ~RBT_RED; \ 00443 RBT_ROTATE_LEFT(__z); \ 00444 break; \ 00445 } \ 00446 } else { /* same as above, with right <-> left */ \ 00447 __y = __z->left; \ 00448 if (__y->rbt_flags & RBT_RED) { \ 00449 __y->rbt_flags &= ~RBT_RED; \ 00450 __z->rbt_flags |= RBT_RED; \ 00451 RBT_ROTATE_RIGHT(__z); \ 00452 __y = __z->left; \ 00453 } \ 00454 if ((__y->left == 0 || !(__y->left->rbt_flags & RBT_RED)) && \ 00455 (__y->next == 0 || !(__y->next->rbt_flags & RBT_RED))) { \ 00456 __y->rbt_flags |= RBT_RED; \ 00457 __x = __z; \ 00458 __z = __z->parent; \ 00459 } else { \ 00460 if (__y->left == 0 || !(__y->left->rbt_flags & RBT_RED)) { \ 00461 if (__y->next) \ 00462 __y->next->rbt_flags &= ~RBT_RED; \ 00463 __y->rbt_flags |= RBT_RED; \ 00464 RBT_ROTATE_LEFT(__y); \ 00465 __y = __z->left; \ 00466 } \ 00467 __y->rbt_flags &= ~RBT_RED; \ 00468 __y->rbt_flags |= __z->rbt_flags & RBT_RED; \ 00469 __z->rbt_flags &= ~RBT_RED; \ 00470 if (__y->left) \ 00471 __y->left->rbt_flags &= ~RBT_RED; \ 00472 RBT_ROTATE_RIGHT(__z); \ 00473 break; \ 00474 } \ 00475 } \ 00476 } \ 00477 if (__x) \ 00478 __x->rbt_flags &= ~RBT_RED; \ 00479 } \ 00480 } 00481 00482 /* 00483 * For RBT_FIND 00484 * __header is the header node 00485 * __node will contain the found node 00486 * __val is a uint64_t and contains the value to search 00487 * __x is a temporary variable 00488 * No nodes are modified 00489 * __node is modified 00490 * 00491 * When RBT_FIND returns, __node points to the node whose value is __val. 00492 * If multiple nodes have the value __val, only one is returned. 00493 * If no node has the value __val, __node points to the preceeding 00494 * or the following node and __node cannot have two children. 00495 * After the call, if __node is NULL, the tree is empty. 00496 * To check for success : 00497 * if (((__node) != 0) && (RBT_VALUE(__node) == (__val))) { 00498 * -- node found -- 00499 * ... 00500 * } 00501 * 00502 * RBT_FIND must be called before inserting a node using RBT_INSERT. 00503 */ 00504 #define RBT_FIND(__header, __node, __val) \ 00505 { \ 00506 struct rbt_node *__x; \ 00507 (__node) = (__header)->root; \ 00508 __x = (__header)->root; \ 00509 while (__x) { \ 00510 (__node) = __x; \ 00511 if (__x->rbt_value > (__val)) { \ 00512 __x = __x->left; \ 00513 } else if (__x->rbt_value < (__val)) { \ 00514 __x = __x->next; \ 00515 } else { \ 00516 break; \ 00517 } \ 00518 } \ 00519 } 00520 00521 /* 00522 * For RBT_FIND_LEFT 00523 * __header is the header node 00524 * __node will contain the found node 00525 * __val is a uint64_t and contains the value to search 00526 * __x is a temporary variable 00527 * No nodes are modified 00528 * __node is modified 00529 * 00530 * When RBT_FIND_LEFT returns, __node points to the leftmost node 00531 * whose value is __val. 00532 * If multiple nodes have the value __val, only one is returned. 00533 * If no node has the value __val, __node is NULL. 00534 * This is different from RBT_FIND. RBT_FIND_LEFT cannot be used 00535 * to insert a new node. 00536 * To check for success : 00537 * if ((__node) != 0) { 00538 * -- node found -- 00539 * ... 00540 * } 00541 */ 00542 #define RBT_FIND_LEFT(__header, __node, __val) \ 00543 { \ 00544 struct rbt_node *__x; \ 00545 (__node) = 0; \ 00546 __x = (__header)->root; \ 00547 while (__x) { \ 00548 if (__x->rbt_value > (__val)) { \ 00549 __x = __x->left; \ 00550 } else if (__x->rbt_value < (__val)) { \ 00551 __x = __x->next; \ 00552 } else { \ 00553 (__node) = __x; \ 00554 while (__x) { \ 00555 while ((__x = __x->left)) { \ 00556 if (__x->rbt_value < (__val)) \ 00557 break; \ 00558 (__node) = __x; \ 00559 } \ 00560 if (__x == 0) \ 00561 break; \ 00562 while ((__x = __x->next)) { \ 00563 if (__x->rbt_value == (__val)) { \ 00564 (__node) = __x; \ 00565 break; \ 00566 } \ 00567 } \ 00568 } \ 00569 break; \ 00570 } \ 00571 } \ 00572 } 00573 00574 /* 00575 * RBT_BLACK_COUNT counts the number of black nodes in the parents of a node 00576 */ 00577 #define RBT_BLACK_COUNT(__node, __sum) \ 00578 { \ 00579 for ((__sum) = 0; (__node); (__node) = (__node)->parent) { \ 00580 if (!((__node)->rbt_flags & RBT_RED)) \ 00581 ++(__sum); \ 00582 } \ 00583 } 00584 00585 #define RBT_VERIFY(__header, __it, __error) \ 00586 { \ 00587 int __len, __num, __sum; \ 00588 struct rbt_node *__L, *__R; \ 00589 (__error) = 0; \ 00590 if ((__header)->rbt_num_node == 0) { \ 00591 /* empty tree */ \ 00592 if (((__header)->leftmost) || \ 00593 ((__header)->rightmost) || \ 00594 ((__header)->root)) { \ 00595 (__error) = 1; \ 00596 (__it) = 0; \ 00597 } \ 00598 } else { \ 00599 __L = (__header)->leftmost; \ 00600 RBT_BLACK_COUNT(__L, __len) \ 00601 /* check each node and test RBT_INCREMENT */ \ 00602 __num = 0; \ 00603 RBT_LOOP((__header), (__it)) { \ 00604 if ((__it)->parent == 0) { \ 00605 if (((__it) != (__header)->root) || \ 00606 ((__it)->anchor != &(__header)->root)) { \ 00607 (__error) = 2; \ 00608 break; \ 00609 } \ 00610 } else { \ 00611 if ((((__it) == (__it)->parent->next) && \ 00612 ((__it)->anchor != &(__it)->parent->next)) || \ 00613 (((__it) == (__it)->parent->left) && \ 00614 ((__it)->anchor != &(__it)->parent->left))) { \ 00615 (__error) = 2; \ 00616 break; \ 00617 } \ 00618 } \ 00619 __L = (__it)->left; \ 00620 __R = (__it)->next; \ 00621 if (((__it)->rbt_flags & RBT_RED) && \ 00622 ((__L && (__L->rbt_flags & RBT_RED)) || \ 00623 (__R && (__R->rbt_flags & RBT_RED)))) { \ 00624 (__error) = 3; \ 00625 break; \ 00626 } \ 00627 if (__L && (__L->rbt_value > (__it)->rbt_value)) { \ 00628 (__error) = 4; \ 00629 break; \ 00630 } \ 00631 if (__R && (__R->rbt_value < (__it)->rbt_value)) { \ 00632 (__error) = 5; \ 00633 break; \ 00634 } \ 00635 if (!__L && !__R) { \ 00636 __L = (__it); \ 00637 RBT_BLACK_COUNT(__L, __sum) \ 00638 if (__sum != __len) { \ 00639 (__error) = 6; \ 00640 break; \ 00641 } \ 00642 } \ 00643 __num++; \ 00644 RBT_INCREMENT(__it) \ 00645 } \ 00646 if (((__error) == 0) && (__num != (__header)->rbt_num_node)) { \ 00647 (__error) = 7; \ 00648 (__it) = 0; \ 00649 } \ 00650 /* test RBT_DECREMENT */ \ 00651 __num = 0; \ 00652 RBT_LOOP_REVERSE(__header, __it) { \ 00653 __num++; \ 00654 RBT_DECREMENT(__it) \ 00655 } \ 00656 if (((__error) == 0) && (__num != (__header)->rbt_num_node)) { \ 00657 (__error) = 8; \ 00658 (__it) = 0; \ 00659 } \ 00660 /* check leftmost and rightmost */ \ 00661 if ((__error) == 0) { \ 00662 __L = (__header)->root; \ 00663 while ((__L)->left) \ 00664 (__L) = (__L)->left; \ 00665 __R = (__header)->root; \ 00666 while ((__R)->next) \ 00667 (__R) = (__R)->next; \ 00668 if ((__L != (__header)->leftmost) || \ 00669 (__R != (__header)->rightmost)) { \ 00670 (__error) = 9; \ 00671 (__it) = 0; \ 00672 } \ 00673 } \ 00674 /* check root flag */ \ 00675 if (((__error) == 0) && ((__header)->root) && \ 00676 !((__header)->root->parent == 0)) { \ 00677 (__error) = 10; \ 00678 (__it) = 0; \ 00679 } \ 00680 } \ 00681 } 00682 00683 #endif /* _RBT_TREE_H */
1.7.3