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)
 Iterate through the list, with safety against removal.
#define EINA_CLIST_FOR_EACH_ENTRY(elem, list, type, field)
 Iterate through the list using a list entry.
#define EINA_CLIST_FOR_EACH_ENTRY_SAFE(cursor, cursor2, list, type, field)
 Iterate through the list using a list entry, with safety against removal.
#define EINA_CLIST_FOR_EACH_REV(cursor, list)   for ((cursor) = (list)->prev; (cursor) != (list); (cursor) = (cursor)->prev)
 Iterate through the list in reverse order.
#define EINA_CLIST_FOR_EACH_SAFE_REV(cursor, cursor2, list)
 Iterate through the list in reverse order, with safety against removal.
#define EINA_CLIST_FOR_EACH_ENTRY_REV(elem, list, type, field)
 Iterate through the list in reverse order using a list entry.
#define EINA_CLIST_FOR_EACH_ENTRY_SAFE_REV(cursor, cursor2, list, type, field)
 Iterate through the list in reverse order using a list entry, with safety against removal.
#define EINA_CLIST_INIT(list)   { &(list), &(list) }
 Macros for statically initialized lists.
#define EINA_CLIST_ENTRY(elem, type, field)   ((type *)((char *)(elem) - (unsigned long)(&((type *)0)->field)))
 Get pointer to object containing list element.

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_Clisteina_clist_next (const Eina_Clist *list, const Eina_Clist *elem)
 Get the next element.
static Eina_Clisteina_clist_prev (const Eina_Clist *list, const Eina_Clist *elem)
 Get the previous element.
static Eina_Clisteina_clist_head (const Eina_Clist *list)
 Get the first element.
static Eina_Clisteina_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

Define a list like so:

   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 ( cursor,
list   )     for ((cursor) = (list)->next; (cursor) != (list); (cursor) = (cursor)->next)

Iterate through the list.

Parameters:
cursor The pointer to be used during the interation.
list The list to be interated.

#define EINA_CLIST_FOR_EACH_SAFE ( cursor,
cursor2,
list   ) 

Value:

for ((cursor) = (list)->next, (cursor2) = (cursor)->next; \
         (cursor) != (list); \
         (cursor) = (cursor2), (cursor2) = (cursor)->next)
Iterate through the list, with safety against removal.

Parameters:
cursor The pointer to be used during the interation.
cursor2 The auxiliar pointer to be used during the interation.
list The list to be interated.

#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))
Iterate through the list using a list entry.

Parameters:
elem The element to be used.
list The list to be iterated.
type The type of the list.
field The field of the element.

#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))
Iterate through the list using a list entry, with safety against removal.

Parameters:
cursor The pointer to be used during the interation.
cursor2 The auxiliar pointer to be used during the interation.
list The list to be interated.
type The type of the list.
field The field of the element.

#define EINA_CLIST_FOR_EACH_REV ( cursor,
list   )     for ((cursor) = (list)->prev; (cursor) != (list); (cursor) = (cursor)->prev)

Iterate through the list in reverse order.

Parameters:
cursor The pointer to be used during the interation.
list The list to be interated.

#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)
Iterate through the list in reverse order, with safety against removal.

Parameters:
cursor The pointer to be used during the interation.
cursor2 The auxiliar pointer to be used during the interation.
list The list to be interated.

#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))
Iterate through the list in reverse order using a list entry.

Parameters:
elem The element to be used.
list The list to be iterated.
type The type of the list.
field The field of the element.

#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))
Iterate through the list in reverse order using a list entry, with safety against removal.

Parameters:
cursor The pointer to be used during the interation.
cursor2 The auxiliar pointer to be used during the interation.
list The list to be interated.
type The type of the list.
field The field of the element.

#define EINA_CLIST_INIT ( list   )     { &(list), &(list) }

Macros for statically initialized lists.

Parameters:
list The list to be used.

#define EINA_CLIST_ENTRY ( elem,
type,
field   )     ((type *)((char *)(elem) - (unsigned long)(&((type *)0)->field)))

Get pointer to object containing list element.

Parameters:
elem The element to be used.
type The type of the element.
field The field of the element.


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