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 eina_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  * @example eina_inlist_01.c
112  */
113 
114 /**
115  * @page eina_inlist_02_example_page Eina_Inlist advanced usage - lists and inlists
116  * @dontinclude eina_inlist_02.c
117  *
118  * This example describes the usage of @ref Eina_Inlist mixed with @ref
119  * Eina_List . We create and add elements to an inlist, and the even members
120  * are also added to a normal list. Later we remove the elements divisible by 3
121  * from this normal list.
122  *
123  * The struct that is going to be used is the same used in @ref
124  * eina_inlist_01_example_page , since we still need the @ref EINA_INLIST macro to
125  * declare the inlist node info:
126  *
127  * @skip struct
128  * @until };
129  *
130  * The resulting node representing this struct can be exemplified by the
131  * following picture:
132  *
133  * @image html eina_inlist-node_eg2-my-struct.png
134  * @image rtf eina_inlist-node_eg2-my-struct.png
135  * @image latex eina_inlist-node_eg2-my-struct.eps
136  *
137  * Now we need some pointers and auxiliary variables that will help us iterate on
138  * the lists:
139  *
140  * @skip struct
141  * @until l_next;
142  *
143  * Allocating 100 elements and putting them into an inlist, and the even
144  * elements also go to the normal list:
145  *
146  * @skip for
147  * @until }
148  *
149  * After this point, what we have are two distinct lists that share some
150  * elements. The first list (inlist) is defined by the pointers inside the
151  * elements data structure, while the second list (normal list) has its own node
152  * data structure that is kept outside of the elements.
153  *
154  * The two lists, sharing some elements, can be represented by the following
155  * picture:
156  *
157  * @image rtf eina_inlist-node_eg2-list-inlist.png
158  * @image html eina_inlist-node_eg2-list-inlist.png
159  * @image latex eina_inlist-node_eg2-list-inlist.eps "" width=\textwidth
160  *
161  * Accessing both lists is done normally, as if they didn't have any elements in
162  * common:
163  *
164  * @skip printf
165  * @until eina_list_count
166  *
167  * We can remove elements from the normal list, but we just don't free them
168  * because they are still stored in the inlist:
169  *
170  * @skip EINA_LIST_FOREACH_SAFE
171  * @until eina_list_count
172  *
173  * To finish this example, we want to free both lists, we can't just free all
174  * elements on the second list (normal list) because they are still being used
175  * in the inlist. So we first discard the normal list without freeing its
176  * elements, then we free all elements in the inlist (that contains all elements
177  * allocated until now):
178  *
179  * @skip eina_list_free
180  * @until }
181  *
182  * Here is the full source code for this example: @ref eina_inlist_02_c
183  * @example eina_inlist_02.c
184  */
185 
186 /**
187  * @page eina_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  * @image rtf eina_inlist-node_eg3-two-inlists.png
233  * @image html eina_inlist-node_eg3-two-inlists.png
234  * @image latex eina_inlist-node_eg3-two-inlists.eps "" width=\textwidth
235  *
236  * For the first list, we can use the macro @ref EINA_INLIST_FOREACH to iterate
237  * over its elements:
238  *
239  * @skip FOREACH
240  * @until printf
241  *
242  * But for the second list, we have to do it manually. Of course we could create
243  * a similar macro to @ref EINA_INLIST_FOREACH, but since this macro is more
244  * complex than the other two and we are using it only once, it's better to just
245  * do it manually:
246  *
247  * @skip for
248  * @until }
249  *
250  * Let's just check that the two lists have the expected number of elements:
251  *
252  * @skip list count
253  * @until list_even count
254  *
255  * And removing the numbers divisible by 3 only from the second list:
256  *
257  * @skip itr
258  * @until list_even count
259  *
260  * Now that we don't need the two lists anymore, we can just free all the items.
261  * Since all of the allocated data was put into the first list, and both lists
262  * are made of pointers to inside the data structures, we can free only the
263  * first list (that contains all the elements) and the second list will be gone
264  * with it:
265  *
266  * @skip while
267  * @until free
268  *
269  * To see the full source code for this example, click here: @ref
270  * eina_inlist_03_c
271  * @example eina_inlist_03.c
272  */
273 
274 /**
275  * @page eina_inlist_01_c eina_inlist_01.c Eina_Inlist basic usage source
276  * @include eina_inlist_01.c
277  */
278 
279 /**
280  * @page eina_inlist_02_c eina_inlist_02.c Eina_Inlist advanced usage - lists and inlists source
281  * @include eina_inlist_02.c
282  */
283 
284 /**
285  * @page eina_inlist_03_c eina_inlist_03.c Eina_Inlist advanced usage - multi-inlists source
286  * @include eina_inlist_03.c
287  */
288 
289 /**
290  * @addtogroup Eina_Inline_List_Group Inline List
291  *
292  * @brief These functions provide inline list management.
293  *
294  * Inline lists mean its nodes pointers are part of same memory as
295  * data. This has the benefit of fragmenting memory less and avoiding
296  * @c node->data indirection, but has the drawback of higher cost for some
297  * common operations like count and sort.
298  *
299  * It is possible to have inlist nodes to be part of regular lists, created with
300  * @ref eina_list_append() or @ref eina_list_prepend(). It's also possible to
301  * have a structure with two inlist pointers, thus be part of two different
302  * inlists at the same time, but the current convenience macros provided won't
303  * work for both of them. Consult @ref inlist_advanced for more info.
304  *
305  * Inline lists have their purposes, but if you don't know what those purposes are, go with
306  * regular lists instead.
307  *
308  * Tip: When using inlists in more than one place (that is, passing them around
309  * functions or keeping a pointer to them in a structure) it's more correct
310  * to keep a pointer to the first container, and not a pointer to the first
311  * inlist item (mostly they are the same, but that's not always correct).
312  * This lets the compiler to do type checking and let the programmer know
313  * exactly what type this list is.
314  *
315  * A simple example demonstrating the basic usage of an inlist can be found
316  * here: @ref eina_inlist_01_example_page
317  *
318  * @section inlist_algo Algorithm
319  *
320  * The basic structure can be represented by the following picture:
321  *
322  * @image html eina_inlist-node.png
323  * @image rtf eina_inlist-node.png
324  * @image latex eina_inlist-node.eps
325  *
326  * One data structure will also have the node information, with three pointers:
327  * @a prev, @a next and @a last. The @a last pointer is just valid for the first
328  * element (the list head), otherwise each insertion in the list would have to
329  * be done updating every node with the correct pointer. This means that it's
330  * always very important to keep a pointer to the first element of the list,
331  * since it is the only one that has the correct information to allow a proper
332  * O(1) append to the list.
333  *
334  * @section inlist_perf Performance
335  *
336  * Due to the nature of the inlist, there's no accounting information, and no
337  * easy access to the last element from each list node. This means that @ref
338  * eina_inlist_count() is order-N, while @ref eina_list_count() is order-1 (constant
339  * time).
340  *
341  * @section inlist_advanced Advanced Usage
342  *
343  * The basic usage considers a struct that will have the user data, and also
344  * have an inlist node information (prev, next and last pointers) created with
345  * @ref EINA_INLIST during the struct declaration. This allows one to use the
346  * convenience macros @ref EINA_INLIST_GET(), @ref EINA_INLIST_CONTAINER_GET(),
347  * @ref EINA_INLIST_FOREACH() and so. This happens because the @ref EINA_INLIST
348  * macro declares a struct member with the name @a __inlist, and all the other
349  * macros assume that this struct member has this name.
350  *
351  * It may be the case that someone needs to have some inlist nodes added to a
352  * @ref Eina_List too. If this happens, the inlist nodes can be added to the
353  * @ref Eina_List without any problems. This example demonstrates this case:
354  * @ref eina_inlist_02_example_page
355  *
356  * It's also possible to have some data that is part of two different inlists.
357  * If this is the case, then it won't be possible to use the convenience macros
358  * to both of the lists. It will be necessary to create a new set of macros that
359  * will allow access to the second list node info. An example for this usage can
360  * be found here:
361  * @ref eina_inlist_03_example_page
362  *
363  * List of examples:
364  * @li @ref eina_inlist_01_example_page
365  * @li @ref eina_inlist_02_example_page
366  * @li @ref eina_inlist_03_example_page
367  */
368 
369 /**
370  * @addtogroup Eina_Data_Types_Group Data Types
371  *
372  * @{
373  */
374 
375 /**
376  * @addtogroup Eina_Containers_Group Containers
377  *
378  * @{
379  */
380 
381 /**
382  * @defgroup Eina_Inline_List_Group Inline List
383  *
384  * @{
385  */
386 
387 /**
388  * @typedef Eina_Inlist
389  * Inlined list type.
390  */
391 typedef struct _Eina_Inlist Eina_Inlist;
392 
393 /**
394  * @typedef Eina_Inlist_Sorted_State
395  * @since 1.1.0
396  * State of sorted Eina_Inlist
397  */
398 typedef struct _Eina_Inlist_Sorted_State Eina_Inlist_Sorted_State;
399 
400 /**
401  * @struct _Eina_Inlist
402  * Inlined list type.
403  */
404 struct _Eina_Inlist
405 {
406    Eina_Inlist *next; /**< next node */
407    Eina_Inlist *prev; /**< previous node */
408    Eina_Inlist *last; /**< last node */
409 };
410 /** Used for declaring an inlist member in a struct */
411 #define EINA_INLIST Eina_Inlist __in_list
412 /** Utility macro to get the inlist object of a struct */
413 #define EINA_INLIST_GET(Inlist)         (& ((Inlist)->__in_list))
414 /** Utility macro to get the container object of an inlist */
415 #define EINA_INLIST_CONTAINER_GET(ptr,                          \
416                                   type) ((type *)(void *)((char *)ptr - \
417                                                   offsetof(type, __in_list)))
418 
419 
420 /**
421  * @brief Adds a new node to end of a list.
422  *
423  * @note This code is meant to be fast: appends are O(1) and do not
424  *       walk @a in_list.
425  *
426  * @note @a in_item is considered to be in no list. If it was in another
427  *       list before, eina_inlist_remove() it before adding. No
428  *       check of @a new_l prev and next pointers is done, so it's safe
429  *       to have them uninitialized.
430  *
431  * @param[in,out] in_list Existing list head or @c NULL to create a new list.
432  * @param[in] in_item New list node, must not be @c NULL.
433  *
434  * @return The new list head. Use it and not @a in_list anymore.
435  */
436 EAPI Eina_Inlist *eina_inlist_append(Eina_Inlist *in_list,
437                                      Eina_Inlist *in_item) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT;
438 
439 /**
440  * @brief Adds a new node to beginning of list.
441  *
442  * @note This code is meant to be fast: appends are O(1) and do not
443  *       walk @a in_list.
444  *
445  * @note @a new_l is considered to be in no list. If it was in another
446  *       list before, eina_inlist_remove() it before adding. No
447  *       check of @a new_l prev and next pointers is done, so it's safe
448  *       to have them uninitialized.
449  *
450  * @param[in,out] in_list Existing list head or @c NULL to create a new list.
451  * @param[in] in_item New list node, must not be @c NULL.
452  *
453  * @return The new list head. Use it and not @a in_list anymore.
454  */
455 EAPI Eina_Inlist *eina_inlist_prepend(Eina_Inlist *in_list,
456                                       Eina_Inlist *in_item) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT;
457 
458 /**
459  * @brief Adds a new node after the given relative item in list.
460  *
461  * @note This code is meant to be fast: appends are O(1) and do not
462  *       walk @a in_list.
463  *
464  * @note @a in_item_l is considered to be in no list. If it was in another
465  *       list before, eina_inlist_remove() it before adding. No
466  *       check of @a in_item prev and next pointers is done, so it's safe
467  *       to have them uninitialized.
468  *
469  * @note @a in_relative is considered to be inside @a in_list, no checks are
470  *       done to confirm that and giving nodes from different lists
471  *       will lead to problems. Giving NULL @a in_relative is the same as
472  *       eina_list_append().
473  *
474  * @param[in,out] in_list Existing list head or @c NULL to create a new list.
475  * @param[in] in_item New list node, must not be @c NULL.
476  * @param[in] in_relative Reference node, @a in_item will be added after it.
477  *
478  * @return The new list head. Use it and not @a list anymore.
479  */
480 EAPI Eina_Inlist *eina_inlist_append_relative(Eina_Inlist *in_list,
481                                               Eina_Inlist *in_item,
482                                               Eina_Inlist *in_relative) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT;
483 
484 /**
485  * @brief Adds a new node before the given relative item in list.
486  *
487  * @note This code is meant to be fast: appends are O(1) and do not
488  *       walk @a in_list.
489  *
490  * @note @a in_item is considered to be in no list. If it was in another
491  *       list before, eina_inlist_remove() it before adding. No
492  *       check of @a in_item prev and next pointers is done, so it's safe
493  *       to have them uninitialized.
494  *
495  * @note @a in_relative is considered to be inside @a in_list, no checks are
496  *       done to confirm that and giving nodes from different lists
497  *       will lead to problems. Giving NULL @a in_relative is the same as
498  *       eina_list_prepend().
499  *
500  * @param[in,out] in_list Existing list head or @c NULL to create a new list.
501  * @param[in] in_item New list node, must not be @c NULL.
502  * @param[in] in_relative Reference node, @a in_item will be added before it.
503  *
504  * @return The new list head. Use it and not @a in_list anymore.
505  */
506 EAPI Eina_Inlist *eina_inlist_prepend_relative(Eina_Inlist *in_list,
507                                                Eina_Inlist *in_item,
508                                                Eina_Inlist *in_relative) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT;
509 
510 /**
511  * @brief Removes node from list.
512  *
513  * @note This code is meant to be fast: appends are O(1) and do not
514  *       walk @a list.
515  *
516  * @note @a in_item is considered to be inside @a in_list, no checks are
517  *       done to confirm that and giving nodes from different lists
518  *       will lead to problems, especially if @a in_item is the head since
519  *       it will be different from @a list and the wrong new head will
520  *       be returned.
521  *
522  * @param[in,out] in_list Existing list head, must not be @c NULL.
523  * @param[in] in_item Existing list node, must not be @c NULL.
524  *
525  * @return The new list head. Use it and not @a list anymore.
526  */
527 EAPI Eina_Inlist   *eina_inlist_remove(Eina_Inlist *in_list,
528                                        Eina_Inlist *in_item) EINA_ARG_NONNULL(1, 2) EINA_WARN_UNUSED_RESULT;
529 
530 /**
531  * @brief Finds given node in list, returns itself if found, NULL if not.
532  *
533  * @warning This is an expensive call and has O(n) cost, possibly
534  *    walking the whole list.
535  *
536  * @param[in] in_list Existing list to search @a in_item in, must not be @c NULL.
537  * @param[in] in_item What to search for, must not be @c NULL.
538  *
539  * @return @a in_item if found, @c NULL if not.
540  */
541 EAPI Eina_Inlist   *eina_inlist_find(Eina_Inlist *in_list,
542                                      Eina_Inlist *in_item) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT;
543 
544 /**
545  * @brief Moves existing node to beginning of list.
546  *
547  * @note This code is meant to be fast: appends are O(1) and do not
548  *       walk @a list.
549  *
550  * @note @a item is considered to be inside @a list. No checks are
551  *       done to confirm this, and giving nodes from different lists
552  *       will lead to problems.
553  *
554  * @param[in] list Existing list head or @c NULL to create a new list.
555  * @param[in] item List node to move to beginning (head), must not be @c NULL.
556  *
557  * @return The new list head. Use it and not @a list anymore.
558  */
559 EAPI Eina_Inlist   *eina_inlist_promote(Eina_Inlist *list,
560                                         Eina_Inlist *item) EINA_ARG_NONNULL(1, 2) EINA_WARN_UNUSED_RESULT;
561 
562 /**
563  * @brief Moves existing node to end of list.
564  *
565  * @note This code is meant to be fast: appends are O(1) and do not
566  *       walk @a list.
567  *
568  * @note @a item is considered to be inside @a list. No checks are
569  *       done to confirm this, and giving nodes from different lists
570  *       will lead to problems.
571  *
572  * @param[in] list Existing list head or @c NULL to create a new list.
573  * @param[in] item List node to move to end (tail), must not be @c NULL.
574  *
575  * @return The new list head. Use it and not @a list anymore.
576  */
577 EAPI Eina_Inlist   *eina_inlist_demote(Eina_Inlist *list,
578                                        Eina_Inlist *item) EINA_ARG_NONNULL(1, 2) EINA_WARN_UNUSED_RESULT;
579 
580 /**
581  * @brief Gets the first list node in the list.
582  *
583  * @param[in] list The list to get the first list node from.
584  * @return The first list node in the list.
585  *
586  * This function returns the first list node in the list @p list. If
587  * @p list is @c NULL, @c NULL is returned.
588  *
589  * This is a O(N) operation (it takes time proportional
590  * to the length of the list).
591  *
592  * @since 1.8
593  */
594 static inline Eina_Inlist *eina_inlist_first(const Eina_Inlist *list) EINA_PURE EINA_WARN_UNUSED_RESULT;
595 
596 /**
597  * @brief Gets the last list node in the list.
598  *
599  * @param[in] list The list to get the last list node from.
600  * @return The last list node in the list.
601  *
602  * This function returns the last list node in the list @p list. If
603  * @p list is @c NULL, @c NULL is returned.
604  *
605  * This is a O(N) operation (it takes time proportional
606  * to the length of the list).
607  *
608  * @since 1.8
609  */
610 static inline Eina_Inlist *eina_inlist_last(const Eina_Inlist *list) EINA_PURE EINA_WARN_UNUSED_RESULT;
611 
612 /**
613  * @brief Gets the count of the number of items in a list.
614  *
615  * @param[in] list The list whose count to return.
616  * @return The number of members in the list.
617  *
618  * This function returns how many members @p list contains. If the
619  * list is @c NULL, @c 0 is returned.
620  *
621  * @warning This is an order-N operation and so the time will depend
622  *    on the number of elements on the list, so, it might become
623  *    slow for big lists!
624  */
625 EAPI unsigned int   eina_inlist_count(const Eina_Inlist *list) EINA_WARN_UNUSED_RESULT;
626 
627 
628 /**
629  * @brief Returns a new iterator associated to @a list.
630  *
631  * @param[in] in_list The list.
632  * @return A new iterator.
633  *
634  * This function returns a newly allocated iterator associated to @p
635  * in_list. If @p in_list is @c NULL or the count member of @p in_list is less
636  * or equal than 0, this function still returns a valid iterator that
637  * will always return false on eina_iterator_next(), thus keeping API
638  * sane.
639  *
640  * If the memory can not be allocated, @c NULL is returned.
641  * Otherwise, a valid iterator is returned.
642  *
643  * @warning if the list structure changes then the iterator becomes
644  *    invalid, and if you add or remove nodes iterator
645  *    behavior is undefined, and your program may crash!
646  */
647 EAPI Eina_Iterator *eina_inlist_iterator_new(const Eina_Inlist *in_list) EINA_MALLOC EINA_WARN_UNUSED_RESULT;
648 
649 /**
650  * @brief Returns a new accessor associated to a list.
651  *
652  * @param[in] in_list The list.
653  * @return A new accessor.
654  *
655  * This function returns a newly allocated accessor associated to
656  * @p in_list. If @p in_list is @c NULL or the count member of @p in_list is
657  * less or equal than @c 0, this function returns @c NULL. If the memory can
658  * not be allocated, @c NULL is returned and Otherwise, a valid accessor is
659  * returned.
660  */
661 EAPI Eina_Accessor *eina_inlist_accessor_new(const Eina_Inlist *in_list) EINA_MALLOC EINA_WARN_UNUSED_RESULT;
662 
663 /**
664  * @brief Inserts a new node into a sorted list.
665  *
666  * @param[in,out] list The given linked list, @b must be sorted.
667  * @param[in] item List node to insert, must not be @c NULL.
668  * @param[in] func The function called for the sort.
669  * @return A list pointer.
670  *
671  * This function inserts item into a linked list assuming it was
672  * sorted and the result will be sorted. If @p list is @c NULL, item
673  * is returned. On success, a new list pointer that should be
674  * used in place of the one given to this function is
675  * returned. Otherwise, the old pointer is returned.
676  *
677  * @note O(log2(n)) comparisons (calls to @p func) average/worst case
678  * performance. As said in eina_list_search_sorted_near_list(),
679  * lists do not have O(1) access time, so walking to the correct node
680  * can be costly, consider worst case to be almost O(n) pointer
681  * dereference (list walk).
682  *
683  * @since 1.1.0
684  */
685 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;
686 
687 /**
688  * @brief Creates state with valid data in it.
689  *
690  * @return A valid Eina_Inlist_Sorted_State.
691  *
692  * @since 1.1.0
693  *
694  * See eina_inlist_sorted_state_insert() for more information.
695  */
696 EAPI Eina_Inlist_Sorted_State *eina_inlist_sorted_state_new(void);
697 
698 /**
699  * @brief Forces an Eina_Inlist_Sorted_State to match the content of a list.
700  *
701  * @param[in,out] state The state to update
702  * @param[in] list The list to match
703  * @return The number of item in the actually in the list
704  *
705  * @since 1.1.0
706  *
707  * See eina_inlist_sorted_state_insert() for more information. This function is
708  * useful if you didn't use eina_inlist_sorted_state_insert() at some point, but
709  * still think you have a sorted list. It will only correctly work on a sorted list.
710  */
711 EAPI int eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list);
712 
713 /**
714  * @brief Frees an Eina_Inlist_Sorted_State.
715  *
716  * @param[in,out] state The state to destroy
717  *
718  * @since 1.1.0
719  *
720  * See eina_inlist_sorted_state_insert() for more information.
721  */
722 EAPI void eina_inlist_sorted_state_free(Eina_Inlist_Sorted_State *state);
723 
724 /**
725  * @brief Inserts a new node into a sorted list.
726  *
727  * @param[in,out] list The given linked list, @b must be sorted.
728  * @param[in] item list node to insert, must not be @c NULL.
729  * @param[in] func The function called for the sort.
730  * @param[in,out] state The current array for initial dichotomic search
731  * @return A list pointer.
732  * @since 1.1.0
733  *
734  * This function inserts item into a linked list assuming @p state matches
735  * the exact content order of the list. It uses @p state to do a fast
736  * first step dichotomic search before starting to walk the inlist itself.
737  * This makes this code much faster than eina_inlist_sorted_insert() as it
738  * doesn't need to walk the list at all. The result is of course a sorted
739  * list with an updated state. If @p list is @c NULL, item
740  * is returned. On success, a new list pointer that should be
741  * used in place of the one given to this function is
742  * returned. Otherwise, the old pointer is returned.
743  *
744  * @note O(log2(n)) comparisons (calls to @p func) average/worst case
745  * performance. As said in eina_list_search_sorted_near_list(),
746  * lists do not have O(1) access time, so walking to the correct node
747  * can be costly, but this version tries to minimize that by making it a
748  * O(log2(n)) for number small number. After n == 256, it starts to add a
749  * linear cost again. Consider worst case to be almost O(n) pointer
750  * dereference (list walk).
751  */
752 EAPI Eina_Inlist *eina_inlist_sorted_state_insert(Eina_Inlist *list,
753 						  Eina_Inlist *item,
754 						  Eina_Compare_Cb func,
755 						  Eina_Inlist_Sorted_State *state);
756 /**
757  * @brief Sorts a list according to the ordering func will return.
758  *
759  * @param[in,out] head The list handle to sort.
760  * @param[in] func A function pointer that can handle comparing the list data
761  * nodes.
762  * @return the new head of list.
763  *
764  * This function sorts all the elements of @p head. @p func is used to
765  * compare two elements of @p head. If @p head or @p func are @c NULL,
766  * this function returns @c NULL.
767  *
768  * @note @b in-place: this will change the given list, so you should
769  * now point to the new list head that is returned by this function.
770  *
771  * @note Worst case is O(n * log2(n)) comparisons (calls to func()).
772  * That means that for 1,000,000 list  elements, sort will do 20,000,000
773  * comparisons.
774  *
775  * Example:
776  * @code
777  * typedef struct _Sort_Ex Sort_Ex;
778  * struct _Sort_Ex
779  * {
780  *   EINA_INLIST;
781  *   const char *text;
782  * };
783  *
784  * int
785  * sort_cb(const Inlist *l1, const Inlist *l2)
786  * {
787  *    const Sort_Ex *x1;
788  *    const Sort_Ex *x2;
789  *
790  *    x1 = EINA_INLIST_CONTAINER_GET(l1, Sort_Ex);
791  *    x2 = EINA_INLIST_CONTAINER_GET(l2, Sort_Ex);
792  *
793  *    return(strcmp(x1->text, x2->text));
794  * }
795  * extern Eina_Inlist *list;
796  *
797  * list = eina_inlist_sort(list, sort_cb);
798  * @endcode
799  */
800 EAPI Eina_Inlist *eina_inlist_sort(Eina_Inlist *head, Eina_Compare_Cb func);
801 
802 /* These two macros are helpers for the _FOREACH ones, don't use them */
803 /**
804  * @def _EINA_INLIST_OFFSET
805  * @param[in,out] ref The reference to be used.
806  */
807 #define _EINA_INLIST_OFFSET(ref)         ((char *)&(ref)->__in_list - (char *)(ref))
808 
809 #if !defined(__cplusplus)
810 /**
811  * @def _EINA_INLIST_CONTAINER
812  * @param[in,out] ref The reference to be used.
813  * @param[out] ptr The pointer to be used.
814  */
815 #define _EINA_INLIST_CONTAINER(ref, ptr) (void *)((char *)(ptr) - \
816                                                   _EINA_INLIST_OFFSET(ref))
817 #else
818 /*
819  * In C++ we can't assign a "type*" pointer to void* so we rely on GCC's typeof
820  * operator.
821  */
822 # define _EINA_INLIST_CONTAINER(ref, ptr) (__typeof__(ref))((char *)(ptr) - \
823 							    _EINA_INLIST_OFFSET(ref))
824 #endif
825 
826 /**
827  * @def EINA_INLIST_FOREACH
828  * @param[in,out] list The list to iterate on.
829  * @param[out] it The pointer to the list item, i.e. a pointer to each
830  *             item that is part of the list.
831  */
832 #define EINA_INLIST_FOREACH(list, it)                                     \
833   for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list) : NULL); it; \
834        it = (EINA_INLIST_GET(it)->next ? _EINA_INLIST_CONTAINER(it, EINA_INLIST_GET(it)->next) : NULL))
835 
836 /**
837  * @def EINA_INLIST_FOREACH_SAFE
838  * @param[in,out] list The list to iterate on.
839  * @param[out] list2 Auxiliary Eina_Inlist variable so we can save the
840  *             pointer to the next element, allowing us to free/remove
841  *             the current one. Note that this macro is only safe if the
842  *             next element is not removed. Only the current one is
843  *             allowed to be removed.
844  * @param[out] it The pointer to the list item, i.e. a pointer to each
845  *             item that is part of the list.
846  */
847 #define EINA_INLIST_FOREACH_SAFE(list, list2, it) \
848    for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list) : NULL), list2 = it ? EINA_INLIST_GET(it)->next : NULL; \
849         it; \
850         it = NULL, it = list2 ? _EINA_INLIST_CONTAINER(it, list2) : NULL, list2 = list2 ? list2->next : NULL)
851 
852 /**
853  * @def EINA_INLIST_REVERSE_FOREACH
854  * @param[in,out] list The list to traverse in reverse order.
855  * @param[out] it The pointer to the list item, i.e. a pointer to each
856  *             item that is part of the list.
857  */
858 #define EINA_INLIST_REVERSE_FOREACH(list, it)                                \
859   for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list->last) : NULL); \
860        it; it = (EINA_INLIST_GET(it)->prev ? _EINA_INLIST_CONTAINER(it, EINA_INLIST_GET(it)->prev) : NULL))
861 
862 /**
863  * @def EINA_INLIST_REVERSE_FOREACH_FROM
864  * @param[in,out] list The last list to traverse in reverse order.
865  * @param[in] it The pointer to the list item, i.e. a pointer to each
866  *            item that is part of the list.
867  * @see EINA_INLIST_REVERSE_FOREACH()
868  *
869  * @since 1.8
870  *
871  * EINA_INLIST_REVERSE_FOREACH() starts from last list of the given list.
872  * This starts from given list, not the last one.
873  */
874 #define EINA_INLIST_REVERSE_FOREACH_FROM(list, it)                                \
875   for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list) : NULL); \
876        it; it = (EINA_INLIST_GET(it)->prev ? _EINA_INLIST_CONTAINER(it, EINA_INLIST_GET(it)->prev) : NULL))
877 
878 /**
879  * @def EINA_INLIST_FREE
880  * @param[in,out] list The list to free.
881  * @param[in] it The pointer to the list item, i.e. a pointer to each item
882  *            that is part of the list.
883  *
884  * NOTE: it is the duty of the body loop to properly remove the item from the
885  * inlist and free it. This function will turn into a infinite loop if you
886  * don't remove all items from the list.
887  * @since 1.8
888  */
889 #define EINA_INLIST_FREE(list, it)				\
890   for (it = (__typeof__(it)) list; list; it = (__typeof__(it)) list)
891 
892 #include "eina_inline_inlist.x"
893 
894 /**
895  * @}
896  */
897 
898 /**
899  * @}
900  */
901 
902 /**
903  * @}
904  */
905 
906 #endif /*EINA_INLIST_H_*/
907