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