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