comparison: src/linked_list.c
src/linked_list.c
- changeset 807
- c8d692131b1e
- parent 764
- ccbdbd088455
- child 829
- 7d4e31d295af
equal
deleted
inserted
replaced
| 806:e06249e09f99 | 807:c8d692131b1e |
|---|---|
| 478 *begin = prev; | 478 *begin = prev; |
| 479 } | 479 } |
| 480 | 480 |
| 481 // HIGH LEVEL LINKED LIST IMPLEMENTATION | 481 // HIGH LEVEL LINKED LIST IMPLEMENTATION |
| 482 | 482 |
| 483 bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false; | |
| 484 | |
| 485 typedef struct cx_linked_list_node cx_linked_list_node; | 483 typedef struct cx_linked_list_node cx_linked_list_node; |
| 486 struct cx_linked_list_node { | 484 struct cx_linked_list_node { |
| 487 cx_linked_list_node *prev; | 485 cx_linked_list_node *prev; |
| 488 cx_linked_list_node *next; | 486 cx_linked_list_node *next; |
| 489 char payload[]; | 487 char payload[]; |
| 627 } | 625 } |
| 628 | 626 |
| 629 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE | 627 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE |
| 630 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128 | 628 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128 |
| 631 #endif | 629 #endif |
| 630 unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE; | |
| 632 | 631 |
| 633 static int cx_ll_swap( | 632 static int cx_ll_swap( |
| 634 struct cx_list_s *list, | 633 struct cx_list_s *list, |
| 635 size_t i, | 634 size_t i, |
| 636 size_t j | 635 size_t j |
| 651 } | 650 } |
| 652 cx_linked_list_node *nleft, *nright; | 651 cx_linked_list_node *nleft, *nright; |
| 653 if (left < mid && right < mid) { | 652 if (left < mid && right < mid) { |
| 654 // case 1: both items left from mid | 653 // case 1: both items left from mid |
| 655 nleft = cx_ll_node_at(ll, left); | 654 nleft = cx_ll_node_at(ll, left); |
| 655 assert(nleft != NULL); | |
| 656 nright = nleft; | 656 nright = nleft; |
| 657 for (size_t c = left; c < right; c++) { | 657 for (size_t c = left; c < right; c++) { |
| 658 nright = nright->next; | 658 nright = nright->next; |
| 659 } | 659 } |
| 660 } else if (left >= mid && right >= mid) { | 660 } else if (left >= mid && right >= mid) { |
| 661 // case 2: both items right from mid | 661 // case 2: both items right from mid |
| 662 nright = cx_ll_node_at(ll, right); | 662 nright = cx_ll_node_at(ll, right); |
| 663 assert(nright != NULL); | |
| 663 nleft = nright; | 664 nleft = nright; |
| 664 for (size_t c = right; c > left; c--) { | 665 for (size_t c = right; c > left; c--) { |
| 665 nleft = nleft->prev; | 666 nleft = nleft->prev; |
| 666 } | 667 } |
| 667 } else { | 668 } else { |
| 704 nleft = cx_ll_node_at(ll, other); | 705 nleft = cx_ll_node_at(ll, other); |
| 705 } | 706 } |
| 706 } | 707 } |
| 707 } | 708 } |
| 708 | 709 |
| 709 if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { | 710 if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE) { |
| 710 cx_linked_list_node *prev = nleft->prev; | 711 cx_linked_list_node *prev = nleft->prev; |
| 711 cx_linked_list_node *next = nright->next; | 712 cx_linked_list_node *next = nright->next; |
| 712 cx_linked_list_node *midstart = nleft->next; | 713 cx_linked_list_node *midstart = nleft->next; |
| 713 cx_linked_list_node *midend = nright->prev; | 714 cx_linked_list_node *midend = nright->prev; |
| 714 | 715 |
