queue.h 19 KB

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