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-2024 Zuse Institute Berlin (ZIB) */
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  assert(x != NULL);
60 
61  SCIP_RBTREENODE* p;
62  SCIP_RBTREENODE* y = x->child[OPPOSITE(dir)];
63 
64  x->child[OPPOSITE(dir)] = y->child[dir];
65  if( y->child[dir] != NULL )
66  {
67  SET_PARENT(y->child[dir], x);
68  }
69 
70  p = PARENT(x);
71  SET_PARENT(y, p);
72 
73  if( p == NULL )
74  *root = y;
75  else if( x == p->child[dir] )
76  p->child[dir] = y;
77  else
78  p->child[OPPOSITE(dir)] = y;
79 
80  y->child[dir] = x;
81  SET_PARENT(x, y);
82 }
83 
84 /** restores the red-black tree property after an insert */
85 static
87  SCIP_RBTREENODE** root, /**< pointer to store new root of the tree */
88  SCIP_RBTREENODE* z /**< inserted node */
89  )
90 {
91  assert(z != NULL);
92 
93  SCIP_RBTREENODE* p;
94  p = PARENT(z);
95 
96  while( IS_RED(p) )
97  {
98  SCIP_RBTREENODE* pp;
100  int dir;
101 
102  assert(p != NULL);
103  pp = PARENT(p);
104  assert(pp != NULL);
105  dir = p == pp->child[LEFT] ? RIGHT : LEFT;
106 
107  y = pp->child[dir];
108  if( IS_RED(y) )
109  {
110  MAKE_BLACK(p);
111  MAKE_BLACK(y);
112  MAKE_RED(pp);
113  z = pp;
114  }
115  else
116  {
117  if( z == p->child[dir] )
118  {
119  z = p;
120  rbRotate(root, z, OPPOSITE(dir));
121  p = PARENT(z);
122  assert(p != NULL);
123  pp = PARENT(p);
124  }
125 
126  assert(p != NULL);
127  MAKE_BLACK(p);
128  assert(pp != NULL);
129  MAKE_RED(pp);
130  rbRotate(root, pp, dir);
131  }
132 
133  p = PARENT(z);
134  }
135 
136  MAKE_BLACK(*root);
137 }
138 
139 /** restores the red-black tree property after an insert */
140 static
142  SCIP_RBTREENODE** root, /**< pointer to store new root of the tree */
143  SCIP_RBTREENODE* x, /**< start node for fixup */
144  SCIP_RBTREENODE* nil /**< fake node representing NULL to properly reassemble the tree */
145  )
146 {
147  while( x != *root && IS_BLACK(x) )
148  {
149  SCIP_RBTREENODE* p;
151  int dir;
152 
153  p = PARENT(x == NULL ? nil : x);
154  assert(p != NULL);
155  dir = x == p->child[LEFT] ? RIGHT : LEFT;
156 
157  w = p->child[dir];
158  assert(w != NULL);
159 
160  if( COLOR(w) == RED )
161  {
162  MAKE_BLACK(w);
163  MAKE_RED(p);
164  rbRotate(root, p, OPPOSITE(dir));
165  assert(p == PARENT(x == NULL ? nil : x));
166  w = p->child[dir];
167  assert(w != NULL);
168  }
169 
170  if( IS_BLACK(w->child[LEFT]) && IS_BLACK(w->child[RIGHT]) )
171  {
172  MAKE_RED(w);
173  x = p;
174  }
175  else
176  {
177  if( IS_BLACK(w->child[dir]) )
178  {
179  MAKE_BLACK(w->child[OPPOSITE(dir)]);
180  MAKE_RED(w);
181  rbRotate(root, w, dir);
182  assert(p == PARENT(x == NULL ? nil : x));
183  w = p->child[dir];
184  }
185  assert(w != NULL);
186  SET_COLOR(w, COLOR(p));
187  MAKE_BLACK(p);
188  MAKE_BLACK(w->child[dir]);
189  rbRotate(root, p, OPPOSITE(dir));
190  x = *root;
191  }
192  }
193 
194  if( x != NULL )
195  {
196  MAKE_BLACK(x);
197  }
198 }
199 
200 /** replaces the subtree rooted at node u with the subtree rooted at node v */
201 static
203  SCIP_RBTREENODE** root, /**< pointer to store the new root */
204  SCIP_RBTREENODE* u, /**< node u */
205  SCIP_RBTREENODE* v, /**< node v */
206  SCIP_RBTREENODE* nil /**< fake node representing NULL to properly reassemble the tree */
207  )
208 {
209  SCIP_RBTREENODE* up;
210 
211  up = PARENT(u);
212 
213  if( up == NULL )
214  *root = v;
215  else if( u == up->child[LEFT] )
216  up->child[LEFT] = v;
217  else
218  up->child[RIGHT] = v;
219 
220  if( v == NULL )
221  v = nil;
222 
223  SET_PARENT(v, up);
224 }
225 
226 /** get first element in tree with respect to sorting key */
228  SCIP_RBTREENODE* root /**< root of the tree */
229  )
230 {
231  if( root == NULL )
232  return NULL;
233 
234  while(root->child[LEFT] != NULL)
235  root = root->child[LEFT];
236 
237  return root;
238 }
239 
240 /** get last element in tree with respect to sorting key */
242  SCIP_RBTREENODE* root /**< root of the tree */
243  )
244 {
245  if( root == NULL )
246  return NULL;
247 
248  while(root->child[RIGHT] != NULL)
249  root = root->child[RIGHT];
250 
251  return root;
252 }
253 
254 /** get successor of given element in the tree */
256  SCIP_RBTREENODE* x /**< element to get successor for */
257  )
258 {
260  if( x->child[RIGHT] != NULL )
261  return SCIPrbtreeFirst_call(x->child[RIGHT]);
262 
263  y = PARENT(x);
264 
265  while( y != NULL && x == y->child[RIGHT] )
266  {
267  x = y;
268  y = PARENT(y);
269  }
270 
271  return y;
272 }
273 
274 /** get predecessor of given element in the tree */
276  SCIP_RBTREENODE* x /**< element to get predecessor for */
277  )
278 {
280  if( x->child[LEFT] != NULL )
281  return SCIPrbtreeLast_call(x->child[LEFT]);
282 
283  y = PARENT(x);
284 
285  while( y != NULL && x == y->child[LEFT] )
286  {
287  x = y;
288  y = PARENT(y);
289  }
290 
291  return y;
292 }
293 
294 /** delete the given node from the tree given by it's root node.
295  * The node must be contained in the tree rooted at root.
296  */
298  SCIP_RBTREENODE** root, /**< root of the tree */
299  SCIP_RBTREENODE* node /**< node to delete from tree */
300  )
301 {
302  SCIP_RBTREENODE nil;
305  unsigned int yorigcolor;
306 
307  nil.parent = 0;
308 
309  y = node;
310  yorigcolor = COLOR(y);
311 
312  if( node->child[LEFT] == NULL )
313  {
314  x = node->child[RIGHT];
315  rbTransplant(root, node, x, &nil);
316  }
317  else if( node->child[RIGHT] == NULL )
318  {
319  x = node->child[LEFT];
320  rbTransplant(root, node, x, &nil);
321  }
322  else
323  {
324  y = SCIPrbtreeFirst(node->child[RIGHT]);
325  yorigcolor = COLOR(y);
326  x = y->child[RIGHT];
327  if( PARENT(y) == node )
328  {
329  SET_PARENT(x == NULL ? &nil : x, y);
330  }
331  else
332  {
333  rbTransplant(root, y, y->child[RIGHT], &nil);
334  y->child[RIGHT] = node->child[RIGHT];
335  SET_PARENT(y->child[RIGHT], y);
336  }
337  rbTransplant(root, node, y, &nil);
338  y->child[LEFT] = node->child[LEFT];
339  SET_PARENT(y->child[LEFT], y);
340  SET_COLOR(y, COLOR(node));
341  }
342 
343  if( yorigcolor == BLACK )
344  rbDeleteFixup(root, x, &nil);
345 }
346 
347 /** insert node into the tree given by it's root. Requires the
348  * future parent and the position of the parent as returned by
349  * the tree's find function defined using the SCIP_DEF_RBTREE_FIND
350  * macro.
351  */
353  SCIP_RBTREENODE** root, /**< root of the tree */
354  SCIP_RBTREENODE* parent, /**< future parent of node to be inserted */
355  int pos, /**< position of parent with respect to node, i.e.
356  * -1 if the parent's key comes before node and 1
357  * if the parent's key comes after the node
358  */
359  SCIP_RBTREENODE* node /**< node to insert into the tree */
360  )
361 {
362  /* we avoid SET_PARENT here, as this would read from uninitialized memory in an attempt to preserve the color of node */
363  node->parent = (uintptr_t)parent | RED;
364  node->child[LEFT] = NULL;
365  node->child[RIGHT] = NULL;
366 
367  if( parent == NULL )
368  *root = node;
369  else if( pos > 0 )
370  parent->child[LEFT] = node;
371  else
372  parent->child[RIGHT] = node;
373 
374  rbInsertFixup(root, node);
375 }
#define COLOR(node)
Definition: rbtree.c:37
SCIP_RBTREENODE * SCIPrbtreeSuccessor_call(SCIP_RBTREENODE *x)
Definition: rbtree.c:255
#define NULL
Definition: def.h:267
#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:297
#define OPPOSITE(dir)
Definition: rbtree.c:44
static void rbDeleteFixup(SCIP_RBTREENODE **root, SCIP_RBTREENODE *x, SCIP_RBTREENODE *nil)
Definition: rbtree.c:141
#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:241
#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:227
#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:275
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:352
#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:202
#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:86