queue.h 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649
  1. /* $OpenBSD: queue.h,v 1.38 2013/07/03 15:05:21 fgsch Exp $ */
  2. /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
  3. /*
  4. * Copyright (c) 1991, 1993
  5. * The Regents of the University of California. All rights reserved.
  6. *
  7. * Redistribution and use in source and binary forms, with or without
  8. * modification, are permitted provided that the following conditions
  9. * are met:
  10. * 1. Redistributions of source code must retain the above copyright
  11. * notice, this list of conditions and the following disclaimer.
  12. * 2. Redistributions in binary form must reproduce the above copyright
  13. * notice, this list of conditions and the following disclaimer in the
  14. * documentation and/or other materials provided with the distribution.
  15. * 3. Neither the name of the University nor the names of its contributors
  16. * may be used to endorse or promote products derived from this software
  17. * without specific prior written permission.
  18. *
  19. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  20. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22. * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  23. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29. * SUCH DAMAGE.
  30. *
  31. * @(#)queue.h 8.5 (Berkeley) 8/20/94
  32. */
  33. #ifndef _SYS_QUEUE_H_
  34. #define _SYS_QUEUE_H_
  35. /*
  36. * This file defines five types of data structures: singly-linked lists,
  37. * lists, simple queues, tail queues, and circular queues.
  38. *
  39. *
  40. * A singly-linked list is headed by a single forward pointer. The elements
  41. * are singly linked for minimum space and pointer manipulation overhead at
  42. * the expense of O(n) removal for arbitrary elements. New elements can be
  43. * added to the list after an existing element or at the head of the list.
  44. * Elements being removed from the head of the list should use the explicit
  45. * macro for this purpose for optimum efficiency. A singly-linked list may
  46. * only be traversed in the forward direction. Singly-linked lists are ideal
  47. * for applications with large datasets and few or no removals or for
  48. * 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 before or 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. #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
  82. #define _Q_INVALIDATE(a) (a) = ((void *)-1)
  83. #else
  84. #define _Q_INVALIDATE(a)
  85. #endif
  86. /*
  87. * Singly-linked List definitions.
  88. */
  89. #define SLIST_HEAD(name, type) \
  90. struct name { \
  91. struct type *slh_first; /* first element */ \
  92. }
  93. #define SLIST_HEAD_INITIALIZER(head) \
  94. { NULL }
  95. #define SLIST_ENTRY(type) \
  96. struct { \
  97. struct type *sle_next; /* next element */ \
  98. }
  99. /*
  100. * Singly-linked List access methods.
  101. */
  102. #define SLIST_FIRST(head) ((head)->slh_first)
  103. #define SLIST_END(head) NULL
  104. #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
  105. #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
  106. #define SLIST_FOREACH(var, head, field) \
  107. for((var) = SLIST_FIRST(head); \
  108. (var) != SLIST_END(head); \
  109. (var) = SLIST_NEXT(var, field))
  110. #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
  111. for ((var) = SLIST_FIRST(head); \
  112. (var) && ((tvar) = SLIST_NEXT(var, field), 1); \
  113. (var) = (tvar))
  114. /*
  115. * Singly-linked List functions.
  116. */
  117. #define SLIST_INIT(head) { \
  118. SLIST_FIRST(head) = SLIST_END(head); \
  119. }
  120. #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
  121. (elm)->field.sle_next = (slistelm)->field.sle_next; \
  122. (slistelm)->field.sle_next = (elm); \
  123. } while (0)
  124. #define SLIST_INSERT_HEAD(head, elm, field) do { \
  125. (elm)->field.sle_next = (head)->slh_first; \
  126. (head)->slh_first = (elm); \
  127. } while (0)
  128. #define SLIST_REMOVE_AFTER(elm, field) do { \
  129. (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
  130. } while (0)
  131. #define SLIST_REMOVE_HEAD(head, field) do { \
  132. (head)->slh_first = (head)->slh_first->field.sle_next; \
  133. } while (0)
  134. #define SLIST_REMOVE(head, elm, type, field) do { \
  135. if ((head)->slh_first == (elm)) { \
  136. SLIST_REMOVE_HEAD((head), field); \
  137. } else { \
  138. struct type *curelm = (head)->slh_first; \
  139. \
  140. while (curelm->field.sle_next != (elm)) \
  141. curelm = curelm->field.sle_next; \
  142. curelm->field.sle_next = \
  143. curelm->field.sle_next->field.sle_next; \
  144. _Q_INVALIDATE((elm)->field.sle_next); \
  145. } \
  146. } while (0)
  147. /*
  148. * List definitions.
  149. */
  150. #define LIST_HEAD(name, type) \
  151. struct name { \
  152. struct type *lh_first; /* first element */ \
  153. }
  154. #define LIST_HEAD_INITIALIZER(head) \
  155. { NULL }
  156. #define LIST_ENTRY(type) \
  157. struct { \
  158. struct type *le_next; /* next element */ \
  159. struct type **le_prev; /* address of previous next element */ \
  160. }
  161. /*
  162. * List access methods
  163. */
  164. #define LIST_FIRST(head) ((head)->lh_first)
  165. #define LIST_END(head) NULL
  166. #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
  167. #define LIST_NEXT(elm, field) ((elm)->field.le_next)
  168. #define LIST_FOREACH(var, head, field) \
  169. for((var) = LIST_FIRST(head); \
  170. (var)!= LIST_END(head); \
  171. (var) = LIST_NEXT(var, field))
  172. #define LIST_FOREACH_SAFE(var, head, field, tvar) \
  173. for ((var) = LIST_FIRST(head); \
  174. (var) && ((tvar) = LIST_NEXT(var, field), 1); \
  175. (var) = (tvar))
  176. /*
  177. * List functions.
  178. */
  179. #define LIST_INIT(head) do { \
  180. LIST_FIRST(head) = LIST_END(head); \
  181. } while (0)
  182. #define LIST_INSERT_AFTER(listelm, elm, field) do { \
  183. if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
  184. (listelm)->field.le_next->field.le_prev = \
  185. &(elm)->field.le_next; \
  186. (listelm)->field.le_next = (elm); \
  187. (elm)->field.le_prev = &(listelm)->field.le_next; \
  188. } while (0)
  189. #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
  190. (elm)->field.le_prev = (listelm)->field.le_prev; \
  191. (elm)->field.le_next = (listelm); \
  192. *(listelm)->field.le_prev = (elm); \
  193. (listelm)->field.le_prev = &(elm)->field.le_next; \
  194. } while (0)
  195. #define LIST_INSERT_HEAD(head, elm, field) do { \
  196. if (((elm)->field.le_next = (head)->lh_first) != NULL) \
  197. (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
  198. (head)->lh_first = (elm); \
  199. (elm)->field.le_prev = &(head)->lh_first; \
  200. } while (0)
  201. #define LIST_REMOVE(elm, field) do { \
  202. if ((elm)->field.le_next != NULL) \
  203. (elm)->field.le_next->field.le_prev = \
  204. (elm)->field.le_prev; \
  205. *(elm)->field.le_prev = (elm)->field.le_next; \
  206. _Q_INVALIDATE((elm)->field.le_prev); \
  207. _Q_INVALIDATE((elm)->field.le_next); \
  208. } while (0)
  209. #define LIST_REPLACE(elm, elm2, field) do { \
  210. if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
  211. (elm2)->field.le_next->field.le_prev = \
  212. &(elm2)->field.le_next; \
  213. (elm2)->field.le_prev = (elm)->field.le_prev; \
  214. *(elm2)->field.le_prev = (elm2); \
  215. _Q_INVALIDATE((elm)->field.le_prev); \
  216. _Q_INVALIDATE((elm)->field.le_next); \
  217. } while (0)
  218. /*
  219. * Simple queue definitions.
  220. */
  221. #define SIMPLEQ_HEAD(name, type) \
  222. struct name { \
  223. struct type *sqh_first; /* first element */ \
  224. struct type **sqh_last; /* addr of last next element */ \
  225. }
  226. #define SIMPLEQ_HEAD_INITIALIZER(head) \
  227. { NULL, &(head).sqh_first }
  228. #define SIMPLEQ_ENTRY(type) \
  229. struct { \
  230. struct type *sqe_next; /* next element */ \
  231. }
  232. /*
  233. * Simple queue access methods.
  234. */
  235. #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
  236. #define SIMPLEQ_END(head) NULL
  237. #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
  238. #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
  239. #define SIMPLEQ_FOREACH(var, head, field) \
  240. for((var) = SIMPLEQ_FIRST(head); \
  241. (var) != SIMPLEQ_END(head); \
  242. (var) = SIMPLEQ_NEXT(var, field))
  243. #define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
  244. for ((var) = SIMPLEQ_FIRST(head); \
  245. (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \
  246. (var) = (tvar))
  247. /*
  248. * Simple queue functions.
  249. */
  250. #define SIMPLEQ_INIT(head) do { \
  251. (head)->sqh_first = NULL; \
  252. (head)->sqh_last = &(head)->sqh_first; \
  253. } while (0)
  254. #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
  255. if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
  256. (head)->sqh_last = &(elm)->field.sqe_next; \
  257. (head)->sqh_first = (elm); \
  258. } while (0)
  259. #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
  260. (elm)->field.sqe_next = NULL; \
  261. *(head)->sqh_last = (elm); \
  262. (head)->sqh_last = &(elm)->field.sqe_next; \
  263. } while (0)
  264. #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
  265. if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
  266. (head)->sqh_last = &(elm)->field.sqe_next; \
  267. (listelm)->field.sqe_next = (elm); \
  268. } while (0)
  269. #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
  270. if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
  271. (head)->sqh_last = &(head)->sqh_first; \
  272. } while (0)
  273. #define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
  274. if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
  275. == NULL) \
  276. (head)->sqh_last = &(elm)->field.sqe_next; \
  277. } while (0)
  278. /*
  279. * XOR Simple queue definitions.
  280. */
  281. #define XSIMPLEQ_HEAD(name, type) \
  282. struct name { \
  283. struct type *sqx_first; /* first element */ \
  284. struct type **sqx_last; /* addr of last next element */ \
  285. unsigned long sqx_cookie; \
  286. }
  287. #define XSIMPLEQ_ENTRY(type) \
  288. struct { \
  289. struct type *sqx_next; /* next element */ \
  290. }
  291. /*
  292. * XOR Simple queue access methods.
  293. */
  294. #define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \
  295. (unsigned long)(ptr)))
  296. #define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first))
  297. #define XSIMPLEQ_END(head) NULL
  298. #define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
  299. #define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
  300. #define XSIMPLEQ_FOREACH(var, head, field) \
  301. for ((var) = XSIMPLEQ_FIRST(head); \
  302. (var) != XSIMPLEQ_END(head); \
  303. (var) = XSIMPLEQ_NEXT(head, var, field))
  304. #define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
  305. for ((var) = XSIMPLEQ_FIRST(head); \
  306. (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \
  307. (var) = (tvar))
  308. /*
  309. * XOR Simple queue functions.
  310. */
  311. #define XSIMPLEQ_INIT(head) do { \
  312. arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
  313. (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \
  314. (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
  315. } while (0)
  316. #define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
  317. if (((elm)->field.sqx_next = (head)->sqx_first) == \
  318. XSIMPLEQ_XOR(head, NULL)) \
  319. (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
  320. (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \
  321. } while (0)
  322. #define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
  323. (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \
  324. *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
  325. (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
  326. } while (0)
  327. #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
  328. if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \
  329. XSIMPLEQ_XOR(head, NULL)) \
  330. (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
  331. (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \
  332. } while (0)
  333. #define XSIMPLEQ_REMOVE_HEAD(head, field) do { \
  334. if (((head)->sqx_first = XSIMPLEQ_XOR(head, \
  335. (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
  336. (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
  337. } while (0)
  338. #define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
  339. if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \
  340. (elm)->field.sqx_next)->field.sqx_next) \
  341. == XSIMPLEQ_XOR(head, NULL)) \
  342. (head)->sqx_last = \
  343. XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
  344. } while (0)
  345. /*
  346. * Tail queue definitions.
  347. */
  348. #define TAILQ_HEAD(name, type) \
  349. struct name { \
  350. struct type *tqh_first; /* first element */ \
  351. struct type **tqh_last; /* addr of last next element */ \
  352. }
  353. #define TAILQ_HEAD_INITIALIZER(head) \
  354. { NULL, &(head).tqh_first }
  355. #define TAILQ_ENTRY(type) \
  356. struct { \
  357. struct type *tqe_next; /* next element */ \
  358. struct type **tqe_prev; /* address of previous next element */ \
  359. }
  360. /*
  361. * tail queue access methods
  362. */
  363. #define TAILQ_FIRST(head) ((head)->tqh_first)
  364. #define TAILQ_END(head) NULL
  365. #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
  366. #define TAILQ_LAST(head, headname) \
  367. (*(((struct headname *)((head)->tqh_last))->tqh_last))
  368. /* XXX */
  369. #define TAILQ_PREV(elm, headname, field) \
  370. (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
  371. #define TAILQ_EMPTY(head) \
  372. (TAILQ_FIRST(head) == TAILQ_END(head))
  373. #define TAILQ_FOREACH(var, head, field) \
  374. for((var) = TAILQ_FIRST(head); \
  375. (var) != TAILQ_END(head); \
  376. (var) = TAILQ_NEXT(var, field))
  377. #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
  378. for ((var) = TAILQ_FIRST(head); \
  379. (var) != TAILQ_END(head) && \
  380. ((tvar) = TAILQ_NEXT(var, field), 1); \
  381. (var) = (tvar))
  382. #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
  383. for((var) = TAILQ_LAST(head, headname); \
  384. (var) != TAILQ_END(head); \
  385. (var) = TAILQ_PREV(var, headname, field))
  386. #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
  387. for ((var) = TAILQ_LAST(head, headname); \
  388. (var) != TAILQ_END(head) && \
  389. ((tvar) = TAILQ_PREV(var, headname, field), 1); \
  390. (var) = (tvar))
  391. /*
  392. * Tail queue functions.
  393. */
  394. #define TAILQ_INIT(head) do { \
  395. (head)->tqh_first = NULL; \
  396. (head)->tqh_last = &(head)->tqh_first; \
  397. } while (0)
  398. #define TAILQ_INSERT_HEAD(head, elm, field) do { \
  399. if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
  400. (head)->tqh_first->field.tqe_prev = \
  401. &(elm)->field.tqe_next; \
  402. else \
  403. (head)->tqh_last = &(elm)->field.tqe_next; \
  404. (head)->tqh_first = (elm); \
  405. (elm)->field.tqe_prev = &(head)->tqh_first; \
  406. } while (0)
  407. #define TAILQ_INSERT_TAIL(head, elm, field) do { \
  408. (elm)->field.tqe_next = NULL; \
  409. (elm)->field.tqe_prev = (head)->tqh_last; \
  410. *(head)->tqh_last = (elm); \
  411. (head)->tqh_last = &(elm)->field.tqe_next; \
  412. } while (0)
  413. #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
  414. if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
  415. (elm)->field.tqe_next->field.tqe_prev = \
  416. &(elm)->field.tqe_next; \
  417. else \
  418. (head)->tqh_last = &(elm)->field.tqe_next; \
  419. (listelm)->field.tqe_next = (elm); \
  420. (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
  421. } while (0)
  422. #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
  423. (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
  424. (elm)->field.tqe_next = (listelm); \
  425. *(listelm)->field.tqe_prev = (elm); \
  426. (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
  427. } while (0)
  428. #define TAILQ_REMOVE(head, elm, field) do { \
  429. if (((elm)->field.tqe_next) != NULL) \
  430. (elm)->field.tqe_next->field.tqe_prev = \
  431. (elm)->field.tqe_prev; \
  432. else \
  433. (head)->tqh_last = (elm)->field.tqe_prev; \
  434. *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
  435. _Q_INVALIDATE((elm)->field.tqe_prev); \
  436. _Q_INVALIDATE((elm)->field.tqe_next); \
  437. } while (0)
  438. #define TAILQ_REPLACE(head, elm, elm2, field) do { \
  439. if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
  440. (elm2)->field.tqe_next->field.tqe_prev = \
  441. &(elm2)->field.tqe_next; \
  442. else \
  443. (head)->tqh_last = &(elm2)->field.tqe_next; \
  444. (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
  445. *(elm2)->field.tqe_prev = (elm2); \
  446. _Q_INVALIDATE((elm)->field.tqe_prev); \
  447. _Q_INVALIDATE((elm)->field.tqe_next); \
  448. } while (0)
  449. /*
  450. * Circular queue definitions.
  451. */
  452. #define CIRCLEQ_HEAD(name, type) \
  453. struct name { \
  454. struct type *cqh_first; /* first element */ \
  455. struct type *cqh_last; /* last element */ \
  456. }
  457. #define CIRCLEQ_HEAD_INITIALIZER(head) \
  458. { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
  459. #define CIRCLEQ_ENTRY(type) \
  460. struct { \
  461. struct type *cqe_next; /* next element */ \
  462. struct type *cqe_prev; /* previous element */ \
  463. }
  464. /*
  465. * Circular queue access methods
  466. */
  467. #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
  468. #define CIRCLEQ_LAST(head) ((head)->cqh_last)
  469. #define CIRCLEQ_END(head) ((void *)(head))
  470. #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
  471. #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
  472. #define CIRCLEQ_EMPTY(head) \
  473. (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
  474. #define CIRCLEQ_FOREACH(var, head, field) \
  475. for((var) = CIRCLEQ_FIRST(head); \
  476. (var) != CIRCLEQ_END(head); \
  477. (var) = CIRCLEQ_NEXT(var, field))
  478. #define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \
  479. for ((var) = CIRCLEQ_FIRST(head); \
  480. (var) != CIRCLEQ_END(head) && \
  481. ((tvar) = CIRCLEQ_NEXT(var, field), 1); \
  482. (var) = (tvar))
  483. #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
  484. for((var) = CIRCLEQ_LAST(head); \
  485. (var) != CIRCLEQ_END(head); \
  486. (var) = CIRCLEQ_PREV(var, field))
  487. #define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
  488. for ((var) = CIRCLEQ_LAST(head, headname); \
  489. (var) != CIRCLEQ_END(head) && \
  490. ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \
  491. (var) = (tvar))
  492. /*
  493. * Circular queue functions.
  494. */
  495. #define CIRCLEQ_INIT(head) do { \
  496. (head)->cqh_first = CIRCLEQ_END(head); \
  497. (head)->cqh_last = CIRCLEQ_END(head); \
  498. } while (0)
  499. #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
  500. (elm)->field.cqe_next = (listelm)->field.cqe_next; \
  501. (elm)->field.cqe_prev = (listelm); \
  502. if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
  503. (head)->cqh_last = (elm); \
  504. else \
  505. (listelm)->field.cqe_next->field.cqe_prev = (elm); \
  506. (listelm)->field.cqe_next = (elm); \
  507. } while (0)
  508. #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
  509. (elm)->field.cqe_next = (listelm); \
  510. (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
  511. if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
  512. (head)->cqh_first = (elm); \
  513. else \
  514. (listelm)->field.cqe_prev->field.cqe_next = (elm); \
  515. (listelm)->field.cqe_prev = (elm); \
  516. } while (0)
  517. #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
  518. (elm)->field.cqe_next = (head)->cqh_first; \
  519. (elm)->field.cqe_prev = CIRCLEQ_END(head); \
  520. if ((head)->cqh_last == CIRCLEQ_END(head)) \
  521. (head)->cqh_last = (elm); \
  522. else \
  523. (head)->cqh_first->field.cqe_prev = (elm); \
  524. (head)->cqh_first = (elm); \
  525. } while (0)
  526. #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
  527. (elm)->field.cqe_next = CIRCLEQ_END(head); \
  528. (elm)->field.cqe_prev = (head)->cqh_last; \
  529. if ((head)->cqh_first == CIRCLEQ_END(head)) \
  530. (head)->cqh_first = (elm); \
  531. else \
  532. (head)->cqh_last->field.cqe_next = (elm); \
  533. (head)->cqh_last = (elm); \
  534. } while (0)
  535. #define CIRCLEQ_REMOVE(head, elm, field) do { \
  536. if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
  537. (head)->cqh_last = (elm)->field.cqe_prev; \
  538. else \
  539. (elm)->field.cqe_next->field.cqe_prev = \
  540. (elm)->field.cqe_prev; \
  541. if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
  542. (head)->cqh_first = (elm)->field.cqe_next; \
  543. else \
  544. (elm)->field.cqe_prev->field.cqe_next = \
  545. (elm)->field.cqe_next; \
  546. _Q_INVALIDATE((elm)->field.cqe_prev); \
  547. _Q_INVALIDATE((elm)->field.cqe_next); \
  548. } while (0)
  549. #define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
  550. if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
  551. CIRCLEQ_END(head)) \
  552. (head)->cqh_last = (elm2); \
  553. else \
  554. (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
  555. if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
  556. CIRCLEQ_END(head)) \
  557. (head)->cqh_first = (elm2); \
  558. else \
  559. (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
  560. _Q_INVALIDATE((elm)->field.cqe_prev); \
  561. _Q_INVALIDATE((elm)->field.cqe_next); \
  562. } while (0)
  563. #endif /* !_SYS_QUEUE_H_ */