list_template.h File Reference

Intrusive circular doubly linked list. More...

#include <stdbool.h>
#include <stddef.h>
#include <assert.h>

Go to the source code of this file.

Classes
struct	list_node
	Intrusive list node structure. More...

Macros
#define	PASTE(a, b)
	Paste two tokens together.
#define	XPASTE(a, b)
	First expand tokens, then paste them together.
#define	JOIN(a, b)
	First expand tokens, then paste them together with a _ in between.
#define	FUNCTION_DEFINITIONS
	Define the functions.
#define	TYPE_DEFINITIONS
	Define the types.
#define	FUNCTION_LINKAGE
	Specify function linkage e.g. static inline.
#define	LIST_FOR_EACH(node_ptr, head_ptr)
	Iterate over a list.
#define	LIST_FOR_EACH_REVERSE(node_ptr, head_ptr)
	Iterate over a list in reverse.
#define	LIST_FOR_EACH_SAFE(node_ptr, next_ptr, head_ptr)
	Iterate over a list while allowing the current node to be modified.
#define	LIST_FOR_EACH_REVERSE_SAFE(node_ptr, prev_ptr, head_ptr)
	Iterate over a list in reverse while allowing the current node to be modified.

Functions
void	list_node_init (list_node_type *node_ptr)
	Initialize a list node.
bool	list_node_is_first (const list_node_type *head_ptr, const list_node_type *node_ptr)
	Check if a given list node is first in the list (aka after the head).
bool	list_node_is_last (const list_node_type *head_ptr, const list_node_type *node_ptr)
	Check if a given list node is the last of the list (aka before the head).
bool	list_node_is_singular (const list_node_type *node_ptr)
	Check if a given list node is singular (and initialized).
void	list_node_add_after (list_node_type *prev_ptr, list_node_type *node_ptr)
	Add a node after the given node.
void	list_node_add_before (list_node_type *next_ptr, list_node_type *node_ptr)
	Add a node before the given node.
list_node_type *	list_node_remove (list_node_type *node_ptr)
	Remove a node from the list it resides in.
void	list_node_replace (list_node_type *restrict old_ptr, list_node_type *restrict new_ptr)
	Replace a given node by a new node.

Detailed Description

Intrusive circular doubly linked list.

Inspired by:

• https://github.com/torvalds/linux/blob/master/include/linux/list.h

Macro Definition Documentation

JOIN

#define JOIN	(		a,
			b )

Value:

XPASTE(a, XPASTE(_, b))

First expand tokens, then paste them together with a _ in between.

LIST_FOR_EACH

#define LIST_FOR_EACH	(		node_ptr,
			head_ptr )

Value:

for ((node_ptr) = (head_ptr)->next_ptr; (node_ptr) != (head_ptr); (node_ptr) = (node_ptr)->next_ptr)

Iterate over a list.

Parameters

node_ptr	Current node pointer.
head_ptr	List head pointer.

Examples

list_example.c.

LIST_FOR_EACH_REVERSE

#define LIST_FOR_EACH_REVERSE	(		node_ptr,
			head_ptr )

Value:

for ((node_ptr) = (head_ptr)->prev_ptr; (node_ptr) != (head_ptr); (node_ptr) = (node_ptr)->prev_ptr)

Iterate over a list in reverse.

Parameters

node_ptr	Current node pointer.
head_ptr	List head pointer.

Examples

list_example.c.

LIST_FOR_EACH_REVERSE_SAFE

#define LIST_FOR_EACH_REVERSE_SAFE	(		node_ptr,
			prev_ptr,
			head_ptr )

Value:

for ((node_ptr) = (head_ptr)->prev_ptr, (prev_ptr) = (node_ptr)->prev_ptr; (node_ptr) != (head_ptr); \
     (node_ptr) = (prev_ptr), (prev_ptr) = (node_ptr)->prev_ptr)

Iterate over a list in reverse while allowing the current node to be modified.

Parameters

node_ptr	Current node pointer.
prev_ptr	Temporary pointer to the previous node.
head_ptr	List head pointer.

Examples

list_example.c.

LIST_FOR_EACH_SAFE

#define LIST_FOR_EACH_SAFE	(		node_ptr,
			next_ptr,
			head_ptr )

Value:

for ((node_ptr) = (head_ptr)->next_ptr, (next_ptr) = (node_ptr)->next_ptr; (node_ptr) != (head_ptr); \
     (node_ptr) = (next_ptr), (next_ptr) = (node_ptr)->next_ptr)

Iterate over a list while allowing the current node to be modified.

Parameters

node_ptr	Current node pointer.
next_ptr	Temporary pointer to the next node.
head_ptr	List head pointer.

Examples

list_example.c.

PASTE

#define PASTE	(		a,
			b )

Value:

a##b

Paste two tokens together.

XPASTE

#define XPASTE	(		a,
			b )

Value:

PASTE(a, b)

First expand tokens, then paste them together.

Function Documentation

list_node_add_after()

void list_node_add_after	(	list_node_type *	prev_ptr,
		list_node_type *	node_ptr )

Add a node after the given node.

Note

This can be used to construct a stack.

Parameters

[in]	node_ptr	The node pointer.
[in]	prev_ptr	The prev node pointer.

Examples

list_example.c.

list_node_add_before()

void list_node_add_before	(	list_node_type *	next_ptr,
		list_node_type *	node_ptr )

Add a node before the given node.

Note

This can be used to construct a queue.

Parameters

[in]	node_ptr	The node pointer.
[in]	next_ptr	The next node pointer.

Examples

list_example.c.

list_node_init()

void list_node_init

(

list_node_type *

node_ptr

)

Initialize a list node.

Parameters

[in]

node_ptr

The node pointer.

Examples

list_example.c.

list_node_is_first()

bool list_node_is_first	(	const list_node_type *	head_ptr,
		const list_node_type *	node_ptr )

Check if a given list node is first in the list (aka after the head).

Precondition

both nodes are part of the same list.

Parameters

[in]	head_ptr	The head node pointer.
[in]	node_ptr	The node pointer.

Returns

Whether the list node is first in the list.

Examples

list_example.c.

list_node_is_last()

bool list_node_is_last	(	const list_node_type *	head_ptr,
		const list_node_type *	node_ptr )

Check if a given list node is the last of the list (aka before the head).

Precondition

both nodes are part of the same list.

Parameters

[in]	head_ptr	The head node pointer.
[in]	node_ptr	The node pointer.

Returns

Whether the list node is the last in the list.

Examples

list_example.c.

list_node_is_singular()

bool list_node_is_singular

(

const list_node_type *

node_ptr

)

Check if a given list node is singular (and initialized).

Parameters

[in]

node_ptr

The node pointer.

Returns

Whether the list node is singular.

Examples

list_example.c.

list_node_remove()

list_node_type * list_node_remove

(

list_node_type *

node_ptr

)

Remove a node from the list it resides in.

Precondition

The node is a part of a list.

Parameters

[in]

node_ptr

The node pointer.

Returns

The removed node, now initialized as a singular node.

Examples

list_example.c.

list_node_replace()

void list_node_replace	(	list_node_type *restrict	old_ptr,
		list_node_type *restrict	new_ptr )

Replace a given node by a new node.

Precondition

The old node is a part of a list while the new node is not.

Parameters

[in]	old_ptr	Pointer to old node.
[in]	new_ptr	Pointer to new node.

Examples

list_example.c.