/* EINA - EFL data type library
* Copyright (C) 2002-2008 Carsten Haitzler, Gustavo Sverzut Barbieri, Tilman Sauerbeck,
* Vincent Torri, Cedric Bail, Jorge Luis Zapata Muga,
* Corey Donohoe, Arnaud de Turckheim, Alexandre Becoulet
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library;
* if not, see <http://www.gnu.org/licenses/>.
*
* This file incorporates work covered by the following copyright and
* permission notice:
*
* Copyright (C) 2004 ncn
* Copyright (C) 2006 Sebastian Dransfeld
* Copyright (C) 2007 Christopher Michael
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to
* deal in the Software without restriction, including without limitation the
* rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
* sell copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
* The above copyright notice and this permission notice shall be included in
* all copies of the Software and its Copyright notices. In addition publicly
* documented acknowledgment must be given that this software has been used if no
* source code of this software is made available publicly. This includes
* acknowledgments in either Copyright notices, Manuals, Publicity and Marketing
* documents or any documentation provided with any product containing this
* software. This License does not apply to any software that links to the
* libraries provided by this software (statically or dynamically), but only to
* the software provided.
* Please see the OLD-COPYING.PLAIN for a plain-english explanation of this notice
* and it's intent.
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
* IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#ifdef HAVE_EVIL
# include <Evil.h>
#endif
#include "eina_config.h"
#include "eina_private.h"
#include "eina_error.h"
#include "eina_log.h"
#include "eina_mempool.h"
/* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
#include "eina_safety_checks.h"
#include "eina_list.h"
/*============================================================================*
* Local *
*============================================================================*/
/**
* @cond LOCAL
*/
static const char EINA_MAGIC_LIST_STR[] = "Eina List";
static const char EINA_MAGIC_LIST_ITERATOR_STR[] = "Eina List Iterator";
static const char EINA_MAGIC_LIST_ACCESSOR_STR[] = "Eina List Accessor";
static const char EINA_MAGIC_LIST_ACCOUNTING_STR[] = "Eina List Accounting";
#define EINA_MAGIC_CHECK_LIST(d, ...) \
do { \
if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST)) \
{ \
EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST); \
return __VA_ARGS__; \
} \
} while(0)
#define EINA_MAGIC_CHECK_LIST_ITERATOR(d, ...) \
do { \
if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ITERATOR)) \
{ \
EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ITERATOR); \
return __VA_ARGS__; \
} \
} while(0)
#define EINA_MAGIC_CHECK_LIST_ACCESSOR(d, ...) \
do { \
if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ACCESSOR)) \
{ \
EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ACCESSOR); \
return __VA_ARGS__; \
} \
} while(0)
#define EINA_MAGIC_CHECK_LIST_ACCOUNTING(d) \
do { \
if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ACCOUNTING)) \
{ \
EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ACCOUNTING); \
return; \
} \
} while(0)
#define EINA_LIST_SORT_STACK_SIZE 32
typedef struct _Eina_Iterator_List Eina_Iterator_List;
typedef struct _Eina_Accessor_List Eina_Accessor_List;
struct _Eina_Iterator_List
{
Eina_Iterator iterator;
const Eina_List *head;
const Eina_List *current;
EINA_MAGIC
};
struct _Eina_Accessor_List
{
Eina_Accessor accessor;
const Eina_List *head;
const Eina_List *current;
unsigned int index;
EINA_MAGIC
};
static Eina_Mempool *_eina_list_mp = NULL;
static Eina_Mempool *_eina_list_accounting_mp = NULL;
static int _eina_list_log_dom = -1;
#ifdef ERR
#undef ERR
#endif
#define ERR(...) EINA_LOG_DOM_ERR(_eina_list_log_dom, __VA_ARGS__)
#ifdef DBG
#undef DBG
#endif
#define DBG(...) EINA_LOG_DOM_DBG(_eina_list_log_dom, __VA_ARGS__)
static inline Eina_List_Accounting *
_eina_list_mempool_accounting_new(__UNUSED__ Eina_List *list)
{
Eina_List_Accounting *tmp;
tmp =
eina_mempool_malloc(_eina_list_accounting_mp,
sizeof (Eina_List_Accounting));
if (!tmp)
return NULL;
EINA_MAGIC_SET(tmp, EINA_MAGIC_LIST_ACCOUNTING);
return tmp;
}
static inline void
_eina_list_mempool_accounting_free(Eina_List_Accounting *accounting)
{
EINA_MAGIC_CHECK_LIST_ACCOUNTING(accounting);
EINA_MAGIC_SET(accounting, EINA_MAGIC_NONE);
eina_mempool_free(_eina_list_accounting_mp, accounting);
}
static inline Eina_List *
_eina_list_mempool_list_new(__UNUSED__ Eina_List *list)
{
Eina_List *tmp;
tmp = eina_mempool_malloc(_eina_list_mp, sizeof (Eina_List));
if (!tmp)
return NULL;
EINA_MAGIC_SET(tmp, EINA_MAGIC_LIST);
return tmp;
}
static inline void
_eina_list_mempool_list_free(Eina_List *list)
{
EINA_MAGIC_CHECK_LIST(list);
list->accounting->count--;
if (list->accounting->count == 0)
_eina_list_mempool_accounting_free(list->accounting);
EINA_MAGIC_SET(list, EINA_MAGIC_NONE);
eina_mempool_free(_eina_list_mp, list);
}
static Eina_List *
_eina_list_setup_accounting(Eina_List *list)
{
EINA_MAGIC_CHECK_LIST(list, NULL);
list->accounting = _eina_list_mempool_accounting_new(list);
if (!list->accounting)
goto on_error;
list->accounting->last = list;
list->accounting->count = 1;
return list;
on_error:
_eina_list_mempool_list_free(list);
return NULL;
}
static inline void
_eina_list_update_accounting(Eina_List *list, Eina_List *new_list)
{
EINA_MAGIC_CHECK_LIST(list);
EINA_MAGIC_CHECK_LIST(new_list);
list->accounting->count++;
new_list->accounting = list->accounting;
}
#if 0
static Eina_Mempool2 _eina_list_mempool =
{
sizeof(Eina_List),
320,
0, NULL, NULL
};
static Eina_Mempool2 _eina_list_accounting_mempool =
{
sizeof(Eina_List_Accounting),
80,
0, NULL, NULL
};
#endif
static Eina_Bool
eina_list_iterator_next(Eina_Iterator_List *it, void **data)
{
EINA_MAGIC_CHECK_LIST_ITERATOR(it, EINA_FALSE);
if (!it->current)
return EINA_FALSE;
*data = eina_list_data_get(it->current);
it->current = eina_list_next(it->current);
return EINA_TRUE;
}
static Eina_Bool
eina_list_iterator_prev(Eina_Iterator_List *it, void **data)
{
EINA_MAGIC_CHECK_LIST_ITERATOR(it, EINA_FALSE);
if (!it->current)
return EINA_FALSE;
*data = eina_list_data_get(it->current);
it->current = eina_list_prev(it->current);
return EINA_TRUE;
}
static Eina_List *
eina_list_iterator_get_container(Eina_Iterator_List *it)
{
EINA_MAGIC_CHECK_LIST_ITERATOR(it, NULL);
return (Eina_List *)it->head;
}
static void
eina_list_iterator_free(Eina_Iterator_List *it)
{
EINA_MAGIC_CHECK_LIST_ITERATOR(it);
MAGIC_FREE(it);
}
static Eina_Bool
eina_list_accessor_get_at(Eina_Accessor_List *it, unsigned int idx, void **data)
{
const Eina_List *over;
unsigned int middle;
unsigned int i;
EINA_MAGIC_CHECK_LIST_ACCESSOR(it, EINA_FALSE);
if (idx >= eina_list_count(it->head))
return EINA_FALSE;
if (it->index == idx)
over = it->current;
else if (idx > it->index)
{
/* After current position. */
middle = ((eina_list_count(it->head) - it->index) >> 1) + it->index;
if (idx > middle)
/* Go backward from the end. */
for (i = eina_list_count(it->head) - 1,
over = eina_list_last(it->head);
i > idx && over;
--i, over = eina_list_prev(over))
;
else
/* Go forward from current. */
for (i = it->index, over = it->current;
i < idx && over;
++i, over = eina_list_next(over))
;
}
else
{
/* Before current position. */
middle = it->index >> 1;
if (idx > middle)
/* Go backward from current. */
for (i = it->index, over = it->current;
i > idx && over;
--i, over = eina_list_prev(over))
;
else
/* Go forward from start. */
for (i = 0, over = it->head;
i < idx && over;
++i, over = eina_list_next(over))
;
}
if (!over)
return EINA_FALSE;
it->current = over;
it->index = idx;
*data = eina_list_data_get(it->current);
return EINA_TRUE;
}
static Eina_List *
eina_list_accessor_get_container(Eina_Accessor_List *it)
{
EINA_MAGIC_CHECK_LIST_ACCESSOR(it, NULL);
return (Eina_List *)it->head;
}
static void
eina_list_accessor_free(Eina_Accessor_List *it)
{
EINA_MAGIC_CHECK_LIST_ACCESSOR(it);
MAGIC_FREE(it);
}
static Eina_List *
eina_list_sort_rebuild_prev(Eina_List *list)
{
Eina_List *prev = NULL;
EINA_MAGIC_CHECK_LIST(list, NULL);
for (; list; list = list->next)
{
list->prev = prev;
prev = list;
}
return prev;
}
static Eina_List *
eina_list_sort_merge(Eina_List *a, Eina_List *b, Eina_Compare_Cb func)
{
Eina_List *first, *last;
if (func(a->data, b->data) < 0)
a = (last = first = a)->next;
else
b = (last = first = b)->next;
while (a && b)
if (func(a->data, b->data) < 0)
a = (last = last->next = a)->next;
else
b = (last = last->next = b)->next;
last->next = a ? a : b;
return first;
}
/**
* @endcond
*/
/*============================================================================*
* Global *
*============================================================================*/
/**
* @internal
* @brief Initialize the list module.
*
* @return #EINA_TRUE on success, #EINA_FALSE on failure.
*
* This function sets up the list module of Eina. It is called by
* eina_init().
*
* This function creates mempool to speed up list node and accounting
* management, using EINA_MEMPOOL environment variable if it is set to
* choose the memory pool type to use.
*
* @see eina_init()
*/
Eina_Bool
eina_list_init(void)
{
const char *choice, *tmp;
_eina_list_log_dom = eina_log_domain_register("eina_list",
EINA_LOG_COLOR_DEFAULT);
if (_eina_list_log_dom < 0)
{
EINA_LOG_ERR("Could not register log domain: eina_list");
return EINA_FALSE;
}
#ifdef EINA_DEFAULT_MEMPOOL
choice = "pass_through";
#else
choice = "chained_mempool";
#endif
tmp = getenv("EINA_MEMPOOL");
if (tmp && tmp[0])
choice = tmp;
_eina_list_mp = eina_mempool_add
(choice, "list", NULL, sizeof(Eina_List), 320);
if (!_eina_list_mp)
{
ERR("ERROR: Mempool for list cannot be allocated in list init.");
goto on_init_fail;
}
_eina_list_accounting_mp = eina_mempool_add
(choice, "list_accounting", NULL, sizeof(Eina_List_Accounting), 80);
if (!_eina_list_accounting_mp)
{
ERR(
"ERROR: Mempool for list accounting cannot be allocated in list init.");
eina_mempool_del(_eina_list_mp);
goto on_init_fail;
}
#define EMS(n) eina_magic_string_static_set(n, n ## _STR)
EMS(EINA_MAGIC_LIST);
EMS(EINA_MAGIC_LIST_ITERATOR);
EMS(EINA_MAGIC_LIST_ACCESSOR);
EMS(EINA_MAGIC_LIST_ACCOUNTING);
#undef EMS
return EINA_TRUE;
on_init_fail:
eina_log_domain_unregister(_eina_list_log_dom);
_eina_list_log_dom = -1;
return EINA_FALSE;
}
/**
* @internal
* @brief Shut down the list module.
*
* @return #EINA_TRUE on success, #EINA_FALSE on failure.
*
* This function shuts down the list module set up by
* eina_list_init(). It is called by eina_shutdown().
*
* @see eina_shutdown()
*/
Eina_Bool
eina_list_shutdown(void)
{
eina_mempool_del(_eina_list_accounting_mp);
eina_mempool_del(_eina_list_mp);
eina_log_domain_unregister(_eina_list_log_dom);
_eina_list_log_dom = -1;
return EINA_TRUE;
}
/*============================================================================*
* API *
*============================================================================*/
EAPI Eina_List *
eina_list_append(Eina_List *list, const void *data)
{
Eina_List *l, *new_l;
eina_error_set(0);
new_l = _eina_list_mempool_list_new(list);
if (!new_l)
return list;
new_l->next = NULL;
new_l->data = (void *)data;
if (!list)
{
new_l->prev = NULL;
return _eina_list_setup_accounting(new_l);
}
EINA_MAGIC_CHECK_LIST(list, NULL);
l = list->accounting->last;
list->accounting->last = new_l;
l->next = new_l;
new_l->prev = l;
_eina_list_update_accounting(list, new_l);
return list;
}
EAPI Eina_List *
eina_list_prepend(Eina_List *list, const void *data)
{
Eina_List *new_l;
eina_error_set(0);
new_l = _eina_list_mempool_list_new(list);
if (!new_l)
return list;
new_l->prev = NULL;
new_l->next = list;
new_l->data = (void *)data;
if (!list)
return _eina_list_setup_accounting(new_l);
EINA_MAGIC_CHECK_LIST(list, NULL);
list->prev = new_l;
_eina_list_update_accounting(list, new_l);
return new_l;
}
EAPI Eina_List *
eina_list_append_relative(Eina_List *list,
const void *data,
const void *relative)
{
Eina_List *l;
void *list_data;
if (list)
EINA_MAGIC_CHECK_LIST(list, NULL);
EINA_LIST_FOREACH(list, l, list_data)
{
if (list_data == relative)
return eina_list_append_relative_list(list, data, l);
}
return eina_list_append(list, data);
}
EAPI Eina_List *
eina_list_append_relative_list(Eina_List *list,
const void *data,
Eina_List *relative)
{
Eina_List *new_l;
if ((!list) || (!relative))
return eina_list_append(list, data);
eina_error_set(0);
new_l = _eina_list_mempool_list_new(list);
if (!new_l)
return list;
EINA_MAGIC_CHECK_LIST(relative, NULL);
new_l->next = relative->next;
new_l->data = (void *)data;
if (relative->next)
relative->next->prev = new_l;
relative->next = new_l;
new_l->prev = relative;
_eina_list_update_accounting(list, new_l);
if (!new_l->next)
new_l->accounting->last = new_l;
return list;
}
EAPI Eina_List *
eina_list_prepend_relative(Eina_List *list,
const void *data,
const void *relative)
{
Eina_List *l;
void *list_data;
if (list)
EINA_MAGIC_CHECK_LIST(list, NULL);
EINA_LIST_FOREACH(list, l, list_data)
{
if (list_data == relative)
return eina_list_prepend_relative_list(list, data, l);
}
return eina_list_prepend(list, data);
}
EAPI Eina_List *
eina_list_prepend_relative_list(Eina_List *list,
const void *data,
Eina_List *relative)
{
Eina_List *new_l;
if ((!list) || (!relative))
return eina_list_prepend(list, data);
eina_error_set(0);
new_l = _eina_list_mempool_list_new(list);
if (!new_l)
return list;
EINA_MAGIC_CHECK_LIST(relative, NULL);
new_l->prev = relative->prev;
new_l->next = relative;
new_l->data = (void *)data;
if (relative->prev)
relative->prev->next = new_l;
relative->prev = new_l;
_eina_list_update_accounting(list, new_l);
if (new_l->prev)
return list;
return new_l;
}
EAPI Eina_List *
eina_list_sorted_insert(Eina_List *list, Eina_Compare_Cb func, const void *data)
{
Eina_List *lnear;
int cmp;
if (!list)
return eina_list_append(NULL, data);
lnear = eina_list_search_sorted_near_list(list, func, data, &cmp);
if (cmp < 0)
return eina_list_append_relative_list(list, data, lnear);
else
return eina_list_prepend_relative_list(list, data, lnear);
}
EAPI Eina_List *
eina_list_remove(Eina_List *list, const void *data)
{
Eina_List *l;
if (list)
EINA_MAGIC_CHECK_LIST(list, NULL);
l = eina_list_data_find_list(list, data);
return eina_list_remove_list(list, l);
}
EAPI Eina_List *
eina_list_remove_list(Eina_List *list, Eina_List *remove_list)
{
Eina_List *return_l;
if (!list)
return NULL;
if (!remove_list)
return list;
EINA_MAGIC_CHECK_LIST(remove_list, NULL);
if (remove_list->next)
remove_list->next->prev = remove_list->prev;
if (remove_list->prev)
{
remove_list->prev->next = remove_list->next;
return_l = list;
}
else
return_l = remove_list->next;
if (remove_list == remove_list->accounting->last)
{
EINA_MAGIC_CHECK_LIST(list, NULL);
list->accounting->last = remove_list->prev;
}
_eina_list_mempool_list_free(remove_list);
return return_l;
}
EAPI Eina_List *
eina_list_free(Eina_List *list)
{
Eina_List *l, *free_l;
if (!list)
return NULL;
EINA_MAGIC_CHECK_LIST(list, NULL);
for (l = list; l; )
{
free_l = l;
l = l->next;
_eina_list_mempool_list_free(free_l);
}
return NULL;
}
EAPI Eina_List *
eina_list_promote_list(Eina_List *list, Eina_List *move_list)
{
if (!list)
return NULL;
if (!move_list)
{
return list; /* Promoting head to be head. */
}
if (move_list == list)
return list;
if (move_list->next == list)
return move_list;
EINA_MAGIC_CHECK_LIST(list, NULL);
EINA_MAGIC_CHECK_LIST(move_list, NULL);
/* Remove the promoted item from the list. */
if (!move_list->prev)
move_list->next->prev = NULL;
else
{
move_list->prev->next = move_list->next;
if (move_list == list->accounting->last)
list->accounting->last = move_list->prev;
else
move_list->next->prev = move_list->prev;
}
/* Add the promoted item in the list. */
move_list->next = list;
move_list->prev = list->prev;
list->prev = move_list;
if (move_list->prev)
move_list->prev->next = move_list;
return move_list;
}
EAPI Eina_List *
eina_list_demote_list(Eina_List *list, Eina_List *move_list)
{
if (!list)
return NULL;
if (!move_list)
{
return list; /* Demoting tail to be tail. */
}
if (move_list == list->accounting->last)
return list;
EINA_MAGIC_CHECK_LIST(list, NULL);
EINA_MAGIC_CHECK_LIST(move_list, NULL);
/* Update pointer list if necessary. */
if (list == move_list)
{
list = move_list->next; /* Remove the demoted item from the list. */
}
if (move_list->prev)
move_list->prev->next = move_list->next;
move_list->next->prev = move_list->prev;
/* Add the demoted item in the list. */
move_list->prev = list->accounting->last;
move_list->prev->next = move_list;
move_list->next = NULL;
list->accounting->last = move_list;
return list;
}
EAPI void *
eina_list_data_find(const Eina_List *list, const void *data)
{
if (eina_list_data_find_list(list, data))
return (void *)data;
return NULL;
}
EAPI Eina_Bool
eina_list_move(Eina_List **to, Eina_List **from, void *data)
{
Eina_List *l;
EINA_SAFETY_ON_NULL_RETURN_VAL(to, EINA_FALSE);
EINA_SAFETY_ON_NULL_RETURN_VAL(from, EINA_FALSE);
EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
if (*to) EINA_MAGIC_CHECK_LIST(*to, EINA_FALSE);
EINA_MAGIC_CHECK_LIST(*from, EINA_FALSE);
l = eina_list_data_find_list(*from, data);
EINA_SAFETY_ON_NULL_RETURN_VAL(l, EINA_FALSE);
*to = eina_list_append(*to, data);
*from = eina_list_remove_list(*from, l);
return EINA_TRUE;
}
EAPI Eina_Bool
eina_list_move_list(Eina_List **to, Eina_List **from, Eina_List *data)
{
EINA_SAFETY_ON_NULL_RETURN_VAL(to, EINA_FALSE);
EINA_SAFETY_ON_NULL_RETURN_VAL(from, EINA_FALSE);
if (*to) EINA_MAGIC_CHECK_LIST(*to, EINA_FALSE);
EINA_MAGIC_CHECK_LIST(*from, EINA_FALSE);
EINA_MAGIC_CHECK_LIST(data, EINA_FALSE);
*to = eina_list_append(*to, data->data);
*from = eina_list_remove_list(*from, data);
return EINA_TRUE;
}
EAPI Eina_List *
eina_list_data_find_list(const Eina_List *list, const void *data)
{
const Eina_List *l;
void *list_data;
if (list)
EINA_MAGIC_CHECK_LIST(list, NULL);
EINA_LIST_FOREACH(list, l, list_data)
{
if (list_data == data)
return (Eina_List *)l;
}
return NULL;
}
EAPI void *
eina_list_nth(const Eina_List *list, unsigned int n)
{
Eina_List *l;
l = eina_list_nth_list(list, n);
return l ? l->data : NULL;
}
EAPI Eina_List *
eina_list_nth_list(const Eina_List *list, unsigned int n)
{
const Eina_List *l;
unsigned int i;
if (list)
EINA_MAGIC_CHECK_LIST(list, NULL);
/* check for non-existing nodes */
if ((!list) || (n > (list->accounting->count - 1)))
return NULL;
/* if the node is in the 2nd half of the list, search from the end
* else, search from the beginning.
*/
if (n > (list->accounting->count / 2))
for (i = list->accounting->count - 1,
l = list->accounting->last;
l;
l = l->prev, i--)
{
if (i == n)
return (Eina_List *)l;
}
else
for (i = 0, l = list; l; l = l->next, i++)
{
if (i == n)
return (Eina_List *)l;
}
abort();
}
EAPI Eina_List *
eina_list_reverse(Eina_List *list)
{
Eina_List *l1, *l2;
if (!list)
return NULL;
EINA_MAGIC_CHECK_LIST(list, NULL);
l1 = list;
l2 = list->accounting->last;
while (l1 != l2)
{
void *data;
data = l1->data;
l1->data = l2->data;
l2->data = data;
l1 = l1->next;
if (l1 == l2)
break;
l2 = l2->prev;
}
return list;
}
EAPI Eina_List *
eina_list_reverse_clone(const Eina_List *list)
{
const Eina_List *l;
Eina_List *lclone;
void *data;
if (!list)
return NULL;
EINA_MAGIC_CHECK_LIST(list, NULL);
lclone = NULL;
EINA_LIST_FOREACH(list, l, data)
lclone = eina_list_prepend(lclone, data);
return lclone;
}
EAPI Eina_List *
eina_list_clone(const Eina_List *list)
{
const Eina_List *l;
Eina_List *lclone;
void *data;
if (!list)
return NULL;
EINA_MAGIC_CHECK_LIST(list, NULL);
lclone = NULL;
EINA_LIST_FOREACH(list, l, data)
lclone = eina_list_append(lclone, data);
return lclone;
}
EAPI Eina_List *
eina_list_sort(Eina_List *list, unsigned int size, Eina_Compare_Cb func)
{
unsigned int i = 0;
unsigned int n = 0;
Eina_List *tail = list;
Eina_List *unsort = NULL;
Eina_List *stack[EINA_LIST_SORT_STACK_SIZE];
EINA_SAFETY_ON_NULL_RETURN_VAL(func, list);
if (!list)
return NULL;
EINA_MAGIC_CHECK_LIST(list, NULL);
/* if the caller specified an invalid size, sort the whole list */
if ((size == 0) ||
(size > list->accounting->count))
size = list->accounting->count;
if (size != list->accounting->count)
{
unsort = eina_list_nth_list(list, size);
if (unsort)
unsort->prev->next = NULL;
}
while (tail)
{
unsigned int idx, tmp;
Eina_List *a = tail;
Eina_List *b = tail->next;
if (!b)
{
stack[i++] = a;
break;
}
tail = b->next;
if (func(a->data, b->data) < 0)
((stack[i++] = a)->next = b)->next = 0;
else
((stack[i++] = b)->next = a)->next = 0;
tmp = n++;
for (idx = n ^ tmp; idx &= idx - 1; i--)
stack[i - 2] = eina_list_sort_merge(stack[i - 2], stack[i - 1], func);
}
while (i-- > 1)
stack[i - 1] = eina_list_sort_merge(stack[i - 1], stack[i], func);
list = stack[0];
tail = eina_list_sort_rebuild_prev(list);
if (unsort)
{
tail->next = unsort;
unsort->prev = tail;
}
else
list->accounting->last = tail;
return list;
}
EAPI Eina_List *
eina_list_merge(Eina_List *left, Eina_List *right)
{
unsigned int n_left, n_right;
if (!left)
return right;
if (!right)
return left;
left->accounting->last->next = right;
right->prev = left->accounting->last;
n_left = left->accounting->count;
n_right = right->accounting->count;
if (n_left >= n_right)
{
Eina_List *itr = right;
left->accounting->last = right->accounting->last;
left->accounting->count += n_right;
_eina_list_mempool_accounting_free(right->accounting);
do
{
itr->accounting = left->accounting;
itr = itr->next;
}
while (itr);
}
else
{
Eina_List *itr = left->accounting->last;
right->accounting->count += n_left;
_eina_list_mempool_accounting_free(left->accounting);
do
{
itr->accounting = right->accounting;
itr = itr->prev;
}
while (itr);
}
return left;
}
EAPI Eina_List *
eina_list_split_list(Eina_List *list, Eina_List *relative, Eina_List **right)
{
Eina_List *next;
Eina_List *itr;
if(!right)
return list;
*right = NULL;
if (!list)
return NULL;
if (!relative)
{
*right = list;
return NULL;
}
if (relative == eina_list_last(list))
return list;
next = eina_list_next(relative);
next->prev = NULL;
next->accounting = _eina_list_mempool_accounting_new(next);
next->accounting->last = list->accounting->last;
*right = next;
itr = next;
do
{
itr->accounting = next->accounting;
next->accounting->count++;
itr = itr->next;
}
while (itr);
relative->next = NULL;
list->accounting->last = relative;
list->accounting->count = list->accounting->count - next->accounting->count;
return list;
}
EAPI Eina_List *
eina_list_sorted_merge(Eina_List *left, Eina_List *right, Eina_Compare_Cb func)
{
Eina_List *ret;
Eina_List *current;
EINA_SAFETY_ON_NULL_RETURN_VAL(func, NULL);
if (!left)
return right;
if (!right)
return left;
if (func(left->data, right->data) < 0)
{
ret = left;
current = left;
left = left->next;
ret->accounting->count += right->accounting->count;
_eina_list_mempool_accounting_free(right->accounting);
}
else
{
ret = right;
current = right;
right = right->next;
ret->accounting->count += left->accounting->count;
_eina_list_mempool_accounting_free(left->accounting);
}
while (left && right)
{
if (func(left->data, right->data) < 0)
{
current->next = left;
left->prev = current;
left = left->next;
}
else
{
current->next = right;
right->prev = current;
right = right->next;
}
current = current->next;
current->accounting = ret->accounting;
}
if (left)
{
current->next = left;
left->prev = current;
current->accounting = ret->accounting;
}
if (right)
{
current->next = right;
right->prev = current;
current->accounting = ret->accounting;
}
while (current->next)
{
current = current->next;
current->accounting = ret->accounting;
}
ret->accounting->last = current;
return ret;
}
EAPI Eina_List *
eina_list_search_sorted_near_list(const Eina_List *list,
Eina_Compare_Cb func,
const void *data,
int *result_cmp)
{
const Eina_List *ct;
unsigned int inf, sup, cur;
int cmp;
if (!list)
{
if (result_cmp)
*result_cmp = 0;
return NULL;
}
if (list->accounting->count == 1)
{
if (result_cmp)
*result_cmp = func(list->data, data);
return (Eina_List *)list;
}
/* list walk is expensive, do quick check: tail */
ct = list->accounting->last;
cmp = func(ct->data, data);
if (cmp <= 0)
goto end;
/* list walk is expensive, do quick check: head */
ct = list;
cmp = func(ct->data, data);
if (cmp >= 0)
goto end;
/* inclusive bounds */
inf = 1;
sup = list->accounting->count - 2;
cur = 1;
ct = list->next;
/* no loop, just compare if comparison value is important to caller */
if (inf > sup)
{
if (result_cmp)
cmp = func(ct->data, data);
goto end;
}
while (inf <= sup)
{
unsigned int tmp = cur;
cur = inf + ((sup - inf) >> 1);
if (tmp < cur)
for (; tmp != cur; tmp++, ct = ct->next) ;
else if (tmp > cur)
for (; tmp != cur; tmp--, ct = ct->prev) ;
cmp = func(ct->data, data);
if (cmp == 0)
break;
else if (cmp < 0)
inf = cur + 1;
else if (cmp > 0)
{
if (cur > 0)
sup = cur - 1;
else
break;
}
else
break;
}
end:
if (result_cmp)
*result_cmp = cmp;
return (Eina_List *)ct;
}
EAPI Eina_List *
eina_list_search_sorted_list(const Eina_List *list,
Eina_Compare_Cb func,
const void *data)
{
Eina_List *lnear;
int cmp;
lnear = eina_list_search_sorted_near_list(list, func, data, &cmp);
if (!lnear)
return NULL;
if (cmp == 0)
return lnear;
return NULL;
}
EAPI void *
eina_list_search_sorted(const Eina_List *list,
Eina_Compare_Cb func,
const void *data)
{
return eina_list_data_get(eina_list_search_sorted_list(list, func, data));
}
EAPI Eina_List *
eina_list_search_unsorted_list(const Eina_List *list,
Eina_Compare_Cb func,
const void *data)
{
const Eina_List *l;
void *d;
EINA_LIST_FOREACH(list, l, d)
{
if (!func(d, data))
return (Eina_List *)l;
}
return NULL;
}
EAPI void *
eina_list_search_unsorted(const Eina_List *list,
Eina_Compare_Cb func,
const void *data)
{
return eina_list_data_get(eina_list_search_unsorted_list(list, func, data));
}
EAPI Eina_Iterator *
eina_list_iterator_new(const Eina_List *list)
{
Eina_Iterator_List *it;
eina_error_set(0);
it = calloc(1, sizeof (Eina_Iterator_List));
if (!it)
{
eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
return NULL;
}
EINA_MAGIC_SET(it, EINA_MAGIC_LIST_ITERATOR);
EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
it->head = list;
it->current = list;
it->iterator.version = EINA_ITERATOR_VERSION;
it->iterator.next = FUNC_ITERATOR_NEXT(eina_list_iterator_next);
it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
eina_list_iterator_get_container);
it->iterator.free = FUNC_ITERATOR_FREE(eina_list_iterator_free);
return &it->iterator;
}
EAPI Eina_Iterator *
eina_list_iterator_reversed_new(const Eina_List *list)
{
Eina_Iterator_List *it;
eina_error_set(0);
it = calloc(1, sizeof (Eina_Iterator_List));
if (!it)
{
eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
return NULL;
}
EINA_MAGIC_SET(it, EINA_MAGIC_LIST_ITERATOR);
EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
it->head = eina_list_last(list);
it->current = it->head;
it->iterator.version = EINA_ITERATOR_VERSION;
it->iterator.next = FUNC_ITERATOR_NEXT(eina_list_iterator_prev);
it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
eina_list_iterator_get_container);
it->iterator.free = FUNC_ITERATOR_FREE(eina_list_iterator_free);
return &it->iterator;
}
EAPI Eina_Accessor *
eina_list_accessor_new(const Eina_List *list)
{
Eina_Accessor_List *ac;
eina_error_set(0);
ac = calloc(1, sizeof (Eina_Accessor_List));
if (!ac)
{
eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
return NULL;
}
EINA_MAGIC_SET(ac, EINA_MAGIC_LIST_ACCESSOR);
EINA_MAGIC_SET(&ac->accessor, EINA_MAGIC_ACCESSOR);
ac->head = list;
ac->current = list;
ac->index = 0;
ac->accessor.version = EINA_ACCESSOR_VERSION;
ac->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_list_accessor_get_at);
ac->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER(
eina_list_accessor_get_container);
ac->accessor.free = FUNC_ACCESSOR_FREE(eina_list_accessor_free);
return &ac->accessor;
}