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

Last change on this file since 643 was 444, checked in by satin@…, 6 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)                                          \
132struct name {                                                           \
133        struct type *slh_first; /* first element */                     \
134}
135
136#define SLIST_HEAD_INITIALIZER(head)                                    \
137        { NULL }
138
139#define SLIST_ENTRY(type)                                               \
140struct {                                                                \
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)                                         \
191struct 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)                                              \
200struct {                                                                \
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)                                           \
274struct name {                                                           \
275        struct type *lh_first;  /* first element */                     \
276}
277
278#define LIST_HEAD_INITIALIZER(head)                                     \
279        { NULL }
280
281#define LIST_ENTRY(type)                                                \
282struct {                                                                \
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)                                          \
337struct 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)                                               \
347struct {                                                                \
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)                                        \
434struct name {                                                           \
435        struct type *cqh_first;         /* first element */             \
436        struct type *cqh_last;          /* last element */              \
437}
438
439#define CIRCLEQ_ENTRY(type)                                             \
440struct {                                                                \
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
531struct quehead
532{
533  struct quehead *qh_link;
534  struct quehead *qh_rlink;
535};
536
537#ifdef  __GNUC__
538
539static __inline void
540insque (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
550static __inline void
551remque (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
562void insque __P ((void *a, void *b));
563void 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.