1/* @title: Lockless MPSC singly linked list */
2#pragma once
3#include <compiler.h>
4#include <container_of.h>
5#include <stdatomic.h>
6#include <stdbool.h>
7#include <stddef.h>
8
9struct mpsc_slist_node {
10 struct mpsc_slist_node *next;
11};
12
13struct mpsc_slist {
14 _Atomic(struct mpsc_slist_node *) head;
15};
16
17#define MPSC_SLIST_INIT {NULL}
18#define MPSC_SLIST(name) struct mpsc_slist name = MPSC_SLIST_INIT
19
20static inline void mpsc_slist_init(struct mpsc_slist *q) {
21 atomic_store_explicit(&q->head, NULL, memory_order_relaxed);
22}
23
24static inline int mpsc_slist_empty(const struct mpsc_slist *q) {
25 return atomic_load_explicit(&q->head, memory_order_acquire) == NULL;
26}
27
28/* Returns true if list was previously empty */
29static inline bool mpsc_slist_push(struct mpsc_slist *q,
30 struct mpsc_slist_node *n) {
31 struct mpsc_slist_node *old =
32 atomic_load_explicit(&q->head, memory_order_relaxed);
33 do {
34 n->next = old;
35 } while (!atomic_compare_exchange_weak_explicit(
36 &q->head, &old, n, memory_order_release, memory_order_relaxed));
37
38 return old == NULL;
39}
40
41/* Return the entire chain and mark as empty */
42static inline struct mpsc_slist_node *mpsc_slist_drain(struct mpsc_slist *q) {
43 return atomic_exchange_explicit(&q->head, NULL, memory_order_acquire);
44}
45
46/* Reverse a detached chain to get the FIFO list order */
47static inline struct mpsc_slist_node *
48mpsc_slist_reverse(struct mpsc_slist_node *chain) {
49 struct mpsc_slist_node *prev = NULL;
50 while (chain) {
51 struct mpsc_slist_node *next = chain->next;
52 chain->next = prev;
53 prev = chain;
54 chain = next;
55 }
56 return prev;
57}
58
59/* Single consumer pop */
60static inline struct mpsc_slist_node *mpsc_slist_pop_one(struct mpsc_slist *q) {
61 struct mpsc_slist_node *old =
62 atomic_load_explicit(&q->head, memory_order_acquire);
63 while (old) {
64 if (atomic_compare_exchange_weak_explicit(&q->head, &old, old->next,
65 memory_order_acquire,
66 memory_order_acquire))
67 return old;
68 }
69 return NULL;
70}
71
72#define mpsc_slist_entry(ptr, type, member) container_of(ptr, type, member)
73
74/* Detached chain */
75#define mpsc_slist_for_each(pos, chain) \
76 for (pos = (chain); pos; pos = pos->next)
77
78#define mpsc_slist_for_each_safe(pos, n, chain) \
79 for (pos = (chain), n = (pos) ? (pos)->next : NULL; pos; \
80 pos = n, n = (pos) ? (pos)->next : NULL)
81
82#define mpsc_slist_for_each_entry(pos, chain, member) \
83 for (pos = (chain) ? mpsc_slist_entry((chain), typeof(*pos), member) \
84 : NULL; \
85 pos; \
86 pos = (pos)->member.next ? mpsc_slist_entry((pos)->member.next, \
87 typeof(*pos), member) \
88 : NULL)
89