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