ucx: src/array_list.c@254cc61c71a0

     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 newsize = index + elem_count;

    56     bool needrealloc = newsize > cap;

    58     /* reallocate if possible */

    59     if (needrealloc) {

    60         /* a reallocator and a capacity variable must be available */

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

    62             return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED;

    63         }

    65         /* check, if we need to repair the src pointer */

    66         uintptr_t targetaddr = (uintptr_t) *target;

    67         uintptr_t srcaddr = (uintptr_t) src;

    68         bool repairsrc = targetaddr <= srcaddr

    69                          && srcaddr < targetaddr + cap * elem_size;

    71         /* calculate new capacity (next number divisible by 16) */

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

    73         assert(cap > newsize);

    75         /* perform reallocation */

    76         void *newmem = reallocator->realloc(

    77                 *target, cap, elem_size, reallocator

    78         );

    79         if (newmem == NULL) {

    80             return CX_ARRAY_COPY_REALLOC_FAILED;

    81         }

    83         /* repair src pointer, if necessary */

    84         if (repairsrc) {

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

    86         }

    88         /* store new pointer and capacity */

    89         *target = newmem;

    90         *capacity = cap;

    91     }

    93     /* determine target pointer */

    94     char *start = *target;

    95     start += index * elem_size;

    97     /* copy elements and set new size */

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

    99     *size = newsize;

   101     /* return successfully */

   102     return CX_ARRAY_COPY_SUCCESS;

   103 }

   105 #define CX_ARRAY_SWAP_SBO_SIZE 512

   107 void cx_array_swap(

   108         void *arr,

   109         size_t elem_size,

   110         size_t idx1,

   111         size_t idx2

   112 ) {

   113     /* short circuit */

   114     if (idx1 == idx2) return;

   116     char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];

   117     void *tmp;

   119     /* decide if we can use the local buffer */

   120     if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {

   121         tmp = malloc(elem_size);

   122         /* we don't want to enforce error handling */

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

   124     } else {

   125         tmp = sbo_mem;

   126     }

   128     /* calculate memory locations */

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

   130     left += idx1 * elem_size;

   131     right += idx2 * elem_size;

   133     /* three-way swap */

   134     memcpy(tmp, left, elem_size);

   135     memcpy(left, right, elem_size);

   136     memcpy(right, tmp, elem_size);

   138     /* free dynamic memory, if it was needed */

   139     if (tmp != sbo_mem) {

   140         free(tmp);

   141     }

   142 }

   144 /* HIGH LEVEL ARRAY LIST FUNCTIONS */

   146 typedef struct {

   147     struct cx_list_s base;

   148     void *data;

   149     struct cx_array_reallocator_s reallocator;

   150 } cx_array_list;

   152 static void *cx_arl_realloc(

   153         void *array,

   154         size_t capacity,

   155         size_t elem_size,

   156         struct cx_array_reallocator_s *alloc

   157 ) {

   158     /* retrieve the pointer to the list allocator */

   159     CxAllocator const *al = alloc->ptr1;

   161     /* use the list allocator to reallocate the memory */

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

   163 }

   165 static void cx_arl_destructor(struct cx_list_s *list) {

   166     cx_array_list *arl = (cx_array_list *) list;

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

   168 }

   170 static int cx_arl_add(

   171         struct cx_list_s *list,

   172         void const *elem

   173 ) {

   174     cx_array_list *arl = (cx_array_list *) list;

   175     return cx_array_copy(

   176             &arl->data,

   177             &list->size,

   178             &list->capacity,

   179             list->size,

   180             elem,

   181             list->itemsize,

   182             1,

   183             &arl->reallocator

   184     );

   185 }

   187 static int cx_arl_insert(

   188         struct cx_list_s *list,

   189         size_t index,

   190         void const *elem

   191 ) {

   192     if (index > list->size) {

   193         return 1;

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

   195         return cx_arl_add(list, elem);

   196     } else {

   197         cx_array_list *arl = (cx_array_list *) list;

   199         /* move elements starting at index to the right */

   200         if (cx_array_copy(

   201                 &arl->data,

   202                 &list->size,

   203                 &list->capacity,

   204                 index + 1,

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

   206                 list->itemsize,

   207                 list->size - index,

   208                 &arl->reallocator

   209         )) {

   210             return 1;

   211         }

   213         /* place the element */

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

   215                elem, list->itemsize);

   217         return 0;

   218     }

   219 }

   221 static int cx_arl_insert_iter(

   222         struct cx_iterator_s *iter,

   223         void const *elem,

   224         int prepend

   225 ) {

   226     struct cx_list_s *list = iter->src_handle;

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

   228         int result = cx_arl_insert(

   229                 list,

   230                 iter->index + 1 - prepend,

   231                 elem

   232         );

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

   234             iter->index++;

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

   236         }

   237         return result;

   238     } else {

   239         int result = cx_arl_add(list, elem);

   240         iter->index = list->size;

   241         return result;

   242     }

   243 }

   245 static int cx_arl_remove(

   246         struct cx_list_s *list,

   247         size_t index

   248 ) {

   249     /* out-of-bounds check */

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

   251         return 1;

   252     }

   254     /* short-circuit removal of last element */

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

   256         list->size--;

   257         return 0;

   258     }

   260     /* just move the elements starting at index to the left */

   261     cx_array_list *arl = (cx_array_list *) list;

   262     int result = cx_array_copy(

   263             &arl->data,

   264             &list->size,

   265             &list->capacity,

   266             index,

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

   268             list->itemsize,

   269             list->size - index - 1,

   270             &arl->reallocator

   271     );

   272     if (result == 0) {

   273         /* decrease the size */

   274         list->size--;

   275     }

   276     return result;

   277 }

   279 static void *cx_arl_at(

   280         struct cx_list_s const *list,

   281         size_t index

   282 ) {

   283     if (index < list->size) {

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

   285         char *space = arl->data;

   286         return space + index * list->itemsize;

   287     } else {

   288         return NULL;

   289     }

   290 }

   292 static size_t cx_arl_find(

   293         struct cx_list_s const *list,

   294         void const *elem

   295 ) {

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

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

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

   300             return i;

   301         }

   302         cur += list->itemsize;

   303     }

   305     return list->size;

   306 }

   308 static void cx_arl_sort(struct cx_list_s *list) {

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

   310           list->size,

   311           list->itemsize,

   312           list->cmpfunc

   313     );

   314 }

   316 static int cx_arl_compare(

   317         struct cx_list_s const *list,

   318         struct cx_list_s const *other

   319 ) {

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

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

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

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

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

   325             if (d != 0) {

   326                 return d;

   327             }

   328             left += list->itemsize;

   329             right += other->itemsize;

   330         }

   331         return 0;

   332     } else {

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

   334     }

   335 }

   337 static void cx_arl_reverse(struct cx_list_s *list) {

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

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

   340     size_t half = list->size / 2;

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

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

   343     }

   344 }

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

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

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

   349 }

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

   352     return iter->elem_handle;

   353 }

   355 static void cx_arl_iter_next(struct cx_iterator_s *iter) {

   356     if (iter->remove) {

   357         iter->remove = false;

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

   359     } else {

   360         iter->index++;

   361         iter->elem_handle =

   362                 ((char *) iter->elem_handle)

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

   364     }

   365 }

   367 static struct cx_iterator_s cx_arl_iterator(

   368         struct cx_list_s *list,

   369         size_t index

   370 ) {

   371     struct cx_iterator_s iter;

   373     iter.index = index;

   374     iter.src_handle = list;

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

   376     iter.valid = cx_arl_iter_valid;

   377     iter.current = cx_arl_iter_current;

   378     iter.next = cx_arl_iter_next;

   379     iter.remove = false;

   381     return iter;

   382 }

   384 static cx_list_class cx_array_list_class = {

   385         cx_arl_destructor,

   386         cx_arl_add,

   387         cx_arl_insert,

   388         cx_arl_insert_iter,

   389         cx_arl_remove,

   390         cx_arl_at,

   391         cx_arl_find,

   392         cx_arl_sort,

   393         cx_arl_compare,

   394         cx_arl_reverse,

   395         cx_arl_iterator,

   396 };

   398 CxList *cxArrayListCreate(

   399         CxAllocator const *allocator,

   400         CxListComparator comparator,

   401         size_t item_size,

   402         size_t initial_capacity

   403 ) {

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

   405     if (list == NULL) return NULL;

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

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

   409         cxFree(allocator, list);

   410         return NULL;

   411     }

   413     list->base.cl = &cx_array_list_class;

   414     list->base.allocator = allocator;

   415     list->base.cmpfunc = comparator;

   416     list->base.itemsize = item_size;

   417     list->base.capacity = initial_capacity;

   419     /* configure the reallocator */

   420     list->reallocator.realloc = cx_arl_realloc;

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

   423     return (CxList *) list;

   424 }

Mercurial > hg > ucx / file revision

src/array_list.c@254cc61c71a0

src/array_list.c