Doubly linked list

Doubly linked list header. More...

Collaboration diagram for Doubly linked list:

Detailed Description

Doubly linked list header.

The sys/list.h header implements a intrusive doubly linked list where the linked list entry structure is stored within each entry instead of each entry having a pointer to each stucture.

Given a entry within a structure, the CONTAINER_OF() macro can be used to get a pointer to the structure from the list entry pointer.

Data Structures
struct	list_entry_t
	A entry in a doubly linked list. More...
struct	list_t
	A doubly linked list. More...

Macros
#define	LIST_FOR_EACH(elem, list, member)
	Iterates over a list.
#define	LIST_FOR_EACH_SAFE(elem, temp, list, member)
	Safely iterates over a list, allowing for element removal during iteration.
#define	LIST_FOR_EACH_REVERSE(elem, list, member)
	Iterates over a list in reverse.
#define	LIST_FOR_EACH_FROM(elem, start, list, member)
	Iterates over a list starting from a specific element.
#define	LIST_FOR_EACH_FROM_REVERSE(elem, start, list, member)
	Iterates over a list in reverse order starting from a specific element.
#define	LIST_FOR_EACH_TO(elem, end, list, member)
	Iterates over a list up to a specific element.
#define	LIST_FOR_EACH_TO_REVERSE(elem, end, list, member)
	Iterates over a list in reverse order up to a specific element.
#define	LIST_ENTRY_CREATE(name)
	Creates a list entry initializer.
#define	LIST_CREATE(name)   (list_t){.head = {.prev = &(name).head, .next = &(name).head, .list = &(name)}, .length = 0}
	Creates a list initializer.

Typedefs
typedef struct list	list_t

Functions
static void	list_entry_init (list_entry_t *entry)
	Initializes a list entry.
static void	list_init (list_t *list)
	Initializes a list.
static bool	list_contains_entry (list_t *list, list_entry_t *entry)
	Check if an entry belongs to a specific list.
static bool	list_is_empty (list_t *list)
	Checks if a list is empty.
static uint64_t	list_length (list_t *list)
	Gets the length of the list.
static void	list_add (list_t *list, list_entry_t *prev, list_entry_t *next, list_entry_t *entry)
	Adds a new element between two existing list entries.
static void	list_append (list_t *list, list_entry_t *prev, list_entry_t *entry)
	Appends an entry to the list.
static void	list_prepend (list_t *list, list_entry_t *head, list_entry_t *entry)
	Prepends an entry to the list.
static void	list_remove (list_t *list, list_entry_t *entry)
	Removes a list entry from its current list.
static void	list_push_back (list_t *list, list_entry_t *entry)
	Pushes an entry to the end of the list.
static void	list_push_front (list_t *list, list_entry_t *entry)
	Pushes an entry to the front of the list.
static list_entry_t *	list_pop_first (list_t *list)
	Pops the first entry from the list.
static list_entry_t *	list_pop_last (list_t *list)
	Pops the last entry from the list.
static list_entry_t *	list_first (list_t *list)
	Gets the first entry in the list without removing it.
static list_entry_t *	list_last (list_t *list)
	Gets the last entry in the list without removing it.

Macro Definition Documentation

LIST_FOR_EACH

#define LIST_FOR_EACH	(		elem,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF((list)->head.next, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))

Iterates over a list.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 63 of file list.h.

LIST_FOR_EACH_SAFE

#define LIST_FOR_EACH_SAFE	(		elem,
			temp,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF((list)->head.next, typeof(*elem), member), \
        (temp) = CONTAINER_OF((elem)->member.next, typeof(*elem), member); \
        &(elem)->member != &((list)->head); \
        (elem) = (temp), (temp) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))

Safely iterates over a list, allowing for element removal during iteration.

The LIST_FOR_EACH_SAFE() macro is similar to LIST_FOR_EACH() but uses a temporary variable to store the next element, making it safe to remove the current element during iteration.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
temp	A temporary loop variable, a pointer to the structure containing the next list entry.
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 79 of file list.h.

LIST_FOR_EACH_REVERSE

#define LIST_FOR_EACH_REVERSE	(		elem,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF((list)->head.prev, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.prev, typeof(*elem), member))

Iterates over a list in reverse.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 93 of file list.h.

LIST_FOR_EACH_FROM

#define LIST_FOR_EACH_FROM	(		elem,
			start,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF(start, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))

Iterates over a list starting from a specific element.

The LIST_FOR_EACH_FROM() macro iterates from a specific element, inclusive, until the end of the list.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
start	A pointer to the list_entry_t from which to start iteration.
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 108 of file list.h.

LIST_FOR_EACH_FROM_REVERSE

#define LIST_FOR_EACH_FROM_REVERSE	(		elem,
			start,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF(start, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.prev, typeof(*elem), member))

Iterates over a list in reverse order starting from a specific element.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
start	A pointer to the list_entry_t from which to start reverse iteration.
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 121 of file list.h.

LIST_FOR_EACH_TO

#define LIST_FOR_EACH_TO	(		elem,
			end,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF((list)->head.next, typeof(*elem), member); \
        &(elem)->member != &((list)->head) && &(elem)->member != (end); \
        (elem) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))

Iterates over a list up to a specific element.

The LIST_FOR_EACH_TO() macro iterates from the start of the list, inclusive, until a specified element, not inclusive.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
end	A pointer to the list_entry_t at which to stop iteration (exclusive).
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 137 of file list.h.

LIST_FOR_EACH_TO_REVERSE

#define LIST_FOR_EACH_TO_REVERSE	(		elem,
			end,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF((list)->head.prev, typeof(*elem), member); \
        &(elem)->member != &((list)->head) && &(elem)->member != (end); \
        (elem) = CONTAINER_OF((elem)->member.prev, typeof(*elem), member))

Iterates over a list in reverse order up to a specific element.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
end	A pointer to the list_entry_t at which to stop reverse iteration (exclusive).
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 151 of file list.h.

LIST_ENTRY_CREATE

#define LIST_ENTRY_CREATE

(

name

)

Value:

    (list_entry_t) \
    { \
        .prev = &(name), .next = &(name), .list = NULL \
    }

Creates a list entry initializer.

Parameters

name	The name of the entry variable to initialize.

Returns

A list_entry_t initializer for the specified entry variable.

Definition at line 162 of file list.h.

LIST_CREATE

#define LIST_CREATE

(

name

)

(list_t){.head = {.prev = &(name).head, .next = &(name).head, .list = &(name)}, .length = 0}

Creates a list initializer.

Parameters

name	The name of the list variable to initialize.

Returns

A list_t initializer for the specified list variable.

Definition at line 174 of file list.h.

Typedef Documentation

list_t

typedef struct list list_t

Definition at line 25 of file list.h.

Function Documentation

list_entry_init()

static void list_entry_init ( list_entry_t *  entry )

inlinestatic

Initializes a list entry.

Parameters

entry

A pointer to the list_entry_t to initialize.

Definition at line 182 of file list.h.

Here is the caller graph for this function:

list_init()

static void list_init ( list_t *  list )

inlinestatic

Initializes a list.

Parameters

list	A pointer to the list_t to initialize.

Definition at line 196 of file list.h.

Here is the call graph for this function:

Here is the caller graph for this function:

list_contains_entry()

static bool list_contains_entry ( list_t *  list, list_entry_t *  entry  )

inlinestatic

Check if an entry belongs to a specific list.

Parameters

list	A pointer to the list_t to search in.
entry	A pointer to the list_entry_t to search for.

Returns

true if the entry is in the list, false otherwise.

Definition at line 212 of file list.h.

list_is_empty()

static bool list_is_empty ( list_t *  list )

inlinestatic

Checks if a list is empty.

Parameters

list	A pointer to the list_t to check.

Returns

true if the list is empty, false otherwise.

Definition at line 227 of file list.h.

Here is the caller graph for this function:

list_length()

static uint64_t list_length ( list_t *  list )

inlinestatic

Gets the length of the list.

Parameters

list	A pointer to the list_t.

Returns

The number of elements in the list.

Definition at line 246 of file list.h.

Here is the caller graph for this function:

list_add()

static void list_add ( list_t *  list, list_entry_t *  prev, list_entry_t *  next, list_entry_t *  entry  )

inlinestatic

Adds a new element between two existing list entries.

Parameters

list	A pointer to the list_t that will contain the new element.
prev	A pointer to the list entry that will precede the new element.
next	A pointer to the list entry that will follow the new element.
elem	A pointer to the list_entry_t to add.

Definition at line 261 of file list.h.

Here is the caller graph for this function:

list_append()

static void list_append ( list_t *  list, list_entry_t *  prev, list_entry_t *  entry  )

inlinestatic

Appends an entry to the list.

Parameters

list	A pointer to the list_t to append to.
prev	A pointer to the list entry after which the new entry will be appended.
entry	A pointer to the list_entry_t to append.

Definition at line 290 of file list.h.

Here is the call graph for this function:

Here is the caller graph for this function:

list_prepend()

static void list_prepend ( list_t *  list, list_entry_t *  head, list_entry_t *  entry  )

inlinestatic

Prepends an entry to the list.

Parameters

list	A pointer to the list_t to prepend to.
head	A pointer to the list entry before which the new entry will be prepended.
entry	A pointer to the list_entry_t to prepend.

Definition at line 303 of file list.h.

Here is the call graph for this function:

Here is the caller graph for this function:

list_remove()

static void list_remove ( list_t *  list, list_entry_t *  entry  )

inlinestatic

Removes a list entry from its current list.

Parameters

list	A pointer to the list_t that contains the entry.
entry	A pointer to the list_entry_t to remove.

Definition at line 315 of file list.h.

Here is the call graph for this function:

Here is the caller graph for this function:

list_push_back()

static void list_push_back ( list_t *  list, list_entry_t *  entry  )

inlinestatic

Pushes an entry to the end of the list.

Parameters

list	A pointer to the list_t to push the entry to.
entry	A pointer to the list_entry_t to push.

Definition at line 343 of file list.h.

Here is the call graph for this function:

list_push_front()

static void list_push_front ( list_t *  list, list_entry_t *  entry  )

inlinestatic

Pushes an entry to the front of the list.

Parameters

list	A pointer to the list_t to push the entry to.
entry	A pointer to the list_entry_t to push.

Definition at line 359 of file list.h.

Here is the call graph for this function:

list_pop_first()

static list_entry_t * list_pop_first ( list_t *  list )

inlinestatic

Pops the first entry from the list.

Parameters

list	A pointer to the list_t to pop the entry from.

Returns

A pointer to the removed list_entry_t, or NULL if the list is empty.

Definition at line 375 of file list.h.

Here is the call graph for this function:

Here is the caller graph for this function:

list_pop_last()

static list_entry_t * list_pop_last ( list_t *  list )

inlinestatic

Pops the last entry from the list.

Parameters

list	A pointer to the list_t to pop the entry from.

Returns

A pointer to the removed list_entry_t, or NULL if the list is empty.

Definition at line 396 of file list.h.

Here is the call graph for this function:

Here is the caller graph for this function:

list_first()

static list_entry_t * list_first ( list_t *  list )

inlinestatic

Gets the first entry in the list without removing it.

Parameters

list	A pointer to the list_t.

Returns

A pointer to the first list_entry_t in the list, or NULL if the list is empty.

Definition at line 417 of file list.h.

Here is the call graph for this function:

Here is the caller graph for this function:

list_last()

static list_entry_t * list_last ( list_t *  list )

inlinestatic

Gets the last entry in the list without removing it.

Parameters

list	A pointer to the list_t.

Returns

A pointer to the last list_entry_t in the list, or NULL if the list is empty.

Definition at line 435 of file list.h.

Here is the call graph for this function:

Here is the caller graph for this function: