l4/pkg/input/lib/include/linux/list.h

   1 #ifndef _LINUX_LIST_H
   2 #define _LINUX_LIST_H
   3
   4 #ifdef __KERNEL__
   5
   6 #ifndef L4INPUT
   7 #include <linux/stddef.h>
   8 #include <linux/prefetch.h>
   9 #include <asm/system.h>
  10 #else
  11 #include <linux/kernel.h>
  12 #include <linux/prefetch.h>
  13 #endif
  14
  15 /*
  16  * These are non-NULL pointers that will result in page faults
  17  * under normal circumstances, used to verify that nobody uses
  18  * non-initialized list entries.
  19  */
  20 #define LIST_POISON1  ((void *) 0x00100100)
  21 #define LIST_POISON2  ((void *) 0x00200200)
  22
  23 /*
  24  * Simple doubly linked list implementation.
  25  *
  26  * Some of the internal functions ("__xxx") are useful when
  27  * manipulating whole lists rather than single entries, as
  28  * sometimes we already know the next/prev entries and we can
  29  * generate better code by using them directly rather than
  30  * using the generic single-entry routines.
  31  */
  32
  33 struct list_head {
  34         struct list_head *next, *prev;
  35 };
  36
  37 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  38
  39 #define LIST_HEAD(name) \
  40         struct list_head name = LIST_HEAD_INIT(name)
  41
  42 #define INIT_LIST_HEAD(ptr) do { \
  43         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  44 } while (0)
  45
  46 /*
  47  * Insert a new entry between two known consecutive entries.
  48  *
  49  * This is only for internal list manipulation where we know
  50  * the prev/next entries already!
  51  */
  52 static inline void __list_add(struct list_head *new,
  53                               struct list_head *prev,
  54                               struct list_head *next)
  55 {
  56         next->prev = new;
  57         new->next = next;
  58         new->prev = prev;
  59         prev->next = new;
  60 }
  61
  62 /**
  63  * list_add - add a new entry
  64  * @new: new entry to be added
  65  * @head: list head to add it after
  66  *
  67  * Insert a new entry after the specified head.
  68  * This is good for implementing stacks.
  69  */
  70 static inline void list_add(struct list_head *new, struct list_head *head)
  71 {
  72         __list_add(new, head, head->next);
  73 }
  74
  75 /**
  76  * list_add_tail - add a new entry
  77  * @new: new entry to be added
  78  * @head: list head to add it before
  79  *
  80  * Insert a new entry before the specified head.
  81  * This is useful for implementing queues.
  82  */
  83 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  84 {
  85         __list_add(new, head->prev, head);
  86 }
  87
  88 /*
  89  * Insert a new entry between two known consecutive entries.
  90  *
  91  * This is only for internal list manipulation where we know
  92  * the prev/next entries already!
  93  */
  94 static __inline__ void __list_add_rcu(struct list_head * new,
  95         struct list_head * prev,
  96         struct list_head * next)
  97 {
  98         new->next = next;
  99         new->prev = prev;
 100 #ifndef L4INPUT
 101         smp_wmb();
 102 #endif
 103         next->prev = new;
 104         prev->next = new;
 105 }
 106
 107 /**
 108  * list_add_rcu - add a new entry to rcu-protected list
 109  * @new: new entry to be added
 110  * @head: list head to add it after
 111  *
 112  * Insert a new entry after the specified head.
 113  * This is good for implementing stacks.
 114  */
 115 static __inline__ void list_add_rcu(struct list_head *new, struct list_head *head)
 116 {
 117         __list_add_rcu(new, head, head->next);
 118 }
 119
 120 /**
 121  * list_add_tail_rcu - add a new entry to rcu-protected list
 122  * @new: new entry to be added
 123  * @head: list head to add it before
 124  *
 125  * Insert a new entry before the specified head.
 126  * This is useful for implementing queues.
 127  */
 128 static __inline__ void list_add_tail_rcu(struct list_head *new, struct list_head *head)
 129 {
 130         __list_add_rcu(new, head->prev, head);
 131 }
 132
 133 /*
 134  * Delete a list entry by making the prev/next entries
 135  * point to each other.
 136  *
 137  * This is only for internal list manipulation where we know
 138  * the prev/next entries already!
 139  */
 140 static inline void __list_del(struct list_head * prev, struct list_head * next)
 141 {
 142         next->prev = prev;
 143         prev->next = next;
 144 }
 145
 146 /**
 147  * list_del - deletes entry from list.
 148  * @entry: the element to delete from the list.
 149  * Note: list_empty on entry does not return true after this, the entry is
 150  * in an undefined state.
 151  */
 152 static inline void list_del(struct list_head *entry)
 153 {
 154         __list_del(entry->prev, entry->next);
 155         entry->next = LIST_POISON1;
 156         entry->prev = LIST_POISON2;
 157 }
 158
 159 /**
 160  * list_del_rcu - deletes entry from list without re-initialization
 161  * @entry: the element to delete from the list.
 162  *
 163  * Note: list_empty on entry does not return true after this,
 164  * the entry is in an undefined state. It is useful for RCU based
 165  * lockfree traversal.
 166  *
 167  * In particular, it means that we can not poison the forward
 168  * pointers that may still be used for walking the list.
 169  */
 170 static inline void list_del_rcu(struct list_head *entry)
 171 {
 172         __list_del(entry->prev, entry->next);
 173         entry->prev = LIST_POISON2;
 174 }
 175
 176 /**
 177  * list_del_init - deletes entry from list and reinitialize it.
 178  * @entry: the element to delete from the list.
 179  */
 180 static inline void list_del_init(struct list_head *entry)
 181 {
 182         __list_del(entry->prev, entry->next);
 183         INIT_LIST_HEAD(entry);
 184 }
 185
 186 /**
 187  * list_move - delete from one list and add as another's head
 188  * @list: the entry to move
 189  * @head: the head that will precede our entry
 190  */
 191 static inline void list_move(struct list_head *list, struct list_head *head)
 192 {
 193         __list_del(list->prev, list->next);
 194         list_add(list, head);
 195 }
 196
 197 /**
 198  * list_move_tail - delete from one list and add as another's tail
 199  * @list: the entry to move
 200  * @head: the head that will follow our entry
 201  */
 202 static inline void list_move_tail(struct list_head *list,
 203                                   struct list_head *head)
 204 {
 205         __list_del(list->prev, list->next);
 206         list_add_tail(list, head);
 207 }
 208
 209 /**
 210  * list_empty - tests whether a list is empty
 211  * @head: the list to test.
 212  */
 213 static inline int list_empty(const struct list_head *head)
 214 {
 215         return head->next == head;
 216 }
 217
 218 static inline void __list_splice(struct list_head *list,
 219                                  struct list_head *head)
 220 {
 221         struct list_head *first = list->next;
 222         struct list_head *last = list->prev;
 223         struct list_head *at = head->next;
 224
 225         first->prev = head;
 226         head->next = first;
 227
 228         last->next = at;
 229         at->prev = last;
 230 }
 231
 232 /**
 233  * list_splice - join two lists
 234  * @list: the new list to add.
 235  * @head: the place to add it in the first list.
 236  */
 237 static inline void list_splice(struct list_head *list, struct list_head *head)
 238 {
 239         if (!list_empty(list))
 240                 __list_splice(list, head);
 241 }
 242
 243 /**
 244  * list_splice_init - join two lists and reinitialise the emptied list.
 245  * @list: the new list to add.
 246  * @head: the place to add it in the first list.
 247  *
 248  * The list at @list is reinitialised
 249  */
 250 static inline void list_splice_init(struct list_head *list,
 251                                     struct list_head *head)
 252 {
 253         if (!list_empty(list)) {
 254                 __list_splice(list, head);
 255                 INIT_LIST_HEAD(list);
 256         }
 257 }
 258
 259 /**
 260  * list_entry - get the struct for this entry
 261  * @ptr:        the &struct list_head pointer.
 262  * @type:       the type of the struct this is embedded in.
 263  * @member:     the name of the list_struct within the struct.
 264  */
 265 #define list_entry(ptr, type, member) \
 266         container_of(ptr, type, member)
 267
 268 /**
 269  * list_for_each        -       iterate over a list
 270  * @pos:        the &struct list_head to use as a loop counter.
 271  * @head:       the head for your list.
 272  */
 273 #define list_for_each(pos, head) \
 274         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
 275                 pos = pos->next, prefetch(pos->next))
 276
 277 /**
 278  * __list_for_each      -       iterate over a list
 279  * @pos:        the &struct list_head to use as a loop counter.
 280  * @head:       the head for your list.
 281  *
 282  * This variant differs from list_for_each() in that it's the
 283  * simplest possible list iteration code, no prefetching is done.
 284  * Use this for code that knows the list to be very short (empty
 285  * or 1 entry) most of the time.
 286  */
 287 #define __list_for_each(pos, head) \
 288         for (pos = (head)->next; pos != (head); pos = pos->next)
 289
 290 /**
 291  * list_for_each_prev   -       iterate over a list backwards
 292  * @pos:        the &struct list_head to use as a loop counter.
 293  * @head:       the head for your list.
 294  */
 295 #define list_for_each_prev(pos, head) \
 296         for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
 297                 pos = pos->prev, prefetch(pos->prev))
 298
 299 /**
 300  * list_for_each_safe   -       iterate over a list safe against removal of list entry
 301  * @pos:        the &struct list_head to use as a loop counter.
 302  * @n:          another &struct list_head to use as temporary storage
 303  * @head:       the head for your list.
 304  */
 305 #define list_for_each_safe(pos, n, head) \
 306         for (pos = (head)->next, n = pos->next; pos != (head); \
 307                 pos = n, n = pos->next)
 308
 309 /**
 310  * list_for_each_entry  -       iterate over list of given type
 311  * @pos:        the type * to use as a loop counter.
 312  * @head:       the head for your list.
 313  * @member:     the name of the list_struct within the struct.
 314  */
 315 #define list_for_each_entry(pos, head, member)                          \
 316         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 317                      prefetch(pos->member.next);                        \
 318              &pos->member != (head);                                    \
 319              pos = list_entry(pos->member.next, typeof(*pos), member),  \
 320                      prefetch(pos->member.next))
 321
 322 /**
 323  * list_for_each_entry_reverse - iterate backwards over list of given type.
 324  * @pos:        the type * to use as a loop counter.
 325  * @head:       the head for your list.
 326  * @member:     the name of the list_struct within the struct.
 327  */
 328 #define list_for_each_entry_reverse(pos, head, member)                  \
 329         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 330                      prefetch(pos->member.prev);                        \
 331              &pos->member != (head);                                    \
 332              pos = list_entry(pos->member.prev, typeof(*pos), member),  \
 333                      prefetch(pos->member.prev))
 334
 335 /**
 336  * list_for_each_entry_continue -       iterate over list of given type
 337  *                      continuing after existing point
 338  * @pos:        the type * to use as a loop counter.
 339  * @head:       the head for your list.
 340  * @member:     the name of the list_struct within the struct.
 341  */
 342 #define list_for_each_entry_continue(pos, head, member)                 \
 343         for (pos = list_entry(pos->member.next, typeof(*pos), member),  \
 344                      prefetch(pos->member.next);                        \
 345              &pos->member != (head);                                    \
 346              pos = list_entry(pos->member.next, typeof(*pos), member),  \
 347                      prefetch(pos->member.next))
 348
 349 /**
 350  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 351  * @pos:        the type * to use as a loop counter.
 352  * @n:          another type * to use as temporary storage
 353  * @head:       the head for your list.
 354  * @member:     the name of the list_struct within the struct.
 355  */
 356 #define list_for_each_entry_safe(pos, n, head, member)                  \
 357         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 358                 n = list_entry(pos->member.next, typeof(*pos), member); \
 359              &pos->member != (head);                                    \
 360              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 361
 362 /**
 363  * list_for_each_rcu    -       iterate over an rcu-protected list
 364  * @pos:        the &struct list_head to use as a loop counter.
 365  * @head:       the head for your list.
 366  */
 367 #define list_for_each_rcu(pos, head) \
 368         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
 369                 pos = pos->next, ({ smp_read_barrier_depends(); 0;}), prefetch(pos->next))
 370
 371 #define __list_for_each_rcu(pos, head) \
 372         for (pos = (head)->next; pos != (head); \
 373                 pos = pos->next, ({ smp_read_barrier_depends(); 0;}))
 374
 375 /**
 376  * list_for_each_safe_rcu       -       iterate over an rcu-protected list safe
 377  *                                      against removal of list entry
 378  * @pos:        the &struct list_head to use as a loop counter.
 379  * @n:          another &struct list_head to use as temporary storage
 380  * @head:       the head for your list.
 381  */
 382 #define list_for_each_safe_rcu(pos, n, head) \
 383         for (pos = (head)->next, n = pos->next; pos != (head); \
 384                 pos = n, ({ smp_read_barrier_depends(); 0;}), n = pos->next)
 385
 386 /**
 387  * list_for_each_entry_rcu      -       iterate over rcu list of given type
 388  * @pos:        the type * to use as a loop counter.
 389  * @head:       the head for your list.
 390  * @member:     the name of the list_struct within the struct.
 391  */
 392 #define list_for_each_entry_rcu(pos, head, member)                      \
 393         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 394                      prefetch(pos->member.next);                        \
 395              &pos->member != (head);                                    \
 396              pos = list_entry(pos->member.next, typeof(*pos), member),  \
 397                      ({ smp_read_barrier_depends(); 0;}),               \
 398                      prefetch(pos->member.next))
 399
 400
 401 /**
 402  * list_for_each_continue_rcu   -       iterate over an rcu-protected list
 403  *                      continuing after existing point.
 404  * @pos:        the &struct list_head to use as a loop counter.
 405  * @head:       the head for your list.
 406  */
 407 #define list_for_each_continue_rcu(pos, head) \
 408         for ((pos) = (pos)->next, prefetch((pos)->next); (pos) != (head); \
 409                 (pos) = (pos)->next, ({ smp_read_barrier_depends(); 0;}), prefetch((pos)->next))
 410
 411 /*
 412  * Double linked lists with a single pointer list head.
 413  * Mostly useful for hash tables where the two pointer list head is
 414  * too wasteful.
 415  * You lose the ability to access the tail in O(1).
 416  */
 417
 418 struct hlist_head {
 419         struct hlist_node *first;
 420 };
 421
 422 struct hlist_node {
 423         struct hlist_node *next, **pprev;
 424 };
 425
 426 #define HLIST_HEAD_INIT { .first = NULL }
 427 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 428 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 429 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
 430
 431 static __inline__ int hlist_unhashed(const struct hlist_node *h)
 432 {
 433         return !h->pprev;
 434 }
 435
 436 static __inline__ int hlist_empty(const struct hlist_head *h)
 437 {
 438         return !h->first;
 439 }
 440
 441 static __inline__ void __hlist_del(struct hlist_node *n)
 442 {
 443         struct hlist_node *next = n->next;
 444         struct hlist_node **pprev = n->pprev;
 445         *pprev = next;
 446         if (next)
 447                 next->pprev = pprev;
 448 }
 449
 450 static __inline__ void hlist_del(struct hlist_node *n)
 451 {
 452         __hlist_del(n);
 453         n->next = LIST_POISON1;
 454         n->pprev = LIST_POISON2;
 455 }
 456
 457 /**
 458  * hlist_del_rcu - deletes entry from hash list without re-initialization
 459  * @n: the element to delete from the hash list.
 460  *
 461  * Note: list_unhashed() on entry does not return true after this,
 462  * the entry is in an undefined state. It is useful for RCU based
 463  * lockfree traversal.
 464  *
 465  * In particular, it means that we can not poison the forward
 466  * pointers that may still be used for walking the hash list.
 467  */
 468 static inline void hlist_del_rcu(struct hlist_node *n)
 469 {
 470         __hlist_del(n);
 471         n->pprev = LIST_POISON2;
 472 }
 473
 474 static __inline__ void hlist_del_init(struct hlist_node *n)
 475 {
 476         if (n->pprev)  {
 477                 __hlist_del(n);
 478                 INIT_HLIST_NODE(n);
 479         }
 480 }
 481
 482 #define hlist_del_rcu_init hlist_del_init
 483
 484 static __inline__ void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 485 {
 486         struct hlist_node *first = h->first;
 487         n->next = first;
 488         if (first)
 489                 first->pprev = &n->next;
 490         h->first = n;
 491         n->pprev = &h->first;
 492 }
 493
 494 static __inline__ void hlist_add_head_rcu(struct hlist_node *n, struct hlist_head *h)
 495 {
 496         struct hlist_node *first = h->first;
 497         n->next = first;
 498         n->pprev = &h->first;
 499 #ifndef L4INPUT
 500         smp_wmb();
 501 #endif
 502         if (first)
 503                 first->pprev = &n->next;
 504         h->first = n;
 505 }
 506
 507 /* next must be != NULL */
 508 static __inline__ void hlist_add_before(struct hlist_node *n, struct hlist_node *next)
 509 {
 510         n->pprev = next->pprev;
 511         n->next = next;
 512         next->pprev = &n->next;
 513         *(n->pprev) = n;
 514 }
 515
 516 static __inline__ void hlist_add_after(struct hlist_node *n,
 517                                        struct hlist_node *next)
 518 {
 519         next->next      = n->next;
 520         *(next->pprev)  = n;
 521         n->next         = next;
 522 }
 523
 524 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 525
 526 /* Cannot easily do prefetch unfortunately */
 527 #define hlist_for_each(pos, head) \
 528         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
 529              pos = pos->next)
 530
 531 #define hlist_for_each_safe(pos, n, head) \
 532         for (pos = (head)->first; n = pos ? pos->next : 0, pos; \
 533              pos = n)
 534
 535 /**
 536  * hlist_for_each_entry - iterate over list of given type
 537  * @tpos:       the type * to use as a loop counter.
 538  * @pos:        the &struct hlist_node to use as a loop counter.
 539  * @head:       the head for your list.
 540  * @member:     the name of the hlist_node within the struct.
 541  */
 542 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 543         for (pos = (head)->first;                                        \
 544              pos && ({ prefetch(pos->next); 1;}) &&                      \
 545                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 546              pos = pos->next)
 547
 548 /**
 549  * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
 550  * @tpos:       the type * to use as a loop counter.
 551  * @pos:        the &struct hlist_node to use as a loop counter.
 552  * @member:     the name of the hlist_node within the struct.
 553  */
 554 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
 555         for (pos = (pos)->next;                                          \
 556              pos && ({ prefetch(pos->next); 1;}) &&                      \
 557                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 558              pos = pos->next)
 559
 560 /**
 561  * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
 562  * @tpos:       the type * to use as a loop counter.
 563  * @pos:        the &struct hlist_node to use as a loop counter.
 564  * @member:     the name of the hlist_node within the struct.
 565  */
 566 #define hlist_for_each_entry_from(tpos, pos, member)                     \
 567         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
 568                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 569              pos = pos->next)
 570
 571 /**
 572  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 573  * @tpos:       the type * to use as a loop counter.
 574  * @pos:        the &struct hlist_node to use as a loop counter.
 575  * @n:          another &struct hlist_node to use as temporary storage
 576  * @head:       the head for your list.
 577  * @member:     the name of the hlist_node within the struct.
 578  */
 579 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 580         for (pos = (head)->first;                                        \
 581              pos && ({ n = pos->next; 1; }) &&                           \
 582                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 583              pos = n)
 584 #else
 585 #warning "don't include kernel headers in userspace"
 586 #endif /* __KERNEL__ */
 587 #endif