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