queue.h 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511
  1. /* $OpenBSD: queue.h,v 1.22 2001/06/23 04:39:35 angelos 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. All advertising materials mentioning features or use of this software
  16. * must display the following acknowledgement:
  17. * This product includes software developed by the University of
  18. * California, Berkeley and its contributors.
  19. * 4. Neither the name of the University nor the names of its contributors
  20. * may be used to endorse or promote products derived from this software
  21. * without specific prior written permission.
  22. *
  23. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26. * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33. * SUCH DAMAGE.
  34. *
  35. * @(#)queue.h 8.5 (Berkeley) 8/20/94
  36. */
  37. #ifndef _SYS_QUEUE_H_
  38. #define _SYS_QUEUE_H_
  39. /*
  40. * This file defines five types of data structures: singly-linked lists,
  41. * lists, simple queues, tail queues, and circular queues.
  42. *
  43. *
  44. * A singly-linked list is headed by a single forward pointer. The elements
  45. * are singly linked for minimum space and pointer manipulation overhead at
  46. * the expense of O(n) removal for arbitrary elements. New elements can be
  47. * added to the list after an existing element or at the head of the list.
  48. * Elements being removed from the head of the list should use the explicit
  49. * macro for this purpose for optimum efficiency. A singly-linked list may
  50. * only be traversed in the forward direction. Singly-linked lists are ideal
  51. * for applications with large datasets and few or no removals or for
  52. * implementing a LIFO queue.
  53. *
  54. * A list is headed by a single forward pointer (or an array of forward
  55. * pointers for a hash table header). The elements are doubly linked
  56. * so that an arbitrary element can be removed without a need to
  57. * traverse the list. New elements can be added to the list before
  58. * or after an existing element or at the head of the list. A list
  59. * may only be traversed in the forward direction.
  60. *
  61. * A simple queue is headed by a pair of pointers, one the head of the
  62. * list and the other to the tail of the list. The elements are singly
  63. * linked to save space, so elements can only be removed from the
  64. * head of the list. New elements can be added to the list before or after
  65. * an existing element, at the head of the list, or at the end of the
  66. * list. A simple queue may only be traversed in the forward direction.
  67. *
  68. * A tail queue is headed by a pair of pointers, one to the head of the
  69. * list and the other to the tail of the list. The elements are doubly
  70. * linked so that an arbitrary element can be removed without a need to
  71. * traverse the list. New elements can be added to the list before or
  72. * after an existing element, at the head of the list, or at the end of
  73. * the list. A tail queue may be traversed in either direction.
  74. *
  75. * A circle queue is headed by a pair of pointers, one to the head of the
  76. * list and the other to the tail of the list. The elements are doubly
  77. * linked so that an arbitrary element can be removed without a need to
  78. * traverse the list. New elements can be added to the list before or after
  79. * an existing element, at the head of the list, or at the end of the list.
  80. * A circle queue may be traversed in either direction, but has a more
  81. * complex end of list detection.
  82. *
  83. * For details on the use of these macros, see the queue(3) manual page.
  84. */
  85. /*
  86. * Singly-linked List definitions.
  87. */
  88. #define SLIST_HEAD(name, type) \
  89. struct name { \
  90. struct type *slh_first; /* first element */ \
  91. }
  92. #define SLIST_HEAD_INITIALIZER(head) \
  93. { NULL }
  94. #define SLIST_ENTRY(type) \
  95. struct { \
  96. struct type *sle_next; /* next element */ \
  97. }
  98. /*
  99. * Singly-linked List access methods.
  100. */
  101. #define SLIST_FIRST(head) ((head)->slh_first)
  102. #define SLIST_END(head) NULL
  103. #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
  104. #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
  105. #define SLIST_FOREACH(var, head, field) \
  106. for((var) = SLIST_FIRST(head); \
  107. (var) != SLIST_END(head); \
  108. (var) = SLIST_NEXT(var, field))
  109. /*
  110. * Singly-linked List functions.
  111. */
  112. #define SLIST_INIT(head) { \
  113. SLIST_FIRST(head) = SLIST_END(head); \
  114. }
  115. #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
  116. (elm)->field.sle_next = (slistelm)->field.sle_next; \
  117. (slistelm)->field.sle_next = (elm); \
  118. } while (0)
  119. #define SLIST_INSERT_HEAD(head, elm, field) do { \
  120. (elm)->field.sle_next = (head)->slh_first; \
  121. (head)->slh_first = (elm); \
  122. } while (0)
  123. #define SLIST_REMOVE_HEAD(head, field) do { \
  124. (head)->slh_first = (head)->slh_first->field.sle_next; \
  125. } while (0)
  126. #define SLIST_REMOVE(head, elm, type, field) do { \
  127. if ((head)->slh_first == (elm)) { \
  128. SLIST_REMOVE_HEAD((head), field); \
  129. } \
  130. else { \
  131. struct type *curelm = (head)->slh_first; \
  132. while( curelm->field.sle_next != (elm) ) \
  133. curelm = curelm->field.sle_next; \
  134. curelm->field.sle_next = \
  135. curelm->field.sle_next->field.sle_next; \
  136. } \
  137. } while (0)
  138. /*
  139. * List definitions.
  140. */
  141. #define LIST_HEAD(name, type) \
  142. struct name { \
  143. struct type *lh_first; /* first element */ \
  144. }
  145. #define LIST_HEAD_INITIALIZER(head) \
  146. { NULL }
  147. #define LIST_ENTRY(type) \
  148. struct { \
  149. struct type *le_next; /* next element */ \
  150. struct type **le_prev; /* address of previous next element */ \
  151. }
  152. /*
  153. * List access methods
  154. */
  155. #define LIST_FIRST(head) ((head)->lh_first)
  156. #define LIST_END(head) NULL
  157. #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
  158. #define LIST_NEXT(elm, field) ((elm)->field.le_next)
  159. #define LIST_FOREACH(var, head, field) \
  160. for((var) = LIST_FIRST(head); \
  161. (var)!= LIST_END(head); \
  162. (var) = LIST_NEXT(var, field))
  163. /*
  164. * List functions.
  165. */
  166. #define LIST_INIT(head) do { \
  167. LIST_FIRST(head) = LIST_END(head); \
  168. } while (0)
  169. #define LIST_INSERT_AFTER(listelm, elm, field) do { \
  170. if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
  171. (listelm)->field.le_next->field.le_prev = \
  172. &(elm)->field.le_next; \
  173. (listelm)->field.le_next = (elm); \
  174. (elm)->field.le_prev = &(listelm)->field.le_next; \
  175. } while (0)
  176. #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
  177. (elm)->field.le_prev = (listelm)->field.le_prev; \
  178. (elm)->field.le_next = (listelm); \
  179. *(listelm)->field.le_prev = (elm); \
  180. (listelm)->field.le_prev = &(elm)->field.le_next; \
  181. } while (0)
  182. #define LIST_INSERT_HEAD(head, elm, field) do { \
  183. if (((elm)->field.le_next = (head)->lh_first) != NULL) \
  184. (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
  185. (head)->lh_first = (elm); \
  186. (elm)->field.le_prev = &(head)->lh_first; \
  187. } while (0)
  188. #define LIST_REMOVE(elm, field) do { \
  189. if ((elm)->field.le_next != NULL) \
  190. (elm)->field.le_next->field.le_prev = \
  191. (elm)->field.le_prev; \
  192. *(elm)->field.le_prev = (elm)->field.le_next; \
  193. } while (0)
  194. #define LIST_REPLACE(elm, elm2, field) do { \
  195. if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
  196. (elm2)->field.le_next->field.le_prev = \
  197. &(elm2)->field.le_next; \
  198. (elm2)->field.le_prev = (elm)->field.le_prev; \
  199. *(elm2)->field.le_prev = (elm2); \
  200. } while (0)
  201. /*
  202. * Simple queue definitions.
  203. */
  204. #define SIMPLEQ_HEAD(name, type) \
  205. struct name { \
  206. struct type *sqh_first; /* first element */ \
  207. struct type **sqh_last; /* addr of last next element */ \
  208. }
  209. #define SIMPLEQ_HEAD_INITIALIZER(head) \
  210. { NULL, &(head).sqh_first }
  211. #define SIMPLEQ_ENTRY(type) \
  212. struct { \
  213. struct type *sqe_next; /* next element */ \
  214. }
  215. /*
  216. * Simple queue access methods.
  217. */
  218. #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
  219. #define SIMPLEQ_END(head) NULL
  220. #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
  221. #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
  222. #define SIMPLEQ_FOREACH(var, head, field) \
  223. for((var) = SIMPLEQ_FIRST(head); \
  224. (var) != SIMPLEQ_END(head); \
  225. (var) = SIMPLEQ_NEXT(var, field))
  226. /*
  227. * Simple queue functions.
  228. */
  229. #define SIMPLEQ_INIT(head) do { \
  230. (head)->sqh_first = NULL; \
  231. (head)->sqh_last = &(head)->sqh_first; \
  232. } while (0)
  233. #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
  234. if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
  235. (head)->sqh_last = &(elm)->field.sqe_next; \
  236. (head)->sqh_first = (elm); \
  237. } while (0)
  238. #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
  239. (elm)->field.sqe_next = NULL; \
  240. *(head)->sqh_last = (elm); \
  241. (head)->sqh_last = &(elm)->field.sqe_next; \
  242. } while (0)
  243. #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
  244. if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
  245. (head)->sqh_last = &(elm)->field.sqe_next; \
  246. (listelm)->field.sqe_next = (elm); \
  247. } while (0)
  248. #define SIMPLEQ_REMOVE_HEAD(head, elm, field) do { \
  249. if (((head)->sqh_first = (elm)->field.sqe_next) == NULL) \
  250. (head)->sqh_last = &(head)->sqh_first; \
  251. } while (0)
  252. /*
  253. * Tail queue definitions.
  254. */
  255. #define TAILQ_HEAD(name, type) \
  256. struct name { \
  257. struct type *tqh_first; /* first element */ \
  258. struct type **tqh_last; /* addr of last next element */ \
  259. }
  260. #define TAILQ_HEAD_INITIALIZER(head) \
  261. { NULL, &(head).tqh_first }
  262. #define TAILQ_ENTRY(type) \
  263. struct { \
  264. struct type *tqe_next; /* next element */ \
  265. struct type **tqe_prev; /* address of previous next element */ \
  266. }
  267. /*
  268. * tail queue access methods
  269. */
  270. #define TAILQ_FIRST(head) ((head)->tqh_first)
  271. #define TAILQ_END(head) NULL
  272. #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
  273. #define TAILQ_LAST(head, headname) \
  274. (*(((struct headname *)((head)->tqh_last))->tqh_last))
  275. /* XXX */
  276. #define TAILQ_PREV(elm, headname, field) \
  277. (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
  278. #define TAILQ_EMPTY(head) \
  279. (TAILQ_FIRST(head) == TAILQ_END(head))
  280. #define TAILQ_FOREACH(var, head, field) \
  281. for((var) = TAILQ_FIRST(head); \
  282. (var) != TAILQ_END(head); \
  283. (var) = TAILQ_NEXT(var, field))
  284. #define TAILQ_FOREACH_REVERSE(var, head, field, headname) \
  285. for((var) = TAILQ_LAST(head, headname); \
  286. (var) != TAILQ_END(head); \
  287. (var) = TAILQ_PREV(var, headname, field))
  288. /*
  289. * Tail queue functions.
  290. */
  291. #define TAILQ_INIT(head) do { \
  292. (head)->tqh_first = NULL; \
  293. (head)->tqh_last = &(head)->tqh_first; \
  294. } while (0)
  295. #define TAILQ_COPY(dst, src, field) do { \
  296. *(dst) = *(src); \
  297. if (((dst)->tqh_first) != NULL) \
  298. (dst)->tqh_first->field.tqe_prev = &(dst)->tqh_first; \
  299. else \
  300. (dst)->tqh_last = &(dst)->tqh_first; \
  301. } while (0)
  302. #define TAILQ_INSERT_HEAD(head, elm, field) do { \
  303. if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
  304. (head)->tqh_first->field.tqe_prev = \
  305. &(elm)->field.tqe_next; \
  306. else \
  307. (head)->tqh_last = &(elm)->field.tqe_next; \
  308. (head)->tqh_first = (elm); \
  309. (elm)->field.tqe_prev = &(head)->tqh_first; \
  310. } while (0)
  311. #define TAILQ_INSERT_TAIL(head, elm, field) do { \
  312. (elm)->field.tqe_next = NULL; \
  313. (elm)->field.tqe_prev = (head)->tqh_last; \
  314. *(head)->tqh_last = (elm); \
  315. (head)->tqh_last = &(elm)->field.tqe_next; \
  316. } while (0)
  317. #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
  318. if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
  319. (elm)->field.tqe_next->field.tqe_prev = \
  320. &(elm)->field.tqe_next; \
  321. else \
  322. (head)->tqh_last = &(elm)->field.tqe_next; \
  323. (listelm)->field.tqe_next = (elm); \
  324. (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
  325. } while (0)
  326. #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
  327. (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
  328. (elm)->field.tqe_next = (listelm); \
  329. *(listelm)->field.tqe_prev = (elm); \
  330. (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
  331. } while (0)
  332. #define TAILQ_REMOVE(head, elm, field) do { \
  333. if (((elm)->field.tqe_next) != NULL) \
  334. (elm)->field.tqe_next->field.tqe_prev = \
  335. (elm)->field.tqe_prev; \
  336. else \
  337. (head)->tqh_last = (elm)->field.tqe_prev; \
  338. *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
  339. } while (0)
  340. #define TAILQ_REPLACE(head, elm, elm2, field) do { \
  341. if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
  342. (elm2)->field.tqe_next->field.tqe_prev = \
  343. &(elm2)->field.tqe_next; \
  344. else \
  345. (head)->tqh_last = &(elm2)->field.tqe_next; \
  346. (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
  347. *(elm2)->field.tqe_prev = (elm2); \
  348. } while (0)
  349. /*
  350. * Circular queue definitions.
  351. */
  352. #define CIRCLEQ_HEAD(name, type) \
  353. struct name { \
  354. struct type *cqh_first; /* first element */ \
  355. struct type *cqh_last; /* last element */ \
  356. }
  357. #define CIRCLEQ_HEAD_INITIALIZER(head) \
  358. { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
  359. #define CIRCLEQ_ENTRY(type) \
  360. struct { \
  361. struct type *cqe_next; /* next element */ \
  362. struct type *cqe_prev; /* previous element */ \
  363. }
  364. /*
  365. * Circular queue access methods
  366. */
  367. #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
  368. #define CIRCLEQ_LAST(head) ((head)->cqh_last)
  369. #define CIRCLEQ_END(head) ((void *)(head))
  370. #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
  371. #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
  372. #define CIRCLEQ_EMPTY(head) \
  373. (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
  374. #define CIRCLEQ_FOREACH(var, head, field) \
  375. for((var) = CIRCLEQ_FIRST(head); \
  376. (var) != CIRCLEQ_END(head); \
  377. (var) = CIRCLEQ_NEXT(var, field))
  378. #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
  379. for((var) = CIRCLEQ_LAST(head); \
  380. (var) != CIRCLEQ_END(head); \
  381. (var) = CIRCLEQ_PREV(var, field))
  382. /*
  383. * Circular queue functions.
  384. */
  385. #define CIRCLEQ_INIT(head) do { \
  386. (head)->cqh_first = CIRCLEQ_END(head); \
  387. (head)->cqh_last = CIRCLEQ_END(head); \
  388. } while (0)
  389. #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
  390. (elm)->field.cqe_next = (listelm)->field.cqe_next; \
  391. (elm)->field.cqe_prev = (listelm); \
  392. if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
  393. (head)->cqh_last = (elm); \
  394. else \
  395. (listelm)->field.cqe_next->field.cqe_prev = (elm); \
  396. (listelm)->field.cqe_next = (elm); \
  397. } while (0)
  398. #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
  399. (elm)->field.cqe_next = (listelm); \
  400. (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
  401. if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
  402. (head)->cqh_first = (elm); \
  403. else \
  404. (listelm)->field.cqe_prev->field.cqe_next = (elm); \
  405. (listelm)->field.cqe_prev = (elm); \
  406. } while (0)
  407. #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
  408. (elm)->field.cqe_next = (head)->cqh_first; \
  409. (elm)->field.cqe_prev = CIRCLEQ_END(head); \
  410. if ((head)->cqh_last == CIRCLEQ_END(head)) \
  411. (head)->cqh_last = (elm); \
  412. else \
  413. (head)->cqh_first->field.cqe_prev = (elm); \
  414. (head)->cqh_first = (elm); \
  415. } while (0)
  416. #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
  417. (elm)->field.cqe_next = CIRCLEQ_END(head); \
  418. (elm)->field.cqe_prev = (head)->cqh_last; \
  419. if ((head)->cqh_first == CIRCLEQ_END(head)) \
  420. (head)->cqh_first = (elm); \
  421. else \
  422. (head)->cqh_last->field.cqe_next = (elm); \
  423. (head)->cqh_last = (elm); \
  424. } while (0)
  425. #define CIRCLEQ_REMOVE(head, elm, field) do { \
  426. if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
  427. (head)->cqh_last = (elm)->field.cqe_prev; \
  428. else \
  429. (elm)->field.cqe_next->field.cqe_prev = \
  430. (elm)->field.cqe_prev; \
  431. if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
  432. (head)->cqh_first = (elm)->field.cqe_next; \
  433. else \
  434. (elm)->field.cqe_prev->field.cqe_next = \
  435. (elm)->field.cqe_next; \
  436. } while (0)
  437. #define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
  438. if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
  439. CIRCLEQ_END(head)) \
  440. (head).cqh_last = (elm2); \
  441. else \
  442. (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
  443. if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
  444. CIRCLEQ_END(head)) \
  445. (head).cqh_first = (elm2); \
  446. else \
  447. (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
  448. } while (0)
  449. #endif /* !_SYS_QUEUE_H_ */