toolkit: comparison ucx/list.c

-:488178e3e328
+:9b5948aa5b90
 const struct cx_iterator_s *iter = it;
 void **ptr = iter->base.current_impl(it);
 return ptr == NULL ? NULL : *ptr;
 }
+static int cx_pl_change_capacity(struct cx_list_s *list, size_t cap) {
+if (list->climpl->change_capacity == NULL) {
+return 0;
+} else {
+return list->climpl->change_capacity(list, cap);
+}
+}
 static struct cx_iterator_s cx_pl_iterator(
 const struct cx_list_s *list,
 size_t index,
 bool backwards
 ) {
 cx_pl_at,
 cx_pl_find_remove,
 cx_pl_sort,
 cx_pl_compare,
 cx_pl_reverse,
+cx_pl_change_capacity,
 cx_pl_iterator,
 };
 // </editor-fold>
 // <editor-fold desc="empty list implementation">
 cx_emptyl_at,
 cx_emptyl_find_remove,
 cx_emptyl_noop,
 NULL,
 cx_emptyl_noop,
+NULL,
 cx_emptyl_iterator,
 };
 CxList cx_empty_list = {
 {
 void cxListFree(CxList *list) {
 if (list == NULL) return;
 list->cl->deallocate(list);
 }
+static void cx_list_pop_uninitialized_elements(CxList *list, size_t n) {
+cx_destructor_func destr_bak = list->collection.simple_destructor;
+cx_destructor_func2 destr2_bak = list->collection.advanced_destructor;
+list->collection.simple_destructor = NULL;
+list->collection.advanced_destructor = NULL;
+if (n == 1) {
+cxListRemove(list, list->collection.size - 1);
+} else {
+cxListRemoveArray(list,list->collection.size - n, n);
+}
+list->collection.simple_destructor = destr_bak;
+list->collection.advanced_destructor = destr2_bak;
+}
+static void* cx_list_simple_clone_func(void *dst, const void *src, const CxAllocator *al, void *data) {
+size_t elem_size = *(size_t*)data;
+if (dst == NULL) dst = cxMalloc(al, elem_size);
+if (dst != NULL) memcpy(dst, src, elem_size);
+return dst;
+}
+#define use_simple_clone_func(list) cx_list_simple_clone_func, NULL, (void*)&((list)->collection.elem_size)
+int cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func,
+const CxAllocator *clone_allocator, void *data) {
+if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
+// remember the original size
+size_t orig_size = dst->collection.size;
+// first, try to allocate the memory in the new list
+CxIterator empl_iter = cxListEmplaceArray(dst, src->collection.size);
+// get an iterator over the source elements
+CxIterator src_iter = cxListIterator(src);
+// now clone the elements
+size_t cloned = empl_iter.elem_count;
+for (size_t i = 0 ; i < empl_iter.elem_count; i++) {
+void *src_elem = cxIteratorCurrent(src_iter);
+void **dest_memory = cxIteratorCurrent(empl_iter);
+void *target = cxCollectionStoresPointers(dst) ? NULL : dest_memory;
+void *dest_ptr = clone_func(target, src_elem, clone_allocator, data);
+if (dest_ptr == NULL) {
+cloned = i;
+break;
+}
+if (cxCollectionStoresPointers(dst)) {
+*dest_memory = dest_ptr;
+}
+cxIteratorNext(src_iter);
+cxIteratorNext(empl_iter);
+}
+// if we could not clone everything, free the allocated memory
+// (disable the destructors!)
+if (cloned < src->collection.size) {
+cx_list_pop_uninitialized_elements(dst,
+dst->collection.size - cloned - orig_size);
+return 1;
+}
+// set the sorted flag when we know it's sorted
+if (orig_size == 0 && src->collection.sorted) {
+dst->collection.sorted = true;
+}
+return 0;
+}
+int cxListDifference(CxList *dst,
+const CxList *minuend, const CxList *subtrahend,
+cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
+if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
+// optimize for sorted collections
+if (cxCollectionSorted(minuend) && cxCollectionSorted(subtrahend)) {
+bool dst_was_empty = cxCollectionSize(dst) == 0;
+CxIterator min_iter = cxListIterator(minuend);
+CxIterator sub_iter = cxListIterator(subtrahend);
+while (cxIteratorValid(min_iter)) {
+void *min_elem = cxIteratorCurrent(min_iter);
+void *sub_elem;
+int d;
+if (cxIteratorValid(sub_iter)) {
+sub_elem = cxIteratorCurrent(sub_iter);
+cx_compare_func cmp = subtrahend->collection.cmpfunc;
+d = cmp(sub_elem, min_elem);
+} else {
+// no more elements in the subtrahend,
+// i.e., the min_elem is larger than any elem of the subtrahend
+d = 1;
+}
+if (d == 0) {
+// is contained, so skip it
+cxIteratorNext(min_iter);
+} else if (d < 0) {
+// subtrahend is smaller than minuend,
+// check the next element
+cxIteratorNext(sub_iter);
+} else {
+// subtrahend is larger than the dst element,
+// clone the minuend and advance
+void **dst_mem = cxListEmplace(dst);
+void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
+void* dst_ptr = clone_func(target, min_elem, clone_allocator, data);
+if (dst_ptr == NULL) {
+cx_list_pop_uninitialized_elements(dst, 1);
+return 1;
+}
+if (cxCollectionStoresPointers(dst)) {
+*dst_mem = dst_ptr;
+}
+cxIteratorNext(min_iter);
+}
+}
+// if dst was empty, it is now guaranteed to be sorted
+dst->collection.sorted = dst_was_empty;
+} else {
+CxIterator min_iter = cxListIterator(minuend);
+cx_foreach(void *, elem, min_iter) {
+if (cxListContains(subtrahend, elem)) {
+continue;
+}
+void **dst_mem = cxListEmplace(dst);
+void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
+void* dst_ptr = clone_func(target, elem, clone_allocator, data);
+if (dst_ptr == NULL) {
+cx_list_pop_uninitialized_elements(dst, 1);
+return 1;
+}
+if (cxCollectionStoresPointers(dst)) {
+*dst_mem = dst_ptr;
+}
+}
+}
+return 0;
+}
+int cxListIntersection(CxList *dst,
+const CxList *src, const CxList *other,
+cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
+if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
+// optimize for sorted collections
+if (cxCollectionSorted(src) && cxCollectionSorted(other)) {
+bool dst_was_empty = cxCollectionSize(dst) == 0;
+CxIterator src_iter = cxListIterator(src);
+CxIterator other_iter = cxListIterator(other);
+while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) {
+void *src_elem = cxIteratorCurrent(src_iter);
+void *other_elem = cxIteratorCurrent(other_iter);
+int d = src->collection.cmpfunc(src_elem, other_elem);
+if (d == 0) {
+// is contained, clone it
+void **dst_mem = cxListEmplace(dst);
+void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
+void* dst_ptr = clone_func(target, src_elem, clone_allocator, data);
+if (dst_ptr == NULL) {
+cx_list_pop_uninitialized_elements(dst, 1);
+return 1;
+}
+if (cxCollectionStoresPointers(dst)) {
+*dst_mem = dst_ptr;
+}
+cxIteratorNext(src_iter);
+} else if (d < 0) {
+// the other element is larger, skip the source element
+cxIteratorNext(src_iter);
+} else {
+// the source element is larger, try to find it in the other list
+cxIteratorNext(other_iter);
+}
+}
+// if dst was empty, it is now guaranteed to be sorted
+dst->collection.sorted = dst_was_empty;
+} else {
+CxIterator src_iter = cxListIterator(src);
+cx_foreach(void *, elem, src_iter) {
+if (!cxListContains(other, elem)) {
+continue;
+}
+void **dst_mem = cxListEmplace(dst);
+void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
+void* dst_ptr = clone_func(target, elem, clone_allocator, data);
+if (dst_ptr == NULL) {
+cx_list_pop_uninitialized_elements(dst, 1);
+return 1;
+}
+if (cxCollectionStoresPointers(dst)) {
+*dst_mem = dst_ptr;
+}
+}
+}
+return 0;
+}
+int cxListUnion(CxList *dst,
+const CxList *src, const CxList *other,
+cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
+if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
+// optimize for sorted collections
+if (cxCollectionSorted(src) && cxCollectionSorted(other)) {
+bool dst_was_empty = cxCollectionSize(dst) == 0;
+CxIterator src_iter = cxListIterator(src);
+CxIterator other_iter = cxListIterator(other);
+while (cxIteratorValid(src_iter) || cxIteratorValid(other_iter)) {
+void *src_elem = NULL, *other_elem = NULL;
+int d;
+if (!cxIteratorValid(src_iter)) {
+other_elem = cxIteratorCurrent(other_iter);
+d = 1;
+} else if (!cxIteratorValid(other_iter)) {
+src_elem = cxIteratorCurrent(src_iter);
+d = -1;
+} else {
+src_elem = cxIteratorCurrent(src_iter);
+other_elem = cxIteratorCurrent(other_iter);
+d = src->collection.cmpfunc(src_elem, other_elem);
+}
+void *clone_from;
+if (d < 0) {
+// source element is smaller clone it
+clone_from = src_elem;
+cxIteratorNext(src_iter);
+} else if (d == 0) {
+// both elements are equal, clone from the source, skip other
+clone_from = src_elem;
+cxIteratorNext(src_iter);
+cxIteratorNext(other_iter);
+} else {
+// the other element is smaller, clone it
+clone_from = other_elem;
+cxIteratorNext(other_iter);
+}
+void **dst_mem = cxListEmplace(dst);
+void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
+void* dst_ptr = clone_func(target, clone_from, clone_allocator, data);
+if (dst_ptr == NULL) {
+cx_list_pop_uninitialized_elements(dst, 1);
+return 1;
+}
+if (cxCollectionStoresPointers(dst)) {
+*dst_mem = dst_ptr;
+}
+}
+// if dst was empty, it is now guaranteed to be sorted
+dst->collection.sorted = dst_was_empty;
+} else {
+if (cxListClone(dst, src, clone_func, clone_allocator, data)) {
+return 1;
+}
+CxIterator other_iter = cxListIterator(other);
+cx_foreach(void *, elem, other_iter) {
+if (cxListContains(src, elem)) {
+continue;
+}
+void **dst_mem = cxListEmplace(dst);
+void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
+void* dst_ptr = clone_func(target, elem, clone_allocator, data);
+if (dst_ptr == NULL) {
+cx_list_pop_uninitialized_elements(dst, 1);
+return 1;
+}
+if (cxCollectionStoresPointers(dst)) {
+*dst_mem = dst_ptr;
+}
+}
+}
+return 0;
+}
+int cxListCloneSimple(CxList *dst, const CxList *src) {
+return cxListClone(dst, src, use_simple_clone_func(src));
+}
+int cxListDifferenceSimple(CxList *dst, const CxList *minuend, const CxList *subtrahend) {
+return cxListDifference(dst, minuend, subtrahend, use_simple_clone_func(minuend));
+}
+int cxListIntersectionSimple(CxList *dst, const CxList *src, const CxList *other) {
+return cxListIntersection(dst, src, other, use_simple_clone_func(src));
+}
+int cxListUnionSimple(CxList *dst, const CxList *src, const CxList *other) {
+return cxListUnion(dst, src, other, use_simple_clone_func(src));
+}
+int cxListReserve(CxList *list, size_t capacity) {
+if (list->cl->change_capacity == NULL) {
+return 0;
+}
+if (capacity <= cxCollectionSize(list)) {
+return 0;
+}
+return list->cl->change_capacity(list, capacity);
+}
+int cxListShrink(CxList *list) {
+if (list->cl->change_capacity == NULL) {
+return 0;
+}
+return list->cl->change_capacity(list, cxCollectionSize(list));
+}

Mercurial > hg > toolkit / file comparison

comparison: ucx/list.c

ucx/list.c