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