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