Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

queue.h @ 684

Last change on this file since 684 was 444, checked in by satin@…, 7 years ago
add newlib,libalmos-mkh, restructure shared_syscalls.h and mini-libc
File size: 18.4 KB

Line
1	//####BSDCOPYRIGHTBEGIN####
2	//
3	// -------------------------------------------
4	//
5	// Portions of this software may have been derived from OpenBSD,
6	// FreeBSD or other sources, and are covered by the appropriate
7	// copyright disclaimers included herein.
8	//
9	// Portions created by Red Hat are
10	// Copyright (C) 2002 Red Hat, Inc. All Rights Reserved.
11	//
12	// -------------------------------------------
13	//
14	//####BSDCOPYRIGHTEND####
15	//==========================================================================
16
17	/*
18	* Copyright (c) 1991, 1993
19	* The Regents of the University of California. All rights reserved.
20	*
21	* Redistribution and use in source and binary forms, with or without
22	* modification, are permitted provided that the following conditions
23	* are met:
24	* 1. Redistributions of source code must retain the above copyright
25	* notice, this list of conditions and the following disclaimer.
26	* 2. Redistributions in binary form must reproduce the above copyright
27	* notice, this list of conditions and the following disclaimer in the
28	* documentation and/or other materials provided with the distribution.
29	* 3. All advertising materials mentioning features or use of this software
30	* must display the following acknowledgement:
31	* This product includes software developed by the University of
32	* California, Berkeley and its contributors.
33	* 4. Neither the name of the University nor the names of its contributors
34	* may be used to endorse or promote products derived from this software
35	* without specific prior written permission.
36	*
37	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
38	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
40	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
41	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
42	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
43	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
45	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
46	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47	* SUCH DAMAGE.
48	*
49	* @(#)queue.h 8.5 (Berkeley) 8/20/94
50	* $FreeBSD: src/sys/sys/queue.h,v 1.32.2.4 2001/03/31 03:33:39 hsu Exp $
51	*/
52
53	#ifndef _SYS_QUEUE_H_
54	#define _SYS_QUEUE_H_
55
56	#ifndef __ASSEMBLER__
57
58	/*
59	* This file defines five types of data structures: singly-linked lists,
60	* singly-linked tail queues, lists, tail queues, and circular queues.
61	*
62	* A singly-linked list is headed by a single forward pointer. The elements
63	* are singly linked for minimum space and pointer manipulation overhead at
64	* the expense of O(n) removal for arbitrary elements. New elements can be
65	* added to the list after an existing element or at the head of the list.
66	* Elements being removed from the head of the list should use the explicit
67	* macro for this purpose for optimum efficiency. A singly-linked list may
68	* only be traversed in the forward direction. Singly-linked lists are ideal
69	* for applications with large datasets and few or no removals or for
70	* implementing a LIFO queue.
71	*
72	* A singly-linked tail queue is headed by a pair of pointers, one to the
73	* head of the list and the other to the tail of the list. The elements are
74	* singly linked for minimum space and pointer manipulation overhead at the
75	* expense of O(n) removal for arbitrary elements. New elements can be added
76	* to the list after an existing element, at the head of the list, or at the
77	* end of the list. Elements being removed from the head of the tail queue
78	* should use the explicit macro for this purpose for optimum efficiency.
79	* A singly-linked tail queue may only be traversed in the forward direction.
80	* Singly-linked tail queues are ideal for applications with large datasets
81	* and few or no removals or for implementing a FIFO queue.
82	*
83	* A list is headed by a single forward pointer (or an array of forward
84	* pointers for a hash table header). The elements are doubly linked
85	* so that an arbitrary element can be removed without a need to
86	* traverse the list. New elements can be added to the list before
87	* or after an existing element or at the head of the list. A list
88	* may only be traversed in the forward direction.
89	*
90	* A tail queue is headed by a pair of pointers, one to the head of the
91	* list and the other to the tail of the list. The elements are doubly
92	* linked so that an arbitrary element can be removed without a need to
93	* traverse the list. New elements can be added to the list before or
94	* after an existing element, at the head of the list, or at the end of
95	* the list. A tail queue may be traversed in either direction.
96	*
97	* A circle queue is headed by a pair of pointers, one to the head of the
98	* list and the other to the tail of the list. The elements are doubly
99	* linked so that an arbitrary element can be removed without a need to
100	* traverse the list. New elements can be added to the list before or after
101	* an existing element, at the head of the list, or at the end of the list.
102	* A circle queue may be traversed in either direction, but has a more
103	* complex end of list detection.
104	*
105	* For details on the use of these macros, see the queue(3) manual page.
106	*
107	*
108	* SLIST LIST STAILQ TAILQ CIRCLEQ
109	* _HEAD + + + + +
110	* _ENTRY + + + + +
111	* _INIT + + + + +
112	* _EMPTY + + + + +
113	* _FIRST + + + + +
114	* _NEXT + + + + +
115	* _PREV - - - + +
116	* _LAST - - + + +
117	* _FOREACH + + + + +
118	* _FOREACH_REVERSE - - - + +
119	* _INSERT_HEAD + + + + +
120	* _INSERT_BEFORE - + - + +
121	* _INSERT_AFTER + + + + +
122	* _INSERT_TAIL - - + + +
123	* _REMOVE_HEAD + - + - -
124	* _REMOVE + + + + +
125	*
126	*/
127
128	/*
129	* Singly-linked List definitions.
130	*/
131	#define SLIST_HEAD(name, type) \
132	struct name { \
133	struct type slh_first; / first element */ \
134	}
135
136	#define SLIST_HEAD_INITIALIZER(head) \
137	{ NULL }
138
139	#define SLIST_ENTRY(type) \
140	struct { \
141	struct type sle_next; / next element */ \
142	}
143
144	/*
145	* Singly-linked List functions.
146	*/
147	#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
148
149	#define SLIST_FIRST(head) ((head)->slh_first)
150
151	#define SLIST_FOREACH(var, head, field) \
152	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
153
154	#define SLIST_INIT(head) { \
155	(head)->slh_first = NULL; \
156	}
157
158	#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
159	(elm)->field.sle_next = (slistelm)->field.sle_next; \
160	(slistelm)->field.sle_next = (elm); \
161	} while (0)
162
163	#define SLIST_INSERT_HEAD(head, elm, field) do { \
164	(elm)->field.sle_next = (head)->slh_first; \
165	(head)->slh_first = (elm); \
166	} while (0)
167
168	#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
169
170	#define SLIST_REMOVE_HEAD(head, field) do { \
171	(head)->slh_first = (head)->slh_first->field.sle_next; \
172	} while (0)
173
174	#define SLIST_REMOVE(head, elm, type, field) do { \
175	if ((head)->slh_first == (elm)) { \
176	SLIST_REMOVE_HEAD((head), field); \
177	} \
178	else { \
179	struct type *curelm = (head)->slh_first; \
180	while( curelm->field.sle_next != (elm) ) \
181	curelm = curelm->field.sle_next; \
182	curelm->field.sle_next = \
183	curelm->field.sle_next->field.sle_next; \
184	} \
185	} while (0)
186
187	/*
188	* Singly-linked Tail queue definitions.
189	*/
190	#define STAILQ_HEAD(name, type) \
191	struct name { \
192	struct type stqh_first;/ first element */ \
193	struct type *stqh_last;/ addr of last next element */ \
194	}
195
196	#define STAILQ_HEAD_INITIALIZER(head) \
197	{ NULL, &(head).stqh_first }
198
199	#define STAILQ_ENTRY(type) \
200	struct { \
201	struct type stqe_next; / next element */ \
202	}
203
204	/*
205	* Singly-linked Tail queue functions.
206	*/
207	#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
208
209	#define STAILQ_INIT(head) do { \
210	(head)->stqh_first = NULL; \
211	(head)->stqh_last = &(head)->stqh_first; \
212	} while (0)
213
214	#define STAILQ_FIRST(head) ((head)->stqh_first)
215
216	#define STAILQ_LAST(head, type, field) \
217	(STAILQ_EMPTY(head) ? \
218	NULL : \
219	((struct type *) \
220	((char *)((head)->stqh_last) - __offsetof(struct type, field))))
221
222	#define STAILQ_FOREACH(var, head, field) \
223	for((var) = (head)->stqh_first; (var); (var) = (var)->field.stqe_next)
224
225	#define STAILQ_INSERT_HEAD(head, elm, field) do { \
226	if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
227	(head)->stqh_last = &(elm)->field.stqe_next; \
228	(head)->stqh_first = (elm); \
229	} while (0)
230
231	#define STAILQ_INSERT_TAIL(head, elm, field) do { \
232	(elm)->field.stqe_next = NULL; \
233	*(head)->stqh_last = (elm); \
234	(head)->stqh_last = &(elm)->field.stqe_next; \
235	} while (0)
236
237	#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
238	if (((elm)->field.stqe_next = (tqelm)->field.stqe_next) == NULL)\
239	(head)->stqh_last = &(elm)->field.stqe_next; \
240	(tqelm)->field.stqe_next = (elm); \
241	} while (0)
242
243	#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
244
245	#define STAILQ_REMOVE_HEAD(head, field) do { \
246	if (((head)->stqh_first = \
247	(head)->stqh_first->field.stqe_next) == NULL) \
248	(head)->stqh_last = &(head)->stqh_first; \
249	} while (0)
250
251	#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
252	if (((head)->stqh_first = (elm)->field.stqe_next) == NULL) \
253	(head)->stqh_last = &(head)->stqh_first; \
254	} while (0)
255
256	#define STAILQ_REMOVE(head, elm, type, field) do { \
257	if ((head)->stqh_first == (elm)) { \
258	STAILQ_REMOVE_HEAD(head, field); \
259	} \
260	else { \
261	struct type *curelm = (head)->stqh_first; \
262	while( curelm->field.stqe_next != (elm) ) \
263	curelm = curelm->field.stqe_next; \
264	if((curelm->field.stqe_next = \
265	curelm->field.stqe_next->field.stqe_next) == NULL) \
266	(head)->stqh_last = &(curelm)->field.stqe_next; \
267	} \
268	} while (0)
269
270	/*
271	* List definitions.
272	*/
273	#define LIST_HEAD(name, type) \
274	struct name { \
275	struct type lh_first; / first element */ \
276	}
277
278	#define LIST_HEAD_INITIALIZER(head) \
279	{ NULL }
280
281	#define LIST_ENTRY(type) \
282	struct { \
283	struct type le_next; / next element */ \
284	struct type *le_prev; / address of previous next element */ \
285	}
286
287	/*
288	* List functions.
289	*/
290
291	#define LIST_EMPTY(head) ((head)->lh_first == NULL)
292
293	#define LIST_FIRST(head) ((head)->lh_first)
294
295	#define LIST_FOREACH(var, head, field) \
296	for((var) = (head)->lh_first; (var); (var) = (var)->field.le_next)
297
298	#define LIST_INIT(head) do { \
299	(head)->lh_first = NULL; \
300	} while (0)
301
302	#define LIST_INSERT_AFTER(listelm, elm, field) do { \
303	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
304	(listelm)->field.le_next->field.le_prev = \
305	&(elm)->field.le_next; \
306	(listelm)->field.le_next = (elm); \
307	(elm)->field.le_prev = &(listelm)->field.le_next; \
308	} while (0)
309
310	#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
311	(elm)->field.le_prev = (listelm)->field.le_prev; \
312	(elm)->field.le_next = (listelm); \
313	*(listelm)->field.le_prev = (elm); \
314	(listelm)->field.le_prev = &(elm)->field.le_next; \
315	} while (0)
316
317	#define LIST_INSERT_HEAD(head, elm, field) do { \
318	if (((elm)->field.le_next = (head)->lh_first) != NULL) \
319	(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
320	(head)->lh_first = (elm); \
321	(elm)->field.le_prev = &(head)->lh_first; \
322	} while (0)
323
324	#define LIST_NEXT(elm, field) ((elm)->field.le_next)
325
326	#define LIST_REMOVE(elm, field) do { \
327	if ((elm)->field.le_next != NULL) \
328	(elm)->field.le_next->field.le_prev = \
329	(elm)->field.le_prev; \
330	*(elm)->field.le_prev = (elm)->field.le_next; \
331	} while (0)
332
333	/*
334	* Tail queue definitions.
335	*/
336	#define TAILQ_HEAD(name, type) \
337	struct name { \
338	struct type tqh_first; / first element */ \
339	struct type *tqh_last; / addr of last next element */ \
340	char *tqh_name; \
341	}
342
343	#define TAILQ_HEAD_INITIALIZER(head) \
344	{ NULL, &(head).tqh_first, 0 }
345
346	#define TAILQ_ENTRY(type) \
347	struct { \
348	struct type tqe_next; / next element */ \
349	struct type *tqe_prev; / address of previous next element */ \
350	}
351
352	/*
353	* Tail queue functions.
354	*/
355	#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
356
357	#define TAILQ_HASTWO(head, field) ((!TAILQ_EMPTY(head)) && TAILQ_NEXT(TAILQ_FIRST(head),field))
358
359	#define TAILQ_FOREACH(var, head, field) \
360	for (var = TAILQ_FIRST(head); var; var = TAILQ_NEXT(var, field))
361
362	#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
363	for ((var) = TAILQ_LAST((head), headname); \
364	(var); \
365	(var) = TAILQ_PREV((var), headname, field))
366
367	#define TAILQ_FIRST(head) ((head)->tqh_first)
368
369	#define TAILQ_LAST(head, headname) \
370	((((struct headname )((head)->tqh_last))->tqh_last))
371
372	#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
373
374	#define TAILQ_PREV(elm, headname, field) \
375	((((struct headname )((elm)->field.tqe_prev))->tqh_last))
376
377	#define TAILQ_INIT(head) do { \
378	(head)->tqh_first = NULL; \
379	(head)->tqh_last = &(head)->tqh_first; \
380	(head)->tqh_name = 0; \
381	} while (0)
382
383	#define TAILQ_INSERT_HEAD(head, elm, field) do { \
384	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
385	(head)->tqh_first->field.tqe_prev = \
386	&(elm)->field.tqe_next; \
387	else \
388	(head)->tqh_last = &(elm)->field.tqe_next; \
389	(head)->tqh_first = (elm); \
390	(elm)->field.tqe_prev = &(head)->tqh_first; \
391	} while (0)
392
393	#define TAILQ_INSERT_TAIL(head, elm, field) do { \
394	(elm)->field.tqe_next = NULL; \
395	(elm)->field.tqe_prev = (head)->tqh_last; \
396	*(head)->tqh_last = (elm); \
397	(head)->tqh_last = &(elm)->field.tqe_next; \
398	} while (0)
399
400	#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
401	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
402	(elm)->field.tqe_next->field.tqe_prev = \
403	&(elm)->field.tqe_next; \
404	else \
405	(head)->tqh_last = &(elm)->field.tqe_next; \
406	(listelm)->field.tqe_next = (elm); \
407	(elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
408	} while (0)
409
410	#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
411	(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
412	(elm)->field.tqe_next = (listelm); \
413	*(listelm)->field.tqe_prev = (elm); \
414	(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
415	} while (0)
416
417	#define TAILQ_REMOVE(head, elm, field) do { \
418	if (((elm)->field.tqe_next) != NULL) \
419	(elm)->field.tqe_next->field.tqe_prev = \
420	(elm)->field.tqe_prev; \
421	else \
422	(head)->tqh_last = (elm)->field.tqe_prev; \
423	*(elm)->field.tqe_prev = (elm)->field.tqe_next; \
424	(elm)->field.tqe_next = 0; \
425	(elm)->field.tqe_prev = 0; /* mark removed */ \
426	} while (0)
427
428	#define TAILQ_REMOVED(elm, field) ((elm)->field.tqe_next == NULL && (elm)->field.tqe_prev == NULL)
429
430	/*
431	* Circular queue definitions.
432	*/
433	#define CIRCLEQ_HEAD(name, type) \
434	struct name { \
435	struct type cqh_first; / first element */ \
436	struct type cqh_last; / last element */ \
437	}
438
439	#define CIRCLEQ_ENTRY(type) \
440	struct { \
441	struct type cqe_next; / next element */ \
442	struct type cqe_prev; / previous element */ \
443	}
444
445	/*
446	* Circular queue functions.
447	*/
448	#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
449
450	#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
451
452	#define CIRCLEQ_FOREACH(var, head, field) \
453	for((var) = (head)->cqh_first; \
454	(var) != (void *)(head); \
455	(var) = (var)->field.cqe_next)
456
457	#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
458	for((var) = (head)->cqh_last; \
459	(var) != (void *)(head); \
460	(var) = (var)->field.cqe_prev)
461
462	#define CIRCLEQ_INIT(head) do { \
463	(head)->cqh_first = (void *)(head); \
464	(head)->cqh_last = (void *)(head); \
465	} while (0)
466
467	#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
468	(elm)->field.cqe_next = (listelm)->field.cqe_next; \
469	(elm)->field.cqe_prev = (listelm); \
470	if ((listelm)->field.cqe_next == (void *)(head)) \
471	(head)->cqh_last = (elm); \
472	else \
473	(listelm)->field.cqe_next->field.cqe_prev = (elm); \
474	(listelm)->field.cqe_next = (elm); \
475	} while (0)
476
477	#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
478	(elm)->field.cqe_next = (listelm); \
479	(elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
480	if ((listelm)->field.cqe_prev == (void *)(head)) \
481	(head)->cqh_first = (elm); \
482	else \
483	(listelm)->field.cqe_prev->field.cqe_next = (elm); \
484	(listelm)->field.cqe_prev = (elm); \
485	} while (0)
486
487	#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
488	(elm)->field.cqe_next = (head)->cqh_first; \
489	(elm)->field.cqe_prev = (void *)(head); \
490	if ((head)->cqh_last == (void *)(head)) \
491	(head)->cqh_last = (elm); \
492	else \
493	(head)->cqh_first->field.cqe_prev = (elm); \
494	(head)->cqh_first = (elm); \
495	} while (0)
496
497	#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
498	(elm)->field.cqe_next = (void *)(head); \
499	(elm)->field.cqe_prev = (head)->cqh_last; \
500	if ((head)->cqh_first == (void *)(head)) \
501	(head)->cqh_first = (elm); \
502	else \
503	(head)->cqh_last->field.cqe_next = (elm); \
504	(head)->cqh_last = (elm); \
505	} while (0)
506
507	#define CIRCLEQ_LAST(head) ((head)->cqh_last)
508
509	#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)
510
511	#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
512
513	#define CIRCLEQ_REMOVE(head, elm, field) do { \
514	if ((elm)->field.cqe_next == (void *)(head)) \
515	(head)->cqh_last = (elm)->field.cqe_prev; \
516	else \
517	(elm)->field.cqe_next->field.cqe_prev = \
518	(elm)->field.cqe_prev; \
519	if ((elm)->field.cqe_prev == (void *)(head)) \
520	(head)->cqh_first = (elm)->field.cqe_next; \
521	else \
522	(elm)->field.cqe_prev->field.cqe_next = \
523	(elm)->field.cqe_next; \
524	} while (0)
525
526	/*
527	* XXX insque() and remque() are an old way of handling certain queues.
528	* They bogusly assumes that all queue heads look alike.
529	*/
530
531	struct quehead
532	{
533	struct quehead *qh_link;
534	struct quehead *qh_rlink;
535	};
536
537	#ifdef __GNUC__
538
539	static __inline void
540	insque (void a, void b)
541	{
542	struct quehead element = a, head = b;
543
544	element->qh_link = head->qh_link;
545	element->qh_rlink = head;
546	head->qh_link = element;
547	element->qh_link->qh_rlink = element;
548	}
549
550	static __inline void
551	remque (void *a)
552	{
553	struct quehead *element = a;
554
555	element->qh_link->qh_rlink = element->qh_rlink;
556	element->qh_rlink->qh_link = element->qh_link;
557	element->qh_rlink = 0;
558	}
559
560	#else /* !__GNUC__ */
561
562	void insque __P ((void a, void b));
563	void remque __P ((void *a));
564
565	#endif /* __GNUC__ */
566
567	#endif /* __ASSEMBLER__ */
568
569
570	#endif /* !_SYS_QUEUE_H_ */

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: trunk/libs/newlib/src/libgloss/sparc_leon/asm-leon/queue.h @ 684

Download in other formats: