FS#8961 - Anti-Aliased Fonts.
[kugel-rb.git] / firmware / common / qsort.c
blobb2071d447f76b2d8186f7ff7adacc9c82d031094
1 /*
2 FUNCTION
3 <<qsort>>---sort an array
5 INDEX
6 qsort
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 *) );
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]>)();
21 DESCRIPTION
22 <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects.
23 <[size]> describes the size of each element of the array.
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).
34 The array is sorted in place; that is, when <<qsort>> returns, the
35 array elements beginning at <[base]> have been reordered.
37 RETURNS
38 <<qsort>> does not return a result.
40 PORTABILITY
41 <<qsort>> is required by ANSI (without specifying the sorting algorithm).
44 /*-
45 * Copyright (c) 1992, 1993
46 * The Regents of the University of California. All rights reserved.
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.
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.
77 #include <_ansi.h>
78 #include <stdlib.h>
80 #ifndef __GNUC__
81 #define inline
82 #endif
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));
87 #define min(a, b) (a) < (b) ? a : b
90 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
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); \
103 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
104 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
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)
113 if(swaptype <= 1)
114 swapcode(long, a, b, n)
115 else
116 swapcode(char, a, b, n)
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)
127 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
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)(const _PTR,const _PTR))
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 ));
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)(const _PTR,const _PTR))
148 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
149 int d, r, swaptype, swap_cnt;
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;
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);
170 pm = med3(pl, pm, pn, cmp);
172 swap(a, pm);
173 pa = pb = (char *) a + es;
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;
183 pb += es;
185 while (pb <= pc && (r = cmp(pc, a)) >= 0) {
186 if (r == 0) {
187 swap_cnt = 1;
188 swap(pc, pd);
189 pd -= es;
191 pc -= es;
193 if (pb > pc)
194 break;
195 swap(pb, pc);
196 swap_cnt = 1;
197 pb += es;
198 pc -= es;
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;
208 pn = (char *) a + n * es;
209 r = min(pa - (char *)a, pb - pa);
210 vecswap(a, pb - r, r);
211 r = min((unsigned int)(pd - pc), pn - pd - es);
212 vecswap(pb, pn - r, r);
213 if ((unsigned int)(r = pb - pa) > es)
214 qsort(a, r / es, es, cmp);
215 if ((unsigned int)(r = pd - pc) > es) {
216 /* Iterate rather than recurse to save stack space */
217 a = pn - r;
218 n = r / es;
219 goto loop;
221 /* qsort(pn - r, r / es, es, cmp);*/