Mercurial > gnulib

annotate lib/qsort.c @ 40169:ecb43221748b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
strtod, strtold: Work around HP-UX 11.31/ia64 bug. * lib/strtod.c (STRTOD): When there is an extra character after the exponent marker 'p', reparse the number. * doc/posix-functions/strtod.texi: Document the HP-UX 11.31 bug. * doc/posix-functions/strtold.texi: Likewise.
author Bruno Haible <bruno@clisp.org>
date Fri, 01 Feb 2019 00:18:57 +0100
parents b06060465f09
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
40057
b06060465f09 maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents: 19484
diff changeset
1 /* Copyright (C) 1991-2019 Free Software Foundation, Inc.
17744
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
2 This file is part of the GNU C Library.
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
3 Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
4
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
5 The GNU C Library is free software; you can redistribute it and/or
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
6 modify it under the terms of the GNU Lesser General Public
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
7 License as published by the Free Software Foundation; either
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
8 version 2.1 of the License, or (at your option) any later version.
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
9
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
10 The GNU C Library is distributed in the hope that it will be useful,
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
13 Lesser General Public License for more details.
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
14
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
15 You should have received a copy of the GNU Lesser General Public
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
16 License along with the GNU C Library; if not, see
19190
9759915b2aca all: prefer https: URLs
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
17 <https://www.gnu.org/licenses/>. */
17744
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
18
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
19 /* If you consider tuning this algorithm, you should consult first:
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
20 Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
21 Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
22
17762
8728cf80b7d8 qsort_r: include <config.h>
Paul Eggert <eggert@cs.ucla.edu>
parents: 17744
diff changeset
23 #ifndef _LIBC
8728cf80b7d8 qsort_r: include <config.h>
Paul Eggert <eggert@cs.ucla.edu>
parents: 17744
diff changeset
24 # include <config.h>
8728cf80b7d8 qsort_r: include <config.h>
Paul Eggert <eggert@cs.ucla.edu>
parents: 17744
diff changeset
25 #endif
8728cf80b7d8 qsort_r: include <config.h>
Paul Eggert <eggert@cs.ucla.edu>
parents: 17744
diff changeset
26
17744
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
27 #include <limits.h>
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
28 #include <stdlib.h>
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
29 #include <string.h>
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
30
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
31 #ifndef _LIBC
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
32 # define _quicksort qsort_r
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
33 # define __compar_d_fn_t compar_d_fn_t
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
34 typedef int (*compar_d_fn_t) (const void *, const void *, void *);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
35 #endif
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
36
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
37 /* Byte-wise swap two items of size SIZE. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
38 #define SWAP(a, b, size) \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
39 do \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
40 { \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
41 size_t __size = (size); \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
42 char *__a = (a), *__b = (b); \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
43 do \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
44 { \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
45 char __tmp = *__a; \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
46 *__a++ = *__b; \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
47 *__b++ = __tmp; \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
48 } while (--__size > 0); \
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
49 } while (0)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
50
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
51 /* Discontinue quicksort algorithm when partition gets below this size.
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
52 This particular magic number was chosen to work best on a Sun 4/260. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
53 #define MAX_THRESH 4
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
54
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
55 /* Stack node declarations used to store unfulfilled partition obligations. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
56 typedef struct
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
57 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
58 char *lo;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
59 char *hi;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
60 } stack_node;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
61
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
62 /* The next 4 #defines implement a very fast in-line stack abstraction. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
63 /* The stack needs log (total_elements) entries (we could even subtract
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
64 log(MAX_THRESH)). Since total_elements has type size_t, we get as
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
65 upper bound for log (total_elements):
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
66 bits per byte (CHAR_BIT) * sizeof(size_t). */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
67 #define STACK_SIZE (CHAR_BIT * sizeof(size_t))
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
68 #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
69 #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
70 #define STACK_NOT_EMPTY (stack < top)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
71
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
72
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
73 /* Order size using quicksort. This implementation incorporates
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
74 four optimizations discussed in Sedgewick:
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
75
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
76 1. Non-recursive, using an explicit stack of pointer that store the
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
77 next array partition to sort. To save time, this maximum amount
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
78 of space required to store an array of SIZE_MAX is allocated on the
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
79 stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
80 only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
81 Pretty cheap, actually.
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
82
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
83 2. Chose the pivot element using a median-of-three decision tree.
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
84 This reduces the probability of selecting a bad pivot value and
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
85 eliminates certain extraneous comparisons.
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
86
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
87 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
88 insertion sort to order the MAX_THRESH items within each partition.
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
89 This is a big win, since insertion sort is faster for small, mostly
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
90 sorted array segments.
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
91
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
92 4. The larger of the two sub-partitions is always pushed onto the
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
93 stack first, with the algorithm then concentrating on the
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
94 smaller partition. This *guarantees* no more than log (total_elems)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
95 stack size is needed (actually O(1) in this case)! */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
96
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
97 void
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
98 _quicksort (void *const pbase, size_t total_elems, size_t size,
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
99 __compar_d_fn_t cmp, void *arg)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
100 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
101 char *base_ptr = (char *) pbase;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
102
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
103 const size_t max_thresh = MAX_THRESH * size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
104
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
105 if (total_elems == 0)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
106 /* Avoid lossage with unsigned arithmetic below. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
107 return;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
108
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
109 if (total_elems > MAX_THRESH)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
110 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
111 char *lo = base_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
112 char *hi = &lo[size * (total_elems - 1)];
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
113 stack_node stack[STACK_SIZE];
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
114 stack_node *top = stack;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
115
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
116 PUSH (NULL, NULL);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
117
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
118 while (STACK_NOT_EMPTY)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
119 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
120 char *left_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
121 char *right_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
122
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
123 /* Select median value from among LO, MID, and HI. Rearrange
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
124 LO and HI so the three values are sorted. This lowers the
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
125 probability of picking a pathological pivot value and
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
126 skips a comparison for both the LEFT_PTR and RIGHT_PTR in
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
127 the while loops. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
128
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
129 char *mid = lo + size * ((hi - lo) / size >> 1);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
130
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
131 if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
132 SWAP (mid, lo, size);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
133 if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
134 SWAP (mid, hi, size);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
135 else
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
136 goto jump_over;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
137 if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
138 SWAP (mid, lo, size);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
139 jump_over:;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
140
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
141 left_ptr = lo + size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
142 right_ptr = hi - size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
143
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
144 /* Here's the famous ``collapse the walls'' section of quicksort.
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
145 Gotta like those tight inner loops! They are the main reason
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
146 that this algorithm runs much faster than others. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
147 do
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
148 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
149 while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
150 left_ptr += size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
151
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
152 while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
153 right_ptr -= size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
154
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
155 if (left_ptr < right_ptr)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
156 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
157 SWAP (left_ptr, right_ptr, size);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
158 if (mid == left_ptr)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
159 mid = right_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
160 else if (mid == right_ptr)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
161 mid = left_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
162 left_ptr += size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
163 right_ptr -= size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
164 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
165 else if (left_ptr == right_ptr)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
166 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
167 left_ptr += size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
168 right_ptr -= size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
169 break;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
170 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
171 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
172 while (left_ptr <= right_ptr);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
173
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
174 /* Set up pointers for next iteration. First determine whether
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
175 left and right partitions are below the threshold size. If so,
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
176 ignore one or both. Otherwise, push the larger partition's
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
177 bounds on the stack and continue sorting the smaller one. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
178
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
179 if ((size_t) (right_ptr - lo) <= max_thresh)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
180 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
181 if ((size_t) (hi - left_ptr) <= max_thresh)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
182 /* Ignore both small partitions. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
183 POP (lo, hi);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
184 else
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
185 /* Ignore small left partition. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
186 lo = left_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
187 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
188 else if ((size_t) (hi - left_ptr) <= max_thresh)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
189 /* Ignore small right partition. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
190 hi = right_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
191 else if ((right_ptr - lo) > (hi - left_ptr))
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
192 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
193 /* Push larger left partition indices. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
194 PUSH (lo, right_ptr);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
195 lo = left_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
196 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
197 else
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
198 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
199 /* Push larger right partition indices. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
200 PUSH (left_ptr, hi);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
201 hi = right_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
202 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
203 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
204 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
205
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
206 /* Once the BASE_PTR array is partially sorted by quicksort the rest
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
207 is completely sorted using insertion sort, since this is efficient
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
208 for partitions below MAX_THRESH size. BASE_PTR points to the beginning
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
209 of the array to sort, and END_PTR points at the very last element in
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
210 the array (*not* one beyond it!). */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
211
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
212 #define min(x, y) ((x) < (y) ? (x) : (y))
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
213
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
214 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
215 char *const end_ptr = &base_ptr[size * (total_elems - 1)];
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
216 char *tmp_ptr = base_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
217 char *thresh = min(end_ptr, base_ptr + max_thresh);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
218 char *run_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
219
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
220 /* Find smallest element in first threshold and place it at the
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
221 array's beginning. This is the smallest array element,
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
222 and the operation speeds up insertion sort's inner loop. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
223
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
224 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
225 if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
226 tmp_ptr = run_ptr;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
227
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
228 if (tmp_ptr != base_ptr)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
229 SWAP (tmp_ptr, base_ptr, size);
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
230
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
231 /* Insertion sort, running from left-hand-side up to right-hand-side. */
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
232
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
233 run_ptr = base_ptr + size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
234 while ((run_ptr += size) <= end_ptr)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
235 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
236 tmp_ptr = run_ptr - size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
237 while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
238 tmp_ptr -= size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
239
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
240 tmp_ptr += size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
241 if (tmp_ptr != run_ptr)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
242 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
243 char *trav;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
244
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
245 trav = run_ptr + size;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
246 while (--trav >= run_ptr)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
247 {
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
248 char c = *trav;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
249 char *hi, *lo;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
250
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
251 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
252 *hi = *lo;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
253 *hi = c;
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
254 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
255 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
256 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
257 }
9c8d212db038 qsort_r: new module, for GNU-style qsort_r
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
258 }