sys/compat/linuxkpi/common/include/linux/list.h

   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-2016 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  * $FreeBSD$
  30  */
  31 #ifndef _LINUX_LIST_H_
  32 #define _LINUX_LIST_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_var.h>
  57 #include <net/if_types.h>
  58 #include <net/if_media.h>
  59 #include <net/vnet.h>
  60
  61 #include <netinet/in.h>
  62 #include <netinet/in_pcb.h>
  63 #include <netinet/in_var.h>
  64
  65 #include <netinet6/in6_var.h>
  66 #include <netinet6/nd6.h>
  67
  68 #include <vm/vm.h>
  69 #include <vm/vm_object.h>
  70 #include <vm/pmap.h>
  71
  72 #define prefetch(x)
  73
  74 struct list_head {
  75         struct list_head *next;
  76         struct list_head *prev;
  77 };
  78
  79 static inline void
  80 INIT_LIST_HEAD(struct list_head *list)
  81 {
  82
  83         list->next = list->prev = list;
  84 }
  85
  86 static inline int
  87 list_empty(const struct list_head *head)
  88 {
  89
  90         return (head->next == head);
  91 }
  92
  93 static inline void
  94 list_del(struct list_head *entry)
  95 {
  96
  97         entry->next->prev = entry->prev;
  98         entry->prev->next = entry->next;
  99 }
 100
 101 static inline void
 102 list_replace(struct list_head *old, struct list_head *new)
 103 {
 104         new->next = old->next;
 105         new->next->prev = new;
 106         new->prev = old->prev;
 107         new->prev->next = new;
 108 }
 109
 110 static inline void
 111 linux_list_add(struct list_head *new, struct list_head *prev,
 112     struct list_head *next)
 113 {
 114
 115         next->prev = new;
 116         new->next = next;
 117         new->prev = prev;
 118         prev->next = new;
 119 }
 120
 121 static inline void
 122 list_del_init(struct list_head *entry)
 123 {
 124
 125         list_del(entry);
 126         INIT_LIST_HEAD(entry);
 127 }
 128
 129 #define list_entry(ptr, type, field)    container_of(ptr, type, field)
 130
 131 #define list_first_entry(ptr, type, member) \
 132         list_entry((ptr)->next, type, member)
 133
 134 #define list_next_entry(ptr, member)                                    \
 135         list_entry(((ptr)->member.next), typeof(*(ptr)), member)
 136
 137 #define list_for_each(p, head)                                          \
 138         for (p = (head)->next; p != (head); p = (p)->next)
 139
 140 #define list_for_each_safe(p, n, head)                                  \
 141         for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next)
 142
 143 #define list_for_each_entry(p, h, field)                                \
 144         for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \
 145             p = list_entry((p)->field.next, typeof(*p), field))
 146
 147 #define list_for_each_entry_safe(p, n, h, field)                        \
 148         for (p = list_entry((h)->next, typeof(*p), field),              \
 149             n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\
 150             p = n, n = list_entry(n->field.next, typeof(*n), field))
 151
 152 #define list_for_each_entry_from(p, h, field) \
 153         for ( ; &(p)->field != (h); \
 154             p = list_entry((p)->field.next, typeof(*p), field))
 155
 156 #define list_for_each_entry_continue(p, h, field)                       \
 157         for (p = list_next_entry((p), field); &(p)->field != (h);       \
 158             p = list_next_entry((p), field))
 159
 160 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 161         for (n = list_entry((pos)->member.next, typeof(*pos), member);          \
 162              &(pos)->member != (head);                                          \
 163              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 164
 165 #define list_for_each_entry_reverse(p, h, field)                        \
 166         for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \
 167             p = list_entry((p)->field.prev, typeof(*p), field))
 168
 169 #define list_for_each_entry_continue_reverse(p, h, field) \
 170         for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
 171             p = list_entry((p)->field.prev, typeof(*p), field))
 172
 173 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev)
 174
 175 static inline void
 176 list_add(struct list_head *new, struct list_head *head)
 177 {
 178
 179         linux_list_add(new, head, head->next);
 180 }
 181
 182 static inline void
 183 list_add_tail(struct list_head *new, struct list_head *head)
 184 {
 185
 186         linux_list_add(new, head->prev, head);
 187 }
 188
 189 static inline void
 190 list_move(struct list_head *list, struct list_head *head)
 191 {
 192
 193         list_del(list);
 194         list_add(list, head);
 195 }
 196
 197 static inline void
 198 list_move_tail(struct list_head *entry, struct list_head *head)
 199 {
 200
 201         list_del(entry);
 202         list_add_tail(entry, head);
 203 }
 204
 205 static inline void
 206 linux_list_splice(const struct list_head *list, struct list_head *prev,
 207     struct list_head *next)
 208 {
 209         struct list_head *first;
 210         struct list_head *last;
 211
 212         if (list_empty(list))
 213                 return;
 214         first = list->next;
 215         last = list->prev;
 216         first->prev = prev;
 217         prev->next = first;
 218         last->next = next;
 219         next->prev = last;
 220 }
 221
 222 static inline void
 223 list_splice(const struct list_head *list, struct list_head *head)
 224 {
 225
 226         linux_list_splice(list, head, head->next);
 227 }
 228
 229 static inline void
 230 list_splice_tail(struct list_head *list, struct list_head *head)
 231 {
 232
 233         linux_list_splice(list, head->prev, head);
 234 }
 235
 236 static inline void
 237 list_splice_init(struct list_head *list, struct list_head *head)
 238 {
 239
 240         linux_list_splice(list, head, head->next);
 241         INIT_LIST_HEAD(list);
 242 }
 243
 244 static inline void
 245 list_splice_tail_init(struct list_head *list, struct list_head *head)
 246 {
 247
 248         linux_list_splice(list, head->prev, head);
 249         INIT_LIST_HEAD(list);
 250 }
 251
 252 #undef LIST_HEAD
 253 #define LIST_HEAD(name) struct list_head name = { &(name), &(name) }
 254
 255
 256 struct hlist_head {
 257         struct hlist_node *first;
 258 };
 259
 260 struct hlist_node {
 261         struct hlist_node *next, **pprev;
 262 };
 263
 264 #define HLIST_HEAD_INIT { }
 265 #define HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT
 266 #define INIT_HLIST_HEAD(head) (head)->first = NULL
 267 #define INIT_HLIST_NODE(node)                                           \
 268 do {                                                                    \
 269         (node)->next = NULL;                                            \
 270         (node)->pprev = NULL;                                           \
 271 } while (0)
 272
 273 static inline int
 274 hlist_unhashed(const struct hlist_node *h)
 275 {
 276
 277         return !h->pprev;
 278 }
 279
 280 static inline int
 281 hlist_empty(const struct hlist_head *h)
 282 {
 283
 284         return !h->first;
 285 }
 286
 287 static inline void
 288 hlist_del(struct hlist_node *n)
 289 {
 290
 291         if (n->next)
 292                 n->next->pprev = n->pprev;
 293         *n->pprev = n->next;
 294 }
 295
 296 static inline void
 297 hlist_del_init(struct hlist_node *n)
 298 {
 299
 300         if (hlist_unhashed(n))
 301                 return;
 302         hlist_del(n);
 303         INIT_HLIST_NODE(n);
 304 }
 305
 306 static inline void
 307 hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 308 {
 309
 310         n->next = h->first;
 311         if (h->first)
 312                 h->first->pprev = &n->next;
 313         h->first = n;
 314         n->pprev = &h->first;
 315 }
 316
 317 static inline void
 318 hlist_add_before(struct hlist_node *n, struct hlist_node *next)
 319 {
 320
 321         n->pprev = next->pprev;
 322         n->next = next;
 323         next->pprev = &n->next;
 324         *(n->pprev) = n;
 325 }
 326
 327 static inline void
 328 hlist_add_after(struct hlist_node *n, struct hlist_node *next)
 329 {
 330
 331         next->next = n->next;
 332         n->next = next;
 333         next->pprev = &n->next;
 334         if (next->next)
 335                 next->next->pprev = &next->next;
 336 }
 337
 338 static inline void
 339 hlist_move_list(struct hlist_head *old, struct hlist_head *new)
 340 {
 341
 342         new->first = old->first;
 343         if (new->first)
 344                 new->first->pprev = &new->first;
 345         old->first = NULL;
 346 }
 347
 348 /**
 349  * list_is_singular - tests whether a list has just one entry.
 350  * @head: the list to test.
 351  */
 352 static inline int list_is_singular(const struct list_head *head)
 353 {
 354         return !list_empty(head) && (head->next == head->prev);
 355 }
 356
 357 static inline void __list_cut_position(struct list_head *list,
 358                 struct list_head *head, struct list_head *entry)
 359 {
 360         struct list_head *new_first = entry->next;
 361         list->next = head->next;
 362         list->next->prev = list;
 363         list->prev = entry;
 364         entry->next = list;
 365         head->next = new_first;
 366         new_first->prev = head;
 367 }
 368
 369 /**
 370  * list_cut_position - cut a list into two
 371  * @list: a new list to add all removed entries
 372  * @head: a list with entries
 373  * @entry: an entry within head, could be the head itself
 374  *      and if so we won't cut the list
 375  *
 376  * This helper moves the initial part of @head, up to and
 377  * including @entry, from @head to @list. You should
 378  * pass on @entry an element you know is on @head. @list
 379  * should be an empty list or a list you do not care about
 380  * losing its data.
 381  *
 382  */
 383 static inline void list_cut_position(struct list_head *list,
 384                 struct list_head *head, struct list_head *entry)
 385 {
 386         if (list_empty(head))
 387                 return;
 388         if (list_is_singular(head) &&
 389                 (head->next != entry && head != entry))
 390                 return;
 391         if (entry == head)
 392                 INIT_LIST_HEAD(list);
 393         else
 394                 __list_cut_position(list, head, entry);
 395 }
 396
 397 /**
 398  *  list_is_last - tests whether @list is the last entry in list @head
 399  *   @list: the entry to test
 400  *    @head: the head of the list
 401  */
 402 static inline int list_is_last(const struct list_head *list,
 403                                 const struct list_head *head)
 404 {
 405         return list->next == head;
 406 }
 407
 408 #define hlist_entry(ptr, type, field)   container_of(ptr, type, field)
 409
 410 #define hlist_for_each(p, head)                                         \
 411         for (p = (head)->first; p; p = (p)->next)
 412
 413 #define hlist_for_each_safe(p, n, head)                                 \
 414         for (p = (head)->first; p && ({ n = (p)->next; 1; }); p = n)
 415
 416 #define hlist_entry_safe(ptr, type, member) \
 417         ((ptr) ? hlist_entry(ptr, type, member) : NULL)
 418
 419 #define hlist_for_each_entry(pos, head, member)                         \
 420         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
 421              pos;                                                       \
 422              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 423
 424 #define hlist_for_each_entry_continue(pos, member)                      \
 425         for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); \
 426              (pos);                                                     \
 427              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 428
 429 #define hlist_for_each_entry_from(pos, member)                          \
 430         for (; (pos);                                                           \
 431              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 432
 433 #define hlist_for_each_entry_safe(pos, n, head, member)                 \
 434         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
 435              (pos) && ({ n = (pos)->member.next; 1; });                 \
 436              pos = hlist_entry_safe(n, typeof(*(pos)), member))
 437
 438 #endif /* _LINUX_LIST_H_ */