ucx: src/list.c@35f06c5eeb0e

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    29 #include "cx/list.h"

    31 #include <string.h>

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

    35 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl;

    37 static int cx_pl_cmpfunc(

    38         void const *l,

    39         void const *r

    40 ) {

    41     void *const *lptr = l;

    42     void *const *rptr = r;

    43     void const *left = lptr == NULL ? NULL : *lptr;

    44     void const *right = rptr == NULL ? NULL : *rptr;

    45     return cx_pl_cmpfunc_impl(left, right);

    46 }

    48 static void cx_pl_hack_cmpfunc(struct cx_list_s const *list) {

    49     // cast away const - this is the hacky thing

    50     struct cx_list_s *l = (struct cx_list_s *) list;

    51     cx_pl_cmpfunc_impl = l->cmpfunc;

    52     l->cmpfunc = cx_pl_cmpfunc;

    53 }

    55 static void cx_pl_unhack_cmpfunc(struct cx_list_s const *list) {

    56     // cast away const - this is the hacky thing

    57     struct cx_list_s *l = (struct cx_list_s *) list;

    58     l->cmpfunc = cx_pl_cmpfunc_impl;

    59 }

    61 static void cx_pl_destructor(struct cx_list_s *list) {

    62     list->climpl->destructor(list);

    63 }

    65 static int cx_pl_insert_element(

    66         struct cx_list_s *list,

    67         size_t index,

    68         void const *element

    69 ) {

    70     return list->climpl->insert_element(list, index, &element);

    71 }

    73 static size_t cx_pl_insert_array(

    74         struct cx_list_s *list,

    75         size_t index,

    76         void const *array,

    77         size_t n

    78 ) {

    79     return list->climpl->insert_array(list, index, array, n);

    80 }

    82 static int cx_pl_insert_iter(

    83         struct cx_mut_iterator_s *iter,

    84         void const *elem,

    85         int prepend

    86 ) {

    87     struct cx_list_s *list = iter->src_handle;

    88     return list->climpl->insert_iter(iter, &elem, prepend);

    89 }

    91 static int cx_pl_remove(

    92         struct cx_list_s *list,

    93         size_t index

    94 ) {

    95     return list->climpl->remove(list, index);

    96 }

    98 static void cx_pl_clear(struct cx_list_s *list) {

    99     list->climpl->clear(list);

   100 }

   102 static int cx_pl_swap(

   103         struct cx_list_s *list,

   104         size_t i,

   105         size_t j

   106 ) {

   107     return list->climpl->swap(list, i, j);

   108 }

   110 static void *cx_pl_at(

   111         struct cx_list_s const *list,

   112         size_t index

   113 ) {

   114     void **ptr = list->climpl->at(list, index);

   115     return ptr == NULL ? NULL : *ptr;

   116 }

   118 static ssize_t cx_pl_find(

   119         struct cx_list_s const *list,

   120         void const *elem

   121 ) {

   122     cx_pl_hack_cmpfunc(list);

   123     ssize_t ret = list->climpl->find(list, &elem);

   124     cx_pl_unhack_cmpfunc(list);

   125     return ret;

   126 }

   128 static void cx_pl_sort(struct cx_list_s *list) {

   129     cx_pl_hack_cmpfunc(list);

   130     list->climpl->sort(list);

   131     cx_pl_unhack_cmpfunc(list);

   132 }

   134 static int cx_pl_compare(

   135         struct cx_list_s const *list,

   136         struct cx_list_s const *other

   137 ) {

   138     cx_pl_hack_cmpfunc(list);

   139     int ret = list->climpl->compare(list, other);

   140     cx_pl_unhack_cmpfunc(list);

   141     return ret;

   142 }

   144 static void cx_pl_reverse(struct cx_list_s *list) {

   145     list->climpl->reverse(list);

   146 }

   148 static void *cx_pl_iter_current(void const *it) {

   149     struct cx_iterator_s const *iter = it;

   150     void **ptr = iter->base.current_impl(it);

   151     return ptr == NULL ? NULL : *ptr;

   152 }

   154 static struct cx_iterator_s cx_pl_iterator(

   155         struct cx_list_s const *list,

   156         size_t index,

   157         bool backwards

   158 ) {

   159     struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);

   160     iter.base.current_impl = iter.base.current;

   161     iter.base.current = cx_pl_iter_current;

   162     return iter;

   163 }

   165 static cx_list_class cx_pointer_list_class = {

   166         cx_pl_destructor,

   167         cx_pl_insert_element,

   168         cx_pl_insert_array,

   169         cx_pl_insert_iter,

   170         cx_pl_remove,

   171         cx_pl_clear,

   172         cx_pl_swap,

   173         cx_pl_at,

   174         cx_pl_find,

   175         cx_pl_sort,

   176         cx_pl_compare,

   177         cx_pl_reverse,

   178         cx_pl_iterator,

   179 };

   181 void cxListStoreObjects(CxList *list) {

   182     list->store_pointer = false;

   183     if (list->climpl != NULL) {

   184         list->cl = list->climpl;

   185         list->climpl = NULL;

   186     }

   187 }

   189 void cxListStorePointers(CxList *list) {

   190     list->item_size = sizeof(void *);

   191     list->store_pointer = true;

   192     list->climpl = list->cl;

   193     list->cl = &cx_pointer_list_class;

   194 }

   196 // </editor-fold>

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

   200 static void cx_emptyl_noop(__attribute__((__unused__)) CxList *list) {

   201     // this is a noop, but MUST be implemented

   202 }

   204 static void *cx_emptyl_at(

   205         __attribute__((__unused__)) struct cx_list_s const *list,

   206         __attribute__((__unused__)) size_t index

   207 ) {

   208     return NULL;

   209 }

   211 static ssize_t cx_emptyl_find(

   212         __attribute__((__unused__)) struct cx_list_s const *list,

   213         __attribute__((__unused__)) void const *elem

   214 ) {

   215     return -1;

   216 }

   218 static int cx_emptyl_compare(

   219         __attribute__((__unused__)) struct cx_list_s const *list,

   220         struct cx_list_s const *other

   221 ) {

   222     if (other->size == 0) return 0;

   223     return -1;

   224 }

   226 static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) {

   227     return false;

   228 }

   230 static CxIterator cx_emptyl_iterator(

   231         struct cx_list_s const *list,

   232         size_t index,

   233         __attribute__((__unused__)) bool backwards

   234 ) {

   235     CxIterator iter = {0};

   236     iter.src_handle = list;

   237     iter.index = index;

   238     iter.base.valid = cx_emptyl_iter_valid;

   239     return iter;

   240 }

   242 static cx_list_class cx_empty_list_class = {

   243         cx_emptyl_noop,

   244         NULL,

   245         NULL,

   246         NULL,

   247         NULL,

   248         cx_emptyl_noop,

   249         NULL,

   250         cx_emptyl_at,

   251         cx_emptyl_find,

   252         cx_emptyl_noop,

   253         cx_emptyl_compare,

   254         cx_emptyl_noop,

   255         cx_emptyl_iterator,

   256 };

   258 CxList cx_empty_list = {

   259         NULL,

   260         NULL,

   261         0,

   262         0,

   263         NULL,

   264         NULL,

   265         NULL,

   266         false,

   267         &cx_empty_list_class,

   268         NULL

   269 };

   271 CxList *const cxEmptyList = &cx_empty_list;

   273 // </editor-fold>

   275 void cxListDestroy(CxList *list) {

   276     if (list->simple_destructor) {

   277         CxIterator iter = cxListIterator(list);

   278         cx_foreach(void*, elem, iter) {

   279             // already correctly resolved pointer - immediately invoke dtor

   280             list->simple_destructor(elem);

   281         }

   282     }

   283     if (list->advanced_destructor) {

   284         CxIterator iter = cxListIterator(list);

   285         cx_foreach(void*, elem, iter) {

   286             // already correctly resolved pointer - immediately invoke dtor

   287             list->advanced_destructor(list->destructor_data, elem);

   288         }

   289     }

   291     list->cl->destructor(list);

   292     if (list->allocator) {

   293         cxFree(list->allocator, list);

   294     }

   295 }

   297 int cxListCompare(

   298         CxList const *list,

   299         CxList const *other

   300 ) {

   301     if ((list->store_pointer ^ other->store_pointer) ||

   302         ((list->climpl == NULL) ^ (other->climpl != NULL)) ||

   303         ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) !=

   304          (other->climpl != NULL ? other->climpl->compare : other->cl->compare))) {

   305         // lists are definitely different - cannot use internal compare function

   306         if (list->size == other->size) {

   307             CxIterator left = cxListIterator(list);

   308             CxIterator right = cxListIterator(other);

   309             for (size_t i = 0; i < list->size; i++) {

   310                 void *leftValue = cxIteratorCurrent(left);

   311                 void *rightValue = cxIteratorCurrent(right);

   312                 int d = list->cmpfunc(leftValue, rightValue);

   313                 if (d != 0) {

   314                     return d;

   315                 }

   316                 cxIteratorNext(left);

   317                 cxIteratorNext(right);

   318             }

   319             return 0;

   320         } else {

   321             return list->size < other->size ? -1 : 1;

   322         }

   323     } else {

   324         // lists are compatible

   325         return list->cl->compare(list, other);

   326     }

   327 }

   329 CxMutIterator cxListMutIteratorAt(

   330         CxList *list,

   331         size_t index

   332 ) {

   333     CxIterator it = list->cl->iterator(list, index, false);

   334     it.base.mutating = true;

   336     // we know the iterators share the same memory layout

   337     CxMutIterator iter;

   338     memcpy(&iter, &it, sizeof(CxMutIterator));

   339     return iter;

   340 }

   342 CxMutIterator cxListMutBackwardsIteratorAt(

   343         CxList *list,

   344         size_t index

   345 ) {

   346     CxIterator it = list->cl->iterator(list, index, true);

   347     it.base.mutating = true;

   349     // we know the iterators share the same memory layout

   350     CxMutIterator iter;

   351     memcpy(&iter, &it, sizeof(CxMutIterator));

   352     return iter;

   353 }

Mercurial > hg > ucx / file revision

src/list.c@35f06c5eeb0e

src/list.c