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