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