doc
c_rbtree.h
Go to the documentation of this file.
1 /*
2  * libcsync -- a library to sync a directory with another
3  *
4  * Copyright (c) 2003-2004 by Andrew Suffield <asuffield@debian.org>
5  * Copyright (c) 2007 by Andreas Schneider <mail@cynapses.org>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software Foundation,
19  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20  *
21  * vim: ft=c.doxygen ts=2 sw=2 et cindent
22  */
23 
24 /**
25  * @file c_rbtree.h
26  *
27  * @brief Interface of the cynapses libc red-black tree implementation
28  *
29  * A red-black tree is a type of self-balancing binary search tree. It is
30  * complex, but has good worst-case running time for its operations and is
31  * efficient in practice: it can search, insert, and delete in O(log n)
32  * time, where n is the number of elements in the tree.
33  *
34  * In red-black trees, the leaf nodes are not relevant and do not contain
35  * data. Therefore we use a sentinal node to save memory. All references
36  * from internal nodes to leaf nodes instead point to the sentinel node.
37  *
38  * In a red-black tree each node has a color attribute, the value of which
39  * is either red or black. In addition to the ordinary requirements imposed
40  * on binary search trees, the following additional requirements of any
41  * valid red-black tree apply:
42  *
43  * 1. A node is either red or black.
44  * 2. The root is black.
45  * 3. All leaves are black, even when the parent is black
46  * (The leaves are the null children.)
47  * 4. Both children of every red node are black.
48  * 5. Every simple path from a node to a descendant leaf contains the same
49  * number of black nodes, either counting or not counting the null black
50  * nodes. (Counting or not counting the null black nodes does not affect
51  * the structure as long as the choice is used consistently.).
52  *
53  * These constraints enforce a critical property of red-black trees: that the
54  * longest path from the root to a leaf is no more than twice as long as the
55  * shortest path from the root to a leaf in that tree. The result is that the
56  * tree is roughly balanced. Since operations such as inserting, deleting, and
57  * finding values requires worst-case time proportional to the height of the
58  * tree, this theoretical upper bound on the height allows red-black trees to
59  * be efficient in the worst-case, unlike ordinary binary search trees.
60  *
61  * http://en.wikipedia.org/wiki/Red-black_tree
62  *
63  * @defgroup cynRBTreeInternals cynapses libc red-black tree functions
64  * @ingroup cynLibraryAPI
65  *
66  * @{
67  */
68 #ifndef _C_RBTREE_H
69 #define _C_RBTREE_H
70 
71 /* Forward declarations */
72 struct c_rbtree_s; typedef struct c_rbtree_s c_rbtree_t;
73 struct c_rbnode_s; typedef struct c_rbnode_s c_rbnode_t;
74 
75 /**
76  * Define the two colors for the red-black tree
77  */
78 enum xrbcolor_e { BLACK = 0, RED }; typedef enum xrbcolor_e xrbcolor_t;
79 
80 /**
81  * @brief Callback function to compare a key with the data from a
82  * red-black tree node.
83  *
84  * @param key key as a generic pointer
85  * @param data data as a generic pointer
86  *
87  * @return It returns an integer less than, equal to, or greater than zero
88  * depending on the key or data you use. The function is similar
89  * to strcmp().
90  */
91 typedef int c_rbtree_compare_func(const void *key, const void *data);
92 
93 /**
94  * @brief Visit function for the c_rbtree_walk() function.
95  *
96  * This function will be called by c_rbtree_walk() for every node. It is up to
97  * the developer what the function does. The fist parameter is a node object
98  * the second can be of any kind.
99  *
100  * @param obj The node data that will be passed by c_rbtree_walk().
101  * @param data Generic data pointer.
102  *
103  * @return 0 on success, < 0 on error. You should set errno.
104  *
105  */
106 typedef int c_rbtree_visit_func(void *, void *);
107 
108 /**
109  * Structure that represents a red-black tree
110  */
111 struct c_rbtree_s {
115  size_t size;
116 };
117 
118 /**
119  * Structure that represents a node of a red-black tree
120  */
121 struct c_rbnode_s {
126  void *data;
128 };
129 
130 /**
131  * @brief Create the red-black tree
132  *
133  * @param rbtree The pointer to assign the allocated memory.
134  *
135  * @param key_compare Callback function to compare a key with the data
136  * inside a reb-black tree node.
137  *
138  * @param data_compare Callback function to compare a key as data with thee
139  * data inside a red-black tree node.
140  *
141  * @return 0 on success, -1 if an error occured with errno set.
142  */
143 int c_rbtree_create(c_rbtree_t **rbtree, c_rbtree_compare_func *key_compare, c_rbtree_compare_func *data_compare);
144 
145 /**
146  * @brief Duplicate a red-black tree.
147  *
148  * @param tree Tree to duplicate.
149  *
150  * @return Pointer to a new allocated duplicated rbtree. NULL if an error
151  * occured.
152  */
153 c_rbtree_t *c_rbtree_dup(const c_rbtree_t *tree);
154 
155 /**
156  * @brief Free the structure of a red-black tree.
157  *
158  * You should call c_rbtree_destroy() before you call this function.
159  *
160  * @param tree The tree to free.
161  *
162  * @return 0 on success, less than 0 if an error occured.
163  */
164 int c_rbtree_free(c_rbtree_t *tree);
165 
166 /**
167  * @brief Destroy the content and the nodes of an red-black tree.
168  *
169  * This is far from the most efficient way to walk a tree, but it is
170  * the *safest* way to destroy a tree - the destructor can do almost
171  * anything (as long as it does not create an infinite loop) to the
172  * tree structure without risk.
173  *
174  * If for some strange reason you need a faster destructor (think
175  * twice - speed and memory deallocation don't mix well) then consider
176  * stashing an llist of dataects and destroying that instead, and just
177  * using c_rbtree_free() on your tree.
178  *
179  * @param T The tree to destroy.
180  * @param DESTRUCTOR The destructor to call on a node to destroy.
181  */
182 #define c_rbtree_destroy(T, DESTRUCTOR) \
183  do { \
184  if (T) { \
185  c_rbnode_t *_c_rbtree_temp; \
186  while ((_c_rbtree_temp = c_rbtree_head(T))) { \
187  (DESTRUCTOR)(_c_rbtree_temp->data); \
188  if (_c_rbtree_temp == c_rbtree_head(T)) { \
189  c_rbtree_node_delete(_c_rbtree_temp); \
190  } \
191  } \
192  } \
193  SAFE_FREE(T); \
194  } while (0);
195 
196 /**
197  * @brief Inserts a node into a red black tree.
198  *
199  * @param tree The red black tree to insert the node.
200  * @param data The data to insert into the tree.
201  *
202  * @return 0 on success, 1 if a duplicate has been found and < 0 if an error
203  * occured with errno set.
204  * EINVAL if a null pointer has been passed as the tree.
205  * ENOMEM if there is no memory left.
206  */
207 int c_rbtree_insert(c_rbtree_t *tree, void *data);
208 
209 /**
210  * @brief Find a node in a red-black tree.
211  *
212  * c_rbtree_find() is searching for the given key in a red-black tree and
213  * returns the node if the key has been found.
214  *
215  * @param tree The tree to search.
216  * @param key The key to search for.
217  *
218  * @return If the key was found the node will be returned. On error NULL
219  * will be returned.
220  */
221 c_rbnode_t *c_rbtree_find(c_rbtree_t *tree, const void *key);
222 
223 /**
224  * @brief Get the head of the red-black tree.
225  *
226  * @param tree The tree to get the head for.
227  *
228  * @return The head node. NULL if an error occured.
229  */
231 
232 /**
233  * @brief Get the tail of the red-black tree.
234  *
235  * @param tree The tree to get the tail for.
236  *
237  * @return The tail node. NULL if an error occured.
238  */
240 
241 /**
242  * @brief Get the size of the red-black tree.
243  *
244  * @param T The tree to get the size from.
245  *
246  * @return The size of the red-black tree.
247  */
248 #define c_rbtree_size(T) (T) == NULL ? 0 : ((T)->size)
249 
250 /**
251  * @brief Walk over a red-black tree.
252  *
253  * Walk over a red-black tree calling a visitor function for each node found.
254  *
255  * @param tree Tree to walk.
256  * @param data Data which should be passed to the visitor function.
257  * @param visitor Visitor function. This will be called for each node passed.
258  *
259  * @return 0 on sucess, less than 0 if an error occured.
260  */
261 int c_rbtree_walk(c_rbtree_t *tree, void *data, c_rbtree_visit_func *visitor);
262 
263 /**
264  * @brief Delete a node in a red-black tree.
265  *
266  * @param node Node which should be deleted.
267  *
268  * @return 0 on success, -1 if an error occured.
269  */
271 
272 /**
273  * @brief Get the next node.
274  *
275  * @param node The node of which you want the next node.
276  *
277  * @return The next node, NULL if an error occured.
278  */
280 
281 /**
282  * @brief Get the previous node.
283  *
284  * @param node The node of which you want the previous node.
285  *
286  * @return The previous node, NULL if an error occured.
287  */
289 
290 /**
291  * @brief Get the data of a node.
292  *
293  * @param N The node to get the data from.
294  *
295  * @return The data, NULL if an error occured.
296  */
297 #define c_rbtree_node_data(N) ((N) ? ((N)->data) : NULL)
298 
299 /**
300  * @brief Perform a sanity check for a red-black tree.
301  *
302  * This is mostly for testing purposes.
303  *
304  * @param tree The tree to check.
305  *
306  * @return 0 on success, less than 0 if an error occured.
307  */
309 
310 /**
311  * }@
312  */
313 #endif /* _C_RBTREE_H */