1/* @title: Lockless MPSC LIFO list */
2#pragma once
3#include <atomic.h>
4#include <compiler/core.h>
5#include <container_of.h>
6#include <stdbool.h>
7#include <stddef.h>
8
9struct mpsc_lifo_list_node {
10 struct mpsc_lifo_list_node *next;
11};
12
13struct mpsc_lifo_list {
14 atomic(struct mpsc_lifo_list_node *) head;
15};
16
17#define MPSC_LIFO_LIST_INIT {NULL}
18#define MPSC_LIFO_LIST(name) struct mpsc_lifo_list name = MPSC_LIFO_LIST_INIT
19
20static inline void mpsc_lifo_list_init(struct mpsc_lifo_list *q) {
21 atomic_store_rlx(&q->head, NULL);
22}
23
24static inline int mpsc_lifo_list_empty(const struct mpsc_lifo_list *q) {
25 return atomic_load_acq(&q->head) == NULL;
26}
27
28/* Returns true if list was previously empty */
29static inline bool mpsc_lifo_list_push(struct mpsc_lifo_list *q,
30 struct mpsc_lifo_list_node *n) {
31 struct mpsc_lifo_list_node *old = atomic_load_rlx(&q->head);
32 do {
33 n->next = old;
34 } while (!atomic_cas_weak(&q->head, &old, n, mo_release, mo_rlx));
35
36 return old == NULL;
37}
38
39/* Return the entire chain and mark as empty */
40static inline struct mpsc_lifo_list_node *
41mpsc_lifo_list_drain(struct mpsc_lifo_list *q) {
42 return atomic_xchg_acq(&q->head, NULL);
43}
44
45/* Reverse a detached chain to get the FIFO list order */
46static inline struct mpsc_lifo_list_node *
47mpsc_lifo_list_reverse(struct mpsc_lifo_list_node *chain) {
48 struct mpsc_lifo_list_node *prev = NULL;
49 while (chain) {
50 struct mpsc_lifo_list_node *next = chain->next;
51 chain->next = prev;
52 prev = chain;
53 chain = next;
54 }
55 return prev;
56}
57
58/* Single consumer pop */
59static inline struct mpsc_lifo_list_node *
60mpsc_lifo_list_pop(struct mpsc_lifo_list *q) {
61 struct mpsc_lifo_list_node *old = atomic_load_acq(&q->head);
62 while (old) {
63 if (atomic_cas_weak(&q->head, &old, old->next, mo_acquire, mo_acquire))
64 return old;
65 }
66 return NULL;
67}
68
69#define mpsc_lifo_list_entry(ptr, type, member) container_of(ptr, type, member)
70
71/* Detached chain */
72#define mpsc_lifo_list_for_each(pos, chain) \
73 for (pos = (chain); pos; pos = pos->next)
74
75#define mpsc_lifo_list_for_each_safe(pos, n, chain) \
76 for (pos = (chain), n = (pos) ? (pos)->next : NULL; pos; \
77 pos = n, n = (pos) ? (pos)->next : NULL)
78
79#define mpsc_lifo_list_for_each_entry(pos, chain, member) \
80 for (pos = (chain) ? mpsc_lifo_list_entry((chain), typeof(*pos), member) \
81 : NULL; \
82 pos; \
83 pos = (pos)->member.next ? mpsc_lifo_list_entry((pos)->member.next, \
84 typeof(*pos), member) \
85 : NULL)
86