wimlib.net Git - wimlib/blob - src/list.h

   1
   2 /*
   3  * This file is based on include/linux/list.h in the Linux kernel source code.
   4  */
   5
   6 #ifndef _LINUX_LIST_H
   7 #define _LINUX_LIST_H
   8
   9 #include <stddef.h>
  10
  11 /**
  12  * container_of - cast a member of a structure out to the containing structure
  13  * @ptr:        the pointer to the member.
  14  * @type:       the type of the container struct this is embedded in.
  15  * @member:     the name of the member within the struct.
  16  *
  17  */
  18 #define container_of(ptr, type, member) ({                      \
  19         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  20         (type *)( (char *)__mptr - offsetof(type,member) );})
  21
  22
  23 # define POISON_POINTER_DELTA 0
  24 /*
  25  * These are non-NULL pointers that will result in page faults
  26  * under normal circumstances, used to verify that nobody uses
  27  * non-initialized list entries.
  28  */
  29 #define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
  30 #define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)
  31 struct list_head {
  32         struct list_head *next, *prev;
  33 };
  34 struct hlist_head {
  35         struct hlist_node *first;
  36 };
  37
  38 struct hlist_node {
  39         struct hlist_node *next, **pprev;
  40 };
  41
  42 /*
  43  * Structure used to create a linked list of streams that share the same lookup
  44  * table entry.  This structure may be embedded in either a dentry (for the
  45  * un-named data stream) or an ads_entry (for an alternate data stream).  The
  46  * @type field indicates which of these structures the stream_list_head is
  47  * embedded in.
  48  */
  49 struct stream_list_head {
  50         struct list_head list;
  51         enum {
  52                 STREAM_TYPE_NORMAL = 0,
  53                 STREAM_TYPE_ADS,
  54         } type;
  55 };
  56
  57 /*
  58  * Simple doubly linked list implementation.
  59  *
  60  * Some of the internal functions ("__xxx") are useful when
  61  * manipulating whole lists rather than single entries, as
  62  * sometimes we already know the next/prev entries and we can
  63  * generate better code by using them directly rather than
  64  * using the generic single-entry routines.
  65  */
  66
  67 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  68
  69 #ifdef LIST_HEAD /* BSD sys/queue.h defines this... */
  70 #undef LIST_HEAD
  71 #endif
  72
  73 #define LIST_HEAD(name) \
  74         struct list_head name = LIST_HEAD_INIT(name)
  75
  76 static inline void INIT_LIST_HEAD(struct list_head *list)
  77 {
  78         list->next = list;
  79         list->prev = list;
  80 }
  81
  82 /*
  83  * Insert a new entry between two known consecutive entries.
  84  *
  85  * This is only for internal list manipulation where we know
  86  * the prev/next entries already!
  87  */
  88 #ifndef CONFIG_DEBUG_LIST
  89 static inline void __list_add(struct list_head *new,
  90                               struct list_head *prev,
  91                               struct list_head *next)
  92 {
  93         next->prev = new;
  94         new->next = next;
  95         new->prev = prev;
  96         prev->next = new;
  97 }
  98 #else
  99 extern void __list_add(struct list_head *new,
 100                               struct list_head *prev,
 101                               struct list_head *next);
 102 #endif
 103
 104 /**
 105  * list_add - add a new entry
 106  * @new: new entry to be added
 107  * @head: list head to add it after
 108  *
 109  * Insert a new entry after the specified head.
 110  * This is good for implementing stacks.
 111  */
 112 static inline void list_add(struct list_head *new, struct list_head *head)
 113 {
 114         __list_add(new, head, head->next);
 115 }
 116
 117
 118 /**
 119  * list_add_tail - add a new entry
 120  * @new: new entry to be added
 121  * @head: list head to add it before
 122  *
 123  * Insert a new entry before the specified head.
 124  * This is useful for implementing queues.
 125  */
 126 static inline void list_add_tail(struct list_head *new, struct list_head *head)
 127 {
 128         __list_add(new, head->prev, head);
 129 }
 130
 131 /*
 132  * Delete a list entry by making the prev/next entries
 133  * point to each other.
 134  *
 135  * This is only for internal list manipulation where we know
 136  * the prev/next entries already!
 137  */
 138 static inline void __list_del(struct list_head * prev, struct list_head * next)
 139 {
 140         next->prev = prev;
 141         prev->next = next;
 142 }
 143
 144 /**
 145  * list_del - deletes entry from list.
 146  * @entry: the element to delete from the list.
 147  * Note: list_empty() on entry does not return true after this, the entry is
 148  * in an undefined state.
 149  */
 150 #ifndef CONFIG_DEBUG_LIST
 151 static inline void __list_del_entry(struct list_head *entry)
 152 {
 153         __list_del(entry->prev, entry->next);
 154 }
 155
 156 static inline void list_del(struct list_head *entry)
 157 {
 158         __list_del(entry->prev, entry->next);
 159         entry->next = LIST_POISON1;
 160         entry->prev = LIST_POISON2;
 161 }
 162 #else
 163 extern void __list_del_entry(struct list_head *entry);
 164 extern void list_del(struct list_head *entry);
 165 #endif
 166
 167 /**
 168  * list_replace - replace old entry by new one
 169  * @old : the element to be replaced
 170  * @new : the new element to insert
 171  *
 172  * If @old was empty, it will be overwritten.
 173  */
 174 static inline void list_replace(struct list_head *old,
 175                                 struct list_head *new)
 176 {
 177         new->next = old->next;
 178         new->next->prev = new;
 179         new->prev = old->prev;
 180         new->prev->next = new;
 181 }
 182
 183 static inline void list_replace_init(struct list_head *old,
 184                                         struct list_head *new)
 185 {
 186         list_replace(old, new);
 187         INIT_LIST_HEAD(old);
 188 }
 189
 190 /**
 191  * list_del_init - deletes entry from list and reinitialize it.
 192  * @entry: the element to delete from the list.
 193  */
 194 static inline void list_del_init(struct list_head *entry)
 195 {
 196         __list_del_entry(entry);
 197         INIT_LIST_HEAD(entry);
 198 }
 199
 200 /**
 201  * list_move - delete from one list and add as another's head
 202  * @list: the entry to move
 203  * @head: the head that will precede our entry
 204  */
 205 static inline void list_move(struct list_head *list, struct list_head *head)
 206 {
 207         __list_del_entry(list);
 208         list_add(list, head);
 209 }
 210
 211 /**
 212  * list_move_tail - delete from one list and add as another's tail
 213  * @list: the entry to move
 214  * @head: the head that will follow our entry
 215  */
 216 static inline void list_move_tail(struct list_head *list,
 217                                   struct list_head *head)
 218 {
 219         __list_del_entry(list);
 220         list_add_tail(list, head);
 221 }
 222
 223 /**
 224  * list_is_last - tests whether @list is the last entry in list @head
 225  * @list: the entry to test
 226  * @head: the head of the list
 227  */
 228 static inline int list_is_last(const struct list_head *list,
 229                                 const struct list_head *head)
 230 {
 231         return list->next == head;
 232 }
 233
 234 /**
 235  * list_empty - tests whether a list is empty
 236  * @head: the list to test.
 237  */
 238 static inline int list_empty(const struct list_head *head)
 239 {
 240         return head->next == head;
 241 }
 242
 243 /**
 244  * list_empty_careful - tests whether a list is empty and not being modified
 245  * @head: the list to test
 246  *
 247  * Description:
 248  * tests whether a list is empty _and_ checks that no other CPU might be
 249  * in the process of modifying either member (next or prev)
 250  *
 251  * NOTE: using list_empty_careful() without synchronization
 252  * can only be safe if the only activity that can happen
 253  * to the list entry is list_del_init(). Eg. it cannot be used
 254  * if another CPU could re-list_add() it.
 255  */
 256 static inline int list_empty_careful(const struct list_head *head)
 257 {
 258         struct list_head *next = head->next;
 259         return (next == head) && (next == head->prev);
 260 }
 261
 262 /**
 263  * list_rotate_left - rotate the list to the left
 264  * @head: the head of the list
 265  */
 266 static inline void list_rotate_left(struct list_head *head)
 267 {
 268         struct list_head *first;
 269
 270         if (!list_empty(head)) {
 271                 first = head->next;
 272                 list_move_tail(first, head);
 273         }
 274 }
 275
 276 /**
 277  * list_is_singular - tests whether a list has just one entry.
 278  * @head: the list to test.
 279  */
 280 static inline int list_is_singular(const struct list_head *head)
 281 {
 282         return !list_empty(head) && (head->next == head->prev);
 283 }
 284
 285 static inline void __list_cut_position(struct list_head *list,
 286                 struct list_head *head, struct list_head *entry)
 287 {
 288         struct list_head *new_first = entry->next;
 289         list->next = head->next;
 290         list->next->prev = list;
 291         list->prev = entry;
 292         entry->next = list;
 293         head->next = new_first;
 294         new_first->prev = head;
 295 }
 296
 297 /**
 298  * list_cut_position - cut a list into two
 299  * @list: a new list to add all removed entries
 300  * @head: a list with entries
 301  * @entry: an entry within head, could be the head itself
 302  *      and if so we won't cut the list
 303  *
 304  * This helper moves the initial part of @head, up to and
 305  * including @entry, from @head to @list. You should
 306  * pass on @entry an element you know is on @head. @list
 307  * should be an empty list or a list you do not care about
 308  * losing its data.
 309  *
 310  */
 311 static inline void list_cut_position(struct list_head *list,
 312                 struct list_head *head, struct list_head *entry)
 313 {
 314         if (list_empty(head))
 315                 return;
 316         if (list_is_singular(head) &&
 317                 (head->next != entry && head != entry))
 318                 return;
 319         if (entry == head)
 320                 INIT_LIST_HEAD(list);
 321         else
 322                 __list_cut_position(list, head, entry);
 323 }
 324
 325 static inline void __list_splice(const struct list_head *list,
 326                                  struct list_head *prev,
 327                                  struct list_head *next)
 328 {
 329         struct list_head *first = list->next;
 330         struct list_head *last = list->prev;
 331
 332         first->prev = prev;
 333         prev->next = first;
 334
 335         last->next = next;
 336         next->prev = last;
 337 }
 338
 339 /**
 340  * list_splice - join two lists, this is designed for stacks
 341  * @list: the new list to add.
 342  * @head: the place to add it in the first list.
 343  */
 344 static inline void list_splice(const struct list_head *list,
 345                                 struct list_head *head)
 346 {
 347         if (!list_empty(list))
 348                 __list_splice(list, head, head->next);
 349 }
 350
 351 /**
 352  * list_splice_tail - join two lists, each list being a queue
 353  * @list: the new list to add.
 354  * @head: the place to add it in the first list.
 355  */
 356 static inline void list_splice_tail(struct list_head *list,
 357                                 struct list_head *head)
 358 {
 359         if (!list_empty(list))
 360                 __list_splice(list, head->prev, head);
 361 }
 362
 363 /**
 364  * list_splice_init - join two lists and reinitialise the emptied list.
 365  * @list: the new list to add.
 366  * @head: the place to add it in the first list.
 367  *
 368  * The list at @list is reinitialised
 369  */
 370 static inline void list_splice_init(struct list_head *list,
 371                                     struct list_head *head)
 372 {
 373         if (!list_empty(list)) {
 374                 __list_splice(list, head, head->next);
 375                 INIT_LIST_HEAD(list);
 376         }
 377 }
 378
 379 /**
 380  * list_splice_tail_init - join two lists and reinitialise the emptied list
 381  * @list: the new list to add.
 382  * @head: the place to add it in the first list.
 383  *
 384  * Each of the lists is a queue.
 385  * The list at @list is reinitialised
 386  */
 387 static inline void list_splice_tail_init(struct list_head *list,
 388                                          struct list_head *head)
 389 {
 390         if (!list_empty(list)) {
 391                 __list_splice(list, head->prev, head);
 392                 INIT_LIST_HEAD(list);
 393         }
 394 }
 395
 396 /**
 397  * list_entry - get the struct for this entry
 398  * @ptr:        the &struct list_head pointer.
 399  * @type:       the type of the struct this is embedded in.
 400  * @member:     the name of the list_struct within the struct.
 401  */
 402 #define list_entry(ptr, type, member) \
 403         container_of(ptr, type, member)
 404
 405 /**
 406  * list_first_entry - get the first element from a list
 407  * @ptr:        the list head to take the element from.
 408  * @type:       the type of the struct this is embedded in.
 409  * @member:     the name of the list_struct within the struct.
 410  *
 411  * Note, that list is expected to be not empty.
 412  */
 413 #define list_first_entry(ptr, type, member) \
 414         list_entry((ptr)->next, type, member)
 415
 416 /**
 417  * list_for_each        -       iterate over a list
 418  * @pos:        the &struct list_head to use as a loop cursor.
 419  * @head:       the head for your list.
 420  */
 421 #define list_for_each(pos, head) \
 422         for (pos = (head)->next; pos != (head); pos = pos->next)
 423
 424 /**
 425  * __list_for_each      -       iterate over a list
 426  * @pos:        the &struct list_head to use as a loop cursor.
 427  * @head:       the head for your list.
 428  *
 429  * This variant doesn't differ from list_for_each() any more.
 430  * We don't do prefetching in either case.
 431  */
 432 #define __list_for_each(pos, head) \
 433         for (pos = (head)->next; pos != (head); pos = pos->next)
 434
 435 /**
 436  * list_for_each_prev   -       iterate over a list backwards
 437  * @pos:        the &struct list_head to use as a loop cursor.
 438  * @head:       the head for your list.
 439  */
 440 #define list_for_each_prev(pos, head) \
 441         for (pos = (head)->prev; pos != (head); pos = pos->prev)
 442
 443 /**
 444  * list_for_each_safe - iterate over a list safe against removal of list entry
 445  * @pos:        the &struct list_head to use as a loop cursor.
 446  * @n:          another &struct list_head to use as temporary storage
 447  * @head:       the head for your list.
 448  */
 449 #define list_for_each_safe(pos, n, head) \
 450         for (pos = (head)->next, n = pos->next; pos != (head); \
 451                 pos = n, n = pos->next)
 452
 453 /**
 454  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
 455  * @pos:        the &struct list_head to use as a loop cursor.
 456  * @n:          another &struct list_head to use as temporary storage
 457  * @head:       the head for your list.
 458  */
 459 #define list_for_each_prev_safe(pos, n, head) \
 460         for (pos = (head)->prev, n = pos->prev; \
 461              pos != (head); \
 462              pos = n, n = pos->prev)
 463
 464 /**
 465  * list_for_each_entry  -       iterate over list of given type
 466  * @pos:        the type * to use as a loop cursor.
 467  * @head:       the head for your list.
 468  * @member:     the name of the list_struct within the struct.
 469  */
 470 #define list_for_each_entry(pos, head, member)                          \
 471         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 472              &pos->member != (head);    \
 473              pos = list_entry(pos->member.next, typeof(*pos), member))
 474
 475 /**
 476  * list_for_each_entry_reverse - iterate backwards over list of given type.
 477  * @pos:        the type * to use as a loop cursor.
 478  * @head:       the head for your list.
 479  * @member:     the name of the list_struct within the struct.
 480  */
 481 #define list_for_each_entry_reverse(pos, head, member)                  \
 482         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 483              &pos->member != (head);    \
 484              pos = list_entry(pos->member.prev, typeof(*pos), member))
 485
 486 /**
 487  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
 488  * @pos:        the type * to use as a start point
 489  * @head:       the head of the list
 490  * @member:     the name of the list_struct within the struct.
 491  *
 492  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
 493  */
 494 #define list_prepare_entry(pos, head, member) \
 495         ((pos) ? : list_entry(head, typeof(*pos), member))
 496
 497 /**
 498  * list_for_each_entry_continue - continue iteration over list of given type
 499  * @pos:        the type * to use as a loop cursor.
 500  * @head:       the head for your list.
 501  * @member:     the name of the list_struct within the struct.
 502  *
 503  * Continue to iterate over list of given type, continuing after
 504  * the current position.
 505  */
 506 #define list_for_each_entry_continue(pos, head, member)                 \
 507         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 508              &pos->member != (head);    \
 509              pos = list_entry(pos->member.next, typeof(*pos), member))
 510
 511 /**
 512  * list_for_each_entry_continue_reverse - iterate backwards from the given point
 513  * @pos:        the type * to use as a loop cursor.
 514  * @head:       the head for your list.
 515  * @member:     the name of the list_struct within the struct.
 516  *
 517  * Start to iterate over list of given type backwards, continuing after
 518  * the current position.
 519  */
 520 #define list_for_each_entry_continue_reverse(pos, head, member)         \
 521         for (pos = list_entry(pos->member.prev, typeof(*pos), member);  \
 522              &pos->member != (head);    \
 523              pos = list_entry(pos->member.prev, typeof(*pos), member))
 524
 525 /**
 526  * list_for_each_entry_from - iterate over list of given type from the current point
 527  * @pos:        the type * to use as a loop cursor.
 528  * @head:       the head for your list.
 529  * @member:     the name of the list_struct within the struct.
 530  *
 531  * Iterate over list of given type, continuing from current position.
 532  */
 533 #define list_for_each_entry_from(pos, head, member)                     \
 534         for (; &pos->member != (head);  \
 535              pos = list_entry(pos->member.next, typeof(*pos), member))
 536
 537 /**
 538  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 539  * @pos:        the type * to use as a loop cursor.
 540  * @n:          another type * to use as temporary storage
 541  * @head:       the head for your list.
 542  * @member:     the name of the list_struct within the struct.
 543  */
 544 #define list_for_each_entry_safe(pos, n, head, member)                  \
 545         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 546                 n = list_entry(pos->member.next, typeof(*pos), member); \
 547              &pos->member != (head);                                    \
 548              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 549
 550 /**
 551  * list_for_each_entry_safe_continue - continue list iteration safe against removal
 552  * @pos:        the type * to use as a loop cursor.
 553  * @n:          another type * to use as temporary storage
 554  * @head:       the head for your list.
 555  * @member:     the name of the list_struct within the struct.
 556  *
 557  * Iterate over list of given type, continuing after current point,
 558  * safe against removal of list entry.
 559  */
 560 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
 561         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
 562                 n = list_entry(pos->member.next, typeof(*pos), member);         \
 563              &pos->member != (head);                                            \
 564              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 565
 566 /**
 567  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
 568  * @pos:        the type * to use as a loop cursor.
 569  * @n:          another type * to use as temporary storage
 570  * @head:       the head for your list.
 571  * @member:     the name of the list_struct within the struct.
 572  *
 573  * Iterate over list of given type from current point, safe against
 574  * removal of list entry.
 575  */
 576 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 577         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
 578              &pos->member != (head);                                            \
 579              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 580
 581 /**
 582  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
 583  * @pos:        the type * to use as a loop cursor.
 584  * @n:          another type * to use as temporary storage
 585  * @head:       the head for your list.
 586  * @member:     the name of the list_struct within the struct.
 587  *
 588  * Iterate backwards over list of given type, safe against removal
 589  * of list entry.
 590  */
 591 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 592         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 593                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 594              &pos->member != (head);                                    \
 595              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 596
 597 /**
 598  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
 599  * @pos:        the loop cursor used in the list_for_each_entry_safe loop
 600  * @n:          temporary storage used in list_for_each_entry_safe
 601  * @member:     the name of the list_struct within the struct.
 602  *
 603  * list_safe_reset_next is not safe to use in general if the list may be
 604  * modified concurrently (eg. the lock is dropped in the loop body). An
 605  * exception to this is if the cursor element (pos) is pinned in the list,
 606  * and list_safe_reset_next is called after re-taking the lock and before
 607  * completing the current iteration of the loop body.
 608  */
 609 #define list_safe_reset_next(pos, n, member)                            \
 610         n = list_entry(pos->member.next, typeof(*pos), member)
 611
 612 /*
 613  * Double linked lists with a single pointer list head.
 614  * Mostly useful for hash tables where the two pointer list head is
 615  * too wasteful.
 616  * You lose the ability to access the tail in O(1).
 617  */
 618
 619 #define HLIST_HEAD_INIT { .first = NULL }
 620 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 621 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 622 static inline void INIT_HLIST_NODE(struct hlist_node *h)
 623 {
 624         h->next = NULL;
 625         h->pprev = NULL;
 626 }
 627
 628 static inline int hlist_unhashed(const struct hlist_node *h)
 629 {
 630         return !h->pprev;
 631 }
 632
 633 static inline int hlist_empty(const struct hlist_head *h)
 634 {
 635         return !h->first;
 636 }
 637
 638 static inline void __hlist_del(struct hlist_node *n)
 639 {
 640         struct hlist_node *next = n->next;
 641         struct hlist_node **pprev = n->pprev;
 642         *pprev = next;
 643         if (next)
 644                 next->pprev = pprev;
 645 }
 646
 647 static inline void hlist_del(struct hlist_node *n)
 648 {
 649         __hlist_del(n);
 650         n->next = LIST_POISON1;
 651         n->pprev = LIST_POISON2;
 652 }
 653
 654 static inline void hlist_del_init(struct hlist_node *n)
 655 {
 656         if (!hlist_unhashed(n)) {
 657                 __hlist_del(n);
 658                 INIT_HLIST_NODE(n);
 659         }
 660 }
 661
 662 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 663 {
 664         struct hlist_node *first = h->first;
 665         n->next = first;
 666         if (first)
 667                 first->pprev = &n->next;
 668         h->first = n;
 669         n->pprev = &h->first;
 670 }
 671
 672 /* next must be != NULL */
 673 static inline void hlist_add_before(struct hlist_node *n,
 674                                         struct hlist_node *next)
 675 {
 676         n->pprev = next->pprev;
 677         n->next = next;
 678         next->pprev = &n->next;
 679         *(n->pprev) = n;
 680 }
 681
 682 static inline void hlist_add_after(struct hlist_node *n,
 683                                         struct hlist_node *next)
 684 {
 685         next->next = n->next;
 686         n->next = next;
 687         next->pprev = &n->next;
 688
 689         if(next->next)
 690                 next->next->pprev  = &next->next;
 691 }
 692
 693 /* after that we'll appear to be on some hlist and hlist_del will work */
 694 static inline void hlist_add_fake(struct hlist_node *n)
 695 {
 696         n->pprev = &n->next;
 697 }
 698
 699 /*
 700  * Move a list from one list head to another. Fixup the pprev
 701  * reference of the first entry if it exists.
 702  */
 703 static inline void hlist_move_list(struct hlist_head *old,
 704                                    struct hlist_head *new)
 705 {
 706         new->first = old->first;
 707         if (new->first)
 708                 new->first->pprev = &new->first;
 709         old->first = NULL;
 710 }
 711
 712 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 713
 714 #define hlist_for_each(pos, head) \
 715         for (pos = (head)->first; pos ; pos = pos->next)
 716
 717 #define hlist_for_each_safe(pos, n, head) \
 718         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 719              pos = n)
 720
 721 /**
 722  * hlist_for_each_entry - iterate over list of given type
 723  * @tpos:       the type * to use as a loop cursor.
 724  * @pos:        the &struct hlist_node to use as a loop cursor.
 725  * @head:       the head for your list.
 726  * @member:     the name of the hlist_node within the struct.
 727  */
 728 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 729         for (pos = (head)->first;                                        \
 730              pos &&                                                      \
 731                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 732              pos = pos->next)
 733
 734 /**
 735  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
 736  * @tpos:       the type * to use as a loop cursor.
 737  * @pos:        the &struct hlist_node to use as a loop cursor.
 738  * @member:     the name of the hlist_node within the struct.
 739  */
 740 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
 741         for (pos = (pos)->next;                                          \
 742              pos &&                                                      \
 743                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 744              pos = pos->next)
 745
 746 /**
 747  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
 748  * @tpos:       the type * to use as a loop cursor.
 749  * @pos:        the &struct hlist_node to use as a loop cursor.
 750  * @member:     the name of the hlist_node within the struct.
 751  */
 752 #define hlist_for_each_entry_from(tpos, pos, member)                     \
 753         for (; pos &&                                                    \
 754                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 755              pos = pos->next)
 756
 757 /**
 758  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 759  * @tpos:       the type * to use as a loop cursor.
 760  * @pos:        the &struct hlist_node to use as a loop cursor.
 761  * @n:          another &struct hlist_node to use as temporary storage
 762  * @head:       the head for your list.
 763  * @member:     the name of the hlist_node within the struct.
 764  */
 765 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 766         for (pos = (head)->first;                                        \
 767              pos && ({ n = pos->next; 1; }) &&                           \
 768                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 769              pos = n)
 770
 771 #endif