Compact List
[Containers]
Eina_Clist is a compact (inline) list implementation.
More...Data Structures | |
struct | _Eina_Clist |
Compact list type. More... | |
Defines | |
#define | EINA_CLIST_FOR_EACH(cursor, list) for ((cursor) = (list)->next; (cursor) != (list); (cursor) = (cursor)->next) |
iterate through the list | |
#define | EINA_CLIST_FOR_EACH_SAFE(cursor, cursor2, list) |
#define | EINA_CLIST_FOR_EACH_ENTRY(elem, list, type, field) |
#define | EINA_CLIST_FOR_EACH_ENTRY_SAFE(cursor, cursor2, list, type, field) |
#define | EINA_CLIST_FOR_EACH_REV(cursor, list) for ((cursor) = (list)->prev; (cursor) != (list); (cursor) = (cursor)->prev) |
#define | EINA_CLIST_FOR_EACH_SAFE_REV(cursor, cursor2, list) |
#define | EINA_CLIST_FOR_EACH_ENTRY_REV(elem, list, type, field) |
#define | EINA_CLIST_FOR_EACH_ENTRY_SAFE_REV(cursor, cursor2, list, type, field) |
#define | EINA_CLIST_INIT(list) { &(list), &(list) } |
#define | EINA_CLIST_ENTRY(elem, type, field) ((type *)((char *)(elem) - (unsigned long)(&((type *)0)->field))) |
Typedefs | |
typedef struct _Eina_Clist | Eina_Clist |
This is the list head and the list entry. | |
Functions | |
static void | eina_clist_add_after (Eina_Clist *elem, Eina_Clist *to_add) |
Add an element after the specified one. | |
static void | eina_clist_add_before (Eina_Clist *elem, Eina_Clist *to_add) |
Add an element before the specified one. | |
static void | eina_clist_add_head (Eina_Clist *list, Eina_Clist *elem) |
Add element at the head of the list. | |
static void | eina_clist_add_tail (Eina_Clist *list, Eina_Clist *elem) |
Add element at the tail of the list. | |
static void | eina_clist_element_init (Eina_Clist *elem) |
Init an (unlinked) element. | |
static int | eina_clist_element_is_linked (Eina_Clist *elem) |
Check if an element is in a list or not. | |
static void | eina_clist_remove (Eina_Clist *elem) |
Remove an element from its list. | |
static Eina_Clist * | eina_clist_next (const Eina_Clist *list, const Eina_Clist *elem) |
Get the next element. | |
static Eina_Clist * | eina_clist_prev (const Eina_Clist *list, const Eina_Clist *elem) |
Get the previous element. | |
static Eina_Clist * | eina_clist_head (const Eina_Clist *list) |
Get the first element. | |
static Eina_Clist * | eina_clist_tail (const Eina_Clist *list) |
Get the last element. | |
static int | eina_clist_empty (const Eina_Clist *list) |
Check if a list is empty. | |
static void | eina_clist_init (Eina_Clist *list) |
Initialize a list. | |
static unsigned int | eina_clist_count (const Eina_Clist *list) |
Count the elements of a list. | |
static void | eina_clist_move_tail (Eina_Clist *dst, Eina_Clist *src) |
Move all elements from src to the tail of dst. | |
static void | eina_clist_move_head (Eina_Clist *dst, Eina_Clist *src) |
move all elements from src to the head of dst |
Detailed Description
Eina_Clist is a compact (inline) list implementation.Elements of this list are members of the structs stored in the list
Advantages over Eina_List and Eina_Inlist:
- uses less memory (two machine words per item)
- allows removing items without knowing which list they're in using O(1) time
- no need to keep updating the head pointer as the list is changed
Disadvantages:
- O(N) time to calculate list length
- requires one list entry in a struct per list (i.e. it's an inlist)
- requires a head/tail pointer
- need to know the list head when moving to next or previous pointer
- Note:
- There's no NULL at the end of the list, the last item points to the head.
List heads must be initialized with EINA_CLIST_INIT or by calling eina_clist_element_init
struct gadget { struct Eina_Clist entry; <-- doesn't have to be the first item in the struct int a, b; }; static Eina_Clist global_gadgets = EINA_CLIST_INIT( global_gadgets );
or
struct some_global_thing { Eina_Clist gadgets; }; eina_clist_init( &some_global_thing->gadgets );
Manipulate it like this:
eina_clist_add_head( &global_gadgets, &new_gadget->entry ); eina_clist_remove( &new_gadget->entry ); eina_clist_add_after( &some_random_gadget->entry, &new_gadget->entry );
And to iterate over it:
struct gadget *gadget; EINA_CLIST_FOR_EACH_ENTRY( gadget, &global_gadgets, struct gadget, entry ) { ... }
Define Documentation
#define EINA_CLIST_FOR_EACH_SAFE | ( | cursor, | |||
cursor2, | |||||
list | ) |
Value:
for ((cursor) = (list)->next, (cursor2) = (cursor)->next; \
(cursor) != (list); \
(cursor) = (cursor2), (cursor2) = (cursor)->next)
#define EINA_CLIST_FOR_EACH_ENTRY | ( | elem, | |||
list, | |||||
type, | |||||
field | ) |
Value:
for ((elem) = EINA_CLIST_ENTRY((list)->next, type, field); \
&(elem)->field != (list); \
(elem) = EINA_CLIST_ENTRY((elem)->field.next, type, field))
#define EINA_CLIST_FOR_EACH_ENTRY_SAFE | ( | cursor, | |||
cursor2, | |||||
list, | |||||
type, | |||||
field | ) |
Value:
for ((cursor) = EINA_CLIST_ENTRY((list)->next, type, field), \
(cursor2) = EINA_CLIST_ENTRY((cursor)->field.next, type, field); \
&(cursor)->field != (list); \
(cursor) = (cursor2), \
(cursor2) = EINA_CLIST_ENTRY((cursor)->field.next, type, field))
#define EINA_CLIST_FOR_EACH_SAFE_REV | ( | cursor, | |||
cursor2, | |||||
list | ) |
Value:
for ((cursor) = (list)->prev, (cursor2) = (cursor)->prev; \
(cursor) != (list); \
(cursor) = (cursor2), (cursor2) = (cursor)->prev)
#define EINA_CLIST_FOR_EACH_ENTRY_REV | ( | elem, | |||
list, | |||||
type, | |||||
field | ) |
Value:
for ((elem) = EINA_CLIST_ENTRY((list)->prev, type, field); \
&(elem)->field != (list); \
(elem) = EINA_CLIST_ENTRY((elem)->field.prev, type, field))
#define EINA_CLIST_FOR_EACH_ENTRY_SAFE_REV | ( | cursor, | |||
cursor2, | |||||
list, | |||||
type, | |||||
field | ) |
Value:
for ((cursor) = EINA_CLIST_ENTRY((list)->prev, type, field), \
(cursor2) = EINA_CLIST_ENTRY((cursor)->field.prev, type, field); \
&(cursor)->field != (list); \
(cursor) = (cursor2), \
(cursor2) = EINA_CLIST_ENTRY((cursor)->field.prev, type, field))
Typedef Documentation
This is the list head and the list entry.
- Since:
- 1.1.0
Function Documentation
static void eina_clist_add_after | ( | Eina_Clist * | elem, | |
Eina_Clist * | to_add | |||
) | [inline, static] |
Add an element after the specified one.
- Parameters:
-
elem An element in the list to_add The element to add to the list
- Precondition:
- The list head must be initialized once before adding anything.
The element is not in any list.
- Note:
- There's no need to initialize an element before adding it to the list.
- Since:
- 1.1.0
static void eina_clist_add_before | ( | Eina_Clist * | elem, | |
Eina_Clist * | to_add | |||
) | [inline, static] |
Add an element before the specified one.
- Parameters:
-
elem An element in the list to_add The element to add to the list
- Precondition:
- The list head must be initialized once before adding anything.
The element is not in any list.
- Note:
- There's no need to initialize an element before adding it to the list.
- Since:
- 1.1.0
static void eina_clist_add_head | ( | Eina_Clist * | list, | |
Eina_Clist * | elem | |||
) | [inline, static] |
Add element at the head of the list.
- Parameters:
-
list The list elem An element
- Precondition:
- The list head must be initialized once before adding anything.
The element is not in any list.
- Note:
- There's no need to initialize an element before adding it to the list.
- Since:
- 1.1.0
static void eina_clist_add_tail | ( | Eina_Clist * | list, | |
Eina_Clist * | elem | |||
) | [inline, static] |
Add element at the tail of the list.
- Parameters:
-
list The list elem An element
- Precondition:
- The list head must be initialized once before adding anything.
The element is not in any list.
- Note:
- There's no need to initialize an element before adding it to the list.
- Since:
- 1.1.0
static void eina_clist_element_init | ( | Eina_Clist * | elem | ) | [inline, static] |
Init an (unlinked) element.
Call this function on elements that have not been added to the list if you want eina_clist_element_init() to work correctly
- Parameters:
-
elem An element
- Precondition:
- The element is not in any list.
- Postcondition:
- The element is marked as not being in any list
- Note:
- It is not necessary to call this before adding an element to this list.
- Since:
- 1.1.0
static int eina_clist_element_is_linked | ( | Eina_Clist * | elem | ) | [inline, static] |
Check if an element is in a list or not.
- Parameters:
-
elem An element
- Precondition:
- Either eina_clist_element_init() has been called on elem, it has been added to a list or remove from a list.
- Since:
- 1.1.0
static void eina_clist_remove | ( | Eina_Clist * | elem | ) | [inline, static] |
Remove an element from its list.
- Parameters:
-
elem An element
- Precondition:
- The element is in a list already
- Postcondition:
- The element is marked as not being in any list
- Since:
- 1.1.0
static Eina_Clist* eina_clist_next | ( | const Eina_Clist * | list, | |
const Eina_Clist * | elem | |||
) | [inline, static] |
Get the next element.
- Parameters:
-
list The list elem An element
- Precondition:
- elem is in list
- Returns:
- The element after elem in list or
NULL
if elem is last in list
- Since:
- 1.1.0
static Eina_Clist* eina_clist_prev | ( | const Eina_Clist * | list, | |
const Eina_Clist * | elem | |||
) | [inline, static] |
Get the previous element.
- Parameters:
-
list The list elem An element
- Returns:
- The element before elem or NULL if elem is the first in the list
- Since:
- 1.1.0
static Eina_Clist* eina_clist_head | ( | const Eina_Clist * | list | ) | [inline, static] |
Get the first element.
- Parameters:
-
list The list
- Returns:
- The first element in list or NULL if list is empty
- Since:
- 1.1.0
static Eina_Clist* eina_clist_tail | ( | const Eina_Clist * | list | ) | [inline, static] |
Get the last element.
- Parameters:
-
list The list
- Returns:
- The last element in list or NULL if list is empty
- Since:
- 1.1.0
static int eina_clist_empty | ( | const Eina_Clist * | list | ) | [inline, static] |
Check if a list is empty.
- Parameters:
-
list The list
- Returns:
- non-zero if list is empty, zero if it is not
- Since:
- 1.1.0
static void eina_clist_init | ( | Eina_Clist * | list | ) | [inline, static] |
Initialize a list.
- Parameters:
-
list The list
- Precondition:
- The list is uninitialized
- Postcondition:
- The list contains no items
- Note:
- Don't call this function on a list with items
This function must be called. Don't try do initialize the list by zero'ing out the list head.
- Since:
- 1.1.0
static unsigned int eina_clist_count | ( | const Eina_Clist * | list | ) | [inline, static] |
Count the elements of a list.
- Parameters:
-
list The list
- Returns:
- The number of items in the list
- Since:
- 1.1.0
static void eina_clist_move_tail | ( | Eina_Clist * | dst, | |
Eina_Clist * | src | |||
) | [inline, static] |
Move all elements from src to the tail of dst.
- Parameters:
-
dst List to be appended to src List to append
- Postcondition:
- src is initialized but empty after this operation
- Since:
- 1.1.0
static void eina_clist_move_head | ( | Eina_Clist * | dst, | |
Eina_Clist * | src | |||
) | [inline, static] |
move all elements from src to the head of dst
- Parameters:
-
dst List to be prepended to src List to prepend
- Postcondition:
- src is initialized but empty after this operation
- Since:
- 1.1.0