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_find_great (RBTree *rbt, const RBTNode *data, bool equal_match)
RBTNode *	rbt_find_less (RBTree *rbt, const RBTNode *data, bool equal_match)
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.

RBTNIL

#define RBTNIL   (&sentinel)

Definition at line 61 of file rbtree.c.

RBTRED

#define RBTRED   (1)

Definition at line 36 of file rbtree.c.

Function Documentation

rbt_begin_iterate()

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

Definition at line 802 of file rbtree.c.

{
    /* 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);
    }
}

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().

rbt_copy_data()

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

inlinestatic

Definition at line 127 of file rbtree.c.

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

References generate_unaccent_rules::dest, and RBTree::node_size.

Referenced by rbt_delete_node(), and rbt_insert().

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.

{
    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;
}

References arg, Assert(), palloc(), RBTNIL, and tree.

Referenced by create_int_rbtree(), and ginInitBA().

rbt_delete()

void rbt_delete	(	RBTree *	rbt,
		RBTNode *	node
	)

Definition at line 695 of file rbtree.c.

{
    rbt_delete_node(rbt, node);
}

References rbt_delete_node().

Referenced by testdelete(), and testfindltgt().

rbt_delete_fixup()

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

static

Definition at line 521 of file rbtree.c.

{
    /*
     * 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;
}

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

Referenced by rbt_delete_node().

rbt_delete_node()

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

static

Definition at line 619 of file rbtree.c.

{
    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);
}

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

Referenced by rbt_delete().

rbt_find()

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

Definition at line 145 of file rbtree.c.

{
    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;
}

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

Referenced by testdelete(), and testfind().

rbt_find_great()

RBTNode * rbt_find_great	(	RBTree *	rbt,
		const RBTNode *	data,
		bool	equal_match
	)

Definition at line 172 of file rbtree.c.

{
    RBTNode    *node = rbt->root;
    RBTNode    *greater = NULL;
 
    while (node != RBTNIL)
    {
        int         cmp = rbt->comparator(data, node, rbt->arg);
 
        if (equal_match && cmp == 0)
            return node;
        else if (cmp < 0)
        {
            greater = node;
            node = node->left;
        }
        else
            node = node->right;
    }
 
    return greater;
}

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

Referenced by testfindltgt().

rbt_find_less()

RBTNode * rbt_find_less	(	RBTree *	rbt,
		const RBTNode *	data,
		bool	equal_match
	)

Definition at line 203 of file rbtree.c.

{
    RBTNode    *node = rbt->root;
    RBTNode    *lesser = NULL;
 
    while (node != RBTNIL)
    {
        int         cmp = rbt->comparator(data, node, rbt->arg);
 
        if (equal_match && cmp == 0)
            return node;
        else if (cmp > 0)
        {
            lesser = node;
            node = node->right;
        }
        else
            node = node->left;
    }
 
    return lesser;
}

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

Referenced by testfindltgt().

rbt_insert()

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

Definition at line 453 of file rbtree.c.

{
    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;
}

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

Referenced by ginInsertBAEntry(), and rbt_populate().

rbt_insert_fixup()

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

static

Definition at line 344 of file rbtree.c.

{
    /*
     * 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;
}

References RBTNode::color, rbt_rotate_left(), rbt_rotate_right(), RBTBLACK, RBTRED, RBTree::root, x, and y.

Referenced by rbt_insert().

rbt_iterate()

RBTNode * rbt_iterate

(

RBTreeIterator *

iter

)

Definition at line 826 of file rbtree.c.

{
    if (iter->is_over)
        return NULL;
 
    return iter->iterate(iter);
}

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

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

rbt_left_right_iterator()

static RBTNode * rbt_left_right_iterator ( RBTreeIterator *  iter )

static

Definition at line 705 of file rbtree.c.

{
    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;
}

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

Referenced by rbt_begin_iterate().

rbt_leftmost()

RBTNode * rbt_leftmost

(

RBTree *

rbt

)

Definition at line 235 of file rbtree.c.

{
    RBTNode    *node = rbt->root;
    RBTNode    *leftmost = rbt->root;
 
    while (node != RBTNIL)
    {
        leftmost = node;
        node = node->left;
    }
 
    if (leftmost != RBTNIL)
        return leftmost;
 
    return NULL;
}

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

Referenced by testdelete(), and testleftmost().

rbt_right_left_iterator()

static RBTNode * rbt_right_left_iterator ( RBTreeIterator *  iter )

static

Definition at line 747 of file rbtree.c.

{
    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;
}

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

Referenced by rbt_begin_iterate().

rbt_rotate_left()

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

static

Definition at line 263 of file rbtree.c.

{
    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;
}

References RBTNIL, RBTree::root, x, and y.

Referenced by rbt_delete_fixup(), and rbt_insert_fixup().

rbt_rotate_right()

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

static

Definition at line 300 of file rbtree.c.

{
    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;
}

References RBTNIL, RBTree::root, x, and y.

Referenced by rbt_delete_fixup(), and rbt_insert_fixup().

Variable Documentation

sentinel

RBTNode sentinel

static

Initial value:

=
{
    .color = RBTBLACK,.left = RBTNIL,.right = RBTNIL,.parent = NULL
}

Definition at line 63 of file rbtree.c.