Thu, 04 Jul 2019 22:23:15 +0200
implements ucx_array_sort()
src/array.c | file | annotate | diff | comparison | revisions | |
src/ucx/array.h | file | annotate | diff | comparison | revisions | |
test/array_tests.c | file | annotate | diff | comparison | revisions |
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);