comparison: src/linked_list.c
src/linked_list.c
- changeset 647
- 2e6e9d9f2159
- parent 641
- d402fead3386
- child 654
- c9d008861178
equal
deleted
inserted
replaced
| 646:dfd0403ff8b6 | 647:2e6e9d9f2159 |
|---|---|
| 449 *begin = prev; | 449 *begin = prev; |
| 450 } | 450 } |
| 451 | 451 |
| 452 // HIGH LEVEL LINKED LIST IMPLEMENTATION | 452 // HIGH LEVEL LINKED LIST IMPLEMENTATION |
| 453 | 453 |
| 454 bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false; | |
| 455 | |
| 454 typedef struct cx_linked_list_node cx_linked_list_node; | 456 typedef struct cx_linked_list_node cx_linked_list_node; |
| 455 struct cx_linked_list_node { | 457 struct cx_linked_list_node { |
| 456 cx_linked_list_node *prev; | 458 cx_linked_list_node *prev; |
| 457 cx_linked_list_node *next; | 459 cx_linked_list_node *next; |
| 458 char payload[]; | 460 char payload[]; |
| 571 // adjust size | 573 // adjust size |
| 572 list->size--; | 574 list->size--; |
| 573 | 575 |
| 574 // free and return | 576 // free and return |
| 575 cxFree(list->allocator, node); | 577 cxFree(list->allocator, node); |
| 578 | |
| 579 return 0; | |
| 580 } | |
| 581 | |
| 582 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE | |
| 583 #define CX_LINKED_LIST_SWAP_SBO_SIZE 16 | |
| 584 #endif | |
| 585 | |
| 586 static int cx_ll_swap( | |
| 587 struct cx_list_s *list, | |
| 588 size_t i, | |
| 589 size_t j | |
| 590 ) { | |
| 591 if (i >= list->size || j >= list->size) return 1; | |
| 592 if (i == j) return 0; | |
| 593 | |
| 594 // perform an optimized search that finds both elements in one run | |
| 595 cx_linked_list *ll = (cx_linked_list *) list; | |
| 596 size_t mid = list->size / 2; | |
| 597 size_t left, right; | |
| 598 if (i < j) { | |
| 599 left = i; | |
| 600 right = j; | |
| 601 } else { | |
| 602 left = j; | |
| 603 right = i; | |
| 604 } | |
| 605 cx_linked_list_node *nleft, *nright; | |
| 606 if (left < mid && right < mid) { | |
| 607 // case 1: both items left from mid | |
| 608 nleft = cx_ll_node_at(ll, left); | |
| 609 nright = nleft; | |
| 610 for (size_t c = left; c < right; c++) { | |
| 611 nright = nright->next; | |
| 612 } | |
| 613 } else if (left >= mid && right >= mid) { | |
| 614 // case 2: both items right from mid | |
| 615 nright = cx_ll_node_at(ll, right); | |
| 616 nleft = nright; | |
| 617 for (size_t c = right; c > left; c--) { | |
| 618 nleft = nleft->prev; | |
| 619 } | |
| 620 } else { | |
| 621 // case 3: one item left, one item right | |
| 622 | |
| 623 // chose the closest to begin / end | |
| 624 size_t closest; | |
| 625 size_t other; | |
| 626 size_t diff2boundary = list->size - right - 1; | |
| 627 if (left <= diff2boundary) { | |
| 628 closest = left; | |
| 629 other = right; | |
| 630 nleft = cx_ll_node_at(ll, left); | |
| 631 } else { | |
| 632 closest = right; | |
| 633 other = left; | |
| 634 diff2boundary = left; | |
| 635 nright = cx_ll_node_at(ll, right); | |
| 636 } | |
| 637 | |
| 638 // is other element closer to us or closer to boundary? | |
| 639 if (right - left <= diff2boundary) { | |
| 640 // search other element starting from already found element | |
| 641 if (closest == left) { | |
| 642 nright = nleft; | |
| 643 for (size_t c = left; c < right; c++) { | |
| 644 nright = nright->next; | |
| 645 } | |
| 646 } else { | |
| 647 nleft = nright; | |
| 648 for (size_t c = right; c > left; c--) { | |
| 649 nleft = nleft->prev; | |
| 650 } | |
| 651 } | |
| 652 } else { | |
| 653 // search other element starting at the boundary | |
| 654 if (closest == left) { | |
| 655 nright = cx_ll_node_at(ll, other); | |
| 656 } else { | |
| 657 nleft = cx_ll_node_at(ll, other); | |
| 658 } | |
| 659 } | |
| 660 } | |
| 661 | |
| 662 if (list->itemsize > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { | |
| 663 cx_linked_list_node *prev = nleft->prev; | |
| 664 cx_linked_list_node *next = nright->next; | |
| 665 cx_linked_list_node *midstart = nleft->next; | |
| 666 cx_linked_list_node *midend = nright->prev; | |
| 667 | |
| 668 if (prev == NULL) { | |
| 669 ll->begin = nright; | |
| 670 } else { | |
| 671 prev->next = nright; | |
| 672 } | |
| 673 nright->prev = prev; | |
| 674 if (midstart == nright) { | |
| 675 // special case: both nodes are adjacent | |
| 676 nright->next = nleft; | |
| 677 nleft->prev = nright; | |
| 678 } else { | |
| 679 // likely case: a chain is between the two nodes | |
| 680 nright->next = midstart; | |
| 681 midstart->prev = nright; | |
| 682 midend->next = nleft; | |
| 683 nleft->prev = midend; | |
| 684 } | |
| 685 nleft->next = next; | |
| 686 if (next == NULL) { | |
| 687 ll->end = nleft; | |
| 688 } else { | |
| 689 next->prev = nleft; | |
| 690 } | |
| 691 } else { | |
| 692 // swap payloads to avoid relinking | |
| 693 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; | |
| 694 memcpy(buf, nleft->payload, list->itemsize); | |
| 695 memcpy(nleft->payload, nright->payload, list->itemsize); | |
| 696 memcpy(nright->payload, buf, list->itemsize); | |
| 697 } | |
| 576 | 698 |
| 577 return 0; | 699 return 0; |
| 578 } | 700 } |
| 579 | 701 |
| 580 static void *cx_ll_at( | 702 static void *cx_ll_at( |
| 712 cx_ll_destructor, | 834 cx_ll_destructor, |
| 713 cx_ll_insert_element, | 835 cx_ll_insert_element, |
| 714 cx_ll_insert_array, | 836 cx_ll_insert_array, |
| 715 cx_ll_insert_iter, | 837 cx_ll_insert_iter, |
| 716 cx_ll_remove, | 838 cx_ll_remove, |
| 839 cx_ll_swap, | |
| 717 cx_ll_at, | 840 cx_ll_at, |
| 718 cx_ll_find, | 841 cx_ll_find, |
| 719 cx_ll_sort, | 842 cx_ll_sort, |
| 720 cx_ll_compare, | 843 cx_ll_compare, |
| 721 cx_ll_reverse, | 844 cx_ll_reverse, |
