17f4dd379Sjsg /* Public domain. */
27f4dd379Sjsg
37f4dd379Sjsg #ifndef _LINUX_LLIST_H
47f4dd379Sjsg #define _LINUX_LLIST_H
57f4dd379Sjsg
67f4dd379Sjsg #include <sys/atomic.h>
77f4dd379Sjsg
87f4dd379Sjsg struct llist_node {
97f4dd379Sjsg struct llist_node *next;
107f4dd379Sjsg };
117f4dd379Sjsg
127f4dd379Sjsg struct llist_head {
137f4dd379Sjsg struct llist_node *first;
147f4dd379Sjsg };
157f4dd379Sjsg
16*75a9d582Sjsg #define llist_entry(ptr, type, member) container_of(ptr, type, member)
177f4dd379Sjsg
187f4dd379Sjsg static inline struct llist_node *
llist_del_all(struct llist_head * head)197f4dd379Sjsg llist_del_all(struct llist_head *head)
207f4dd379Sjsg {
217f4dd379Sjsg return atomic_swap_ptr(&head->first, NULL);
227f4dd379Sjsg }
237f4dd379Sjsg
247f4dd379Sjsg static inline struct llist_node *
llist_del_first(struct llist_head * head)257f4dd379Sjsg llist_del_first(struct llist_head *head)
267f4dd379Sjsg {
277f4dd379Sjsg struct llist_node *first, *next;
287f4dd379Sjsg
297f4dd379Sjsg do {
307f4dd379Sjsg first = head->first;
317f4dd379Sjsg if (first == NULL)
327f4dd379Sjsg return NULL;
337f4dd379Sjsg next = first->next;
347f4dd379Sjsg } while (atomic_cas_ptr(&head->first, first, next) != first);
357f4dd379Sjsg
367f4dd379Sjsg return first;
377f4dd379Sjsg }
387f4dd379Sjsg
397f4dd379Sjsg static inline bool
llist_add(struct llist_node * new,struct llist_head * head)407f4dd379Sjsg llist_add(struct llist_node *new, struct llist_head *head)
417f4dd379Sjsg {
427f4dd379Sjsg struct llist_node *first;
437f4dd379Sjsg
447f4dd379Sjsg do {
457f4dd379Sjsg new->next = first = head->first;
467f4dd379Sjsg } while (atomic_cas_ptr(&head->first, first, new) != first);
477f4dd379Sjsg
487f4dd379Sjsg return (first == NULL);
497f4dd379Sjsg }
507f4dd379Sjsg
51c349dbc7Sjsg static inline bool
llist_add_batch(struct llist_node * new_first,struct llist_node * new_last,struct llist_head * head)52c349dbc7Sjsg llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
53c349dbc7Sjsg struct llist_head *head)
54c349dbc7Sjsg {
55c349dbc7Sjsg struct llist_node *first;
56c349dbc7Sjsg
57c349dbc7Sjsg do {
58c349dbc7Sjsg new_last->next = first = head->first;
59c349dbc7Sjsg } while (atomic_cas_ptr(&head->first, first, new_first) != first);
60c349dbc7Sjsg
61c349dbc7Sjsg return (first == NULL);
62c349dbc7Sjsg }
63c349dbc7Sjsg
647f4dd379Sjsg static inline void
init_llist_head(struct llist_head * head)657f4dd379Sjsg init_llist_head(struct llist_head *head)
667f4dd379Sjsg {
677f4dd379Sjsg head->first = NULL;
687f4dd379Sjsg }
697f4dd379Sjsg
707f4dd379Sjsg static inline bool
llist_empty(struct llist_head * head)717f4dd379Sjsg llist_empty(struct llist_head *head)
727f4dd379Sjsg {
737f4dd379Sjsg return (head->first == NULL);
747f4dd379Sjsg }
757f4dd379Sjsg
76c349dbc7Sjsg #define llist_for_each_safe(pos, n, node) \
77c349dbc7Sjsg for ((pos) = (node); \
78c349dbc7Sjsg (pos) != NULL && \
79c349dbc7Sjsg ((n) = (pos)->next, pos); \
80c349dbc7Sjsg (pos) = (n))
81c349dbc7Sjsg
827f4dd379Sjsg #define llist_for_each_entry_safe(pos, n, node, member) \
837f4dd379Sjsg for (pos = llist_entry((node), __typeof(*pos), member); \
84*75a9d582Sjsg ((char *)(pos) + offsetof(typeof(*(pos)), member)) != NULL && \
857f4dd379Sjsg (n = llist_entry(pos->member.next, __typeof(*pos), member), pos); \
867f4dd379Sjsg pos = n)
877f4dd379Sjsg
88c349dbc7Sjsg #define llist_for_each_entry(pos, node, member) \
89c349dbc7Sjsg for ((pos) = llist_entry((node), __typeof(*(pos)), member); \
90*75a9d582Sjsg ((char *)(pos) + offsetof(typeof(*(pos)), member)) != NULL; \
91c349dbc7Sjsg (pos) = llist_entry((pos)->member.next, __typeof(*(pos)), member))
92c349dbc7Sjsg
937f4dd379Sjsg #endif
94