lib/redblack.h

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