1 /* $NetBSD: list.h,v 1.5 2014/08/20 15:26:52 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 56 struct 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 63 static inline void 64 INIT_LIST_HEAD(struct list_head *head) 65 { 66 head->prev = head; 67 head->next = head; 68 } 69 70 static inline struct list_head * 71 list_first(const struct list_head *head) 72 { 73 return head->next; 74 } 75 76 static inline struct list_head * 77 list_last(const struct list_head *head) 78 { 79 return head->prev; 80 } 81 82 static inline struct list_head * 83 list_next(const struct list_head *node) 84 { 85 return node->next; 86 } 87 88 static inline struct list_head * 89 list_prev(const struct list_head *node) 90 { 91 return node->prev; 92 } 93 94 static inline int 95 list_empty(const struct list_head *head) 96 { 97 return (head->next == head); 98 } 99 100 static inline int 101 list_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 111 static 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 121 static inline void 122 list_add(struct list_head *node, struct list_head *head) 123 { 124 __list_add_between(head, node, head->next); 125 } 126 127 static inline void 128 list_add_tail(struct list_head *node, struct list_head *head) 129 { 130 __list_add_between(head->prev, node, head); 131 } 132 133 static inline void 134 list_del(struct list_head *entry) 135 { 136 entry->prev->next = entry->next; 137 entry->next->prev = entry->prev; 138 } 139 140 static 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 154 static inline void 155 list_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 161 static inline void 162 list_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 168 static inline void 169 list_move(struct list_head *node, struct list_head *head) 170 { 171 list_del(node); 172 list_add(node, head); 173 } 174 175 static inline void 176 list_move_tail(struct list_head *node, struct list_head *head) 177 { 178 list_del(node); 179 list_add_tail(node, head); 180 } 181 182 static inline void 183 list_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 191 static inline void 192 list_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 257 LIST_HEAD(hlist_head, hlist_node); 258 struct hlist_node { 259 LIST_ENTRY(hlist_node) hln_entry; 260 }; 261 262 static inline struct hlist_node * 263 hlist_first(struct hlist_head *head) 264 { 265 return LIST_FIRST(head); 266 } 267 268 static inline struct hlist_node * 269 hlist_next(struct hlist_node *node) 270 { 271 return LIST_NEXT(node, hln_entry); 272 } 273 274 static inline void 275 hlist_add_head(struct hlist_node *node, struct hlist_head *head) 276 { 277 LIST_INSERT_HEAD(head, node, hln_entry); 278 } 279 280 static inline void 281 hlist_add_after(struct hlist_node *node, struct hlist_node *next) 282 { 283 LIST_INSERT_AFTER(node, next, hln_entry); 284 } 285 286 static inline void 287 hlist_del(struct hlist_node *node) 288 { 289 LIST_REMOVE(node, hln_entry); 290 } 291 292 static inline void 293 hlist_del_init(struct hlist_node *node) 294 { 295 LIST_REMOVE(node, hln_entry); 296 } 297 298 #define hlist_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 299 #define hlist_for_each(VAR, HEAD) LIST_FOREACH(VAR, HEAD, hln_entry) 300 #define hlist_for_each_safe(VAR, NEXT, HEAD) \ 301 LIST_FOREACH_SAFE(VAR, HEAD, hln_entry, NEXT) 302 303 #define hlist_for_each_entry(VAR, HEAD, FIELD) \ 304 for ((VAR) = hlist_entry(LIST_FIRST((HEAD)), typeof(*(VAR)), FIELD); \ 305 &(VAR)->FIELD != NULL; \ 306 (VAR) = hlist_entry(LIST_NEXT(&(VAR)->FIELD, hln_entry), \ 307 typeof(*(VAR)), FIELD)) 308 309 /* 310 * XXX The nominally RCU-safe APIs below lack dependent read barriers, 311 * so they're not actually RCU-safe...on the alpha, anyway. Someone^TM 312 * should fix this. 313 */ 314 315 #define hlist_add_after_rcu hlist_add_after 316 #define hlist_add_head_rcu hlist_add_head 317 #define hlist_del_init_rcu hlist_del_init 318 #define hlist_for_each_entry_rcu hlist_for_each_entry 319 320 #endif /* _LINUX_LIST_H_ */ 321