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 9 struct llist_node { 10 struct llist_node *next; 11 }; 12 13 struct 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 23 static inline struct llist_node * 24 llist_del_all(struct llist_head *head) 25 { 26 return ((void *)atomic_readandclear_ptr((uintptr_t *)&head->first)); 27 } 28 29 static inline struct llist_node * 30 llist_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 45 static inline bool 46 llist_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 58 static inline bool 59 llist_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 72 static inline void 73 init_llist_head(struct llist_head *head) 74 { 75 head->first = NULL; 76 } 77 78 static inline bool 79 llist_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