1 /*- 2 * Copyright (c) 2010 Isilon Systems, Inc. 3 * Copyright (c) 2010 iX Systems, Inc. 4 * Copyright (c) 2010 Panasas, Inc. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice unmodified, this list of conditions, and the following 12 * disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 #ifndef _LINUX_LIST_H_ 29 #define _LINUX_LIST_H_ 30 31 /* 32 * Since LIST_HEAD conflicts with the linux definition we must include any 33 * FreeBSD header which requires it here so it is resolved with the correct 34 * definition prior to the undef. 35 */ 36 #include <linux/compiler.h> 37 38 #include <sys/param.h> 39 #include <sys/kernel.h> 40 #include <sys/queue.h> 41 #include <sys/lock.h> 42 #include <sys/mutex.h> 43 #include <sys/proc.h> 44 #include <sys/vnode.h> 45 #include <sys/conf.h> 46 #include <sys/socket.h> 47 #include <sys/mbuf.h> 48 49 #include <net/bpf.h> 50 #include <net/if.h> 51 #include <net/if_types.h> 52 #include <net/if_media.h> 53 54 #include <netinet/in.h> 55 #include <netinet/in_pcb.h> 56 57 #include <netinet6/in6_var.h> 58 #include <netinet6/nd6.h> 59 60 #include <vm/vm.h> 61 #include <vm/vm_object.h> 62 63 #define prefetch(x) 64 65 struct list_head { 66 struct list_head *next; 67 struct list_head *prev; 68 }; 69 70 static inline void 71 INIT_LIST_HEAD(struct list_head *list) 72 { 73 74 list->next = list->prev = list; 75 } 76 77 static inline int 78 list_empty(const struct list_head *head) 79 { 80 81 return (head->next == head); 82 } 83 84 static inline void 85 list_del(struct list_head *entry) 86 { 87 88 entry->next->prev = entry->prev; 89 entry->prev->next = entry->next; 90 } 91 92 static inline void list_replace(struct list_head *old, 93 struct list_head *new) 94 { 95 new->next = old->next; 96 new->next->prev = new; 97 new->prev = old->prev; 98 new->prev->next = new; 99 } 100 101 static inline void 102 _list_add(struct list_head *new, struct list_head *prev, 103 struct list_head *next) 104 { 105 106 next->prev = new; 107 new->next = next; 108 new->prev = prev; 109 prev->next = new; 110 } 111 112 static inline void 113 list_del_init(struct list_head *entry) 114 { 115 116 list_del(entry); 117 INIT_LIST_HEAD(entry); 118 } 119 120 #define list_entry(ptr, type, field) container_of(ptr, type, field) 121 122 #define list_first_entry(ptr, type, member) \ 123 list_entry((ptr)->next, type, member) 124 125 #define list_for_each(p, head) \ 126 for (p = (head)->next; p != (head); p = p->next) 127 128 #define list_for_each_safe(p, n, head) \ 129 for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next) 130 131 #define list_for_each_entry(p, h, field) \ 132 for (p = list_entry((h)->next, typeof(*p), field); &p->field != (h); \ 133 p = list_entry(p->field.next, typeof(*p), field)) 134 135 #define list_for_each_entry_continue_reverse(pos, head, member) \ 136 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \ 137 &pos->member != (head); \ 138 pos = list_entry(pos->member.prev, typeof(*pos), member)) 139 140 #define list_for_each_entry_safe(p, n, h, field) \ 141 for (p = list_entry((h)->next, typeof(*p), field), \ 142 n = list_entry(p->field.next, typeof(*p), field); &p->field != (h);\ 143 p = n, n = list_entry(n->field.next, typeof(*n), field)) 144 145 #define list_for_each_entry_safe_from(pos, n, head, member) \ 146 for (n = list_entry(pos->member.next, typeof(*pos), member); \ 147 &pos->member != (head); \ 148 pos = n, n = list_entry(n->member.next, typeof(*n), member)) 149 150 #define list_for_each_entry_reverse(p, h, field) \ 151 for (p = list_entry((h)->prev, typeof(*p), field); &p->field != (h); \ 152 p = list_entry(p->field.prev, typeof(*p), field)) 153 154 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = p->prev) 155 156 static inline void 157 list_add(struct list_head *new, struct list_head *head) 158 { 159 160 _list_add(new, head, head->next); 161 } 162 163 static inline void 164 list_add_tail(struct list_head *new, struct list_head *head) 165 { 166 167 _list_add(new, head->prev, head); 168 } 169 170 static inline void 171 list_move(struct list_head *list, struct list_head *head) 172 { 173 174 list_del(list); 175 list_add(list, head); 176 } 177 178 static inline void 179 list_move_tail(struct list_head *entry, struct list_head *head) 180 { 181 182 list_del(entry); 183 list_add_tail(entry, head); 184 } 185 186 static inline void 187 _list_splice(const struct list_head *list, struct list_head *prev, 188 struct list_head *next) 189 { 190 struct list_head *first; 191 struct list_head *last; 192 193 if (list_empty(list)) 194 return; 195 first = list->next; 196 last = list->prev; 197 first->prev = prev; 198 prev->next = first; 199 last->next = next; 200 next->prev = last; 201 } 202 203 static inline void 204 list_splice(const struct list_head *list, struct list_head *head) 205 { 206 207 _list_splice(list, head, head->next); 208 } 209 210 static inline void 211 list_splice_tail(struct list_head *list, struct list_head *head) 212 { 213 214 _list_splice(list, head->prev, head); 215 } 216 217 static inline void 218 list_splice_init(struct list_head *list, struct list_head *head) 219 { 220 221 _list_splice(list, head, head->next); 222 INIT_LIST_HEAD(list); 223 } 224 225 static inline void 226 list_splice_tail_init(struct list_head *list, struct list_head *head) 227 { 228 229 _list_splice(list, head->prev, head); 230 INIT_LIST_HEAD(list); 231 } 232 233 #define LINUX_LIST_HEAD(name) struct list_head name = { &(name), &(name) } 234 235 236 struct hlist_head { 237 struct hlist_node *first; 238 }; 239 240 struct hlist_node { 241 struct hlist_node *next, **pprev; 242 }; 243 244 #define HLIST_HEAD_INIT { } 245 #define HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT 246 #define INIT_HLIST_HEAD(head) (head)->first = NULL 247 #define INIT_HLIST_NODE(node) \ 248 do { \ 249 (node)->next = NULL; \ 250 (node)->pprev = NULL; \ 251 } while (0) 252 253 static inline int 254 hlist_unhashed(const struct hlist_node *h) 255 { 256 257 return !h->pprev; 258 } 259 260 static inline int 261 hlist_empty(const struct hlist_head *h) 262 { 263 264 return !h->first; 265 } 266 267 static inline void 268 hlist_del(struct hlist_node *n) 269 { 270 271 if (n->next) 272 n->next->pprev = n->pprev; 273 *n->pprev = n->next; 274 } 275 276 static inline void 277 hlist_del_init(struct hlist_node *n) 278 { 279 280 if (hlist_unhashed(n)) 281 return; 282 hlist_del(n); 283 INIT_HLIST_NODE(n); 284 } 285 286 static inline void 287 hlist_add_head(struct hlist_node *n, struct hlist_head *h) 288 { 289 290 n->next = h->first; 291 if (h->first) 292 h->first->pprev = &n->next; 293 h->first = n; 294 n->pprev = &h->first; 295 } 296 297 static inline void 298 hlist_add_before(struct hlist_node *n, struct hlist_node *next) 299 { 300 301 n->pprev = next->pprev; 302 n->next = next; 303 next->pprev = &n->next; 304 *(n->pprev) = n; 305 } 306 307 static inline void 308 hlist_add_after(struct hlist_node *n, struct hlist_node *next) 309 { 310 311 next->next = n->next; 312 n->next = next; 313 next->pprev = &n->next; 314 if (next->next) 315 next->next->pprev = &next->next; 316 } 317 318 static inline void 319 hlist_move_list(struct hlist_head *old, struct hlist_head *new) 320 { 321 322 new->first = old->first; 323 if (new->first) 324 new->first->pprev = &new->first; 325 old->first = NULL; 326 } 327 328 #define hlist_entry(ptr, type, field) container_of(ptr, type, field) 329 330 #define hlist_for_each(p, head) \ 331 for (p = (head)->first; p; p = p->next) 332 333 #define hlist_for_each_safe(p, n, head) \ 334 for (p = (head)->first; p && ({ n = p->next; 1; }); p = n) 335 336 #define hlist_for_each_entry(tp, p, head, field) \ 337 for (p = (head)->first; \ 338 p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next) 339 340 #define hlist_for_each_entry_continue(tp, p, field) \ 341 for (p = (p)->next; \ 342 p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next) 343 344 #define hlist_for_each_entry_from(tp, p, field) \ 345 for (; p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next) 346 347 #define hlist_for_each_entry_safe(tp, p, n, head, field) \ 348 for (p = (head)->first; p ? \ 349 (n = p->next) | (tp = hlist_entry(p, typeof(*tp), field)) : \ 350 NULL; p = n) 351 352 void drm_list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv, 353 struct list_head *a, struct list_head *b)); 354 355 #define hlist_for_each_entry_rcu(tp, p, head, field) \ 356 hlist_for_each_entry(tp, p, head, field) 357 358 #define hlist_add_after_rcu(prev, n) hlist_add_after(prev, n) 359 360 #define hlist_add_head_rcu(n, h) hlist_add_head(n, h) 361 362 #define hlist_del_init_rcu(n) hlist_del_init(n) 363 364 #endif /* _LINUX_LIST_H_ */ 365