1 /* $NetBSD: list.h,v 1.18 2018/08/27 13:56:58 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/null.h> 48 #include <sys/pslist.h> 49 #include <sys/queue.h> 50 51 #include <linux/kernel.h> 52 53 /* 54 * Doubly-linked lists. 55 */ 56 57 struct list_head { 58 struct list_head *prev; 59 struct list_head *next; 60 }; 61 62 #define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } 63 64 static inline void 65 INIT_LIST_HEAD(struct list_head *head) 66 { 67 head->prev = head; 68 head->next = head; 69 } 70 71 static inline struct list_head * 72 list_first(const struct list_head *head) 73 { 74 return head->next; 75 } 76 77 static inline struct list_head * 78 list_last(const struct list_head *head) 79 { 80 return head->prev; 81 } 82 83 static inline struct list_head * 84 list_next(const struct list_head *node) 85 { 86 return node->next; 87 } 88 89 static inline struct list_head * 90 list_prev(const struct list_head *node) 91 { 92 return node->prev; 93 } 94 95 static inline int 96 list_empty(const struct list_head *head) 97 { 98 return (head->next == head); 99 } 100 101 static inline int 102 list_is_singular(const struct list_head *head) 103 { 104 105 if (list_empty(head)) 106 return false; 107 if (head->next != head->prev) 108 return false; 109 return true; 110 } 111 112 static inline void 113 __list_add_between(struct list_head *prev, struct list_head *node, 114 struct list_head *next) 115 { 116 prev->next = node; 117 node->prev = prev; 118 node->next = next; 119 next->prev = node; 120 } 121 122 static inline void 123 list_add(struct list_head *node, struct list_head *head) 124 { 125 __list_add_between(head, node, head->next); 126 } 127 128 static inline void 129 list_add_tail(struct list_head *node, struct list_head *head) 130 { 131 __list_add_between(head->prev, node, head); 132 } 133 134 static inline void 135 list_del(struct list_head *entry) 136 { 137 entry->prev->next = entry->next; 138 entry->next->prev = entry->prev; 139 } 140 141 static inline void 142 __list_splice_between(struct list_head *prev, const struct list_head *list, 143 struct list_head *next) 144 { 145 struct list_head *first = list->next; 146 struct list_head *last = list->prev; 147 148 first->prev = prev; 149 prev->next = first; 150 151 last->next = next; 152 next->prev = last; 153 } 154 155 static inline void 156 list_splice(const struct list_head *list, struct list_head *head) 157 { 158 if (!list_empty(list)) 159 __list_splice_between(head, list, head->next); 160 } 161 162 static inline void 163 list_splice_init(struct list_head *list, struct list_head *head) 164 { 165 if (!list_empty(list)) { 166 __list_splice_between(head, list, head->next); 167 INIT_LIST_HEAD(list); 168 } 169 } 170 171 static inline void 172 list_splice_tail(const struct list_head *list, struct list_head *head) 173 { 174 if (!list_empty(list)) 175 __list_splice_between(head->prev, list, head); 176 } 177 178 static inline void 179 list_splice_tail_init(struct list_head *list, struct list_head *head) 180 { 181 if (!list_empty(list)) { 182 __list_splice_between(head->prev, list, head); 183 INIT_LIST_HEAD(list); 184 } 185 } 186 187 static inline void 188 list_move(struct list_head *node, struct list_head *head) 189 { 190 list_del(node); 191 list_add(node, head); 192 } 193 194 static inline void 195 list_move_tail(struct list_head *node, struct list_head *head) 196 { 197 list_del(node); 198 list_add_tail(node, head); 199 } 200 201 static inline void 202 list_replace(struct list_head *old, struct list_head *new) 203 { 204 new->prev = old->prev; 205 old->prev->next = new; 206 new->next = old->next; 207 old->next->prev = new; 208 } 209 210 static inline void 211 list_replace_init(struct list_head *old, struct list_head *new) 212 { 213 list_replace(old, new); 214 INIT_LIST_HEAD(old); 215 } 216 217 static inline void 218 list_del_init(struct list_head *node) 219 { 220 list_del(node); 221 INIT_LIST_HEAD(node); 222 } 223 224 #define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 225 #define list_first_entry(PTR, TYPE, FIELD) \ 226 list_entry(list_first((PTR)), TYPE, FIELD) 227 #define list_first_entry_or_null(PTR, TYPE, FIELD) \ 228 (list_empty((PTR)) ? NULL : list_entry(list_first((PTR)), TYPE, FIELD)) 229 #define list_last_entry(PTR, TYPE, FIELD) \ 230 list_entry(list_last((PTR)), TYPE, FIELD) 231 #define list_next_entry(ENTRY, FIELD) \ 232 list_entry(list_next(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 233 #define list_prev_entry(ENTRY, FIELD) \ 234 list_entry(list_prev(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 235 236 #define list_for_each(VAR, HEAD) \ 237 for ((VAR) = list_first((HEAD)); \ 238 (VAR) != (HEAD); \ 239 (VAR) = list_next((VAR))) 240 241 #define list_for_each_safe(VAR, NEXT, HEAD) \ 242 for ((VAR) = list_first((HEAD)); \ 243 ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \ 244 (VAR) = (NEXT)) 245 246 #define list_for_each_entry(VAR, HEAD, FIELD) \ 247 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 248 &(VAR)->FIELD != (HEAD); \ 249 (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \ 250 FIELD)) 251 252 #define list_for_each_entry_reverse(VAR, HEAD, FIELD) \ 253 for ((VAR) = list_entry(list_last((HEAD)), typeof(*(VAR)), FIELD); \ 254 &(VAR)->FIELD != (HEAD); \ 255 (VAR) = list_entry(list_prev(&(VAR)->FIELD), typeof(*(VAR)), \ 256 FIELD)) 257 258 #define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 259 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 260 (&(VAR)->FIELD != (HEAD)) && \ 261 ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \ 262 typeof(*(VAR)), FIELD), 1); \ 263 (VAR) = (NEXT)) 264 265 #define list_for_each_entry_continue(VAR, HEAD, FIELD) \ 266 for ((VAR) = list_next_entry((VAR), FIELD); \ 267 &(VAR)->FIELD != (HEAD); \ 268 (VAR) = list_next_entry((VAR), FIELD)) 269 270 #define list_for_each_entry_continue_reverse(VAR, HEAD, FIELD) \ 271 for ((VAR) = list_prev_entry((VAR), FIELD); \ 272 &(VAR)->FIELD != (HEAD); \ 273 (VAR) = list_prev_entry((VAR), FIELD)) 274 275 #define list_for_each_entry_safe_from(VAR, NEXT, HEAD, FIELD) \ 276 for (; \ 277 (&(VAR)->FIELD != (HEAD)) && \ 278 ((NEXT) = list_next_entry((VAR), FIELD)); \ 279 (VAR) = (NEXT)) 280 281 /* 282 * `H'ead-only/`H'ash-table doubly-linked lists. 283 */ 284 285 #define hlist_head pslist_head 286 #define hlist_node pslist_entry 287 288 #define HLIST_HEAD_INIT PSLIST_INITIALIZER 289 #define INIT_HLIST_HEAD PSLIST_INIT 290 #define hlist_empty(h) (pslist_writer_first(h) == NULL) 291 #define hlist_first pslist_writer_first 292 #define hlist_next pslist_writer_next 293 294 static inline void 295 hlist_add_head(struct hlist_node *node, struct hlist_head *head) 296 { 297 298 pslist_entry_init(node); 299 pslist_writer_insert_head(head, node); 300 } 301 302 static inline void 303 hlist_del(struct hlist_node *node) 304 { 305 306 pslist_writer_remove(node); 307 /* XXX abstraction violation */ 308 node->ple_prevp = _PSLIST_POISON; 309 } 310 311 static inline void 312 hlist_del_init(struct hlist_node *node) 313 { 314 315 /* XXX abstraction violation */ 316 if (node->ple_prevp != NULL) 317 pslist_writer_remove(node); 318 } 319 320 #define hlist_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 321 #define hlist_for_each(VAR, HEAD) \ 322 for ((VAR) = hlist_first(HEAD); (VAR) != NULL; (VAR) = hlist_next(VAR)) 323 #define hlist_for_each_safe(VAR, NEXT, HEAD) \ 324 for ((VAR) = hlist_first(HEAD); \ 325 (VAR) != NULL && ((NEXT) = hlist_next(HEAD), 1); \ 326 (VAR) = (NEXT)) 327 #define hlist_for_each_entry(VAR, HEAD, FIELD) \ 328 for ((VAR) = (hlist_first(HEAD) == NULL ? NULL : \ 329 hlist_entry(hlist_first(HEAD), typeof(*(VAR)), \ 330 FIELD)); \ 331 (VAR) != NULL; \ 332 (VAR) = (hlist_next(&(VAR)->FIELD) == NULL ? NULL : \ 333 hlist_entry(hlist_next(&(VAR)->FIELD), typeof(*(VAR)),\ 334 FIELD))) 335 336 #define hlist_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 337 for ((VAR) = (hlist_first(HEAD) == NULL ? NULL : \ 338 hlist_entry(hlist_first(HEAD), typeof(*(VAR)), \ 339 FIELD)); \ 340 ((VAR) != NULL && \ 341 ((NEXT) = hlist_next(&(VAR)->FIELD), 1)); \ 342 (VAR) = hlist_entry((NEXT), typeof(*(VAR)), FIELD)) 343 344 static inline void 345 hlist_add_behind_rcu(struct hlist_node *node, struct hlist_node *prev) 346 { 347 348 pslist_entry_init(node); 349 pslist_writer_insert_after(prev, node); 350 } 351 352 static inline void 353 hlist_add_head_rcu(struct hlist_node *node, struct hlist_head *head) 354 { 355 356 pslist_entry_init(node); 357 pslist_writer_insert_head(head, node); 358 } 359 360 #define hlist_del_init_rcu hlist_del_init /* no special needs */ 361 362 #define hlist_first_rcu pslist_reader_first 363 #define hlist_next_rcu pslist_reader_next 364 365 #define hlist_for_each_entry_rcu(VAR, HEAD, FIELD) \ 366 for ((VAR) = (hlist_first_rcu(HEAD) == NULL ? NULL : \ 367 hlist_entry(hlist_first_rcu(HEAD), typeof(*(VAR)), \ 368 FIELD)); \ 369 (VAR) != NULL; \ 370 (VAR) = (hlist_next_rcu(&(VAR)->FIELD) == NULL ? NULL : \ 371 hlist_entry(hlist_next_rcu(&(VAR)->FIELD), \ 372 typeof(*(VAR)), FIELD))) 373 374 #endif /* _LINUX_LIST_H_ */ 375