git.gag.com Git - fw/openocd/blob - src/helper/list.h

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2
   3 /*
   4  * The content of this file is mainly copied/inspired from Linux kernel
   5  * code in include/linux/list.h, include/linux/types.h
   6  * Last aligned with kernel v5.12:
   7  * - skip the functions hlist_unhashed_lockless() and __list_del_clearprev()
   8  *   that are relevant only in kernel;
   9  * - Remove non-standard GCC extension "omitted conditional operand" from
  10  *   list_prepare_entry;
  11  * - expand READ_ONCE, WRITE_ONCE, smp_load_acquire, smp_store_release;
  12  * - make comments compatible with doxygen.
  13  */
  14
  15 #ifndef OPENOCD_HELPER_LIST_H
  16 #define OPENOCD_HELPER_LIST_H
  17
  18 /* begin local changes */
  19 #include <helper/types.h>
  20
  21 #define LIST_POISON1 NULL
  22 #define LIST_POISON2 NULL
  23
  24 struct list_head {
  25         struct list_head *next, *prev;
  26 };
  27
  28 struct hlist_head {
  29         struct hlist_node *first;
  30 };
  31
  32 struct hlist_node {
  33         struct hlist_node *next, **pprev;
  34 };
  35 /* end local changes */
  36
  37 /*
  38  * Circular doubly linked list implementation.
  39  *
  40  * Some of the internal functions ("__xxx") are useful when
  41  * manipulating whole lists rather than single entries, as
  42  * sometimes we already know the next/prev entries and we can
  43  * generate better code by using them directly rather than
  44  * using the generic single-entry routines.
  45  */
  46
  47 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  48
  49 #define LIST_HEAD(name) \
  50         struct list_head name = LIST_HEAD_INIT(name)
  51
  52 /**
  53  * INIT_LIST_HEAD - Initialize a list_head structure
  54  * @param list list_head structure to be initialized.
  55  *
  56  * Initializes the list_head to point to itself.  If it is a list header,
  57  * the result is an empty list.
  58  */
  59 static inline void INIT_LIST_HEAD(struct list_head *list)
  60 {
  61         list->next = list;
  62         list->prev = list;
  63 }
  64
  65 #ifdef CONFIG_DEBUG_LIST
  66 extern bool __list_add_valid(struct list_head *new,
  67                               struct list_head *prev,
  68                               struct list_head *next);
  69 extern bool __list_del_entry_valid(struct list_head *entry);
  70 #else
  71 static inline bool __list_add_valid(struct list_head *new,
  72                                 struct list_head *prev,
  73                                 struct list_head *next)
  74 {
  75         return true;
  76 }
  77 static inline bool __list_del_entry_valid(struct list_head *entry)
  78 {
  79         return true;
  80 }
  81 #endif
  82
  83 /*
  84  * Insert a new entry between two known consecutive entries.
  85  *
  86  * This is only for internal list manipulation where we know
  87  * the prev/next entries already!
  88  */
  89 static inline void __list_add(struct list_head *new,
  90                               struct list_head *prev,
  91                               struct list_head *next)
  92 {
  93         if (!__list_add_valid(new, prev, next))
  94                 return;
  95
  96         next->prev = new;
  97         new->next = next;
  98         new->prev = prev;
  99         prev->next = new;
 100 }
 101
 102 /**
 103  * list_add - add a new entry
 104  * @param new new entry to be added
 105  * @param head list head to add it after
 106  *
 107  * Insert a new entry after the specified head.
 108  * This is good for implementing stacks.
 109  */
 110 static inline void list_add(struct list_head *new, struct list_head *head)
 111 {
 112         __list_add(new, head, head->next);
 113 }
 114
 115
 116 /**
 117  * list_add_tail - add a new entry
 118  * @param new new entry to be added
 119  * @param head list head to add it before
 120  *
 121  * Insert a new entry before the specified head.
 122  * This is useful for implementing queues.
 123  */
 124 static inline void list_add_tail(struct list_head *new, struct list_head *head)
 125 {
 126         __list_add(new, head->prev, head);
 127 }
 128
 129 /*
 130  * Delete a list entry by making the prev/next entries
 131  * point to each other.
 132  *
 133  * This is only for internal list manipulation where we know
 134  * the prev/next entries already!
 135  */
 136 static inline void __list_del(struct list_head *prev, struct list_head *next)
 137 {
 138         next->prev = prev;
 139         prev->next = next;
 140 }
 141
 142 /* Ignore kernel __list_del_clearprev() */
 143
 144 static inline void __list_del_entry(struct list_head *entry)
 145 {
 146         if (!__list_del_entry_valid(entry))
 147                 return;
 148
 149         __list_del(entry->prev, entry->next);
 150 }
 151
 152 /**
 153  * list_del - deletes entry from list.
 154  * @param entry the element to delete from the list.
 155  * Note: list_empty() on entry does not return true after this, the entry is
 156  * in an undefined state.
 157  */
 158 static inline void list_del(struct list_head *entry)
 159 {
 160         __list_del_entry(entry);
 161         entry->next = LIST_POISON1;
 162         entry->prev = LIST_POISON2;
 163 }
 164
 165 /**
 166  * list_replace - replace old entry by new one
 167  * @param old the element to be replaced
 168  * @param new the new element to insert
 169  *
 170  * If @a old was empty, it will be overwritten.
 171  */
 172 static inline void list_replace(struct list_head *old,
 173                                 struct list_head *new)
 174 {
 175         new->next = old->next;
 176         new->next->prev = new;
 177         new->prev = old->prev;
 178         new->prev->next = new;
 179 }
 180
 181 /**
 182  * list_replace_init - replace old entry by new one and initialize the old one
 183  * @param old the element to be replaced
 184  * @param new the new element to insert
 185  *
 186  * If @a old was empty, it will be overwritten.
 187  */
 188 static inline void list_replace_init(struct list_head *old,
 189                                      struct list_head *new)
 190 {
 191         list_replace(old, new);
 192         INIT_LIST_HEAD(old);
 193 }
 194
 195 /**
 196  * list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
 197  * @param entry1 the location to place entry2
 198  * @param entry2 the location to place entry1
 199  */
 200 static inline void list_swap(struct list_head *entry1,
 201                              struct list_head *entry2)
 202 {
 203         struct list_head *pos = entry2->prev;
 204
 205         list_del(entry2);
 206         list_replace(entry1, entry2);
 207         if (pos == entry1)
 208                 pos = entry2;
 209         list_add(entry1, pos);
 210 }
 211
 212 /**
 213  * list_del_init - deletes entry from list and reinitialize it.
 214  * @param entry the element to delete from the list.
 215  */
 216 static inline void list_del_init(struct list_head *entry)
 217 {
 218         __list_del_entry(entry);
 219         INIT_LIST_HEAD(entry);
 220 }
 221
 222 /**
 223  * list_move - delete from one list and add as another's head
 224  * @param list the entry to move
 225  * @param head the head that will precede our entry
 226  */
 227 static inline void list_move(struct list_head *list, struct list_head *head)
 228 {
 229         __list_del_entry(list);
 230         list_add(list, head);
 231 }
 232
 233 /**
 234  * list_move_tail - delete from one list and add as another's tail
 235  * @param list the entry to move
 236  * @param head the head that will follow our entry
 237  */
 238 static inline void list_move_tail(struct list_head *list,
 239                                   struct list_head *head)
 240 {
 241         __list_del_entry(list);
 242         list_add_tail(list, head);
 243 }
 244
 245 /**
 246  * list_bulk_move_tail - move a subsection of a list to its tail
 247  * @param head  the head that will follow our entry
 248  * @param first the first entry to move
 249  * @param last  the last entry to move, can be the same as first
 250  *
 251  * Move all entries between @a first and including @a last before @a head.
 252  * All three entries must belong to the same linked list.
 253  */
 254 static inline void list_bulk_move_tail(struct list_head *head,
 255                                        struct list_head *first,
 256                                        struct list_head *last)
 257 {
 258         first->prev->next = last->next;
 259         last->next->prev = first->prev;
 260
 261         head->prev->next = first;
 262         first->prev = head->prev;
 263
 264         last->next = head;
 265         head->prev = last;
 266 }
 267
 268 /**
 269  * list_is_first -- tests whether @a list is the first entry in list @a head
 270  * @param list the entry to test
 271  * @param head the head of the list
 272  */
 273 static inline int list_is_first(const struct list_head *list,
 274                                         const struct list_head *head)
 275 {
 276         return list->prev == head;
 277 }
 278
 279 /**
 280  * list_is_last - tests whether @a list is the last entry in list @a head
 281  * @param list the entry to test
 282  * @param head the head of the list
 283  */
 284 static inline int list_is_last(const struct list_head *list,
 285                                 const struct list_head *head)
 286 {
 287         return list->next == head;
 288 }
 289
 290 /**
 291  * list_empty - tests whether a list is empty
 292  * @param head the list to test.
 293  */
 294 static inline int list_empty(const struct list_head *head)
 295 {
 296         return head->next == head;
 297 }
 298
 299 /**
 300  * list_del_init_careful - deletes entry from list and reinitialize it.
 301  * @param entry the element to delete from the list.
 302  *
 303  * This is the same as list_del_init(), except designed to be used
 304  * together with list_empty_careful() in a way to guarantee ordering
 305  * of other memory operations.
 306  *
 307  * Any memory operations done before a list_del_init_careful() are
 308  * guaranteed to be visible after a list_empty_careful() test.
 309  */
 310 static inline void list_del_init_careful(struct list_head *entry)
 311 {
 312         __list_del_entry(entry);
 313         entry->prev = entry;
 314         entry->next = entry;
 315 }
 316
 317 /**
 318  * list_empty_careful - tests whether a list is empty and not being modified
 319  * @param head the list to test
 320  *
 321  * Description:
 322  * tests whether a list is empty _and_ checks that no other CPU might be
 323  * in the process of modifying either member (next or prev)
 324  *
 325  * NOTE: using list_empty_careful() without synchronization
 326  * can only be safe if the only activity that can happen
 327  * to the list entry is list_del_init(). Eg. it cannot be used
 328  * if another CPU could re-list_add() it.
 329  */
 330 static inline int list_empty_careful(const struct list_head *head)
 331 {
 332         struct list_head *next = head->next;
 333         return (next == head) && (next == head->prev);
 334 }
 335
 336 /**
 337  * list_rotate_left - rotate the list to the left
 338  * @param head the head of the list
 339  */
 340 static inline void list_rotate_left(struct list_head *head)
 341 {
 342         struct list_head *first;
 343
 344         if (!list_empty(head)) {
 345                 first = head->next;
 346                 list_move_tail(first, head);
 347         }
 348 }
 349
 350 /**
 351  * list_rotate_to_front() - Rotate list to specific item.
 352  * @param list The desired new front of the list.
 353  * @param head The head of the list.
 354  *
 355  * Rotates list so that @a list becomes the new front of the list.
 356  */
 357 static inline void list_rotate_to_front(struct list_head *list,
 358                                         struct list_head *head)
 359 {
 360         /*
 361          * Deletes the list head from the list denoted by @a head and
 362          * places it as the tail of @a list, this effectively rotates the
 363          * list so that @a list is at the front.
 364          */
 365         list_move_tail(head, list);
 366 }
 367
 368 /**
 369  * list_is_singular - tests whether a list has just one entry.
 370  * @param head the list to test.
 371  */
 372 static inline int list_is_singular(const struct list_head *head)
 373 {
 374         return !list_empty(head) && (head->next == head->prev);
 375 }
 376
 377 static inline void __list_cut_position(struct list_head *list,
 378                 struct list_head *head, struct list_head *entry)
 379 {
 380         struct list_head *new_first = entry->next;
 381         list->next = head->next;
 382         list->next->prev = list;
 383         list->prev = entry;
 384         entry->next = list;
 385         head->next = new_first;
 386         new_first->prev = head;
 387 }
 388
 389 /**
 390  * list_cut_position - cut a list into two
 391  * @param list a new list to add all removed entries
 392  * @param head a list with entries
 393  * @param entry an entry within head, could be the head itself
 394  *      and if so we won't cut the list
 395  *
 396  * This helper moves the initial part of @a head, up to and
 397  * including @a entry, from @a head to @a list. You should
 398  * pass on @a entry an element you know is on @a head. @a list
 399  * should be an empty list or a list you do not care about
 400  * losing its data.
 401  *
 402  */
 403 static inline void list_cut_position(struct list_head *list,
 404                 struct list_head *head, struct list_head *entry)
 405 {
 406         if (list_empty(head))
 407                 return;
 408         if (list_is_singular(head) &&
 409                 (head->next != entry && head != entry))
 410                 return;
 411         if (entry == head)
 412                 INIT_LIST_HEAD(list);
 413         else
 414                 __list_cut_position(list, head, entry);
 415 }
 416
 417 /**
 418  * list_cut_before - cut a list into two, before given entry
 419  * @param list  a new list to add all removed entries
 420  * @param head  a list with entries
 421  * @param entry an entry within head, could be the head itself
 422  *
 423  * This helper moves the initial part of @a head, up to but
 424  * excluding @a entry, from @a head to @a list.  You should pass
 425  * in @a entry an element you know is on @a head.  @a list should
 426  * be an empty list or a list you do not care about losing
 427  * its data.
 428  * If @a entry == @a head, all entries on @a head are moved to
 429  * @a list.
 430  */
 431 static inline void list_cut_before(struct list_head *list,
 432                                    struct list_head *head,
 433                                    struct list_head *entry)
 434 {
 435         if (head->next == entry) {
 436                 INIT_LIST_HEAD(list);
 437                 return;
 438         }
 439         list->next = head->next;
 440         list->next->prev = list;
 441         list->prev = entry->prev;
 442         list->prev->next = list;
 443         head->next = entry;
 444         entry->prev = head;
 445 }
 446
 447 static inline void __list_splice(const struct list_head *list,
 448                                  struct list_head *prev,
 449                                  struct list_head *next)
 450 {
 451         struct list_head *first = list->next;
 452         struct list_head *last = list->prev;
 453
 454         first->prev = prev;
 455         prev->next = first;
 456
 457         last->next = next;
 458         next->prev = last;
 459 }
 460
 461 /**
 462  * list_splice - join two lists, this is designed for stacks
 463  * @param list the new list to add.
 464  * @param head the place to add it in the first list.
 465  */
 466 static inline void list_splice(const struct list_head *list,
 467                                 struct list_head *head)
 468 {
 469         if (!list_empty(list))
 470                 __list_splice(list, head, head->next);
 471 }
 472
 473 /**
 474  * list_splice_tail - join two lists, each list being a queue
 475  * @param list the new list to add.
 476  * @param head the place to add it in the first list.
 477  */
 478 static inline void list_splice_tail(struct list_head *list,
 479                                 struct list_head *head)
 480 {
 481         if (!list_empty(list))
 482                 __list_splice(list, head->prev, head);
 483 }
 484
 485 /**
 486  * list_splice_init - join two lists and reinitialise the emptied list.
 487  * @param list the new list to add.
 488  * @param head the place to add it in the first list.
 489  *
 490  * The list at @a list is reinitialised
 491  */
 492 static inline void list_splice_init(struct list_head *list,
 493                                     struct list_head *head)
 494 {
 495         if (!list_empty(list)) {
 496                 __list_splice(list, head, head->next);
 497                 INIT_LIST_HEAD(list);
 498         }
 499 }
 500
 501 /**
 502  * list_splice_tail_init - join two lists and reinitialise the emptied list
 503  * @param list the new list to add.
 504  * @param head the place to add it in the first list.
 505  *
 506  * Each of the lists is a queue.
 507  * The list at @a list is reinitialised
 508  */
 509 static inline void list_splice_tail_init(struct list_head *list,
 510                                          struct list_head *head)
 511 {
 512         if (!list_empty(list)) {
 513                 __list_splice(list, head->prev, head);
 514                 INIT_LIST_HEAD(list);
 515         }
 516 }
 517
 518 /**
 519  * list_entry - get the struct for this entry
 520  * @param ptr    the &struct list_head pointer.
 521  * @param type   the type of the struct this is embedded in.
 522  * @param member the name of the list_head within the struct.
 523  */
 524 #define list_entry(ptr, type, member) \
 525         container_of(ptr, type, member)
 526
 527 /**
 528  * list_first_entry - get the first element from a list
 529  * @param ptr    the list head to take the element from.
 530  * @param type   the type of the struct this is embedded in.
 531  * @param member the name of the list_head within the struct.
 532  *
 533  * Note, that list is expected to be not empty.
 534  */
 535 #define list_first_entry(ptr, type, member) \
 536         list_entry((ptr)->next, type, member)
 537
 538 /**
 539  * list_last_entry - get the last element from a list
 540  * @param ptr    the list head to take the element from.
 541  * @param type   the type of the struct this is embedded in.
 542  * @param member the name of the list_head within the struct.
 543  *
 544  * Note, that list is expected to be not empty.
 545  */
 546 #define list_last_entry(ptr, type, member) \
 547         list_entry((ptr)->prev, type, member)
 548
 549 /**
 550  * list_first_entry_or_null - get the first element from a list
 551  * @param ptr    the list head to take the element from.
 552  * @param type   the type of the struct this is embedded in.
 553  * @param member the name of the list_head within the struct.
 554  *
 555  * Note that if the list is empty, it returns NULL.
 556  */
 557 #define list_first_entry_or_null(ptr, type, member) ({ \
 558         struct list_head *head__ = (ptr); \
 559         struct list_head *pos__ = head__->next; \
 560         pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
 561 })
 562
 563 /**
 564  * list_next_entry - get the next element in list
 565  * @param pos    the type * to cursor
 566  * @param member the name of the list_head within the struct.
 567  */
 568 #define list_next_entry(pos, member) \
 569         list_entry((pos)->member.next, typeof(*(pos)), member)
 570
 571 /**
 572  * list_prev_entry - get the prev element in list
 573  * @param pos    the type * to cursor
 574  * @param member the name of the list_head within the struct.
 575  */
 576 #define list_prev_entry(pos, member) \
 577         list_entry((pos)->member.prev, typeof(*(pos)), member)
 578
 579 /**
 580  * list_for_each        -       iterate over a list
 581  * @param pos  the &struct list_head to use as a loop cursor.
 582  * @param head the head for your list.
 583  */
 584 #define list_for_each(pos, head) \
 585         for (pos = (head)->next; pos != (head); pos = pos->next)
 586
 587 /**
 588  * list_for_each_continue - continue iteration over a list
 589  * @param pos  the &struct list_head to use as a loop cursor.
 590  * @param head the head for your list.
 591  *
 592  * Continue to iterate over a list, continuing after the current position.
 593  */
 594 #define list_for_each_continue(pos, head) \
 595         for (pos = pos->next; pos != (head); pos = pos->next)
 596
 597 /**
 598  * list_for_each_prev   -       iterate over a list backwards
 599  * @param pos  the &struct list_head to use as a loop cursor.
 600  * @param head the head for your list.
 601  */
 602 #define list_for_each_prev(pos, head) \
 603         for (pos = (head)->prev; pos != (head); pos = pos->prev)
 604
 605 /**
 606  * list_for_each_safe - iterate over a list safe against removal of list entry
 607  * @param pos  the &struct list_head to use as a loop cursor.
 608  * @param n    another &struct list_head to use as temporary storage
 609  * @param head the head for your list.
 610  */
 611 #define list_for_each_safe(pos, n, head) \
 612         for (pos = (head)->next, n = pos->next; pos != (head); \
 613                 pos = n, n = pos->next)
 614
 615 /**
 616  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
 617  * @param pos  the &struct list_head to use as a loop cursor.
 618  * @param n    another &struct list_head to use as temporary storage
 619  * @param head the head for your list.
 620  */
 621 #define list_for_each_prev_safe(pos, n, head) \
 622         for (pos = (head)->prev, n = pos->prev; \
 623              pos != (head); \
 624              pos = n, n = pos->prev)
 625
 626 /**
 627  * list_entry_is_head - test if the entry points to the head of the list
 628  * @param pos    the type * to cursor
 629  * @param head   the head for your list.
 630  * @param member the name of the list_head within the struct.
 631  */
 632 #define list_entry_is_head(pos, head, member)                           \
 633         (&pos->member == (head))
 634
 635 /**
 636  * list_for_each_entry  -       iterate over list of given type
 637  * @param pos    the type * to use as a loop cursor.
 638  * @param head   the head for your list.
 639  * @param member the name of the list_head within the struct.
 640  */
 641 #define list_for_each_entry(pos, head, member)                          \
 642         for (pos = list_first_entry(head, typeof(*pos), member);        \
 643              !list_entry_is_head(pos, head, member);                    \
 644              pos = list_next_entry(pos, member))
 645
 646 /**
 647  * list_for_each_entry_reverse - iterate backwards over list of given type.
 648  * @param pos    the type * to use as a loop cursor.
 649  * @param head   the head for your list.
 650  * @param member the name of the list_head within the struct.
 651  */
 652 #define list_for_each_entry_reverse(pos, head, member)                  \
 653         for (pos = list_last_entry(head, typeof(*pos), member);         \
 654              !list_entry_is_head(pos, head, member);                    \
 655              pos = list_prev_entry(pos, member))
 656
 657 /**
 658  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
 659  * @param pos    the type * to use as a start point
 660  * @param head   the head of the list
 661  * @param member the name of the list_head within the struct.
 662  *
 663  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
 664  */
 665 #define list_prepare_entry(pos, head, member) \
 666         ((pos) ? (pos) : list_entry(head, typeof(*pos), member))
 667
 668 /**
 669  * list_for_each_entry_continue - continue iteration over list of given type
 670  * @param pos    the type * to use as a loop cursor.
 671  * @param head   the head for your list.
 672  * @param member the name of the list_head within the struct.
 673  *
 674  * Continue to iterate over list of given type, continuing after
 675  * the current position.
 676  */
 677 #define list_for_each_entry_continue(pos, head, member)         \
 678         for (pos = list_next_entry(pos, member);                        \
 679              !list_entry_is_head(pos, head, member);                    \
 680              pos = list_next_entry(pos, member))
 681
 682 /**
 683  * list_for_each_entry_continue_reverse - iterate backwards from the given point
 684  * @param pos    the type * to use as a loop cursor.
 685  * @param head   the head for your list.
 686  * @param member the name of the list_head within the struct.
 687  *
 688  * Start to iterate over list of given type backwards, continuing after
 689  * the current position.
 690  */
 691 #define list_for_each_entry_continue_reverse(pos, head, member)         \
 692         for (pos = list_prev_entry(pos, member);                        \
 693              !list_entry_is_head(pos, head, member);                    \
 694              pos = list_prev_entry(pos, member))
 695
 696 /**
 697  * list_for_each_entry_from - iterate over list of given type from the current point
 698  * @param pos    the type * to use as a loop cursor.
 699  * @param head   the head for your list.
 700  * @param member the name of the list_head within the struct.
 701  *
 702  * Iterate over list of given type, continuing from current position.
 703  */
 704 #define list_for_each_entry_from(pos, head, member)                     \
 705         for (; !list_entry_is_head(pos, head, member);                  \
 706              pos = list_next_entry(pos, member))
 707
 708 /**
 709  * list_for_each_entry_from_reverse - iterate backwards over list of given type
 710  *                                    from the current point
 711  * @param pos    the type * to use as a loop cursor.
 712  * @param head   the head for your list.
 713  * @param member the name of the list_head within the struct.
 714  *
 715  * Iterate backwards over list of given type, continuing from current position.
 716  */
 717 #define list_for_each_entry_from_reverse(pos, head, member)             \
 718         for (; !list_entry_is_head(pos, head, member);                  \
 719              pos = list_prev_entry(pos, member))
 720
 721 /**
 722  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 723  * @param pos    the type * to use as a loop cursor.
 724  * @param n      another type * to use as temporary storage
 725  * @param head   the head for your list.
 726  * @param member the name of the list_head within the struct.
 727  */
 728 #define list_for_each_entry_safe(pos, n, head, member)                  \
 729         for (pos = list_first_entry(head, typeof(*pos), member),        \
 730                 n = list_next_entry(pos, member);                       \
 731              !list_entry_is_head(pos, head, member);                    \
 732              pos = n, n = list_next_entry(n, member))
 733
 734 /**
 735  * list_for_each_entry_safe_continue - continue list iteration safe against removal
 736  * @param pos    the type * to use as a loop cursor.
 737  * @param n      another type * to use as temporary storage
 738  * @param head   the head for your list.
 739  * @param member the name of the list_head within the struct.
 740  *
 741  * Iterate over list of given type, continuing after current point,
 742  * safe against removal of list entry.
 743  */
 744 #define list_for_each_entry_safe_continue(pos, n, head, member)         \
 745         for (pos = list_next_entry(pos, member),                                \
 746                 n = list_next_entry(pos, member);                               \
 747              !list_entry_is_head(pos, head, member);                            \
 748              pos = n, n = list_next_entry(n, member))
 749
 750 /**
 751  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
 752  * @param pos    the type * to use as a loop cursor.
 753  * @param n      another type * to use as temporary storage
 754  * @param head   the head for your list.
 755  * @param member the name of the list_head within the struct.
 756  *
 757  * Iterate over list of given type from current point, safe against
 758  * removal of list entry.
 759  */
 760 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 761         for (n = list_next_entry(pos, member);                                  \
 762              !list_entry_is_head(pos, head, member);                            \
 763              pos = n, n = list_next_entry(n, member))
 764
 765 /**
 766  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
 767  * @param pos    the type * to use as a loop cursor.
 768  * @param n      another type * to use as temporary storage
 769  * @param head   the head for your list.
 770  * @param member the name of the list_head within the struct.
 771  *
 772  * Iterate backwards over list of given type, safe against removal
 773  * of list entry.
 774  */
 775 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 776         for (pos = list_last_entry(head, typeof(*pos), member),         \
 777                 n = list_prev_entry(pos, member);                       \
 778              !list_entry_is_head(pos, head, member);                    \
 779              pos = n, n = list_prev_entry(n, member))
 780
 781 /**
 782  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
 783  * @param pos    the loop cursor used in the list_for_each_entry_safe loop
 784  * @param n      temporary storage used in list_for_each_entry_safe
 785  * @param member the name of the list_head within the struct.
 786  *
 787  * list_safe_reset_next is not safe to use in general if the list may be
 788  * modified concurrently (eg. the lock is dropped in the loop body). An
 789  * exception to this is if the cursor element (pos) is pinned in the list,
 790  * and list_safe_reset_next is called after re-taking the lock and before
 791  * completing the current iteration of the loop body.
 792  */
 793 #define list_safe_reset_next(pos, n, member)                            \
 794         n = list_next_entry(pos, member)
 795
 796 /*
 797  * Double linked lists with a single pointer list head.
 798  * Mostly useful for hash tables where the two pointer list head is
 799  * too wasteful.
 800  * You lose the ability to access the tail in O(1).
 801  */
 802
 803 #define HLIST_HEAD_INIT { .first = NULL }
 804 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 805 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 806 static inline void INIT_HLIST_NODE(struct hlist_node *h)
 807 {
 808         h->next = NULL;
 809         h->pprev = NULL;
 810 }
 811
 812 /**
 813  * hlist_unhashed - Has node been removed from list and reinitialized?
 814  * @param h Node to be checked
 815  *
 816  * Not that not all removal functions will leave a node in unhashed
 817  * state.  For example, hlist_nulls_del_init_rcu() does leave the
 818  * node in unhashed state, but hlist_nulls_del() does not.
 819  */
 820 static inline int hlist_unhashed(const struct hlist_node *h)
 821 {
 822         return !h->pprev;
 823 }
 824
 825 /* Ignore kernel hlist_unhashed_lockless() */
 826
 827 /**
 828  * hlist_empty - Is the specified hlist_head structure an empty hlist?
 829  * @param h Structure to check.
 830  */
 831 static inline int hlist_empty(const struct hlist_head *h)
 832 {
 833         return !h->first;
 834 }
 835
 836 static inline void __hlist_del(struct hlist_node *n)
 837 {
 838         struct hlist_node *next = n->next;
 839         struct hlist_node **pprev = n->pprev;
 840
 841         *pprev = next;
 842         if (next)
 843                 next->pprev = pprev;
 844 }
 845
 846 /**
 847  * hlist_del - Delete the specified hlist_node from its list
 848  * @param n Node to delete.
 849  *
 850  * Note that this function leaves the node in hashed state.  Use
 851  * hlist_del_init() or similar instead to unhash @a n.
 852  */
 853 static inline void hlist_del(struct hlist_node *n)
 854 {
 855         __hlist_del(n);
 856         n->next = LIST_POISON1;
 857         n->pprev = LIST_POISON2;
 858 }
 859
 860 /**
 861  * hlist_del_init - Delete the specified hlist_node from its list and initialize
 862  * @param n Node to delete.
 863  *
 864  * Note that this function leaves the node in unhashed state.
 865  */
 866 static inline void hlist_del_init(struct hlist_node *n)
 867 {
 868         if (!hlist_unhashed(n)) {
 869                 __hlist_del(n);
 870                 INIT_HLIST_NODE(n);
 871         }
 872 }
 873
 874 /**
 875  * hlist_add_head - add a new entry at the beginning of the hlist
 876  * @param n new entry to be added
 877  * @param h hlist head to add it after
 878  *
 879  * Insert a new entry after the specified head.
 880  * This is good for implementing stacks.
 881  */
 882 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 883 {
 884         struct hlist_node *first = h->first;
 885         n->next = first;
 886         if (first)
 887                 first->pprev = &n->next;
 888         h->first = n;
 889         n->pprev = &h->first;
 890 }
 891
 892 /**
 893  * hlist_add_before - add a new entry before the one specified
 894  * @param n    new entry to be added
 895  * @param next hlist node to add it before, which must be non-NULL
 896  */
 897 static inline void hlist_add_before(struct hlist_node *n,
 898                                     struct hlist_node *next)
 899 {
 900         n->pprev = next->pprev;
 901         n->next = next;
 902         next->pprev = &n->next;
 903         *(n->pprev) = n;
 904 }
 905
 906 /**
 907  * hlist_add_behind - add a new entry after the one specified
 908  * @param n    new entry to be added
 909  * @param prev hlist node to add it after, which must be non-NULL
 910  */
 911 static inline void hlist_add_behind(struct hlist_node *n,
 912                                     struct hlist_node *prev)
 913 {
 914         n->next = prev->next;
 915         prev->next = n;
 916         n->pprev = &prev->next;
 917
 918         if (n->next)
 919                 n->next->pprev = &n->next;
 920 }
 921
 922 /**
 923  * hlist_add_fake - create a fake hlist consisting of a single headless node
 924  * @param n Node to make a fake list out of
 925  *
 926  * This makes @a n appear to be its own predecessor on a headless hlist.
 927  * The point of this is to allow things like hlist_del() to work correctly
 928  * in cases where there is no list.
 929  */
 930 static inline void hlist_add_fake(struct hlist_node *n)
 931 {
 932         n->pprev = &n->next;
 933 }
 934
 935 /**
 936  * hlist_fake: Is this node a fake hlist?
 937  * @param h Node to check for being a self-referential fake hlist.
 938  */
 939 static inline bool hlist_fake(struct hlist_node *h)
 940 {
 941         return h->pprev == &h->next;
 942 }
 943
 944 /**
 945  * hlist_is_singular_node - is node the only element of the specified hlist?
 946  * @param n Node to check for singularity.
 947  * @param h Header for potentially singular list.
 948  *
 949  * Check whether the node is the only node of the head without
 950  * accessing head, thus avoiding unnecessary cache misses.
 951  */
 952 static inline bool
 953 hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
 954 {
 955         return !n->next && n->pprev == &h->first;
 956 }
 957
 958 /**
 959  * hlist_move_list - Move an hlist
 960  * @param old hlist_head for old list.
 961  * @param new hlist_head for new list.
 962  *
 963  * Move a list from one list head to another. Fixup the pprev
 964  * reference of the first entry if it exists.
 965  */
 966 static inline void hlist_move_list(struct hlist_head *old,
 967                                    struct hlist_head *new)
 968 {
 969         new->first = old->first;
 970         if (new->first)
 971                 new->first->pprev = &new->first;
 972         old->first = NULL;
 973 }
 974
 975 #define hlist_entry(ptr, type, member) container_of(ptr, type, member)
 976
 977 #define hlist_for_each(pos, head) \
 978         for (pos = (head)->first; pos ; pos = pos->next)
 979
 980 #define hlist_for_each_safe(pos, n, head) \
 981         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 982              pos = n)
 983
 984 #define hlist_entry_safe(ptr, type, member) \
 985         ({ typeof(ptr) ____ptr = (ptr); \
 986            ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
 987         })
 988
 989 /**
 990  * hlist_for_each_entry - iterate over list of given type
 991  * @param pos    the type * to use as a loop cursor.
 992  * @param head   the head for your list.
 993  * @param member the name of the hlist_node within the struct.
 994  */
 995 #define hlist_for_each_entry(pos, head, member)                         \
 996         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
 997              pos;                                                       \
 998              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 999
1000 /**
1001  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1002  * @param pos    the type * to use as a loop cursor.
1003  * @param member the name of the hlist_node within the struct.
1004  */
1005 #define hlist_for_each_entry_continue(pos, member)                      \
1006         for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
1007              pos;                                                       \
1008              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1009
1010 /**
1011  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1012  * @param pos    the type * to use as a loop cursor.
1013  * @param member the name of the hlist_node within the struct.
1014  */
1015 #define hlist_for_each_entry_from(pos, member)                          \
1016         for (; pos;                                                     \
1017              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1018
1019 /**
1020  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1021  * @param pos    the type * to use as a loop cursor.
1022  * @param n      a &struct hlist_node to use as temporary storage
1023  * @param head   the head for your list.
1024  * @param member the name of the hlist_node within the struct.
1025  */
1026 #define hlist_for_each_entry_safe(pos, n, head, member)         \
1027         for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
1028              pos && ({ n = pos->member.next; 1; });                     \
1029              pos = hlist_entry_safe(n, typeof(*pos), member))
1030
1031 #endif /* OPENOCD_HELPER_LIST_H */