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