ucx/list.c

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include "cx/list.h"

#include <string.h>
#include <assert.h>

// we don't want to include the full array_list.h.
// therefore, we only forward declare the one function we want to use
CX_EXPORT void cx_array_qsort_c(void *array, size_t nmemb, size_t size,
        cx_compare_func2 fn, void *context);


int cx_list_compare_wrapper(const void *l, const void *r, void *c) {
    CxList *list = c;
    const void *left;
    const void *right;
    if (cxCollectionStoresPointers(list)) {
        left = *(void**)l;
        right = *(void**)r;
        // for historic reasons, we are handling the NULL case here
        // because every UCX compare function does not support NULL arguments
        if (left == NULL) {
            if (right == NULL) return 0;
            return -1;
        } else if (right == NULL) {
            return 1;
        }
    } else {
        left = l;
        right = r;
    }
    return cx_invoke_compare_func(list, left, right);
}

#define cx_list_compare_wrapper(l, r, c) cx_list_compare_wrapper(l, r, (void*)c)

// <editor-fold desc="empty list implementation">

static void cx_emptyl_noop(CX_UNUSED CxList *list) {
    // this is a noop, but MUST be implemented
}

static void *cx_emptyl_at(
        CX_UNUSED const struct cx_list_s *list,
        CX_UNUSED size_t index
) {
    return NULL;
}

static size_t cx_emptyl_find_remove(
        CX_UNUSED struct cx_list_s *list,
        CX_UNUSED const void *elem,
        CX_UNUSED bool remove
) {
    return 0;
}

static bool cx_emptyl_iter_valid(CX_UNUSED const void *iter) {
    return false;
}

static CxIterator cx_emptyl_iterator(
        const struct cx_list_s *list,
        size_t index,
        CX_UNUSED bool backwards
) {
    CxIterator iter = {0};
    iter.src_handle = (void*) list;
    iter.index = index;
    iter.base.valid = cx_emptyl_iter_valid;
    return iter;
}

static cx_list_class cx_empty_list_class = {
        cx_emptyl_noop,
        NULL,
        NULL,
        NULL,
        NULL,
        NULL,
        NULL,
        cx_emptyl_noop,
        NULL,
        cx_emptyl_at,
        cx_emptyl_find_remove,
        cx_emptyl_noop,
        NULL,
        cx_emptyl_noop,
        NULL,
        cx_emptyl_iterator,
};

CxList cx_empty_list = {
    {
        NULL,
        0,
        0,
        NULL,
        NULL,
        NULL,
        NULL,
        NULL,
        NULL,
        false,
        true,
    },
    &cx_empty_list_class,
};

CxList *const cxEmptyList = &cx_empty_list;

// </editor-fold>

size_t cx_list_default_insert_array(
        struct cx_list_s *list,
        size_t index,
        const void *data,
        size_t n
) {
    const char *src = data;
    size_t i = 0;
    for (; i < n; i++) {
        if (NULL == list->cl->insert_element(list, index + i, src)) {
            return i; // LCOV_EXCL_LINE
        }
        if (src != NULL) {
            src += list->collection.elem_size;
        }
    }
    return i;
}

static size_t cx_list_default_insert_sorted_impl(
        struct cx_list_s *list,
        const void *sorted_data,
        size_t n,
        bool allow_duplicates
) {
    // corner case
    if (n == 0) return 0;

    size_t elem_size = list->collection.elem_size;
    const char *src = sorted_data;

    // track indices and number of inserted items
    size_t di = 0, si = 0, processed = 0;

    // search the list for insertion points
    while (di < list->collection.size) {
        const void *list_elm = list->cl->at(list, di);

        // compare the current list element with the first source element
        // if less, skip the list elements
        // if equal, skip the list elements and optionally the source elements
        {
            int d = cx_list_compare_wrapper(list_elm, src, list);
            if (d <= 0) {
                if (!allow_duplicates && d == 0) {
                    src += elem_size;
                    si++;
                    processed++; // we also count duplicates for the return value
                    while (si < n && cx_list_compare_wrapper(list_elm, src, list) == 0) {
                        src += elem_size;
                        si++;
                        processed++;
                    }
                    if (processed == n) {
                        return processed;
                    }
                }
                di++;
                continue;
            }
        }

        // determine the number of consecutive elements that can be inserted
        size_t ins = 1, skip = 0;
        const char *next = src;
        while (++si < n) {
            if (!allow_duplicates) {
                // skip duplicates within the source
                if (cx_list_compare_wrapper(next, next + elem_size, list) == 0) {
                    next += elem_size;
                    skip++;
                    continue;
                } else {
                    if (skip > 0) {
                        // if we had to skip something, we must wait for the next run
                        next += elem_size;
                        break;
                    }
                }
            }
            next += elem_size;
            // once we become larger than the list elem, break
            if (cx_list_compare_wrapper(list_elm, next, list) <= 0) {
                break;
            }
            // otherwise, we can insert one more
            ins++;
        }

        // insert the elements at location si
        if (ins == 1) {
            if (NULL == list->cl->insert_element(list, di, src)) {
                return processed; // LCOV_EXCL_LINE
            }
        } else {
            size_t r = list->cl->insert_array(list, di, src, ins);
            if (r < ins) {
                return processed + r;  // LCOV_EXCL_LINE
            }
        }
        processed += ins + skip;
        di += ins;

        // everything inserted?
        if (processed == n) {
            return processed;
        }
        src = next;
    }

    // insert remaining items
    if (si < n) {
        if (allow_duplicates) {
            processed += list->cl->insert_array(list, di, src, n - si);
        } else {
            const void *last = di == 0 ? NULL : list->cl->at(list, di - 1);
            for (; si < n; si++) {
                // skip duplicates within the source
                if (last == NULL || cx_list_compare_wrapper(last, src, list) != 0) {
                    if (NULL == list->cl->insert_element(list, di, src)) {
                        return processed; // LCOV_EXCL_LINE
                    }
                    last = src;
                    di++;
                }
                processed++;
                src += elem_size;
            }
        }
    }

    return processed;
}

size_t cx_list_default_insert_sorted(
        struct cx_list_s *list,
        const void *sorted_data,
        size_t n
) {
    return cx_list_default_insert_sorted_impl(list, sorted_data, n, true);
}

size_t cx_list_default_insert_unique(
        struct cx_list_s *list,
        const void *sorted_data,
        size_t n
) {
    return cx_list_default_insert_sorted_impl(list, sorted_data, n, false);
}

void cx_list_default_sort(struct cx_list_s *list) {
    size_t elem_size = list->collection.elem_size;
    size_t list_size = list->collection.size;
    void *tmp = cxMallocDefault(elem_size * list_size);
    if (tmp == NULL) abort(); // LCOV_EXCL_LINE

    // copy elements from source array
    char *loc = tmp;
    for (size_t i = 0; i < list_size; i++) {
        void *src = list->cl->at(list, i);
        memcpy(loc, src, elem_size);
        loc += elem_size;
    }

    // qsort
    cx_array_qsort_c(tmp, list_size, elem_size, cx_list_compare_wrapper, list);

    // copy elements back
    loc = tmp;
    for (size_t i = 0; i < list_size; i++) {
        void *dest = list->cl->at(list, i);
        memcpy(dest, loc, elem_size);
        loc += elem_size;
    }

    cxFreeDefault(tmp);
}

int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) {
    if (i == j) return 0;
    if (i >= list->collection.size) return 1;
    if (j >= list->collection.size) return 1;

    size_t elem_size = list->collection.elem_size;

    void *tmp = cxMallocDefault(elem_size);
    if (tmp == NULL) return 1; // LCOV_EXCL_LINE

    void *ip = list->cl->at(list, i);
    void *jp = list->cl->at(list, j);

    memcpy(tmp, ip, elem_size);
    memcpy(ip, jp, elem_size);
    memcpy(jp, tmp, elem_size);

    cxFreeDefault(tmp);

    return 0;
}

static int cx_list_cmpfunc2_safe_memcmp(const void *a, const void *b, void *c) {
    // it is not safe to store a pointer to the size in the list
    // because the entire list structure might get reallocated
    size_t elem_size = (size_t)(uintptr_t)c;
    return memcmp(a, b, elem_size);
}

void cx_list_init(
    struct cx_list_s *list,
    struct cx_list_class_s *cl,
    const struct cx_allocator_s *allocator,
    size_t elem_size
) {
    list->cl = cl;
    list->collection.allocator = allocator;
    list->collection.size = 0;
    list->collection.sorted = false; // should be set by the implementation
    if (elem_size > 0) {
        list->collection.elem_size = elem_size;
        list->collection.simple_cmp = NULL;
        list->collection.advanced_cmp = cx_list_cmpfunc2_safe_memcmp;
        list->collection.cmp_data = (void*)(uintptr_t)list->collection.elem_size;
        list->collection.store_pointer = false;
    } else {
        list->collection.elem_size = sizeof(void *);
        list->collection.simple_cmp = cx_cmp_ptr;
        list->collection.advanced_cmp = NULL;
        list->collection.cmp_data = NULL;
        list->collection.store_pointer = true;
    }
}

int cxListCompare(
        const CxList *list,
        const CxList *other
) {
    // check if we cannot use the list internal function
    bool cannot_optimize = false;

    // if one is storing pointers but the other is not
    cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;

    // check if the lists are incompatible or this list does not implement compare
    cx_compare_func list_cmp = (cx_compare_func) list->cl->compare;
    cx_compare_func other_cmp = (cx_compare_func) other->cl->compare;
    cannot_optimize |= list_cmp != other_cmp;
    cannot_optimize |= list_cmp == NULL;

    if (cannot_optimize) {
        // lists are definitely different - cannot use internal compare function
        if (list->collection.size == other->collection.size) {
            CxIterator left = cxListIterator(list);
            CxIterator right = cxListIterator(other);
            for (size_t i = 0; i < list->collection.size; i++) {
                void *leftValue = cxIteratorCurrent(left);
                void *rightValue = cxIteratorCurrent(right);
                // values are already unwrapped, invoke immediately
                int d = cx_invoke_compare_func(list, leftValue, rightValue);
                if (d != 0) {
                    return d;
                }
                cxIteratorNext(left);
                cxIteratorNext(right);
            }
            return 0;
        } else {
            return list->collection.size < other->collection.size ? -1 : 1;
        }
    } else {
        // lists are compatible
        return list->cl->compare(list, other);
    }
}

size_t cxListSize(const CxList *list) {
    return list->collection.size;
}

int cxListAdd(CxList *list, const void *elem) {
    list->collection.sorted = false;
    return list->cl->insert_element(list, list->collection.size, cx_ref(list, elem)) == NULL;
}

size_t cxListAddArray(CxList *list, const void *array, size_t n) {
    list->collection.sorted = false;
    return list->cl->insert_array(list, list->collection.size, array, n);
}

int cxListInsert(CxList *list, size_t index, const void *elem) {
    list->collection.sorted = false;
    return list->cl->insert_element(list, index, cx_ref(list, elem)) == NULL;
}

void *cxListEmplaceAt(CxList *list, size_t index) {
    list->collection.sorted = false;
    return list->cl->insert_element(list, index, NULL);
}

void *cxListEmplace(CxList *list) {
    list->collection.sorted = false;
    return list->cl->insert_element(list, list->collection.size, NULL);
}

static bool cx_list_emplace_iterator_valid(const void *it) {
    const CxIterator *iter = it;
    return iter->index < iter->elem_count;
}

CxIterator cxListEmplaceArrayAt(CxList *list, size_t index, size_t n) {
    list->collection.sorted = false;
    size_t c = list->cl->insert_array(list, index, NULL, n);
    CxIterator iter = list->cl->iterator(list, index, false);
    // tweak the fields of this iterator
    iter.elem_count = c;
    iter.index = 0;
    // replace the valid function to abort iteration when c is reached
    iter.base.valid = cx_list_emplace_iterator_valid;
    return iter;
}

CxIterator cxListEmplaceArray(CxList *list, size_t n) {
    return cxListEmplaceArrayAt(list, list->collection.size, n);
}

int cxListInsertSorted(CxList *list, const void *elem) {
    assert(cxCollectionSorted(list));
    list->collection.sorted = true;
    return list->cl->insert_sorted(list, cx_ref(list, elem), 1) == 0;
}

int cxListInsertUnique(CxList *list, const void *elem) {
    if (cxCollectionSorted(list)) {
        list->collection.sorted = true;
        return list->cl->insert_unique(list, cx_ref(list, elem), 1) == 0;
    } else {
        if (cxListContains(list, elem)) {
            return 0;
        } else {
            return cxListAdd(list, elem);
        }
    }
}

size_t cxListInsertArray(CxList *list, size_t index, const void *array, size_t n) {
    list->collection.sorted = false;
    return list->cl->insert_array(list, index, array, n);
}

size_t cxListInsertSortedArray(CxList *list, const void *array, size_t n) {
    assert(cxCollectionSorted(list));
    list->collection.sorted = true;
    return list->cl->insert_sorted(list, array, n);
}

size_t cxListInsertUniqueArray(CxList *list, const void *array, size_t n) {
    if (cxCollectionSorted(list)) {
        list->collection.sorted = true;
        return list->cl->insert_unique(list, array, n);
    } else {
        const char *source = array;
        for (size_t i = 0 ; i < n; i++) {
            // note: this also checks elements added in a previous iteration
            const void *data = cx_deref(list, source);
            if (!cxListContains(list, data)) {
                if (cxListAdd(list, data)) {
                    return i; // LCOV_EXCL_LINE
                }
            }
            source += list->collection.elem_size;
        }
        return n;
    }
}

int cxListInsertAfter(CxIterator *iter, const void *elem) {
    CxList* list = iter->src_handle;
    list->collection.sorted = false;
    return list->cl->insert_iter(iter, cx_ref(list, elem), 0);
}

int cxListInsertBefore(CxIterator *iter, const void *elem) {
    CxList* list = iter->src_handle;
    list->collection.sorted = false;
    return list->cl->insert_iter(iter, cx_ref(list, elem), 1);
}

int cxListRemove(CxList *list, size_t index) {
    return list->cl->remove(list, index, 1, NULL) == 0;
}

int cxListRemoveAndGet(CxList *list, size_t index, void *targetbuf) {
    return list->cl->remove(list, index, 1, targetbuf) == 0;
}

int cxListRemoveAndGetFirst(CxList *list, void *targetbuf) {
    return list->cl->remove(list, 0, 1, targetbuf) == 0;
}

int cxListRemoveAndGetLast(CxList *list, void *targetbuf) {
    // note: index may wrap - member function will catch that
    return list->cl->remove(list, list->collection.size - 1, 1, targetbuf) == 0;
}

size_t cxListRemoveArray(CxList *list, size_t index, size_t num) {
    return list->cl->remove(list, index, num, NULL);
}

size_t cxListRemoveArrayAndGet(CxList *list, size_t index, size_t num, void *targetbuf) {
    return list->cl->remove(list, index, num, targetbuf);
}

void cxListClear(CxList *list) {
    list->cl->clear(list);
    list->collection.sorted = true; // empty lists are always sorted
}

int cxListSwap(CxList *list, size_t i, size_t j) {
    list->collection.sorted = false;
    return list->cl->swap(list, i, j);
}

void *cxListAt(const CxList *list, size_t index) {
    void *result = list->cl->at(list, index);
    if (result == NULL) return NULL;
    return cx_deref(list, result);
}

void *cxListFirst(const CxList *list) {
    return cxListAt(list, 0);
}

void *cxListLast(const CxList *list) {
    return cxListAt(list, list->collection.size - 1);
}

int cxListSet(CxList *list, size_t index, const void *elem) {
    if (index >= list->collection.size) {
        return 1;
    }

    if (list->collection.store_pointer) {
        void **target = list->cl->at(list, index);
        *target = (void *)elem;
    } else {
        void *target = list->cl->at(list, index);
        memcpy(target, elem, list->collection.elem_size);
    }

    return 0;
}

static void *cx_pl_iter_current(const void *it) {
    const struct cx_iterator_s *iter = it;
    void **ptr = iter->base.current_impl(it);
    return ptr == NULL ? NULL : *ptr;
}

CX_INLINE CxIterator cx_pl_iter_wrap(const CxList *list, CxIterator iter) {
    if (cxCollectionStoresPointers(list)) {
        iter.base.current_impl = iter.base.current;
        iter.base.current = cx_pl_iter_current;
        return iter;
    } else {
        return iter;
    }
}

CxIterator cxListIteratorAt(const CxList *list, size_t index) {
    if (list == NULL) list = cxEmptyList;
    return cx_pl_iter_wrap(list, list->cl->iterator(list, index, false));
}

CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) {
    if (list == NULL) list = cxEmptyList;
    return cx_pl_iter_wrap(list, list->cl->iterator(list, index, true));
}

CxIterator cxListIterator(const CxList *list) {
    if (list == NULL) list = cxEmptyList;
    return cx_pl_iter_wrap(list, list->cl->iterator(list, 0, false));
}

CxIterator cxListBackwardsIterator(const CxList *list) {
    if (list == NULL) list = cxEmptyList;
    return cx_pl_iter_wrap(list, list->cl->iterator(list, list->collection.size - 1, true));
}

size_t cxListFind(const CxList *list, const void *elem) {
    return list->cl->find_remove((CxList*)list, cx_ref(list, elem), false);
}

bool cxListContains(const CxList* list, const void* elem) {
    return list->cl->find_remove((CxList*)list, cx_ref(list, elem), false) < list->collection.size;
}

bool cxListIndexValid(const CxList *list, size_t index) {
    return index < list->collection.size;
}

size_t cxListFindRemove(CxList *list, const void *elem) {
    return list->cl->find_remove(list, cx_ref(list, elem), true);
}

void cxListSort(CxList *list) {
    if (list->collection.sorted) return;
    list->cl->sort(list);
    list->collection.sorted = true;
}

void cxListReverse(CxList *list) {
    // still sorted, but not according to the cmp_func
    list->collection.sorted = false;
    list->cl->reverse(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_shallow_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_shallow_clone_func(list) cx_list_shallow_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);
                d = cx_list_compare_wrapper(sub_elem, min_elem, subtrahend);
            } 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 = cx_list_compare_wrapper(src_elem, other_elem, src);
            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 = cx_list_compare_wrapper(src_elem, other_elem, src);
            }
            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 cxListCloneShallow(CxList *dst, const CxList *src) {
    return cxListClone(dst, src, use_shallow_clone_func(src));
}

int cxListDifferenceShallow(CxList *dst, const CxList *minuend, const CxList *subtrahend) {
    return cxListDifference(dst, minuend, subtrahend, use_shallow_clone_func(minuend));
}

int cxListIntersectionShallow(CxList *dst, const CxList *src, const CxList *other) {
    return cxListIntersection(dst, src, other, use_shallow_clone_func(src));
}

int cxListUnionShallow(CxList *dst, const CxList *src, const CxList *other) {
    return cxListUnion(dst, src, other, use_shallow_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));
}