Tizen Native API
|
Functions | |
Eina_Inlist * | eina_inlist_append (Eina_Inlist *in_list, Eina_Inlist *in_item) |
Adds a new node to the end of a list. | |
Eina_Inlist * | eina_inlist_prepend (Eina_Inlist *in_list, Eina_Inlist *in_item) |
Adds a new node to the beginning of the list. | |
Eina_Inlist * | eina_inlist_append_relative (Eina_Inlist *in_list, Eina_Inlist *in_item, Eina_Inlist *in_relative) |
Adds a new node after the given relative item in the list. | |
Eina_Inlist * | eina_inlist_prepend_relative (Eina_Inlist *in_list, Eina_Inlist *in_item, Eina_Inlist *in_relative) |
Adds a new node before the given relative item in the list. | |
Eina_Inlist * | eina_inlist_remove (Eina_Inlist *in_list, Eina_Inlist *in_item) |
Removes a node from the list. | |
Eina_Inlist * | eina_inlist_find (Eina_Inlist *in_list, Eina_Inlist *in_item) |
Finds a given node in the list, returns itself if found, NULL if not. | |
Eina_Inlist * | eina_inlist_promote (Eina_Inlist *list, Eina_Inlist *item) |
Moves an existing node to the beginning of the list. | |
Eina_Inlist * | eina_inlist_demote (Eina_Inlist *list, Eina_Inlist *item) |
Moves an existing node to the end of the list. | |
unsigned int | eina_inlist_count (const Eina_Inlist *list) |
Gets the count of the number of items in a list. | |
Eina_Iterator * | eina_inlist_iterator_new (const Eina_Inlist *in_list) |
Returns a new iterator associated to list. | |
Eina_Accessor * | eina_inlist_accessor_new (const Eina_Inlist *in_list) |
Returns a new accessor associated to the list. | |
Eina_Inlist * | eina_inlist_sorted_insert (Eina_Inlist *list, Eina_Inlist *item, Eina_Compare_Cb func) |
Inserts a new node into a sorted list. | |
Eina_Inlist_Sorted_State * | eina_inlist_sorted_state_new (void) |
Creates a state with the valid data in it. | |
int | eina_inlist_sorted_state_init (Eina_Inlist_Sorted_State *state, Eina_Inlist *list) |
Forces an Eina_Inlist_Sorted_State to match the content of a list. | |
void | eina_inlist_sorted_state_free (Eina_Inlist_Sorted_State *state) |
Frees an Eina_Inlist_Sorted_State. | |
Eina_Inlist * | eina_inlist_sorted_state_insert (Eina_Inlist *list, Eina_Inlist *item, Eina_Compare_Cb func, Eina_Inlist_Sorted_State *state) |
Inserts a new node into a sorted list. | |
Eina_Inlist * | eina_inlist_sort (Eina_Inlist *head, Eina_Compare_Cb func) |
Sorts a list according to the ordering that func returns. | |
Typedefs | |
typedef struct _Eina_Inlist | Eina_Inlist |
The structure type for an inlined list type. | |
typedef struct _Eina_Inlist_Sorted_State | Eina_Inlist_Sorted_State |
The structure type for the state of a sorted Eina_Inlist. | |
Defines | |
#define | EINA_INLIST Eina_Inlist __in_list |
#define | EINA_INLIST_GET(Inlist) (& ((Inlist)->__in_list)) |
#define | EINA_INLIST_CONTAINER_GET(ptr,type) |
#define | _EINA_INLIST_OFFSET(ref) ((char *)&(ref)->__in_list - (char *)(ref)) |
#define | _EINA_INLIST_CONTAINER(ref, ptr) |
#define | EINA_INLIST_FOREACH(list, it) |
#define | EINA_INLIST_FOREACH_SAFE(list, list2, it) |
#define | EINA_INLIST_REVERSE_FOREACH(list, it) |
These functions provide inline list management.
Inline lists mean its nodes pointers are part of the same memory as the data. This has the benefit of fragmenting less memory and avoiding node->data
indirection, but has the drawback of higher cost for some common operations like count and sort.
It is possible to have inlist nodes to be part of regular lists, created with eina_list_append() or eina_list_prepend(). It's also possible to have a structure with two inlist pointers, thus being part of two different inlists at the same time, but the current convenience macros that are provided won't work for both of them. Consult Advanced Usage for more info.
Inline lists have their purposes, but if you don't know what those purposes are, go with regular lists instead.
Tip: When using inlists in more than one place (that is, passing them around functions or keeping a pointer to them in a structure) it's is better to keep a pointer to the first container, and not a pointer to the first inlist item (mostly they are the same, but that's not always correct). This lets the compiler do type checking and lets the programmer know exactly what type this list is.
The basic structure can be represented by the following picture:
One data structure also has node information with three pointers: prev, next, and last. The last pointer is just valid for the first element (the list head), otherwise each insertion in the list has to be done by updating every node with the correct pointer. This means that it's very important to keep a pointer to the first element of the list, since it is the only one that has the correct information to allow a proper O(1) append to the list.
Due to the nature of the inlist, there's no accounting information, and no easy access to the last element of each list node. This means that eina_inlist_count() is order-N, while eina_list_count() is order-1 (constant time).
The basic usage considers a struct that has the user data, and also has the inlist node information (prev, next, and last pointers) created with EINA_INLIST during struct declaration. This allows one to use the convenience macros EINA_INLIST_GET(), EINA_INLIST_CONTAINER_GET(), EINA_INLIST_FOREACH(), and so on. This happens because the EINA_INLIST macro declares a struct member with the name __inlist, and all the other macros assume that this struct member has this name.
It may be the case that someone needs to have some inlist nodes added to a Eina_List too. If this happens, the inlist nodes can be added to the Eina_List without any problem.
It's also possible to have data that is part of two different inlists. If this is the case, then it won't be possible to use convenience macros for both of the lists. It is necessary to create a new set of macros that allow access to the second list node info.
#define _EINA_INLIST_CONTAINER | ( | ref, | |
ptr | |||
) |
(void *)((char *)(ptr) - \ _EINA_INLIST_OFFSET(ref))
ref | The reference to be used |
ptr | The pointer to be used |
#define _EINA_INLIST_OFFSET | ( | ref | ) | ((char *)&(ref)->__in_list - (char *)(ref)) |
ref | The reference to be used |
#define EINA_INLIST Eina_Inlist __in_list |
Definition used for declaring an inlist member in a struct
#define EINA_INLIST_CONTAINER_GET | ( | ptr, | |
type | |||
) |
((type *)((char *)ptr - \
offsetof(type, __in_list)))
Definition of the utility macro to get the container object of an inlist
#define EINA_INLIST_FOREACH | ( | list, | |
it | |||
) |
for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list) : NULL); it; \ it = (EINA_INLIST_GET(it)->next ? _EINA_INLIST_CONTAINER(it, EINA_INLIST_GET(it)->next) : NULL))
list | The list to iterate on |
it | A pointer to the list item, i.e. a pointer to each item that is a part of the list. |
#define EINA_INLIST_FOREACH_SAFE | ( | list, | |
list2, | |||
it | |||
) |
for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list) : NULL), list2 = it ? ((EINA_INLIST_GET(it) ? EINA_INLIST_GET(it)->next : NULL)) : NULL; \ it; \ it = NULL, it = list2 ? _EINA_INLIST_CONTAINER(it, list2) : NULL, list2 = list2 ? list2->next : NULL)
list | The list to iterate on |
list2 | The auxiliar Eina_Inlist variable so we can save the pointer to the next element, allowing us to free/remove the current one Note that this macro is safe only if the next element is not removed Only the current one is allowed to be removed. |
it | A pointer to the list item, i.e. a pointer to each item that is a part of the list |
#define EINA_INLIST_GET | ( | Inlist | ) | (& ((Inlist)->__in_list)) |
Definition of the utility macro to get the inlist object of a struct
#define EINA_INLIST_REVERSE_FOREACH | ( | list, | |
it | |||
) |
for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list->last) : NULL); \ it; it = (EINA_INLIST_GET(it)->prev ? _EINA_INLIST_CONTAINER(it, EINA_INLIST_GET(it)->prev) : NULL))
list | The list to traverse in the reverse order |
it | A pointer to the list item, i.e. a pointer to each item that is a part of the list |
The structure type for the state of a sorted Eina_Inlist.
Eina_Accessor* eina_inlist_accessor_new | ( | const Eina_Inlist * | in_list | ) |
Returns a new accessor associated to the list.
This function returns a newly allocated accessor associated to in_list. If in_list is NULL
or the count member of in_list is less than or equal to 0
, this function returns NULL
. If the memory cannot be allocated, NULL
is returned and EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid accessor is returned.
[in] | in_list | The list |
Eina_Inlist* eina_inlist_append | ( | Eina_Inlist * | in_list, |
Eina_Inlist * | in_item | ||
) |
Adds a new node to the end of a list.
This code is meant to be fast: appends are O(1) and do not walk through in_list.
[in] | in_list | The existing list head, otherwise NULL to create a new list |
[in] | in_item | new The list node, must not be NULL |
Eina_Inlist* eina_inlist_append_relative | ( | Eina_Inlist * | in_list, |
Eina_Inlist * | in_item, | ||
Eina_Inlist * | in_relative | ||
) |
Adds a new node after the given relative item in the list.
This code is meant to be fast: appends are O(1) and do not walk through in_list.
NULL
is the same as eina_list_append().[in] | in_list | The existing list head, otherwise NULL to create a new list |
[in] | in_item | new The list node, must not be NULL |
[in] | in_relative | The reference node, in_item is added after it |
unsigned int eina_inlist_count | ( | const Eina_Inlist * | list | ) |
Gets the count of the number of items in a list.
This function returns the number of members that list contains. If the list is NULL
, 0
is returned.
[in] | list | The list whose count to return |
Eina_Inlist* eina_inlist_demote | ( | Eina_Inlist * | list, |
Eina_Inlist * | item | ||
) |
Moves an existing node to the end of the list.
This code is meant to be fast: appends are O(1) and do not walk through list.
[in] | list | The existing list head, otherwise NULL to create a new list |
[in] | item | The list node to move to the end (tail), must not be NULL |
Eina_Inlist* eina_inlist_find | ( | Eina_Inlist * | in_list, |
Eina_Inlist * | in_item | ||
) |
Finds a given node in the list, returns itself if found, NULL
if not.
This is an expensive call and has O(n) cost, possibly walking the whole list.
[in] | in_list | The existing list to search in_item in, must not be NULL |
[in] | in_item | The item to search for, must not be NULL |
NULL
if not Eina_Iterator* eina_inlist_iterator_new | ( | const Eina_Inlist * | in_list | ) |
Returns a new iterator associated to list.
This function returns a newly allocated iterator associated to in_list. If in_list is NULL
or the count member of in_list is less than or equal to 0
, this function still returns a valid iterator that always returns false
on a call to eina_iterator_next(), thus keeping the API sane.
NULL
is returned and EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is returned.[in] | in_list | The list |
Eina_Inlist* eina_inlist_prepend | ( | Eina_Inlist * | in_list, |
Eina_Inlist * | in_item | ||
) |
Adds a new node to the beginning of the list.
This code is meant to be fast: appends are O(1) and do not walk through in_list.
[in] | in_list | The existing list head, otherwise NULL to create a new list |
[in] | in_item | The new list node, must not be NULL |
Eina_Inlist* eina_inlist_prepend_relative | ( | Eina_Inlist * | in_list, |
Eina_Inlist * | in_item, | ||
Eina_Inlist * | in_relative | ||
) |
Adds a new node before the given relative item in the list.
This code is meant to be fast: appends are O(1) and do not walk through in_list.
NULL
is the same as eina_list_prepend().[in] | in_list | The existing list head, otherwise NULL to create a new list |
[in] | in_item | new The list node, must not be NULL |
[in] | in_relative | The reference node, in_item is added before it |
Eina_Inlist* eina_inlist_promote | ( | Eina_Inlist * | list, |
Eina_Inlist * | item | ||
) |
Moves an existing node to the beginning of the list.
This code is meant to be fast: appends are O(1) and do not walk through list.
[in] | list | The existing list head, otherwise NULL to create a new list |
[in] | item | The list node to move to the beginning (head), must not be NULL |
Eina_Inlist* eina_inlist_remove | ( | Eina_Inlist * | in_list, |
Eina_Inlist * | in_item | ||
) |
Removes a node from the list.
This code is meant to be fast: appends are O(1) and do not walk through list.
[in] | in_list | The existing list head, must not be NULL |
[in] | in_item | The existing list node, must not be NULL |
Eina_Inlist* eina_inlist_sort | ( | Eina_Inlist * | head, |
Eina_Compare_Cb | func | ||
) |
Sorts a list according to the ordering that func returns.
This function sorts all the elements of head. func is used to compare two elements of head. If head or func is NULL
, this function returns NULL
.
Example:
typedef struct _Sort_Ex Sort_Ex; struct _Sort_Ex { INLIST; const char *text; }; int sort_cb(const Inlist *l1, const Inlist *l2) { const Sort_Ex *x1; const Sort_Ex *x2; x1 = EINA_INLIST_CONTAINER_GET(l1, Sort_Ex); x2 = EINA_INLIST_CONTAINER_GET(l2, Sort_Ex); return(strcmp(x1->text, x2->text)); } extern Eina_Inlist *list; list = eina_inlist_sort(list, sort_cb);
[in] | head | The list handle to sort |
[in] | func | A function pointer that can handle comparing the list data nodes |
Eina_Inlist* eina_inlist_sorted_insert | ( | Eina_Inlist * | list, |
Eina_Inlist * | item, | ||
Eina_Compare_Cb | func | ||
) |
Inserts a new node into a sorted list.
This function inserts items into a linked list assuming it is sorted and the result is sorted. If list is NULLL
, item is returned. On success, a new list pointer that should be used in place of the one given to this function is returned. Otherwise, the old pointer is returned.
[in] | list | The given linked list, must be sorted |
[in] | item | The list node to insert, must not be NULL |
[in] | func | The function called for the sort |
void eina_inlist_sorted_state_free | ( | Eina_Inlist_Sorted_State * | state | ) |
Frees an Eina_Inlist_Sorted_State.
[in] | state | The state to destroy |
int eina_inlist_sorted_state_init | ( | Eina_Inlist_Sorted_State * | state, |
Eina_Inlist * | list | ||
) |
Forces an Eina_Inlist_Sorted_State to match the content of a list.
This function is useful if you didn't use eina_inlist_sorted_state_insert() at any point, but still think you have a sorted list. It only works correctly on a sorted list.
[in] | state | The state to update |
[in] | list | The list to match |
Eina_Inlist* eina_inlist_sorted_state_insert | ( | Eina_Inlist * | list, |
Eina_Inlist * | item, | ||
Eina_Compare_Cb | func, | ||
Eina_Inlist_Sorted_State * | state | ||
) |
Inserts a new node into a sorted list.
This function inserts an item into a linked list assuming state matches the exact content order of the list. It uses state to do a fast first step dichotomic search before starting to walk through the inlist itself. This makes this code much faster than eina_inlist_sorted_insert() as it doesn't need to walk through the list at all. The result is of course a sorted list with an updated state.. If list is NULLL
, item is returned. On success, a new list pointer that should be used in place of the one given to this function is returned. Otherwise, the old pointer is returned.
[in] | list | The given linked list, must be sorted |
[in] | item | The list node to insert, must not be NULL |
[in] | func | The function called for the sort |
[in] | state | The current array for an initial dichotomic search |
Creates a state with the valid data in it.