diff options
Diffstat (limited to 'libraries/eina/src/include/eina_inlist.h')
-rw-r--r-- | libraries/eina/src/include/eina_inlist.h | 813 |
1 files changed, 813 insertions, 0 deletions
diff --git a/libraries/eina/src/include/eina_inlist.h b/libraries/eina/src/include/eina_inlist.h new file mode 100644 index 0000000..1b3ab27 --- /dev/null +++ b/libraries/eina/src/include/eina_inlist.h | |||
@@ -0,0 +1,813 @@ | |||
1 | /* EINA - EFL data type library | ||
2 | * Copyright (C) 2002-2008 Carsten Haitzler, Vincent Torri | ||
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_INLIST_H_ | ||
20 | #define EINA_INLIST_H_ | ||
21 | |||
22 | #include "eina_types.h" | ||
23 | #include "eina_iterator.h" | ||
24 | #include "eina_accessor.h" | ||
25 | #include <stddef.h> | ||
26 | |||
27 | /** | ||
28 | * @page inlist_01_example_page Eina_Inlist basic usage | ||
29 | * @dontinclude eina_inlist_01.c | ||
30 | * | ||
31 | * To see the full source for this example, click here: @ref | ||
32 | * eina_inlist_01_c | ||
33 | * | ||
34 | * As explained before, inline lists mean its nodes pointers are part of same | ||
35 | * memory block/blob. This is done by using the macro @ref EINA_INLIST inside the | ||
36 | * data structure that will be used: | ||
37 | * | ||
38 | * @skip struct | ||
39 | * @until }; | ||
40 | * | ||
41 | * The resulting node representing this struct can be exemplified by the | ||
42 | * following picture: | ||
43 | * | ||
44 | * @image html eina_inlist-node_eg1-my-struct.png | ||
45 | * @image rtf eina_inlist-node_eg1-my-struct.png | ||
46 | * @image latex eina_inlist-node_eg1-my-struct.eps | ||
47 | * | ||
48 | * Let's define a comparison function that will be used later during the | ||
49 | * sorting of the list: | ||
50 | * | ||
51 | * @skip int | ||
52 | * @until } | ||
53 | * | ||
54 | * The @ref Eina_Inlist can be used exactly the same way as @ref Eina_List when | ||
55 | * appending, prepending and removing items. But since we already have the node | ||
56 | * pointers inside the structure, they need to be retrieved with the macro @ref | ||
57 | * EINA_INLIST_GET : | ||
58 | * | ||
59 | * @skip malloc | ||
60 | * @until append | ||
61 | * | ||
62 | * Notice that @ref eina_inlist_append always receives the head of the list as | ||
63 | * first argument, and its return value should be used as the list pointer | ||
64 | * (head): | ||
65 | * | ||
66 | * @skip malloc | ||
67 | * @until append | ||
68 | * | ||
69 | * After appending 3 items, the list now should look similar to this: | ||
70 | * | ||
71 | * @image html eina_inlist-node_eg1-inlist.png | ||
72 | * @image rtf eina_inlist-node_eg1-inlist.png | ||
73 | * @image latex eina_inlist-node_eg1-inlist.eps width=\textwidth | ||
74 | * | ||
75 | * The macro @ref EINA_INLIST_FOREACH can be used to iterate over the list: | ||
76 | * | ||
77 | * @skip printf | ||
78 | * @until cur->a | ||
79 | * | ||
80 | * @ref eina_inlist_promote(), @ref eina_inlist_demote(), @ref | ||
81 | * eina_inlist_append_relative() and similar functions all work in the same way | ||
82 | * as the @ref Eina_List : | ||
83 | * | ||
84 | * @skip eina_inlist_promote | ||
85 | * @until eina_inlist_demote | ||
86 | * | ||
87 | * Now let's use the @c sort_cb function declared above to sort our list: | ||
88 | * | ||
89 | * @skipline eina_inlist_sort | ||
90 | * | ||
91 | * Removing an element from the inlist is also similar to @ref Eina_List : | ||
92 | * | ||
93 | * @skip inlist_remove | ||
94 | * @until free | ||
95 | * | ||
96 | * Another way of walking through the inlist. | ||
97 | * | ||
98 | * @skip for | ||
99 | * @until } | ||
100 | * | ||
101 | * Notice that in the previous piece of code, since we only have the pointers to | ||
102 | * the inlist nodes, we have to use the @ref EINA_INLIST_CONTAINER_GET macro | ||
103 | * that will return the pointer to the entire structure. Of course, in this case | ||
104 | * it is the same as the list pointer, since the @ref EINA_INLIST macro was used | ||
105 | * in the beginning of the structure. | ||
106 | * | ||
107 | * Now to finish this example, lets delete this list: | ||
108 | * | ||
109 | * @skip while | ||
110 | * @until } | ||
111 | */ | ||
112 | |||
113 | /** | ||
114 | * @page inlist_02_example_page Eina_Inlist advanced usage - lists and inlists | ||
115 | * @dontinclude eina_inlist_02.c | ||
116 | * | ||
117 | * This example describes the usage of @ref Eina_Inlist mixed with @ref | ||
118 | * Eina_List . We create and add elements to an inlist, and the even members | ||
119 | * are also added to a normal list. Later we remove the elements divisible by 3 | ||
120 | * from this normal list. | ||
121 | * | ||
122 | * The struct that is going to be used is the same used in @ref | ||
123 | * inlist_01_example_page , since we still need the @ref EINA_INLIST macro to | ||
124 | * declare the inlist node info: | ||
125 | * | ||
126 | * @skip struct | ||
127 | * @until }; | ||
128 | * | ||
129 | * The resulting node representing this struct can be exemplified by the | ||
130 | * following picture: | ||
131 | * | ||
132 | * @image html eina_inlist-node_eg2-my-struct.png | ||
133 | * @image rtf eina_inlist-node_eg2-my-struct.png | ||
134 | * @image latex eina_inlist-node_eg2-my-struct.eps | ||
135 | * | ||
136 | * Now we need some pointers and auxiliar variables that will help us iterate on | ||
137 | * the lists: | ||
138 | * | ||
139 | * @skip struct | ||
140 | * @until l_next; | ||
141 | * | ||
142 | * Allocating 100 elements and putting them into an inlist, and the even | ||
143 | * elements also go to the normal list: | ||
144 | * | ||
145 | * @skip for | ||
146 | * @until } | ||
147 | * | ||
148 | * After this point, what we have are two distinct lists that share some | ||
149 | * elements. The first list (inlist) is defined by the pointers inside the | ||
150 | * elements data structure, while the second list (normal list) has its own node | ||
151 | * data structure that is kept outside of the elements. | ||
152 | * | ||
153 | * The two lists, sharing some elements, can be represented by the following | ||
154 | * picture: | ||
155 | * | ||
156 | * @htmlonly | ||
157 | * <img src="eina_inlist-node_eg2-list-inlist.png" style="max-width: 100%;"/> | ||
158 | * @endhtmlonly | ||
159 | * @image rtf eina_inlist-node_eg2-list-inlist.png | ||
160 | * @image latex eina_inlist-node_eg2-list-inlist.eps width=\textwidth | ||
161 | * | ||
162 | * Accessing both lists is done normally, as if they didn't have any elements in | ||
163 | * common: | ||
164 | * | ||
165 | * @skip printf | ||
166 | * @until eina_list_count | ||
167 | * | ||
168 | * We can remove elements from the normal list, but we just don't free them | ||
169 | * because they are still stored in the inlist: | ||
170 | * | ||
171 | * @skip EINA_LIST_FOREACH_SAFE | ||
172 | * @until eina_list_count | ||
173 | * | ||
174 | * To finish this example, we want to free both lists, we can't just free all | ||
175 | * elements on the second list (normal list) because they are still being used | ||
176 | * in the inlist. So we first discard the normal list without freeing its | ||
177 | * elements, then we free all elements in the inlist (that contains all elements | ||
178 | * allocated until now): | ||
179 | * | ||
180 | * @skip eina_list_free | ||
181 | * @until } | ||
182 | * | ||
183 | * Here is the full source code for this example: @ref eina_inlist_02_c | ||
184 | */ | ||
185 | |||
186 | /** | ||
187 | * @page inlist_03_example_page Eina_Inlist advanced usage - multi-inlists | ||
188 | * @dontinclude eina_inlist_03.c | ||
189 | * | ||
190 | * This example describes the usage of multiple inlists storing the same data. | ||
191 | * It means that some data may appear in more than one inlist at the same time. | ||
192 | * We will demonstrate this by creating an inlist with 100 numbers, and adding | ||
193 | * the odd numbers to the second inlist, then remove the numbers divisible by 3 | ||
194 | * from the second list. | ||
195 | * | ||
196 | * To accomplish this, it is necessary to have two inlist pointers in the struct | ||
197 | * that is going to be stored. We are using the default inlist member @ref | ||
198 | * EINA_INLIST, and adding another member @c even that is of type @ref | ||
199 | * Eina_Inlist too: | ||
200 | * | ||
201 | * @skip struct | ||
202 | * @until }; | ||
203 | * | ||
204 | * The representation for this struct is: | ||
205 | * | ||
206 | * @image html eina_inlist-node_eg3-my-struct.png | ||
207 | * @image rtf eina_inlist-node_eg3-my-struct.png | ||
208 | * @image latex eina_inlist-node_eg3-my-struct.eps | ||
209 | * | ||
210 | * And we will define some convenience macros that are equivalent to @ref | ||
211 | * EINA_INLIST_GET and @ref EINA_INLIST_CONTAINER_GET : | ||
212 | * | ||
213 | * @skip define | ||
214 | * @until offsetof | ||
215 | * | ||
216 | * We need two pointers, one for each list, and a pointer that will be used as | ||
217 | * an iterator: | ||
218 | * | ||
219 | * @skipline Eina_Inlist | ||
220 | * | ||
221 | * Now we allocate and add to the first list every number from 0 to 99. These | ||
222 | * nodes data also have the @ref Eina_Inlist node info for the second list (@c | ||
223 | * even). We will use them to add just the even numbers to the second list, the | ||
224 | * @c list_even. Also notice that we are using our macro @c EVEN_INLIST_GET to | ||
225 | * get the pointer to the even list node info: | ||
226 | * | ||
227 | * @skip for | ||
228 | * @until } | ||
229 | * | ||
230 | * And the resulting lists will be as follow: | ||
231 | * | ||
232 | * @htmlonly | ||
233 | * <img src="eina_inlist-node_eg3-two-inlists.png" style="max-width: 100%;"/> | ||
234 | * @endhtmlonly | ||
235 | * @image rtf eina_inlist-node_eg3-two-inlists.png | ||
236 | * @image latex eina_inlist-node_eg3-two-inlists.eps width=\textwidth | ||
237 | * | ||
238 | * For the first list, we can use the macro @ref EINA_INLIST_FOREACH to iterate | ||
239 | * over its elements: | ||
240 | * | ||
241 | * @skip FOREACH | ||
242 | * @until printf | ||
243 | * | ||
244 | * But for the second list, we have to do it manually. Of course we could create | ||
245 | * a similar macro to @ref EINA_INLIST_FOREACH, but since this macro is more | ||
246 | * complex than the other two and we are using it only once, it's better to just | ||
247 | * do it manually: | ||
248 | * | ||
249 | * @skip for | ||
250 | * @until } | ||
251 | * | ||
252 | * Let's just check that the two lists have the expected number of elements: | ||
253 | * | ||
254 | * @skip list count | ||
255 | * @until list_even count | ||
256 | * | ||
257 | * And removing the numbers divisible by 3 only from the second list: | ||
258 | * | ||
259 | * @skip itr | ||
260 | * @until list_even count | ||
261 | * | ||
262 | * Now that we don't need the two lists anymore, we can just free all the items. | ||
263 | * Since all of the allocated data was put into the first list, and both lists | ||
264 | * are made of pointers to inside the data structures, we can free only the | ||
265 | * first list (that contains all the elements) and the second list will be gone | ||
266 | * with it: | ||
267 | * | ||
268 | * @skip while | ||
269 | * @until free | ||
270 | * | ||
271 | * To see the full source code for this example, click here: @ref | ||
272 | * eina_inlist_03_c | ||
273 | * | ||
274 | */ | ||
275 | |||
276 | /** | ||
277 | * @page eina_inlist_01_c eina_inlist_01.c Eina_Inlist basic usage source | ||
278 | * @include eina_inlist_01.c | ||
279 | */ | ||
280 | |||
281 | /** | ||
282 | * @page eina_inlist_02_c eina_inlist_02.c Eina_Inlist advanced usage - lists and inlists source | ||
283 | * @include eina_inlist_02.c | ||
284 | */ | ||
285 | |||
286 | /** | ||
287 | * @page eina_inlist_03_c eina_inlist_03.c Eina_Inlist advanced usage - multi-inlists source | ||
288 | * @include eina_inlist_03.c | ||
289 | */ | ||
290 | |||
291 | /** | ||
292 | * @addtogroup Eina_Inline_List_Group Inline List | ||
293 | * | ||
294 | * @brief These functions provide inline list management. | ||
295 | * | ||
296 | * Inline lists mean its nodes pointers are part of same memory as | ||
297 | * data. This has the benefit of fragmenting memory less and avoiding | ||
298 | * @c node->data indirection, but has the drawback of higher cost for some | ||
299 | * common operations like count and sort. | ||
300 | * | ||
301 | * It is possible to have inlist nodes to be part of regular lists, created with | ||
302 | * @ref eina_list_append() or @ref eina_list_prepend(). It's also possible to | ||
303 | * have a structure with two inlist pointers, thus be part of two different | ||
304 | * inlists at the same time, but the current convenience macros provided won't | ||
305 | * work for both of them. Consult @ref inlist_advanced for more info. | ||
306 | * | ||
307 | * Inline lists have their purposes, but if you don't know what those purposes are, go with | ||
308 | * regular lists instead. | ||
309 | * | ||
310 | * Tip: When using inlists in more than one place (that is, passing them around | ||
311 | * functions or keeping a pointer to them in a structure) it's more correct | ||
312 | * to keep a pointer to the first container, and not a pointer to the first | ||
313 | * inlist item (mostly they are the same, but that's not always correct). | ||
314 | * This lets the compiler to do type checking and let the programmer know | ||
315 | * exactly what type this list is. | ||
316 | * | ||
317 | * A simple example demonstrating the basic usage of an inlist can be found | ||
318 | * here: @ref inlist_01_example_page | ||
319 | * | ||
320 | * @section inlist_algo Algorithm | ||
321 | * | ||
322 | * The basic structure can be represented by the following picture: | ||
323 | * | ||
324 | * @image html eina_inlist-node.png | ||
325 | * @image rtf eina_inlist-node.png | ||
326 | * @image latex eina_inlist-node.eps | ||
327 | * | ||
328 | * One data structure will also have the node information, with three pointers: | ||
329 | * @a prev, @a next and @a last. The @a last pointer is just valid for the first | ||
330 | * element (the list head), otherwise each insertion in the list would have to | ||
331 | * be done updating every node with the correct pointer. This means that it's | ||
332 | * always very important to keep a pointer to the first element of the list, | ||
333 | * since it is the only one that has the correct information to allow a proper | ||
334 | * O(1) append to the list. | ||
335 | * | ||
336 | * @section inlist_perf Performance | ||
337 | * | ||
338 | * Due to the nature of the inlist, there's no accounting information, and no | ||
339 | * easy access to the last element from each list node. This means that @ref | ||
340 | * eina_inlist_count() is order-N, while @ref eina_list_count() is order-1 (constant | ||
341 | * time). | ||
342 | * | ||
343 | * For the same reasons, @ref eina_inlist_sort() is slower than @ref | ||
344 | * eina_list_sort() . If the list is intended to have faster access, be | ||
345 | * sorted/merged frequently, or needs to have other complex operations, consider | ||
346 | * using @ref Eina_List instead. | ||
347 | * | ||
348 | * @section inlist_advanced Advanced Usage | ||
349 | * | ||
350 | * The basic usage considers a struct that will have the user data, and also | ||
351 | * have an inlist node information (prev, next and last pointers) created with | ||
352 | * @ref EINA_INLIST during the struct declaration. This allows one to use the | ||
353 | * convenience macros @ref EINA_INLIST_GET(), @ref EINA_INLIST_CONTAINER_GET(), | ||
354 | * @ref EINA_INLIST_FOREACH() and so. This happens because the @ref EINA_INLIST | ||
355 | * macro declares a struct member with the name @a __inlist, and all the other | ||
356 | * macros assume that this struct member has this name. | ||
357 | * | ||
358 | * It may be the case that someone needs to have some inlist nodes added to a | ||
359 | * @ref Eina_List too. If this happens, the inlist nodes can be added to the | ||
360 | * @ref Eina_List without any problems. This example demonstrates this case: | ||
361 | * @ref inlist_02_example_page | ||
362 | * | ||
363 | * It's also possible to have some data that is part of two different inlists. | ||
364 | * If this is the case, then it won't be possible to use the convenience macros | ||
365 | * to both of the lists. It will be necessary to create a new set of macros that | ||
366 | * will allow access to the second list node info. An example for this usage can | ||
367 | * be found here: | ||
368 | * @ref inlist_03_example_page | ||
369 | * | ||
370 | * List of examples: | ||
371 | * @li @ref inlist_01_example_page | ||
372 | * @li @ref inlist_02_example_page | ||
373 | * @li @ref inlist_03_example_page | ||
374 | */ | ||
375 | |||
376 | /** | ||
377 | * @addtogroup Eina_Data_Types_Group Data Types | ||
378 | * | ||
379 | * @{ | ||
380 | */ | ||
381 | |||
382 | /** | ||
383 | * @addtogroup Eina_Containers_Group Containers | ||
384 | * | ||
385 | * @{ | ||
386 | */ | ||
387 | |||
388 | /** | ||
389 | * @defgroup Eina_Inline_List_Group Inline List | ||
390 | * | ||
391 | * @{ | ||
392 | */ | ||
393 | |||
394 | /** | ||
395 | * @typedef Eina_Inlist | ||
396 | * Inlined list type. | ||
397 | */ | ||
398 | typedef struct _Eina_Inlist Eina_Inlist; | ||
399 | |||
400 | /** | ||
401 | * @typedef Eina_Inlist_Sorted_State | ||
402 | * @since 1.1.0 | ||
403 | * State of sorted Eina_Inlist | ||
404 | */ | ||
405 | typedef struct _Eina_Inlist_Sorted_State Eina_Inlist_Sorted_State; | ||
406 | |||
407 | /** | ||
408 | * @struct _Eina_Inlist | ||
409 | * Inlined list type. | ||
410 | */ | ||
411 | struct _Eina_Inlist | ||
412 | { | ||
413 | Eina_Inlist *next; /**< next node */ | ||
414 | Eina_Inlist *prev; /**< previous node */ | ||
415 | Eina_Inlist *last; /**< last node */ | ||
416 | }; | ||
417 | /** Used for declaring an inlist member in a struct */ | ||
418 | #define EINA_INLIST Eina_Inlist __in_list | ||
419 | /** Utility macro to get the inlist object of a struct */ | ||
420 | #define EINA_INLIST_GET(Inlist) (& ((Inlist)->__in_list)) | ||
421 | /** Utility macro to get the container object of an inlist */ | ||
422 | #define EINA_INLIST_CONTAINER_GET(ptr, \ | ||
423 | type) ((type *)((char *)ptr - \ | ||
424 | offsetof(type, __in_list))) | ||
425 | |||
426 | |||
427 | /** | ||
428 | * Add a new node to end of a list. | ||
429 | * | ||
430 | * @note this code is meant to be fast: appends are O(1) and do not | ||
431 | * walk @a list. | ||
432 | * | ||
433 | * @note @a new_l is considered to be in no list. If it was in another | ||
434 | * list before, eina_inlist_remove() it before adding. No | ||
435 | * check of @a new_l prev and next pointers is done, so it's safe | ||
436 | * to have them uninitialized. | ||
437 | * | ||
438 | * @param list existing list head or NULL to create a new list. | ||
439 | * @param new_l new list node, must not be NULL. | ||
440 | * | ||
441 | * @return the new list head. Use it and not @a list anymore. | ||
442 | */ | ||
443 | EAPI Eina_Inlist *eina_inlist_append(Eina_Inlist *in_list, | ||
444 | Eina_Inlist *in_item) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; | ||
445 | |||
446 | /** | ||
447 | * Add a new node to beginning of list. | ||
448 | * | ||
449 | * @note this code is meant to be fast: appends are O(1) and do not | ||
450 | * walk @a list. | ||
451 | * | ||
452 | * @note @a new_l is considered to be in no list. If it was in another | ||
453 | * list before, eina_inlist_remove() it before adding. No | ||
454 | * check of @a new_l prev and next pointers is done, so it's safe | ||
455 | * to have them uninitialized. | ||
456 | * | ||
457 | * @param list existing list head or NULL to create a new list. | ||
458 | * @param new_l new list node, must not be NULL. | ||
459 | * | ||
460 | * @return the new list head. Use it and not @a list anymore. | ||
461 | */ | ||
462 | EAPI Eina_Inlist *eina_inlist_prepend(Eina_Inlist *in_list, | ||
463 | Eina_Inlist *in_item) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; | ||
464 | |||
465 | /** | ||
466 | * Add a new node after the given relative item in list. | ||
467 | * | ||
468 | * @note this code is meant to be fast: appends are O(1) and do not | ||
469 | * walk @a list. | ||
470 | * | ||
471 | * @note @a new_l is considered to be in no list. If it was in another | ||
472 | * list before, eina_inlist_remove() it before adding. No | ||
473 | * check of @a new_l prev and next pointers is done, so it's safe | ||
474 | * to have them uninitialized. | ||
475 | * | ||
476 | * @note @a relative is considered to be inside @a list, no checks are | ||
477 | * done to confirm that and giving nodes from different lists | ||
478 | * will lead to problems. Giving NULL @a relative is the same as | ||
479 | * eina_list_append(). | ||
480 | * | ||
481 | * @param list existing list head or NULL to create a new list. | ||
482 | * @param new_l new list node, must not be NULL. | ||
483 | * @param relative reference node, @a new_l will be added after it. | ||
484 | * | ||
485 | * @return the new list head. Use it and not @a list anymore. | ||
486 | */ | ||
487 | EAPI Eina_Inlist *eina_inlist_append_relative(Eina_Inlist *in_list, | ||
488 | Eina_Inlist *in_item, | ||
489 | Eina_Inlist *in_relative) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; | ||
490 | |||
491 | /** | ||
492 | * Add a new node before the given relative item in list. | ||
493 | * | ||
494 | * @note this code is meant to be fast: appends are O(1) and do not | ||
495 | * walk @a list. | ||
496 | * | ||
497 | * @note @a new_l is considered to be in no list. If it was in another | ||
498 | * list before, eina_inlist_remove() it before adding. No | ||
499 | * check of @a new_l prev and next pointers is done, so it's safe | ||
500 | * to have them uninitialized. | ||
501 | * | ||
502 | * @note @a relative is considered to be inside @a list, no checks are | ||
503 | * done to confirm that and giving nodes from different lists | ||
504 | * will lead to problems. Giving NULL @a relative is the same as | ||
505 | * eina_list_prepend(). | ||
506 | * | ||
507 | * @param list existing list head or NULL to create a new list. | ||
508 | * @param new_l new list node, must not be NULL. | ||
509 | * @param relative reference node, @a new_l will be added before it. | ||
510 | * | ||
511 | * @return the new list head. Use it and not @a list anymore. | ||
512 | */ | ||
513 | EAPI Eina_Inlist *eina_inlist_prepend_relative(Eina_Inlist *in_list, | ||
514 | Eina_Inlist *in_item, | ||
515 | Eina_Inlist *in_relative) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; | ||
516 | |||
517 | /** | ||
518 | * Remove node from list. | ||
519 | * | ||
520 | * @note this code is meant to be fast: appends are O(1) and do not | ||
521 | * walk @a list. | ||
522 | * | ||
523 | * @note @a item is considered to be inside @a list, no checks are | ||
524 | * done to confirm that and giving nodes from different lists | ||
525 | * will lead to problems, especially if @a item is the head since | ||
526 | * it will be different from @a list and the wrong new head will | ||
527 | * be returned. | ||
528 | * | ||
529 | * @param list existing list head, must not be NULL. | ||
530 | * @param item existing list node, must not be NULL. | ||
531 | * | ||
532 | * @return the new list head. Use it and not @a list anymore. | ||
533 | */ | ||
534 | EAPI Eina_Inlist *eina_inlist_remove(Eina_Inlist *in_list, | ||
535 | Eina_Inlist *in_item) EINA_ARG_NONNULL(1, 2) EINA_WARN_UNUSED_RESULT; | ||
536 | |||
537 | /** | ||
538 | * Find given node in list, returns itself if found, NULL if not. | ||
539 | * | ||
540 | * @warning this is an expensive call and has O(n) cost, possibly | ||
541 | * walking the whole list. | ||
542 | * | ||
543 | * @param list existing list to search @a item in, must not be NULL. | ||
544 | * @param item what to search for, must not be NULL. | ||
545 | * | ||
546 | * @return @a item if found, NULL if not. | ||
547 | */ | ||
548 | EAPI Eina_Inlist *eina_inlist_find(Eina_Inlist *in_list, | ||
549 | Eina_Inlist *in_item) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; | ||
550 | |||
551 | /** | ||
552 | * Move existing node to beginning of list. | ||
553 | * | ||
554 | * @note this code is meant to be fast: appends are O(1) and do not | ||
555 | * walk @a list. | ||
556 | * | ||
557 | * @note @a item is considered to be inside @a list. No checks are | ||
558 | * done to confirm this, and giving nodes from different lists | ||
559 | * will lead to problems. | ||
560 | * | ||
561 | * @param list existing list head or NULL to create a new list. | ||
562 | * @param item list node to move to beginning (head), must not be NULL. | ||
563 | * | ||
564 | * @return the new list head. Use it and not @a list anymore. | ||
565 | */ | ||
566 | EAPI Eina_Inlist *eina_inlist_promote(Eina_Inlist *list, | ||
567 | Eina_Inlist *item) EINA_ARG_NONNULL(1, 2) EINA_WARN_UNUSED_RESULT; | ||
568 | |||
569 | /** | ||
570 | * Move existing node to end of list. | ||
571 | * | ||
572 | * @note this code is meant to be fast: appends are O(1) and do not | ||
573 | * walk @a list. | ||
574 | * | ||
575 | * @note @a item is considered to be inside @a list. No checks are | ||
576 | * done to confirm this, and giving nodes from different lists | ||
577 | * will lead to problems. | ||
578 | * | ||
579 | * @param list existing list head or NULL to create a new list. | ||
580 | * @param item list node to move to end (tail), must not be NULL. | ||
581 | * | ||
582 | * @return the new list head. Use it and not @a list anymore. | ||
583 | */ | ||
584 | EAPI Eina_Inlist *eina_inlist_demote(Eina_Inlist *list, | ||
585 | Eina_Inlist *item) EINA_ARG_NONNULL(1, 2) EINA_WARN_UNUSED_RESULT; | ||
586 | |||
587 | /** | ||
588 | * @brief Get the count of the number of items in a list. | ||
589 | * | ||
590 | * @param list The list whose count to return. | ||
591 | * @return The number of members in the list. | ||
592 | * | ||
593 | * This function returns how many members @p list contains. If the | ||
594 | * list is @c NULL, 0 is returned. | ||
595 | * | ||
596 | * @warning This is an order-N operation and so the time will depend | ||
597 | * on the number of elements on the list, so, it might become | ||
598 | * slow for big lists! | ||
599 | */ | ||
600 | EAPI unsigned int eina_inlist_count(const Eina_Inlist *list) EINA_WARN_UNUSED_RESULT; | ||
601 | |||
602 | |||
603 | /** | ||
604 | * @brief Returns a new iterator associated to @a list. | ||
605 | * | ||
606 | * @param list The list. | ||
607 | * @return A new iterator. | ||
608 | * | ||
609 | * This function returns a newly allocated iterator associated to @p | ||
610 | * list. If @p list is @c NULL or the count member of @p list is less | ||
611 | * or equal than 0, this function still returns a valid iterator that | ||
612 | * will always return false on eina_iterator_next(), thus keeping API | ||
613 | * sane. | ||
614 | * | ||
615 | * If the memory can not be allocated, NULL is returned and | ||
616 | * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is | ||
617 | * returned. | ||
618 | * | ||
619 | * @warning if the list structure changes then the iterator becomes | ||
620 | * invalid, and if you add or remove nodes iterator | ||
621 | * behavior is undefined, and your program may crash! | ||
622 | */ | ||
623 | EAPI Eina_Iterator *eina_inlist_iterator_new(const Eina_Inlist *in_list) EINA_MALLOC EINA_WARN_UNUSED_RESULT; | ||
624 | |||
625 | /** | ||
626 | * @brief Returns a new accessor associated to a list. | ||
627 | * | ||
628 | * @param list The list. | ||
629 | * @return A new accessor. | ||
630 | * | ||
631 | * This function returns a newly allocated accessor associated to | ||
632 | * @p list. If @p list is @c NULL or the count member of @p list is | ||
633 | * less or equal than 0, this function returns NULL. If the memory can | ||
634 | * not be allocated, NULL is returned and #EINA_ERROR_OUT_OF_MEMORY is | ||
635 | * set. Otherwise, a valid accessor is returned. | ||
636 | */ | ||
637 | EAPI Eina_Accessor *eina_inlist_accessor_new(const Eina_Inlist *in_list) EINA_MALLOC EINA_WARN_UNUSED_RESULT; | ||
638 | |||
639 | /** | ||
640 | * @brief Insert a new node into a sorted list. | ||
641 | * | ||
642 | * @param list The given linked list, @b must be sorted. | ||
643 | * @param item list node to insert, must not be NULL. | ||
644 | * @param func The function called for the sort. | ||
645 | * @return A list pointer. | ||
646 | * @since 1.1.0 | ||
647 | * | ||
648 | * This function inserts item into a linked list assuming it was | ||
649 | * sorted and the result will be sorted. If @p list is @c NULLL, item | ||
650 | * is returned. On success, a new list pointer that should be | ||
651 | * used in place of the one given to this function is | ||
652 | * returned. Otherwise, the old pointer is returned. See eina_error_get(). | ||
653 | * | ||
654 | * @note O(log2(n)) comparisons (calls to @p func) average/worst case | ||
655 | * performance. As said in eina_list_search_sorted_near_list(), | ||
656 | * lists do not have O(1) access time, so walking to the correct node | ||
657 | * can be costly, consider worst case to be almost O(n) pointer | ||
658 | * dereference (list walk). | ||
659 | */ | ||
660 | EAPI Eina_Inlist *eina_inlist_sorted_insert(Eina_Inlist *list, Eina_Inlist *item, Eina_Compare_Cb func) EINA_ARG_NONNULL(2, 3) EINA_WARN_UNUSED_RESULT; | ||
661 | |||
662 | /** | ||
663 | * @brief Create state with valid data in it. | ||
664 | * | ||
665 | * @return A valid Eina_Inlist_Sorted_State. | ||
666 | * @since 1.1.0 | ||
667 | * | ||
668 | * See eina_inlist_sorted_state_insert() for more information. | ||
669 | */ | ||
670 | EAPI Eina_Inlist_Sorted_State *eina_inlist_sorted_state_new(void); | ||
671 | |||
672 | /** | ||
673 | * @brief Force an Eina_Inlist_Sorted_State to match the content of a list. | ||
674 | * | ||
675 | * @param state The state to update | ||
676 | * @param list The list to match | ||
677 | * @return The number of item in the actually in the list | ||
678 | * @since 1.1.0 | ||
679 | * | ||
680 | * See eina_inlist_sorted_state_insert() for more information. This function is | ||
681 | * usefull if you didn't use eina_inlist_sorted_state_insert() at some point, but | ||
682 | * still think you have a sorted list. It will only correctly work on a sorted list. | ||
683 | */ | ||
684 | EAPI int eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list); | ||
685 | |||
686 | /** | ||
687 | * @brief Free an Eina_Inlist_Sorted_State. | ||
688 | * | ||
689 | * @param state The state to destroy | ||
690 | * @since 1.1.0 | ||
691 | * | ||
692 | * See eina_inlist_sorted_state_insert() for more information. | ||
693 | */ | ||
694 | EAPI void eina_inlist_sorted_state_free(Eina_Inlist_Sorted_State *state); | ||
695 | |||
696 | /** | ||
697 | * @brief Insert a new node into a sorted list. | ||
698 | * | ||
699 | * @param list The given linked list, @b must be sorted. | ||
700 | * @param item list node to insert, must not be NULL. | ||
701 | * @param func The function called for the sort. | ||
702 | * @param state The current array for initial dichotomic search | ||
703 | * @return A list pointer. | ||
704 | * @since 1.1.0 | ||
705 | * | ||
706 | * This function inserts item into a linked list assuming @p state match | ||
707 | * the exact content order of the list. It use @p state to do a fast | ||
708 | * first step dichotomic search before starting to walk the inlist itself. | ||
709 | * This make this code much faster than eina_inlist_sorted_insert() as it | ||
710 | * doesn't need to walk the list at all. The result is of course a sorted | ||
711 | * list with an updated state.. If @p list is @c NULLL, item | ||
712 | * is returned. On success, a new list pointer that should be | ||
713 | * used in place of the one given to this function is | ||
714 | * returned. Otherwise, the old pointer is returned. See eina_error_get(). | ||
715 | * | ||
716 | * @note O(log2(n)) comparisons (calls to @p func) average/worst case | ||
717 | * performance. As said in eina_list_search_sorted_near_list(), | ||
718 | * lists do not have O(1) access time, so walking to the correct node | ||
719 | * can be costly, but this version try to minimize that by making it a | ||
720 | * O(log2(n)) for number small number. After n == 256, it start to add a | ||
721 | * linear cost again. Consider worst case to be almost O(n) pointer | ||
722 | * dereference (list walk). | ||
723 | */ | ||
724 | EAPI Eina_Inlist *eina_inlist_sorted_state_insert(Eina_Inlist *list, | ||
725 | Eina_Inlist *item, | ||
726 | Eina_Compare_Cb func, | ||
727 | Eina_Inlist_Sorted_State *state); | ||
728 | /** | ||
729 | * @brief Sort a list according to the ordering func will return. | ||
730 | * | ||
731 | * @param list The list handle to sort. | ||
732 | * @param func A function pointer that can handle comparing the list data | ||
733 | * nodes. | ||
734 | * @return the new head of list. | ||
735 | * | ||
736 | * This function sorts all the elements of @p list. @p func is used to | ||
737 | * compare two elements of @p list. If @p list or @p func are @c NULL, | ||
738 | * this function returns @c NULL. | ||
739 | * | ||
740 | * @note @b in-place: this will change the given list, so you should | ||
741 | * now point to the new list head that is returned by this function. | ||
742 | * | ||
743 | * @note worst case is O(n * log2(n)) comparisons (calls to func()), | ||
744 | * O(n) comparisons average case. That means that for 1,000,000 list | ||
745 | * elements, sort will usually do 1,000,000 comparisons, but may do up | ||
746 | * to 20,000,000. | ||
747 | * | ||
748 | * Example: | ||
749 | * @code | ||
750 | * typedef struct _Sort_Ex Sort_Ex; | ||
751 | * struct _Sort_Ex | ||
752 | * { | ||
753 | * INLIST; | ||
754 | * const char *text; | ||
755 | * }; | ||
756 | * | ||
757 | * int | ||
758 | * sort_cb(const Inlist *l1, const Inlist *l2) | ||
759 | * { | ||
760 | * const Sort_Ex *x1; | ||
761 | * const Sort_Ex *x2; | ||
762 | * | ||
763 | * x1 = EINA_INLIST_CONTAINER_GET(l1, Sort_Ex); | ||
764 | * x2 = EINA_INLIST_CONTAINER_GET(l2, Sort_Ex); | ||
765 | * | ||
766 | * return(strcmp(x1->text, x2->text)); | ||
767 | * } | ||
768 | * extern Eina_Inlist *list; | ||
769 | * | ||
770 | * list = eina_inlist_sort(list, sort_cb); | ||
771 | * @endcode | ||
772 | */ | ||
773 | EAPI Eina_Inlist *eina_inlist_sort(Eina_Inlist *head, Eina_Compare_Cb func); | ||
774 | |||
775 | /* This two macros are helpers for the _FOREACH ones, don't use them */ | ||
776 | #define _EINA_INLIST_OFFSET(ref) ((char *)&(ref)->__in_list - (char *)(ref)) | ||
777 | |||
778 | #if !defined(__cplusplus) | ||
779 | #define _EINA_INLIST_CONTAINER(ref, ptr) (void *)((char *)(ptr) - \ | ||
780 | _EINA_INLIST_OFFSET(ref)) | ||
781 | #else | ||
782 | /* | ||
783 | * In C++ we can't assign a "type*" pointer to void* so we rely on GCC's typeof | ||
784 | * operator. | ||
785 | */ | ||
786 | #define _EINA_INLIST_CONTAINER(ref, ptr) (typeof(ref))((char *)(ptr) - \ | ||
787 | _EINA_INLIST_OFFSET(ref)) | ||
788 | #endif | ||
789 | |||
790 | #define EINA_INLIST_FOREACH(list, l) \ | ||
791 | for (l = NULL, l = (list ? _EINA_INLIST_CONTAINER(l, list) : NULL); l; \ | ||
792 | l = (EINA_INLIST_GET(l)->next ? _EINA_INLIST_CONTAINER(l, EINA_INLIST_GET(l)->next) : NULL)) | ||
793 | #define EINA_INLIST_FOREACH_SAFE(list, list2, l) \ | ||
794 | for (l = (list ? _EINA_INLIST_CONTAINER(l, list) : NULL), list2 = l ? ((EINA_INLIST_GET(l) ? EINA_INLIST_GET(l)->next : NULL)) : NULL; \ | ||
795 | l; \ | ||
796 | l = _EINA_INLIST_CONTAINER(l, list2), list2 = list2 ? list2->next : NULL) | ||
797 | #define EINA_INLIST_REVERSE_FOREACH(list, l) \ | ||
798 | for (l = NULL, l = (list ? _EINA_INLIST_CONTAINER(l, list->last) : NULL); \ | ||
799 | l; l = (EINA_INLIST_GET(l)->prev ? _EINA_INLIST_CONTAINER(l, EINA_INLIST_GET(l)->prev) : NULL)) | ||
800 | |||
801 | /** | ||
802 | * @} | ||
803 | */ | ||
804 | |||
805 | /** | ||
806 | * @} | ||
807 | */ | ||
808 | |||
809 | /** | ||
810 | * @} | ||
811 | */ | ||
812 | |||
813 | #endif /*EINA_INLIST_H_*/ | ||