Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 :
3 : /*-
4 : * Copyright (c) 1992, 1993
5 : * The Regents of the University of California. All rights reserved.
6 : *
7 : * Redistribution and use in source and binary forms, with or without
8 : * modification, are permitted provided that the following conditions
9 : * are met:
10 : * 1. Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * 2. Redistributions in binary form must reproduce the above copyright
13 : * notice, this list of conditions and the following disclaimer in the
14 : * documentation and/or other materials provided with the distribution.
15 : * 3. Neither the name of the University nor the names of its contributors
16 : * may be used to endorse or promote products derived from this software
17 : * without specific prior written permission.
18 : *
19 : * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 : * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 : * SUCH DAMAGE.
30 : */
31 :
32 : /* We need this because Solaris' version of qsort is broken and
33 : * causes array bounds reads.
34 : */
35 :
36 : #include <stdlib.h>
37 : #include "nsAlgorithm.h"
38 : #include "nsQuickSort.h"
39 :
40 : extern "C" {
41 :
42 : #if !defined(DEBUG) && (defined(__cplusplus) || defined(__gcc))
43 : # ifndef INLINE
44 : # define INLINE inline
45 : # endif
46 : #else
47 : # define INLINE
48 : #endif
49 :
50 : typedef int cmp_t(const void *, const void *, void *);
51 : static INLINE char *med3(char *, char *, char *, cmp_t *, void *);
52 : static INLINE void swapfunc(char *, char *, int, int);
53 :
54 : /*
55 : * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
56 : */
57 : #define swapcode(TYPE, parmi, parmj, n) { \
58 : long i = (n) / sizeof (TYPE); \
59 : TYPE *pi = (TYPE *) (parmi); \
60 : TYPE *pj = (TYPE *) (parmj); \
61 : do { \
62 : TYPE t = *pi; \
63 : *pi++ = *pj; \
64 : *pj++ = t; \
65 : } while (--i > 0); \
66 : }
67 :
68 : #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
69 : es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
70 :
71 : static INLINE void
72 7729 : swapfunc(char *a, char *b, int n, int swaptype)
73 : {
74 7729 : if(swaptype <= 1)
75 831 : swapcode(long, a, b, n)
76 : else
77 6898 : swapcode(char, a, b, n)
78 7729 : }
79 :
80 : #define swap(a, b) \
81 : if (swaptype == 0) { \
82 : long t = *(long *)(a); \
83 : *(long *)(a) = *(long *)(b); \
84 : *(long *)(b) = t; \
85 : } else \
86 : swapfunc((char *)a, (char*)b, (int)es, swaptype)
87 :
88 : #define vecswap(a, b, n) if ((n) > 0) swapfunc((char *)a, (char *)b, (int)n, swaptype)
89 :
90 : static INLINE char *
91 1001 : med3(char *a, char *b, char *c, cmp_t* cmp, void *data)
92 : {
93 2002 : return cmp(a, b, data) < 0 ?
94 548 : (cmp(b, c, data) < 0 ? b : (cmp(a, c, data) < 0 ? c : a ))
95 1454 : :(cmp(b, c, data) > 0 ? b : (cmp(a, c, data) < 0 ? a : c ));
96 : }
97 :
98 1795 : void NS_QuickSort (
99 : void *a,
100 : unsigned int n,
101 : unsigned int es,
102 : cmp_t *cmp,
103 : void *data
104 : )
105 : {
106 : char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
107 : int d, r, swaptype;
108 :
109 1795 : loop: SWAPINIT(a, es);
110 : /* Use insertion sort when input is small */
111 1795 : if (n < 7) {
112 3660 : for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
113 5528 : for (pl = pm; pl > (char *)a && cmp(pl - es, pl, data) > 0;
114 2828 : pl -= es)
115 2828 : swap(pl, pl - es);
116 960 : return;
117 : }
118 : /* Choose pivot */
119 835 : pm = (char *)a + (n / 2) * es;
120 835 : if (n > 7) {
121 746 : pl = (char *)a;
122 746 : pn = (char *)a + (n - 1) * es;
123 746 : if (n > 40) {
124 85 : d = (n / 8) * es;
125 85 : pl = med3(pl, pl + d, pl + 2 * d, cmp, data);
126 85 : pm = med3(pm - d, pm, pm + d, cmp, data);
127 85 : pn = med3(pn - 2 * d, pn - d, pn, cmp, data);
128 : }
129 746 : pm = med3(pl, pm, pn, cmp, data);
130 : }
131 835 : swap(a, pm);
132 835 : pa = pb = (char *)a + es;
133 :
134 835 : pc = pd = (char *)a + (n - 1) * es;
135 : /* loop invariants:
136 : * [a, pa) = pivot
137 : * [pa, pb) < pivot
138 : * [pb, pc + es) unprocessed
139 : * [pc + es, pd + es) > pivot
140 : * [pd + es, pn) = pivot
141 : */
142 : for (;;) {
143 16408 : while (pb <= pc && (r = cmp(pb, a, data)) <= 0) {
144 6008 : if (r == 0) {
145 0 : swap(pa, pb);
146 0 : pa += es;
147 : }
148 6008 : pb += es;
149 : }
150 16836 : while (pb <= pc && (r = cmp(pc, a, data)) >= 0) {
151 6222 : if (r == 0) {
152 0 : swap(pc, pd);
153 0 : pd -= es;
154 : }
155 6222 : pc -= es;
156 : }
157 4392 : if (pb > pc)
158 835 : break;
159 3557 : swap(pb, pc);
160 3557 : pb += es;
161 3557 : pc -= es;
162 3557 : }
163 : /* Move pivot values */
164 835 : pn = (char *)a + n * es;
165 835 : r = XPCOM_MIN(pa - (char *)a, pb - pa);
166 835 : vecswap(a, pb - r, r);
167 835 : r = XPCOM_MIN<size_t>(pd - pc, pn - pd - es);
168 835 : vecswap(pb, pn - r, r);
169 : /* Recursively process partitioned items */
170 835 : if ((r = pb - pa) > (int)es)
171 755 : NS_QuickSort(a, r / es, es, cmp, data);
172 835 : if ((r = pd - pc) > (int)es) {
173 : /* Iterate rather than recurse to save stack space */
174 755 : a = pn - r;
175 755 : n = r / es;
176 755 : goto loop;
177 : }
178 : /* NS_QuickSort(pn - r, r / es, es, cmp, data);*/
179 : }
180 :
181 : }
182 :
183 : #undef INLINE
184 : #undef swapcode
185 : #undef SWAPINIT
186 : #undef swap
187 : #undef vecswap
|
