queue.h 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592
  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: src/sys/sys/queue.h,v 1.58 2004/04/07 04:19:49 imp Exp $
  31. */
  32. #ifndef _QUEUE_H_
  33. #define _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_HEAD + - + -
  96. * _REMOVE + + + +
  97. *
  98. */
  99. #define QUEUE_MACRO_DEBUG 0
  100. #if QUEUE_MACRO_DEBUG
  101. /*
  102. * Store the last 2 places the queue element or head was altered
  103. */
  104. struct qm_trace {
  105. char *lastfile;
  106. int lastline;
  107. char *prevfile;
  108. int prevline;
  109. };
  110. #define TRACEBUF struct qm_trace trace;
  111. #define TRASHIT(x) do {(x) = (void *)NULL; } while (0)
  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 TRACEBUF
  128. #define TRASHIT(x) do {(x) = (void *)0; } while (0)
  129. #endif /* QUEUE_MACRO_DEBUG */
  130. #ifdef ATHR_RNWF
  131. /*
  132. * NDIS contains a defn for SLIST_ENTRY and SINGLE_LIST_ENTRY
  133. */
  134. #endif
  135. /*
  136. * Singly-linked List declarations.
  137. */
  138. #define SLIST_HEAD(name, type) \
  139. struct name { \
  140. struct type *slh_first; /* first element */ \
  141. }
  142. #define SLIST_HEAD_INITIALIZER(head) \
  143. { NULL }
  144. #define SING_LIST_ENTRY(type) \
  145. struct { \
  146. struct type *sle_next; /* next element */ \
  147. }
  148. /*
  149. * Singly-linked List functions.
  150. */
  151. #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
  152. #define SLIST_FIRST(head) ((head)->slh_first)
  153. #define SLIST_FOREACH(var, head, field) \
  154. for ((var) = SLIST_FIRST((head)); \
  155. (var); \
  156. (var) = SLIST_NEXT((var), field))
  157. #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
  158. for ((var) = SLIST_FIRST((head)); \
  159. (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
  160. (var) = (tvar))
  161. #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
  162. for ((varp) = &SLIST_FIRST((head)); \
  163. ((var) = *(varp)) != NULL; \
  164. (varp) = &SLIST_NEXT((var), field))
  165. #define SLIST_INIT(head) do { \
  166. SLIST_FIRST((head)) = NULL; \
  167. } while (0)
  168. #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
  169. SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
  170. SLIST_NEXT((slistelm), field) = (elm); \
  171. } while (0)
  172. #define SLIST_INSERT_HEAD(head, elm, field) do { \
  173. SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
  174. SLIST_FIRST((head)) = (elm); \
  175. } while (0)
  176. #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
  177. #define SLIST_REMOVE(head, elm, type, field) do { \
  178. if (SLIST_FIRST((head)) == (elm)) { \
  179. SLIST_REMOVE_HEAD((head), field); \
  180. } \
  181. else { \
  182. struct type *curelm = SLIST_FIRST((head)); \
  183. while (SLIST_NEXT(curelm, field) != (elm)) \
  184. curelm = SLIST_NEXT(curelm, field); \
  185. SLIST_NEXT(curelm, field) = \
  186. SLIST_NEXT(SLIST_NEXT(curelm, field), field);\
  187. } \
  188. } while (0)
  189. #define SLIST_REMOVE_HEAD(head, field) do { \
  190. SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), \
  191. field); \
  192. } while (0)
  193. /*
  194. * Singly-linked Tail queue declarations.
  195. */
  196. #define STAILQ_HEAD(name, type) \
  197. struct name { \
  198. struct type *stqh_first; \
  199. struct type **stqh_last; \
  200. }
  201. #define STAILQ_HEAD_INITIALIZER(head) \
  202. { NULL, &(head).stqh_first }
  203. #define STAILQ_ENTRY(type) \
  204. struct { \
  205. struct type *stqe_next; /* next element */ \
  206. }
  207. /*
  208. * Singly-linked Tail queue functions.
  209. */
  210. #define STAILQ_CONCAT(head1, head2) do { \
  211. if (!STAILQ_EMPTY((head2))) { \
  212. *(head1)->stqh_last = (head2)->stqh_first; \
  213. (head1)->stqh_last = (head2)->stqh_last; \
  214. STAILQ_INIT((head2)); \
  215. } \
  216. } while (0)
  217. #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
  218. #define STAILQ_FIRST(head) ((head)->stqh_first)
  219. #define STAILQ_FOREACH(var, head, field) \
  220. for ((var) = STAILQ_FIRST((head)); \
  221. (var); \
  222. (var) = STAILQ_NEXT((var), field))
  223. #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
  224. for ((var) = STAILQ_FIRST((head)); \
  225. (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
  226. (var) = (tvar))
  227. #define STAILQ_INIT(head) do { \
  228. STAILQ_FIRST((head)) = NULL; \
  229. (head)->stqh_last = &STAILQ_FIRST((head)); \
  230. } while (0)
  231. #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
  232. if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), \
  233. field)) == NULL) \
  234. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  235. STAILQ_NEXT((tqelm), field) = (elm); \
  236. } while (0)
  237. #define STAILQ_INSERT_HEAD(head, elm, field) do { \
  238. if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == \
  239. NULL) \
  240. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  241. STAILQ_FIRST((head)) = (elm); \
  242. } while (0)
  243. #define STAILQ_INSERT_TAIL(head, elm, field) do { \
  244. STAILQ_NEXT((elm), field) = NULL; \
  245. *(head)->stqh_last = (elm); \
  246. (head)->stqh_last = &STAILQ_NEXT((elm), field); \
  247. } while (0)
  248. #define STAILQ_LAST(head, type, field) \
  249. (STAILQ_EMPTY((head)) ? \
  250. NULL : \
  251. ((struct type *) \
  252. ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
  253. #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
  254. #define STAILQ_REMOVE(head, elm, type, field) do { \
  255. if (STAILQ_FIRST((head)) == (elm)) { \
  256. STAILQ_REMOVE_HEAD((head), field); \
  257. } \
  258. else { \
  259. struct type *curelm = STAILQ_FIRST((head)); \
  260. while (STAILQ_NEXT(curelm, field) != (elm)) \
  261. curelm = STAILQ_NEXT(curelm, field); \
  262. if ((STAILQ_NEXT(curelm, field) = \
  263. STAILQ_NEXT(STAILQ_NEXT(curelm, field), \
  264. field)) == NULL) \
  265. (head)->stqh_last = &STAILQ_NEXT((curelm),\
  266. field); \
  267. } \
  268. } while (0)
  269. #define STAILQ_REMOVE_AFTER(head, elm, field) do { \
  270. if (STAILQ_NEXT(elm, field)) { \
  271. if ((STAILQ_NEXT(elm, field) = \
  272. STAILQ_NEXT(STAILQ_NEXT(elm, field), \
  273. field)) == NULL) \
  274. (head)->stqh_last = \
  275. &STAILQ_NEXT((elm), field); \
  276. } \
  277. } while (0)
  278. #define STAILQ_REMOVE_HEAD(head, field) do { \
  279. if ((STAILQ_FIRST((head)) = \
  280. STAILQ_NEXT(STAILQ_FIRST((head)), field)) == \
  281. NULL)\
  282. (head)->stqh_last = &STAILQ_FIRST((head)); \
  283. } while (0)
  284. #define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
  285. if ((STAILQ_FIRST((head)) = \
  286. STAILQ_NEXT((elm), field)) == NULL) \
  287. (head)->stqh_last = &STAILQ_FIRST((head)); \
  288. } while (0)
  289. /*
  290. * List declarations.
  291. */
  292. #define ATH_LIST_HEAD(name, type) \
  293. struct name { \
  294. struct type *lh_first; \
  295. }
  296. #ifndef LIST_HEAD
  297. #define LIST_HEAD ATH_LIST_HEAD
  298. #endif
  299. #define LIST_HEAD_INITIALIZER(head) \
  300. { NULL }
  301. #define LIST_ENTRY(type) \
  302. struct { \
  303. struct type *le_next; \
  304. struct type **le_prev; \
  305. }
  306. /*
  307. * List functions.
  308. */
  309. #define LIST_EMPTY(head) ((head)->lh_first == NULL)
  310. #define LIST_FIRST(head) ((head)->lh_first)
  311. #define LIST_FOREACH(var, head, field) \
  312. for ((var) = LIST_FIRST((head)); \
  313. (var); \
  314. (var) = LIST_NEXT((var), field))
  315. #define LIST_FOREACH_SAFE(var, head, field, tvar) \
  316. for ((var) = LIST_FIRST((head)); \
  317. (var) && ((tvar) = LIST_NEXT((var), field), 1); \
  318. (var) = (tvar))
  319. #define LIST_INIT(head) do { \
  320. LIST_FIRST((head)) = NULL; \
  321. } while (0)
  322. #define LIST_INSERT_AFTER(listelm, elm, field) do { \
  323. if ((LIST_NEXT((elm), field) = \
  324. LIST_NEXT((listelm), field)) != NULL) \
  325. LIST_NEXT((listelm), field)->field.le_prev = \
  326. &LIST_NEXT((elm), field); \
  327. LIST_NEXT((listelm), field) = (elm); \
  328. (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
  329. } while (0)
  330. #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
  331. (elm)->field.le_prev = (listelm)->field.le_prev; \
  332. LIST_NEXT((elm), field) = (listelm); \
  333. *(listelm)->field.le_prev = (elm); \
  334. (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
  335. } while (0)
  336. #define LIST_INSERT_HEAD(head, elm, field) do { \
  337. if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
  338. LIST_FIRST((head))->field.le_prev = \
  339. &LIST_NEXT((elm), field); \
  340. LIST_FIRST((head)) = (elm); \
  341. (elm)->field.le_prev = &LIST_FIRST((head)); \
  342. } while (0)
  343. #define LIST_NEXT(elm, field) ((elm)->field.le_next)
  344. #define LIST_REMOVE(elm, field) do { \
  345. if (LIST_NEXT((elm), field) != NULL) \
  346. LIST_NEXT((elm), field)->field.le_prev = \
  347. (elm)->field.le_prev; \
  348. *(elm)->field.le_prev = LIST_NEXT((elm), field); \
  349. } while (0)
  350. /*
  351. * Tail queue declarations.
  352. */
  353. #ifndef TRACE_TX_LEAK
  354. #define TRACE_TX_LEAK 0
  355. #endif
  356. #if TRACE_TX_LEAK
  357. #define HEADNAME char headname[64];
  358. #define COPY_HEADNAME(head) OS_MEMCPY((head)->headname, #head, sizeof(#head))
  359. #else
  360. #define HEADNAME
  361. #define COPY_HEADNAME(head)
  362. #endif
  363. #define TAILQ_HEAD(name, type) \
  364. struct name { \
  365. struct type *tqh_first; \
  366. struct type **tqh_last; \
  367. HEADNAME \
  368. TRACEBUF \
  369. }
  370. #define TAILQ_HEAD_INITIALIZER(head) \
  371. { NULL, &(head).tqh_first }
  372. #define TAILQ_ENTRY(type) \
  373. struct { \
  374. struct type *tqe_next; \
  375. struct type **tqe_prev; \
  376. TRACEBUF \
  377. }
  378. /*
  379. * Tail queue functions.
  380. */
  381. #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
  382. #define TAILQ_FIRST(head) ((head)->tqh_first)
  383. #define TAILQ_FOREACH(var, head, field) \
  384. for ((var) = TAILQ_FIRST((head)); \
  385. (var); \
  386. (var) = TAILQ_NEXT((var), field))
  387. #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
  388. for ((var) = TAILQ_FIRST((head)); \
  389. (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
  390. (var) = (tvar))
  391. #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
  392. for ((var) = TAILQ_LAST((head), headname); \
  393. (var); \
  394. (var) = TAILQ_PREV((var), headname, field))
  395. #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
  396. for ((var) = TAILQ_LAST((head), headname); \
  397. (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
  398. (var) = (tvar))
  399. #define TAILQ_INIT(head) do { \
  400. TAILQ_FIRST((head)) = NULL; \
  401. (head)->tqh_last = &TAILQ_FIRST((head)); \
  402. COPY_HEADNAME(head); \
  403. QMD_TRACE_HEAD(head); \
  404. } while (0)
  405. #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
  406. if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), \
  407. field)) != NULL) \
  408. TAILQ_NEXT((elm), field)->field.tqe_prev = \
  409. &TAILQ_NEXT((elm), field); \
  410. else { \
  411. (head)->tqh_last = &TAILQ_NEXT((elm), field); \
  412. QMD_TRACE_HEAD(head); \
  413. } \
  414. TAILQ_NEXT((listelm), field) = (elm); \
  415. (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
  416. QMD_TRACE_ELEM(&(elm)->field); \
  417. QMD_TRACE_ELEM(&listelm->field); \
  418. } while (0)
  419. #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
  420. (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
  421. TAILQ_NEXT((elm), field) = (listelm); \
  422. *(listelm)->field.tqe_prev = (elm); \
  423. (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
  424. QMD_TRACE_ELEM(&(elm)->field); \
  425. QMD_TRACE_ELEM(&listelm->field); \
  426. } while (0)
  427. #define TAILQ_INSERT_HEAD(head, elm, field) do { \
  428. if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)\
  429. TAILQ_FIRST((head))->field.tqe_prev = \
  430. &TAILQ_NEXT((elm), field); \
  431. else \
  432. (head)->tqh_last = &TAILQ_NEXT((elm), field); \
  433. TAILQ_FIRST((head)) = (elm); \
  434. (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
  435. QMD_TRACE_HEAD(head); \
  436. QMD_TRACE_ELEM(&(elm)->field); \
  437. } while (0)
  438. #define TAILQ_INSERT_TAIL(head, elm, field) do { \
  439. TAILQ_NEXT((elm), field) = NULL; \
  440. (elm)->field.tqe_prev = (head)->tqh_last; \
  441. *(head)->tqh_last = (elm); \
  442. (head)->tqh_last = &TAILQ_NEXT((elm), field); \
  443. QMD_TRACE_HEAD(head); \
  444. QMD_TRACE_ELEM(&(elm)->field); \
  445. } while (0)
  446. #define TAILQ_LAST(head, headname) \
  447. (*(((struct headname *)((head)->tqh_last))->tqh_last))
  448. #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
  449. #define TAILQ_PREV(elm, headname, field) \
  450. (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
  451. #define TAILQ_REMOVE(head, elm, field) do { \
  452. if ((TAILQ_NEXT((elm), field)) != NULL) \
  453. TAILQ_NEXT((elm), field)->field.tqe_prev = \
  454. (elm)->field.tqe_prev; \
  455. else { \
  456. (head)->tqh_last = (elm)->field.tqe_prev; \
  457. QMD_TRACE_HEAD(head); \
  458. } \
  459. *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
  460. TRASHIT((elm)->field.tqe_next); \
  461. TRASHIT((elm)->field.tqe_prev); \
  462. QMD_TRACE_ELEM(&(elm)->field); \
  463. } while (0)
  464. #define TAILQ_CONCAT(head1, head2, field) do { \
  465. if (!TAILQ_EMPTY(head2)) { \
  466. *(head1)->tqh_last = (head2)->tqh_first; \
  467. (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;\
  468. (head1)->tqh_last = (head2)->tqh_last; \
  469. TAILQ_INIT((head2)); \
  470. } \
  471. } while (0)
  472. #ifdef _KERNEL
  473. /*
  474. * XXX insque() and remque() are an old way of handling certain queues.
  475. * They bogusly assumes that all queue heads look alike.
  476. */
  477. struct quehead {
  478. struct quehead *qh_link;
  479. struct quehead *qh_rlink;
  480. };
  481. #if defined(__GNUC__) || defined(__INTEL_COMPILER)
  482. static inline void insque(void *a, void *b)
  483. {
  484. struct quehead *element = (struct quehead *)a,
  485. *head = (struct quehead *)b;
  486. element->qh_link = head->qh_link;
  487. element->qh_rlink = head;
  488. head->qh_link = element;
  489. element->qh_link->qh_rlink = element;
  490. }
  491. static inline void remque(void *a)
  492. {
  493. struct quehead *element = (struct quehead *)a;
  494. element->qh_link->qh_rlink = element->qh_rlink;
  495. element->qh_rlink->qh_link = element->qh_link;
  496. element->qh_rlink = 0;
  497. }
  498. #else /* !(__GNUC__ || __INTEL_COMPILER) */
  499. void insque(void *a, void *b);
  500. void remque(void *a);
  501. #endif /* __GNUC__ || __INTEL_COMPILER */
  502. #endif /* _KERNEL */
  503. #endif /* _QUEUE_H_ */