Mercurial > hg > ucx / changeset

     1.1 --- a/src/array.c	Thu Jul 04 21:31:45 2019 +0200
     1.2 +++ b/src/array.c	Thu Jul 04 22:23:15 2019 +0200
     1.3 @@ -27,7 +27,9 @@
     1.4   */
     1.5  
     1.6  #include "ucx/array.h"
     1.7 +#include "ucx/utils.h"
     1.8  
     1.9 +#include <string.h>
    1.10  
    1.11  UcxArray ucx_array_new(size_t capacity, size_t elemsize) {
    1.12      return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
    1.13 @@ -37,71 +39,278 @@
    1.14          UcxAllocator* allocator) {
    1.15      UcxArray array;
    1.16      
    1.17 +    array.allocator = allocator;
    1.18 +    array.elemsize = elemsize;
    1.19 +    array.size = 0;
    1.20 +    array.data = alcalloc(allocator, capacity, elemsize);
    1.21 +    
    1.22 +    if (array.data) {
    1.23 +        array.capacity = capacity;
    1.24 +    } else {
    1.25 +        array.capacity = 0;
    1.26 +    }
    1.27 +    
    1.28      return array;
    1.29  }
    1.30  
    1.31  UcxArray ucx_array_clone(UcxArray array) {
    1.32      UcxArray clone;
    1.33      
    1.34 +    clone.allocator = array.allocator;
    1.35 +    clone.elemsize = array.elemsize;
    1.36 +    clone.size = array.size;
    1.37 +    clone.data = alcalloc(array.allocator, array.capacity, array.elemsize);
    1.38 +    
    1.39 +    if (clone.data) {
    1.40 +        clone.capacity = array.capacity;
    1.41 +        memcpy(clone.data, array.data, array.size*array.elemsize);
    1.42 +    } else {
    1.43 +        clone.capacity = clone.size = 0;
    1.44 +    }
    1.45 +    
    1.46      return clone;
    1.47  }
    1.48  
    1.49  int ucx_array_equals(UcxArray array1, UcxArray array2,
    1.50          cmp_func cmpfnc, void* data) {
    1.51      
    1.52 -    return 1;
    1.53 +    if (array1.size != array2.size || array1.elemsize != array2.elemsize) {
    1.54 +        return 0;
    1.55 +    } else {
    1.56 +        if (array1.size == 0)
    1.57 +            return 1;
    1.58 +        
    1.59 +        if (cmpfnc == NULL) {
    1.60 +            cmpfnc = ucx_cmp_mem;
    1.61 +            data = &array1.elemsize;
    1.62 +        }
    1.63 +        
    1.64 +        for (size_t i = 0 ; i < array1.size ; i++) {
    1.65 +            int r = cmpfnc(
    1.66 +                    ucx_array_at(array1, i),
    1.67 +                    ucx_array_at(array2, i),
    1.68 +                    data);
    1.69 +            if (r != 0)
    1.70 +                return 0;
    1.71 +        }
    1.72 +        return 1;
    1.73 +    }
    1.74  }
    1.75  
    1.76  void ucx_array_free(UcxArray *array) {
    1.77 -    
    1.78 +    alfree(array->allocator, array->data);
    1.79 +    array->data = NULL;
    1.80 +    array->capacity = array->size = 0;
    1.81  }
    1.82  
    1.83  int ucx_array_append(UcxArray *array, void *data) {
    1.84 -    return 1;
    1.85 +    if (array->size == array->capacity) {
    1.86 +        if (ucx_array_reserve(array, array->capacity*2)) {
    1.87 +            return 1;
    1.88 +        }
    1.89 +    }
    1.90 +    
    1.91 +    void* dest = ucx_array_at(*array, array->size++);
    1.92 +    if (data) {
    1.93 +        memcpy(dest, data, array->elemsize);
    1.94 +    } else {
    1.95 +        memset(dest, 0, array->elemsize);
    1.96 +    }
    1.97 +    
    1.98 +    return 0;
    1.99  }
   1.100  
   1.101  int ucx_array_prepend(UcxArray *array, void *data) {
   1.102 -    return 1;
   1.103 +    if (array->size == array->capacity) {
   1.104 +        if (ucx_array_reserve(array, array->capacity*2)) {
   1.105 +            return 1;
   1.106 +        }
   1.107 +    }
   1.108 +    
   1.109 +    array->size++;
   1.110 +    
   1.111 +    if (array->size > 1) {
   1.112 +        void *dest = ucx_array_at(*array,1);
   1.113 +        memmove(dest, array->data, array->elemsize*array->size);
   1.114 +    }
   1.115 +    
   1.116 +    if (data) {
   1.117 +        memcpy(array->data, data, array->elemsize);
   1.118 +    } else {
   1.119 +        memset(array->data, 0, array->elemsize);
   1.120 +    }
   1.121 +        
   1.122 +    return 0;
   1.123  }
   1.124  
   1.125  int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
   1.126 -    return 1;
   1.127 +    
   1.128 +    if (array1->elemsize != array2->elemsize)
   1.129 +        return 1;
   1.130 +    
   1.131 +    size_t capacity = array1->capacity+array2->capacity;
   1.132 +        
   1.133 +    if (array1->capacity < capacity) {
   1.134 +        if (ucx_array_reserve(array1, capacity)) {
   1.135 +            return 1;
   1.136 +        }
   1.137 +    }
   1.138 +    
   1.139 +    void* dest = ucx_array_at(*array1, array1->size);
   1.140 +    memcpy(dest, array2->data, array2->size*array2->elemsize);
   1.141 +    
   1.142 +    array1->size += array2->size;
   1.143 +    
   1.144 +    return 0;
   1.145  }
   1.146  
   1.147  void *ucx_array_at(UcxArray array, size_t index) {
   1.148 -    return NULL;
   1.149 +    char* memory = array.data;
   1.150 +    char* loc = memory + index*array.elemsize;
   1.151 +    return loc;
   1.152  }
   1.153  
   1.154  size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
   1.155      
   1.156 -    return 0;
   1.157 +    if (cmpfnc == NULL) {
   1.158 +        cmpfnc = ucx_cmp_mem;
   1.159 +        data = &array.elemsize;
   1.160 +    }
   1.161 +
   1.162 +    if (array.size > 0) {
   1.163 +        for (size_t i = 0 ; i < array.size ; i++) {
   1.164 +            void* ptr = ucx_array_at(array, i);
   1.165 +            if (cmpfnc(ptr, elem, data) == 0) {
   1.166 +                return i;
   1.167 +            }
   1.168 +        }
   1.169 +        return array.size;
   1.170 +    } else {
   1.171 +        return 0;
   1.172 +    }
   1.173  }
   1.174  
   1.175  int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
   1.176      return ucx_array_find(array, elem, cmpfnc, data) != array.size;
   1.177  }
   1.178  
   1.179 -int ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {
   1.180 -    return 1;
   1.181 +static void ucx_array_merge(UcxArray *array, cmp_func cmpfnc, void *data,
   1.182 +        size_t start, size_t mid, size_t end) { 
   1.183 +    
   1.184 +    size_t rightstart = mid + 1; 
   1.185 +  
   1.186 +    if (cmpfnc(ucx_array_at(*array, mid),
   1.187 +            ucx_array_at(*array, rightstart), data) <= 0) {
   1.188 +        /* already sorted */
   1.189 +        return;
   1.190 +    }
   1.191 +  
   1.192 +    // we need memory for one element
   1.193 +    void *value = malloc(array->elemsize);
   1.194 +    
   1.195 +    while (start <= mid && rightstart <= end) { 
   1.196 +        if (cmpfnc(ucx_array_at(*array, start),
   1.197 +                ucx_array_at(*array, rightstart), data) <= 0) { 
   1.198 +            start++; 
   1.199 +        } else {
   1.200 +            // save the value from the right
   1.201 +            memcpy(value, ucx_array_at(*array, rightstart), array->elemsize);
   1.202 +                        
   1.203 +            // shift all left elements one element to the right
   1.204 +            size_t shiftcount = rightstart-start;
   1.205 +            void *startptr = ucx_array_at(*array, start);
   1.206 +            void *dest = ucx_array_at(*array, start+1);
   1.207 +            memmove(dest, startptr, shiftcount*array->elemsize);
   1.208 +            
   1.209 +            // bring the first value from the right to the left
   1.210 +            memcpy(startptr, value, array->elemsize);
   1.211 +  
   1.212 +            start++; 
   1.213 +            mid++; 
   1.214 +            rightstart++; 
   1.215 +        }
   1.216 +    }
   1.217 +    
   1.218 +    // free the temporary memory
   1.219 +    free(value);
   1.220 +} 
   1.221 +  
   1.222 +static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data,
   1.223 +        size_t l, size_t r) { 
   1.224 +    if (l < r) {
   1.225 +        size_t m = l + (r - l) / 2; 
   1.226 +  
   1.227 +        ucx_array_mergesort(array, cmpfnc, data, l, m); 
   1.228 +        ucx_array_mergesort(array, cmpfnc, data, m + 1, r); 
   1.229 +        ucx_array_merge(array, cmpfnc, data, l, m, r);
   1.230 +    } 
   1.231 +}
   1.232 +
   1.233 +void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {   
   1.234 +    ucx_array_mergesort(&array, cmpfnc, data, 0, array.size-1);
   1.235  }
   1.236  
   1.237  void ucx_array_remove(UcxArray *array, size_t index) {
   1.238 -    
   1.239 +    array->size--;
   1.240 +    if (index < array->size) {
   1.241 +        void* dest = ucx_array_at(*array, index);
   1.242 +        void* src = ucx_array_at(*array, index+1);
   1.243 +        memmove(dest, src, (array->size - index)*array->elemsize);
   1.244 +    }
   1.245  }
   1.246  
   1.247  void ucx_array_remove_fast(UcxArray *array, size_t index) {
   1.248 -    
   1.249 +    array->size--;
   1.250 +    if (index < array->size) {       
   1.251 +        void* dest = ucx_array_at(*array, index);
   1.252 +        void* src = ucx_array_at(*array, array->size);
   1.253 +        memcpy(dest, src, array->elemsize);
   1.254 +    }
   1.255  }
   1.256  
   1.257  int ucx_array_shrink(UcxArray* array) {
   1.258 -    return 1;
   1.259 +    void* newptr = alrealloc(array->allocator, array->data,
   1.260 +                array->size*array->elemsize);
   1.261 +    if (newptr) {
   1.262 +        array->data = newptr;
   1.263 +        array->capacity = array->size;
   1.264 +        return 0;
   1.265 +    } else {
   1.266 +        return 1;
   1.267 +    }
   1.268  }
   1.269  
   1.270  int ucx_array_resize(UcxArray* array, size_t capacity) {
   1.271 -    return 1;
   1.272 +    if (array->capacity >= capacity) {
   1.273 +        void* newptr = alrealloc(array->allocator, array->data,
   1.274 +                capacity*array->elemsize);
   1.275 +        if (newptr) {
   1.276 +            array->data = newptr;
   1.277 +            array->capacity = capacity;
   1.278 +            if (array->size > array->capacity) {
   1.279 +                array->size = array->capacity;
   1.280 +            }
   1.281 +            return 0;
   1.282 +        } else {
   1.283 +            return 1;
   1.284 +        }
   1.285 +    } else {
   1.286 +        return ucx_array_reserve(array, capacity);
   1.287 +    }
   1.288  }
   1.289  
   1.290  int ucx_array_reserve(UcxArray* array, size_t capacity) {
   1.291 -    return 1;
   1.292 +    if (array->capacity > capacity) {
   1.293 +        return 0;
   1.294 +    } else {
   1.295 +        void* newptr = alrealloc(array->allocator, array->data,
   1.296 +                capacity*array->elemsize);
   1.297 +        if (newptr) {
   1.298 +            array->data = newptr;
   1.299 +            array->capacity = capacity;
   1.300 +            return 0;
   1.301 +        } else {
   1.302 +            return 1;
   1.303 +        }
   1.304 +    }
   1.305  }
   1.306 -

     2.1 --- a/src/ucx/array.h	Thu Jul 04 21:31:45 2019 +0200
     2.2 +++ b/src/ucx/array.h	Thu Jul 04 22:23:15 2019 +0200
     2.3 @@ -276,17 +276,15 @@
     2.4  int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data);
     2.5  
     2.6  /**
     2.7 - * Sorts a UcxArray with natural merge sort.
     2.8 + * Sorts a UcxArray with an almost in-place merge sort.
     2.9   * 
    2.10 - * This function uses O(n) additional temporary memory for merge operations
    2.11 - * that is automatically freed after each merge.
    2.12 + * This function uses additional memory for exactly one element.
    2.13   * 
    2.14   * @param the array to sort
    2.15   * @param cmpfnc the function that shall be used to compare the element data
    2.16   * @param data additional data for the cmp_func()
    2.17 - * @return zero on success, non-zero if allocation of temporary memory failed
    2.18   */
    2.19 -int ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data);
    2.20 +void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data);
    2.21  
    2.22  /**
    2.23   * Removes an element from the array.

     3.1 --- a/test/array_tests.c	Thu Jul 04 21:31:45 2019 +0200
     3.2 +++ b/test/array_tests.c	Thu Jul 04 22:23:15 2019 +0200
     3.3 @@ -151,19 +151,17 @@
     3.4      
     3.5      UCX_TEST_BEGIN
     3.6      
     3.7 -    UCX_TEST_ASSERT(ucx_array_equals(a1, a2, ucx_cmp_int, NULL) == 0, "failed");
     3.8 -    UCX_TEST_ASSERT(ucx_array_equals(a1, a4, ucx_cmp_int, NULL) > 0, "failed");
     3.9 -    UCX_TEST_ASSERT(ucx_array_equals(a4, a1, ucx_cmp_int, NULL) < 0, "failed");
    3.10 -    UCX_TEST_ASSERT(ucx_array_equals(a1, a3, ucx_cmp_int, NULL) < 0,
    3.11 -            "comparing arrays of different element size failed");
    3.12 -    UCX_TEST_ASSERT(ucx_array_equals(a3, a1, ucx_cmp_int, NULL) > 0,
    3.13 -            "comparing arrays of different element size failed");
    3.14 +    UCX_TEST_ASSERT(ucx_array_equals(a1, a2, ucx_cmp_int, NULL), "failed");
    3.15 +    UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, ucx_cmp_int, NULL), "failed");
    3.16 +    UCX_TEST_ASSERT(!ucx_array_equals(a4, a1, ucx_cmp_int, NULL), "failed");
    3.17 +    UCX_TEST_ASSERT(!ucx_array_equals(a1, a3, ucx_cmp_int, NULL),
    3.18 +            "comparing arrays of different element size shall fail");
    3.19 +    UCX_TEST_ASSERT(!ucx_array_equals(a3, a1, ucx_cmp_int, NULL),
    3.20 +            "comparing arrays of different element size shall fail");
    3.21      
    3.22 -    UCX_TEST_ASSERT(ucx_array_equals(a1, a2, NULL, NULL) == 0,
    3.23 +    UCX_TEST_ASSERT(ucx_array_equals(a1, a2, NULL, NULL),
    3.24              "compare using memcmp() failed");
    3.25 -    UCX_TEST_ASSERT(ucx_array_equals(a1, a4, NULL, NULL) > 0,
    3.26 -            "compare using memcmp() failed");
    3.27 -    UCX_TEST_ASSERT(ucx_array_equals(a4, a1, NULL, NULL) < 0,
    3.28 +    UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, NULL, NULL),
    3.29              "compare using memcmp() failed");
    3.30      
    3.31      UCX_TEST_END
    3.32 @@ -337,11 +335,11 @@
    3.33      UCX_TEST_BEGIN
    3.34  
    3.35      UCX_TEST_ASSERT(array.data != copy.data, "no true copy");
    3.36 -    UCX_TEST_ASSERT(ucx_array_equals(array, copy, ucx_cmp_int, NULL), "failed");
    3.37      UCX_TEST_ASSERT(array.size == copy.size, "size mismatch");
    3.38      UCX_TEST_ASSERT(array.capacity == copy.capacity, "capacity mismatch");
    3.39      UCX_TEST_ASSERT(array.elemsize == copy.elemsize, "element size mismatch");
    3.40      UCX_TEST_ASSERT(array.allocator == copy.allocator, "allocator mismatch");
    3.41 +    UCX_TEST_ASSERT(ucx_array_equals(array, copy, ucx_cmp_int, NULL), "failed");
    3.42      
    3.43      UCX_TEST_END
    3.44  
    3.45 @@ -369,10 +367,22 @@
    3.46  
    3.47      UCX_TEST_BEGIN
    3.48      void* original_ptr = array.data;
    3.49 -    UCX_TEST_ASSERT(!ucx_array_sort(array, ucx_cmp_int, NULL), "failed");
    3.50 -    UCX_TEST_ASSERT(!ucx_array_equals(array, expected, NULL, NULL), "failed");
    3.51 +    ucx_array_sort(array, ucx_cmp_int, NULL);
    3.52 +    UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL), "failed");
    3.53      UCX_TEST_ASSERT(array.size == 5, "size corrupted");
    3.54      UCX_TEST_ASSERT(array.data == original_ptr, "shall not reallocate");
    3.55 +                
    3.56 +    ucx_array_reserve(&array, 32);
    3.57 +    ucx_array_reserve(&expected, 32);
    3.58 +    array.size = expected.size = 32;
    3.59 +    for (size_t i = 0 ; i < 32 ; i++) {
    3.60 +        ucx_array_at_int(array, i) = ((i%2==0)?-1:1) * ((int) i);
    3.61 +        ucx_array_at_int(expected, i) = (-30+2*i) - (i > 15 ? 1 : 0);
    3.62 +    }
    3.63 +    
    3.64 +    ucx_array_sort(array, ucx_cmp_int, NULL);
    3.65 +    UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL),
    3.66 +            "failed for bigger arrays");
    3.67      UCX_TEST_END
    3.68  
    3.69      ucx_array_free(&expected);