universe@503: /*
universe@503:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@503:  *
universe@503:  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
universe@503:  *
universe@503:  * Redistribution and use in source and binary forms, with or without
universe@503:  * modification, are permitted provided that the following conditions are met:
universe@503:  *
universe@503:  *   1. Redistributions of source code must retain the above copyright
universe@503:  *      notice, this list of conditions and the following disclaimer.
universe@503:  *
universe@503:  *   2. Redistributions in binary form must reproduce the above copyright
universe@503:  *      notice, this list of conditions and the following disclaimer in the
universe@503:  *      documentation and/or other materials provided with the distribution.
universe@503:  *
universe@503:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@503:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@503:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@503:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@503:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@503:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@503:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@503:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@503:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@503:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@503:  * POSSIBILITY OF SUCH DAMAGE.
universe@503:  */
universe@503: 
universe@503: #include "cx/list.h"
universe@503: 
universe@640: #include <string.h>
universe@640: 
universe@641: // <editor-fold desc="Store Pointers Functionality">
universe@641: 
universe@677: static _Thread_local cx_compare_func cx_pl_cmpfunc_impl;
universe@641: 
universe@641: static int cx_pl_cmpfunc(
universe@641:         void const *l,
universe@641:         void const *r
universe@641: ) {
universe@641:     void *const *lptr = l;
universe@641:     void *const *rptr = r;
universe@641:     void const *left = lptr == NULL ? NULL : *lptr;
universe@641:     void const *right = rptr == NULL ? NULL : *rptr;
universe@641:     return cx_pl_cmpfunc_impl(left, right);
universe@641: }
universe@641: 
universe@641: static void cx_pl_hack_cmpfunc(struct cx_list_s const *list) {
universe@641:     // cast away const - this is the hacky thing
universe@641:     struct cx_list_s *l = (struct cx_list_s *) list;
universe@641:     cx_pl_cmpfunc_impl = l->cmpfunc;
universe@641:     l->cmpfunc = cx_pl_cmpfunc;
universe@641: }
universe@641: 
universe@641: static void cx_pl_unhack_cmpfunc(struct cx_list_s const *list) {
universe@641:     // cast away const - this is the hacky thing
universe@641:     struct cx_list_s *l = (struct cx_list_s *) list;
universe@641:     l->cmpfunc = cx_pl_cmpfunc_impl;
universe@641: }
universe@641: 
universe@641: static void cx_pl_destructor(struct cx_list_s *list) {
universe@641:     list->climpl->destructor(list);
universe@641: }
universe@641: 
universe@641: static int cx_pl_insert_element(
universe@641:         struct cx_list_s *list,
universe@641:         size_t index,
universe@641:         void const *element
universe@641: ) {
universe@641:     return list->climpl->insert_element(list, index, &element);
universe@641: }
universe@641: 
universe@641: static size_t cx_pl_insert_array(
universe@641:         struct cx_list_s *list,
universe@641:         size_t index,
universe@641:         void const *array,
universe@641:         size_t n
universe@641: ) {
universe@641:     return list->climpl->insert_array(list, index, array, n);
universe@641: }
universe@641: 
universe@641: static int cx_pl_insert_iter(
universe@641:         struct cx_mut_iterator_s *iter,
universe@641:         void const *elem,
universe@641:         int prepend
universe@641: ) {
universe@641:     struct cx_list_s *list = iter->src_handle;
universe@641:     return list->climpl->insert_iter(iter, &elem, prepend);
universe@641: }
universe@641: 
universe@641: static int cx_pl_remove(
universe@641:         struct cx_list_s *list,
universe@641:         size_t index
universe@641: ) {
universe@641:     return list->climpl->remove(list, index);
universe@641: }
universe@641: 
universe@664: static void cx_pl_clear(struct cx_list_s *list) {
universe@664:     list->climpl->clear(list);
universe@664: }
universe@664: 
universe@647: static int cx_pl_swap(
universe@647:         struct cx_list_s *list,
universe@647:         size_t i,
universe@647:         size_t j
universe@647: ) {
universe@647:     return list->climpl->swap(list, i, j);
universe@647: }
universe@647: 
universe@641: static void *cx_pl_at(
universe@641:         struct cx_list_s const *list,
universe@641:         size_t index
universe@641: ) {
universe@641:     void **ptr = list->climpl->at(list, index);
universe@641:     return ptr == NULL ? NULL : *ptr;
universe@641: }
universe@641: 
universe@699: static ssize_t cx_pl_find(
universe@641:         struct cx_list_s const *list,
universe@641:         void const *elem
universe@641: ) {
universe@641:     cx_pl_hack_cmpfunc(list);
universe@699:     ssize_t ret = list->climpl->find(list, &elem);
universe@641:     cx_pl_unhack_cmpfunc(list);
universe@641:     return ret;
universe@641: }
universe@641: 
universe@641: static void cx_pl_sort(struct cx_list_s *list) {
universe@641:     cx_pl_hack_cmpfunc(list);
universe@641:     list->climpl->sort(list);
universe@641:     cx_pl_unhack_cmpfunc(list);
universe@641: }
universe@641: 
universe@641: static int cx_pl_compare(
universe@641:         struct cx_list_s const *list,
universe@641:         struct cx_list_s const *other
universe@641: ) {
universe@641:     cx_pl_hack_cmpfunc(list);
universe@641:     int ret = list->climpl->compare(list, other);
universe@641:     cx_pl_unhack_cmpfunc(list);
universe@641:     return ret;
universe@641: }
universe@641: 
universe@641: static void cx_pl_reverse(struct cx_list_s *list) {
universe@641:     list->climpl->reverse(list);
universe@641: }
universe@641: 
universe@641: static void *cx_pl_iter_current(void const *it) {
universe@641:     struct cx_iterator_s const *iter = it;
universe@641:     void **ptr = iter->base.current_impl(it);
universe@641:     return ptr == NULL ? NULL : *ptr;
universe@641: }
universe@641: 
universe@641: static struct cx_iterator_s cx_pl_iterator(
universe@641:         struct cx_list_s const *list,
universe@655:         size_t index,
universe@655:         bool backwards
universe@641: ) {
universe@655:     struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
universe@641:     iter.base.current_impl = iter.base.current;
universe@641:     iter.base.current = cx_pl_iter_current;
universe@641:     return iter;
universe@641: }
universe@641: 
universe@641: static cx_list_class cx_pointer_list_class = {
universe@641:         cx_pl_destructor,
universe@641:         cx_pl_insert_element,
universe@641:         cx_pl_insert_array,
universe@641:         cx_pl_insert_iter,
universe@641:         cx_pl_remove,
universe@664:         cx_pl_clear,
universe@647:         cx_pl_swap,
universe@641:         cx_pl_at,
universe@641:         cx_pl_find,
universe@641:         cx_pl_sort,
universe@641:         cx_pl_compare,
universe@641:         cx_pl_reverse,
universe@641:         cx_pl_iterator,
universe@641: };
universe@641: 
universe@641: void cxListStoreObjects(CxList *list) {
universe@677:     list->store_pointer = false;
universe@641:     if (list->climpl != NULL) {
universe@641:         list->cl = list->climpl;
universe@641:         list->climpl = NULL;
universe@641:     }
universe@641: }
universe@641: 
universe@641: void cxListStorePointers(CxList *list) {
universe@677:     list->item_size = sizeof(void *);
universe@677:     list->store_pointer = true;
universe@641:     list->climpl = list->cl;
universe@641:     list->cl = &cx_pointer_list_class;
universe@641: }
universe@641: 
universe@641: // </editor-fold>
universe@641: 
universe@704: // <editor-fold desc="empty list implementation">
universe@704: 
universe@704: static void cx_emptyl_noop(__attribute__((__unused__)) CxList *list) {
universe@704:     // this is a noop, but MUST be implemented
universe@704: }
universe@704: 
universe@704: static void *cx_emptyl_at(
universe@704:         __attribute__((__unused__)) struct cx_list_s const *list,
universe@704:         __attribute__((__unused__)) size_t index
universe@704: ) {
universe@704:     return NULL;
universe@704: }
universe@704: 
universe@704: static ssize_t cx_emptyl_find(
universe@704:         __attribute__((__unused__)) struct cx_list_s const *list,
universe@704:         __attribute__((__unused__)) void const *elem
universe@704: ) {
universe@704:     return -1;
universe@704: }
universe@704: 
universe@704: static int cx_emptyl_compare(
universe@704:         __attribute__((__unused__)) struct cx_list_s const *list,
universe@704:         struct cx_list_s const *other
universe@704: ) {
universe@704:     if (other->size == 0) return 0;
universe@704:     return -1;
universe@704: }
universe@704: 
universe@704: static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) {
universe@704:     return false;
universe@704: }
universe@704: 
universe@704: static CxIterator cx_emptyl_iterator(
universe@704:         struct cx_list_s const *list,
universe@704:         size_t index,
universe@704:         __attribute__((__unused__)) bool backwards
universe@704: ) {
universe@704:     CxIterator iter = {0};
universe@704:     iter.src_handle = list;
universe@704:     iter.index = index;
universe@704:     iter.base.valid = cx_emptyl_iter_valid;
universe@704:     return iter;
universe@704: }
universe@704: 
universe@704: static cx_list_class cx_empty_list_class = {
universe@704:         cx_emptyl_noop,
universe@704:         NULL,
universe@704:         NULL,
universe@704:         NULL,
universe@704:         NULL,
universe@704:         cx_emptyl_noop,
universe@704:         NULL,
universe@704:         cx_emptyl_at,
universe@704:         cx_emptyl_find,
universe@704:         cx_emptyl_noop,
universe@704:         cx_emptyl_compare,
universe@704:         cx_emptyl_noop,
universe@704:         cx_emptyl_iterator,
universe@704: };
universe@704: 
universe@704: CxList cx_empty_list = {
universe@704:         NULL,
universe@704:         NULL,
universe@704:         0,
universe@704:         0,
universe@704:         NULL,
universe@704:         NULL,
universe@704:         NULL,
universe@704:         false,
universe@704:         &cx_empty_list_class,
universe@704:         NULL
universe@704: };
universe@704: 
universe@704: CxList *const cxEmptyList = &cx_empty_list;
universe@704: 
universe@704: // </editor-fold>
universe@704: 
universe@677: void cxListDestroy(CxList *list) {
universe@677:     if (list->simple_destructor) {
universe@677:         CxIterator iter = cxListIterator(list);
universe@677:         cx_foreach(void*, elem, iter) {
universe@677:             // already correctly resolved pointer - immediately invoke dtor
universe@677:             list->simple_destructor(elem);
universe@664:         }
universe@677:     }
universe@677:     if (list->advanced_destructor) {
universe@677:         CxIterator iter = cxListIterator(list);
universe@677:         cx_foreach(void*, elem, iter) {
universe@677:             // already correctly resolved pointer - immediately invoke dtor
universe@677:             list->advanced_destructor(list->destructor_data, elem);
universe@664:         }
universe@503:     }
universe@528: 
universe@524:     list->cl->destructor(list);
universe@704:     if (list->allocator) {
universe@704:         cxFree(list->allocator, list);
universe@704:     }
universe@503: }
universe@618: 
universe@618: int cxListCompare(
universe@618:         CxList const *list,
universe@618:         CxList const *other
universe@618: ) {
universe@680:     if ((list->store_pointer ^ other->store_pointer) ||
universe@680:         ((list->climpl == NULL) ^ (other->climpl != NULL)) ||
universe@680:         ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) !=
universe@680:          (other->climpl != NULL ? other->climpl->compare : other->cl->compare))) {
universe@680:         // lists are definitely different - cannot use internal compare function
universe@618:         if (list->size == other->size) {
universe@655:             CxIterator left = cxListIterator(list);
universe@655:             CxIterator right = cxListIterator(other);
universe@618:             for (size_t i = 0; i < list->size; i++) {
universe@630:                 void *leftValue = cxIteratorCurrent(left);
universe@630:                 void *rightValue = cxIteratorCurrent(right);
universe@618:                 int d = list->cmpfunc(leftValue, rightValue);
universe@618:                 if (d != 0) {
universe@618:                     return d;
universe@618:                 }
universe@630:                 cxIteratorNext(left);
universe@630:                 cxIteratorNext(right);
universe@618:             }
universe@618:             return 0;
universe@618:         } else {
universe@618:             return list->size < other->size ? -1 : 1;
universe@618:         }
universe@680:     } else {
universe@680:         // lists are compatible
universe@680:         return list->cl->compare(list, other);
universe@618:     }
universe@618: }
universe@640: 
universe@655: CxMutIterator cxListMutIteratorAt(
universe@640:         CxList *list,
universe@640:         size_t index
universe@640: ) {
universe@655:     CxIterator it = list->cl->iterator(list, index, false);
universe@640:     it.base.mutating = true;
universe@640: 
universe@640:     // we know the iterators share the same memory layout
universe@640:     CxMutIterator iter;
universe@640:     memcpy(&iter, &it, sizeof(CxMutIterator));
universe@640:     return iter;
universe@640: }
universe@655: 
universe@655: CxMutIterator cxListMutBackwardsIteratorAt(
universe@655:         CxList *list,
universe@655:         size_t index
universe@655: ) {
universe@655:     CxIterator it = list->cl->iterator(list, index, true);
universe@655:     it.base.mutating = true;
universe@655: 
universe@655:     // we know the iterators share the same memory layout
universe@655:     CxMutIterator iter;
universe@655:     memcpy(&iter, &it, sizeof(CxMutIterator));
universe@655:     return iter;
universe@655: }