5 * Copyright (C) 2013 Xamarin Inc
7 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
14 #include "sgen/sgen-gc.h"
17 (((unsigned char*)array) + ((i) * element_size))
19 do memmove ((i), (j), element_size); while (0)
22 size_t __i = (i), __j = (j); \
24 SET (swap_tmp, ELEM (__i)); \
25 SET (ELEM (__i), ELEM (__j)); \
26 SET (ELEM (__j), swap_tmp); \
33 const size_t element_size,
34 int (*compare) (const void *, const void *),
37 unsigned char *const pivot_tmp,
38 unsigned char *const swap_tmp)
40 ssize_t left, right, mid, pivot;
44 mid = begin + (end - begin) / 2;
46 /* Choose median of 3 as pivot and pre-sort to avoid O(n^2) case.
54 if (compare (ELEM (mid), ELEM (left)) < 0)
56 if (compare (ELEM (right), ELEM (left)) < 0)
58 if (compare (ELEM (right), ELEM (mid)) < 0)
61 SET (pivot_tmp, ELEM (pivot));
65 while (left <= right && compare (ELEM (left), pivot_tmp) <= 0)
67 while (left <= right && compare (ELEM (right), pivot_tmp) > 0)
77 SET (ELEM (pivot), ELEM (right));
78 SET (ELEM (right), pivot_tmp);
81 /* Recursively sort shorter partition, loop on longer partition. */
82 if (right - begin < end - left) {
109 const size_t element_size,
110 int (*compare) (const void *, const void *))
113 unsigned char pivot_tmp [element_size];
114 unsigned char swap_tmp [element_size];
116 unsigned char *pivot_tmp = (unsigned char *)alloca (element_size);
117 unsigned char *swap_tmp = (unsigned char *)alloca (element_size);