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_for_each_entry_direction - iterate forward/backward over list of given type
 661  * @param forward the iterate direction, true for forward, false for backward.
 662  * @param pos     the type * to use as a loop cursor.
 663  * @param head    the head for your list.
 664  * @param member  the name of the list_head within the struct.
 665  */
 666 #define list_for_each_entry_direction(forward, pos, head, member)               \
 667         for (pos = forward ? list_first_entry(head, typeof(*pos), member)       \
 668                                            : list_last_entry(head, typeof(*pos), member);       \
 669                  !list_entry_is_head(pos, head, member);                                                \
 670                  pos = forward ? list_next_entry(pos, member)                                   \
 671                                            : list_prev_entry(pos, member))
 672
 673 /**
 674  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
 675  * @param pos    the type * to use as a start point
 676  * @param head   the head of the list
 677  * @param member the name of the list_head within the struct.
 678  *
 679  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
 680  */
 681 #define list_prepare_entry(pos, head, member) \
 682         ((pos) ? (pos) : list_entry(head, typeof(*pos), member))
 683
 684 /**
 685  * list_for_each_entry_continue - continue iteration over list of given type
 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  * Continue to iterate over list of given type, continuing after
 691  * the current position.
 692  */
 693 #define list_for_each_entry_continue(pos, head, member)         \
 694         for (pos = list_next_entry(pos, member);                        \
 695              !list_entry_is_head(pos, head, member);                    \
 696              pos = list_next_entry(pos, member))
 697
 698 /**
 699  * list_for_each_entry_continue_reverse - iterate backwards from the given 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  * Start to iterate over list of given type backwards, continuing after
 705  * the current position.
 706  */
 707 #define list_for_each_entry_continue_reverse(pos, head, member)         \
 708         for (pos = list_prev_entry(pos, member);                        \
 709              !list_entry_is_head(pos, head, member);                    \
 710              pos = list_prev_entry(pos, member))
 711
 712 /**
 713  * list_for_each_entry_from - iterate over list of given type from the current point
 714  * @param pos    the type * to use as a loop cursor.
 715  * @param head   the head for your list.
 716  * @param member the name of the list_head within the struct.
 717  *
 718  * Iterate over list of given type, continuing from current position.
 719  */
 720 #define list_for_each_entry_from(pos, head, member)                     \
 721         for (; !list_entry_is_head(pos, head, member);                  \
 722              pos = list_next_entry(pos, member))
 723
 724 /**
 725  * list_for_each_entry_from_reverse - iterate backwards over list of given type
 726  *                                    from the current point
 727  * @param pos    the type * to use as a loop cursor.
 728  * @param head   the head for your list.
 729  * @param member the name of the list_head within the struct.
 730  *
 731  * Iterate backwards over list of given type, continuing from current position.
 732  */
 733 #define list_for_each_entry_from_reverse(pos, head, member)             \
 734         for (; !list_entry_is_head(pos, head, member);                  \
 735              pos = list_prev_entry(pos, member))
 736
 737 /**
 738  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 739  * @param pos    the type * to use as a loop cursor.
 740  * @param n      another type * to use as temporary storage
 741  * @param head   the head for your list.
 742  * @param member the name of the list_head within the struct.
 743  */
 744 #define list_for_each_entry_safe(pos, n, head, member)                  \
 745         for (pos = list_first_entry(head, typeof(*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_continue - continue list iteration 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, continuing after current point,
 758  * safe against removal of list entry.
 759  */
 760 #define list_for_each_entry_safe_continue(pos, n, head, member)         \
 761         for (pos = list_next_entry(pos, member),                                \
 762                 n = list_next_entry(pos, member);                               \
 763              !list_entry_is_head(pos, head, member);                            \
 764              pos = n, n = list_next_entry(n, member))
 765
 766 /**
 767  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
 768  * @param pos    the type * to use as a loop cursor.
 769  * @param n      another type * to use as temporary storage
 770  * @param head   the head for your list.
 771  * @param member the name of the list_head within the struct.
 772  *
 773  * Iterate over list of given type from current point, safe against
 774  * removal of list entry.
 775  */
 776 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 777         for (n = list_next_entry(pos, member);                                  \
 778              !list_entry_is_head(pos, head, member);                            \
 779              pos = n, n = list_next_entry(n, member))
 780
 781 /**
 782  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
 783  * @param pos    the type * to use as a loop cursor.
 784  * @param n      another type * to use as temporary storage
 785  * @param head   the head for your list.
 786  * @param member the name of the list_head within the struct.
 787  *
 788  * Iterate backwards over list of given type, safe against removal
 789  * of list entry.
 790  */
 791 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 792         for (pos = list_last_entry(head, typeof(*pos), member),         \
 793                 n = list_prev_entry(pos, member);                       \
 794              !list_entry_is_head(pos, head, member);                    \
 795              pos = n, n = list_prev_entry(n, member))
 796
 797 /**
 798  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
 799  * @param pos    the loop cursor used in the list_for_each_entry_safe loop
 800  * @param n      temporary storage used in list_for_each_entry_safe
 801  * @param member the name of the list_head within the struct.
 802  *
 803  * list_safe_reset_next is not safe to use in general if the list may be
 804  * modified concurrently (eg. the lock is dropped in the loop body). An
 805  * exception to this is if the cursor element (pos) is pinned in the list,
 806  * and list_safe_reset_next is called after re-taking the lock and before
 807  * completing the current iteration of the loop body.
 808  */
 809 #define list_safe_reset_next(pos, n, member)                            \
 810         n = list_next_entry(pos, member)
 811
 812 /*
 813  * Double linked lists with a single pointer list head.
 814  * Mostly useful for hash tables where the two pointer list head is
 815  * too wasteful.
 816  * You lose the ability to access the tail in O(1).
 817  */
 818
 819 #define HLIST_HEAD_INIT { .first = NULL }
 820 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 821 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 822 static inline void INIT_HLIST_NODE(struct hlist_node *h)
 823 {
 824         h->next = NULL;
 825         h->pprev = NULL;
 826 }
 827
 828 /**
 829  * hlist_unhashed - Has node been removed from list and reinitialized?
 830  * @param h Node to be checked
 831  *
 832  * Not that not all removal functions will leave a node in unhashed
 833  * state.  For example, hlist_nulls_del_init_rcu() does leave the
 834  * node in unhashed state, but hlist_nulls_del() does not.
 835  */
 836 static inline int hlist_unhashed(const struct hlist_node *h)
 837 {
 838         return !h->pprev;
 839 }
 840
 841 /* Ignore kernel hlist_unhashed_lockless() */
 842
 843 /**
 844  * hlist_empty - Is the specified hlist_head structure an empty hlist?
 845  * @param h Structure to check.
 846  */
 847 static inline int hlist_empty(const struct hlist_head *h)
 848 {
 849         return !h->first;
 850 }
 851
 852 static inline void __hlist_del(struct hlist_node *n)
 853 {
 854         struct hlist_node *next = n->next;
 855         struct hlist_node **pprev = n->pprev;
 856
 857         *pprev = next;
 858         if (next)
 859                 next->pprev = pprev;
 860 }
 861
 862 /**
 863  * hlist_del - Delete the specified hlist_node from its list
 864  * @param n Node to delete.
 865  *
 866  * Note that this function leaves the node in hashed state.  Use
 867  * hlist_del_init() or similar instead to unhash @a n.
 868  */
 869 static inline void hlist_del(struct hlist_node *n)
 870 {
 871         __hlist_del(n);
 872         n->next = LIST_POISON1;
 873         n->pprev = LIST_POISON2;
 874 }
 875
 876 /**
 877  * hlist_del_init - Delete the specified hlist_node from its list and initialize
 878  * @param n Node to delete.
 879  *
 880  * Note that this function leaves the node in unhashed state.
 881  */
 882 static inline void hlist_del_init(struct hlist_node *n)
 883 {
 884         if (!hlist_unhashed(n)) {
 885                 __hlist_del(n);
 886                 INIT_HLIST_NODE(n);
 887         }
 888 }
 889
 890 /**
 891  * hlist_add_head - add a new entry at the beginning of the hlist
 892  * @param n new entry to be added
 893  * @param h hlist head to add it after
 894  *
 895  * Insert a new entry after the specified head.
 896  * This is good for implementing stacks.
 897  */
 898 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 899 {
 900         struct hlist_node *first = h->first;
 901         n->next = first;
 902         if (first)
 903                 first->pprev = &n->next;
 904         h->first = n;
 905         n->pprev = &h->first;
 906 }
 907
 908 /**
 909  * hlist_add_before - add a new entry before the one specified
 910  * @param n    new entry to be added
 911  * @param next hlist node to add it before, which must be non-NULL
 912  */
 913 static inline void hlist_add_before(struct hlist_node *n,
 914                                     struct hlist_node *next)
 915 {
 916         n->pprev = next->pprev;
 917         n->next = next;
 918         next->pprev = &n->next;
 919         *(n->pprev) = n;
 920 }
 921
 922 /**
 923  * hlist_add_behind - add a new entry after the one specified
 924  * @param n    new entry to be added
 925  * @param prev hlist node to add it after, which must be non-NULL
 926  */
 927 static inline void hlist_add_behind(struct hlist_node *n,
 928                                     struct hlist_node *prev)
 929 {
 930         n->next = prev->next;
 931         prev->next = n;
 932         n->pprev = &prev->next;
 933
 934         if (n->next)
 935                 n->next->pprev = &n->next;
 936 }
 937
 938 /**
 939  * hlist_add_fake - create a fake hlist consisting of a single headless node
 940  * @param n Node to make a fake list out of
 941  *
 942  * This makes @a n appear to be its own predecessor on a headless hlist.
 943  * The point of this is to allow things like hlist_del() to work correctly
 944  * in cases where there is no list.
 945  */
 946 static inline void hlist_add_fake(struct hlist_node *n)
 947 {
 948         n->pprev = &n->next;
 949 }
 950
 951 /**
 952  * hlist_fake: Is this node a fake hlist?
 953  * @param h Node to check for being a self-referential fake hlist.
 954  */
 955 static inline bool hlist_fake(struct hlist_node *h)
 956 {
 957         return h->pprev == &h->next;
 958 }
 959
 960 /**
 961  * hlist_is_singular_node - is node the only element of the specified hlist?
 962  * @param n Node to check for singularity.
 963  * @param h Header for potentially singular list.
 964  *
 965  * Check whether the node is the only node of the head without
 966  * accessing head, thus avoiding unnecessary cache misses.
 967  */
 968 static inline bool
 969 hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
 970 {
 971         return !n->next && n->pprev == &h->first;
 972 }
 973
 974 /**
 975  * hlist_move_list - Move an hlist
 976  * @param old hlist_head for old list.
 977  * @param new hlist_head for new list.
 978  *
 979  * Move a list from one list head to another. Fixup the pprev
 980  * reference of the first entry if it exists.
 981  */
 982 static inline void hlist_move_list(struct hlist_head *old,
 983                                    struct hlist_head *new)
 984 {
 985         new->first = old->first;
 986         if (new->first)
 987                 new->first->pprev = &new->first;
 988         old->first = NULL;
 989 }
 990
 991 #define hlist_entry(ptr, type, member) container_of(ptr, type, member)
 992
 993 #define hlist_for_each(pos, head) \
 994         for (pos = (head)->first; pos ; pos = pos->next)
 995
 996 #define hlist_for_each_safe(pos, n, head) \
 997         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 998              pos = n)
 999
1000 #define hlist_entry_safe(ptr, type, member) \
1001         ({ typeof(ptr) ____ptr = (ptr); \
1002            ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
1003         })
1004
1005 /**
1006  * hlist_for_each_entry - iterate over list of given type
1007  * @param pos    the type * to use as a loop cursor.
1008  * @param head   the head for your list.
1009  * @param member the name of the hlist_node within the struct.
1010  */
1011 #define hlist_for_each_entry(pos, head, member)                         \
1012         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
1013              pos;                                                       \
1014              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1015
1016 /**
1017  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1018  * @param pos    the type * to use as a loop cursor.
1019  * @param member the name of the hlist_node within the struct.
1020  */
1021 #define hlist_for_each_entry_continue(pos, member)                      \
1022         for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
1023              pos;                                                       \
1024              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1025
1026 /**
1027  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1028  * @param pos    the type * to use as a loop cursor.
1029  * @param member the name of the hlist_node within the struct.
1030  */
1031 #define hlist_for_each_entry_from(pos, member)                          \
1032         for (; pos;                                                     \
1033              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1034
1035 /**
1036  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1037  * @param pos    the type * to use as a loop cursor.
1038  * @param n      a &struct hlist_node to use as temporary storage
1039  * @param head   the head for your list.
1040  * @param member the name of the hlist_node within the struct.
1041  */
1042 #define hlist_for_each_entry_safe(pos, n, head, member)         \
1043         for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
1044              pos && ({ n = pos->member.next; 1; });                     \
1045              pos = hlist_entry_safe(n, typeof(*pos), member))
1046
1047 #endif /* OPENOCD_HELPER_LIST_H */