Detailed Description

intrusive red black tree datastructure

Author: Leona Gottwald

Definition in file rbtree.h.

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

Data Structures
struct	SCIP_RBTreeNode

Macros
#define	SCIP_RBTREE_HOOKS SCIP_RBTREENODE _rbtreenode
#define	SCIPrbtreeFirst(root)
#define	SCIPrbtreeLast(root)
#define	SCIPrbtreeSuccessor(x)
#define	SCIPrbtreePredecessor(x)
#define	SCIPrbtreeDelete(root, node)
#define	SCIPrbtreeInsert(r, p, c, n)
#define	SCIPrbtreeFindInt(r, k, n)
#define	SCIPrbtreeFindReal(r, k, n)
#define	SCIPrbtreeFindPtr(c, r, k, n)
#define	SCIPrbtreeFindElem(c, r, k, n)
#define	FOR_EACH_NODE(type, n, r, body)
#define	SCIP_DEF_RBTREE_FIND(NAME, KEYTYPE, NODETYPE, LT, GT)

Functions
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

◆ SCIP_RBTREE_HOOKS

#define SCIP_RBTREE_HOOKS SCIP_RBTREENODE _rbtreenode

Definition at line 62 of file rbtree.h.

◆ SCIPrbtreeFirst

#define SCIPrbtreeFirst ( root )

Value:

SCIPrbtreeFirst_call((SCIP_RBTREENODE*)(root))

SCIPrbtreeFirst_call

SCIP_RBTREENODE * SCIPrbtreeFirst_call(SCIP_RBTREENODE *root)

Definition rbtree.c:227

SCIP_RBTREENODE

struct SCIP_RBTreeNode SCIP_RBTREENODE

Definition rbtree.h:42

Definition at line 65 of file rbtree.h.

Referenced by SCIPrbtreeDelete_call().

◆ SCIPrbtreeLast

#define SCIPrbtreeLast ( root )

Value:

SCIPrbtreeLast_call((SCIP_RBTREENODE*)(root))

SCIPrbtreeLast_call

SCIP_RBTREENODE * SCIPrbtreeLast_call(SCIP_RBTREENODE *root)

Definition rbtree.c:241

Definition at line 66 of file rbtree.h.

◆ SCIPrbtreeSuccessor

#define SCIPrbtreeSuccessor ( x )

Value:

SCIPrbtreeSuccessor_call((SCIP_RBTREENODE*)(x))

x

SCIP_VAR ** x

Definition circlepacking.c:63

SCIPrbtreeSuccessor_call

SCIP_RBTREENODE * SCIPrbtreeSuccessor_call(SCIP_RBTREENODE *x)

Definition rbtree.c:255

Definition at line 67 of file rbtree.h.

◆ SCIPrbtreePredecessor

#define SCIPrbtreePredecessor ( x )

Value:

SCIPrbtreePredecessor_call((SCIP_RBTREENODE*)(x))

SCIPrbtreePredecessor_call

SCIP_RBTREENODE * SCIPrbtreePredecessor_call(SCIP_RBTREENODE *x)

Definition rbtree.c:275

Definition at line 68 of file rbtree.h.

◆ SCIPrbtreeDelete

#define SCIPrbtreeDelete	(		root,
			node )

Value:

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

SCIPrbtreeDelete_call

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

Definition rbtree.c:297

Definition at line 69 of file rbtree.h.

Referenced by unlinkChunk().

◆ SCIPrbtreeInsert

#define SCIPrbtreeInsert	(	r,
		p,
		c,
		n )

Value:

SCIPrbtreeInsert_call((SCIP_RBTREENODE**)(r), (SCIP_RBTREENODE*)(p), (c), (SCIP_RBTREENODE*)(n) )

c

int c

Definition heur_intdiving.c:219

r

int r

Definition heur_intshifting.c:719

SCIPrbtreeInsert_call

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

Definition rbtree.c:352

Definition at line 70 of file rbtree.h.

Referenced by linkChunk().

◆ SCIPrbtreeFindInt

#define SCIPrbtreeFindInt	(	r,
		k,
		n )

Value:

SCIPrbtreeFindInt_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n))

Definition at line 71 of file rbtree.h.

◆ SCIPrbtreeFindReal

#define SCIPrbtreeFindReal	(	r,
		k,
		n )

Value:

SCIPrbtreeFindReal_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n))

Definition at line 72 of file rbtree.h.

◆ SCIPrbtreeFindPtr

#define SCIPrbtreeFindPtr	(	c,
		r,
		k,
		n )

Value:

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,
		n )

Value:

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; \
  } \
}

Definition at line 77 of file rbtree.h.

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

◆ 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

typedef struct SCIP_RBTreeNode 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

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.

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ SCIP_RBTREE_HOOKS

◆ SCIPrbtreeFirst

◆ SCIPrbtreeLast

◆ SCIPrbtreeSuccessor

◆ SCIPrbtreePredecessor

◆ SCIPrbtreeDelete

◆ SCIPrbtreeInsert

◆ SCIPrbtreeFindInt

◆ SCIPrbtreeFindReal

◆ SCIPrbtreeFindPtr

◆ SCIPrbtreeFindElem

◆ FOR_EACH_NODE

◆ SCIP_DEF_RBTREE_FIND

Typedef Documentation

◆ SCIP_RBTREENODE

Function Documentation

◆ SCIPrbtreeFirst_call()

◆ SCIPrbtreeLast_call()

◆ SCIPrbtreeSuccessor_call()

◆ SCIPrbtreePredecessor_call()

◆ SCIPrbtreeDelete_call()

◆ SCIPrbtreeInsert_call()