C 宏实现队列

蔚落 2022-09-30 07:06 127阅读 0赞

[http://trac.openrays.org/projects/pmon/browser/trunk/sys/sys/queue.h?rev=2][http_trac.openrays.org_projects_pmon_browser_trunk_sys_sys_queue.h_rev_2]

/\* $OpenBSD: queue.h,v 1.32 2007/04/30 18:42:34 pedro Exp $ \*/ /\* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ \*/ /\* \* Copyright (c) 1991, 1993 \* The Regents of the University of California. All rights reserved. \* \* Redistribution and use in source and binary forms, with or without \* modification, are permitted provided that the following conditions \* are met: \* 1. Redistributions of source code must retain the above copyright \* notice, this list of conditions and the following disclaimer. \* 2. Redistributions in binary form must reproduce the above copyright \* notice, this list of conditions and the following disclaimer in the \* documentation and/or other materials provided with the distribution. \* 3. Neither the name of the University nor the names of its contributors \* may be used to endorse or promote products derived from this software \* without specific prior written permission. \* \* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS \`\`AS IS'' AND \* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE \* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE \* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE \* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL \* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS \* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) \* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT \* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY \* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF \* SUCH DAMAGE. \* \* @(\#)queue.h 8.5 (Berkeley) 8/20/94 \*/ \#ifndef \_SYS\_QUEUE\_H\_ \#define \_SYS\_QUEUE\_H\_ /\* \* This file defines five types of data structures: singly-linked lists, \* lists, simple queues, tail queues, and circular queues. \* \* \* A singly-linked list is headed by a single forward pointer. The elements \* are singly linked for minimum space and pointer manipulation overhead at \* the expense of O(n) removal for arbitrary elements. New elements can be \* added to the list after an existing element or at the head of the list. \* Elements being removed from the head of the list should use the explicit \* macro for this purpose for optimum efficiency. A singly-linked list may \* only be traversed in the forward direction. Singly-linked lists are ideal \* for applications with large datasets and few or no removals or for \* implementing a LIFO queue. \* \* A list is headed by a single forward pointer (or an array of forward \* pointers for a hash table header). The elements are doubly linked \* so that an arbitrary element can be removed without a need to \* traverse the list. New elements can be added to the list before \* or after an existing element or at the head of the list. A list \* may only be traversed in the forward direction. \* \* A simple queue is headed by a pair of pointers, one the head of the \* list and the other to the tail of the list. The elements are singly \* linked to save space, so elements can only be removed from the \* head of the list. New elements can be added to the list before or after \* an existing element, at the head of the list, or at the end of the \* list. A simple queue may only be traversed in the forward direction. \* \* A tail queue is headed by a pair of pointers, one to the head of the \* list and the other to the tail of the list. The elements are doubly \* linked so that an arbitrary element can be removed without a need to \* traverse the list. New elements can be added to the list before or \* after an existing element, at the head of the list, or at the end of \* the list. A tail queue may be traversed in either direction. \* \* A circle queue is headed by a pair of pointers, one to the head of the \* list and the other to the tail of the list. The elements are doubly \* linked so that an arbitrary element can be removed without a need to \* traverse the list. New elements can be added to the list before or after \* an existing element, at the head of the list, or at the end of the list. \* A circle queue may be traversed in either direction, but has a more \* complex end of list detection. \* \* For details on the use of these macros, see the queue(3) manual page. \*/ \#if defined(QUEUE\_MACRO\_DEBUG) || (defined(\_KERNEL) && defined(DIAGNOSTIC)) \#define \_Q\_INVALIDATE(a) (a) = ((void \*)-1) \#else \#define \_Q\_INVALIDATE(a) \#endif /\* \* Singly-linked List definitions. \*/ \#define SLIST\_HEAD(name, type) / struct name \{ / struct type \*slh\_first; /\* first element \*/ / \} \#define SLIST\_HEAD\_INITIALIZER(head) / \{ NULL \} \#if 0 /\* 与WinNT.h中重复定义 \*/ \#define SLIST\_ENTRY(type) / struct \{ / struct type \*sle\_next; /\* next element \*/ / \} \#endif /\* \* Singly-linked List access methods. \*/ \#define SLIST\_FIRST(head) ((head)->slh\_first) \#define SLIST\_END(head) NULL \#define SLIST\_EMPTY(head) (SLIST\_FIRST(head) == SLIST\_END(head)) \#define SLIST\_NEXT(elm, field) ((elm)->field.sle\_next) \#define SLIST\_FOREACH(var, head, field) / for((var) = SLIST\_FIRST(head); / (var) != SLIST\_END(head); / (var) = SLIST\_NEXT(var, field)) \#define SLIST\_FOREACH\_PREVPTR(var, varp, head, field) / for ((varp) = &SLIST\_FIRST((head)); / ((var) = \*(varp)) != SLIST\_END(head); / (varp) = &SLIST\_NEXT((var), field)) /\* \* Singly-linked List functions. \*/ \#define SLIST\_INIT(head) \{ / SLIST\_FIRST(head) = SLIST\_END(head); / \} \#define SLIST\_INSERT\_AFTER(slistelm, elm, field) do \{ / (elm)->field.sle\_next = (slistelm)->field.sle\_next; / (slistelm)->field.sle\_next = (elm); / \} while (0) \#define SLIST\_INSERT\_HEAD(head, elm, field) do \{ / (elm)->field.sle\_next = (head)->slh\_first; / (head)->slh\_first = (elm); / \} while (0) \#define SLIST\_REMOVE\_NEXT(head, elm, field) do \{ / (elm)->field.sle\_next = (elm)->field.sle\_next->field.sle\_next; / \} while (0) \#define SLIST\_REMOVE\_HEAD(head, field) do \{ / (head)->slh\_first = (head)->slh\_first->field.sle\_next; / \} while (0) \#define SLIST\_REMOVE(head, elm, type, field) do \{ / if ((head)->slh\_first == (elm)) \{ / SLIST\_REMOVE\_HEAD((head), field); / \} else \{ / struct type \*curelm = (head)->slh\_first; / / while (curelm->field.sle\_next != (elm)) / curelm = curelm->field.sle\_next; / curelm->field.sle\_next = / curelm->field.sle\_next->field.sle\_next; / \_Q\_INVALIDATE((elm)->field.sle\_next); / \} / \} while (0) /\* \* List definitions. \*/ \#define LIST\_HEAD(name, type) / struct name \{ / struct type \*lh\_first; /\* first element \*/ / \} \#define LIST\_HEAD\_INITIALIZER(head) / \{ NULL \} \#define LIST\_ENTRY(type) / struct \{ / struct type \*le\_next; /\* next element \*/ / struct type \*\*le\_prev; /\* address of previous next element \*/ / \} /\* \* List access methods \*/ \#define LIST\_FIRST(head) ((head)->lh\_first) \#define LIST\_END(head) NULL \#define LIST\_EMPTY(head) (LIST\_FIRST(head) == LIST\_END(head)) \#define LIST\_NEXT(elm, field) ((elm)->field.le\_next) \#define LIST\_FOREACH(var, head, field) / for((var) = LIST\_FIRST(head); / (var)!= LIST\_END(head); / (var) = LIST\_NEXT(var, field)) /\* \* List functions. \*/ \#define LIST\_INIT(head) do \{ / LIST\_FIRST(head) = LIST\_END(head); / \} while (0) \#define LIST\_INSERT\_AFTER(listelm, elm, field) do \{ / if (((elm)->field.le\_next = (listelm)->field.le\_next) != NULL) / (listelm)->field.le\_next->field.le\_prev = / &(elm)->field.le\_next; / (listelm)->field.le\_next = (elm); / (elm)->field.le\_prev = &(listelm)->field.le\_next; / \} while (0) \#define LIST\_INSERT\_BEFORE(listelm, elm, field) do \{ / (elm)->field.le\_prev = (listelm)->field.le\_prev; / (elm)->field.le\_next = (listelm); / \*(listelm)->field.le\_prev = (elm); / (listelm)->field.le\_prev = &(elm)->field.le\_next; / \} while (0) \#define LIST\_INSERT\_HEAD(head, elm, field) do \{ / if (((elm)->field.le\_next = (head)->lh\_first) != NULL) / (head)->lh\_first->field.le\_prev = &(elm)->field.le\_next;/ (head)->lh\_first = (elm); / (elm)->field.le\_prev = &(head)->lh\_first; / \} while (0) \#define LIST\_REMOVE(elm, field) do \{ / if ((elm)->field.le\_next != NULL) / (elm)->field.le\_next->field.le\_prev = / (elm)->field.le\_prev; / \*(elm)->field.le\_prev = (elm)->field.le\_next; / \_Q\_INVALIDATE((elm)->field.le\_prev); / \_Q\_INVALIDATE((elm)->field.le\_next); / \} while (0) \#define LIST\_REPLACE(elm, elm2, field) do \{ / if (((elm2)->field.le\_next = (elm)->field.le\_next) != NULL) / (elm2)->field.le\_next->field.le\_prev = / &(elm2)->field.le\_next; / (elm2)->field.le\_prev = (elm)->field.le\_prev; / \*(elm2)->field.le\_prev = (elm2); / \_Q\_INVALIDATE((elm)->field.le\_prev); / \_Q\_INVALIDATE((elm)->field.le\_next); / \} while (0) /\* \* Simple queue definitions. \*/ \#define SIMPLEQ\_HEAD(name, type) / struct name \{ / struct type \*sqh\_first; /\* first element \*/ / struct type \*\*sqh\_last; /\* addr of last next element \*/ / \} \#define SIMPLEQ\_HEAD\_INITIALIZER(head) / \{ NULL, &(head).sqh\_first \} \#define SIMPLEQ\_ENTRY(type) / struct \{ / struct type \*sqe\_next; /\* next element \*/ / \} /\* \* Simple queue access methods. \*/ \#define SIMPLEQ\_FIRST(head) ((head)->sqh\_first) \#define SIMPLEQ\_END(head) NULL \#define SIMPLEQ\_EMPTY(head) (SIMPLEQ\_FIRST(head) == SIMPLEQ\_END(head)) \#define SIMPLEQ\_NEXT(elm, field) ((elm)->field.sqe\_next) \#define SIMPLEQ\_FOREACH(var, head, field) / for((var) = SIMPLEQ\_FIRST(head); / (var) != SIMPLEQ\_END(head); / (var) = SIMPLEQ\_NEXT(var, field)) /\* \* Simple queue functions. \*/ \#define SIMPLEQ\_INIT(head) do \{ / (head)->sqh\_first = NULL; / (head)->sqh\_last = &(head)->sqh\_first; / \} while (0) \#define SIMPLEQ\_INSERT\_HEAD(head, elm, field) do \{ / if (((elm)->field.sqe\_next = (head)->sqh\_first) == NULL) / (head)->sqh\_last = &(elm)->field.sqe\_next; / (head)->sqh\_first = (elm); / \} while (0) \#define SIMPLEQ\_INSERT\_TAIL(head, elm, field) do \{ / (elm)->field.sqe\_next = NULL; / \*(head)->sqh\_last = (elm); / (head)->sqh\_last = &(elm)->field.sqe\_next; / \} while (0) \#define SIMPLEQ\_INSERT\_AFTER(head, listelm, elm, field) do \{ / if (((elm)->field.sqe\_next = (listelm)->field.sqe\_next) == NULL)/ (head)->sqh\_last = &(elm)->field.sqe\_next; / (listelm)->field.sqe\_next = (elm); / \} while (0) \#define SIMPLEQ\_REMOVE\_HEAD(head, field) do \{ / if (((head)->sqh\_first = (head)->sqh\_first->field.sqe\_next) == NULL) / (head)->sqh\_last = &(head)->sqh\_first; / \} while (0) /\* \* Tail queue definitions. \*/ \#define TAILQ\_HEAD(name, type) / struct name \{ / struct type \*tqh\_first; /\* first element \*/ / struct type \*\*tqh\_last; /\* addr of last next element \*/ / \} \#define TAILQ\_HEAD\_INITIALIZER(head) / \{ NULL, &(head).tqh\_first \} \#define TAILQ\_ENTRY(type) / struct \{ / struct type \*tqe\_next; /\* next element \*/ / struct type \*\*tqe\_prev; /\* address of previous next element \*/ / \} /\* \* tail queue access methods \*/ \#define TAILQ\_FIRST(head) ((head)->tqh\_first) \#define TAILQ\_END(head) NULL \#define TAILQ\_NEXT(elm, field) ((elm)->field.tqe\_next) \#define TAILQ\_LAST(head, headname) / (\*(((struct headname \*)((head)->tqh\_last))->tqh\_last)) /\* XXX \*/ \#define TAILQ\_PREV(elm, headname, field) / (\*(((struct headname \*)((elm)->field.tqe\_prev))->tqh\_last)) \#define TAILQ\_EMPTY(head) / (TAILQ\_FIRST(head) == TAILQ\_END(head)) \#define TAILQ\_FOREACH(var, head, field) / for((var) = TAILQ\_FIRST(head); / (var) != TAILQ\_END(head); / (var) = TAILQ\_NEXT(var, field)) \#define TAILQ\_FOREACH\_REVERSE(var, head, headname, field) / for((var) = TAILQ\_LAST(head, headname); / (var) != TAILQ\_END(head); / (var) = TAILQ\_PREV(var, headname, field)) /\* \* Tail queue functions. \*/ \#define TAILQ\_INIT(head) do \{ / (head)->tqh\_first = NULL; / (head)->tqh\_last = &(head)->tqh\_first; / \} while (0) \#define TAILQ\_INSERT\_HEAD(head, elm, field) do \{ / if (((elm)->field.tqe\_next = (head)->tqh\_first) != NULL) / (head)->tqh\_first->field.tqe\_prev = / &(elm)->field.tqe\_next; / else / (head)->tqh\_last = &(elm)->field.tqe\_next; / (head)->tqh\_first = (elm); / (elm)->field.tqe\_prev = &(head)->tqh\_first; / \} while (0) \#define TAILQ\_INSERT\_TAIL(head, elm, field) do \{ / (elm)->field.tqe\_next = NULL; / (elm)->field.tqe\_prev = (head)->tqh\_last; / \*(head)->tqh\_last = (elm); / (head)->tqh\_last = &(elm)->field.tqe\_next; / \} while (0) \#define TAILQ\_INSERT\_AFTER(head, listelm, elm, field) do \{ / if (((elm)->field.tqe\_next = (listelm)->field.tqe\_next) != NULL)/ (elm)->field.tqe\_next->field.tqe\_prev = / &(elm)->field.tqe\_next; / else / (head)->tqh\_last = &(elm)->field.tqe\_next; / (listelm)->field.tqe\_next = (elm); / (elm)->field.tqe\_prev = &(listelm)->field.tqe\_next; / \} while (0) \#define TAILQ\_INSERT\_BEFORE(listelm, elm, field) do \{ / (elm)->field.tqe\_prev = (listelm)->field.tqe\_prev; / (elm)->field.tqe\_next = (listelm); / \*(listelm)->field.tqe\_prev = (elm); / (listelm)->field.tqe\_prev = &(elm)->field.tqe\_next; / \} while (0) \#define TAILQ\_REMOVE(head, elm, field) do \{ / if (((elm)->field.tqe\_next) != NULL) / (elm)->field.tqe\_next->field.tqe\_prev = / (elm)->field.tqe\_prev; / else / (head)->tqh\_last = (elm)->field.tqe\_prev; / \*(elm)->field.tqe\_prev = (elm)->field.tqe\_next; / \_Q\_INVALIDATE((elm)->field.tqe\_prev); / \_Q\_INVALIDATE((elm)->field.tqe\_next); / \} while (0) \#define TAILQ\_REPLACE(head, elm, elm2, field) do \{ / if (((elm2)->field.tqe\_next = (elm)->field.tqe\_next) != NULL) / (elm2)->field.tqe\_next->field.tqe\_prev = / &(elm2)->field.tqe\_next; / else / (head)->tqh\_last = &(elm2)->field.tqe\_next; / (elm2)->field.tqe\_prev = (elm)->field.tqe\_prev; / \*(elm2)->field.tqe\_prev = (elm2); / \_Q\_INVALIDATE((elm)->field.tqe\_prev); / \_Q\_INVALIDATE((elm)->field.tqe\_next); / \} while (0) /\* \* Circular queue definitions. \*/ \#define CIRCLEQ\_HEAD(name, type) / struct name \{ / struct type \*cqh\_first; /\* first element \*/ / struct type \*cqh\_last; /\* last element \*/ / \} \#define CIRCLEQ\_HEAD\_INITIALIZER(head) / \{ CIRCLEQ\_END(&head), CIRCLEQ\_END(&head) \} \#define CIRCLEQ\_ENTRY(type) / struct \{ / struct type \*cqe\_next; /\* next element \*/ / struct type \*cqe\_prev; /\* previous element \*/ / \} /\* \* Circular queue access methods \*/ \#define CIRCLEQ\_FIRST(head) ((head)->cqh\_first) \#define CIRCLEQ\_LAST(head) ((head)->cqh\_last) \#define CIRCLEQ\_END(head) ((void \*)(head)) \#define CIRCLEQ\_NEXT(elm, field) ((elm)->field.cqe\_next) \#define CIRCLEQ\_PREV(elm, field) ((elm)->field.cqe\_prev) \#define CIRCLEQ\_EMPTY(head) / (CIRCLEQ\_FIRST(head) == CIRCLEQ\_END(head)) \#define CIRCLEQ\_FOREACH(var, head, field) / for((var) = CIRCLEQ\_FIRST(head); / (var) != CIRCLEQ\_END(head); / (var) = CIRCLEQ\_NEXT(var, field)) \#define CIRCLEQ\_FOREACH\_REVERSE(var, head, field) / for((var) = CIRCLEQ\_LAST(head); / (var) != CIRCLEQ\_END(head); / (var) = CIRCLEQ\_PREV(var, field)) /\* \* Circular queue functions. \*/ \#define CIRCLEQ\_INIT(head) do \{ / (head)->cqh\_first = CIRCLEQ\_END(head); / (head)->cqh\_last = CIRCLEQ\_END(head); / \} while (0) \#define CIRCLEQ\_INSERT\_AFTER(head, listelm, elm, field) do \{ / (elm)->field.cqe\_next = (listelm)->field.cqe\_next; / (elm)->field.cqe\_prev = (listelm); / if ((listelm)->field.cqe\_next == CIRCLEQ\_END(head)) / (head)->cqh\_last = (elm); / else / (listelm)->field.cqe\_next->field.cqe\_prev = (elm); / (listelm)->field.cqe\_next = (elm); / \} while (0) \#define CIRCLEQ\_INSERT\_BEFORE(head, listelm, elm, field) do \{ / (elm)->field.cqe\_next = (listelm); / (elm)->field.cqe\_prev = (listelm)->field.cqe\_prev; / if ((listelm)->field.cqe\_prev == CIRCLEQ\_END(head)) / (head)->cqh\_first = (elm); / else / (listelm)->field.cqe\_prev->field.cqe\_next = (elm); / (listelm)->field.cqe\_prev = (elm); / \} while (0) \#define CIRCLEQ\_INSERT\_HEAD(head, elm, field) do \{ / (elm)->field.cqe\_next = (head)->cqh\_first; / (elm)->field.cqe\_prev = CIRCLEQ\_END(head); / if ((head)->cqh\_last == CIRCLEQ\_END(head)) / (head)->cqh\_last = (elm); / else / (head)->cqh\_first->field.cqe\_prev = (elm); / (head)->cqh\_first = (elm); / \} while (0) \#define CIRCLEQ\_INSERT\_TAIL(head, elm, field) do \{ / (elm)->field.cqe\_next = CIRCLEQ\_END(head); / (elm)->field.cqe\_prev = (head)->cqh\_last; / if ((head)->cqh\_first == CIRCLEQ\_END(head)) / (head)->cqh\_first = (elm); / else / (head)->cqh\_last->field.cqe\_next = (elm); / (head)->cqh\_last = (elm); / \} while (0) \#define CIRCLEQ\_REMOVE(head, elm, field) do \{ / if ((elm)->field.cqe\_next == CIRCLEQ\_END(head)) / (head)->cqh\_last = (elm)->field.cqe\_prev; / else / (elm)->field.cqe\_next->field.cqe\_prev = / (elm)->field.cqe\_prev; / if ((elm)->field.cqe\_prev == CIRCLEQ\_END(head)) / (head)->cqh\_first = (elm)->field.cqe\_next; / else / (elm)->field.cqe\_prev->field.cqe\_next = / (elm)->field.cqe\_next; / \_Q\_INVALIDATE((elm)->field.cqe\_prev); / \_Q\_INVALIDATE((elm)->field.cqe\_next); / \} while (0) \#define CIRCLEQ\_REPLACE(head, elm, elm2, field) do \{ / if (((elm2)->field.cqe\_next = (elm)->field.cqe\_next) == / CIRCLEQ\_END(head)) / (head).cqh\_last = (elm2); / else / (elm2)->field.cqe\_next->field.cqe\_prev = (elm2); / if (((elm2)->field.cqe\_prev = (elm)->field.cqe\_prev) == / CIRCLEQ\_END(head)) / (head).cqh\_first = (elm2); / else / (elm2)->field.cqe\_prev->field.cqe\_next = (elm2); / \_Q\_INVALIDATE((elm)->field.cqe\_prev); / \_Q\_INVALIDATE((elm)->field.cqe\_next); / \} while (0) \#endif /\* !\_SYS\_QUEUE\_H\_ \*/

[http_trac.openrays.org_projects_pmon_browser_trunk_sys_sys_queue.h_rev_2]: http://trac.openrays.org/projects/pmon/browser/trunk/sys/sys/queue.h?rev=2