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