1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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
rbRotate(SCIP_RBTREENODE ** root,SCIP_RBTREENODE * x,int dir)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
rbInsertFixup(SCIP_RBTREENODE ** root,SCIP_RBTREENODE * z)74 void rbInsertFixup(
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;
85 SCIP_RBTREENODE* y;
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
rbDeleteFixup(SCIP_RBTREENODE ** root,SCIP_RBTREENODE * x,SCIP_RBTREENODE * nil)122 void rbDeleteFixup(
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;
131 SCIP_RBTREENODE* w;
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
rbTransplant(SCIP_RBTREENODE ** root,SCIP_RBTREENODE * u,SCIP_RBTREENODE * v,SCIP_RBTREENODE * nil)181 void rbTransplant(
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 */
SCIPrbtreeFirst_call(SCIP_RBTREENODE * root)206 SCIP_RBTREENODE* SCIPrbtreeFirst_call(
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 */
SCIPrbtreeLast_call(SCIP_RBTREENODE * root)220 SCIP_RBTREENODE* SCIPrbtreeLast_call(
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 */
SCIPrbtreeSuccessor_call(SCIP_RBTREENODE * x)234 SCIP_RBTREENODE* SCIPrbtreeSuccessor_call(
235 SCIP_RBTREENODE* x /**< element to get successor for */
236 )
237 {
238 SCIP_RBTREENODE* y;
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 */
SCIPrbtreePredecessor_call(SCIP_RBTREENODE * x)254 SCIP_RBTREENODE* SCIPrbtreePredecessor_call(
255 SCIP_RBTREENODE* x /**< element to get predecessor for */
256 )
257 {
258 SCIP_RBTREENODE* y;
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 */
SCIPrbtreeDelete_call(SCIP_RBTREENODE ** root,SCIP_RBTREENODE * node)276 void SCIPrbtreeDelete_call(
277 SCIP_RBTREENODE** root, /**< root of the tree */
278 SCIP_RBTREENODE* node /**< node to delete from tree */
279 )
280 {
281 SCIP_RBTREENODE nil;
282 SCIP_RBTREENODE* y;
283 SCIP_RBTREENODE* x;
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 */
SCIPrbtreeInsert_call(SCIP_RBTREENODE ** root,SCIP_RBTREENODE * parent,int pos,SCIP_RBTREENODE * node)331 void SCIPrbtreeInsert_call(
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 }
354