1 /* 2 * Copyright (c) International Business Machines Corp., 2001-2004 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation; either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See 12 * the GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 #ifndef RED_BLACK_TREE_H 19 #define RED_BLACK_TREE_H 20 21 /* 22 * *************************************************************************** 23 * 24 * Container class for a red-black tree ...... 25 * 26 * A binary tree that satisfies the following properties: 27 * 28 * 1. Every node is either red or black 29 * 2. The root node is black 30 * 3. Every leaf (NIL) is black 31 * 4. If a node is red, both its children are black 32 * 5. For each node, all paths from the node to descendant leaf nodes 33 * contain the same number of black nodes 34 * 35 * Due to points 4 & 5, the depth of a red-black tree containing n nodes 36 * is bounded by 2*log2(n+1) (WC). 37 * 38 * 39 * The rb_tree template requires two additional parmeters: 40 * 41 * - The contained TYPE class represents the objects stored in the tree. 42 * It has to support the copy constructor and the assignment operator (opr) 43 * - cmp is a functor used to define the order of objects of class TYPE: 44 * This class has to support an operator() that receives two objects from 45 * the TYPE class and returns a negative, 0, or a positive integer, 46 * depending on the comparison result. 47 * 48 * Dominique Heger, S. Rao 49 * 50 * *************************************************************************** 51 */ 52 53 /* Color enumeration for nodes of red-black tree */ 54 /* ********************************************* */ 55 56 #include "filelist.h" 57 58 typedef struct ffsb_file *datatype; 59 60 #define COMP_NODES(a, b) ((a)->num - (b)->num) 61 62 typedef enum red_black_color {red, black} rb_color; 63 64 /*! Representation of a node in a red-black tree */ 65 typedef struct red_black_node { 66 datatype object; /* the stored object */ 67 rb_color color; /* the color of the node */ 68 struct red_black_node *parent; /* points to the parent node */ 69 struct red_black_node *right; /* points to the right child */ 70 struct red_black_node *left; /* points to the left child */ 71 } rb_node; 72 73 typedef int(cmp)(datatype, datatype); 74 typedef void(opr)(void *); 75 typedef void(destructor)(datatype); 76 77 /* Construct of a red-black tree node 78 * - The object stored in the node 79 * - The color of the node 80 */ 81 82 extern rb_node *rbnode_construct(datatype object, rb_color color); 83 84 /* Recursive destructor for the entire sub-tree */ 85 /* ******************************************** */ 86 87 extern void rbnode_destruct(rb_node *node, destructor d); 88 89 /* Calculate the depth of the sub-tree spanned by the given node 90 * - The sub-tree root 91 * - The sub-tree depth 92 */ 93 94 extern int rbnode_depth(rb_node *node); 95 96 /* Get the leftmost node in the sub-tree spanned by the given node 97 * - The sub-tree root 98 * - The sub-tree minimum 99 */ 100 101 extern rb_node *rbnode_minimum(rb_node *node); 102 103 /* Get the rightmost node in the sub-tree spanned by the given node 104 * - The sub-tree root 105 * - The sub-tree maximum 106 */ 107 108 extern rb_node *rbnode_maximum(rb_node *node); 109 110 /* Replace the object */ 111 /* ****************** */ 112 113 extern void rbnode_replace(rb_node *node, datatype object); 114 115 /* Get the next node in the tree (according to the tree order) 116 * - The current node 117 * - The successor node, or NULL if node is the tree maximum 118 */ 119 120 extern rb_node *rbnode_successor(rb_node *node); 121 122 /* Get the previous node in the tree (according to the tree order) 123 * - The current node 124 * - The predecessor node, or NULL if node is the tree minimum 125 */ 126 127 extern rb_node *rbnode_predecessor(rb_node *node); 128 129 /* Duplicate the entire sub-tree rooted at the given node 130 * - The sub-tree root 131 * - A pointer to the duplicated sub-tree root 132 */ 133 134 extern rb_node *rbnode_duplicate(rb_node *node); 135 136 /* Traverse a red-black sub-tree 137 * - The sub-tree root 138 * - The operation to perform on each object in the sub-tree 139 */ 140 extern void rbnode_traverse(rb_node *node, opr *op); 141 142 /* Representation of a red-black tree */ 143 /* ********************************** */ 144 145 typedef struct red_black_tree { 146 rb_node *root; /* pointer to the tree root */ 147 int isize; /* number of objects stored */ 148 /* cmp * comp; */ /* compare function */ 149 } rb_tree; 150 151 /* Initialize a red-black tree with a comparision function 152 * - The tree 153 * - The comparision function 154 */ 155 156 void rbtree_init(rb_tree *tree); 157 158 /* Construct a red-black tree with a comparison object 159 * - A pointer to the comparison object to be used by the tree 160 * - The newly constructed tree 161 */ 162 163 rb_tree *rbtree_construct(void); 164 165 /* Clean a red-black tree [takes O(n) operations] 166 * - The tree 167 */ 168 169 extern void rbtree_clean(rb_tree *tree, destructor d); 170 171 /* Destruct a red-black tree 172 * - The tree 173 */ 174 175 extern void rbtree_destruct(rb_tree *tree, destructor d); 176 177 /* Get the size of the tree [takes O(1) operations] 178 * - The tree 179 * - The number of objects stored in the tree 180 */ 181 182 extern int rbtree_size(rb_tree *tree); 183 184 /* Get the depth of the tree [takes O(n) operations] 185 * - The tree 186 * - The length of the longest path from the root to a leaf node 187 */ 188 189 extern int rbtree_depth(rb_tree *tree); 190 191 /* Check whether the tree contains an object [takes O(log n) operations] 192 * - The tree 193 * - The query object 194 * - (true) if an equal object is found in the tree, otherwise (false) 195 */ 196 197 extern int rbtree_contains(rb_tree *tree, datatype object); 198 199 /* Insert an object to the tree [takes O(log n) operations] 200 * - The tree 201 * - The object to be inserted 202 * - Return the inserted object node 203 */ 204 205 extern rb_node *rbtree_insert(rb_tree *tree, datatype object); 206 207 /* Insert a new object to the tree as the a successor of a given node 208 * - The tree 209 * - The new node 210 */ 211 212 extern rb_node *insert_successor_at(rb_tree *tree, rb_node *at_node, 213 datatype object); 214 215 /* Insert a new object to the tree as the a predecessor of a given node 216 * - The tree 217 * - The new node 218 */ 219 220 extern rb_node *insert_predecessor_at(rb_tree *tree, rb_node *at_node, 221 datatype object); 222 223 /* Remove an object from the tree [takes O(log n) operations] 224 * - The tree 225 * - The object to be removed 226 * - The object should be contained in the tree 227 */ 228 229 extern void rbtree_remove(rb_tree *tree, datatype object, destructor d); 230 231 /* Get a handle to the tree minimum [takes O(log n) operations] 232 * - The tree 233 * - Return the minimal object in the tree, or a NULL if the tree is empty 234 */ 235 236 extern rb_node *rbtree_minimum(rb_tree *tree); 237 238 /* Get a handle to the tree maximum [takes O(log n) operations] 239 * - The tree 240 * - Return the maximal object in the tree, or a NULL if the tree is empty 241 */ 242 243 extern rb_node *rbtree_maximum(rb_tree *tree); 244 245 /* Get the next node in the tree (according to the tree order) 246 * - [takes O(log n) operations at worst-case, but only O(1) amortized] 247 * - The tree 248 * - The current object 249 * - The successor node, or a NULL, if we are at the tree maximum 250 */ 251 extern rb_node *rbtree_successor(rb_tree *tree, rb_node *node); 252 253 /* Get the previous node in the tree (according to the tree order) 254 * - [takes O(log n) operations at worst-case, but only O(1) amortized] 255 * - The tree 256 * - The current object 257 * - The predecessor node, or a NULL, if we are at the tree minimum 258 */ 259 260 extern rb_node *rbtree_predecessor(rb_tree *tree, rb_node *node); 261 262 /* Find a node that contains the given object 263 * - The tree 264 * - The desired object 265 * - Return a node that contains the given object, or NULL if no such object 266 * is found in the tree 267 */ 268 269 extern rb_node *rbtree_find(rb_tree *tree, datatype object); 270 271 /* Remove the object stored in the given tree node 272 * - The tree 273 * - The node storing the object to be removed from the tree 274 */ 275 276 extern void rbtree_remove_at(rb_tree *tree, rb_node *node, destructor d); 277 278 /* Left-rotate the sub-tree spanned by the given node 279 * - The tree 280 * - The sub-tree root 281 */ 282 283 extern void rbtree_rotate_left(rb_tree *tree, rb_node *node); 284 285 /* Right-rotate the sub-tree spanned by the given node 286 * - The tree 287 * - The sub-tree root 288 */ 289 290 extern void rbtree_rotate_right(rb_tree *tree, rb_node *node); 291 292 /* 293 * Fix the red-black tree properties after an insertion operation 294 * - The tree 295 * - The node that has just been inserted to the tree 296 * - The color of node must be red 297 */ 298 299 extern void rbtree_insert_fixup(rb_tree *tree, rb_node *node); 300 301 /* Fix the red-black tree properties after a removal operation 302 * - The tree 303 * - The child of the node that has just been removed from the tree 304 */ 305 306 extern void rbtree_remove_fixup(rb_tree *tree, rb_node *node); 307 308 /* Traverse a red-black tree 309 * - The tree 310 * - The operation to perform on every object of the tree (according to 311 * the tree order) 312 */ 313 314 extern void rbtree_traverse(rb_tree *tree, opr *op); 315 316 #endif 317