rbtree.c File Reference

#include "postgres.h"
#include "lib/rbtree.h"

Include dependency graph for rbtree.c:

Go to the source code of this file.

Data Structures
struct	RBTree

Macros
#define	RBTBLACK   (0)
#define	RBTRED   (1)
#define	RBTNIL   (&sentinel)

Functions
RBTree *	rbt_create (Size node_size, rbt_comparator comparator, rbt_combiner combiner, rbt_allocfunc allocfunc, rbt_freefunc freefunc, void *arg)
static void	rbt_copy_data (RBTree *rbt, RBTNode *dest, const RBTNode *src)
RBTNode *	rbt_find (RBTree *rbt, const RBTNode *data)
RBTNode *	rbt_leftmost (RBTree *rbt)
static void	rbt_rotate_left (RBTree *rbt, RBTNode *x)
static void	rbt_rotate_right (RBTree *rbt, RBTNode *x)
static void	rbt_insert_fixup (RBTree *rbt, RBTNode *x)
RBTNode *	rbt_insert (RBTree *rbt, const RBTNode *data, bool *isNew)
static void	rbt_delete_fixup (RBTree *rbt, RBTNode *x)
static void	rbt_delete_node (RBTree *rbt, RBTNode *z)
void	rbt_delete (RBTree *rbt, RBTNode *node)
static RBTNode *	rbt_left_right_iterator (RBTreeIterator *iter)
static RBTNode *	rbt_right_left_iterator (RBTreeIterator *iter)
void	rbt_begin_iterate (RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
RBTNode *	rbt_iterate (RBTreeIterator *iter)

Variables
static RBTNode	sentinel

Macro Definition Documentation

RBTBLACK

#define RBTBLACK   (0)

Definition at line 35 of file rbtree.c.

Referenced by rbt_delete_fixup(), rbt_delete_node(), and rbt_insert_fixup().

RBTNIL

#define RBTNIL   (&sentinel)

Definition at line 61 of file rbtree.c.

Referenced by rbt_begin_iterate(), rbt_create(), rbt_delete_node(), rbt_find(), rbt_insert(), rbt_left_right_iterator(), rbt_leftmost(), rbt_right_left_iterator(), rbt_rotate_left(), and rbt_rotate_right().

RBTRED

#define RBTRED   (1)

Definition at line 36 of file rbtree.c.

Referenced by rbt_delete_fixup(), rbt_insert(), and rbt_insert_fixup().

Function Documentation

rbt_begin_iterate()

void rbt_begin_iterate	(	RBTree *	rbt,
		RBTOrderControl	ctrl,
		RBTreeIterator *	iter
	)

Definition at line 740 of file rbtree.c.

References elog, ERROR, RBTreeIterator::is_over, RBTreeIterator::iterate, RBTreeIterator::last_visited, LeftRightWalk, RBTreeIterator::rbt, rbt_left_right_iterator(), rbt_right_left_iterator(), RBTNIL, RightLeftWalk, and RBTree::root.

Referenced by ginBeginBAScan(), testleftright(), and testrightleft().

{
    /* Common initialization for all traversal orders */
    iter->rbt = rbt;
    iter->last_visited = NULL;
    iter->is_over = (rbt->root == RBTNIL);

    switch (ctrl)
    {
        case LeftRightWalk:     /* visit left, then self, then right */
            iter->iterate = rbt_left_right_iterator;
            break;
        case RightLeftWalk:     /* visit right, then self, then left */
            iter->iterate = rbt_right_left_iterator;
            break;
        default:
            elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
    }
}

rbt_copy_data()

static void rbt_copy_data ( RBTree *  rbt, RBTNode *  dest, const RBTNode *  src  )

inlinestatic

Definition at line 127 of file rbtree.c.

References RBTree::node_size.

Referenced by rbt_delete_node(), and rbt_insert().

{
    memcpy(dest + 1, src + 1, rbt->node_size - sizeof(RBTNode));
}

rbt_create()

RBTree* rbt_create	(	Size	node_size,
		rbt_comparator	comparator,
		rbt_combiner	combiner,
		rbt_allocfunc	allocfunc,
		rbt_freefunc	freefunc,
		void *	arg
	)

Definition at line 102 of file rbtree.c.

References RBTree::allocfunc, RBTree::arg, Assert, RBTree::combiner, RBTree::comparator, RBTree::freefunc, RBTree::node_size, palloc(), RBTNIL, and RBTree::root.

Referenced by create_int_rbtree(), and ginInitBA().

{
    RBTree     *tree = (RBTree *) palloc(sizeof(RBTree));

    Assert(node_size > sizeof(RBTNode));

    tree->root = RBTNIL;
    tree->node_size = node_size;
    tree->comparator = comparator;
    tree->combiner = combiner;
    tree->allocfunc = allocfunc;
    tree->freefunc = freefunc;

    tree->arg = arg;

    return tree;
}

rbt_delete()

void rbt_delete	(	RBTree *	rbt,
		RBTNode *	node
	)

Definition at line 633 of file rbtree.c.

References rbt_delete_node().

Referenced by testdelete().

{
    rbt_delete_node(rbt, node);
}

rbt_delete_fixup()

static void rbt_delete_fixup ( RBTree *  rbt, RBTNode *  x  )

static

Definition at line 459 of file rbtree.c.

References RBTNode::color, RBTNode::left, RBTNode::parent, rbt_rotate_left(), rbt_rotate_right(), RBTBLACK, RBTRED, RBTNode::right, and RBTree::root.

Referenced by rbt_delete_node().

{
    /*
     * x is always a black node.  Initially, it is the former child of the
     * deleted node.  Each iteration of this loop moves it higher up in the
     * tree.
     */
    while (x != rbt->root && x->color == RBTBLACK)
    {
        /*
         * Left and right cases are symmetric.  Any nodes that are children of
         * x have a black-height one less than the remainder of the nodes in
         * the tree.  We rotate and recolor nodes to move the problem up the
         * tree: at some stage we'll either fix the problem, or reach the root
         * (where the black-height is allowed to decrease).
         */
        if (x == x->parent->left)
        {
            RBTNode    *w = x->parent->right;

            if (w->color == RBTRED)
            {
                w->color = RBTBLACK;
                x->parent->color = RBTRED;

                rbt_rotate_left(rbt, x->parent);
                w = x->parent->right;
            }

            if (w->left->color == RBTBLACK && w->right->color == RBTBLACK)
            {
                w->color = RBTRED;

                x = x->parent;
            }
            else
            {
                if (w->right->color == RBTBLACK)
                {
                    w->left->color = RBTBLACK;
                    w->color = RBTRED;

                    rbt_rotate_right(rbt, w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = RBTBLACK;
                w->right->color = RBTBLACK;

                rbt_rotate_left(rbt, x->parent);
                x = rbt->root;  /* Arrange for loop to terminate. */
            }
        }
        else
        {
            RBTNode    *w = x->parent->left;

            if (w->color == RBTRED)
            {
                w->color = RBTBLACK;
                x->parent->color = RBTRED;

                rbt_rotate_right(rbt, x->parent);
                w = x->parent->left;
            }

            if (w->right->color == RBTBLACK && w->left->color == RBTBLACK)
            {
                w->color = RBTRED;

                x = x->parent;
            }
            else
            {
                if (w->left->color == RBTBLACK)
                {
                    w->right->color = RBTBLACK;
                    w->color = RBTRED;

                    rbt_rotate_left(rbt, w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = RBTBLACK;
                w->left->color = RBTBLACK;

                rbt_rotate_right(rbt, x->parent);
                x = rbt->root;  /* Arrange for loop to terminate. */
            }
        }
    }
    x->color = RBTBLACK;
}

rbt_delete_node()

static void rbt_delete_node ( RBTree *  rbt, RBTNode *  z  )

static

Definition at line 557 of file rbtree.c.

References RBTree::arg, RBTNode::color, RBTree::freefunc, RBTNode::left, RBTNode::parent, rbt_copy_data(), rbt_delete_fixup(), RBTBLACK, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by rbt_delete().

{
    RBTNode    *x,
               *y;

    /* This is just paranoia: we should only get called on a valid node */
    if (!z || z == RBTNIL)
        return;

    /*
     * y is the node that will actually be removed from the tree.  This will
     * be z if z has fewer than two children, or the tree successor of z
     * otherwise.
     */
    if (z->left == RBTNIL || z->right == RBTNIL)
    {
        /* y has a RBTNIL node as a child */
        y = z;
    }
    else
    {
        /* find tree successor */
        y = z->right;
        while (y->left != RBTNIL)
            y = y->left;
    }

    /* x is y's only child */
    if (y->left != RBTNIL)
        x = y->left;
    else
        x = y->right;

    /* Remove y from the tree. */
    x->parent = y->parent;
    if (y->parent)
    {
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    }
    else
    {
        rbt->root = x;
    }

    /*
     * If we removed the tree successor of z rather than z itself, then move
     * the data for the removed node to the one we were supposed to remove.
     */
    if (y != z)
        rbt_copy_data(rbt, z, y);

    /*
     * Removing a black node might make some paths from root to leaf contain
     * fewer black nodes than others, or it might make two red nodes adjacent.
     */
    if (y->color == RBTBLACK)
        rbt_delete_fixup(rbt, x);

    /* Now we can recycle the y node */
    if (rbt->freefunc)
        rbt->freefunc(y, rbt->arg);
}

rbt_find()

RBTNode* rbt_find	(	RBTree *	rbt,
		const RBTNode *	data
	)

Definition at line 145 of file rbtree.c.

References RBTree::arg, cmp(), RBTree::comparator, RBTNode::left, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by testdelete(), and testfind().

{
    RBTNode    *node = rbt->root;

    while (node != RBTNIL)
    {
        int         cmp = rbt->comparator(data, node, rbt->arg);

        if (cmp == 0)
            return node;
        else if (cmp < 0)
            node = node->left;
        else
            node = node->right;
    }

    return NULL;
}

rbt_insert()

RBTNode* rbt_insert	(	RBTree *	rbt,
		const RBTNode *	data,
		bool *	isNew
	)

Definition at line 391 of file rbtree.c.

References RBTree::allocfunc, RBTree::arg, cmp(), RBTNode::color, RBTree::combiner, RBTree::comparator, RBTNode::left, RBTNode::parent, rbt_copy_data(), rbt_insert_fixup(), RBTNIL, RBTRED, RBTNode::right, and RBTree::root.

Referenced by ginInsertBAEntry(), and rbt_populate().

{
    RBTNode    *current,
               *parent,
               *x;
    int         cmp;

    /* find where node belongs */
    current = rbt->root;
    parent = NULL;
    cmp = 0;                    /* just to prevent compiler warning */

    while (current != RBTNIL)
    {
        cmp = rbt->comparator(data, current, rbt->arg);
        if (cmp == 0)
        {
            /*
             * Found node with given key.  Apply combiner.
             */
            rbt->combiner(current, data, rbt->arg);
            *isNew = false;
            return current;
        }
        parent = current;
        current = (cmp < 0) ? current->left : current->right;
    }

    /*
     * Value is not present, so create a new node containing data.
     */
    *isNew = true;

    x = rbt->allocfunc(rbt->arg);

    x->color = RBTRED;

    x->left = RBTNIL;
    x->right = RBTNIL;
    x->parent = parent;
    rbt_copy_data(rbt, x, data);

    /* insert node in tree */
    if (parent)
    {
        if (cmp < 0)
            parent->left = x;
        else
            parent->right = x;
    }
    else
    {
        rbt->root = x;
    }

    rbt_insert_fixup(rbt, x);

    return x;
}

rbt_insert_fixup()

static void rbt_insert_fixup ( RBTree *  rbt, RBTNode *  x  )

static

Definition at line 282 of file rbtree.c.

References RBTNode::color, RBTNode::left, RBTNode::parent, rbt_rotate_left(), rbt_rotate_right(), RBTBLACK, RBTRED, RBTNode::right, and RBTree::root.

Referenced by rbt_insert().

{
    /*
     * x is always a red node.  Initially, it is the newly inserted node. Each
     * iteration of this loop moves it higher up in the tree.
     */
    while (x != rbt->root && x->parent->color == RBTRED)
    {
        /*
         * x and x->parent are both red.  Fix depends on whether x->parent is
         * a left or right child.  In either case, we define y to be the
         * "uncle" of x, that is, the other child of x's grandparent.
         *
         * If the uncle is red, we flip the grandparent to red and its two
         * children to black.  Then we loop around again to check whether the
         * grandparent still has a problem.
         *
         * If the uncle is black, we will perform one or two "rotations" to
         * balance the tree.  Either x or x->parent will take the
         * grandparent's position in the tree and recolored black, and the
         * original grandparent will be recolored red and become a child of
         * that node. This always leaves us with a valid red-black tree, so
         * the loop will terminate.
         */
        if (x->parent == x->parent->parent->left)
        {
            RBTNode    *y = x->parent->parent->right;

            if (y->color == RBTRED)
            {
                /* uncle is RBTRED */
                x->parent->color = RBTBLACK;
                y->color = RBTBLACK;
                x->parent->parent->color = RBTRED;

                x = x->parent->parent;
            }
            else
            {
                /* uncle is RBTBLACK */
                if (x == x->parent->right)
                {
                    /* make x a left child */
                    x = x->parent;
                    rbt_rotate_left(rbt, x);
                }

                /* recolor and rotate */
                x->parent->color = RBTBLACK;
                x->parent->parent->color = RBTRED;

                rbt_rotate_right(rbt, x->parent->parent);
            }
        }
        else
        {
            /* mirror image of above code */
            RBTNode    *y = x->parent->parent->left;

            if (y->color == RBTRED)
            {
                /* uncle is RBTRED */
                x->parent->color = RBTBLACK;
                y->color = RBTBLACK;
                x->parent->parent->color = RBTRED;

                x = x->parent->parent;
            }
            else
            {
                /* uncle is RBTBLACK */
                if (x == x->parent->left)
                {
                    x = x->parent;
                    rbt_rotate_right(rbt, x);
                }
                x->parent->color = RBTBLACK;
                x->parent->parent->color = RBTRED;

                rbt_rotate_left(rbt, x->parent->parent);
            }
        }
    }

    /*
     * The root may already have been black; if not, the black-height of every
     * node in the tree increases by one.
     */
    rbt->root->color = RBTBLACK;
}

rbt_iterate()

RBTNode* rbt_iterate

(

RBTreeIterator *

iter

)

Definition at line 764 of file rbtree.c.

References RBTreeIterator::is_over, and RBTreeIterator::iterate.

Referenced by ginGetBAEntry(), testleftright(), and testrightleft().

{
    if (iter->is_over)
        return NULL;

    return iter->iterate(iter);
}

rbt_left_right_iterator()

static RBTNode* rbt_left_right_iterator ( RBTreeIterator *  iter )

static

Definition at line 643 of file rbtree.c.

References RBTreeIterator::is_over, RBTreeIterator::last_visited, RBTNode::left, RBTNode::parent, RBTreeIterator::rbt, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by rbt_begin_iterate().

{
    if (iter->last_visited == NULL)
    {
        iter->last_visited = iter->rbt->root;
        while (iter->last_visited->left != RBTNIL)
            iter->last_visited = iter->last_visited->left;

        return iter->last_visited;
    }

    if (iter->last_visited->right != RBTNIL)
    {
        iter->last_visited = iter->last_visited->right;
        while (iter->last_visited->left != RBTNIL)
            iter->last_visited = iter->last_visited->left;

        return iter->last_visited;
    }

    for (;;)
    {
        RBTNode    *came_from = iter->last_visited;

        iter->last_visited = iter->last_visited->parent;
        if (iter->last_visited == NULL)
        {
            iter->is_over = true;
            break;
        }

        if (iter->last_visited->left == came_from)
            break;              /* came from left sub-tree, return current
                                 * node */

        /* else - came from right sub-tree, continue to move up */
    }

    return iter->last_visited;
}

rbt_leftmost()

RBTNode* rbt_leftmost

(

RBTree *

rbt

)

Definition at line 173 of file rbtree.c.

References RBTNode::left, RBTNIL, and RBTree::root.

Referenced by testdelete(), and testleftmost().

{
    RBTNode    *node = rbt->root;
    RBTNode    *leftmost = rbt->root;

    while (node != RBTNIL)
    {
        leftmost = node;
        node = node->left;
    }

    if (leftmost != RBTNIL)
        return leftmost;

    return NULL;
}

rbt_right_left_iterator()

static RBTNode* rbt_right_left_iterator ( RBTreeIterator *  iter )

static

Definition at line 685 of file rbtree.c.

References RBTreeIterator::is_over, RBTreeIterator::last_visited, RBTNode::left, RBTNode::parent, RBTreeIterator::rbt, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by rbt_begin_iterate().

{
    if (iter->last_visited == NULL)
    {
        iter->last_visited = iter->rbt->root;
        while (iter->last_visited->right != RBTNIL)
            iter->last_visited = iter->last_visited->right;

        return iter->last_visited;
    }

    if (iter->last_visited->left != RBTNIL)
    {
        iter->last_visited = iter->last_visited->left;
        while (iter->last_visited->right != RBTNIL)
            iter->last_visited = iter->last_visited->right;

        return iter->last_visited;
    }

    for (;;)
    {
        RBTNode    *came_from = iter->last_visited;

        iter->last_visited = iter->last_visited->parent;
        if (iter->last_visited == NULL)
        {
            iter->is_over = true;
            break;
        }

        if (iter->last_visited->right == came_from)
            break;              /* came from right sub-tree, return current
                                 * node */

        /* else - came from left sub-tree, continue to move up */
    }

    return iter->last_visited;
}

rbt_rotate_left()

static void rbt_rotate_left ( RBTree *  rbt, RBTNode *  x  )

static

Definition at line 201 of file rbtree.c.

References RBTNode::left, RBTNode::parent, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by rbt_delete_fixup(), and rbt_insert_fixup().

{
    RBTNode    *y = x->right;

    /* establish x->right link */
    x->right = y->left;
    if (y->left != RBTNIL)
        y->left->parent = x;

    /* establish y->parent link */
    if (y != RBTNIL)
        y->parent = x->parent;
    if (x->parent)
    {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    }
    else
    {
        rbt->root = y;
    }

    /* link x and y */
    y->left = x;
    if (x != RBTNIL)
        x->parent = y;
}

rbt_rotate_right()

static void rbt_rotate_right ( RBTree *  rbt, RBTNode *  x  )

static

Definition at line 238 of file rbtree.c.

References RBTNode::left, RBTNode::parent, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by rbt_delete_fixup(), and rbt_insert_fixup().

{
    RBTNode    *y = x->left;

    /* establish x->left link */
    x->left = y->right;
    if (y->right != RBTNIL)
        y->right->parent = x;

    /* establish y->parent link */
    if (y != RBTNIL)
        y->parent = x->parent;
    if (x->parent)
    {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    }
    else
    {
        rbt->root = y;
    }

    /* link x and y */
    y->right = x;
    if (x != RBTNIL)
        x->parent = y;
}

Variable Documentation

sentinel

RBTNode sentinel

static

Initial value:

=
{
    RBTBLACK, RBTNIL, RBTNIL, NULL
}

Definition at line 63 of file rbtree.c.