Intrusive doubly linked list. More...

Data Structures
struct	ListNode
	List node, embedded in the listed structure. More...

Macros
#define	LIST_NODE_NULL {.next = NULL, .prev = NULL}
	Initializer of an unlinked node.

Typedefs
typedef bool(*	ListFilterCallback) (ListNode found_node, void data)
	Filter for list_find() and its variants.

typedef bool(*	ListForEachCallback) (ListNode node, void context)
	Callback for list_foreach().

Functions
void	list_init (ListNode *head)
	Initialize a node as unlinked.

ListNode *	list_insert_after (ListNode node, ListNode new_node)
	Insert a node after another one.

ListNode *	list_insert_before (ListNode node, ListNode new_node)
	Insert a node before another one.

ListNode *	list_pop_head (ListNode *node)
	Unlink the head of a list.

ListNode *	list_pop_tail (ListNode *node)
	Unlink the tail of a list.

void	list_remove (ListNode node, ListNode head, ListNode *tail)
	Unlink a node from its list.

ListNode *	list_append (ListNode node, ListNode new_node)
	Append a node to the tail of a list.

ListNode *	list_prepend (ListNode node, ListNode new_node)
	Prepend a node to the head of a list.

ListNode *	list_get_next (ListNode *node)
	Get the next node.

ListNode *	list_get_prev (ListNode *node)
	Get the previous node.

ListNode *	list_get_tail (ListNode *node)
	Get the tail of a list.

ListNode *	list_get_head (ListNode *node)
	Get the head of a list.

bool	list_is_head (const ListNode *node)
	Check whether a node is the head of its list.

bool	list_is_tail (const ListNode *node)
	Check whether a node is the tail of its list.

uint32_t	list_count_to_tail_from (ListNode *node)
	Count the nodes from a node to the tail.

uint32_t	list_count_to_head_from (ListNode *node)
	Count the nodes from a node to the head.

uint32_t	list_count (ListNode *node)
	Count the nodes of a list.

ListNode *	list_get_at (ListNode *node, int32_t index)
	Get the node at a distance from another one.

ListNode *	list_sorted_add (ListNode head, ListNode new_node, Comparator comparator, bool ascending)
	Insert a node into a sorted list, keeping it sorted.

bool	list_contains (const ListNode head, const ListNode node)
	Check whether a list contains a node.

ListNode *	list_find (ListNode node, ListFilterCallback filter_callback, void data)
	Find the first matching node, from a node towards the tail.

ListNode *	list_find_next (ListNode node, ListFilterCallback filter_callback, bool wrap_around, void data)
	Find the next matching node after a node.

ListNode *	list_find_prev (ListNode node, ListFilterCallback filter_callback, bool wrap_around, void data)
	Find the previous matching node before a node.

ListNode *	list_concatenate (ListNode list_a, ListNode list_b)
	Append a list to another one.

void	list_foreach (ListNode head, ListForEachCallback each_cb, void context)
	Call a function on each node, from a node to the tail.

void	list_debug_dump (ListNode *head)
	Log every node from a node to the tail with UTIL_LOG().

Detailed Description

Intrusive doubly linked list.

A list is a chain of ListNode embedded in the caller's structures; there is no separate list object, a list is referenced by any of its nodes, usually its head. Functions that take "any node" walk to the head or tail as needed. Nothing is allocated and there is no locking.

struct job {
  ListNode node;
  int id;
};
 
static ListNode *s_jobs;
 
s_jobs = list_prepend(s_jobs, &job->node);
 
for (ListNode *n = s_jobs; n != NULL; n = list_get_next(n)) {
  struct job *j = container_of(n, struct job, node);
  ...
}
 
list_remove(&job->node, &s_jobs, NULL);

Data Structure Documentation

◆ ListNode

struct ListNode

List node, embedded in the listed structure.

Data Fields
struct ListNode *	next	Next node, towards the tail, or NULL.
struct ListNode *	prev	Previous node, towards the head, or NULL.

Macro Definition Documentation

◆ LIST_NODE_NULL

#define LIST_NODE_NULL {.next = NULL, .prev = NULL}

Initializer of an unlinked node.

Typedef Documentation

◆ ListFilterCallback

typedef bool(* ListFilterCallback) (ListNode *found_node, void *data)

Filter for list_find() and its variants.

Parameters

found_node	Node to check.
data	Callback data.

Returns: true if found_node matches.

◆ ListForEachCallback

typedef bool(* ListForEachCallback) (ListNode *node, void *context)

Callback for list_foreach().

The callback may unlink or free node.

Parameters

node	Current node.
context	Callback data.

Returns: true to continue iterating, false to stop.

Function Documentation

◆ list_append()

ListNode * list_append	(	ListNode *	node,
		ListNode *	new_node
	)

Append a node to the tail of a list.

Parameters

node	Any node in the list, or NULL for an empty list.
new_node	Node to append.

Returns: new_node, the new tail.

◆ list_concatenate()

ListNode * list_concatenate	(	ListNode *	list_a,
		ListNode *	list_b
	)

Append a list to another one.

Nothing is done when both nodes are already in the same list.

Parameters

list_a	Any node of the first list, may be NULL.
list_b	Any node of the list to append, may be NULL.

Returns: Head of the resulting list.

◆ list_contains()

bool list_contains	(	const ListNode *	head,
		const ListNode *	node
	)

Check whether a list contains a node.

Parameters

head	Head of the list, may be NULL.
node	Node to search for.

Returns: true if node is at or after head.

◆ list_count()

uint32_t list_count ( ListNode * node )

Count the nodes of a list.

Parameters

node	Any node in the list, may be NULL.

Returns: Number of nodes.

◆ list_count_to_head_from()

uint32_t list_count_to_head_from ( ListNode * node )

Count the nodes from a node to the head.

Parameters

node	Starting node, counted. May be NULL.

Returns: Number of nodes.

◆ list_count_to_tail_from()

uint32_t list_count_to_tail_from ( ListNode * node )

Count the nodes from a node to the tail.

Parameters

node	Starting node, counted. May be NULL.

Returns: Number of nodes.

◆ list_debug_dump()

void list_debug_dump ( ListNode * head )

Log every node from a node to the tail with UTIL_LOG().

Parameters

head	Starting node.

◆ list_find()

ListNode * list_find	(	ListNode *	node,
		ListFilterCallback	filter_callback,
		void *	data
	)

Find the first matching node, from a node towards the tail.

Parameters

node	Node to start from, included in the search. May be NULL.
filter_callback	Filter.
data	Filter data.

Returns: Matching node, or NULL.

◆ list_find_next()

ListNode * list_find_next	(	ListNode *	node,
		ListFilterCallback	filter_callback,
		bool	wrap_around,
		void *	data
	)

Find the next matching node after a node.

Parameters

node	Node to start after. May be NULL.
filter_callback	Filter.
wrap_around	Continue from the head after reaching the tail, up to and including `node`.
data	Filter data.

Returns: Matching node, or NULL.

◆ list_find_prev()

ListNode * list_find_prev	(	ListNode *	node,
		ListFilterCallback	filter_callback,
		bool	wrap_around,
		void *	data
	)

Find the previous matching node before a node.

Parameters

node	Node to start before. May be NULL.
filter_callback	Filter.
wrap_around	Continue from the tail after reaching the head, up to and including `node`.
data	Filter data.

Returns: Matching node, or NULL.

◆ list_foreach()

void list_foreach	(	ListNode *	head,
		ListForEachCallback	each_cb,
		void *	context
	)

Call a function on each node, from a node to the tail.

Parameters

head	Starting node, may be NULL.
each_cb	Callback; it may unlink or free the node it gets.
context	Callback data.

◆ list_get_at()

ListNode * list_get_at	(	ListNode *	node,
		int32_t	index
	)

Get the node at a distance from another one.

Parameters

node	Starting node.
index	Number of nodes to move, towards the tail if positive, the head if negative.

Returns: Node found, or NULL if the list ends first.

◆ list_get_head()

ListNode * list_get_head ( ListNode * node )

Get the head of a list.

Parameters

node	Any node in the list, may be NULL.

Returns: Head, or NULL for NULL.

◆ list_get_next()

ListNode * list_get_next ( ListNode * node )

Get the next node.

Parameters

node	Node, may be NULL.

Returns: Next node, or NULL.

◆ list_get_prev()

ListNode * list_get_prev ( ListNode * node )

Get the previous node.

Parameters

node	Node, may be NULL.

Returns: Previous node, or NULL.

◆ list_get_tail()

ListNode * list_get_tail ( ListNode * node )

Get the tail of a list.

Parameters

node	Any node in the list, may be NULL.

Returns: Tail, or NULL for NULL.

◆ list_init()

void list_init ( ListNode * head )

Initialize a node as unlinked.

Parameters

[out] head Node.

◆ list_insert_after()

ListNode * list_insert_after	(	ListNode *	node,
		ListNode *	new_node
	)

Insert a node after another one.

Parameters

node	Node to insert after, may be NULL.
new_node	Node to insert.

Returns: new_node.

◆ list_insert_before()

ListNode * list_insert_before	(	ListNode *	node,
		ListNode *	new_node
	)

Insert a node before another one.

Parameters

node	Node to insert before, may be NULL.
new_node	Node to insert.

Returns: new_node, which is the new head only when node was the head.

◆ list_is_head()

bool list_is_head ( const ListNode * node )

Check whether a node is the head of its list.

Parameters

node	Node, may be NULL.

Returns: true if node has no previous node, false for NULL.

◆ list_is_tail()

bool list_is_tail ( const ListNode * node )

Check whether a node is the tail of its list.

Parameters

node	Node, may be NULL.

Returns: true if node has no next node, false for NULL.

◆ list_pop_head()

ListNode * list_pop_head ( ListNode * node )

Unlink the head of a list.

Parameters

node	Any node in the list, may be NULL.

Returns: New head, or NULL if the list is now empty.

◆ list_pop_tail()

ListNode * list_pop_tail ( ListNode * node )

Unlink the tail of a list.

Parameters

node	Any node in the list, may be NULL.

Returns: New tail, or NULL if the list is now empty.

◆ list_prepend()

ListNode * list_prepend	(	ListNode *	node,
		ListNode *	new_node
	)

Prepend a node to the head of a list.

Parameters

node	Any node in the list, or NULL for an empty list.
new_node	Node to prepend.

Returns: new_node, the new head.

◆ list_remove()

void list_remove	(	ListNode *	node,
		ListNode **	head,
		ListNode **	tail
	)

Unlink a node from its list.

Parameters

	node	Node to remove, may be NULL.
[in,out]	head	Head of the list, updated if it is `node`. May be NULL.
[in,out]	tail	Tail of the list, updated if it is `node`. May be NULL.

◆ list_sorted_add()

ListNode * list_sorted_add	(	ListNode *	head,
		ListNode *	new_node,
		Comparator	comparator,
		bool	ascending
	)

Insert a node into a sorted list, keeping it sorted.

Existing nodes are not sorted. The node goes before the first node that sorts after it, so equal nodes keep their insertion order.

Parameters

head	Head of the list, or NULL for an empty list.
new_node	Node to insert.
comparator	Called with an existing node and `new_node`; see Comparator.
ascending	true to keep the list in ascending order from head to tail.

Returns: New head of the list.

Data Structures

Macros

Typedefs

Functions

Detailed Description

Data Structure Documentation

◆ ListNode

Macro Definition Documentation

◆ LIST_NODE_NULL

Typedef Documentation

◆ ListFilterCallback

◆ ListForEachCallback

Function Documentation

◆ list_append()

◆ list_concatenate()

◆ list_contains()

◆ list_count()

◆ list_count_to_head_from()

◆ list_count_to_tail_from()

◆ list_debug_dump()

◆ list_find()

◆ list_find_next()

◆ list_find_prev()

◆ list_foreach()

◆ list_get_at()

◆ list_get_head()

◆ list_get_next()

◆ list_get_prev()

◆ list_get_tail()

◆ list_init()

◆ list_insert_after()

◆ list_insert_before()

◆ list_is_head()

◆ list_is_tail()

◆ list_pop_head()

◆ list_pop_tail()

◆ list_prepend()

◆ list_remove()

◆ list_sorted_add()