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