ucx: src/array_list.c@6c81ee4f11ad

     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/array_list.h"

    30 #include <assert.h>

    31 #include <string.h>

    32 #include <stdint.h>

    34 // LOW LEVEL ARRAY LIST FUNCTIONS

    36 enum cx_array_copy_result cx_array_copy(

    37         void **target,

    38         size_t *size,

    39         size_t *capacity,

    40         size_t index,

    41         void const *src,

    42         size_t elem_size,

    43         size_t elem_count,

    44         struct cx_array_reallocator_s *reallocator

    45 ) {

    46     // assert pointers

    47     assert(target != NULL);

    48     assert(size != NULL);

    49     assert(src != NULL);

    51     // determine capacity

    52     size_t cap = capacity == NULL ? *size : *capacity;

    54     // check if resize is required

    55     size_t minsize = index + elem_count;

    56     size_t newsize = *size < minsize ? minsize : *size;

    57     bool needrealloc = newsize > cap;

    59     // reallocate if possible

    60     if (needrealloc) {

    61         // a reallocator and a capacity variable must be available

    62         if (reallocator == NULL || capacity == NULL) {

    63             return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED;

    64         }

    66         // check, if we need to repair the src pointer

    67         uintptr_t targetaddr = (uintptr_t) *target;

    68         uintptr_t srcaddr = (uintptr_t) src;

    69         bool repairsrc = targetaddr <= srcaddr

    70                          && srcaddr < targetaddr + cap * elem_size;

    72         // calculate new capacity (next number divisible by 16)

    73         cap = newsize - (newsize % 16) + 16;

    74         assert(cap > newsize);

    76         // perform reallocation

    77         void *newmem = reallocator->realloc(

    78                 *target, cap, elem_size, reallocator

    79         );

    80         if (newmem == NULL) {

    81             return CX_ARRAY_COPY_REALLOC_FAILED;

    82         }

    84         // repair src pointer, if necessary

    85         if (repairsrc) {

    86             src = ((char *) newmem) + (srcaddr - targetaddr);

    87         }

    89         // store new pointer and capacity

    90         *target = newmem;

    91         *capacity = cap;

    92     }

    94     // determine target pointer

    95     char *start = *target;

    96     start += index * elem_size;

    98     // copy elements and set new size

    99     memmove(start, src, elem_count * elem_size);

   100     *size = newsize;

   102     // return successfully

   103     return CX_ARRAY_COPY_SUCCESS;

   104 }

   106 #define CX_ARRAY_SWAP_SBO_SIZE 512

   108 void cx_array_swap(

   109         void *arr,

   110         size_t elem_size,

   111         size_t idx1,

   112         size_t idx2

   113 ) {

   114     // short circuit

   115     if (idx1 == idx2) return;

   117     char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];

   118     void *tmp;

   120     // decide if we can use the local buffer

   121     if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {

   122         tmp = malloc(elem_size);

   123         // we don't want to enforce error handling

   124         if (tmp == NULL) abort();

   125     } else {

   126         tmp = sbo_mem;

   127     }

   129     // calculate memory locations

   130     char *left = arr, *right = arr;

   131     left += idx1 * elem_size;

   132     right += idx2 * elem_size;

   134     // three-way swap

   135     memcpy(tmp, left, elem_size);

   136     memcpy(left, right, elem_size);

   137     memcpy(right, tmp, elem_size);

   139     // free dynamic memory, if it was needed

   140     if (tmp != sbo_mem) {

   141         free(tmp);

   142     }

   143 }

   145 // HIGH LEVEL ARRAY LIST FUNCTIONS

   147 typedef struct {

   148     struct cx_list_s base;

   149     void *data;

   150     struct cx_array_reallocator_s reallocator;

   151 } cx_array_list;

   153 static void *cx_arl_realloc(

   154         void *array,

   155         size_t capacity,

   156         size_t elem_size,

   157         struct cx_array_reallocator_s *alloc

   158 ) {

   159     // retrieve the pointer to the list allocator

   160     CxAllocator const *al = alloc->ptr1;

   162     // use the list allocator to reallocate the memory

   163     return cxRealloc(al, array, capacity * elem_size);

   164 }

   166 static void cx_arl_destructor(struct cx_list_s *list) {

   167     cx_array_list *arl = (cx_array_list *) list;

   168     cxFree(list->allocator, arl->data);

   169 }

   171 static int cx_arl_add(

   172         struct cx_list_s *list,

   173         void const *elem

   174 ) {

   175     cx_array_list *arl = (cx_array_list *) list;

   176     return cx_array_copy(

   177             &arl->data,

   178             &list->size,

   179             &list->capacity,

   180             list->size,

   181             elem,

   182             list->itemsize,

   183             1,

   184             &arl->reallocator

   185     );

   186 }

   188 static size_t cx_arl_add_array(

   189         struct cx_list_s *list,

   190         void const *array,

   191         size_t n

   192 ) {

   193     cx_array_list *arl = (cx_array_list *) list;

   194     if (CX_ARRAY_COPY_SUCCESS == cx_array_copy(

   195             &arl->data,

   196             &list->size,

   197             &list->capacity,

   198             list->size,

   199             array,

   200             list->itemsize,

   201             n,

   202             &arl->reallocator

   203     )) {

   204         return n;

   205     } else {

   206         // array list implementation is "all or nothing"

   207         return 0;

   208     }

   209 }

   211 static int cx_arl_insert(

   212         struct cx_list_s *list,

   213         size_t index,

   214         void const *elem

   215 ) {

   216     if (index > list->size) {

   217         return 1;

   218     } else if (index == list->size) {

   219         return cx_arl_add(list, elem);

   220     } else {

   221         cx_array_list *arl = (cx_array_list *) list;

   223         // move elements starting at index to the right

   224         if (cx_array_copy(

   225                 &arl->data,

   226                 &list->size,

   227                 &list->capacity,

   228                 index + 1,

   229                 ((char *) arl->data) + index * list->itemsize,

   230                 list->itemsize,

   231                 list->size - index,

   232                 &arl->reallocator

   233         )) {

   234             return 1;

   235         }

   237         // place the element

   238         memcpy(((char *) arl->data) + index * list->itemsize,

   239                elem, list->itemsize);

   241         return 0;

   242     }

   243 }

   245 static int cx_arl_insert_iter(

   246         struct cx_iterator_s *iter,

   247         void const *elem,

   248         int prepend

   249 ) {

   250     struct cx_list_s *list = iter->src_handle;

   251     if (iter->index < list->size) {

   252         int result = cx_arl_insert(

   253                 list,

   254                 iter->index + 1 - prepend,

   255                 elem

   256         );

   257         if (result == 0 && prepend != 0) {

   258             iter->index++;

   259             iter->elem_handle = ((char *) iter->elem_handle) + list->itemsize;

   260         }

   261         return result;

   262     } else {

   263         int result = cx_arl_add(list, elem);

   264         iter->index = list->size;

   265         return result;

   266     }

   267 }

   269 static int cx_arl_remove(

   270         struct cx_list_s *list,

   271         size_t index

   272 ) {

   273     // out-of-bounds check

   274     if (index >= list->size) {

   275         return 1;

   276     }

   278     // short-circuit removal of last element

   279     if (index == list->size - 1) {

   280         list->size--;

   281         return 0;

   282     }

   284     // just move the elements starting at index to the left

   285     cx_array_list *arl = (cx_array_list *) list;

   286     int result = cx_array_copy(

   287             &arl->data,

   288             &list->size,

   289             &list->capacity,

   290             index,

   291             ((char *) arl->data) + (index + 1) * list->itemsize,

   292             list->itemsize,

   293             list->size - index - 1,

   294             &arl->reallocator

   295     );

   296     if (result == 0) {

   297         // decrease the size

   298         list->size--;

   299     }

   300     return result;

   301 }

   303 static void *cx_arl_at(

   304         struct cx_list_s const *list,

   305         size_t index

   306 ) {

   307     if (index < list->size) {

   308         cx_array_list const *arl = (cx_array_list const *) list;

   309         char *space = arl->data;

   310         return space + index * list->itemsize;

   311     } else {

   312         return NULL;

   313     }

   314 }

   316 static size_t cx_arl_find(

   317         struct cx_list_s const *list,

   318         void const *elem

   319 ) {

   320     char *cur = ((cx_array_list const *) list)->data;

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

   323         if (0 == list->cmpfunc(elem, cur)) {

   324             return i;

   325         }

   326         cur += list->itemsize;

   327     }

   329     return list->size;

   330 }

   332 static void cx_arl_sort(struct cx_list_s *list) {

   333     qsort(((cx_array_list *) list)->data,

   334           list->size,

   335           list->itemsize,

   336           list->cmpfunc

   337     );

   338 }

   340 static int cx_arl_compare(

   341         struct cx_list_s const *list,

   342         struct cx_list_s const *other

   343 ) {

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

   345         char const *left = ((cx_array_list const *) list)->data;

   346         char const *right = ((cx_array_list const *) other)->data;

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

   348             int d = list->cmpfunc(left, right);

   349             if (d != 0) {

   350                 return d;

   351             }

   352             left += list->itemsize;

   353             right += other->itemsize;

   354         }

   355         return 0;

   356     } else {

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

   358     }

   359 }

   361 static void cx_arl_reverse(struct cx_list_s *list) {

   362     if (list->size < 2) return;

   363     void *data = ((cx_array_list const *) list)->data;

   364     size_t half = list->size / 2;

   365     for (size_t i = 0; i < half; i++) {

   366         cx_array_swap(data, list->itemsize, i, list->size - 1 - i);

   367     }

   368 }

   370 static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) {

   371     struct cx_list_s const *list = iter->src_handle;

   372     return iter->index < list->size;

   373 }

   375 static void *cx_arl_iter_current(struct cx_iterator_s const *iter) {

   376     return iter->elem_handle;

   377 }

   379 static void cx_arl_iter_next(struct cx_iterator_s *iter) {

   380     if (iter->remove) {

   381         iter->remove = false;

   382         cx_arl_remove(iter->src_handle, iter->index);

   383     } else {

   384         iter->index++;

   385         iter->elem_handle =

   386                 ((char *) iter->elem_handle)

   387                 + ((struct cx_list_s const *) iter->src_handle)->itemsize;

   388     }

   389 }

   391 static struct cx_iterator_s cx_arl_iterator(

   392         struct cx_list_s *list,

   393         size_t index

   394 ) {

   395     struct cx_iterator_s iter;

   397     iter.index = index;

   398     iter.src_handle = list;

   399     iter.elem_handle = cx_arl_at(list, index);

   400     iter.valid = cx_arl_iter_valid;

   401     iter.current = cx_arl_iter_current;

   402     iter.next = cx_arl_iter_next;

   403     iter.remove = false;

   405     return iter;

   406 }

   408 static cx_list_class cx_array_list_class = {

   409         cx_arl_destructor,

   410         cx_arl_add,

   411         cx_arl_add_array,

   412         cx_arl_insert,

   413         cx_arl_insert_iter,

   414         cx_arl_remove,

   415         cx_arl_at,

   416         cx_arl_find,

   417         cx_arl_sort,

   418         cx_arl_compare,

   419         cx_arl_reverse,

   420         cx_arl_iterator,

   421 };

   423 CxList *cxArrayListCreate(

   424         CxAllocator const *allocator,

   425         CxListComparator comparator,

   426         size_t item_size,

   427         size_t initial_capacity

   428 ) {

   429     cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));

   430     if (list == NULL) return NULL;

   432     list->data = cxCalloc(allocator, initial_capacity, item_size);

   433     if (list->data == NULL) {

   434         cxFree(allocator, list);

   435         return NULL;

   436     }

   438     list->base.cl = &cx_array_list_class;

   439     list->base.allocator = allocator;

   440     list->base.cmpfunc = comparator;

   441     list->base.itemsize = item_size;

   442     list->base.capacity = initial_capacity;

   444     // configure the reallocator

   445     list->reallocator.realloc = cx_arl_realloc;

   446     list->reallocator.ptr1 = (void *) allocator;

   448     return (CxList *) list;

   449 }

Mercurial > hg > ucx / file revision

src/array_list.c@6c81ee4f11ad

src/array_list.c