1 /* $NetBSD: list.h,v 1.5 2014/08/20 15:26:52 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2013 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Taylor R. Campbell. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * Notes on porting: 34 * 35 * - LIST_HEAD(x) means a declaration `struct list_head x = 36 * LIST_HEAD_INIT(x)' in Linux, but something else in NetBSD. 37 * Replace by the expansion. 38 * 39 * - The `_rcu' routines here are not actually pserialize(9)-safe. 40 * They need dependent read memory barriers added. Please fix this 41 * if you need to use them with pserialize(9). 42 */ 43 44 #ifndef _LINUX_LIST_H_ 45 #define _LINUX_LIST_H_ 46 47 #include <sys/queue.h> 48 49 #define container_of(ptr, type, member) \ 50 ({ \ 51 __typeof(((type *)0)->member) *_p = (ptr); \ 52 (type *)((char *)_p - offsetof(type, member)); \ 53 }) 54 55 /* 56 * Doubly-linked lists. 57 */ 58 59 struct list_head { 60 struct list_head *prev; 61 struct list_head *next; 62 }; 63 64 #define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } 65 66 static inline void 67 INIT_LIST_HEAD(struct list_head *head) 68 { 69 head->prev = head; 70 head->next = head; 71 } 72 73 static inline struct list_head * 74 list_first(const struct list_head *head) 75 { 76 return head->next; 77 } 78 79 static inline struct list_head * 80 list_last(const struct list_head *head) 81 { 82 return head->prev; 83 } 84 85 static inline struct list_head * 86 list_next(const struct list_head *node) 87 { 88 return node->next; 89 } 90 91 static inline struct list_head * 92 list_prev(const struct list_head *node) 93 { 94 return node->prev; 95 } 96 97 static inline int 98 list_empty(const struct list_head *head) 99 { 100 return (head->next == head); 101 } 102 103 static inline int 104 list_is_singular(const struct list_head *head) 105 { 106 107 if (list_empty(head)) 108 return false; 109 if (head->next != head->prev) 110 return false; 111 return true; 112 } 113 114 static inline void 115 __list_add_between(struct list_head *prev, struct list_head *node, 116 struct list_head *next) 117 { 118 prev->next = node; 119 node->prev = prev; 120 node->next = next; 121 next->prev = node; 122 } 123 124 static inline void 125 list_add(struct list_head *node, struct list_head *head) 126 { 127 __list_add_between(head, node, head->next); 128 } 129 130 static inline void 131 list_add_tail(struct list_head *node, struct list_head *head) 132 { 133 __list_add_between(head->prev, node, head); 134 } 135 136 static inline void 137 list_del(struct list_head *entry) 138 { 139 entry->prev->next = entry->next; 140 entry->next->prev = entry->prev; 141 } 142 143 static inline void 144 __list_splice_between(struct list_head *prev, const struct list_head *list, 145 struct list_head *next) 146 { 147 struct list_head *first = list->next; 148 struct list_head *last = list->prev; 149 150 first->prev = prev; 151 prev->next = first; 152 153 last->next = next; 154 next->prev = last; 155 } 156 157 static inline void 158 list_splice(const struct list_head *list, struct list_head *head) 159 { 160 if (!list_empty(list)) 161 __list_splice_between(head, list, head->next); 162 } 163 164 static inline void 165 list_splice_tail(const struct list_head *list, struct list_head *head) 166 { 167 if (!list_empty(list)) 168 __list_splice_between(head->prev, list, head); 169 } 170 171 static inline void 172 list_move(struct list_head *node, struct list_head *head) 173 { 174 list_del(node); 175 list_add(node, head); 176 } 177 178 static inline void 179 list_move_tail(struct list_head *node, struct list_head *head) 180 { 181 list_del(node); 182 list_add_tail(node, head); 183 } 184 185 static inline void 186 list_replace(struct list_head *old, struct list_head *new) 187 { 188 new->prev = old->prev; 189 old->prev->next = new; 190 new->next = old->next; 191 old->next->prev = new; 192 } 193 194 static inline void 195 list_del_init(struct list_head *node) 196 { 197 list_del(node); 198 INIT_LIST_HEAD(node); 199 } 200 201 #define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 202 #define list_first_entry(PTR, TYPE, FIELD) \ 203 list_entry(list_first((PTR)), TYPE, FIELD) 204 #define list_last_entry(PTR, TYPE, FIELD) \ 205 list_entry(list_last((PTR)), TYPE, FIELD) 206 #define list_next_entry(ENTRY, FIELD) \ 207 list_entry(list_next(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 208 #define list_prev_entry(ENTRY, FIELD) \ 209 list_entry(list_prev(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 210 211 #define list_for_each(VAR, HEAD) \ 212 for ((VAR) = list_first((HEAD)); \ 213 (VAR) != (HEAD); \ 214 (VAR) = list_next((VAR))) 215 216 #define list_for_each_safe(VAR, NEXT, HEAD) \ 217 for ((VAR) = list_first((HEAD)); \ 218 ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \ 219 (VAR) = (NEXT)) 220 221 #define list_for_each_entry(VAR, HEAD, FIELD) \ 222 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 223 &(VAR)->FIELD != (HEAD); \ 224 (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \ 225 FIELD)) 226 227 #define list_for_each_entry_reverse(VAR, HEAD, FIELD) \ 228 for ((VAR) = list_entry(list_last((HEAD)), typeof(*(VAR)), FIELD); \ 229 &(VAR)->FIELD != (HEAD); \ 230 (VAR) = list_entry(list_prev(&(VAR)->FIELD), typeof(*(VAR)), \ 231 FIELD)) 232 233 #define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 234 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 235 (&(VAR)->FIELD != (HEAD)) && \ 236 ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \ 237 typeof(*(VAR)), FIELD), 1); \ 238 (VAR) = (NEXT)) 239 240 #define list_for_each_entry_continue(VAR, HEAD, FIELD) \ 241 for ((VAR) = list_next_entry((VAR), FIELD); \ 242 &(VAR)->FIELD != (HEAD); \ 243 (VAR) = list_next_entry((VAR), FIELD)) 244 245 #define list_for_each_entry_continue_reverse(VAR, HEAD, FIELD) \ 246 for ((VAR) = list_prev_entry((VAR), FIELD); \ 247 &(VAR)->FIELD != (HEAD); \ 248 (VAR) = list_prev_entry((VAR), FIELD)) 249 250 #define list_for_each_entry_safe_from(VAR, NEXT, HEAD, FIELD) \ 251 for (; \ 252 (&(VAR)->FIELD != (HEAD)) && \ 253 ((NEXT) = list_next_entry((VAR), FIELD)); \ 254 (VAR) = (NEXT)) 255 256 #endif /* _LINUX_LIST_H_ */ 257