tree.h 25.1 KB
Newer Older
Cedric Roux's avatar
Cedric Roux committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
/*
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

26 27
#ifndef _SYS_TREE_H_
#define _SYS_TREE_H_
Cedric Roux's avatar
Cedric Roux committed
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

/*
 * This file defines data structures for different types of trees:
 * splay trees and red-black trees.
 *
 * A splay tree is a self-organizing data structure.  Every operation
 * on the tree causes a splay to happen.  The splay moves the requested
 * node to the root of the tree and partly rebalances it.
 *
 * This has the benefit that request locality causes faster lookups as
 * the requested nodes move to the top of the tree.  On the other hand,
 * every lookup causes memory writes.
 *
 * The Balance Theorem bounds the total access time for m operations
 * and n inserts on an initially empty tree as O((m + n)lg n).  The
 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
 *
 * A red-black tree is a binary search tree with the node color as an
 * extra attribute.  It fulfills a set of conditions:
47 48 49 50
 *  - every search path from the root to a leaf consists of the
 *    same number of black nodes,
 *  - each red node (except for the root) has a black parent,
 *  - each leaf node is black.
Cedric Roux's avatar
Cedric Roux committed
51 52 53 54 55
 *
 * Every operation on a red-black tree is bounded as O(lg n).
 * The maximum height of a red-black tree is 2lg (n+1).
 */

56 57 58
#define SPLAY_HEAD(name, type)            \
struct name {               \
  struct type *sph_root; /* root of the tree */     \
Cedric Roux's avatar
Cedric Roux committed
59 60
}

61 62
#define SPLAY_INITIALIZER(root)           \
  { NULL }
Cedric Roux's avatar
Cedric Roux committed
63

64 65
#define SPLAY_INIT(root) do {           \
  (root)->sph_root = NULL;          \
Cedric Roux's avatar
Cedric Roux committed
66 67
} while (0)

68 69 70 71
#define SPLAY_ENTRY(type)           \
struct {                \
  struct type *spe_left; /* left element */     \
  struct type *spe_right; /* right element */     \
Cedric Roux's avatar
Cedric Roux committed
72 73
}

74 75 76 77
#define SPLAY_LEFT(elm, field)    (elm)->field.spe_left
#define SPLAY_RIGHT(elm, field)   (elm)->field.spe_right
#define SPLAY_ROOT(head)    (head)->sph_root
#define SPLAY_EMPTY(head)   (SPLAY_ROOT(head) == NULL)
Cedric Roux's avatar
Cedric Roux committed
78 79

/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
80 81 82 83
#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {     \
  SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
  SPLAY_RIGHT(tmp, field) = (head)->sph_root;     \
  (head)->sph_root = tmp;           \
Cedric Roux's avatar
Cedric Roux committed
84
} while (0)
85 86 87 88 89

#define SPLAY_ROTATE_LEFT(head, tmp, field) do {      \
  SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
  SPLAY_LEFT(tmp, field) = (head)->sph_root;      \
  (head)->sph_root = tmp;           \
Cedric Roux's avatar
Cedric Roux committed
90 91
} while (0)

92 93 94 95
#define SPLAY_LINKLEFT(head, tmp, field) do {       \
  SPLAY_LEFT(tmp, field) = (head)->sph_root;      \
  tmp = (head)->sph_root;           \
  (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);   \
Cedric Roux's avatar
Cedric Roux committed
96 97
} while (0)

98 99 100 101
#define SPLAY_LINKRIGHT(head, tmp, field) do {        \
  SPLAY_RIGHT(tmp, field) = (head)->sph_root;     \
  tmp = (head)->sph_root;           \
  (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);  \
Cedric Roux's avatar
Cedric Roux committed
102 103
} while (0)

104 105 106 107 108
#define SPLAY_ASSEMBLE(head, node, left, right, field) do {   \
  SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
  SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
  SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
  SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
Cedric Roux's avatar
Cedric Roux committed
109 110 111 112
} while (0)

/* Generates prototypes and inline functions */

113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149
#define SPLAY_PROTOTYPE(name, type, field, cmp)       \
void name##_SPLAY(struct name *, struct type *);      \
void name##_SPLAY_MINMAX(struct name *, int);       \
struct type *name##_SPLAY_INSERT(struct name *, struct type *);   \
struct type *name##_SPLAY_REMOVE(struct name *, struct type *);   \
                  \
/* Finds the node with the same key as elm */       \
static __inline struct type *           \
name##_SPLAY_FIND(struct name *head, struct type *elm)      \
{                 \
  if (SPLAY_EMPTY(head))            \
    return(NULL);           \
  name##_SPLAY(head, elm);          \
  if ((cmp)(elm, (head)->sph_root) == 0)        \
    return (head->sph_root);        \
  return (NULL);              \
}                 \
                  \
static __inline struct type *           \
name##_SPLAY_NEXT(struct name *head, struct type *elm)      \
{                 \
  name##_SPLAY(head, elm);          \
  if (SPLAY_RIGHT(elm, field) != NULL) {        \
    elm = SPLAY_RIGHT(elm, field);        \
    while (SPLAY_LEFT(elm, field) != NULL) {    \
      elm = SPLAY_LEFT(elm, field);     \
    }             \
  } else                \
    elm = NULL;           \
  return (elm);             \
}                 \
                  \
static __inline struct type *           \
name##_SPLAY_MIN_MAX(struct name *head, int val)      \
{                 \
  name##_SPLAY_MINMAX(head, val);         \
        return (SPLAY_ROOT(head));          \
Cedric Roux's avatar
Cedric Roux committed
150 151 152 153 154
}

/* Main splay operation.
 * Moves node close to the key of elm to top
 */
155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205
#define SPLAY_GENERATE(name, type, field, cmp)        \
struct type *               \
name##_SPLAY_INSERT(struct name *head, struct type *elm)    \
{                 \
    if (SPLAY_EMPTY(head)) {            \
      SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;  \
    } else {                \
      int __comp;             \
      name##_SPLAY(head, elm);          \
      __comp = (cmp)(elm, (head)->sph_root);      \
      if(__comp < 0) {            \
        SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
        SPLAY_RIGHT(elm, field) = (head)->sph_root;   \
        SPLAY_LEFT((head)->sph_root, field) = NULL;   \
      } else if (__comp > 0) {          \
        SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
        SPLAY_LEFT(elm, field) = (head)->sph_root;    \
        SPLAY_RIGHT((head)->sph_root, field) = NULL;  \
      } else              \
        return ((head)->sph_root);        \
    }                 \
    (head)->sph_root = (elm);           \
    return (NULL);              \
}                 \
                  \
struct type *               \
name##_SPLAY_REMOVE(struct name *head, struct type *elm)    \
{                 \
  struct type *__tmp;           \
  if (SPLAY_EMPTY(head))            \
    return (NULL);            \
  name##_SPLAY(head, elm);          \
  if ((cmp)(elm, (head)->sph_root) == 0) {      \
    if (SPLAY_LEFT((head)->sph_root, field) == NULL) {  \
      (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
    } else {            \
      __tmp = SPLAY_RIGHT((head)->sph_root, field); \
      (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
      name##_SPLAY(head, elm);      \
      SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
    }             \
    return (elm);           \
  }               \
  return (NULL);              \
}                 \
                  \
void                  \
name##_SPLAY(struct name *head, struct type *elm)     \
{                 \
  struct type __node, *__left, *__right, *__tmp;      \
  int __comp;             \
Cedric Roux's avatar
Cedric Roux committed
206
\
207 208
  SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
  __left = __right = &__node;         \
Cedric Roux's avatar
Cedric Roux committed
209
\
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238
  while ((__comp = (cmp)(elm, (head)->sph_root))) {   \
    if (__comp < 0) {         \
      __tmp = SPLAY_LEFT((head)->sph_root, field);  \
      if (__tmp == NULL)        \
        break;          \
      if ((cmp)(elm, __tmp) < 0){     \
        SPLAY_ROTATE_RIGHT(head, __tmp, field); \
        if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
          break;        \
      }           \
      SPLAY_LINKLEFT(head, __right, field);   \
    } else if (__comp > 0) {        \
      __tmp = SPLAY_RIGHT((head)->sph_root, field); \
      if (__tmp == NULL)        \
        break;          \
      if ((cmp)(elm, __tmp) > 0){     \
        SPLAY_ROTATE_LEFT(head, __tmp, field);  \
        if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
          break;        \
      }           \
      SPLAY_LINKRIGHT(head, __left, field);   \
    }             \
  }               \
  SPLAY_ASSEMBLE(head, &__node, __left, __right, field);    \
}                 \
                  \
/* Splay with either the minimum or the maximum element     \
 * Used to find minimum or maximum element in tree.     \
 */                 \
Cedric Roux's avatar
Cedric Roux committed
239
void name##_SPLAY_MINMAX(struct name *head, int __comp) \
240 241
{                 \
  struct type __node, *__left, *__right, *__tmp;      \
Cedric Roux's avatar
Cedric Roux committed
242
\
243 244
  SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
  __left = __right = &__node;         \
Cedric Roux's avatar
Cedric Roux committed
245
\
246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
  while (1) {             \
    if (__comp < 0) {         \
      __tmp = SPLAY_LEFT((head)->sph_root, field);  \
      if (__tmp == NULL)        \
        break;          \
      if (__comp < 0){        \
        SPLAY_ROTATE_RIGHT(head, __tmp, field); \
        if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
          break;        \
      }           \
      SPLAY_LINKLEFT(head, __right, field);   \
    } else if (__comp > 0) {        \
      __tmp = SPLAY_RIGHT((head)->sph_root, field); \
      if (__tmp == NULL)        \
        break;          \
      if (__comp > 0) {       \
        SPLAY_ROTATE_LEFT(head, __tmp, field);  \
        if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
          break;        \
      }           \
      SPLAY_LINKRIGHT(head, __left, field);   \
    }             \
  }               \
  SPLAY_ASSEMBLE(head, &__node, __left, __right, field);    \
Cedric Roux's avatar
Cedric Roux committed
270 271
}

272 273
#define SPLAY_NEGINF  -1
#define SPLAY_INF 1
Cedric Roux's avatar
Cedric Roux committed
274

275 276 277 278 279 280 281 282
#define SPLAY_INSERT(name, x, y)  name##_SPLAY_INSERT(x, y)
#define SPLAY_REMOVE(name, x, y)  name##_SPLAY_REMOVE(x, y)
#define SPLAY_FIND(name, x, y)    name##_SPLAY_FIND(x, y)
#define SPLAY_NEXT(name, x, y)    name##_SPLAY_NEXT(x, y)
#define SPLAY_MIN(name, x)    (SPLAY_EMPTY(x) ? NULL  \
          : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
#define SPLAY_MAX(name, x)    (SPLAY_EMPTY(x) ? NULL  \
          : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
Cedric Roux's avatar
Cedric Roux committed
283

284 285 286 287
#define SPLAY_FOREACH(x, name, head)          \
  for ((x) = SPLAY_MIN(name, head);       \
       (x) != NULL;           \
       (x) = SPLAY_NEXT(name, head, x))
Cedric Roux's avatar
Cedric Roux committed
288 289

/* Macros that define a red-back tree */
290 291 292
#define RB_HEAD(name, type)           \
struct name {               \
  struct type *rbh_root; /* root of the tree */     \
Cedric Roux's avatar
Cedric Roux committed
293 294
}

295 296
#define RB_INITIALIZER(root)            \
  { NULL }
Cedric Roux's avatar
Cedric Roux committed
297

298 299
#define RB_INIT(root) do {            \
  (root)->rbh_root = NULL;          \
Cedric Roux's avatar
Cedric Roux committed
300 301
} while (0)

302 303 304 305 306 307 308 309
#define RB_BLACK  0
#define RB_RED    1
#define RB_ENTRY(type)              \
struct {                \
  struct type *rbe_left;    /* left element */    \
  struct type *rbe_right;   /* right element */   \
  struct type *rbe_parent;  /* parent element */    \
  int rbe_color;      /* node color */    \
Cedric Roux's avatar
Cedric Roux committed
310 311
}

312 313 314 315 316 317 318 319 320 321 322
#define RB_LEFT(elm, field)   (elm)->field.rbe_left
#define RB_RIGHT(elm, field)    (elm)->field.rbe_right
#define RB_PARENT(elm, field)   (elm)->field.rbe_parent
#define RB_COLOR(elm, field)    (elm)->field.rbe_color
#define RB_ROOT(head)     (head)->rbh_root
#define RB_EMPTY(head)      (RB_ROOT(head) == NULL)

#define RB_SET(elm, parent, field) do {         \
  RB_PARENT(elm, field) = parent;         \
  RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;    \
  RB_COLOR(elm, field) = RB_RED;          \
Cedric Roux's avatar
Cedric Roux committed
323 324
} while (0)

325 326 327
#define RB_SET_BLACKRED(black, red, field) do {       \
  RB_COLOR(black, field) = RB_BLACK;        \
  RB_COLOR(red, field) = RB_RED;          \
Cedric Roux's avatar
Cedric Roux committed
328 329 330 331 332 333
} while (0)

#ifndef RB_AUGMENT
#define RB_AUGMENT(x)
#endif

334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351
#define RB_ROTATE_LEFT(head, elm, tmp, field) do {      \
  (tmp) = RB_RIGHT(elm, field);         \
  if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {   \
    RB_PARENT(RB_LEFT(tmp, field), field) = (elm);    \
  }               \
  RB_AUGMENT(elm);            \
  if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {    \
    if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
      RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
    else              \
      RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
  } else                \
    (head)->rbh_root = (tmp);       \
  RB_LEFT(tmp, field) = (elm);          \
  RB_PARENT(elm, field) = (tmp);          \
  RB_AUGMENT(tmp);            \
  if ((RB_PARENT(tmp, field)))          \
    RB_AUGMENT(RB_PARENT(tmp, field));      \
Cedric Roux's avatar
Cedric Roux committed
352 353
} while (0)

354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {     \
  (tmp) = RB_LEFT(elm, field);          \
  if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {   \
    RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);   \
  }               \
  RB_AUGMENT(elm);            \
  if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {    \
    if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
      RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
    else              \
      RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
  } else                \
    (head)->rbh_root = (tmp);       \
  RB_RIGHT(tmp, field) = (elm);         \
  RB_PARENT(elm, field) = (tmp);          \
  RB_AUGMENT(tmp);            \
  if ((RB_PARENT(tmp, field)))          \
    RB_AUGMENT(RB_PARENT(tmp, field));      \
Cedric Roux's avatar
Cedric Roux committed
372 373 374
} while (0)

/* Generates prototypes and inline functions */
375 376
#define RB_PROTOTYPE(name, type, field, cmp)        \
void name##_RB_INSERT_COLOR(struct name *, struct type *);  \
Cedric Roux's avatar
Cedric Roux committed
377
void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
378 379 380 381 382 383 384
struct type *name##_RB_REMOVE(struct name *, struct type *);    \
struct type *name##_RB_INSERT(struct name *, struct type *);    \
struct type *name##_RB_FIND(struct name *, struct type *);    \
struct type *name##_RB_NEXT(struct type *);       \
struct type *name##_RB_MINMAX(struct name *, int);      \
                  \
 
Cedric Roux's avatar
Cedric Roux committed
385 386 387
/* Main rb operation.
 * Moves node close to the key of elm to top
 */
388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
#define RB_GENERATE(name, type, field, cmp)       \
void                  \
name##_RB_INSERT_COLOR(struct name *head, struct type *elm)   \
{                 \
  struct type *parent, *gparent, *tmp;        \
  while ((parent = RB_PARENT(elm, field)) &&      \
      RB_COLOR(parent, field) == RB_RED) {      \
    gparent = RB_PARENT(parent, field);     \
    if (parent == RB_LEFT(gparent, field)) {    \
      tmp = RB_RIGHT(gparent, field);     \
      if (tmp && RB_COLOR(tmp, field) == RB_RED) {  \
        RB_COLOR(tmp, field) = RB_BLACK;  \
        RB_SET_BLACKRED(parent, gparent, field);\
        elm = gparent;        \
        continue;       \
      }           \
      if (RB_RIGHT(parent, field) == elm) {   \
        RB_ROTATE_LEFT(head, parent, tmp, field);\
        tmp = parent;       \
        parent = elm;       \
        elm = tmp;        \
      }           \
      RB_SET_BLACKRED(parent, gparent, field);  \
      RB_ROTATE_RIGHT(head, gparent, tmp, field); \
    } else {            \
      tmp = RB_LEFT(gparent, field);      \
      if (tmp && RB_COLOR(tmp, field) == RB_RED) {  \
        RB_COLOR(tmp, field) = RB_BLACK;  \
        RB_SET_BLACKRED(parent, gparent, field);\
        elm = gparent;        \
        continue;       \
      }           \
      if (RB_LEFT(parent, field) == elm) {    \
        RB_ROTATE_RIGHT(head, parent, tmp, field);\
        tmp = parent;       \
        parent = elm;       \
        elm = tmp;        \
      }           \
      RB_SET_BLACKRED(parent, gparent, field);  \
      RB_ROTATE_LEFT(head, gparent, tmp, field);  \
    }             \
  }               \
  RB_COLOR(head->rbh_root, field) = RB_BLACK;     \
}                 \
                  \
void                  \
Cedric Roux's avatar
Cedric Roux committed
434
name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601
{                 \
  struct type *tmp;           \
  while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
      elm != RB_ROOT(head)) {         \
    if (RB_LEFT(parent, field) == elm) {      \
      tmp = RB_RIGHT(parent, field);      \
      if (RB_COLOR(tmp, field) == RB_RED) {   \
        RB_SET_BLACKRED(tmp, parent, field);  \
        RB_ROTATE_LEFT(head, parent, tmp, field);\
        tmp = RB_RIGHT(parent, field);    \
      }           \
      if ((RB_LEFT(tmp, field) == NULL ||   \
          RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
          (RB_RIGHT(tmp, field) == NULL ||    \
          RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
        RB_COLOR(tmp, field) = RB_RED;    \
        elm = parent;       \
        parent = RB_PARENT(elm, field);   \
      } else {          \
        if (RB_RIGHT(tmp, field) == NULL || \
            RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
          struct type *oleft;   \
          if ((oleft = RB_LEFT(tmp, field)))\
            RB_COLOR(oleft, field) = RB_BLACK;\
          RB_COLOR(tmp, field) = RB_RED;  \
          RB_ROTATE_RIGHT(head, tmp, oleft, field);\
          tmp = RB_RIGHT(parent, field);  \
        }         \
        RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
        RB_COLOR(parent, field) = RB_BLACK; \
        if (RB_RIGHT(tmp, field))   \
          RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
        RB_ROTATE_LEFT(head, parent, tmp, field);\
        elm = RB_ROOT(head);      \
        break;          \
      }           \
    } else {            \
      tmp = RB_LEFT(parent, field);     \
      if (RB_COLOR(tmp, field) == RB_RED) {   \
        RB_SET_BLACKRED(tmp, parent, field);  \
        RB_ROTATE_RIGHT(head, parent, tmp, field);\
        tmp = RB_LEFT(parent, field);   \
      }           \
      if ((RB_LEFT(tmp, field) == NULL ||   \
          RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
          (RB_RIGHT(tmp, field) == NULL ||    \
          RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
        RB_COLOR(tmp, field) = RB_RED;    \
        elm = parent;       \
        parent = RB_PARENT(elm, field);   \
      } else {          \
        if (RB_LEFT(tmp, field) == NULL ||  \
            RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
          struct type *oright;    \
          if ((oright = RB_RIGHT(tmp, field)))\
            RB_COLOR(oright, field) = RB_BLACK;\
          RB_COLOR(tmp, field) = RB_RED;  \
          RB_ROTATE_LEFT(head, tmp, oright, field);\
          tmp = RB_LEFT(parent, field); \
        }         \
        RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
        RB_COLOR(parent, field) = RB_BLACK; \
        if (RB_LEFT(tmp, field))    \
          RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
        RB_ROTATE_RIGHT(head, parent, tmp, field);\
        elm = RB_ROOT(head);      \
        break;          \
      }           \
    }             \
  }               \
  if (elm)              \
    RB_COLOR(elm, field) = RB_BLACK;      \
}                 \
                  \
struct type *               \
name##_RB_REMOVE(struct name *head, struct type *elm)     \
{                 \
  struct type *child, *parent, *old = elm;      \
  int color;              \
  if (RB_LEFT(elm, field) == NULL)        \
    child = RB_RIGHT(elm, field);       \
  else if (RB_RIGHT(elm, field) == NULL)        \
    child = RB_LEFT(elm, field);        \
  else {                \
    struct type *left;          \
    elm = RB_RIGHT(elm, field);       \
    while ((left = RB_LEFT(elm, field)))      \
      elm = left;         \
    child = RB_RIGHT(elm, field);       \
    parent = RB_PARENT(elm, field);       \
    color = RB_COLOR(elm, field);       \
    if (child)            \
      RB_PARENT(child, field) = parent;   \
    if (parent) {           \
      if (RB_LEFT(parent, field) == elm)    \
        RB_LEFT(parent, field) = child;   \
      else            \
        RB_RIGHT(parent, field) = child;  \
      RB_AUGMENT(parent);       \
    } else              \
      RB_ROOT(head) = child;        \
    if (RB_PARENT(elm, field) == old)     \
      parent = elm;         \
    (elm)->field = (old)->field;        \
    if (RB_PARENT(old, field)) {        \
      if (RB_LEFT(RB_PARENT(old, field), field) == old)\
        RB_LEFT(RB_PARENT(old, field), field) = elm;\
      else            \
        RB_RIGHT(RB_PARENT(old, field), field) = elm;\
      RB_AUGMENT(RB_PARENT(old, field));    \
    } else              \
      RB_ROOT(head) = elm;        \
    RB_PARENT(RB_LEFT(old, field), field) = elm;    \
    if (RB_RIGHT(old, field))       \
      RB_PARENT(RB_RIGHT(old, field), field) = elm; \
    if (parent) {           \
      left = parent;          \
      do {            \
        RB_AUGMENT(left);     \
      } while ((left = RB_PARENT(left, field)));  \
    }             \
    goto color;           \
  }               \
  parent = RB_PARENT(elm, field);         \
  color = RB_COLOR(elm, field);         \
  if (child)              \
    RB_PARENT(child, field) = parent;     \
  if (parent) {             \
    if (RB_LEFT(parent, field) == elm)      \
      RB_LEFT(parent, field) = child;     \
    else              \
      RB_RIGHT(parent, field) = child;    \
    RB_AUGMENT(parent);         \
  } else                \
    RB_ROOT(head) = child;          \
color:                  \
  if (color == RB_BLACK)            \
    name##_RB_REMOVE_COLOR(head, parent, child);    \
  return (old);             \
}                 \
                  \
/* Inserts a node into the RB tree */         \
struct type *               \
name##_RB_INSERT(struct name *head, struct type *elm)     \
{                 \
  struct type *tmp;           \
  struct type *parent = NULL;         \
  int comp = 0;             \
  tmp = RB_ROOT(head);            \
  while (tmp) {             \
    parent = tmp;           \
    comp = (cmp)(elm, parent);        \
    if (comp < 0)           \
      tmp = RB_LEFT(tmp, field);      \
    else if (comp > 0)          \
      tmp = RB_RIGHT(tmp, field);     \
    else              \
      return (tmp);         \
  }               \
  RB_SET(elm, parent, field);         \
  if (parent != NULL) {           \
    if (comp < 0)           \
      RB_LEFT(parent, field) = elm;     \
    else              \
      RB_RIGHT(parent, field) = elm;      \
    RB_AUGMENT(parent);         \
  } else                \
Cedric Roux's avatar
Cedric Roux committed
602
  {                                                                     \
603
    RB_ROOT(head) = elm;          \
Cedric Roux's avatar
Cedric Roux committed
604
  }                                                                     \
605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660
  name##_RB_INSERT_COLOR(head, elm);        \
  return (NULL);              \
}                 \
                  \
/* Finds the node with the same key as elm */       \
struct type *               \
name##_RB_FIND(struct name *head, struct type *elm)     \
{                 \
  struct type *tmp = RB_ROOT(head);       \
  int comp;             \
  while (tmp) {             \
    comp = cmp(elm, tmp);         \
    if (comp < 0)           \
      tmp = RB_LEFT(tmp, field);      \
    else if (comp > 0)          \
      tmp = RB_RIGHT(tmp, field);     \
    else              \
      return (tmp);         \
  }               \
  return (NULL);              \
}                 \
                  \
struct type *               \
name##_RB_NEXT(struct type *elm)          \
{                 \
  if (RB_RIGHT(elm, field)) {         \
    elm = RB_RIGHT(elm, field);       \
    while (RB_LEFT(elm, field))       \
      elm = RB_LEFT(elm, field);      \
  } else {              \
    if (RB_PARENT(elm, field) &&        \
        (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
      elm = RB_PARENT(elm, field);      \
    else {              \
      while (RB_PARENT(elm, field) &&     \
          (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
        elm = RB_PARENT(elm, field);    \
      elm = RB_PARENT(elm, field);      \
    }             \
  }               \
  return (elm);             \
}                 \
                  \
struct type *               \
name##_RB_MINMAX(struct name *head, int val)        \
{                 \
  struct type *tmp = RB_ROOT(head);       \
  struct type *parent = NULL;         \
  while (tmp) {             \
    parent = tmp;           \
    if (val < 0)            \
      tmp = RB_LEFT(tmp, field);      \
    else              \
      tmp = RB_RIGHT(tmp, field);     \
  }               \
  return (parent);            \
Cedric Roux's avatar
Cedric Roux committed
661 662
}

663 664
#define RB_NEGINF -1
#define RB_INF  1
Cedric Roux's avatar
Cedric Roux committed
665

666 667 668 669 670 671
#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
#define RB_MIN(name, x)   name##_RB_MINMAX(x, RB_NEGINF)
#define RB_MAX(name, x)   name##_RB_MINMAX(x, RB_INF)
Cedric Roux's avatar
Cedric Roux committed
672

673 674 675 676
#define RB_FOREACH(x, name, head)         \
  for ((x) = RB_MIN(name, head);          \
       (x) != NULL;           \
       (x) = name##_RB_NEXT(x))
Cedric Roux's avatar
Cedric Roux committed
677

678
#endif  /* _SYS_TREE_H_ */