4 * Copyright (c) 1992, 1993
5 * The Regents of the University of California. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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.
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
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.
46 /* FIXME: these types should be from the default includes */
48 typedef int (* _pfunccmp_t
) (const void *, const void *);
50 #define min(a,b) ((a)<(b)?(a):(b))
53 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
55 #define swapcode(TYPE, parmi, parmj, n) { \
56 long i = (n) / sizeof (TYPE); \
57 register TYPE *pi = (TYPE *) (parmi); \
58 register TYPE *pj = (TYPE *) (parmj); \
60 register TYPE t = *pi; \
66 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
67 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
78 swapcode(long, a
, b
, n
)
80 swapcode(char, a
, b
, n
)
84 if (swaptype == 0) { \
85 long t = *(long *)(a); \
86 *(long *)(a) = *(long *)(b); \
89 swapfunc(a, b, es, swaptype)
91 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
101 return cmp(a
, b
) < 0 ?
102 (cmp(b
, c
) < 0 ? b
: (cmp(a
, c
) < 0 ? c
: a
))
103 :(cmp(b
, c
) > 0 ? b
: (cmp(a
, c
) < 0 ? a
: c
));
116 char *pa
, *pb
, *pc
, *pd
, *pl
, *pm
, *pn
;
117 int d
, r
, swaptype
, swap_cnt
;
119 loop
: SWAPINIT(a
, es
);
123 for ( pm
= (char *) a
+ es
;
124 pm
< (char *) a
+ n
* es
;
129 pl
> (char *) a
&& cmp(pl
- es
, pl
) > 0;
138 pm
= (char *) a
+ (n
/ 2) * es
;
142 pn
= (char *) a
+ (n
- 1) * es
;
146 pl
= med3(pl
, pl
+ d
, pl
+ 2 * d
, cmp
);
147 pm
= med3(pm
- d
, pm
, pm
+ d
, cmp
);
148 pn
= med3(pn
- 2 * d
, pn
- d
, pn
, cmp
);
150 pm
= med3(pl
, pm
, pn
, cmp
);
153 pa
= pb
= (char *) a
+ es
;
155 pc
= pd
= (char *) a
+ (n
- 1) * es
;
158 while (pb
<= pc
&& (r
= cmp(pb
, a
)) <= 0)
168 while (pb
<= pc
&& (r
= cmp(pc
, a
)) >= 0)
187 if (swap_cnt
== 0) /* Switch to insertion sort */
189 for ( pm
= (char *) a
+ es
;
190 pm
< (char *) a
+ n
* es
;
195 pl
> (char *) a
&& cmp(pl
- es
, pl
) > 0;
205 pn
= (char *) a
+ n
* es
;
206 r
= min(pa
- (char *)a
, pb
- pa
);
207 vecswap(a
, pb
- r
, r
);
208 r
= min(pd
- pc
, pn
- pd
- es
);
209 vecswap(pb
, pn
- r
, r
);
210 if ((r
= pb
- pa
) > es
)
212 qsort(a
, r
/ es
, es
, cmp
);
214 if ((r
= pd
- pc
) > es
)
216 /* Iterate rather than recurse to save stack space */
221 /* qsort(pn - r, r / es, es, cmp);*/