1/* Public domain. */ 2 3#ifndef _LINUXKPI_LINUX_LLIST_H 4#define _LINUXKPI_LINUX_LLIST_H 5 6#include <sys/types.h> 7#include <machine/atomic.h> 8 9struct llist_node { 10 struct llist_node *next; 11}; 12 13struct llist_head { 14 struct llist_node *first; 15}; 16 17#define LLIST_HEAD_INIT(name) { NULL } 18#define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name) 19 20#define llist_entry(ptr, type, member) \ 21 ((ptr) ? container_of(ptr, type, member) : NULL) 22 23static inline struct llist_node * 24llist_del_all(struct llist_head *head) 25{ 26 return ((void *)atomic_readandclear_ptr((uintptr_t *)&head->first)); 27} 28 29static inline struct llist_node * 30llist_del_first(struct llist_head *head) 31{ 32 struct llist_node *first, *next; 33 34 do { 35 first = head->first; 36 if (first == NULL) 37 return NULL; 38 next = first->next; 39 } while (atomic_cmpset_ptr((uintptr_t *)&head->first, 40 (uintptr_t)first, (uintptr_t)next) == 0); 41 42 return (first); 43} 44 45static inline bool 46llist_add(struct llist_node *new, struct llist_head *head) 47{ 48 struct llist_node *first; 49 50 do { 51 new->next = first = head->first; 52 } while (atomic_cmpset_ptr((uintptr_t *)&head->first, 53 (uintptr_t)first, (uintptr_t)new) == 0); 54 55 return (first == NULL); 56} 57 58static inline bool 59llist_add_batch(struct llist_node *new_first, struct llist_node *new_last, 60 struct llist_head *head) 61{ 62 struct llist_node *first; 63 64 do { 65 new_last->next = first = head->first; 66 } while (atomic_cmpset_ptr((uintptr_t *)&head->first, 67 (uintptr_t)first, (uintptr_t)new_first) == 0); 68 69 return (first == NULL); 70} 71 72static inline void 73init_llist_head(struct llist_head *head) 74{ 75 head->first = NULL; 76} 77 78static inline bool 79llist_empty(struct llist_head *head) 80{ 81 return (head->first == NULL); 82} 83 84#define llist_for_each_safe(pos, n, node) \ 85 for ((pos) = (node); \ 86 (pos) != NULL && \ 87 ((n) = (pos)->next, pos); \ 88 (pos) = (n)) 89 90#define llist_for_each_entry_safe(pos, n, node, member) \ 91 for (pos = llist_entry((node), __typeof(*pos), member); \ 92 pos != NULL && \ 93 (n = llist_entry(pos->member.next, __typeof(*pos), member), pos); \ 94 pos = n) 95 96#define llist_for_each_entry(pos, node, member) \ 97 for ((pos) = llist_entry((node), __typeof(*(pos)), member); \ 98 (pos) != NULL; \ 99 (pos) = llist_entry((pos)->member.next, __typeof(*(pos)), member)) 100 101#endif 102