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