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.

Algorithm

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.

Performance

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).

Advanced Usage

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.

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) 2)
	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) 2)
	Moves an existing node to the beginning of the list.
Eina_Inlist *	eina_inlist_demote (Eina_Inlist list, Eina_Inlist item) 2)
	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) 3)
	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)

Define Documentation

#define _EINA_INLIST_CONTAINER	(	ref,
		ptr
	)

Value:

(void *)((char *)(ptr) - \
                                                  _EINA_INLIST_OFFSET(ref))

Since :: 2.3.1

Parameters:

ref	The reference to be used
ptr	The pointer to be used

#define _EINA_INLIST_OFFSET ( ref ) ((char *)&(ref)->__in_list - (char *)(ref))

Since :: 2.3.1

Parameters:

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
	)

Value:

((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
	)

Value:

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))

Since :: 2.3.1

Parameters:

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
	)

Value:

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)

Since :: 2.3.1

Parameters:

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
	)

Value:

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))

Since :: 2.3.1

Parameters:

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

Typedef Documentation

Eina_Inlist_Sorted_State

The structure type for the state of a sorted Eina_Inlist.

Since (EFL) :: 1.1.0

Function Documentation

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.

Since :: 2.3.1

Parameters:

[in] in_list The list

Returns:: A new accessor

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.

Since :: 2.3.1

Remarks:: in_item is considered to be in no list. If it has been in another list before, eina_inlist_remove() it before adding. No check of new_l prev and next pointers is done, so it's safe to have them uninitialized.

Parameters:

[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`

Returns:: The new list head
Use it and not in_list anymore.

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.

Since :: 2.3.1

Remarks:: in_item_l is considered to be in no list. If it has been in another list before, eina_inlist_remove() it before adding. No check of in_item prev and next pointers is done, so it's safe to have them uninitialized.; in_relative is considered to be inside in_list, no checks are done to confirm that and giving nodes from different lists leads to problems. Setting in_relative to NULL is the same as eina_list_append().

Parameters:

[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

Returns:: The new list head
Use it and not list anymore.

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.

Since :: 2.3.1

Remarks:: This is an order-N operation and so the time depends on the number of elements in the list, so it might become slow for big lists.

Parameters:

[in] list The list whose count to return

Returns:: The number of members in the list

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.

Since :: 2.3.1

Remarks:: item is considered to be inside list. No checks are done to confirm this, and giving nodes from different lists leads to problems.

Parameters:

[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`

Returns:: The new list head
Use it and not list anymore.

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.

Since :: 2.3.1

Parameters:

[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`

Returns:: in_item if found, 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.

Since :: 2.3.1

Remarks:: If the memory cannot be allocated, NULL is returned and EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is returned.; If the list structure changes then the iterator becomes invalid, and if you add or remove nodes the iterator's behavior is undefined, and your program may crash.

Parameters:

[in] in_list The list

Returns:: A new iterator

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.

Since :: 2.3.1

Remarks:: new_l is considered to be in no list. If it has been in another list before, eina_inlist_remove() it before adding. No check of new_l prev and next pointers is done, so it's safe to have them uninitialized.

Parameters:

[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`

Returns:: The new list head
Use it and not in_list anymore.

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.

Since :: 2.3.1

Remarks:: in_item is considered to be in no list. If it has been in another list before, eina_inlist_remove() it before adding. No check of in_item prev and next pointers is done, so it's safe to have them uninitialized.; in_relative is considered to be inside in_list, no checks are done to confirm that and giving nodes from different lists leads to problems. Setting in_relative to NULL is the same as eina_list_prepend().

Parameters:

[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

Returns:: The new list head
Use it and not in_list anymore.

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.

Since :: 2.3.1

Remarks:: item is considered to be inside list. No checks are done to confirm this, and giving nodes from different lists leads to problems.

Parameters:

[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`

Returns:: The new list head
Use it and not list anymore.

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.

Since :: 2.3.1

Remarks:: in_item is considered to be inside in_list, no checks are done to confirm that and giving nodes from different lists lead to problems, especially if in_item is the head since it is different from list and the wrong new head is returned.

Parameters:

[in]	in_list	The existing list head, must not be `NULL`
[in]	in_item	The existing list node, must not be `NULL`

Returns:: The new list head
Use it and not list anymore.

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.

Since :: 2.3.1

Remarks:: in-place: This changes the given list, so you should now point to the new list head that is returned by this function.; Worst case is O(n * log2(n)) comparisons (calls to func()). That means, for 1,000,000 list elements, sort does 20,000,000 comparisons.

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);

Parameters:

[in]	head	The list handle to sort
[in]	func	A function pointer that can handle comparing the list data nodes

Returns:: The new head of 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.

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.

Since (EFL) :: 1.1.0

Since :: 2.3.1

Remarks:: Average/worst case performance is O(log2(n)) comparisons (calls to func). As said in eina_list_search_sorted_near_list(), lists do not have O(1) access time, so walking to the correct node can be costly, consider worst case to be almost O(n) pointer dereference (list walk).

Parameters:

[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

Returns:: A list pointer

void eina_inlist_sorted_state_free ( Eina_Inlist_Sorted_State * state )

Frees an Eina_Inlist_Sorted_State.

Since (EFL) :: 1.1.0

Since :: 2.3.1

Parameters:

[in] state The state to destroy

See also:: eina_inlist_sorted_state_insert()

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.

Since (EFL) :: 1.1.0

Since :: 2.3.1

Parameters:

[in]	state	The state to update
[in]	list	The list to match

Returns:: The number of items that are actually in the list

See also:: eina_inlist_sorted_state_insert()

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.

Since (EFL) :: 1.1.0

Since :: 2.3.1

Remarks:: Average/worst case performance is O(log2(n)) comparisons (calls to func) As said in eina_list_search_sorted_near_list(), lists do not have O(1) access time, so walking to the correct node can be costly, but this version tries to minimize that by making it O(log2(n)) for a small number. After n == 256, it starts to add linear cost again. Consider worst case to be almost O(n) pointer dereference (list walk).

Parameters:

[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

Returns:: A list pointer

Eina_Inlist_Sorted_State* eina_inlist_sorted_state_new ( void )

Creates a state with the valid data in it.

Since (EFL) :: 1.1.0

Since :: 2.3.1

Returns:: A valid Eina_Inlist_Sorted_State

See also:: eina_inlist_sorted_state_insert()

Algorithm

Performance

Advanced Usage

Functions

Typedefs

Defines

Define Documentation

Typedef Documentation

Function Documentation