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	RBBLACK   (0)
#define	RBRED   (1)
#define	RBNIL   (&sentinel)

Typedefs
typedef enum InvertedWalkNextStep	InvertedWalkNextStep

Enumerations
enum	InvertedWalkNextStep { NextStepBegin, NextStepUp, NextStepLeft, NextStepRight }

Functions
RBTree *	rb_create (Size node_size, rb_comparator comparator, rb_combiner combiner, rb_allocfunc allocfunc, rb_freefunc freefunc, void *arg)
static void	rb_copy_data (RBTree *rb, RBNode *dest, const RBNode *src)
RBNode *	rb_find (RBTree *rb, const RBNode *data)
RBNode *	rb_leftmost (RBTree *rb)
static void	rb_rotate_left (RBTree *rb, RBNode *x)
static void	rb_rotate_right (RBTree *rb, RBNode *x)
static void	rb_insert_fixup (RBTree *rb, RBNode *x)
RBNode *	rb_insert (RBTree *rb, const RBNode *data, bool *isNew)
static void	rb_delete_fixup (RBTree *rb, RBNode *x)
static void	rb_delete_node (RBTree *rb, RBNode *z)
void	rb_delete (RBTree *rb, RBNode *node)
static RBNode *	rb_left_right_iterator (RBTreeIterator *iter)
static RBNode *	rb_right_left_iterator (RBTreeIterator *iter)
static RBNode *	rb_direct_iterator (RBTreeIterator *iter)
static RBNode *	rb_inverted_iterator (RBTreeIterator *iter)
void	rb_begin_iterate (RBTree *rb, RBOrderControl ctrl, RBTreeIterator *iter)
RBNode *	rb_iterate (RBTreeIterator *iter)

Variables
static RBNode	sentinel = {RBBLACK, RBNIL, RBNIL, NULL}

Macro Definition Documentation

#define RBBLACK   (0)

Definition at line 35 of file rbtree.c.

Referenced by rb_delete_fixup(), rb_delete_node(), and rb_insert_fixup().

#define RBNIL   (&sentinel)

Definition at line 61 of file rbtree.c.

Referenced by rb_begin_iterate(), rb_create(), rb_delete_node(), rb_direct_iterator(), rb_find(), rb_insert(), rb_inverted_iterator(), rb_left_right_iterator(), rb_leftmost(), rb_right_left_iterator(), rb_rotate_left(), and rb_rotate_right().

#define RBRED   (1)

Definition at line 36 of file rbtree.c.

Referenced by rb_delete_fixup(), rb_insert(), and rb_insert_fixup().

Typedef Documentation

typedef enum InvertedWalkNextStep InvertedWalkNextStep

Enumeration Type Documentation

enum InvertedWalkNextStep

Enumerator
NextStepBegin
NextStepUp
NextStepLeft
NextStepRight

Definition at line 69 of file rbtree.c.

{
    NextStepBegin,
    NextStepUp,
    NextStepLeft,
    NextStepRight
} InvertedWalkNextStep;

Function Documentation

void rb_begin_iterate	(	RBTree *	rb,
		RBOrderControl	ctrl,
		RBTreeIterator *	iter
	)

Definition at line 855 of file rbtree.c.

References DirectWalk, elog, ERROR, InvertedWalk, RBTreeIterator::is_over, RBTreeIterator::iterate, RBTreeIterator::last_visited, LeftRightWalk, RBTreeIterator::next_step, NextStepBegin, NULL, RBTreeIterator::rb, rb_direct_iterator(), rb_inverted_iterator(), rb_left_right_iterator(), rb_right_left_iterator(), RBNIL, RightLeftWalk, and RBTree::root.

Referenced by ginBeginBAScan().

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

    switch (ctrl)
    {
        case LeftRightWalk:     /* visit left, then self, then right */
            iter->iterate = rb_left_right_iterator;
            break;
        case RightLeftWalk:     /* visit right, then self, then left */
            iter->iterate = rb_right_left_iterator;
            break;
        case DirectWalk:        /* visit self, then left, then right */
            iter->iterate = rb_direct_iterator;
            break;
        case InvertedWalk:      /* visit left, then right, then self */
            iter->iterate = rb_inverted_iterator;
            iter->next_step = NextStepBegin;
            break;
        default:
            elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
    }
}

static void rb_copy_data ( RBTree *  rb, RBNode *  dest, const RBNode *  src  )

inlinestatic

Definition at line 135 of file rbtree.c.

References RBTree::node_size.

Referenced by rb_delete_node(), and rb_insert().

{
    memcpy(dest + 1, src + 1, rb->node_size - sizeof(RBNode));
}

RBTree* rb_create	(	Size	node_size,
		rb_comparator	comparator,
		rb_combiner	combiner,
		rb_allocfunc	allocfunc,
		rb_freefunc	freefunc,
		void *	arg
	)

Definition at line 110 of file rbtree.c.

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

Referenced by ginInitBA().

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

    Assert(node_size > sizeof(RBNode));

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

    tree->arg = arg;

    return tree;
}

void rb_delete	(	RBTree *	rb,
		RBNode *	node
	)

Definition at line 640 of file rbtree.c.

References rb_delete_node().

{
    rb_delete_node(rb, node);
}

static void rb_delete_fixup ( RBTree *  rb, RBNode *  x  )

static

Definition at line 467 of file rbtree.c.

References RBNode::color, RBNode::left, RBNode::parent, rb_rotate_left(), rb_rotate_right(), RBBLACK, RBRED, RBNode::right, and RBTree::root.

Referenced by rb_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 != rb->root && x->color == RBBLACK)
    {
        /*
         * 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)
        {
            RBNode     *w = x->parent->right;

            if (w->color == RBRED)
            {
                w->color = RBBLACK;
                x->parent->color = RBRED;

                rb_rotate_left(rb, x->parent);
                w = x->parent->right;
            }

            if (w->left->color == RBBLACK && w->right->color == RBBLACK)
            {
                w->color = RBRED;

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

                    rb_rotate_right(rb, w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = RBBLACK;
                w->right->color = RBBLACK;

                rb_rotate_left(rb, x->parent);
                x = rb->root;   /* Arrange for loop to terminate. */
            }
        }
        else
        {
            RBNode     *w = x->parent->left;

            if (w->color == RBRED)
            {
                w->color = RBBLACK;
                x->parent->color = RBRED;

                rb_rotate_right(rb, x->parent);
                w = x->parent->left;
            }

            if (w->right->color == RBBLACK && w->left->color == RBBLACK)
            {
                w->color = RBRED;

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

                    rb_rotate_left(rb, w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = RBBLACK;
                w->left->color = RBBLACK;

                rb_rotate_right(rb, x->parent);
                x = rb->root;   /* Arrange for loop to terminate. */
            }
        }
    }
    x->color = RBBLACK;
}

static void rb_delete_node ( RBTree *  rb, RBNode *  z  )

static

Definition at line 565 of file rbtree.c.

References RBTree::arg, RBNode::color, RBTree::freefunc, RBNode::left, RBNode::parent, rb_copy_data(), rb_delete_fixup(), RBBLACK, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_delete().

{
    RBNode     *x,
               *y;

    if (!z || z == RBNIL)
        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 == RBNIL || z->right == RBNIL)
    {
        /* y has a RBNIL node as a child */
        y = z;
    }
    else
    {
        /* find tree successor */
        y = z->right;
        while (y->left != RBNIL)
            y = y->left;
    }

    /* x is y's only child */
    if (y->left != RBNIL)
        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
    {
        rb->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)
        rb_copy_data(rb, 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 == RBBLACK)
        rb_delete_fixup(rb, x);

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

static RBNode* rb_direct_iterator ( RBTreeIterator *  iter )

static

Definition at line 734 of file rbtree.c.

References RBTreeIterator::is_over, RBTreeIterator::last_visited, RBNode::left, NULL, RBNode::parent, RBTreeIterator::rb, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_begin_iterate().

{
    if (iter->last_visited == NULL)
    {
        iter->last_visited = iter->rb->root;
        return iter->last_visited;
    }

    if (iter->last_visited->left != RBNIL)
    {
        iter->last_visited = iter->last_visited->left;
        return iter->last_visited;
    }

    do
    {
        if (iter->last_visited->right != RBNIL)
        {
            iter->last_visited = iter->last_visited->right;
            break;
        }

        /* go up and one step right */
        for (;;)
        {
            RBNode     *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) && (iter->last_visited->right != RBNIL))
            {
                iter->last_visited = iter->last_visited->right;
                return iter->last_visited;
            }
        }
    }
    while (iter->last_visited != NULL);

    return iter->last_visited;
}

RBNode* rb_find	(	RBTree *	rb,
		const RBNode *	data
	)

Definition at line 153 of file rbtree.c.

References RBTree::arg, cmp(), RBTree::comparator, RBNode::left, NULL, RBNIL, RBNode::right, and RBTree::root.

{
    RBNode     *node = rb->root;

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

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

    return NULL;
}

RBNode* rb_insert	(	RBTree *	rb,
		const RBNode *	data,
		bool *	isNew
	)

Definition at line 399 of file rbtree.c.

References RBTree::allocfunc, RBTree::arg, cmp(), RBNode::color, RBTree::combiner, RBTree::comparator, RBNode::left, NULL, RBNode::parent, rb_copy_data(), rb_insert_fixup(), RBNIL, RBRED, RBNode::right, and RBTree::root.

Referenced by ginInsertBAEntry().

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

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

    while (current != RBNIL)
    {
        cmp = rb->comparator(data, current, rb->arg);
        if (cmp == 0)
        {
            /*
             * Found node with given key.  Apply combiner.
             */
            rb->combiner(current, data, rb->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 = rb->allocfunc(rb->arg);

    x->color = RBRED;

    x->left = RBNIL;
    x->right = RBNIL;
    x->parent = parent;
    rb_copy_data(rb, x, data);

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

    rb_insert_fixup(rb, x);

    return x;
}

static void rb_insert_fixup ( RBTree *  rb, RBNode *  x  )

static

Definition at line 290 of file rbtree.c.

References RBNode::color, RBNode::left, RBNode::parent, rb_rotate_left(), rb_rotate_right(), RBBLACK, RBRED, RBNode::right, and RBTree::root.

Referenced by rb_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 != rb->root && x->parent->color == RBRED)
    {
        /*
         * 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)
        {
            RBNode     *y = x->parent->parent->right;

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

                x = x->parent->parent;
            }
            else
            {
                /* uncle is RBBLACK */
                if (x == x->parent->right)
                {
                    /* make x a left child */
                    x = x->parent;
                    rb_rotate_left(rb, x);
                }

                /* recolor and rotate */
                x->parent->color = RBBLACK;
                x->parent->parent->color = RBRED;

                rb_rotate_right(rb, x->parent->parent);
            }
        }
        else
        {
            /* mirror image of above code */
            RBNode     *y = x->parent->parent->left;

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

                x = x->parent->parent;
            }
            else
            {
                /* uncle is RBBLACK */
                if (x == x->parent->left)
                {
                    x = x->parent;
                    rb_rotate_right(rb, x);
                }
                x->parent->color = RBBLACK;
                x->parent->parent->color = RBRED;

                rb_rotate_left(rb, x->parent->parent);
            }
        }
    }

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

static RBNode* rb_inverted_iterator ( RBTreeIterator *  iter )

static

Definition at line 781 of file rbtree.c.

References Assert, RBTreeIterator::is_over, RBTreeIterator::last_visited, RBNode::left, RBTreeIterator::next_step, NextStepBegin, NextStepLeft, NextStepRight, NextStepUp, NULL, RBNode::parent, RBTreeIterator::rb, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_begin_iterate().

{
    RBNode     *came_from;
    RBNode     *current;

    current = iter->last_visited;

loop:
    switch ((InvertedWalkNextStep) iter->next_step)
    {
            /* First call, begin from root */
        case NextStepBegin:
            current = iter->rb->root;
            iter->next_step = NextStepLeft;
            goto loop;

        case NextStepLeft:
            while (current->left != RBNIL)
                current = current->left;

            iter->next_step = NextStepRight;
            goto loop;

        case NextStepRight:
            if (current->right != RBNIL)
            {
                current = current->right;
                iter->next_step = NextStepLeft;
                goto loop;
            }
            else                /* not moved - return current, then go up */
                iter->next_step = NextStepUp;
            break;

        case NextStepUp:
            came_from = current;
            current = current->parent;
            if (current == NULL)
            {
                iter->is_over = true;
                break;          /* end of iteration */
            }
            else if (came_from == current->right)
            {
                /* return current, then continue to go up */
                break;
            }
            else
            {
                /* otherwise we came from the left */
                Assert(came_from == current->left);
                iter->next_step = NextStepRight;
                goto loop;
            }
    }

    iter->last_visited = current;
    return current;
}

RBNode* rb_iterate

(

RBTreeIterator *

iter

)

Definition at line 886 of file rbtree.c.

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

Referenced by ginGetBAEntry().

{
    if (iter->is_over)
        return NULL;

    return iter->iterate(iter);
}

static RBNode* rb_left_right_iterator ( RBTreeIterator *  iter )

static

Definition at line 650 of file rbtree.c.

References RBTreeIterator::is_over, RBTreeIterator::last_visited, RBNode::left, NULL, RBNode::parent, RBTreeIterator::rb, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_begin_iterate().

{
    if (iter->last_visited == NULL)
    {
        iter->last_visited = iter->rb->root;
        while (iter->last_visited->left != RBNIL)
            iter->last_visited = iter->last_visited->left;

        return iter->last_visited;
    }

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

        return iter->last_visited;
    }

    for (;;)
    {
        RBNode     *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;
}

RBNode* rb_leftmost

(

RBTree *

rb

)

Definition at line 181 of file rbtree.c.

References RBNode::left, NULL, RBNIL, and RBTree::root.

{
    RBNode     *node = rb->root;
    RBNode     *leftmost = rb->root;

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

    if (leftmost != RBNIL)
        return leftmost;

    return NULL;
}

static RBNode* rb_right_left_iterator ( RBTreeIterator *  iter )

static

Definition at line 692 of file rbtree.c.

References RBTreeIterator::is_over, RBTreeIterator::last_visited, RBNode::left, NULL, RBNode::parent, RBTreeIterator::rb, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_begin_iterate().

{
    if (iter->last_visited == NULL)
    {
        iter->last_visited = iter->rb->root;
        while (iter->last_visited->right != RBNIL)
            iter->last_visited = iter->last_visited->right;

        return iter->last_visited;
    }

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

        return iter->last_visited;
    }

    for (;;)
    {
        RBNode     *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;
}

static void rb_rotate_left ( RBTree *  rb, RBNode *  x  )

static

Definition at line 209 of file rbtree.c.

References RBNode::left, RBNode::parent, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_delete_fixup(), and rb_insert_fixup().

{
    RBNode     *y = x->right;

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

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

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

static void rb_rotate_right ( RBTree *  rb, RBNode *  x  )

static

Definition at line 246 of file rbtree.c.

References RBNode::left, RBNode::parent, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_delete_fixup(), and rb_insert_fixup().

{
    RBNode     *y = x->left;

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

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

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

Variable Documentation

RBNode sentinel = {RBBLACK, RBNIL, RBNIL, NULL}

static

Definition at line 63 of file rbtree.c.