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 */
70struct c_rbtree_s; typedef struct c_rbtree_s c_rbtree_t;
71struct c_rbnode_s; typedef struct c_rbnode_s c_rbnode_t;
72
73/**
74 * Define the two colors for the red-black tree
75 */
76enum 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 */
89typedef 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 */
104typedef int c_rbtree_visit_func(void *, void *);
105
106/**
107 * Structure that represents a red-black tree
108 */
115
116/**
117 * Structure that represents a node of a red-black tree
118 */
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 */
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 */
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 */
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 */
205int 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 */
219c_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 */
259int 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 */
int c_rbtree_insert(c_rbtree_t *tree, void *data)
Inserts a node into a red black tree.
size_t size
Definition c_rbtree.h:113
c_rbnode_t * c_rbtree_head(c_rbtree_t *tree)
Get the head of the red-black tree.
c_rbtree_t * tree
Definition c_rbtree.h:120
c_rbnode_t * c_rbtree_find(c_rbtree_t *tree, const void *key)
Find a node in a red-black tree.
c_rbtree_compare_func * data_compare
Definition c_rbtree.h:112
c_rbnode_t * right
Definition c_rbtree.h:122
xrbcolor_e
Define the two colors for the red-black tree.
Definition c_rbtree.h:76
c_rbnode_t * parent
Definition c_rbtree.h:123
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.
xrbcolor_t color
Definition c_rbtree.h:125
enum xrbcolor_e xrbcolor_t
Definition c_rbtree.h:76
int c_rbtree_node_delete(c_rbnode_t *node)
Delete a node in a red-black tree.
c_rbnode_t * left
Definition c_rbtree.h:121
c_rbnode_t * c_rbtree_tail(c_rbtree_t *tree)
Get the tail of the 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
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_node_prev(c_rbnode_t *node)
Get the previous node.
int c_rbtree_free(c_rbtree_t *tree)
Free the structure of a red-black tree.
c_rbtree_compare_func * key_compare
Definition c_rbtree.h:111
c_rbnode_t * c_rbtree_node_next(c_rbnode_t *node)
Get the next node.
int c_rbtree_walk(c_rbtree_t *tree, void *data, c_rbtree_visit_func *visitor)
Walk over 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.
void * data
Definition c_rbtree.h:124
c_rbnode_t * root
Definition c_rbtree.h:110
@ BLACK
Definition c_rbtree.h:76
@ RED
Definition c_rbtree.h:76
Structure that represents a node of a red-black tree.
Definition c_rbtree.h:119
Structure that represents a red-black tree.
Definition c_rbtree.h:109