1 2 /* 3 * Copyright (C) Igor Sysoev 4 * Copyright (C) NGINX, Inc. 5 */ 6 7 #ifndef _NJS_QUEUE_H_INCLUDED_ 8 #define _NJS_QUEUE_H_INCLUDED_ 9 10 11 typedef struct njs_queue_link_s njs_queue_link_t; 12 13 struct njs_queue_link_s { 14 njs_queue_link_t *prev; 15 njs_queue_link_t *next; 16 }; 17 18 19 typedef struct { 20 njs_queue_link_t head; 21 } njs_queue_t; 22 23 24 #define njs_queue_init(queue) \ 25 do { \ 26 (queue)->head.prev = &(queue)->head; \ 27 (queue)->head.next = &(queue)->head; \ 28 } while (0) 29 30 31 #define njs_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 njs_queue_remove(). 41 */ 42 43 #define njs_queue_self(link) \ 44 njs_queue_sentinel(link) 45 46 47 #define njs_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 * njs_queue_link_t link; 54 * } njs_type_t *tp; 55 * 56 * 57 * for (lnk = njs_queue_first(queue); 58 * lnk != njs_queue_tail(queue); 59 * lnk = njs_queue_next(lnk)) 60 * { 61 * tp = njs_queue_link_data(lnk, njs_type_t, link); 62 * 63 * or starting from tail: 64 * 65 * for (lnk = njs_queue_last(queue); 66 * lnk != njs_queue_head(queue); 67 * lnk = njs_queue_next(lnk)) 68 * { 69 * tp = njs_queue_link_data(lnk, njs_type_t, link); 70 */ 71 72 #define njs_queue_first(queue) \ 73 (queue)->head.next 74 75 76 #define njs_queue_last(queue) \ 77 (queue)->head.prev 78 79 80 #define njs_queue_head(queue) \ 81 (&(queue)->head) 82 83 84 #define njs_queue_tail(queue) \ 85 (&(queue)->head) 86 87 88 #define njs_queue_next(link) \ 89 (link)->next 90 91 92 #define njs_queue_prev(link) \ 93 (link)->prev 94 95 96 #define njs_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 njs_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 njs_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 njs_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 (NJS_DEBUG) 133 134 #define njs_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 njs_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 njs_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 njs_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 /* Add the queue "tail" to the queue "queue". */ 179 180 #define njs_queue_add(queue, tail) \ 181 do { \ 182 (queue)->head.prev->next = (tail)->head.next; \ 183 (tail)->head.next->prev = (queue)->head.prev; \ 184 (queue)->head.prev = (tail)->head.prev; \ 185 (queue)->head.prev->next = &(queue)->head; \ 186 } while (0) 187 188 189 #define njs_queue_link_data(lnk, type, link) \ 190 njs_container_of(lnk, type, link) 191 192 193 NJS_EXPORT njs_queue_link_t *njs_queue_middle(njs_queue_t *queue); 194 NJS_EXPORT void njs_queue_sort(njs_queue_t *queue, 195 njs_int_t (*compare)(const void *, const njs_queue_link_t *, 196 const njs_queue_link_t *), const void *data); 197 198 199 #endif /* _NJS_QUEUE_H_INCLUDED_ */ 200