cc903d5d9f699372b38a3206fefd8fc306127bc9
[akaros.git] / inc / queue.h
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  * 4. 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.3 (Berkeley) 12/13/93
30  *
31  * For Jos, extra comments have been added to this file, and the original
32  * TAILQ and CIRCLEQ definitions have been removed.   - August 9, 2005
33  */
34
35 #ifndef ROS_INC_QUEUE_H
36 #define ROS_INC_QUEUE_H
37
38 /*
39  * A list is headed by a single forward pointer (or an array of forward
40  * pointers for a hash table header). The elements are doubly linked
41  * so that an arbitrary element can be removed without a need to
42  * traverse the list. New elements can be added to the list before
43  * or after an existing element or at the head of the list. A list
44  * may only be traversed in the forward direction.
45  */
46
47 /*
48  * An example using the below functions.
49  */
50 #if 0
51
52 typedef struct Frob
53 {
54         int frobozz;
55         LIST_ENTRY(frob_t) frob_link;   /* this contains the list element pointers */
56 } frob_t;
57
58 LIST_HEAD(frob_list_t, frob_t)          /* defines struct Frob_list as a list of Frob */
59
60 frob_list_t flist;                      /* declare a Frob list */
61
62 LIST_INIT(&flist);                      /* clear flist (globals are cleared anyway) */
63 flist = LIST_HEAD_INITIALIZER(&flist);  /* alternate way to clear flist */
64
65 if(LIST_EMPTY(&flist))                  /* check whether list is empty */
66         printf("list is empty\n");
67
68 frob_t *f = LIST_FIRST(&flist); /* f is first element in list */
69 f = LIST_NEXT(f, frob_link);            /* now f is next (second) element in list */
70 f = LIST_NEXT(f, frob_link);            /* now f is next (third) element in list */
71
72 for(f=LIST_FIRST(&flist); f != 0;       /* iterate over elements in flist */
73     f = LIST_NEXT(f, frob_link))
74         printf("f %d\n", f->frobozz);
75
76 LIST_FOREACH(f, &flist, frob_link)      /* alternate way to say that */
77         printf("f %d\n", f->frobozz);
78
79 f = LIST_NEXT(LIST_FIRST(&flist));      /* f is second element in list */
80 LIST_INSERT_AFTER(f, g, frob_link);     /* add g right after f in list */
81 LIST_REMOVE(g, frob_link);              /* remove g from list (can't insert twice!) */
82 LIST_INSERT_BEFORE(f, g, frob_link);    /* add g right before f */
83 LIST_REMOVE(g, frob_link);              /* remove g again */
84 LIST_INSERT_HEAD(&flist, g, frob_link); /* add g as first element in list */
85
86 #endif
87
88 /*
89  * List declarations.
90  */
91
92 /*
93  * A list is headed by a structure defined by the LIST_HEAD macro.  This structure con‐
94  * tains a single pointer to the first element on the list.  The elements are doubly
95  * linked so that an arbitrary element can be removed without traversing the list.  New
96  * elements can be added to the list after an existing element or at the head of the list.
97  * A LIST_HEAD structure is declared as follows:
98  * 
99  *       LIST_HEAD(HEADNAME, TYPE) head;
100  * 
101  * where HEADNAME is the name of the structure to be defined, and TYPE is the type of the
102  * elements to be linked into the list.  A pointer to the head of the list can later be
103  * declared as:
104  * 
105  *       HEADNAME *headp;
106  * 
107  * (The names head and headp are user selectable.)
108  */
109 #define LIST_HEAD(name, type)                                   \
110 typedef struct {                                                                \
111         type *lh_first; /* first element */                     \
112 } name;
113
114 /*
115  * Set a list head variable to LIST_HEAD_INITIALIZER(head)
116  * to reset it to the empty list.
117  */
118 #define LIST_HEAD_INITIALIZER(head)                                     \
119         { NULL }
120
121 /*
122  * Use this inside a structure "LIST_ENTRY(type) field" to use
123  * x as the list piece.
124  *
125  * The le_prev points at the pointer to the structure containing
126  * this very LIST_ENTRY, so that if we want to remove this list entry,
127  * we can do *le_prev = le_next to update the structure pointing at us.
128  */
129 #define LIST_ENTRY(type)                                                \
130 struct {                                                                \
131         type *le_next;  /* next element */                      \
132         type **le_prev; /* ptr to ptr to this element */        \
133 }
134
135 /*
136  * List functions.
137  */
138
139 /*
140  * Is the list named "head" empty?
141  */
142 #define LIST_EMPTY(head)        ((head)->lh_first == NULL)
143
144 /*
145  * Return the first element in the list named "head".
146  */
147 #define LIST_FIRST(head)        ((head)->lh_first)
148
149 /*
150  * Return the element after "elm" in the list.
151  * The "field" name is the link element as above.
152  */
153 #define LIST_NEXT(elm, field)   ((elm)->field.le_next)
154
155 /*
156  * Iterate over the elements in the list named "head".
157  * During the loop, assign the list elements to the variable "var"
158  * and use the LIST_ENTRY structure member "field" as the link field.
159  */
160 #define LIST_FOREACH(var, head, field)                                  \
161         for ((var) = LIST_FIRST((head));                                \
162             (var);                                                      \
163             (var) = LIST_NEXT((var), field))
164
165 /*
166  * Reset the list named "head" to the empty list.
167  */
168 #define LIST_INIT(head) do {                                            \
169         LIST_FIRST((head)) = NULL;                                      \
170 } while (0)
171
172 /*
173  * Insert the element "elm" *after* the element "listelm" which is
174  * already in the list.  The "field" name is the link element
175  * as above.
176  */
177 #define LIST_INSERT_AFTER(listelm, elm, field) do {                     \
178         if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
179                 LIST_NEXT((listelm), field)->field.le_prev =            \
180                     &LIST_NEXT((elm), field);                           \
181         LIST_NEXT((listelm), field) = (elm);                            \
182         (elm)->field.le_prev = &LIST_NEXT((listelm), field);            \
183 } while (0)
184
185 /*
186  * Insert the element "elm" *before* the element "listelm" which is
187  * already in the list.  The "field" name is the link element
188  * as above.
189  */
190 #define LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
191         (elm)->field.le_prev = (listelm)->field.le_prev;                \
192         LIST_NEXT((elm), field) = (listelm);                            \
193         *(listelm)->field.le_prev = (elm);                              \
194         (listelm)->field.le_prev = &LIST_NEXT((elm), field);            \
195 } while (0)
196
197 /*
198  * Insert the element "elm" at the head of the list named "head".
199  * The "field" name is the link element as above.
200  */
201 #define LIST_INSERT_HEAD(head, elm, field) do {                         \
202         if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)     \
203                 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
204         LIST_FIRST((head)) = (elm);                                     \
205         (elm)->field.le_prev = &LIST_FIRST((head));                     \
206 } while (0)
207
208 /*
209  * Remove the element "elm" from the list.
210  * The "field" name is the link element as above.
211  */
212 #define LIST_REMOVE(elm, field) do {                                    \
213         if (LIST_NEXT((elm), field) != NULL)                            \
214                 LIST_NEXT((elm), field)->field.le_prev =                \
215                     (elm)->field.le_prev;                               \
216         *(elm)->field.le_prev = LIST_NEXT((elm), field);                \
217 } while (0)
218
219 #endif  /* !_SYS_QUEUE_H_ */