1 /* EINA - EFL data type library
2 * Copyright (C) 2002-2008 Carsten Haitzler, Gustavo Sverzut Barbieri, Tilman Sauerbeck,
3 * Vincent Torri, Cedric Bail, Jorge Luis Zapata Muga,
4 * Corey Donohoe, Arnaud de Turckheim, Alexandre Becoulet
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library;
18 * if not, see <http://www.gnu.org/licenses/>.
20 * This file incorporates work covered by the following copyright and
23 * Copyright (C) 2004 ncn
24 * Copyright (C) 2006 Sebastian Dransfeld
25 * Copyright (C) 2007 Christopher Michael
27 * Permission is hereby granted, free of charge, to any person obtaining a copy
28 * of this software and associated documentation files (the "Software"), to
29 * deal in the Software without restriction, including without limitation the
30 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
31 * sell copies of the Software, and to permit persons to whom the Software is
32 * furnished to do so, subject to the following conditions:
34 * The above copyright notice and this permission notice shall be included in
35 * all copies of the Software and its Copyright notices. In addition publicly
36 * documented acknowledgment must be given that this software has been used if no
37 * source code of this software is made available publicly. This includes
38 * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing
39 * documents or any documentation provided with any product containing this
40 * software. This License does not apply to any software that links to the
41 * libraries provided by this software (statically or dynamically), but only to
42 * the software provided.
44 * Please see the OLD-COPYING.PLAIN for a plain-english explanation of this notice
47 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
48 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
49 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
50 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
51 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
52 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
57 * @page tutorial_list_page List Tutorial
75 #include "eina_config.h"
76 #include "eina_private.h"
77 #include "eina_error.h"
78 #include "eina_mempool.h"
80 /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
81 #include "eina_safety_checks.h"
82 #include "eina_list.h"
85 /*============================================================================*
87 *============================================================================*/
93 #define EINA_MAGIC_CHECK_LIST(d, ...) \
95 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST)) \
97 EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST); \
102 #define EINA_MAGIC_CHECK_LIST_ITERATOR(d, ...) \
104 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ITERATOR)) \
106 EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ITERATOR); \
107 return __VA_ARGS__; \
111 #define EINA_MAGIC_CHECK_LIST_ACCESSOR(d, ...) \
113 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ACCESSOR)) \
115 EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ACCESSOR); \
116 return __VA_ARGS__; \
120 #define EINA_MAGIC_CHECK_LIST_ACCOUNTING(d) \
122 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ACCOUNTING)) \
124 EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ACCOUNTING); \
129 #define EINA_LIST_SORT_STACK_SIZE 32
131 typedef struct _Eina_Iterator_List Eina_Iterator_List;
132 typedef struct _Eina_Accessor_List Eina_Accessor_List;
134 struct _Eina_Iterator_List
136 Eina_Iterator iterator;
138 const Eina_List *head;
139 const Eina_List *current;
144 struct _Eina_Accessor_List
146 Eina_Accessor accessor;
148 const Eina_List *head;
149 const Eina_List *current;
156 static Eina_Mempool *_eina_list_mp = NULL;
157 static Eina_Mempool *_eina_list_accounting_mp = NULL;
158 static int _eina_list_log_dom = -1;
160 #define ERR(...) EINA_LOG_DOM_ERR(_eina_list_log_dom, __VA_ARGS__)
161 #define DBG(...) EINA_LOG_DOM_DBG(_eina_list_log_dom, __VA_ARGS__)
163 static inline Eina_List_Accounting*
164 _eina_list_mempool_accounting_new(__UNUSED__ Eina_List *list)
166 Eina_List_Accounting *tmp;
168 tmp = eina_mempool_malloc(_eina_list_accounting_mp, sizeof (Eina_List_Accounting));
169 if (!tmp) return NULL;
171 EINA_MAGIC_SET(tmp, EINA_MAGIC_LIST_ACCOUNTING);
176 _eina_list_mempool_accounting_free(Eina_List_Accounting *accounting)
178 EINA_MAGIC_CHECK_LIST_ACCOUNTING(accounting);
180 EINA_MAGIC_SET(accounting, EINA_MAGIC_NONE);
181 eina_mempool_free(_eina_list_accounting_mp, accounting);
184 static inline Eina_List*
185 _eina_list_mempool_list_new(__UNUSED__ Eina_List *list)
189 tmp = eina_mempool_malloc(_eina_list_mp, sizeof (Eina_List));
190 if (!tmp) return NULL;
192 EINA_MAGIC_SET(tmp, EINA_MAGIC_LIST);
197 _eina_list_mempool_list_free(Eina_List *list)
199 EINA_MAGIC_CHECK_LIST(list);
201 list->accounting->count--;
202 if (list->accounting->count == 0)
203 _eina_list_mempool_accounting_free(list->accounting);
205 EINA_MAGIC_SET(list, EINA_MAGIC_NONE);
206 eina_mempool_free(_eina_list_mp, list);
210 _eina_list_setup_accounting(Eina_List *list)
212 EINA_MAGIC_CHECK_LIST(list, NULL);
214 list->accounting = _eina_list_mempool_accounting_new(list);
215 if (!list->accounting) goto on_error;
217 list->accounting->last = list;
218 list->accounting->count = 1;
223 _eina_list_mempool_list_free(list);
228 _eina_list_update_accounting(Eina_List *list, Eina_List *new_list)
230 EINA_MAGIC_CHECK_LIST(list);
231 EINA_MAGIC_CHECK_LIST(new_list);
233 list->accounting->count++;
234 new_list->accounting = list->accounting;
238 static Eina_Mempool2 _eina_list_mempool =
244 static Eina_Mempool2 _eina_list_accounting_mempool =
246 sizeof(Eina_List_Accounting),
253 eina_list_iterator_next(Eina_Iterator_List *it, void **data)
255 EINA_MAGIC_CHECK_LIST_ITERATOR(it, EINA_FALSE);
257 if (it->current == NULL) return EINA_FALSE;
258 *data = eina_list_data_get(it->current);
260 it->current = eina_list_next(it->current);
266 eina_list_iterator_prev(Eina_Iterator_List *it, void **data)
268 EINA_MAGIC_CHECK_LIST_ITERATOR(it, EINA_FALSE);
270 if (it->current == NULL) return EINA_FALSE;
271 *data = eina_list_data_get(it->current);
273 it->current = eina_list_prev(it->current);
279 eina_list_iterator_get_container(Eina_Iterator_List *it)
281 EINA_MAGIC_CHECK_LIST_ITERATOR(it, NULL);
283 return (Eina_List *) it->head;
287 eina_list_iterator_free(Eina_Iterator_List *it)
289 EINA_MAGIC_CHECK_LIST_ITERATOR(it);
295 eina_list_accessor_get_at(Eina_Accessor_List *it, unsigned int index, void **data)
297 const Eina_List *over;
301 EINA_MAGIC_CHECK_LIST_ACCESSOR(it, EINA_FALSE);
303 if (index >= eina_list_count(it->head)) return EINA_FALSE;
305 if (it->index == index)
309 else if (index > it->index)
311 /* After current position. */
312 middle = ((eina_list_count(it->head) - it->index) >> 1) + it->index;
316 /* Go backward from the end. */
317 for (i = eina_list_count(it->head) - 1, over = eina_list_last(it->head);
318 i > index && over != NULL;
319 --i, over = eina_list_prev(over))
324 /* Go forward from current. */
325 for (i = it->index, over = it->current;
326 i < index && over != NULL;
327 ++i, over = eina_list_next(over))
333 /* Before current position. */
334 middle = it->index >> 1;
338 /* Go backward from current. */
339 for (i = it->index, over = it->current;
340 i > index && over != NULL;
341 --i, over = eina_list_prev(over))
346 /* Go forward from start. */
347 for (i = 0, over = it->head;
348 i < index && over != NULL;
349 ++i, over = eina_list_next(over))
354 if (over == NULL) return EINA_FALSE;
359 *data = eina_list_data_get(it->current);
364 eina_list_accessor_get_container(Eina_Accessor_List *it)
366 EINA_MAGIC_CHECK_LIST_ACCESSOR(it, NULL);
368 return (Eina_List *) it->head;
372 eina_list_accessor_free(Eina_Accessor_List *it)
374 EINA_MAGIC_CHECK_LIST_ACCESSOR(it);
380 eina_list_sort_rebuild_prev(Eina_List *list)
382 Eina_List *prev = NULL;
384 EINA_MAGIC_CHECK_LIST(list, NULL);
386 for (; list; list = list->next)
396 eina_list_sort_merge(Eina_List *a, Eina_List *b, Eina_Compare_Cb func)
398 Eina_List *first, *last;
400 if (func(a->data, b->data) < 0)
401 a = (last = first = a)->next;
403 b = (last = first = b)->next;
406 if (func(a->data, b->data) < 0)
407 a = (last = last->next = a)->next;
409 b = (last = last->next = b)->next;
411 last->next = a ? a : b;
420 /*============================================================================*
422 *============================================================================*/
424 /*============================================================================*
426 *============================================================================*/
429 * @addtogroup Eina_List_Group List
431 * @brief These functions provide double linked list management.
433 * For more information, you can look at the @ref tutorial_list_page.
440 * @brief Initialize the list module.
442 * @return #EINA_TRUE on success, #EINA_FALSE on failure.
444 * This function sets up the list module of Eina. It is called by
447 * This function creates mempool to speed up list node and accounting
448 * management, using EINA_MEMPOOL environment variable if it is set to
449 * choose the memory pool type to use.
456 const char *choice, *tmp;
458 _eina_list_log_dom = eina_log_domain_register("eina_list", EINA_LOG_COLOR_DEFAULT);
459 if (_eina_list_log_dom < 0)
461 EINA_LOG_ERR("Could not register log domain: eina_list");
465 #ifdef EINA_DEFAULT_MEMPOOL
466 choice = "pass_through";
468 choice = "chained_mempool";
470 tmp = getenv("EINA_MEMPOOL");
474 _eina_list_mp = eina_mempool_add
475 (choice, "list", NULL, sizeof(Eina_List), 320);
478 ERR("ERROR: Mempool for list cannot be allocated in list init.");
481 _eina_list_accounting_mp = eina_mempool_add
482 (choice, "list_accounting", NULL, sizeof(Eina_List_Accounting), 80);
483 if (!_eina_list_accounting_mp)
485 ERR("ERROR: Mempool for list accounting cannot be allocated in list init.");
486 eina_mempool_del(_eina_list_mp);
490 eina_magic_string_set(EINA_MAGIC_LIST, "Eina List");
491 eina_magic_string_set(EINA_MAGIC_LIST_ITERATOR, "Eina List Iterator");
492 eina_magic_string_set(EINA_MAGIC_LIST_ACCESSOR, "Eina List Accessor");
493 eina_magic_string_set(EINA_MAGIC_LIST_ACCOUNTING, "Eina List Accounting");
498 eina_log_domain_unregister(_eina_list_log_dom);
499 _eina_list_log_dom = -1;
505 * @brief Shut down the list module.
507 * @return #EINA_TRUE on success, #EINA_FALSE on failure.
509 * This function shuts down the list module set up by
510 * eina_list_init(). It is called by eina_shutdown().
512 * @see eina_shutdown()
515 eina_list_shutdown(void)
517 eina_mempool_del(_eina_list_accounting_mp);
518 eina_mempool_del(_eina_list_mp);
520 eina_log_domain_unregister(_eina_list_log_dom);
521 _eina_list_log_dom = -1;
526 * @brief Append the given data to the given linked list.
528 * @param list The given list.
529 * @param data The data to append.
530 * @return A list pointer.
532 * This function appends @p data to @p list. If @p list is @c NULL, a
533 * new list is returned. On success, a new list pointer that should be
534 * used in place of the one given to this function is
535 * returned. Otherwise, the old pointer is returned.
537 * The following example code demonstrates how to ensure that the
538 * given data has been successfully appended.
541 * Eina_List *list = NULL;
542 * extern void *my_data;
544 * list = eina_list_append(list, my_data);
545 * if (eina_error_get())
547 * fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
553 eina_list_append(Eina_List *list, const void *data)
555 Eina_List *l, *new_l;
558 new_l = _eina_list_mempool_list_new(list);
559 if (!new_l) return list;
561 new_l->data = (void *)data;
565 return _eina_list_setup_accounting(new_l);
568 EINA_MAGIC_CHECK_LIST(list, NULL);
570 l = list->accounting->last;
571 list->accounting->last = new_l;
576 _eina_list_update_accounting(list, new_l);
581 * @brief Prepends the given data to the given linked list.
583 * @param list The given list.
584 * @param data The data to prepend.
585 * @return A list pointer.
587 * This function prepends @p data to @p list. If @p list is @c NULL, a
588 * new list is returned. On success, a new list pointer that should be
589 * used in place of the one given to this function is
590 * returned. Otherwise, the old pointer is returned.
592 * The following example code demonstrates how to ensure that the
593 * given data has been successfully prepended.
597 * Eina_List *list = NULL;
598 * extern void *my_data;
600 * list = eina_list_prepend(list, my_data);
601 * if (eina_error_get())
603 * fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
609 eina_list_prepend(Eina_List *list, const void *data)
614 new_l = _eina_list_mempool_list_new(list);
615 if (!new_l) return list;
619 new_l->data = (void *)data;
621 if (!list) return _eina_list_setup_accounting(new_l);
623 EINA_MAGIC_CHECK_LIST(list, NULL);
627 _eina_list_update_accounting(list, new_l);
633 * @brief Insert the given data into the given linked list after the specified data.
635 * @param list The given linked list.
636 * @param data The data to insert.
637 * @param relative The data to insert after.
638 * @return A list pointer.
640 * This function inserts @p data to @p list after @p relative. If
641 * @p relative is not in the list, @p data is appended to the end of
642 * the list. If @p list is @c NULL, a new list is returned. If there
643 * are multiple instances of @p relative in the list, @p data is
644 * inserted after the first instance.On success, a new list pointer
645 * that should be used in place of the one given to this function is
646 * returned. Otherwise, the old pointer is returned.
648 * The following example code demonstrates how to ensure that the
649 * given data has been successfully inserted.
652 * Eina_List *list = NULL;
653 * extern void *my_data;
654 * extern void *relative_member;
656 * list = eina_list_append(list, relative_member);
657 * if (eina_error_get())
659 * fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
662 * list = eina_list_append_relative(list, my_data, relative_member);
663 * if (eina_error_get())
665 * fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
671 eina_list_append_relative(Eina_List *list, const void *data, const void *relative)
676 if (list) EINA_MAGIC_CHECK_LIST(list, NULL);
678 EINA_LIST_FOREACH(list, l, list_data)
680 if (list_data == relative)
681 return eina_list_append_relative_list(list, data, l);
684 return eina_list_append(list, data);
688 * @brief Append a list node to a linked list after the specified member
690 * @param list The given linked list.
691 * @param data The data to insert.
692 * @param relative The list node to insert after.
693 * @return A list pointer.
695 * This function inserts @p data to @p list after the list node
696 * @p relative. If @p list or @p relative are @c NULL, @p data is just
697 * appended to @p list using eina_list_append(). If @p list is
698 * @c NULL, a new list is returned. If there are multiple instances
699 * of @p relative in the list, @p data is inserted after the first
700 * instance. On success, a new list pointer that should be used in
701 * place of the one given to this function is returned. Otherwise, the
702 * old pointer is returned.
705 eina_list_append_relative_list(Eina_List *list, const void *data, Eina_List *relative)
709 if ((!list) || (!relative)) return eina_list_append(list, data);
711 new_l = _eina_list_mempool_list_new(list);
712 if (!new_l) return list;
714 EINA_MAGIC_CHECK_LIST(relative, NULL);
715 new_l->next = relative->next;
716 new_l->data = (void *)data;
719 relative->next->prev = new_l;
721 relative->next = new_l;
722 new_l->prev = relative;
724 _eina_list_update_accounting(list, new_l);
727 new_l->accounting->last = new_l;
733 * @brief Prepend a data pointer to a linked list before the specified member
735 * @param list The given linked list.
736 * @param data The data to insert.
737 * @param relative The data to insert before.
738 * @return A list pointer.
740 * This function inserts @p data to @p list before @p relative. If
741 * @p relative is not in the list, @p data is prepended to the list
742 * with eina_list_prepend(). If @p list is @c NULL, a new list is
743 * returned. If there are multiple instances of @p relative in the
744 * list, @p data is inserted before the first instance. On success, a
745 * new list pointer that should be used in place of the one given to
746 * this function is returned. Otherwise, the old pointer is returned.
748 * The following code example demonstrates how to ensure that the
749 * given data has been successfully inserted.
752 * Eina_List *list = NULL;
753 * extern void *my_data;
754 * extern void *relative_member;
756 * list = eina_list_append(list, relative_member);
757 * if (eina_error_get_error())
759 * fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
762 * list = eina_list_prepend_relative(list, my_data, relative_member);
763 * if (eina_error_get())
765 * fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
771 eina_list_prepend_relative(Eina_List *list, const void *data, const void *relative)
776 if (list) EINA_MAGIC_CHECK_LIST(list, NULL);
778 EINA_LIST_FOREACH(list, l, list_data)
780 if (list_data == relative)
781 return eina_list_prepend_relative_list(list, data, l);
783 return eina_list_prepend(list, data);
787 * @brief Prepend a list node to a linked list before the specified member
789 * @param list The given linked list.
790 * @param data The data to insert.
791 * @param relative The list node to insert before.
792 * @return A list pointer.
794 * This function inserts @p data to @p list before the list node
795 * @p relative. If @p list or @p relative are @c NULL, @p data is just
796 * prepended to @p list using eina_list_prepend(). If @p list is
797 * @c NULL, a new list is returned. If there are multiple instances
798 * of @p relative in the list, @p data is inserted before the first
799 * instance. On success, a new list pointer that should be used in
800 * place of the one given to this function is returned. Otherwise, the
801 * old pointer is returned.
804 eina_list_prepend_relative_list(Eina_List *list, const void *data, Eina_List *relative)
808 if ((!list) || (!relative)) return eina_list_prepend(list, data);
810 new_l = _eina_list_mempool_list_new(list);
811 if (!new_l) return list;
813 EINA_MAGIC_CHECK_LIST(relative, NULL);
815 new_l->prev = relative->prev;
816 new_l->next = relative;
817 new_l->data = (void *)data;
819 if (relative->prev) relative->prev->next = new_l;
820 relative->prev = new_l;
822 _eina_list_update_accounting(list, new_l);
831 * @brief Insert a new node into a sorted list.
833 * @param list The given linked list, @b must be sorted.
834 * @param data The data to insert sorted.
835 * @return A list pointer.
837 * This function inserts values into a linked list assuming it was
838 * sorted and the result will be sorted. If @p list is @c NULLL, a new
839 * list is returned. On success, a new list pointer that should be
840 * used in place of the one given to this function is
841 * returned. Otherwise, the old pointer is returned. See eina_error_get().
843 * @note O(log2(n)) comparisons (calls to func) average/worst case
844 * performance as it uses eina_list_search_sorted_near_list() and thus
845 * is bounded to that. As said in eina_list_search_sorted_near_list(),
846 * lists do not have O(1) access time, so walking to the correct node
847 * can be costly, consider worst case to be almost O(n) pointer
848 * dereference (list walk).
851 eina_list_sorted_insert(Eina_List *list, Eina_Compare_Cb func, const void *data)
856 if (!list) return eina_list_append(NULL, data);
858 lnear = eina_list_search_sorted_near_list(list, func, data, &cmp);
860 return eina_list_append_relative_list(list, data, lnear);
862 return eina_list_prepend_relative_list(list, data, lnear);
866 * @brief Remove the first instance of the specified data from the given list.
868 * @param list The given list.
869 * @param data The specified data.
870 * @return A list pointer.
872 * This function removes the first instance of @p data from
873 * @p list. If the specified data is not in the given list (tihis
874 * include the case where @p data is @c NULL), nothing is done. If
875 * @p list is @c NULL, @c NULL is returned, otherwise a new list
876 * pointer that should be used in place of the one passed to this
880 eina_list_remove(Eina_List *list, const void *data)
884 if (list) EINA_MAGIC_CHECK_LIST(list, NULL);
886 l = eina_list_data_find_list(list, data);
887 return eina_list_remove_list(list, l);
891 * @brief Remove the specified data.
893 * @param list The given linked list.
894 * @param remove_list The list node which is to be removed.
895 * @return A list pointer.
897 * This function removes the list node @p remove_list from @p list and
898 * frees the list node structure @p remove_list. If @p list is
899 * @c NULL, this function returns @c NULL. If @p remove_list is
900 * @c NULL, it returns @p list, otherwise, a new list pointer that
901 * should be used in place of the one passed to this function.
903 * The following code gives an example (notice we use EINA_LIST_FOREACH
904 * instead of EINA_LIST_FOREACH_SAFE because we stop the loop after
905 * removing the current node).
908 * extern Eina_List *list;
910 * extern void *my_data;
913 * EINA_LIST_FOREACH(list, l, data)
915 * if (data == my_data)
917 * list = eina_list_remove_list(list, l);
924 eina_list_remove_list(Eina_List *list, Eina_List *remove_list)
928 if (!list) return NULL;
929 if (!remove_list) return list;
931 EINA_MAGIC_CHECK_LIST(remove_list, NULL);
933 if (remove_list->next) remove_list->next->prev = remove_list->prev;
934 if (remove_list->prev)
936 remove_list->prev->next = remove_list->next;
940 return_l = remove_list->next;
941 if (remove_list == remove_list->accounting->last)
943 EINA_MAGIC_CHECK_LIST(list, NULL);
944 list->accounting->last = remove_list->prev;
946 _eina_list_mempool_list_free(remove_list);
951 * @brief Free an entire list and all the nodes, ignoring the data contained.
953 * @param list The list to free
954 * @return A NULL pointer
956 * This function frees all the nodes of @p list. It does not free the
957 * data of the nodes. To free them, use #EINA_LIST_FREE.
960 eina_list_free(Eina_List *list)
962 Eina_List *l, *free_l;
964 if (!list) return NULL;
966 EINA_MAGIC_CHECK_LIST(list, NULL);
973 _eina_list_mempool_list_free(free_l);
980 * @brief Move the specified data to the head of the list.
982 * @param list The list handle to move the data.
983 * @param move_list The list node to move.
984 * @return A new list handle to replace the old one
986 * This function move @p move_list to the front of @p list. If list is
987 * @c NULL, @c NULL is returned. If @p move_list is @c NULL,
988 * @p list is returned. Otherwise, a new list pointer that should be
989 * used in place of the one passed to this function.
993 * extern Eina_List *list;
995 * extern void *my_data;
998 * EINA_LIST_FOREACH(list, l, data)
1000 * if (data == my_data)
1002 * list = eina_list_promote_list(list, l);
1009 eina_list_promote_list(Eina_List *list, Eina_List *move_list)
1011 if (!list) return NULL;
1012 if (!move_list) return list;
1013 /* Promoting head to be head. */
1014 if (move_list == list) return list;
1015 if (move_list->next == list) return move_list;
1017 EINA_MAGIC_CHECK_LIST(list, NULL);
1018 EINA_MAGIC_CHECK_LIST(move_list, NULL);
1020 /* Remove the promoted item from the list. */
1021 if (!move_list->prev)
1022 move_list->next->prev = NULL;
1025 move_list->prev->next = move_list->next;
1026 if (move_list == list->accounting->last)
1027 list->accounting->last = move_list->prev;
1029 move_list->next->prev = move_list->prev;
1032 /* Add the promoted item in the list. */
1033 move_list->next = list;
1034 move_list->prev = list->prev;
1035 list->prev = move_list;
1036 if (move_list->prev)
1037 move_list->prev->next = move_list;
1043 * @brief Move the specified data to the tail of the list.
1045 * @param list The list handle to move the data.
1046 * @param move_list The list node to move.
1047 * @return A new list handle to replace the old one
1049 * This function move @p move_list to the back of @p list. If list is
1050 * @c NULL, @c NULL is returned. If @p move_list is @c NULL,
1051 * @p list is returned. Otherwise, a new list pointer that should be
1052 * used in place of the one passed to this function.
1056 * extern Eina_List *list;
1058 * extern void *my_data;
1061 * EINA_LIST_FOREACH(list, l, data)
1063 * if (data == my_data)
1065 * list = eina_list_demote_list(list, l);
1072 eina_list_demote_list(Eina_List *list, Eina_List *move_list)
1074 if (!list) return NULL;
1075 if (!move_list) return list;
1076 /* Demoting tail to be tail. */
1077 if (move_list == list->accounting->last) return list;
1079 EINA_MAGIC_CHECK_LIST(list, NULL);
1080 EINA_MAGIC_CHECK_LIST(move_list, NULL);
1082 /* Update pointer list if necessary. */
1083 if (list == move_list)
1084 list = move_list->next;
1085 /* Remove the demoted item from the list. */
1086 if (move_list->prev)
1087 move_list->prev->next = move_list->next;
1088 move_list->next->prev = move_list->prev;
1089 /* Add the demoted item in the list. */
1090 move_list->prev = list->accounting->last;
1091 move_list->prev->next = move_list;
1092 move_list->next = NULL;
1093 list->accounting->last = move_list;
1099 * @brief Find a member of a list and return the member.
1101 * @param list The list to search for a data.
1102 * @param data The data pointer to find in the list.
1103 * @return The found member data pointer if foun, @c NULL otherwise.
1105 * This function searches in @p list from beginning to end for the
1106 * first member whose data pointer is @p data. If it is found, @p data
1107 * will be returned, otherwise NULL will be returned.
1111 * extern Eina_List *list;
1112 * extern void *my_data;
1114 * if (eina_list_data_find(list, my_data) == my_data)
1116 * printf("Found member %p\n", my_data);
1121 eina_list_data_find(const Eina_List *list, const void *data)
1123 if (eina_list_data_find_list(list, data)) return (void*) data;
1128 * @brief Find a member of a list and return the list node containing that member.
1130 * @param list The list to search for data.
1131 * @param data The data pointer to find in the list.
1132 * @return The found members list node on success, @c NULL otherwise.
1134 * This function searches in @p list from beginning to end for the
1135 * first member whose data pointer is @p data. If it is found, the
1136 * list node containing the specified member is returned, otherwise
1137 * @c NULL is returned.
1140 eina_list_data_find_list(const Eina_List *list, const void *data)
1145 if (list) EINA_MAGIC_CHECK_LIST(list, NULL);
1147 EINA_LIST_FOREACH(list, l, list_data)
1149 if (list_data == data) return (Eina_List *)l;
1156 * @brief Get the nth member's data pointer in a list.
1158 * @param list The list to get the specified member number from.
1159 * @param n The number of the element (0 being the first).
1160 * @return The data pointer stored in the specified element.
1162 * This function returns the data pointer of element number @p n, in
1163 * the @p list. The first element in the array is element number 0. If
1164 * the element number @p n does not exist, @c NULL is
1165 * returned. Otherwise, the data of the found element is returned.
1168 eina_list_nth(const Eina_List *list, unsigned int n)
1172 l = eina_list_nth_list(list, n);
1173 return l ? l->data : NULL;
1177 * @brief Get the nth member's list node in a list.
1179 * @param list The list to get the specfied member number from.
1180 * @param n The number of the element (0 being the first).
1181 * @return The list node stored in the numbered element.
1183 * This function returns the list node of element number @p n, in
1184 * @ list. The first element in the array is element number 0. If the
1185 * element number @p n does not exist or @p list is @c NULL or @p n is
1186 * greater than the count of elements in @p list minus 1, @c NULL is
1187 * returned. Otherwise the list node stored in the numbered element is
1191 eina_list_nth_list(const Eina_List *list, unsigned int n)
1196 if (list) EINA_MAGIC_CHECK_LIST(list, NULL);
1198 /* check for non-existing nodes */
1199 if ((!list) || (n > (list->accounting->count - 1)))
1202 /* if the node is in the 2nd half of the list, search from the end
1203 * else, search from the beginning.
1205 if (n > (list->accounting->count / 2))
1207 for (i = list->accounting->count - 1,
1208 l = list->accounting->last;
1212 if (i == n) return (Eina_List *)l;
1217 for (i = 0, l = list; l; l = l->next, i++)
1219 if (i == n) return (Eina_List *)l;
1226 * @brief Get the last list node in the list.
1228 * @param list The list to get the last list node from.
1229 * @return The last list node in the list.
1231 * This function returns the last list node in the list. If @p list is
1232 * @c NULL or empty, @c NULL is returned.
1234 * This is a order-1 operation (it takes the same short time
1235 * regardless of the length of the list).
1237 static inline Eina_List *eina_list_last(const Eina_List *list);
1240 * @brief Get the next list node after the specified list node.
1242 * @param list The list node to get the next list node from
1243 * @return The next list node on success, @c NULL otherwise.
1245 * This function returns the next list node after the current one in
1246 * @p list. It is equivalent to list->next. If @p list is @c NULL or
1247 * if no next list node exists, it returns @c NULL.
1249 static inline Eina_List *eina_list_next(const Eina_List *list);
1252 * @brief Get the previous list node before the specified list node.
1254 * @param list The list node to get the previous list node from.
1255 * @return The previous list node o success, @c NULL otherwise.
1256 * if no previous list node exists
1258 * This function returns the previous list node before the current one
1259 * in @p list. It is equivalent to list->prev. If @p list is @c NULL or
1260 * if no previous list node exists, it returns @c NULL.
1262 static inline Eina_List *eina_list_prev(const Eina_List *list);
1265 * @brief Get the list node data member.
1267 * @param list The list node to get the data member of.
1268 * @return The data member from the list node.
1270 * This function returns the data member of the specified list node @p
1271 * list. It is equivalent to list->data. If @p list is @c NULL, this
1272 * function returns @c NULL.
1274 static inline void *eina_list_data_get(const Eina_List *list);
1277 * @brief Get the count of the number of items in a list.
1279 * @param list The list whose count to return.
1280 * @return The number of members in the list.
1282 * This function returns how many members @p list contains. If the
1283 * list is @c NULL, 0 is returned.
1285 * NB: This is an order-1 operation and takes the same tiem regardless
1286 * of the length of the list.
1288 static inline unsigned int eina_list_count(const Eina_List *list);
1291 * @brief Reverse all the elements in the list.
1293 * @param list The list to reverse.
1294 * @return The list head after it has been reversed.
1296 * This function reverses the order of all elements in @p list, so the
1297 * last member is now first, and so on. If @p list is @c NULL, this
1298 * functon returns @c NULL.
1300 * @note @b in-place: this will change the given list, so you should
1301 * now point to the new list head that is returned by this function.
1303 * @see eina_list_reverse_clone()
1304 * @see eina_list_iterator_reversed_new()
1307 eina_list_reverse(Eina_List *list)
1311 if (!list) return NULL;
1313 EINA_MAGIC_CHECK_LIST(list, NULL);
1316 l2 = list->accounting->last;
1322 l1->data = l2->data;
1325 if (l1 == l2) break;
1333 * @brief Clone (copy) all the elements in the list in reverse order.
1335 * @param list The list to reverse.
1336 * @return The new list that has been reversed.
1338 * This function reverses the order of all elements in @p list, so the
1339 * last member is now first, and so on. If @p list is @c NULL, this
1340 * functon returns @c NULL. This returns a copy of the given list.
1342 * @note @b copy: this will copy the list and you should then
1343 * eina_list_free() when it is not required anymore.
1345 * @see eina_list_reverse()
1346 * @see eina_list_clone()
1349 eina_list_reverse_clone(const Eina_List *list)
1355 if (!list) return NULL;
1357 EINA_MAGIC_CHECK_LIST(list, NULL);
1360 EINA_LIST_FOREACH(list, l, data)
1361 clone = eina_list_prepend(clone, data);
1367 * @brief Clone (copy) all the elements in the list in exact order.
1369 * @param list The list to clone.
1370 * @return The new list that has been cloned.
1372 * This function clone in order of all elements in @p list. If @p list
1373 * is @c NULL, this functon returns @c NULL. This returns a copy of
1376 * @note @b copy: this will copy the list and you should then
1377 * eina_list_free() when it is not required anymore.
1379 * @see eina_list_reverse_clone()
1382 eina_list_clone(const Eina_List *list)
1388 if (!list) return NULL;
1390 EINA_MAGIC_CHECK_LIST(list, NULL);
1393 EINA_LIST_FOREACH(list, l, data)
1394 clone = eina_list_append(clone, data);
1400 * @brief Sort a list according to the ordering func will return.
1402 * @param list The list handle to sort.
1403 * @param size The length of the list to sort.
1404 * @param func A function pointer that can handle comparing the list data
1406 * @return the new head of list.
1408 * This function sorts @p list. @p size if the number of the first
1409 * element to sort. If @p size is 0 or greater than the number of
1410 * elements in @p list, all the elemnts are sorted. @p func is used to
1411 * compare two elements of @p list. If @p list or @p func are @c NULL,
1412 * this function returns @c NULL.
1414 * @note @b in-place: this will change the given list, so you should
1415 * now point to the new list head that is returned by this function.
1417 * @note worst case is O(n * log2(n)) comparisons (calls to func()),
1418 * O(n) comparisons average case. That means that for 1,000,000 list
1419 * elements, sort will usually do 1,000,000 comparisons, but may do up
1425 * sort_cb(const void *d1, const void *d2)
1427 * const char *txt = NULL;
1428 * const char *txt2 = NULL;
1430 * if(!d1) return(1);
1431 * if(!d2) return(-1);
1433 * return(strcmp((const char*)d1, (const char*)d2));
1435 * extern Eina_List *list;
1437 * list = eina_list_sort(list, eina_list_count(list), sort_cb);
1441 eina_list_sort(Eina_List *list, unsigned int size, Eina_Compare_Cb func)
1445 Eina_List *tail = list;
1446 Eina_List *unsort = NULL;
1447 Eina_List *stack[EINA_LIST_SORT_STACK_SIZE];
1449 EINA_SAFETY_ON_NULL_RETURN_VAL(func, list);
1450 if (!list) return NULL;
1451 EINA_MAGIC_CHECK_LIST(list, NULL);
1453 /* if the caller specified an invalid size, sort the whole list */
1455 (size > list->accounting->count))
1456 size = list->accounting->count;
1458 if (size != list->accounting->count)
1460 unsort = eina_list_nth_list(list, size);
1462 unsort->prev->next = NULL;
1467 unsigned int idx, tmp;
1469 Eina_List *a = tail;
1470 Eina_List *b = tail->next;
1480 if (func(a->data, b->data) < 0)
1481 ((stack[i++] = a)->next = b)->next = 0;
1483 ((stack[i++] = b)->next = a)->next = 0;
1486 for (idx = n ^ tmp; idx &= idx - 1; i--)
1487 stack[i-2] = eina_list_sort_merge(stack[i-2], stack[i-1], func);
1491 stack[i-1] = eina_list_sort_merge(stack[i-1], stack[i], func);
1494 tail = eina_list_sort_rebuild_prev(list);
1498 tail->next = unsort;
1499 unsort->prev = tail;
1502 list->accounting->last = tail;
1508 * @brief Merge two list.
1510 * @param left Head list to merge.
1511 * @param right Tail list to merge.
1512 * @return A new merged list.
1514 * This function put right at the end of left and return the head.
1516 * Both left and right does not exist anymore after the merge.
1518 * @note merge cost is O(n), being @b n the size of the smallest
1519 * list. This is due the need to fix accounting of that segment,
1520 * making count and last access O(1).
1523 eina_list_merge(Eina_List *left, Eina_List *right)
1525 unsigned int n_left, n_right;
1527 if (!left) return right;
1528 if (!right) return left;
1530 left->accounting->last->next = right;
1531 right->prev = left->accounting->last;
1533 n_left = left->accounting->count;
1534 n_right = right->accounting->count;
1536 if (n_left >= n_right)
1538 Eina_List *itr = right;
1539 left->accounting->last = right->accounting->last;
1540 left->accounting->count += n_right;
1542 _eina_list_mempool_accounting_free(right->accounting);
1546 itr->accounting = left->accounting;
1553 Eina_List *itr = left->accounting->last;
1554 right->accounting->count += n_left;
1556 _eina_list_mempool_accounting_free(left->accounting);
1560 itr->accounting = right->accounting;
1570 * @brief Merge two sorted list according to the ordering func will return.
1572 * @param left First list to merge.
1573 * @param right Second list to merge.
1574 * @param func A function pointer that can handle comparing the list data
1576 * @return A new sorted list.
1578 * This function compare the head of @p left and @p right, and choose the
1579 * smallest one to be head of the returned list. It will continue this process
1580 * for all entry of both list.
1582 * Both left and right does not exist anymore after the merge.
1583 * If @p func is NULL, it will return NULL.
1588 * sort_cb(void *d1, void *d2)
1590 * const char *txt = NULL;
1591 * const char *txt2 = NULL;
1593 * if(!d1) return(1);
1594 * if(!d2) return(-1);
1596 * return(strcmp((const char*)d1, (const char*)d2));
1598 * extern Eina_List *sorted1;
1599 * extern Eina_List *sorted2;
1601 * list = eina_list_sorted_merge(sorted1, sorted2, sort_cb);
1605 eina_list_sorted_merge(Eina_List *left, Eina_List *right, Eina_Compare_Cb func)
1610 EINA_SAFETY_ON_NULL_RETURN_VAL(func, NULL);
1612 if (!left) return right;
1613 if (!right) return left;
1615 if (func(left->data, right->data) < 0)
1620 ret->accounting->count += right->accounting->count;
1622 _eina_list_mempool_accounting_free(right->accounting);
1628 right = right->next;
1629 ret->accounting->count += left->accounting->count;
1631 _eina_list_mempool_accounting_free(left->accounting);
1634 while (left && right)
1636 if (func(left->data, right->data) < 0)
1638 current->next = left;
1639 left->prev = current;
1644 current->next = right;
1645 right->prev = current;
1646 right = right->next;
1649 current = current->next;
1650 current->accounting = ret->accounting;
1655 current->next = left;
1656 left->prev = current;
1657 current->accounting = ret->accounting;
1662 current->next = right;
1663 right->prev = current;
1664 current->accounting = ret->accounting;
1667 while (current->next)
1669 current = current->next;
1670 current->accounting = ret->accounting;
1673 ret->accounting->last = current;
1679 * @brief Returns node nearest to data is in the sorted list.
1681 * @param list The list to search for data, @b must be sorted.
1682 * @param func A function pointer that can handle comparing the list data nodes.
1683 * @param data reference value to search.
1684 * @param result_cmp if provided returns the result of
1685 * func(node->data, data) node being the last (returned) node. If node
1686 * was found (exact match), then it is 0. If returned node is smaller
1687 * than requested data, it is less than 0 and if it's bigger it's
1688 * greater than 0. It is the last value returned by func().
1689 * @return the nearest node, NULL if not found.
1691 * This can be used to check if some value is inside the list and get
1692 * the nearest container node in this case. It should be used when list is
1693 * known to be sorted as it will do binary search for results.
1695 * Example: imagine user gives a string, you check if it's in the list
1696 * before duplicating its contents, otherwise you want to insert it
1697 * sorted. In this case you get the result of this function and either
1698 * append or prepend the value.
1700 * @note O(log2(n)) average/worst case performance, for 1,000,000
1701 * elements it will do a maximum of 20 comparisons. This is much
1702 * faster than the 1,000,000 comparisons made naively walking the list
1703 * from head to tail, so depending on the number of searches and
1704 * insertions, it may be worth to eina_list_sort() the list and do he
1705 * searches later. As lists do not have O(1) access time, walking to
1706 * the correct node can be costly, consider worst case to be almost
1707 * O(n) pointer dereference (list walk).
1709 * @see eina_list_search_sorted_list()
1710 * @see eina_list_sort()
1711 * @see eina_list_sorted_merge()
1714 eina_list_search_sorted_near_list(const Eina_List *list, Eina_Compare_Cb func, const void *data, int *result_cmp)
1716 const Eina_List *ct;
1717 unsigned int inf, sup, cur;
1722 if (result_cmp) *result_cmp = 0;
1726 if (list->accounting->count == 1)
1728 if (result_cmp) *result_cmp = func(list->data, data);
1729 return (Eina_List *)list;
1732 /* list walk is expensive, do quick check: tail */
1733 ct = list->accounting->last;
1734 cmp = func(ct->data, data);
1738 /* list walk is expensive, do quick check: head */
1740 cmp = func(ct->data, data);
1744 /* inclusive bounds */
1746 sup = list->accounting->count - 2;
1750 /* no loop, just compare if comparison value is important to caller */
1753 if (result_cmp) cmp = func(ct->data, data);
1759 unsigned int tmp = cur;
1760 cur = inf + ((sup - inf) >> 1);
1761 if (tmp < cur) for (; tmp != cur; tmp++, ct = ct->next);
1762 else if (tmp > cur) for (; tmp != cur; tmp--, ct = ct->prev);
1764 cmp = func(ct->data, data);
1779 if (result_cmp) *result_cmp = cmp;
1780 return (Eina_List *)ct;
1784 * @brief Returns node if data is in the sorted list.
1786 * @param list The list to search for data, @b must be sorted.
1787 * @param func A function pointer that can handle comparing the list data nodes.
1788 * @param data reference value to search.
1789 * @return the node if func(node->data, data) == 0, NULL if not found.
1791 * This can be used to check if some value is inside the list and get
1792 * the container node in this case. It should be used when list is
1793 * known to be sorted as it will do binary search for results.
1795 * Example: imagine user gives a string, you check if it's in the list
1796 * before duplicating its contents.
1798 * @note O(log2(n)) average/worst case performance, for 1,000,000
1799 * elements it will do a maximum of 20 comparisons. This is much
1800 * faster than the 1,000,000 comparisons made by
1801 * eina_list_search_unsorted_list(), so depending on the number of
1802 * searches and insertions, it may be worth to eina_list_sort() the
1803 * list and do he searches later. As said in
1804 * eina_list_search_sorted_near_list(), lists do not have O(1) access
1805 * time, so walking to the correct node can be costly, consider worst
1806 * case to be almost O(n) pointer dereference (list walk).
1808 * @see eina_list_search_sorted()
1809 * @see eina_list_sort()
1810 * @see eina_list_sorted_merge()
1811 * @see eina_list_search_unsorted_list()
1812 * @see eina_list_search_sorted_near_list()
1815 eina_list_search_sorted_list(const Eina_List *list, Eina_Compare_Cb func, const void *data)
1820 lnear = eina_list_search_sorted_near_list(list, func, data, &cmp);
1821 if (!lnear) return NULL;
1829 * @brief Returns node data if it is in the sorted list.
1831 * @param list The list to search for data, @b must be sorted.
1832 * @param func A function pointer that can handle comparing the list data nodes.
1833 * @param data reference value to search.
1834 * @return the node value (@c node->data) if func(node->data, data) == 0,
1835 * NULL if not found.
1837 * This can be used to check if some value is inside the list and get
1838 * the existing instance in this case. It should be used when list is
1839 * known to be sorted as it will do binary search for results.
1841 * Example: imagine user gives a string, you check if it's in the list
1842 * before duplicating its contents.
1844 * @note O(log2(n)) average/worst case performance, for 1,000,000
1845 * elements it will do a maximum of 20 comparisons. This is much
1846 * faster than the 1,000,000 comparisons made by
1847 * eina_list_search_unsorted(), so depending on the number of
1848 * searches and insertions, it may be worth to eina_list_sort() the
1849 * list and do he searches later. As said in
1850 * eina_list_search_sorted_near_list(), lists do not have O(1) access
1851 * time, so walking to the correct node can be costly, consider worst
1852 * case to be almost O(n) pointer dereference (list walk).
1854 * @see eina_list_search_sorted_list()
1855 * @see eina_list_sort()
1856 * @see eina_list_sorted_merge()
1857 * @see eina_list_search_unsorted_list()
1860 eina_list_search_sorted(const Eina_List *list, Eina_Compare_Cb func, const void *data)
1862 return eina_list_data_get(eina_list_search_sorted_list(list, func, data));
1866 * @brief Returns node if data is in the unsorted list.
1868 * @param list The list to search for data, may be unsorted.
1869 * @param func A function pointer that can handle comparing the list data nodes.
1870 * @param data reference value to search.
1871 * @return the node if func(node->data, data) == 0, NULL if not found.
1873 * This can be used to check if some value is inside the list and get
1874 * the container node in this case.
1876 * Example: imagine user gives a string, you check if it's in the list
1877 * before duplicating its contents.
1879 * @note this is expensive and may walk the whole list, it's order-N,
1880 * that is for 1,000,000 elements list it may walk and compare
1883 * @see eina_list_search_sorted_list()
1884 * @see eina_list_search_unsorted()
1887 eina_list_search_unsorted_list(const Eina_List *list, Eina_Compare_Cb func, const void *data)
1892 EINA_LIST_FOREACH(list, l, d)
1895 return (Eina_List*) l;
1901 * @brief Returns node data if it is in the unsorted list.
1903 * @param list The list to search for data, may be unsorted.
1904 * @param func A function pointer that can handle comparing the list data nodes.
1905 * @param data reference value to search.
1906 * @return the node value (@c node->data) if func(node->data, data) == 0,
1907 * NULL if not found.
1909 * This can be used to check if some value is inside the list and get
1910 * the existing instance in this case.
1912 * Example: imagine user gives a string, you check if it's in the list
1913 * before duplicating its contents.
1915 * @note this is expensive and may walk the whole list, it's order-N,
1916 * that is for 1,000,000 elements list it may walk and compare
1919 * @see eina_list_search_sorted()
1920 * @see eina_list_search_unsorted_list()
1923 eina_list_search_unsorted(const Eina_List *list, Eina_Compare_Cb func, const void *data)
1925 return eina_list_data_get(eina_list_search_unsorted_list(list, func, data));
1930 * @brief Returned a new iterator asociated to a list.
1932 * @param list The list.
1933 * @return A new iterator.
1935 * This function returns a newly allocated iterator associated to @p
1936 * list. If @p list is @c NULL or the count member of @p list is less
1937 * or equal than 0, this function still returns a valid iterator that
1938 * will always return false on eina_iterator_next(), thus keeping API
1941 * If the memory can not be allocated, NULL is returned and
1942 * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
1945 * @warning if the list structure changes then the iterator becomes
1946 * invalid! That is, if you add or remove nodes this iterator
1947 * behavior is undefined and your program may crash!
1949 EAPI Eina_Iterator *
1950 eina_list_iterator_new(const Eina_List *list)
1952 Eina_Iterator_List *it;
1955 it = calloc(1, sizeof (Eina_Iterator_List));
1957 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1961 EINA_MAGIC_SET(it, EINA_MAGIC_LIST_ITERATOR);
1962 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1967 it->iterator.next = FUNC_ITERATOR_NEXT(eina_list_iterator_next);
1968 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(eina_list_iterator_get_container);
1969 it->iterator.free = FUNC_ITERATOR_FREE(eina_list_iterator_free);
1971 return &it->iterator;
1975 * @brief Returned a new reversed iterator asociated to a list.
1977 * @param list The list.
1978 * @return A new iterator.
1980 * This function returns a newly allocated iterator associated to @p
1981 * list. If @p list is @c NULL or the count member of @p list is less
1982 * or equal than 0, this function still returns a valid iterator that
1983 * will always return false on eina_iterator_next(), thus keeping API
1986 * Unlike eina_list_iterator_new(), this will walk the list backwards.
1988 * If the memory can not be allocated, NULL is returned and
1989 * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
1992 * @warning if the list structure changes then the iterator becomes
1993 * invalid! That is, if you add or remove nodes this iterator
1994 * behavior is undefined and your program may crash!
1996 EAPI Eina_Iterator *
1997 eina_list_iterator_reversed_new(const Eina_List *list)
1999 Eina_Iterator_List *it;
2002 it = calloc(1, sizeof (Eina_Iterator_List));
2004 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
2008 EINA_MAGIC_SET(it, EINA_MAGIC_LIST_ITERATOR);
2009 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
2011 it->head = eina_list_last(list);
2012 it->current = it->head;
2014 it->iterator.next = FUNC_ITERATOR_NEXT(eina_list_iterator_prev);
2015 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(eina_list_iterator_get_container);
2016 it->iterator.free = FUNC_ITERATOR_FREE(eina_list_iterator_free);
2018 return &it->iterator;
2022 * @brief Returned a new accessor asociated to a list.
2024 * @param list The list.
2025 * @return A new accessor.
2027 * This function returns a newly allocated accessor associated to
2028 * @p list. If @p list is @c NULL or the count member of @p list is
2029 * less or equal than 0, this function returns NULL. If the memory can
2030 * not be allocated, NULL is returned and #EINA_ERROR_OUT_OF_MEMORY is
2031 * set. Otherwise, a valid accessor is returned.
2033 EAPI Eina_Accessor *
2034 eina_list_accessor_new(const Eina_List *list)
2036 Eina_Accessor_List *it;
2039 it = calloc(1, sizeof (Eina_Accessor_List));
2041 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
2045 EINA_MAGIC_SET(it, EINA_MAGIC_LIST_ACCESSOR);
2046 EINA_MAGIC_SET(&it->accessor, EINA_MAGIC_ACCESSOR);
2052 it->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_list_accessor_get_at);
2053 it->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER(eina_list_accessor_get_container);
2054 it->accessor.free = FUNC_ACCESSOR_FREE(eina_list_accessor_free);
2056 return &it->accessor;