summaryrefslogtreecommitdiff
path: root/firmware/common/qsort.c
diff options
context:
space:
mode:
Diffstat (limited to 'firmware/common/qsort.c')
-rw-r--r--firmware/common/qsort.c252
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
5INDEX 5INDEX
6 qsort 6 qsort
7 7
8ANSI_SYNOPSIS 8ANSI_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
13TRAD_SYNOPSIS 13TRAD_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
21DESCRIPTION 21DESCRIPTION
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
84static inline char *med3 _PARAMS((char *, char *, char *, int (*cmp)(const _PTR,const _PTR))); 84static inline char *med3 _PARAMS((char *, char *, char *, int (*cmp)(const _PTR,const _PTR)));
85static inline void swapfunc _PARAMS((char *, char *, int, int)); 85static 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
106static inline void 106static 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
129static inline char * 129static 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
141void 141void
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
151loop: SWAPINIT(a, es); 151loop: 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}
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-12 14:56:23 +0000