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