queue.h 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636
  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.5 (Berkeley) 8/20/94
  30. * $FreeBSD$
  31. */
  32. #ifndef _SYS_QUEUE_H_
  33. #define _SYS_QUEUE_H_
  34. /*
  35. * This file defines four types of data structures: singly-linked lists,
  36. * singly-linked tail queues, lists and tail queues.
  37. *
  38. * A singly-linked list is headed by a single forward pointer. The elements
  39. * are singly linked for minimum space and pointer manipulation overhead at
  40. * the expense of O(n) removal for arbitrary elements. New elements can be
  41. * added to the list after an existing element or at the head of the list.
  42. * Elements being removed from the head of the list should use the explicit
  43. * macro for this purpose for optimum efficiency. A singly-linked list may
  44. * only be traversed in the forward direction. Singly-linked lists are ideal
  45. * for applications with large datasets and few or no removals or for
  46. * implementing a LIFO queue.
  47. *
  48. * A singly-linked tail queue is headed by a pair of pointers, one to the
  49. * head of the list and the other to the tail of the list. The elements are
  50. * singly linked for minimum space and pointer manipulation overhead at the
  51. * expense of O(n) removal for arbitrary elements. New elements can be added
  52. * to the list after an existing element, at the head of the list, or at the
  53. * end of the list. Elements being removed from the head of the tail queue
  54. * should use the explicit macro for this purpose for optimum efficiency.
  55. * A singly-linked tail queue may only be traversed in the forward direction.
  56. * Singly-linked tail queues are ideal for applications with large datasets
  57. * and few or no removals or for implementing a FIFO queue.
  58. *
  59. * A list is headed by a single forward pointer (or an array of forward
  60. * pointers for a hash table header). The elements are doubly linked
  61. * so that an arbitrary element can be removed without a need to
  62. * traverse the list. New elements can be added to the list before
  63. * or after an existing element or at the head of the list. A list
  64. * may only be traversed in the forward direction.
  65. *
  66. * A tail queue is headed by a pair of pointers, one to the head of the
  67. * list and the other to the tail of the list. The elements are doubly
  68. * linked so that an arbitrary element can be removed without a need to
  69. * traverse the list. New elements can be added to the list before or
  70. * after an existing element, at the head of the list, or at the end of
  71. * the list. A tail queue may be traversed in either direction.
  72. *
  73. * For details on the use of these macros, see the queue(3) manual page.
  74. *
  75. *
  76. * SLIST LIST STAILQ TAILQ
  77. * _HEAD + + + +
  78. * _HEAD_INITIALIZER + + + +
  79. * _ENTRY + + + +
  80. * _INIT + + + +
  81. * _EMPTY + + + +
  82. * _FIRST + + + +
  83. * _NEXT + + + +
  84. * _PREV - - - +
  85. * _LAST - - + +
  86. * _FOREACH + + + +
  87. * _FOREACH_SAFE + + + +
  88. * _FOREACH_REVERSE - - - +
  89. * _FOREACH_REVERSE_SAFE - - - +
  90. * _INSERT_HEAD + + + +
  91. * _INSERT_BEFORE - + - +
  92. * _INSERT_AFTER + + + +
  93. * _INSERT_TAIL - - + +
  94. * _CONCAT - - + +
  95. * _REMOVE_AFTER + - + -
  96. * _REMOVE_HEAD + - + -
  97. * _REMOVE + + + +
  98. * _SWAP + + + +
  99. *
  100. */
  101. #ifdef QUEUE_MACRO_DEBUG
  102. /* Store the last 2 places the queue element or head was altered */
  103. struct qm_trace {
  104. char * lastfile;
  105. int lastline;
  106. char * prevfile;
  107. int prevline;
  108. };
  109. #define TRACEBUF struct qm_trace trace;
  110. #define TRASHIT(x) do {(x) = (void *)-1;} while (0)
  111. #define QMD_SAVELINK(name, link) void **name = (void *)&(link)
  112. #define QMD_TRACE_HEAD(head) do { \
  113. (head)->trace.prevline = (head)->trace.lastline; \
  114. (head)->trace.prevfile = (head)->trace.lastfile; \
  115. (head)->trace.lastline = __LINE__; \
  116. (head)->trace.lastfile = __FILE__; \
  117. } while (0)
  118. #define QMD_TRACE_ELEM(elem) do { \
  119. (elem)->trace.prevline = (elem)->trace.lastline; \
  120. (elem)->trace.prevfile = (elem)->trace.lastfile; \
  121. (elem)->trace.lastline = __LINE__; \
  122. (elem)->trace.lastfile = __FILE__; \
  123. } while (0)
  124. #else
  125. #define QMD_TRACE_ELEM(elem)
  126. #define QMD_TRACE_HEAD(head)
  127. #define QMD_SAVELINK(name, link)
  128. #define TRACEBUF
  129. #define TRASHIT(x)
  130. #endif /* QUEUE_MACRO_DEBUG */
  131. /*
  132. * Singly-linked List declarations.
  133. */
  134. #define SLIST_HEAD(name, type) \
  135. struct name { \
  136. struct type *slh_first; /* first element */ \
  137. }
  138. #define SLIST_HEAD_INITIALIZER(head) \
  139. { NULL }
  140. #define SLIST_ENTRY(type) \
  141. struct { \
  142. struct type *sle_next; /* next element */ \
  143. }
  144. /*
  145. * Singly-linked List functions.
  146. */
  147. #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
  148. #define SLIST_FIRST(head) ((head)->slh_first)
  149. #define SLIST_FOREACH(var, head, field) \
  150. for ((var) = SLIST_FIRST((head)); \
  151. (var); \
  152. (var) = SLIST_NEXT((var), field))
  153. #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
  154. for ((var) = SLIST_FIRST((head)); \
  155. (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
  156. (var) = (tvar))
  157. #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
  158. for ((varp) = &SLIST_FIRST((head)); \
  159. ((var) = *(varp)) != NULL; \
  160. (varp) = &SLIST_NEXT((var), field))
  161. #define SLIST_INIT(head) do { \
  162. SLIST_FIRST((head)) = NULL; \
  163. } while (0)
  164. #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
  165. SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
  166. SLIST_NEXT((slistelm), field) = (elm); \
  167. } while (0)
  168. #define SLIST_INSERT_HEAD(head, elm, field) do { \
  169. SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
  170. SLIST_FIRST((head)) = (elm); \
  171. } while (0)
  172. #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
  173. #define SLIST_REMOVE(head, elm, type, field) do { \
  174. QMD_SAVELINK(oldnext, (elm)->field.sle_next); \
  175. if (SLIST_FIRST((head)) == (elm)) { \
  176. SLIST_REMOVE_HEAD((head), field); \
  177. } \
  178. else { \
  179. struct type *curelm = SLIST_FIRST((head)); \
  180. while (SLIST_NEXT(curelm, field) != (elm)) \
  181. curelm = SLIST_NEXT(curelm, field); \
  182. SLIST_REMOVE_AFTER(curelm, field); \
  183. } \
  184. TRASHIT(*oldnext); \
  185. } while (0)
  186. #define SLIST_REMOVE_AFTER(elm, field) do { \
  187. SLIST_NEXT(elm, field) = \
  188. SLIST_NEXT(SLIST_NEXT(elm, field), field); \
  189. } while (0)
  190. #define SLIST_REMOVE_HEAD(head, field) do { \
  191. SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
  192. } while (0)
  193. #define SLIST_SWAP(head1, head2, type) do { \
  194. struct type *swap_first = SLIST_FIRST(head1); \
  195. SLIST_FIRST(head1) = SLIST_FIRST(head2); \
  196. SLIST_FIRST(head2) = swap_first; \
  197. } while (0)
  198. /*
  199. * Singly-linked Tail queue declarations.
  200. */
  201. #define STAILQ_HEAD(name, type) \
  202. struct name { \
  203. struct type *stqh_first;/* first element */ \
  204. struct type **stqh_last;/* addr of last next element */ \
  205. }
  206. #define STAILQ_HEAD_INITIALIZER(head) \
  207. { NULL, &(head).stqh_first }
  208. #define STAILQ_ENTRY(type) \
  209. struct { \
  210. struct type *stqe_next; /* next element */ \
  211. }
  212. /*
  213. * Singly-linked Tail queue functions.
  214. */
  215. #define STAILQ_CONCAT(head1, head2) do { \
  216. if (!STAILQ_EMPTY((head2))) { \
  217. *(head1)->stqh_last = (head2)->stqh_first; \
  218. (head1)->stqh_last = (head2)->stqh_last; \
  219. STAILQ_INIT((head2)); \
  220. } \
  221. } while (0)
  222. #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
  223. #define STAILQ_FIRST(head) ((head)->stqh_first)
  224. #define STAILQ_FOREACH(var, head, field) \
  225. for((var) = STAILQ_FIRST((head)); \
  226. (var); \
  227. (var) = STAILQ_NEXT((var), field))
  228. #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
  229. for ((var) = STAILQ_FIRST((head)); \
  230. (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
  231. (var) = (tvar))
  232. #define STAILQ_INIT(head) do { \
  233. STAILQ_FIRST((head)) = NULL; \
  234. (head)->stqh_last = &STAILQ_FIRST((head)); \
  235. } while (0)
  236. #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
  237. if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
  238. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  239. STAILQ_NEXT((tqelm), field) = (elm); \
  240. } while (0)
  241. #define STAILQ_INSERT_HEAD(head, elm, field) do { \
  242. if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
  243. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  244. STAILQ_FIRST((head)) = (elm); \
  245. } while (0)
  246. #define STAILQ_INSERT_TAIL(head, elm, field) do { \
  247. STAILQ_NEXT((elm), field) = NULL; \
  248. *(head)->stqh_last = (elm); \
  249. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  250. } while (0)
  251. #define STAILQ_LAST(head, type, field) \
  252. (STAILQ_EMPTY((head)) ? \
  253. NULL : \
  254. ((struct type *)(void *) \
  255. ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
  256. #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
  257. #define STAILQ_REMOVE(head, elm, type, field) do { \
  258. QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \
  259. if (STAILQ_FIRST((head)) == (elm)) { \
  260. STAILQ_REMOVE_HEAD((head), field); \
  261. } \
  262. else { \
  263. struct type *curelm = STAILQ_FIRST((head)); \
  264. while (STAILQ_NEXT(curelm, field) != (elm)) \
  265. curelm = STAILQ_NEXT(curelm, field); \
  266. STAILQ_REMOVE_AFTER(head, curelm, field); \
  267. } \
  268. TRASHIT(*oldnext); \
  269. } while (0)
  270. #define STAILQ_REMOVE_AFTER(head, elm, field) do { \
  271. if ((STAILQ_NEXT(elm, field) = \
  272. STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \
  273. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  274. } while (0)
  275. #define STAILQ_REMOVE_HEAD(head, field) do { \
  276. if ((STAILQ_FIRST((head)) = \
  277. STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
  278. (head)->stqh_last = &STAILQ_FIRST((head)); \
  279. } while (0)
  280. #define STAILQ_SWAP(head1, head2, type) do { \
  281. struct type *swap_first = STAILQ_FIRST(head1); \
  282. struct type **swap_last = (head1)->stqh_last; \
  283. STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \
  284. (head1)->stqh_last = (head2)->stqh_last; \
  285. STAILQ_FIRST(head2) = swap_first; \
  286. (head2)->stqh_last = swap_last; \
  287. if (STAILQ_EMPTY(head1)) \
  288. (head1)->stqh_last = &STAILQ_FIRST(head1); \
  289. if (STAILQ_EMPTY(head2)) \
  290. (head2)->stqh_last = &STAILQ_FIRST(head2); \
  291. } while (0)
  292. /*
  293. * List declarations.
  294. */
  295. #define LIST_HEAD(name, type) \
  296. struct name { \
  297. struct type *lh_first; /* first element */ \
  298. }
  299. #define LIST_HEAD_INITIALIZER(head) \
  300. { NULL }
  301. #define LIST_ENTRY(type) \
  302. struct { \
  303. struct type *le_next; /* next element */ \
  304. struct type **le_prev; /* address of previous next element */ \
  305. }
  306. /*
  307. * List functions.
  308. */
  309. #if (defined(_KERNEL) && defined(INVARIANTS))
  310. #define QMD_LIST_CHECK_HEAD(head, field) do { \
  311. if (LIST_FIRST((head)) != NULL && \
  312. LIST_FIRST((head))->field.le_prev != \
  313. &LIST_FIRST((head))) \
  314. panic("Bad list head %p first->prev != head", (head)); \
  315. } while (0)
  316. #define QMD_LIST_CHECK_NEXT(elm, field) do { \
  317. if (LIST_NEXT((elm), field) != NULL && \
  318. LIST_NEXT((elm), field)->field.le_prev != \
  319. &((elm)->field.le_next)) \
  320. panic("Bad link elm %p next->prev != elm", (elm)); \
  321. } while (0)
  322. #define QMD_LIST_CHECK_PREV(elm, field) do { \
  323. if (*(elm)->field.le_prev != (elm)) \
  324. panic("Bad link elm %p prev->next != elm", (elm)); \
  325. } while (0)
  326. #else
  327. #define QMD_LIST_CHECK_HEAD(head, field)
  328. #define QMD_LIST_CHECK_NEXT(elm, field)
  329. #define QMD_LIST_CHECK_PREV(elm, field)
  330. #endif /* (_KERNEL && INVARIANTS) */
  331. #define LIST_EMPTY(head) ((head)->lh_first == NULL)
  332. #define LIST_FIRST(head) ((head)->lh_first)
  333. #define LIST_FOREACH(var, head, field) \
  334. for ((var) = LIST_FIRST((head)); \
  335. (var); \
  336. (var) = LIST_NEXT((var), field))
  337. #define LIST_FOREACH_SAFE(var, head, field, tvar) \
  338. for ((var) = LIST_FIRST((head)); \
  339. (var) && ((tvar) = LIST_NEXT((var), field), 1); \
  340. (var) = (tvar))
  341. #define LIST_INIT(head) do { \
  342. LIST_FIRST((head)) = NULL; \
  343. } while (0)
  344. #define LIST_INSERT_AFTER(listelm, elm, field) do { \
  345. QMD_LIST_CHECK_NEXT(listelm, field); \
  346. if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
  347. LIST_NEXT((listelm), field)->field.le_prev = \
  348. &LIST_NEXT((elm), field); \
  349. LIST_NEXT((listelm), field) = (elm); \
  350. (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
  351. } while (0)
  352. #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
  353. QMD_LIST_CHECK_PREV(listelm, field); \
  354. (elm)->field.le_prev = (listelm)->field.le_prev; \
  355. LIST_NEXT((elm), field) = (listelm); \
  356. *(listelm)->field.le_prev = (elm); \
  357. (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
  358. } while (0)
  359. #define LIST_INSERT_HEAD(head, elm, field) do { \
  360. QMD_LIST_CHECK_HEAD((head), field); \
  361. if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
  362. LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
  363. LIST_FIRST((head)) = (elm); \
  364. (elm)->field.le_prev = &LIST_FIRST((head)); \
  365. } while (0)
  366. #define LIST_NEXT(elm, field) ((elm)->field.le_next)
  367. #define LIST_REMOVE(elm, field) do { \
  368. QMD_SAVELINK(oldnext, (elm)->field.le_next); \
  369. QMD_SAVELINK(oldprev, (elm)->field.le_prev); \
  370. QMD_LIST_CHECK_NEXT(elm, field); \
  371. QMD_LIST_CHECK_PREV(elm, field); \
  372. if (LIST_NEXT((elm), field) != NULL) \
  373. LIST_NEXT((elm), field)->field.le_prev = \
  374. (elm)->field.le_prev; \
  375. *(elm)->field.le_prev = LIST_NEXT((elm), field); \
  376. TRASHIT(*oldnext); \
  377. TRASHIT(*oldprev); \
  378. } while (0)
  379. #define LIST_SWAP(head1, head2, type, field) do { \
  380. struct type *swap_tmp = LIST_FIRST((head1)); \
  381. LIST_FIRST((head1)) = LIST_FIRST((head2)); \
  382. LIST_FIRST((head2)) = swap_tmp; \
  383. if ((swap_tmp = LIST_FIRST((head1))) != NULL) \
  384. swap_tmp->field.le_prev = &LIST_FIRST((head1)); \
  385. if ((swap_tmp = LIST_FIRST((head2))) != NULL) \
  386. swap_tmp->field.le_prev = &LIST_FIRST((head2)); \
  387. } while (0)
  388. /*
  389. * Tail queue declarations.
  390. */
  391. #define TAILQ_HEAD(name, type) \
  392. struct name { \
  393. struct type *tqh_first; /* first element */ \
  394. struct type **tqh_last; /* addr of last next element */ \
  395. TRACEBUF \
  396. }
  397. #define TAILQ_HEAD_INITIALIZER(head) \
  398. { NULL, &(head).tqh_first }
  399. #define TAILQ_ENTRY(type) \
  400. struct { \
  401. struct type *tqe_next; /* next element */ \
  402. struct type **tqe_prev; /* address of previous next element */ \
  403. TRACEBUF \
  404. }
  405. /*
  406. * Tail queue functions.
  407. */
  408. #if (defined(_KERNEL) && defined(INVARIANTS))
  409. #define QMD_TAILQ_CHECK_HEAD(head, field) do { \
  410. if (!TAILQ_EMPTY(head) && \
  411. TAILQ_FIRST((head))->field.tqe_prev != \
  412. &TAILQ_FIRST((head))) \
  413. panic("Bad tailq head %p first->prev != head", (head)); \
  414. } while (0)
  415. #define QMD_TAILQ_CHECK_TAIL(head, field) do { \
  416. if (*(head)->tqh_last != NULL) \
  417. panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
  418. } while (0)
  419. #define QMD_TAILQ_CHECK_NEXT(elm, field) do { \
  420. if (TAILQ_NEXT((elm), field) != NULL && \
  421. TAILQ_NEXT((elm), field)->field.tqe_prev != \
  422. &((elm)->field.tqe_next)) \
  423. panic("Bad link elm %p next->prev != elm", (elm)); \
  424. } while (0)
  425. #define QMD_TAILQ_CHECK_PREV(elm, field) do { \
  426. if (*(elm)->field.tqe_prev != (elm)) \
  427. panic("Bad link elm %p prev->next != elm", (elm)); \
  428. } while (0)
  429. #else
  430. #define QMD_TAILQ_CHECK_HEAD(head, field)
  431. #define QMD_TAILQ_CHECK_TAIL(head, headname)
  432. #define QMD_TAILQ_CHECK_NEXT(elm, field)
  433. #define QMD_TAILQ_CHECK_PREV(elm, field)
  434. #endif /* (_KERNEL && INVARIANTS) */
  435. #define TAILQ_CONCAT(head1, head2, field) do { \
  436. if (!TAILQ_EMPTY(head2)) { \
  437. *(head1)->tqh_last = (head2)->tqh_first; \
  438. (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
  439. (head1)->tqh_last = (head2)->tqh_last; \
  440. TAILQ_INIT((head2)); \
  441. QMD_TRACE_HEAD(head1); \
  442. QMD_TRACE_HEAD(head2); \
  443. } \
  444. } while (0)
  445. #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
  446. #define TAILQ_FIRST(head) ((head)->tqh_first)
  447. #define TAILQ_FOREACH(var, head, field) \
  448. for ((var) = TAILQ_FIRST((head)); \
  449. (var); \
  450. (var) = TAILQ_NEXT((var), field))
  451. #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
  452. for ((var) = TAILQ_FIRST((head)); \
  453. (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
  454. (var) = (tvar))
  455. #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
  456. for ((var) = TAILQ_LAST((head), headname); \
  457. (var); \
  458. (var) = TAILQ_PREV((var), headname, field))
  459. #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
  460. for ((var) = TAILQ_LAST((head), headname); \
  461. (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
  462. (var) = (tvar))
  463. #define TAILQ_INIT(head) do { \
  464. TAILQ_FIRST((head)) = NULL; \
  465. (head)->tqh_last = &TAILQ_FIRST((head)); \
  466. QMD_TRACE_HEAD(head); \
  467. } while (0)
  468. #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
  469. QMD_TAILQ_CHECK_NEXT(listelm, field); \
  470. if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
  471. TAILQ_NEXT((elm), field)->field.tqe_prev = \
  472. &TAILQ_NEXT((elm), field); \
  473. else { \
  474. (head)->tqh_last = &TAILQ_NEXT((elm), field); \
  475. QMD_TRACE_HEAD(head); \
  476. } \
  477. TAILQ_NEXT((listelm), field) = (elm); \
  478. (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
  479. QMD_TRACE_ELEM(&(elm)->field); \
  480. QMD_TRACE_ELEM(&listelm->field); \
  481. } while (0)
  482. #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
  483. QMD_TAILQ_CHECK_PREV(listelm, field); \
  484. (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
  485. TAILQ_NEXT((elm), field) = (listelm); \
  486. *(listelm)->field.tqe_prev = (elm); \
  487. (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
  488. QMD_TRACE_ELEM(&(elm)->field); \
  489. QMD_TRACE_ELEM(&listelm->field); \
  490. } while (0)
  491. #define TAILQ_INSERT_HEAD(head, elm, field) do { \
  492. QMD_TAILQ_CHECK_HEAD(head, field); \
  493. if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
  494. TAILQ_FIRST((head))->field.tqe_prev = \
  495. &TAILQ_NEXT((elm), field); \
  496. else \
  497. (head)->tqh_last = &TAILQ_NEXT((elm), field); \
  498. TAILQ_FIRST((head)) = (elm); \
  499. (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
  500. QMD_TRACE_HEAD(head); \
  501. QMD_TRACE_ELEM(&(elm)->field); \
  502. } while (0)
  503. #define TAILQ_INSERT_TAIL(head, elm, field) do { \
  504. QMD_TAILQ_CHECK_TAIL(head, field); \
  505. TAILQ_NEXT((elm), field) = NULL; \
  506. (elm)->field.tqe_prev = (head)->tqh_last; \
  507. *(head)->tqh_last = (elm); \
  508. (head)->tqh_last = &TAILQ_NEXT((elm), field); \
  509. QMD_TRACE_HEAD(head); \
  510. QMD_TRACE_ELEM(&(elm)->field); \
  511. } while (0)
  512. #define TAILQ_LAST(head, headname) \
  513. (*(((struct headname *)((head)->tqh_last))->tqh_last))
  514. #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
  515. #define TAILQ_PREV(elm, headname, field) \
  516. (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
  517. #define TAILQ_REMOVE(head, elm, field) do { \
  518. QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
  519. QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
  520. QMD_TAILQ_CHECK_NEXT(elm, field); \
  521. QMD_TAILQ_CHECK_PREV(elm, field); \
  522. if ((TAILQ_NEXT((elm), field)) != NULL) \
  523. TAILQ_NEXT((elm), field)->field.tqe_prev = \
  524. (elm)->field.tqe_prev; \
  525. else { \
  526. (head)->tqh_last = (elm)->field.tqe_prev; \
  527. QMD_TRACE_HEAD(head); \
  528. } \
  529. *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
  530. TRASHIT(*oldnext); \
  531. TRASHIT(*oldprev); \
  532. QMD_TRACE_ELEM(&(elm)->field); \
  533. } while (0)
  534. #define TAILQ_SWAP(head1, head2, type, field) do { \
  535. struct type *swap_first = (head1)->tqh_first; \
  536. struct type **swap_last = (head1)->tqh_last; \
  537. (head1)->tqh_first = (head2)->tqh_first; \
  538. (head1)->tqh_last = (head2)->tqh_last; \
  539. (head2)->tqh_first = swap_first; \
  540. (head2)->tqh_last = swap_last; \
  541. if ((swap_first = (head1)->tqh_first) != NULL) \
  542. swap_first->field.tqe_prev = &(head1)->tqh_first; \
  543. else \
  544. (head1)->tqh_last = &(head1)->tqh_first; \
  545. if ((swap_first = (head2)->tqh_first) != NULL) \
  546. swap_first->field.tqe_prev = &(head2)->tqh_first; \
  547. else \
  548. (head2)->tqh_last = &(head2)->tqh_first; \
  549. } while (0)
  550. #endif /* !_SYS_QUEUE_H_ */