2 * sgen-qsort.c: Quicksort.
4 * Copyright (C) 2013 Xamarin Inc
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License 2.0 as published by the Free Software Foundation;
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
15 * You should have received a copy of the GNU Library General Public
16 * License 2.0 along with this library; if not, write to the Free
17 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
24 #include "sgen/sgen-gc.h"
26 #define ELEM(i) (((unsigned char*)base) + ((i) * width))
27 #define SWAP(i,j) do { \
28 size_t __i = (i), __j = (j); \
30 memcpy (swap_tmp, ELEM (__i), width); \
31 memcpy (ELEM (__i), ELEM (__j), width); \
32 memcpy (ELEM (__j), swap_tmp, width); \
37 partition (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*), unsigned char *pivot_tmp, unsigned char *swap_tmp)
39 size_t pivot_idx = nel >> 1;
42 memcpy (pivot_tmp, ELEM (pivot_idx), width);
43 SWAP (pivot_idx, nel - 1);
45 for (i = 0; i < nel - 1; ++i) {
46 if (compar (ELEM (i), pivot_tmp) <= 0) {
56 qsort_rec (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*), unsigned char *pivot_tmp, unsigned char *swap_tmp)
63 pivot_idx = partition (base, nel, width, compar, pivot_tmp, swap_tmp);
64 qsort_rec (base, pivot_idx, width, compar, pivot_tmp, swap_tmp);
66 qsort_rec (ELEM (pivot_idx + 1), nel - pivot_idx - 1, width, compar, pivot_tmp, swap_tmp);
70 sgen_qsort (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
73 unsigned char pivot_tmp [width];
74 unsigned char swap_tmp [width];
76 unsigned char* pivot_tmp = (unsigned char*) alloca(width);
77 unsigned char* swap_tmp = (unsigned char*) alloca(width);
80 qsort_rec (base, nel, width, compar, pivot_tmp, swap_tmp);