# HG changeset patch # User Paul Eggert # Date 1170055401 0 # Node ID d95ff1660f83e53273be67ce3b4ac4491b09c15c # Parent 7dcf8a1f2f5ec3883e3d9abf21748f9253916191 * MODULES.html.sh: New module mpsort. * lib/mpsort.c, lib/mpsort.h, m4/mpsort.m4, modules/mpsort: New files. diff --git a/ChangeLog b/ChangeLog --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,8 @@ 2007-01-28 Paul Eggert + * MODULES.html.sh: New module mpsort. + * lib/mpsort.c, lib/mpsort.h, m4/mpsort.m4, modules/mpsort: New files. + * lib/regex.h (_Restrict_): Renamed from __restrict, to avoid a circularity problem with HP-UX ia64 reported by Bob Proulx in . diff --git a/MODULES.html.sh b/MODULES.html.sh --- a/MODULES.html.sh +++ b/MODULES.html.sh @@ -1540,6 +1540,16 @@ func_module pagealign_alloc func_end_table + element="Sorting functions " + element=`printf "%s" "$element" | sed -e "$sed_lt" -e "$sed_gt"` + func_section_wrap ansic_enh_stdlib_sorting + func_wrap H3 + func_echo "$element" + + func_begin_table + func_module mpsort + func_end_table + element="Date and time " element=`printf "%s" "$element" | sed -e "$sed_lt" -e "$sed_gt"` func_section_wrap ansic_enh_time_datetime diff --git a/lib/mpsort.c b/lib/mpsort.c new file mode 100644 --- /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 + +#include "mpsort.h" + +#include + +/* 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) +{ + return mpsort_with_tmp (base, n, base + n, cmp); +} diff --git a/lib/mpsort.h b/lib/mpsort.h new file mode 100644 --- /dev/null +++ b/lib/mpsort.h @@ -0,0 +1,2 @@ +#include +void mpsort (void const **, size_t, int (*) (void const *, void const *)); diff --git a/m4/mpsort.m4 b/m4/mpsort.m4 new file mode 100644 --- /dev/null +++ b/m4/mpsort.m4 @@ -0,0 +1,13 @@ +# Sort a vector of pointers to data. + +# Copyright (C) 2007 Free Software Foundation, Inc. + +# This file is free software; the Free Software Foundation +# gives unlimited permission to copy and/or distribute it, +# with or without modifications, as long as this notice is preserved. + +AC_DEFUN([gl_MPSORT], +[ + AC_REQUIRE([AC_C_RESTRICT]) + AC_LIBOBJ([mpsort]) +]) diff --git a/modules/mpsort b/modules/mpsort new file mode 100644 --- /dev/null +++ b/modules/mpsort @@ -0,0 +1,23 @@ +Description: +Sort a vector of pointers to data. + +Files: +lib/mpsort.h +lib/mpsort.c +m4/mpsort.m4 + +Depends-on: + +configure.ac: +gl_MPSORT + +Makefile.am: + +Include: +"mpsort.h" + +License: +GPL + +Maintainer: +Paul Eggert