Scippy

SCIP

Solving Constraint Integer Programs

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_RBTREENODESCIPrbtreeFirst_call (SCIP_RBTREENODE *root)
 
SCIP_RBTREENODESCIPrbtreeLast_call (SCIP_RBTREENODE *root)
 
SCIP_RBTREENODESCIPrbtreeSuccessor_call (SCIP_RBTREENODE *x)
 
SCIP_RBTREENODESCIPrbtreePredecessor_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,
 
)    do { (n)->parent = (uintptr_t)(p) | COLOR(n); } while(0)

Definition at line 46 of file rbtree.c.

◆ SET_COLOR

#define SET_COLOR (   n,
 
)    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
rootpointer to store new root of the tree
xnode to perform rotation for
dirdirection 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
rootpointer to store new root of the tree
zinserted 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
rootpointer to store new root of the tree
xstart node for fixup
nilfake 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
rootpointer to store the new root
unode u
vnode v
nilfake 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
rootroot 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
rootroot 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
xelement 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
xelement 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
rootroot of the tree
nodenode 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
rootroot of the tree
parentfuture parent of node to be inserted
posposition 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
nodenode 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.