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