src/mcas/rb_stm.c

   1 /******************************************************************************
   2  * rb_stm.c
   3  *
   4  * Lock-free red-black trees, based on STM.
   5  *
   6  * Copyright (c) 2002-2003, K A Fraser
   7  *
   8 Redistribution and use in source and binary forms, with or without
   9 modification, are permitted provided that the following conditions are
  10 met:
  11
  12     * Redistributions of source code must retain the above copyright
  13     * notice, this list of conditions and the following disclaimer.
  14     * Redistributions in binary form must reproduce the above
  15     * copyright notice, this list of conditions and the following
  16     * disclaimer in the documentation and/or other materials provided
  17     * with the distribution.  Neither the name of the Keir Fraser
  18     * nor the names of its contributors may be used to endorse or
  19     * promote products derived from this software without specific
  20     * prior written permission.
  21
  22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  25 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  26 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  27 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  28 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  29 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  30 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  31 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  32 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  33  */
  34
  35 #define __SET_IMPLEMENTATION__
  36
  37 #include <stdio.h>
  38 #include <assert.h>
  39 #include <stdlib.h>
  40 #include <unistd.h>
  41 #include "portable_defns.h"
  42 #include "gc.h"
  43 #include "stm.h"
  44 #include "set.h"
  45
  46 #define IS_BLACK(_v)   ((int_addr_t)(_v)&1)
  47 #define IS_RED(_v)     (!IS_BLACK(_v))
  48 #define MK_BLACK(_v)   ((setval_t)((int_addr_t)(_v)|1))
  49 #define MK_RED(_v)     ((setval_t)((int_addr_t)(_v)&~1))
  50 #define GET_VALUE(_v)  (MK_RED(_v))
  51 #define GET_COLOUR(_v) (IS_BLACK(_v))
  52 #define SET_COLOUR(_v,_c) ((setval_t)((unsigned long)(_v)|(unsigned long)(_c)))
  53
  54 typedef struct node_st node_t;
  55 typedef stm_blk set_t;
  56
  57 struct node_st
  58 {
  59     setkey_t k;
  60     setval_t v;
  61     stm_blk *l, *r, *p;
  62 };
  63
  64 static struct {
  65     CACHE_PAD(0);
  66     stm *memory;    /* read-only */
  67     stm_blk *nullb; /* read-only */
  68     CACHE_PAD(2);
  69 } shared;
  70
  71 #define MEMORY (shared.memory)
  72 #define NULLB  (shared.nullb)
  73
  74 static void left_rotate(ptst_t *ptst, stm_tx *tx, stm_blk *xb, node_t *x)
  75 {
  76     stm_blk *yb, *pb;
  77     node_t *y, *p;
  78
  79     yb = x->r;
  80     pb = x->p;
  81
  82     y = write_stm_blk(ptst, tx, yb);
  83     p = write_stm_blk(ptst, tx, pb);
  84
  85     if ( (x->r = y->l) != NULLB )
  86     {
  87         node_t *xr = write_stm_blk(ptst, tx, x->r);
  88         xr->p = xb;
  89     }
  90
  91     x->p = yb;
  92     y->l = xb;
  93     y->p = pb;
  94     if ( xb == p->l ) p->l = yb; else p->r = yb;
  95 }
  96
  97
  98 static void right_rotate(ptst_t *ptst, stm_tx *tx, stm_blk *xb, node_t *x)
  99 {
 100     stm_blk *yb, *pb;
 101     node_t *y, *p;
 102
 103     yb = x->l;
 104     pb = x->p;
 105
 106     y = write_stm_blk(ptst, tx, yb);
 107     p = write_stm_blk(ptst, tx, pb);
 108
 109     if ( (x->l = y->r) != NULLB )
 110     {
 111         node_t *xl = write_stm_blk(ptst, tx, x->l);
 112         xl->p = xb;
 113     }
 114
 115     x->p = yb;
 116     y->r = xb;
 117     y->p = pb;
 118     if ( xb == p->l ) p->l = yb; else p->r = yb;
 119 }
 120
 121
 122 static void delete_fixup(ptst_t *ptst, stm_tx *tx, set_t *s,
 123                          stm_blk *xb, node_t *x)
 124 {
 125     stm_blk *pb, *wb, *wlb, *wrb;
 126     node_t *p, *w, *wl, *wr;
 127
 128     while ( (x->p != s) && IS_BLACK(x->v) )
 129     {
 130         pb = x->p;
 131         p  = write_stm_blk(ptst, tx, pb);
 132
 133         if ( xb == p->l )
 134         {
 135             wb = p->r;
 136             w  = write_stm_blk(ptst, tx, wb);
 137             if ( IS_RED(w->v) )
 138             {
 139                 w->v = MK_BLACK(w->v);
 140                 p->v = MK_RED(p->v);
 141                 left_rotate(ptst, tx, pb, p);
 142                 wb = p->r;
 143                 w  = write_stm_blk(ptst, tx, wb);
 144             }
 145
 146             wlb = w->l;
 147             wl  = read_stm_blk(ptst, tx, wlb);
 148             wrb = w->r;
 149             wr  = read_stm_blk(ptst, tx, wrb);
 150             if ( IS_BLACK(wl->v) && IS_BLACK(wr->v) )
 151             {
 152                 w->v = MK_RED(w->v);
 153                 xb = pb;
 154                 x  = p;
 155             }
 156             else
 157             {
 158                 if ( IS_BLACK(wr->v) )
 159                 {
 160                     wl = write_stm_blk(ptst, tx, wlb);
 161                     wl->v = MK_BLACK(wl->v);
 162                     w->v  = MK_RED(w->v);
 163                     right_rotate(ptst, tx, wb, w);
 164                     wb = p->r;
 165                     w  = write_stm_blk(ptst, tx, wb);
 166                 }
 167
 168                 wrb = w->r;
 169                 wr  = write_stm_blk(ptst, tx, wrb);
 170                 w->v = SET_COLOUR(GET_VALUE(w->v), GET_COLOUR(p->v));
 171                 p->v = MK_BLACK(p->v);
 172                 wr->v = MK_BLACK(wr->v);
 173                 left_rotate(ptst, tx, pb, p);
 174                 break;
 175             }
 176         }
 177         else /* SYMMETRIC CASE */
 178         {
 179             wb = p->l;
 180             w  = write_stm_blk(ptst, tx, wb);
 181             if ( IS_RED(w->v) )
 182             {
 183                 w->v = MK_BLACK(w->v);
 184                 p->v = MK_RED(p->v);
 185                 right_rotate(ptst, tx, pb, p);
 186                 wb = p->l;
 187                 w  = write_stm_blk(ptst, tx, wb);
 188             }
 189
 190             wlb = w->l;
 191             wl  = read_stm_blk(ptst, tx, wlb);
 192             wrb = w->r;
 193             wr  = read_stm_blk(ptst, tx, wrb);
 194             if ( IS_BLACK(wl->v) && IS_BLACK(wr->v) )
 195             {
 196                 w->v = MK_RED(w->v);
 197                 xb = pb;
 198                 x  = p;
 199             }
 200             else
 201             {
 202                 if ( IS_BLACK(wl->v) )
 203                 {
 204                     wr = write_stm_blk(ptst, tx, wrb);
 205                     wr->v = MK_BLACK(wr->v);
 206                     w->v  = MK_RED(w->v);
 207                     left_rotate(ptst, tx, wb, w);
 208                     wb = p->l;
 209                     w  = write_stm_blk(ptst, tx, wb);
 210                 }
 211
 212                 wlb = w->l;
 213                 wl  = write_stm_blk(ptst, tx, wlb);
 214                 w->v = SET_COLOUR(GET_VALUE(w->v), GET_COLOUR(p->v));
 215                 p->v = MK_BLACK(p->v);
 216                 wl->v = MK_BLACK(wl->v);
 217                 right_rotate(ptst, tx, pb, p);
 218                 break;
 219             }
 220         }
 221     }
 222
 223     x->v = MK_BLACK(x->v);
 224 }
 225
 226
 227 set_t *set_alloc(void)
 228 {
 229     ptst_t *ptst;
 230     set_t  *set;
 231     node_t *root;
 232
 233     ptst = critical_enter();
 234
 235     set = new_stm_blk(ptst, MEMORY);
 236
 237     root = init_stm_blk(ptst, MEMORY, set);
 238     root->k = SENTINEL_KEYMIN;
 239     root->v = MK_RED(NULL);
 240     root->l = NULLB;
 241     root->r = NULLB;
 242     root->p = NULL;
 243
 244     critical_exit(ptst);
 245
 246     return set;
 247 }
 248
 249
 250 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
 251 {
 252     ptst_t  *ptst;
 253     stm_tx  *tx;
 254     stm_blk *xb, *b, *pb, *gb, *yb, *newb;
 255     node_t  *x, *p, *g, *y, *new;
 256     setval_t ov;
 257
 258     k = CALLER_TO_INTERNAL_KEY(k);
 259
 260     newb = NULL;
 261
 262     ptst = critical_enter();
 263
 264     do {
 265         new_stm_tx(tx, ptst, MEMORY);
 266
 267         b = s;
 268         while ( b != NULLB )
 269         {
 270             xb = b;
 271             x = read_stm_blk(ptst, tx, xb);
 272             if ( k == x->k ) break;
 273             b = (k < x->k) ? x->l : x->r;
 274         }
 275
 276         x = write_stm_blk(ptst, tx, xb);
 277
 278         if ( k == x->k )
 279         {
 280             ov = x->v;
 281             if ( overwrite ) x->v = SET_COLOUR(v, GET_COLOUR(ov));
 282             ov = GET_VALUE(ov);
 283         }
 284         else
 285         {
 286             ov = NULL;
 287             if ( newb == NULL )
 288             {
 289                 newb = new_stm_blk(ptst, MEMORY);
 290                 new = init_stm_blk(ptst, MEMORY, newb);
 291                 new->k = k;
 292             }
 293
 294             new->v = MK_RED(v);
 295             new->l = NULLB;
 296             new->r = NULLB;
 297             new->p = xb;
 298
 299             if ( k < x->k ) x->l = newb; else x->r = newb;
 300
 301             xb = newb;
 302             x  = new;
 303
 304             for ( ; ; )
 305             {
 306                 if ( (pb = x->p) == s )
 307                 {
 308                     x->v = MK_BLACK(x->v);
 309                     break;
 310                 }
 311
 312                 p = read_stm_blk(ptst, tx, pb);
 313                 if ( IS_BLACK(p->v) ) break;
 314
 315                 gb = p->p;
 316                 g = read_stm_blk(ptst, tx, gb);
 317                 if ( pb == g->l )
 318                 {
 319                     yb = g->r;
 320                     y  = read_stm_blk(ptst, tx, yb);
 321                     if ( IS_RED(y->v) )
 322                     {
 323                         p = write_stm_blk(ptst, tx, pb);
 324                         y = write_stm_blk(ptst, tx, yb);
 325                         g = write_stm_blk(ptst, tx, gb);
 326                         p->v = MK_BLACK(p->v);
 327                         y->v = MK_BLACK(y->v);
 328                         g->v = MK_RED(g->v);
 329                         xb = gb;
 330                         x  = g;
 331                     }
 332                     else
 333                     {
 334                         if ( xb == p->r )
 335                         {
 336                             xb = pb;
 337                             x  = write_stm_blk(ptst, tx, pb);
 338                             left_rotate(ptst, tx, xb, x);
 339                         }
 340                         pb = x->p;
 341                         p  = write_stm_blk(ptst, tx, pb);
 342                         gb = p->p;
 343                         g  = write_stm_blk(ptst, tx, gb);
 344                         p->v = MK_BLACK(p->v);
 345                         g->v = MK_RED(g->v);
 346                         right_rotate(ptst, tx, gb, g);
 347                     }
 348                 }
 349                 else /* SYMMETRIC CASE */
 350                 {
 351                     yb = g->l;
 352                     y  = read_stm_blk(ptst, tx, yb);
 353                     if ( IS_RED(y->v) )
 354                     {
 355                         p = write_stm_blk(ptst, tx, pb);
 356                         y = write_stm_blk(ptst, tx, yb);
 357                         g = write_stm_blk(ptst, tx, gb);
 358                         p->v = MK_BLACK(p->v);
 359                         y->v = MK_BLACK(y->v);
 360                         g->v = MK_RED(g->v);
 361                         xb = gb;
 362                         x  = g;
 363                     }
 364                     else
 365                     {
 366                         if ( xb == p->l )
 367                         {
 368                             xb = pb;
 369                             x  = write_stm_blk(ptst, tx, pb);
 370                             right_rotate(ptst, tx, xb, x);
 371                         }
 372                         pb = x->p;
 373                         p  = write_stm_blk(ptst, tx, pb);
 374                         gb = p->p;
 375                         g  = write_stm_blk(ptst, tx, gb);
 376                         p->v = MK_BLACK(p->v);
 377                         g->v = MK_RED(g->v);
 378                         left_rotate(ptst, tx, gb, g);
 379                     }
 380                 }
 381             }
 382         }
 383
 384         remove_from_tx(ptst, tx, NULLB);
 385     }
 386     while ( !commit_stm_tx(ptst, tx) );
 387
 388     /* Free unused new block. */
 389     if ( (ov != NULL) && (newb != NULL) ) free_stm_blk(ptst, MEMORY, newb);
 390
 391     critical_exit(ptst);
 392
 393     return ov;
 394 }
 395
 396
 397 setval_t set_remove(set_t *s, setkey_t k)
 398 {
 399     ptst_t  *ptst;
 400     stm_tx  *tx;
 401     stm_blk *zb, *b, *xb, *yb;
 402     node_t  *z, *x, *y, *yp;
 403     setval_t ov;
 404
 405     k = CALLER_TO_INTERNAL_KEY(k);
 406
 407     ptst = critical_enter();
 408
 409     do {
 410         new_stm_tx(tx, ptst, MEMORY);
 411         ov = NULL;
 412         b  = s;
 413
 414         while ( b != NULLB )
 415         {
 416             zb = b;
 417             z = read_stm_blk(ptst, tx, zb);
 418             if ( k == z->k )
 419             {
 420                 ov = GET_VALUE(z->v);
 421                 break;
 422             }
 423             b = (k < z->k) ? z->l : z->r;
 424         }
 425
 426         if ( ov != NULL )
 427         {
 428             z = write_stm_blk(ptst, tx, zb);
 429
 430             if ( (z->l != NULLB) && (z->r != NULLB) )
 431             {
 432                 /* Find successor of node z, and place in (yb,y). */
 433                 yb = z->r;
 434                 y  = read_stm_blk(ptst, tx, yb);
 435
 436                 while ( y->l != NULLB )
 437                 {
 438                     yb = y->l;
 439                     y  = read_stm_blk(ptst, tx, yb);
 440                 }
 441
 442                 y = write_stm_blk(ptst, tx, yb);
 443             }
 444             else
 445             {
 446                 yb = zb;
 447                 y  = z;
 448             }
 449
 450             xb = (y->l != NULLB) ? y->l : y->r;
 451             x = write_stm_blk(ptst, tx, xb);
 452             x->p = y->p;
 453
 454             yp = write_stm_blk(ptst, tx, y->p);
 455             if ( yb == yp->l ) yp->l = xb; else yp->r = xb;
 456
 457             if ( y != z )
 458             {
 459                 z->k = y->k;
 460                 z->v = SET_COLOUR(GET_VALUE(y->v), GET_COLOUR(z->v));
 461             }
 462
 463             if ( IS_BLACK(y->v) ) delete_fixup(ptst, tx, s, xb, x);
 464         }
 465
 466         remove_from_tx(ptst, tx, NULLB);
 467     }
 468     while ( !commit_stm_tx(ptst, tx) );
 469
 470     /* Free a deleted block. */
 471     if ( ov != NULL ) free_stm_blk(ptst, MEMORY, yb);
 472
 473     critical_exit(ptst);
 474
 475     return ov;
 476 }
 477
 478
 479 setval_t set_lookup(set_t *s, setkey_t k)
 480 {
 481     ptst_t  *ptst;
 482     stm_tx  *tx;
 483     stm_blk *nb;
 484     node_t  *n;
 485     setval_t v;
 486
 487     k = CALLER_TO_INTERNAL_KEY(k);
 488
 489     ptst = critical_enter();
 490
 491     do {
 492         new_stm_tx(tx, ptst, MEMORY);
 493         v  = NULL;
 494         nb = s;
 495
 496         while ( nb != NULLB )
 497         {
 498             n = read_stm_blk(ptst, tx, nb);
 499             if ( k == n->k )
 500             {
 501                 v = GET_VALUE(n->v);
 502                 break;
 503             }
 504             nb = (k < n->k) ? n->l : n->r;
 505         }
 506     }
 507     while ( !commit_stm_tx(ptst, tx) );
 508
 509     critical_exit(ptst);
 510
 511     return v;
 512 }
 513
 514
 515 void _init_set_subsystem(void)
 516 {
 517     node_t *null;
 518     ptst_t *ptst;
 519
 520     ptst = critical_enter();
 521
 522     _init_stm_subsystem(0);
 523
 524     MEMORY = new_stm(ptst, sizeof(node_t));
 525
 526     NULLB = new_stm_blk(ptst, MEMORY);
 527     null  = init_stm_blk(ptst, MEMORY, NULLB);
 528     null->k = 0;
 529     null->v = MK_BLACK(NULL);
 530     null->l = NULL;
 531     null->r = NULL;
 532     null->p = NULL;
 533
 534     critical_exit(ptst);
 535 }