comparison: src/list.c
src/list.c
- changeset 1466
- a58c65d31342
- parent 1463
- e228b5bde7f6
equal
deleted
inserted
replaced
| 1465:dc886f1a6155 | 1466:a58c65d31342 |
|---|---|
| 864 int cxListDifference(CxList *dst, | 864 int cxListDifference(CxList *dst, |
| 865 const CxList *minuend, const CxList *subtrahend, | 865 const CxList *minuend, const CxList *subtrahend, |
| 866 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) { | 866 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) { |
| 867 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; | 867 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; |
| 868 | 868 |
| 869 // first, remove existing items from dst when needed | 869 // optimize for sorted collections |
| 870 if (cxCollectionSorted(dst) && cxCollectionSorted(subtrahend)) { | |
| 871 CxIterator dst_iter = cxListIterator(dst); | |
| 872 CxIterator sub_iter = cxListIterator(subtrahend); | |
| 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)) { | 870 if (cxCollectionSorted(minuend) && cxCollectionSorted(subtrahend)) { |
| 903 bool dst_was_empty = cxCollectionSize(dst) == 0; | 871 bool dst_was_empty = cxCollectionSize(dst) == 0; |
| 904 | 872 |
| 905 CxIterator min_iter = cxListIterator(minuend); | 873 CxIterator min_iter = cxListIterator(minuend); |
| 906 CxIterator sub_iter = cxListIterator(subtrahend); | 874 CxIterator sub_iter = cxListIterator(subtrahend); |
