list.h 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213
  1. /* SPDX-License-Identifier: GPL-2.0 */
  2. #ifndef LIST_H
  3. #define LIST_H
  4. #include <stdbool.h>
  5. #include <stddef.h>
  6. /* Are two types/vars the same type (ignoring qualifiers)? */
  7. #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
  8. /**
  9. * container_of - cast a member of a structure out to the containing structure
  10. * @ptr: the pointer to the member.
  11. * @type: the type of the container struct this is embedded in.
  12. * @member: the name of the member within the struct.
  13. *
  14. */
  15. #define container_of(ptr, type, member) ({ \
  16. void *__mptr = (void *)(ptr); \
  17. _Static_assert(__same_type(*(ptr), ((type *)0)->member) || \
  18. __same_type(*(ptr), void), \
  19. "pointer type mismatch in container_of()"); \
  20. ((type *)(__mptr - offsetof(type, member))); })
  21. #define LIST_POISON1 ((void *) 0x100)
  22. #define LIST_POISON2 ((void *) 0x122)
  23. /*
  24. * Circular doubly linked list implementation.
  25. *
  26. * Some of the internal functions ("__xxx") are useful when
  27. * manipulating whole lists rather than single entries, as
  28. * sometimes we already know the next/prev entries and we can
  29. * generate better code by using them directly rather than
  30. * using the generic single-entry routines.
  31. */
  32. struct list_head {
  33. struct list_head *next, *prev;
  34. };
  35. #define LIST_HEAD_INIT(name) { &(name), &(name) }
  36. #define LIST_HEAD(name) \
  37. struct list_head name = LIST_HEAD_INIT(name)
  38. /**
  39. * INIT_LIST_HEAD - Initialize a list_head structure
  40. * @list: list_head structure to be initialized.
  41. *
  42. * Initializes the list_head to point to itself. If it is a list header,
  43. * the result is an empty list.
  44. */
  45. static inline void INIT_LIST_HEAD(struct list_head *list)
  46. {
  47. list->next = list;
  48. list->prev = list;
  49. }
  50. /*
  51. * Insert a new entry between two known consecutive entries.
  52. *
  53. * This is only for internal list manipulation where we know
  54. * the prev/next entries already!
  55. */
  56. static inline void __list_add(struct list_head *new,
  57. struct list_head *prev,
  58. struct list_head *next)
  59. {
  60. next->prev = new;
  61. new->next = next;
  62. new->prev = prev;
  63. prev->next = new;
  64. }
  65. /**
  66. * list_add - add a new entry
  67. * @new: new entry to be added
  68. * @head: list head to add it after
  69. *
  70. * Insert a new entry after the specified head.
  71. * This is good for implementing stacks.
  72. */
  73. static inline void list_add(struct list_head *new, struct list_head *head)
  74. {
  75. __list_add(new, head, head->next);
  76. }
  77. /**
  78. * list_add_tail - add a new entry
  79. * @new: new entry to be added
  80. * @head: list head to add it before
  81. *
  82. * Insert a new entry before the specified head.
  83. * This is useful for implementing queues.
  84. */
  85. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  86. {
  87. __list_add(new, head->prev, head);
  88. }
  89. /*
  90. * Delete a list entry by making the prev/next entries
  91. * point to each other.
  92. *
  93. * This is only for internal list manipulation where we know
  94. * the prev/next entries already!
  95. */
  96. static inline void __list_del(struct list_head *prev, struct list_head *next)
  97. {
  98. next->prev = prev;
  99. prev->next = next;
  100. }
  101. static inline void __list_del_entry(struct list_head *entry)
  102. {
  103. __list_del(entry->prev, entry->next);
  104. }
  105. /**
  106. * list_del - deletes entry from list.
  107. * @entry: the element to delete from the list.
  108. * Note: list_empty() on entry does not return true after this, the entry is
  109. * in an undefined state.
  110. */
  111. static inline void list_del(struct list_head *entry)
  112. {
  113. __list_del_entry(entry);
  114. entry->next = LIST_POISON1;
  115. entry->prev = LIST_POISON2;
  116. }
  117. /**
  118. * list_is_head - tests whether @list is the list @head
  119. * @list: the entry to test
  120. * @head: the head of the list
  121. */
  122. static inline int list_is_head(const struct list_head *list, const struct list_head *head)
  123. {
  124. return list == head;
  125. }
  126. /**
  127. * list_empty - tests whether a list is empty
  128. * @head: the list to test.
  129. */
  130. static inline int list_empty(const struct list_head *head)
  131. {
  132. return head->next == head;
  133. }
  134. /**
  135. * list_entry - get the struct for this entry
  136. * @ptr: the &struct list_head pointer.
  137. * @type: the type of the struct this is embedded in.
  138. * @member: the name of the list_head within the struct.
  139. */
  140. #define list_entry(ptr, type, member) \
  141. container_of(ptr, type, member)
  142. /**
  143. * list_first_entry - get the first element from a list
  144. * @ptr: the list head to take the element from.
  145. * @type: the type of the struct this is embedded in.
  146. * @member: the name of the list_head within the struct.
  147. *
  148. * Note, that list is expected to be not empty.
  149. */
  150. #define list_first_entry(ptr, type, member) \
  151. list_entry((ptr)->next, type, member)
  152. /**
  153. * list_next_entry - get the next element in list
  154. * @pos: the type * to cursor
  155. * @member: the name of the list_head within the struct.
  156. */
  157. #define list_next_entry(pos, member) \
  158. list_entry((pos)->member.next, typeof(*(pos)), member)
  159. /**
  160. * list_entry_is_head - test if the entry points to the head of the list
  161. * @pos: the type * to cursor
  162. * @head: the head for your list.
  163. * @member: the name of the list_head within the struct.
  164. */
  165. #define list_entry_is_head(pos, head, member) \
  166. (&pos->member == (head))
  167. /**
  168. * list_for_each_entry - iterate over list of given type
  169. * @pos: the type * to use as a loop cursor.
  170. * @head: the head for your list.
  171. * @member: the name of the list_head within the struct.
  172. */
  173. #define list_for_each_entry(pos, head, member) \
  174. for (pos = list_first_entry(head, typeof(*pos), member); \
  175. !list_entry_is_head(pos, head, member); \
  176. pos = list_next_entry(pos, member))
  177. /**
  178. * list_for_each_entry_safe - iterate over list of given type. Safe against removal of list entry
  179. * @pos: the type * to use as a loop cursor.
  180. * @n: another type * to use as temporary storage
  181. * @head: the head for your list.
  182. * @member: the name of the list_head within the struct.
  183. */
  184. #define list_for_each_entry_safe(pos, n, head, member) \
  185. for (pos = list_first_entry(head, typeof(*pos), member), \
  186. n = list_next_entry(pos, member); \
  187. !list_entry_is_head(pos, head, member); \
  188. pos = n, n = list_next_entry(n, member))
  189. #endif /* LIST_H */