comparison: src/linked_list.c
src/linked_list.c
- changeset 1113
- dce04550fbef
- parent 1111
- 78eeeb950883
equal
deleted
inserted
replaced
| 1112:22dc2163fffd | 1113:dce04550fbef |
|---|---|
| 809 } | 809 } |
| 810 ll->begin = ll->end = NULL; | 810 ll->begin = ll->end = NULL; |
| 811 list->collection.size = 0; | 811 list->collection.size = 0; |
| 812 } | 812 } |
| 813 | 813 |
| 814 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE | |
| 815 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128 | |
| 816 #endif | |
| 817 const unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE; | |
| 818 | |
| 819 static int cx_ll_swap( | 814 static int cx_ll_swap( |
| 820 struct cx_list_s *list, | 815 struct cx_list_s *list, |
| 821 size_t i, | 816 size_t i, |
| 822 size_t j | 817 size_t j |
| 823 ) { | 818 ) { |
| 892 nleft = cx_ll_node_at(ll, other); | 887 nleft = cx_ll_node_at(ll, other); |
| 893 } | 888 } |
| 894 } | 889 } |
| 895 } | 890 } |
| 896 | 891 |
| 897 if (list->collection.elem_size > CX_LINKED_LIST_SWAP_SBO_SIZE) { | 892 cx_linked_list_node *prev = nleft->prev; |
| 898 cx_linked_list_node *prev = nleft->prev; | 893 cx_linked_list_node *next = nright->next; |
| 899 cx_linked_list_node *next = nright->next; | 894 cx_linked_list_node *midstart = nleft->next; |
| 900 cx_linked_list_node *midstart = nleft->next; | 895 cx_linked_list_node *midend = nright->prev; |
| 901 cx_linked_list_node *midend = nright->prev; | 896 |
| 902 | 897 if (prev == NULL) { |
| 903 if (prev == NULL) { | 898 ll->begin = nright; |
| 904 ll->begin = nright; | 899 } else { |
| 905 } else { | 900 prev->next = nright; |
| 906 prev->next = nright; | 901 } |
| 907 } | 902 nright->prev = prev; |
| 908 nright->prev = prev; | 903 if (midstart == nright) { |
| 909 if (midstart == nright) { | 904 // special case: both nodes are adjacent |
| 910 // special case: both nodes are adjacent | 905 nright->next = nleft; |
| 911 nright->next = nleft; | 906 nleft->prev = nright; |
| 912 nleft->prev = nright; | 907 } else { |
| 913 } else { | 908 // likely case: a chain is between the two nodes |
| 914 // likely case: a chain is between the two nodes | 909 nright->next = midstart; |
| 915 nright->next = midstart; | 910 midstart->prev = nright; |
| 916 midstart->prev = nright; | 911 midend->next = nleft; |
| 917 midend->next = nleft; | 912 nleft->prev = midend; |
| 918 nleft->prev = midend; | 913 } |
| 919 } | 914 nleft->next = next; |
| 920 nleft->next = next; | 915 if (next == NULL) { |
| 921 if (next == NULL) { | 916 ll->end = nleft; |
| 922 ll->end = nleft; | 917 } else { |
| 923 } else { | 918 next->prev = nleft; |
| 924 next->prev = nleft; | |
| 925 } | |
| 926 } else { | |
| 927 // swap payloads to avoid relinking | |
| 928 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; | |
| 929 memcpy(buf, nleft->payload, list->collection.elem_size); | |
| 930 memcpy(nleft->payload, nright->payload, list->collection.elem_size); | |
| 931 memcpy(nright->payload, buf, list->collection.elem_size); | |
| 932 } | 919 } |
| 933 | 920 |
| 934 return 0; | 921 return 0; |
| 935 } | 922 } |
| 936 | 923 |
