queue.h 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241
  1. /*
  2. * Copyright (c) 1991, 1993
  3. * The Regents of the University of California. All rights reserved.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions
  7. * are met:
  8. * 1. Redistributions of source code must retain the above copyright
  9. * notice, this list of conditions and the following disclaimer.
  10. * 2. Redistributions in binary form must reproduce the above copyright
  11. * notice, this list of conditions and the following disclaimer in the
  12. * documentation and/or other materials provided with the distribution.
  13. * 4. Neither the name of the University nor the names of its contributors
  14. * may be used to endorse or promote products derived from this software
  15. * without specific prior written permission.
  16. *
  17. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20. * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27. * SUCH DAMAGE.
  28. *
  29. * @(#)queue.h 8.3 (Berkeley) 12/13/93
  30. */
  31. #ifndef _SYS_QUEUE_H
  32. #define _SYS_QUEUE_H 1
  33. /*
  34. * This file defines three types of data structures: lists, tail queues,
  35. * and circular queues.
  36. *
  37. * A list is headed by a single forward pointer (or an array of forward
  38. * pointers for a hash table header). The elements are doubly linked
  39. * so that an arbitrary element can be removed without a need to
  40. * traverse the list. New elements can be added to the list after
  41. * an existing element or at the head of the list. A list may only be
  42. * traversed in the forward direction.
  43. *
  44. * A tail queue is headed by a pair of pointers, one to the head of the
  45. * list and the other to the tail of the list. The elements are doubly
  46. * linked so that an arbitrary element can be removed without a need to
  47. * traverse the list. New elements can be added to the list after
  48. * an existing element, at the head of the list, or at the end of the
  49. * list. A tail queue may only be traversed in the forward direction.
  50. *
  51. * A circle queue is headed by a pair of pointers, one to the head of the
  52. * list and the other to the tail of the list. The elements are doubly
  53. * linked so that an arbitrary element can be removed without a need to
  54. * traverse the list. New elements can be added to the list before or after
  55. * an existing element, at the head of the list, or at the end of the list.
  56. * A circle queue may be traversed in either direction, but has a more
  57. * complex end of list detection.
  58. *
  59. * For details on the use of these macros, see the queue(3) manual page.
  60. */
  61. /*
  62. * List definitions.
  63. */
  64. #define LIST_HEAD(name, type) \
  65. struct name { \
  66. struct type *lh_first; /* first element */ \
  67. }
  68. #define LIST_ENTRY(type) \
  69. struct { \
  70. struct type *le_next; /* next element */ \
  71. struct type **le_prev; /* address of previous next element */ \
  72. }
  73. /*
  74. * List functions.
  75. */
  76. #define LIST_INIT(head) { \
  77. (head)->lh_first = NULL; \
  78. }
  79. #define LIST_INSERT_AFTER(listelm, elm, field) { \
  80. if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
  81. (listelm)->field.le_next->field.le_prev = \
  82. &(elm)->field.le_next; \
  83. (listelm)->field.le_next = (elm); \
  84. (elm)->field.le_prev = &(listelm)->field.le_next; \
  85. }
  86. #define LIST_INSERT_HEAD(head, elm, field) { \
  87. if (((elm)->field.le_next = (head)->lh_first) != NULL) \
  88. (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
  89. (head)->lh_first = (elm); \
  90. (elm)->field.le_prev = &(head)->lh_first; \
  91. }
  92. #define LIST_REMOVE(elm, field) { \
  93. if ((elm)->field.le_next != NULL) \
  94. (elm)->field.le_next->field.le_prev = \
  95. (elm)->field.le_prev; \
  96. *(elm)->field.le_prev = (elm)->field.le_next; \
  97. }
  98. /*
  99. * Tail queue definitions.
  100. */
  101. #define TAILQ_HEAD(name, type) \
  102. struct name { \
  103. struct type *tqh_first; /* first element */ \
  104. struct type **tqh_last; /* addr of last next element */ \
  105. }
  106. #define TAILQ_ENTRY(type) \
  107. struct { \
  108. struct type *tqe_next; /* next element */ \
  109. struct type **tqe_prev; /* address of previous next element */ \
  110. }
  111. /*
  112. * Tail queue functions.
  113. */
  114. #define TAILQ_INIT(head) { \
  115. (head)->tqh_first = NULL; \
  116. (head)->tqh_last = &(head)->tqh_first; \
  117. }
  118. #define TAILQ_INSERT_HEAD(head, elm, field) { \
  119. if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
  120. (elm)->field.tqe_next->field.tqe_prev = \
  121. &(elm)->field.tqe_next; \
  122. else \
  123. (head)->tqh_last = &(elm)->field.tqe_next; \
  124. (head)->tqh_first = (elm); \
  125. (elm)->field.tqe_prev = &(head)->tqh_first; \
  126. }
  127. #define TAILQ_INSERT_TAIL(head, elm, field) { \
  128. (elm)->field.tqe_next = NULL; \
  129. (elm)->field.tqe_prev = (head)->tqh_last; \
  130. *(head)->tqh_last = (elm); \
  131. (head)->tqh_last = &(elm)->field.tqe_next; \
  132. }
  133. #define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \
  134. if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
  135. (elm)->field.tqe_next->field.tqe_prev = \
  136. &(elm)->field.tqe_next; \
  137. else \
  138. (head)->tqh_last = &(elm)->field.tqe_next; \
  139. (listelm)->field.tqe_next = (elm); \
  140. (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
  141. }
  142. #define TAILQ_REMOVE(head, elm, field) { \
  143. if (((elm)->field.tqe_next) != NULL) \
  144. (elm)->field.tqe_next->field.tqe_prev = \
  145. (elm)->field.tqe_prev; \
  146. else \
  147. (head)->tqh_last = (elm)->field.tqe_prev; \
  148. *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
  149. }
  150. /*
  151. * Circular queue definitions.
  152. */
  153. #define CIRCLEQ_HEAD(name, type) \
  154. struct name { \
  155. struct type *cqh_first; /* first element */ \
  156. struct type *cqh_last; /* last element */ \
  157. }
  158. #define CIRCLEQ_ENTRY(type) \
  159. struct { \
  160. struct type *cqe_next; /* next element */ \
  161. struct type *cqe_prev; /* previous element */ \
  162. }
  163. /*
  164. * Circular queue functions.
  165. */
  166. #define CIRCLEQ_INIT(head) { \
  167. (head)->cqh_first = (void *)(head); \
  168. (head)->cqh_last = (void *)(head); \
  169. }
  170. #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \
  171. (elm)->field.cqe_next = (listelm)->field.cqe_next; \
  172. (elm)->field.cqe_prev = (listelm); \
  173. if ((listelm)->field.cqe_next == (void *)(head)) \
  174. (head)->cqh_last = (elm); \
  175. else \
  176. (listelm)->field.cqe_next->field.cqe_prev = (elm); \
  177. (listelm)->field.cqe_next = (elm); \
  178. }
  179. #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \
  180. (elm)->field.cqe_next = (listelm); \
  181. (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
  182. if ((listelm)->field.cqe_prev == (void *)(head)) \
  183. (head)->cqh_first = (elm); \
  184. else \
  185. (listelm)->field.cqe_prev->field.cqe_next = (elm); \
  186. (listelm)->field.cqe_prev = (elm); \
  187. }
  188. #define CIRCLEQ_INSERT_HEAD(head, elm, field) { \
  189. (elm)->field.cqe_next = (head)->cqh_first; \
  190. (elm)->field.cqe_prev = (void *)(head); \
  191. if ((head)->cqh_last == (void *)(head)) \
  192. (head)->cqh_last = (elm); \
  193. else \
  194. (head)->cqh_first->field.cqe_prev = (elm); \
  195. (head)->cqh_first = (elm); \
  196. }
  197. #define CIRCLEQ_INSERT_TAIL(head, elm, field) { \
  198. (elm)->field.cqe_next = (void *)(head); \
  199. (elm)->field.cqe_prev = (head)->cqh_last; \
  200. if ((head)->cqh_first == (void *)(head)) \
  201. (head)->cqh_first = (elm); \
  202. else \
  203. (head)->cqh_last->field.cqe_next = (elm); \
  204. (head)->cqh_last = (elm); \
  205. }
  206. #define CIRCLEQ_REMOVE(head, elm, field) { \
  207. if ((elm)->field.cqe_next == (void *)(head)) \
  208. (head)->cqh_last = (elm)->field.cqe_prev; \
  209. else \
  210. (elm)->field.cqe_next->field.cqe_prev = \
  211. (elm)->field.cqe_prev; \
  212. if ((elm)->field.cqe_prev == (void *)(head)) \
  213. (head)->cqh_first = (elm)->field.cqe_next; \
  214. else \
  215. (elm)->field.cqe_prev->field.cqe_next = \
  216. (elm)->field.cqe_next; \
  217. }
  218. #endif /* sys/queue.h */