Scippy

SCIP

Solving Constraint Integer Programs

rbtree.c File Reference

Detailed Description

intrusive red black tree datastructure

Author
Robert Lion 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 25 of file rbtree.c.

Referenced by rbDeleteFixup().

◆ BLACK

#define BLACK   ((uintptr_t)0x0u)

Definition at line 26 of file rbtree.c.

Referenced by SCIPrbtreeDelete_call().

◆ COLOR

#define COLOR (   node)    ((node)->parent & RED)

Definition at line 27 of file rbtree.c.

Referenced by rbDeleteFixup(), and SCIPrbtreeDelete_call().

◆ IS_RED

#define IS_RED (   node)    ( (node) != NULL && COLOR(node) )

Definition at line 28 of file rbtree.c.

Referenced by rbInsertFixup().

◆ IS_BLACK

#define IS_BLACK (   node)    ( (node) == NULL || !COLOR(node) )

Definition at line 29 of file rbtree.c.

Referenced by rbDeleteFixup().

◆ MAKE_RED

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

Definition at line 30 of file rbtree.c.

Referenced by rbDeleteFixup(), rbInsertFixup(), and SCIPrbtreeInsert_call().

◆ MAKE_BLACK

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

Definition at line 31 of file rbtree.c.

Referenced by rbDeleteFixup(), and rbInsertFixup().

◆ LEFT

◆ RIGHT

◆ OPPOSITE

#define OPPOSITE (   dir)    ( 1 - (dir) )

Definition at line 34 of file rbtree.c.

Referenced by rbDeleteFixup(), rbInsertFixup(), and rbRotate().

◆ PARENT

#define PARENT (   node)    ( (SCIP_RBTREENODE*)((node)->parent & ~RED) )

◆ SET_PARENT

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

Definition at line 36 of file rbtree.c.

Referenced by rbRotate(), rbTransplant(), SCIPrbtreeDelete_call(), and SCIPrbtreeInsert_call().

◆ SET_COLOR

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

Definition at line 37 of file rbtree.c.

Referenced by rbDeleteFixup(), and SCIPrbtreeDelete_call().

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 43 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 73 of file rbtree.c.

References SCIP_RBTreeNode::child, IS_RED, LEFT, MAKE_BLACK, MAKE_RED, 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 121 of file rbtree.c.

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

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 180 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 205 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 219 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 233 of file rbtree.c.

References SCIP_RBTreeNode::child, NULL, PARENT, RIGHT, SCIPrbtreeFirst_call(), 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 253 of file rbtree.c.

References SCIP_RBTreeNode::child, LEFT, NULL, PARENT, SCIPrbtreeLast_call(), 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 275 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 330 of file rbtree.c.

References SCIP_RBTreeNode::child, LEFT, MAKE_RED, NULL, rbInsertFixup(), RIGHT, and SET_PARENT.