From ccc143b9ed802f5b0aa3069423227972de039ba5 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Tue, 10 May 2011 13:20:49 -0600 Subject: Use arrays for PR-tree construction instead of lists. --- libdimension/dimension/array.h | 55 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 54 insertions(+), 1 deletion(-) (limited to 'libdimension/dimension/array.h') diff --git a/libdimension/dimension/array.h b/libdimension/dimension/array.h index 51830e7..18affd7 100644 --- a/libdimension/dimension/array.h +++ b/libdimension/dimension/array.h @@ -27,7 +27,8 @@ #define DIMENSION_ARRAY_H #include /* For size_t */ -#include /* For memcpy */ +#include /* For qsort() */ +#include /* For memcpy() */ /** Dynamic array type. */ typedef struct dmnsn_array { @@ -97,6 +98,38 @@ dmnsn_array_resize(dmnsn_array *array, size_t length) array->length = length; } +/** + * Copy an array. + * @param[in] array The array to copy. + * @return A copy of the array. + */ +DMNSN_INLINE dmnsn_array * +dmnsn_array_copy(const dmnsn_array *array) +{ + dmnsn_array *copy = dmnsn_new_array(array->obj_size); + dmnsn_array_resize(copy, dmnsn_array_size(array)); + memcpy(copy->ptr, array->ptr, dmnsn_array_size(array)*array->obj_size); + return copy; +} + +/** + * Split an array in half. + * @param[in,out] array The array to split. + * @return The second half of the array. + */ +DMNSN_INLINE dmnsn_array * +dmnsn_array_split(dmnsn_array *array) +{ + dmnsn_array *half = dmnsn_new_array(array->obj_size); + size_t new_size = dmnsn_array_size(array)/2; + size_t old_size = dmnsn_array_size(array) - new_size; + dmnsn_array_resize(half, new_size); + memcpy(half->ptr, (char *)array->ptr + old_size*array->obj_size, + new_size*array->obj_size); + dmnsn_array_resize(array, old_size); + return half; +} + /** * Get the i'th element. * @param[in] array The array to access. @@ -240,6 +273,26 @@ dmnsn_array_apply(dmnsn_array *array, dmnsn_callback_fn *callback) } } +/** + * Callback type for array sorting. + * @param[in] a The first element. + * @param[in] b The second element. + * @return A negative value iff a < b, zero iff a == b, and a positive value iff + * a > b. + */ +typedef int dmnsn_array_comparator_fn(const void *a, const void *b); + +/** + * Sort an array. + * @param[in,out] array The array to sort. + * @param[in] comparator The sorting comparator to use. + */ +DMNSN_INLINE void +dmnsn_array_sort(dmnsn_array *array, dmnsn_array_comparator_fn *comparator) +{ + qsort(array->ptr, dmnsn_array_size(array), array->obj_size, comparator); +} + /* Macros to shorten array iteration */ /** -- cgit v1.2.3