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