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