list.h revision 1.6
1/* $NetBSD: list.h,v 1.6 2018/08/27 06:23:19 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/queue.h> 49 50#include <linux/kernel.h> 51 52/* 53 * Doubly-linked lists. 54 */ 55 56struct list_head { 57 struct list_head *prev; 58 struct list_head *next; 59}; 60 61#define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } 62 63static inline void 64INIT_LIST_HEAD(struct list_head *head) 65{ 66 head->prev = head; 67 head->next = head; 68} 69 70static inline struct list_head * 71list_first(const struct list_head *head) 72{ 73 return head->next; 74} 75 76static inline struct list_head * 77list_last(const struct list_head *head) 78{ 79 return head->prev; 80} 81 82static inline struct list_head * 83list_next(const struct list_head *node) 84{ 85 return node->next; 86} 87 88static inline struct list_head * 89list_prev(const struct list_head *node) 90{ 91 return node->prev; 92} 93 94static inline int 95list_empty(const struct list_head *head) 96{ 97 return (head->next == head); 98} 99 100static inline int 101list_is_singular(const struct list_head *head) 102{ 103 104 if (list_empty(head)) 105 return false; 106 if (head->next != head->prev) 107 return false; 108 return true; 109} 110 111static inline void 112__list_add_between(struct list_head *prev, struct list_head *node, 113 struct list_head *next) 114{ 115 prev->next = node; 116 node->prev = prev; 117 node->next = next; 118 next->prev = node; 119} 120 121static inline void 122list_add(struct list_head *node, struct list_head *head) 123{ 124 __list_add_between(head, node, head->next); 125} 126 127static inline void 128list_add_tail(struct list_head *node, struct list_head *head) 129{ 130 __list_add_between(head->prev, node, head); 131} 132 133static inline void 134list_del(struct list_head *entry) 135{ 136 entry->prev->next = entry->next; 137 entry->next->prev = entry->prev; 138} 139 140static inline void 141__list_splice_between(struct list_head *prev, const struct list_head *list, 142 struct list_head *next) 143{ 144 struct list_head *first = list->next; 145 struct list_head *last = list->prev; 146 147 first->prev = prev; 148 prev->next = first; 149 150 last->next = next; 151 next->prev = last; 152} 153 154static inline void 155list_splice(const struct list_head *list, struct list_head *head) 156{ 157 if (!list_empty(list)) 158 __list_splice_between(head, list, head->next); 159} 160 161static inline void 162list_splice_tail(const struct list_head *list, struct list_head *head) 163{ 164 if (!list_empty(list)) 165 __list_splice_between(head->prev, list, head); 166} 167 168static inline void 169list_move(struct list_head *node, struct list_head *head) 170{ 171 list_del(node); 172 list_add(node, head); 173} 174 175static inline void 176list_move_tail(struct list_head *node, struct list_head *head) 177{ 178 list_del(node); 179 list_add_tail(node, head); 180} 181 182static inline void 183list_replace(struct list_head *old, struct list_head *new) 184{ 185 new->prev = old->prev; 186 old->prev->next = new; 187 new->next = old->next; 188 old->next->prev = new; 189} 190 191static inline void 192list_del_init(struct list_head *node) 193{ 194 list_del(node); 195 INIT_LIST_HEAD(node); 196} 197 198#define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 199#define list_first_entry(PTR, TYPE, FIELD) \ 200 list_entry(list_first((PTR)), TYPE, FIELD) 201#define list_last_entry(PTR, TYPE, FIELD) \ 202 list_entry(list_last((PTR)), TYPE, FIELD) 203#define list_next_entry(ENTRY, FIELD) \ 204 list_entry(list_next(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 205#define list_prev_entry(ENTRY, FIELD) \ 206 list_entry(list_prev(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 207 208#define list_for_each(VAR, HEAD) \ 209 for ((VAR) = list_first((HEAD)); \ 210 (VAR) != (HEAD); \ 211 (VAR) = list_next((VAR))) 212 213#define list_for_each_safe(VAR, NEXT, HEAD) \ 214 for ((VAR) = list_first((HEAD)); \ 215 ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \ 216 (VAR) = (NEXT)) 217 218#define list_for_each_entry(VAR, HEAD, FIELD) \ 219 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 220 &(VAR)->FIELD != (HEAD); \ 221 (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \ 222 FIELD)) 223 224#define list_for_each_entry_reverse(VAR, HEAD, FIELD) \ 225 for ((VAR) = list_entry(list_last((HEAD)), typeof(*(VAR)), FIELD); \ 226 &(VAR)->FIELD != (HEAD); \ 227 (VAR) = list_entry(list_prev(&(VAR)->FIELD), typeof(*(VAR)), \ 228 FIELD)) 229 230#define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 231 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 232 (&(VAR)->FIELD != (HEAD)) && \ 233 ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \ 234 typeof(*(VAR)), FIELD), 1); \ 235 (VAR) = (NEXT)) 236 237#define list_for_each_entry_continue(VAR, HEAD, FIELD) \ 238 for ((VAR) = list_next_entry((VAR), FIELD); \ 239 &(VAR)->FIELD != (HEAD); \ 240 (VAR) = list_next_entry((VAR), FIELD)) 241 242#define list_for_each_entry_continue_reverse(VAR, HEAD, FIELD) \ 243 for ((VAR) = list_prev_entry((VAR), FIELD); \ 244 &(VAR)->FIELD != (HEAD); \ 245 (VAR) = list_prev_entry((VAR), FIELD)) 246 247#define list_for_each_entry_safe_from(VAR, NEXT, HEAD, FIELD) \ 248 for (; \ 249 (&(VAR)->FIELD != (HEAD)) && \ 250 ((NEXT) = list_next_entry((VAR), FIELD)); \ 251 (VAR) = (NEXT)) 252 253/* 254 * `H'ead-only/`H'ash-table doubly-linked lists. 255 */ 256 257LIST_HEAD(hlist_head, hlist_node); 258struct hlist_node { 259 LIST_ENTRY(hlist_node) hln_entry; 260}; 261 262/* 263 * XXX This works only because LIST_HEAD_INITIALIZER doesn't actually 264 * use the name. Really, this is just initialization to a null 265 * pointer. 266 */ 267#define HLIST_HEAD_INIT LIST_HEAD_INITIALIZER(dummy) 268 269static inline void 270INIT_HLIST_HEAD(struct hlist_head *head) 271{ 272 LIST_INIT(head); 273} 274 275static inline bool 276hlist_empty(struct hlist_head *head) 277{ 278 return LIST_EMPTY(head); 279} 280 281static inline struct hlist_node * 282hlist_first(struct hlist_head *head) 283{ 284 return LIST_FIRST(head); 285} 286 287static inline struct hlist_node * 288hlist_next(struct hlist_node *node) 289{ 290 return LIST_NEXT(node, hln_entry); 291} 292 293static inline void 294hlist_add_head(struct hlist_node *node, struct hlist_head *head) 295{ 296 LIST_INSERT_HEAD(head, node, hln_entry); 297} 298 299static inline void 300hlist_add_after(struct hlist_node *node, struct hlist_node *next) 301{ 302 LIST_INSERT_AFTER(node, next, hln_entry); 303} 304 305static inline void 306hlist_del(struct hlist_node *node) 307{ 308 LIST_REMOVE(node, hln_entry); 309} 310 311static inline void 312hlist_del_init(struct hlist_node *node) 313{ 314 LIST_REMOVE(node, hln_entry); 315} 316 317#define hlist_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 318#define hlist_for_each(VAR, HEAD) LIST_FOREACH(VAR, HEAD, hln_entry) 319#define hlist_for_each_safe(VAR, NEXT, HEAD) \ 320 LIST_FOREACH_SAFE(VAR, HEAD, hln_entry, NEXT) 321 322#define hlist_for_each_entry(VAR, HEAD, FIELD) \ 323 for ((VAR) = hlist_entry(LIST_FIRST((HEAD)), typeof(*(VAR)), FIELD); \ 324 &(VAR)->FIELD != NULL; \ 325 (VAR) = hlist_entry(LIST_NEXT(&(VAR)->FIELD, hln_entry), \ 326 typeof(*(VAR)), FIELD)) 327 328#define hlist_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 329 for ((VAR) = hlist_entry(LIST_FIRST((HEAD)), typeof(*(VAR)), FIELD), \ 330 (NEXT) = (&(VAR)->FIELD == NULL ? NULL : \ 331 hlist_entry(LIST_NEXT(&(VAR)->FIELD, hln_entry), \ 332 typeof(*(VAR)), FIELD)); \ 333 &(VAR)->FIELD != NULL; \ 334 (VAR) = (NEXT)) 335 336/* 337 * XXX The nominally RCU-safe APIs below lack dependent read barriers, 338 * so they're not actually RCU-safe...on the alpha, anyway. Someone^TM 339 * should fix this. 340 */ 341 342#define hlist_add_after_rcu hlist_add_after 343#define hlist_add_head_rcu hlist_add_head 344#define hlist_del_init_rcu hlist_del_init 345#define hlist_for_each_entry_rcu hlist_for_each_entry 346 347#endif /* _LINUX_LIST_H_ */ 348