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