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