1
0

queue.h 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574
  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. * 3. 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.5 (Berkeley) 8/20/94
  30. */
  31. #ifndef _SYS_QUEUE_H_
  32. #define _SYS_QUEUE_H_
  33. /*
  34. * This file defines five types of data structures: singly-linked lists,
  35. * lists, simple queues, tail queues, and circular queues.
  36. *
  37. * A singly-linked list is headed by a single forward pointer. The
  38. * elements are singly linked for minimum space and pointer manipulation
  39. * overhead at the expense of O(n) removal for arbitrary elements. New
  40. * elements can be added to the list after an existing element or at the
  41. * head of the list. Elements being removed from the head of the list
  42. * should use the explicit macro for this purpose for optimum
  43. * efficiency. A singly-linked list may only be traversed in the forward
  44. * direction. Singly-linked lists are ideal for applications with large
  45. * datasets and few or no removals or for implementing a LIFO queue.
  46. *
  47. * A list is headed by a single forward pointer (or an array of forward
  48. * pointers for a hash table header). The elements are doubly linked
  49. * so that an arbitrary element can be removed without a need to
  50. * traverse the list. New elements can be added to the list before
  51. * or after an existing element or at the head of the list. A list
  52. * may only be traversed in the forward direction.
  53. *
  54. * A simple queue is headed by a pair of pointers, one the head of the
  55. * list and the other to the tail of the list. The elements are singly
  56. * linked to save space, so elements can only be removed from the
  57. * head of the list. New elements can be added to the list after
  58. * an existing element, at the head of the list, or at the end of the
  59. * list. A simple queue may only be traversed in the forward direction.
  60. *
  61. * A tail queue is headed by a pair of pointers, one to the head of the
  62. * list and the other to the tail of the list. The elements are doubly
  63. * linked so that an arbitrary element can be removed without a need to
  64. * traverse the list. New elements can be added to the list before or
  65. * after an existing element, at the head of the list, or at the end of
  66. * the list. A tail queue may be traversed in either direction.
  67. *
  68. * A circle queue is headed by a pair of pointers, one to the head of the
  69. * list and the other to the tail of the list. The elements are doubly
  70. * linked so that an arbitrary element can be removed without a need to
  71. * traverse the list. New elements can be added to the list before or after
  72. * an existing element, at the head of the list, or at the end of the list.
  73. * A circle queue may be traversed in either direction, but has a more
  74. * complex end of list detection.
  75. *
  76. * For details on the use of these macros, see the queue(3) manual page.
  77. */
  78. /*
  79. * List definitions.
  80. */
  81. #define LIST_HEAD(name, type) \
  82. struct name { \
  83. struct type *lh_first; /* first element */ \
  84. }
  85. #define LIST_HEAD_INITIALIZER(head) \
  86. { NULL }
  87. #define LIST_ENTRY(type) \
  88. struct { \
  89. struct type *le_next; /* next element */ \
  90. struct type **le_prev; /* address of previous next element */ \
  91. }
  92. /*
  93. * List functions.
  94. */
  95. #define LIST_INIT(head) do { \
  96. (head)->lh_first = NULL; \
  97. } while (/*CONSTCOND*/0)
  98. #define LIST_INSERT_AFTER(listelm, elm, field) do { \
  99. if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
  100. (listelm)->field.le_next->field.le_prev = \
  101. &(elm)->field.le_next; \
  102. (listelm)->field.le_next = (elm); \
  103. (elm)->field.le_prev = &(listelm)->field.le_next; \
  104. } while (/*CONSTCOND*/0)
  105. #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
  106. (elm)->field.le_prev = (listelm)->field.le_prev; \
  107. (elm)->field.le_next = (listelm); \
  108. *(listelm)->field.le_prev = (elm); \
  109. (listelm)->field.le_prev = &(elm)->field.le_next; \
  110. } while (/*CONSTCOND*/0)
  111. #define LIST_INSERT_HEAD(head, elm, field) do { \
  112. if (((elm)->field.le_next = (head)->lh_first) != NULL) \
  113. (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
  114. (head)->lh_first = (elm); \
  115. (elm)->field.le_prev = &(head)->lh_first; \
  116. } while (/*CONSTCOND*/0)
  117. #define LIST_REMOVE(elm, field) do { \
  118. if ((elm)->field.le_next != NULL) \
  119. (elm)->field.le_next->field.le_prev = \
  120. (elm)->field.le_prev; \
  121. *(elm)->field.le_prev = (elm)->field.le_next; \
  122. } while (/*CONSTCOND*/0)
  123. #define LIST_FOREACH(var, head, field) \
  124. for ((var) = ((head)->lh_first); \
  125. (var); \
  126. (var) = ((var)->field.le_next))
  127. /*
  128. * List access methods.
  129. */
  130. #define LIST_EMPTY(head) ((head)->lh_first == NULL)
  131. #define LIST_FIRST(head) ((head)->lh_first)
  132. #define LIST_NEXT(elm, field) ((elm)->field.le_next)
  133. /*
  134. * Singly-linked List definitions.
  135. */
  136. #define SLIST_HEAD(name, type) \
  137. struct name { \
  138. struct type *slh_first; /* first element */ \
  139. }
  140. #define SLIST_HEAD_INITIALIZER(head) \
  141. { NULL }
  142. #define SLIST_ENTRY(type) \
  143. struct { \
  144. struct type *sle_next; /* next element */ \
  145. }
  146. /*
  147. * Singly-linked List functions.
  148. */
  149. #define SLIST_INIT(head) do { \
  150. (head)->slh_first = NULL; \
  151. } while (/*CONSTCOND*/0)
  152. #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
  153. (elm)->field.sle_next = (slistelm)->field.sle_next; \
  154. (slistelm)->field.sle_next = (elm); \
  155. } while (/*CONSTCOND*/0)
  156. #define SLIST_INSERT_HEAD(head, elm, field) do { \
  157. (elm)->field.sle_next = (head)->slh_first; \
  158. (head)->slh_first = (elm); \
  159. } while (/*CONSTCOND*/0)
  160. #define SLIST_REMOVE_HEAD(head, field) do { \
  161. (head)->slh_first = (head)->slh_first->field.sle_next; \
  162. } while (/*CONSTCOND*/0)
  163. #define SLIST_REMOVE(head, elm, type, field) do { \
  164. if ((head)->slh_first == (elm)) { \
  165. SLIST_REMOVE_HEAD((head), field); \
  166. } \
  167. else { \
  168. struct type *curelm = (head)->slh_first; \
  169. while(curelm->field.sle_next != (elm)) \
  170. curelm = curelm->field.sle_next; \
  171. curelm->field.sle_next = \
  172. curelm->field.sle_next->field.sle_next; \
  173. } \
  174. } while (/*CONSTCOND*/0)
  175. #define SLIST_FOREACH(var, head, field) \
  176. for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
  177. /*
  178. * Singly-linked List access methods.
  179. */
  180. #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
  181. #define SLIST_FIRST(head) ((head)->slh_first)
  182. #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
  183. /*
  184. * Singly-linked Tail queue declarations.
  185. */
  186. #define STAILQ_HEAD(name, type) \
  187. struct name { \
  188. struct type *stqh_first; /* first element */ \
  189. struct type **stqh_last; /* addr of last next element */ \
  190. }
  191. #define STAILQ_HEAD_INITIALIZER(head) \
  192. { NULL, &(head).stqh_first }
  193. #define STAILQ_ENTRY(type) \
  194. struct { \
  195. struct type *stqe_next; /* next element */ \
  196. }
  197. /*
  198. * Singly-linked Tail queue functions.
  199. */
  200. #define STAILQ_INIT(head) do { \
  201. (head)->stqh_first = NULL; \
  202. (head)->stqh_last = &(head)->stqh_first; \
  203. } while (/*CONSTCOND*/0)
  204. #define STAILQ_INSERT_HEAD(head, elm, field) do { \
  205. if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
  206. (head)->stqh_last = &(elm)->field.stqe_next; \
  207. (head)->stqh_first = (elm); \
  208. } while (/*CONSTCOND*/0)
  209. #define STAILQ_INSERT_TAIL(head, elm, field) do { \
  210. (elm)->field.stqe_next = NULL; \
  211. *(head)->stqh_last = (elm); \
  212. (head)->stqh_last = &(elm)->field.stqe_next; \
  213. } while (/*CONSTCOND*/0)
  214. #define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
  215. if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
  216. (head)->stqh_last = &(elm)->field.stqe_next; \
  217. (listelm)->field.stqe_next = (elm); \
  218. } while (/*CONSTCOND*/0)
  219. #define STAILQ_REMOVE_HEAD(head, field) do { \
  220. if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
  221. (head)->stqh_last = &(head)->stqh_first; \
  222. } while (/*CONSTCOND*/0)
  223. #define STAILQ_REMOVE(head, elm, type, field) do { \
  224. if ((head)->stqh_first == (elm)) { \
  225. STAILQ_REMOVE_HEAD((head), field); \
  226. } else { \
  227. struct type *curelm = (head)->stqh_first; \
  228. while (curelm->field.stqe_next != (elm)) \
  229. curelm = curelm->field.stqe_next; \
  230. if ((curelm->field.stqe_next = \
  231. curelm->field.stqe_next->field.stqe_next) == NULL) \
  232. (head)->stqh_last = &(curelm)->field.stqe_next; \
  233. } \
  234. } while (/*CONSTCOND*/0)
  235. #define STAILQ_FOREACH(var, head, field) \
  236. for ((var) = ((head)->stqh_first); \
  237. (var); \
  238. (var) = ((var)->field.stqe_next))
  239. #define STAILQ_CONCAT(head1, head2) do { \
  240. if (!STAILQ_EMPTY((head2))) { \
  241. *(head1)->stqh_last = (head2)->stqh_first; \
  242. (head1)->stqh_last = (head2)->stqh_last; \
  243. STAILQ_INIT((head2)); \
  244. } \
  245. } while (/*CONSTCOND*/0)
  246. /*
  247. * Singly-linked Tail queue access methods.
  248. */
  249. #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
  250. #define STAILQ_FIRST(head) ((head)->stqh_first)
  251. #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
  252. /*
  253. * Simple queue definitions.
  254. */
  255. #define SIMPLEQ_HEAD(name, type) \
  256. struct name { \
  257. struct type *sqh_first; /* first element */ \
  258. struct type **sqh_last; /* addr of last next element */ \
  259. }
  260. #define SIMPLEQ_HEAD_INITIALIZER(head) \
  261. { NULL, &(head).sqh_first }
  262. #define SIMPLEQ_ENTRY(type) \
  263. struct { \
  264. struct type *sqe_next; /* next element */ \
  265. }
  266. /*
  267. * Simple queue functions.
  268. */
  269. #define SIMPLEQ_INIT(head) do { \
  270. (head)->sqh_first = NULL; \
  271. (head)->sqh_last = &(head)->sqh_first; \
  272. } while (/*CONSTCOND*/0)
  273. #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
  274. if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
  275. (head)->sqh_last = &(elm)->field.sqe_next; \
  276. (head)->sqh_first = (elm); \
  277. } while (/*CONSTCOND*/0)
  278. #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
  279. (elm)->field.sqe_next = NULL; \
  280. *(head)->sqh_last = (elm); \
  281. (head)->sqh_last = &(elm)->field.sqe_next; \
  282. } while (/*CONSTCOND*/0)
  283. #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
  284. if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
  285. (head)->sqh_last = &(elm)->field.sqe_next; \
  286. (listelm)->field.sqe_next = (elm); \
  287. } while (/*CONSTCOND*/0)
  288. #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
  289. if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
  290. (head)->sqh_last = &(head)->sqh_first; \
  291. } while (/*CONSTCOND*/0)
  292. #define SIMPLEQ_REMOVE(head, elm, type, field) do { \
  293. if ((head)->sqh_first == (elm)) { \
  294. SIMPLEQ_REMOVE_HEAD((head), field); \
  295. } else { \
  296. struct type *curelm = (head)->sqh_first; \
  297. while (curelm->field.sqe_next != (elm)) \
  298. curelm = curelm->field.sqe_next; \
  299. if ((curelm->field.sqe_next = \
  300. curelm->field.sqe_next->field.sqe_next) == NULL) \
  301. (head)->sqh_last = &(curelm)->field.sqe_next; \
  302. } \
  303. } while (/*CONSTCOND*/0)
  304. #define SIMPLEQ_FOREACH(var, head, field) \
  305. for ((var) = ((head)->sqh_first); \
  306. (var); \
  307. (var) = ((var)->field.sqe_next))
  308. /*
  309. * Simple queue access methods.
  310. */
  311. #define SIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)
  312. #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
  313. #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
  314. /*
  315. * Tail queue definitions.
  316. */
  317. #define _TAILQ_HEAD(name, type, qual) \
  318. struct name { \
  319. qual type *tqh_first; /* first element */ \
  320. qual type *qual *tqh_last; /* addr of last next element */ \
  321. }
  322. #define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,)
  323. #define TAILQ_HEAD_INITIALIZER(head) \
  324. { NULL, &(head).tqh_first }
  325. #define _TAILQ_ENTRY(type, qual) \
  326. struct { \
  327. qual type *tqe_next; /* next element */ \
  328. qual type *qual *tqe_prev; /* address of previous next element */\
  329. }
  330. #define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,)
  331. /*
  332. * Tail queue functions.
  333. */
  334. #define TAILQ_INIT(head) do { \
  335. (head)->tqh_first = NULL; \
  336. (head)->tqh_last = &(head)->tqh_first; \
  337. } while (/*CONSTCOND*/0)
  338. #define TAILQ_INSERT_HEAD(head, elm, field) do { \
  339. if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
  340. (head)->tqh_first->field.tqe_prev = \
  341. &(elm)->field.tqe_next; \
  342. else \
  343. (head)->tqh_last = &(elm)->field.tqe_next; \
  344. (head)->tqh_first = (elm); \
  345. (elm)->field.tqe_prev = &(head)->tqh_first; \
  346. } while (/*CONSTCOND*/0)
  347. #define TAILQ_INSERT_TAIL(head, elm, field) do { \
  348. (elm)->field.tqe_next = NULL; \
  349. (elm)->field.tqe_prev = (head)->tqh_last; \
  350. *(head)->tqh_last = (elm); \
  351. (head)->tqh_last = &(elm)->field.tqe_next; \
  352. } while (/*CONSTCOND*/0)
  353. #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
  354. if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
  355. (elm)->field.tqe_next->field.tqe_prev = \
  356. &(elm)->field.tqe_next; \
  357. else \
  358. (head)->tqh_last = &(elm)->field.tqe_next; \
  359. (listelm)->field.tqe_next = (elm); \
  360. (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
  361. } while (/*CONSTCOND*/0)
  362. #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
  363. (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
  364. (elm)->field.tqe_next = (listelm); \
  365. *(listelm)->field.tqe_prev = (elm); \
  366. (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
  367. } while (/*CONSTCOND*/0)
  368. #define TAILQ_REMOVE(head, elm, field) do { \
  369. if (((elm)->field.tqe_next) != NULL) \
  370. (elm)->field.tqe_next->field.tqe_prev = \
  371. (elm)->field.tqe_prev; \
  372. else \
  373. (head)->tqh_last = (elm)->field.tqe_prev; \
  374. *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
  375. } while (/*CONSTCOND*/0)
  376. #define TAILQ_FOREACH(var, head, field) \
  377. for ((var) = ((head)->tqh_first); \
  378. (var); \
  379. (var) = ((var)->field.tqe_next))
  380. #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
  381. for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \
  382. (var); \
  383. (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
  384. #define TAILQ_CONCAT(head1, head2, field) do { \
  385. if (!TAILQ_EMPTY(head2)) { \
  386. *(head1)->tqh_last = (head2)->tqh_first; \
  387. (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
  388. (head1)->tqh_last = (head2)->tqh_last; \
  389. TAILQ_INIT((head2)); \
  390. } \
  391. } while (/*CONSTCOND*/0)
  392. /*
  393. * Tail queue access methods.
  394. */
  395. #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
  396. #define TAILQ_FIRST(head) ((head)->tqh_first)
  397. #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
  398. #define TAILQ_LAST(head, headname) \
  399. (*(((struct headname *)((head)->tqh_last))->tqh_last))
  400. #define TAILQ_PREV(elm, headname, field) \
  401. (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
  402. /*
  403. * Circular queue definitions.
  404. */
  405. #define CIRCLEQ_HEAD(name, type) \
  406. struct name { \
  407. struct type *cqh_first; /* first element */ \
  408. struct type *cqh_last; /* last element */ \
  409. }
  410. #define CIRCLEQ_HEAD_INITIALIZER(head) \
  411. { (void *)&head, (void *)&head }
  412. #define CIRCLEQ_ENTRY(type) \
  413. struct { \
  414. struct type *cqe_next; /* next element */ \
  415. struct type *cqe_prev; /* previous element */ \
  416. }
  417. /*
  418. * Circular queue functions.
  419. */
  420. #define CIRCLEQ_INIT(head) do { \
  421. (head)->cqh_first = (void *)(head); \
  422. (head)->cqh_last = (void *)(head); \
  423. } while (/*CONSTCOND*/0)
  424. #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
  425. (elm)->field.cqe_next = (listelm)->field.cqe_next; \
  426. (elm)->field.cqe_prev = (listelm); \
  427. if ((listelm)->field.cqe_next == (void *)(head)) \
  428. (head)->cqh_last = (elm); \
  429. else \
  430. (listelm)->field.cqe_next->field.cqe_prev = (elm); \
  431. (listelm)->field.cqe_next = (elm); \
  432. } while (/*CONSTCOND*/0)
  433. #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
  434. (elm)->field.cqe_next = (listelm); \
  435. (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
  436. if ((listelm)->field.cqe_prev == (void *)(head)) \
  437. (head)->cqh_first = (elm); \
  438. else \
  439. (listelm)->field.cqe_prev->field.cqe_next = (elm); \
  440. (listelm)->field.cqe_prev = (elm); \
  441. } while (/*CONSTCOND*/0)
  442. #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
  443. (elm)->field.cqe_next = (head)->cqh_first; \
  444. (elm)->field.cqe_prev = (void *)(head); \
  445. if ((head)->cqh_last == (void *)(head)) \
  446. (head)->cqh_last = (elm); \
  447. else \
  448. (head)->cqh_first->field.cqe_prev = (elm); \
  449. (head)->cqh_first = (elm); \
  450. } while (/*CONSTCOND*/0)
  451. #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
  452. (elm)->field.cqe_next = (void *)(head); \
  453. (elm)->field.cqe_prev = (head)->cqh_last; \
  454. if ((head)->cqh_first == (void *)(head)) \
  455. (head)->cqh_first = (elm); \
  456. else \
  457. (head)->cqh_last->field.cqe_next = (elm); \
  458. (head)->cqh_last = (elm); \
  459. } while (/*CONSTCOND*/0)
  460. #define CIRCLEQ_REMOVE(head, elm, field) do { \
  461. if ((elm)->field.cqe_next == (void *)(head)) \
  462. (head)->cqh_last = (elm)->field.cqe_prev; \
  463. else \
  464. (elm)->field.cqe_next->field.cqe_prev = \
  465. (elm)->field.cqe_prev; \
  466. if ((elm)->field.cqe_prev == (void *)(head)) \
  467. (head)->cqh_first = (elm)->field.cqe_next; \
  468. else \
  469. (elm)->field.cqe_prev->field.cqe_next = \
  470. (elm)->field.cqe_next; \
  471. } while (/*CONSTCOND*/0)
  472. #define CIRCLEQ_FOREACH(var, head, field) \
  473. for ((var) = ((head)->cqh_first); \
  474. (var) != (const void *)(head); \
  475. (var) = ((var)->field.cqe_next))
  476. #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
  477. for ((var) = ((head)->cqh_last); \
  478. (var) != (const void *)(head); \
  479. (var) = ((var)->field.cqe_prev))
  480. /*
  481. * Circular queue access methods.
  482. */
  483. #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
  484. #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
  485. #define CIRCLEQ_LAST(head) ((head)->cqh_last)
  486. #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
  487. #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
  488. #define CIRCLEQ_LOOP_NEXT(head, elm, field) \
  489. (((elm)->field.cqe_next == (void *)(head)) \
  490. ? ((head)->cqh_first) \
  491. : (elm->field.cqe_next))
  492. #define CIRCLEQ_LOOP_PREV(head, elm, field) \
  493. (((elm)->field.cqe_prev == (void *)(head)) \
  494. ? ((head)->cqh_last) \
  495. : (elm->field.cqe_prev))
  496. #endif /* sys/queue.h */