queue.h 6.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204
  1. #ifndef _SYS_QUEUE_H_
  2. #define _SYS_QUEUE_H_
  3. #define QMD_SAVELINK(name, link)
  4. #define TRASHIT(x)
  5. /*
  6. * Singly-linked List declarations.
  7. */
  8. #define SLIST_HEAD(name, type) \
  9. struct name { \
  10. struct type *slh_first; /* first element */ \
  11. }
  12. #define SLIST_HEAD_INITIALIZER(head) \
  13. { NULL }
  14. #define SLIST_ENTRY(type) \
  15. struct { \
  16. struct type *sle_next; /* next element */ \
  17. }
  18. /*
  19. * Singly-linked List functions.
  20. */
  21. #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
  22. #define SLIST_FIRST(head) ((head)->slh_first)
  23. #define SLIST_FOREACH(var, head, field) \
  24. for ((var) = SLIST_FIRST((head)); \
  25. (var); \
  26. (var) = SLIST_NEXT((var), field))
  27. #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
  28. for ((var) = SLIST_FIRST((head)); \
  29. (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
  30. (var) = (tvar))
  31. #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
  32. for ((varp) = &SLIST_FIRST((head)); \
  33. ((var) = *(varp)) != NULL; \
  34. (varp) = &SLIST_NEXT((var), field))
  35. #define SLIST_INIT(head) do { \
  36. SLIST_FIRST((head)) = NULL; \
  37. } while (0)
  38. #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
  39. SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
  40. SLIST_NEXT((slistelm), field) = (elm); \
  41. } while (0)
  42. #define SLIST_INSERT_HEAD(head, elm, field) do { \
  43. SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
  44. SLIST_FIRST((head)) = (elm); \
  45. } while (0)
  46. #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
  47. #define SLIST_REMOVE(head, elm, type, field) do { \
  48. QMD_SAVELINK(oldnext, (elm)->field.sle_next); \
  49. if (SLIST_FIRST((head)) == (elm)) { \
  50. SLIST_REMOVE_HEAD((head), field); \
  51. } \
  52. else { \
  53. struct type *curelm = SLIST_FIRST((head)); \
  54. while (SLIST_NEXT(curelm, field) != (elm)) \
  55. curelm = SLIST_NEXT(curelm, field); \
  56. SLIST_REMOVE_AFTER(curelm, field); \
  57. } \
  58. TRASHIT(*oldnext); \
  59. } while (0)
  60. #define SLIST_REMOVE_AFTER(elm, field) do { \
  61. SLIST_NEXT(elm, field) = \
  62. SLIST_NEXT(SLIST_NEXT(elm, field), field); \
  63. } while (0)
  64. #define SLIST_REMOVE_HEAD(head, field) do { \
  65. SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
  66. } while (0)
  67. /*
  68. * Singly-linked Tail queue declarations.
  69. */
  70. #define STAILQ_HEAD(name, type) \
  71. struct name { \
  72. struct type *stqh_first;/* first element */ \
  73. struct type **stqh_last;/* addr of last next element */ \
  74. }
  75. #define STAILQ_HEAD_INITIALIZER(head) \
  76. { NULL, &(head).stqh_first }
  77. #define STAILQ_ENTRY(type) \
  78. struct { \
  79. struct type *stqe_next; /* next element */ \
  80. }
  81. /*
  82. * Singly-linked Tail queue functions.
  83. */
  84. #define STAILQ_CONCAT(head1, head2) do { \
  85. if (!STAILQ_EMPTY((head2))) { \
  86. *(head1)->stqh_last = (head2)->stqh_first; \
  87. (head1)->stqh_last = (head2)->stqh_last; \
  88. STAILQ_INIT((head2)); \
  89. } \
  90. } while (0)
  91. #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
  92. #define STAILQ_FIRST(head) ((head)->stqh_first)
  93. #define STAILQ_FOREACH(var, head, field) \
  94. for((var) = STAILQ_FIRST((head)); \
  95. (var); \
  96. (var) = STAILQ_NEXT((var), field))
  97. #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
  98. for ((var) = STAILQ_FIRST((head)); \
  99. (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
  100. (var) = (tvar))
  101. #define STAILQ_INIT(head) do { \
  102. STAILQ_FIRST((head)) = NULL; \
  103. (head)->stqh_last = &STAILQ_FIRST((head)); \
  104. } while (0)
  105. #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
  106. if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
  107. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  108. STAILQ_NEXT((tqelm), field) = (elm); \
  109. } while (0)
  110. #define STAILQ_INSERT_HEAD(head, elm, field) do { \
  111. if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
  112. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  113. STAILQ_FIRST((head)) = (elm); \
  114. } while (0)
  115. #define STAILQ_INSERT_TAIL(head, elm, field) do { \
  116. STAILQ_NEXT((elm), field) = NULL; \
  117. *(head)->stqh_last = (elm); \
  118. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  119. } while (0)
  120. #define STAILQ_LAST(head, type, field) \
  121. (STAILQ_EMPTY((head)) ? \
  122. NULL : \
  123. ((struct type *)(void *) \
  124. ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
  125. #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
  126. #define STAILQ_REMOVE(head, elm, type, field) do { \
  127. QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \
  128. if (STAILQ_FIRST((head)) == (elm)) { \
  129. STAILQ_REMOVE_HEAD((head), field); \
  130. } \
  131. else { \
  132. struct type *curelm = STAILQ_FIRST((head)); \
  133. while (STAILQ_NEXT(curelm, field) != (elm)) \
  134. curelm = STAILQ_NEXT(curelm, field); \
  135. STAILQ_REMOVE_AFTER(head, curelm, field); \
  136. } \
  137. TRASHIT(*oldnext); \
  138. } while (0)
  139. #define STAILQ_REMOVE_HEAD(head, field) do { \
  140. if ((STAILQ_FIRST((head)) = \
  141. STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
  142. (head)->stqh_last = &STAILQ_FIRST((head)); \
  143. } while (0)
  144. #define STAILQ_REMOVE_AFTER(head, elm, field) do { \
  145. if ((STAILQ_NEXT(elm, field) = \
  146. STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \
  147. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  148. } while (0)
  149. #define STAILQ_SWAP(head1, head2, type) do { \
  150. struct type *swap_first = STAILQ_FIRST(head1); \
  151. struct type **swap_last = (head1)->stqh_last; \
  152. STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \
  153. (head1)->stqh_last = (head2)->stqh_last; \
  154. STAILQ_FIRST(head2) = swap_first; \
  155. (head2)->stqh_last = swap_last; \
  156. if (STAILQ_EMPTY(head1)) \
  157. (head1)->stqh_last = &STAILQ_FIRST(head1); \
  158. if (STAILQ_EMPTY(head2)) \
  159. (head2)->stqh_last = &STAILQ_FIRST(head2); \
  160. } while (0)
  161. #define STAILQ_INSERT_CHAIN_HEAD(head, elm_chead, elm_ctail, field) do { \
  162. if ((STAILQ_NEXT(elm_ctail, field) = STAILQ_FIRST(head)) == NULL ) { \
  163. (head)->stqh_last = &STAILQ_NEXT(elm_ctail, field); \
  164. } \
  165. STAILQ_FIRST(head) = (elm_chead); \
  166. } while (0)
  167. #endif /* !_SYS_QUEUE_H_ */