Mercurial > hg > webserver / file comparison

comparison: src/ucx/linked_list.c

src/ucx/linked_list.c

changeset 579
e10457d74fe1
parent 504
c094afcdfb27
equal deleted inserted replaced
578:eb48f716b31c 579:e10457d74fe1
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #include "cx/linked_list.h" 29 #include "cx/linked_list.h"
30 #include "cx/utils.h" 30 #include "cx/compare.h"
31 #include <string.h> 31 #include <string.h>
32 #include <assert.h> 32 #include <assert.h>
33 33
34 // LOW LEVEL LINKED LIST FUNCTIONS 34 // LOW LEVEL LINKED LIST FUNCTIONS
35 35
38 #define ll_next(node) CX_LL_PTR(node, loc_next) 38 #define ll_next(node) CX_LL_PTR(node, loc_next)
39 #define ll_advance(node) CX_LL_PTR(node, loc_advance) 39 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
40 #define ll_data(node) (((char*)(node))+loc_data) 40 #define ll_data(node) (((char*)(node))+loc_data)
41 41
42 void *cx_linked_list_at( 42 void *cx_linked_list_at(
43 void const *start, 43 const void *start,
44 size_t start_index, 44 size_t start_index,
45 ptrdiff_t loc_advance, 45 ptrdiff_t loc_advance,
46 size_t index 46 size_t index
47 ) { 47 ) {
48 assert(start != NULL); 48 assert(start != NULL);
49 assert(loc_advance >= 0); 49 assert(loc_advance >= 0);
50 size_t i = start_index; 50 size_t i = start_index;
51 void const *cur = start; 51 const void *cur = start;
52 while (i != index && cur != NULL) { 52 while (i != index && cur != NULL) {
53 cur = ll_advance(cur); 53 cur = ll_advance(cur);
54 i < index ? i++ : i--; 54 i < index ? i++ : i--;
55 } 55 }
56 return (void *) cur; 56 return (void *) cur;
57 } 57 }
58 58
59 ssize_t cx_linked_list_find( 59 void *cx_linked_list_find(
60 void const *start, 60 const void *start,
61 ptrdiff_t loc_advance, 61 ptrdiff_t loc_advance,
62 ptrdiff_t loc_data, 62 ptrdiff_t loc_data,
63 cx_compare_func cmp_func, 63 cx_compare_func cmp_func,
64 void const *elem 64 const void *elem,
65 size_t *found_index
65 ) { 66 ) {
66 assert(start != NULL); 67 assert(start != NULL);
67 assert(loc_advance >= 0); 68 assert(loc_advance >= 0);
68 assert(loc_data >= 0); 69 assert(loc_data >= 0);
69 assert(cmp_func); 70 assert(cmp_func);
70 71
71 void const *node = start; 72 void *node = (void*) start;
72 ssize_t index = 0; 73 size_t index = 0;
73 do { 74 do {
74 void *current = ll_data(node); 75 void *current = ll_data(node);
75 if (cmp_func(current, elem) == 0) { 76 if (cmp_func(current, elem) == 0) {
76 return index; 77 if (found_index != NULL) {
78 *found_index = index;
79 }
80 return node;
77 } 81 }
78 node = ll_advance(node); 82 node = ll_advance(node);
79 index++; 83 index++;
80 } while (node != NULL); 84 } while (node != NULL);
81 return -1; 85 return NULL;
82 } 86 }
83 87
84 void *cx_linked_list_first( 88 void *cx_linked_list_first(
85 void const *node, 89 const void *node,
86 ptrdiff_t loc_prev 90 ptrdiff_t loc_prev
87 ) { 91 ) {
88 return cx_linked_list_last(node, loc_prev); 92 return cx_linked_list_last(node, loc_prev);
89 } 93 }
90 94
91 void *cx_linked_list_last( 95 void *cx_linked_list_last(
92 void const *node, 96 const void *node,
93 ptrdiff_t loc_next 97 ptrdiff_t loc_next
94 ) { 98 ) {
95 assert(node != NULL); 99 assert(node != NULL);
96 assert(loc_next >= 0); 100 assert(loc_next >= 0);
97 101
98 void const *cur = node; 102 const void *cur = node;
99 void const *last; 103 const void *last;
100 do { 104 do {
101 last = cur; 105 last = cur;
102 } while ((cur = ll_next(cur)) != NULL); 106 } while ((cur = ll_next(cur)) != NULL);
103 107
104 return (void *) last; 108 return (void *) last;
105 } 109 }
106 110
107 void *cx_linked_list_prev( 111 void *cx_linked_list_prev(
108 void const *begin, 112 const void *begin,
109 ptrdiff_t loc_next, 113 ptrdiff_t loc_next,
110 void const *node 114 const void *node
111 ) { 115 ) {
112 assert(begin != NULL); 116 assert(begin != NULL);
113 assert(node != NULL); 117 assert(node != NULL);
114 assert(loc_next >= 0); 118 assert(loc_next >= 0);
115 if (begin == node) return NULL; 119 if (begin == node) return NULL;
116 void const *cur = begin; 120 const void *cur = begin;
117 void const *next; 121 const void *next;
118 while (1) { 122 while (1) {
119 next = ll_next(cur); 123 next = ll_next(cur);
120 if (next == node) return (void *) cur; 124 if (next == node) return (void *) cur;
121 cur = next; 125 cur = next;
122 } 126 }
225 } else { 229 } else {
226 cx_linked_list_link(insert_end, successor, loc_prev, loc_next); 230 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
227 } 231 }
228 } 232 }
229 233
230 void cx_linked_list_remove( 234 void cx_linked_list_insert_sorted(
231 void **begin, 235 void **begin,
232 void **end, 236 void **end,
233 ptrdiff_t loc_prev, 237 ptrdiff_t loc_prev,
234 ptrdiff_t loc_next, 238 ptrdiff_t loc_next,
235 void *node 239 void *new_node,
240 cx_compare_func cmp_func
241 ) {
242 assert(ll_next(new_node) == NULL);
243 cx_linked_list_insert_sorted_chain(
244 begin, end, loc_prev, loc_next, new_node, cmp_func);
245 }
246
247 void cx_linked_list_insert_sorted_chain(
248 void **begin,
249 void **end,
250 ptrdiff_t loc_prev,
251 ptrdiff_t loc_next,
252 void *insert_begin,
253 cx_compare_func cmp_func
254 ) {
255 assert(begin != NULL);
256 assert(loc_next >= 0);
257 assert(insert_begin != NULL);
258
259 // track currently observed nodes
260 void *dest_prev = NULL;
261 void *dest = *begin;
262 void *src = insert_begin;
263
264 // special case: list is empty
265 if (dest == NULL) {
266 *begin = src;
267 if (end != NULL) {
268 *end = cx_linked_list_last(src, loc_next);
269 }
270 return;
271 }
272
273 // search the list for insertion points
274 while (dest != NULL && src != NULL) {
275 // compare current list node with source node
276 // if less or equal, skip
277 if (cmp_func(dest, src) <= 0) {
278 dest_prev = dest;
279 dest = ll_next(dest);
280 continue;
281 }
282
283 // determine chain of elements that can be inserted
284 void *end_of_chain = src;
285 void *next_in_chain = ll_next(src);
286 while (next_in_chain != NULL) {
287 // once we become larger than the list elem, break
288 if (cmp_func(dest, next_in_chain) <= 0) {
289 break;
290 }
291 // otherwise, we can insert one more
292 end_of_chain = next_in_chain;
293 next_in_chain = ll_next(next_in_chain);
294 }
295
296 // insert the elements
297 if (dest_prev == NULL) {
298 // new begin
299 *begin = src;
300 } else {
301 cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
302 }
303 cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next);
304
305 // continue with next
306 src = next_in_chain;
307 dest_prev = dest;
308 dest = ll_next(dest);
309 }
310
311 // insert remaining items
312 if (src != NULL) {
313 cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
314 }
315
316 // determine new end of list, if requested
317 if (end != NULL) {
318 *end = cx_linked_list_last(
319 dest != NULL ? dest : dest_prev, loc_next);
320 }
321 }
322
323 size_t cx_linked_list_remove_chain(
324 void **begin,
325 void **end,
326 ptrdiff_t loc_prev,
327 ptrdiff_t loc_next,
328 void *node,
329 size_t num
236 ) { 330 ) {
237 assert(node != NULL); 331 assert(node != NULL);
238 assert(loc_next >= 0); 332 assert(loc_next >= 0);
239 assert(loc_prev >= 0 || begin != NULL); 333 assert(loc_prev >= 0 || begin != NULL);
240 334
335 // easy exit
336 if (num == 0) return 0;
337
241 // find adjacent nodes 338 // find adjacent nodes
242 void *next = ll_next(node);
243 void *prev; 339 void *prev;
244 if (loc_prev >= 0) { 340 if (loc_prev >= 0) {
245 prev = ll_prev(node); 341 prev = ll_prev(node);
246 } else { 342 } else {
247 prev = cx_linked_list_prev(*begin, loc_next, node); 343 prev = cx_linked_list_prev(*begin, loc_next, node);
344 }
345
346 void *next = ll_next(node);
347 size_t removed = 1;
348 for (; removed < num && next != NULL ; removed++) {
349 next = ll_next(next);
248 } 350 }
249 351
250 // update next pointer of prev node, or set begin 352 // update next pointer of prev node, or set begin
251 if (prev == NULL) { 353 if (prev == NULL) {
252 if (begin != NULL) { 354 if (begin != NULL) {
262 *end = prev; 364 *end = prev;
263 } 365 }
264 } else if (loc_prev >= 0) { 366 } else if (loc_prev >= 0) {
265 ll_prev(next) = prev; 367 ll_prev(next) = prev;
266 } 368 }
369
370 return removed;
267 } 371 }
268 372
269 size_t cx_linked_list_size( 373 size_t cx_linked_list_size(
270 void const *node, 374 const void *node,
271 ptrdiff_t loc_next 375 ptrdiff_t loc_next
272 ) { 376 ) {
273 assert(loc_next >= 0); 377 assert(loc_next >= 0);
274 size_t size = 0; 378 size_t size = 0;
275 while (node != NULL) { 379 while (node != NULL) {
325 n++; 429 n++;
326 } 430 }
327 431
328 // Update pointer 432 // Update pointer
329 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL; 433 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
330 cx_for_n (i, length - 1) { 434 for (size_t i = 0 ; i < length - 1; i++) {
331 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next); 435 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
332 } 436 }
333 ll_next(sorted[length - 1]) = NULL; 437 ll_next(sorted[length - 1]) = NULL;
334 438
335 *begin = sorted[0]; 439 *begin = sorted[0];
336 *end = sorted[length-1]; 440 *end = sorted[length - 1];
337 if (sorted != sbo) { 441 if (sorted != sbo) {
338 free(sorted); 442 free(sorted);
339 } 443 }
340 } 444 }
341 445
403 if (end) *end = sorted_end; 507 if (end) *end = sorted_end;
404 } 508 }
405 } 509 }
406 510
407 int cx_linked_list_compare( 511 int cx_linked_list_compare(
408 void const *begin_left, 512 const void *begin_left,
409 void const *begin_right, 513 const void *begin_right,
410 ptrdiff_t loc_advance, 514 ptrdiff_t loc_advance,
411 ptrdiff_t loc_data, 515 ptrdiff_t loc_data,
412 cx_compare_func cmp_func 516 cx_compare_func cmp_func
413 ) { 517 ) {
414 void const *left = begin_left, *right = begin_right; 518 const void *left = begin_left, *right = begin_right;
415 519
416 while (left != NULL && right != NULL) { 520 while (left != NULL && right != NULL) {
417 void const *left_data = ll_data(left); 521 const void *left_data = ll_data(left);
418 void const *right_data = ll_data(right); 522 const void *right_data = ll_data(right);
419 int result = cmp_func(left_data, right_data); 523 int result = cmp_func(left_data, right_data);
420 if (result != 0) return result; 524 if (result != 0) return result;
421 left = ll_advance(left); 525 left = ll_advance(left);
422 right = ll_advance(right); 526 right = ll_advance(right);
423 } 527 }
457 } 561 }
458 *begin = prev; 562 *begin = prev;
459 } 563 }
460 564
461 // HIGH LEVEL LINKED LIST IMPLEMENTATION 565 // HIGH LEVEL LINKED LIST IMPLEMENTATION
462
463 bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
464 566
465 typedef struct cx_linked_list_node cx_linked_list_node; 567 typedef struct cx_linked_list_node cx_linked_list_node;
466 struct cx_linked_list_node { 568 struct cx_linked_list_node {
467 cx_linked_list_node *prev; 569 cx_linked_list_node *prev;
468 cx_linked_list_node *next; 570 cx_linked_list_node *next;
478 cx_linked_list_node *begin; 580 cx_linked_list_node *begin;
479 cx_linked_list_node *end; 581 cx_linked_list_node *end;
480 } cx_linked_list; 582 } cx_linked_list;
481 583
482 static cx_linked_list_node *cx_ll_node_at( 584 static cx_linked_list_node *cx_ll_node_at(
483 cx_linked_list const *list, 585 const cx_linked_list *list,
484 size_t index 586 size_t index
485 ) { 587 ) {
486 if (index >= list->base.size) { 588 if (index >= list->base.collection.size) {
487 return NULL; 589 return NULL;
488 } else if (index > list->base.size / 2) { 590 } else if (index > list->base.collection.size / 2) {
489 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); 591 return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index);
490 } else { 592 } else {
491 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 593 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
492 } 594 }
595 }
596
597 static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) {
598 return cxMalloc(list->collection.allocator,
599 sizeof(cx_linked_list_node) + list->collection.elem_size);
493 } 600 }
494 601
495 static int cx_ll_insert_at( 602 static int cx_ll_insert_at(
496 struct cx_list_s *list, 603 struct cx_list_s *list,
497 cx_linked_list_node *node, 604 cx_linked_list_node *node,
498 void const *elem 605 const void *elem
499 ) { 606 ) {
500 607
501 // create the new new_node 608 // create the new new_node
502 cx_linked_list_node *new_node = cxMalloc(list->allocator, 609 cx_linked_list_node *new_node = cx_ll_malloc_node(list);
503 sizeof(cx_linked_list_node) + list->item_size);
504 610
505 // sortir if failed 611 // sortir if failed
506 if (new_node == NULL) return 1; 612 if (new_node == NULL) return 1;
507 613
508 // initialize new new_node 614 // initialize new new_node
509 new_node->prev = new_node->next = NULL; 615 new_node->prev = new_node->next = NULL;
510 memcpy(new_node->payload, elem, list->item_size); 616 memcpy(new_node->payload, elem, list->collection.elem_size);
511 617
512 // insert 618 // insert
513 cx_linked_list *ll = (cx_linked_list *) list; 619 cx_linked_list *ll = (cx_linked_list *) list;
514 cx_linked_list_insert_chain( 620 cx_linked_list_insert_chain(
515 (void **) &ll->begin, (void **) &ll->end, 621 (void **) &ll->begin, (void **) &ll->end,
516 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, 622 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
517 node, new_node, new_node 623 node, new_node, new_node
518 ); 624 );
519 625
520 // increase the size and return 626 // increase the size and return
521 list->size++; 627 list->collection.size++;
522 return 0; 628 return 0;
523 } 629 }
524 630
525 static size_t cx_ll_insert_array( 631 static size_t cx_ll_insert_array(
526 struct cx_list_s *list, 632 struct cx_list_s *list,
527 size_t index, 633 size_t index,
528 void const *array, 634 const void *array,
529 size_t n 635 size_t n
530 ) { 636 ) {
531 // out-of bounds and corner case check 637 // out-of bounds and corner case check
532 if (index > list->size || n == 0) return 0; 638 if (index > list->collection.size || n == 0) return 0;
533 639
534 // find position efficiently 640 // find position efficiently
535 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); 641 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
536 642
537 // perform first insert 643 // perform first insert
538 if (0 != cx_ll_insert_at(list, node, array)) { 644 if (0 != cx_ll_insert_at(list, node, array)) return 1;
539 return 1;
540 }
541 645
542 // is there more? 646 // is there more?
543 if (n == 1) return 1; 647 if (n == 1) return 1;
544 648
545 // we now know exactly where we are 649 // we now know exactly where we are
546 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; 650 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
547 651
548 // we can add the remaining nodes and immedately advance to the inserted node 652 // we can add the remaining nodes and immediately advance to the inserted node
549 char const *source = array; 653 const char *source = array;
550 for (size_t i = 1; i < n; i++) { 654 for (size_t i = 1; i < n; i++) {
551 source += list->item_size; 655 source += list->collection.elem_size;
552 if (0 != cx_ll_insert_at(list, node, source)) { 656 if (0 != cx_ll_insert_at(list, node, source)) return i;
553 return i;
554 }
555 node = node->next; 657 node = node->next;
556 } 658 }
557 return n; 659 return n;
558 } 660 }
559 661
560 static int cx_ll_insert_element( 662 static int cx_ll_insert_element(
561 struct cx_list_s *list, 663 struct cx_list_s *list,
562 size_t index, 664 size_t index,
563 void const *element 665 const void *element
564 ) { 666 ) {
565 return 1 != cx_ll_insert_array(list, index, element, 1); 667 return 1 != cx_ll_insert_array(list, index, element, 1);
566 } 668 }
567 669
568 static int cx_ll_remove( 670 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func;
671
672 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) {
673 const cx_linked_list_node *left = l;
674 const cx_linked_list_node *right = r;
675 return cx_ll_insert_sorted_cmp_func(left->payload, right->payload);
676 }
677
678 static size_t cx_ll_insert_sorted(
569 struct cx_list_s *list, 679 struct cx_list_s *list,
570 size_t index 680 const void *array,
681 size_t n
682 ) {
683 // special case
684 if (n == 0) return 0;
685
686 // create a new chain of nodes
687 cx_linked_list_node *chain = cx_ll_malloc_node(list);
688 if (chain == NULL) return 0;
689
690 memcpy(chain->payload, array, list->collection.elem_size);
691 chain->prev = NULL;
692 chain->next = NULL;
693
694 // add all elements from the array to that chain
695 cx_linked_list_node *prev = chain;
696 const char *src = array;
697 size_t inserted = 1;
698 for (; inserted < n; inserted++) {
699 cx_linked_list_node *next = cx_ll_malloc_node(list);
700 if (next == NULL) break;
701 src += list->collection.elem_size;
702 memcpy(next->payload, src, list->collection.elem_size);
703 prev->next = next;
704 next->prev = prev;
705 prev = next;
706 }
707 prev->next = NULL;
708
709 // invoke the low level function
710 cx_linked_list *ll = (cx_linked_list *) list;
711 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
712 cx_linked_list_insert_sorted_chain(
713 (void **) &ll->begin,
714 (void **) &ll->end,
715 CX_LL_LOC_PREV,
716 CX_LL_LOC_NEXT,
717 chain,
718 cx_ll_insert_sorted_cmp_helper
719 );
720
721 // adjust the list metadata
722 list->collection.size += inserted;
723
724 return inserted;
725 }
726
727 static size_t cx_ll_remove(
728 struct cx_list_s *list,
729 size_t index,
730 size_t num,
731 void *targetbuf
571 ) { 732 ) {
572 cx_linked_list *ll = (cx_linked_list *) list; 733 cx_linked_list *ll = (cx_linked_list *) list;
573 cx_linked_list_node *node = cx_ll_node_at(ll, index); 734 cx_linked_list_node *node = cx_ll_node_at(ll, index);
574 735
575 // out-of-bounds check 736 // out-of-bounds check
576 if (node == NULL) return 1; 737 if (node == NULL) return 0;
577
578 // element destruction
579 cx_invoke_destructor(list, node->payload);
580 738
581 // remove 739 // remove
582 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 740 size_t removed = cx_linked_list_remove_chain(
583 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 741 (void **) &ll->begin,
742 (void **) &ll->end,
743 CX_LL_LOC_PREV,
744 CX_LL_LOC_NEXT,
745 node,
746 num
747 );
584 748
585 // adjust size 749 // adjust size
586 list->size--; 750 list->collection.size -= removed;
587 751
588 // free and return 752 // copy or destroy the removed chain
589 cxFree(list->allocator, node); 753 if (targetbuf == NULL) {
590 754 cx_linked_list_node *n = node;
591 return 0; 755 for (size_t i = 0; i < removed; i++) {
756 // element destruction
757 cx_invoke_destructor(list, n->payload);
758
759 // free the node and advance
760 void *next = n->next;
761 cxFree(list->collection.allocator, n);
762 n = next;
763 }
764 } else {
765 char *dest = targetbuf;
766 cx_linked_list_node *n = node;
767 for (size_t i = 0; i < removed; i++) {
768 // copy payload
769 memcpy(dest, n->payload, list->collection.elem_size);
770
771 // advance target buffer
772 dest += list->collection.elem_size;
773
774 // free the node and advance
775 void *next = n->next;
776 cxFree(list->collection.allocator, n);
777 n = next;
778 }
779 }
780
781 return removed;
592 } 782 }
593 783
594 static void cx_ll_clear(struct cx_list_s *list) { 784 static void cx_ll_clear(struct cx_list_s *list) {
595 if (list->size == 0) return; 785 if (list->collection.size == 0) return;
596 786
597 cx_linked_list *ll = (cx_linked_list *) list; 787 cx_linked_list *ll = (cx_linked_list *) list;
598 cx_linked_list_node *node = ll->begin; 788 cx_linked_list_node *node = ll->begin;
599 while (node != NULL) { 789 while (node != NULL) {
600 cx_invoke_destructor(list, node->payload); 790 cx_invoke_destructor(list, node->payload);
601 cx_linked_list_node *next = node->next; 791 cx_linked_list_node *next = node->next;
602 cxFree(list->allocator, node); 792 cxFree(list->collection.allocator, node);
603 node = next; 793 node = next;
604 } 794 }
605 ll->begin = ll->end = NULL; 795 ll->begin = ll->end = NULL;
606 list->size = 0; 796 list->collection.size = 0;
607 } 797 }
608
609 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
610 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128
611 #endif
612 798
613 static int cx_ll_swap( 799 static int cx_ll_swap(
614 struct cx_list_s *list, 800 struct cx_list_s *list,
615 size_t i, 801 size_t i,
616 size_t j 802 size_t j
617 ) { 803 ) {
618 if (i >= list->size || j >= list->size) return 1; 804 if (i >= list->collection.size || j >= list->collection.size) return 1;
619 if (i == j) return 0; 805 if (i == j) return 0;
620 806
621 // perform an optimized search that finds both elements in one run 807 // perform an optimized search that finds both elements in one run
622 cx_linked_list *ll = (cx_linked_list *) list; 808 cx_linked_list *ll = (cx_linked_list *) list;
623 size_t mid = list->size / 2; 809 size_t mid = list->collection.size / 2;
624 size_t left, right; 810 size_t left, right;
625 if (i < j) { 811 if (i < j) {
626 left = i; 812 left = i;
627 right = j; 813 right = j;
628 } else { 814 } else {
629 left = j; 815 left = j;
630 right = i; 816 right = i;
631 } 817 }
632 cx_linked_list_node *nleft, *nright; 818 cx_linked_list_node *nleft = NULL, *nright = NULL;
633 if (left < mid && right < mid) { 819 if (left < mid && right < mid) {
634 // case 1: both items left from mid 820 // case 1: both items left from mid
635 nleft = cx_ll_node_at(ll, left); 821 nleft = cx_ll_node_at(ll, left);
822 assert(nleft != NULL);
636 nright = nleft; 823 nright = nleft;
637 for (size_t c = left; c < right; c++) { 824 for (size_t c = left; c < right; c++) {
638 nright = nright->next; 825 nright = nright->next;
639 } 826 }
640 } else if (left >= mid && right >= mid) { 827 } else if (left >= mid && right >= mid) {
641 // case 2: both items right from mid 828 // case 2: both items right from mid
642 nright = cx_ll_node_at(ll, right); 829 nright = cx_ll_node_at(ll, right);
830 assert(nright != NULL);
643 nleft = nright; 831 nleft = nright;
644 for (size_t c = right; c > left; c--) { 832 for (size_t c = right; c > left; c--) {
645 nleft = nleft->prev; 833 nleft = nleft->prev;
646 } 834 }
647 } else { 835 } else {
648 // case 3: one item left, one item right 836 // case 3: one item left, one item right
649 837
650 // chose the closest to begin / end 838 // chose the closest to begin / end
651 size_t closest; 839 size_t closest;
652 size_t other; 840 size_t other;
653 size_t diff2boundary = list->size - right - 1; 841 size_t diff2boundary = list->collection.size - right - 1;
654 if (left <= diff2boundary) { 842 if (left <= diff2boundary) {
655 closest = left; 843 closest = left;
656 other = right; 844 other = right;
657 nleft = cx_ll_node_at(ll, left); 845 nleft = cx_ll_node_at(ll, left);
658 } else { 846 } else {
684 nleft = cx_ll_node_at(ll, other); 872 nleft = cx_ll_node_at(ll, other);
685 } 873 }
686 } 874 }
687 } 875 }
688 876
689 if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { 877 cx_linked_list_node *prev = nleft->prev;
690 cx_linked_list_node *prev = nleft->prev; 878 cx_linked_list_node *next = nright->next;
691 cx_linked_list_node *next = nright->next; 879 cx_linked_list_node *midstart = nleft->next;
692 cx_linked_list_node *midstart = nleft->next; 880 cx_linked_list_node *midend = nright->prev;
693 cx_linked_list_node *midend = nright->prev; 881
694 882 if (prev == NULL) {
695 if (prev == NULL) { 883 ll->begin = nright;
696 ll->begin = nright; 884 } else {
697 } else { 885 prev->next = nright;
698 prev->next = nright; 886 }
699 } 887 nright->prev = prev;
700 nright->prev = prev; 888 if (midstart == nright) {
701 if (midstart == nright) { 889 // special case: both nodes are adjacent
702 // special case: both nodes are adjacent 890 nright->next = nleft;
703 nright->next = nleft; 891 nleft->prev = nright;
704 nleft->prev = nright; 892 } else {
705 } else { 893 // likely case: a chain is between the two nodes
706 // likely case: a chain is between the two nodes 894 nright->next = midstart;
707 nright->next = midstart; 895 midstart->prev = nright;
708 midstart->prev = nright; 896 midend->next = nleft;
709 midend->next = nleft; 897 nleft->prev = midend;
710 nleft->prev = midend; 898 }
711 } 899 nleft->next = next;
712 nleft->next = next; 900 if (next == NULL) {
713 if (next == NULL) { 901 ll->end = nleft;
714 ll->end = nleft; 902 } else {
715 } else { 903 next->prev = nleft;
716 next->prev = nleft;
717 }
718 } else {
719 // swap payloads to avoid relinking
720 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
721 memcpy(buf, nleft->payload, list->item_size);
722 memcpy(nleft->payload, nright->payload, list->item_size);
723 memcpy(nright->payload, buf, list->item_size);
724 } 904 }
725 905
726 return 0; 906 return 0;
727 } 907 }
728 908
729 static void *cx_ll_at( 909 static void *cx_ll_at(
730 struct cx_list_s const *list, 910 const struct cx_list_s *list,
731 size_t index 911 size_t index
732 ) { 912 ) {
733 cx_linked_list *ll = (cx_linked_list *) list; 913 cx_linked_list *ll = (cx_linked_list *) list;
734 cx_linked_list_node *node = cx_ll_node_at(ll, index); 914 cx_linked_list_node *node = cx_ll_node_at(ll, index);
735 return node == NULL ? NULL : node->payload; 915 return node == NULL ? NULL : node->payload;
736 } 916 }
737 917
738 static ssize_t cx_ll_find( 918 static size_t cx_ll_find_remove(
739 struct cx_list_s const *list, 919 struct cx_list_s *list,
740 void const *elem 920 const void *elem,
741 ) { 921 bool remove
742 return cx_linked_list_find(((cx_linked_list *) list)->begin, 922 ) {
743 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 923 if (list->collection.size == 0) return 0;
744 list->cmpfunc, elem); 924
925 size_t index;
926 cx_linked_list *ll = ((cx_linked_list *) list);
927 cx_linked_list_node *node = cx_linked_list_find(
928 ll->begin,
929 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
930 list->collection.cmpfunc, elem,
931 &index
932 );
933 if (node == NULL) {
934 return list->collection.size;
935 }
936 if (remove) {
937 cx_invoke_destructor(list, node->payload);
938 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
939 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
940 list->collection.size--;
941 cxFree(list->collection.allocator, node);
942 }
943 return index;
745 } 944 }
746 945
747 static void cx_ll_sort(struct cx_list_s *list) { 946 static void cx_ll_sort(struct cx_list_s *list) {
748 cx_linked_list *ll = (cx_linked_list *) list; 947 cx_linked_list *ll = (cx_linked_list *) list;
749 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 948 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
750 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 949 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
751 list->cmpfunc); 950 list->collection.cmpfunc);
752 } 951 }
753 952
754 static void cx_ll_reverse(struct cx_list_s *list) { 953 static void cx_ll_reverse(struct cx_list_s *list) {
755 cx_linked_list *ll = (cx_linked_list *) list; 954 cx_linked_list *ll = (cx_linked_list *) list;
756 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); 955 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
757 } 956 }
758 957
759 static int cx_ll_compare( 958 static int cx_ll_compare(
760 struct cx_list_s const *list, 959 const struct cx_list_s *list,
761 struct cx_list_s const *other 960 const struct cx_list_s *other
762 ) { 961 ) {
763 cx_linked_list *left = (cx_linked_list *) list; 962 cx_linked_list *left = (cx_linked_list *) list;
764 cx_linked_list *right = (cx_linked_list *) other; 963 cx_linked_list *right = (cx_linked_list *) other;
765 return cx_linked_list_compare(left->begin, right->begin, 964 return cx_linked_list_compare(left->begin, right->begin,
766 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 965 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
767 list->cmpfunc); 966 list->collection.cmpfunc);
768 } 967 }
769 968
770 static bool cx_ll_iter_valid(void const *it) { 969 static bool cx_ll_iter_valid(const void *it) {
771 struct cx_iterator_s const *iter = it; 970 const struct cx_iterator_s *iter = it;
772 return iter->elem_handle != NULL; 971 return iter->elem_handle != NULL;
773 } 972 }
774 973
775 static void cx_ll_iter_next(void *it) { 974 static void cx_ll_iter_next(void *it) {
776 struct cx_iterator_base_s *itbase = it; 975 struct cx_iterator_s *iter = it;
777 if (itbase->remove) { 976 if (iter->base.remove) {
778 itbase->remove = false; 977 iter->base.remove = false;
779 struct cx_mut_iterator_s *iter = it; 978 struct cx_list_s *list = iter->src_handle.m;
780 struct cx_list_s *list = iter->src_handle; 979 cx_linked_list *ll = iter->src_handle.m;
781 cx_linked_list *ll = iter->src_handle;
782 cx_linked_list_node *node = iter->elem_handle; 980 cx_linked_list_node *node = iter->elem_handle;
783 iter->elem_handle = node->next; 981 iter->elem_handle = node->next;
784 cx_invoke_destructor(list, node->payload); 982 cx_invoke_destructor(list, node->payload);
785 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 983 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
786 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 984 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
787 list->size--; 985 list->collection.size--;
788 cxFree(list->allocator, node); 986 cxFree(list->collection.allocator, node);
789 } else { 987 } else {
790 struct cx_iterator_s *iter = it;
791 iter->index++; 988 iter->index++;
792 cx_linked_list_node *node = iter->elem_handle; 989 cx_linked_list_node *node = iter->elem_handle;
793 iter->elem_handle = node->next; 990 iter->elem_handle = node->next;
794 } 991 }
795 } 992 }
796 993
797 static void cx_ll_iter_prev(void *it) { 994 static void cx_ll_iter_prev(void *it) {
798 struct cx_iterator_base_s *itbase = it; 995 struct cx_iterator_s *iter = it;
799 if (itbase->remove) { 996 if (iter->base.remove) {
800 itbase->remove = false; 997 iter->base.remove = false;
801 struct cx_mut_iterator_s *iter = it; 998 struct cx_list_s *list = iter->src_handle.m;
802 struct cx_list_s *list = iter->src_handle; 999 cx_linked_list *ll = iter->src_handle.m;
803 cx_linked_list *ll = iter->src_handle;
804 cx_linked_list_node *node = iter->elem_handle; 1000 cx_linked_list_node *node = iter->elem_handle;
805 iter->elem_handle = node->prev; 1001 iter->elem_handle = node->prev;
806 iter->index--; 1002 iter->index--;
807 cx_invoke_destructor(list, node->payload); 1003 cx_invoke_destructor(list, node->payload);
808 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 1004 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
809 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 1005 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
810 list->size--; 1006 list->collection.size--;
811 cxFree(list->allocator, node); 1007 cxFree(list->collection.allocator, node);
812 } else { 1008 } else {
813 struct cx_iterator_s *iter = it;
814 iter->index--; 1009 iter->index--;
815 cx_linked_list_node *node = iter->elem_handle; 1010 cx_linked_list_node *node = iter->elem_handle;
816 iter->elem_handle = node->prev; 1011 iter->elem_handle = node->prev;
817 } 1012 }
818 } 1013 }
819 1014
820 static void *cx_ll_iter_current(void const *it) { 1015 static void *cx_ll_iter_current(const void *it) {
821 struct cx_iterator_s const *iter = it; 1016 const struct cx_iterator_s *iter = it;
822 cx_linked_list_node *node = iter->elem_handle; 1017 cx_linked_list_node *node = iter->elem_handle;
823 return node->payload; 1018 return node->payload;
824 } 1019 }
825 1020
826 static bool cx_ll_iter_flag_rm(void *it) {
827 struct cx_iterator_base_s *iter = it;
828 if (iter->mutating) {
829 iter->remove = true;
830 return true;
831 } else {
832 return false;
833 }
834 }
835
836 static CxIterator cx_ll_iterator( 1021 static CxIterator cx_ll_iterator(
837 struct cx_list_s const *list, 1022 const struct cx_list_s *list,
838 size_t index, 1023 size_t index,
839 bool backwards 1024 bool backwards
840 ) { 1025 ) {
841 CxIterator iter; 1026 CxIterator iter;
842 iter.index = index; 1027 iter.index = index;
843 iter.src_handle = list; 1028 iter.src_handle.c = list;
844 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); 1029 iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index);
1030 iter.elem_size = list->collection.elem_size;
1031 iter.elem_count = list->collection.size;
845 iter.base.valid = cx_ll_iter_valid; 1032 iter.base.valid = cx_ll_iter_valid;
846 iter.base.current = cx_ll_iter_current; 1033 iter.base.current = cx_ll_iter_current;
847 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; 1034 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
848 iter.base.flag_removal = cx_ll_iter_flag_rm;
849 iter.base.mutating = false; 1035 iter.base.mutating = false;
850 iter.base.remove = false; 1036 iter.base.remove = false;
851 return iter; 1037 return iter;
852 } 1038 }
853 1039
854 static int cx_ll_insert_iter( 1040 static int cx_ll_insert_iter(
855 CxMutIterator *iter, 1041 CxIterator *iter,
856 void const *elem, 1042 const void *elem,
857 int prepend 1043 int prepend
858 ) { 1044 ) {
859 struct cx_list_s *list = iter->src_handle; 1045 struct cx_list_s *list = iter->src_handle.m;
860 cx_linked_list_node *node = iter->elem_handle; 1046 cx_linked_list_node *node = iter->elem_handle;
861 if (node != NULL) { 1047 if (node != NULL) {
862 assert(prepend >= 0 && prepend <= 1); 1048 assert(prepend >= 0 && prepend <= 1);
863 cx_linked_list_node *choice[2] = {node, node->prev}; 1049 cx_linked_list_node *choice[2] = {node, node->prev};
864 int result = cx_ll_insert_at(list, choice[prepend], elem); 1050 int result = cx_ll_insert_at(list, choice[prepend], elem);
865 iter->index += prepend * (0 == result); 1051 if (result == 0) {
1052 iter->elem_count++;
1053 if (prepend) {
1054 iter->index++;
1055 }
1056 }
866 return result; 1057 return result;
867 } else { 1058 } else {
868 int result = cx_ll_insert_element(list, list->size, elem); 1059 int result = cx_ll_insert_element(list, list->collection.size, elem);
869 iter->index = list->size; 1060 if (result == 0) {
1061 iter->elem_count++;
1062 iter->index = list->collection.size;
1063 }
870 return result; 1064 return result;
871 } 1065 }
872 } 1066 }
873 1067
874 static void cx_ll_destructor(CxList *list) { 1068 static void cx_ll_destructor(CxList *list) {
876 1070
877 cx_linked_list_node *node = ll->begin; 1071 cx_linked_list_node *node = ll->begin;
878 while (node) { 1072 while (node) {
879 cx_invoke_destructor(list, node->payload); 1073 cx_invoke_destructor(list, node->payload);
880 void *next = node->next; 1074 void *next = node->next;
881 cxFree(list->allocator, node); 1075 cxFree(list->collection.allocator, node);
882 node = next; 1076 node = next;
883 } 1077 }
884 1078
885 cxFree(list->allocator, list); 1079 cxFree(list->collection.allocator, list);
886 } 1080 }
887 1081
888 static cx_list_class cx_linked_list_class = { 1082 static cx_list_class cx_linked_list_class = {
889 cx_ll_destructor, 1083 cx_ll_destructor,
890 cx_ll_insert_element, 1084 cx_ll_insert_element,
891 cx_ll_insert_array, 1085 cx_ll_insert_array,
1086 cx_ll_insert_sorted,
892 cx_ll_insert_iter, 1087 cx_ll_insert_iter,
893 cx_ll_remove, 1088 cx_ll_remove,
894 cx_ll_clear, 1089 cx_ll_clear,
895 cx_ll_swap, 1090 cx_ll_swap,
896 cx_ll_at, 1091 cx_ll_at,
897 cx_ll_find, 1092 cx_ll_find_remove,
898 cx_ll_sort, 1093 cx_ll_sort,
899 cx_ll_compare, 1094 cx_ll_compare,
900 cx_ll_reverse, 1095 cx_ll_reverse,
901 cx_ll_iterator, 1096 cx_ll_iterator,
902 }; 1097 };
903 1098
904 CxList *cxLinkedListCreate( 1099 CxList *cxLinkedListCreate(
905 CxAllocator const *allocator, 1100 const CxAllocator *allocator,
906 cx_compare_func comparator, 1101 cx_compare_func comparator,
907 size_t item_size 1102 size_t elem_size
908 ) { 1103 ) {
909 if (allocator == NULL) { 1104 if (allocator == NULL) {
910 allocator = cxDefaultAllocator; 1105 allocator = cxDefaultAllocator;
911 } 1106 }
912 1107
913 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 1108 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
914 if (list == NULL) return NULL; 1109 if (list == NULL) return NULL;
915 1110 cx_list_init((CxList*)list, &cx_linked_list_class,
916 list->base.cl = &cx_linked_list_class; 1111 allocator, comparator, elem_size);
917 list->base.allocator = allocator;
918 list->base.cmpfunc = comparator;
919
920 if (item_size > 0) {
921 list->base.item_size = item_size;
922 } else {
923 cxListStorePointers((CxList *) list);
924 }
925 1112
926 return (CxList *) list; 1113 return (CxList *) list;
927 } 1114 }

Mercurial Repository: webserver

mercurial