OpenOCD
list.h
Go to the documentation of this file.
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 
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 
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 
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 
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 
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 
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 
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 
218 static inline void list_del_init(struct list_head *entry)
219 {
220  __list_del_entry(entry);
221  INIT_LIST_HEAD(entry);
222 }
223 
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 
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 
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 
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 
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 
296 static inline int list_empty(const struct list_head *head)
297 {
298  return head->next == head;
299 }
300 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
526 #define list_entry(ptr, type, member) \
527  container_of(ptr, type, member)
528 
537 #define list_first_entry(ptr, type, member) \
538  list_entry((ptr)->next, type, member)
539 
548 #define list_last_entry(ptr, type, member) \
549  list_entry((ptr)->prev, type, member)
550 
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 
570 #define list_next_entry(pos, member) \
571  list_entry((pos)->member.next, typeof(*(pos)), member)
572 
578 #define list_prev_entry(pos, member) \
579  list_entry((pos)->member.prev, typeof(*(pos)), member)
580 
586 #define list_for_each(pos, head) \
587  for (pos = (head)->next; pos != (head); pos = pos->next)
588 
596 #define list_for_each_continue(pos, head) \
597  for (pos = pos->next; pos != (head); pos = pos->next)
598 
604 #define list_for_each_prev(pos, head) \
605  for (pos = (head)->prev; pos != (head); pos = pos->prev)
606 
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 
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 
634 #define list_entry_is_head(pos, head, member) \
635  (&pos->member == (head))
636 
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 
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 
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 
681 #define list_prepare_entry(pos, head, member) \
682  ((pos) ? (pos) : list_entry(head, typeof(*pos), member))
683 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
946 static inline void hlist_add_fake(struct hlist_node *n)
947 {
948  n->pprev = &n->next;
949 }
950 
955 static inline bool hlist_fake(struct hlist_node *h)
956 {
957  return h->pprev == &h->next;
958 }
959 
968 static inline bool
970 {
971  return !n->next && n->pprev == &h->first;
972 }
973 
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 
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 
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 
1031 #define hlist_for_each_entry_from(pos, member) \
1032  for (; pos; \
1033  pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1034 
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 */
static void list_add(struct list_head *new, struct list_head *head)
list_add - add a new entry
Definition: list.h:112
static void list_splice(const struct list_head *list, struct list_head *head)
list_splice - join two lists, this is designed for stacks
Definition: list.h:468
static void list_bulk_move_tail(struct list_head *head, struct list_head *first, struct list_head *last)
list_bulk_move_tail - move a subsection of a list to its tail
Definition: list.h:256
static void __hlist_del(struct hlist_node *n)
Definition: list.h:852
static void __list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry)
Definition: list.h:379
static void list_splice_tail_init(struct list_head *list, struct list_head *head)
list_splice_tail_init - join two lists and reinitialise the emptied list
Definition: list.h:511
static void list_move_tail(struct list_head *list, struct list_head *head)
list_move_tail - delete from one list and add as another's tail
Definition: list.h:240
static void hlist_add_behind(struct hlist_node *n, struct hlist_node *prev)
hlist_add_behind - add a new entry after the one specified
Definition: list.h:927
static void __list_del(struct list_head *prev, struct list_head *next)
Definition: list.h:138
static void hlist_add_before(struct hlist_node *n, struct hlist_node *next)
hlist_add_before - add a new entry before the one specified
Definition: list.h:913
static void list_replace_init(struct list_head *old, struct list_head *new)
list_replace_init - replace old entry by new one and initialize the old one
Definition: list.h:190
static void list_cut_before(struct list_head *list, struct list_head *head, struct list_head *entry)
list_cut_before - cut a list into two, before given entry
Definition: list.h:433
static void hlist_del_init(struct hlist_node *n)
hlist_del_init - Delete the specified hlist_node from its list and initialize
Definition: list.h:882
static bool hlist_fake(struct hlist_node *h)
hlist_fake: Is this node a fake hlist?
Definition: list.h:955
#define LIST_POISON2
Definition: list.h:24
static int list_is_first(const struct list_head *list, const struct list_head *head)
list_is_first – tests whether list is the first entry in list head
Definition: list.h:275
static void list_replace(struct list_head *old, struct list_head *new)
list_replace - replace old entry by new one
Definition: list.h:174
static int list_is_singular(const struct list_head *head)
list_is_singular - tests whether a list has just one entry.
Definition: list.h:374
static void INIT_HLIST_NODE(struct hlist_node *h)
Definition: list.h:822
static void list_del_init_careful(struct list_head *entry)
list_del_init_careful - deletes entry from list and reinitialize it.
Definition: list.h:312
static void list_add_tail(struct list_head *new, struct list_head *head)
list_add_tail - add a new entry
Definition: list.h:126
static int list_empty(const struct list_head *head)
list_empty - tests whether a list is empty
Definition: list.h:296
static bool hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
hlist_is_singular_node - is node the only element of the specified hlist?
Definition: list.h:969
static void hlist_add_fake(struct hlist_node *n)
hlist_add_fake - create a fake hlist consisting of a single headless node
Definition: list.h:946
static bool __list_add_valid(struct list_head *new, struct list_head *prev, struct list_head *next)
Definition: list.h:73
static void list_rotate_to_front(struct list_head *list, struct list_head *head)
list_rotate_to_front() - Rotate list to specific item.
Definition: list.h:359
static int hlist_unhashed(const struct hlist_node *h)
hlist_unhashed - Has node been removed from list and reinitialized?
Definition: list.h:836
static void list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry)
list_cut_position - cut a list into two
Definition: list.h:405
static void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
Definition: list.h:91
static void list_splice_init(struct list_head *list, struct list_head *head)
list_splice_init - join two lists and reinitialise the emptied list.
Definition: list.h:494
#define LIST_POISON1
Definition: list.h:23
static bool __list_del_entry_valid(struct list_head *entry)
Definition: list.h:79
static void hlist_del(struct hlist_node *n)
hlist_del - Delete the specified hlist_node from its list
Definition: list.h:869
static void list_swap(struct list_head *entry1, struct list_head *entry2)
list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
Definition: list.h:202
static void __list_del_entry(struct list_head *entry)
Definition: list.h:146
static void list_del(struct list_head *entry)
list_del - deletes entry from list.
Definition: list.h:160
static int list_empty_careful(const struct list_head *head)
list_empty_careful - tests whether a list is empty and not being modified
Definition: list.h:332
static void __list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next)
Definition: list.h:449
static void list_rotate_left(struct list_head *head)
list_rotate_left - rotate the list to the left
Definition: list.h:342
static int list_is_last(const struct list_head *list, const struct list_head *head)
list_is_last - tests whether list is the last entry in list head
Definition: list.h:286
static void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
hlist_add_head - add a new entry at the beginning of the hlist
Definition: list.h:898
static void list_del_init(struct list_head *entry)
list_del_init - deletes entry from list and reinitialize it.
Definition: list.h:218
static void list_splice_tail(struct list_head *list, struct list_head *head)
list_splice_tail - join two lists, each list being a queue
Definition: list.h:480
static void INIT_LIST_HEAD(struct list_head *list)
INIT_LIST_HEAD - Initialize a list_head structure.
Definition: list.h:61
static void hlist_move_list(struct hlist_head *old, struct hlist_head *new)
hlist_move_list - Move an hlist
Definition: list.h:982
static void list_move(struct list_head *list, struct list_head *head)
list_move - delete from one list and add as another's head
Definition: list.h:229
static int hlist_empty(const struct hlist_head *h)
hlist_empty - Is the specified hlist_head structure an empty hlist?
Definition: list.h:847
struct hlist_node * first
Definition: list.h:31
struct hlist_node ** pprev
Definition: list.h:35
struct hlist_node * next
Definition: list.h:35
Definition: list.h:26
struct list_head * prev
Definition: list.h:27
struct list_head * next
Definition: list.h:27
#define NULL
Definition: usb.h:16