src/mcas/rb_lock_mutex.c

   1 /******************************************************************************
   2  * rb_lock_mutex.c
   3  *
   4  * Lock-based red-black trees, based on Hanke's relaxed balancing operations.
   5  *
   6  * For more details on the local tree restructuring operations used here:
   7  *  S. Hanke, T. Ottmann, and E. Soisalon-Soininen.
   8  *  "Relaxed balanced red-black trees".
   9  *  3rd Italian Conference on Algorithms and Complexity, pages 193-204.
  10  *
  11  * Rather than issuing up-in and up-out requests to a balancing process,
  12  * each operation is directly responsible for local rebalancing. However,
  13  * this process can be split into a number of individual restructuring
  14  * operations, and locks can be released between each operation. Between
  15  * operations, we mark the node concerned as UNBALANCED -- contending
  16  * updates will then wait for this mark to be removed before continuing.
  17  *
  18  * Copyright (c) 2002-2003, K A Fraser
  19
  20 Redistribution and use in source and binary forms, with or without
  21 modification, are permitted provided that the following conditions are
  22 met:
  23
  24     * Redistributions of source code must retain the above copyright
  25     * notice, this list of conditions and the following disclaimer.
  26     * Redistributions in binary form must reproduce the above
  27     * copyright notice, this list of conditions and the following
  28     * disclaimer in the documentation and/or other materials provided
  29     * with the distribution.  Neither the name of the Keir Fraser
  30     * nor the names of its contributors may be used to endorse or
  31     * promote products derived from this software without specific
  32     * prior written permission.
  33
  34 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  35 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  36 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  37 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  38 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  39 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  40 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  41 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  42 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  43 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  44 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  45  */
  46
  47 #define __SET_IMPLEMENTATION__
  48
  49 #include <stdio.h>
  50 #include <assert.h>
  51 #include <stdlib.h>
  52 #include <unistd.h>
  53 #include "portable_defns.h"
  54 #include "gc.h"
  55 #include "set.h"
  56
  57 #define BLACK_MARK      0
  58 #define RED_MARK        1
  59 #define UNBALANCED_MARK 2
  60
  61 #define SET_VALUE(_v,_n)  \
  62     ((_v) = ((setval_t)(((unsigned long)(_v)&3)|((unsigned long)(_n)))))
  63 #define GET_VALUE(_v)     ((setval_t)((int_addr_t)(_v) & ~3UL))
  64 #define GET_COLOUR(_v)    ((int_addr_t)(_v) & 1)
  65 #define SET_COLOUR(_v,_c) \
  66     ((setval_t)(((unsigned long)(_v)&~1UL)|(unsigned long)(_c)))
  67
  68 #define IS_BLACK(_v)      (GET_COLOUR(_v) == 0)
  69 #define IS_RED(_v)        (GET_COLOUR(_v) == 1)
  70 #define IS_UNBALANCED(_v) (((int_addr_t)(_v) & 2) == 2)
  71
  72 #define MK_BLACK(_v)      ((setval_t)(((int_addr_t)(_v)&~1UL) | 0))
  73 #define MK_RED(_v)        ((setval_t)(((int_addr_t)(_v)&~1UL) | 1))
  74 #define MK_BALANCED(_v)   ((setval_t)(((int_addr_t)(_v)&~2UL) | 0))
  75 #define MK_UNBALANCED(_v) ((setval_t)(((int_addr_t)(_v)&~2UL) | 2))
  76
  77 #define GARBAGE_VALUE     ((setval_t)4)
  78 #define IS_GARBAGE(_n)    (GET_VALUE((_n)->v) == GARBAGE_VALUE)
  79 #define MK_GARBAGE(_n)    (SET_VALUE((_n)->v, GARBAGE_VALUE))
  80
  81 #define INTERNAL_VALUE ((void *)0xdeadbee0)
  82
  83 #define IS_ROOT(_n) ((_n)->p->k == 0)
  84 #define IS_LEAF(_n) ((_n)->l == NULL)
  85
  86 /* TRUE if node X is a child of P. */
  87 #define ADJACENT(_p,_x) (((_p)->l==(_x))||((_p)->r==(_x)))
  88
  89 typedef struct node_st node_t;
  90 typedef struct set_st set_t;
  91
  92 struct node_st
  93 {
  94     setkey_t k;
  95     setval_t v;
  96     node_t *l, *r, *p;
  97     mcs_lock_t lock;
  98 };
  99
 100 struct set_st
 101 {
 102     node_t root;
 103     node_t null;
 104     node_t dummy_g, dummy_gg;
 105 };
 106
 107 static int gc_id;
 108
 109 /* Nodes p, x, y must be locked. */
 110 static void left_rotate(ptst_t *ptst, node_t *x)
 111 {
 112     node_t *y = x->r, *p = x->p, *nx;
 113
 114     nx    = gc_alloc(ptst, gc_id);
 115     nx->p = y;
 116     nx->l = x->l;
 117     nx->r = y->l;
 118     nx->k = x->k;
 119     nx->v = x->v;
 120     mcs_init(&nx->lock);
 121
 122     WMB();
 123
 124     y->p    = p;
 125     x->l->p = nx;
 126     y->l->p = nx;
 127     y->l    = nx;
 128     if ( x == p->l ) p->l = y; else p->r = y;
 129
 130     MK_GARBAGE(x);
 131     gc_free(ptst, x, gc_id);
 132 }
 133
 134
 135 /* Nodes p, x, y must be locked. */
 136 static void right_rotate(ptst_t *ptst, node_t *x)
 137 {
 138     node_t *y = x->l, *p = x->p, *nx;
 139
 140     nx    = gc_alloc(ptst, gc_id);
 141     nx->p = y;
 142     nx->l = y->r;
 143     nx->r = x->r;
 144     nx->k = x->k;
 145     nx->v = x->v;
 146     mcs_init(&nx->lock);
 147
 148     WMB();
 149
 150     y->p    = p;
 151     x->r->p = nx;
 152     y->r->p = nx;
 153     y->r    = nx;
 154     if ( x == p->l ) p->l = y; else p->r = y;
 155
 156     MK_GARBAGE(x);
 157     gc_free(ptst, x, gc_id);
 158 }
 159
 160
 161 static void fix_unbalance_up(ptst_t *ptst, node_t *x)
 162 {
 163     qnode_t x_qn, g_qn, p_qn, w_qn, gg_qn;
 164     node_t *g, *p, *w, *gg;
 165     int done = 0;
 166
 167     do {
 168         assert(IS_UNBALANCED(x->v));
 169         if ( IS_GARBAGE(x) ) return;
 170
 171         p  = x->p;
 172         g  = p->p;
 173         gg = g->p;
 174
 175         mcs_lock(&gg->lock, &gg_qn);
 176         if ( !ADJACENT(gg, g) || IS_UNBALANCED(gg->v) || IS_GARBAGE(gg) )
 177             goto unlock_gg;
 178
 179         mcs_lock(&g->lock, &g_qn);
 180         if ( !ADJACENT(g, p) || IS_UNBALANCED(g->v) ) goto unlock_ggg;
 181
 182         mcs_lock(&p->lock, &p_qn);
 183         if ( !ADJACENT(p, x) || IS_UNBALANCED(p->v) ) goto unlock_pggg;
 184
 185         mcs_lock(&x->lock, &x_qn);
 186
 187         assert(IS_RED(x->v));
 188         assert(IS_UNBALANCED(x->v));
 189
 190         if ( IS_BLACK(p->v) )
 191         {
 192             /* Case 1. Nothing to do. */
 193             x->v = MK_BALANCED(x->v);
 194             done = 1;
 195             goto unlock_xpggg;
 196         }
 197
 198         if ( IS_ROOT(x) )
 199         {
 200             /* Case 2. */
 201             x->v = MK_BLACK(MK_BALANCED(x->v));
 202             done = 1;
 203             goto unlock_xpggg;
 204         }
 205
 206         if ( IS_ROOT(p) )
 207         {
 208             /* Case 2. */
 209             p->v = MK_BLACK(p->v);
 210             x->v = MK_BALANCED(x->v);
 211             done = 1;
 212             goto unlock_xpggg;
 213         }
 214
 215         if ( g->l == p ) w = g->r; else w = g->l;
 216         mcs_lock(&w->lock, &w_qn);
 217
 218         if ( IS_RED(w->v) )
 219         {
 220             /* Case 5. */
 221             /* In all other cases, doesn't change colour or subtrees. */
 222             if ( IS_UNBALANCED(w->v) ) goto unlock_wxpggg;
 223             g->v = MK_UNBALANCED(MK_RED(g->v));
 224             p->v = MK_BLACK(p->v);
 225             w->v = MK_BLACK(w->v);
 226             x->v = MK_BALANCED(x->v);
 227             done = 2;
 228             goto unlock_wxpggg;
 229         }
 230
 231         /* Cases 3 & 4. Both of these need the great-grandfather locked. */
 232         if ( p == g->l )
 233         {
 234             if ( x == p->l )
 235             {
 236                 /* Case 3. Single rotation. */
 237                 x->v = MK_BALANCED(x->v);
 238                 p->v = MK_BLACK(p->v);
 239                 g->v = MK_RED(g->v);
 240                 right_rotate(ptst, g);
 241             }
 242             else
 243             {
 244                 /* Case 4. Double rotation. */
 245                 x->v = MK_BALANCED(MK_BLACK(x->v));
 246                 g->v = MK_RED(g->v);
 247                 left_rotate(ptst, p);
 248                 right_rotate(ptst, g);
 249             }
 250         }
 251         else /* SYMMETRIC CASE */
 252         {
 253             if ( x == p->r )
 254             {
 255                 /* Case 3. Single rotation. */
 256                 x->v = MK_BALANCED(x->v);
 257                 p->v = MK_BLACK(p->v);
 258                 g->v = MK_RED(g->v);
 259                 left_rotate(ptst, g);
 260             }
 261             else
 262             {
 263                 /* Case 4. Double rotation. */
 264                 x->v = MK_BALANCED(MK_BLACK(x->v));
 265                 g->v = MK_RED(g->v);
 266                 right_rotate(ptst, p);
 267                 left_rotate(ptst, g);
 268             }
 269         }
 270
 271         done = 1;
 272
 273     unlock_wxpggg:
 274         mcs_unlock(&w->lock, &w_qn);
 275     unlock_xpggg:
 276         mcs_unlock(&x->lock, &x_qn);
 277     unlock_pggg:
 278         mcs_unlock(&p->lock, &p_qn);
 279     unlock_ggg:
 280         mcs_unlock(&g->lock, &g_qn);
 281     unlock_gg:
 282         mcs_unlock(&gg->lock, &gg_qn);
 283
 284         if ( done == 2 )
 285         {
 286             x = g;
 287             done = 0;
 288         }
 289     }
 290     while ( !done );
 291 }
 292
 293
 294 static void fix_unbalance_down(ptst_t *ptst, node_t *x)
 295 {
 296     /* WN == W_NEAR, WF == W_FAR (W_FAR is further, in key space, from X). */
 297     qnode_t x_qn, w_qn, p_qn, g_qn, wn_qn, wf_qn;
 298     node_t *w, *p, *g, *wn, *wf;
 299     int done = 0;
 300
 301     do {
 302         if ( !IS_UNBALANCED(x->v) || IS_GARBAGE(x) ) return;
 303
 304         p = x->p;
 305         g = p->p;
 306
 307         mcs_lock(&g->lock, &g_qn);
 308         if ( !ADJACENT(g, p) || IS_UNBALANCED(g->v) || IS_GARBAGE(g) )
 309             goto unlock_g;
 310
 311         mcs_lock(&p->lock, &p_qn);
 312         if ( !ADJACENT(p, x) || IS_UNBALANCED(p->v) ) goto unlock_pg;
 313
 314         mcs_lock(&x->lock, &x_qn);
 315
 316         if ( !IS_BLACK(x->v) || !IS_UNBALANCED(x->v) )
 317         {
 318             done = 1;
 319             goto unlock_xpg;
 320         }
 321
 322         if ( IS_ROOT(x) )
 323         {
 324             x->v = MK_BALANCED(x->v);
 325             done = 1;
 326             goto unlock_xpg;
 327         }
 328
 329         w = (x == p->l) ? p->r : p->l;
 330         mcs_lock(&w->lock, &w_qn);
 331         if ( IS_UNBALANCED(w->v) )
 332         {
 333             if ( IS_BLACK(w->v) )
 334             {
 335                 /* Funky relaxed rules to the rescue. */
 336                 x->v = MK_BALANCED(x->v);
 337                 w->v = MK_BALANCED(w->v);
 338                 if ( IS_BLACK(p->v) )
 339                 {
 340                     p->v = MK_UNBALANCED(p->v);
 341                     done = 2;
 342                 }
 343                 else
 344                 {
 345                     p->v = MK_BLACK(p->v);
 346                     done = 1;
 347                 }
 348             }
 349             goto unlock_wxpg;
 350         }
 351
 352         assert(!IS_LEAF(w));
 353
 354         if ( x == p->l )
 355         {
 356             wn = w->l;
 357             wf = w->r;
 358         }
 359         else
 360         {
 361             wn = w->r;
 362             wf = w->l;
 363         }
 364
 365         mcs_lock(&wn->lock, &wn_qn);
 366         /* Hanke has an extra relaxed transform here. It's not needed. */
 367         if ( IS_UNBALANCED(wn->v) ) goto unlock_wnwxpg;
 368
 369         mcs_lock(&wf->lock, &wf_qn);
 370         if ( IS_UNBALANCED(wf->v) ) goto unlock_wfwnwxpg;
 371
 372         if ( IS_RED(w->v) )
 373         {
 374             /* Case 1. Rotate at parent. */
 375             assert(IS_BLACK(p->v) && IS_BLACK(wn->v) && IS_BLACK(wf->v));
 376             w->v = MK_BLACK(w->v);
 377             p->v = MK_RED(p->v);
 378             if ( x == p->l ) left_rotate(ptst, p); else right_rotate(ptst, p);
 379             goto unlock_wfwnwxpg;
 380         }
 381
 382         if ( IS_BLACK(wn->v) && IS_BLACK(wf->v) )
 383         {
 384             if ( IS_RED(p->v) )
 385             {
 386                 /* Case 2. Simple recolouring. */
 387                 p->v = MK_BLACK(p->v);
 388                 done = 1;
 389             }
 390             else
 391             {
 392                 /* Case 5. Simple recolouring. */
 393                 p->v = MK_UNBALANCED(p->v);
 394                 done = 2;
 395             }
 396             w->v = MK_RED(w->v);
 397             x->v = MK_BALANCED(x->v);
 398             goto unlock_wfwnwxpg;
 399         }
 400
 401         if ( x == p->l )
 402         {
 403             if ( IS_RED(wf->v) )
 404             {
 405                 /* Case 3. Single rotation. */
 406                 wf->v = MK_BLACK(wf->v);
 407                 w->v = SET_COLOUR(w->v, GET_COLOUR(p->v));
 408                 p->v = MK_BLACK(p->v);
 409                 x->v = MK_BALANCED(x->v);
 410                 left_rotate(ptst, p);
 411             }
 412             else
 413             {
 414                 /* Case 4. Double rotation. */
 415                 assert(IS_RED(wn->v));
 416                 wn->v = SET_COLOUR(wn->v, GET_COLOUR(p->v));
 417                 p->v = MK_BLACK(p->v);
 418                 x->v = MK_BALANCED(x->v);
 419                 right_rotate(ptst, w);
 420                 left_rotate(ptst, p);
 421             }
 422         }
 423         else /* SYMMETRIC CASE: X == P->R  */
 424         {
 425             if ( IS_RED(wf->v) )
 426             {
 427                 /* Case 3. Single rotation. */
 428                 wf->v = MK_BLACK(wf->v);
 429                 w->v = SET_COLOUR(w->v, GET_COLOUR(p->v));
 430                 p->v = MK_BLACK(p->v);
 431                 x->v = MK_BALANCED(x->v);
 432                 right_rotate(ptst, p);
 433             }
 434             else
 435             {
 436                 /* Case 4. Double rotation. */
 437                 assert(IS_RED(wn->v));
 438                 wn->v = SET_COLOUR(wn->v, GET_COLOUR(p->v));
 439                 p->v = MK_BLACK(p->v);
 440                 x->v = MK_BALANCED(x->v);
 441                 left_rotate(ptst, w);
 442                 right_rotate(ptst, p);
 443             }
 444         }
 445
 446         done = 1;
 447
 448     unlock_wfwnwxpg:
 449         mcs_unlock(&wf->lock, &wf_qn);
 450     unlock_wnwxpg:
 451         mcs_unlock(&wn->lock, &wn_qn);
 452     unlock_wxpg:
 453         mcs_unlock(&w->lock, &w_qn);
 454     unlock_xpg:
 455         mcs_unlock(&x->lock, &x_qn);
 456     unlock_pg:
 457         mcs_unlock(&p->lock, &p_qn);
 458     unlock_g:
 459         mcs_unlock(&g->lock, &g_qn);
 460
 461         if ( done == 2 )
 462         {
 463             x = p;
 464             done = 0;
 465         }
 466     }
 467     while ( !done );
 468 }
 469
 470
 471 static void delete_finish(ptst_t *ptst, node_t *x)
 472 {
 473     qnode_t g_qn, p_qn, w_qn, x_qn;
 474     node_t *g, *p, *w;
 475     int done = 0;
 476
 477     do {
 478         if ( IS_GARBAGE(x) ) return;
 479
 480         p = x->p;
 481         g = p->p;
 482
 483         mcs_lock(&g->lock, &g_qn);
 484         if ( !ADJACENT(g, p) || IS_UNBALANCED(g->v) || IS_GARBAGE(g) )
 485             goto unlock_g;
 486
 487         mcs_lock(&p->lock, &p_qn);
 488         /* Removing unbalanced red nodes is okay. */
 489         if ( !ADJACENT(p, x) || (IS_UNBALANCED(p->v) && IS_BLACK(p->v)) )
 490             goto unlock_pg;
 491
 492         mcs_lock(&x->lock, &x_qn);
 493         if ( IS_UNBALANCED(x->v) ) goto unlock_xpg;
 494         if ( GET_VALUE(x->v) != NULL )
 495         {
 496             done = 1;
 497             goto unlock_xpg;
 498         }
 499
 500         if ( p->l == x ) w = p->r; else w = p->l;
 501         assert(w != x);
 502         mcs_lock(&w->lock, &w_qn);
 503         if ( IS_UNBALANCED(w->v) ) goto unlock_wxpg;
 504
 505         if ( g->l == p ) g->l = w; else g->r = w;
 506         MK_GARBAGE(p); gc_free(ptst, p, gc_id);
 507         MK_GARBAGE(x); gc_free(ptst, x, gc_id);
 508         w->p = g;
 509         if ( IS_BLACK(p->v) && IS_BLACK(w->v) )
 510         {
 511             w->v = MK_UNBALANCED(w->v);
 512             done = 2;
 513         }
 514         else
 515         {
 516             w->v = MK_BLACK(w->v);
 517             done = 1;
 518         }
 519
 520     unlock_wxpg:
 521         mcs_unlock(&w->lock, &w_qn);
 522     unlock_xpg:
 523         mcs_unlock(&x->lock, &x_qn);
 524     unlock_pg:
 525         mcs_unlock(&p->lock, &p_qn);
 526     unlock_g:
 527         mcs_unlock(&g->lock, &g_qn);
 528     }
 529     while ( !done );
 530
 531     if ( done == 2 ) fix_unbalance_down(ptst, w);
 532 }
 533
 534
 535 set_t *set_alloc(void)
 536 {
 537     ptst_t *ptst;
 538     set_t  *set;
 539     node_t *root, *null;
 540
 541     ptst = critical_enter();
 542
 543     set = (set_t *)malloc(sizeof(*set));
 544     memset(set, 0, sizeof(*set));
 545
 546     root = &set->root;
 547     null = &set->null;
 548
 549     root->k = 0;
 550     root->v = MK_RED(INTERNAL_VALUE);
 551     root->l = NULL;
 552     root->r = null;
 553     root->p = NULL;
 554     mcs_init(&root->lock);
 555
 556     null->k = SENTINEL_KEYMIN;
 557     null->v = MK_BLACK(INTERNAL_VALUE);
 558     null->l = NULL;
 559     null->r = NULL;
 560     null->p = root;
 561     mcs_init(&null->lock);
 562
 563     set->dummy_gg.l = &set->dummy_g;
 564     set->dummy_g.p  = &set->dummy_gg;
 565     set->dummy_g.l  = &set->root;
 566     set->root.p     = &set->dummy_g;
 567
 568     critical_exit(ptst);
 569
 570     return set;
 571 }
 572
 573
 574 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
 575 {
 576     ptst_t  *ptst;
 577     qnode_t  y_qn, z_qn;
 578     node_t  *y, *z, *new_internal, *new_leaf;
 579     int      fix_up = 0;
 580     setval_t ov = NULL;
 581
 582     k = CALLER_TO_INTERNAL_KEY(k);
 583
 584     ptst = critical_enter();
 585
 586  retry:
 587     z = &s->root;
 588     while ( (y = (k <= z->k) ? z->l : z->r) != NULL )
 589         z = y;
 590
 591     y = z->p;
 592     mcs_lock(&y->lock, &y_qn);
 593     if ( (((k <= y->k) ? y->l : y->r) != z) || IS_GARBAGE(y) )
 594     {
 595         mcs_unlock(&y->lock, &y_qn);
 596         goto retry;
 597     }
 598
 599     mcs_lock(&z->lock, &z_qn);
 600     assert(!IS_GARBAGE(z) && IS_LEAF(z));
 601
 602     if ( z->k == k )
 603     {
 604         ov = GET_VALUE(z->v);
 605         if ( overwrite || (ov == NULL) )
 606             SET_VALUE(z->v, v);
 607     }
 608     else
 609     {
 610         new_leaf     = gc_alloc(ptst, gc_id);
 611         new_internal = gc_alloc(ptst, gc_id);
 612         new_leaf->k = k;
 613         new_leaf->v = MK_BLACK(v);
 614         new_leaf->l = NULL;
 615         new_leaf->r = NULL;
 616
 617         new_leaf->p = new_internal;
 618         mcs_init(&new_leaf->lock);
 619         if ( z->k < k )
 620         {
 621             new_internal->k = z->k;
 622             new_internal->l = z;
 623             new_internal->r = new_leaf;
 624         }
 625         else
 626         {
 627             new_internal->k = k;
 628             new_internal->l = new_leaf;
 629             new_internal->r = z;
 630         }
 631         new_internal->p = y;
 632         mcs_init(&new_internal->lock);
 633
 634         if ( IS_UNBALANCED(z->v) )
 635         {
 636             z->v = MK_BALANCED(z->v);
 637             new_internal->v = MK_BLACK(INTERNAL_VALUE);
 638         }
 639         else if ( IS_RED(y->v) )
 640         {
 641             new_internal->v = MK_UNBALANCED(MK_RED(INTERNAL_VALUE));
 642             fix_up = 1;
 643         }
 644         else
 645         {
 646             new_internal->v = MK_RED(INTERNAL_VALUE);
 647         }
 648
 649         WMB();
 650
 651         z->p = new_internal;
 652         if ( y->l == z ) y->l = new_internal; else y->r = new_internal;
 653     }
 654
 655     mcs_unlock(&y->lock, &y_qn);
 656     mcs_unlock(&z->lock, &z_qn);
 657
 658     if ( fix_up )
 659         fix_unbalance_up(ptst, new_internal);
 660
 661  out:
 662     critical_exit(ptst);
 663
 664     return ov;
 665 }
 666
 667
 668 setval_t set_remove(set_t *s, setkey_t k)
 669 {
 670     ptst_t  *ptst;
 671     node_t  *y, *z;
 672     qnode_t  z_qn;
 673     setval_t ov = NULL;
 674
 675     k = CALLER_TO_INTERNAL_KEY(k);
 676
 677     ptst = critical_enter();
 678
 679     z = &s->root;
 680     while ( (y = (k <= z->k) ? z->l : z->r) != NULL )
 681         z = y;
 682
 683     if ( z->k == k )
 684     {
 685         mcs_lock(&z->lock, &z_qn);
 686         if ( !IS_GARBAGE(z) )
 687         {
 688             ov = GET_VALUE(z->v);
 689
 690             SET_VALUE(z->v, NULL);
 691         }
 692         mcs_unlock(&z->lock, &z_qn);
 693     }
 694
 695     if ( ov != NULL )
 696         delete_finish(ptst, z);
 697
 698     critical_exit(ptst);
 699
 700     return ov;
 701 }
 702
 703
 704 setval_t set_lookup(set_t *s, setkey_t k)
 705 {
 706     ptst_t  *ptst;
 707     node_t  *m, *n;
 708     setval_t v;
 709
 710     k = CALLER_TO_INTERNAL_KEY(k);
 711
 712     ptst = critical_enter();
 713
 714     n = &s->root;
 715     while ( (m = (k <= n->k) ? n->l : n->r) != NULL )
 716         n = m;
 717
 718     v = (k == n->k) ? GET_VALUE(n->v) : NULL;
 719     if ( v == GARBAGE_VALUE ) v = NULL;
 720
 721     critical_exit(ptst);
 722
 723     return v;
 724 }
 725
 726
 727 void _init_set_subsystem(void)
 728 {
 729     gc_id = gc_add_allocator(sizeof(node_t));
 730 }
 731
 732 #if 0
 733 static int valll=0, bug=0, nrb=-1;
 734 static void __traverse(node_t *n, int d, int _nrb)
 735 {
 736     int i;
 737     if ( n == NULL )
 738     {
 739         if ( nrb == -1 ) nrb = _nrb;
 740         if ( nrb != _nrb )
 741             printf("Imbalance at depth %d (%d,%d)\n", d, nrb, _nrb);
 742         return;
 743     }
 744     if ( IS_LEAF(n) && (n->k != 0) )
 745     {
 746         assert(n->l == NULL);
 747         assert(n->r == NULL);
 748         assert(IS_BLACK(n->v));
 749     }
 750     if ( !IS_LEAF(n) && IS_RED(n->v) )
 751     {
 752         assert(IS_BLACK(n->l->v));
 753         assert(IS_BLACK(n->r->v));
 754     }
 755     if ( IS_BLACK(n->v) ) _nrb++;
 756     __traverse(n->l, d+1, _nrb);
 757     if ( valll > n->k ) bug=1;
 758 #if 0
 759     for ( i = 0; i < d; i++ ) printf("  ");
 760     printf("%c%p K: %5d  V: %p  P: %p  L: %p  R: %p  depth: %d\n",
 761            IS_BLACK(n->v) ? 'B' : 'R', n, n->k, n->v, n->p, n->l, n->r, d);
 762 #endif
 763     valll = n->k;
 764     __traverse(n->r, d+1, _nrb);
 765 }
 766 void check_tree(set_t *s)
 767 {
 768     __traverse(s->root.r, 0, 0);
 769     if ( bug )
 770         printf("***********************************************************************************************\n");
 771 }
 772 #endif