libUPnP  1.8.4
list.h
1 #ifndef _LINUX_LIST_H
2 #define _LINUX_LIST_H
3 
4 #if 0
5 #include <linux/types.h>
6 #include <linux/stddef.h>
7 #include <linux/poison.h>
8 #include <linux/const.h>
9 #include <linux/kernel.h>
10 #include <linux/prefetch.h>
11 #include <asm/system.h>
12 #endif
13 #include "poison.h"
14 
15 #ifdef __APPLE__
16 /* Apple systems define these macros in system headers, so we undef
17  * them prior to inclusion of this file */
18 #undef LIST_HEAD
19 #undef LIST_HEAD_INIT
20 #undef INIT_LIST_HEAD
21 #endif
22 
23 #include "UpnpGlobal.h" /* For UPNP_INLINE */
24 
25 #define bool int
26 #define true !0
27 
28 #undef READ_ONCE
29 #define READ_ONCE(x) x
30 
31 #undef WRITE_ONCE
32 #define WRITE_ONCE(x,y) x = y
33 
34 #undef offsetof
35 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
36 
44 #define container_of(ptr, type, member) ({ \
45  const typeof( ((type *)0)->member ) *__mptr = (ptr); \
46  (type *)( (char *)__mptr - offsetof(type,member) );})
47 
48 /*
49  * Simple doubly linked list implementation.
50  *
51  * Some of the internal functions ("__xxx") are useful when
52  * manipulating whole lists rather than single entries, as
53  * sometimes we already know the next/prev entries and we can
54  * generate better code by using them directly rather than
55  * using the generic single-entry routines.
56  */
57 
58 struct list_head {
59  struct list_head *next, *prev;
60 };
61 
62 struct hlist_head {
63  struct hlist_node *first;
64 };
65 
66 struct hlist_node {
67  struct hlist_node *next, **pprev;
68 };
69 
70 #define LIST_HEAD_INIT(name) { &(name), &(name) }
71 
72 #define LIST_HEAD(name) \
73  struct list_head name = LIST_HEAD_INIT(name)
74 
75 static UPNP_INLINE void INIT_LIST_HEAD(struct list_head *list)
76 {
77  WRITE_ONCE(list->next, list);
78  list->prev = list;
79 }
80 
81 #ifdef CONFIG_DEBUG_LIST
82 extern bool __list_add_valid(struct list_head *newent,
83  struct list_head *prev,
84  struct list_head *next);
85 extern bool __list_del_entry_valid(struct list_head *entry);
86 #else
87 static UPNP_INLINE bool __list_add_valid(struct list_head *newent,
88  struct list_head *prev,
89  struct list_head *next)
90 {
91  return true;
92  newent++; prev++; next++; /* against compiler warnings */
93 }
94 static UPNP_INLINE bool __list_del_entry_valid(struct list_head *entry)
95 {
96  return true;
97  entry++; /* against compiler warnings */
98 }
99 #endif
100 
101 /*
102  * Insert a new entry between two known consecutive entries.
103  *
104  * This is only for internal list manipulation where we know
105  * the prev/next entries already!
106  */
107 static UPNP_INLINE void __list_add(struct list_head *newent,
108  struct list_head *prev,
109  struct list_head *next)
110 {
111  if (!__list_add_valid(newent, prev, next))
112  return;
113 
114  next->prev = newent;
115  newent->next = next;
116  newent->prev = prev;
117  WRITE_ONCE(prev->next, newent);
118 }
119 
128 static UPNP_INLINE void list_add(struct list_head *newent, struct list_head *head)
129 {
130  __list_add(newent, head, head->next);
131 }
132 
133 
142 static UPNP_INLINE void list_add_tail(struct list_head *newent, struct list_head *head)
143 {
144  __list_add(newent, head->prev, head);
145 }
146 
147 /*
148  * Delete a list entry by making the prev/next entries
149  * point to each other.
150  *
151  * This is only for internal list manipulation where we know
152  * the prev/next entries already!
153  */
154 static UPNP_INLINE void __list_del(struct list_head * prev, struct list_head * next)
155 {
156  next->prev = prev;
157  WRITE_ONCE(prev->next, next);
158 }
159 
166 static UPNP_INLINE void __list_del_entry(struct list_head *entry)
167 {
168  if (!__list_del_entry_valid(entry))
169  return;
170 
171  __list_del(entry->prev, entry->next);
172 }
173 
174 static UPNP_INLINE void list_del(struct list_head *entry)
175 {
176  __list_del_entry(entry);
177  entry->next = (struct list_head*)LIST_POISON1;
178  entry->prev = (struct list_head*)LIST_POISON2;
179 }
180 
188 static UPNP_INLINE void list_replace(struct list_head *old,
189  struct list_head *newent)
190 {
191  newent->next = old->next;
192  newent->next->prev = newent;
193  newent->prev = old->prev;
194  newent->prev->next = newent;
195 }
196 
197 static UPNP_INLINE void list_replace_init(struct list_head *old,
198  struct list_head *newent)
199 {
200  list_replace(old, newent);
201  INIT_LIST_HEAD(old);
202 }
203 
208 static UPNP_INLINE void list_del_init(struct list_head *entry)
209 {
210  __list_del_entry(entry);
211  INIT_LIST_HEAD(entry);
212 }
213 
219 static UPNP_INLINE void list_move(struct list_head *list, struct list_head *head)
220 {
221  __list_del_entry(list);
222  list_add(list, head);
223 }
224 
230 static UPNP_INLINE void list_move_tail(struct list_head *list,
231  struct list_head *head)
232 {
233  __list_del_entry(list);
234  list_add_tail(list, head);
235 }
236 
242 static UPNP_INLINE int list_is_last(const struct list_head *list,
243  const struct list_head *head)
244 {
245  return list->next == head;
246 }
247 
252 static UPNP_INLINE int list_empty(const struct list_head *head)
253 {
254  return READ_ONCE(head->next) == head;
255 }
256 
270 static UPNP_INLINE int list_empty_careful(const struct list_head *head)
271 {
272  struct list_head *next = head->next;
273  return (next == head) && (next == head->prev);
274 }
275 
280 static UPNP_INLINE void list_rotate_left(struct list_head *head)
281 {
282  struct list_head *first;
283 
284  if (!list_empty(head)) {
285  first = head->next;
286  list_move_tail(first, head);
287  }
288 }
289 
294 static UPNP_INLINE int list_is_singular(const struct list_head *head)
295 {
296  return !list_empty(head) && (head->next == head->prev);
297 }
298 
299 static UPNP_INLINE void __list_cut_position(struct list_head *list,
300  struct list_head *head, struct list_head *entry)
301 {
302  struct list_head *new_first = entry->next;
303  list->next = head->next;
304  list->next->prev = list;
305  list->prev = entry;
306  entry->next = list;
307  head->next = new_first;
308  new_first->prev = head;
309 }
310 
325 static UPNP_INLINE void list_cut_position(struct list_head *list,
326  struct list_head *head, struct list_head *entry)
327 {
328  if (list_empty(head))
329  return;
330  if (list_is_singular(head) &&
331  (head->next != entry && head != entry))
332  return;
333  if (entry == head)
334  INIT_LIST_HEAD(list);
335  else
336  __list_cut_position(list, head, entry);
337 }
338 
339 static UPNP_INLINE void __list_splice(const struct list_head *list,
340  struct list_head *prev,
341  struct list_head *next)
342 {
343  struct list_head *first = list->next;
344  struct list_head *last = list->prev;
345 
346  first->prev = prev;
347  prev->next = first;
348 
349  last->next = next;
350  next->prev = last;
351 }
352 
358 static UPNP_INLINE void list_splice(const struct list_head *list,
359  struct list_head *head)
360 {
361  if (!list_empty(list))
362  __list_splice(list, head, head->next);
363 }
364 
370 static UPNP_INLINE void list_splice_tail(struct list_head *list,
371  struct list_head *head)
372 {
373  if (!list_empty(list))
374  __list_splice(list, head->prev, head);
375 }
376 
384 static UPNP_INLINE void list_splice_init(struct list_head *list,
385  struct list_head *head)
386 {
387  if (!list_empty(list)) {
388  __list_splice(list, head, head->next);
389  INIT_LIST_HEAD(list);
390  }
391 }
392 
401 static UPNP_INLINE void list_splice_tail_init(struct list_head *list,
402  struct list_head *head)
403 {
404  if (!list_empty(list)) {
405  __list_splice(list, head->prev, head);
406  INIT_LIST_HEAD(list);
407  }
408 }
409 
416 #define list_entry(ptr, type, member) \
417  container_of(ptr, type, member)
418 
427 #define list_first_entry(ptr, type, member) \
428  list_entry((ptr)->next, type, member)
429 
438 #define list_last_entry(ptr, type, member) \
439  list_entry((ptr)->prev, type, member)
440 
449 #define list_first_entry_or_null(ptr, type, member) ({ \
450  struct list_head *head__ = (ptr); \
451  struct list_head *pos__ = READ_ONCE(head__->next); \
452  pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
453 })
454 
460 #define list_next_entry(pos, member) \
461  list_entry((pos)->member.next, typeof(*(pos)), member)
462 
468 #define list_prev_entry(pos, member) \
469  list_entry((pos)->member.prev, typeof(*(pos)), member)
470 
476 #define list_for_each(pos, head) \
477  for (pos = (head)->next; pos != (head); pos = pos->next)
478 
484 #define list_for_each_prev(pos, head) \
485  for (pos = (head)->prev; pos != (head); pos = pos->prev)
486 
493 #define list_for_each_safe(pos, n, head) \
494  for (pos = (head)->next, n = pos->next; pos != (head); \
495  pos = n, n = pos->next)
496 
503 #define list_for_each_prev_safe(pos, n, head) \
504  for (pos = (head)->prev, n = pos->prev; \
505  pos != (head); \
506  pos = n, n = pos->prev)
507 
514 #define list_for_each_entry(pos, head, member) \
515  for (pos = list_first_entry(head, typeof(*pos), member); \
516  &pos->member != (head); \
517  pos = list_next_entry(pos, member))
518 
525 #define list_for_each_entry_reverse(pos, head, member) \
526  for (pos = list_last_entry(head, typeof(*pos), member); \
527  &pos->member != (head); \
528  pos = list_prev_entry(pos, member))
529 
538 #define list_prepare_entry(pos, head, member) \
539  ((pos) ? : list_entry(head, typeof(*pos), member))
540 
550 #define list_for_each_entry_continue(pos, head, member) \
551  for (pos = list_next_entry(pos, member); \
552  &pos->member != (head); \
553  pos = list_next_entry(pos, member))
554 
564 #define list_for_each_entry_continue_reverse(pos, head, member) \
565  for (pos = list_prev_entry(pos, member); \
566  &pos->member != (head); \
567  pos = list_prev_entry(pos, member))
568 
577 #define list_for_each_entry_from(pos, head, member) \
578  for (; &pos->member != (head); \
579  pos = list_next_entry(pos, member))
580 
590 #define list_for_each_entry_from_reverse(pos, head, member) \
591  for (; &pos->member != (head); \
592  pos = list_prev_entry(pos, member))
593 
601 #define list_for_each_entry_safe(pos, n, head, member) \
602  for (pos = list_first_entry(head, typeof(*pos), member), \
603  n = list_next_entry(pos, member); \
604  &pos->member != (head); \
605  pos = n, n = list_next_entry(n, member))
606 
617 #define list_for_each_entry_safe_continue(pos, n, head, member) \
618  for (pos = list_next_entry(pos, member), \
619  n = list_next_entry(pos, member); \
620  &pos->member != (head); \
621  pos = n, n = list_next_entry(n, member))
622 
633 #define list_for_each_entry_safe_from(pos, n, head, member) \
634  for (n = list_next_entry(pos, member); \
635  &pos->member != (head); \
636  pos = n, n = list_next_entry(n, member))
637 
648 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
649  for (pos = list_last_entry(head, typeof(*pos), member), \
650  n = list_prev_entry(pos, member); \
651  &pos->member != (head); \
652  pos = n, n = list_prev_entry(n, member))
653 
666 #define list_safe_reset_next(pos, n, member) \
667  n = list_next_entry(pos, member)
668 
669 /*
670  * Double linked lists with a single pointer list head.
671  * Mostly useful for hash tables where the two pointer list head is
672  * too wasteful.
673  * You lose the ability to access the tail in O(1).
674  */
675 
676 #define HLIST_HEAD_INIT { .first = NULL }
677 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
678 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
679 static UPNP_INLINE void INIT_HLIST_NODE(struct hlist_node *h)
680 {
681  h->next = NULL;
682  h->pprev = NULL;
683 }
684 
685 static UPNP_INLINE int hlist_unhashed(const struct hlist_node *h)
686 {
687  return !h->pprev;
688 }
689 
690 static UPNP_INLINE int hlist_empty(const struct hlist_head *h)
691 {
692  return !READ_ONCE(h->first);
693 }
694 
695 static UPNP_INLINE void __hlist_del(struct hlist_node *n)
696 {
697  struct hlist_node *next = n->next;
698  struct hlist_node **pprev = n->pprev;
699 
700  WRITE_ONCE(*pprev, next);
701  if (next)
702  next->pprev = pprev;
703 }
704 
705 static UPNP_INLINE void hlist_del(struct hlist_node *n)
706 {
707  __hlist_del(n);
708  n->next = (struct hlist_node*)LIST_POISON1;
709  n->pprev = (struct hlist_node**)LIST_POISON2;
710 }
711 
712 static UPNP_INLINE void hlist_del_init(struct hlist_node *n)
713 {
714  if (!hlist_unhashed(n)) {
715  __hlist_del(n);
716  INIT_HLIST_NODE(n);
717  }
718 }
719 
720 static UPNP_INLINE void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
721 {
722  struct hlist_node *first = h->first;
723  n->next = first;
724  if (first)
725  first->pprev = &n->next;
726  WRITE_ONCE(h->first, n);
727  n->pprev = &h->first;
728 }
729 
730 /* next must be != NULL */
731 static UPNP_INLINE void hlist_add_before(struct hlist_node *n,
732  struct hlist_node *next)
733 {
734  n->pprev = next->pprev;
735  n->next = next;
736  next->pprev = &n->next;
737  WRITE_ONCE(*(n->pprev), n);
738 }
739 
740 static UPNP_INLINE void hlist_add_behind(struct hlist_node *n,
741  struct hlist_node *prev)
742 {
743  n->next = prev->next;
744  WRITE_ONCE(prev->next, n);
745  n->pprev = &prev->next;
746 
747  if (n->next)
748  n->next->pprev = &n->next;
749 }
750 
751 /* after that we'll appear to be on some hlist and hlist_del will work */
752 static UPNP_INLINE void hlist_add_fake(struct hlist_node *n)
753 {
754  n->pprev = &n->next;
755 }
756 
757 static UPNP_INLINE bool hlist_fake(struct hlist_node *h)
758 {
759  return h->pprev == &h->next;
760 }
761 
762 /*
763  * Check whether the node is the only node of the head without
764  * accessing head:
765  */
766 static UPNP_INLINE bool
767 hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
768 {
769  return !n->next && n->pprev == &h->first;
770 }
771 
772 /*
773  * Move a list from one list head to another. Fixup the pprev
774  * reference of the first entry if it exists.
775  */
776 static UPNP_INLINE void hlist_move_list(struct hlist_head *old,
777  struct hlist_head *newent)
778 {
779  newent->first = old->first;
780  if (newent->first)
781  newent->first->pprev = &newent->first;
782  old->first = NULL;
783 }
784 
785 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
786 
787 #define hlist_for_each(pos, head) \
788  for (pos = (head)->first; pos ; pos = pos->next)
789 
790 #define hlist_for_each_safe(pos, n, head) \
791  for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
792  pos = n)
793 
794 #define hlist_entry_safe(ptr, type, member) \
795  ({ typeof(ptr) ____ptr = (ptr); \
796  ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
797  })
798 
805 #define hlist_for_each_entry(pos, head, member) \
806  for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
807  pos; \
808  pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
809 
815 #define hlist_for_each_entry_continue(pos, member) \
816  for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
817  pos; \
818  pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
819 
825 #define hlist_for_each_entry_from(pos, member) \
826  for (; pos; \
827  pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
828 
836 #define hlist_for_each_entry_safe(pos, n, head, member) \
837  for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
838  pos && ({ n = pos->member.next; 1; }); \
839  pos = hlist_entry_safe(n, typeof(*pos), member))
840 
841 #undef bool
842 #undef true
843 #endif
Definition: list.h:62
Definition: list.h:58
Definition: list.h:66
#define UPNP_INLINE
Declares an inline function.
Definition: UpnpGlobal.h:99
Defines constants that for some reason are not defined on some systems.