tokuredblack.c 20 KB
Newer Older
Yoni Fogel's avatar
Yoni Fogel committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
/*
   Redblack balanced tree algorithm
   Copyright (C) Damian Ivereigh 2000

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as published by
   the Free Software Foundation; either version 2.1 of the License, or
   (at your option) any later version. See the file COPYING for details.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU Lesser General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/* Implement the red/black tree structure. It is designed to emulate
** the standard tsearch() stuff. i.e. the calling conventions are
** exactly the same
*/

#include <stddef.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
29
#include <tokuredblack.h>
Yoni Fogel's avatar
Yoni Fogel committed
30
#include <assert.h>
Yoni Fogel's avatar
Yoni Fogel committed
31 32 33 34 35 36 37 38

/* Dummy (sentinel) node, so that we can make X->left->up = X
** We then use this instead of NULL to mean the top or bottom
** end of the rb tree. It is a black node.
**
** Initialization of the last field in this initializer is left implicit
** because it could be of any type.  We count on the compiler to zero it.
*/
Yoni Fogel's avatar
Yoni Fogel committed
39 40
static struct toku_rbt_node toku_rbt__null;
static struct toku_rbt_node* RBNULL = &toku_rbt__null;
Yoni Fogel's avatar
Yoni Fogel committed
41 42


Yoni Fogel's avatar
Yoni Fogel committed
43 44
static struct toku_rbt_node *toku_rbt__alloc(struct toku_rbt_tree *rbinfo) {return (struct toku_rbt_node *) rbinfo->rb_malloc(sizeof(struct toku_rbt_node));}
static void toku_rbt__free(struct toku_rbt_tree *rbinfo, struct toku_rbt_node *x) {rbinfo->rb_free(x);}
Yoni Fogel's avatar
Yoni Fogel committed
45 46

/* These functions are always needed */
Yoni Fogel's avatar
Yoni Fogel committed
47 48 49 50 51
static void toku_rbt__left_rotate(struct toku_rbt_node **, struct toku_rbt_node *);
static void toku_rbt__right_rotate(struct toku_rbt_node **, struct toku_rbt_node *);
static struct toku_rbt_node *toku_rbt__successor(const struct toku_rbt_node *);
static struct toku_rbt_node *toku_rbt__predecessor(const struct toku_rbt_node *);
static struct toku_rbt_node *toku_rbt__traverse(int, const toku_range * , struct toku_rbt_tree *);
Yoni Fogel's avatar
Yoni Fogel committed
52 53

/* These functions may not be needed */
Yoni Fogel's avatar
Yoni Fogel committed
54 55 56 57
static struct toku_rbt_node* toku_rbt__insert(
    const  toku_range* key,
    struct toku_rbt_tree*   rbinfo,
    struct toku_rbt_node*   parent
Yoni Fogel's avatar
Yoni Fogel committed
58 59
);

Yoni Fogel's avatar
Yoni Fogel committed
60
static struct toku_rbt_node *toku_rbt__lookup(int, const toku_interval * , struct toku_rbt_tree *, struct toku_rbt_node**);
Yoni Fogel's avatar
Yoni Fogel committed
61

62
static void toku_rbt__destroy(struct toku_rbt_tree *rbinfo, struct toku_rbt_node *);
Yoni Fogel's avatar
Yoni Fogel committed
63

64
static void toku_rbt__delete(struct toku_rbt_tree* rbinfo, struct toku_rbt_node **, struct toku_rbt_node *);
Yoni Fogel's avatar
Yoni Fogel committed
65
static void toku_rbt__delete_fix(struct toku_rbt_node **, struct toku_rbt_node *);
Yoni Fogel's avatar
Yoni Fogel committed
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

/*
** OK here we go, the balanced tree stuff. The algorithm is the
** fairly standard red/black taken from "Introduction to Algorithms"
** by Cormen, Leiserson & Rivest. Maybe one of these days I will
** fully understand all this stuff.
**
** Basically a red/black balanced tree has the following properties:-
** 1) Every node is either red or black (colour is RED or BLACK)
** 2) A leaf (RBNULL pointer) is considered black
** 3) If a node is red then its children are black
** 4) Every path from a node to a leaf contains the same no
**    of black nodes
**
** 3) & 4) above guarantee that the longest path (alternating
** red and black nodes) is only twice as long as the shortest
** path (all black nodes). Thus the tree remains fairly balanced.
*/

/*
 * Initialise a tree. Identifies the comparison routine and any config
 * data that must be sent to it when called.
 * Returns a pointer to the top of the tree.
 */
Yoni Fogel's avatar
Yoni Fogel committed
90
int toku_rbt_init (
Yoni Fogel's avatar
Yoni Fogel committed
91
    int (*cmp)(const toku_point*, const toku_point*),
Yoni Fogel's avatar
Yoni Fogel committed
92 93 94 95
    struct toku_rbt_tree** ptree,
    void* (*user_malloc) (size_t),
    void  (*user_free)   (void*),
    void* (*user_realloc)(void*, size_t)
Yoni Fogel's avatar
Yoni Fogel committed
96 97
)
{
Yoni Fogel's avatar
Yoni Fogel committed
98
    struct toku_rbt_tree* temptree = NULL;
Yoni Fogel's avatar
Yoni Fogel committed
99 100
    int r = ENOSYS;

Yoni Fogel's avatar
Yoni Fogel committed
101 102 103 104 105 106 107 108
   static int toku_rbt__null_is_initialized = 0;
   if (!toku_rbt__null_is_initialized) {
      toku_rbt__null_is_initialized = 1;
      toku_rbt__null.up     = &toku_rbt__null;
      toku_rbt__null.left   = &toku_rbt__null;
      toku_rbt__null.right  = &toku_rbt__null;
      toku_rbt__null.colour = BLACK;
      /* Key is initialized since the toku_rbt__null is static. */
Yoni Fogel's avatar
Yoni Fogel committed
109 110
   }

Yoni Fogel's avatar
Yoni Fogel committed
111 112
    if (!cmp || !ptree || !user_malloc || !user_free || !user_realloc) {
        r = EINVAL; goto cleanup; }
Yoni Fogel's avatar
Yoni Fogel committed
113
    temptree=(struct toku_rbt_tree *) user_malloc(sizeof(struct toku_rbt_tree));
Yoni Fogel's avatar
Yoni Fogel committed
114
    if (!temptree) { r = ENOMEM; goto cleanup; }
Yoni Fogel's avatar
Yoni Fogel committed
115 116 117 118 119 120 121
    
    temptree->rb_cmp=cmp;
    temptree->rb_root=RBNULL;
    temptree->rb_malloc  = user_malloc;
    temptree->rb_free    = user_free;
    temptree->rb_realloc = user_realloc;
    
Yoni Fogel's avatar
Yoni Fogel committed
122 123

    *ptree = temptree;
Yoni Fogel's avatar
Yoni Fogel committed
124
    r = 0;    
Yoni Fogel's avatar
Yoni Fogel committed
125 126 127 128
cleanup:
    return r;
}

Yoni Fogel's avatar
Yoni Fogel committed
129 130 131 132 133
void toku_rbt_clear(struct toku_rbt_tree *rbinfo) {
    assert(rbinfo);
    if (rbinfo->rb_root!=RBNULL) { toku_rbt__destroy(rbinfo, rbinfo->rb_root); }
    rbinfo->rb_root = RBNULL;
}
Yoni Fogel's avatar
Yoni Fogel committed
134

Yoni Fogel's avatar
Yoni Fogel committed
135 136
void toku_rbt_destroy(struct toku_rbt_tree *rbinfo) {
    toku_rbt_clear(rbinfo);
Yoni Fogel's avatar
Yoni Fogel committed
137
    rbinfo->rb_free(rbinfo);
Yoni Fogel's avatar
Yoni Fogel committed
138 139
}

Yoni Fogel's avatar
Yoni Fogel committed
140
int toku_rbt_finger_delete(struct toku_rbt_node* node, struct toku_rbt_tree *rbinfo) {
Yoni Fogel's avatar
Yoni Fogel committed
141 142
    int r = ENOSYS;

Yoni Fogel's avatar
Yoni Fogel committed
143
    if (!rbinfo || !node || node == RBNULL) { r = EINVAL; goto cleanup; }
144
    toku_rbt__delete(rbinfo, &rbinfo->rb_root, node);
Yoni Fogel's avatar
Yoni Fogel committed
145
    r = 0;
Yoni Fogel's avatar
Yoni Fogel committed
146 147 148 149
cleanup:
    return r;
}

Yoni Fogel's avatar
Yoni Fogel committed
150
int toku_rbt_lookup(
Yoni Fogel's avatar
Yoni Fogel committed
151
    int mode,
Yoni Fogel's avatar
Yoni Fogel committed
152
    const  toku_interval*    key,
Yoni Fogel's avatar
Yoni Fogel committed
153 154 155
    struct toku_rbt_tree*    rbinfo,
    struct toku_rbt_node**   pinsert_finger,
    struct toku_rbt_node**   pelement_finger,
Yoni Fogel's avatar
Yoni Fogel committed
156
           toku_range** pdata
Yoni Fogel's avatar
Yoni Fogel committed
157 158 159 160 161 162 163 164 165 166 167
)
{
    int r = ENOSYS;

    if (!rbinfo || !rbinfo->rb_root || !pdata ||
        !pinsert_finger || !pelement_finger ||
        (
           (mode == RB_LUFIRST || mode == RB_LULAST) != (key == NULL)
        )) {
        r = EINVAL; goto cleanup; }
    
Yoni Fogel's avatar
Yoni Fogel committed
168
    *pelement_finger = toku_rbt__lookup(mode, key, rbinfo, pinsert_finger);
Yoni Fogel's avatar
Yoni Fogel committed
169 170 171 172 173 174 175 176 177 178 179
    *pdata = *pelement_finger == RBNULL ? NULL : RB_GET((*pelement_finger), key);
    r = 0;
cleanup:
    return r;
}

/* --------------------------------------------------------------------- */

/* Search for and if not found and insert is true, will add a new
** node in. Returns a pointer to the new node, or the node found
*/
Yoni Fogel's avatar
Yoni Fogel committed
180 181
static struct toku_rbt_node *
toku_rbt__traverse(int insert, const toku_range *key, struct toku_rbt_tree *rbinfo)
Yoni Fogel's avatar
Yoni Fogel committed
182
{
Yoni Fogel's avatar
Yoni Fogel committed
183 184 185 186 187 188 189 190 191 192 193 194 195
    struct toku_rbt_node *x,*y;
    int cmp;
    int found=0;
    int cmpmods();

    y=RBNULL; /* points to the parent of x */
    x=rbinfo->rb_root;

    /* walk x down the tree */
    while(x!=RBNULL && found==0)
    {
        y=x;
        /* printf("key=%s, RB_GET(x, key)=%s\n", key, RB_GET(x, key)); */
Yoni Fogel's avatar
Yoni Fogel committed
196
        cmp=rbinfo->rb_cmp(key->ends.left, x->key.ends.left);
Yoni Fogel's avatar
Yoni Fogel committed
197 198 199 200 201 202 203 204 205 206 207 208 209

        if (cmp<0)
            x=x->left;
        else if (cmp>0)
            x=x->right;
        else
            found=1;
    }

    if (found || !insert)
        return(x);

    return toku_rbt__insert(key, rbinfo, y);
Yoni Fogel's avatar
Yoni Fogel committed
210 211
}

Yoni Fogel's avatar
Yoni Fogel committed
212 213
static struct toku_rbt_node* toku_rbt__insert(
    const  toku_range* key,
Yoni Fogel's avatar
Yoni Fogel committed
214 215
    struct toku_rbt_tree* rbinfo,
    struct toku_rbt_node* parent
Yoni Fogel's avatar
Yoni Fogel committed
216
) {
Yoni Fogel's avatar
Yoni Fogel committed
217 218 219
    struct toku_rbt_node* x;
    struct toku_rbt_node* y = parent;
    struct toku_rbt_node* z;
Yoni Fogel's avatar
Yoni Fogel committed
220 221 222 223 224
    int cmp;

    if (parent == NULL) {
        /* This means we have NOT actually located the right spot.
           Locate it with traverse and then insert. */
Yoni Fogel's avatar
Yoni Fogel committed
225
        return toku_rbt__traverse(1, key, rbinfo);
Yoni Fogel's avatar
Yoni Fogel committed
226 227
    }

Yoni Fogel's avatar
Yoni Fogel committed
228 229 230 231 232 233 234 235 236 237 238 239 240 241
    if ((z=toku_rbt__alloc(rbinfo))==NULL)
    {
        /* Whoops, no memory */
        return(RBNULL);
    }

    RB_SET(z, key, key);
    z->up=y;
    if (y==RBNULL)
    {
        rbinfo->rb_root=z;
    }
    else
    {
Yoni Fogel's avatar
Yoni Fogel committed
242
        cmp=rbinfo->rb_cmp(z->key.ends.left, y->key.ends.left);
Yoni Fogel's avatar
Yoni Fogel committed
243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335
        if (cmp<0)
            y->left=z;
        else
            y->right=z;
    }

    z->left=RBNULL;
    z->right=RBNULL;

    /* colour this new node red */
    z->colour=RED;

    /* Having added a red node, we must now walk back up the tree balancing
    ** it, by a series of rotations and changing of colours
    */
    x=z;

    /* While we are not at the top and our parent node is red
    ** N.B. Since the root node is garanteed black, then we
    ** are also going to stop if we are the child of the root
    */

    while(x != rbinfo->rb_root && (x->up->colour == RED))
    {
        /* if our parent is on the left side of our grandparent */
        if (x->up == x->up->up->left)
        {
            /* get the right side of our grandparent (uncle?) */
            y=x->up->up->right;
            if (y->colour == RED)
            {
                /* make our parent black */
                x->up->colour = BLACK;
                /* make our uncle black */
                y->colour = BLACK;
                /* make our grandparent red */
                x->up->up->colour = RED;

                /* now consider our grandparent */
                x=x->up->up;
            }
            else
            {
                /* if we are on the right side of our parent */
                if (x == x->up->right)
                {
                    /* Move up to our parent */
                    x=x->up;
                    toku_rbt__left_rotate(&rbinfo->rb_root, x);
                }

                /* make our parent black */
                x->up->colour = BLACK;
                /* make our grandparent red */
                x->up->up->colour = RED;
                /* right rotate our grandparent */
                toku_rbt__right_rotate(&rbinfo->rb_root, x->up->up);
            }
        }
        else
        {
            /* everything here is the same as above, but
            ** exchanging left for right
            */

            y=x->up->up->left;
            if (y->colour == RED)
            {
                x->up->colour = BLACK;
                y->colour = BLACK;
                x->up->up->colour = RED;

                x=x->up->up;
            }
            else
            {
                if (x == x->up->left)
                {
                    x=x->up;
                    toku_rbt__right_rotate(&rbinfo->rb_root, x);
                }

                x->up->colour = BLACK;
                x->up->up->colour = RED;
                toku_rbt__left_rotate(&rbinfo->rb_root, x->up->up);
            }
        }
    }

    /* Set the root node black */
    (rbinfo->rb_root)->colour = BLACK;

    return(z);
Yoni Fogel's avatar
Yoni Fogel committed
336 337 338 339
}

/* Search for a key according to mode (see redblack.h)
*/
Yoni Fogel's avatar
Yoni Fogel committed
340
static struct toku_rbt_node *
Yoni Fogel's avatar
Yoni Fogel committed
341
toku_rbt__lookup(int mode, const toku_interval *key, struct toku_rbt_tree *rbinfo, struct toku_rbt_node** pinsert_finger)
Yoni Fogel's avatar
Yoni Fogel committed
342
{
Yoni Fogel's avatar
Yoni Fogel committed
343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377
    struct toku_rbt_node *x,*y;
    int cmp = 0;
    int found=0;

    y=RBNULL; /* points to the parent of x */
    x=rbinfo->rb_root;

    if (mode==RB_LUFIRST)
    {
        /* Keep going left until we hit a NULL */
        while(x!=RBNULL)
        {
            y=x;
            x=x->left;
        }

        return(y);
    }
    else if (mode==RB_LULAST)
    {
        /* Keep going right until we hit a NULL */
        while(x!=RBNULL)
        {
            y=x;
            x=x->right;
        }

        return(y);
    }

    /* walk x down the tree */
    while(x!=RBNULL && found==0)
    {
        y=x;
        /* printf("key=%s, RB_GET(x, key)=%s\n", key, RB_GET(x, key)); */
Yoni Fogel's avatar
Yoni Fogel committed
378
        cmp=rbinfo->rb_cmp(key->left, x->key.ends.left);
Yoni Fogel's avatar
Yoni Fogel committed
379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419


        if (cmp<0)
            x=x->left;
        else if (cmp>0)
            x=x->right;
        else
            found=1;
    }
    if (pinsert_finger) *pinsert_finger = y;

    if (found && (mode==RB_LUEQUAL || mode==RB_LUGTEQ || mode==RB_LULTEQ))
        return(x);
    
    if (!found && (mode==RB_LUEQUAL || mode==RB_LUNEXT || mode==RB_LUPREV))
        return(RBNULL);
    
    if (mode==RB_LUGTEQ || (!found && mode==RB_LUGREAT))
    {
        if (cmp>0)
            return(toku_rbt__successor(y));
        else
            return(y);
    }

    if (mode==RB_LULTEQ || (!found && mode==RB_LULESS))
    {
        if (cmp<0)
            return(toku_rbt__predecessor(y));
        else
            return(y);
    }

    if (mode==RB_LUNEXT || (found && mode==RB_LUGREAT))
        return(toku_rbt__successor(x));

    if (mode==RB_LUPREV || (found && mode==RB_LULESS))
        return(toku_rbt__predecessor(x));
    
    /* Shouldn't get here */
    return(RBNULL);
Yoni Fogel's avatar
Yoni Fogel committed
420 421 422 423 424 425 426
}

/*
 * Destroy all the elements blow us in the tree
 * only useful as part of a complete tree destroy.
 */
static void
427
toku_rbt__destroy(struct toku_rbt_tree *rbinfo, struct toku_rbt_node *x)
Yoni Fogel's avatar
Yoni Fogel committed
428
{
Yoni Fogel's avatar
Yoni Fogel committed
429 430 431
    if (x!=RBNULL)
    {
        if (x->left!=RBNULL)
432
            toku_rbt__destroy(rbinfo, x->left);
Yoni Fogel's avatar
Yoni Fogel committed
433
        if (x->right!=RBNULL)
434
            toku_rbt__destroy(rbinfo, x->right);
Yoni Fogel's avatar
Yoni Fogel committed
435 436
        toku_rbt__free(rbinfo,x);
    }
Yoni Fogel's avatar
Yoni Fogel committed
437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453
}

/*
** Rotate our tree thus:-
**
**             X        rb_left_rotate(X)--->            Y
**           /   \                                     /   \
**          A     Y     <---rb_right_rotate(Y)        X     C
**              /   \                               /   \
**             B     C                             A     B
**
** N.B. This does not change the ordering.
**
** We assume that neither X or Y is NULL
*/

static void
Yoni Fogel's avatar
Yoni Fogel committed
454
toku_rbt__left_rotate(struct toku_rbt_node **rootp, struct toku_rbt_node *x)
Yoni Fogel's avatar
Yoni Fogel committed
455
{
Yoni Fogel's avatar
Yoni Fogel committed
456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495
    struct toku_rbt_node *y;

    assert(x!=RBNULL);
    assert(x->right!=RBNULL);

    y=x->right; /* set Y */

    /* Turn Y's left subtree into X's right subtree (move B)*/
    x->right = y->left;

    /* If B is not null, set it's parent to be X */
    if (y->left != RBNULL)
        y->left->up = x;

    /* Set Y's parent to be what X's parent was */
    y->up = x->up;

    /* if X was the root */
    if (x->up == RBNULL)
    {
        *rootp=y;
    }
    else
    {
        /* Set X's parent's left or right pointer to be Y */
        if (x == x->up->left)
        {
            x->up->left=y;
        }
        else
        {
            x->up->right=y;
        }
    }

    /* Put X on Y's left */
    y->left=x;

    /* Set X's parent to be Y */
    x->up = y;
Yoni Fogel's avatar
Yoni Fogel committed
496 497 498
}

static void
Yoni Fogel's avatar
Yoni Fogel committed
499
toku_rbt__right_rotate(struct toku_rbt_node **rootp, struct toku_rbt_node *y)
Yoni Fogel's avatar
Yoni Fogel committed
500
{
Yoni Fogel's avatar
Yoni Fogel committed
501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540
    struct toku_rbt_node *x;

    assert(y!=RBNULL);
    assert(y->left!=RBNULL);

    x=y->left; /* set X */

    /* Turn X's right subtree into Y's left subtree (move B) */
    y->left = x->right;

    /* If B is not null, set it's parent to be Y */
    if (x->right != RBNULL)
        x->right->up = y;

    /* Set X's parent to be what Y's parent was */
    x->up = y->up;

    /* if Y was the root */
    if (y->up == RBNULL)
    {
        *rootp=x;
    }
    else
    {
        /* Set Y's parent's left or right pointer to be X */
        if (y == y->up->left)
        {
            y->up->left=x;
        }
        else
        {
            y->up->right=x;
        }
    }

    /* Put Y on X's right */
    x->right=y;

    /* Set Y's parent to be X */
    y->up = x;
Yoni Fogel's avatar
Yoni Fogel committed
541 542 543 544
}

/* Return a pointer to the smallest key greater than x
*/
Yoni Fogel's avatar
Yoni Fogel committed
545 546
static struct toku_rbt_node *
toku_rbt__successor(const struct toku_rbt_node *x)
Yoni Fogel's avatar
Yoni Fogel committed
547
{
Yoni Fogel's avatar
Yoni Fogel committed
548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571
    struct toku_rbt_node *y;

    if (x->right!=RBNULL)
    {
        /* If right is not NULL then go right one and
        ** then keep going left until we find a node with
        ** no left pointer.
        */
        for (y=x->right; y->left!=RBNULL; y=y->left);
    }
    else
    {
        /* Go up the tree until we get to a node that is on the
        ** left of its parent (or the root) and then return the
        ** parent.
        */
        y=x->up;
        while(y!=RBNULL && x==y->right)
        {
            x=y;
            y=y->up;
        }
    }
    return(y);
Yoni Fogel's avatar
Yoni Fogel committed
572 573 574 575
}

/* Return a pointer to the largest key smaller than x
*/
Yoni Fogel's avatar
Yoni Fogel committed
576 577
static struct toku_rbt_node *
toku_rbt__predecessor(const struct toku_rbt_node *x)
Yoni Fogel's avatar
Yoni Fogel committed
578
{
Yoni Fogel's avatar
Yoni Fogel committed
579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602
    struct toku_rbt_node *y;

    if (x->left!=RBNULL)
    {
        /* If left is not NULL then go left one and
        ** then keep going right until we find a node with
        ** no right pointer.
        */
        for (y=x->left; y->right!=RBNULL; y=y->right);
    }
    else
    {
        /* Go up the tree until we get to a node that is on the
        ** right of its parent (or the root) and then return the
        ** parent.
        */
        y=x->up;
        while(y!=RBNULL && x==y->left)
        {
            x=y;
            y=y->up;
        }
    }
    return(y);
Yoni Fogel's avatar
Yoni Fogel committed
603 604
}

Yoni Fogel's avatar
Yoni Fogel committed
605 606
int toku_rbt_finger_predecessor(struct toku_rbt_node** pfinger,
                                toku_range** ppred_data) {
Yoni Fogel's avatar
Yoni Fogel committed
607 608 609 610
    int r = ENOSYS;

    if (!pfinger || !*pfinger ||
        *pfinger == RBNULL || !ppred_data) { r = EINVAL; goto cleanup; }
Yoni Fogel's avatar
Yoni Fogel committed
611
    *pfinger = toku_rbt__predecessor(*pfinger);
Yoni Fogel's avatar
Yoni Fogel committed
612 613
    *ppred_data = (toku_range*)
        ((*pfinger==RBNULL) ? NULL : RB_GET((*pfinger), key));
Yoni Fogel's avatar
Yoni Fogel committed
614 615 616 617 618
    r = 0;
cleanup:
    return r;
}

Yoni Fogel's avatar
Yoni Fogel committed
619 620
int toku_rbt_finger_successor(struct toku_rbt_node** pfinger,
                                toku_range** psucc_data) {
Yoni Fogel's avatar
Yoni Fogel committed
621 622
    int r = ENOSYS;

Yoni Fogel's avatar
Yoni Fogel committed
623 624
    if (!pfinger || !*pfinger || !psucc_data) { r = EINVAL; goto cleanup; }
    if (*pfinger == RBNULL)                   { r = EDOM;   goto cleanup; }
Yoni Fogel's avatar
Yoni Fogel committed
625
    *pfinger = toku_rbt__successor(*pfinger);
Yoni Fogel's avatar
Yoni Fogel committed
626 627
    *psucc_data = (toku_range*)
        ((*pfinger==RBNULL) ? NULL : RB_GET((*pfinger), key));
Yoni Fogel's avatar
Yoni Fogel committed
628 629 630 631 632
    r = 0;
cleanup:
    return r;
}

Yoni Fogel's avatar
Yoni Fogel committed
633
int toku_rbt_finger_insert(
Yoni Fogel's avatar
Yoni Fogel committed
634
    const  toku_range* key,
Yoni Fogel's avatar
Yoni Fogel committed
635 636
    struct toku_rbt_tree* rbinfo,
    struct toku_rbt_node* parent
Yoni Fogel's avatar
Yoni Fogel committed
637
) {
Yoni Fogel's avatar
Yoni Fogel committed
638 639 640
    if (!key || !rbinfo || !parent) return EINVAL;
    toku_rbt__insert(key, rbinfo, parent);
    return 0;
Yoni Fogel's avatar
Yoni Fogel committed
641 642 643 644 645
}

/* Delete the node z, and free up the space
*/
static void
646
toku_rbt__delete(struct toku_rbt_tree* rbinfo, struct toku_rbt_node **rootp, struct toku_rbt_node *z)
Yoni Fogel's avatar
Yoni Fogel committed
647
{
Yoni Fogel's avatar
Yoni Fogel committed
648
    struct toku_rbt_node *x, *y;
Yoni Fogel's avatar
Yoni Fogel committed
649

Yoni Fogel's avatar
Yoni Fogel committed
650 651 652 653
    if (z->left == RBNULL || z->right == RBNULL)
        y=z;
    else
        y=toku_rbt__successor(z);
Yoni Fogel's avatar
Yoni Fogel committed
654

Yoni Fogel's avatar
Yoni Fogel committed
655 656 657 658
    if (y->left != RBNULL)
        x=y->left;
    else
        x=y->right;
Yoni Fogel's avatar
Yoni Fogel committed
659

Yoni Fogel's avatar
Yoni Fogel committed
660
    x->up = y->up;
Yoni Fogel's avatar
Yoni Fogel committed
661

Yoni Fogel's avatar
Yoni Fogel committed
662 663 664 665 666 667 668 669 670 671 672
    if (y->up == RBNULL)
    {
        *rootp=x;
    }
    else
    {
        if (y==y->up->left)
            y->up->left = x;
        else
            y->up->right = x;
    }
Yoni Fogel's avatar
Yoni Fogel committed
673

Yoni Fogel's avatar
Yoni Fogel committed
674 675 676 677
    if (y!=z)
    {
        RB_SET(z, key, RB_GET(y, key));
    }
Yoni Fogel's avatar
Yoni Fogel committed
678

Yoni Fogel's avatar
Yoni Fogel committed
679 680
    if (y->colour == BLACK)
        toku_rbt__delete_fix(rootp, x);
Yoni Fogel's avatar
Yoni Fogel committed
681

Yoni Fogel's avatar
Yoni Fogel committed
682
    toku_rbt__free(rbinfo,y);
Yoni Fogel's avatar
Yoni Fogel committed
683 684
}

Yoni Fogel's avatar
Yoni Fogel committed
685
/* Restore the reb-black properties after a delete */
Yoni Fogel's avatar
Yoni Fogel committed
686
static void
Yoni Fogel's avatar
Yoni Fogel committed
687
toku_rbt__delete_fix(struct toku_rbt_node **rootp, struct toku_rbt_node *x)
Yoni Fogel's avatar
Yoni Fogel committed
688
{
Yoni Fogel's avatar
Yoni Fogel committed
689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760
    struct toku_rbt_node *w;

    while (x!=*rootp && x->colour==BLACK)
    {
        if (x==x->up->left)
        {
            w=x->up->right;
            if (w->colour==RED)
            {
                w->colour=BLACK;
                x->up->colour=RED;
                toku_rbt__left_rotate(rootp, x->up);
                w=x->up->right;
            }

            if (w->left->colour==BLACK && w->right->colour==BLACK)
            {
                w->colour=RED;
                x=x->up;
            }
            else
            {
                if (w->right->colour == BLACK)
                {
                    w->left->colour=BLACK;
                    w->colour=RED;
                    toku_rbt__right_rotate(rootp, w);
                    w=x->up->right;
                }


                w->colour=x->up->colour;
                x->up->colour = BLACK;
                w->right->colour = BLACK;
                toku_rbt__left_rotate(rootp, x->up);
                x=*rootp;
            }
        }
        else
        {
            w=x->up->left;
            if (w->colour==RED)
            {
                w->colour=BLACK;
                x->up->colour=RED;
                toku_rbt__right_rotate(rootp, x->up);
                w=x->up->left;
            }

            if (w->right->colour==BLACK && w->left->colour==BLACK)
            {
                w->colour=RED;
                x=x->up;
            }
            else
            {
                if (w->left->colour == BLACK)
                {
                    w->right->colour=BLACK;
                    w->colour=RED;
                    toku_rbt__left_rotate(rootp, w);
                    w=x->up->left;
                }

                w->colour=x->up->colour;
                x->up->colour = BLACK;
                w->left->colour = BLACK;
                toku_rbt__right_rotate(rootp, x->up);
                x=*rootp;
            }
        }
    }
Yoni Fogel's avatar
Yoni Fogel committed
761

Yoni Fogel's avatar
Yoni Fogel committed
762
    x->colour=BLACK;
Yoni Fogel's avatar
Yoni Fogel committed
763
}