Doubly linked lists interface. More...

#include <Lazuli/common.h>
#include <Lazuli/config.h>

Data Structures
struct	_Lz_LinkedListElement
	Represents an element of a doubly linked list. More...

struct	Lz_LinkedList
	Represents the main container for doubly linked elements. More...

Macros
#define	LINKED_LIST_INIT { NULL, NULL }
	Define the initialization value for the type Lz_LinkedList.

#define	LINKED_LIST_ELEMENT_INIT { NULL, NULL }
	Define the initialization value for the type Lz_LinkedListElement.

#define	List_UntypedForEach(LINKEDLIST, ITEM)
	Run through an Lz_LinkedList like a for loop.

#define	List_ForEach(LINKEDLIST, TYPE, ITEM, MEMBER)
	Run through an Lz_LinkedList like a for loop.

#define	List_RemovableForEach(LINKEDLIST, TYPE, ITEM, MEMBER, ITERATOR)
	Run through an Lz_LinkedList like a for loop, with the ability of removing elements from the list while iterating on it.

Typedefs
typedef struct _Lz_LinkedListElement	Lz_LinkedListElement
	Represents an element of a doubly linked list.

Functions
void	List_Append (Lz_LinkedList const linkedList, Lz_LinkedListElement const item)
	Insert an Lz_LinkedListElement as the last element of an existing Lz_LinkedList.

void	List_Prepend (Lz_LinkedList const linkedList, Lz_LinkedListElement const item)
	Insert an Lz_LinkedListElement as the first element of an existing Lz_LinkedList.

void	List_AppendList (Lz_LinkedList const linkedListDestination, Lz_LinkedList const linkedListToMove)
	Move the content of an Lz_LinkedList to the end of an existing Lz_LinkedList.

Lz_LinkedListElement *	List_PickFirst (Lz_LinkedList *const linkedList)
	Return the first element of an existing linked list.

Lz_LinkedListElement *	List_PointFirst (const Lz_LinkedList *const linkedList)
	Return a pointer to the first element of an existing linked list.

bool	List_IsEmpty (const Lz_LinkedList *const linkedList)
	Test if an Lz_LinkedList is empty.

void	List_InsertAfter (Lz_LinkedList const linkedList, Lz_LinkedListElement const listItem, Lz_LinkedListElement *const itemToInsert)
	Insert an element after another in an Lz_LinkedList.

void	List_InsertBefore (Lz_LinkedList const linkedList, Lz_LinkedListElement const listItem, Lz_LinkedListElement *const itemToInsert)
	Insert an element before another in a Lz_LinkedList.

Lz_LinkedListElement *	List_Remove (Lz_LinkedList const linkedList, Lz_LinkedListElement const itemToRemove)
	Remove an element from an Lz_LinkedList.

Lz_LinkedListElement *	List_PointElementAt (const Lz_LinkedList *const linkedList, const size_t index)
	Point to an indexed element in an Lz_LinkedList, starting at index 0.

void	List_InitLinkedList (Lz_LinkedList *const linkedList)
	Initialize an Lz_LinkedList.

void	List_InitLinkedListElement (Lz_LinkedListElement *const item)
	Initialize an Lz_LinkedListElement.

Detailed Description

Doubly linked lists interface.

Copyright: 2017-2020, Remi Andruccioli remi..nosp@m.andr.nosp@m.uccio.nosp@m.li@g.nosp@m.mail..nosp@m.com

Describes types and functions related to doubly linked lists.

Definition in file list.h.

Macro Definition Documentation

◆ LINKED_LIST_INIT

#define LINKED_LIST_INIT { NULL, NULL }

Define the initialization value for the type Lz_LinkedList.

Definition at line 47 of file list.h.

◆ LINKED_LIST_ELEMENT_INIT

#define LINKED_LIST_ELEMENT_INIT { NULL, NULL }

Define the initialization value for the type Lz_LinkedListElement.

Definition at line 52 of file list.h.

◆ List_UntypedForEach

#define List_UntypedForEach	(	LINKEDLIST,
		ITEM
	)

Value:

  if ((LZ_CONFIG_CHECK_NULL_PARAMETERS_IN_LISTS && (NULL == (LINKEDLIST))) || \
      (NULL == (LINKEDLIST)->first))                                    \
    {}                                                                  \
  else                                                                  \
    for ((ITEM) = (LINKEDLIST)->first;                                  \
         NULL != (ITEM);                                                \
         (ITEM) = (ITEM)->next)

Run through an Lz_LinkedList like a for loop.

If the list is empty, no loop is performed, and the execution will continue after the foreach.

With configuration option CHECK_NULL_PARAMETERS_IN_LISTS, this implementation can also verify if the LINKEDLIST pointer is NULL. If so, the loop is not run and the execution continues after the loop.

Parameters

LINKEDLIST	A pointer to the Lz_LinkedList to run through.
ITEM	A pointer to an Lz_LinkedListElement that will point to the current item of each loop turn. This pointer will never be NULL.

Definition at line 146 of file list.h.

◆ List_ForEach

#define List_ForEach	(	LINKEDLIST,
		TYPE,
		ITEM,
		MEMBER
	)

Value:

  if ((LZ_CONFIG_CHECK_NULL_PARAMETERS_IN_LISTS && (NULL == (LINKEDLIST))) || \
      (NULL == (LINKEDLIST)->first))                                    \
    {}                                                                  \
  else                                                                  \
    for ((ITEM) = CONTAINER_OF((LINKEDLIST)->first, MEMBER, TYPE);      \
         NULL != (ITEM);                                                \
         (ITEM) =                                                       \
           (NULL == ((ITEM)->MEMBER).next)                              \
           ? NULL                                                       \
           : CONTAINER_OF(((ITEM)->MEMBER).next, MEMBER, TYPE))

Run through an Lz_LinkedList like a for loop.

This foreach implementation is typed, so each loop turn will return a typed pointer to the current loop element (ie. not a pointer to a raw Lz_LinkedListElement).

If the list is empty, no loop is performed, and the execution will continue after the foreach.

With configuration option CHECK_NULL_PARAMETERS_IN_LISTS, this implementation can also verify if the LINKEDLIST pointer is NULL. If so, the loop is not run and the execution continues after the loop.

Parameters

LINKEDLIST	A pointer to the Lz_LinkedList to run through.
TYPE	The real type of the list elements
ITEM	A pointer to a struct of type `TYPE` containing the Lz_LinkedListElement. This pointer will point to the current item of each loop turn. This pointer will never be NULL while the loop is running.
MEMBER	The name of the member in `TYPE` which bears the Lz_LinkedListElement.

Definition at line 178 of file list.h.

◆ List_RemovableForEach

#define List_RemovableForEach	(	LINKEDLIST,
		TYPE,
		ITEM,
		MEMBER,
		ITERATOR
	)

Value:

  if ((LZ_CONFIG_CHECK_NULL_PARAMETERS_IN_LISTS && (NULL == (LINKEDLIST))) || \
      (NULL == (LINKEDLIST)->first))                                    \
    {}                                                                  \
  else                                                                  \
    for (STATIC_CHECK_TYPE((*(ITERATOR)), Lz_LinkedListElement),        \
           (ITERATOR) = (LINKEDLIST)->first,                            \
           (ITEM) = CONTAINER_OF((LINKEDLIST)->first, MEMBER, TYPE);    \
                                                                        \
         NULL != (ITEM);                                                \
                                                                        \
         ((ITERATOR) = (NULL == (ITERATOR)) ?                           \
          (LINKEDLIST)->first : (ITERATOR)->next),                      \
           ((ITEM) = (NULL == (ITERATOR)) ?                             \
            NULL : CONTAINER_OF((ITERATOR), MEMBER, TYPE)))

Run through an Lz_LinkedList like a for loop, with the ability of removing elements from the list while iterating on it.

An iterator must be provided, in the form of a pointer to an allocated Lz_LinkedListElement. In order to remove elements while iterating, the iterator must be updated with the return value of List_Remove.

This foreach implementation is typed, so each loop turn will return a typed pointer to the current loop element (ie. not a pointer to a raw Lz_LinkedListElement).

If the list is empty, no loop is performed, and the execution will continue after the foreach.

With configuration option CHECK_NULL_PARAMETERS_IN_LISTS, this implementation can also verify if the LINKEDLIST pointer is NULL. If so, the loop is not run and the execution continues after the loop.

Parameters

LINKEDLIST	A pointer to the Lz_LinkedList to run through.
TYPE	The real type of the list elements
ITEM	A pointer to a struct of type `TYPE` containing the Lz_LinkedListElement. This pointer will point to the current item of each loop turn. This pointer will never be NULL while the loop is running.
MEMBER	The name of the member in `TYPE` which bears the Lz_LinkedListElement.
ITERATOR	A pointer to an allocated Lz_LinkedListElement that will be used as the loop iterator. This iterator can be updated when removing elements from the list, using the return value of List_Remove.

Definition at line 222 of file list.h.

Function Documentation

◆ List_Append()

void List_Append	(	Lz_LinkedList *const	linkedList,
		Lz_LinkedListElement *const	item
	)

Insert an Lz_LinkedListElement as the last element of an existing Lz_LinkedList.

Parameters

linkedList	A pointer to the linked list head.
item	A pointer to the item to append to the list.

Definition at line 22 of file list.c.

◆ List_Prepend()

void List_Prepend	(	Lz_LinkedList *const	linkedList,
		Lz_LinkedListElement *const	item
	)

Insert an Lz_LinkedListElement as the first element of an existing Lz_LinkedList.

Parameters

linkedList	A pointer to the linked list head.
item	A pointer to the item to prepend to the list.

Definition at line 46 of file list.c.

◆ List_AppendList()

void List_AppendList	(	Lz_LinkedList *const	linkedListDestination,
		Lz_LinkedList *const	linkedListToMove
	)

Move the content of an Lz_LinkedList to the end of an existing Lz_LinkedList.

Parameters

linkedListDestination	A pointer to the Lz_LinkedList on which to append.
linkedListToMove	A pointer to the Lz_LinkedList to move. After the operation, this linked list will be empty.

Definition at line 71 of file list.c.

◆ List_PickFirst()

Lz_LinkedListElement * List_PickFirst ( Lz_LinkedList *const linkedList )

Return the first element of an existing linked list.

This function drops the first element of the list if it exists.

Parameters

linkedList A pointer to the linked list head.

Returns

A pointer to the first element of the list, or NULL if:

The linkedList is empty
The parameter linkedList is NULL

Definition at line 98 of file list.c.

◆ List_PointFirst()

Lz_LinkedListElement * List_PointFirst ( const Lz_LinkedList *const linkedList )

Return a pointer to the first element of an existing linked list.

This function does not drop the first element of the list.

Parameters

linkedList A pointer to an existing Lz_LinkedList.

Returns

A pointer to the first element of the list, or NULL if:

The linkedList is empty
The parameter linkedList is NULL

Definition at line 129 of file list.c.

◆ List_IsEmpty()

bool List_IsEmpty ( const Lz_LinkedList *const linkedList )

Test if an Lz_LinkedList is empty.

Parameters

linkedList A pointer to the Lz_LinkedList to test.

Returns

true if:
- The linkedList is empty
- The parameter linkedList is NULL
false if:
- The linkedList contains at least 1 element

Definition at line 141 of file list.c.

◆ List_InsertAfter()

void List_InsertAfter	(	Lz_LinkedList *const	linkedList,
		Lz_LinkedListElement *const	listItem,
		Lz_LinkedListElement *const	itemToInsert
	)

Insert an element after another in an Lz_LinkedList.

Parameters

linkedList	A pointer to the LinkedList containing the element `listItem` on which to insert after.
listItem	A pointer to an element on which to insert after, already present in the `linkedList`.
itemToInsert	A pointer to the item to insert in the list.

Warning: The listItem parameter MUST already be part of the Lz_LinkedList pointed to by parameter linkedList. No check is performed.

Definition at line 153 of file list.c.

◆ List_InsertBefore()

void List_InsertBefore	(	Lz_LinkedList *const	linkedList,
		Lz_LinkedListElement *const	listItem,
		Lz_LinkedListElement *const	itemToInsert
	)

Insert an element before another in a Lz_LinkedList.

Parameters

linkedList	A pointer to the Lz_LinkedList containing the element `listItem` on which to insert before.
listItem	A pointer to an element on which to insert before, already present in the `linkedList`.
itemToInsert	A pointer to the item to insert in the list.

Warning: The listItem parameter MUST already be part of the Lz_LinkedList pointed to by parameter linkedList. No check is performed.

Definition at line 173 of file list.c.

◆ List_Remove()

Lz_LinkedListElement * List_Remove	(	Lz_LinkedList *const	linkedList,
		Lz_LinkedListElement *const	itemToRemove
	)

Remove an element from an Lz_LinkedList.

Parameters

linkedList	A pointer to the Lz_LinkedList containing the element to remove.
itemToRemove	A pointer to the element to remove from the list.

Returns: A pointer to the previous element of itemToRemove before it is removed. This return value must be used to update an iterator when using List_RemovableForEach, in order to allow removing elements from a list while iterating on it.

Warning: The itemToRemove parameter MUST already be part of the Lz_LinkedList pointed to by parameter linkedList. No check is performed.

Definition at line 197 of file list.c.

◆ List_PointElementAt()

Lz_LinkedListElement * List_PointElementAt	(	const Lz_LinkedList *const	linkedList,
		const size_t	index
	)

Point to an indexed element in an Lz_LinkedList, starting at index 0.

The element will not be removed from the list.

Warning: The complexity of this function is O(n), as it is iterative.

Parameters

linkedList	A pointer to an Lz_LinkedList.
index	The index of the element to point.

Returns: A pointer to the indexed Lz_LinkedListElement, or NULL if the index is out of the boundaries of the list.

Definition at line 229 of file list.c.

◆ List_InitLinkedList()

void List_InitLinkedList ( Lz_LinkedList *const linkedList )

Initialize an Lz_LinkedList.

Parameters

linkedList A pointer to the Lz_LinkedList to initialize.

Definition at line 252 of file list.c.

◆ List_InitLinkedListElement()

void List_InitLinkedListElement ( Lz_LinkedListElement *const item )

Initialize an Lz_LinkedListElement.

Parameters

item	A pointer to the Lz_LinkedListElement to initialize.

Definition at line 266 of file list.c.

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ LINKED_LIST_INIT

◆ LINKED_LIST_ELEMENT_INIT

◆ List_UntypedForEach

◆ List_ForEach

◆ List_RemovableForEach

Function Documentation

◆ List_Append()

◆ List_Prepend()

◆ List_AppendList()

◆ List_PickFirst()

◆ List_PointFirst()

◆ List_IsEmpty()

◆ List_InsertAfter()

◆ List_InsertBefore()

◆ List_Remove()

◆ List_PointElementAt()

◆ List_InitLinkedList()

◆ List_InitLinkedListElement()