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.h 26 * @brief intrusive red black tree datastructure 27 * @author Leona Gottwald 28 */ 29 30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 31 32 #ifndef __SCIP_RB_TREE_H__ 33 #define __SCIP_RB_TREE_H__ 34 35 #include "scip/def.h" 36 #include "scip/type_misc.h" 37 38 #ifdef __cplusplus 39 extern "C" { 40 #endif 41 42 typedef struct SCIP_RBTreeNode SCIP_RBTREENODE; 43 44 struct SCIP_RBTreeNode 45 { 46 uintptr_t parent; 47 SCIP_RBTREENODE* child[2]; 48 }; 49 50 /* macro to make any structure a node in a rbtree. 51 * It is very important that this is the first member of the structure. 52 * 53 * Example usage: 54 * struct SomeStruct 55 * { 56 * SCIP_RBTREE_HOOKS; 57 * OTHERDATA* mydata; 58 * int othermember; 59 * }; 60 * 61 */ 62 #define SCIP_RBTREE_HOOKS SCIP_RBTREENODE _rbtreenode 63 64 /* convenience macros that automtically cast the given arguments to SCIP_RBTREENODE */ 65 #define SCIPrbtreeFirst(root) SCIPrbtreeFirst_call((SCIP_RBTREENODE*)(root)) 66 #define SCIPrbtreeLast(root) SCIPrbtreeLast_call((SCIP_RBTREENODE*)(root)) 67 #define SCIPrbtreeSuccessor(x) SCIPrbtreeSuccessor_call((SCIP_RBTREENODE*)(x)) 68 #define SCIPrbtreePredecessor(x) SCIPrbtreePredecessor_call((SCIP_RBTREENODE*)(x)) 69 #define SCIPrbtreeDelete(root, node) SCIPrbtreeDelete_call((SCIP_RBTREENODE**)(root), (SCIP_RBTREENODE*)(node)) 70 #define SCIPrbtreeInsert(r,p,c,n) SCIPrbtreeInsert_call((SCIP_RBTREENODE**)(r), (SCIP_RBTREENODE*)(p), (c), (SCIP_RBTREENODE*)(n) ) 71 #define SCIPrbtreeFindInt(r,k,n) SCIPrbtreeFindInt_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n)) 72 #define SCIPrbtreeFindReal(r,k,n) SCIPrbtreeFindReal_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n)) 73 #define SCIPrbtreeFindPtr(c,r,k,n) SCIPrbtreeFindPtr_call((c),(SCIP_RBTREENODE*)(r),(void*)(k),(SCIP_RBTREENODE**)(n)) 74 #define SCIPrbtreeFindElem(c,r,k,n) SCIPrbtreeFindElem_call((c),(SCIP_RBTREENODE*)(r),(SCIP_RBTREENODE*)(k),(SCIP_RBTREENODE**)(n)) 75 76 77 #define FOR_EACH_NODE(type, n, r, body) \ 78 { \ 79 type n; \ 80 type __next; \ 81 n = (type) SCIPrbtreeFirst(r); \ 82 while( n != NULL ) \ 83 { \ 84 __next = (type) SCIPrbtreeSuccessor(n); \ 85 body \ 86 n = __next; \ 87 } \ 88 } 89 90 #define SCIP_DEF_RBTREE_FIND(NAME, KEYTYPE, NODETYPE, LT, GT) \ 91 /** Searches for an element in the tree given by it's root. If a node equal to the given element exists in the tree, \ 92 * (*node) will point to that node upon termination of this function and 0 will be returned. \ 93 * If the tree is empty (*node) will be NULL. Otherwise (*node) will point to the predecessor or \ 94 * successor of the given element and -1 or 1 will be returned respectively. The return value and the \ 95 * predecessor or successor can then be passed to the insert function to insert the element but only if \ 96 * it is not in the tree already, i.e. this function did not return 0. \ 97 * \ 98 * @returns 0 if the key was found, then *node is the node with the key and \ 99 * -1 or 1 if the node was node found, then *node is the node with the \ 100 * next smaller, or next larger key repectively. \ 101 */ \ 102 int NAME( \ 103 NODETYPE* root, /**< root of the tree */ \ 104 KEYTYPE key, /**< key to search for */ \ 105 NODETYPE** node /**< pointer to return node */ \ 106 ) \ 107 { \ 108 SCIP_RBTREENODE* x; \ 109 *node = NULL; \ 110 x = (SCIP_RBTREENODE*) root; \ 111 while( x != NULL ) \ 112 { \ 113 *node = (NODETYPE*) x; \ 114 if( LT(key, ((NODETYPE*)x)) ) \ 115 x = x->child[0]; \ 116 else if( GT(key, ((NODETYPE*)x)) ) \ 117 x = x->child[1]; \ 118 else \ 119 return 0; \ 120 } \ 121 if( *node != NULL && LT(key, ((NODETYPE*)(*node)) ) ) \ 122 return 1; \ 123 return -1; \ 124 } 125 126 127 /** get first element in tree with respect to sorting key */ 128 SCIP_EXPORT 129 SCIP_RBTREENODE* SCIPrbtreeFirst_call( 130 SCIP_RBTREENODE* root /**< root of the tree */ 131 ); 132 133 /** get last element in tree with respect to sorting key */ 134 SCIP_EXPORT 135 SCIP_RBTREENODE* SCIPrbtreeLast_call( 136 SCIP_RBTREENODE* root /**< root of the tree */ 137 ); 138 139 /** get successor of given element in the tree */ 140 SCIP_EXPORT 141 SCIP_RBTREENODE* SCIPrbtreeSuccessor_call( 142 SCIP_RBTREENODE* x /**< element to get successor for */ 143 ); 144 145 /** get predecessor of given element in the tree */ 146 SCIP_EXPORT 147 SCIP_RBTREENODE* SCIPrbtreePredecessor_call( 148 SCIP_RBTREENODE* x /**< element to get predecessor for */ 149 ); 150 151 /** delete the given node from the tree given by it's root node. 152 * The node must be contained in the tree rooted at root. 153 */ 154 SCIP_EXPORT 155 void SCIPrbtreeDelete_call( 156 SCIP_RBTREENODE** root, /**< root of the tree */ 157 SCIP_RBTREENODE* node /**< node to delete from tree */ 158 ); 159 160 /** insert node into the tree given by it's root. Requires the 161 * future parent and the position of the parent as returned by 162 * the tree's find function defined using the SCIP_DEF_RBTREE_FIND 163 * macro. 164 */ 165 SCIP_EXPORT 166 void SCIPrbtreeInsert_call( 167 SCIP_RBTREENODE** root, /**< root of the tree */ 168 SCIP_RBTREENODE* parent, /**< future parent of node to be inserted */ 169 int pos, /**< position of parent with respect to node, i.e. 170 * -1 if the parent's key comes before node and 1 171 * if the parent's key comes after the node 172 */ 173 SCIP_RBTREENODE* node /**< node to insert into the tree */ 174 ); 175 176 #ifdef __cplusplus 177 } 178 #endif 179 180 #endif 181