The NetBSD Project

CVS log for src/lib/libc/stdlib/qsort.c

[BACK] Up to [cvs.NetBSD.org] / src / lib / libc / stdlib

Request diff between arbitrary revisions


Default branch: MAIN
Current tag: MAIN


Revision 1.23 / (download) - annotate - [select for diffs], Fri May 19 19:48:19 2017 UTC (6 years, 11 months ago) by christos
Branch: MAIN
CVS Tags: phil-wifi-base, phil-wifi-20200421, phil-wifi-20200411, phil-wifi-20200406, phil-wifi-20191119, phil-wifi-20190609, phil-wifi, pgoyette-compat-merge-20190127, pgoyette-compat-base, pgoyette-compat-20190127, pgoyette-compat-20190118, pgoyette-compat-1226, pgoyette-compat-1126, pgoyette-compat-1020, pgoyette-compat-0930, pgoyette-compat-0906, pgoyette-compat-0728, pgoyette-compat-0625, pgoyette-compat-0521, pgoyette-compat-0502, pgoyette-compat-0422, pgoyette-compat-0415, pgoyette-compat-0407, pgoyette-compat-0330, pgoyette-compat-0322, pgoyette-compat-0315, pgoyette-compat, perseant-stdc-iso10646-base, perseant-stdc-iso10646, netbsd-9-base, netbsd-9-3-RELEASE, netbsd-9-2-RELEASE, netbsd-9-1-RELEASE, netbsd-9-0-RELEASE, netbsd-9-0-RC2, netbsd-9-0-RC1, netbsd-9, netbsd-8-base, netbsd-8-2-RELEASE, netbsd-8-1-RELEASE, netbsd-8-1-RC1, netbsd-8-0-RELEASE, netbsd-8-0-RC2, netbsd-8-0-RC1, netbsd-8, netbsd-10-base, netbsd-10-0-RELEASE, netbsd-10-0-RC6, netbsd-10-0-RC5, netbsd-10-0-RC4, netbsd-10-0-RC3, netbsd-10-0-RC2, netbsd-10-0-RC1, netbsd-10, matt-nb8-mediatek-base, matt-nb8-mediatek, is-mlppp-base, is-mlppp, cjep_sun2x-base1, cjep_sun2x-base, cjep_sun2x, cjep_staticlib_x-base1, cjep_staticlib_x-base, cjep_staticlib_x, HEAD
Changes since 1.22: +26 -12 lines
Diff to previous 1.22 (colored) to selected 1.6 (colored)

The BSD qsort() performs tail recursion elimination on the second
side of the array being partitioned to save on stack space.  Greater
savings can be gained by choosing recursion for the smaller side
of the partition and eliminating recursion for the larger side.
This also results in a small but measurable performance gain.
(From OpenBSD)

Revision 1.22 / (download) - annotate - [select for diffs], Sat May 26 21:47:05 2012 UTC (11 years, 10 months ago) by christos
Branch: MAIN
CVS Tags: yamt-pagecache-base9, yamt-pagecache-base8, yamt-pagecache-base7, yamt-pagecache-base6, tls-maxphys-base, tls-maxphys, tls-earlyentropy-base, tls-earlyentropy, riastradh-xf86-video-intel-2-7-1-pre-2-21-15, riastradh-drm2-base3, riastradh-drm2-base2, riastradh-drm2-base1, riastradh-drm2-base, riastradh-drm2, prg-localcount2-base3, prg-localcount2-base2, prg-localcount2-base1, prg-localcount2-base, prg-localcount2, pgoyette-localcount-base, pgoyette-localcount-20170426, pgoyette-localcount-20170320, pgoyette-localcount-20170107, pgoyette-localcount-20161104, pgoyette-localcount-20160806, pgoyette-localcount-20160726, pgoyette-localcount, netbsd-7-nhusb-base-20170116, netbsd-7-nhusb-base, netbsd-7-nhusb, netbsd-7-base, netbsd-7-2-RELEASE, netbsd-7-1-RELEASE, netbsd-7-1-RC2, netbsd-7-1-RC1, netbsd-7-1-2-RELEASE, netbsd-7-1-1-RELEASE, netbsd-7-1, netbsd-7-0-RELEASE, netbsd-7-0-RC3, netbsd-7-0-RC2, netbsd-7-0-RC1, netbsd-7-0-2-RELEASE, netbsd-7-0-1-RELEASE, netbsd-7-0, netbsd-7, localcount-20160914, bouyer-socketcan-base1, bouyer-socketcan-base, bouyer-socketcan, agc-symver-base, agc-symver
Changes since 1.21: +3 -3 lines
Diff to previous 1.21 (colored) to selected 1.6 (colored)

don't trigger diagassert for a null array with 0 elements or 0 elementsize.

Revision 1.21 / (download) - annotate - [select for diffs], Wed May 18 19:36:36 2011 UTC (12 years, 11 months ago) by dsl
Branch: MAIN
CVS Tags: yamt-pagecache-base5, yamt-pagecache-base4, yamt-pagecache-base3, yamt-pagecache-base2, yamt-pagecache-base, netbsd-6-base, netbsd-6-1-RELEASE, netbsd-6-1-RC4, netbsd-6-1-RC3, netbsd-6-1-RC2, netbsd-6-1-RC1, netbsd-6-1-5-RELEASE, netbsd-6-1-4-RELEASE, netbsd-6-1-3-RELEASE, netbsd-6-1-2-RELEASE, netbsd-6-1-1-RELEASE, netbsd-6-1, netbsd-6-0-RELEASE, netbsd-6-0-RC2, netbsd-6-0-RC1, netbsd-6-0-6-RELEASE, netbsd-6-0-5-RELEASE, netbsd-6-0-4-RELEASE, netbsd-6-0-3-RELEASE, netbsd-6-0-2-RELEASE, netbsd-6-0-1-RELEASE, netbsd-6-0, netbsd-6, matt-nb6-plus-nbase, matt-nb6-plus-base, matt-nb6-plus, cherry-xenmp-base, cherry-xenmp
Branch point for: yamt-pagecache
Changes since 1.20: +7 -7 lines
Diff to previous 1.20 (colored) to selected 1.6 (colored)

Remove __P()

Revision 1.20 / (download) - annotate - [select for diffs], Mon Jun 1 06:37:40 2009 UTC (14 years, 10 months ago) by yamt
Branch: MAIN
CVS Tags: matt-premerge-20091211, matt-mips64-premerge-20101231, bouyer-quota2-nbase, bouyer-quota2-base, bouyer-quota2
Changes since 1.19: +3 -14 lines
Diff to previous 1.19 (colored) to selected 1.6 (colored)

qsort: remove the "switch to insertion sort" optimization because it
causes catastrophic performance for certain inputs.

Revision 1.19 / (download) - annotate - [select for diffs], Fri Jan 30 23:38:44 2009 UTC (15 years, 2 months ago) by lukem
Branch: MAIN
CVS Tags: jym-xensuspend-nbase, jym-xensuspend-base, jym-xensuspend
Changes since 1.18: +3 -3 lines
Diff to previous 1.18 (colored) to selected 1.6 (colored)

sign-compare fix

Revision 1.18 / (download) - annotate - [select for diffs], Sun Jan 11 02:46:30 2009 UTC (15 years, 3 months ago) by christos
Branch: MAIN
Changes since 1.17: +2 -2 lines
Diff to previous 1.17 (colored) to selected 1.6 (colored)

merge christos-time_t

Revision 1.17 / (download) - annotate - [select for diffs], Sun Nov 16 16:15:58 2008 UTC (15 years, 5 months ago) by ad
Branch: MAIN
CVS Tags: christos-time_t-nbase, christos-time_t-base
Changes since 1.16: +2 -2 lines
Diff to previous 1.16 (colored) to selected 1.6 (colored)

Our qsort() is inappropriate for kernel use because it makes recursive
calls. Replace it with a kheapsort() function in kernel. Pointed out
by tron@.

Revision 1.16, Sun Nov 16 15:01:26 2008 UTC (15 years, 5 months ago) by ad
Branch: MAIN
Changes since 1.15: +2 -2 lines
FILE REMOVED

Make qsort() available in libkern.

Revision 1.15 / (download) - annotate - [select for diffs], Tue Mar 11 18:04:59 2008 UTC (16 years, 1 month ago) by rmind
Branch: MAIN
CVS Tags: yamt-pf42-baseX, yamt-pf42-base4, yamt-pf42-base3, yamt-pf42-base2, yamt-pf42-base, yamt-pf42, wrstuden-revivesa-base-3, wrstuden-revivesa-base-2, wrstuden-revivesa-base-1, wrstuden-revivesa-base, wrstuden-revivesa, netbsd-5-base, netbsd-5-2-RELEASE, netbsd-5-2-RC1, netbsd-5-2-3-RELEASE, netbsd-5-2-2-RELEASE, netbsd-5-2-1-RELEASE, netbsd-5-2, netbsd-5-1-RELEASE, netbsd-5-1-RC4, netbsd-5-1-RC3, netbsd-5-1-RC2, netbsd-5-1-RC1, netbsd-5-1-5-RELEASE, netbsd-5-1-4-RELEASE, netbsd-5-1-3-RELEASE, netbsd-5-1-2-RELEASE, netbsd-5-1-1-RELEASE, netbsd-5-1, netbsd-5-0-RELEASE, netbsd-5-0-RC4, netbsd-5-0-RC3, netbsd-5-0-RC2, netbsd-5-0-RC1, netbsd-5-0-2-RELEASE, netbsd-5-0-1-RELEASE, netbsd-5-0, netbsd-5, matt-nb5-pq3-base, matt-nb5-pq3, matt-nb5-mips64-u2-k2-k4-k7-k8-k9, matt-nb5-mips64-u1-k1-k5, matt-nb5-mips64-premerge-20101231, matt-nb5-mips64-premerge-20091211, matt-nb5-mips64-k15, matt-nb5-mips64, matt-nb4-mips64-k7-u2a-k9b, matt-mips64-base2, matt-armv6-nbase, keiichi-mipv6-base, hpcarm-cleanup-nbase
Branch point for: christos-time_t
Changes since 1.14: +15 -18 lines
Diff to previous 1.14 (colored) to selected 1.6 (colored)

Use size_t to avoid overflow when sorting large arrays. While here, ANSIfy.
Obtained from FreeBSD (das@).

Revision 1.14 / (download) - annotate - [select for diffs], Sat Dec 24 21:11:16 2005 UTC (18 years, 3 months ago) by perry
Branch: MAIN
CVS Tags: wrstuden-fixsa-newbase, wrstuden-fixsa-base-1, wrstuden-fixsa-base, wrstuden-fixsa, netbsd-4-base, netbsd-4-0-RELEASE, netbsd-4-0-RC5, netbsd-4-0-RC4, netbsd-4-0-RC3, netbsd-4-0-RC2, netbsd-4-0-RC1, netbsd-4-0-1-RELEASE, netbsd-4-0, netbsd-4, matt-mips64-base, matt-mips64, matt-armv6-prevmlocking, matt-armv6-base, hpcarm-cleanup-base, hpcarm-cleanup, cube-autoconf-base, cube-autoconf, abandoned-netbsd-4-base, abandoned-netbsd-4
Branch point for: matt-armv6, keiichi-mipv6
Changes since 1.13: +6 -6 lines
Diff to previous 1.13 (colored) to selected 1.6 (colored)

Remove leading __ from __(const|inline|signed|volatile) -- it is obsolete.

Revision 1.13 / (download) - annotate - [select for diffs], Thu Aug 7 16:43:42 2003 UTC (20 years, 8 months ago) by agc
Branch: MAIN
CVS Tags: netbsd-3-base, netbsd-3-1-RELEASE, netbsd-3-1-RC4, netbsd-3-1-RC3, netbsd-3-1-RC2, netbsd-3-1-RC1, netbsd-3-1-1-RELEASE, netbsd-3-1, netbsd-3-0-RELEASE, netbsd-3-0-RC6, netbsd-3-0-RC5, netbsd-3-0-RC4, netbsd-3-0-RC3, netbsd-3-0-RC2, netbsd-3-0-RC1, netbsd-3-0-3-RELEASE, netbsd-3-0-2-RELEASE, netbsd-3-0-1-RELEASE, netbsd-3-0, netbsd-3, netbsd-2-base, netbsd-2-1-RELEASE, netbsd-2-1-RC6, netbsd-2-1-RC5, netbsd-2-1-RC4, netbsd-2-1-RC3, netbsd-2-1-RC2, netbsd-2-1-RC1, netbsd-2-1, netbsd-2-0-base, netbsd-2-0-RELEASE, netbsd-2-0-RC5, netbsd-2-0-RC4, netbsd-2-0-RC3, netbsd-2-0-RC2, netbsd-2-0-RC1, netbsd-2-0-3-RELEASE, netbsd-2-0-2-RELEASE, netbsd-2-0-1-RELEASE, netbsd-2-0, netbsd-2
Changes since 1.12: +3 -7 lines
Diff to previous 1.12 (colored) to selected 1.6 (colored)

Move UCB-licensed code from 4-clause to 3-clause licence.

Patches provided by Joel Baker in PR 22280, verified by myself.

Revision 1.12 / (download) - annotate - [select for diffs], Mon Sep 20 04:39:40 1999 UTC (24 years, 7 months ago) by lukem
Branch: MAIN
CVS Tags: wrstuden-devbsize-base, wrstuden-devbsize-19991221, wrstuden-devbsize, netbsd-1-6-base, netbsd-1-6-RELEASE, netbsd-1-6-RC3, netbsd-1-6-RC2, netbsd-1-6-RC1, netbsd-1-6-PATCH002-RELEASE, netbsd-1-6-PATCH002-RC4, netbsd-1-6-PATCH002-RC3, netbsd-1-6-PATCH002-RC2, netbsd-1-6-PATCH002-RC1, netbsd-1-6-PATCH002, netbsd-1-6-PATCH001-RELEASE, netbsd-1-6-PATCH001-RC3, netbsd-1-6-PATCH001-RC2, netbsd-1-6-PATCH001-RC1, netbsd-1-6-PATCH001, netbsd-1-6, netbsd-1-5-base, netbsd-1-5-RELEASE, netbsd-1-5-PATCH003, netbsd-1-5-PATCH002, netbsd-1-5-PATCH001, netbsd-1-5-BETA2, netbsd-1-5-BETA, netbsd-1-5-ALPHA2, netbsd-1-5, nathanw_sa_end, nathanw_sa_before_merge, nathanw_sa_base, nathanw_sa, minoura-xpg4dl-base, minoura-xpg4dl, fvdl_fs64_base, comdex-fall-1999-base, comdex-fall-1999
Changes since 1.11: +2 -8 lines
Diff to previous 1.11 (colored) to selected 1.6 (colored)

back out the #ifdef _DIAGNOSTIC argument checks; too many people complained.
_DIAGASSERT() is still retained.

Revision 1.11 / (download) - annotate - [select for diffs], Thu Sep 16 11:45:35 1999 UTC (24 years, 7 months ago) by lukem
Branch: MAIN
Changes since 1.10: +14 -2 lines
Diff to previous 1.10 (colored) to selected 1.6 (colored)

* use _DIAGASSERT() to check pointer arguments against NULL and file
  descriptors against -1 (as appropriate).
* add actual checks which to detect stuff that would trigger_DIAGASSERT(),
  and attempt to return a sane error condition.
* knf some code
* remove some `register' decls.

the first two items result in the addition of code similar to the
following in various functions:

		_DIAGASSERT(path != NULL)
	#ifdef _DIAGNOSTIC
		if (path == NULL) {
			errno = EFAULT;
			return (-1);
		}
	#endif

Revision 1.10 / (download) - annotate - [select for diffs], Sun Nov 15 17:13:51 1998 UTC (25 years, 5 months ago) by christos
Branch: MAIN
CVS Tags: netbsd-1-4-base, netbsd-1-4-RELEASE, netbsd-1-4-PATCH003, netbsd-1-4-PATCH002, netbsd-1-4-PATCH001, netbsd-1-4
Changes since 1.9: +16 -15 lines
Diff to previous 1.9 (colored) to selected 1.6 (colored)

delint

Revision 1.9 / (download) - annotate - [select for diffs], Tue Feb 3 18:44:18 1998 UTC (26 years, 2 months ago) by perry
Branch: MAIN
Changes since 1.8: +5 -5 lines
Diff to previous 1.8 (colored) to selected 1.6 (colored)

remove obsolete register declarations

Revision 1.8 / (download) - annotate - [select for diffs], Sun Jul 13 20:16:51 1997 UTC (26 years, 9 months ago) by christos
Branch: MAIN
CVS Tags: netbsd-1-3-base, netbsd-1-3-RELEASE, netbsd-1-3-PATCH003-CANDIDATE2, netbsd-1-3-PATCH003-CANDIDATE1, netbsd-1-3-PATCH003-CANDIDATE0, netbsd-1-3-PATCH003, netbsd-1-3-PATCH002, netbsd-1-3-PATCH001, netbsd-1-3-BETA, netbsd-1-3
Changes since 1.7: +7 -5 lines
Diff to previous 1.7 (colored) to selected 1.6 (colored)

Add local.h for local prototypes.
Fix namespace issues for strtoq and strtouq
Fix gcc warnings.
Fix RCSID's

Revision 1.7 / (download) - annotate - [select for diffs], Thu Jun 19 07:41:33 1997 UTC (26 years, 10 months ago) by mikel
Branch: MAIN
Changes since 1.6: +13 -13 lines
Diff to previous 1.6 (colored)

avoid unportable arithmetic on void pointers

Revision 1.6 / (download) - annotate - [selected], Thu Dec 19 07:56:33 1996 UTC (27 years, 4 months ago) by cgd
Branch: MAIN
Changes since 1.5: +6 -6 lines
Diff to previous 1.5 (colored)

use __inline and __asm, rather than inline and asm.  By default (without -g)
lint won't accept the latter two, but will accept the former two as valid.
As far as gcc's concerned, they're the same.

Revision 1.5 / (download) - annotate - [select for diffs], Thu Dec 28 08:52:36 1995 UTC (28 years, 3 months ago) by thorpej
Branch: MAIN
CVS Tags: nsswitch, netbsd-1-2-base, netbsd-1-2-RELEASE, netbsd-1-2-PATCH001, netbsd-1-2-BETA, netbsd-1-2, ivory_soap2
Changes since 1.4: +7 -2 lines
Diff to previous 1.4 (colored) to selected 1.6 (colored)

New-style RCS ids.

Revision 1.4 / (download) - annotate - [select for diffs], Thu Jun 16 05:26:39 1994 UTC (29 years, 10 months ago) by mycroft
Branch: MAIN
CVS Tags: netbsd-1-1-base, netbsd-1-1-RELEASE, netbsd-1-1-PATCH001, netbsd-1-1, netbsd-1-0-base, netbsd-1-0-RELEASE, netbsd-1-0-PATCH1, netbsd-1-0-PATCH06, netbsd-1-0-PATCH05, netbsd-1-0-PATCH04, netbsd-1-0-PATCH03, netbsd-1-0-PATCH02, netbsd-1-0-PATCH0, netbsd-1-0, ivory_soap
Changes since 1.3: +114 -215 lines
Diff to previous 1.3 (colored) to selected 1.6 (colored)

Add RCS ids.

Revision 1.3 / (download) - annotate - [select for diffs], Thu Aug 26 00:48:06 1993 UTC (30 years, 7 months ago) by jtc
Branch: MAIN
Changes since 1.2: +2 -2 lines
Diff to previous 1.2 (colored) to selected 1.6 (colored)

Declare rcsid strings so they are stored in text segment.

Revision 1.2 / (download) - annotate - [select for diffs], Sun Aug 1 18:37:00 1993 UTC (30 years, 8 months ago) by mycroft
Branch: MAIN
Changes since 1.1: +2 -1 lines
Diff to previous 1.1 (colored) to selected 1.6 (colored)

Add RCS identifiers.

Revision 1.1 / (download) - annotate - [select for diffs], Sun Mar 21 09:45:37 1993 UTC (31 years, 1 month ago) by cgd
Branch: MAIN
Diff to selected 1.6 (colored)

Initial revision

This form allows you to request diff's between any two revisions of a file. You may select a symbolic revision name using the selection box or you may type in a numeric name using the type-in text box.




CVSweb <webmaster@jp.NetBSD.org>