rbtree.c File Reference

Detailed Description

intrusive red black tree datastructure

Author

Leona Gottwald

Definition in file rbtree.c.

#include "scip/rbtree.h"

Go to the source code of this file.

Macros
#define	RED   ((uintptr_t)0x1u)
#define	BLACK   ((uintptr_t)0x0u)
#define	COLOR(node)   ((node)->parent & RED)
#define	IS_RED(node)   ( (node) != NULL && COLOR(node) )
#define	IS_BLACK(node)   ( (node) == NULL || !COLOR(node) )
#define	MAKE_RED(node)   do { (node)->parent |= RED; } while(0)
#define	MAKE_BLACK(node)   do { (node)->parent &= ~RED; } while(0)
#define	LEFT   0
#define	RIGHT   1
#define	OPPOSITE(dir)   ( 1 - (dir) )
#define	PARENT(node)   ( (SCIP_RBTREENODE*)((node)->parent & ~RED) )
#define	SET_PARENT(n, p)   do { (n)->parent = (uintptr_t)(p) | COLOR(n); } while(0)
#define	SET_COLOR(n, c)   do { if( c == RED ) { MAKE_RED(n); } else { MAKE_BLACK(n); } } while(0)

Functions
static void	rbRotate (SCIP_RBTREENODE **root, SCIP_RBTREENODE *x, int dir)
static void	rbInsertFixup (SCIP_RBTREENODE **root, SCIP_RBTREENODE *z)
static void	rbDeleteFixup (SCIP_RBTREENODE **root, SCIP_RBTREENODE *x, SCIP_RBTREENODE *nil)
static void	rbTransplant (SCIP_RBTREENODE **root, SCIP_RBTREENODE *u, SCIP_RBTREENODE *v, SCIP_RBTREENODE *nil)
SCIP_RBTREENODE *	SCIPrbtreeFirst_call (SCIP_RBTREENODE *root)
SCIP_RBTREENODE *	SCIPrbtreeLast_call (SCIP_RBTREENODE *root)
SCIP_RBTREENODE *	SCIPrbtreeSuccessor_call (SCIP_RBTREENODE *x)
SCIP_RBTREENODE *	SCIPrbtreePredecessor_call (SCIP_RBTREENODE *x)
void	SCIPrbtreeDelete_call (SCIP_RBTREENODE **root, SCIP_RBTREENODE *node)
void	SCIPrbtreeInsert_call (SCIP_RBTREENODE **root, SCIP_RBTREENODE *parent, int pos, SCIP_RBTREENODE *node)

Macro Definition Documentation

RED

#define RED   ((uintptr_t)0x1u)

Definition at line 35 of file rbtree.c.

BLACK

#define BLACK   ((uintptr_t)0x0u)

Definition at line 36 of file rbtree.c.

COLOR

#define COLOR

(

node

)

((node)->parent & RED)

Definition at line 37 of file rbtree.c.

IS_RED

#define IS_RED

(

node

)

( (node) != NULL && COLOR(node) )

Definition at line 38 of file rbtree.c.

IS_BLACK

#define IS_BLACK

(

node

)

( (node) == NULL || !COLOR(node) )

Definition at line 39 of file rbtree.c.

MAKE_RED

#define MAKE_RED

(

node

)

do { (node)->parent |= RED; } while(0)

Definition at line 40 of file rbtree.c.

MAKE_BLACK

#define MAKE_BLACK

(

node

)

do { (node)->parent &= ~RED; } while(0)

Definition at line 41 of file rbtree.c.

LEFT

#define LEFT   0

Definition at line 42 of file rbtree.c.

RIGHT

#define RIGHT   1

Definition at line 43 of file rbtree.c.

OPPOSITE

#define OPPOSITE

(

dir

)

( 1 - (dir) )

Definition at line 44 of file rbtree.c.

PARENT

#define PARENT

(

node

)

( (SCIP_RBTREENODE*)((node)->parent & ~RED) )

Definition at line 45 of file rbtree.c.

SET_PARENT

#define SET_PARENT	(		n,
			p
	)		do { (n)->parent = (uintptr_t)(p) | COLOR(n); } while(0)

Definition at line 46 of file rbtree.c.

SET_COLOR

#define SET_COLOR	(		n,
			c
	)		do { if( c == RED ) { MAKE_RED(n); } else { MAKE_BLACK(n); } } while(0)

Definition at line 47 of file rbtree.c.

Function Documentation

rbRotate()

static void rbRotate ( SCIP_RBTREENODE **  root, SCIP_RBTREENODE *  x, int  dir  )

static

rotate the tree in the given direction

Parameters

root	pointer to store new root of the tree
x	node to perform rotation for
dir	direction of rotation

Definition at line 53 of file rbtree.c.

References SCIP_RBTreeNode::child, NULL, OPPOSITE, PARENT, SET_PARENT, x, and y.

Referenced by rbDeleteFixup(), and rbInsertFixup().

rbInsertFixup()

static void rbInsertFixup ( SCIP_RBTREENODE **  root, SCIP_RBTREENODE *  z  )

static

restores the red-black tree property after an insert

Parameters

root	pointer to store new root of the tree
z	inserted node

Definition at line 86 of file rbtree.c.

References SCIP_RBTreeNode::child, IS_RED, LEFT, MAKE_BLACK, MAKE_RED, NULL, OPPOSITE, PARENT, rbRotate(), RIGHT, and y.

Referenced by SCIPrbtreeInsert_call().

rbDeleteFixup()

static void rbDeleteFixup ( SCIP_RBTREENODE **  root, SCIP_RBTREENODE *  x, SCIP_RBTREENODE *  nil  )

static

restores the red-black tree property after an insert

Parameters

root	pointer to store new root of the tree
x	start node for fixup
nil	fake node representing NULL to properly reassemble the tree

Definition at line 141 of file rbtree.c.

References SCIP_RBTreeNode::child, COLOR, IS_BLACK, LEFT, MAKE_BLACK, MAKE_RED, NULL, OPPOSITE, PARENT, rbRotate(), RED, RIGHT, SET_COLOR, w, and x.

Referenced by SCIPrbtreeDelete_call().

rbTransplant()

static void rbTransplant ( SCIP_RBTREENODE **  root, SCIP_RBTREENODE *  u, SCIP_RBTREENODE *  v, SCIP_RBTREENODE *  nil  )

static

replaces the subtree rooted at node u with the subtree rooted at node v

Parameters

root	pointer to store the new root
u	node u
v	node v
nil	fake node representing NULL to properly reassemble the tree

Definition at line 202 of file rbtree.c.

References SCIP_RBTreeNode::child, LEFT, NULL, PARENT, RIGHT, and SET_PARENT.

Referenced by SCIPrbtreeDelete_call().

SCIPrbtreeFirst_call()

SCIP_RBTREENODE * SCIPrbtreeFirst_call

(

SCIP_RBTREENODE *

root

)

get first element in tree with respect to sorting key

Parameters

root	root of the tree

Definition at line 227 of file rbtree.c.

References SCIP_RBTreeNode::child, LEFT, and NULL.

Referenced by SCIPrbtreeSuccessor_call().

SCIPrbtreeLast_call()

SCIP_RBTREENODE * SCIPrbtreeLast_call

(

SCIP_RBTREENODE *

root

)

get last element in tree with respect to sorting key

Parameters

root	root of the tree

Definition at line 241 of file rbtree.c.

References SCIP_RBTreeNode::child, NULL, and RIGHT.

Referenced by SCIPrbtreePredecessor_call().

SCIPrbtreeSuccessor_call()

SCIP_RBTREENODE * SCIPrbtreeSuccessor_call

(

SCIP_RBTREENODE *

x

)

get successor of given element in the tree

Parameters

x	element to get successor for

Definition at line 255 of file rbtree.c.

References NULL, PARENT, RIGHT, SCIPrbtreeFirst_call(), x, and y.

SCIPrbtreePredecessor_call()

SCIP_RBTREENODE * SCIPrbtreePredecessor_call

(

SCIP_RBTREENODE *

x

)

get predecessor of given element in the tree

Parameters

x	element to get predecessor for

Definition at line 275 of file rbtree.c.

References LEFT, NULL, PARENT, SCIPrbtreeLast_call(), x, and y.

SCIPrbtreeDelete_call()

void SCIPrbtreeDelete_call	(	SCIP_RBTREENODE **	root,
		SCIP_RBTREENODE *	node
	)

delete the given node from the tree given by it's root node. The node must be contained in the tree rooted at root.

Parameters

root	root of the tree
node	node to delete from tree

Definition at line 297 of file rbtree.c.

References BLACK, SCIP_RBTreeNode::child, COLOR, LEFT, NULL, PARENT, SCIP_RBTreeNode::parent, rbDeleteFixup(), rbTransplant(), RIGHT, SCIPrbtreeFirst, SET_COLOR, SET_PARENT, x, and y.

SCIPrbtreeInsert_call()

void SCIPrbtreeInsert_call	(	SCIP_RBTREENODE **	root,
		SCIP_RBTREENODE *	parent,
		int	pos,
		SCIP_RBTREENODE *	node
	)

insert node into the tree given by it's root. Requires the future parent and the position of the parent as returned by the tree's find function defined using the SCIP_DEF_RBTREE_FIND macro.

Parameters

root	root of the tree
parent	future parent of node to be inserted
pos	position of parent with respect to node, i.e. -1 if the parent's key comes before node and 1 if the parent's key comes after the node
node	node to insert into the tree

Definition at line 352 of file rbtree.c.

References SCIP_RBTreeNode::child, LEFT, NULL, SCIP_RBTreeNode::parent, rbInsertFixup(), RED, and RIGHT.