![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to queue.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / bsd / sys|
Return to queue.h CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / sys |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */
26: /*
27: * Copyright (c) 1991, 1993
28: * The Regents of the University of California. All rights reserved.
29: *
30: * Redistribution and use in source and binary forms, with or without
31: * modification, are permitted provided that the following conditions
32: * are met:
33: * 1. Redistributions of source code must retain the above copyright
34: * notice, this list of conditions and the following disclaimer.
35: * 2. Redistributions in binary form must reproduce the above copyright
36: * notice, this list of conditions and the following disclaimer in the
37: * documentation and/or other materials provided with the distribution.
38: * 3. All advertising materials mentioning features or use of this software
39: * must display the following acknowledgement:
40: * This product includes software developed by the University of
41: * California, Berkeley and its contributors.
42: * 4. Neither the name of the University nor the names of its contributors
43: * may be used to endorse or promote products derived from this software
44: * without specific prior written permission.
45: *
46: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
47: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
48: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
49: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
50: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
51: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
52: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
53: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
54: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
55: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
56: * SUCH DAMAGE.
57: *
58: * @(#)queue.h 8.5 (Berkeley) 8/20/94
59: */
60:
61: #ifndef _SYS_QUEUE_H_
62: #define _SYS_QUEUE_H_
63:
64: /*
65: * This file defines three types of data structures: lists, tail queues,
66: * and circular queues.
67: *
68: * A list is headed by a single forward pointer (or an array of forward
69: * pointers for a hash table header). The elements are doubly linked
70: * 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
72: * or after an existing element or at the head of the list. A list
73: * may only be traversed in the forward direction.
74: *
75: * A tail 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
79: * after an existing element, at the head of the list, or at the end of
80: * the list. A tail queue may only be traversed in the forward direction.
81: *
82: * A circle 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 after
86: * an existing element, at the head of the list, or at the end of the list.
87: * A circle queue may be traversed in either direction, but has a more
88: * complex end of list detection.
89: *
90: * For details on the use of these macros, see the queue(3) manual page.
91: */
92:
93: /*
94: * List definitions.
95: */
96: #define LIST_HEAD(name, type) \
97: struct name { \
98: struct type *lh_first; /* first element */ \
99: }
100:
101: #define LIST_ENTRY(type) \
102: struct { \
103: struct type *le_next; /* next element */ \
104: struct type **le_prev; /* address of previous next element */ \
105: }
106:
107: /*
108: * List functions.
109: */
110: #define LIST_INIT(head) { \
111: (head)->lh_first = NULL; \
112: }
113:
114: #define LIST_INSERT_AFTER(listelm, elm, field) { \
115: if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
116: (listelm)->field.le_next->field.le_prev = \
117: &(elm)->field.le_next; \
118: (listelm)->field.le_next = (elm); \
119: (elm)->field.le_prev = &(listelm)->field.le_next; \
120: }
121:
122: #define LIST_INSERT_BEFORE(listelm, elm, field) { \
123: (elm)->field.le_prev = (listelm)->field.le_prev; \
124: (elm)->field.le_next = (listelm); \
125: *(listelm)->field.le_prev = (elm); \
126: (listelm)->field.le_prev = &(elm)->field.le_next; \
127: }
128:
129: #define LIST_INSERT_HEAD(head, elm, field) { \
130: if (((elm)->field.le_next = (head)->lh_first) != NULL) \
131: (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
132: (head)->lh_first = (elm); \
133: (elm)->field.le_prev = &(head)->lh_first; \
134: }
135:
136: #define LIST_REMOVE(elm, field) { \
137: if ((elm)->field.le_next != NULL) \
138: (elm)->field.le_next->field.le_prev = \
139: (elm)->field.le_prev; \
140: *(elm)->field.le_prev = (elm)->field.le_next; \
141: }
142:
143: /*
144: * Tail queue definitions.
145: */
146: #define TAILQ_HEAD(name, type) \
147: struct name { \
148: struct type *tqh_first; /* first element */ \
149: struct type **tqh_last; /* addr of last next element */ \
150: }
151:
152: #define TAILQ_ENTRY(type) \
153: struct { \
154: struct type *tqe_next; /* next element */ \
155: struct type **tqe_prev; /* address of previous next element */ \
156: }
157:
158: /*
159: * Tail queue functions.
160: */
161: #define TAILQ_INIT(head) { \
162: (head)->tqh_first = NULL; \
163: (head)->tqh_last = &(head)->tqh_first; \
164: }
165:
166: #define TAILQ_INSERT_HEAD(head, elm, field) { \
167: if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
168: (head)->tqh_first->field.tqe_prev = \
169: &(elm)->field.tqe_next; \
170: else \
171: (head)->tqh_last = &(elm)->field.tqe_next; \
172: (head)->tqh_first = (elm); \
173: (elm)->field.tqe_prev = &(head)->tqh_first; \
174: }
175:
176: #define TAILQ_INSERT_TAIL(head, elm, field) { \
177: (elm)->field.tqe_next = NULL; \
178: (elm)->field.tqe_prev = (head)->tqh_last; \
179: *(head)->tqh_last = (elm); \
180: (head)->tqh_last = &(elm)->field.tqe_next; \
181: }
182:
183: #define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \
184: if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
185: (elm)->field.tqe_next->field.tqe_prev = \
186: &(elm)->field.tqe_next; \
187: else \
188: (head)->tqh_last = &(elm)->field.tqe_next; \
189: (listelm)->field.tqe_next = (elm); \
190: (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
191: }
192:
193: #define TAILQ_INSERT_BEFORE(listelm, elm, field) { \
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: }
199:
200: #define TAILQ_REMOVE(head, elm, field) { \
201: if (((elm)->field.tqe_next) != NULL) \
202: (elm)->field.tqe_next->field.tqe_prev = \
203: (elm)->field.tqe_prev; \
204: else \
205: (head)->tqh_last = (elm)->field.tqe_prev; \
206: *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
207: }
208:
209: /*
210: * Circular queue definitions.
211: */
212: #define CIRCLEQ_HEAD(name, type) \
213: struct name { \
214: struct type *cqh_first; /* first element */ \
215: struct type *cqh_last; /* last element */ \
216: }
217:
218: #define CIRCLEQ_ENTRY(type) \
219: struct { \
220: struct type *cqe_next; /* next element */ \
221: struct type *cqe_prev; /* previous element */ \
222: }
223:
224: /*
225: * Circular queue functions.
226: */
227: #define CIRCLEQ_INIT(head) { \
228: (head)->cqh_first = (void *)(head); \
229: (head)->cqh_last = (void *)(head); \
230: }
231:
232: #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \
233: (elm)->field.cqe_next = (listelm)->field.cqe_next; \
234: (elm)->field.cqe_prev = (listelm); \
235: if ((listelm)->field.cqe_next == (void *)(head)) \
236: (head)->cqh_last = (elm); \
237: else \
238: (listelm)->field.cqe_next->field.cqe_prev = (elm); \
239: (listelm)->field.cqe_next = (elm); \
240: }
241:
242: #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \
243: (elm)->field.cqe_next = (listelm); \
244: (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
245: if ((listelm)->field.cqe_prev == (void *)(head)) \
246: (head)->cqh_first = (elm); \
247: else \
248: (listelm)->field.cqe_prev->field.cqe_next = (elm); \
249: (listelm)->field.cqe_prev = (elm); \
250: }
251:
252: #define CIRCLEQ_INSERT_HEAD(head, elm, field) { \
253: (elm)->field.cqe_next = (head)->cqh_first; \
254: (elm)->field.cqe_prev = (void *)(head); \
255: if ((head)->cqh_last == (void *)(head)) \
256: (head)->cqh_last = (elm); \
257: else \
258: (head)->cqh_first->field.cqe_prev = (elm); \
259: (head)->cqh_first = (elm); \
260: }
261:
262: #define CIRCLEQ_INSERT_TAIL(head, elm, field) { \
263: (elm)->field.cqe_next = (void *)(head); \
264: (elm)->field.cqe_prev = (head)->cqh_last; \
265: if ((head)->cqh_first == (void *)(head)) \
266: (head)->cqh_first = (elm); \
267: else \
268: (head)->cqh_last->field.cqe_next = (elm); \
269: (head)->cqh_last = (elm); \
270: }
271:
272: #define CIRCLEQ_REMOVE(head, elm, field) { \
273: if ((elm)->field.cqe_next == (void *)(head)) \
274: (head)->cqh_last = (elm)->field.cqe_prev; \
275: else \
276: (elm)->field.cqe_next->field.cqe_prev = \
277: (elm)->field.cqe_prev; \
278: if ((elm)->field.cqe_prev == (void *)(head)) \
279: (head)->cqh_first = (elm)->field.cqe_next; \
280: else \
281: (elm)->field.cqe_prev->field.cqe_next = \
282: (elm)->field.cqe_next; \
283: }
284: #endif /* !_SYS_QUEUE_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.