1 /* $NetBSD: list.h,v 1.4 2014/07/16 20:59: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/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_next(const struct list_head *node) 78 { 79 return node->next; 80 } 81 82 static inline struct list_head * 83 list_prev(const struct list_head *node) 84 { 85 return node->prev; 86 } 87 88 static inline int 89 list_empty(const struct list_head *head) 90 { 91 return (head->next == head); 92 } 93 94 static inline int 95 list_is_singular(const struct list_head *head) 96 { 97 98 if (list_empty(head)) 99 return false; 100 if (head->next != head->prev) 101 return false; 102 return true; 103 } 104 105 static inline void 106 __list_add_between(struct list_head *prev, struct list_head *node, 107 struct list_head *next) 108 { 109 prev->next = node; 110 node->prev = prev; 111 node->next = next; 112 next->prev = node; 113 } 114 115 static inline void 116 list_add(struct list_head *node, struct list_head *head) 117 { 118 __list_add_between(head, node, head->next); 119 } 120 121 static inline void 122 list_add_tail(struct list_head *node, struct list_head *head) 123 { 124 __list_add_between(head->prev, node, head); 125 } 126 127 static inline void 128 list_del(struct list_head *entry) 129 { 130 entry->prev->next = entry->next; 131 entry->next->prev = entry->prev; 132 } 133 134 static inline void 135 __list_splice_between(struct list_head *prev, const struct list_head *list, 136 struct list_head *next) 137 { 138 struct list_head *first = list->next; 139 struct list_head *last = list->prev; 140 141 first->prev = prev; 142 prev->next = first; 143 144 last->next = next; 145 next->prev = last; 146 } 147 148 static inline void 149 list_splice(const struct list_head *list, struct list_head *head) 150 { 151 if (!list_empty(list)) 152 __list_splice_between(head, list, head->next); 153 } 154 155 static inline void 156 list_splice_tail(const struct list_head *list, struct list_head *head) 157 { 158 if (!list_empty(list)) 159 __list_splice_between(head->prev, list, head); 160 } 161 162 static inline void 163 list_move(struct list_head *node, struct list_head *head) 164 { 165 list_del(node); 166 list_add(node, head); 167 } 168 169 static inline void 170 list_move_tail(struct list_head *node, struct list_head *head) 171 { 172 list_del(node); 173 list_add_tail(node, head); 174 } 175 176 static inline void 177 list_replace(struct list_head *old, struct list_head *new) 178 { 179 new->prev = old->prev; 180 old->prev->next = new; 181 new->next = old->next; 182 old->next->prev = new; 183 } 184 185 static inline void 186 list_del_init(struct list_head *node) 187 { 188 list_del(node); 189 INIT_LIST_HEAD(node); 190 } 191 192 #define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 193 #define list_first_entry(PTR, TYPE, FIELD) \ 194 list_entry(list_first((PTR)), TYPE, FIELD) 195 #define list_next_entry(ENTRY, FIELD) \ 196 list_entry(list_next(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 197 198 #define list_for_each(VAR, HEAD) \ 199 for ((VAR) = list_first((HEAD)); \ 200 (VAR) != (HEAD); \ 201 (VAR) = list_next((VAR))) 202 203 #define list_for_each_safe(VAR, NEXT, HEAD) \ 204 for ((VAR) = list_first((HEAD)); \ 205 ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \ 206 (VAR) = (NEXT)) 207 208 #define list_for_each_entry(VAR, HEAD, FIELD) \ 209 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 210 &(VAR)->FIELD != (HEAD); \ 211 (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \ 212 FIELD)) 213 214 #define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 215 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 216 (&(VAR)->FIELD != (HEAD)) && \ 217 ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \ 218 typeof(*(VAR)), FIELD), 1); \ 219 (VAR) = (NEXT)) 220 221 #define list_for_each_entry_continue(VAR, HEAD, FIELD) \ 222 for ((VAR) = list_next_entry((VAR), FIELD); \ 223 &(VAR)->FIELD != (HEAD); \ 224 (VAR) = list_next_entry((VAR), FIELD)) 225 226 #define list_for_each_entry_safe_from(VAR, NEXT, HEAD, FIELD) \ 227 for (; \ 228 (&(VAR)->FIELD != (HEAD)) && \ 229 ((NEXT) = list_next_entry((VAR), FIELD)); \ 230 (VAR) = (NEXT)) 231 232 /* 233 * `H'ead-only/`H'ash-table doubly-linked lists. 234 */ 235 236 LIST_HEAD(hlist_head, hlist_node); 237 struct hlist_node { 238 LIST_ENTRY(hlist_node) hln_entry; 239 }; 240 241 static inline struct hlist_node * 242 hlist_first(struct hlist_head *head) 243 { 244 return LIST_FIRST(head); 245 } 246 247 static inline struct hlist_node * 248 hlist_next(struct hlist_node *node) 249 { 250 return LIST_NEXT(node, hln_entry); 251 } 252 253 static inline void 254 hlist_add_head(struct hlist_node *node, struct hlist_head *head) 255 { 256 LIST_INSERT_HEAD(head, node, hln_entry); 257 } 258 259 static inline void 260 hlist_add_after(struct hlist_node *node, struct hlist_node *next) 261 { 262 LIST_INSERT_AFTER(node, next, hln_entry); 263 } 264 265 static inline void 266 hlist_del(struct hlist_node *node) 267 { 268 LIST_REMOVE(node, hln_entry); 269 } 270 271 static inline void 272 hlist_del_init(struct hlist_node *node) 273 { 274 LIST_REMOVE(node, hln_entry); 275 } 276 277 #define hlist_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 278 #define hlist_for_each(VAR, HEAD) LIST_FOREACH(VAR, HEAD, hln_entry) 279 #define hlist_for_each_safe(VAR, NEXT, HEAD) \ 280 LIST_FOREACH_SAFE(VAR, HEAD, hln_entry, NEXT) 281 282 #define hlist_for_each_entry(VAR, HEAD, FIELD) \ 283 for ((VAR) = hlist_entry(LIST_FIRST((HEAD)), typeof(*(VAR)), FIELD); \ 284 &(VAR)->FIELD != NULL; \ 285 (VAR) = hlist_entry(LIST_NEXT(&(VAR)->FIELD, hln_entry), \ 286 typeof(*(VAR)), FIELD)) 287 288 /* 289 * XXX The nominally RCU-safe APIs below lack dependent read barriers, 290 * so they're not actually RCU-safe...on the alpha, anyway. Someone^TM 291 * should fix this. 292 */ 293 294 #define hlist_add_after_rcu hlist_add_after 295 #define hlist_add_head_rcu hlist_add_head 296 #define hlist_del_init_rcu hlist_del_init 297 #define hlist_for_each_entry_rcu hlist_for_each_entry 298 299 #endif /* _LINUX_LIST_H_ */ 300