Mercurial > ecos

comparison packages/language/c/libc/stdlib/current/src/qsort.cxx @ 115:6ed91473a1cd ecos-sw-2000-08-21

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge from eCos master repository on 2000-08-21-22:40:54-BST
author jlarmour
date Fri, 25 Aug 2000 17:32:38 +0000
parents
children e0c0827131d1
comparison
equal deleted inserted replaced
114:5ad2b71d525e 115:6ed91473a1cd
1 //===========================================================================
2 //
3 // qsort.cxx
4 //
5 // ANSI standard sorting function defined in section 7.10.5.2
6 // of the standard
7 //
8 //===========================================================================
9 //####COPYRIGHTBEGIN####
10 //
11 // -------------------------------------------
12 // The contents of this file are subject to the Red Hat eCos Public License
13 // Version 1.1 (the "License"); you may not use this file except in
14 // compliance with the License. You may obtain a copy of the License at
15 // http://www.redhat.com/
16 //
17 // Software distributed under the License is distributed on an "AS IS"
18 // basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
19 // License for the specific language governing rights and limitations under
20 // the License.
21 //
22 // The Original Code is eCos - Embedded Configurable Operating System,
23 // released September 30, 1998.
24 //
25 // The Initial Developer of the Original Code is Red Hat.
26 // Portions created by Red Hat are
27 // Copyright (C) 1998, 1999, 2000 Red Hat, Inc.
28 // All Rights Reserved.
29 // -------------------------------------------
30 //
31 //####COPYRIGHTEND####
32 //===========================================================================
33 //#####DESCRIPTIONBEGIN####
34 //
35 // Author(s): jlarmour
36 // Contributors:
37 // Date: 2000-04-30
38 // Purpose:
39 // Description:
40 // Usage:
41 //
42 //####DESCRIPTIONEND####
43 //
44 //===========================================================================
45 //
46 // This code is based on original code with the following copyright:
47 //
48 /*-
49 * Copyright (c) 1992, 1993
50 * The Regents of the University of California. All rights reserved.
51 *
52 * Redistribution and use in source and binary forms, with or without
53 * modification, are permitted provided that the following conditions
54 * are met:
55 * 1. Redistributions of source code must retain the above copyright
56 * notice, this list of conditions and the following disclaimer.
57 * 2. Redistributions in binary form must reproduce the above copyright
58 * notice, this list of conditions and the following disclaimer in the
59 * documentation and/or other materials provided with the distribution.
60 * 3. 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
78
79 // CONFIGURATION
80
81 #include <pkgconf/libc_stdlib.h> // Configuration header
82
83 // INCLUDES
84
85 #include <cyg/infra/cyg_type.h> // Common type definitions and support
86 #include <cyg/infra/cyg_trac.h> // Tracing support
87 #include <cyg/infra/cyg_ass.h> // Assertion support
88 #include <stdlib.h> // Header for all stdlib functions
89 // (like this one)
90
91 // TRACING
92
93 # if defined(CYGDBG_USE_TRACING) && defined(CYGNUM_LIBC_QSORT_TRACE_LEVEL)
94 static int qsort_trace = CYGNUM_LIBC_QSORT_TRACE_LEVEL;
95 # define TL1 (0 < qsort_trace)
96 # else
97 # define TL1 (0)
98 # endif
99
100
101 // FUNCTION PROTOTYPES
102
103 static __inline__ char *med3(char *, char *, char *, __qsort_comparison_fn_t);
104 static __inline__ void swapfunc(char *, char *, int, int);
105
106
107 // MACRO FUNCTIONS
108
109 #define min(a, b) ((a) < (b) ? (a) : (b))
110
111 //
112 // Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
113 //
114
115 #define swapcode(TYPE, parmi, parmj, n) do { \
116 long i = (n) / sizeof (TYPE); \
117 TYPE *pi = (TYPE *) (parmi); \
118 TYPE *pj = (TYPE *) (parmj); \
119 do { \
120 TYPE t = *pi; \
121 *pi++ = *pj; \
122 *pj++ = t; \
123 } while (--i > 0); \
124 } while (0)
125
126 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
127 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
128
129
130 #define swap(a, b) \
131 if (swaptype == 0) { \
132 long t = *(long *)(a); \
133 *(long *)(a) = *(long *)(b); \
134 *(long *)(b) = t; \
135 } else \
136 swapfunc(a, b, size, swaptype)
137
138 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
139
140
141 // FUNCTIONS
142
143 // Debug wrapper for comparison function
144 static __inline__ int
145 cmp_wrapper( __qsort_comparison_fn_t cmp, void *x, void *y )
146 {
147 int retval;
148 CYG_TRACE3( TL1, "Calling comparison function address %08x with args "
149 "( %08x, %08x )", cmp, x, y );
150 retval = cmp(x, y);
151
152 CYG_TRACE1( TL1, "Comparison function returned %d", retval );
153
154 return retval;
155 } // cmp_wrapper()
156
157 static __inline__ void
158 swapfunc( char *a, char *b, int n, int swaptype)
159 {
160 if(swaptype <= 1)
161 swapcode(long, a, b, n);
162 else
163 swapcode(char, a, b, n);
164 } // swapfunc()
165
166
167 static __inline__ char *
168 med3( char *a, char *b, char *c, __qsort_comparison_fn_t cmp )
169 {
170 return cmp_wrapper(cmp, a, b) < 0 ?
171 (cmp_wrapper(cmp, b, c) < 0 ? b : (cmp_wrapper(cmp, a, c) < 0 ? c : a ))
172 :(cmp_wrapper(cmp, b, c) > 0 ? b : (cmp_wrapper(cmp, a, c) < 0 ? a : c ));
173 } // med3()
174
175
176 void
177 qsort( void *base, size_t nmemb, size_t size, __qsort_comparison_fn_t compar )
178 {
179 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
180 int d, r, swaptype, swap_cnt;
181
182 CYG_REPORT_FUNCNAME( "qsort" );
183 CYG_REPORT_FUNCARG4( "base=%08x, nmemb=%d, size=%d, compar=%08x",
184 base, nmemb, size, compar );
185
186 CYG_CHECK_DATA_PTR( base, "base is not a valid pointer!" );
187 CYG_CHECK_FUNC_PTR( compar, "compar is not a valid function pointer!" );
188
189 loop:
190 SWAPINIT(base, size);
191 swap_cnt = 0;
192 if (nmemb < 7) {
193 for (pm = (char *) base + size;
194 pm < (char *) base + nmemb * size;
195 pm += size)
196 for (pl = pm; pl > (char *) base && cmp_wrapper( compar, pl - size, pl) > 0;
197 pl -= size)
198 swap(pl, pl - size);
199 {
200 CYG_REPORT_RETURN();
201 return;
202 } // for
203 } // if
204 pm = (char *) base + (nmemb / 2) * size;
205 if (nmemb > 7) {
206 pl = (char *) base;
207 pn = (char *) base + (nmemb - 1) * size;
208 if (nmemb > 40) {
209 d = (nmemb / 8) * size;
210 pl = med3(pl, pl + d, pl + 2 * d, compar);
211 pm = med3(pm - d, pm, pm + d, compar);
212 pn = med3(pn - 2 * d, pn - d, pn, compar);
213 } // if
214 pm = med3(pl, pm, pn, compar);
215 } // if
216 swap( (char *)base, pm );
217 pa = pb = (char *) base + size;
218
219 pc = pd = (char *) base + (nmemb - 1) * size;
220 for (;;) {
221 while (pb <= pc && (r = cmp_wrapper( compar, pb, base)) <= 0) {
222 if (r == 0) {
223 swap_cnt = 1;
224 swap(pa, pb);
225 pa += size;
226 } // if
227 pb += size;
228 } // while
229 while (pb <= pc && (r = cmp_wrapper( compar, pc, base)) >= 0) {
230 if (r == 0) {
231 swap_cnt = 1;
232 swap(pc, pd);
233 pd -= size;
234 } // if
235 pc -= size;
236 } // while
237 if (pb > pc)
238 break;
239 swap(pb, pc);
240 swap_cnt = 1;
241 pb += size;
242 pc -= size;
243 } // for
244 if (swap_cnt == 0) { // Switch to insertion sort
245 for (pm = (char *) base + size;
246 pm < (char *) base + nmemb * size;
247 pm += size)
248 for (pl = pm; pl > (char *) base && cmp_wrapper( compar, pl - size, pl) > 0;
249 pl -= size)
250 swap(pl, pl - size);
251 {
252 CYG_REPORT_RETURN();
253 return;
254 } // for
255 } //if
256
257 pn = (char *) base + nmemb * size;
258 r = min(pa - (char *)base, pb - pa);
259 vecswap((char *)base, pb - r, r);
260 r = min( (unsigned)(pd - pc), pn - pd - size );
261 vecswap(pb, pn - r, r);
262 if ((unsigned)(r = pb - pa) > size)
263 qsort(base, r / size, size, compar);
264 if ((unsigned)(r = pd - pc) > size) {
265 // Iterate rather than recurse to save stack space
266 base = pn - r;
267 nmemb = r / size;
268 goto loop;
269 } // if
270 /* qsort(pn - r, r / size, size, compar);*/
271
272 CYG_REPORT_RETURN();
273 } // qsort()
274
275 // EOF qsort.cxx