diff options
Diffstat (limited to 'lib/mpsort.c')
| -rw-r--r-- | lib/mpsort.c | 157 |
1 files changed, 157 insertions, 0 deletions
diff --git a/lib/mpsort.c b/lib/mpsort.c new file mode 100644 index 0000000..d6b1e0e --- /dev/null +++ b/lib/mpsort.c @@ -0,0 +1,157 @@ +/* Sort a vector of pointers to data. + + Copyright (C) 2007 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Written by Paul Eggert. */ + +#include <config.h> + +#include "mpsort.h" + +#include <string.h> + +/* The type of qsort-style comparison functions. */ + +typedef int (*comparison_function) (void const *, void const *); + +static void mpsort_with_tmp (void const **restrict, size_t, + void const **restrict, comparison_function); + +/* Sort a vector BASE containing N pointers, placing the sorted array + into TMP. Compare pointers with CMP. N must be at least 2. */ + +static void +mpsort_into_tmp (void const **restrict base, size_t n, + void const **restrict tmp, + comparison_function cmp) +{ + size_t n1 = n / 2; + size_t n2 = n - n1; + size_t a = 0; + size_t alim = n1; + size_t b = n1; + size_t blim = n; + void const *ba; + void const *bb; + + mpsort_with_tmp (base + n1, n2, tmp, cmp); + mpsort_with_tmp (base, n1, tmp, cmp); + + ba = base[a]; + bb = base[b]; + + for (;;) + if (cmp (ba, bb) <= 0) + { + *tmp++ = ba; + a++; + if (a == alim) + { + a = b; + alim = blim; + break; + } + ba = base[a]; + } + else + { + *tmp++ = bb; + b++; + if (b == blim) + break; + bb = base[b]; + } + + memcpy (tmp, base + a, (alim - a) * sizeof *base); +} + +/* Sort a vector BASE containing N pointers, in place. Use TMP + (containing N / 2 pointers) for temporary storage. Compare + pointers with CMP. */ + +static void +mpsort_with_tmp (void const **restrict base, size_t n, + void const **restrict tmp, + comparison_function cmp) +{ + if (n <= 2) + { + if (n == 2) + { + void const *p0 = base[0]; + void const *p1 = base[1]; + if (! (cmp (p0, p1) <= 0)) + { + base[0] = p1; + base[1] = p0; + } + } + } + else + { + size_t n1 = n / 2; + size_t n2 = n - n1; + size_t i; + size_t t = 0; + size_t tlim = n1; + size_t b = n1; + size_t blim = n; + void const *bb; + void const *tt; + + mpsort_with_tmp (base + n1, n2, tmp, cmp); + + if (n1 < 2) + tmp[0] = base[0]; + else + mpsort_into_tmp (base, n1, tmp, cmp); + + tt = tmp[t]; + bb = base[b]; + + for (i = 0; ; ) + if (cmp (tt, bb) <= 0) + { + base[i++] = tt; + t++; + if (t == tlim) + break; + tt = tmp[t]; + } + else + { + base[i++] = bb; + b++; + if (b == blim) + { + memcpy (base + i, tmp + t, (tlim - t) * sizeof *base); + break; + } + bb = base[b]; + } + } +} + +/* Sort a vector BASE containing N pointers, in place. BASE must + contain enough storage to hold N + N / 2 vectors; the trailing + vectors are used for temporaries. Compare pointers with CMP. */ + +void +mpsort (void const **base, size_t n, comparison_function cmp) +{ + mpsort_with_tmp (base, n, base + n, cmp); +} |