diff options
Diffstat (limited to 'firmware/common/qsort.c')
-rw-r--r-- | firmware/common/qsort.c | 252 |
1 files changed, 126 insertions, 126 deletions
diff --git a/firmware/common/qsort.c b/firmware/common/qsort.c index b2071d447f..8c4d1ad511 100644 --- a/firmware/common/qsort.c +++ b/firmware/common/qsort.c | |||
@@ -3,20 +3,20 @@ FUNCTION | |||
3 | <<qsort>>---sort an array | 3 | <<qsort>>---sort an array |
4 | 4 | ||
5 | INDEX | 5 | INDEX |
6 | qsort | 6 | qsort |
7 | 7 | ||
8 | ANSI_SYNOPSIS | 8 | ANSI_SYNOPSIS |
9 | #include <stdlib.h> | 9 | #include <stdlib.h> |
10 | void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>, | 10 | void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>, |
11 | int (*<[compar]>)(const void *, const void *) ); | 11 | int (*<[compar]>)(const void *, const void *) ); |
12 | 12 | ||
13 | TRAD_SYNOPSIS | 13 | TRAD_SYNOPSIS |
14 | #include <stdlib.h> | 14 | #include <stdlib.h> |
15 | qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> ) | 15 | qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> ) |
16 | char *<[base]>; | 16 | char *<[base]>; |
17 | size_t <[nmemb]>; | 17 | size_t <[nmemb]>; |
18 | size_t <[size]>; | 18 | size_t <[size]>; |
19 | int (*<[compar]>)(); | 19 | int (*<[compar]>)(); |
20 | 20 | ||
21 | DESCRIPTION | 21 | DESCRIPTION |
22 | <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects. | 22 | <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects. |
@@ -43,7 +43,7 @@ PORTABILITY | |||
43 | 43 | ||
44 | /*- | 44 | /*- |
45 | * Copyright (c) 1992, 1993 | 45 | * Copyright (c) 1992, 1993 |
46 | * The Regents of the University of California. All rights reserved. | 46 | * The Regents of the University of California. All rights reserved. |
47 | * | 47 | * |
48 | * Redistribution and use in source and binary forms, with or without | 48 | * Redistribution and use in source and binary forms, with or without |
49 | * modification, are permitted provided that the following conditions | 49 | * modification, are permitted provided that the following conditions |
@@ -55,8 +55,8 @@ PORTABILITY | |||
55 | * documentation and/or other materials provided with the distribution. | 55 | * documentation and/or other materials provided with the distribution. |
56 | * 3. All advertising materials mentioning features or use of this software | 56 | * 3. All advertising materials mentioning features or use of this software |
57 | * must display the following acknowledgement: | 57 | * must display the following acknowledgement: |
58 | * This product includes software developed by the University of | 58 | * This product includes software developed by the University of |
59 | * California, Berkeley and its contributors. | 59 | * California, Berkeley and its contributors. |
60 | * 4. Neither the name of the University nor the names of 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 | 61 | * may be used to endorse or promote products derived from this software |
62 | * without specific prior written permission. | 62 | * without specific prior written permission. |
@@ -81,142 +81,142 @@ PORTABILITY | |||
81 | #define inline | 81 | #define inline |
82 | #endif | 82 | #endif |
83 | 83 | ||
84 | static inline char *med3 _PARAMS((char *, char *, char *, int (*cmp)(const _PTR,const _PTR))); | 84 | static inline char *med3 _PARAMS((char *, char *, char *, int (*cmp)(const _PTR,const _PTR))); |
85 | static inline void swapfunc _PARAMS((char *, char *, int, int)); | 85 | static inline void swapfunc _PARAMS((char *, char *, int, int)); |
86 | 86 | ||
87 | #define min(a, b) (a) < (b) ? a : b | 87 | #define min(a, b) (a) < (b) ? a : b |
88 | 88 | ||
89 | /* | 89 | /* |
90 | * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". | 90 | * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". |
91 | */ | 91 | */ |
92 | #define swapcode(TYPE, parmi, parmj, n) { \ | 92 | #define swapcode(TYPE, parmi, parmj, n) { \ |
93 | long i = (n) / sizeof (TYPE); \ | 93 | long i = (n) / sizeof (TYPE); \ |
94 | register TYPE *pi = (TYPE *) (parmi); \ | 94 | register TYPE *pi = (TYPE *) (parmi); \ |
95 | register TYPE *pj = (TYPE *) (parmj); \ | 95 | register TYPE *pj = (TYPE *) (parmj); \ |
96 | do { \ | 96 | do { \ |
97 | register TYPE t = *pi; \ | 97 | register TYPE t = *pi; \ |
98 | *pi++ = *pj; \ | 98 | *pi++ = *pj; \ |
99 | *pj++ = t; \ | 99 | *pj++ = t; \ |
100 | } while (--i > 0); \ | 100 | } while (--i > 0); \ |
101 | } | 101 | } |
102 | 102 | ||
103 | #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ | 103 | #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ |
104 | es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; | 104 | es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; |
105 | 105 | ||
106 | static inline void | 106 | static inline void |
107 | _DEFUN(swapfunc, (a, b, n, swaptype), | 107 | _DEFUN(swapfunc, (a, b, n, swaptype), |
108 | char *a _AND | 108 | char *a _AND |
109 | char *b _AND | 109 | char *b _AND |
110 | int n _AND | 110 | int n _AND |
111 | int swaptype) | 111 | int swaptype) |
112 | { | 112 | { |
113 | if(swaptype <= 1) | 113 | if(swaptype <= 1) |
114 | swapcode(long, a, b, n) | 114 | swapcode(long, a, b, n) |
115 | else | 115 | else |
116 | swapcode(char, a, b, n) | 116 | swapcode(char, a, b, n) |
117 | } | 117 | } |
118 | 118 | ||
119 | #define swap(a, b) \ | 119 | #define swap(a, b) \ |
120 | if (swaptype == 0) { \ | 120 | if (swaptype == 0) { \ |
121 | long t = *(long *)(a); \ | 121 | long t = *(long *)(a); \ |
122 | *(long *)(a) = *(long *)(b); \ | 122 | *(long *)(a) = *(long *)(b); \ |
123 | *(long *)(b) = t; \ | 123 | *(long *)(b) = t; \ |
124 | } else \ | 124 | } else \ |
125 | swapfunc(a, b, es, swaptype) | 125 | swapfunc(a, b, es, swaptype) |
126 | 126 | ||
127 | #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) | 127 | #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) |
128 | 128 | ||
129 | static inline char * | 129 | static inline char * |
130 | _DEFUN(med3, (a, b, c, cmp), | 130 | _DEFUN(med3, (a, b, c, cmp), |
131 | char *a _AND | 131 | char *a _AND |
132 | char *b _AND | 132 | char *b _AND |
133 | char *c _AND | 133 | char *c _AND |
134 | int (*cmp)(const _PTR,const _PTR)) | 134 | int (*cmp)(const _PTR,const _PTR)) |
135 | { | 135 | { |
136 | return cmp(a, b) < 0 ? | 136 | return cmp(a, b) < 0 ? |
137 | (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) | 137 | (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) |
138 | :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); | 138 | :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); |
139 | } | 139 | } |
140 | 140 | ||
141 | void | 141 | void |
142 | _DEFUN(qsort, (a, n, es, cmp), | 142 | _DEFUN(qsort, (a, n, es, cmp), |
143 | void *a _AND | 143 | void *a _AND |
144 | size_t n _AND | 144 | size_t n _AND |
145 | size_t es _AND | 145 | size_t es _AND |
146 | int (*cmp)(const _PTR,const _PTR)) | 146 | int (*cmp)(const _PTR,const _PTR)) |
147 | { | 147 | { |
148 | char *pa, *pb, *pc, *pd, *pl, *pm, *pn; | 148 | char *pa, *pb, *pc, *pd, *pl, *pm, *pn; |
149 | int d, r, swaptype, swap_cnt; | 149 | int d, r, swaptype, swap_cnt; |
150 | 150 | ||
151 | loop: SWAPINIT(a, es); | 151 | loop: SWAPINIT(a, es); |
152 | swap_cnt = 0; | 152 | swap_cnt = 0; |
153 | if (n < 7) { | 153 | if (n < 7) { |
154 | for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) | 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; | 155 | for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; |
156 | pl -= es) | 156 | pl -= es) |
157 | swap(pl, pl - es); | 157 | swap(pl, pl - es); |
158 | return; | 158 | return; |
159 | } | 159 | } |
160 | pm = (char *) a + (n / 2) * es; | 160 | pm = (char *) a + (n / 2) * es; |
161 | if (n > 7) { | 161 | if (n > 7) { |
162 | pl = a; | 162 | pl = a; |
163 | pn = (char *) a + (n - 1) * es; | 163 | pn = (char *) a + (n - 1) * es; |
164 | if (n > 40) { | 164 | if (n > 40) { |
165 | d = (n / 8) * es; | 165 | d = (n / 8) * es; |
166 | pl = med3(pl, pl + d, pl + 2 * d, cmp); | 166 | pl = med3(pl, pl + d, pl + 2 * d, cmp); |
167 | pm = med3(pm - d, pm, pm + d, cmp); | 167 | pm = med3(pm - d, pm, pm + d, cmp); |
168 | pn = med3(pn - 2 * d, pn - d, pn, cmp); | 168 | pn = med3(pn - 2 * d, pn - d, pn, cmp); |
169 | } | 169 | } |
170 | pm = med3(pl, pm, pn, cmp); | 170 | pm = med3(pl, pm, pn, cmp); |
171 | } | 171 | } |
172 | swap(a, pm); | 172 | swap(a, pm); |
173 | pa = pb = (char *) a + es; | 173 | pa = pb = (char *) a + es; |
174 | 174 | ||
175 | pc = pd = (char *) a + (n - 1) * es; | 175 | pc = pd = (char *) a + (n - 1) * es; |
176 | for (;;) { | 176 | for (;;) { |
177 | while (pb <= pc && (r = cmp(pb, a)) <= 0) { | 177 | while (pb <= pc && (r = cmp(pb, a)) <= 0) { |
178 | if (r == 0) { | 178 | if (r == 0) { |
179 | swap_cnt = 1; | 179 | swap_cnt = 1; |
180 | swap(pa, pb); | 180 | swap(pa, pb); |
181 | pa += es; | 181 | pa += es; |
182 | } | 182 | } |
183 | pb += es; | 183 | pb += es; |
184 | } | 184 | } |
185 | while (pb <= pc && (r = cmp(pc, a)) >= 0) { | 185 | while (pb <= pc && (r = cmp(pc, a)) >= 0) { |
186 | if (r == 0) { | 186 | if (r == 0) { |
187 | swap_cnt = 1; | 187 | swap_cnt = 1; |
188 | swap(pc, pd); | 188 | swap(pc, pd); |
189 | pd -= es; | 189 | pd -= es; |
190 | } | 190 | } |
191 | pc -= es; | 191 | pc -= es; |
192 | } | 192 | } |
193 | if (pb > pc) | 193 | if (pb > pc) |
194 | break; | 194 | break; |
195 | swap(pb, pc); | 195 | swap(pb, pc); |
196 | swap_cnt = 1; | 196 | swap_cnt = 1; |
197 | pb += es; | 197 | pb += es; |
198 | pc -= es; | 198 | pc -= es; |
199 | } | 199 | } |
200 | if (swap_cnt == 0) { /* Switch to insertion sort */ | 200 | if (swap_cnt == 0) { /* Switch to insertion sort */ |
201 | for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) | 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; | 202 | for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; |
203 | pl -= es) | 203 | pl -= es) |
204 | swap(pl, pl - es); | 204 | swap(pl, pl - es); |
205 | return; | 205 | return; |
206 | } | 206 | } |
207 | 207 | ||
208 | pn = (char *) a + n * es; | 208 | pn = (char *) a + n * es; |
209 | r = min(pa - (char *)a, pb - pa); | 209 | r = min(pa - (char *)a, pb - pa); |
210 | vecswap(a, pb - r, r); | 210 | vecswap(a, pb - r, r); |
211 | r = min((unsigned int)(pd - pc), pn - pd - es); | 211 | r = min((unsigned int)(pd - pc), pn - pd - es); |
212 | vecswap(pb, pn - r, r); | 212 | vecswap(pb, pn - r, r); |
213 | if ((unsigned int)(r = pb - pa) > es) | 213 | if ((unsigned int)(r = pb - pa) > es) |
214 | qsort(a, r / es, es, cmp); | 214 | qsort(a, r / es, es, cmp); |
215 | if ((unsigned int)(r = pd - pc) > es) { | 215 | if ((unsigned int)(r = pd - pc) > es) { |
216 | /* Iterate rather than recurse to save stack space */ | 216 | /* Iterate rather than recurse to save stack space */ |
217 | a = pn - r; | 217 | a = pn - r; |
218 | n = r / es; | 218 | n = r / es; |
219 | goto loop; | 219 | goto loop; |
220 | } | 220 | } |
221 | /* qsort(pn - r, r / es, es, cmp);*/ | 221 | /* qsort(pn - r, r / es, es, cmp);*/ |
222 | } | 222 | } |