aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/eina/src/include/eina_rbtree.h
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/eina/src/include/eina_rbtree.h')
-rw-r--r--libraries/eina/src/include/eina_rbtree.h271
1 files changed, 0 insertions, 271 deletions
diff --git a/libraries/eina/src/include/eina_rbtree.h b/libraries/eina/src/include/eina_rbtree.h
deleted file mode 100644
index 8e5b730..0000000
--- a/libraries/eina/src/include/eina_rbtree.h
+++ /dev/null
@@ -1,271 +0,0 @@
1/* EINA - EFL data type library
2 * Copyright (C) 2008 Cedric Bail
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library 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 the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library;
16 * if not, see <http://www.gnu.org/licenses/>.
17 */
18
19#ifndef EINA_RBTREE_H__
20#define EINA_RBTREE_H__
21
22#include <stdlib.h>
23
24#include "eina_types.h"
25#include "eina_error.h"
26#include "eina_iterator.h"
27
28/**
29 * @addtogroup Eina_Rbtree_Group Red-Black tree
30 *
31 * @brief These functions provide Red-Black trees management.
32 *
33 * For a brief description look at http://en.wikipedia.org/wiki/Red-black_tree .
34 * This code is largely inspired from a tutorial written by Julienne Walker at :
35 * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx . The
36 * main difference is that this set of function never allocate any data, making
37 * them particularly useful for memory management.
38 */
39
40/**
41 * @addtogroup Eina_Data_Types_Group Data Types
42 *
43 * @{
44 */
45
46/**
47 * @addtogroup Eina_Containers_Group Containers
48 *
49 * @{
50 */
51
52/**
53 * @defgroup Eina_Rbtree_Group Red-Black tree
54 *
55 * @{
56 */
57
58/**
59 * @typedef Eina_Rbtree_Color
60 * node color.
61 */
62typedef enum {
63 EINA_RBTREE_RED,
64 EINA_RBTREE_BLACK
65} Eina_Rbtree_Color;
66
67/**
68 * @typedef Eina_Rbtree_Direction
69 * walk direction.
70 */
71typedef enum {
72 EINA_RBTREE_LEFT = 0,
73 EINA_RBTREE_RIGHT = 1
74} Eina_Rbtree_Direction;
75
76/**
77 * @typedef Eina_Rbtree
78 * Type for a Red-Black tree node. It should be inlined into user's type.
79 */
80typedef struct _Eina_Rbtree Eina_Rbtree;
81struct _Eina_Rbtree
82{
83 Eina_Rbtree *son[2];
84
85 Eina_Rbtree_Color color : 1;
86};
87
88/**
89 * @def EINA_RBTREE
90 * recommended way to declare the inlined Eina_Rbtree in your type.
91 *
92 * @code
93 * struct my_type {
94 * EINA_RBTREE;
95 * int my_value;
96 * char *my_name;
97 * };
98 * @endcode
99 *
100 * @see EINA_RBTREE_GET()
101 */
102#define EINA_RBTREE Eina_Rbtree __rbtree
103
104/**
105 * @def EINA_RBTREE_GET
106 * access the inlined node if it was created with #EINA_RBTREE.
107 */
108#define EINA_RBTREE_GET(Rbtree) (&((Rbtree)->__rbtree))
109
110/**
111 * @def EINA_RBTREE_CONTAINER_GET
112 * find back the container of an red black tree.
113 */
114#define EINA_RBTREE_CONTAINER_GET(Ptr, Type) ((Type *)((char *)Ptr - offsetof(Type, __rbtree)))
115
116/**
117 * @typedef Eina_Rbtree_Cmp_Node_Cb
118 * Function used compare two nodes and see which direction to navigate.
119 */
120typedef Eina_Rbtree_Direction (*Eina_Rbtree_Cmp_Node_Cb)(const Eina_Rbtree *left, const Eina_Rbtree *right, void *data);
121
122/**
123 * @def EINA_RBTREE_CMP_NODE_CB
124 * Cast using #Eina_Rbtree_Cmp_Node_Cb
125 */
126#define EINA_RBTREE_CMP_NODE_CB(Function) ((Eina_Rbtree_Cmp_Node_Cb)Function)
127
128/**
129 * @typedef Eina_Rbtree_Cmp_Key_Cb
130 * Function used compare node with a given key of specified length.
131 */
132typedef int (*Eina_Rbtree_Cmp_Key_Cb)(const Eina_Rbtree *node, const void *key, int length, void *data);
133/**
134 * @def EINA_RBTREE_CMP_KEY_CB
135 * Cast using #Eina_Rbtree_Cmp_Key_Cb
136 */
137#define EINA_RBTREE_CMP_KEY_CB(Function) ((Eina_Rbtree_Cmp_Key_Cb)Function)
138
139/**
140 * @typedef Eina_Rbtree_Free_Cb
141 * Function used free a node.
142 */
143typedef void (*Eina_Rbtree_Free_Cb)(Eina_Rbtree *node, void *data);
144/**
145 * @def EINA_RBTREE_FREE_CB
146 * Cast using #Eina_Rbtree_Free_Cb
147 */
148#define EINA_RBTREE_FREE_CB(Function) ((Eina_Rbtree_Free_Cb)Function)
149
150
151/**
152 * @brief Insert a new node inside an existing red black tree.
153 *
154 * @param root The root of an exisiting valid red black tree.
155 * @param node The new node to insert.
156 * @param cmp The callback that is able to compare two nodes.
157 * @param data Private data to help the compare function.
158 * @return The new root of the red black tree.
159 *
160 * This function insert a new node in a valid red black tree. NULL is
161 * an empty valid red black tree. The resulting new tree is a valid red
162 * black tree. This function doesn't allocate any data.
163 */
164EAPI Eina_Rbtree *eina_rbtree_inline_insert(Eina_Rbtree *root, Eina_Rbtree *node, Eina_Rbtree_Cmp_Node_Cb cmp, const void *data) EINA_ARG_NONNULL(2, 3) EINA_WARN_UNUSED_RESULT;
165
166/**
167 * @brief Remove a node from an existing red black tree.
168 *
169 * @param root The root of a valid red black tree.
170 * @param node The node to remove from the tree.
171 * @param cmp The callback that is able to compare two nodes.
172 * @param data Private data to help the compare function.
173 * @return The new root of the red black tree.
174 *
175 * This function remove a new node in a valid red black tree that should
176 * contain the node that you are removing. This function will return NULL
177 * when the red black tree got empty. This function doesn't free any data.
178 */
179EAPI Eina_Rbtree *eina_rbtree_inline_remove(Eina_Rbtree *root, Eina_Rbtree *node, Eina_Rbtree_Cmp_Node_Cb cmp, const void *data) EINA_ARG_NONNULL(2, 3) EINA_WARN_UNUSED_RESULT;
180
181/**
182 * @brief Delete all nodes from a valid red black tree.
183 *
184 * @param root The root of a valid red black tree.
185 * @param func The callback that will free each node.
186 * @param data Private data to help the compare function.
187 *
188 */
189EAPI void eina_rbtree_delete(Eina_Rbtree *root, Eina_Rbtree_Free_Cb func, void *data) EINA_ARG_NONNULL(2);
190
191static inline Eina_Rbtree *eina_rbtree_inline_lookup(const Eina_Rbtree *root, const void *key, int length, Eina_Rbtree_Cmp_Key_Cb cmp, const void *data) EINA_PURE EINA_ARG_NONNULL(2, 4) EINA_WARN_UNUSED_RESULT;
192
193
194/**
195 * @brief Returned a new prefix iterator associated to a rbtree.
196 *
197 * @param root The root of rbtree.
198 * @return A new iterator.
199 *
200 * This function returns a newly allocated iterator associated to @p
201 * root. It will iterate the tree using prefix walk. If @p root is @c
202 * NULL, this function still returns a valid iterator that will always
203 * return false on eina_iterator_next(), thus keeping API sane.
204 *
205 * If the memory can not be allocated, NULL is returned and
206 * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
207 * returned.
208 *
209 * @warning if the rbtree structure changes then the iterator becomes
210 * invalid! That is, if you add or remove nodes this iterator
211 * behavior is undefined and your program may crash!
212 */
213EAPI Eina_Iterator *eina_rbtree_iterator_prefix(const Eina_Rbtree *root) EINA_MALLOC EINA_WARN_UNUSED_RESULT;
214
215/**
216 * @brief Returned a new prefix iterator associated to a rbtree.
217 *
218 * @param root The root of rbtree.
219 * @return A new iterator.
220 *
221 * This function returns a newly allocated iterator associated to @p
222 * root. It will iterate the tree using infix walk. If @p root is @c
223 * NULL, this function still returns a valid iterator that will always
224 * return false on eina_iterator_next(), thus keeping API sane.
225 *
226 * If the memory can not be allocated, NULL is returned and
227 * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
228 * returned.
229 *
230 * @warning if the rbtree structure changes then the iterator becomes
231 * invalid! That is, if you add or remove nodes this iterator
232 * behavior is undefined and your program may crash!
233 */
234EAPI Eina_Iterator *eina_rbtree_iterator_infix(const Eina_Rbtree *root) EINA_MALLOC EINA_WARN_UNUSED_RESULT;
235
236/**
237 * @brief Returned a new prefix iterator associated to a rbtree.
238 *
239 * @param root The root of rbtree.
240 * @return A new iterator.
241 *
242 * This function returns a newly allocated iterator associated to @p
243 * root. It will iterate the tree using postfix walk. If @p root is @c
244 * NULL, this function still returns a valid iterator that will always
245 * return false on eina_iterator_next(), thus keeping API sane.
246 *
247 * If the memory can not be allocated, NULL is returned and
248 * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
249 * returned.
250 *
251 * @warning if the rbtree structure changes then the iterator becomes
252 * invalid! That is, if you add or remove nodes this iterator
253 * behavior is undefined and your program may crash!
254 */
255EAPI Eina_Iterator *eina_rbtree_iterator_postfix(const Eina_Rbtree *root) EINA_MALLOC EINA_WARN_UNUSED_RESULT;
256
257#include "eina_inline_rbtree.x"
258
259/**
260 * @}
261 */
262
263/**
264 * @}
265 */
266
267/**
268 * @}
269 */
270
271#endif
generated by cgit v1.1 at 2024-08-27 20:40:03 +0000