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) { |