Scippy

SCIP

Solving Constraint Integer Programs

rbtree.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file rbtree.c
17  * @brief intrusive red black tree datastructure
18  * @author Robert Lion Gottwald
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "scip/rbtree.h"
24 
25 #define RED ((uintptr_t)0x1u)
26 #define BLACK ((uintptr_t)0x0u)
27 #define COLOR(node) ((node)->parent & RED)
28 #define IS_RED(node) ( (node) != NULL && COLOR(node) )
29 #define IS_BLACK(node) ( (node) == NULL || !COLOR(node) )
30 #define MAKE_RED(node) do { (node)->parent |= RED; } while(0)
31 #define MAKE_BLACK(node) do { (node)->parent &= ~RED; } while(0)
32 #define LEFT 0
33 #define RIGHT 1
34 #define OPPOSITE(dir) ( 1 - (dir) )
35 #define PARENT(node) ( (SCIP_RBTREENODE*)((node)->parent & ~RED) )
36 #define SET_PARENT(n, p) do { (n)->parent = (uintptr_t)(p) | COLOR(n); } while(0)
37 #define SET_COLOR(n, c) do { if( c == RED ) { MAKE_RED(n); } else { MAKE_BLACK(n); } } while(0)
38 
39 /* functions for red black tree management; see Cormen, Thomas H. Introduction to algorithms. MIT press, 2009. */
40 
41 /** rotate the tree in the given direction */
42 static
43 void rbRotate(
44  SCIP_RBTREENODE** root, /**< pointer to store new root of the tree */
45  SCIP_RBTREENODE* x, /**< node to perform rotation for */
46  int dir /**< direction of rotation */
47  )
48 {
49  SCIP_RBTREENODE* p;
50  SCIP_RBTREENODE* y = x->child[OPPOSITE(dir)];
51  x->child[OPPOSITE(dir)] = y->child[dir];
52  if( y->child[dir] != NULL )
53  {
54  SET_PARENT(y->child[dir], x);
55  }
56 
57  p = PARENT(x);
58  SET_PARENT(y, p);
59 
60  if( p == NULL )
61  *root = y;
62  else if( x == p->child[dir] )
63  p->child[dir] = y;
64  else
65  p->child[OPPOSITE(dir)] = y;
66 
67  y->child[dir] = x;
68  SET_PARENT(x, y);
69 }
70 
71 /** restores the red-black tree property after an insert */
72 static
74  SCIP_RBTREENODE** root, /**< pointer to store new root of the tree */
75  SCIP_RBTREENODE* z /**< inserted node */
76  )
77 {
78  SCIP_RBTREENODE* p;
79  p = PARENT(z);
80 
81  while( IS_RED(p) )
82  {
83  SCIP_RBTREENODE* pp;
84  SCIP_RBTREENODE* y;
85  int dir;
86 
87  pp = PARENT(p);
88  dir = p == pp->child[LEFT] ? RIGHT : LEFT;
89 
90  y = pp->child[dir];
91  if( IS_RED(y) )
92  {
93  MAKE_BLACK(p);
94  MAKE_BLACK(y);
95  MAKE_RED(pp);
96  z = pp;
97  }
98  else
99  {
100  if( z == p->child[dir] )
101  {
102  z = p;
103  rbRotate(root, z, OPPOSITE(dir));
104  p = PARENT(z);
105  pp = PARENT(p);
106  }
107 
108  MAKE_BLACK(p);
109  MAKE_RED(pp);
110  rbRotate(root, pp, dir);
111  }
112 
113  p = PARENT(z);
114  }
115 
116  MAKE_BLACK(*root);
117 }
118 
119 /** restores the red-black tree property after an insert */
120 static
122  SCIP_RBTREENODE** root, /**< pointer to store new root of the tree */
123  SCIP_RBTREENODE* x, /**< start node for fixup */
124  SCIP_RBTREENODE* nil /**< fake node representing NULL to properly reassemble the tree */
125  )
126 {
127  while( x != *root && IS_BLACK(x) )
128  {
129  SCIP_RBTREENODE* p;
130  SCIP_RBTREENODE* w;
131  int dir;
132 
133  p = PARENT(x == NULL ? nil : x);
134  dir = x == p->child[LEFT] ? RIGHT : LEFT;
135 
136  w = p->child[dir];
137  assert(w != NULL);
138 
139  if( COLOR(w) == RED )
140  {
141  MAKE_BLACK(w);
142  MAKE_RED(p);
143  rbRotate(root, p, OPPOSITE(dir));
144  assert(p == PARENT(x == NULL ? nil : x));
145  w = p->child[dir];
146  assert(w != NULL);
147  }
148 
149  if( IS_BLACK(w->child[LEFT]) && IS_BLACK(w->child[RIGHT]) )
150  {
151  MAKE_RED(w);
152  x = p;
153  }
154  else
155  {
156  if( IS_BLACK(w->child[dir]) )
157  {
158  MAKE_BLACK(w->child[OPPOSITE(dir)]);
159  MAKE_RED(w);
160  rbRotate(root, w, dir);
161  assert(p == PARENT(x == NULL ? nil : x));
162  w = p->child[dir];
163  }
164  SET_COLOR(w, COLOR(p));
165  MAKE_BLACK(p);
166  MAKE_BLACK(w->child[dir]);
167  rbRotate(root, p, OPPOSITE(dir));
168  x = *root;
169  }
170  }
171 
172  if( x != NULL )
173  {
174  MAKE_BLACK(x);
175  }
176 }
177 
178 /** replaces the subtree rooted at node u with the subtree rooted at node v */
179 static
181  SCIP_RBTREENODE** root, /**< pointer to store the new root */
182  SCIP_RBTREENODE* u, /**< node u */
183  SCIP_RBTREENODE* v, /**< node v */
184  SCIP_RBTREENODE* nil /**< fake node representing NULL to properly reassemble the tree */
185  )
186 {
187  SCIP_RBTREENODE* up;
188 
189  up = PARENT(u);
190 
191  if( up == NULL )
192  *root = v;
193  else if( u == up->child[LEFT] )
194  up->child[LEFT] = v;
195  else
196  up->child[RIGHT] = v;
197 
198  if( v == NULL )
199  v = nil;
200 
201  SET_PARENT(v, up);
202 }
203 
204 /** get first element in tree with respect to sorting key */
206  SCIP_RBTREENODE* root /**< root of the tree */
207  )
208 {
209  if( root == NULL )
210  return NULL;
211 
212  while(root->child[LEFT] != NULL)
213  root = root->child[LEFT];
214 
215  return root;
216 }
217 
218 /** get last element in tree with respect to sorting key */
220  SCIP_RBTREENODE* root /**< root of the tree */
221  )
222 {
223  if( root == NULL )
224  return NULL;
225 
226  while(root->child[RIGHT] != NULL)
227  root = root->child[RIGHT];
228 
229  return root;
230 }
231 
232 /** get successor of given element in the tree */
234  SCIP_RBTREENODE* x /**< element to get successor for */
235  )
236 {
237  SCIP_RBTREENODE* y;
238  if( x->child[RIGHT] != NULL )
239  return SCIPrbtreeFirst_call(x->child[RIGHT]);
240 
241  y = PARENT(x);
242 
243  while( y != NULL && x == y->child[RIGHT] )
244  {
245  x = y;
246  y = PARENT(y);
247  }
248 
249  return y;
250 }
251 
252 /** get predecessor of given element in the tree */
254  SCIP_RBTREENODE* x /**< element to get predecessor for */
255  )
256 {
257  SCIP_RBTREENODE* y;
258  if( x->child[LEFT] != NULL )
259  return SCIPrbtreeLast_call(x->child[LEFT]);
260 
261  y = PARENT(x);
262 
263  while( y != NULL && x == y->child[LEFT] )
264  {
265  x = y;
266  y = PARENT(y);
267  }
268 
269  return y;
270 }
271 
272 /** delete the given node from the tree given by it's root node.
273  * The node must be contained in the tree rooted at root.
274  */
276  SCIP_RBTREENODE** root, /**< root of the tree */
277  SCIP_RBTREENODE* node /**< node to delete from tree */
278  )
279 {
280  SCIP_RBTREENODE nil;
281  SCIP_RBTREENODE* y;
282  SCIP_RBTREENODE* x;
283  unsigned int yorigcolor;
284 
285  nil.parent = 0;
286 
287  y = node;
288  yorigcolor = COLOR(y);
289 
290  if( node->child[LEFT] == NULL )
291  {
292  x = node->child[RIGHT];
293  rbTransplant(root, node, x, &nil);
294  }
295  else if( node->child[RIGHT] == NULL )
296  {
297  x = node->child[LEFT];
298  rbTransplant(root, node, x, &nil);
299  }
300  else
301  {
302  y = SCIPrbtreeFirst(node->child[RIGHT]);
303  yorigcolor = COLOR(y);
304  x = y->child[RIGHT];
305  if( PARENT(y) == node )
306  {
307  SET_PARENT(x == NULL ? &nil : x, y);
308  }
309  else
310  {
311  rbTransplant(root, y, y->child[RIGHT], &nil);
312  y->child[RIGHT] = node->child[RIGHT];
313  SET_PARENT(y->child[RIGHT], y);
314  }
315  rbTransplant(root, node, y, &nil);
316  y->child[LEFT] = node->child[LEFT];
317  SET_PARENT(y->child[LEFT], y);
318  SET_COLOR(y, COLOR(node));
319  }
320 
321  if( yorigcolor == BLACK )
322  rbDeleteFixup(root, x, &nil);
323 }
324 
325 /** insert node into the tree given by it's root. Requires the
326  * future parent and the position of the parent as returned by
327  * the tree's find function defined using the SCIP_DEF_RBTREE_FIND
328  * macro.
329  */
331  SCIP_RBTREENODE** root, /**< root of the tree */
332  SCIP_RBTREENODE* parent, /**< future parent of node to be inserted */
333  int pos, /**< position of parent with respect to node, i.e.
334  * -1 if the parent's key comes before node and 1
335  * if the parent's key comes after the node
336  */
337  SCIP_RBTREENODE* node /**< node to insert into the tree */
338  )
339 {
340  SET_PARENT(node, parent);
341  if( parent == NULL )
342  *root = node;
343  else if( pos > 0 )
344  parent->child[LEFT] = node;
345  else
346  parent->child[RIGHT] = node;
347 
348  node->child[LEFT] = NULL;
349  node->child[RIGHT] = NULL;
350  MAKE_RED(node);
351  rbInsertFixup(root, node);
352 }
#define COLOR(node)
Definition: rbtree.c:27
SCIP_RBTREENODE * SCIPrbtreeSuccessor_call(SCIP_RBTREENODE *x)
Definition: rbtree.c:233
#define IS_RED(node)
Definition: rbtree.c:28
#define SET_COLOR(n, c)
Definition: rbtree.c:37
#define IS_BLACK(node)
Definition: rbtree.c:29
void SCIPrbtreeDelete_call(SCIP_RBTREENODE **root, SCIP_RBTREENODE *node)
Definition: rbtree.c:275
#define OPPOSITE(dir)
Definition: rbtree.c:34
static void rbDeleteFixup(SCIP_RBTREENODE **root, SCIP_RBTREENODE *x, SCIP_RBTREENODE *nil)
Definition: rbtree.c:121
#define LEFT
Definition: rbtree.c:32
#define RED
Definition: rbtree.c:25
SCIP_RBTREENODE * SCIPrbtreeLast_call(SCIP_RBTREENODE *root)
Definition: rbtree.c:219
#define MAKE_BLACK(node)
Definition: rbtree.c:31
SCIP_RBTREENODE * child[2]
Definition: rbtree.h:38
SCIP_RBTREENODE * SCIPrbtreeFirst_call(SCIP_RBTREENODE *root)
Definition: rbtree.c:205
#define SET_PARENT(n, p)
Definition: rbtree.c:36
#define SCIPrbtreeFirst(root)
Definition: rbtree.h:56
#define PARENT(node)
Definition: rbtree.c:35
#define BLACK
Definition: rbtree.c:26
SCIP_RBTREENODE * SCIPrbtreePredecessor_call(SCIP_RBTREENODE *x)
Definition: rbtree.c:253
static void rbRotate(SCIP_RBTREENODE **root, SCIP_RBTREENODE *x, int dir)
Definition: rbtree.c:43
void SCIPrbtreeInsert_call(SCIP_RBTREENODE **root, SCIP_RBTREENODE *parent, int pos, SCIP_RBTREENODE *node)
Definition: rbtree.c:330
#define RIGHT
Definition: rbtree.c:33
uintptr_t parent
Definition: rbtree.h:37
static void rbTransplant(SCIP_RBTREENODE **root, SCIP_RBTREENODE *u, SCIP_RBTREENODE *v, SCIP_RBTREENODE *nil)
Definition: rbtree.c:180
#define MAKE_RED(node)
Definition: rbtree.c:30
intrusive red black tree datastructure
static void rbInsertFixup(SCIP_RBTREENODE **root, SCIP_RBTREENODE *z)
Definition: rbtree.c:73