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
58struct list_head {
59 struct list_head *next, *prev;
60};
61
62struct hlist_head {
63 struct hlist_node *first;
64};
65
66struct 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
75static 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
82extern bool __list_add_valid(struct list_head *newent,
83 struct list_head *prev,
84 struct list_head *next);
85extern bool __list_del_entry_valid(struct list_head *entry);
86#else
87static 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}
94static 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 */
107static 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
128static UPNP_INLINE void list_add(struct list_head *newent, struct list_head *head)
129{
130 __list_add(newent, head, head->next);
131}
132
133
142static 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 */
154static 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
166static 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
174static 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
188static 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
197static 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
208static UPNP_INLINE void list_del_init(struct list_head *entry)
209{
210 __list_del_entry(entry);
211 INIT_LIST_HEAD(entry);
212}
213
219static 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
230static 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
242static 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
252static UPNP_INLINE int list_empty(const struct list_head *head)
253{
254 return READ_ONCE(head->next) == head;
255}
256
270static 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
280static 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
294static UPNP_INLINE int list_is_singular(const struct list_head *head)
295{
296 return !list_empty(head) && (head->next == head->prev);
297}
298
299static 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
325static 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
339static 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
358static 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
370static 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
384static 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
401static 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)
679static UPNP_INLINE void INIT_HLIST_NODE(struct hlist_node *h)
680{
681 h->next = NULL;
682 h->pprev = NULL;
683}
684
685static UPNP_INLINE int hlist_unhashed(const struct hlist_node *h)
686{
687 return !h->pprev;
688}
689
690static UPNP_INLINE int hlist_empty(const struct hlist_head *h)
691{
692 return !READ_ONCE(h->first);
693}
694
695static 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
705static 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
712static 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
720static 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 */
731static 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
740static 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 */
752static UPNP_INLINE void hlist_add_fake(struct hlist_node *n)
753{
754 n->pprev = &n->next;
755}
756
757static 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 */
766static UPNP_INLINE bool
767hlist_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 */
776static 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
Defines constants that for some reason are not defined on some systems.
#define UPNP_INLINE
Declares an inline function.
Definition: UpnpGlobal.h:99
Definition: list.h:62
Definition: list.h:66
Definition: list.h:58