sys/queue.h

On BSD, Unix, and Linux systems, the sys/queue.h header file provides implementations and utility functions for singly/doubly linked lists and tail queues. In practice, the queues are implemented as linked lists.

• SLIST: singly-linked list
• LIST: doubly-linked list
• STAILQ: singly-linked tail queue
• TAILQ: doubly-linked tail queue

Use

To define a list, we need to define each list node:

typedef struct list_entry {
	size_t entry;
	TAILQ_ENTRY(list_entry) ptr;
} node_t;

Then, we need to define the head:

TAILQ_HEAD(list_head, list_entry);
static struct list_head list_head;

Whenever we access the struct fields, we dereference to get entry or ptr. Whenever a macro requires we pass the list head, we’ll pass in list_head. Simple enough!

API

The list and queue API is mainly provided via function macros.

Some list manipulation macros:

• TAILQ_INIT(TAILQ_HEAD *head): initialises an empty FIFO.
• TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NEXT): inserts a new list entry to the head of the list, where elm is of type struct list_entry. The NEXT refers to the pointer to the next list entry, ptr.
• TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NEXT): inserts a list entry to the tail of the list.
• TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NEXT): removes the given list entry pointer from the list.

List access macros:

• TAILQ_EMPTY(TAILQ_HEAD *head): checks if the list is empty.
• TAILQ_FIRST(TAILQ_HEAD *head): returns the first entry in the list.

Finally, there’s a set of list iteration macros. They’re a little more involved than the other macros, but essentially operate like a for loop:

node_t *curr; // define pointer for macro to use
TAILQ_FOREACH(curr, &list_head, ptr) {
	// operations involving curr
}

Other iteration macros:

• TAILQ_FOREACH_SAFE
• TAILQ_FOREACH_REVERSE
• TAILQ_FOREACH_REVERSE_SAFE