libUPnP  1.8.0
list.h
1 #ifndef _LINUX_LIST_H
2 #define _LINUX_LIST_H
3 
4 #if 0
5 #include <linux/stddef.h>
6 #include <linux/poison.h>
7 #include <linux/prefetch.h>
8 #include <asm/system.h>
9 #endif
10 #include "poison.h"
11 
12 #ifdef __APPLE__
13 /* Apple systems define these macros in system headers, so we undef
14  * them prior to inclusion of this file */
15 #undef LIST_HEAD
16 #undef LIST_HEAD_INIT
17 #undef INIT_LIST_HEAD
18 #endif
19 
20 /*
21  * Simple doubly linked list implementation.
22  *
23  * Some of the internal functions ("__xxx") are useful when
24  * manipulating whole lists rather than single entries, as
25  * sometimes we already know the next/prev entries and we can
26  * generate better code by using them directly rather than
27  * using the generic single-entry routines.
28  */
29 
30 struct list_head {
31  struct list_head *next, *prev;
32 };
33 
34 #define LIST_HEAD_INIT(name) { &(name), &(name) }
35 
36 #define LIST_HEAD(name) \
37  struct list_head name = LIST_HEAD_INIT(name)
38 
39 static UPNP_INLINE void INIT_LIST_HEAD(struct list_head *list)
40 {
41  list->next = list;
42  list->prev = list;
43 }
44 
45 /*
46  * Insert a new entry between two known consecutive entries.
47  *
48  * This is only for internal list manipulation where we know
49  * the prev/next entries already!
50  */
51 #ifndef CONFIG_DEBUG_LIST
52 static UPNP_INLINE void __list_add(struct list_head *new_,
53  struct list_head *prev,
54  struct list_head *next)
55 {
56  next->prev = new_;
57  new_->next = next;
58  new_->prev = prev;
59  prev->next = new_;
60 }
61 #else
62 extern void __list_add(struct list_head *new_,
63  struct list_head *prev,
64  struct list_head *next);
65 #endif
66 
75 static UPNP_INLINE void list_add(struct list_head *new_, struct list_head *head)
76 {
77  __list_add(new_, head, head->next);
78 }
79 
80 
89 static UPNP_INLINE void list_add_tail(struct list_head *new_, struct list_head *head)
90 {
91  __list_add(new_, head->prev, head);
92 }
93 
94 /*
95  * Delete a list entry by making the prev/next entries
96  * point to each other.
97  *
98  * This is only for internal list manipulation where we know
99  * the prev/next entries already!
100  */
101 static UPNP_INLINE void __list_del(struct list_head * prev, struct list_head * next)
102 {
103  next->prev = prev;
104  prev->next = next;
105 }
106 
113 #ifndef CONFIG_DEBUG_LIST
114 static UPNP_INLINE void list_del(struct list_head *entry)
115 {
116  __list_del(entry->prev, entry->next);
117  entry->next = (struct list_head *)LIST_POISON1;
118  entry->prev = (struct list_head *)LIST_POISON2;
119 }
120 #else
121 extern void list_del(struct list_head *entry);
122 #endif
123 
131 static UPNP_INLINE void list_replace(struct list_head *old,
132  struct list_head *new_)
133 {
134  new_->next = old->next;
135  new_->next->prev = new_;
136  new_->prev = old->prev;
137  new_->prev->next = new_;
138 }
139 
140 static UPNP_INLINE void list_replace_init(struct list_head *old,
141  struct list_head *new_)
142 {
143  list_replace(old, new_);
144  INIT_LIST_HEAD(old);
145 }
146 
151 static UPNP_INLINE void list_del_init(struct list_head *entry)
152 {
153  __list_del(entry->prev, entry->next);
154  INIT_LIST_HEAD(entry);
155 }
156 
162 static UPNP_INLINE void list_move(struct list_head *list, struct list_head *head)
163 {
164  __list_del(list->prev, list->next);
165  list_add(list, head);
166 }
167 
173 static UPNP_INLINE void list_move_tail(struct list_head *list,
174  struct list_head *head)
175 {
176  __list_del(list->prev, list->next);
177  list_add_tail(list, head);
178 }
179 
185 static UPNP_INLINE int list_is_last(const struct list_head *list,
186  const struct list_head *head)
187 {
188  return list->next == head;
189 }
190 
195 static UPNP_INLINE int list_empty(const struct list_head *head)
196 {
197  return head->next == head;
198 }
199 
213 static UPNP_INLINE int list_empty_careful(const struct list_head *head)
214 {
215  struct list_head *next = head->next;
216  return (next == head) && (next == head->prev);
217 }
218 
223 static UPNP_INLINE void list_rotate_left(struct list_head *head)
224 {
225  struct list_head *first;
226 
227  if (!list_empty(head)) {
228  first = head->next;
229  list_move_tail(first, head);
230  }
231 }
232 
237 static UPNP_INLINE int list_is_singular(const struct list_head *head)
238 {
239  return !list_empty(head) && (head->next == head->prev);
240 }
241 
242 static UPNP_INLINE void __list_cut_position(struct list_head *list,
243  struct list_head *head, struct list_head *entry)
244 {
245  struct list_head *new_first = entry->next;
246  list->next = head->next;
247  list->next->prev = list;
248  list->prev = entry;
249  entry->next = list;
250  head->next = new_first;
251  new_first->prev = head;
252 }
253 
268 static UPNP_INLINE void list_cut_position(struct list_head *list,
269  struct list_head *head, struct list_head *entry)
270 {
271  if (list_empty(head))
272  return;
273  if (list_is_singular(head) &&
274  (head->next != entry && head != entry))
275  return;
276  if (entry == head)
277  INIT_LIST_HEAD(list);
278  else
279  __list_cut_position(list, head, entry);
280 }
281 
282 static UPNP_INLINE void __list_splice(const struct list_head *list,
283  struct list_head *prev,
284  struct list_head *next)
285 {
286  struct list_head *first = list->next;
287  struct list_head *last = list->prev;
288 
289  first->prev = prev;
290  prev->next = first;
291 
292  last->next = next;
293  next->prev = last;
294 }
295 
301 static UPNP_INLINE void list_splice(const struct list_head *list,
302  struct list_head *head)
303 {
304  if (!list_empty(list))
305  __list_splice(list, head, head->next);
306 }
307 
313 static UPNP_INLINE void list_splice_tail(struct list_head *list,
314  struct list_head *head)
315 {
316  if (!list_empty(list))
317  __list_splice(list, head->prev, head);
318 }
319 
327 static UPNP_INLINE void list_splice_init(struct list_head *list,
328  struct list_head *head)
329 {
330  if (!list_empty(list)) {
331  __list_splice(list, head, head->next);
332  INIT_LIST_HEAD(list);
333  }
334 }
335 
344 static UPNP_INLINE void list_splice_tail_init(struct list_head *list,
345  struct list_head *head)
346 {
347  if (!list_empty(list)) {
348  __list_splice(list, head->prev, head);
349  INIT_LIST_HEAD(list);
350  }
351 }
352 
359 #define list_entry(ptr, type, member) \
360  container_of(ptr, type, member)
361 
370 #define list_first_entry(ptr, type, member) \
371  list_entry((ptr)->next, type, member)
372 
378 #define list_for_each(pos, head) \
379  for (pos = (head)->next; prefetch(pos->next), pos != (head); \
380  pos = pos->next)
381 
392 #define __list_for_each(pos, head) \
393  for (pos = (head)->next; pos != (head); pos = pos->next)
394 
400 #define list_for_each_prev(pos, head) \
401  for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
402  pos = pos->prev)
403 
410 #define list_for_each_safe(pos, n, head) \
411  for (pos = (head)->next, n = pos->next; pos != (head); \
412  pos = n, n = pos->next)
413 
420 #define list_for_each_prev_safe(pos, n, head) \
421  for (pos = (head)->prev, n = pos->prev; \
422  prefetch(pos->prev), pos != (head); \
423  pos = n, n = pos->prev)
424 
431 #define list_for_each_entry(pos, head, member) \
432  for (pos = list_entry((head)->next, typeof(*pos), member); \
433  prefetch(pos->member.next), &pos->member != (head); \
434  pos = list_entry(pos->member.next, typeof(*pos), member))
435 
442 #define list_for_each_entry_reverse(pos, head, member) \
443  for (pos = list_entry((head)->prev, typeof(*pos), member); \
444  prefetch(pos->member.prev), &pos->member != (head); \
445  pos = list_entry(pos->member.prev, typeof(*pos), member))
446 
455 #define list_prepare_entry(pos, head, member) \
456  ((pos) ? : list_entry(head, typeof(*pos), member))
457 
467 #define list_for_each_entry_continue(pos, head, member) \
468  for (pos = list_entry(pos->member.next, typeof(*pos), member); \
469  prefetch(pos->member.next), &pos->member != (head); \
470  pos = list_entry(pos->member.next, typeof(*pos), member))
471 
481 #define list_for_each_entry_continue_reverse(pos, head, member) \
482  for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
483  prefetch(pos->member.prev), &pos->member != (head); \
484  pos = list_entry(pos->member.prev, typeof(*pos), member))
485 
494 #define list_for_each_entry_from(pos, head, member) \
495  for (; prefetch(pos->member.next), &pos->member != (head); \
496  pos = list_entry(pos->member.next, typeof(*pos), member))
497 
505 #define list_for_each_entry_safe(pos, n, head, member) \
506  for (pos = list_entry((head)->next, typeof(*pos), member), \
507  n = list_entry(pos->member.next, typeof(*pos), member); \
508  &pos->member != (head); \
509  pos = n, n = list_entry(n->member.next, typeof(*n), member))
510 
521 #define list_for_each_entry_safe_continue(pos, n, head, member) \
522  for (pos = list_entry(pos->member.next, typeof(*pos), member), \
523  n = list_entry(pos->member.next, typeof(*pos), member); \
524  &pos->member != (head); \
525  pos = n, n = list_entry(n->member.next, typeof(*n), member))
526 
537 #define list_for_each_entry_safe_from(pos, n, head, member) \
538  for (n = list_entry(pos->member.next, typeof(*pos), member); \
539  &pos->member != (head); \
540  pos = n, n = list_entry(n->member.next, typeof(*n), member))
541 
552 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
553  for (pos = list_entry((head)->prev, typeof(*pos), member), \
554  n = list_entry(pos->member.prev, typeof(*pos), member); \
555  &pos->member != (head); \
556  pos = n, n = list_entry(n->member.prev, typeof(*n), member))
557 
558 /*
559  * Double linked lists with a single pointer list head.
560  * Mostly useful for hash tables where the two pointer list head is
561  * too wasteful.
562  * You lose the ability to access the tail in O(1).
563  */
564 
565 struct hlist_head {
566  struct hlist_node *first;
567 };
568 
569 struct hlist_node {
570  struct hlist_node *next, **pprev;
571 };
572 
573 #define HLIST_HEAD_INIT { .first = NULL }
574 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
575 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
576 static UPNP_INLINE void INIT_HLIST_NODE(struct hlist_node *h)
577 {
578  h->next = NULL;
579  h->pprev = NULL;
580 }
581 
582 static UPNP_INLINE int hlist_unhashed(const struct hlist_node *h)
583 {
584  return !h->pprev;
585 }
586 
587 static UPNP_INLINE int hlist_empty(const struct hlist_head *h)
588 {
589  return !h->first;
590 }
591 
592 static UPNP_INLINE void __hlist_del(struct hlist_node *n)
593 {
594  struct hlist_node *next = n->next;
595  struct hlist_node **pprev = n->pprev;
596  *pprev = next;
597  if (next)
598  next->pprev = pprev;
599 }
600 
601 static UPNP_INLINE void hlist_del(struct hlist_node *n)
602 {
603  __hlist_del(n);
604  n->next = (struct hlist_node *)LIST_POISON1;
605  n->pprev = (struct hlist_node **)LIST_POISON2;
606 }
607 
608 static UPNP_INLINE void hlist_del_init(struct hlist_node *n)
609 {
610  if (!hlist_unhashed(n)) {
611  __hlist_del(n);
612  INIT_HLIST_NODE(n);
613  }
614 }
615 
616 static UPNP_INLINE void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
617 {
618  struct hlist_node *first = h->first;
619  n->next = first;
620  if (first)
621  first->pprev = &n->next;
622  h->first = n;
623  n->pprev = &h->first;
624 }
625 
626 /* next must be != NULL */
627 static UPNP_INLINE void hlist_add_before(struct hlist_node *n,
628  struct hlist_node *next)
629 {
630  n->pprev = next->pprev;
631  n->next = next;
632  next->pprev = &n->next;
633  *(n->pprev) = n;
634 }
635 
636 static UPNP_INLINE void hlist_add_after(struct hlist_node *n,
637  struct hlist_node *next)
638 {
639  next->next = n->next;
640  n->next = next;
641  next->pprev = &n->next;
642 
643  if(next->next)
644  next->next->pprev = &next->next;
645 }
646 
647 /*
648  * Move a list from one list head to another. Fixup the pprev
649  * reference of the first entry if it exists.
650  */
651 static UPNP_INLINE void hlist_move_list(struct hlist_head *old,
652  struct hlist_head *new_)
653 {
654  new_->first = old->first;
655  if (new_->first)
656  new_->first->pprev = &new_->first;
657  old->first = NULL;
658 }
659 
660 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
661 
662 #define hlist_for_each(pos, head) \
663  for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
664  pos = pos->next)
665 
666 #define hlist_for_each_safe(pos, n, head) \
667  for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
668  pos = n)
669 
677 #define hlist_for_each_entry(tpos, pos, head, member) \
678  for (pos = (head)->first; \
679  pos && ({ prefetch(pos->next); 1;}) && \
680  ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
681  pos = pos->next)
682 
689 #define hlist_for_each_entry_continue(tpos, pos, member) \
690  for (pos = (pos)->next; \
691  pos && ({ prefetch(pos->next); 1;}) && \
692  ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
693  pos = pos->next)
694 
701 #define hlist_for_each_entry_from(tpos, pos, member) \
702  for (; pos && ({ prefetch(pos->next); 1;}) && \
703  ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
704  pos = pos->next)
705 
714 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
715  for (pos = (head)->first; \
716  pos && ({ n = pos->next; 1; }) && \
717  ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
718  pos = n)
719 
720 #endif
Definition: list.h:565
Definition: list.h:30
Definition: list.h:569
#define UPNP_INLINE
Declares an inline function.
Definition: UpnpGlobal.h:93