xref: /unit/src/nxt_queue.h (revision 2084:7d479274f334)
10Sigor@sysoev.ru 
20Sigor@sysoev.ru /*
30Sigor@sysoev.ru  * Copyright (C) Igor Sysoev
40Sigor@sysoev.ru  * Copyright (C) NGINX, Inc.
50Sigor@sysoev.ru  */
60Sigor@sysoev.ru 
70Sigor@sysoev.ru #ifndef _NXT_QUEUE_H_INCLUDED_
80Sigor@sysoev.ru #define _NXT_QUEUE_H_INCLUDED_
90Sigor@sysoev.ru 
100Sigor@sysoev.ru 
110Sigor@sysoev.ru typedef struct nxt_queue_link_s  nxt_queue_link_t;
120Sigor@sysoev.ru 
130Sigor@sysoev.ru struct nxt_queue_link_s {
140Sigor@sysoev.ru     nxt_queue_link_t  *prev;
150Sigor@sysoev.ru     nxt_queue_link_t  *next;
160Sigor@sysoev.ru };
170Sigor@sysoev.ru 
180Sigor@sysoev.ru 
190Sigor@sysoev.ru typedef struct {
200Sigor@sysoev.ru     nxt_queue_link_t  head;
210Sigor@sysoev.ru } nxt_queue_t;
220Sigor@sysoev.ru 
230Sigor@sysoev.ru 
24*2084Salx.manpages@gmail.com #define nxt_queue_init(queue)                                                 \
250Sigor@sysoev.ru     do {                                                                      \
260Sigor@sysoev.ru         (queue)->head.prev = &(queue)->head;                                  \
270Sigor@sysoev.ru         (queue)->head.next = &(queue)->head;                                  \
280Sigor@sysoev.ru     } while (0)
290Sigor@sysoev.ru 
300Sigor@sysoev.ru 
31*2084Salx.manpages@gmail.com #define nxt_queue_sentinel(link)                                              \
320Sigor@sysoev.ru     do {                                                                      \
330Sigor@sysoev.ru         (link)->prev = (link);                                                \
340Sigor@sysoev.ru         (link)->next = (link);                                                \
350Sigor@sysoev.ru     } while (0)
360Sigor@sysoev.ru 
370Sigor@sysoev.ru 
380Sigor@sysoev.ru /*
390Sigor@sysoev.ru  * Short-circuit a queue link to itself to allow once remove safely it
400Sigor@sysoev.ru  * using nxt_queue_remove().
410Sigor@sysoev.ru  */
420Sigor@sysoev.ru 
43*2084Salx.manpages@gmail.com #define nxt_queue_self(link)                                                  \
440Sigor@sysoev.ru     nxt_queue_sentinel(link)
450Sigor@sysoev.ru 
460Sigor@sysoev.ru 
47*2084Salx.manpages@gmail.com #define nxt_queue_is_empty(queue)                                             \
480Sigor@sysoev.ru     (&(queue)->head == (queue)->head.prev)
490Sigor@sysoev.ru 
500Sigor@sysoev.ru /*
510Sigor@sysoev.ru  * A loop to iterate all queue links starting from head:
520Sigor@sysoev.ru  *
530Sigor@sysoev.ru  *      nxt_queue_link_t  link;
540Sigor@sysoev.ru  *  } nxt_type_t  *tp;
550Sigor@sysoev.ru  *
560Sigor@sysoev.ru  *
570Sigor@sysoev.ru  *  for (lnk = nxt_queue_first(queue);
580Sigor@sysoev.ru  *       lnk != nxt_queue_tail(queue);
590Sigor@sysoev.ru  *       lnk = nxt_queue_next(lnk))
600Sigor@sysoev.ru  *  {
610Sigor@sysoev.ru  *      tp = nxt_queue_link_data(lnk, nxt_type_t, link);
620Sigor@sysoev.ru  *
630Sigor@sysoev.ru  * or starting from tail:
640Sigor@sysoev.ru  *
650Sigor@sysoev.ru  *  for (lnk = nxt_queue_last(queue);
660Sigor@sysoev.ru  *       lnk != nxt_queue_head(queue);
6720Sigor@sysoev.ru  *       lnk = nxt_queue_prev(lnk))
680Sigor@sysoev.ru  *  {
690Sigor@sysoev.ru  *      tp = nxt_queue_link_data(lnk, nxt_type_t, link);
700Sigor@sysoev.ru  */
710Sigor@sysoev.ru 
72*2084Salx.manpages@gmail.com #define nxt_queue_first(queue)                                                \
730Sigor@sysoev.ru     (queue)->head.next
740Sigor@sysoev.ru 
750Sigor@sysoev.ru 
76*2084Salx.manpages@gmail.com #define nxt_queue_last(queue)                                                 \
770Sigor@sysoev.ru     (queue)->head.prev
780Sigor@sysoev.ru 
790Sigor@sysoev.ru 
80*2084Salx.manpages@gmail.com #define nxt_queue_head(queue)                                                 \
810Sigor@sysoev.ru     (&(queue)->head)
820Sigor@sysoev.ru 
830Sigor@sysoev.ru 
84*2084Salx.manpages@gmail.com #define nxt_queue_tail(queue)                                                 \
850Sigor@sysoev.ru     (&(queue)->head)
860Sigor@sysoev.ru 
870Sigor@sysoev.ru 
88*2084Salx.manpages@gmail.com #define nxt_queue_next(link)                                                  \
890Sigor@sysoev.ru     (link)->next
900Sigor@sysoev.ru 
910Sigor@sysoev.ru 
92*2084Salx.manpages@gmail.com #define nxt_queue_prev(link)                                                  \
930Sigor@sysoev.ru     (link)->prev
940Sigor@sysoev.ru 
950Sigor@sysoev.ru 
96*2084Salx.manpages@gmail.com #define nxt_queue_insert_head(queue, link)                                    \
970Sigor@sysoev.ru     do {                                                                      \
980Sigor@sysoev.ru         (link)->next = (queue)->head.next;                                    \
990Sigor@sysoev.ru         (link)->next->prev = (link);                                          \
1000Sigor@sysoev.ru         (link)->prev = &(queue)->head;                                        \
1010Sigor@sysoev.ru         (queue)->head.next = (link);                                          \
1020Sigor@sysoev.ru     } while (0)
1030Sigor@sysoev.ru 
1040Sigor@sysoev.ru 
105*2084Salx.manpages@gmail.com #define nxt_queue_insert_tail(queue, link)                                    \
1060Sigor@sysoev.ru     do {                                                                      \
1070Sigor@sysoev.ru         (link)->prev = (queue)->head.prev;                                    \
1080Sigor@sysoev.ru         (link)->prev->next = (link);                                          \
1090Sigor@sysoev.ru         (link)->next = &(queue)->head;                                        \
1100Sigor@sysoev.ru         (queue)->head.prev = (link);                                          \
1110Sigor@sysoev.ru     } while (0)
1120Sigor@sysoev.ru 
1130Sigor@sysoev.ru 
114*2084Salx.manpages@gmail.com #define nxt_queue_insert_after(target, link)                                  \
1150Sigor@sysoev.ru     do {                                                                      \
1160Sigor@sysoev.ru         (link)->next = (target)->next;                                        \
1170Sigor@sysoev.ru         (link)->next->prev = (link);                                          \
1180Sigor@sysoev.ru         (link)->prev = (target);                                              \
1190Sigor@sysoev.ru         (target)->next = (link);                                              \
1200Sigor@sysoev.ru     } while (0)
1210Sigor@sysoev.ru 
1220Sigor@sysoev.ru 
123*2084Salx.manpages@gmail.com #define nxt_queue_insert_before(target, link)                                 \
1240Sigor@sysoev.ru     do {                                                                      \
1250Sigor@sysoev.ru         (link)->next = (target);                                              \
1260Sigor@sysoev.ru         (link)->prev = (target)->prev;                                        \
1270Sigor@sysoev.ru         (target)->prev = (link);                                              \
1280Sigor@sysoev.ru         (link)->prev->next = (link);                                          \
1290Sigor@sysoev.ru     } while (0)
1300Sigor@sysoev.ru 
1310Sigor@sysoev.ru 
1320Sigor@sysoev.ru #if (NXT_DEBUG)
1330Sigor@sysoev.ru 
134*2084Salx.manpages@gmail.com #define nxt_queue_remove(link)                                                \
1350Sigor@sysoev.ru     do {                                                                      \
1360Sigor@sysoev.ru         (link)->next->prev = (link)->prev;                                    \
1370Sigor@sysoev.ru         (link)->prev->next = (link)->next;                                    \
1380Sigor@sysoev.ru         (link)->prev = NULL;                                                  \
1390Sigor@sysoev.ru         (link)->next = NULL;                                                  \
1400Sigor@sysoev.ru     } while (0)
1410Sigor@sysoev.ru 
1420Sigor@sysoev.ru #else
1430Sigor@sysoev.ru 
144*2084Salx.manpages@gmail.com #define nxt_queue_remove(link)                                                \
1450Sigor@sysoev.ru     do {                                                                      \
1460Sigor@sysoev.ru         (link)->next->prev = (link)->prev;                                    \
1470Sigor@sysoev.ru         (link)->prev->next = (link)->next;                                    \
1480Sigor@sysoev.ru     } while (0)
1490Sigor@sysoev.ru 
1500Sigor@sysoev.ru #endif
1510Sigor@sysoev.ru 
1520Sigor@sysoev.ru 
1530Sigor@sysoev.ru /*
1540Sigor@sysoev.ru  * Split the queue "queue" starting at the element "link",
1550Sigor@sysoev.ru  * the "tail" is the new tail queue.
1560Sigor@sysoev.ru  */
1570Sigor@sysoev.ru 
158*2084Salx.manpages@gmail.com #define nxt_queue_split(queue, link, tail)                                    \
1590Sigor@sysoev.ru     do {                                                                      \
1600Sigor@sysoev.ru         (tail)->head.prev = (queue)->head.prev;                               \
1610Sigor@sysoev.ru         (tail)->head.prev->next = &(tail)->head;                              \
1620Sigor@sysoev.ru         (tail)->head.next = (link);                                           \
1630Sigor@sysoev.ru         (queue)->head.prev = (link)->prev;                                    \
1640Sigor@sysoev.ru         (queue)->head.prev->next = &(queue)->head;                            \
1650Sigor@sysoev.ru         (link)->prev = &(tail)->head;                                         \
1660Sigor@sysoev.ru     } while (0)
1670Sigor@sysoev.ru 
1680Sigor@sysoev.ru 
1690Sigor@sysoev.ru /* Truncate the queue "queue" starting at element "link". */
1700Sigor@sysoev.ru 
171*2084Salx.manpages@gmail.com #define nxt_queue_truncate(queue, link)                                       \
1720Sigor@sysoev.ru     do {                                                                      \
1730Sigor@sysoev.ru         (queue)->head.prev = (link)->prev;                                    \
1740Sigor@sysoev.ru         (queue)->head.prev->next = &(queue)->head;                            \
1750Sigor@sysoev.ru     } while (0)
1760Sigor@sysoev.ru 
1770Sigor@sysoev.ru 
178115Sigor@sysoev.ru /*
179115Sigor@sysoev.ru  * Add the queue "tail" to the queue "queue".
180115Sigor@sysoev.ru  * If the queue "tail" is intended to be reused again,
181115Sigor@sysoev.ru  * it must be initiated with nxt_queue_init(tail).
182115Sigor@sysoev.ru  */
1830Sigor@sysoev.ru 
184*2084Salx.manpages@gmail.com #define nxt_queue_add(queue, tail)                                            \
1850Sigor@sysoev.ru     do {                                                                      \
1860Sigor@sysoev.ru         (queue)->head.prev->next = (tail)->head.next;                         \
1870Sigor@sysoev.ru         (tail)->head.next->prev = (queue)->head.prev;                         \
1880Sigor@sysoev.ru         (queue)->head.prev = (tail)->head.prev;                               \
1890Sigor@sysoev.ru         (queue)->head.prev->next = &(queue)->head;                            \
1900Sigor@sysoev.ru     } while (0)
1910Sigor@sysoev.ru 
1920Sigor@sysoev.ru 
193*2084Salx.manpages@gmail.com #define nxt_queue_link_data(lnk, type, link)                                  \
1940Sigor@sysoev.ru     nxt_container_of(lnk, type, link)
1950Sigor@sysoev.ru 
1960Sigor@sysoev.ru 
1970Sigor@sysoev.ru NXT_EXPORT nxt_queue_link_t *nxt_queue_middle(nxt_queue_t *queue);
1980Sigor@sysoev.ru NXT_EXPORT void nxt_queue_sort(nxt_queue_t *queue,
1990Sigor@sysoev.ru     nxt_int_t (*cmp)(const void *, const nxt_queue_link_t *,
2000Sigor@sysoev.ru     const nxt_queue_link_t *), const void *data);
2010Sigor@sysoev.ru 
2020Sigor@sysoev.ru 
20342Smax.romanov@nginx.com #define nxt_queue_each(elt, queue, type, link)                                \
20442Smax.romanov@nginx.com     do {                                                                      \
205125Smax.romanov@nginx.com         nxt_queue_link_t  *_lnk, *_nxt;                                       \
20642Smax.romanov@nginx.com                                                                               \
20742Smax.romanov@nginx.com         for (_lnk = nxt_queue_first(queue);                                   \
20842Smax.romanov@nginx.com              _lnk != nxt_queue_tail(queue);                                   \
209125Smax.romanov@nginx.com              _lnk = _nxt) {                                                   \
21042Smax.romanov@nginx.com                                                                               \
211125Smax.romanov@nginx.com             _nxt = nxt_queue_next(_lnk);                                      \
21242Smax.romanov@nginx.com             elt = nxt_queue_link_data(_lnk, type, link);                      \
21342Smax.romanov@nginx.com 
21442Smax.romanov@nginx.com #define nxt_queue_loop                                                        \
21542Smax.romanov@nginx.com         }                                                                     \
21642Smax.romanov@nginx.com     } while(0)
21742Smax.romanov@nginx.com 
21842Smax.romanov@nginx.com 
2190Sigor@sysoev.ru #endif /* _NXT_QUEUE_H_INCLUDED_ */
220