queue.h
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:11k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /*
  2.  * Copyright (c) 1991, 1993
  3.  * The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. Neither the name of the University nor the names of its contributors
  14.  *    may be used to endorse or promote products derived from this software
  15.  *    without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27.  * SUCH DAMAGE.
  28.  *
  29.  * @(#)queue.h 8.5 (Berkeley) 8/20/94
  30.  */
  31. /*
  32.  * XXX
  33.  * We #undef the queue macros because there are incompatible versions of this
  34.  * file and these macros on various systems.  What makes the problem worse is
  35.  * they are included and/or defined by system include files which we may have
  36.  * already loaded into Berkeley DB before getting here.  For example, FreeBSD's
  37.  * <rpc/rpc.h> includes its system <sys/queue.h>, and VxWorks UnixLib.h defines
  38.  * several of the LIST_XXX macros.  Make sure we use ours.
  39.  */
  40. #undef LIST_HEAD
  41. #undef LIST_ENTRY
  42. #undef LIST_FIRST
  43. #undef LIST_NEXT
  44. #undef LIST_INIT
  45. #undef LIST_INSERT_AFTER
  46. #undef LIST_INSERT_BEFORE
  47. #undef LIST_INSERT_HEAD
  48. #undef LIST_REMOVE
  49. #undef TAILQ_HEAD
  50. #undef TAILQ_ENTRY
  51. #undef TAILQ_FIRST
  52. #undef TAILQ_NEXT
  53. #undef TAILQ_INIT
  54. #undef TAILQ_INSERT_HEAD
  55. #undef TAILQ_INSERT_TAIL
  56. #undef TAILQ_INSERT_AFTER
  57. #undef TAILQ_INSERT_BEFORE
  58. #undef TAILQ_REMOVE
  59. #undef CIRCLEQ_HEAD
  60. #undef CIRCLEQ_ENTRY
  61. #undef CIRCLEQ_FIRST
  62. #undef CIRCLEQ_LAST
  63. #undef CIRCLEQ_NEXT
  64. #undef CIRCLEQ_PREV
  65. #undef CIRCLEQ_INIT
  66. #undef CIRCLEQ_INSERT_AFTER
  67. #undef CIRCLEQ_INSERT_BEFORE
  68. #undef CIRCLEQ_INSERT_HEAD
  69. #undef CIRCLEQ_INSERT_TAIL
  70. #undef CIRCLEQ_REMOVE
  71. /*
  72.  * This file defines three types of data structures: lists, tail queues,
  73.  * and circular queues.
  74.  *
  75.  * A list is headed by a single forward pointer (or an array of forward
  76.  * pointers for a hash table header). The elements are doubly linked
  77.  * 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
  79.  * or after an existing element or at the head of the list. A list
  80.  * may only be traversed in the forward direction.
  81.  *
  82.  * A tail queue is headed by a pair of pointers, one to the head of the
  83.  * list and the other to the tail of the list. The elements are doubly
  84.  * linked so that an arbitrary element can be removed without a need to
  85.  * traverse the list. New elements can be added to the list before or
  86.  * after an existing element, at the head of the list, or at the end of
  87.  * the list. A tail queue may only be traversed in the forward direction.
  88.  *
  89.  * A circle queue is headed by a pair of pointers, one to the head of the
  90.  * list and the other to the tail of the list. The elements are doubly
  91.  * linked so that an arbitrary element can be removed without a need to
  92.  * traverse the list. New elements can be added to the list before or after
  93.  * an existing element, at the head of the list, or at the end of the list.
  94.  * A circle queue may be traversed in either direction, but has a more
  95.  * complex end of list detection.
  96.  *
  97.  * For details on the use of these macros, see the queue(3) manual page.
  98.  */
  99. #if defined(__cplusplus)
  100. extern "C" {
  101. #endif
  102. /*
  103.  * List definitions.
  104.  */
  105. #define LIST_HEAD(name, type)
  106. struct name {
  107. struct type *lh_first; /* first element */
  108. }
  109. #define LIST_ENTRY(type)
  110. struct {
  111. struct type *le_next; /* next element */
  112. struct type **le_prev; /* address of previous next element */
  113. }
  114. #define LIST_FIRST(head) ((head)->lh_first)
  115. #define LIST_NEXT(elm, field) ((elm)->field.le_next)
  116. /*
  117.  * List functions.
  118.  */
  119. #define LIST_INIT(head) {
  120. (head)->lh_first = NULL;
  121. }
  122. #define LIST_INSERT_AFTER(listelm, elm, field) do {
  123. if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)
  124. (listelm)->field.le_next->field.le_prev =
  125.     &(elm)->field.le_next;
  126. (listelm)->field.le_next = (elm);
  127. (elm)->field.le_prev = &(listelm)->field.le_next;
  128. } while (0)
  129. #define LIST_INSERT_BEFORE(listelm, elm, field) do {
  130. (elm)->field.le_prev = (listelm)->field.le_prev;
  131. (elm)->field.le_next = (listelm);
  132. *(listelm)->field.le_prev = (elm);
  133. (listelm)->field.le_prev = &(elm)->field.le_next;
  134. } while (0)
  135. #define LIST_INSERT_HEAD(head, elm, field) do {
  136. if (((elm)->field.le_next = (head)->lh_first) != NULL)
  137. (head)->lh_first->field.le_prev = &(elm)->field.le_next;
  138. (head)->lh_first = (elm);
  139. (elm)->field.le_prev = &(head)->lh_first;
  140. } while (0)
  141. #define LIST_REMOVE(elm, field) do {
  142. if ((elm)->field.le_next != NULL)
  143. (elm)->field.le_next->field.le_prev =
  144.     (elm)->field.le_prev;
  145. *(elm)->field.le_prev = (elm)->field.le_next;
  146. } while (0)
  147. /*
  148.  * Tail queue definitions.
  149.  */
  150. #define TAILQ_HEAD(name, type)
  151. struct name {
  152. struct type *tqh_first; /* first element */
  153. struct type **tqh_last; /* addr of last next element */
  154. }
  155. #define TAILQ_ENTRY(type)
  156. struct {
  157. struct type *tqe_next; /* next element */
  158. struct type **tqe_prev; /* address of previous next element */
  159. }
  160. #define TAILQ_FIRST(head) ((head)->tqh_first)
  161. #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
  162. /*
  163.  * Tail queue functions.
  164.  */
  165. #define TAILQ_INIT(head) do {
  166. (head)->tqh_first = NULL;
  167. (head)->tqh_last = &(head)->tqh_first;
  168. } while (0)
  169. #define TAILQ_INSERT_HEAD(head, elm, field) do {
  170. if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)
  171. (head)->tqh_first->field.tqe_prev =
  172.     &(elm)->field.tqe_next;
  173. else
  174. (head)->tqh_last = &(elm)->field.tqe_next;
  175. (head)->tqh_first = (elm);
  176. (elm)->field.tqe_prev = &(head)->tqh_first;
  177. } while (0)
  178. #define TAILQ_INSERT_TAIL(head, elm, field) do {
  179. (elm)->field.tqe_next = NULL;
  180. (elm)->field.tqe_prev = (head)->tqh_last;
  181. *(head)->tqh_last = (elm);
  182. (head)->tqh_last = &(elm)->field.tqe_next;
  183. } while (0)
  184. #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {
  185. if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)
  186. (elm)->field.tqe_next->field.tqe_prev =
  187.     &(elm)->field.tqe_next;
  188. else
  189. (head)->tqh_last = &(elm)->field.tqe_next;
  190. (listelm)->field.tqe_next = (elm);
  191. (elm)->field.tqe_prev = &(listelm)->field.tqe_next;
  192. } while (0)
  193. #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {
  194. (elm)->field.tqe_prev = (listelm)->field.tqe_prev;
  195. (elm)->field.tqe_next = (listelm);
  196. *(listelm)->field.tqe_prev = (elm);
  197. (listelm)->field.tqe_prev = &(elm)->field.tqe_next;
  198. } while (0)
  199. #define TAILQ_REMOVE(head, elm, field) do {
  200. if (((elm)->field.tqe_next) != NULL)
  201. (elm)->field.tqe_next->field.tqe_prev =
  202.     (elm)->field.tqe_prev;
  203. else
  204. (head)->tqh_last = (elm)->field.tqe_prev;
  205. *(elm)->field.tqe_prev = (elm)->field.tqe_next;
  206. } while (0)
  207. /*
  208.  * This macro is used to fixup the queue after moving the head.
  209.  */
  210. #define TAILQ_REINSERT_HEAD(head, elm, field) do {
  211. DB_ASSERT((head)->tqh_first == (elm));
  212. (elm)->field.tqe_prev = &(head)->tqh_first;                     
  213. } while (0)
  214. /*
  215.  * Circular queue definitions.
  216.  */
  217. #define CIRCLEQ_HEAD(name, type)
  218. struct name {
  219. struct type *cqh_first; /* first element */
  220. struct type *cqh_last; /* last element */
  221. }
  222. #define CIRCLEQ_ENTRY(type)
  223. struct {
  224. struct type *cqe_next; /* next element */
  225. struct type *cqe_prev; /* previous element */
  226. }
  227. #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
  228. #define CIRCLEQ_LAST(head) ((head)->cqh_last)
  229. #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
  230. #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
  231. /*
  232.  * Circular queue functions.
  233.  */
  234. #define CIRCLEQ_INIT(head) do {
  235. (head)->cqh_first = (void *)(head);
  236. (head)->cqh_last = (void *)(head);
  237. } while (0)
  238. #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {
  239. (elm)->field.cqe_next = (listelm)->field.cqe_next;
  240. (elm)->field.cqe_prev = (listelm);
  241. if ((listelm)->field.cqe_next == (void *)(head))
  242. (head)->cqh_last = (elm);
  243. else
  244. (listelm)->field.cqe_next->field.cqe_prev = (elm);
  245. (listelm)->field.cqe_next = (elm);
  246. } while (0)
  247. #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {
  248. (elm)->field.cqe_next = (listelm);
  249. (elm)->field.cqe_prev = (listelm)->field.cqe_prev;
  250. if ((listelm)->field.cqe_prev == (void *)(head))
  251. (head)->cqh_first = (elm);
  252. else
  253. (listelm)->field.cqe_prev->field.cqe_next = (elm);
  254. (listelm)->field.cqe_prev = (elm);
  255. } while (0)
  256. #define CIRCLEQ_INSERT_HEAD(head, elm, field) do {
  257. (elm)->field.cqe_next = (head)->cqh_first;
  258. (elm)->field.cqe_prev = (void *)(head);
  259. if ((head)->cqh_last == (void *)(head))
  260. (head)->cqh_last = (elm);
  261. else
  262. (head)->cqh_first->field.cqe_prev = (elm);
  263. (head)->cqh_first = (elm);
  264. } while (0)
  265. #define CIRCLEQ_INSERT_TAIL(head, elm, field) do {
  266. (elm)->field.cqe_next = (void *)(head);
  267. (elm)->field.cqe_prev = (head)->cqh_last;
  268. if ((head)->cqh_first == (void *)(head))
  269. (head)->cqh_first = (elm);
  270. else
  271. (head)->cqh_last->field.cqe_next = (elm);
  272. (head)->cqh_last = (elm);
  273. } while (0)
  274. #define CIRCLEQ_REMOVE(head, elm, field) do {
  275. if ((elm)->field.cqe_next == (void *)(head))
  276. (head)->cqh_last = (elm)->field.cqe_prev;
  277. else
  278. (elm)->field.cqe_next->field.cqe_prev =
  279.     (elm)->field.cqe_prev;
  280. if ((elm)->field.cqe_prev == (void *)(head))
  281. (head)->cqh_first = (elm)->field.cqe_next;
  282. else
  283. (elm)->field.cqe_prev->field.cqe_next =
  284.     (elm)->field.cqe_next;
  285. } while (0)
  286. #if defined(__cplusplus)
  287. }
  288. #endif