1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) NGINX, Inc.
5  */
6 
7 #ifndef _NXT_QUEUE_H_INCLUDED_
8 #define _NXT_QUEUE_H_INCLUDED_
9 
10 
11 typedef struct nxt_queue_link_s  nxt_queue_link_t;
12 
13 struct nxt_queue_link_s {
14     nxt_queue_link_t  *prev;
15     nxt_queue_link_t  *next;
16 };
17 
18 
19 typedef struct {
20     nxt_queue_link_t  head;
21 } nxt_queue_t;
22 
23 
24 #define                                                                       \
25 nxt_queue_init(queue)                                                         \
26     do {                                                                      \
27         (queue)->head.prev = &(queue)->head;                                  \
28         (queue)->head.next = &(queue)->head;                                  \
29     } while (0)
30 
31 
32 #define                                                                       \
33 nxt_queue_sentinel(link)                                                      \
34     do {                                                                      \
35         (link)->prev = (link);                                                \
36         (link)->next = (link);                                                \
37     } while (0)
38 
39 
40 /*
41  * Short-circuit a queue link to itself to allow once remove safely it
42  * using nxt_queue_remove().
43  */
44 
45 #define                                                                       \
46 nxt_queue_self(link)                                                          \
47     nxt_queue_sentinel(link)
48 
49 
50 #define                                                                       \
51 nxt_queue_is_empty(queue)                                                     \
52     (&(queue)->head == (queue)->head.prev)
53 
54 /*
55  * A loop to iterate all queue links starting from head:
56  *
57  *      nxt_queue_link_t  link;
58  *  } nxt_type_t  *tp;
59  *
60  *
61  *  for (lnk = nxt_queue_first(queue);
62  *       lnk != nxt_queue_tail(queue);
63  *       lnk = nxt_queue_next(lnk))
64  *  {
65  *      tp = nxt_queue_link_data(lnk, nxt_type_t, link);
66  *
67  * or starting from tail:
68  *
69  *  for (lnk = nxt_queue_last(queue);
70  *       lnk != nxt_queue_head(queue);
71  *       lnk = nxt_queue_prev(lnk))
72  *  {
73  *      tp = nxt_queue_link_data(lnk, nxt_type_t, link);
74  */
75 
76 #define                                                                       \
77 nxt_queue_first(queue)                                                        \
78     (queue)->head.next
79 
80 
81 #define                                                                       \
82 nxt_queue_last(queue)                                                         \
83     (queue)->head.prev
84 
85 
86 #define                                                                       \
87 nxt_queue_head(queue)                                                         \
88     (&(queue)->head)
89 
90 
91 #define                                                                       \
92 nxt_queue_tail(queue)                                                         \
93     (&(queue)->head)
94 
95 
96 #define                                                                       \
97 nxt_queue_next(link)                                                          \
98     (link)->next
99 
100 
101 #define                                                                       \
102 nxt_queue_prev(link)                                                          \
103     (link)->prev
104 
105 
106 #define                                                                       \
107 nxt_queue_insert_head(queue, link)                                            \
108     do {                                                                      \
109         (link)->next = (queue)->head.next;                                    \
110         (link)->next->prev = (link);                                          \
111         (link)->prev = &(queue)->head;                                        \
112         (queue)->head.next = (link);                                          \
113     } while (0)
114 
115 
116 #define                                                                       \
117 nxt_queue_insert_tail(queue, link)                                            \
118     do {                                                                      \
119         (link)->prev = (queue)->head.prev;                                    \
120         (link)->prev->next = (link);                                          \
121         (link)->next = &(queue)->head;                                        \
122         (queue)->head.prev = (link);                                          \
123     } while (0)
124 
125 
126 #define                                                                       \
127 nxt_queue_insert_after(target, link)                                          \
128     do {                                                                      \
129         (link)->next = (target)->next;                                        \
130         (link)->next->prev = (link);                                          \
131         (link)->prev = (target);                                              \
132         (target)->next = (link);                                              \
133     } while (0)
134 
135 
136 #define                                                                       \
137 nxt_queue_insert_before(target, link)                                         \
138     do {                                                                      \
139         (link)->next = (target);                                              \
140         (link)->prev = (target)->prev;                                        \
141         (target)->prev = (link);                                              \
142         (link)->prev->next = (link);                                          \
143     } while (0)
144 
145 
146 #if (NXT_DEBUG)
147 
148 #define                                                                       \
149 nxt_queue_remove(link)                                                        \
150     do {                                                                      \
151         (link)->next->prev = (link)->prev;                                    \
152         (link)->prev->next = (link)->next;                                    \
153         (link)->prev = NULL;                                                  \
154         (link)->next = NULL;                                                  \
155     } while (0)
156 
157 #else
158 
159 #define                                                                       \
160 nxt_queue_remove(link)                                                        \
161     do {                                                                      \
162         (link)->next->prev = (link)->prev;                                    \
163         (link)->prev->next = (link)->next;                                    \
164     } while (0)
165 
166 #endif
167 
168 
169 /*
170  * Split the queue "queue" starting at the element "link",
171  * the "tail" is the new tail queue.
172  */
173 
174 #define                                                                       \
175 nxt_queue_split(queue, link, tail)                                            \
176     do {                                                                      \
177         (tail)->head.prev = (queue)->head.prev;                               \
178         (tail)->head.prev->next = &(tail)->head;                              \
179         (tail)->head.next = (link);                                           \
180         (queue)->head.prev = (link)->prev;                                    \
181         (queue)->head.prev->next = &(queue)->head;                            \
182         (link)->prev = &(tail)->head;                                         \
183     } while (0)
184 
185 
186 /* Truncate the queue "queue" starting at element "link". */
187 
188 #define                                                                       \
189 nxt_queue_truncate(queue, link)                                               \
190     do {                                                                      \
191         (queue)->head.prev = (link)->prev;                                    \
192         (queue)->head.prev->next = &(queue)->head;                            \
193     } while (0)
194 
195 
196 /*
197  * Add the queue "tail" to the queue "queue".
198  * If the queue "tail" is intended to be reused again,
199  * it must be initiated with nxt_queue_init(tail).
200  */
201 
202 #define                                                                       \
203 nxt_queue_add(queue, tail)                                                    \
204     do {                                                                      \
205         (queue)->head.prev->next = (tail)->head.next;                         \
206         (tail)->head.next->prev = (queue)->head.prev;                         \
207         (queue)->head.prev = (tail)->head.prev;                               \
208         (queue)->head.prev->next = &(queue)->head;                            \
209     } while (0)
210 
211 
212 #define                                                                       \
213 nxt_queue_link_data(lnk, type, link)                                          \
214     nxt_container_of(lnk, type, link)
215 
216 
217 NXT_EXPORT nxt_queue_link_t *nxt_queue_middle(nxt_queue_t *queue);
218 NXT_EXPORT void nxt_queue_sort(nxt_queue_t *queue,
219     nxt_int_t (*cmp)(const void *, const nxt_queue_link_t *,
220     const nxt_queue_link_t *), const void *data);
221 
222 
223 #define nxt_queue_each(elt, queue, type, link)                                \
224     do {                                                                      \
225         nxt_queue_link_t  *_lnk, *_nxt;                                       \
226                                                                               \
227         for (_lnk = nxt_queue_first(queue);                                   \
228              _lnk != nxt_queue_tail(queue);                                   \
229              _lnk = _nxt) {                                                   \
230                                                                               \
231             _nxt = nxt_queue_next(_lnk);                                      \
232             elt = nxt_queue_link_data(_lnk, type, link);                      \
233 
234 #define nxt_queue_loop                                                        \
235         }                                                                     \
236     } while(0)
237 
238 
239 #endif /* _NXT_QUEUE_H_INCLUDED_ */
240