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 recieves 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 58typedef struct ffsb_file *datatype; 59 60#define COMP_NODES(a, b) ((a)->num - (b)->num) 61 62typedef enum red_black_color {red, black} rb_color; 63 64/*! Representation of a node in a red-black tree */ 65typedef 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 73typedef int(cmp)(datatype, datatype); 74typedef void(opr)(void *); 75typedef 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 82extern rb_node *rbnode_construct(datatype object, rb_color color); 83 84/* Recursive destructor for the entire sub-tree */ 85/* ******************************************** */ 86 87extern 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 94extern 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 101extern 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 108extern rb_node *rbnode_maximum(rb_node *node); 109 110/* Replace the object */ 111/* ****************** */ 112 113extern 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 120extern 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 127extern 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 134extern 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 */ 140extern void rbnode_traverse(rb_node *node, opr *op); 141 142/* Representation of a red-black tree */ 143/* ********************************** */ 144 145typedef 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 156void 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 163rb_tree *rbtree_construct(void); 164 165/* Clean a red-black tree [takes O(n) operations] 166 * - The tree 167 */ 168 169extern void rbtree_clean(rb_tree *tree, destructor d); 170 171/* Destruct a red-black tree 172 * - The tree 173 */ 174 175extern 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 182extern 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 189extern 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 197extern 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 205extern 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 212extern 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 220extern 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 229extern 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 236extern 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 243extern 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 */ 251extern 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 260extern 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 269extern 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 276extern 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 283extern 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 290extern 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 299extern 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 306extern 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 314extern void rbtree_traverse(rb_tree *tree, opr *op); 315 316#endif 317