Mercurial > hg > xemacs-beta
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 |
| rev | line source |
|---|---|
| 0 | 1 /* Plug-compatible replacement for UNIX qsort. |
| 2 Copyright (C) 1989 Free Software Foundation, Inc. | |
| 3 Written by Douglas C. Schmidt (schmidt@ics.uci.edu) | |
| 4 | |
| 5 This file is part of GNU CC. | |
| 6 | |
| 7 GNU QSORT is free software; you can redistribute it and/or modify | |
| 8 it under the terms of the GNU General Public License as published by | |
| 9 the Free Software Foundation; either version 2, or (at your option) | |
| 10 any later version. | |
| 11 | |
| 12 GNU QSORT is distributed in the hope that it will be useful, | |
| 13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 15 GNU General Public License for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 18 along with GNU QSORT; see the file COPYING. If not, write to | |
| 19 the Free the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
| 20 Boston, MA 02111-1307, USA. */ | |
| 21 | |
| 22 /* Synched up with: FSF 19.28. */ | |
| 23 | |
| 24 #ifdef sparc | |
| 25 #include <alloca.h> | |
| 26 #endif | |
| 27 | |
| 28 /* Invoke the comparison function, returns either 0, < 0, or > 0. */ | |
| 29 #define CMP(A,B) ((*cmp)((A),(B))) | |
| 30 | |
| 31 /* Byte-wise swap two items of size SIZE. */ | |
| 32 #define SWAP(A,B,SIZE) do {int sz = (SIZE); char *a = (A); char *b = (B); \ | |
| 33 do { char _temp = *a;*a++ = *b;*b++ = _temp;} while (--sz);} while (0) | |
| 34 | |
| 35 /* Copy SIZE bytes from item B to item A. */ | |
| 36 #define COPY(A,B,SIZE) {int sz = (SIZE); do { *(A)++ = *(B)++; } while (--sz); } | |
| 37 | |
| 38 /* This should be replaced by a standard ANSI macro. */ | |
| 39 #define BYTES_PER_WORD 8 | |
| 40 | |
| 41 /* The next 4 #defines implement a very fast in-line stack abstraction. */ | |
| 42 #define STACK_SIZE (BYTES_PER_WORD * sizeof (long)) | |
| 43 #define PUSH(LOW,HIGH) do {top->lo = LOW;top++->hi = HIGH;} while (0) | |
| 44 #define POP(LOW,HIGH) do {LOW = (--top)->lo;HIGH = top->hi;} while (0) | |
| 45 #define STACK_NOT_EMPTY (stack < top) | |
| 46 | |
| 47 /* Discontinue quicksort algorithm when partition gets below this size. | |
| 48 This particular magic number was chosen to work best on a Sun 4/260. */ | |
| 49 #define MAX_THRESH 4 | |
| 50 | |
| 51 /* Stack node declarations used to store unfulfilled partition obligations. */ | |
| 52 typedef struct | |
| 53 { | |
| 54 char *lo; | |
| 55 char *hi; | |
| 56 } stack_node; | |
| 57 | |
| 58 /* Order size using quicksort. This implementation incorporates | |
| 59 four optimizations discussed in Sedgewick: | |
| 60 | |
| 61 1. Non-recursive, using an explicit stack of pointer that store the | |
| 62 next array partition to sort. To save time, this maximum amount | |
| 63 of space required to store an array of MAX_INT is allocated on the | |
| 64 stack. Assuming a 32-bit integer, this needs only 32 * | |
| 65 sizeof (stack_node) == 136 bits. Pretty cheap, actually. | |
| 66 | |
| 444 | 67 2. Choose the pivot element using a median-of-three decision tree. |
| 0 | 68 This reduces the probability of selecting a bad pivot value and |
| 69 eliminates certain extraneous comparisons. | |
| 70 | |
| 71 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving | |
| 72 insertion sort to order the MAX_THRESH items within each partition. | |
| 73 This is a big win, since insertion sort is faster for small, mostly | |
| 74 sorted array segments. | |
| 75 | |
| 76 4. The larger of the two sub-partitions is always pushed onto the | |
| 77 stack first, with the algorithm then concentrating on the | |
| 78 smaller partition. This *guarantees* no more than log (n) | |
| 79 stack size is needed (actually O(1) in this case)! */ | |
| 80 | |
| 81 int | |
| 82 qsort (base_ptr, total_elems, size, cmp) | |
| 83 char *base_ptr; | |
| 84 int total_elems; | |
| 85 int size; | |
| 86 int (*cmp)(); | |
| 87 { | |
| 88 /* Allocating SIZE bytes for a pivot buffer facilitates a better | |
| 89 algorithm below since we can do comparisons directly on the pivot. */ | |
| 90 char *pivot_buffer = (char *) alloca (size); | |
| 91 int max_thresh = MAX_THRESH * size; | |
| 92 | |
| 93 if (total_elems > MAX_THRESH) | |
| 94 { | |
| 95 char *lo = base_ptr; | |
| 96 char *hi = lo + size * (total_elems - 1); | |
| 97 stack_node stack[STACK_SIZE]; /* Largest size needed for 32-bit int!!! */ | |
| 98 stack_node *top = stack + 1; | |
| 99 | |
| 100 while (STACK_NOT_EMPTY) | |
| 101 { | |
| 102 char *left_ptr; | |
| 103 char *right_ptr; | |
| 104 { | |
| 105 char *pivot = pivot_buffer; | |
| 106 { | |
| 107 /* Select median value from among LO, MID, and HI. Rearrange | |
| 108 LO and HI so the three values are sorted. This lowers the | |
| 109 probability of picking a pathological pivot value and | |
| 110 skips a comparison for both the LEFT_PTR and RIGHT_PTR. */ | |
| 111 | |
| 112 char *mid = lo + size * ((hi - lo) / size >> 1); | |
| 113 | |
| 114 if (CMP (mid, lo) < 0) | |
| 115 SWAP (mid, lo, size); | |
| 116 if (CMP (hi, mid) < 0) | |
| 117 SWAP (mid, hi, size); | |
| 118 else | |
| 119 goto jump_over; | |
| 120 if (CMP (mid, lo) < 0) | |
| 121 SWAP (mid, lo, size); | |
| 122 jump_over: | |
| 123 COPY (pivot, mid, size); | |
| 124 pivot = pivot_buffer; | |
| 125 } | |
| 126 left_ptr = lo + size; | |
| 127 right_ptr = hi - size; | |
| 128 | |
| 129 /* Here's the famous ``collapse the walls'' section of quicksort. | |
| 130 Gotta like those tight inner loops! They are the main reason | |
| 131 that this algorithm runs much faster than others. */ | |
| 132 do | |
| 133 { | |
| 134 while (CMP (left_ptr, pivot) < 0) | |
| 135 left_ptr += size; | |
| 136 | |
| 137 while (CMP (pivot, right_ptr) < 0) | |
| 138 right_ptr -= size; | |
| 139 | |
| 140 if (left_ptr < right_ptr) | |
| 141 { | |
| 142 SWAP (left_ptr, right_ptr, size); | |
| 143 left_ptr += size; | |
| 144 right_ptr -= size; | |
| 145 } | |
| 146 else if (left_ptr == right_ptr) | |
| 147 { | |
| 148 left_ptr += size; | |
| 149 right_ptr -= size; | |
| 150 break; | |
| 151 } | |
| 152 } | |
| 153 while (left_ptr <= right_ptr); | |
| 154 | |
| 155 } | |
| 156 | |
| 157 /* Set up pointers for next iteration. First determine whether | |
| 158 left and right partitions are below the threshold size. If so, | |
| 159 ignore one or both. Otherwise, push the larger partition's | |
| 160 bounds on the stack and continue sorting the smaller one. */ | |
| 161 | |
| 162 if ((right_ptr - lo) <= max_thresh) | |
| 163 { | |
| 164 if ((hi - left_ptr) <= max_thresh) /* Ignore both small partitions. */ | |
| 165 POP (lo, hi); | |
| 166 else /* Ignore small left partition. */ | |
| 167 lo = left_ptr; | |
| 168 } | |
| 169 else if ((hi - left_ptr) <= max_thresh) /* Ignore small right partition. */ | |
| 170 hi = right_ptr; | |
| 171 else if ((right_ptr - lo) > (hi - left_ptr)) /* Push larger left partition indices. */ | |
| 172 { | |
| 173 PUSH (lo, right_ptr); | |
| 174 lo = left_ptr; | |
| 175 } | |
| 176 else /* Push larger right partition indices. */ | |
| 177 { | |
| 178 PUSH (left_ptr, hi); | |
| 179 hi = right_ptr; | |
| 180 } | |
| 181 } | |
| 182 } | |
| 183 | |
| 184 /* Once the BASE_PTR array is partially sorted by quicksort the rest | |
| 185 is completely sorted using insertion sort, since this is efficient | |
| 186 for partitions below MAX_THRESH size. BASE_PTR points to the beginning | |
| 187 of the array to sort, and END_PTR points at the very last element in | |
| 188 the array (*not* one beyond it!). */ | |
| 189 | |
| 190 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) | |
| 191 | |
| 192 { | |
| 193 char *end_ptr = base_ptr + size * (total_elems - 1); | |
| 194 char *run_ptr; | |
| 195 char *tmp_ptr = base_ptr; | |
| 196 char *thresh = MIN (end_ptr, base_ptr + max_thresh); | |
| 197 | |
| 198 /* Find smallest element in first threshold and place it at the | |
| 199 array's beginning. This is the smallest array element, | |
| 200 and the operation speeds up insertion sort's inner loop. */ | |
| 201 | |
| 202 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) | |
| 203 if (CMP (run_ptr, tmp_ptr) < 0) | |
| 204 tmp_ptr = run_ptr; | |
| 205 | |
| 206 if (tmp_ptr != base_ptr) | |
| 207 SWAP (tmp_ptr, base_ptr, size); | |
| 208 | |
| 209 /* Insertion sort, running from left-hand-side up to `right-hand-side.' | |
| 210 Pretty much straight out of the original GNU qsort routine. */ | |
| 211 | |
| 212 for (run_ptr = base_ptr + size; (tmp_ptr = run_ptr += size) <= end_ptr; ) | |
| 213 { | |
| 214 | |
| 215 while (CMP (run_ptr, tmp_ptr -= size) < 0) | |
| 216 ; | |
| 217 | |
| 218 if ((tmp_ptr += size) != run_ptr) | |
| 219 { | |
| 220 char *trav; | |
| 221 | |
| 222 for (trav = run_ptr + size; --trav >= run_ptr;) | |
| 223 { | |
| 224 char c = *trav; | |
| 225 char *hi, *lo; | |
| 226 | |
| 227 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) | |
| 228 *hi = *lo; | |
| 229 *hi = c; | |
| 230 } | |
| 231 } | |
| 232 | |
| 233 } | |
| 234 } | |
| 235 return 1; | |
| 236 } | |
| 237 |
