annotate lib-src/qsort.c @ 2367:ecf1ebac70d8

[xemacs-hg @ 2004-11-04 23:05:23 by ben] commit mega-patch configure.in: Turn off -Winline and -Wchar-subscripts. Use the right set of cflags when compiling modules. Rewrite ldap configuration to separate the inclusion of lber (needed in recent Cygwin) from the basic checks for the needed libraries. add a function for MAKE_JUNK_C; initially code was added to generate xemacs.def using this, but it will need to be rewritten. add an rm -f for junk.c to avoid weird Cygwin bug with cp -f onto an existing file. Sort list of auto-detected functions and eliminate unused checks for stpcpy, setlocale and getwd. Add autodetection of Cygwin scanf problems BETA: Rewrite section on configure to indicate what flags are important and what not. digest-doc.c, make-dump-id.c, profile.c, sorted-doc.c: Add proper decls for main(). make-msgfile.c: Document that this is old junk. Move proposal to text.c. make-msgfile.lex: Move proposal to text.c. make-mswin-unicode.pl: Convert error-generating code so that the entire message will be seen as a single unrecognized token. mule/mule-ccl.el: Update docs. lispref/mule.texi: Update CCL docs. ldap/eldap.c: Mule-ize. Use EXTERNAL_LIST_LOOP_2 instead of deleted EXTERNAL_LIST_LOOP. * XEmacs 21.5.18 "chestnut" is released. --------------------------------------------------------------- MULE-RELATED WORK: --------------------------------------------------------------- --------------------------- byte-char conversion --------------------------- buffer.c, buffer.h, insdel.c, text.c: Port FSF algorithm for byte-char conversion, replacing broken previous version. Track the char position of the gap. Add functions to do char-byte conversion downwards as well as upwards. Move comments about algorithm workings to internals manual. --------------------------- work on types --------------------------- alloc.c, console-x-impl.h, dump-data.c, dump-data.h, dumper.c, dialog-msw.c, dired-msw.c, doc.c, editfns.c, esd.c, event-gtk.h, event-msw.c, events.c, file-coding.c, file-coding.h, fns.c, glyphs-eimage.c, glyphs-gtk.c, glyphs-msw.c, glyphs-shared.c, glyphs-x.c, glyphs.c, glyphs.h, gui.c, hpplay.c, imgproc.c, intl-win32.c, lrecord.h, lstream.c, keymap.c, lisp.h, libsst.c, linuxplay.c, miscplay.c, miscplay.h, mule-coding.c, nas.c, nt.c, ntheap.c, ntplay.c, objects-msw.c, objects-tty.c, objects-x.c, print.c, process-nt.c, process.c, redisplay.h, select-common.h, select-gtk.c, select-x.c, sgiplay.c, sound.c, sound.h, sunplay.c, sysfile.h, sysdep.c, syswindows.h, text.c, unexnt.c, win32.c, xgccache.c: Further work on types. This creates a full set of types for all the basic semantics of `char' that I have so far identified, so that its semantics can always be identified for the purposes of proper Mule-safe code, and the raw use of `char' always avoided. (1) More type renaming, for consistency of naming. Char_ASCII -> Ascbyte UChar_ASCII -> UAscbyte Char_Binary -> CBinbyte UChar_Binary -> Binbyte SChar_Binary -> SBinbyte (2) Introduce Rawbyte, CRawbyte, Boolbyte, Chbyte, UChbyte, and Bitbyte and use them. (3) New types Itext, Wexttext and Textcount for separating out the concepts of bytes and textual units (different under UTF-16 and UTF-32, which are potential internal encodings). (4) qxestr*_c -> qxestr*_ascii. lisp.h: New; goes with other qxe() functions. #### Maybe goes in a different section. lisp.h: Group generic int-type defs together with EMACS_INT defs. lisp.h: * lisp.h (WEXTTEXT_IS_WIDE) New defns. lisp.h: New type to replace places where int occurs as a boolean. It's signed because occasionally people may want to use -1 as an error value, and because unsigned ints are viral -- see comments in the internals manual against using them. dynarr.c: int -> Bytecount. --------------------------- Mule-izing --------------------------- device-x.c: Partially Mule-ize. dumper.c, dumper.h: Mule-ize. Use Rawbyte. Use stderr_out not printf. Use wext_*(). sysdep.c, syswindows.h, text.c: New Wexttext API for manipulation of external text that may be Unicode (e.g. startup code under Windows). emacs.c: Mule-ize. Properly deal with argv in external encoding. Use wext_*() and Wexttext. Use Rawbyte. #if 0 some old junk on SCO that is unlikely to be correct. Rewrite allocation code in run-temacs. emacs.c, symsinit.h, win32.c: Rename win32 init function and call it even earlier, to initialize mswindows_9x_p even earlier, for use in startup code (XEUNICODE_P). process.c: Use _wenviron not environ under Windows, to get Unicode environment variables. event-Xt.c: Mule-ize drag-n-drop related stuff. dragdrop.c, dragdrop.h, frame-x.c: Mule-ize. text.h: Add some more stand-in defines for particular kinds of conversion; use in Mule-ization work in frame-x.c etc. --------------------------- Freshening --------------------------- intl-auto-encap-win32.c, intl-auto-encap-win32.h: Regenerate. --------------------------- Unicode-work --------------------------- intl-win32.c, syswindows.h: Factor out common options to MultiByteToWideChar and WideCharToMultiByte. Add convert_unicode_to_multibyte_malloc() and convert_unicode_to_multibyte_dynarr() and use. Add stuff for alloca() conversion of multibyte/unicode. alloc.c: Use dfc_external_data_len() in case of unicode coding system. alloc.c, mule-charset.c: Don't zero out and reinit charset Unicode tables. This fucks up dump-time loading. Anyway, either we load them at dump time or run time, never both. unicode.c: Dump the blank tables as well. --------------------------------------------------------------- DOCUMENTATION, MOSTLY MULE-RELATED: --------------------------------------------------------------- EmacsFrame.c, emodules.c, event-Xt.c, fileio.c, input-method-xlib.c, mule-wnnfns.c, redisplay-gtk.c, redisplay-tty.c, redisplay-x.c, regex.c, sysdep.c: Add comment about Mule work needed. text.h: Add more documentation describing why DFC routines were not written to return their value. Add some other DFC documentation. console-msw.c, console-msw.h: Add pointer to docs in win32.c. emacs.c: Add comments on sources of doc info. text.c, charset.h, unicode.c, intl-win32.c, intl-encap-win32.c, text.h, file-coding.c, mule-coding.c: Collect background comments and related to text matters and internationalization, and proposals for work to be done, in text.c or Internals manual, stuff related to specific textual API's in text.h, and stuff related to internal implementation of Unicode conversion in unicode.c. Put lots of pointers to the comments to make them easier to find. s/mingw32.h, s/win32-common.h, s/win32-native.h, s/windowsnt.h, win32.c: Add bunches of new documentation on the different kinds of builds and environments under Windows and how they work. Collect this info in win32.c. Add pointers to these docs in the relevant s/* files. emacs.c: Document places with long comments. Remove comment about exiting, move to internals manual, put in pointer. event-stream.c: Move docs about event queues and focus to internals manual, put in pointer. events.h: Move docs about event stream callbacks to internals manual, put in pointer. profile.c, redisplay.c, signal.c: Move documentation to the Internals manual. process-nt.c: Add pointer to comment in win32-native.el. lisp.h: Add comments about some comment conventions. lisp.h: Add comment about the second argument. device-msw.c, redisplay-msw.c: @@#### comments are out-of-date. --------------------------------------------------------------- PDUMP WORK (MOTIVATED BY UNICODE CHANGES) --------------------------------------------------------------- alloc.c, buffer.c, bytecode.c, console-impl.h, console.c, device.c, dumper.c, lrecord.h, elhash.c, emodules.h, events.c, extents.c, frame.c, glyphs.c, glyphs.h, mule-charset.c, mule-coding.c, objects.c, profile.c, rangetab.c, redisplay.c, specifier.c, specifier.h, window.c, lstream.c, file-coding.h, file-coding.c: PDUMP: Properly implement dump_add_root_block(), which never worked before, and is necessary for dumping Unicode tables. Pdump name changes for accuracy: XD_STRUCT_PTR -> XD_BLOCK_PTR. XD_STRUCT_ARRAY -> XD_BLOCK_ARRAY. XD_C_STRING -> XD_ASCII_STRING. *_structure_* -> *_block_*. lrecord.h: some comments added about dump_add_root_block() vs dump_add_root_block_ptr(). extents.c: remove incorrect comment about pdump problems with gap array. --------------------------------------------------------------- ALLOCATION --------------------------------------------------------------- abbrev.c, alloc.c, bytecode.c, casefiddle.c, device-msw.c, device-x.c, dired-msw.c, doc.c, doprnt.c, dragdrop.c, editfns.c, emodules.c, file-coding.c, fileio.c, filelock.c, fns.c, glyphs-eimage.c, glyphs-gtk.c, glyphs-msw.c, glyphs-x.c, gui-msw.c, gui-x.c, imgproc.c, intl-win32.c, lread.c, menubar-gtk.c, menubar.c, nt.c, objects-msw.c, objects-x.c, print.c, process-nt.c, process-unix.c, process.c, realpath.c, redisplay.c, search.c, select-common.c, symbols.c, sysdep.c, syswindows.h, text.c, text.h, ui-byhand.c: New macros {alloca,xnew}_{itext,{i,ext,raw,bin,asc}bytes} for more convenient allocation of these commonly requested items. Modify functions to use alloca_ibytes, alloca_array, alloca_extbytes, xnew_ibytes, etc. also XREALLOC_ARRAY, xnew. alloc.c: Rewrite the allocation functions to factor out repeated code. Add assertions for freeing dumped data. lisp.h: Moved down and consolidated with other allocation stuff. lisp.h, dynarr.c: New functions for allocation that's very efficient when mostly in LIFO order. lisp.h, text.c, text.h: Factor out some stuff for general use by alloca()-conversion funs. text.h, lisp.h: Fill out convenience routines for allocating various kinds of bytes and put them in lisp.h. Use them in place of xmalloc(), ALLOCA(). text.h: Fill out the convenience functions so the _MALLOC() kinds match the alloca() kinds. --------------------------------------------------------------- ERROR-CHECKING --------------------------------------------------------------- text.h: Create ASSERT_ASCTEXT_ASCII() and ASSERT_ASCTEXT_ASCII_LEN() from similar Eistring checkers and change the Eistring checkers to use them instead. --------------------------------------------------------------- MACROS IN LISP.H --------------------------------------------------------------- lisp.h: Redo GCPRO declarations. Create a "base" set of functions that can be used to generate any kind of gcpro sets -- regular, ngcpro, nngcpro, private ones used in GC_EXTERNAL_LIST_LOOP_2. buffer.c, callint.c, chartab.c, console-msw.c, device-x.c, dialog-msw.c, dired.c, extents.c, ui-gtk.c, rangetab.c, nt.c, mule-coding.c, minibuf.c, menubar-msw.c, menubar.c, menubar-gtk.c, lread.c, lisp.h, gutter.c, glyphs.c, glyphs-widget.c, fns.c, fileio.c, file-coding.c, specifier.c: Eliminate EXTERNAL_LIST_LOOP, which does not check for circularities. Use EXTERNAL_LIST_LOOP_2 instead or EXTERNAL_LIST_LOOP_3 or EXTERNAL_PROPERTY_LIST_LOOP_3 or GC_EXTERNAL_LIST_LOOP_2 (new macro). Removed/redid comments on EXTERNAL_LIST_LOOP. --------------------------------------------------------------- SPACING FIXES --------------------------------------------------------------- callint.c, hftctl.c, number-gmp.c, process-unix.c: Spacing fixes. --------------------------------------------------------------- FIX FOR GEOMETRY PROBLEM IN FIRST FRAME --------------------------------------------------------------- unicode.c: Add workaround for newlib bug in sscanf() [should be fixed by release 1.5.12 of Cygwin]. toolbar.c: bug fix for problem of initial frame being 77 chars wide on Windows. will be overridden by my other ws. --------------------------------------------------------------- FIX FOR LEAKING PROCESS HANDLES: --------------------------------------------------------------- process-nt.c: Fixes for leaking handles. Inspired by work done by Adrian Aichner <adrian@xemacs.org>. --------------------------------------------------------------- FIX FOR CYGWIN BUG (Unicode-related): --------------------------------------------------------------- unicode.c: Add workaround for newlib bug in sscanf() [should be fixed by release 1.5.12 of Cygwin]. --------------------------------------------------------------- WARNING FIXES: --------------------------------------------------------------- console-stream.c: `reinit' is unused. compiler.h, event-msw.c, frame-msw.c, intl-encap-win32.c, text.h: Add stuff to deal with ANSI-aliasing warnings I got. regex.c: Gather includes together to avoid warning. --------------------------------------------------------------- CHANGES TO INITIALIZATION ROUTINES: --------------------------------------------------------------- buffer.c, emacs.c, console.c, debug.c, device-x.c, device.c, dragdrop.c, emodules.c, eval.c, event-Xt.c, event-gtk.c, event-msw.c, event-stream.c, event-tty.c, events.c, extents.c, faces.c, file-coding.c, fileio.c, font-lock.c, frame-msw.c, glyphs-widget.c, glyphs.c, gui-x.c, insdel.c, lread.c, lstream.c, menubar-gtk.c, menubar-x.c, minibuf.c, mule-wnnfns.c, objects-msw.c, objects.c, print.c, scrollbar-x.c, search.c, select-x.c, text.c, undo.c, unicode.c, window.c, symsinit.h: Call reinit_*() functions directly from emacs.c, for clarity. Factor out some redundant init code. Move disallowed stuff that had crept into vars_of_glyphs() into complex_vars_of_glyphs(). Call init_eval_semi_early() from eval.c not in the middle of vars_of_() in emacs.c since there should be no order dependency in the latter calls. --------------------------------------------------------------- ARMAGEDDON: --------------------------------------------------------------- alloc.c, emacs.c, lisp.h, print.c: Rename inhibit_non_essential_printing_operations to inhibit_non_essential_conversion_operations. text.c: Assert on !inhibit_non_essential_conversion_operations. console-msw.c, print.c: Don't do conversion in SetConsoleTitle or FindWindow to avoid problems during armageddon. Put #errors for NON_ASCII_INTERNAL_FORMAT in places where problems would arise. --------------------------------------------------------------- CHANGES TO THE BUILD PROCEDURE: --------------------------------------------------------------- config.h.in, s/cxux.h, s/usg5-4-2.h, m/powerpc.h: Add comment about correct ordering of this file. Rearrange everything to follow this -- put all #undefs together and before the s&m files. Add undefs for HAVE_ALLOCA, C_ALLOCA, BROKEN_ALLOCA_IN_FUNCTION_CALLS, STACK_DIRECTION. Remove unused HAVE_STPCPY, HAVE_GETWD, HAVE_SETLOCALE. m/gec63.h: Deleted; totally broken, not used at all, not in FSF. m/7300.h, m/acorn.h, m/alliant-2800.h, m/alliant.h, m/altos.h, m/amdahl.h, m/apollo.h, m/att3b.h, m/aviion.h, m/celerity.h, m/clipper.h, m/cnvrgnt.h, m/convex.h, m/cydra5.h, m/delta.h, m/delta88k.h, m/dpx2.h, m/elxsi.h, m/ews4800r.h, m/gould.h, m/hp300bsd.h, m/hp800.h, m/hp9000s300.h, m/i860.h, m/ibmps2-aix.h, m/ibmrs6000.h, m/ibmrt-aix.h, m/ibmrt.h, m/intel386.h, m/iris4d.h, m/iris5d.h, m/iris6d.h, m/irist.h, m/isi-ov.h, m/luna88k.h, m/m68k.h, m/masscomp.h, m/mg1.h, m/mips-nec.h, m/mips-siemens.h, m/mips.h, m/news.h, m/nh3000.h, m/nh4000.h, m/ns32000.h, m/orion105.h, m/pfa50.h, m/plexus.h, m/pmax.h, m/powerpc.h, m/pyrmips.h, m/sequent-ptx.h, m/sequent.h, m/sgi-challenge.h, m/symmetry.h, m/tad68k.h, m/tahoe.h, m/targon31.h, m/tekxd88.h, m/template.h, m/tower32.h, m/tower32v3.h, m/ustation.h, m/vax.h, m/wicat.h, m/xps100.h: Delete C_ALLOCA, HAVE_ALLOCA, STACK_DIRECTION, BROKEN_ALLOCA_IN_FUNCTION_CALLS. All of this is auto-detected. When in doubt, I followed recent FSF sources, which also have these things deleted.
author ben
date Thu, 04 Nov 2004 23:08:28 +0000
parents 576fb035e263
children 061f4f90f874
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
1 /* Plug-compatible replacement for UNIX qsort.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
2 Copyright (C) 1989 Free Software Foundation, Inc.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
3 Written by Douglas C. Schmidt (schmidt@ics.uci.edu)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
4
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
5 This file is part of GNU CC.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
6
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
7 GNU QSORT is free software; you can redistribute it and/or modify
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
8 it under the terms of the GNU General Public License as published by
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
9 the Free Software Foundation; either version 2, or (at your option)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
10 any later version.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
11
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
12 GNU QSORT is distributed in the hope that it will be useful,
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
15 GNU General Public License for more details.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
16
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
17 You should have received a copy of the GNU General Public License
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
18 along with GNU QSORT; see the file COPYING. If not, write to
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
19 the Free the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
20 Boston, MA 02111-1307, USA. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
21
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
22 /* Synched up with: FSF 19.28. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
23
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
24 #ifdef sparc
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
25 #include <alloca.h>
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
26 #endif
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
27
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
28 /* Invoke the comparison function, returns either 0, < 0, or > 0. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
29 #define CMP(A,B) ((*cmp)((A),(B)))
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
30
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
31 /* Byte-wise swap two items of size SIZE. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
32 #define SWAP(A,B,SIZE) do {int sz = (SIZE); char *a = (A); char *b = (B); \
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
33 do { char _temp = *a;*a++ = *b;*b++ = _temp;} while (--sz);} while (0)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
34
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
35 /* Copy SIZE bytes from item B to item A. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
36 #define COPY(A,B,SIZE) {int sz = (SIZE); do { *(A)++ = *(B)++; } while (--sz); }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
37
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
38 /* This should be replaced by a standard ANSI macro. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
39 #define BYTES_PER_WORD 8
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
40
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
41 /* The next 4 #defines implement a very fast in-line stack abstraction. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
42 #define STACK_SIZE (BYTES_PER_WORD * sizeof (long))
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
43 #define PUSH(LOW,HIGH) do {top->lo = LOW;top++->hi = HIGH;} while (0)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
44 #define POP(LOW,HIGH) do {LOW = (--top)->lo;HIGH = top->hi;} while (0)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
45 #define STACK_NOT_EMPTY (stack < top)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
46
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
47 /* Discontinue quicksort algorithm when partition gets below this size.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
48 This particular magic number was chosen to work best on a Sun 4/260. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
49 #define MAX_THRESH 4
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
50
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
51 /* Stack node declarations used to store unfulfilled partition obligations. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
52 typedef struct
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
53 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
54 char *lo;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
55 char *hi;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
56 } stack_node;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
57
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
58 /* Order size using quicksort. This implementation incorporates
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
59 four optimizations discussed in Sedgewick:
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
60
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
61 1. Non-recursive, using an explicit stack of pointer that store the
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
62 next array partition to sort. To save time, this maximum amount
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
63 of space required to store an array of MAX_INT is allocated on the
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
64 stack. Assuming a 32-bit integer, this needs only 32 *
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
65 sizeof (stack_node) == 136 bits. Pretty cheap, actually.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
66
444
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
67 2. Choose the pivot element using a median-of-three decision tree.
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
68 This reduces the probability of selecting a bad pivot value and
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
69 eliminates certain extraneous comparisons.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
70
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
71 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
72 insertion sort to order the MAX_THRESH items within each partition.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
73 This is a big win, since insertion sort is faster for small, mostly
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
74 sorted array segments.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
75
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
76 4. The larger of the two sub-partitions is always pushed onto the
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
77 stack first, with the algorithm then concentrating on the
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
78 smaller partition. This *guarantees* no more than log (n)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
79 stack size is needed (actually O(1) in this case)! */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
80
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
81 int
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
82 qsort (base_ptr, total_elems, size, cmp)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
83 char *base_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
84 int total_elems;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
85 int size;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
86 int (*cmp)();
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
87 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
88 /* Allocating SIZE bytes for a pivot buffer facilitates a better
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
89 algorithm below since we can do comparisons directly on the pivot. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
90 char *pivot_buffer = (char *) alloca (size);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
91 int max_thresh = MAX_THRESH * size;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
92
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
93 if (total_elems > MAX_THRESH)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
94 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
95 char *lo = base_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
96 char *hi = lo + size * (total_elems - 1);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
97 stack_node stack[STACK_SIZE]; /* Largest size needed for 32-bit int!!! */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
98 stack_node *top = stack + 1;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
99
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
100 while (STACK_NOT_EMPTY)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
101 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
102 char *left_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
103 char *right_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
104 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
105 char *pivot = pivot_buffer;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
106 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
107 /* Select median value from among LO, MID, and HI. Rearrange
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
108 LO and HI so the three values are sorted. This lowers the
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
109 probability of picking a pathological pivot value and
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
110 skips a comparison for both the LEFT_PTR and RIGHT_PTR. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
111
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
112 char *mid = lo + size * ((hi - lo) / size >> 1);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
113
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
114 if (CMP (mid, lo) < 0)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
115 SWAP (mid, lo, size);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
116 if (CMP (hi, mid) < 0)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
117 SWAP (mid, hi, size);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
118 else
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
119 goto jump_over;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
120 if (CMP (mid, lo) < 0)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
121 SWAP (mid, lo, size);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
122 jump_over:
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
123 COPY (pivot, mid, size);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
124 pivot = pivot_buffer;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
125 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
126 left_ptr = lo + size;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
127 right_ptr = hi - size;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
128
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
129 /* Here's the famous ``collapse the walls'' section of quicksort.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
130 Gotta like those tight inner loops! They are the main reason
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
131 that this algorithm runs much faster than others. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
132 do
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
133 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
134 while (CMP (left_ptr, pivot) < 0)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
135 left_ptr += size;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
136
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
137 while (CMP (pivot, right_ptr) < 0)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
138 right_ptr -= size;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
139
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
140 if (left_ptr < right_ptr)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
141 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
142 SWAP (left_ptr, right_ptr, size);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
143 left_ptr += size;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
144 right_ptr -= size;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
145 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
146 else if (left_ptr == right_ptr)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
147 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
148 left_ptr += size;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
149 right_ptr -= size;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
150 break;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
151 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
152 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
153 while (left_ptr <= right_ptr);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
154
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
155 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
156
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
157 /* Set up pointers for next iteration. First determine whether
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
158 left and right partitions are below the threshold size. If so,
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
159 ignore one or both. Otherwise, push the larger partition's
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
160 bounds on the stack and continue sorting the smaller one. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
161
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
162 if ((right_ptr - lo) <= max_thresh)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
163 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
164 if ((hi - left_ptr) <= max_thresh) /* Ignore both small partitions. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
165 POP (lo, hi);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
166 else /* Ignore small left partition. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
167 lo = left_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
168 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
169 else if ((hi - left_ptr) <= max_thresh) /* Ignore small right partition. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
170 hi = right_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
171 else if ((right_ptr - lo) > (hi - left_ptr)) /* Push larger left partition indices. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
172 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
173 PUSH (lo, right_ptr);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
174 lo = left_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
175 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
176 else /* Push larger right partition indices. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
177 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
178 PUSH (left_ptr, hi);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
179 hi = right_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
180 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
181 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
182 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
183
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
184 /* Once the BASE_PTR array is partially sorted by quicksort the rest
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
185 is completely sorted using insertion sort, since this is efficient
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
186 for partitions below MAX_THRESH size. BASE_PTR points to the beginning
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
187 of the array to sort, and END_PTR points at the very last element in
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
188 the array (*not* one beyond it!). */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
189
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
190 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
191
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
192 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
193 char *end_ptr = base_ptr + size * (total_elems - 1);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
194 char *run_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
195 char *tmp_ptr = base_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
196 char *thresh = MIN (end_ptr, base_ptr + max_thresh);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
197
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
198 /* Find smallest element in first threshold and place it at the
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
199 array's beginning. This is the smallest array element,
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
200 and the operation speeds up insertion sort's inner loop. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
201
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
202 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
203 if (CMP (run_ptr, tmp_ptr) < 0)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
204 tmp_ptr = run_ptr;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
205
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
206 if (tmp_ptr != base_ptr)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
207 SWAP (tmp_ptr, base_ptr, size);
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
208
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
209 /* Insertion sort, running from left-hand-side up to `right-hand-side.'
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
210 Pretty much straight out of the original GNU qsort routine. */
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
211
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
212 for (run_ptr = base_ptr + size; (tmp_ptr = run_ptr += size) <= end_ptr; )
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
213 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
214
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
215 while (CMP (run_ptr, tmp_ptr -= size) < 0)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
216 ;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
217
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
218 if ((tmp_ptr += size) != run_ptr)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
219 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
220 char *trav;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
221
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
222 for (trav = run_ptr + size; --trav >= run_ptr;)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
223 {
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
224 char c = *trav;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
225 char *hi, *lo;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
226
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
227 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
228 *hi = *lo;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
229 *hi = c;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
230 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
231 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
232
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
233 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
234 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
235 return 1;
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
236 }
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
237