diff options
author | Björn Stenberg <bjorn@haxx.se> | 2002-05-30 21:03:17 +0000 |
---|---|---|
committer | Björn Stenberg <bjorn@haxx.se> | 2002-05-30 21:03:17 +0000 |
commit | b69338f9f8ae2ae957949a0f4af9749ebb4adc3f (patch) | |
tree | c29019589ce21007d1ff99dd74d3115f19dbd3f4 /firmware/common/qsort.c | |
parent | 80361f88818ad1ce2ebc00a10f7aa8de1605b3a5 (diff) | |
download | rockbox-b69338f9f8ae2ae957949a0f4af9749ebb4adc3f.tar.gz rockbox-b69338f9f8ae2ae957949a0f4af9749ebb4adc3f.zip |
Added code from libc instead of requiring newlib
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@835 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'firmware/common/qsort.c')
-rw-r--r-- | firmware/common/qsort.c | 222 |
1 files changed, 222 insertions, 0 deletions
diff --git a/firmware/common/qsort.c b/firmware/common/qsort.c new file mode 100644 index 0000000000..d47f470999 --- /dev/null +++ b/firmware/common/qsort.c | |||
@@ -0,0 +1,222 @@ | |||
1 | /* | ||
2 | FUNCTION | ||
3 | <<qsort>>---sort an array | ||
4 | |||
5 | INDEX | ||
6 | qsort | ||
7 | |||
8 | ANSI_SYNOPSIS | ||
9 | #include <stdlib.h> | ||
10 | void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>, | ||
11 | int (*<[compar]>)(const void *, const void *) ); | ||
12 | |||
13 | TRAD_SYNOPSIS | ||
14 | #include <stdlib.h> | ||
15 | qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> ) | ||
16 | char *<[base]>; | ||
17 | size_t <[nmemb]>; | ||
18 | size_t <[size]>; | ||
19 | int (*<[compar]>)(); | ||
20 | |||
21 | DESCRIPTION | ||
22 | <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects. | ||
23 | <[size]> describes the size of each element of the array. | ||
24 | |||
25 | You must supply a pointer to a comparison function, using the argument | ||
26 | shown as <[compar]>. (This permits sorting objects of unknown | ||
27 | properties.) Define the comparison function to accept two arguments, | ||
28 | each a pointer to an element of the array starting at <[base]>. The | ||
29 | result of <<(*<[compar]>)>> must be negative if the first argument is | ||
30 | less than the second, zero if the two arguments match, and positive if | ||
31 | the first argument is greater than the second (where ``less than'' and | ||
32 | ``greater than'' refer to whatever arbitrary ordering is appropriate). | ||
33 | |||
34 | The array is sorted in place; that is, when <<qsort>> returns, the | ||
35 | array elements beginning at <[base]> have been reordered. | ||
36 | |||
37 | RETURNS | ||
38 | <<qsort>> does not return a result. | ||
39 | |||
40 | PORTABILITY | ||
41 | <<qsort>> is required by ANSI (without specifying the sorting algorithm). | ||
42 | */ | ||
43 | |||
44 | /*- | ||
45 | * Copyright (c) 1992, 1993 | ||
46 | * The Regents of the University of California. All rights reserved. | ||
47 | * | ||
48 | * Redistribution and use in source and binary forms, with or without | ||
49 | * modification, are permitted provided that the following conditions | ||
50 | * are met: | ||
51 | * 1. Redistributions of source code must retain the above copyright | ||
52 | * notice, this list of conditions and the following disclaimer. | ||
53 | * 2. Redistributions in binary form must reproduce the above copyright | ||
54 | * notice, this list of conditions and the following disclaimer in the | ||
55 | * documentation and/or other materials provided with the distribution. | ||
56 | * 3. All advertising materials mentioning features or use of this software | ||
57 | * must display the following acknowledgement: | ||
58 | * This product includes software developed by the University of | ||
59 | * California, Berkeley and its contributors. | ||
60 | * 4. Neither the name of the University nor the names of its contributors | ||
61 | * may be used to endorse or promote products derived from this software | ||
62 | * without specific prior written permission. | ||
63 | * | ||
64 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | ||
65 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
66 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
67 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | ||
68 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||
69 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | ||
70 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||
71 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||
72 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | ||
73 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | ||
74 | * SUCH DAMAGE. | ||
75 | */ | ||
76 | |||
77 | #include <_ansi.h> | ||
78 | #include <stdlib.h> | ||
79 | |||
80 | #ifndef __GNUC__ | ||
81 | #define inline | ||
82 | #endif | ||
83 | |||
84 | static inline char *med3 _PARAMS((char *, char *, char *, int (*)())); | ||
85 | static inline void swapfunc _PARAMS((char *, char *, int, int)); | ||
86 | |||
87 | #define min(a, b) (a) < (b) ? a : b | ||
88 | |||
89 | /* | ||
90 | * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". | ||
91 | */ | ||
92 | #define swapcode(TYPE, parmi, parmj, n) { \ | ||
93 | long i = (n) / sizeof (TYPE); \ | ||
94 | register TYPE *pi = (TYPE *) (parmi); \ | ||
95 | register TYPE *pj = (TYPE *) (parmj); \ | ||
96 | do { \ | ||
97 | register TYPE t = *pi; \ | ||
98 | *pi++ = *pj; \ | ||
99 | *pj++ = t; \ | ||
100 | } while (--i > 0); \ | ||
101 | } | ||
102 | |||
103 | #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ | ||
104 | es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; | ||
105 | |||
106 | static inline void | ||
107 | _DEFUN(swapfunc, (a, b, n, swaptype), | ||
108 | char *a _AND | ||
109 | char *b _AND | ||
110 | int n _AND | ||
111 | int swaptype) | ||
112 | { | ||
113 | if(swaptype <= 1) | ||
114 | swapcode(long, a, b, n) | ||
115 | else | ||
116 | swapcode(char, a, b, n) | ||
117 | } | ||
118 | |||
119 | #define swap(a, b) \ | ||
120 | if (swaptype == 0) { \ | ||
121 | long t = *(long *)(a); \ | ||
122 | *(long *)(a) = *(long *)(b); \ | ||
123 | *(long *)(b) = t; \ | ||
124 | } else \ | ||
125 | swapfunc(a, b, es, swaptype) | ||
126 | |||
127 | #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) | ||
128 | |||
129 | static inline char * | ||
130 | _DEFUN(med3, (a, b, c, cmp), | ||
131 | char *a _AND | ||
132 | char *b _AND | ||
133 | char *c _AND | ||
134 | int (*cmp)()) | ||
135 | { | ||
136 | return cmp(a, b) < 0 ? | ||
137 | (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) | ||
138 | :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); | ||
139 | } | ||
140 | |||
141 | void | ||
142 | _DEFUN(qsort, (a, n, es, cmp), | ||
143 | void *a _AND | ||
144 | size_t n _AND | ||
145 | size_t es _AND | ||
146 | int (*cmp)()) | ||
147 | { | ||
148 | char *pa, *pb, *pc, *pd, *pl, *pm, *pn; | ||
149 | int d, r, swaptype, swap_cnt; | ||
150 | |||
151 | loop: SWAPINIT(a, es); | ||
152 | swap_cnt = 0; | ||
153 | if (n < 7) { | ||
154 | for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) | ||
155 | for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; | ||
156 | pl -= es) | ||
157 | swap(pl, pl - es); | ||
158 | return; | ||
159 | } | ||
160 | pm = (char *) a + (n / 2) * es; | ||
161 | if (n > 7) { | ||
162 | pl = a; | ||
163 | pn = (char *) a + (n - 1) * es; | ||
164 | if (n > 40) { | ||
165 | d = (n / 8) * es; | ||
166 | pl = med3(pl, pl + d, pl + 2 * d, cmp); | ||
167 | pm = med3(pm - d, pm, pm + d, cmp); | ||
168 | pn = med3(pn - 2 * d, pn - d, pn, cmp); | ||
169 | } | ||
170 | pm = med3(pl, pm, pn, cmp); | ||
171 | } | ||
172 | swap(a, pm); | ||
173 | pa = pb = (char *) a + es; | ||
174 | |||
175 | pc = pd = (char *) a + (n - 1) * es; | ||
176 | for (;;) { | ||
177 | while (pb <= pc && (r = cmp(pb, a)) <= 0) { | ||
178 | if (r == 0) { | ||
179 | swap_cnt = 1; | ||
180 | swap(pa, pb); | ||
181 | pa += es; | ||
182 | } | ||
183 | pb += es; | ||
184 | } | ||
185 | while (pb <= pc && (r = cmp(pc, a)) >= 0) { | ||
186 | if (r == 0) { | ||
187 | swap_cnt = 1; | ||
188 | swap(pc, pd); | ||
189 | pd -= es; | ||
190 | } | ||
191 | pc -= es; | ||
192 | } | ||
193 | if (pb > pc) | ||
194 | break; | ||
195 | swap(pb, pc); | ||
196 | swap_cnt = 1; | ||
197 | pb += es; | ||
198 | pc -= es; | ||
199 | } | ||
200 | if (swap_cnt == 0) { /* Switch to insertion sort */ | ||
201 | for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) | ||
202 | for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; | ||
203 | pl -= es) | ||
204 | swap(pl, pl - es); | ||
205 | return; | ||
206 | } | ||
207 | |||
208 | pn = (char *) a + n * es; | ||
209 | r = min(pa - (char *)a, pb - pa); | ||
210 | vecswap(a, pb - r, r); | ||
211 | r = min(pd - pc, pn - pd - es); | ||
212 | vecswap(pb, pn - r, r); | ||
213 | if ((r = pb - pa) > es) | ||
214 | qsort(a, r / es, es, cmp); | ||
215 | if ((r = pd - pc) > es) { | ||
216 | /* Iterate rather than recurse to save stack space */ | ||
217 | a = pn - r; | ||
218 | n = r / es; | ||
219 | goto loop; | ||
220 | } | ||
221 | /* qsort(pn - r, r / es, es, cmp);*/ | ||
222 | } | ||