list.h 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191
  1. /* Linux kernel style list handling function
  2. *
  3. * Written from scratch by Timo Teräs <timo.teras@iki.fi>, but modeled
  4. * after the linux kernel code.
  5. *
  6. * This file is free software: you may copy, redistribute and/or modify
  7. * it under the terms of the GNU General Public License as published by
  8. * the Free Software Foundation, either version 2 of the License, or
  9. * (at your option) any later version.
  10. */
  11. #ifndef LIST_H
  12. #define LIST_H
  13. #ifndef NULL
  14. #define NULL 0L
  15. #endif
  16. #ifndef offsetof
  17. #ifdef __compiler_offsetof
  18. #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
  19. #else
  20. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
  21. #endif
  22. #endif
  23. #ifndef container_of
  24. #define container_of(ptr, type, member) ({ \
  25. const typeof( ((type *)0)->member ) *__mptr = (ptr); \
  26. (type *)( (char *)__mptr - offsetof(type,member) );})
  27. #endif
  28. struct hlist_head {
  29. struct hlist_node *first;
  30. };
  31. struct hlist_node {
  32. struct hlist_node *next;
  33. struct hlist_node **pprev;
  34. };
  35. static inline int hlist_empty(const struct hlist_head *h)
  36. {
  37. return !h->first;
  38. }
  39. static inline int hlist_hashed(const struct hlist_node *n)
  40. {
  41. return n->pprev != NULL;
  42. }
  43. static inline void hlist_del(struct hlist_node *n)
  44. {
  45. struct hlist_node *next = n->next;
  46. struct hlist_node **pprev = n->pprev;
  47. *pprev = next;
  48. if (next)
  49. next->pprev = pprev;
  50. n->next = NULL;
  51. n->pprev = NULL;
  52. }
  53. static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
  54. {
  55. struct hlist_node *first = h->first;
  56. n->next = first;
  57. if (first)
  58. first->pprev = &n->next;
  59. n->pprev = &h->first;
  60. h->first = n;
  61. }
  62. static inline void hlist_add_after(struct hlist_node *n, struct hlist_node *prev)
  63. {
  64. n->next = prev->next;
  65. n->pprev = &prev->next;
  66. prev->next = n;
  67. }
  68. static inline struct hlist_node **hlist_tail_ptr(struct hlist_head *h)
  69. {
  70. struct hlist_node *n = h->first;
  71. if (n == NULL)
  72. return &h->first;
  73. while (n->next != NULL)
  74. n = n->next;
  75. return &n->next;
  76. }
  77. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
  78. #define hlist_for_each(pos, head) \
  79. for (pos = (head)->first; pos; pos = pos->next)
  80. #define hlist_for_each_safe(pos, n, head) \
  81. for (pos = (head)->first; pos && ({ n = pos->next; 1; }); pos = n)
  82. #define hlist_for_each_entry(tpos, pos, head, member) \
  83. for (pos = (head)->first; pos && \
  84. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  85. pos = pos->next)
  86. #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
  87. for (pos = (head)->first; \
  88. pos && ({ n = pos->next; 1; }) && \
  89. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  90. pos = n)
  91. struct list_head {
  92. struct list_head *next, *prev;
  93. };
  94. #define LIST_INITIALIZER(l) { .next = &l, .prev = &l }
  95. static inline void list_init(struct list_head *list)
  96. {
  97. list->next = list;
  98. list->prev = list;
  99. }
  100. static inline void __list_add(struct list_head *new,
  101. struct list_head *prev,
  102. struct list_head *next)
  103. {
  104. next->prev = new;
  105. new->next = next;
  106. new->prev = prev;
  107. prev->next = new;
  108. }
  109. static inline void list_add(struct list_head *new, struct list_head *head)
  110. {
  111. __list_add(new, head, head->next);
  112. }
  113. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  114. {
  115. __list_add(new, head->prev, head);
  116. }
  117. static inline void __list_del(struct list_head * prev, struct list_head * next)
  118. {
  119. next->prev = prev;
  120. prev->next = next;
  121. }
  122. static inline void list_del(struct list_head *entry)
  123. {
  124. __list_del(entry->prev, entry->next);
  125. entry->next = NULL;
  126. entry->prev = NULL;
  127. }
  128. static inline int list_hashed(const struct list_head *n)
  129. {
  130. return n->next != n && n->next != NULL;
  131. }
  132. static inline int list_empty(const struct list_head *n)
  133. {
  134. return !list_hashed(n);
  135. }
  136. #define list_next(ptr, type, member) \
  137. (list_hashed(ptr) ? container_of((ptr)->next,type,member) : NULL)
  138. #define list_entry(ptr, type, member) container_of(ptr,type,member)
  139. #define list_for_each(pos, head) \
  140. for (pos = (head)->next; pos != (head); pos = pos->next)
  141. #define list_for_each_safe(pos, n, head) \
  142. for (pos = (head)->next, n = pos->next; pos != (head); \
  143. pos = n, n = pos->next)
  144. #define list_for_each_entry(pos, head, member) \
  145. for (pos = list_entry((head)->next, typeof(*pos), member); \
  146. &pos->member != (head); \
  147. pos = list_entry(pos->member.next, typeof(*pos), member))
  148. #define list_for_each_entry_safe(pos, n, head, member) \
  149. for (pos = list_entry((head)->next, typeof(*pos), member), \
  150. n = list_entry(pos->member.next, typeof(*pos), member); \
  151. &pos->member != (head); \
  152. pos = n, n = list_entry(n->member.next, typeof(*n), member))
  153. #endif