rbtree.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	RBTNode
struct	RBTreeIterator

Typedefs
typedef struct RBTNode	RBTNode
typedef struct RBTree	RBTree
typedef enum RBTOrderControl	RBTOrderControl
typedef struct RBTreeIterator	RBTreeIterator
typedef int(*	rbt_comparator) (const RBTNode *a, const RBTNode *b, void *arg)
typedef void(*	rbt_combiner) (RBTNode *existing, const RBTNode *newdata, void *arg)
typedef RBTNode *(*	rbt_allocfunc) (void *arg)
typedef void(*	rbt_freefunc) (RBTNode *x, void *arg)

Enumerations
enum	RBTOrderControl { LeftRightWalk , RightLeftWalk }

Functions
RBTree *	rbt_create (Size node_size, rbt_comparator comparator, rbt_combiner combiner, rbt_allocfunc allocfunc, rbt_freefunc freefunc, void *arg)
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)
RBTNode *	rbt_insert (RBTree *rbt, const RBTNode *data, bool *isNew)
void	rbt_delete (RBTree *rbt, RBTNode *node)
void	rbt_begin_iterate (RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
RBTNode *	rbt_iterate (RBTreeIterator *iter)

Typedef Documentation

rbt_allocfunc

typedef RBTNode *(* rbt_allocfunc) (void *arg)

Definition at line 59 of file rbtree.h.

rbt_combiner

typedef void(* rbt_combiner) (RBTNode *existing, const RBTNode *newdata, void *arg)

Definition at line 58 of file rbtree.h.

rbt_comparator

typedef int(* rbt_comparator) (const RBTNode *a, const RBTNode *b, void *arg)

Definition at line 57 of file rbtree.h.

rbt_freefunc

typedef void(* rbt_freefunc) (RBTNode *x, void *arg)

Definition at line 60 of file rbtree.h.

RBTNode

typedef struct RBTNode RBTNode

RBTOrderControl

typedef enum RBTOrderControl RBTOrderControl

RBTree

typedef struct RBTree RBTree

Definition at line 32 of file rbtree.h.

RBTreeIterator

typedef struct RBTreeIterator RBTreeIterator

Definition at line 46 of file rbtree.h.

Enumeration Type Documentation

RBTOrderControl

enum RBTOrderControl

Enumerator
LeftRightWalk
RightLeftWalk

Definition at line 35 of file rbtree.h.

{
    LeftRightWalk,              /* inorder: left child, node, right child */
    RightLeftWalk               /* reverse inorder: right, node, left */
} RBTOrderControl;

Function Documentation

rbt_begin_iterate()

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

extern

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, fb(), 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_create()

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

extern

Definition at line 102 of file rbtree.c.

{
    RBTree     *tree = palloc_object(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_object, RBTNIL, and tree.

Referenced by create_int_rbtree(), and ginInitBA().

rbt_delete()

void rbt_delete ( RBTree *  rbt, RBTNode *  node  )

extern

Definition at line 695 of file rbtree.c.

{
    rbt_delete_node(rbt, node);
}

References rbt_delete_node().

Referenced by testdelete(), and testfindltgt().

rbt_find()

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

extern

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, fb(), 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  )

extern

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, fb(), 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  )

extern

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, fb(), RBTNode::left, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by testfindltgt().

rbt_insert()

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

extern

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, fb(), RBTNode::left, rbt_copy_data(), rbt_insert_fixup(), RBTNIL, RBTRED, RBTNode::right, RBTree::root, and x.

Referenced by ginInsertBAEntry(), and rbt_populate().

rbt_iterate()

RBTNode * rbt_iterate ( RBTreeIterator *  iter )

extern

Definition at line 826 of file rbtree.c.

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

References fb(), RBTreeIterator::is_over, and RBTreeIterator::iterate.

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

rbt_leftmost()

RBTNode * rbt_leftmost ( RBTree *  rbt )

extern

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 fb(), RBTNode::left, RBTNIL, and RBTree::root.

Referenced by testdelete(), and testleftmost().