Gnash 0.8.9
|
00001 /* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ 00002 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 00003 /* $FreeBSD: src/sys/sys/tree.h,v 1.7 2007/12/28 07:03:26 jasone Exp $ */ 00004 00005 /*- 00006 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 00007 * All rights reserved. 00008 * 00009 * Redistribution and use in source and binary forms, with or without 00010 * modification, are permitted provided that the following conditions 00011 * are met: 00012 * 1. Redistributions of source code must retain the above copyright 00013 * notice, this list of conditions and the following disclaimer. 00014 * 2. Redistributions in binary form must reproduce the above copyright 00015 * notice, this list of conditions and the following disclaimer in the 00016 * documentation and/or other materials provided with the distribution. 00017 * 00018 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 00019 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00020 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 00021 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 00022 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00023 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00024 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00025 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00026 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 00027 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00028 */ 00029 00030 #ifndef _SYS_TREE_H_ 00031 #define _SYS_TREE_H_ 00032 00033 /* 00034 * This file defines data structures for different types of trees: 00035 * splay trees and red-black trees. 00036 * 00037 * A splay tree is a self-organizing data structure. Every operation 00038 * on the tree causes a splay to happen. The splay moves the requested 00039 * node to the root of the tree and partly rebalances it. 00040 * 00041 * This has the benefit that request locality causes faster lookups as 00042 * the requested nodes move to the top of the tree. On the other hand, 00043 * every lookup causes memory writes. 00044 * 00045 * The Balance Theorem bounds the total access time for m operations 00046 * and n inserts on an initially empty tree as O((m + n)lg n). The 00047 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 00048 * 00049 * A red-black tree is a binary search tree with the node color as an 00050 * extra attribute. It fulfills a set of conditions: 00051 * - every search path from the root to a leaf consists of the 00052 * same number of black nodes, 00053 * - each red node (except for the root) has a black parent, 00054 * - each leaf node is black. 00055 * 00056 * Every operation on a red-black tree is bounded as O(lg n). 00057 * The maximum height of a red-black tree is 2lg (n+1). 00058 */ 00059 00060 #define SPLAY_HEAD(name, type) \ 00061 struct name { \ 00062 struct type *sph_root; /* root of the tree */ \ 00063 } 00064 00065 #define SPLAY_INITIALIZER(root) \ 00066 { NULL } 00067 00068 #define SPLAY_INIT(root) do { \ 00069 (root)->sph_root = NULL; \ 00070 } while (/*CONSTCOND*/ 0) 00071 00072 #define SPLAY_ENTRY(type) \ 00073 struct { \ 00074 struct type *spe_left; /* left element */ \ 00075 struct type *spe_right; /* right element */ \ 00076 } 00077 00078 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 00079 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 00080 #define SPLAY_ROOT(head) (head)->sph_root 00081 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 00082 00083 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 00084 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 00085 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 00086 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 00087 (head)->sph_root = tmp; \ 00088 } while (/*CONSTCOND*/ 0) 00089 00090 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 00091 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 00092 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 00093 (head)->sph_root = tmp; \ 00094 } while (/*CONSTCOND*/ 0) 00095 00096 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 00097 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 00098 tmp = (head)->sph_root; \ 00099 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 00100 } while (/*CONSTCOND*/ 0) 00101 00102 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 00103 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 00104 tmp = (head)->sph_root; \ 00105 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 00106 } while (/*CONSTCOND*/ 0) 00107 00108 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 00109 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 00110 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 00111 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 00112 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 00113 } while (/*CONSTCOND*/ 0) 00114 00115 /* Generates prototypes and inline functions */ 00116 00117 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 00118 void name##_SPLAY(struct name *, struct type *); \ 00119 void name##_SPLAY_MINMAX(struct name *, int); \ 00120 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 00121 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 00122 \ 00123 /* Finds the node with the same key as elm */ \ 00124 static __inline struct type * \ 00125 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 00126 { \ 00127 if (SPLAY_EMPTY(head)) \ 00128 return(NULL); \ 00129 name##_SPLAY(head, elm); \ 00130 if ((cmp)(elm, (head)->sph_root) == 0) \ 00131 return (head->sph_root); \ 00132 return (NULL); \ 00133 } \ 00134 \ 00135 static __inline struct type * \ 00136 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 00137 { \ 00138 name##_SPLAY(head, elm); \ 00139 if (SPLAY_RIGHT(elm, field) != NULL) { \ 00140 elm = SPLAY_RIGHT(elm, field); \ 00141 while (SPLAY_LEFT(elm, field) != NULL) { \ 00142 elm = SPLAY_LEFT(elm, field); \ 00143 } \ 00144 } else \ 00145 elm = NULL; \ 00146 return (elm); \ 00147 } \ 00148 \ 00149 static __inline struct type * \ 00150 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 00151 { \ 00152 name##_SPLAY_MINMAX(head, val); \ 00153 return (SPLAY_ROOT(head)); \ 00154 } 00155 00156 /* Main splay operation. 00157 * Moves node close to the key of elm to top 00158 */ 00159 #define SPLAY_GENERATE(name, type, field, cmp) \ 00160 struct type * \ 00161 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 00162 { \ 00163 if (SPLAY_EMPTY(head)) { \ 00164 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 00165 } else { \ 00166 int __comp; \ 00167 name##_SPLAY(head, elm); \ 00168 __comp = (cmp)(elm, (head)->sph_root); \ 00169 if(__comp < 0) { \ 00170 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 00171 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 00172 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 00173 } else if (__comp > 0) { \ 00174 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 00175 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 00176 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 00177 } else \ 00178 return ((head)->sph_root); \ 00179 } \ 00180 (head)->sph_root = (elm); \ 00181 return (NULL); \ 00182 } \ 00183 \ 00184 struct type * \ 00185 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 00186 { \ 00187 struct type *__tmp; \ 00188 if (SPLAY_EMPTY(head)) \ 00189 return (NULL); \ 00190 name##_SPLAY(head, elm); \ 00191 if ((cmp)(elm, (head)->sph_root) == 0) { \ 00192 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 00193 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 00194 } else { \ 00195 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 00196 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 00197 name##_SPLAY(head, elm); \ 00198 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 00199 } \ 00200 return (elm); \ 00201 } \ 00202 return (NULL); \ 00203 } \ 00204 \ 00205 void \ 00206 name##_SPLAY(struct name *head, struct type *elm) \ 00207 { \ 00208 struct type __node, *__left, *__right, *__tmp; \ 00209 int __comp; \ 00210 \ 00211 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 00212 __left = __right = &__node; \ 00213 \ 00214 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 00215 if (__comp < 0) { \ 00216 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 00217 if (__tmp == NULL) \ 00218 break; \ 00219 if ((cmp)(elm, __tmp) < 0){ \ 00220 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 00221 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 00222 break; \ 00223 } \ 00224 SPLAY_LINKLEFT(head, __right, field); \ 00225 } else if (__comp > 0) { \ 00226 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 00227 if (__tmp == NULL) \ 00228 break; \ 00229 if ((cmp)(elm, __tmp) > 0){ \ 00230 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 00231 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 00232 break; \ 00233 } \ 00234 SPLAY_LINKRIGHT(head, __left, field); \ 00235 } \ 00236 } \ 00237 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 00238 } \ 00239 \ 00240 /* Splay with either the minimum or the maximum element \ 00241 * Used to find minimum or maximum element in tree. \ 00242 */ \ 00243 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 00244 { \ 00245 struct type __node, *__left, *__right, *__tmp; \ 00246 \ 00247 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 00248 __left = __right = &__node; \ 00249 \ 00250 while (1) { \ 00251 if (__comp < 0) { \ 00252 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 00253 if (__tmp == NULL) \ 00254 break; \ 00255 if (__comp < 0){ \ 00256 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 00257 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 00258 break; \ 00259 } \ 00260 SPLAY_LINKLEFT(head, __right, field); \ 00261 } else if (__comp > 0) { \ 00262 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 00263 if (__tmp == NULL) \ 00264 break; \ 00265 if (__comp > 0) { \ 00266 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 00267 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 00268 break; \ 00269 } \ 00270 SPLAY_LINKRIGHT(head, __left, field); \ 00271 } \ 00272 } \ 00273 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 00274 } 00275 00276 #define SPLAY_NEGINF -1 00277 #define SPLAY_INF 1 00278 00279 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 00280 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 00281 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 00282 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 00283 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 00284 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 00285 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 00286 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 00287 00288 #define SPLAY_FOREACH(x, name, head) \ 00289 for ((x) = SPLAY_MIN(name, head); \ 00290 (x) != NULL; \ 00291 (x) = SPLAY_NEXT(name, head, x)) 00292 00293 /* Macros that define a red-black tree */ 00294 #define RB_HEAD(name, type) \ 00295 struct name { \ 00296 struct type *rbh_root; /* root of the tree */ \ 00297 } 00298 00299 #define RB_INITIALIZER(root) \ 00300 { NULL } 00301 00302 #define RB_INIT(root) do { \ 00303 (root)->rbh_root = NULL; \ 00304 } while (/*CONSTCOND*/ 0) 00305 00306 #define RB_BLACK 0 00307 #define RB_RED 1 00308 #define RB_ENTRY(type) \ 00309 struct { \ 00310 struct type *rbe_left; /* left element */ \ 00311 struct type *rbe_right; /* right element */ \ 00312 struct type *rbe_parent; /* parent element */ \ 00313 int rbe_color; /* node color */ \ 00314 } 00315 00316 #define RB_LEFT(elm, field) (elm)->field.rbe_left 00317 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 00318 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 00319 #define RB_COLOR(elm, field) (elm)->field.rbe_color 00320 #define RB_ROOT(head) (head)->rbh_root 00321 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 00322 00323 #define RB_SET(elm, parent, field) do { \ 00324 RB_PARENT(elm, field) = parent; \ 00325 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 00326 RB_COLOR(elm, field) = RB_RED; \ 00327 } while (/*CONSTCOND*/ 0) 00328 00329 #define RB_SET_BLACKRED(black, red, field) do { \ 00330 RB_COLOR(black, field) = RB_BLACK; \ 00331 RB_COLOR(red, field) = RB_RED; \ 00332 } while (/*CONSTCOND*/ 0) 00333 00334 #ifndef RB_AUGMENT 00335 #define RB_AUGMENT(x) do {} while (0) 00336 #endif 00337 00338 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 00339 (tmp) = RB_RIGHT(elm, field); \ 00340 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 00341 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 00342 } \ 00343 RB_AUGMENT(elm); \ 00344 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 00345 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 00346 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 00347 else \ 00348 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 00349 } else \ 00350 (head)->rbh_root = (tmp); \ 00351 RB_LEFT(tmp, field) = (elm); \ 00352 RB_PARENT(elm, field) = (tmp); \ 00353 RB_AUGMENT(tmp); \ 00354 if ((RB_PARENT(tmp, field))) \ 00355 RB_AUGMENT(RB_PARENT(tmp, field)); \ 00356 } while (/*CONSTCOND*/ 0) 00357 00358 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 00359 (tmp) = RB_LEFT(elm, field); \ 00360 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 00361 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 00362 } \ 00363 RB_AUGMENT(elm); \ 00364 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 00365 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 00366 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 00367 else \ 00368 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 00369 } else \ 00370 (head)->rbh_root = (tmp); \ 00371 RB_RIGHT(tmp, field) = (elm); \ 00372 RB_PARENT(elm, field) = (tmp); \ 00373 RB_AUGMENT(tmp); \ 00374 if ((RB_PARENT(tmp, field))) \ 00375 RB_AUGMENT(RB_PARENT(tmp, field)); \ 00376 } while (/*CONSTCOND*/ 0) 00377 00378 /* Generates prototypes and inline functions */ 00379 #define RB_PROTOTYPE(name, type, field, cmp) \ 00380 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 00381 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 00382 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 00383 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 00384 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 00385 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 00386 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 00387 attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 00388 attr struct type *name##_RB_FIND(struct name *, struct type *); \ 00389 attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 00390 attr struct type *name##_RB_NEXT(struct type *); \ 00391 attr struct type *name##_RB_PREV(struct type *); \ 00392 attr struct type *name##_RB_MINMAX(struct name *, int); \ 00393 \ 00394 00395 /* Main rb operation. 00396 * Moves node close to the key of elm to top 00397 */ 00398 #define RB_GENERATE(name, type, field, cmp) \ 00399 RB_GENERATE_INTERNAL(name, type, field, cmp,) 00400 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 00401 RB_GENERATE_INTERNAL(name, type, field, cmp, static) 00402 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 00403 attr void \ 00404 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 00405 { \ 00406 struct type *parent, *gparent, *tmp; \ 00407 while ((parent = RB_PARENT(elm, field)) != NULL && \ 00408 RB_COLOR(parent, field) == RB_RED) { \ 00409 gparent = RB_PARENT(parent, field); \ 00410 if (parent == RB_LEFT(gparent, field)) { \ 00411 tmp = RB_RIGHT(gparent, field); \ 00412 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 00413 RB_COLOR(tmp, field) = RB_BLACK; \ 00414 RB_SET_BLACKRED(parent, gparent, field);\ 00415 elm = gparent; \ 00416 continue; \ 00417 } \ 00418 if (RB_RIGHT(parent, field) == elm) { \ 00419 RB_ROTATE_LEFT(head, parent, tmp, field);\ 00420 tmp = parent; \ 00421 parent = elm; \ 00422 elm = tmp; \ 00423 } \ 00424 RB_SET_BLACKRED(parent, gparent, field); \ 00425 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 00426 } else { \ 00427 tmp = RB_LEFT(gparent, field); \ 00428 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 00429 RB_COLOR(tmp, field) = RB_BLACK; \ 00430 RB_SET_BLACKRED(parent, gparent, field);\ 00431 elm = gparent; \ 00432 continue; \ 00433 } \ 00434 if (RB_LEFT(parent, field) == elm) { \ 00435 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 00436 tmp = parent; \ 00437 parent = elm; \ 00438 elm = tmp; \ 00439 } \ 00440 RB_SET_BLACKRED(parent, gparent, field); \ 00441 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 00442 } \ 00443 } \ 00444 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 00445 } \ 00446 \ 00447 attr void \ 00448 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 00449 { \ 00450 struct type *tmp; \ 00451 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 00452 elm != RB_ROOT(head)) { \ 00453 if (RB_LEFT(parent, field) == elm) { \ 00454 tmp = RB_RIGHT(parent, field); \ 00455 if (RB_COLOR(tmp, field) == RB_RED) { \ 00456 RB_SET_BLACKRED(tmp, parent, field); \ 00457 RB_ROTATE_LEFT(head, parent, tmp, field);\ 00458 tmp = RB_RIGHT(parent, field); \ 00459 } \ 00460 if ((RB_LEFT(tmp, field) == NULL || \ 00461 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 00462 (RB_RIGHT(tmp, field) == NULL || \ 00463 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 00464 RB_COLOR(tmp, field) = RB_RED; \ 00465 elm = parent; \ 00466 parent = RB_PARENT(elm, field); \ 00467 } else { \ 00468 if (RB_RIGHT(tmp, field) == NULL || \ 00469 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 00470 struct type *oleft; \ 00471 if ((oleft = RB_LEFT(tmp, field)) \ 00472 != NULL) \ 00473 RB_COLOR(oleft, field) = RB_BLACK;\ 00474 RB_COLOR(tmp, field) = RB_RED; \ 00475 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 00476 tmp = RB_RIGHT(parent, field); \ 00477 } \ 00478 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 00479 RB_COLOR(parent, field) = RB_BLACK; \ 00480 if (RB_RIGHT(tmp, field)) \ 00481 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 00482 RB_ROTATE_LEFT(head, parent, tmp, field);\ 00483 elm = RB_ROOT(head); \ 00484 break; \ 00485 } \ 00486 } else { \ 00487 tmp = RB_LEFT(parent, field); \ 00488 if (RB_COLOR(tmp, field) == RB_RED) { \ 00489 RB_SET_BLACKRED(tmp, parent, field); \ 00490 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 00491 tmp = RB_LEFT(parent, field); \ 00492 } \ 00493 if ((RB_LEFT(tmp, field) == NULL || \ 00494 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 00495 (RB_RIGHT(tmp, field) == NULL || \ 00496 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 00497 RB_COLOR(tmp, field) = RB_RED; \ 00498 elm = parent; \ 00499 parent = RB_PARENT(elm, field); \ 00500 } else { \ 00501 if (RB_LEFT(tmp, field) == NULL || \ 00502 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 00503 struct type *oright; \ 00504 if ((oright = RB_RIGHT(tmp, field)) \ 00505 != NULL) \ 00506 RB_COLOR(oright, field) = RB_BLACK;\ 00507 RB_COLOR(tmp, field) = RB_RED; \ 00508 RB_ROTATE_LEFT(head, tmp, oright, field);\ 00509 tmp = RB_LEFT(parent, field); \ 00510 } \ 00511 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 00512 RB_COLOR(parent, field) = RB_BLACK; \ 00513 if (RB_LEFT(tmp, field)) \ 00514 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 00515 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 00516 elm = RB_ROOT(head); \ 00517 break; \ 00518 } \ 00519 } \ 00520 } \ 00521 if (elm) \ 00522 RB_COLOR(elm, field) = RB_BLACK; \ 00523 } \ 00524 \ 00525 attr struct type * \ 00526 name##_RB_REMOVE(struct name *head, struct type *elm) \ 00527 { \ 00528 struct type *child, *parent, *old = elm; \ 00529 int color; \ 00530 if (RB_LEFT(elm, field) == NULL) \ 00531 child = RB_RIGHT(elm, field); \ 00532 else if (RB_RIGHT(elm, field) == NULL) \ 00533 child = RB_LEFT(elm, field); \ 00534 else { \ 00535 struct type *left; \ 00536 elm = RB_RIGHT(elm, field); \ 00537 while ((left = RB_LEFT(elm, field)) != NULL) \ 00538 elm = left; \ 00539 child = RB_RIGHT(elm, field); \ 00540 parent = RB_PARENT(elm, field); \ 00541 color = RB_COLOR(elm, field); \ 00542 if (child) \ 00543 RB_PARENT(child, field) = parent; \ 00544 if (parent) { \ 00545 if (RB_LEFT(parent, field) == elm) \ 00546 RB_LEFT(parent, field) = child; \ 00547 else \ 00548 RB_RIGHT(parent, field) = child; \ 00549 RB_AUGMENT(parent); \ 00550 } else \ 00551 RB_ROOT(head) = child; \ 00552 if (RB_PARENT(elm, field) == old) \ 00553 parent = elm; \ 00554 (elm)->field = (old)->field; \ 00555 if (RB_PARENT(old, field)) { \ 00556 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 00557 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 00558 else \ 00559 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 00560 RB_AUGMENT(RB_PARENT(old, field)); \ 00561 } else \ 00562 RB_ROOT(head) = elm; \ 00563 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 00564 if (RB_RIGHT(old, field)) \ 00565 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 00566 if (parent) { \ 00567 left = parent; \ 00568 do { \ 00569 RB_AUGMENT(left); \ 00570 } while ((left = RB_PARENT(left, field)) != NULL); \ 00571 } \ 00572 goto color; \ 00573 } \ 00574 parent = RB_PARENT(elm, field); \ 00575 color = RB_COLOR(elm, field); \ 00576 if (child) \ 00577 RB_PARENT(child, field) = parent; \ 00578 if (parent) { \ 00579 if (RB_LEFT(parent, field) == elm) \ 00580 RB_LEFT(parent, field) = child; \ 00581 else \ 00582 RB_RIGHT(parent, field) = child; \ 00583 RB_AUGMENT(parent); \ 00584 } else \ 00585 RB_ROOT(head) = child; \ 00586 color: \ 00587 if (color == RB_BLACK) \ 00588 name##_RB_REMOVE_COLOR(head, parent, child); \ 00589 return (old); \ 00590 } \ 00591 \ 00592 /* Inserts a node into the RB tree */ \ 00593 attr struct type * \ 00594 name##_RB_INSERT(struct name *head, struct type *elm) \ 00595 { \ 00596 struct type *tmp; \ 00597 struct type *parent = NULL; \ 00598 int comp = 0; \ 00599 tmp = RB_ROOT(head); \ 00600 while (tmp) { \ 00601 parent = tmp; \ 00602 comp = (cmp)(elm, parent); \ 00603 if (comp < 0) \ 00604 tmp = RB_LEFT(tmp, field); \ 00605 else if (comp > 0) \ 00606 tmp = RB_RIGHT(tmp, field); \ 00607 else \ 00608 return (tmp); \ 00609 } \ 00610 RB_SET(elm, parent, field); \ 00611 if (parent != NULL) { \ 00612 if (comp < 0) \ 00613 RB_LEFT(parent, field) = elm; \ 00614 else \ 00615 RB_RIGHT(parent, field) = elm; \ 00616 RB_AUGMENT(parent); \ 00617 } else \ 00618 RB_ROOT(head) = elm; \ 00619 name##_RB_INSERT_COLOR(head, elm); \ 00620 return (NULL); \ 00621 } \ 00622 \ 00623 /* Finds the node with the same key as elm */ \ 00624 attr struct type * \ 00625 name##_RB_FIND(struct name *head, struct type *elm) \ 00626 { \ 00627 struct type *tmp = RB_ROOT(head); \ 00628 int comp; \ 00629 while (tmp) { \ 00630 comp = cmp(elm, tmp); \ 00631 if (comp < 0) \ 00632 tmp = RB_LEFT(tmp, field); \ 00633 else if (comp > 0) \ 00634 tmp = RB_RIGHT(tmp, field); \ 00635 else \ 00636 return (tmp); \ 00637 } \ 00638 return (NULL); \ 00639 } \ 00640 \ 00641 /* Finds the first node greater than or equal to the search key */ \ 00642 attr struct type * \ 00643 name##_RB_NFIND(struct name *head, struct type *elm) \ 00644 { \ 00645 struct type *tmp = RB_ROOT(head); \ 00646 struct type *res = NULL; \ 00647 int comp; \ 00648 while (tmp) { \ 00649 comp = cmp(elm, tmp); \ 00650 if (comp < 0) { \ 00651 res = tmp; \ 00652 tmp = RB_LEFT(tmp, field); \ 00653 } \ 00654 else if (comp > 0) \ 00655 tmp = RB_RIGHT(tmp, field); \ 00656 else \ 00657 return (tmp); \ 00658 } \ 00659 return (res); \ 00660 } \ 00661 \ 00662 /* ARGSUSED */ \ 00663 attr struct type * \ 00664 name##_RB_NEXT(struct type *elm) \ 00665 { \ 00666 if (RB_RIGHT(elm, field)) { \ 00667 elm = RB_RIGHT(elm, field); \ 00668 while (RB_LEFT(elm, field)) \ 00669 elm = RB_LEFT(elm, field); \ 00670 } else { \ 00671 if (RB_PARENT(elm, field) && \ 00672 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 00673 elm = RB_PARENT(elm, field); \ 00674 else { \ 00675 while (RB_PARENT(elm, field) && \ 00676 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 00677 elm = RB_PARENT(elm, field); \ 00678 elm = RB_PARENT(elm, field); \ 00679 } \ 00680 } \ 00681 return (elm); \ 00682 } \ 00683 \ 00684 /* ARGSUSED */ \ 00685 attr struct type * \ 00686 name##_RB_PREV(struct type *elm) \ 00687 { \ 00688 if (RB_LEFT(elm, field)) { \ 00689 elm = RB_LEFT(elm, field); \ 00690 while (RB_RIGHT(elm, field)) \ 00691 elm = RB_RIGHT(elm, field); \ 00692 } else { \ 00693 if (RB_PARENT(elm, field) && \ 00694 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 00695 elm = RB_PARENT(elm, field); \ 00696 else { \ 00697 while (RB_PARENT(elm, field) && \ 00698 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 00699 elm = RB_PARENT(elm, field); \ 00700 elm = RB_PARENT(elm, field); \ 00701 } \ 00702 } \ 00703 return (elm); \ 00704 } \ 00705 \ 00706 attr struct type * \ 00707 name##_RB_MINMAX(struct name *head, int val) \ 00708 { \ 00709 struct type *tmp = RB_ROOT(head); \ 00710 struct type *parent = NULL; \ 00711 while (tmp) { \ 00712 parent = tmp; \ 00713 if (val < 0) \ 00714 tmp = RB_LEFT(tmp, field); \ 00715 else \ 00716 tmp = RB_RIGHT(tmp, field); \ 00717 } \ 00718 return (parent); \ 00719 } 00720 00721 #define RB_NEGINF -1 00722 #define RB_INF 1 00723 00724 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 00725 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 00726 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 00727 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 00728 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 00729 #define RB_PREV(name, x, y) name##_RB_PREV(y) 00730 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 00731 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 00732 00733 #define RB_FOREACH(x, name, head) \ 00734 for ((x) = RB_MIN(name, head); \ 00735 (x) != NULL; \ 00736 (x) = name##_RB_NEXT(x)) 00737 00738 #define RB_FOREACH_REVERSE(x, name, head) \ 00739 for ((x) = RB_MAX(name, head); \ 00740 (x) != NULL; \ 00741 (x) = name##_RB_PREV(x)) 00742 00743 #endif /* _SYS_TREE_H_ */