Singly linked list

Intrusive singly linked list. More...

Data Structures
struct	SingleListNode
	Singly linked list node, embedded in the listed structure. More...

Macros
#define	SINGLE_LIST_NODE_NULL   {.next = NULL}
	Initializer of an unlinked node.

Typedefs
typedef bool(*	SingleListFilterCallback) (SingleListNode *found_node, void *data)
	Filter for slist_find().
typedef bool(*	SingleListForEachCallback) (SingleListNode *node, void *context)
	Callback for slist_foreach().

Functions
void	slist_init (SingleListNode *node)
	Initialize a node as unlinked.
SingleListNode *	slist_insert_after (SingleListNode *node, SingleListNode *new_node)
	Insert a node after another one.
SingleListNode *	slist_prepend (SingleListNode *head, SingleListNode *new_node)
	Prepend a node to a list.
SingleListNode *	slist_append (SingleListNode *head, SingleListNode *new_node)
	Append a node to the tail of a list.
SingleListNode *	slist_pop_head (SingleListNode *head)
	Unlink the head of a list.
void	slist_remove (SingleListNode *node, SingleListNode **head)
	Unlink a node from a list.
SingleListNode *	slist_get_next (SingleListNode *node)
	Get the next node.
SingleListNode *	slist_get_tail (SingleListNode *node)
	Get the tail of a list.
bool	slist_is_tail (const SingleListNode *node)
	Check whether a node is the tail of its list.
uint32_t	slist_count (SingleListNode *head)
	Count the nodes of a list.
bool	slist_contains (const SingleListNode *head, const SingleListNode *node)
	Check whether a list contains a node.
SingleListNode *	slist_find (SingleListNode *head, SingleListFilterCallback filter_callback, void *data)
	Find the first matching node.
SingleListNode *	slist_sorted_add (SingleListNode *head, SingleListNode *new_node, Comparator comparator, bool ascending)
	Insert a node into a sorted list, keeping it sorted.
SingleListNode *	slist_concatenate (SingleListNode *list_a, SingleListNode *list_b)
	Append a list to another one.
void	slist_foreach (SingleListNode *head, SingleListForEachCallback each_cb, void *context)
	Call a function on each node of a list.
void	slist_debug_dump (SingleListNode *head)
	Log every node of a list with UTIL_LOG().

Detailed Description

Intrusive singly linked list.

Like Linked list with half the per-node overhead, at the cost of linear-time removal. A list is referenced by its head.

struct waiter {
  SingleListNode node;
  int id;
};
 
static SingleListNode *s_waiters;
 
s_waiters = slist_prepend(s_waiters, &w->node);
 
for (SingleListNode *n = s_waiters; n != NULL; n = slist_get_next(n)) {
  struct waiter *it = container_of(n, struct waiter, node);
  ...
}
 
slist_remove(&w->node, &s_waiters);

---

Data Structure Documentation

SingleListNode

struct SingleListNode

Singly linked list node, embedded in the listed structure.

Data Fields
struct SingleListNode *	next	Next node, or NULL.

Macro Definition Documentation

SINGLE_LIST_NODE_NULL

#define SINGLE_LIST_NODE_NULL   {.next = NULL}

Initializer of an unlinked node.

Typedef Documentation

SingleListFilterCallback

typedef bool(* SingleListFilterCallback) (SingleListNode *found_node, void *data)

Filter for slist_find().

Parameters

found_node	Node to check.
data	Callback data.

Returns

true if found_node matches.

SingleListForEachCallback

typedef bool(* SingleListForEachCallback) (SingleListNode *node, void *context)

Callback for slist_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

slist_append()

SingleListNode * slist_append	(	SingleListNode *	head,
		SingleListNode *	new_node
	)

Append a node to the tail of a list.

Parameters

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

Returns

new_node, the new tail.

slist_concatenate()

SingleListNode * slist_concatenate	(	SingleListNode *	list_a,
		SingleListNode *	list_b
	)

Append a list to another one.

Parameters

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

Returns

Head of the resulting list.

slist_contains()

bool slist_contains	(	const SingleListNode *	head,
		const SingleListNode *	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 in the list.

slist_count()

uint32_t slist_count

(

SingleListNode *

head

)

Count the nodes of a list.

Parameters

head	Head of the list, may be NULL.

Returns

Number of nodes.

slist_debug_dump()

void slist_debug_dump

(

SingleListNode *

head

)

Log every node of a list with UTIL_LOG().

Parameters

head	Head of the list.

slist_find()

SingleListNode * slist_find	(	SingleListNode *	head,
		SingleListFilterCallback	filter_callback,
		void *	data
	)

Find the first matching node.

Parameters

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

Returns

Matching node, or NULL.

slist_foreach()

void slist_foreach	(	SingleListNode *	head,
		SingleListForEachCallback	each_cb,
		void *	context
	)

Call a function on each node of a list.

Parameters

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

slist_get_next()

SingleListNode * slist_get_next

(

SingleListNode *

node

)

Get the next node.

Parameters

node	Node, may be NULL.

Returns

Next node, or NULL.

slist_get_tail()

SingleListNode * slist_get_tail

(

SingleListNode *

node

)

Get the tail of a list.

Parameters

node	Any node in the list, may be NULL.

Returns

Tail, or NULL for NULL.

slist_init()

void slist_init

(

SingleListNode *

node

)

Initialize a node as unlinked.

Parameters

[out]

node

Node.

slist_insert_after()

SingleListNode * slist_insert_after	(	SingleListNode *	node,
		SingleListNode *	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.

slist_is_tail()

bool slist_is_tail

(

const SingleListNode *

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.

slist_pop_head()

SingleListNode * slist_pop_head

(

SingleListNode *

head

)

Unlink the head of a list.

Parameters

head	Head of the list, may be NULL.

Returns

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

slist_prepend()

SingleListNode * slist_prepend	(	SingleListNode *	head,
		SingleListNode *	new_node
	)

Prepend a node to a list.

Parameters

head	Head of the list, or NULL for an empty list.
new_node	Node to prepend, may be NULL.

Returns

New head of the list.

slist_remove()

void slist_remove	(	SingleListNode *	node,
		SingleListNode **	head
	)

Unlink a node from a list.

Nothing is done if node is not in the list.

Parameters

	node	Node to remove.
[in,out]	head	Head of the list, updated if it is node.

slist_sorted_add()

SingleListNode * slist_sorted_add	(	SingleListNode *	head,
		SingleListNode *	new_node,
		Comparator	comparator,
		bool	ascending
	)

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

Existing nodes are not sorted. 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.