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 3 of the License, or
8 (at your option) any later version.
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
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
18 /* Written by Paul Eggert. */
26 /* The type of qsort-style comparison functions. */
28 typedef int (*comparison_function) (void const *, void const *);
30 static void mpsort_with_tmp (void const **restrict, size_t,
31 void const **restrict, comparison_function);
33 /* Sort a vector BASE containing N pointers, placing the sorted array
34 into TMP. Compare pointers with CMP. N must be at least 2. */
37 mpsort_into_tmp (void const **restrict base, size_t n,
38 void const **restrict tmp,
39 comparison_function cmp)
50 mpsort_with_tmp (base + n1, n2, tmp, cmp);
51 mpsort_with_tmp (base, n1, tmp, cmp);
57 if (cmp (ba, bb) <= 0)
78 memcpy (tmp, base + a, (alim - a) * sizeof *base);
81 /* Sort a vector BASE containing N pointers, in place. Use TMP
82 (containing N / 2 pointers) for temporary storage. Compare
86 mpsort_with_tmp (void const **restrict base, size_t n,
87 void const **restrict tmp,
88 comparison_function cmp)
94 void const *p0 = base[0];
95 void const *p1 = base[1];
96 if (! (cmp (p0, p1) <= 0))
115 mpsort_with_tmp (base + n1, n2, tmp, cmp);
120 mpsort_into_tmp (base, n1, tmp, cmp);
126 if (cmp (tt, bb) <= 0)
140 memcpy (base + i, tmp + t, (tlim - t) * sizeof *base);
148 /* Sort a vector BASE containing N pointers, in place. BASE must
149 contain enough storage to hold N + N / 2 vectors; the trailing
150 vectors are used for temporaries. Compare pointers with CMP. */
153 mpsort (void const **base, size_t n, comparison_function cmp)
155 mpsort_with_tmp (base, n, base + n, cmp);