| OLD | NEW |
|---|
| (Empty) | |
| 1 /* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */ |
| 2 /* |
| 3 * Copyright 2002 Niels Provos <provos@citi.umich.edu> |
| 4 * All rights reserved. |
| 5 * |
| 6 * Redistribution and use in source and binary forms, with or without |
| 7 * modification, are permitted provided that the following conditions |
| 8 * are met: |
| 9 * 1. Redistributions of source code must retain the above copyright |
| 10 * notice, this list of conditions and the following disclaimer. |
| 11 * 2. Redistributions in binary form must reproduce the above copyright |
| 12 * notice, this list of conditions and the following disclaimer in the |
| 13 * documentation and/or other materials provided with the distribution. |
| 14 * |
| 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 25 */ |
| 26 |
| 27 #ifndef _SYS_TREE_H_ |
| 28 #define _SYS_TREE_H_ |
| 29 |
| 30 /* |
| 31 * This file defines data structures for different types of trees: |
| 32 * splay trees and red-black trees. |
| 33 * |
| 34 * A splay tree is a self-organizing data structure. Every operation |
| 35 * on the tree causes a splay to happen. The splay moves the requested |
| 36 * node to the root of the tree and partly rebalances it. |
| 37 * |
| 38 * This has the benefit that request locality causes faster lookups as |
| 39 * the requested nodes move to the top of the tree. On the other hand, |
| 40 * every lookup causes memory writes. |
| 41 * |
| 42 * The Balance Theorem bounds the total access time for m operations |
| 43 * and n inserts on an initially empty tree as O((m + n)lg n). The |
| 44 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); |
| 45 * |
| 46 * A red-black tree is a binary search tree with the node color as an |
| 47 * extra attribute. It fulfills a set of conditions: |
| 48 * - every search path from the root to a leaf consists of the |
| 49 * same number of black nodes, |
| 50 * - each red node (except for the root) has a black parent, |
| 51 * - each leaf node is black. |
| 52 * |
| 53 * Every operation on a red-black tree is bounded as O(lg n). |
| 54 * The maximum height of a red-black tree is 2lg (n+1). |
| 55 */ |
| 56 |
| 57 #define SPLAY_HEAD(name, type) \ |
| 58 struct name { \ |
| 59 struct type *sph_root; /* root of the tree */ \ |
| 60 } |
| 61 |
| 62 #define SPLAY_INITIALIZER(root) \ |
| 63 { NULL } |
| 64 |
| 65 #define SPLAY_INIT(root) do { \ |
| 66 (root)->sph_root = NULL; \ |
| 67 } while (0) |
| 68 |
| 69 #define SPLAY_ENTRY(type) \ |
| 70 struct { \ |
| 71 struct type *spe_left; /* left element */ \ |
| 72 struct type *spe_right; /* right element */ \ |
| 73 } |
| 74 |
| 75 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left |
| 76 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right |
| 77 #define SPLAY_ROOT(head) (head)->sph_root |
| 78 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) |
| 79 |
| 80 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ |
| 81 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ |
| 82 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ |
| 83 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ |
| 84 (head)->sph_root = tmp; \ |
| 85 } while (0) |
| 86 |
| 87 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ |
| 88 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ |
| 89 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ |
| 90 (head)->sph_root = tmp; \ |
| 91 } while (0) |
| 92 |
| 93 #define SPLAY_LINKLEFT(head, tmp, field) do { \ |
| 94 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ |
| 95 tmp = (head)->sph_root; \ |
| 96 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ |
| 97 } while (0) |
| 98 |
| 99 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ |
| 100 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ |
| 101 tmp = (head)->sph_root; \ |
| 102 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ |
| 103 } while (0) |
| 104 |
| 105 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ |
| 106 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ |
| 107 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ |
| 108 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ |
| 109 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ |
| 110 } while (0) |
| 111 |
| 112 /* Generates prototypes and inline functions */ |
| 113 |
| 114 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ |
| 115 void name##_SPLAY(struct name *, struct type *); \ |
| 116 void name##_SPLAY_MINMAX(struct name *, int); \ |
| 117 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ |
| 118 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ |
| 119 \ |
| 120 /* Finds the node with the same key as elm */ \ |
| 121 static __inline struct type * \ |
| 122 name##_SPLAY_FIND(struct name *head, struct type *elm) \ |
| 123 { \ |
| 124 if (SPLAY_EMPTY(head)) \ |
| 125 return(NULL); \ |
| 126 name##_SPLAY(head, elm); \ |
| 127 if ((cmp)(elm, (head)->sph_root) == 0) \ |
| 128 return (head->sph_root); \ |
| 129 return (NULL); \ |
| 130 } \ |
| 131 \ |
| 132 static __inline struct type * \ |
| 133 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ |
| 134 { \ |
| 135 name##_SPLAY(head, elm); \ |
| 136 if (SPLAY_RIGHT(elm, field) != NULL) { \ |
| 137 elm = SPLAY_RIGHT(elm, field); \ |
| 138 while (SPLAY_LEFT(elm, field) != NULL) { \ |
| 139 elm = SPLAY_LEFT(elm, field); \ |
| 140 } \ |
| 141 } else \ |
| 142 elm = NULL; \ |
| 143 return (elm); \ |
| 144 } \ |
| 145 \ |
| 146 static __inline struct type * \ |
| 147 name##_SPLAY_MIN_MAX(struct name *head, int val) \ |
| 148 { \ |
| 149 name##_SPLAY_MINMAX(head, val); \ |
| 150 return (SPLAY_ROOT(head)); \ |
| 151 } |
| 152 |
| 153 /* Main splay operation. |
| 154 * Moves node close to the key of elm to top |
| 155 */ |
| 156 #define SPLAY_GENERATE(name, type, field, cmp) \ |
| 157 struct type * \ |
| 158 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ |
| 159 { \ |
| 160 if (SPLAY_EMPTY(head)) { \ |
| 161 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ |
| 162 } else { \ |
| 163 int __comp; \ |
| 164 name##_SPLAY(head, elm); \ |
| 165 __comp = (cmp)(elm, (head)->sph_root); \ |
| 166 if(__comp < 0) { \ |
| 167 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ |
| 168 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ |
| 169 SPLAY_LEFT((head)->sph_root, field) = NULL; \ |
| 170 } else if (__comp > 0) { \ |
| 171 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ |
| 172 SPLAY_LEFT(elm, field) = (head)->sph_root; \ |
| 173 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ |
| 174 } else \ |
| 175 return ((head)->sph_root); \ |
| 176 } \ |
| 177 (head)->sph_root = (elm); \ |
| 178 return (NULL); \ |
| 179 } \ |
| 180 \ |
| 181 struct type * \ |
| 182 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ |
| 183 { \ |
| 184 struct type *__tmp; \ |
| 185 if (SPLAY_EMPTY(head)) \ |
| 186 return (NULL); \ |
| 187 name##_SPLAY(head, elm); \ |
| 188 if ((cmp)(elm, (head)->sph_root) == 0) { \ |
| 189 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ |
| 190 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ |
| 191 } else { \ |
| 192 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ |
| 193 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ |
| 194 name##_SPLAY(head, elm); \ |
| 195 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ |
| 196 } \ |
| 197 return (elm); \ |
| 198 } \ |
| 199 return (NULL); \ |
| 200 } \ |
| 201 \ |
| 202 void \ |
| 203 name##_SPLAY(struct name *head, struct type *elm) \ |
| 204 { \ |
| 205 struct type __node, *__left, *__right, *__tmp; \ |
| 206 int __comp; \ |
| 207 \ |
| 208 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ |
| 209 __left = __right = &__node; \ |
| 210 \ |
| 211 while ((__comp = (cmp)(elm, (head)->sph_root))) { \ |
| 212 if (__comp < 0) { \ |
| 213 __tmp = SPLAY_LEFT((head)->sph_root, field); \ |
| 214 if (__tmp == NULL) \ |
| 215 break; \ |
| 216 if ((cmp)(elm, __tmp) < 0){ \ |
| 217 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ |
| 218 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ |
| 219 break; \ |
| 220 } \ |
| 221 SPLAY_LINKLEFT(head, __right, field); \ |
| 222 } else if (__comp > 0) { \ |
| 223 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ |
| 224 if (__tmp == NULL) \ |
| 225 break; \ |
| 226 if ((cmp)(elm, __tmp) > 0){ \ |
| 227 SPLAY_ROTATE_LEFT(head, __tmp, field); \ |
| 228 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ |
| 229 break; \ |
| 230 } \ |
| 231 SPLAY_LINKRIGHT(head, __left, field); \ |
| 232 } \ |
| 233 } \ |
| 234 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ |
| 235 } \ |
| 236 \ |
| 237 /* Splay with either the minimum or the maximum element \ |
| 238 * Used to find minimum or maximum element in tree. \ |
| 239 */ \ |
| 240 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ |
| 241 { \ |
| 242 struct type __node, *__left, *__right, *__tmp; \ |
| 243 \ |
| 244 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ |
| 245 __left = __right = &__node; \ |
| 246 \ |
| 247 while (1) { \ |
| 248 if (__comp < 0) { \ |
| 249 __tmp = SPLAY_LEFT((head)->sph_root, field); \ |
| 250 if (__tmp == NULL) \ |
| 251 break; \ |
| 252 if (__comp < 0){ \ |
| 253 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ |
| 254 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ |
| 255 break; \ |
| 256 } \ |
| 257 SPLAY_LINKLEFT(head, __right, field); \ |
| 258 } else if (__comp > 0) { \ |
| 259 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ |
| 260 if (__tmp == NULL) \ |
| 261 break; \ |
| 262 if (__comp > 0) { \ |
| 263 SPLAY_ROTATE_LEFT(head, __tmp, field); \ |
| 264 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ |
| 265 break; \ |
| 266 } \ |
| 267 SPLAY_LINKRIGHT(head, __left, field); \ |
| 268 } \ |
| 269 } \ |
| 270 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ |
| 271 } |
| 272 |
| 273 #define SPLAY_NEGINF -1 |
| 274 #define SPLAY_INF 1 |
| 275 |
| 276 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) |
| 277 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) |
| 278 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) |
| 279 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) |
| 280 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ |
| 281 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) |
| 282 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ |
| 283 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) |
| 284 |
| 285 #define SPLAY_FOREACH(x, name, head) \ |
| 286 for ((x) = SPLAY_MIN(name, head); \ |
| 287 (x) != NULL; \ |
| 288 (x) = SPLAY_NEXT(name, head, x)) |
| 289 |
| 290 /* Macros that define a red-black tree */ |
| 291 #define RB_HEAD(name, type) \ |
| 292 struct name { \ |
| 293 struct type *rbh_root; /* root of the tree */ \ |
| 294 } |
| 295 |
| 296 #define RB_INITIALIZER(root) \ |
| 297 { NULL } |
| 298 |
| 299 #define RB_INIT(root) do { \ |
| 300 (root)->rbh_root = NULL; \ |
| 301 } while (0) |
| 302 |
| 303 #define RB_BLACK 0 |
| 304 #define RB_RED 1 |
| 305 #define RB_ENTRY(type) \ |
| 306 struct { \ |
| 307 struct type *rbe_left; /* left element */ \ |
| 308 struct type *rbe_right; /* right element */ \ |
| 309 struct type *rbe_parent; /* parent element */ \ |
| 310 int rbe_color; /* node color */ \ |
| 311 } |
| 312 |
| 313 #define RB_LEFT(elm, field) (elm)->field.rbe_left |
| 314 #define RB_RIGHT(elm, field) (elm)->field.rbe_right |
| 315 #define RB_PARENT(elm, field) (elm)->field.rbe_parent |
| 316 #define RB_COLOR(elm, field) (elm)->field.rbe_color |
| 317 #define RB_ROOT(head) (head)->rbh_root |
| 318 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) |
| 319 |
| 320 #define RB_SET(elm, parent, field) do { \ |
| 321 RB_PARENT(elm, field) = parent; \ |
| 322 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ |
| 323 RB_COLOR(elm, field) = RB_RED; \ |
| 324 } while (0) |
| 325 |
| 326 #define RB_SET_BLACKRED(black, red, field) do { \ |
| 327 RB_COLOR(black, field) = RB_BLACK; \ |
| 328 RB_COLOR(red, field) = RB_RED; \ |
| 329 } while (0) |
| 330 |
| 331 #ifndef RB_AUGMENT |
| 332 #define RB_AUGMENT(x) do {} while (0) |
| 333 #endif |
| 334 |
| 335 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ |
| 336 (tmp) = RB_RIGHT(elm, field); \ |
| 337 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ |
| 338 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ |
| 339 } \ |
| 340 RB_AUGMENT(elm); \ |
| 341 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ |
| 342 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ |
| 343 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ |
| 344 else \ |
| 345 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ |
| 346 } else \ |
| 347 (head)->rbh_root = (tmp); \ |
| 348 RB_LEFT(tmp, field) = (elm); \ |
| 349 RB_PARENT(elm, field) = (tmp); \ |
| 350 RB_AUGMENT(tmp); \ |
| 351 if ((RB_PARENT(tmp, field))) \ |
| 352 RB_AUGMENT(RB_PARENT(tmp, field)); \ |
| 353 } while (0) |
| 354 |
| 355 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ |
| 356 (tmp) = RB_LEFT(elm, field); \ |
| 357 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ |
| 358 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ |
| 359 } \ |
| 360 RB_AUGMENT(elm); \ |
| 361 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ |
| 362 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ |
| 363 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ |
| 364 else \ |
| 365 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ |
| 366 } else \ |
| 367 (head)->rbh_root = (tmp); \ |
| 368 RB_RIGHT(tmp, field) = (elm); \ |
| 369 RB_PARENT(elm, field) = (tmp); \ |
| 370 RB_AUGMENT(tmp); \ |
| 371 if ((RB_PARENT(tmp, field))) \ |
| 372 RB_AUGMENT(RB_PARENT(tmp, field)); \ |
| 373 } while (0) |
| 374 |
| 375 /* Generates prototypes and inline functions */ |
| 376 #define RB_PROTOTYPE(name, type, field, cmp) \ |
| 377 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) |
| 378 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ |
| 379 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) stat
ic) |
| 380 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ |
| 381 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ |
| 382 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ |
| 383 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ |
| 384 attr struct type *name##_RB_INSERT(struct name *, struct type *); \ |
| 385 attr struct type *name##_RB_FIND(struct name *, struct type *); \ |
| 386 attr struct type *name##_RB_NFIND(struct name *, struct type *); \ |
| 387 attr struct type *name##_RB_NEXT(struct type *); \ |
| 388 attr struct type *name##_RB_PREV(struct type *); \ |
| 389 attr struct type *name##_RB_MINMAX(struct name *, int); \ |
| 390 \ |
| 391 |
| 392 /* Main rb operation. |
| 393 * Moves node close to the key of elm to top |
| 394 */ |
| 395 #define RB_GENERATE(name, type, field, cmp) \ |
| 396 RB_GENERATE_INTERNAL(name, type, field, cmp,) |
| 397 #define RB_GENERATE_STATIC(name, type, field, cmp) \ |
| 398 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) stati
c) |
| 399 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ |
| 400 attr void \ |
| 401 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ |
| 402 { \ |
| 403 struct type *parent, *gparent, *tmp; \ |
| 404 while ((parent = RB_PARENT(elm, field)) && \ |
| 405 RB_COLOR(parent, field) == RB_RED) { \ |
| 406 gparent = RB_PARENT(parent, field); \ |
| 407 if (parent == RB_LEFT(gparent, field)) { \ |
| 408 tmp = RB_RIGHT(gparent, field); \ |
| 409 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ |
| 410 RB_COLOR(tmp, field) = RB_BLACK; \ |
| 411 RB_SET_BLACKRED(parent, gparent, field);\ |
| 412 elm = gparent; \ |
| 413 continue; \ |
| 414 } \ |
| 415 if (RB_RIGHT(parent, field) == elm) { \ |
| 416 RB_ROTATE_LEFT(head, parent, tmp, field);\ |
| 417 tmp = parent; \ |
| 418 parent = elm; \ |
| 419 elm = tmp; \ |
| 420 } \ |
| 421 RB_SET_BLACKRED(parent, gparent, field); \ |
| 422 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ |
| 423 } else { \ |
| 424 tmp = RB_LEFT(gparent, field); \ |
| 425 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ |
| 426 RB_COLOR(tmp, field) = RB_BLACK; \ |
| 427 RB_SET_BLACKRED(parent, gparent, field);\ |
| 428 elm = gparent; \ |
| 429 continue; \ |
| 430 } \ |
| 431 if (RB_LEFT(parent, field) == elm) { \ |
| 432 RB_ROTATE_RIGHT(head, parent, tmp, field);\ |
| 433 tmp = parent; \ |
| 434 parent = elm; \ |
| 435 elm = tmp; \ |
| 436 } \ |
| 437 RB_SET_BLACKRED(parent, gparent, field); \ |
| 438 RB_ROTATE_LEFT(head, gparent, tmp, field); \ |
| 439 } \ |
| 440 } \ |
| 441 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ |
| 442 } \ |
| 443 \ |
| 444 attr void \ |
| 445 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm)
\ |
| 446 { \ |
| 447 struct type *tmp; \ |
| 448 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ |
| 449 elm != RB_ROOT(head)) { \ |
| 450 if (RB_LEFT(parent, field) == elm) { \ |
| 451 tmp = RB_RIGHT(parent, field); \ |
| 452 if (RB_COLOR(tmp, field) == RB_RED) { \ |
| 453 RB_SET_BLACKRED(tmp, parent, field); \ |
| 454 RB_ROTATE_LEFT(head, parent, tmp, field);\ |
| 455 tmp = RB_RIGHT(parent, field); \ |
| 456 } \ |
| 457 if ((RB_LEFT(tmp, field) == NULL || \ |
| 458 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ |
| 459 (RB_RIGHT(tmp, field) == NULL || \ |
| 460 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ |
| 461 RB_COLOR(tmp, field) = RB_RED; \ |
| 462 elm = parent; \ |
| 463 parent = RB_PARENT(elm, field); \ |
| 464 } else { \ |
| 465 if (RB_RIGHT(tmp, field) == NULL || \ |
| 466 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ |
| 467 struct type *oleft; \ |
| 468 if ((oleft = RB_LEFT(tmp, field)))\ |
| 469 RB_COLOR(oleft, field) = RB_BLACK;\ |
| 470 RB_COLOR(tmp, field) = RB_RED; \ |
| 471 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ |
| 472 tmp = RB_RIGHT(parent, field); \ |
| 473 } \ |
| 474 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ |
| 475 RB_COLOR(parent, field) = RB_BLACK; \ |
| 476 if (RB_RIGHT(tmp, field)) \ |
| 477 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ |
| 478 RB_ROTATE_LEFT(head, parent, tmp, field);\ |
| 479 elm = RB_ROOT(head); \ |
| 480 break; \ |
| 481 } \ |
| 482 } else { \ |
| 483 tmp = RB_LEFT(parent, field); \ |
| 484 if (RB_COLOR(tmp, field) == RB_RED) { \ |
| 485 RB_SET_BLACKRED(tmp, parent, field); \ |
| 486 RB_ROTATE_RIGHT(head, parent, tmp, field);\ |
| 487 tmp = RB_LEFT(parent, field); \ |
| 488 } \ |
| 489 if ((RB_LEFT(tmp, field) == NULL || \ |
| 490 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ |
| 491 (RB_RIGHT(tmp, field) == NULL || \ |
| 492 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ |
| 493 RB_COLOR(tmp, field) = RB_RED; \ |
| 494 elm = parent; \ |
| 495 parent = RB_PARENT(elm, field); \ |
| 496 } else { \ |
| 497 if (RB_LEFT(tmp, field) == NULL || \ |
| 498 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ |
| 499 struct type *oright; \ |
| 500 if ((oright = RB_RIGHT(tmp, field)))\ |
| 501 RB_COLOR(oright, field) = RB_BLACK;\ |
| 502 RB_COLOR(tmp, field) = RB_RED; \ |
| 503 RB_ROTATE_LEFT(head, tmp, oright, field);\ |
| 504 tmp = RB_LEFT(parent, field); \ |
| 505 } \ |
| 506 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ |
| 507 RB_COLOR(parent, field) = RB_BLACK; \ |
| 508 if (RB_LEFT(tmp, field)) \ |
| 509 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ |
| 510 RB_ROTATE_RIGHT(head, parent, tmp, field);\ |
| 511 elm = RB_ROOT(head); \ |
| 512 break; \ |
| 513 } \ |
| 514 } \ |
| 515 } \ |
| 516 if (elm) \ |
| 517 RB_COLOR(elm, field) = RB_BLACK; \ |
| 518 } \ |
| 519 \ |
| 520 attr struct type * \ |
| 521 name##_RB_REMOVE(struct name *head, struct type *elm) \ |
| 522 { \ |
| 523 struct type *child, *parent, *old = elm; \ |
| 524 int color; \ |
| 525 if (RB_LEFT(elm, field) == NULL) \ |
| 526 child = RB_RIGHT(elm, field); \ |
| 527 else if (RB_RIGHT(elm, field) == NULL) \ |
| 528 child = RB_LEFT(elm, field); \ |
| 529 else { \ |
| 530 struct type *left; \ |
| 531 elm = RB_RIGHT(elm, field); \ |
| 532 while ((left = RB_LEFT(elm, field))) \ |
| 533 elm = left; \ |
| 534 child = RB_RIGHT(elm, field); \ |
| 535 parent = RB_PARENT(elm, field); \ |
| 536 color = RB_COLOR(elm, field); \ |
| 537 if (child) \ |
| 538 RB_PARENT(child, field) = parent; \ |
| 539 if (parent) { \ |
| 540 if (RB_LEFT(parent, field) == elm) \ |
| 541 RB_LEFT(parent, field) = child; \ |
| 542 else \ |
| 543 RB_RIGHT(parent, field) = child; \ |
| 544 RB_AUGMENT(parent); \ |
| 545 } else \ |
| 546 RB_ROOT(head) = child; \ |
| 547 if (RB_PARENT(elm, field) == old) \ |
| 548 parent = elm; \ |
| 549 (elm)->field = (old)->field; \ |
| 550 if (RB_PARENT(old, field)) { \ |
| 551 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ |
| 552 RB_LEFT(RB_PARENT(old, field), field) = elm;\ |
| 553 else \ |
| 554 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ |
| 555 RB_AUGMENT(RB_PARENT(old, field)); \ |
| 556 } else \ |
| 557 RB_ROOT(head) = elm; \ |
| 558 RB_PARENT(RB_LEFT(old, field), field) = elm; \ |
| 559 if (RB_RIGHT(old, field)) \ |
| 560 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ |
| 561 if (parent) { \ |
| 562 left = parent; \ |
| 563 do { \ |
| 564 RB_AUGMENT(left); \ |
| 565 } while ((left = RB_PARENT(left, field))); \ |
| 566 } \ |
| 567 goto color; \ |
| 568 } \ |
| 569 parent = RB_PARENT(elm, field); \ |
| 570 color = RB_COLOR(elm, field); \ |
| 571 if (child) \ |
| 572 RB_PARENT(child, field) = parent; \ |
| 573 if (parent) { \ |
| 574 if (RB_LEFT(parent, field) == elm) \ |
| 575 RB_LEFT(parent, field) = child; \ |
| 576 else \ |
| 577 RB_RIGHT(parent, field) = child; \ |
| 578 RB_AUGMENT(parent); \ |
| 579 } else \ |
| 580 RB_ROOT(head) = child; \ |
| 581 color: \ |
| 582 if (color == RB_BLACK) \ |
| 583 name##_RB_REMOVE_COLOR(head, parent, child); \ |
| 584 return (old); \ |
| 585 } \ |
| 586 \ |
| 587 /* Inserts a node into the RB tree */ \ |
| 588 attr struct type * \ |
| 589 name##_RB_INSERT(struct name *head, struct type *elm) \ |
| 590 { \ |
| 591 struct type *tmp; \ |
| 592 struct type *parent = NULL; \ |
| 593 int comp = 0; \ |
| 594 tmp = RB_ROOT(head); \ |
| 595 while (tmp) { \ |
| 596 parent = tmp; \ |
| 597 comp = (cmp)(elm, parent); \ |
| 598 if (comp < 0) \ |
| 599 tmp = RB_LEFT(tmp, field); \ |
| 600 else if (comp > 0) \ |
| 601 tmp = RB_RIGHT(tmp, field); \ |
| 602 else \ |
| 603 return (tmp); \ |
| 604 } \ |
| 605 RB_SET(elm, parent, field); \ |
| 606 if (parent != NULL) { \ |
| 607 if (comp < 0) \ |
| 608 RB_LEFT(parent, field) = elm; \ |
| 609 else \ |
| 610 RB_RIGHT(parent, field) = elm; \ |
| 611 RB_AUGMENT(parent); \ |
| 612 } else \ |
| 613 RB_ROOT(head) = elm; \ |
| 614 name##_RB_INSERT_COLOR(head, elm); \ |
| 615 return (NULL); \ |
| 616 } \ |
| 617 \ |
| 618 /* Finds the node with the same key as elm */ \ |
| 619 attr struct type * \ |
| 620 name##_RB_FIND(struct name *head, struct type *elm) \ |
| 621 { \ |
| 622 struct type *tmp = RB_ROOT(head); \ |
| 623 int comp; \ |
| 624 while (tmp) { \ |
| 625 comp = cmp(elm, tmp); \ |
| 626 if (comp < 0) \ |
| 627 tmp = RB_LEFT(tmp, field); \ |
| 628 else if (comp > 0) \ |
| 629 tmp = RB_RIGHT(tmp, field); \ |
| 630 else \ |
| 631 return (tmp); \ |
| 632 } \ |
| 633 return (NULL); \ |
| 634 } \ |
| 635 \ |
| 636 /* Finds the first node greater than or equal to the search key */ \ |
| 637 attr struct type * \ |
| 638 name##_RB_NFIND(struct name *head, struct type *elm) \ |
| 639 { \ |
| 640 struct type *tmp = RB_ROOT(head); \ |
| 641 struct type *res = NULL; \ |
| 642 int comp; \ |
| 643 while (tmp) { \ |
| 644 comp = cmp(elm, tmp); \ |
| 645 if (comp < 0) { \ |
| 646 res = tmp; \ |
| 647 tmp = RB_LEFT(tmp, field); \ |
| 648 } \ |
| 649 else if (comp > 0) \ |
| 650 tmp = RB_RIGHT(tmp, field); \ |
| 651 else \ |
| 652 return (tmp); \ |
| 653 } \ |
| 654 return (res); \ |
| 655 } \ |
| 656 \ |
| 657 /* ARGSUSED */ \ |
| 658 attr struct type * \ |
| 659 name##_RB_NEXT(struct type *elm) \ |
| 660 { \ |
| 661 if (RB_RIGHT(elm, field)) { \ |
| 662 elm = RB_RIGHT(elm, field); \ |
| 663 while (RB_LEFT(elm, field)) \ |
| 664 elm = RB_LEFT(elm, field); \ |
| 665 } else { \ |
| 666 if (RB_PARENT(elm, field) && \ |
| 667 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ |
| 668 elm = RB_PARENT(elm, field); \ |
| 669 else { \ |
| 670 while (RB_PARENT(elm, field) && \ |
| 671 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ |
| 672 elm = RB_PARENT(elm, field); \ |
| 673 elm = RB_PARENT(elm, field); \ |
| 674 } \ |
| 675 } \ |
| 676 return (elm); \ |
| 677 } \ |
| 678 \ |
| 679 /* ARGSUSED */ \ |
| 680 attr struct type * \ |
| 681 name##_RB_PREV(struct type *elm) \ |
| 682 { \ |
| 683 if (RB_LEFT(elm, field)) { \ |
| 684 elm = RB_LEFT(elm, field); \ |
| 685 while (RB_RIGHT(elm, field)) \ |
| 686 elm = RB_RIGHT(elm, field); \ |
| 687 } else { \ |
| 688 if (RB_PARENT(elm, field) && \ |
| 689 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ |
| 690 elm = RB_PARENT(elm, field); \ |
| 691 else { \ |
| 692 while (RB_PARENT(elm, field) && \ |
| 693 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ |
| 694 elm = RB_PARENT(elm, field); \ |
| 695 elm = RB_PARENT(elm, field); \ |
| 696 } \ |
| 697 } \ |
| 698 return (elm); \ |
| 699 } \ |
| 700 \ |
| 701 attr struct type * \ |
| 702 name##_RB_MINMAX(struct name *head, int val) \ |
| 703 { \ |
| 704 struct type *tmp = RB_ROOT(head); \ |
| 705 struct type *parent = NULL; \ |
| 706 while (tmp) { \ |
| 707 parent = tmp; \ |
| 708 if (val < 0) \ |
| 709 tmp = RB_LEFT(tmp, field); \ |
| 710 else \ |
| 711 tmp = RB_RIGHT(tmp, field); \ |
| 712 } \ |
| 713 return (parent); \ |
| 714 } |
| 715 |
| 716 #define RB_NEGINF -1 |
| 717 #define RB_INF 1 |
| 718 |
| 719 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) |
| 720 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) |
| 721 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) |
| 722 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) |
| 723 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) |
| 724 #define RB_PREV(name, x, y) name##_RB_PREV(y) |
| 725 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) |
| 726 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) |
| 727 |
| 728 #define RB_FOREACH(x, name, head) \ |
| 729 for ((x) = RB_MIN(name, head); \ |
| 730 (x) != NULL; \ |
| 731 (x) = name##_RB_NEXT(x)) |
| 732 |
| 733 #define RB_FOREACH_SAFE(x, name, head, y) \ |
| 734 for ((x) = RB_MIN(name, head); \ |
| 735 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ |
| 736 (x) = (y)) |
| 737 |
| 738 #define RB_FOREACH_REVERSE(x, name, head) \ |
| 739 for ((x) = RB_MAX(name, head); \ |
| 740 (x) != NULL; \ |
| 741 (x) = name##_RB_PREV(x)) |
| 742 |
| 743 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ |
| 744 for ((x) = RB_MAX(name, head); \ |
| 745 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ |
| 746 (x) = (y)) |
| 747 |
| 748 #endif /* _SYS_TREE_H_ */ |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 323873004:
Add unpatched OpenBSD trees to tools/android/heap_profiler/ (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master