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 /* Macros that define a red-black tree */ 31 #define RB_HEAD(name, type) \ 32 struct name { \ 33 struct type *rbh_root; /* root of the tree */ \ 34 } 35 36 #define RB_INITIALIZER(root) \ 37 { NULL } 38 39 #define RB_INIT(root) do { \ 40 (root)->rbh_root = NULL; \ 41 } while (0) 42 43 #define RB_BLACK 0 44 #define RB_RED 1 45 #define RB_ENTRY(type) \ 46 struct { \ 47 struct type *rbe_left; /* left element */ \ 48 struct type *rbe_right; /* right element */ \ 49 struct type *rbe_parent; /* parent element */ \ 50 int rbe_color; /* node color */ \ 51 } 52 53 #define RB_LEFT(elm, field) (elm)->field.rbe_left 54 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 55 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 56 #define RB_COLOR(elm, field) (elm)->field.rbe_color 57 #define RB_ROOT(head) (head)->rbh_root 58 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 59 60 #define RB_SET(elm, parent, field) do { \ 61 RB_PARENT(elm, field) = parent; \ 62 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 63 RB_COLOR(elm, field) = RB_RED; \ 64 } while (0) 65 66 #define RB_SET_BLACKRED(black, red, field) do { \ 67 RB_COLOR(black, field) = RB_BLACK; \ 68 RB_COLOR(red, field) = RB_RED; \ 69 } while (0) 70 71 #ifndef RB_AUGMENT 72 #define RB_AUGMENT(x) do {} while (0) 73 #endif 74 75 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 76 (tmp) = RB_RIGHT(elm, field); \ 77 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 78 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 79 } \ 80 RB_AUGMENT(elm); \ 81 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 82 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 83 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 84 else \ 85 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 86 } else \ 87 (head)->rbh_root = (tmp); \ 88 RB_LEFT(tmp, field) = (elm); \ 89 RB_PARENT(elm, field) = (tmp); \ 90 RB_AUGMENT(tmp); \ 91 if ((RB_PARENT(tmp, field))) \ 92 RB_AUGMENT(RB_PARENT(tmp, field)); \ 93 } while (0) 94 95 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 96 (tmp) = RB_LEFT(elm, field); \ 97 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 98 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 99 } \ 100 RB_AUGMENT(elm); \ 101 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 102 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 103 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 104 else \ 105 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 106 } else \ 107 (head)->rbh_root = (tmp); \ 108 RB_RIGHT(tmp, field) = (elm); \ 109 RB_PARENT(elm, field) = (tmp); \ 110 RB_AUGMENT(tmp); \ 111 if ((RB_PARENT(tmp, field))) \ 112 RB_AUGMENT(RB_PARENT(tmp, field)); \ 113 } while (0) 114 115 /* Generates prototypes and inline functions */ 116 #define RB_PROTOTYPE(name, type, field, cmp) \ 117 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 118 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 119 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 120 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 121 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 122 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 123 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 124 attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 125 attr struct type *name##_RB_FIND(struct name *, struct type *); \ 126 attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 127 attr struct type *name##_RB_NEXT(struct type *); \ 128 attr struct type *name##_RB_PREV(struct type *); \ 129 attr struct type *name##_RB_MINMAX(struct name *, int); \ 130 \ 131 132 /* Main rb operation. 133 * Moves node close to the key of elm to top 134 */ 135 #define RB_GENERATE(name, type, field, cmp) \ 136 RB_GENERATE_INTERNAL(name, type, field, cmp,) 137 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 138 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 139 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 140 attr void \ 141 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 142 { \ 143 struct type *parent, *gparent, *tmp; \ 144 while ((parent = RB_PARENT(elm, field)) && \ 145 RB_COLOR(parent, field) == RB_RED) { \ 146 gparent = RB_PARENT(parent, field); \ 147 if (parent == RB_LEFT(gparent, field)) { \ 148 tmp = RB_RIGHT(gparent, field); \ 149 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 150 RB_COLOR(tmp, field) = RB_BLACK; \ 151 RB_SET_BLACKRED(parent, gparent, field);\ 152 elm = gparent; \ 153 continue; \ 154 } \ 155 if (RB_RIGHT(parent, field) == elm) { \ 156 RB_ROTATE_LEFT(head, parent, tmp, field);\ 157 tmp = parent; \ 158 parent = elm; \ 159 elm = tmp; \ 160 } \ 161 RB_SET_BLACKRED(parent, gparent, field); \ 162 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 163 } else { \ 164 tmp = RB_LEFT(gparent, field); \ 165 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 166 RB_COLOR(tmp, field) = RB_BLACK; \ 167 RB_SET_BLACKRED(parent, gparent, field);\ 168 elm = gparent; \ 169 continue; \ 170 } \ 171 if (RB_LEFT(parent, field) == elm) { \ 172 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 173 tmp = parent; \ 174 parent = elm; \ 175 elm = tmp; \ 176 } \ 177 RB_SET_BLACKRED(parent, gparent, field); \ 178 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 179 } \ 180 } \ 181 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 182 } \ 183 \ 184 attr void \ 185 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 186 { \ 187 struct type *tmp; \ 188 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 189 elm != RB_ROOT(head)) { \ 190 if (RB_LEFT(parent, field) == elm) { \ 191 tmp = RB_RIGHT(parent, field); \ 192 if (RB_COLOR(tmp, field) == RB_RED) { \ 193 RB_SET_BLACKRED(tmp, parent, field); \ 194 RB_ROTATE_LEFT(head, parent, tmp, field);\ 195 tmp = RB_RIGHT(parent, field); \ 196 } \ 197 if ((RB_LEFT(tmp, field) == NULL || \ 198 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 199 (RB_RIGHT(tmp, field) == NULL || \ 200 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 201 RB_COLOR(tmp, field) = RB_RED; \ 202 elm = parent; \ 203 parent = RB_PARENT(elm, field); \ 204 } else { \ 205 if (RB_RIGHT(tmp, field) == NULL || \ 206 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 207 struct type *oleft; \ 208 if ((oleft = RB_LEFT(tmp, field)))\ 209 RB_COLOR(oleft, field) = RB_BLACK;\ 210 RB_COLOR(tmp, field) = RB_RED; \ 211 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 212 tmp = RB_RIGHT(parent, field); \ 213 } \ 214 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 215 RB_COLOR(parent, field) = RB_BLACK; \ 216 if (RB_RIGHT(tmp, field)) \ 217 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 218 RB_ROTATE_LEFT(head, parent, tmp, field);\ 219 elm = RB_ROOT(head); \ 220 break; \ 221 } \ 222 } else { \ 223 tmp = RB_LEFT(parent, field); \ 224 if (RB_COLOR(tmp, field) == RB_RED) { \ 225 RB_SET_BLACKRED(tmp, parent, field); \ 226 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 227 tmp = RB_LEFT(parent, field); \ 228 } \ 229 if ((RB_LEFT(tmp, field) == NULL || \ 230 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 231 (RB_RIGHT(tmp, field) == NULL || \ 232 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 233 RB_COLOR(tmp, field) = RB_RED; \ 234 elm = parent; \ 235 parent = RB_PARENT(elm, field); \ 236 } else { \ 237 if (RB_LEFT(tmp, field) == NULL || \ 238 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 239 struct type *oright; \ 240 if ((oright = RB_RIGHT(tmp, field)))\ 241 RB_COLOR(oright, field) = RB_BLACK;\ 242 RB_COLOR(tmp, field) = RB_RED; \ 243 RB_ROTATE_LEFT(head, tmp, oright, field);\ 244 tmp = RB_LEFT(parent, field); \ 245 } \ 246 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 247 RB_COLOR(parent, field) = RB_BLACK; \ 248 if (RB_LEFT(tmp, field)) \ 249 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 250 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 251 elm = RB_ROOT(head); \ 252 break; \ 253 } \ 254 } \ 255 } \ 256 if (elm) \ 257 RB_COLOR(elm, field) = RB_BLACK; \ 258 } \ 259 \ 260 attr struct type * \ 261 name##_RB_REMOVE(struct name *head, struct type *elm) \ 262 { \ 263 struct type *child, *parent, *old = elm; \ 264 int color; \ 265 if (RB_LEFT(elm, field) == NULL) \ 266 child = RB_RIGHT(elm, field); \ 267 else if (RB_RIGHT(elm, field) == NULL) \ 268 child = RB_LEFT(elm, field); \ 269 else { \ 270 struct type *left; \ 271 elm = RB_RIGHT(elm, field); \ 272 while ((left = RB_LEFT(elm, field))) \ 273 elm = left; \ 274 child = RB_RIGHT(elm, field); \ 275 parent = RB_PARENT(elm, field); \ 276 color = RB_COLOR(elm, field); \ 277 if (child) \ 278 RB_PARENT(child, field) = parent; \ 279 if (parent) { \ 280 if (RB_LEFT(parent, field) == elm) \ 281 RB_LEFT(parent, field) = child; \ 282 else \ 283 RB_RIGHT(parent, field) = child; \ 284 RB_AUGMENT(parent); \ 285 } else \ 286 RB_ROOT(head) = child; \ 287 if (RB_PARENT(elm, field) == old) \ 288 parent = elm; \ 289 (elm)->field = (old)->field; \ 290 if (RB_PARENT(old, field)) { \ 291 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 292 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 293 else \ 294 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 295 RB_AUGMENT(RB_PARENT(old, field)); \ 296 } else \ 297 RB_ROOT(head) = elm; \ 298 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 299 if (RB_RIGHT(old, field)) \ 300 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 301 if (parent) { \ 302 left = parent; \ 303 do { \ 304 RB_AUGMENT(left); \ 305 } while ((left = RB_PARENT(left, field))); \ 306 } \ 307 goto color; \ 308 } \ 309 parent = RB_PARENT(elm, field); \ 310 color = RB_COLOR(elm, field); \ 311 if (child) \ 312 RB_PARENT(child, field) = parent; \ 313 if (parent) { \ 314 if (RB_LEFT(parent, field) == elm) \ 315 RB_LEFT(parent, field) = child; \ 316 else \ 317 RB_RIGHT(parent, field) = child; \ 318 RB_AUGMENT(parent); \ 319 } else \ 320 RB_ROOT(head) = child; \ 321 color: \ 322 if (color == RB_BLACK) \ 323 name##_RB_REMOVE_COLOR(head, parent, child); \ 324 return (old); \ 325 } \ 326 \ 327 /* Inserts a node into the RB tree */ \ 328 attr struct type * \ 329 name##_RB_INSERT(struct name *head, struct type *elm) \ 330 { \ 331 struct type *tmp; \ 332 struct type *parent = NULL; \ 333 int comp = 0; \ 334 tmp = RB_ROOT(head); \ 335 while (tmp) { \ 336 parent = tmp; \ 337 comp = (cmp)(elm, parent); \ 338 if (comp < 0) \ 339 tmp = RB_LEFT(tmp, field); \ 340 else if (comp > 0) \ 341 tmp = RB_RIGHT(tmp, field); \ 342 else \ 343 return (tmp); \ 344 } \ 345 RB_SET(elm, parent, field); \ 346 if (parent != NULL) { \ 347 if (comp < 0) \ 348 RB_LEFT(parent, field) = elm; \ 349 else \ 350 RB_RIGHT(parent, field) = elm; \ 351 RB_AUGMENT(parent); \ 352 } else \ 353 RB_ROOT(head) = elm; \ 354 name##_RB_INSERT_COLOR(head, elm); \ 355 return (NULL); \ 356 } \ 357 \ 358 /* Finds the node with the same key as elm */ \ 359 attr struct type * \ 360 name##_RB_FIND(struct name *head, struct type *elm) \ 361 { \ 362 struct type *tmp = RB_ROOT(head); \ 363 int comp; \ 364 while (tmp) { \ 365 comp = cmp(elm, tmp); \ 366 if (comp < 0) \ 367 tmp = RB_LEFT(tmp, field); \ 368 else if (comp > 0) \ 369 tmp = RB_RIGHT(tmp, field); \ 370 else \ 371 return (tmp); \ 372 } \ 373 return (NULL); \ 374 } \ 375 \ 376 /* Finds the first node greater than or equal to the search key */ \ 377 attr struct type * \ 378 name##_RB_NFIND(struct name *head, struct type *elm) \ 379 { \ 380 struct type *tmp = RB_ROOT(head); \ 381 struct type *res = NULL; \ 382 int comp; \ 383 while (tmp) { \ 384 comp = cmp(elm, tmp); \ 385 if (comp < 0) { \ 386 res = tmp; \ 387 tmp = RB_LEFT(tmp, field); \ 388 } \ 389 else if (comp > 0) \ 390 tmp = RB_RIGHT(tmp, field); \ 391 else \ 392 return (tmp); \ 393 } \ 394 return (res); \ 395 } \ 396 \ 397 /* ARGSUSED */ \ 398 attr struct type * \ 399 name##_RB_NEXT(struct type *elm) \ 400 { \ 401 if (RB_RIGHT(elm, field)) { \ 402 elm = RB_RIGHT(elm, field); \ 403 while (RB_LEFT(elm, field)) \ 404 elm = RB_LEFT(elm, field); \ 405 } else { \ 406 if (RB_PARENT(elm, field) && \ 407 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 408 elm = RB_PARENT(elm, field); \ 409 else { \ 410 while (RB_PARENT(elm, field) && \ 411 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 412 elm = RB_PARENT(elm, field); \ 413 elm = RB_PARENT(elm, field); \ 414 } \ 415 } \ 416 return (elm); \ 417 } \ 418 \ 419 /* ARGSUSED */ \ 420 attr struct type * \ 421 name##_RB_PREV(struct type *elm) \ 422 { \ 423 if (RB_LEFT(elm, field)) { \ 424 elm = RB_LEFT(elm, field); \ 425 while (RB_RIGHT(elm, field)) \ 426 elm = RB_RIGHT(elm, field); \ 427 } else { \ 428 if (RB_PARENT(elm, field) && \ 429 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 430 elm = RB_PARENT(elm, field); \ 431 else { \ 432 while (RB_PARENT(elm, field) && \ 433 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 434 elm = RB_PARENT(elm, field); \ 435 elm = RB_PARENT(elm, field); \ 436 } \ 437 } \ 438 return (elm); \ 439 } \ 440 \ 441 attr struct type * \ 442 name##_RB_MINMAX(struct name *head, int val) \ 443 { \ 444 struct type *tmp = RB_ROOT(head); \ 445 struct type *parent = NULL; \ 446 while (tmp) { \ 447 parent = tmp; \ 448 if (val < 0) \ 449 tmp = RB_LEFT(tmp, field); \ 450 else \ 451 tmp = RB_RIGHT(tmp, field); \ 452 } \ 453 return (parent); \ 454 } 455 456 #define RB_NEGINF -1 457 #define RB_INF 1 458 459 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 460 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 461 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 462 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 463 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 464 #define RB_PREV(name, x, y) name##_RB_PREV(y) 465 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 466 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 467 468 #define RB_FOREACH(x, name, head) \ 469 for ((x) = RB_MIN(name, head); \ 470 (x) != NULL; \ 471 (x) = name##_RB_NEXT(x)) 472 473 #define RB_FOREACH_SAFE(x, name, head, y) \ 474 for ((x) = RB_MIN(name, head); \ 475 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ 476 (x) = (y)) 477 478 #define RB_FOREACH_REVERSE(x, name, head) \ 479 for ((x) = RB_MAX(name, head); \ 480 (x) != NULL; \ 481 (x) = name##_RB_PREV(x)) 482 483 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 484 for ((x) = RB_MAX(name, head); \ 485 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ 486 (x) = (y)) 487 488 #endif /* _SYS_TREE_H_ */ 489