list.h revision 219820
198937Sdes/*- 298937Sdes * Copyright (c) 2010 Isilon Systems, Inc. 398937Sdes * Copyright (c) 2010 iX Systems, Inc. 4126274Sdes * Copyright (c) 2010 Panasas, Inc. 5126274Sdes * All rights reserved. 6126274Sdes * 7124208Sdes * Redistribution and use in source and binary forms, with or without 898937Sdes * modification, are permitted provided that the following conditions 998937Sdes * are met: 1098937Sdes * 1. Redistributions of source code must retain the above copyright 1198937Sdes * notice unmodified, this list of conditions, and the following 1298937Sdes * disclaimer. 1398937Sdes * 2. Redistributions in binary form must reproduce the above copyright 14162852Sdes * notice, this list of conditions and the following disclaimer in the 15162852Sdes * documentation and/or other materials provided with the distribution. 16162852Sdes * 17162852Sdes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1898937Sdes * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1998937Sdes * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20124208Sdes * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21124208Sdes * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22124208Sdes * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2398937Sdes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24124208Sdes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25124208Sdes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26124208Sdes * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27124208Sdes */ 2898937Sdes#ifndef _LINUX_LIST_H_ 29124208Sdes#define _LINUX_LIST_H_ 30124208Sdes 31124208Sdes/* 32124208Sdes * Since LIST_HEAD conflicts with the linux definition we must include any 33124208Sdes * FreeBSD header which requires it here so it is resolved with the correct 34124208Sdes * definition prior to the undef. 35124208Sdes */ 3698937Sdes#include <linux/types.h> 3798937Sdes 3898937Sdes#include <sys/param.h> 3998937Sdes#include <sys/kernel.h> 40126274Sdes#include <sys/queue.h> 41124208Sdes#include <sys/lock.h> 4298937Sdes#include <sys/mutex.h> 4398937Sdes#include <sys/proc.h> 4498937Sdes#include <sys/vnode.h> 4598937Sdes#include <sys/conf.h> 4698937Sdes#include <sys/socket.h> 47124208Sdes#include <sys/mbuf.h> 4898937Sdes 4998937Sdes#include <net/bpf.h> 5098937Sdes#include <net/if.h> 5198937Sdes#include <net/if_types.h> 5298937Sdes#include <net/if_media.h> 53124208Sdes 54124208Sdes#include <netinet/in.h> 55124208Sdes#include <netinet/in_pcb.h> 56124208Sdes 57124208Sdes#include <netinet6/in6_var.h> 5898937Sdes#include <netinet6/nd6.h> 5998937Sdes 6098937Sdes#include <vm/vm.h> 6198937Sdes#include <vm/vm_object.h> 6298937Sdes 6398937Sdes#define prefetch(x) 64124208Sdes 6598937Sdesstruct list_head { 6698937Sdes struct list_head *next; 6798937Sdes struct list_head *prev; 68124208Sdes}; 69124208Sdes 70124208Sdesstatic inline void 71124208SdesINIT_LIST_HEAD(struct list_head *list) 7298937Sdes{ 7398937Sdes 7498937Sdes list->next = list->prev = list; 7598937Sdes} 76124208Sdes 77124208Sdesstatic inline int 78124208Sdeslist_empty(const struct list_head *head) 79124208Sdes{ 8098937Sdes 8198937Sdes return (head->next == head); 8298937Sdes} 83124208Sdes 8498937Sdesstatic inline void 8598937Sdeslist_del(struct list_head *entry) 86124208Sdes{ 8798937Sdes 8898937Sdes entry->next->prev = entry->prev; 89124208Sdes entry->prev->next = entry->next; 9098937Sdes} 91124208Sdes 9298937Sdesstatic inline void 93124208Sdes_list_add(struct list_head *new, struct list_head *prev, 94124208Sdes struct list_head *next) 95124208Sdes{ 96124208Sdes 97124208Sdes next->prev = new; 9898937Sdes new->next = next; 99124208Sdes new->prev = prev; 10098937Sdes prev->next = new; 10198937Sdes} 102124208Sdes 10398937Sdesstatic inline void 10498937Sdeslist_del_init(struct list_head *entry) 105124208Sdes{ 106124208Sdes 107124208Sdes list_del(entry); 10898937Sdes INIT_LIST_HEAD(entry); 109124208Sdes} 11098937Sdes 11198937Sdes#define list_entry(ptr, type, field) container_of(ptr, type, field) 112124208Sdes 11398937Sdes#define list_for_each(p, head) \ 114124208Sdes for (p = (head)->next; p != (head); p = p->next) 11598937Sdes 11698937Sdes#define list_for_each_safe(p, n, head) \ 11798937Sdes for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next) 11898937Sdes 11998937Sdes#define list_for_each_entry(p, h, field) \ 12098937Sdes for (p = list_entry((h)->next, typeof(*p), field); &p->field != (h); \ 121124208Sdes p = list_entry(p->field.next, typeof(*p), field)) 12298937Sdes 123124208Sdes#define list_for_each_entry_safe(p, n, h, field) \ 124124208Sdes for (p = list_entry((h)->next, typeof(*p), field), \ 12598937Sdes n = list_entry(p->field.next, typeof(*p), field); &p->field != (h);\ 126124208Sdes p = n, n = list_entry(n->field.next, typeof(*n), field)) 12798937Sdes 128124208Sdes#define list_for_each_entry_reverse(p, h, field) \ 129124208Sdes for (p = list_entry((h)->prev, typeof(*p), field); &p->field != (h); \ 13098937Sdes p = list_entry(p->field.prev, typeof(*p), field)) 131124208Sdes 132124208Sdes#define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = p->prev) 13398937Sdes 134124208Sdesstatic inline void 135124208Sdeslist_add(struct list_head *new, struct list_head *head) 13698937Sdes{ 137124208Sdes 138124208Sdes _list_add(new, head, head->next); 139124208Sdes} 14098937Sdes 14198937Sdesstatic inline void 14298937Sdeslist_add_tail(struct list_head *new, struct list_head *head) 14398937Sdes{ 144124208Sdes 145124208Sdes _list_add(new, head->prev, head); 146124208Sdes} 147124208Sdes 148124208Sdesstatic inline void 149124208Sdeslist_move(struct list_head *list, struct list_head *head) 150124208Sdes{ 151124208Sdes 152124208Sdes list_del(list); 153124208Sdes list_add(list, head); 154124208Sdes} 155124208Sdes 15698937Sdesstatic inline void 15798937Sdeslist_move_tail(struct list_head *entry, struct list_head *head) 158124208Sdes{ 159124208Sdes 160124208Sdes list_del(entry); 161124208Sdes list_add_tail(entry, head); 162124208Sdes} 16398937Sdes 164124208Sdesstatic inline void 16598937Sdes_list_splice(const struct list_head *list, struct list_head *prev, 16698937Sdes struct list_head *next) 16798937Sdes{ 168 struct list_head *first; 169 struct list_head *last; 170 171 if (list_empty(list)) 172 return; 173 first = list->next; 174 last = list->prev; 175 first->prev = prev; 176 prev->next = first; 177 last->next = next; 178 next->prev = last; 179} 180 181static inline void 182list_splice(const struct list_head *list, struct list_head *head) 183{ 184 185 _list_splice(list, head, head->next); 186} 187 188static inline void 189list_splice_tail(struct list_head *list, struct list_head *head) 190{ 191 192 _list_splice(list, head->prev, head); 193} 194 195static inline void 196list_splice_init(struct list_head *list, struct list_head *head) 197{ 198 199 _list_splice(list, head, head->next); 200 INIT_LIST_HEAD(list); 201} 202 203static inline void 204list_splice_tail_init(struct list_head *list, struct list_head *head) 205{ 206 207 _list_splice(list, head->prev, head); 208 INIT_LIST_HEAD(list); 209} 210 211#undef LIST_HEAD 212#define LIST_HEAD(name) struct list_head name = { &(name), &(name) } 213 214 215struct hlist_head { 216 struct hlist_node *first; 217}; 218 219struct hlist_node { 220 struct hlist_node *next, **pprev; 221}; 222 223#define HLIST_HEAD_INIT { } 224#define HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT 225#define INIT_HLIST_HEAD(head) (head)->first = NULL 226#define INIT_HLIST_NODE(node) \ 227do { \ 228 (node)->next = NULL; \ 229 (node)->pprev = NULL; \ 230} while (0) 231 232static inline int 233hlist_unhashed(const struct hlist_node *h) 234{ 235 236 return !h->pprev; 237} 238 239static inline int 240hlist_empty(const struct hlist_head *h) 241{ 242 243 return !h->first; 244} 245 246static inline void 247hlist_del(struct hlist_node *n) 248{ 249 250 if (n->next) 251 n->next->pprev = n->pprev; 252 *n->pprev = n->next; 253} 254 255static inline void 256hlist_del_init(struct hlist_node *n) 257{ 258 259 if (hlist_unhashed(n)) 260 return; 261 hlist_del(n); 262 INIT_HLIST_NODE(n); 263} 264 265static inline void 266hlist_add_head(struct hlist_node *n, struct hlist_head *h) 267{ 268 269 n->next = h->first; 270 if (h->first) 271 h->first->pprev = &n->next; 272 h->first = n; 273 n->pprev = &h->first; 274} 275 276static inline void 277hlist_add_before(struct hlist_node *n, struct hlist_node *next) 278{ 279 280 n->pprev = next->pprev; 281 n->next = next; 282 next->pprev = &n->next; 283 *(n->pprev) = n; 284} 285 286static inline void 287hlist_add_after(struct hlist_node *n, struct hlist_node *next) 288{ 289 290 next->next = n->next; 291 n->next = next; 292 next->pprev = &n->next; 293 if (next->next) 294 next->next->pprev = &next->next; 295} 296 297static inline void 298hlist_move_list(struct hlist_head *old, struct hlist_head *new) 299{ 300 301 new->first = old->first; 302 if (new->first) 303 new->first->pprev = &new->first; 304 old->first = NULL; 305} 306 307#define hlist_entry(ptr, type, field) container_of(ptr, type, field) 308 309#define hlist_for_each(p, head) \ 310 for (p = (head)->first; p; p = p->next) 311 312#define hlist_for_each_safe(p, n, head) \ 313 for (p = (head)->first; p && ({ n = p->next; 1; }); p = n) 314 315#define hlist_for_each_entry(tp, p, head, field) \ 316 for (p = (head)->first; \ 317 p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next) 318 319#define hlist_for_each_entry_continue(tp, p, field) \ 320 for (p = (p)->next; \ 321 p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next) 322 323#define hlist_for_each_entry_from(tp, p, field) \ 324 for (; p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next) 325 326#define hlist_for_each_entry_safe(tp, p, n, head, field) \ 327 for (p = (head)->first; p ? \ 328 (n = p->next) | (tp = hlist_entry(p, typeof(*tp), field)) : \ 329 NULL; p = n) 330 331#endif /* _LINUX_LIST_H_ */ 332