ucx: src/array.c@f695ae118460

     1 /*

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

     3  *

     4  * Copyright 2019 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 "ucx/array.h"

    30 #include "ucx/utils.h"

    32 #include <string.h>

    34 UcxArray ucx_array_new(size_t capacity, size_t elemsize) {

    35     return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());

    36 }

    38 UcxArray ucx_array_new_a(size_t capacity, size_t elemsize,

    39         UcxAllocator* allocator) {

    40     UcxArray array;

    42     array.allocator = allocator;

    43     array.elemsize = elemsize;

    44     array.size = 0;

    45     array.data = alcalloc(allocator, capacity, elemsize);

    47     if (array.data) {

    48         array.capacity = capacity;

    49     } else {

    50         array.capacity = 0;

    51     }

    53     return array;

    54 }

    56 UcxArray ucx_array_clone(UcxArray array) {

    57     UcxArray clone;

    59     clone.allocator = array.allocator;

    60     clone.elemsize = array.elemsize;

    61     clone.size = array.size;

    62     clone.data = alcalloc(array.allocator, array.capacity, array.elemsize);

    64     if (clone.data) {

    65         clone.capacity = array.capacity;

    66         memcpy(clone.data, array.data, array.size*array.elemsize);

    67     } else {

    68         clone.capacity = clone.size = 0;

    69     }

    71     return clone;

    72 }

    74 int ucx_array_equals(UcxArray array1, UcxArray array2,

    75         cmp_func cmpfnc, void* data) {

    77     if (array1.size != array2.size || array1.elemsize != array2.elemsize) {

    78         return 0;

    79     } else {

    80         if (array1.size == 0)

    81             return 1;

    83         if (cmpfnc == NULL) {

    84             cmpfnc = ucx_cmp_mem;

    85             data = &array1.elemsize;

    86         }

    88         for (size_t i = 0 ; i < array1.size ; i++) {

    89             int r = cmpfnc(

    90                     ucx_array_at(array1, i),

    91                     ucx_array_at(array2, i),

    92                     data);

    93             if (r != 0)

    94                 return 0;

    95         }

    96         return 1;

    97     }

    98 }

   100 void ucx_array_free(UcxArray *array) {

   101     alfree(array->allocator, array->data);

   102     array->data = NULL;

   103     array->capacity = array->size = 0;

   104 }

   106 int ucx_array_append(UcxArray *array, void *data) {

   107     if (array->size == array->capacity) {

   108         if (ucx_array_reserve(array, array->capacity*2)) {

   109             return 1;

   110         }

   111     }

   113     void* dest = ucx_array_at(*array, array->size++);

   114     if (data) {

   115         memcpy(dest, data, array->elemsize);

   116     } else {

   117         memset(dest, 0, array->elemsize);

   118     }

   120     return 0;

   121 }

   123 int ucx_array_prepend(UcxArray *array, void *data) {

   124     if (array->size == array->capacity) {

   125         if (ucx_array_reserve(array, array->capacity*2)) {

   126             return 1;

   127         }

   128     }

   130     array->size++;

   132     if (array->size > 1) {

   133         void *dest = ucx_array_at(*array,1);

   134         memmove(dest, array->data, array->elemsize*array->size);

   135     }

   137     if (data) {

   138         memcpy(array->data, data, array->elemsize);

   139     } else {

   140         memset(array->data, 0, array->elemsize);

   141     }

   143     return 0;

   144 }

   146 int ucx_array_set(UcxArray *array, size_t index, void *data) {

   147     if (index >= array->size) {

   148         if (ucx_array_reserve(array, index+1)) {

   149             return 1;

   150         }

   151         array->size = index+1;

   152     }

   154     void *dest = ucx_array_at(*array, index);

   155     if (data) {

   156         memcpy(dest, data, array->elemsize);

   157     } else {

   158         memset(dest, 0, array->elemsize);

   159     }

   161     return 0;

   162 }

   164 int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {

   166     if (array1->elemsize != array2->elemsize)

   167         return 1;

   169     size_t capacity = array1->capacity+array2->capacity;

   171     if (array1->capacity < capacity) {

   172         if (ucx_array_reserve(array1, capacity)) {

   173             return 1;

   174         }

   175     }

   177     void* dest = ucx_array_at(*array1, array1->size);

   178     memcpy(dest, array2->data, array2->size*array2->elemsize);

   180     array1->size += array2->size;

   182     return 0;

   183 }

   185 void *ucx_array_at(UcxArray array, size_t index) {

   186     char* memory = array.data;

   187     char* loc = memory + index*array.elemsize;

   188     return loc;

   189 }

   191 size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {

   193     if (cmpfnc == NULL) {

   194         cmpfnc = ucx_cmp_mem;

   195         data = &array.elemsize;

   196     }

   198     if (array.size > 0) {

   199         for (size_t i = 0 ; i < array.size ; i++) {

   200             void* ptr = ucx_array_at(array, i);

   201             if (cmpfnc(ptr, elem, data) == 0) {

   202                 return i;

   203             }

   204         }

   205         return array.size;

   206     } else {

   207         return 0;

   208     }

   209 }

   211 int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {

   212     return ucx_array_find(array, elem, cmpfnc, data) != array.size;

   213 }

   215 static void ucx_array_merge(UcxArray *array, cmp_func cmpfnc, void *data,

   216         size_t start, size_t mid, size_t end) {

   218     size_t rightstart = mid + 1;

   220     if (cmpfnc(ucx_array_at(*array, mid),

   221             ucx_array_at(*array, rightstart), data) <= 0) {

   222         /* already sorted */

   223         return;

   224     }

   226     // we need memory for one element

   227     void *value = malloc(array->elemsize);

   229     while (start <= mid && rightstart <= end) {

   230         if (cmpfnc(ucx_array_at(*array, start),

   231                 ucx_array_at(*array, rightstart), data) <= 0) {

   232             start++;

   233         } else {

   234             // save the value from the right

   235             memcpy(value, ucx_array_at(*array, rightstart), array->elemsize);

   237             // shift all left elements one element to the right

   238             size_t shiftcount = rightstart-start;

   239             void *startptr = ucx_array_at(*array, start);

   240             void *dest = ucx_array_at(*array, start+1);

   241             memmove(dest, startptr, shiftcount*array->elemsize);

   243             // bring the first value from the right to the left

   244             memcpy(startptr, value, array->elemsize);

   246             start++;

   247             mid++;

   248             rightstart++;

   249         }

   250     }

   252     // free the temporary memory

   253     free(value);

   254 }

   256 static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data,

   257         size_t l, size_t r) {

   258     if (l < r) {

   259         size_t m = l + (r - l) / 2;

   261         ucx_array_mergesort(array, cmpfnc, data, l, m);

   262         ucx_array_mergesort(array, cmpfnc, data, m + 1, r);

   263         ucx_array_merge(array, cmpfnc, data, l, m, r);

   264     }

   265 }

   267 void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {

   268     ucx_array_mergesort(&array, cmpfnc, data, 0, array.size-1);

   269 }

   271 void ucx_array_remove(UcxArray *array, size_t index) {

   272     array->size--;

   273     if (index < array->size) {

   274         void* dest = ucx_array_at(*array, index);

   275         void* src = ucx_array_at(*array, index+1);

   276         memmove(dest, src, (array->size - index)*array->elemsize);

   277     }

   278 }

   280 void ucx_array_remove_fast(UcxArray *array, size_t index) {

   281     array->size--;

   282     if (index < array->size) {

   283         void* dest = ucx_array_at(*array, index);

   284         void* src = ucx_array_at(*array, array->size);

   285         memcpy(dest, src, array->elemsize);

   286     }

   287 }

   289 int ucx_array_shrink(UcxArray* array) {

   290     void* newptr = alrealloc(array->allocator, array->data,

   291                 array->size*array->elemsize);

   292     if (newptr) {

   293         array->data = newptr;

   294         array->capacity = array->size;

   295         return 0;

   296     } else {

   297         return 1;

   298     }

   299 }

   301 int ucx_array_resize(UcxArray* array, size_t capacity) {

   302     if (array->capacity >= capacity) {

   303         void* newptr = alrealloc(array->allocator, array->data,

   304                 capacity*array->elemsize);

   305         if (newptr) {

   306             array->data = newptr;

   307             array->capacity = capacity;

   308             if (array->size > array->capacity) {

   309                 array->size = array->capacity;

   310             }

   311             return 0;

   312         } else {

   313             return 1;

   314         }

   315     } else {

   316         return ucx_array_reserve(array, capacity);

   317     }

   318 }

   320 int ucx_array_reserve(UcxArray* array, size_t capacity) {

   321     if (array->capacity > capacity) {

   322         return 0;

   323     } else {

   324         void* newptr = alrealloc(array->allocator, array->data,

   325                 capacity*array->elemsize);

   326         if (newptr) {

   327             array->data = newptr;

   328             array->capacity = capacity;

   329             return 0;

   330         } else {

   331             return 1;

   332         }

   333     }

   334 }

Mercurial > hg > ucx / file revision

src/array.c@f695ae118460

src/array.c