Re: qsort can get very slow

--3uo+9/B/ebqu+fSQ
Content-Type: multipart/mixed; boundary="BOKacYhQ+x31HxR3"
Content-Disposition: inline


--BOKacYhQ+x31HxR3
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Sun, Feb 19, 2012 at 10:00:57AM -0500, Thomas Dickey wrote:
> On Sun, Feb 19, 2012 at 03:42:02PM +0100, Urs Jan?en wrote:
> > why ever the attachment was missing from the last mail, here it is...
>=20
> thanks.  I'll take a look today regarding the option and (I have as
> usual some updates to configure macros which might be useful).

here's the part with the option added (am starting to work on the other
part...)


--=20
Thomas E. Dickey <[email protected]>
http://invisible-island.net
ftp://invisible-island.net

--BOKacYhQ+x31HxR3
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment; filename="tin-2.1.0+heapsort2.patch"
Content-Transfer-Encoding: quoted-printable

# ftp://invisible-island.net/temp/tin-2.1.0+heapsort2.patch.gz
# patch by Thomas E. Dickey <[email protected]>
# created  Mon Feb 20 10:45:28 UTC 2012
# -------------------------------------------------------------------------=
-----
# configure.in         |   29 +++++++++++++++++++++++++++--
# include/autoconf.hin |    7 ++++++-
# src/heapsort.c       |    4 ++--
# 3 files changed, 35 insertions(+), 5 deletions(-)
# -------------------------------------------------------------------------=
-----
Index: configure.in
--- tin-2.1.0+heapsort+/configure.in	2012-02-19 15:12:38.000000000 +0000
+++ tin-2.1.0+heapsort2/configure.in	2012-02-20 10:35:43.000000000 +0000
@@ -2,7 +2,7 @@
 dnl Module    : configure.in
 dnl Author    : Thomas E. Dickey <[email protected]>
 dnl Created   : 1995-08-24
-dnl Updated   : 2011-12-21
+dnl Updated   : 2012-02-20
 dnl Notes     :
 dnl
 dnl Copyright (c) 1995-2012 Thomas E. Dickey <[email protected]>
@@ -344,6 +344,32 @@
 	AC_MSG_WARN([[None of fcntl(), lockf(), flock() available]])
 fi
=20
+AC_MSG_CHECKING(if you would like to use heapsort)
+CF_ARG_ENABLE(heapsort,
+	[  --enable-heapsort       enable heapsort() as alternative to qsort],
+	[cf_use_heapsort=3Dyes],
+	[cf_use_heapsort=3Dno])
+AC_MSG_RESULT($cf_use_heapsort)
+if test "x$cf_use_heapsort" =3D xyes; then
+	AC_CHECK_FUNCS(heapsort)
+	if test x"$ac_cv_func_heapsort" =3D xyes; then
+		AC_MSG_CHECKING(if its prototype is compatible with qsort)
+		AC_TRY_COMPILE([
+#include <stdlib.h>
+#include <sys/types.h>
+extern int my_compare(const void *, const void *);
+],[
+	char *base =3D 0;
+	heapsort((void *)0, 1, 2, my_compare);
+],,[cf_use_heapsort=3Dno]);
+		AC_MSG_RESULT($cf_use_heapsort)
+	else
+		CF_VERBOSE(will use our own heapsort function)
+	fi
+fi
+if test "x$cf_use_heapsort" =3D xyes; then
+	AC_DEFINE(USE_HEAPSORT)
+fi
=20
 AC_MSG_CHECKING(for screen type)
 AC_ARG_WITH(screen,
@@ -1009,7 +1035,6 @@
 	getcwd \
 	gettimeofday \
 	getwd \
-	heapsort \
 	inet_aton \
 	is_xterm \
 	isascii \
Index: include/autoconf.hin
--- tin-2.1.0+heapsort+/include/autoconf.hin	2012-02-19 15:12:38.000000000 =
+0000
+++ tin-2.1.0+heapsort2/include/autoconf.hin	2012-02-20 10:38:56.000000000 =
+0000
@@ -3,7 +3,7 @@
  *  Module    : autoconf.hin
  *  Author    : Thomas Dickey
  *  Created   : 1995-08-24
- *  Updated   : 2011-12-21
+ *  Updated   : 2012-02-20
  *  Notes     : #include files, #defines & struct's
  *
  * Copyright (c) 1995-2012 Thomas Dickey <[email protected]>
@@ -519,6 +519,11 @@
 #	undef USE_LOCKF
=20
 /*
+ * Define this if we intend to use heapsort as an alternative to qsort.
+ */
+#	undef USE_HEAPSORT
+
+/*
  * Define this if the compiler performs ANSI-style token substitution (use=
d in
  * our 'assert' macro).
  */
Index: src/heapsort.c
--- tin-2.1.0+heapsort+/src/heapsort.c	2012-02-19 15:12:38.000000000 +0000
+++ tin-2.1.0+heapsort2/src/heapsort.c	2012-02-20 10:40:26.000000000 +0000
@@ -42,7 +42,7 @@
 #	endif /* !TIN_H */
 #endif /* 0 */
=20
-#ifndef HAVE_HEAPSORT
+#if defined(USE_HEAPSORT) && !defined(HAVE_HEAPSORT)
 /*
  * Swap two areas of size number of bytes.  Although qsort(3) permits rand=
om
  * blocks of memory to be sorted, sorting pointers is almost certainly the
@@ -193,4 +193,4 @@
 	void)
 {
 }
-#endif /* !HAVE_HEAPSORT */
+#endif /* USE_HEAPSORT && !HAVE_HEAPSORT */

--BOKacYhQ+x31HxR3--

--3uo+9/B/ebqu+fSQ
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAk9CJJYACgkQcCNT4PfkjtsjawCeI09sd3CCInen1W8+AlzQ1TL2
zlEAn2zZFWgR2Ph8/TXQ7IFkyA47q9Xs
=9rpm
-----END PGP SIGNATURE-----

--3uo+9/B/ebqu+fSQ--