ucx: src/array_list.c@77efa5163ae5

     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_coppy_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         /* increase capacity linearly */

    72         cap += 16;

    74         /* perform reallocation */

    75         void *newmem = reallocator->realloc(

    76                 *target, cap, elem_size, reallocator

    77         );

    78         if (newmem == NULL) {

    79             return CX_ARRAY_COPY_REALLOC_FAILED;

    80         }

    82         /* repair src pointer, if necessary */

    83         if (repairsrc) {

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

    85         }

    87         /* store new pointer and capacity */

    88         *target = newmem;

    89         *capacity = cap;

    90     }

    92     /* determine target pointer */

    93     char *start = *target;

    94     start += index * elem_size;

    96     /* copy elements and set new size */

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

    98     *size = newsize;

   100     /* return successfully */

   101     return CX_ARRAY_COPY_SUCCESS;

   102 }

   104 /* HIGH LEVEL ARRAY LIST FUNCTIONS */

   106 typedef struct {

   107     struct cx_list_s base;

   108     void *data;

   109     struct cx_array_reallocator_s reallocator;

   110 } cx_array_list;

   112 static void *cx_arl_realloc(

   113         void *array,

   114         size_t capacity,

   115         size_t elem_size,

   116         struct cx_array_reallocator_s *alloc

   117 ) {

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

   119     CxAllocator const *al = alloc->ptr1;

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

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

   123 }

   125 static void cx_arl_destructor(struct cx_list_s *list) {

   126     cx_array_list *arl = (cx_array_list *) list;

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

   128 }

   130 static int cx_arl_add(

   131         struct cx_list_s *list,

   132         void const *elem

   133 ) {

   134     cx_array_list *arl = (cx_array_list *) list;

   135     return cx_array_copy(

   136             &arl->data,

   137             &list->size,

   138             &list->capacity,

   139             list->size,

   140             elem,

   141             list->itemsize,

   142             1,

   143             &arl->reallocator

   144     );

   145 }

   147 static int cx_arl_insert(

   148         struct cx_list_s *list,

   149         size_t index,

   150         void const *elem

   151 ) {

   152     if (index > list->size) {

   153         return 1;

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

   155         return cx_arl_add(list, elem);

   156     } else {

   157         cx_array_list *arl = (cx_array_list *) list;

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

   160         if (cx_array_copy(

   161                 &arl->data,

   162                 &list->size,

   163                 &list->capacity,

   164                 index + 1,

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

   166                 list->itemsize,

   167                 list->size - index,

   168                 &arl->reallocator

   169         )) {

   170             return 1;

   171         }

   173         /* place the element */

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

   175                elem, list->itemsize);

   177         return 0;

   178     }

   179 }

   181 static int cx_arl_insert_iter(

   182         struct cx_iterator_s *iter,

   183         void const *elem,

   184         int prepend

   185 ) {

   186     return 1;

   187 }

   189 static int cx_arl_remove(

   190         struct cx_list_s *list,

   191         size_t index

   192 ) {

   193     return 1;

   194 }

   196 static void *cx_arl_at(

   197         struct cx_list_s const *list,

   198         size_t index

   199 ) {

   200     if (index < list->size) {

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

   202         char *space = arl->data;

   203         return space + index * list->itemsize;

   204     } else {

   205         return NULL;

   206     }

   207 }

   209 static size_t cx_arl_find(

   210         struct cx_list_s const *list,

   211         void const *elem

   212 ) {

   213     return 0;

   214 }

   216 static void cx_arl_sort(struct cx_list_s *list) {

   218 }

   220 static int cx_arl_compare(

   221         struct cx_list_s const *list,

   222         struct cx_list_s const *other

   223 ) {

   225 }

   227 static void cx_arl_reverse(struct cx_list_s *list) {

   229 }

   231 static struct cx_iterator_s cx_arl_iterator(

   232         struct cx_list_s *list,

   233         size_t index

   234 ) {

   235     struct cx_iterator_s iter;

   237     return iter;

   238 }

   240 static cx_list_class cx_array_list_class = {

   241         cx_arl_destructor,

   242         cx_arl_add,

   243         cx_arl_insert,

   244         cx_arl_insert_iter,

   245         cx_arl_remove,

   246         cx_arl_at,

   247         cx_arl_find,

   248         cx_arl_sort,

   249         cx_arl_compare,

   250         cx_arl_reverse,

   251         cx_arl_iterator,

   252 };

   254 CxList *cxArrayListCreate(

   255         CxAllocator const *allocator,

   256         CxListComparator comparator,

   257         size_t item_size,

   258         size_t initial_capacity

   259 ) {

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

   261     if (list == NULL) return NULL;

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

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

   265         cxFree(allocator, list);

   266         return NULL;

   267     }

   269     list->base.cl = &cx_array_list_class;

   270     list->base.allocator = allocator;

   271     list->base.cmpfunc = comparator;

   272     list->base.itemsize = item_size;

   273     list->base.capacity = initial_capacity;

   275     /* configure the reallocator */

   276     list->reallocator.realloc = cx_arl_realloc;

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

   279     return (CxList *) list;

   280 }

Mercurial > hg > ucx / file revision

src/array_list.c@77efa5163ae5

src/array_list.c