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