Linked list

include/structures/list.h View source View on GitHub

Structs

list_node

struct list_node (1 field)

Circular doubly linked list.

We use two different types here since a unified list_head proved problematic for readability and semantics. It’s largely symbolic and for type safety.

struct list_node is the link struct list_head is the head/anchor of the list.

list_head_* operations take the list_head, list_node_* operations a list_node, list_root_* operations technically take a list_node, but this is meant to be the list_head’s root member, and is used as convenience.

Thus, swapping arguments like list_add(&parent->node, &child->node); is not possible and fails to compile.

§ struct list_node *next

list_head

struct list_head (1 field)

§ struct list_node root

slist_node

struct slist_node (1 field)

§ struct slist_node *next

slist_head

struct slist_head (2 fields)

§ struct slist_node *first

§ struct slist_node *last

Type Aliases

list_cmp_fn

typedef int (*list_cmp_fn)(struct list_node * *, struct list_node * *)

Functions

list_add_check

void list_add_check(
    const struct list_node *new,
    const struct list_node *prev,
    const struct list_node *next
)

list_del_check

void list_del_check(const struct list_node *entry)

list_splice_check

void list_splice_check(
    const struct list_node *list,
    const struct list_node *prev,
    const struct list_node *next
)

list_add_check

void list_add_check(
    const struct list_node *new,
    const struct list_node *prev,
    const struct list_node *next
)

list_del_check

void list_del_check(const struct list_node *entry)

list_splice_check

void list_splice_check(
    const struct list_node *list,
    const struct list_node *prev,
    const struct list_node *next
)

list_node_init

void list_node_init(struct list_node *n)

list_head_init

void list_head_init(struct list_head *h)

list_node_is_linked

bool list_node_is_linked(const struct list_node *n)

list_node_next

struct list_node * list_node_next(const struct list_node *n)

list_node_prev

struct list_node * list_node_prev(const struct list_node *n)

list_head_sentinel

struct list_node * list_head_sentinel(struct list_head *h)

list_node_as_head

struct list_head * list_node_as_head(struct list_node *n)

Treat a node as if it’s the head. Should only be used in headless lists where one of the middle members is also the anchor

list_node_link_between

void list_node_link_between(
    struct list_node *new,
    struct list_node *prev,
    struct list_node *next
)

list_node_unlink_between

void list_node_unlink_between(
    struct list_node *prev,
    struct list_node *next
)

list_node_insert_after

void list_node_insert_after(
    struct list_node *pos,
    struct list_node *n
)

list_node_insert_before

void list_node_insert_before(
    struct list_node *pos,
    struct list_node *n
)

list_node_delete

void list_node_delete(struct list_node *n)

list_node_delete_init

void list_node_delete_init(struct list_node *n)

list_head_empty

bool list_head_empty(const struct list_head *h)

list_head_push_front

void list_head_push_front(struct list_head *h, struct list_node *n)

list_head_push_back

void list_head_push_back(struct list_head *h, struct list_node *n)

list_root_pop_front

struct list_node * list_root_pop_front(struct list_node *root)

root_*, For direct sentinel manipulation

list_root_pop_back

struct list_node * list_root_pop_back(struct list_node *root)

list_head_peek_front

struct list_node * list_head_peek_front(struct list_head *h)

list_head_peek_back

struct list_node * list_head_peek_back(struct list_head *h)

list_head_pop_front

struct list_node * list_head_pop_front(struct list_head *h)

list_head_pop_back

struct list_node * list_head_pop_back(struct list_head *h)

list_head_pop_front_init

struct list_node * list_head_pop_front_init(struct list_head *h)

list_head_pop_back_init

struct list_node * list_head_pop_back_init(struct list_head *h)

list_splice_between

void list_splice_between(
    const struct list_node *list,
    struct list_node *prev,
    struct list_node *next
)

list_head_splice_front_init

void list_head_splice_front_init(
    struct list_head *dst,
    struct list_head *src
)

Move everyone from src to the front of dst

list_head_splice_back_init

void list_head_splice_back_init(
    struct list_head *dst,
    struct list_head *src
)

Move everyone from src to the back of dst

list_root_sort

void list_root_sort(struct list_node *root, list_cmp_fn cmp)

list_head_sort

void list_head_sort(struct list_head *h, list_cmp_fn cmp)

slist_head_init

void slist_head_init(struct slist_head *h)

slist_empty

int slist_empty(const struct slist_head *h)

slist_push_head

void slist_push_head(struct slist_head *h, struct slist_node *n)

slist_push_tail

void slist_push_tail(struct slist_head *h, struct slist_node *n)

slist_pop_head

struct slist_node * slist_pop_head(struct slist_head *h)

slist_remove_node_after

void slist_remove_node_after(
    struct slist_head *h,
    struct slist_node *prev,
    struct slist_node *target
)

Macros

LIST_NODE_INIT

#define LIST_NODE_INIT(name)

Expansion

#define LIST_NODE_INIT(name) {&(name), &(name)}

LIST_HEAD_INIT

#define LIST_HEAD_INIT(name)

Expansion

#define LIST_HEAD_INIT(name) \
    { \
        .root = { &(name).root, &(name).root } \
    }

LIST_HEAD

#define LIST_HEAD(name)

Expansion

#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

list_root

#define list_root(h)

Expansion

#define list_root(h) (&(h)->root)

list_entry

#define list_entry(ptr, type, member)

Expansion

#define list_entry(ptr, type, member) container_of(ptr, type, member)

list_entry_safe

#define list_entry_safe(ptr, type, member)

Expansion

#define list_entry_safe(ptr, type, member) \
    ({ \
        __auto_type __list_ptr = (ptr); \
        __list_ptr ? list_entry(__list_ptr, type, member) : NULL; \
    })

list_for_each

#define list_for_each(pos, head)

Expansion

#define list_for_each(pos, head) \
    for (pos = list_root(head)->next; pos != list_root(head); pos = pos->next)

list_for_each_rev

#define list_for_each_rev(pos, head)

Expansion

#define list_for_each_rev(pos, head) \
    for (pos = list_root(head)->prev; pos != list_root(head); pos = pos->prev)

list_for_each_safe

#define list_for_each_safe(pos, n, head)

Expansion

#define list_for_each_safe(pos, n, head) \
    for (pos = list_root(head)->next, n = pos->next; pos != list_root(head); \
         pos = n, n = pos->next)

list_for_each_rev_safe

#define list_for_each_rev_safe(pos, n, head)

Expansion

#define list_for_each_rev_safe(pos, n, head) \
    for (pos = list_root(head)->prev, n = pos->prev; pos != list_root(head); \
         pos = n, n = pos->prev)

list_for_each_entry

#define list_for_each_entry(pos, head, member)

Expansion

#define list_for_each_entry(pos, head, member) \
    for (pos = list_entry(list_root(head)->next, typeof(*pos), member); \
         &pos->member != list_root(head); \
         pos = list_entry(pos->member.next, typeof(*pos), member))

list_for_each_entry_rev

#define list_for_each_entry_rev(pos, head, member)

Expansion

#define list_for_each_entry_rev(pos, head, member) \
    for (pos = list_entry(list_root(head)->prev, typeof(*pos), member); \
         &pos->member != list_root(head); \
         pos = list_entry(pos->member.prev, typeof(*pos), member))

list_first_entry

#define list_first_entry(ptr, type, member)

Expansion

#define list_first_entry(ptr, type, member) \
    list_entry(list_root(ptr)->next, type, member)

list_last_entry

#define list_last_entry(ptr, type, member)

Expansion

#define list_last_entry(ptr, type, member) \
    list_entry(list_root(ptr)->prev, type, member)

list_for_each_entry_safe

#define list_for_each_entry_safe(pos, n, head, member)

Expansion

#define list_for_each_entry_safe(pos, n, head, member) \
    for (pos = list_entry(list_root(head)->next, typeof(*pos), member), \
        n = list_entry(pos->member.next, typeof(*pos), member); \
         &pos->member != list_root(head); \
         pos = n, n = list_entry(n->member.next, typeof(*n), member))

list_for_each_entry_safe_rev

#define list_for_each_entry_safe_rev(pos, n, head, member)

Expansion

#define list_for_each_entry_safe_rev(pos, n, head, member) \
    for (pos = list_entry(list_root(head)->prev, typeof(*pos), member), \
        n = list_entry(pos->member.prev, typeof(*pos), member); \
         &pos->member != list_root(head); \
         pos = n, n = list_entry(n->member.prev, typeof(*n), member))

list_for_each_entry_safe_continue

#define list_for_each_entry_safe_continue(pos, n, head, member)

Expansion

#define list_for_each_entry_safe_continue(pos, n, head, member) \
    for (pos = list_entry(pos->member.next, typeof(*pos), member), \
        n = list_entry(pos->member.next, typeof(*pos), member); \
         &pos->member != list_root(head); \
         pos = n, n = list_entry(n->member.next, typeof(*n), member))

list_for_each_entry_safe_continue_rev

#define list_for_each_entry_safe_continue_rev(pos, n, head, member)

Expansion

#define list_for_each_entry_safe_continue_rev(pos, n, head, member) \
    for (pos = list_entry(pos->member.prev, typeof(*pos), member), \
        n = list_entry(pos->member.prev, typeof(*pos), member); \
         &pos->member != list_root(head); \
         pos = n, n = list_entry(n->member.prev, typeof(*n), member))