Scippy

SCIP

Solving Constraint Integer Programs

rbtree.h File Reference

Detailed Description

intrusive red black tree datastructure

Author
Leona Gottwald

Definition in file rbtree.h.

#include "scip/def.h"
#include "scip/type_misc.h"

Go to the source code of this file.

Data Structures

struct  SCIP_RBTreeNode
 

Macros

#define SCIP_RBTREE_HOOKS   SCIP_RBTREENODE _rbtreenode
 
#define SCIPrbtreeFirst(root)   SCIPrbtreeFirst_call((SCIP_RBTREENODE*)(root))
 
#define SCIPrbtreeLast(root)   SCIPrbtreeLast_call((SCIP_RBTREENODE*)(root))
 
#define SCIPrbtreeSuccessor(x)   SCIPrbtreeSuccessor_call((SCIP_RBTREENODE*)(x))
 
#define SCIPrbtreePredecessor(x)   SCIPrbtreePredecessor_call((SCIP_RBTREENODE*)(x))
 
#define SCIPrbtreeDelete(root, node)   SCIPrbtreeDelete_call((SCIP_RBTREENODE**)(root), (SCIP_RBTREENODE*)(node))
 
#define SCIPrbtreeInsert(r, p, c, n)   SCIPrbtreeInsert_call((SCIP_RBTREENODE**)(r), (SCIP_RBTREENODE*)(p), (c), (SCIP_RBTREENODE*)(n) )
 
#define SCIPrbtreeFindInt(r, k, n)   SCIPrbtreeFindInt_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n))
 
#define SCIPrbtreeFindReal(r, k, n)   SCIPrbtreeFindReal_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n))
 
#define SCIPrbtreeFindPtr(c, r, k, n)   SCIPrbtreeFindPtr_call((c),(SCIP_RBTREENODE*)(r),(void*)(k),(SCIP_RBTREENODE**)(n))
 
#define SCIPrbtreeFindElem(c, r, k, n)   SCIPrbtreeFindElem_call((c),(SCIP_RBTREENODE*)(r),(SCIP_RBTREENODE*)(k),(SCIP_RBTREENODE**)(n))
 
#define FOR_EACH_NODE(type, n, r, body)
 
#define SCIP_DEF_RBTREE_FIND(NAME, KEYTYPE, NODETYPE, LT, GT)
 

Typedefs

typedef struct SCIP_RBTreeNode SCIP_RBTREENODE
 

Functions

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

◆ SCIP_RBTREE_HOOKS

#define SCIP_RBTREE_HOOKS   SCIP_RBTREENODE _rbtreenode

Definition at line 62 of file rbtree.h.

◆ SCIPrbtreeFirst

#define SCIPrbtreeFirst (   root)    SCIPrbtreeFirst_call((SCIP_RBTREENODE*)(root))

Definition at line 65 of file rbtree.h.

Referenced by SCIPrbtreeDelete_call().

◆ SCIPrbtreeLast

#define SCIPrbtreeLast (   root)    SCIPrbtreeLast_call((SCIP_RBTREENODE*)(root))

Definition at line 66 of file rbtree.h.

◆ SCIPrbtreeSuccessor

#define SCIPrbtreeSuccessor (   x)    SCIPrbtreeSuccessor_call((SCIP_RBTREENODE*)(x))

Definition at line 67 of file rbtree.h.

◆ SCIPrbtreePredecessor

#define SCIPrbtreePredecessor (   x)    SCIPrbtreePredecessor_call((SCIP_RBTREENODE*)(x))

Definition at line 68 of file rbtree.h.

◆ SCIPrbtreeDelete

#define SCIPrbtreeDelete (   root,
  node 
)    SCIPrbtreeDelete_call((SCIP_RBTREENODE**)(root), (SCIP_RBTREENODE*)(node))

Definition at line 69 of file rbtree.h.

Referenced by unlinkChunk().

◆ SCIPrbtreeInsert

#define SCIPrbtreeInsert (   r,
  p,
  c,
 
)    SCIPrbtreeInsert_call((SCIP_RBTREENODE**)(r), (SCIP_RBTREENODE*)(p), (c), (SCIP_RBTREENODE*)(n) )

Definition at line 70 of file rbtree.h.

Referenced by linkChunk().

◆ SCIPrbtreeFindInt

#define SCIPrbtreeFindInt (   r,
  k,
 
)    SCIPrbtreeFindInt_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n))

Definition at line 71 of file rbtree.h.

◆ SCIPrbtreeFindReal

#define SCIPrbtreeFindReal (   r,
  k,
 
)    SCIPrbtreeFindReal_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n))

Definition at line 72 of file rbtree.h.

◆ SCIPrbtreeFindPtr

#define SCIPrbtreeFindPtr (   c,
  r,
  k,
 
)    SCIPrbtreeFindPtr_call((c),(SCIP_RBTREENODE*)(r),(void*)(k),(SCIP_RBTREENODE**)(n))

Definition at line 73 of file rbtree.h.

◆ SCIPrbtreeFindElem

#define SCIPrbtreeFindElem (   c,
  r,
  k,
 
)    SCIPrbtreeFindElem_call((c),(SCIP_RBTREENODE*)(r),(SCIP_RBTREENODE*)(k),(SCIP_RBTREENODE**)(n))

Definition at line 74 of file rbtree.h.

◆ FOR_EACH_NODE

#define FOR_EACH_NODE (   type,
  n,
  r,
  body 
)
Value:
{ \
type n; \
type __next; \
n = (type) SCIPrbtreeFirst(r); \
while( n != NULL ) \
{ \
__next = (type) SCIPrbtreeSuccessor(n); \
body \
n = __next; \
} \
}
#define NULL
Definition: def.h:267
#define SCIPrbtreeFirst(root)
Definition: rbtree.h:65
SCIP_Real * r
Definition: circlepacking.c:59
#define SCIPrbtreeSuccessor(x)
Definition: rbtree.h:67

Definition at line 77 of file rbtree.h.

Referenced by BMScheckEmptyBlockMemory_call(), BMSdisplayBlockMemory_call(), clearChkmem(), and isPtrInChkmem().

◆ SCIP_DEF_RBTREE_FIND

#define SCIP_DEF_RBTREE_FIND (   NAME,
  KEYTYPE,
  NODETYPE,
  LT,
  GT 
)

Definition at line 90 of file rbtree.h.

Typedef Documentation

◆ SCIP_RBTREENODE

Definition at line 42 of file rbtree.h.

Function Documentation

◆ 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 215 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 229 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 243 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 263 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 285 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 340 of file rbtree.c.

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