rbt.h

   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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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
  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