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