comparison: src/array.c
src/array.c
- branch
- feature/array
- changeset 345
- 6089eb30a51a
- parent 342
- 8f0a3c00d1d2
- child 346
- 1a9c112f4116
equal
deleted
inserted
replaced
| 344:320b962afaf9 | 345:6089eb30a51a |
|---|---|
| 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | 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 | 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #define _GNU_SOURCE /* we want to use qsort_r(), if available */ | |
| 30 | |
| 29 #include "ucx/array.h" | 31 #include "ucx/array.h" |
| 30 #include "ucx/utils.h" | 32 #include "ucx/utils.h" |
| 31 | 33 |
| 32 #include <string.h> | 34 #include <string.h> |
| 35 #include <stdlib.h> | |
| 36 | |
| 37 #ifndef UCX_ARRAY_DISABLE_QSORT | |
| 38 #if defined(__GLIBC__) | |
| 39 #if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8) | |
| 40 #define ucx_array_sort_impl qsort_r | |
| 41 #endif /* glibc version >= 2.8 */ | |
| 42 #endif /* __GLIBC__ */ | |
| 43 | |
| 44 #if defined(__APPLE__) || defined(__FreeBSD__) | |
| 45 #define ucx_array_sort_impl ucx_qsort_r | |
| 46 #define USE_UCX_QSORT_R | |
| 47 #endif /* __APLE__ or __FreeBSD__ */ | |
| 48 #endif /* UCX_ARRAY_DISABLE_QSORT */ | |
| 49 | |
| 50 #ifndef ucx_array_sort_impl | |
| 51 #define ucx_array_sort_impl ucx_mergesort | |
| 52 #endif | |
| 33 | 53 |
| 34 UcxArray ucx_array_new(size_t capacity, size_t elemsize) { | 54 UcxArray ucx_array_new(size_t capacity, size_t elemsize) { |
| 35 return ucx_array_new_a(capacity, elemsize, ucx_default_allocator()); | 55 return ucx_array_new_a(capacity, elemsize, ucx_default_allocator()); |
| 36 } | 56 } |
| 37 | 57 |
| 210 | 230 |
| 211 int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) { | 231 int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) { |
| 212 return ucx_array_find(array, elem, cmpfnc, data) != array.size; | 232 return ucx_array_find(array, elem, cmpfnc, data) != array.size; |
| 213 } | 233 } |
| 214 | 234 |
| 215 static void ucx_array_merge(UcxArray *array, cmp_func cmpfnc, void *data, | 235 static void ucx_mergesort_merge(void *arrdata,size_t elemsize, |
| 236 cmp_func cmpfnc, void *data, | |
| 216 size_t start, size_t mid, size_t end) { | 237 size_t start, size_t mid, size_t end) { |
| 217 | 238 |
| 239 char* array = arrdata; | |
| 240 | |
| 218 size_t rightstart = mid + 1; | 241 size_t rightstart = mid + 1; |
| 219 | 242 |
| 220 if (cmpfnc(ucx_array_at(*array, mid), | 243 if (cmpfnc(array + mid*elemsize, |
| 221 ucx_array_at(*array, rightstart), data) <= 0) { | 244 array + rightstart*elemsize, data) <= 0) { |
| 222 /* already sorted */ | 245 /* already sorted */ |
| 223 return; | 246 return; |
| 224 } | 247 } |
| 225 | 248 |
| 226 /* we need memory for one element */ | 249 /* we need memory for one element */ |
| 227 void *value = malloc(array->elemsize); | 250 void *value = malloc(elemsize); |
| 228 | 251 |
| 229 while (start <= mid && rightstart <= end) { | 252 while (start <= mid && rightstart <= end) { |
| 230 if (cmpfnc(ucx_array_at(*array, start), | 253 if (cmpfnc(array + start*elemsize, |
| 231 ucx_array_at(*array, rightstart), data) <= 0) { | 254 array + rightstart*elemsize, data) <= 0) { |
| 232 start++; | 255 start++; |
| 233 } else { | 256 } else { |
| 234 /* save the value from the right */ | 257 /* save the value from the right */ |
| 235 memcpy(value, ucx_array_at(*array, rightstart), array->elemsize); | 258 memcpy(value, array + rightstart*elemsize, elemsize); |
| 236 | 259 |
| 237 /* shift all left elements one element to the right */ | 260 /* shift all left elements one element to the right */ |
| 238 size_t shiftcount = rightstart-start; | 261 size_t shiftcount = rightstart-start; |
| 239 void *startptr = ucx_array_at(*array, start); | 262 void *startptr = array + start*elemsize; |
| 240 void *dest = ucx_array_at(*array, start+1); | 263 void *dest = array + (start+1)*elemsize; |
| 241 memmove(dest, startptr, shiftcount*array->elemsize); | 264 memmove(dest, startptr, shiftcount*elemsize); |
| 242 | 265 |
| 243 /* bring the first value from the right to the left */ | 266 /* bring the first value from the right to the left */ |
| 244 memcpy(startptr, value, array->elemsize); | 267 memcpy(startptr, value, elemsize); |
| 245 | 268 |
| 246 start++; | 269 start++; |
| 247 mid++; | 270 mid++; |
| 248 rightstart++; | 271 rightstart++; |
| 249 } | 272 } |
| 251 | 274 |
| 252 /* free the temporary memory */ | 275 /* free the temporary memory */ |
| 253 free(value); | 276 free(value); |
| 254 } | 277 } |
| 255 | 278 |
| 256 static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data, | 279 static void ucx_mergesort_impl(void *arrdata, size_t elemsize, |
| 257 size_t l, size_t r) { | 280 cmp_func cmpfnc, void *data, size_t l, size_t r) { |
| 258 if (l < r) { | 281 if (l < r) { |
| 259 size_t m = l + (r - l) / 2; | 282 size_t m = l + (r - l) / 2; |
| 260 | 283 |
| 261 ucx_array_mergesort(array, cmpfnc, data, l, m); | 284 ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m); |
| 262 ucx_array_mergesort(array, cmpfnc, data, m + 1, r); | 285 ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r); |
| 263 ucx_array_merge(array, cmpfnc, data, l, m, r); | 286 ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r); |
| 264 } | 287 } |
| 265 } | 288 } |
| 266 | 289 |
| 267 void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) { | 290 static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize, |
| 268 ucx_array_mergesort(&array, cmpfnc, data, 0, array.size-1); | 291 cmp_func cmpfnc, void *data) { |
| 292 | |
| 293 ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1); | |
| 294 } | |
| 295 | |
| 296 #ifdef USE_UCX_QSORT_R | |
| 297 struct cmpfnc_swapargs_info { | |
| 298 cmp_func func; | |
| 299 void *data; | |
| 300 }; | |
| 301 | |
| 302 static int cmp_func_swap_args(void *data, const void *x, const void *y) { | |
| 303 cmpfnc_swapargs_info* info = data; | |
| 304 return info->func(x, y, info->data); | |
| 305 } | |
| 306 | |
| 307 static void ucx_qsort_r(void *array, size_t count, size_t elemsize, | |
| 308 cmp_func cmpfnc, void *data) { | |
| 309 struct cmpfnc_swapargs_info info; | |
| 310 info.func = cmpfnc; | |
| 311 info.data = data; | |
| 312 qsort_r(array, count, elemsize, &info, cmp_func_swap_args); | |
| 313 } | |
| 314 #endif /* USE_UCX_QSORT_R */ | |
| 315 | |
| 316 void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) { | |
| 317 ucx_array_sort_impl(array.data, array.size, array.elemsize, cmpfnc, data); | |
| 269 } | 318 } |
| 270 | 319 |
| 271 void ucx_array_remove(UcxArray *array, size_t index) { | 320 void ucx_array_remove(UcxArray *array, size_t index) { |
| 272 array->size--; | 321 array->size--; |
| 273 if (index < array->size) { | 322 if (index < array->size) { |
