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