comparison: src/list.c
src/list.c
- changeset 1453
- b6fc5b1d5c5d
- parent 1449
- bbca398783ed
- child 1454
- 808688e304d5
equal
deleted
inserted
replaced
| 1452:26e006ba651d | 1453:b6fc5b1d5c5d |
|---|---|
| 803 void cxListFree(CxList *list) { | 803 void cxListFree(CxList *list) { |
| 804 if (list == NULL) return; | 804 if (list == NULL) return; |
| 805 list->cl->deallocate(list); | 805 list->cl->deallocate(list); |
| 806 } | 806 } |
| 807 | 807 |
| 808 static void cx_list_pop_uninitialized_elements(CxList *list, size_t n) { | |
| 809 cx_destructor_func destr_bak = list->collection.simple_destructor; | |
| 810 cx_destructor_func2 destr2_bak = list->collection.advanced_destructor; | |
| 811 list->collection.simple_destructor = NULL; | |
| 812 list->collection.advanced_destructor = NULL; | |
| 813 if (n == 1) { | |
| 814 cxListRemove(list, list->collection.size - 1); | |
| 815 } else { | |
| 816 cxListRemoveArray(list,list->collection.size - n, n); | |
| 817 } | |
| 818 list->collection.simple_destructor = destr_bak; | |
| 819 list->collection.advanced_destructor = destr2_bak; | |
| 820 } | |
| 821 | |
| 808 int cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func, | 822 int cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func, |
| 809 const CxAllocator *clone_allocator, void *data) { | 823 const CxAllocator *clone_allocator, void *data) { |
| 810 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; | 824 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; |
| 811 | 825 |
| 812 // remember the original size | 826 // remember the original size |
| 837 } | 851 } |
| 838 | 852 |
| 839 // if we could not clone everything, free the allocated memory | 853 // if we could not clone everything, free the allocated memory |
| 840 // (disable the destructors!) | 854 // (disable the destructors!) |
| 841 if (cloned < src->collection.size) { | 855 if (cloned < src->collection.size) { |
| 842 cx_destructor_func destr_bak = dst->collection.simple_destructor; | 856 cx_list_pop_uninitialized_elements(dst, |
| 843 cx_destructor_func2 destr2_bak = dst->collection.advanced_destructor; | |
| 844 dst->collection.simple_destructor = NULL; | |
| 845 dst->collection.advanced_destructor = NULL; | |
| 846 cxListRemoveArray(dst, | |
| 847 orig_size + cloned, | |
| 848 dst->collection.size - cloned - orig_size); | 857 dst->collection.size - cloned - orig_size); |
| 849 dst->collection.simple_destructor = destr_bak; | |
| 850 dst->collection.advanced_destructor = destr2_bak; | |
| 851 return 1; | 858 return 1; |
| 852 } | 859 } |
| 853 | 860 |
| 854 return 0; | 861 return 0; |
| 855 } | 862 } |
| 863 | |
| 864 int cxListDifference(CxList *dst, | |
| 865 const CxList *minuend, const CxList *subtrahend, | |
| 866 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) { | |
| 867 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; | |
| 868 | |
| 869 // first, remove existing items from dst when needed | |
| 870 if (cxCollectionSorted(dst) && cxCollectionSorted(subtrahend)) { | |
| 871 CxIterator sub_iter = cxListIterator(dst); | |
| 872 CxIterator dst_iter = cxListIterator(dst); | |
| 873 while (cxIteratorValid(dst_iter) && cxIteratorValid(sub_iter)) { | |
| 874 void *dst_elem = cxIteratorCurrent(dst_iter); | |
| 875 void *sub_elem = cxIteratorCurrent(sub_iter); | |
| 876 cx_compare_func cmp = subtrahend->collection.cmpfunc; | |
| 877 int d = cmp(sub_elem, dst_elem); | |
| 878 if (d == 0) { | |
| 879 // is contained, so remove it | |
| 880 cxIteratorFlagRemoval(dst_iter); | |
| 881 cxIteratorNext(dst_iter); | |
| 882 } else if (d < 0) { | |
| 883 // subtrahend is smaller than the dst element, | |
| 884 // check the next element in the subtrahend | |
| 885 cxIteratorNext(sub_iter); | |
| 886 } else { | |
| 887 // subtrahend is larger than the dst element, | |
| 888 // check the next dst element | |
| 889 cxIteratorNext(dst_iter); | |
| 890 } | |
| 891 } | |
| 892 } else { | |
| 893 CxIterator dst_iter = cxListIterator(dst); | |
| 894 cx_foreach(void *, elem, dst_iter) { | |
| 895 if (cxListContains(subtrahend, elem)) { | |
| 896 cxIteratorFlagRemoval(dst_iter); | |
| 897 } | |
| 898 } | |
| 899 } | |
| 900 | |
| 901 // now perform the difference calculation | |
| 902 if (cxCollectionSorted(minuend) && cxCollectionSorted(subtrahend)) { | |
| 903 CxIterator min_iter = cxListIterator(minuend); | |
| 904 CxIterator sub_iter = cxListIterator(subtrahend); | |
| 905 while (cxIteratorValid(min_iter)) { | |
| 906 void *min_elem = cxIteratorCurrent(min_iter); | |
| 907 void *sub_elem; | |
| 908 int d; | |
| 909 if (cxIteratorValid(sub_iter)) { | |
| 910 sub_elem = cxIteratorCurrent(sub_iter); | |
| 911 cx_compare_func cmp = subtrahend->collection.cmpfunc; | |
| 912 d = cmp(sub_elem, min_elem); | |
| 913 } else { | |
| 914 // no more elements in the subtrahend, | |
| 915 // i.e., the min_elem is larger than any elem of the subtrahend | |
| 916 d = 1; | |
| 917 } | |
| 918 if (d == 0) { | |
| 919 // is contained, so skip it | |
| 920 cxIteratorNext(min_iter); | |
| 921 } else if (d < 0) { | |
| 922 // subtrahend is smaller than minuend, | |
| 923 // check the next element | |
| 924 cxIteratorNext(sub_iter); | |
| 925 } else { | |
| 926 // subtrahend is larger than the dst element, | |
| 927 // clone the minuend and advance | |
| 928 void **dst_mem = cxListEmplace(dst); | |
| 929 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; | |
| 930 void* dst_ptr = clone_func(target, min_elem, clone_allocator, data); | |
| 931 if (dst_ptr == NULL) { | |
| 932 cx_list_pop_uninitialized_elements(dst, 1); | |
| 933 return 1; | |
| 934 } | |
| 935 if (cxCollectionStoresPointers(dst)) { | |
| 936 *dst_mem = dst_ptr; | |
| 937 } | |
| 938 cxIteratorNext(min_iter); | |
| 939 } | |
| 940 } | |
| 941 } else { | |
| 942 CxIterator min_iter = cxListIterator(minuend); | |
| 943 cx_foreach(void *, elem, min_iter) { | |
| 944 if (cxListContains(subtrahend, elem)) { | |
| 945 continue; | |
| 946 } | |
| 947 void **dst_mem = cxListEmplace(dst); | |
| 948 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; | |
| 949 void* dst_ptr = clone_func(target, elem, clone_allocator, data); | |
| 950 if (dst_ptr == NULL) { | |
| 951 cx_list_pop_uninitialized_elements(dst, 1); | |
| 952 return 1; | |
| 953 } | |
| 954 if (cxCollectionStoresPointers(dst)) { | |
| 955 *dst_mem = dst_ptr; | |
| 956 } | |
| 957 } | |
| 958 } | |
| 959 | |
| 960 return 0; | |
| 961 } |
