1 /* Sort a vector of pointers to data.
3 Copyright (C) 2007 Free Software Foundation, Inc.
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2, or (at your option)
10 This program 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
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License along
16 with this program; if not, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
19 /* Written by Paul Eggert. */
27 /* The type of qsort-style comparison functions. */
29 typedef int (*comparison_function) (void const *, void const *);
31 static void mpsort_with_tmp (void const **restrict, size_t,
32 void const **restrict, comparison_function);
34 /* Sort a vector BASE containing N pointers, placing the sorted array
35 into TMP. Compare pointers with CMP. N must be at least 2. */
38 mpsort_into_tmp (void const **restrict base, size_t n,
39 void const **restrict tmp,
40 comparison_function cmp)
51 mpsort_with_tmp (base + n1, n2, tmp, cmp);
52 mpsort_with_tmp (base, n1, tmp, cmp);
58 if (cmp (ba, bb) <= 0)
79 memcpy (tmp, base + a, (alim - a) * sizeof *base);
82 /* Sort a vector BASE containing N pointers, in place. Use TMP
83 (containing N / 2 pointers) for temporary storage. Compare
87 mpsort_with_tmp (void const **restrict base, size_t n,
88 void const **restrict tmp,
89 comparison_function cmp)
95 void const *p0 = base[0];
96 void const *p1 = base[1];
97 if (! (cmp (p0, p1) <= 0))
116 mpsort_with_tmp (base + n1, n2, tmp, cmp);
121 mpsort_into_tmp (base, n1, tmp, cmp);
127 if (cmp (tt, bb) <= 0)
141 memcpy (base + i, tmp + t, (tlim - t) * sizeof *base);
149 /* Sort a vector BASE containing N pointers, in place. BASE must
150 contain enough storage to hold N + N / 2 vectors; the trailing
151 vectors are used for temporaries. Compare pointers with CMP. */
154 mpsort (void const **base, size_t n, comparison_function cmp)
156 mpsort_with_tmp (base, n, base + n, cmp);