ucx/array.c

   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  */
  28
  29 #define _GNU_SOURCE /* we want to use qsort_r(), if available */
  30 #define __STDC_WANT_LIB_EXT1__ 1 /* use qsort_s, if available */
  31
  32
  33 #include "ucx/array.h"
  34 #include "ucx/utils.h"
  35
  36 #include <string.h>
  37 #include <stdlib.h>
  38 #include <errno.h>
  39
  40 #ifndef UCX_ARRAY_DISABLE_QSORT
  41 #ifdef __GLIBC__
  42 #if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)
  43 #define ucx_array_sort_impl qsort_r
  44 #endif /* glibc version >= 2.8 */
  45 #elif /* not  __GLIBC__ */ defined(__APPLE__) || defined(__FreeBSD__)
  46 #define ucx_array_sort_impl ucx_qsort_r
  47 #define USE_UCX_QSORT_R
  48 #elif /* not (__APPLE || __FreeBSD__) */ defined(__sun)
  49 #if __STDC_VERSION__ >= 201112L
  50 #define ucx_array_sort_impl qsort_s
  51 #endif
  52 #endif /* __GLIBC__, __APLE__, __FreeBSD__, __sun */
  53 #endif /* UCX_ARRAY_DISABLE_QSORT */
  54
  55 #ifndef ucx_array_sort_impl
  56 #define ucx_array_sort_impl ucx_mergesort
  57 #endif
  58
  59 static int ucx_array_ensurecap(UcxArray *array, size_t reqcap) {
  60     size_t required_capacity = array->capacity;
  61     while (reqcap > required_capacity) {
  62         if (required_capacity * 2 < required_capacity)
  63             return 1;
  64         required_capacity <<= 1;
  65     }
  66     if (ucx_array_reserve(array, required_capacity)) {
  67         return 1;
  68     }
  69     return 0;
  70 }
  71
  72 int ucx_array_util_set_a(UcxAllocator* alloc, void** array, size_t* capacity,
  73     size_t elmsize, size_t index, void* data) {
  74
  75     if(!alloc || !capacity || !array) {
  76         errno = EINVAL;
  77         return 1;
  78     }
  79
  80     size_t newcapacity = *capacity;
  81     while(index >= newcapacity) {
  82         if(ucx_szmul(newcapacity, 2, &newcapacity)) {
  83             errno = EOVERFLOW;
  84             return 1;
  85         }
  86     }
  87
  88     size_t memlen, offset;
  89     if(ucx_szmul(newcapacity, elmsize, &memlen)) {
  90         errno = EOVERFLOW;
  91         return 1;
  92     }
  93     /* we don't need to check index*elmsize - it is smaller than memlen */
  94
  95
  96     void* newptr = alrealloc(alloc, *array, memlen);
  97     if(newptr == NULL) {
  98         errno = ENOMEM; /* we cannot assume that every allocator sets this */
  99         return 1;
 100     }
 101     *array = newptr;
 102     *capacity = newcapacity;
 103
 104
 105     char* dest = *array;
 106     dest += elmsize*index;
 107     memcpy(dest, data, elmsize);
 108
 109     return 0;
 110 }
 111
 112 int ucx_array_util_setptr_a(UcxAllocator* alloc, void** array, size_t* capacity,
 113     size_t index, void* data) {
 114
 115     return ucx_array_util_set_a(alloc, array, capacity, sizeof(void*),
 116             index, &data);
 117 }
 118
 119 UcxArray* ucx_array_new(size_t capacity, size_t elemsize) {
 120     return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
 121 }
 122
 123 UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize,
 124         UcxAllocator* allocator) {
 125     UcxArray* array = almalloc(allocator, sizeof(UcxArray));
 126     if(array) {
 127         ucx_array_init_a(array, capacity, elemsize, allocator);
 128     }
 129     return array;
 130 }
 131
 132 void ucx_array_init(UcxArray* array, size_t capacity, size_t elemsize) {
 133     ucx_array_init_a(array, capacity, elemsize, ucx_default_allocator());
 134 }
 135
 136 void ucx_array_init_a(UcxArray* array, size_t capacity, size_t elemsize,
 137         UcxAllocator* allocator) {
 138
 139     array->allocator = allocator;
 140     array->elemsize = elemsize;
 141     array->size = 0;
 142     array->data = alcalloc(allocator, capacity, elemsize);
 143
 144     if (array->data) {
 145         array->capacity = capacity;
 146     } else {
 147         array->capacity = 0;
 148     }
 149 }
 150
 151 int ucx_array_clone(UcxArray* dest, UcxArray const* src) {
 152     if (ucx_array_ensurecap(dest, src->capacity)) {
 153         return 1;
 154     }
 155
 156     dest->elemsize = src->elemsize;
 157     dest->size = src->size;
 158
 159     if (dest->data) {
 160         memcpy(dest->data, src->data, src->size*src->elemsize);
 161     }
 162
 163     return 0;
 164 }
 165
 166 int ucx_array_equals(UcxArray const *array1, UcxArray const *array2,
 167         cmp_func cmpfnc, void* data) {
 168
 169     if (array1->size != array2->size || array1->elemsize != array2->elemsize) {
 170         return 0;
 171     } else {
 172         if (array1->size == 0)
 173             return 1;
 174
 175         size_t elemsize;
 176         if (cmpfnc == NULL) {
 177             cmpfnc = ucx_cmp_mem;
 178             elemsize = array1->elemsize;
 179             data = &elemsize;
 180         }
 181
 182         for (size_t i = 0 ; i < array1->size ; i++) {
 183             int r = cmpfnc(
 184                     ucx_array_at(array1, i),
 185                     ucx_array_at(array2, i),
 186                     data);
 187             if (r != 0)
 188                 return 0;
 189         }
 190         return 1;
 191     }
 192 }
 193
 194 void ucx_array_destroy(UcxArray *array) {
 195     if(array->data)
 196         alfree(array->allocator, array->data);
 197     array->data = NULL;
 198     array->capacity = array->size = 0;
 199 }
 200
 201 void ucx_array_free(UcxArray *array) {
 202     ucx_array_destroy(array);
 203     alfree(array->allocator, array);
 204 }
 205
 206 int ucx_array_append_from(UcxArray *array, void *data, size_t count) {
 207     if (ucx_array_ensurecap(array, array->size + count))
 208         return 1;
 209
 210     void* dest = ucx_array_at(array, array->size);
 211     if (data) {
 212         memcpy(dest, data, array->elemsize*count);
 213     } else {
 214         memset(dest, 0, array->elemsize*count);
 215     }
 216     array->size += count;
 217
 218     return 0;
 219 }
 220
 221 int ucx_array_prepend_from(UcxArray *array, void *data, size_t count) {
 222     if (ucx_array_ensurecap(array, array->size + count))
 223         return 1;
 224
 225     if (array->size > 0) {
 226         void *dest = ucx_array_at(array, count);
 227         memmove(dest, array->data, array->elemsize*array->size);
 228     }
 229
 230     if (data) {
 231         memcpy(array->data, data, array->elemsize*count);
 232     } else {
 233         memset(array->data, 0, array->elemsize*count);
 234     }
 235     array->size += count;
 236
 237     return 0;
 238 }
 239
 240 int ucx_array_set_from(UcxArray *array, size_t index,
 241         void *data, size_t count) {
 242     if (ucx_array_ensurecap(array, index + count))
 243         return 1;
 244
 245     if (index+count > array->size) {
 246         array->size = index+count;
 247     }
 248
 249     void *dest = ucx_array_at(array, index);
 250     if (data) {
 251         memcpy(dest, data, array->elemsize*count);
 252     } else {
 253         memset(dest, 0, array->elemsize*count);
 254     }
 255
 256     return 0;
 257 }
 258
 259 int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
 260
 261     if (array1->elemsize != array2->elemsize)
 262         return 1;
 263
 264     size_t capacity = array1->capacity+array2->capacity;
 265
 266     if (array1->capacity < capacity) {
 267         if (ucx_array_reserve(array1, capacity)) {
 268             return 1;
 269         }
 270     }
 271
 272     void* dest = ucx_array_at(array1, array1->size);
 273     memcpy(dest, array2->data, array2->size*array2->elemsize);
 274
 275     array1->size += array2->size;
 276
 277     return 0;
 278 }
 279
 280 void *ucx_array_at(UcxArray const *array, size_t index) {
 281     char* memory = array->data;
 282     char* loc = memory + index*array->elemsize;
 283     return loc;
 284 }
 285
 286 size_t ucx_array_find(UcxArray const *array, void *elem,
 287         cmp_func cmpfnc, void *data) {
 288
 289     size_t elemsize;
 290     if (cmpfnc == NULL) {
 291         cmpfnc = ucx_cmp_mem;
 292         elemsize = array->elemsize;
 293         data = &elemsize;
 294     }
 295
 296     if (array->size > 0) {
 297         for (size_t i = 0 ; i < array->size ; i++) {
 298             void* ptr = ucx_array_at(array, i);
 299             if (cmpfnc(ptr, elem, data) == 0) {
 300                 return i;
 301             }
 302         }
 303         return array->size;
 304     } else {
 305         return 0;
 306     }
 307 }
 308
 309 int ucx_array_contains(UcxArray const *array, void *elem,
 310         cmp_func cmpfnc, void *data) {
 311     return ucx_array_find(array, elem, cmpfnc, data) != array->size;
 312 }
 313
 314 static void ucx_mergesort_merge(void *arrdata,size_t elemsize,
 315         cmp_func cmpfnc, void *data,
 316         size_t start, size_t mid, size_t end) {
 317
 318     char* array = arrdata;
 319
 320     size_t rightstart = mid + 1;
 321
 322     if (cmpfnc(array + mid*elemsize,
 323             array + rightstart*elemsize, data) <= 0) {
 324         /* already sorted */
 325         return;
 326     }
 327
 328     /* we need memory for one element */
 329     void *value = malloc(elemsize);
 330
 331     while (start <= mid && rightstart <= end) {
 332         if (cmpfnc(array + start*elemsize,
 333                 array + rightstart*elemsize, data) <= 0) {
 334             start++;
 335         } else {
 336             /* save the value from the right */
 337             memcpy(value, array + rightstart*elemsize, elemsize);
 338
 339             /* shift all left elements one element to the right */
 340             size_t shiftcount = rightstart-start;
 341             void *startptr = array + start*elemsize;
 342             void *dest = array + (start+1)*elemsize;
 343             memmove(dest, startptr, shiftcount*elemsize);
 344
 345             /* bring the first value from the right to the left */
 346             memcpy(startptr, value, elemsize);
 347
 348             start++;
 349             mid++;
 350             rightstart++;
 351         }
 352     }
 353
 354     /* free the temporary memory */
 355     free(value);
 356 }
 357
 358 static void ucx_mergesort_impl(void *arrdata, size_t elemsize,
 359         cmp_func cmpfnc, void *data, size_t l, size_t r) {
 360     if (l < r) {
 361         size_t m = l + (r - l) / 2;
 362
 363         ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m);
 364         ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r);
 365         ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);
 366     }
 367 }
 368
 369 static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,
 370         cmp_func cmpfnc, void *data) {
 371
 372     ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);
 373 }
 374
 375 #ifdef USE_UCX_QSORT_R
 376 struct cmpfnc_swapargs_info {
 377     cmp_func func;
 378     void *data;
 379 };
 380
 381 static int cmp_func_swap_args(void *data, const void *x, const void *y) {
 382     struct cmpfnc_swapargs_info* info = data;
 383     return info->func(x, y, info->data);
 384 }
 385
 386 static void ucx_qsort_r(void *array, size_t count, size_t elemsize,
 387                      cmp_func cmpfnc, void *data) {
 388     struct cmpfnc_swapargs_info info;
 389     info.func = cmpfnc;
 390     info.data = data;
 391     qsort_r(array, count, elemsize, &info, cmp_func_swap_args);
 392 }
 393 #endif /* USE_UCX_QSORT_R */
 394
 395 void ucx_array_sort(UcxArray* array, cmp_func cmpfnc, void *data) {
 396     ucx_array_sort_impl(array->data, array->size, array->elemsize,
 397             cmpfnc, data);
 398 }
 399
 400 void ucx_array_remove(UcxArray *array, size_t index) {
 401     array->size--;
 402     if (index < array->size) {
 403         void* dest = ucx_array_at(array, index);
 404         void* src = ucx_array_at(array, index+1);
 405         memmove(dest, src, (array->size - index)*array->elemsize);
 406     }
 407 }
 408
 409 void ucx_array_remove_fast(UcxArray *array, size_t index) {
 410     array->size--;
 411     if (index < array->size) {
 412         void* dest = ucx_array_at(array, index);
 413         void* src = ucx_array_at(array, array->size);
 414         memcpy(dest, src, array->elemsize);
 415     }
 416 }
 417
 418 int ucx_array_shrink(UcxArray* array) {
 419     void* newptr = alrealloc(array->allocator, array->data,
 420                 array->size*array->elemsize);
 421     if (newptr) {
 422         array->data = newptr;
 423         array->capacity = array->size;
 424         return 0;
 425     } else {
 426         return 1;
 427     }
 428 }
 429
 430 int ucx_array_resize(UcxArray* array, size_t capacity) {
 431     if (array->capacity >= capacity) {
 432         void* newptr = alrealloc(array->allocator, array->data,
 433                 capacity*array->elemsize);
 434         if (newptr) {
 435             array->data = newptr;
 436             array->capacity = capacity;
 437             if (array->size > array->capacity) {
 438                 array->size = array->capacity;
 439             }
 440             return 0;
 441         } else {
 442             return 1;
 443         }
 444     } else {
 445         return ucx_array_reserve(array, capacity);
 446     }
 447 }
 448
 449 int ucx_array_reserve(UcxArray* array, size_t capacity) {
 450     if (array->capacity > capacity) {
 451         return 0;
 452     } else {
 453         void* newptr = alrealloc(array->allocator, array->data,
 454                 capacity*array->elemsize);
 455         if (newptr) {
 456             array->data = newptr;
 457             array->capacity = capacity;
 458             return 0;
 459         } else {
 460             return 1;
 461         }
 462     }
 463 }
 464
 465 int ucx_array_grow(UcxArray* array, size_t count) {
 466     return ucx_array_reserve(array, array->size+count);
 467 }