comparison: src/list.c
src/list.c
- changeset 1469
- 9b2b40a3c9f0
- parent 1466
- a58c65d31342
equal
deleted
inserted
replaced
| 1468:0f4d90a1ae23 | 1469:9b2b40a3c9f0 |
|---|---|
| 930 } | 930 } |
| 931 } | 931 } |
| 932 | 932 |
| 933 return 0; | 933 return 0; |
| 934 } | 934 } |
| 935 | |
| 936 int cxListIntersection(CxList *dst, | |
| 937 const CxList *src, const CxList *other, | |
| 938 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) { | |
| 939 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; | |
| 940 | |
| 941 // optimize for sorted collections | |
| 942 if (cxCollectionSorted(src) && cxCollectionSorted(other)) { | |
| 943 bool dst_was_empty = cxCollectionSize(dst) == 0; | |
| 944 | |
| 945 CxIterator src_iter = cxListIterator(src); | |
| 946 CxIterator other_iter = cxListIterator(other); | |
| 947 while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) { | |
| 948 void *src_elem = cxIteratorCurrent(src_iter); | |
| 949 void *other_elem = cxIteratorCurrent(other_iter); | |
| 950 int d = src->collection.cmpfunc(src_elem, other_elem); | |
| 951 if (d == 0) { | |
| 952 // is contained, clone it | |
| 953 void **dst_mem = cxListEmplace(dst); | |
| 954 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; | |
| 955 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data); | |
| 956 if (dst_ptr == NULL) { | |
| 957 cx_list_pop_uninitialized_elements(dst, 1); | |
| 958 return 1; | |
| 959 } | |
| 960 if (cxCollectionStoresPointers(dst)) { | |
| 961 *dst_mem = dst_ptr; | |
| 962 } | |
| 963 cxIteratorNext(src_iter); | |
| 964 } else if (d < 0) { | |
| 965 // the other element is larger, skip the source element | |
| 966 cxIteratorNext(src_iter); | |
| 967 } else { | |
| 968 // the source element is larger, try to find it in the other list | |
| 969 cxIteratorNext(other_iter); | |
| 970 } | |
| 971 } | |
| 972 | |
| 973 // if dst was empty, it is now guaranteed to be sorted | |
| 974 dst->collection.sorted = dst_was_empty; | |
| 975 } else { | |
| 976 CxIterator src_iter = cxListIterator(src); | |
| 977 cx_foreach(void *, elem, src_iter) { | |
| 978 if (!cxListContains(other, elem)) { | |
| 979 continue; | |
| 980 } | |
| 981 void **dst_mem = cxListEmplace(dst); | |
| 982 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; | |
| 983 void* dst_ptr = clone_func(target, elem, clone_allocator, data); | |
| 984 if (dst_ptr == NULL) { | |
| 985 cx_list_pop_uninitialized_elements(dst, 1); | |
| 986 return 1; | |
| 987 } | |
| 988 if (cxCollectionStoresPointers(dst)) { | |
| 989 *dst_mem = dst_ptr; | |
| 990 } | |
| 991 } | |
| 992 } | |
| 993 | |
| 994 return 0; | |
| 995 } |
