diff options
Diffstat (limited to 'libraries/eina/src/include/eina_rbtree.h')
-rw-r--r-- | libraries/eina/src/include/eina_rbtree.h | 271 |
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 | */ | ||
62 | typedef enum { | ||
63 | EINA_RBTREE_RED, | ||
64 | EINA_RBTREE_BLACK | ||
65 | } Eina_Rbtree_Color; | ||
66 | |||
67 | /** | ||
68 | * @typedef Eina_Rbtree_Direction | ||
69 | * walk direction. | ||
70 | */ | ||
71 | typedef 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 | */ | ||
80 | typedef struct _Eina_Rbtree Eina_Rbtree; | ||
81 | struct _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 | */ | ||
120 | typedef 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 | */ | ||
132 | typedef 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 | */ | ||
143 | typedef 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 | */ | ||
164 | EAPI 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 | */ | ||
179 | EAPI 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 | */ | ||
189 | EAPI void eina_rbtree_delete(Eina_Rbtree *root, Eina_Rbtree_Free_Cb func, void *data) EINA_ARG_NONNULL(2); | ||
190 | |||
191 | static 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 | */ | ||
213 | EAPI 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 | */ | ||
234 | EAPI 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 | */ | ||
255 | EAPI 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 | ||