Collaboration diagram for Linked List:

Data Structures
struct	linked_list_node
	Intrusive doubly-linked list node. More...

struct	linked_list_head
	The head of a doubly linked list. More...

Macros
#define	__LLIST_INIT(_head)
	Linked list head default init value (one entry)

#define	__INIT_LLIST(_name) _name = __LLIST_INIT(_name)
	Initialize an empty linked list head.

#define	DECLARE_LLIST(_name) llist_t INIT_LLIST(_name)
	Declare empty linked list head.

#define	LLIST_NODE(_name) node_t _name
	Declare an intrusive list node. More...

#define	FOREACH_LLIST(_name, _list)
	Loop over each element inside a linked list. More...

#define	FOREACH_LLIST_SAFE(_name, _tmp, _list)
	Loop over each element inside a linked list in a safer way. More...

#define	FOREACH_LLIST_REVERSE(_name, _list)
	Loop over each element inside a linked list in reverse order. More...

#define	FOREACH_LLIST_SAFE_REVERSE(_name, _tmp, _list)
	Loop over each element inside a linked list in reverse order in a safer way. More...

#define	FOREACH_LLIST_ENTRY(_entry, _list, _field)
	Loop over each entry inside a linked list. More...

#define	FOREACH_LLIST_ENTRY_SAFE(_entry, _tmp, _list, _field)
	Loop over each entry inside a linked list in a safer manner. More...

#define	FOREACH_LLIST_ENTRY_REVERSE(_entry, _list, _field)
	Loop over each entry inside a linked list in reverse order. More...

#define	FOREACH_LLIST_ENTRY_REVERSE_SAFE(_entry, _tmp, _list, _field)
	Loop over each entry inside a linked list in reverse order in a safer manner. More...

#define	llist_head(_list) (&(_list)->head)

#define	llist_entry(ptr, type, member) container_of(ptr, type, member)
	Return the struct containing this list node.

Functions
static node_t *	llist_first (const llist_t *list)

static node_t *	llist_last (const llist_t *list)

static PURE bool	llist_is_empty (const llist_t *list)

static void	__llist_add (node_t new, node_t prev, node_t *next)
	Insert a new entry between two known consecutive ones (internal use only)

static void	__list_remove (node_t prev, node_t next)
	Delete a list entry (internal use only). More...

static void	llist_add_after (node_t prev, node_t new)
	Insert a new entry into a list. More...

static void	llist_add_before (node_t next, node_t new)
	Insert a new entry into a list. More...

static void	llist_add (llist_t list, node_t new)
	Insert a new entry as the first element of the list. More...

static void	llist_add_tail (llist_t list, node_t new)
	Insert a new entry as the last element of the list. More...

static node_t *	llist_remove (node_t *node)
	Remove an entry from a list. More...

static node_t *	llist_pop (llist_t *list)
	Pop the first element in a list. More...

static node_t *	llist_pop_tail (llist_t *list)
	Pop the last element in a list. More...

static void	llist_insert_sorted (llist_t list, node_t new, compare_t compare)
	Insert a new item inside a sorted list in ascending order. More...

static bool	llist_insert_sorted_unique (llist_t list, node_t new, compare_t compare)
	Insert a new item inside a sorted list in ascending order. More...

static node_t *	llist_find_first (const llist_t list, const void data, compare_t compare)
	Retreive the first matching element inside the list (or NULL) More...

Variables
struct linked_list_node *	linked_list_node::next
	Next item in the list.

struct linked_list_node *	linked_list_node::prev
	Previous item in the list.

Detailed Description

Linked list

This is our implementation for doubly linked lists.

Note: We use an intrusive linked list design.

Macro Definition Documentation

◆ FOREACH_LLIST

#define FOREACH_LLIST	(	_name,
		_list
	)

Value:

for (node_t *_name = llist_first(_list); _name != llist_head(_list); \

_name = llist_next(_name))

llist_first

static node_t * llist_first(const llist_t *list)

Definition: linked_list.h:168

llist_head

#define llist_head(_list)

Definition: linked_list.h:165

linked_list_node

Intrusive doubly-linked list node.

Definition: linked_list.h:27

Parameters

_name	The name of the current node
_list	The head of the linked list

◆ FOREACH_LLIST_ENTRY

#define FOREACH_LLIST_ENTRY	(	_entry,
		_list,
		_field
	)

Value:

    for (_entry = llist_entry(llist_first(_list), typeof(*_entry), _field); \
         &_entry->_field != llist_head(_list);                              \
         _entry = llist_entry(llist_next(&_entry->_field), typeof(*_entry), \
                              _field))

Parameters

_entry	The variable used to store the entry
_list	The head of the linked list
_field	The name of the node field inside the entry's structure

◆ FOREACH_LLIST_ENTRY_REVERSE

#define FOREACH_LLIST_ENTRY_REVERSE	(	_entry,
		_list,
		_field
	)

Value:

    for (_entry = llist_entry(llist_last(_list), typeof(*_entry), _field);  \
         &_entry->_field != llist_head(_list);                              \
         _entry = llist_entry(llist_prev(&_entry->_field), typeof(*_entry), \
                              _field))

Parameters

_entry	The variable used to store the entry
_list	The head of the linked list
_field	The name of the node field inside the entry's structure

◆ FOREACH_LLIST_ENTRY_REVERSE_SAFE

#define FOREACH_LLIST_ENTRY_REVERSE_SAFE	(	_entry,
		_tmp,
		_list,
		_field
	)

Value:

    for (_entry = llist_entry(llist_last(_list), typeof(*_entry), _field),    \
        _tmp =                                                                \
             llist_entry(llist_prev(&_entry->_field), typeof(*_tmp), _field); \
         &_entry->_field != llist_head(_list);                                \
         _entry = _tmp, _tmp = llist_entry(llist_prev(&_tmp->_field),         \
                                           typeof(*_entry), _field))

Parameters

_entry	The variable used to store the entry
_tmp	The variable used to store the temporary entry
_list	The head of the linked list
_field	The name of the node field inside the entry's structure

◆ FOREACH_LLIST_ENTRY_SAFE

#define FOREACH_LLIST_ENTRY_SAFE	(	_entry,
		_tmp,
		_list,
		_field
	)

Value:

    for (_entry = llist_entry(llist_first(_list), typeof(*_entry), _field),   \
        _tmp =                                                                \
             llist_entry(llist_next(&_entry->_field), typeof(*_tmp), _field); \
         &_entry->_field != llist_head(_list);                                \
         _entry = _tmp, _tmp = llist_entry(llist_next(&_tmp->_field),         \
                                           typeof(*_entry), _field))

Parameters

_entry	The variable used to store the entry
_tmp	The variable used to store the temporary entry
_list	The head of the linked list
_field	The name of the node field inside the entry's structure

◆ FOREACH_LLIST_REVERSE

#define FOREACH_LLIST_REVERSE	(	_name,
		_list
	)

Value:

for (node_t *_name = llist_last(_list); _name != llist_head(_list); \

_name = llist_prev(_name))

Parameters

_name	The name of the current node
_list	The tail of the linked list

◆ FOREACH_LLIST_SAFE

#define FOREACH_LLIST_SAFE	(	_name,
		_tmp,
		_list
	)

Value:

for (node_t *_name = llist_first(_list), *_tmp = llist_next(_name); \

_name != llist_head(_list); _name = _tmp, _tmp = llist_next(_tmp))

The next element in the list is stored each time, letting us freely release the current one without having to dereference it in the next iteration.

Parameters

_name	The name of the current node
_tmp	The name of the node used to store the next pointer
_list	The head of the list

◆ FOREACH_LLIST_SAFE_REVERSE

#define FOREACH_LLIST_SAFE_REVERSE	(	_name,
		_tmp,
		_list
	)

Value:

for (node_t *_name = llist_last(_list), *_tmp = llist_prev(_name); \

_name != llist_head(_list); _name = _tmp, _tmp = llist_prev(_tmp))

The prev element in the list is stored each time, letting us freely release the current one without having to dereference it in the next iteration.

Parameters

_name	The name of the current node
_tmp	The name of the node used to store the prev pointer
_list	The tail of the linked list

◆ llist_head

#define llist_head ( _list ) (&(_list)->head)

Returns: the given list's head

◆ LLIST_NODE

#define LLIST_NODE ( _name ) node_t _name

Should be put inside a struct definition.

Function Documentation

◆ __list_remove()

static void __list_remove	(	node_t *	prev,
		node_t *	next
	)

inlinestatic

Parameters

prev	The node before the deleted entry
next	The node after the deleted entry

◆ llist_add()

static void llist_add	(	llist_t *	list,
		node_t *	new
	)

inlinestatic

Parameters

list	list to add into
new	list entry to be added

◆ llist_add_after()

static void llist_add_after	(	node_t *	prev,
		node_t *	new
	)

inlinestatic

Parameters

prev	list entry to add it after
new	list entry to be added

◆ llist_add_before()

static void llist_add_before	(	node_t *	next,
		node_t *	new
	)

inlinestatic

Parameters

next	list entry to add it before
new	list entry to be added

◆ llist_add_tail()

static void llist_add_tail	(	llist_t *	list,
		node_t *	new
	)

inlinestatic

Parameters

list	list to add into
new	list entry to be added

◆ llist_find_first()

static node_t * llist_find_first	(	const llist_t *	list,
		const void *	data,
		compare_t	compare
	)

inlinestatic

Parameters

list	The list's head
data	The data to be matched against
compare	The function used to compare the nodes and the data (`data` is passed as its second argument)

Returns: The first matching node, or NULL

◆ llist_first()

static node_t * llist_first ( const llist_t * list )

inlinestatic

Returns: the given list's first entry

◆ llist_insert_sorted()

static void llist_insert_sorted	(	llist_t *	list,
		node_t *	new,
		compare_t	compare
	)

inlinestatic

Parameters

list	The list's head
new	The node to be inserted
compare	The comparison function used to keep the list sorted (new is passed as its first argument when called)

◆ llist_insert_sorted_unique()

static bool llist_insert_sorted_unique	(	llist_t *	list,
		node_t *	new,
		compare_t	compare
	)

inlinestatic

Similar to llist_insert_sorted(), but does not create a duplicate.

Parameters

list	The list's head
new	The node to be inserted
compare	The comparison function used to keep the list sorted (`new` is passed as its first argument)

Returns: true if the element was inserted.

◆ llist_is_empty()

static PURE bool llist_is_empty ( const llist_t * list )

inlinestatic

Returns: Whether a list is empty

◆ llist_last()

static node_t * llist_last ( const llist_t * list )

inlinestatic

Returns: the given list's last entry

◆ llist_pop()

static node_t * llist_pop ( llist_t * list )

inlinestatic

Parameters

list	A linked list's sentinel

Returns: The list's previous first node, or NULL if empty

◆ llist_pop_tail()

static node_t * llist_pop_tail ( llist_t * list )

inlinestatic

Parameters

list	A linked list's sentinel

Returns: The list's previous tail, or NULL if empty

◆ llist_remove()

static node_t * llist_remove ( node_t * node )

inlinestatic

Parameters

node	The entry to remove

Returns: The removed entry

Data Structures

Macros

Functions

Variables

Detailed Description

Linked list

Macro Definition Documentation

◆ FOREACH_LLIST

◆ FOREACH_LLIST_ENTRY

◆ FOREACH_LLIST_ENTRY_REVERSE

◆ FOREACH_LLIST_ENTRY_REVERSE_SAFE

◆ FOREACH_LLIST_ENTRY_SAFE

◆ FOREACH_LLIST_REVERSE

◆ FOREACH_LLIST_SAFE

◆ FOREACH_LLIST_SAFE_REVERSE

◆ llist_head

◆ LLIST_NODE

Function Documentation

◆ __list_remove()

◆ llist_add()

◆ llist_add_after()

◆ llist_add_before()

◆ llist_add_tail()

◆ llist_find_first()

◆ llist_first()

◆ llist_insert_sorted()

◆ llist_insert_sorted_unique()

◆ llist_is_empty()

◆ llist_last()

◆ llist_pop()

◆ llist_pop_tail()

◆ llist_remove()