1 /* $NetBSD: list.h,v 1.32 2021/12/19 11:39:24 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 40 #ifndef _LINUX_LIST_H_ 41 #define _LINUX_LIST_H_ 42 43 #include <sys/null.h> 44 #include <sys/pslist.h> 45 #include <sys/queue.h> 46 47 #include <linux/kernel.h> 48 #include <linux/types.h> 49 50 #define POISON_INUSE 0x5a /* XXX */ 51 52 /* 53 * Doubly-linked lists. Type defined in <linux/types.h>. 54 */ 55 56 #define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } 57 58 #define LINUX_LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) 59 60 static inline void 61 INIT_LIST_HEAD(struct list_head *head) 62 { 63 head->prev = head; 64 head->next = head; 65 } 66 67 static inline struct list_head * 68 list_first(const struct list_head *head) 69 { 70 return head->next; 71 } 72 73 static inline struct list_head * 74 list_last(const struct list_head *head) 75 { 76 return head->prev; 77 } 78 79 static inline struct list_head * 80 list_next(const struct list_head *node) 81 { 82 return node->next; 83 } 84 85 static inline struct list_head * 86 list_prev(const struct list_head *node) 87 { 88 return node->prev; 89 } 90 91 static inline int 92 list_empty(const struct list_head *head) 93 { 94 return (head->next == head); 95 } 96 97 static inline int 98 list_is_singular(const struct list_head *head) 99 { 100 101 if (list_empty(head)) 102 return false; 103 if (head->next != head->prev) 104 return false; 105 return true; 106 } 107 108 static inline bool 109 list_is_first(const struct list_head *entry, const struct list_head *head) 110 { 111 return head == entry->prev; 112 } 113 114 static inline bool 115 list_is_last(const struct list_head *entry, const struct list_head *head) 116 { 117 return head == entry->next; 118 } 119 120 static inline void 121 __list_add_between(struct list_head *prev, struct list_head *node, 122 struct list_head *next) 123 { 124 prev->next = node; 125 node->prev = prev; 126 node->next = next; 127 next->prev = node; 128 } 129 130 static inline void 131 list_add(struct list_head *node, struct list_head *head) 132 { 133 __list_add_between(head, node, head->next); 134 } 135 136 static inline void 137 list_add_rcu(struct list_head *node, struct list_head *head) 138 { 139 struct list_head *next = head->next; 140 141 /* Initialize the new node first. */ 142 node->next = next; 143 node->prev = head; 144 145 /* Now publish it. */ 146 atomic_store_release(&head->next, node); 147 148 /* Fix up back pointers, not protected by RCU. */ 149 next->prev = node; 150 } 151 152 static inline void 153 list_add_tail(struct list_head *node, struct list_head *head) 154 { 155 __list_add_between(head->prev, node, head); 156 } 157 158 static inline void 159 __list_del_entry(struct list_head *entry) 160 { 161 entry->prev->next = entry->next; 162 entry->next->prev = entry->prev; 163 } 164 165 static inline void 166 list_del(struct list_head *entry) 167 { 168 __list_del_entry(entry); 169 entry->next = (void *)(uintptr_t)1; 170 entry->prev = (void *)(uintptr_t)2; 171 } 172 173 static inline void 174 __list_splice_between(struct list_head *prev, const struct list_head *list, 175 struct list_head *next) 176 { 177 struct list_head *first = list->next; 178 struct list_head *last = list->prev; 179 180 first->prev = prev; 181 prev->next = first; 182 183 last->next = next; 184 next->prev = last; 185 } 186 187 static inline void 188 list_splice(const struct list_head *list, struct list_head *head) 189 { 190 if (!list_empty(list)) 191 __list_splice_between(head, list, head->next); 192 } 193 194 static inline void 195 list_splice_init(struct list_head *list, struct list_head *head) 196 { 197 if (!list_empty(list)) { 198 __list_splice_between(head, list, head->next); 199 INIT_LIST_HEAD(list); 200 } 201 } 202 203 static inline void 204 list_splice_tail(const struct list_head *list, struct list_head *head) 205 { 206 if (!list_empty(list)) 207 __list_splice_between(head->prev, list, head); 208 } 209 210 static inline void 211 list_splice_tail_init(struct list_head *list, struct list_head *head) 212 { 213 if (!list_empty(list)) { 214 __list_splice_between(head->prev, list, head); 215 INIT_LIST_HEAD(list); 216 } 217 } 218 219 static inline void 220 list_move(struct list_head *node, struct list_head *head) 221 { 222 list_del(node); 223 list_add(node, head); 224 } 225 226 static inline void 227 list_move_tail(struct list_head *node, struct list_head *head) 228 { 229 list_del(node); 230 list_add_tail(node, head); 231 } 232 233 static inline void 234 list_bulk_move_tail(struct list_head *head, struct list_head *first, 235 struct list_head *last) 236 { 237 238 first->prev->next = last->next; 239 last->next->prev = first->prev; 240 241 head->prev->next = first; 242 first->prev = head->prev; 243 244 last->next = head; 245 head->prev = last; 246 } 247 248 static inline void 249 list_replace(struct list_head *old, struct list_head *new) 250 { 251 new->prev = old->prev; 252 old->prev->next = new; 253 new->next = old->next; 254 old->next->prev = new; 255 } 256 257 static inline void 258 list_replace_init(struct list_head *old, struct list_head *new) 259 { 260 list_replace(old, new); 261 INIT_LIST_HEAD(old); 262 } 263 264 static inline void 265 list_del_init(struct list_head *node) 266 { 267 list_del(node); 268 INIT_LIST_HEAD(node); 269 } 270 271 #define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 272 #define list_first_entry(PTR, TYPE, FIELD) \ 273 list_entry(list_first((PTR)), TYPE, FIELD) 274 #define list_first_entry_or_null(PTR, TYPE, FIELD) \ 275 (list_empty((PTR)) ? NULL : list_entry(list_first((PTR)), TYPE, FIELD)) 276 #define list_last_entry(PTR, TYPE, FIELD) \ 277 list_entry(list_last((PTR)), TYPE, FIELD) 278 #define list_next_entry(ENTRY, FIELD) \ 279 list_entry(list_next(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 280 #define list_prev_entry(ENTRY, FIELD) \ 281 list_entry(list_prev(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 282 283 #define list_for_each(VAR, HEAD) \ 284 for ((VAR) = list_first((HEAD)); \ 285 (VAR) != (HEAD); \ 286 (VAR) = list_next((VAR))) 287 288 #define list_for_each_prev(VAR, HEAD) \ 289 for ((VAR) = list_last((HEAD)); \ 290 (VAR) != (HEAD); \ 291 (VAR) = list_prev((VAR))) 292 293 #define list_for_each_safe(VAR, NEXT, HEAD) \ 294 for ((VAR) = list_first((HEAD)); \ 295 ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \ 296 (VAR) = (NEXT)) 297 298 #define list_safe_reset_next(VAR, NEXT, FIELD) \ 299 (NEXT) = list_next_entry(VAR, FIELD) 300 301 #define list_for_each_entry(VAR, HEAD, FIELD) \ 302 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 303 &(VAR)->FIELD != (HEAD); \ 304 (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \ 305 FIELD)) 306 307 #define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 308 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 309 (&(VAR)->FIELD != (HEAD)) && \ 310 ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \ 311 typeof(*(VAR)), FIELD), 1); \ 312 (VAR) = (NEXT)) 313 314 #define list_for_each_entry_safe_reverse(VAR, NEXT, HEAD, FIELD) \ 315 for ((VAR) = list_entry(list_last((HEAD)), typeof(*(VAR)), FIELD); \ 316 (&(VAR)->FIELD != (HEAD)) && \ 317 ((NEXT) = list_entry(list_prev(&(VAR)->FIELD), \ 318 typeof(*(VAR)), FIELD), 1); \ 319 (VAR) = (NEXT)) 320 321 #define list_for_each_entry_reverse(VAR, HEAD, FIELD) \ 322 for ((VAR) = list_entry(list_last((HEAD)), typeof(*(VAR)), FIELD); \ 323 &(VAR)->FIELD != (HEAD); \ 324 (VAR) = list_entry(list_prev(&(VAR)->FIELD), typeof(*(VAR)), \ 325 FIELD)) 326 327 #define list_for_each_entry_continue(VAR, HEAD, FIELD) \ 328 for ((VAR) = list_next_entry((VAR), FIELD); \ 329 &(VAR)->FIELD != (HEAD); \ 330 (VAR) = list_next_entry((VAR), FIELD)) 331 332 #define list_for_each_entry_continue_reverse(VAR, HEAD, FIELD) \ 333 for ((VAR) = list_prev_entry((VAR), FIELD); \ 334 &(VAR)->FIELD != (HEAD); \ 335 (VAR) = list_prev_entry((VAR), FIELD)) 336 337 #define list_for_each_entry_from(VAR, HEAD, FIELD) \ 338 for (; \ 339 (&(VAR)->FIELD != (HEAD)); \ 340 (VAR) = list_next_entry((VAR), FIELD)) 341 342 #define list_for_each_entry_from_reverse(VAR, HEAD, FIELD) \ 343 for (; \ 344 (&(VAR)->FIELD != (HEAD)); \ 345 (VAR) = list_prev_entry((VAR), FIELD)) 346 347 #define list_for_each_entry_safe_from(VAR, NEXT, HEAD, FIELD) \ 348 for (; \ 349 (&(VAR)->FIELD != (HEAD)) && \ 350 ((NEXT) = list_next_entry((VAR), FIELD)); \ 351 (VAR) = (NEXT)) 352 353 /* 354 * `H'ead-only/`H'ash-table doubly-linked lists. 355 */ 356 357 #define hlist_head pslist_head 358 #define hlist_node pslist_entry 359 360 #define HLIST_HEAD_INIT PSLIST_INITIALIZER 361 #define INIT_HLIST_HEAD PSLIST_INIT 362 #define hlist_empty(h) (pslist_writer_first(h) == NULL) 363 #define hlist_first pslist_writer_first 364 #define hlist_next pslist_writer_next 365 366 static inline void 367 hlist_add_head(struct hlist_node *node, struct hlist_head *head) 368 { 369 370 pslist_entry_init(node); 371 pslist_writer_insert_head(head, node); 372 } 373 374 static inline void 375 hlist_del(struct hlist_node *node) 376 { 377 378 pslist_writer_remove(node); 379 /* XXX abstraction violation */ 380 node->ple_prevp = _PSLIST_POISON; 381 } 382 383 static inline void 384 hlist_del_init(struct hlist_node *node) 385 { 386 387 /* XXX abstraction violation */ 388 if (node->ple_prevp != NULL) 389 pslist_writer_remove(node); 390 } 391 392 #define hlist_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 393 #define hlist_for_each(VAR, HEAD) \ 394 for ((VAR) = hlist_first(HEAD); (VAR) != NULL; (VAR) = hlist_next(VAR)) 395 #define hlist_for_each_safe(VAR, NEXT, HEAD) \ 396 for ((VAR) = hlist_first(HEAD); \ 397 (VAR) != NULL && ((NEXT) = hlist_next(HEAD), 1); \ 398 (VAR) = (NEXT)) 399 #define hlist_for_each_entry(VAR, HEAD, FIELD) \ 400 for ((VAR) = (hlist_first(HEAD) == NULL ? NULL : \ 401 hlist_entry(hlist_first(HEAD), typeof(*(VAR)), \ 402 FIELD)); \ 403 (VAR) != NULL; \ 404 (VAR) = (hlist_next(&(VAR)->FIELD) == NULL ? NULL : \ 405 hlist_entry(hlist_next(&(VAR)->FIELD), typeof(*(VAR)),\ 406 FIELD))) 407 408 #define hlist_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 409 for ((VAR) = (hlist_first(HEAD) == NULL ? NULL : \ 410 hlist_entry(hlist_first(HEAD), typeof(*(VAR)), \ 411 FIELD)); \ 412 ((VAR) != NULL && \ 413 ((NEXT) = hlist_next(&(VAR)->FIELD), 1)); \ 414 (VAR) = hlist_entry((NEXT), typeof(*(VAR)), FIELD)) 415 416 static inline void 417 hlist_add_behind_rcu(struct hlist_node *node, struct hlist_node *prev) 418 { 419 420 pslist_entry_init(node); 421 pslist_writer_insert_after(prev, node); 422 } 423 424 static inline void 425 hlist_add_head_rcu(struct hlist_node *node, struct hlist_head *head) 426 { 427 428 pslist_entry_init(node); 429 pslist_writer_insert_head(head, node); 430 } 431 432 #define hlist_del_init_rcu hlist_del_init /* no special needs */ 433 434 #define hlist_first_rcu pslist_reader_first 435 #define hlist_next_rcu pslist_reader_next 436 437 #define hlist_for_each_entry_rcu(VAR, HEAD, FIELD) \ 438 for ((VAR) = (hlist_first_rcu(HEAD) == NULL ? NULL : \ 439 hlist_entry(hlist_first_rcu(HEAD), typeof(*(VAR)), \ 440 FIELD)); \ 441 (VAR) != NULL; \ 442 (VAR) = (hlist_next_rcu(&(VAR)->FIELD) == NULL ? NULL : \ 443 hlist_entry(hlist_next_rcu(&(VAR)->FIELD), \ 444 typeof(*(VAR)), FIELD))) 445 446 #endif /* _LINUX_LIST_H_ */ 447