1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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   	   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
83   	void rbInsertFixup(
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;
94   	      SCIP_RBTREENODE* y;
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
131  	void rbDeleteFixup(
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;
140  	      SCIP_RBTREENODE* w;
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
190  	void rbTransplant(
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 */
215  	SCIP_RBTREENODE* SCIPrbtreeFirst_call(
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 */
229  	SCIP_RBTREENODE* SCIPrbtreeLast_call(
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 */
243  	SCIP_RBTREENODE* SCIPrbtreeSuccessor_call(
244  	   SCIP_RBTREENODE*      x                   /**< element to get successor for */
245  	   )
246  	{
247  	   SCIP_RBTREENODE* y;
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 */
263  	SCIP_RBTREENODE* SCIPrbtreePredecessor_call(
264  	   SCIP_RBTREENODE*      x                   /**< element to get predecessor for */
265  	   )
266  	{
267  	   SCIP_RBTREENODE* y;
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  	 */
285  	void SCIPrbtreeDelete_call(
286  	   SCIP_RBTREENODE**     root,               /**< root of the tree */
287  	   SCIP_RBTREENODE*      node                /**< node to delete from tree */
288  	   )
289  	{
290  	   SCIP_RBTREENODE nil;
291  	   SCIP_RBTREENODE* y;
292  	   SCIP_RBTREENODE* x;
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  	 */
340  	void SCIPrbtreeInsert_call(
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  	}
363