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