lib/redblack.h

   1 /*
   2  *      Red-black trees
   3  *
   4  *      (c) 2002, Robert Spalek <robert@ucw.cz>
   5  *
   6  *      Skeleton based on hash-tables by:
   7  *
   8  *      (c) 2002, Martin Mares <mj@ucw.cz>
   9  *
  10  */
  11
  12 /*
  13  * Data structure description:
  14  *
  15  * A red-black tree is a binary search tree, where records are stored
  16  * in nodes (may be also leaves).  Every node has a colour.  The
  17  * following restrictions hold:
  18  *
  19  * - a parent of a red node is black
  20  * - every path from the root to a node with less than 2 children
  21  *   contains the same number of black nodes
  22  *
  23  * A usual interpretation is, that leaves are intervals between records
  24  * and contain no data.  Every leaf is black.  This is equivalent, but
  25  * saves the space.
  26  */
  27
  28 /*
  29  *  This is not a normal header file, it's a generator of red-black trees.
  30  *  Each time you include it with parameters set in the corresponding
  31  *  preprocessor macros, it generates a tree structure with the parameters
  32  *  given.
  33  *
  34  *  You need to specify:
  35  *
  36  *  TREE_NODE           data type where a node dwells (usually a struct).
  37  *  TREE_PREFIX(x)      macro to add a name prefix (used on all global names
  38  *                      defined by the tree generator).
  39  *
  40  *  Then decide on type of keys:
  41  *
  42  *  TREE_KEY_ATOMIC=f   use node->f as a key of an atomic type (i.e.,
  43  *                      a type which can be compared using '>', `==', and '<')
  44  *                      & TREE_ATOMIC_TYPE (defaults to int).
  45  *  | TREE_KEY_STRING=f use node->f as a string key, allocated
  46  *                      separately from the rest of the node.
  47  *  | TREE_KEY_ENDSTRING=f use node->f as a string key, allocated
  48  *                      automatically at the end of the node struct
  49  *                      (to be declared as "char f[1]" at the end).
  50  *  | TREE_KEY_COMPLEX  use a multi-component key; as the name suggests,
  51  *                      the passing of parameters is a bit complex then.
  52  *                      The TREE_KEY_COMPLEX(x) macro should expand to
  53  *                      `x k1, x k2, ... x kn' and you should also define:
  54  *    & TREE_KEY_DECL   declaration of function parameters in which key
  55  *                      should be passed to all tree operations.
  56  *                      That is, `type1 k1, type2 k2, ... typen kn'.
  57  *                      With complex keys, TREE_GIVE_CMP is mandatory.
  58  *
  59  *  Then specify what operations you request (all names are automatically
  60  *  prefixed by calling TREE_PREFIX):
  61  *
  62  *  <always defined>    init() -- initialize the tree.
  63  *  TREE_WANT_CLEANUP   cleanup() -- deallocate the tree.
  64  *  TREE_WANT_FIND      node *find(key) -- find first node with the specified
  65  *                      key, return NULL if no such node exists.
  66  *  TREE_WANT_FIND_NEXT node *find(node *start) -- find next node with the
  67  *                      specified key, return NULL if no such node exists.
  68  *  TREE_WANT_SEARCH    node *search(key) -- find the node with the specified
  69  *                      or, if it does not exist, the nearest one.
  70  *  TREE_WANT_ADJACENT  node *adjacent(node *) -- finds next/previous node.
  71  *  TREE_WANT_NEW       node *new(key) -- create new node with given key.
  72  *                      If it already exists, it is created as the last one.
  73  *  TREE_WANT_LOOKUP    node *lookup(key) -- find node with given key,
  74  *                      if it doesn't exist, create it. Defining
  75  *                      TREE_GIVE_INIT_DATA is strongly recommended.
  76  *  TREE_WANT_DELETE    int delete(key) -- delete and deallocate node
  77  *                      with given key. Returns success.
  78  *  TREE_WANT_REMOVE    remove(node *) -- delete and deallocate given node.
  79  *
  80  *  TREE_WANT_DUMP      dump() -- dumps the whole tree to stdout
  81  *
  82  *  You can also supply several functions:
  83  *
  84  *  TREE_GIVE_CMP       int cmp(key1, key2) -- return -1, 0, and 1 according to
  85  *                      the relation of keys.  By default, we use <, ==, > for
  86  *                      atomic types and either strcmp or strcasecmp for
  87  *                      strings.
  88  *  TREE_GIVE_EXTRA_SIZE int extra_size(key) -- returns how many bytes after the
  89  *                      node should be allocated for dynamic data. Default=0
  90  *                      or length of the string with TREE_KEY_ENDSTRING.
  91  *  TREE_GIVE_INIT_KEY  void init_key(node *,key) -- initialize key in a newly
  92  *                      created node. Defaults: assignment for atomic keys
  93  *                      and static strings, strcpy for end-allocated strings.
  94  *  TREE_GIVE_INIT_DATA void init_data(node *) -- initialize data fields in a
  95  *                      newly created node. Very useful for lookup operations.
  96  *  TREE_GIVE_ALLOC     void *alloc(unsigned int size) -- allocate space for
  97  *                      a node. Default is either normal or pooled allocation
  98  *                      depending on whether we want deletions.
  99  *                      void free(void *) -- the converse.
 100  *
 101  *  ... and a couple of extra parameters:
 102  *
 103  *  TREE_NOCASE         string comparisons should be case-insensitive.
 104  *  TREE_ATOMIC_TYPE=t  Atomic values are of type `t' instead of int.
 105  *  TREE_USE_POOL=pool  Allocate all nodes from given mempool.
 106  *                      Collides with delete/remove functions.
 107  *  TREE_STATIC         Functions are declared as static.
 108  *  TREE_CONSERVE_SPACE Use as little space as possible at the price of a
 109  *                      little slowdown.
 110  *  TREE_MAX_DEPTH      Maximal depth of a tree (for stack allocation).
 111  *
 112  *  If you set TREE_WANT_ITERATOR, you also get a iterator macro at no
 113  *  extra charge:
 114  *
 115  *  TREE_FOR_ALL(tree_prefix, tree_pointer, variable)
 116  *    {
 117  *      // node *variable gets declared automatically
 118  *      do_something_with_node(variable);
 119  *      // use TREE_BREAK and TREE_CONTINUE instead of break and continue
 120  *      // you must not alter contents of the tree here
 121  *    }
 122  *  TREE_END_FOR;
 123  *
 124  *  Then include <lib/redblack.h> and voila, you have a tree suiting all your
 125  *  needs (at least those which you've revealed :) ).
 126  *
 127  *  After including this file, all parameter macros are automatically
 128  *  undef'd.
 129  */
 130
 131 #include <string.h>
 132
 133 #if !defined(TREE_NODE) || !defined(TREE_PREFIX)
 134 #error Some of the mandatory configuration macros are missing.
 135 #endif
 136
 137 #define P(x) TREE_PREFIX(x)
 138
 139 /* Declare buckets and the tree.  */
 140
 141 typedef TREE_NODE P(node);
 142
 143 #if defined(TREE_WANT_FIND_NEXT) || defined(TREE_WANT_ADJACENT) || defined(TREE_WANT_ITERATOR) || defined(TREE_WANT_REMOVE)
 144 #       define TREE_STORE_PARENT
 145 #endif
 146
 147 typedef struct P(bucket) {
 148         struct P(bucket) *son[2];
 149 #ifdef TREE_STORE_PARENT
 150         struct P(bucket) *parent;
 151 #endif
 152 #if !defined(TREE_CONSERVE_SPACE) && (defined(TREE_GIVE_EXTRA_SIZE) || defined(TREE_KEY_ENDSTRING))
 153         uns red_flag:1;
 154 #endif
 155         P(node) n;
 156 #if !defined(TREE_CONSERVE_SPACE) && !defined(TREE_GIVE_EXTRA_SIZE) && !defined(TREE_KEY_ENDSTRING)
 157         uns red_flag:1;
 158 #endif
 159 } P(bucket);
 160
 161 struct P(tree) {
 162         uns count;
 163         uns height;                     /* of black nodes */
 164         P(bucket) *root;
 165 };
 166
 167 typedef struct P(stack_entry) {
 168         P(bucket) *buck;
 169         uns son;
 170 } P(stack_entry);
 171
 172 #define T struct P(tree)
 173
 174 /* Preset parameters */
 175
 176 #if defined(TREE_KEY_ATOMIC)
 177
 178 #define TREE_KEY(x) x TREE_KEY_ATOMIC
 179
 180 #ifndef TREE_ATOMIC_TYPE
 181 #       define TREE_ATOMIC_TYPE int
 182 #endif
 183 #define TREE_KEY_DECL TREE_ATOMIC_TYPE TREE_KEY()
 184
 185 #ifndef TREE_GIVE_CMP
 186 #       define TREE_GIVE_CMP
 187         static inline int P(cmp) (TREE_ATOMIC_TYPE x, TREE_ATOMIC_TYPE y)
 188         {
 189                 if (x < y)
 190                         return -1;
 191                 else if (x > y)
 192                         return 1;
 193                 else
 194                         return 0;
 195         }
 196 #endif
 197
 198 #ifndef TREE_GIVE_INIT_KEY
 199 #       define TREE_GIVE_INIT_KEY
 200         static inline void P(init_key) (P(node) *n, TREE_ATOMIC_TYPE k)
 201         { TREE_KEY(n->) = k; }
 202 #endif
 203
 204 #elif defined(TREE_KEY_STRING) || defined(TREE_KEY_ENDSTRING)
 205
 206 #ifdef TREE_KEY_STRING
 207 #       define TREE_KEY(x) x TREE_KEY_STRING
 208 #       ifndef TREE_GIVE_INIT_KEY
 209 #               define TREE_GIVE_INIT_KEY
 210                 static inline void P(init_key) (P(node) *n, char *k)
 211                 { TREE_KEY(n->) = k; }
 212 #       endif
 213 #else
 214 #       define TREE_KEY(x) x TREE_KEY_ENDSTRING
 215 #       define TREE_GIVE_EXTRA_SIZE
 216         static inline int P(extra_size) (char *k)
 217         { return strlen(k); }
 218 #       ifndef TREE_GIVE_INIT_KEY
 219 #               define TREE_GIVE_INIT_KEY
 220                 static inline void P(init_key) (P(node) *n, char *k)
 221                 { strcpy(TREE_KEY(n->), k); }
 222 #       endif
 223 #endif
 224 #define TREE_KEY_DECL char *TREE_KEY()
 225
 226 #ifndef TREE_GIVE_CMP
 227 #       define TREE_GIVE_CMP
 228         static inline int P(cmp) (char *x, char *y)
 229         {
 230 #               ifdef TREE_NOCASE
 231                         return strcasecmp(x,y);
 232 #               else
 233                         return strcmp(x,y);
 234 #               endif
 235         }
 236 #endif
 237
 238 #elif defined(TREE_KEY_COMPLEX)
 239
 240 #define TREE_KEY(x) TREE_KEY_COMPLEX(x)
 241
 242 #else
 243 #error You forgot to set the tree key type.
 244 #endif
 245
 246 #ifndef TREE_CONSERVE_SPACE
 247         static inline uns P(red_flag) (P(bucket) *node)
 248         { return node->red_flag; }
 249         static inline void P(set_red_flag) (P(bucket) *node, uns flag)
 250         { node->red_flag = flag; }
 251         static inline P(bucket) * P(tree_son) (P(bucket) *node, uns id)
 252         { return node->son[id]; }
 253         static inline void P(set_tree_son) (P(bucket) *node, uns id, P(bucket) *son)
 254         { node->son[id] = son; }
 255 #else
 256         /* Pointers are aligned, hence we can use lower bits.  */
 257         static inline uns P(red_flag) (P(bucket) *node)
 258         { return ((long) node->son[0]) & 1L; }
 259         static inline void P(set_red_flag) (P(bucket) *node, uns flag)
 260         { (long) node->son[0] = (((long) node->son[0]) & ~1L) | (flag & 1L); }
 261         static inline P(bucket) * P(tree_son) (P(bucket) *node, uns id)
 262         { return (void *) (((long) node->son[id]) & ~1L); }
 263         static inline void P(set_tree_son) (P(bucket) *node, uns id, P(bucket) *son)
 264         { node->son[id] = (void *) ((long) son | (((long) node->son[id]) & 1L) ); }
 265 #endif
 266
 267 /* Defaults for missing parameters.  */
 268
 269 #ifndef TREE_GIVE_CMP
 270 #error Unable to determine how to compare two keys.
 271 #endif
 272
 273 #ifdef TREE_GIVE_EXTRA_SIZE
 274 /* This trickery is needed to avoid `unused parameter' warnings */
 275 #       define TREE_EXTRA_SIZE P(extra_size)
 276 #else
 277 /*
 278  *  Beware, C macros are expanded iteratively, not recursively,
 279  *  hence we get only a _single_ argument, although the expansion
 280  *  of TREE_KEY contains commas.
 281  */
 282 #       define TREE_EXTRA_SIZE(x) 0
 283 #endif
 284
 285 #ifndef TREE_GIVE_INIT_KEY
 286 #       error Unable to determine how to initialize keys.
 287 #endif
 288
 289 #ifndef TREE_GIVE_INIT_DATA
 290 static inline void P(init_data) (P(node) *n UNUSED)
 291 {
 292 }
 293 #endif
 294
 295 #include <stdlib.h>
 296
 297 #ifndef TREE_GIVE_ALLOC
 298 #       ifdef TREE_USE_POOL
 299                 static inline void * P(alloc) (unsigned int size)
 300                 { return mp_alloc_fast(TREE_USE_POOL, size); }
 301 #               define TREE_SAFE_FREE(x)
 302 #       else
 303                 static inline void * P(alloc) (unsigned int size)
 304                 { return xmalloc(size); }
 305
 306                 static inline void P(free) (void *x)
 307                 { xfree(x); }
 308 #       endif
 309 #endif
 310
 311 #ifndef TREE_SAFE_FREE
 312 #       define TREE_SAFE_FREE(x)        P(free) (x)
 313 #endif
 314
 315 #ifdef TREE_STATIC
 316 #       define STATIC static
 317 #else
 318 #       define STATIC
 319 #endif
 320
 321 #ifndef TREE_MAX_DEPTH
 322 #       define TREE_MAX_DEPTH 64
 323 #endif
 324
 325 /* Now the operations */
 326
 327 STATIC void P(init) (T *t)
 328 {
 329         t->count = t->height = 0;
 330         t->root = NULL;
 331 }
 332
 333 #ifdef TREE_WANT_CLEANUP
 334 static void P(cleanup_subtree) (T *t, P(bucket) *node)
 335 {
 336         if (!node)
 337                 return;
 338         P(cleanup_subtree) (t, P(tree_son) (node, 0));
 339         P(cleanup_subtree) (t, P(tree_son) (node, 1));
 340         P(free) (node);
 341         t->count--;
 342 }
 343
 344 STATIC void P(cleanup) (T *t)
 345 {
 346         P(cleanup_subtree) (t, t->root);
 347         ASSERT(!t->count);
 348         t->height = 0;
 349 }
 350 #endif
 351
 352 static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *node, TREE_KEY_DECL, uns son_id)
 353 {
 354         uns i;
 355         stack[0].buck = node;
 356         for (i=0; stack[i].buck; i++)
 357         {
 358                 int cmp;
 359                 cmp = P(cmp) (TREE_KEY(), TREE_KEY(stack[i].buck->n.));
 360                 if (cmp == 0)
 361                         break;
 362                 else if (cmp < 0)
 363                         stack[i].son = 0;
 364                 else
 365                         stack[i].son = 1;
 366                 ASSERT(i+1 < max_depth);
 367                 stack[i+1].buck = P(tree_son) (stack[i].buck, stack[i].son);
 368         }
 369 #ifdef TREE_WANT_FIND_NEXT
 370         if (stack[i].buck)
 371         {
 372                 uns idx;
 373                 /* Find first/last of equal keys according to son_id.  */
 374                 idx = P(fill_stack) (stack+i+1, max_depth-i-1,
 375                         P(tree_son) (stack[i].buck, son_id), TREE_KEY(), son_id);
 376                 if (stack[i+1+idx].buck)
 377                 {
 378                         stack[i].son = son_id;
 379                         i = i+1+idx;
 380                 }
 381         }
 382 #endif
 383         stack[i].son = 10;
 384         return i;
 385 }
 386
 387 #if defined(TREE_WANT_FIND) || defined(TREE_WANT_LOOKUP)
 388 STATIC P(node) * P(find) (T *t, TREE_KEY_DECL)
 389 {
 390         P(stack_entry) stack[TREE_MAX_DEPTH];
 391         uns depth;
 392         depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 0);
 393         return stack[depth].buck ? &stack[depth].buck->n : NULL;
 394 }
 395 #endif
 396
 397 #ifdef TREE_STORE_PARENT
 398 STATIC P(node) * P(adjacent) (P(node) *start, uns direction)
 399 {
 400         P(bucket) *node = SKIP_BACK(P(bucket), n, start);
 401         P(bucket) *next = P(tree_son) (node, direction);
 402         if (next)
 403         {
 404                 while (1)
 405                 {
 406                         node = P(tree_son) (next, 1 - direction);
 407                         if (!node)
 408                                 break;
 409                         next = node;
 410                 }
 411         }
 412         else
 413         {
 414                 next = node->parent;
 415                 while (next && node == P(tree_son) (next, direction))
 416                 {
 417                         node = next;
 418                         next = node->parent;
 419                 }
 420                 if (!next)
 421                         return NULL;
 422                 ASSERT(node == P(tree_son) (next, 1 - direction));
 423         }
 424         return &next->n;
 425 }
 426 #endif
 427
 428 #if defined(TREE_WANT_FIND_NEXT) || defined(TREE_WANT_DELETE) || defined(TREE_WANT_REMOVE)
 429 static int P(find_next_node) (P(stack_entry) *stack, uns max_depth, uns direction)
 430 {
 431         uns depth = 0;
 432         if (stack[0].buck)
 433         {
 434                 ASSERT(depth+1 < max_depth);
 435                 stack[depth].son = direction;
 436                 stack[depth+1].buck = P(tree_son) (stack[depth].buck, direction);
 437                 depth++;
 438                 while (stack[depth].buck)
 439                 {
 440                         ASSERT(depth+1 < max_depth);
 441                         stack[depth].son = 1 - direction;
 442                         stack[depth+1].buck = P(tree_son) (stack[depth].buck, 1 - direction);
 443                         depth++;
 444                 }
 445         }
 446         return depth;
 447 }
 448 #endif
 449
 450 #ifdef TREE_WANT_FIND_NEXT
 451 STATIC P(node) * P(find_next) (P(node) *start)
 452 {
 453         P(node) *next = P(adjacent) (start, 1);
 454         if (next && P(cmp) (TREE_KEY(start->), TREE_KEY(next->)) == 0)
 455                 return next;
 456         else
 457                 return NULL;
 458
 459 }
 460 #endif
 461
 462 #ifdef TREE_WANT_SEARCH
 463 STATIC P(node) * P(search) (T *t, TREE_KEY_DECL)
 464 {
 465         P(stack_entry) stack[TREE_MAX_DEPTH];
 466         uns depth;
 467         depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 0);
 468         if (!stack[depth].buck)
 469         {
 470                 if (depth > 0)
 471                         depth--;
 472                 else
 473                         return NULL;
 474         }
 475         return &stack[depth].buck->n;
 476 }
 477 #endif
 478
 479 //#define TRACE(txt...) do { printf(txt); fflush(stdout); } while (0)
 480 #define TRACE(txt...)
 481
 482 static inline P(bucket) * P(rotation) (P(bucket) *node, uns son_id)
 483 {
 484         /* Destroys red_flag's in node, son.  Returns new root.  */
 485         P(bucket) *son = P(tree_son) (node, son_id);
 486         TRACE("Rotation (node %d, son %d), direction %d\n", node->n.key, son->n.key, son_id);
 487         node->son[son_id] = P(tree_son) (son, 1-son_id);
 488         son->son[1-son_id] = node;
 489 #ifdef TREE_STORE_PARENT
 490         if (node->son[son_id])
 491                 node->son[son_id]->parent = node;
 492         son->parent = node->parent;
 493         node->parent = son;
 494 #endif
 495         return son;
 496 }
 497
 498 static void P(rotate_after_insert) (T *t, P(stack_entry) *stack, uns depth)
 499 {
 500         P(bucket) *node;
 501         P(bucket) *parent, *grand, *uncle;
 502         int s1, s2;
 503 try_it_again:
 504         node = stack[depth].buck;
 505         ASSERT(P(red_flag) (node));
 506         /* At this moment, node became red.  The paths sum have
 507          * been preserved, but we have to check the parental
 508          * condition.  */
 509         if (depth == 0)
 510         {
 511                 ASSERT(t->root == node);
 512                 return;
 513         }
 514         parent = stack[depth-1].buck;
 515         if (!P(red_flag) (parent))
 516                 return;
 517         if (depth == 1)
 518         {
 519                 ASSERT(t->root == parent);
 520                 P(set_red_flag) (parent, 0);
 521                 t->height++;
 522                 return;
 523         }
 524         grand = stack[depth-2].buck;
 525         ASSERT(!P(red_flag) (grand));
 526         /* The parent is also red, the grandparent exists and it
 527          * is black.  */
 528         s1 = stack[depth-1].son;
 529         s2 = stack[depth-2].son;
 530         uncle = P(tree_son) (grand, 1-s2);
 531         if (uncle && P(red_flag) (uncle))
 532         {
 533                 /* Red parent and uncle, black grandparent.
 534                  * Exchange and try another iteration. */
 535                 P(set_red_flag) (parent, 0);
 536                 P(set_red_flag) (uncle, 0);
 537                 P(set_red_flag) (grand, 1);
 538                 depth -= 2;
 539                 TRACE("Swapping colours (parent %d, uncle %d, grand %d), passing thru\n", parent->n.key, uncle->n.key, grand->n.key);
 540                 goto try_it_again;
 541         }
 542         /* Black uncle and grandparent, we need to rotate.  Test
 543          * the direction.  */
 544         if (s1 == s2)
 545         {
 546                 node = P(rotation) (grand, s2);
 547                 P(set_red_flag) (parent, 0);
 548                 P(set_red_flag) (grand, 1);
 549         }
 550         else
 551         {
 552                 grand->son[s2] = P(rotation) (parent, s1);
 553                 node = P(rotation) (grand, s2);
 554                 P(set_red_flag) (grand, 1);
 555                 P(set_red_flag) (parent, 1);
 556                 P(set_red_flag) (node, 0);
 557         }
 558         if (depth >= 3)
 559                 P(set_tree_son) (stack[depth-3].buck, stack[depth-3].son, node);
 560         else
 561                 t->root = node;
 562 }
 563
 564 #if defined(TREE_WANT_NEW) || defined(TREE_WANT_LOOKUP)
 565 STATIC P(node) * P(new) (T *t, TREE_KEY_DECL)
 566 {
 567         P(stack_entry) stack[TREE_MAX_DEPTH];
 568         P(bucket) *added;
 569         uns depth;
 570         depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 1);
 571 #ifdef TREE_WANT_FIND_NEXT
 572         /* It is the last found value, hence everything in the right subtree is
 573          * strongly _bigger_.  */
 574         depth += P(find_next_node) (stack+depth, TREE_MAX_DEPTH-depth, 1);
 575 #endif
 576         ASSERT(!stack[depth].buck);
 577         /* We are in a leaf, hence we can easily append a new leaf to it.  */
 578         added = P(alloc) (sizeof(struct P(bucket)) + TREE_EXTRA_SIZE(TREE_KEY()) );
 579         added->son[0] = added->son[1] = NULL;
 580         stack[depth].buck = added;
 581         if (depth > 0)
 582         {
 583 #ifdef TREE_STORE_PARENT
 584                 added->parent = stack[depth-1].buck;
 585 #endif
 586                 P(set_tree_son) (stack[depth-1].buck, stack[depth-1].son, added);
 587         }
 588         else
 589         {
 590 #ifdef TREE_STORE_PARENT
 591                 added->parent = NULL;
 592 #endif
 593                 t->root = added;
 594         }
 595         P(set_red_flag) (added, 1);     /* Set it red to not disturb the path sum.  */
 596         P(init_key) (&added->n, TREE_KEY());
 597         P(init_data) (&added->n);
 598         t->count++;
 599         /* Let us reorganize the red_flag's and the structure of the tree.  */
 600         P(rotate_after_insert) (t, stack, depth);
 601         return &added->n;
 602 }
 603 #endif
 604
 605 #ifdef TREE_WANT_LOOKUP
 606 STATIC P(node) * P(lookup) (T *t, TREE_KEY_DECL)
 607 {
 608         P(node) *node;
 609         node = P(find) (t, TREE_KEY());
 610         if (node)
 611                 return node;
 612         return P(new) (t, TREE_KEY());
 613 }
 614 #endif
 615
 616 #if defined(TREE_WANT_REMOVE) || defined(TREE_WANT_DELETE)
 617 static void P(rotate_after_delete) (T *t, P(stack_entry) *stack, int depth)
 618 {
 619         uns iteration = 0;
 620         P(bucket) *parent, *sibling, *instead;
 621         uns parent_red, del_son, sibl_red;
 622 missing_black:
 623         if (depth < 0)
 624         {
 625                 t->height--;
 626                 return;
 627         }
 628         parent = stack[depth].buck;
 629         parent_red = P(red_flag) (parent);
 630         del_son = stack[depth].son;
 631         /* For the 1st iteration: we have deleted parent->son[del_son], which
 632          * was a black node with no son.  Hence there is one mising black
 633          * vertex in that path, which we are going to fix now.
 634          *
 635          * For other iterations: in that path, there is also missing a black
 636          * node.  */
 637         if (!iteration)
 638                 ASSERT(!P(tree_son) (parent, del_son));
 639         sibling = P(tree_son) (parent, 1-del_son);
 640         ASSERT(sibling);
 641         sibl_red = P(red_flag) (sibling);
 642         instead = NULL;
 643         if (!sibl_red)
 644         {
 645                 P(bucket) *son[2];
 646                 uns red[2];
 647                 son[0] = P(tree_son) (sibling, 0);
 648                 son[1] = P(tree_son) (sibling, 1);
 649                 red[0] = son[0] ? P(red_flag) (son[0]) : 0;
 650                 red[1] = son[1] ? P(red_flag) (son[1]) : 0;
 651                 if (!red[0] && !red[1])
 652                 {
 653                         P(set_red_flag) (sibling, 1);
 654                         P(set_red_flag) (parent, 0);
 655                         if (parent_red)
 656                                 return;
 657                         else
 658                         {
 659                                 depth--;
 660                                 iteration++;
 661                                 TRACE("Swapping colours (parent %d, sibling %d), passing thru\n", parent->n.key, sibling->n.key);
 662                                 goto missing_black;
 663                         }
 664                 } else if (!red[del_son])
 665                 {
 666                         instead = P(rotation) (parent, 1-del_son);
 667                         P(set_red_flag) (instead, parent_red);
 668                         P(set_red_flag) (parent, 0);
 669                         P(set_red_flag) (son[1-del_son], 0);
 670                 } else /* red[del_son] */
 671                 {
 672                         parent->son[1-del_son] = P(rotation) (sibling, del_son);
 673                         instead = P(rotation) (parent, 1-del_son);
 674                         P(set_red_flag) (instead, parent_red);
 675                         P(set_red_flag) (parent, 0);
 676                         P(set_red_flag) (sibling, 0);
 677                 }
 678         } else /* sibl_red */
 679         {
 680                 P(bucket) *grand[2], *son;
 681                 uns red[2];
 682                 ASSERT(!parent_red);
 683                 son = P(tree_son) (sibling, del_son);
 684                 ASSERT(son && !P(red_flag) (son));
 685                 grand[0] = P(tree_son) (son, 0);
 686                 grand[1] = P(tree_son) (son, 1);
 687                 red[0] = grand[0] ? P(red_flag) (grand[0]) : 0;
 688                 red[1] = grand[1] ? P(red_flag) (grand[1]) : 0;
 689                 if (!red[0] && !red[1])
 690                 {
 691                         instead = P(rotation) (parent, 1-del_son);
 692                         P(set_red_flag) (instead, 0);
 693                         P(set_red_flag) (parent, 0);
 694                         P(set_red_flag) (son, 1);
 695                 }
 696                 else if (!red[del_son])
 697                 {
 698                         parent->son[1-del_son] = P(rotation) (sibling, del_son);
 699                         instead = P(rotation) (parent, 1-del_son);
 700                         P(set_red_flag) (instead, 0);
 701                         P(set_red_flag) (parent, 0);
 702                         P(set_red_flag) (sibling, 1);
 703                         P(set_red_flag) (grand[1-del_son], 0);
 704                 } else /* red[del_son] */
 705                 {
 706                         sibling->son[del_son] = P(rotation) (son, del_son);
 707                         parent->son[1-del_son] = P(rotation) (sibling, del_son);
 708                         instead = P(rotation) (parent, 1-del_son);
 709                         P(set_red_flag) (instead, 0);
 710                         P(set_red_flag) (parent, 0);
 711                         P(set_red_flag) (sibling, 1);
 712                         P(set_red_flag) (son, 0);
 713                 }
 714         }
 715         /* We have performed all desired rotations and need to store the new
 716          * pointer to the subtree.  */
 717         ASSERT(instead);
 718         if (depth > 0)
 719                 P(set_tree_son) (stack[depth-1].buck, stack[depth-1].son, instead);
 720         else
 721                 t->root = instead;
 722 }
 723
 724 static void P(remove_by_stack) (T *t, P(stack_entry) *stack, uns depth)
 725 {
 726         P(bucket) *node = stack[depth].buck;
 727         P(bucket) *son;
 728         uns i;
 729         for (i=0; i<depth; i++)
 730                 ASSERT(P(tree_son) (stack[i].buck, stack[i].son) == stack[i+1].buck);
 731         if (P(tree_son) (node, 0) && P(tree_son) (node, 1))
 732         {
 733                 P(bucket) *xchg;
 734                 uns flag_node, flag_xchg;
 735                 uns d = P(find_next_node) (stack+depth, TREE_MAX_DEPTH-depth, 1);
 736
 737                 ASSERT(d >= 2);
 738                 d--;
 739                 xchg = stack[depth+d].buck;
 740                 flag_node = P(red_flag) (node);
 741                 flag_xchg = P(red_flag) (xchg);
 742                 ASSERT(!P(tree_son) (xchg, 0));
 743                 son = P(tree_son) (xchg, 1);
 744                 stack[depth].buck = xchg;       /* Magic iff d == 1.  */
 745                 stack[depth+d].buck = node;
 746                 xchg->son[0] = P(tree_son) (node, 0);
 747                 xchg->son[1] = P(tree_son) (node, 1);
 748                 if (depth > 0)
 749                         P(set_tree_son) (stack[depth-1].buck, stack[depth-1].son, xchg);
 750                 else
 751                         t->root = xchg;
 752                 node->son[0] = NULL;
 753                 node->son[1] = son;
 754                 P(set_tree_son) (stack[depth+d-1].buck, stack[depth+d-1].son, node);
 755 #ifdef TREE_STORE_PARENT
 756                 xchg->parent = depth > 0 ? stack[depth-1].buck : NULL;
 757                 xchg->son[0]->parent = xchg;
 758                 xchg->son[1]->parent = xchg;
 759                 node->parent = stack[depth+d-1].buck;
 760                 if (son)
 761                         son->parent = node;
 762 #endif
 763                 P(set_red_flag) (xchg, flag_node);
 764                 P(set_red_flag) (node, flag_xchg);
 765                 depth += d;
 766         }
 767         else if (P(tree_son) (node, 0))
 768                 son = P(tree_son) (node, 0);
 769         else
 770                 son = P(tree_son) (node, 1);
 771         /* At this moment, stack[depth].buck == node and it has at most one son
 772          * and it is stored in the variable son.  */
 773         t->count--;
 774         if (depth > 0)
 775         {
 776                 P(set_tree_son) (stack[depth-1].buck, stack[depth-1].son, son);
 777 #ifdef TREE_STORE_PARENT
 778                 if (son)
 779                         son->parent = stack[depth-1].buck;
 780 #endif
 781         }
 782         else
 783         {
 784                 t->root = son;
 785 #ifdef TREE_STORE_PARENT
 786                 if (son)
 787                         son->parent = NULL;
 788 #endif
 789         }
 790         if (P(red_flag) (node))
 791         {
 792                 ASSERT(!son);
 793                 return;
 794         }
 795         TREE_SAFE_FREE(node);
 796         /* We have deleted a black node.  */
 797         if (son)
 798         {
 799                 ASSERT(P(red_flag) (son));
 800                 P(set_red_flag) (son, 0);
 801                 return;
 802         }
 803         P(rotate_after_delete) (t, stack, (int) depth - 1);
 804 }
 805 #endif
 806
 807 #ifdef TREE_WANT_REMOVE
 808 STATIC void P(remove) (T *t, P(node) *Node)
 809 {
 810         P(stack_entry) stack[TREE_MAX_DEPTH];
 811         P(bucket) *node = SKIP_BACK(P(bucket), n, Node);
 812         uns depth = 0, i;
 813         stack[0].buck = node;
 814         stack[0].son = 10;
 815         while (node->parent)
 816         {
 817                 depth++;
 818                 ASSERT(depth < TREE_MAX_DEPTH);
 819                 stack[depth].buck = node->parent;
 820                 stack[depth].son = P(tree_son) (node->parent, 0) == node ? 0 : 1;
 821                 node = node->parent;
 822         }
 823         for (i=0; i<(depth+1)/2; i++)
 824         {
 825                 P(stack_entry) tmp = stack[i];
 826                 stack[i] = stack[depth-i];
 827                 stack[depth-i] = tmp;
 828         }
 829         P(remove_by_stack) (t, stack, depth);
 830 }
 831 #endif
 832
 833 #ifdef TREE_WANT_DELETE
 834 STATIC int P(delete) (T *t, TREE_KEY_DECL)
 835 {
 836         P(stack_entry) stack[TREE_MAX_DEPTH];
 837         uns depth;
 838         depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 1);
 839         if (stack[depth].buck)
 840         {
 841                 P(remove_by_stack) (t, stack, depth);
 842                 return 1;
 843         }
 844         else
 845                 return 0;
 846 }
 847 #endif
 848
 849 #ifdef TREE_WANT_DUMP
 850 static void P(dump_subtree) (struct fastbuf *fb, T *t, P(bucket) *node, P(bucket) *parent, int cmp_res, int level, int black)
 851 {
 852         uns flag;
 853         int i;
 854         if (!node)
 855         {
 856                 ASSERT(black == t->height);
 857                 return;
 858         }
 859         flag = P(red_flag) (node);
 860 #ifdef TREE_STORE_PARENT
 861         ASSERT(node->parent == parent);
 862 #endif
 863         if (parent)
 864         {
 865                 ASSERT(!flag || !P(red_flag) (parent));
 866                 cmp_res *= P(cmp) (TREE_KEY(node->n.), TREE_KEY(parent->n.));
 867 #ifdef TREE_WANT_FIND_NEXT
 868                 ASSERT(cmp_res >= 0);
 869 #else
 870                 ASSERT(cmp_res > 0);
 871 #endif
 872         }
 873         P(dump_subtree) (fb, t, P(tree_son) (node, 0), node, -1, level+1, black + (1-flag));
 874         if (fb)
 875         {
 876                 char tmp[20];
 877                 for (i=0; i<level; i++)
 878                         bputs(fb, "  ");
 879                 sprintf(tmp, "L%d %c\t", level, flag ? 'R' : 'B');
 880                 bputs(fb, tmp);
 881                 P(dump_key) (fb, &node->n);
 882                 P(dump_data) (fb, &node->n);
 883                 bputs(fb, "\n");
 884         }
 885         P(dump_subtree) (fb, t, P(tree_son) (node, 1), node, +1, level+1, black + (1-flag));
 886 }
 887
 888 STATIC void P(dump) (struct fastbuf *fb, T *t)
 889 {
 890         if (fb)
 891         {
 892                 char tmp[50];
 893                 sprintf(tmp, "Tree of %d nodes and height %d\n", t->count, t->height);
 894                 bputs(fb, tmp);
 895         }
 896         P(dump_subtree) (fb, t, t->root, NULL, 0, 0, 0);
 897         if (fb)
 898         {
 899                 bputs(fb, "\n");
 900                 bflush(fb);
 901         }
 902 }
 903 #endif
 904
 905 /* And the iterator */
 906
 907 #ifdef TREE_WANT_ITERATOR
 908 static P(node) * P(first_node) (T *t, uns direction)
 909 {
 910         P(bucket) *node = t->root, *prev = NULL;
 911         while (node)
 912         {
 913                 prev = node;
 914                 node = P(tree_son) (node, direction);
 915         }
 916         return prev ? &prev->n : NULL;
 917 }
 918
 919 #ifndef TREE_FOR_ALL
 920
 921 #define TREE_FOR_ALL(t_px, t_ptr, t_var)                                                \
 922 do                                                                                      \
 923 {                                                                                       \
 924         TREE_GLUE(t_px,node) *t_var = TREE_GLUE(t_px,first_node)(t_ptr, 0);             \
 925         for (; t_var; t_var = TREE_GLUE(t_px,adjacent)(t_var, 1))                       \
 926         {
 927 #define TREE_END_FOR } } while(0)
 928 #define TREE_BREAK break
 929 #define TREE_CONTINUE continue
 930 #define TREE_GLUE(x,y) x##_##y
 931
 932 #endif
 933 #endif
 934
 935 /* Finally, undefine all the parameters */
 936
 937 #undef P
 938 #undef T
 939
 940 #undef TREE_NODE
 941 #undef TREE_PREFIX
 942 #undef TREE_KEY_ATOMIC
 943 #undef TREE_KEY_STRING
 944 #undef TREE_KEY_ENDSTRING
 945 #undef TREE_KEY_COMPLEX
 946 #undef TREE_KEY_DECL
 947 #undef TREE_WANT_CLEANUP
 948 #undef TREE_WANT_FIND
 949 #undef TREE_WANT_FIND_NEXT
 950 #undef TREE_WANT_SEARCH
 951 #undef TREE_WANT_ADJACENT
 952 #undef TREE_WANT_NEW
 953 #undef TREE_WANT_LOOKUP
 954 #undef TREE_WANT_DELETE
 955 #undef TREE_WANT_REMOVE
 956 #undef TREE_WANT_DUMP
 957 #undef TREE_WANT_ITERATOR
 958 #undef TREE_GIVE_CMP
 959 #undef TREE_GIVE_EXTRA_SIZE
 960 #undef TREE_GIVE_INIT_KEY
 961 #undef TREE_GIVE_INIT_DATA
 962 #undef TREE_GIVE_ALLOC
 963 #undef TREE_NOCASE
 964 #undef TREE_ATOMIC_TYPE
 965 #undef TREE_USE_POOL
 966 #undef TREE_STATIC
 967 #undef TREE_CONSERVE_SPACE
 968 #undef TREE_MAX_DEPTH
 969 #undef TREE_STORE_PARENT
 970 #undef TREE_KEY
 971 #undef TREE_EXTRA_SIZE
 972 #undef TREE_SAFE_FREE
 973 #undef STATIC