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 -
