c9951420c52f498484d7058dfccac6e263051e7e
[reactos.git] / reactos / lib / rtl / qsort.c
1 /*
2 * COPYRIGHT:
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. All advertising materials mentioning features or use of this software
16 * must display the following acknowledgement:
17 * This product includes software developed by the University of
18 * California, Berkeley and its contributors.
19 * 4. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 *
35 * PROJECT: ReactOS system libraries
36 * PURPOSE: Unicode Conversion Routines
37 * FILE: lib/rtl/qsort.c
38 * PROGRAMMER: Adapted from CygWin newlib 2000-03-12.
39 */
40
41 #include <stddef.h>
42
43 #ifndef __GNUC__
44 #define inline
45 #endif
46
47 /* FIXME: these types should be from the default includes */
48
49 typedef int (* _pfunccmp_t) (char *, char *);
50
51 #define min(a,b) ((a)<(b)?(a):(b))
52
53 /*
54 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
55 */
56 #define swapcode(TYPE, parmi, parmj, n) { \
57 long i = (n) / sizeof (TYPE); \
58 register TYPE *pi = (TYPE *) (parmi); \
59 register TYPE *pj = (TYPE *) (parmj); \
60 do { \
61 register TYPE t = *pi; \
62 *pi++ = *pj; \
63 *pj++ = t; \
64 } while (--i > 0); \
65 }
66
67 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
68 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
69
70 static inline void
71 swapfunc (
72 char * a,
73 char * b,
74 int n,
75 int swaptype
76 )
77 {
78 if(swaptype <= 1)
79 swapcode(long, a, b, n)
80 else
81 swapcode(char, a, b, n)
82 }
83
84 #define swap(a, b) \
85 if (swaptype == 0) { \
86 long t = *(long *)(a); \
87 *(long *)(a) = *(long *)(b); \
88 *(long *)(b) = t; \
89 } else \
90 swapfunc(a, b, es, swaptype)
91
92 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
93
94 static inline char *
95 med3 (
96 char * a,
97 char * b,
98 char * c,
99 _pfunccmp_t cmp
100 )
101 {
102 return cmp(a, b) < 0 ?
103 (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
104 :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
105 }
106
107
108 /* EXPORTED */
109 void
110 qsort (
111 void * a,
112 size_t n,
113 size_t es,
114 _pfunccmp_t cmp
115 )
116 {
117 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
118 int d, r, swaptype, swap_cnt;
119
120 loop: SWAPINIT(a, es);
121 swap_cnt = 0;
122 if (n < 7)
123 {
124 for ( pm = (char *) a + es;
125 pm < (char *) a + n * es;
126 pm += es
127 )
128 {
129 for ( pl = pm;
130 pl > (char *) a && cmp(pl - es, pl) > 0;
131 pl -= es
132 )
133 {
134 swap(pl, pl - es);
135 }
136 }
137 return;
138 }
139 pm = (char *) a + (n / 2) * es;
140 if (n > 7)
141 {
142 pl = (char *) a;
143 pn = (char *) a + (n - 1) * es;
144 if (n > 40)
145 {
146 d = (n / 8) * es;
147 pl = med3(pl, pl + d, pl + 2 * d, cmp);
148 pm = med3(pm - d, pm, pm + d, cmp);
149 pn = med3(pn - 2 * d, pn - d, pn, cmp);
150 }
151 pm = med3(pl, pm, pn, cmp);
152 }
153 swap(a, pm);
154 pa = pb = (char *) a + es;
155
156 pc = pd = (char *) a + (n - 1) * es;
157 for (;;)
158 {
159 while (pb <= pc && (r = cmp(pb, a)) <= 0)
160 {
161 if (r == 0)
162 {
163 swap_cnt = 1;
164 swap(pa, pb);
165 pa += es;
166 }
167 pb += es;
168 }
169 while (pb <= pc && (r = cmp(pc, a)) >= 0)
170 {
171 if (r == 0)
172 {
173 swap_cnt = 1;
174 swap(pc, pd);
175 pd -= es;
176 }
177 pc -= es;
178 }
179 if (pb > pc)
180 {
181 break;
182 }
183 swap(pb, pc);
184 swap_cnt = 1;
185 pb += es;
186 pc -= es;
187 }
188 if (swap_cnt == 0) /* Switch to insertion sort */
189 {
190 for ( pm = (char *) a + es;
191 pm < (char *) a + n * es;
192 pm += es
193 )
194 {
195 for ( pl = pm;
196 pl > (char *) a && cmp(pl - es, pl) > 0;
197 pl -= es
198 )
199 {
200 swap(pl, pl - es);
201 }
202 }
203 return;
204 }
205
206 pn = (char *) a + n * es;
207 r = min(pa - (char *)a, pb - pa);
208 vecswap(a, pb - r, r);
209 r = min(pd - pc, pn - pd - es);
210 vecswap(pb, pn - r, r);
211 if ((r = pb - pa) > es)
212 {
213 qsort(a, r / es, es, cmp);
214 }
215 if ((r = pd - pc) > es)
216 {
217 /* Iterate rather than recurse to save stack space */
218 a = pn - r;
219 n = r / es;
220 goto loop;
221 }
222 /* qsort(pn - r, r / es, es, cmp);*/
223 }
224
225
226 /* EOF */