ucx: src/list.c@edb9f875b7f9

     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_remove(

   119         struct cx_list_s *list,

   120         void const *elem,

   121         bool remove

   122 ) {

   123     cx_pl_hack_cmpfunc(list);

   124     ssize_t ret = list->climpl->find_remove(list, &elem, remove);

   125     cx_pl_unhack_cmpfunc(list);

   126     return ret;

   127 }

   129 static void cx_pl_sort(struct cx_list_s *list) {

   130     cx_pl_hack_cmpfunc(list);

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

   132     cx_pl_unhack_cmpfunc(list);

   133 }

   135 static int cx_pl_compare(

   136         struct cx_list_s const *list,

   137         struct cx_list_s const *other

   138 ) {

   139     cx_pl_hack_cmpfunc(list);

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

   141     cx_pl_unhack_cmpfunc(list);

   142     return ret;

   143 }

   145 static void cx_pl_reverse(struct cx_list_s *list) {

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

   147 }

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

   150     struct cx_iterator_s const *iter = it;

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

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

   153 }

   155 static struct cx_iterator_s cx_pl_iterator(

   156         struct cx_list_s const *list,

   157         size_t index,

   158         bool backwards

   159 ) {

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

   161     iter.base.current_impl = iter.base.current;

   162     iter.base.current = cx_pl_iter_current;

   163     return iter;

   164 }

   166 static cx_list_class cx_pointer_list_class = {

   167         cx_pl_destructor,

   168         cx_pl_insert_element,

   169         cx_pl_insert_array,

   170         cx_pl_insert_iter,

   171         cx_pl_remove,

   172         cx_pl_clear,

   173         cx_pl_swap,

   174         cx_pl_at,

   175         cx_pl_find_remove,

   176         cx_pl_sort,

   177         cx_pl_compare,

   178         cx_pl_reverse,

   179         cx_pl_iterator,

   180 };

   182 void cxListStoreObjects(CxList *list) {

   183     list->store_pointer = false;

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

   185         list->cl = list->climpl;

   186         list->climpl = NULL;

   187     }

   188 }

   190 void cxListStorePointers(CxList *list) {

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

   192     list->store_pointer = true;

   193     list->climpl = list->cl;

   194     list->cl = &cx_pointer_list_class;

   195 }

   197 // </editor-fold>

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

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

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

   203 }

   205 static void *cx_emptyl_at(

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

   207         __attribute__((__unused__)) size_t index

   208 ) {

   209     return NULL;

   210 }

   212 static ssize_t cx_emptyl_find_remove(

   213         __attribute__((__unused__)) struct cx_list_s *list,

   214         __attribute__((__unused__)) void const *elem,

   215         __attribute__((__unused__)) bool remove

   216 ) {

   217     return -1;

   218 }

   220 static int cx_emptyl_compare(

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

   222         struct cx_list_s const *other

   223 ) {

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

   225     return -1;

   226 }

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

   229     return false;

   230 }

   232 static CxIterator cx_emptyl_iterator(

   233         struct cx_list_s const *list,

   234         size_t index,

   235         __attribute__((__unused__)) bool backwards

   236 ) {

   237     CxIterator iter = {0};

   238     iter.src_handle = list;

   239     iter.index = index;

   240     iter.base.valid = cx_emptyl_iter_valid;

   241     return iter;

   242 }

   244 static cx_list_class cx_empty_list_class = {

   245         cx_emptyl_noop,

   246         NULL,

   247         NULL,

   248         NULL,

   249         NULL,

   250         cx_emptyl_noop,

   251         NULL,

   252         cx_emptyl_at,

   253         cx_emptyl_find_remove,

   254         cx_emptyl_noop,

   255         cx_emptyl_compare,

   256         cx_emptyl_noop,

   257         cx_emptyl_iterator,

   258 };

   260 CxList cx_empty_list = {

   261         NULL,

   262         NULL,

   263         0,

   264         0,

   265         NULL,

   266         NULL,

   267         NULL,

   268         false,

   269         &cx_empty_list_class,

   270         NULL

   271 };

   273 CxList *const cxEmptyList = &cx_empty_list;

   275 // </editor-fold>

   277 void cxListDestroy(CxList *list) {

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

   279 }

   281 int cxListCompare(

   282         CxList const *list,

   283         CxList const *other

   284 ) {

   285     if (

   286         // if one is storing pointers but the other is not

   287         (list->store_pointer ^ other->store_pointer) ||

   289         // if one class is wrapped but the other is not

   290         ((list->climpl == NULL) ^ (other->climpl == NULL)) ||

   292         // if the resolved compare functions are not the same

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

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

   295     ) {

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

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

   298             CxIterator left = list->cl->iterator(list, 0, false);

   299             CxIterator right = other->cl->iterator(other, 0, false);

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

   301                 void *leftValue = cxIteratorCurrent(left);

   302                 void *rightValue = cxIteratorCurrent(right);

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

   304                 if (d != 0) {

   305                     return d;

   306                 }

   307                 cxIteratorNext(left);

   308                 cxIteratorNext(right);

   309             }

   310             return 0;

   311         } else {

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

   313         }

   314     } else {

   315         // lists are compatible

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

   317     }

   318 }

   320 CxMutIterator cxListMutIteratorAt(

   321         CxList *list,

   322         size_t index

   323 ) {

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

   325     it.base.mutating = true;

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

   328     CxMutIterator iter;

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

   330     return iter;

   331 }

   333 CxMutIterator cxListMutBackwardsIteratorAt(

   334         CxList *list,

   335         size_t index

   336 ) {

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

   338     it.base.mutating = true;

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

   341     CxMutIterator iter;

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

   343     return iter;

   344 }

Mercurial > hg > ucx / file revision

src/list.c@edb9f875b7f9

src/list.c