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

Include dependency graph for rbtree.c:

Data Structures
struct	RBTree
Defines
#define	InitialState (0)
#define	FirstStepDone (1)
#define	SecondStepDone (2)
#define	ThirdStepDone (3)
#define	RBBLACK (0)
#define	RBRED (1)
#define	RBNIL (&sentinel)
#define	descend(next_node)
#define	ascend(next_node)
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 (RBTree *rb)
static RBNode *	rb_right_left_iterator (RBTree *rb)
static RBNode *	rb_direct_iterator (RBTree *rb)
static RBNode *	rb_inverted_iterator (RBTree *rb)
void	rb_begin_iterate (RBTree *rb, RBOrderControl ctrl)
RBNode *	rb_iterate (RBTree *rb)
Variables
static RBNode	sentinel = {InitialState, RBBLACK, RBNIL, RBNIL, NULL}

Define Documentation

#define ascend ( next_node )

Value:

do { \
        node = rb->cur = (next_node); \
        goto restart; \
    } while (0)

Definition at line 668 of file rbtree.c.

Referenced by rb_direct_iterator(), rb_inverted_iterator(), rb_left_right_iterator(), and rb_right_left_iterator().

#define descend ( next_node )

Value:

do { \
        (next_node)->iteratorState = InitialState; \
        node = rb->cur = (next_node); \
        goto restart; \
    } while (0)

Definition at line 661 of file rbtree.c.

Referenced by rb_direct_iterator(), rb_inverted_iterator(), rb_left_right_iterator(), and rb_right_left_iterator().

#define FirstStepDone (1)

Definition at line 39 of file rbtree.c.

Referenced by rb_direct_iterator(), rb_inverted_iterator(), rb_left_right_iterator(), and rb_right_left_iterator().

#define InitialState (0)

Definition at line 38 of file rbtree.c.

Referenced by rb_direct_iterator(), rb_inverted_iterator(), rb_left_right_iterator(), and rb_right_left_iterator().

#define RBBLACK (0)

Definition at line 46 of file rbtree.c.

Referenced by rb_delete_fixup(), and rb_delete_node().

#define RBNIL (&sentinel)

Definition at line 76 of file rbtree.c.

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

#define RBRED (1)

Definition at line 47 of file rbtree.c.

Referenced by rb_delete_fixup(), and rb_insert_fixup().

#define SecondStepDone (2)

Definition at line 40 of file rbtree.c.

Referenced by rb_direct_iterator(), rb_inverted_iterator(), rb_left_right_iterator(), and rb_right_left_iterator().

#define ThirdStepDone (3)

Definition at line 41 of file rbtree.c.

Referenced by rb_direct_iterator(), rb_inverted_iterator(), rb_left_right_iterator(), and rb_right_left_iterator().

Function Documentation

void rb_begin_iterate	(	RBTree *	rb,
		RBOrderControl	ctrl
	)

Definition at line 838 of file rbtree.c.

References RBTree::cur, DirectWalk, elog, ERROR, InvertedWalk, RBTree::iterate, RBNode::iteratorState, LeftRightWalk, RBNIL, RightLeftWalk, and RBTree::root.

Referenced by ginBeginBAScan().

{
    rb->cur = rb->root;
    if (rb->cur != RBNIL)
        rb->cur->iteratorState = InitialState;

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

static void rb_copy_data	(	RBTree *	rb,
		RBNode *	dest,
		const RBNode *	src
	)			`[inline, static]`

Definition at line 141 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 114 of file rbtree.c.

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

Referenced by ginInitBA(), and gistrescan().

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

    Assert(node_size > sizeof(RBNode));

    tree->root = RBNIL;
    tree->cur = RBNIL;
    tree->iterate = NULL;
    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 647 of file rbtree.c.

References rb_delete_node().

Referenced by getNextGISTSearchItem().

{
    rb_delete_node(rb, node);
}

static void rb_delete_fixup	(	RBTree *	rb,
		RBNode *	x
	)			`[static]`

Definition at line 474 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 572 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 ( RBTree * rb ) [static]

Definition at line 750 of file rbtree.c.

References ascend, RBTree::cur, descend, elog, ERROR, FirstStepDone, InitialState, RBNode::iteratorState, RBNode::left, RBNode::parent, RBNIL, RBNode::right, SecondStepDone, and ThirdStepDone.

{
    RBNode     *node = rb->cur;

restart:
    switch (node->iteratorState)
    {
        case InitialState:
            node->iteratorState = FirstStepDone;
            return node;
        case FirstStepDone:
            if (node->left != RBNIL)
            {
                node->iteratorState = SecondStepDone;
                descend(node->left);
            }
            /* FALL THROUGH */
        case SecondStepDone:
            if (node->right != RBNIL)
            {
                node->iteratorState = ThirdStepDone;
                descend(node->right);
            }
            /* FALL THROUGH */
        case ThirdStepDone:
            if (node->parent)
                ascend(node->parent);
            break;
        default:
            elog(ERROR, "unrecognized rbtree node state: %d",
                 node->iteratorState);
    }

    return NULL;
}

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

Definition at line 159 of file rbtree.c.

References RBTree::arg, cmp(), RBTree::comparator, RBNode::left, 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 405 of file rbtree.c.

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

Referenced by ginInsertBAEntry(), and gistScanPage().

{
    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->iteratorState = InitialState;
    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 296 of file rbtree.c.

References RBNode::color, RBNode::left, RBNode::parent, rb_rotate_left(), rb_rotate_right(), 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 ( RBTree * rb ) [static]

Definition at line 787 of file rbtree.c.

References ascend, RBTree::cur, descend, elog, ERROR, FirstStepDone, InitialState, RBNode::iteratorState, RBNode::left, RBNode::parent, RBNIL, RBNode::right, SecondStepDone, and ThirdStepDone.

{
    RBNode     *node = rb->cur;

restart:
    switch (node->iteratorState)
    {
        case InitialState:
            if (node->left != RBNIL)
            {
                node->iteratorState = FirstStepDone;
                descend(node->left);
            }
            /* FALL THROUGH */
        case FirstStepDone:
            if (node->right != RBNIL)
            {
                node->iteratorState = SecondStepDone;
                descend(node->right);
            }
            /* FALL THROUGH */
        case SecondStepDone:
            node->iteratorState = ThirdStepDone;
            return node;
        case ThirdStepDone:
            if (node->parent)
                ascend(node->parent);
            break;
        default:
            elog(ERROR, "unrecognized rbtree node state: %d",
                 node->iteratorState);
    }

    return NULL;
}

RBNode* rb_iterate ( RBTree * rb )

Definition at line 867 of file rbtree.c.

References RBTree::cur, RBTree::iterate, and RBNIL.

Referenced by ginGetBAEntry().

{
    if (rb->cur == RBNIL)
        return NULL;

    return rb->iterate(rb);
}

static RBNode* rb_left_right_iterator ( RBTree * rb ) [static]

Definition at line 676 of file rbtree.c.

References ascend, RBTree::cur, descend, elog, ERROR, FirstStepDone, InitialState, RBNode::iteratorState, RBNode::left, RBNode::parent, RBNIL, RBNode::right, SecondStepDone, and ThirdStepDone.

{
    RBNode     *node = rb->cur;

restart:
    switch (node->iteratorState)
    {
        case InitialState:
            if (node->left != RBNIL)
            {
                node->iteratorState = FirstStepDone;
                descend(node->left);
            }
            /* FALL THROUGH */
        case FirstStepDone:
            node->iteratorState = SecondStepDone;
            return node;
        case SecondStepDone:
            if (node->right != RBNIL)
            {
                node->iteratorState = ThirdStepDone;
                descend(node->right);
            }
            /* FALL THROUGH */
        case ThirdStepDone:
            if (node->parent)
                ascend(node->parent);
            break;
        default:
            elog(ERROR, "unrecognized rbtree node state: %d",
                 node->iteratorState);
    }

    return NULL;
}

RBNode* rb_leftmost ( RBTree * rb )

Definition at line 187 of file rbtree.c.

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

Referenced by getNextGISTSearchItem().

{
    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 ( RBTree * rb ) [static]

Definition at line 713 of file rbtree.c.

References ascend, RBTree::cur, descend, elog, ERROR, FirstStepDone, InitialState, RBNode::iteratorState, RBNode::left, RBNode::parent, RBNIL, RBNode::right, SecondStepDone, and ThirdStepDone.

{
    RBNode     *node = rb->cur;

restart:
    switch (node->iteratorState)
    {
        case InitialState:
            if (node->right != RBNIL)
            {
                node->iteratorState = FirstStepDone;
                descend(node->right);
            }
            /* FALL THROUGH */
        case FirstStepDone:
            node->iteratorState = SecondStepDone;
            return node;
        case SecondStepDone:
            if (node->left != RBNIL)
            {
                node->iteratorState = ThirdStepDone;
                descend(node->left);
            }
            /* FALL THROUGH */
        case ThirdStepDone:
            if (node->parent)
                ascend(node->parent);
            break;
        default:
            elog(ERROR, "unrecognized rbtree node state: %d",
                 node->iteratorState);
    }

    return NULL;
}

static void rb_rotate_left	(	RBTree *	rb,
		RBNode *	x
	)			`[static]`

Definition at line 215 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 252 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 = {InitialState, RBBLACK, RBNIL, RBNIL, NULL} [static]

Definition at line 78 of file rbtree.c.

Header And Logo

rbtree.c File Reference

Data Structures

Defines

Functions

Variables

Define Documentation

Function Documentation

Variable Documentation