1 2 /* We define three data structures: 3 * 1. a Stack. a singly-ended, singly-linked list. 4 * 2. a Queue. a doubly-ended, singly-linked list. 5 * 3. a List. a doubly-ended, doubly-linked list. 6 * 7 * Stack operations: 8 * PUSH(stack, node) [O(1)] 9 * POP(stack, rv_node) [O(1)] 10 * INSERT_AFTER(stack, above_node, new_node) [O(1)] 11 * IS_EMPTY(stack) [O(1)] 12 * REVERSE(stack) [O(N)] 13 * SORT(stack, comparator) [O(NlogN)] 14 * GET_BOTTOM(stack, rv_node) [O(N)] 15 * Queue operations: 16 * ENQUEUE(queue, node) [O(1)] 17 * DEQUEUE(queue, rv_node) [O(1)] 18 * PREPEND(queue, node) [O(1)] 19 * IS_EMPTY(queue) [O(1)] 20 * REVERSE(queue) [O(N)] 21 * SORT(queue, comparator) [O(NlogN)] 22 * List operations: 23 * PREPEND(list, node) [O(1)] 24 * APPEND(list, node) [O(1)] 25 * REMOVE_FIRST(list) [O(1)] 26 * REMOVE_LAST(list) [O(1)] 27 * REMOVE(list, node) [O(1)] 28 * INSERT_AFTER(list, position_node, new_node) [O(1)] 29 * INSERT_BEFORE(list, position_node, new_node) [O(1)] 30 * IS_EMPTY(list) [O(1)] 31 * REVERSE(list) [O(N)] 32 * SORT(list) [O(NlogN)] 33 * 34 * note: the SORT operation is stable, i.e. if two 35 * elements are equal according to the comparator, 36 * then their relative order in the list 37 * will be preserved. 38 * 39 * In the above, 'stack', 'queue', and 'list' are 40 * a comma-separated list of arguments, actually. 41 * In particular: 42 * stack => NodeType*, top, next_member_name 43 * queue => NodeType*, head, tail, next_member_name 44 * list => NodeType*, first, last, prev_member_name, next_member_name 45 * We recommend making macros that end in GET_STACK_ARGS, GET_QUEUE_ARGS, 46 * and GET_LIST_ARGS that return the relevant N-tuples. 47 */ 48 49 #define GSK_LOG2_MAX_LIST_SIZE (GLIB_SIZEOF_SIZE_T*8) 50 51 /* --- Stacks --- */ 52 #define GSK_STACK_PUSH(stack, node) GSK_STACK_PUSH_(stack, node) 53 #define GSK_STACK_POP(stack, rv_node) GSK_STACK_POP_(stack, rv_node) 54 #define GSK_STACK_INSERT_AFTER(stack, above_node, new_node) \ 55 GSK_STACK_INSERT_AFTER_(stack, above_node, new_node) 56 #define GSK_STACK_IS_EMPTY(stack) GSK_STACK_IS_EMPTY_(stack) 57 #define GSK_STACK_REVERSE(stack) GSK_STACK_REVERSE_(stack) 58 #define GSK_STACK_FOREACH(stack, iter_var, code) GSK_STACK_FOREACH_(stack, iter_var, code) 59 #define GSK_STACK_SORT(stack, comparator) GSK_STACK_SORT_(stack, comparator) 60 #define GSK_STACK_GET_BOTTOM(stack, rv_node) GSK_STACK_GET_BOTTOM_(stack, rv_node) 61 62 #define GSK_STACK_PUSH_(type, top, next, node) \ 63 G_STMT_START{ \ 64 type _gsk_tmp = (node); \ 65 _gsk_tmp->next = (top); \ 66 (top) = _gsk_tmp; \ 67 }G_STMT_END 68 #define GSK_STACK_POP_(type, top, next, rv_node) \ 69 G_STMT_START{ \ 70 rv_node = (top); \ 71 (top) = (top)->next; \ 72 }G_STMT_END 73 #define GSK_STACK_INSERT_AFTER_(type, top, next, above_node, new_node) \ 74 G_STMT_START{ \ 75 type _gsk_tmp = (new_node); \ 76 type _gsk_above = (above_node); \ 77 _gsk_tmp->next = _gsk_above->next; \ 78 _gsk_above->next = _gsk_tmp; \ 79 }G_STMT_END 80 #define GSK_STACK_IS_EMPTY_(type, top, next) \ 81 ((top) == NULL) 82 #define GSK_STACK_REVERSE_(type, top, next) \ 83 G_STMT_START{ \ 84 type _gsk___prev = NULL; \ 85 type _gsk___at = (top); \ 86 while (_gsk___at != NULL) \ 87 { \ 88 type _gsk__next = _gsk___at->next; \ 89 _gsk___at->next = _gsk___prev; \ 90 _gsk___prev = _gsk___at; \ 91 _gsk___at = _gsk__next; \ 92 } \ 93 (top) = _gsk___prev; \ 94 }G_STMT_END 95 #define GSK_STACK_FOREACH_(type, top, next, iter_var, code) \ 96 for (iter_var = top; iter_var != NULL; ) \ 97 { \ 98 type _gsk__next = iter_var->next; \ 99 code; \ 100 iter_var = _gsk__next; \ 101 } 102 /* sort algorithm: 103 * in order to implement SORT in a macro, it cannot use recursion. 104 * but that's ok because you can just manually implement a stack, 105 * which is probably faster anyways. 106 */ 107 #define GSK_STACK_SORT_(type, top, next, comparator) \ 108 G_STMT_START{ \ 109 type _gsk_stack[GSK_LOG2_MAX_LIST_SIZE]; \ 110 guint _gsk_stack_size = 0; \ 111 guint _gsk_i; \ 112 type _gsk_at; \ 113 for (_gsk_at = top; _gsk_at != NULL; ) \ 114 { \ 115 type _gsk_a = _gsk_at; \ 116 type _gsk_b; \ 117 type _gsk_cur_list; \ 118 int _gsk_comparator_rv; \ 119 _gsk_at = _gsk_at->next; \ 120 if (_gsk_at) \ 121 { \ 122 _gsk_b = _gsk_at; \ 123 _gsk_at = _gsk_at->next; \ 124 comparator (_gsk_a, _gsk_b, _gsk_comparator_rv); \ 125 if (_gsk_comparator_rv > 0) \ 126 { \ 127 /* sort first two elements */ \ 128 type _gsk_swap = _gsk_b; \ 129 _gsk_b = _gsk_a; \ 130 _gsk_a = _gsk_swap; \ 131 _gsk_a->next = _gsk_b; \ 132 _gsk_b->next = NULL; \ 133 } \ 134 else \ 135 { \ 136 /* first two elements already sorted */ \ 137 _gsk_b->next = NULL; \ 138 } \ 139 } \ 140 else \ 141 { \ 142 /* only one element remains */ \ 143 _gsk_a->next = NULL; \ 144 _gsk_at = NULL; \ 145 } \ 146 _gsk_cur_list = _gsk_a; \ 147 \ 148 /* merge _gsk_cur_list up the stack */ \ 149 for (_gsk_i = 0; TRUE; _gsk_i++) \ 150 { \ 151 /* expanding the stack is marked unlikely, */ \ 152 /* since in the case it matters (where the number */ \ 153 /* of elements is big), the stack rarely grows. */ \ 154 if (G_UNLIKELY (_gsk_i == _gsk_stack_size)) \ 155 { \ 156 _gsk_stack[_gsk_stack_size++] = _gsk_cur_list; \ 157 break; \ 158 } \ 159 else if (_gsk_stack[_gsk_i] == NULL) \ 160 { \ 161 _gsk_stack[_gsk_i] = _gsk_cur_list; \ 162 break; \ 163 } \ 164 else \ 165 { \ 166 /* Merge _gsk_stack[_gsk_i] and _gsk_cur_list. */ \ 167 type _gsk_merge_list = _gsk_stack[_gsk_i]; \ 168 type _gsk_new_cur_list; \ 169 _gsk_stack[_gsk_i] = NULL; \ 170 \ 171 _GSK_MERGE_NONEMPTY_LISTS (_gsk_merge_list, \ 172 _gsk_cur_list, \ 173 _gsk_new_cur_list, \ 174 type, next, comparator); \ 175 _gsk_cur_list = _gsk_new_cur_list; \ 176 _gsk_stack[_gsk_i] = NULL; \ 177 } \ 178 } \ 179 } \ 180 \ 181 /* combine all the elements on the stack into a final output */ \ 182 top = NULL; \ 183 for (_gsk_i = 0; _gsk_i < _gsk_stack_size; _gsk_i++) \ 184 if (_gsk_stack[_gsk_i] != NULL) \ 185 { \ 186 if (top == NULL) \ 187 top = _gsk_stack[_gsk_i]; \ 188 else \ 189 { \ 190 type _gsk_new_top; \ 191 _GSK_MERGE_NONEMPTY_LISTS (_gsk_stack[_gsk_i], \ 192 top, \ 193 _gsk_new_top, \ 194 type, next, comparator); \ 195 top = _gsk_new_top; \ 196 } \ 197 } \ 198 }G_STMT_END 199 200 #define GSK_STACK_GET_BOTTOM_(type, top, next, rv_node) \ 201 G_STMT_START{ \ 202 rv_node = top; \ 203 if (rv_node != NULL) \ 204 while (rv_node->next) \ 205 rv_node = rv_node->next; \ 206 }G_STMT_END 207 208 /* --- Queues --- */ 209 #define GSK_QUEUE_ENQUEUE(queue, node) GSK_QUEUE_ENQUEUE_(queue, node) 210 #define GSK_QUEUE_DEQUEUE(queue, rv_node) GSK_QUEUE_DEQUEUE_(queue, rv_node) 211 #define GSK_QUEUE_PREPEND(queue, node) GSK_QUEUE_PREPEND_(queue, node) 212 #define GSK_QUEUE_IS_EMPTY(queue) GSK_QUEUE_IS_EMPTY_(queue) 213 #define GSK_QUEUE_REVERSE(queue) GSK_QUEUE_REVERSE_(queue) 214 #define GSK_QUEUE_SORT(queue, comparator) GSK_QUEUE_SORT_(queue, comparator) 215 216 #define GSK_QUEUE_ENQUEUE_(type, head, tail, next, node) \ 217 G_STMT_START{ \ 218 type _gsk_tmp = (node); \ 219 if (tail) \ 220 tail->next = _gsk_tmp; \ 221 else \ 222 head = _gsk_tmp; \ 223 tail = _gsk_tmp; \ 224 node->next = NULL; \ 225 }G_STMT_END 226 #define GSK_QUEUE_DEQUEUE_(type, head, tail, next, rv_node) \ 227 G_STMT_START{ \ 228 rv_node = head; \ 229 if (head) \ 230 { \ 231 head = head->next; \ 232 if (head == NULL) \ 233 tail = NULL; \ 234 } \ 235 }G_STMT_END 236 #define GSK_QUEUE_PREPEND_(type, head, tail, next, node) \ 237 G_STMT_START{ \ 238 type _gsk_tmp = (node); \ 239 _gsk_tmp->next = head; \ 240 head = _gsk_tmp; \ 241 if (tail == NULL) \ 242 tail = head; \ 243 }G_STMT_END 244 245 #define GSK_QUEUE_IS_EMPTY_(type, head, tail, next) \ 246 ((head) == NULL) 247 248 #define GSK_QUEUE_REVERSE_(type, head, tail, next) \ 249 G_STMT_START{ \ 250 type _gsk_queue_new_tail = head; \ 251 GSK_STACK_REVERSE_(type, head, next); \ 252 tail = _gsk_queue_new_tail; \ 253 }G_STMT_END 254 255 #define GSK_QUEUE_SORT_(type, head, tail, next, comparator) \ 256 G_STMT_START{ \ 257 GSK_STACK_SORT_(type, head, next, comparator); \ 258 GSK_STACK_GET_BOTTOM_(type, head, next, tail); \ 259 }G_STMT_END 260 261 /* --- List --- */ 262 #define GSK_LIST_PREPEND(list, node) GSK_LIST_PREPEND_(list, node) 263 #define GSK_LIST_APPEND(list, node) GSK_LIST_APPEND_(list, node) 264 #define GSK_LIST_REMOVE_FIRST(list) GSK_LIST_REMOVE_FIRST_(list) 265 #define GSK_LIST_REMOVE_LAST(list) GSK_LIST_REMOVE_LAST_(list) 266 #define GSK_LIST_REMOVE(list, node) GSK_LIST_REMOVE_(list, node) 267 #define GSK_LIST_INSERT_AFTER(list, at, node) GSK_LIST_INSERT_AFTER_(list, at, node) 268 #define GSK_LIST_INSERT_BEFORE(list, at, node) GSK_LIST_INSERT_BEFORE_(list, at, node) 269 #define GSK_LIST_IS_EMPTY(list) GSK_LIST_IS_EMPTY_(list) 270 #define GSK_LIST_REVERSE(list) GSK_LIST_REVERSE_(list) 271 #define GSK_LIST_SORT(list, comparator) GSK_LIST_SORT_(list, comparator) 272 273 #define GSK_LIST_PREPEND_(type, first, last, prev, next, node) \ 274 G_STMT_START{ \ 275 type _gsk_tmp = (node); \ 276 if (first) \ 277 first->prev = (_gsk_tmp); \ 278 else \ 279 last = (_gsk_tmp); \ 280 node->next = first; \ 281 node->prev = NULL; \ 282 first = node; \ 283 }G_STMT_END 284 #define GSK_LIST_APPEND_(type, first, last, prev, next, node) \ 285 GSK_LIST_PREPEND_(type, last, first, next, prev, node) 286 #define GSK_LIST_REMOVE_FIRST_(type, first, last, prev, next) \ 287 G_STMT_START{ \ 288 first = first->next; \ 289 if (first == NULL) \ 290 last = NULL; \ 291 else \ 292 first->prev = NULL; \ 293 }G_STMT_END 294 #define GSK_LIST_REMOVE_LAST_(type, first, last, prev, next) \ 295 GSK_LIST_REMOVE_FIRST_(type, last, first, next, prev) 296 #define GSK_LIST_REMOVE_(type, first, last, prev, next, node) \ 297 G_STMT_START{ \ 298 type _gsk_tmp = (node); \ 299 if (_gsk_tmp->prev) \ 300 _gsk_tmp->prev->next = _gsk_tmp->next; \ 301 else \ 302 first = _gsk_tmp->next; \ 303 if (_gsk_tmp->next) \ 304 _gsk_tmp->next->prev = _gsk_tmp->prev; \ 305 else \ 306 last = _gsk_tmp->prev; \ 307 }G_STMT_END 308 309 #define GSK_LIST_INSERT_AFTER_(type, first, last, prev, next, at, node) \ 310 G_STMT_START{ \ 311 type _gsk_at = (at); \ 312 type _gsk_node = (node); \ 313 _gsk_node->prev = _gsk_at; \ 314 _gsk_node->next = _gsk_at->next; \ 315 if (_gsk_node->next) \ 316 _gsk_node->next->prev = _gsk_node; \ 317 else \ 318 last = _gsk_node; \ 319 _gsk_at->next = _gsk_node; \ 320 }G_STMT_END 321 #define GSK_LIST_INSERT_BEFORE_(type, first, last, prev, next, at, node)\ 322 GSK_LIST_INSERT_AFTER_(type, last, first, next, prev, at, node) 323 #define GSK_LIST_IS_EMPTY_(type, first, last, prev, next) \ 324 ((first) == NULL) 325 #define GSK_LIST_REVERSE_(type, first, last, prev, next) \ 326 G_STMT_START{ \ 327 type _gsk_at = first; \ 328 first = last; \ 329 last = _gsk_at; \ 330 while (_gsk_at) \ 331 { \ 332 type _gsk_old_next = _gsk_at->next; \ 333 _gsk_at->next = _gsk_at->prev; \ 334 _gsk_at->prev = _gsk_old_next; \ 335 _gsk_at = _gsk_old_next; \ 336 } \ 337 }G_STMT_END 338 #define GSK_LIST_SORT_(type, first, last, prev, next, comparator) \ 339 G_STMT_START{ \ 340 type _gsk_prev = NULL; \ 341 type _gsk_at; \ 342 GSK_STACK_SORT_(type, first, next, comparator); \ 343 for (_gsk_at = first; _gsk_at; _gsk_at = _gsk_at->next) \ 344 { \ 345 _gsk_at->prev = _gsk_prev; \ 346 _gsk_prev = _gsk_at; \ 347 } \ 348 last = _gsk_prev; \ 349 }G_STMT_END 350 351 /* --- Internals --- */ 352 #define _GSK_MERGE_NONEMPTY_LISTS(a,b,out,type,next,comparator) \ 353 G_STMT_START{ \ 354 type _gsk_out_at; \ 355 int _gsk_comparator_rv; \ 356 /* merge 'a' and 'b' into 'out' -- in order to make the sort stable,*/ \ 357 /* always put elements if 'a' first in the event of a tie (i.e. */ \ 358 /* when comparator_rv==0) */ \ 359 comparator (a, b, _gsk_comparator_rv); \ 360 if (_gsk_comparator_rv <= 0) \ 361 { \ 362 out = a; \ 363 a = a->next; \ 364 } \ 365 else \ 366 { \ 367 out = b; \ 368 b = b->next; \ 369 } \ 370 _gsk_out_at = out; \ 371 while (a && b) \ 372 { \ 373 comparator (a, b, _gsk_comparator_rv); \ 374 if (_gsk_comparator_rv <= 0) \ 375 { \ 376 _gsk_out_at->next = a; \ 377 _gsk_out_at = a; \ 378 a = a->next; \ 379 } \ 380 else \ 381 { \ 382 _gsk_out_at->next = b; \ 383 _gsk_out_at = b; \ 384 b = b->next; \ 385 } \ 386 } \ 387 _gsk_out_at->next = (a != NULL) ? a : b; \ 388 }G_STMT_END 389