Intrusive Linked Lists

Zero-allocation macros for pushing/popping nodes in intrusive linked lists. More...

Macros
#define	DLL_PUSH_BACK_NP(f, l, n, next, prev)
	Pushes a node to the back of a doubly linked list (Custom pointer names).
#define	DLL_PUSH_BACK(f, l, n)
	Pushes a node to the back of a doubly linked list.
#define	DLL_PUSH_FRONT(f, l, n)
	Pushes a node to the front of a doubly linked list.
#define	DLL_REMOVE_NP(f, l, n, next, prev)
	Removes a node from a doubly linked list (Custom pointer names).
#define	DLL_REMOVE(f, l, n)
	Removes a node from a doubly linked list.
#define	SLL_QUEUE_PUSH_N(f, l, n, next)
	Pushes a node to a singly linked queue (Custom pointer name).
#define	SLL_QUEUE_PUSH(f, l, n)
	Pushes a node to the back of a singly linked queue.
#define	SLL_STACK_PUSH_N(f, n, next)
	Pushes a node to the top of a singly linked stack (Custom pointer name).
#define	SLL_STACK_PUSH(f, n)
	Pushes a node to the top of a singly linked stack.
#define	SLL_STACK_POP_N(f, next)
	Pops a node from the top of a singly linked stack (Custom pointer name).
#define	SLL_STACK_POP(f)
	Pops a node from the top of a singly linked stack.

Detailed Description

Zero-allocation macros for pushing/popping nodes in intrusive linked lists.

Intrusive linked lists require the data structures to contain their own next and/or prev pointers. These macros handle the pointer wiring automatically without needing to call malloc or wrap your data in a generic node struct.

Warning

These macros evaluate their arguments multiple times. Do not pass expressions with side-effects (e.g., DLL_PUSH_BACK(head, tail, new_nodes[i++])).

Macro Definition Documentation

DLL_PUSH_BACK

#define DLL_PUSH_BACK	(		f,
			l,
			n )

Value:

DLL_PUSH_BACK_NP(f, l, n, next, prev)

Pushes a node to the back of a doubly linked list.

Assumes the node struct has pointers exactly named next and prev.

Example:

struct Node { struct Node *next; struct Node *prev; int id; };
struct Node *head = NULL;
struct Node *tail = NULL;
struct Node my_node = { .id = 1 };
 
DLL_PUSH_BACK(head, tail, &my_node);

Parameters

f	Pointer to the first (head) element.
l	Pointer to the last (tail) element.
n	Pointer to the new node to insert.

Definition at line 473 of file base_macros.h.

DLL_PUSH_BACK_NP

#define DLL_PUSH_BACK_NP	(		f,
			l,
			n,
			next,
			prev )

Value:

((f) == 0 ? ((f) = (l) = (n), (n)->next = (n)->prev = 0)                                   \
      : ((n)->prev = (l), (l)->next = (n), (l) = (n), (n)->next = 0))

Pushes a node to the back of a doubly linked list (Custom pointer names).

Parameters

f	Pointer to the first (head) element of the list.
l	Pointer to the last (tail) element of the list.
n	Pointer to the new node to insert.
next	The literal variable name of the 'next' pointer inside the struct.
prev	The literal variable name of the 'prev' pointer inside the struct.

Definition at line 450 of file base_macros.h.

DLL_PUSH_FRONT

#define DLL_PUSH_FRONT	(		f,
			l,
			n )

Value:

DLL_PUSH_BACK_NP(l, f, n, prev, next)

Pushes a node to the front of a doubly linked list.

Assumes the node struct has pointers exactly named next and prev.

Parameters

f	Pointer to the first (head) element.
l	Pointer to the last (tail) element.
n	Pointer to the new node to insert.

Definition at line 484 of file base_macros.h.

DLL_REMOVE

#define DLL_REMOVE	(		f,
			l,
			n )

Value:

DLL_REMOVE_NP(f, l, n, next, prev)

Removes a node from a doubly linked list.

Safely unlinks the node and updates the head/tail pointers if the node was at the boundary of the list. Assumes next and prev pointers.

Parameters

f	Pointer to the first (head) element.
l	Pointer to the last (tail) element.
n	Pointer to the node to remove.

Definition at line 509 of file base_macros.h.

DLL_REMOVE_NP

#define DLL_REMOVE_NP	(		f,
			l,
			n,
			next,
			prev )

Value:

((f) == (n)   ? ((f) == (l) ? ((f) = (l) = (0)) : ((f) = (f)->next, (f)->prev = 0))        \
 : (l) == (n) ? ((l) = (l)->prev, (l)->next = 0)                                           \
          : ((n)->next->prev = (n)->prev, (n)->prev->next = (n)->next))

Removes a node from a doubly linked list (Custom pointer names).

Parameters

f	Pointer to the first (head) element of the list.
l	Pointer to the last (tail) element of the list.
n	Pointer to the node to remove (must currently be in the list).
next	The literal variable name of the 'next' pointer.
prev	The literal variable name of the 'prev' pointer.

Definition at line 494 of file base_macros.h.

SLL_QUEUE_PUSH

#define SLL_QUEUE_PUSH	(		f,
			l,
			n )

Value:

SLL_QUEUE_PUSH_N(f, l, n, next)

Pushes a node to the back of a singly linked queue.

Adds to the tail (l). Assumes the node struct has a pointer named next.

Parameters

f	Pointer to the first (head) element.
l	Pointer to the last (tail) element.
n	Pointer to the new node to insert.

Definition at line 530 of file base_macros.h.

SLL_QUEUE_PUSH_N

#define SLL_QUEUE_PUSH_N	(		f,
			l,
			n,
			next )

Value:

(((f) == 0 ? (f) = (l) = (n) : ((l)->next = (n), (l) = (n))), (n)->next = 0)

Pushes a node to a singly linked queue (Custom pointer name).

Parameters

f	Pointer to the first (head) element.
l	Pointer to the last (tail) element.
n	Pointer to the new node.
next	The literal variable name of the 'next' pointer.

Definition at line 518 of file base_macros.h.

SLL_STACK_POP

#define SLL_STACK_POP

(

f

)

Value:

SLL_STACK_POP_N(f, next)

Pops a node from the top of a singly linked stack.

Advances the head pointer to the next element. It does not return the popped node, it merely updates the pointer. Assumes the node struct has a pointer named next.

Parameters

f	Pointer to the top (head) element.

Definition at line 565 of file base_macros.h.

SLL_STACK_POP_N

#define SLL_STACK_POP_N	(		f,
			next )

Value:

((f) == 0 ? 0 : ((f) = (f)->next))

Pops a node from the top of a singly linked stack (Custom pointer name).

Parameters

f	Pointer to the top (head) element.
next	The literal variable name of the 'next' pointer.

Definition at line 555 of file base_macros.h.

SLL_STACK_PUSH

#define SLL_STACK_PUSH	(		f,
			n )

Value:

SLL_STACK_PUSH_N(f, n, next)

Pushes a node to the top of a singly linked stack.

Adds to the head (f). Assumes the node struct has a pointer named next.

Parameters

f	Pointer to the top (head) element.
n	Pointer to the new node to insert.

Definition at line 548 of file base_macros.h.

SLL_STACK_PUSH_N

#define SLL_STACK_PUSH_N	(		f,
			n,
			next )

Value:

((n)->next = (f), (f) = (n))

Pushes a node to the top of a singly linked stack (Custom pointer name).

Parameters

f	Pointer to the top (head) element.
n	Pointer to the new node.
next	The literal variable name of the 'next' pointer.

Definition at line 538 of file base_macros.h.