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>

// <editor-fold desc="Store Pointers Functionality">

static _Thread_local cx_compare_func cx_pl_cmpfunc_impl;

static int cx_pl_cmpfunc(
        const void *l,
        const void *r
) {
    // l and r are guaranteed to be non-NULL pointing to the list's memory
    void *const *lptr = l;
    void *const *rptr = r;
    const void *left = *lptr;
    const void *right = *rptr;
    if (left == NULL) {
        // NULL is smaller than any value except NULL
        return right == NULL ? 0 : -1;
    } else if (right == NULL) {
        // any value is larger than NULL
        return 1;
    }
    return cx_pl_cmpfunc_impl(left, right);
}

static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) {
    // cast away const - this is the hacky thing
    struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
    cx_pl_cmpfunc_impl = l->cmpfunc;
    l->cmpfunc = cx_pl_cmpfunc;
}

static void cx_pl_unhack_cmpfunc(const struct cx_list_s *list) {
    // cast away const - this is the hacky thing
    struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
    l->cmpfunc = cx_pl_cmpfunc_impl;
}

static void cx_pl_destructor(struct cx_list_s *list) {
    list->climpl->deallocate(list);
}

static void *cx_pl_insert_element(
        struct cx_list_s *list,
        size_t index,
        const void *element
) {
    return list->climpl->insert_element(list, index, &element);
}

static size_t cx_pl_insert_array(
        struct cx_list_s *list,
        size_t index,
        const void *array,
        size_t n
) {
    return list->climpl->insert_array(list, index, array, n);
}

static size_t cx_pl_insert_sorted(
        struct cx_list_s *list,
        const void *array,
        size_t n
) {
    cx_pl_hack_cmpfunc(list);
    size_t result = list->climpl->insert_sorted(list, array, n);
    cx_pl_unhack_cmpfunc(list);
    return result;
}

static size_t cx_pl_insert_unique(
        struct cx_list_s *list,
        const void *array,
        size_t n
) {
    cx_pl_hack_cmpfunc(list);
    size_t result = list->climpl->insert_unique(list, array, n);
    cx_pl_unhack_cmpfunc(list);
    return result;
}

static int cx_pl_insert_iter(
        struct cx_iterator_s *iter,
        const void *elem,
        int prepend
) {
    struct cx_list_s *list = iter->src_handle;
    return list->climpl->insert_iter(iter, &elem, prepend);
}

static size_t cx_pl_remove(
        struct cx_list_s *list,
        size_t index,
        size_t num,
        void *targetbuf
) {
    return list->climpl->remove(list, index, num, targetbuf);
}

static void cx_pl_clear(struct cx_list_s *list) {
    list->climpl->clear(list);
}

static int cx_pl_swap(
        struct cx_list_s *list,
        size_t i,
        size_t j
) {
    return list->climpl->swap(list, i, j);
}

static void *cx_pl_at(
        const struct cx_list_s *list,
        size_t index
) {
    void **ptr = list->climpl->at(list, index);
    return ptr == NULL ? NULL : *ptr;
}

static size_t cx_pl_find_remove(
        struct cx_list_s *list,
        const void *elem,
        bool remove
) {
    cx_pl_hack_cmpfunc(list);
    size_t ret = list->climpl->find_remove(list, &elem, remove);
    cx_pl_unhack_cmpfunc(list);
    return ret;
}

static void cx_pl_sort(struct cx_list_s *list) {
    cx_pl_hack_cmpfunc(list);
    list->climpl->sort(list);
    cx_pl_unhack_cmpfunc(list);
}

static int cx_pl_compare(
        const struct cx_list_s *list,
        const struct cx_list_s *other
) {
    cx_pl_hack_cmpfunc(list);
    int ret = list->climpl->compare(list, other);
    cx_pl_unhack_cmpfunc(list);
    return ret;
}

static void cx_pl_reverse(struct cx_list_s *list) {
    list->climpl->reverse(list);
}

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;
}

static struct cx_iterator_s cx_pl_iterator(
        const struct cx_list_s *list,
        size_t index,
        bool backwards
) {
    struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
    iter.base.current_impl = iter.base.current;
    iter.base.current = cx_pl_iter_current;
    return iter;
}

static cx_list_class cx_pointer_list_class = {
        cx_pl_destructor,
        cx_pl_insert_element,
        cx_pl_insert_array,
        cx_pl_insert_sorted,
        cx_pl_insert_unique,
        cx_pl_insert_iter,
        cx_pl_remove,
        cx_pl_clear,
        cx_pl_swap,
        cx_pl_at,
        cx_pl_find_remove,
        cx_pl_sort,
        cx_pl_compare,
        cx_pl_reverse,
        cx_pl_iterator,
};
// </editor-fold>

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

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

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

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

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

static CxIterator cx_emptyl_iterator(
        const struct cx_list_s *list,
        size_t index,
        cx_attr_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,
        cx_emptyl_iterator,
};

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

CxList *const cxEmptyList = &cx_empty_list;

// </editor-fold>

#define invoke_list_func(name, list, ...) \
    ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \
    (list, __VA_ARGS__)

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 == invoke_list_func(
            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;
    cx_compare_func cmp = list->collection.cmpfunc;
    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 = invoke_list_func(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 = cmp(list_elm, src);
            if (d <= 0) {
                if (!allow_duplicates && d == 0) {
                    src += elem_size;
                    si++;
                    processed++; // we also count duplicates for the return value
                    while (si < n && cmp(list_elm, src) == 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 (cmp(next, next + elem_size) == 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 (cmp(list_elm, next) <= 0) {
                break;
            }
            // otherwise, we can insert one more
            ins++;
        }

        // insert the elements at location si
        if (ins == 1) {
            if (NULL == invoke_list_func(insert_element, list, di, src)) {
                return processed; // LCOV_EXCL_LINE
            }
        } else {
            size_t r = invoke_list_func(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 += invoke_list_func(insert_array, list, di, src, n - si);
        } else {
            const void *last = di == 0 ? NULL : invoke_list_func(at, list, di - 1);
            for (; si < n; si++) {
                // skip duplicates within the source
                if (last == NULL || cmp(last, src) != 0) {
                    if (NULL == invoke_list_func(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 = invoke_list_func(at, list, i);
        memcpy(loc, src, elem_size);
        loc += elem_size;
    }

    // qsort
    qsort(tmp, list_size, elem_size,
          list->collection.cmpfunc);

    // copy elements back
    loc = tmp;
    for (size_t i = 0; i < list_size; i++) {
        void *dest = invoke_list_func(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 = invoke_list_func(at, list, i);
    void *jp = invoke_list_func(at, list, j);

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

    cxFreeDefault(tmp);

    return 0;
}

void cx_list_init(
    struct cx_list_s *list,
    struct cx_list_class_s *cl,
    const struct cx_allocator_s *allocator,
    cx_compare_func comparator,
    size_t elem_size
) {
    list->cl = cl;
    list->collection.allocator = allocator;
    list->collection.cmpfunc = comparator;
    if (elem_size > 0) {
        list->collection.elem_size = elem_size;
    } else {
        list->collection.elem_size = sizeof(void *);
        if (list->collection.cmpfunc == NULL) {
            list->collection.cmpfunc = cx_cmp_ptr;
        }
        list->collection.store_pointer = true;
        list->climpl = list->cl;
        list->cl = &cx_pointer_list_class;
    }
}

int cxListCompare(
        const CxList *list,
        const CxList *other
) {
    bool cannot_optimize = false;

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

    // if one class is wrapped but the other is not
    cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL);

    // if the compare functions do not match or both are NULL
    if (!cannot_optimize) {
        cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
                                                      list->climpl->compare : list->cl->compare);
        cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
                                                       other->climpl->compare : 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 = list->cl->iterator(list, 0, false);
            CxIterator right = other->cl->iterator(other, 0, false);
            for (size_t i = 0; i < list->collection.size; i++) {
                void *leftValue = cxIteratorCurrent(left);
                void *rightValue = cxIteratorCurrent(right);
                int d = list->collection.cmpfunc(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, 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, 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;
    // if we are storing pointers, we want to return the pure pointers.
    // therefore, we must unwrap the "current" method
    if (list->collection.store_pointer) {
        iter.base.current = iter.base.current_impl;
    }
    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;
    const void *data = list->collection.store_pointer ? &elem : elem;
    return list->cl->insert_sorted(list, data, 1) == 0;
}

int cxListInsertUnique(CxList *list, const void *elem) {
    if (cxCollectionSorted(list)) {
        list->collection.sorted = true;
        const void *data = list->collection.store_pointer ? &elem : elem;
        return list->cl->insert_unique(list, data, 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 = list->collection.store_pointer ?
                    *((const void**)source) : 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 = (CxList*)iter->src_handle;
    list->collection.sorted = false;
    return list->cl->insert_iter(iter, elem, 0);
}

int cxListInsertBefore(CxIterator *iter, const void *elem) {
    CxList* list = (CxList*)iter->src_handle;
    list->collection.sorted = false;
    return list->cl->insert_iter(iter, 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) {
    return list->cl->at(list, index);
}

void *cxListFirst(const CxList *list) {
    return list->cl->at(list, 0);
}

void *cxListLast(const CxList *list) {
    return list->cl->at(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) {
        // For pointer collections, always use climpl
        void **target = list->climpl->at(list, index);
        *target = (void *)elem;
    } else {
        void *target = list->cl->at(list, index);
        memcpy(target, elem, list->collection.elem_size);
    }

    return 0;
}

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

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

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

CxIterator cxListBackwardsIterator(const CxList *list) {
    if (list == NULL) list = cxEmptyList;
    return 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, elem, false);
}

bool cxListContains(const CxList* list, const void* elem) {
    return list->cl->find_remove((CxList*)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, 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);
}