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