]>
git.proxmox.com Git - mirror_edk2.git/blob - StdLib/LibC/StdLib/Qsort.c
2 Quick Sort utility function.
4 This utility makes use of a comparison function to search arrays of
5 unspecified type. Where an argument declared as size_t nmemb specifies the
6 length of the array for a function, nmemb can have the value zero on a call
7 to that function; the comparison function is not called, a search finds no
8 matching element. Pointer arguments on such a call shall still have valid
11 The implementation shall ensure that both arguments of the comparison
12 function are pointers to elements of the array.
14 The comparison function shall not alter the contents of the array. The
15 implementation may reorder elements of the array between calls to the
16 comparison function, but shall not alter the contents of any individual
19 When the same objects (consisting of size bytes, irrespective of their
20 current positions in the array) are passed more than once to the comparison
21 function, the results shall be consistent with one another. That is, they
22 define a total ordering on the array.
24 A sequence point occurs immediately before and immediately after each call to
25 the comparison function, and also between any call to the comparison function
26 and any movement of the objects passed as arguments to that call.
28 Copyright (c) 2010, Intel Corporation. All rights reserved.<BR>
29 * Copyright (c) 1992, 1993
30 * The Regents of the University of California. All rights reserved.
32 * Redistribution and use in source and binary forms, with or without
33 * modification, are permitted provided that the following conditions
35 * 1. Redistributions of source code must retain the above copyright
36 * notice, this list of conditions and the following disclaimer.
37 * 2. Redistributions in binary form must reproduce the above copyright
38 * notice, this list of conditions and the following disclaimer in the
39 * documentation and/or other materials provided with the distribution.
40 * 4. Neither the name of the University nor the names of its contributors
41 * may be used to endorse or promote products derived from this software
42 * without specific prior written permission.
44 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
45 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
46 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
47 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
48 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
49 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
50 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
51 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
52 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
53 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
56 ("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15.2.1.2.1 2009/10/25 01:10:29 kensmith Exp $");
58 #include <LibConfig.h>
62 typedef int cmp_t(const void *, const void *);
64 static __inline
char *med3(char *, char *, char *, cmp_t
*);
65 static __inline
void swapfunc(char *, char *, size_t, int);
68 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
70 #define swapcode(TYPE, parmi, parmj, n) { \
71 size_t i = (n) / sizeof (TYPE); \
72 TYPE *pi = (TYPE *) (parmi); \
73 TYPE *pj = (TYPE *) (parmj); \
81 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
82 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
85 swapfunc(char *a
, char *b
, size_t n
, int swaptype
)
88 swapcode(long, a
, b
, n
)
90 swapcode(char, a
, b
, n
)
94 if (swaptype == 0) { \
95 long t = *(long *)(a); \
96 *(long *)(a) = *(long *)(b); \
99 swapfunc(a, b, es, swaptype)
101 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
103 static __inline
char *
104 med3(char *a
, char *b
, char *c
, cmp_t
*cmp
)
106 return cmp(a
, b
) < 0 ?
107 (cmp(b
, c
) < 0 ? b
: (cmp(a
, c
) < 0 ? c
: a
))
108 :(cmp(b
, c
) > 0 ? b
: (cmp(a
, c
) < 0 ? a
: c
));
111 /* The qsort function sorts an array of nmemb objects, the initial element of
112 which is pointed to by base. The size of each object is specified by size.
114 The contents of the array are sorted into ascending order according to a
115 comparison function pointed to by compar, which is called with two
116 arguments that point to the objects being compared. The function shall
117 return an integer less than, equal to, or greater than zero if the first
118 argument is considered to be respectively less than, equal to, or greater
121 If two elements compare as equal, their order in the resulting sorted array
125 qsort(void *a
, size_t n
, size_t es
, cmp_t
*cmp
)
127 char *pa
, *pb
, *pc
, *pd
, *pl
, *pm
, *pn
;
130 int swaptype
, swap_cnt
;
132 loop
: SWAPINIT(a
, es
);
135 for (pm
= (char *)a
+ es
; pm
< (char *)a
+ n
* es
; pm
+= es
)
137 pl
> (char *)a
&& cmp(pl
- es
, pl
) > 0;
142 pm
= (char *)a
+ (n
/ 2) * es
;
145 pn
= (char *)a
+ (n
- 1) * es
;
148 pl
= med3(pl
, pl
+ d
, pl
+ 2 * d
, cmp
);
149 pm
= med3(pm
- d
, pm
, pm
+ d
, cmp
);
150 pn
= med3(pn
- 2 * d
, pn
- d
, pn
, cmp
);
152 pm
= med3(pl
, pm
, pn
, cmp
);
155 pa
= pb
= (char *)a
+ es
;
157 pc
= pd
= (char *)a
+ (n
- 1) * es
;
159 while (pb
<= pc
&& (cmp_result
= cmp(pb
, a
)) <= 0) {
160 if (cmp_result
== 0) {
167 while (pb
<= pc
&& (cmp_result
= cmp(pc
, a
)) >= 0) {
168 if (cmp_result
== 0) {
182 if (swap_cnt
== 0) { /* Switch to insertion sort */
183 for (pm
= (char *)a
+ es
; pm
< (char *)a
+ n
* es
; pm
+= es
)
185 pl
> (char *)a
&& cmp(pl
- es
, pl
) > 0;
191 pn
= (char *)a
+ n
* es
;
192 r
= MIN(pa
- (char *)a
, pb
- pa
);
193 vecswap(a
, pb
- r
, r
);
194 r
= MIN((size_t)(pd
- pc
), ((size_t)(pn
- pd
)) - es
);
195 vecswap(pb
, pn
- r
, r
);
196 if ((size_t)(r
= pb
- pa
) > es
)
197 qsort(a
, r
/ es
, es
, cmp
);
198 if ((size_t)(r
= pd
- pc
) > es
) {
199 /* Iterate rather than recurse to save stack space */
204 /* qsort(pn - r, r / es, es, cmp);*/