ucx: src/array.c@6089eb30a51a (annotated)

src/array.c@6089eb30a51a (annotated)

src/array.c

Wed, 07 Aug 2019 21:14:58 +0200

author: Mike Becker <universe@uap-core.de>
date: Wed, 07 Aug 2019 21:14:58 +0200
branch: feature/array
changeset 345: 6089eb30a51a
parent 342: 8f0a3c00d1d2
child 346: 1a9c112f4116
permissions: -rw-r--r--

ucx_array_sort() uses qsort_r(), if available

 /*
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
  *
  * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are met:
  *
  *   1. Redistributions of source code must retain the above copyright
  *      notice, this list of conditions and the following disclaimer.
  *
  *   2. Redistributions in binary form must reproduce the above copyright
  *      notice, this list of conditions and the following disclaimer in the
  *      documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
 #define _GNU_SOURCE /* we want to use qsort_r(), if available */
 #include "ucx/array.h"
 #include "ucx/utils.h"
 #include <string.h>
 #include <stdlib.h>
 #ifndef UCX_ARRAY_DISABLE_QSORT
 #if defined(__GLIBC__)
 #if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)
 #define ucx_array_sort_impl qsort_r
 #endif /* glibc version >= 2.8 */
 #endif /* __GLIBC__ */
 #if defined(__APPLE__) || defined(__FreeBSD__)
 #define ucx_array_sort_impl ucx_qsort_r
 #define USE_UCX_QSORT_R
 #endif /* __APLE__ or __FreeBSD__ */
 #endif /* UCX_ARRAY_DISABLE_QSORT */
 #ifndef ucx_array_sort_impl
 #define ucx_array_sort_impl ucx_mergesort
 #endif
 UcxArray ucx_array_new(size_t capacity, size_t elemsize) {
     return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
 }
 UcxArray ucx_array_new_a(size_t capacity, size_t elemsize,
         UcxAllocator* allocator) {
     UcxArray array;
     array.allocator = allocator;
     array.elemsize = elemsize;
     array.size = 0;
     array.data = alcalloc(allocator, capacity, elemsize);
     if (array.data) {
         array.capacity = capacity;
     } else {
         array.capacity = 0;
     }
     return array;
 }
 UcxArray ucx_array_clone(UcxArray array) {
     UcxArray clone;
     clone.allocator = array.allocator;
     clone.elemsize = array.elemsize;
     clone.size = array.size;
     clone.data = alcalloc(array.allocator, array.capacity, array.elemsize);
     if (clone.data) {
         clone.capacity = array.capacity;
         memcpy(clone.data, array.data, array.size*array.elemsize);
     } else {
         clone.capacity = clone.size = 0;
     }
     return clone;
 }
 int ucx_array_equals(UcxArray array1, UcxArray array2,
         cmp_func cmpfnc, void* data) {
     if (array1.size != array2.size || array1.elemsize != array2.elemsize) {
         return 0;
     } else {
         if (array1.size == 0)
             return 1;
         if (cmpfnc == NULL) {
             cmpfnc = ucx_cmp_mem;
             data = &array1.elemsize;
         }
         for (size_t i = 0 ; i < array1.size ; i++) {
             int r = cmpfnc(
                     ucx_array_at(array1, i),
                     ucx_array_at(array2, i),
                     data);
             if (r != 0)
                 return 0;
         }
         return 1;
     }
 }
 void ucx_array_free(UcxArray *array) {
     alfree(array->allocator, array->data);
     array->data = NULL;
     array->capacity = array->size = 0;
 }
 int ucx_array_append(UcxArray *array, void *data) {
     if (array->size == array->capacity) {
         if (ucx_array_reserve(array, array->capacity*2)) {
             return 1;
         }
     }
     void* dest = ucx_array_at(*array, array->size++);
     if (data) {
         memcpy(dest, data, array->elemsize);
     } else {
         memset(dest, 0, array->elemsize);
     }
     return 0;
 }
 int ucx_array_prepend(UcxArray *array, void *data) {
     if (array->size == array->capacity) {
         if (ucx_array_reserve(array, array->capacity*2)) {
             return 1;
         }
     }
     array->size++;
     if (array->size > 1) {
         void *dest = ucx_array_at(*array,1);
         memmove(dest, array->data, array->elemsize*array->size);
     }
     if (data) {
         memcpy(array->data, data, array->elemsize);
     } else {
         memset(array->data, 0, array->elemsize);
     }
     return 0;
 }
 int ucx_array_set(UcxArray *array, size_t index, void *data) {
     if (index >= array->size) {
         if (ucx_array_reserve(array, index+1)) {
             return 1;
         }
         array->size = index+1;
     }
     void *dest = ucx_array_at(*array, index);
     if (data) {
         memcpy(dest, data, array->elemsize);
     } else {
         memset(dest, 0, array->elemsize);
     }
     return 0;
 }
 int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
     if (array1->elemsize != array2->elemsize)
         return 1;
     size_t capacity = array1->capacity+array2->capacity;
     if (array1->capacity < capacity) {
         if (ucx_array_reserve(array1, capacity)) {
             return 1;
         }
     }
     void* dest = ucx_array_at(*array1, array1->size);
     memcpy(dest, array2->data, array2->size*array2->elemsize);
     array1->size += array2->size;
     return 0;
 }
 void *ucx_array_at(UcxArray array, size_t index) {
     char* memory = array.data;
     char* loc = memory + index*array.elemsize;
     return loc;
 }
 size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
     if (cmpfnc == NULL) {
         cmpfnc = ucx_cmp_mem;
         data = &array.elemsize;
     }
     if (array.size > 0) {
         for (size_t i = 0 ; i < array.size ; i++) {
             void* ptr = ucx_array_at(array, i);
             if (cmpfnc(ptr, elem, data) == 0) {
                 return i;
             }
         }
         return array.size;
     } else {
         return 0;
     }
 }
 int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
     return ucx_array_find(array, elem, cmpfnc, data) != array.size;
 }
 static void ucx_mergesort_merge(void *arrdata,size_t elemsize,
         cmp_func cmpfnc, void *data,
         size_t start, size_t mid, size_t end) {
     char* array = arrdata;
     size_t rightstart = mid + 1;
     if (cmpfnc(array + mid*elemsize,
             array + rightstart*elemsize, data) <= 0) {
         /* already sorted */
         return;
     }
     /* we need memory for one element */
     void *value = malloc(elemsize);
     while (start <= mid && rightstart <= end) {
         if (cmpfnc(array + start*elemsize,
                 array + rightstart*elemsize, data) <= 0) {
             start++;
         } else {
             /* save the value from the right */
             memcpy(value, array + rightstart*elemsize, elemsize);
             /* shift all left elements one element to the right */
             size_t shiftcount = rightstart-start;
             void *startptr = array + start*elemsize;
             void *dest = array + (start+1)*elemsize;
             memmove(dest, startptr, shiftcount*elemsize);
             /* bring the first value from the right to the left */
             memcpy(startptr, value, elemsize);
             start++;
             mid++;
             rightstart++;
         }
     }
     /* free the temporary memory */
     free(value);
 }
 static void ucx_mergesort_impl(void *arrdata, size_t elemsize,
         cmp_func cmpfnc, void *data, size_t l, size_t r) {
     if (l < r) {
         size_t m = l + (r - l) / 2;
         ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m);
         ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r);
         ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);
     }
 }
 static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,
         cmp_func cmpfnc, void *data) {
     ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);
 }
 #ifdef USE_UCX_QSORT_R
 struct cmpfnc_swapargs_info {
     cmp_func func;
     void *data;
 };
 static int cmp_func_swap_args(void *data, const void *x, const void *y) {
     cmpfnc_swapargs_info* info = data;
     return info->func(x, y, info->data);
 }
 static void ucx_qsort_r(void *array, size_t count, size_t elemsize,
 		     cmp_func cmpfnc, void *data) {
     struct cmpfnc_swapargs_info info;
     info.func = cmpfnc;
     info.data = data;
     qsort_r(array, count, elemsize, &info, cmp_func_swap_args);
 }
 #endif /* USE_UCX_QSORT_R */
 void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {
     ucx_array_sort_impl(array.data, array.size, array.elemsize, cmpfnc, data);
 }
 void ucx_array_remove(UcxArray *array, size_t index) {
     array->size--;
     if (index < array->size) {
         void* dest = ucx_array_at(*array, index);
         void* src = ucx_array_at(*array, index+1);
         memmove(dest, src, (array->size - index)*array->elemsize);
     }
 }
 void ucx_array_remove_fast(UcxArray *array, size_t index) {
     array->size--;
     if (index < array->size) {
         void* dest = ucx_array_at(*array, index);
         void* src = ucx_array_at(*array, array->size);
         memcpy(dest, src, array->elemsize);
     }
 }
 int ucx_array_shrink(UcxArray* array) {
     void* newptr = alrealloc(array->allocator, array->data,
                 array->size*array->elemsize);
     if (newptr) {
         array->data = newptr;
         array->capacity = array->size;
         return 0;
     } else {
         return 1;
     }
 }
 int ucx_array_resize(UcxArray* array, size_t capacity) {
     if (array->capacity >= capacity) {
         void* newptr = alrealloc(array->allocator, array->data,
                 capacity*array->elemsize);
         if (newptr) {
             array->data = newptr;
             array->capacity = capacity;
             if (array->size > array->capacity) {
                 array->size = array->capacity;
             }
             return 0;
         } else {
             return 1;
         }
     } else {
         return ucx_array_reserve(array, capacity);
     }
 }
 int ucx_array_reserve(UcxArray* array, size_t capacity) {
     if (array->capacity > capacity) {
         return 0;
     } else {
         void* newptr = alrealloc(array->allocator, array->data,
                 capacity*array->elemsize);
         if (newptr) {
             array->data = newptr;
             array->capacity = capacity;
             return 0;
         } else {
             return 1;
         }
     }
 }

Mercurial > hg > ucx / annotate

src/array.c@6089eb30a51a (annotated)

src/array.c