Mercurial > ecos
annotate packages/language/c/libc/current/src/stdlib/qsort.cxx @ 64:c38311975d4f ecos-sw-2000-01-28
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
| author | jlarmour |
|---|---|
| date | Fri, 28 Jan 2000 04:59:39 +0000 |
| parents | 443894e2e912 |
| children | bf00f99aec69 |
| rev | line source |
|---|---|
| 0 | 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#### | |
|
64
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
10 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
11 // ------------------------------------------- |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
12 // The contents of this file are subject to the Red Hat eCos Public License |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
13 // Version 1.0 (the "License"); you may not use this file except in |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
14 // compliance with the License. You may obtain a copy of the License at |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
15 // http://sourceware.cygnus.com/ecos |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
16 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
17 // Software distributed under the License is distributed on an |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
18 // basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
19 // License for the specific language governing rights and limitations under |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
20 // the License. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
21 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
22 // The Original Code is eCos - Embedded Configurable Operating System, |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
23 // released September 30, 1998. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
24 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
25 // The Initial Developer of the Original Code is Red Hat. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
26 // Portions created by Red Hat are |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
27 // Copyright (C) 1998, 1999, 2000 Red Hat, Inc. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
28 // All Rights Reserved. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
29 // ------------------------------------------- |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
30 // |
| 0 | 31 //####COPYRIGHTEND#### |
| 32 //=========================================================================== | |
| 33 //#####DESCRIPTIONBEGIN#### | |
| 34 // | |
| 35 // Author(s): jlarmour | |
| 2 | 36 // Contributors: jlarmour |
| 0 | 37 // Date: 1998-02-13 |
| 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. All advertising materials mentioning features or use of this software | |
| 61 * must display the following acknowledgement: | |
| 62 * This product includes software developed by the University of | |
| 63 * California, Berkeley and its contributors. | |
| 64 * 4. Neither the name of the University nor the names of its contributors | |
| 65 * may be used to endorse or promote products derived from this software | |
| 66 * without specific prior written permission. | |
| 67 * | |
| 68 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
| 69 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
| 70 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
| 71 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
| 72 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
| 73 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
| 74 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
| 75 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
| 76 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
| 77 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
| 78 * SUCH DAMAGE. | |
| 79 */ | |
| 80 | |
| 81 | |
| 82 | |
| 83 // CONFIGURATION | |
| 84 | |
| 85 #include <pkgconf/libc.h> // Configuration header | |
| 86 | |
| 87 // Include the C library? | |
| 88 #ifdef CYGPKG_LIBC | |
| 89 | |
| 90 // INCLUDES | |
| 91 | |
| 92 #include <cyg/infra/cyg_type.h> // Common type definitions and support | |
| 93 #include <cyg/infra/cyg_trac.h> // Tracing support | |
| 94 #include <cyg/infra/cyg_ass.h> // Assertion support | |
| 95 #include <stdlib.h> // Header for all stdlib functions | |
| 96 // (like this one) | |
| 97 #include "clibincl/stdlibsupp.hxx" // Support for stdlib functions | |
| 98 | |
| 99 // TRACING | |
| 100 | |
| 101 # if defined(CYGDBG_USE_TRACING) && defined(CYGNUM_LIBC_QSORT_TRACE_LEVEL) | |
| 102 static int qsort_trace = CYGNUM_LIBC_QSORT_TRACE_LEVEL; | |
| 103 # define TL1 (0 < qsort_trace) | |
| 104 # else | |
| 105 # define TL1 (0) | |
| 106 # endif | |
| 107 | |
| 108 | |
| 109 // EXPORTED SYMBOLS | |
| 110 | |
| 111 externC void | |
| 112 qsort( void *base, size_t nmemb, size_t size, Cyg_comparison_fn_t compar ) \ | |
| 113 CYGPRI_LIBC_WEAK_ALIAS("_qsort"); | |
| 114 | |
| 115 | |
| 116 // FUNCTION PROTOTYPES | |
| 117 | |
| 118 static __inline__ char *med3(char *, char *, char *, Cyg_comparison_fn_t); | |
| 119 static __inline__ void swapfunc(char *, char *, int, int); | |
| 120 | |
| 121 | |
| 122 // MACRO FUNCTIONS | |
| 123 | |
| 124 #define min(a, b) ((a) < (b) ? (a) : (b)) | |
| 125 | |
| 126 // | |
| 127 // Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". | |
| 128 // | |
| 129 | |
| 130 #define swapcode(TYPE, parmi, parmj, n) do { \ | |
| 131 long i = (n) / sizeof (TYPE); \ | |
| 132 TYPE *pi = (TYPE *) (parmi); \ | |
| 133 TYPE *pj = (TYPE *) (parmj); \ | |
| 134 do { \ | |
| 135 TYPE t = *pi; \ | |
| 136 *pi++ = *pj; \ | |
| 137 *pj++ = t; \ | |
| 138 } while (--i > 0); \ | |
| 139 } while (0) | |
| 140 | |
| 141 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ | |
| 142 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; | |
| 143 | |
| 144 | |
| 145 #define swap(a, b) \ | |
| 146 if (swaptype == 0) { \ | |
| 147 long t = *(long *)(a); \ | |
| 148 *(long *)(a) = *(long *)(b); \ | |
| 149 *(long *)(b) = t; \ | |
| 150 } else \ | |
| 151 swapfunc(a, b, size, swaptype) | |
| 152 | |
| 153 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) | |
| 154 | |
| 155 | |
| 156 // FUNCTIONS | |
| 157 | |
| 158 // Debug wrapper for comparison function | |
| 159 static __inline__ int | |
| 160 cmp_wrapper( Cyg_comparison_fn_t cmp, void *x, void *y ) | |
| 161 { | |
| 162 int retval; | |
| 163 CYG_TRACE3( TL1, "Calling comparison function address %08x with args " | |
| 164 "( %08x, %08x )", cmp, x, y ); | |
| 165 retval = cmp(x, y); | |
| 166 | |
| 167 CYG_TRACE1( TL1, "Comparison function returned %d", retval ); | |
| 168 | |
| 169 return retval; | |
| 170 } // cmp_wrapper() | |
| 171 | |
| 172 static __inline__ void | |
| 173 swapfunc( char *a, char *b, int n, int swaptype) | |
| 174 { | |
| 175 if(swaptype <= 1) | |
| 176 swapcode(long, a, b, n); | |
| 177 else | |
| 178 swapcode(char, a, b, n); | |
| 179 } // swapfunc() | |
| 180 | |
| 181 | |
| 182 static __inline__ char * | |
| 183 med3( char *a, char *b, char *c, Cyg_comparison_fn_t cmp ) | |
| 184 { | |
| 185 return cmp_wrapper(cmp, a, b) < 0 ? | |
| 186 (cmp_wrapper(cmp, b, c) < 0 ? b : (cmp_wrapper(cmp, a, c) < 0 ? c : a )) | |
| 187 :(cmp_wrapper(cmp, b, c) > 0 ? b : (cmp_wrapper(cmp, a, c) < 0 ? a : c )); | |
| 188 } // med3() | |
| 189 | |
| 190 | |
| 191 void | |
| 192 _qsort( void *base, size_t nmemb, size_t size, Cyg_comparison_fn_t compar ) | |
| 193 { | |
| 194 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; | |
| 195 int d, r, swaptype, swap_cnt; | |
| 196 | |
| 2 | 197 CYG_REPORT_FUNCNAME( "_qsort" ); |
| 0 | 198 CYG_REPORT_FUNCARG4( "base=%08x, nmemb=%d, size=%d, compar=%08x", |
| 199 base, nmemb, size, compar ); | |
| 200 | |
| 201 CYG_CHECK_DATA_PTR( base, "base is not a valid pointer!" ); | |
| 202 CYG_CHECK_FUNC_PTR( compar, "compar is not a valid function pointer!" ); | |
| 203 | |
| 204 loop: | |
| 205 SWAPINIT(base, size); | |
| 206 swap_cnt = 0; | |
| 207 if (nmemb < 7) { | |
| 208 for (pm = (char *) base + size; | |
| 209 pm < (char *) base + nmemb * size; | |
| 210 pm += size) | |
| 211 for (pl = pm; pl > (char *) base && cmp_wrapper( compar, pl - size, pl) > 0; | |
| 212 pl -= size) | |
| 213 swap(pl, pl - size); | |
| 214 { | |
| 215 CYG_REPORT_RETURN(); | |
| 216 return; | |
| 217 } // for | |
| 218 } // if | |
| 219 pm = (char *) base + (nmemb / 2) * size; | |
| 220 if (nmemb > 7) { | |
| 221 pl = (char *) base; | |
| 222 pn = (char *) base + (nmemb - 1) * size; | |
| 223 if (nmemb > 40) { | |
| 224 d = (nmemb / 8) * size; | |
| 225 pl = med3(pl, pl + d, pl + 2 * d, compar); | |
| 226 pm = med3(pm - d, pm, pm + d, compar); | |
| 227 pn = med3(pn - 2 * d, pn - d, pn, compar); | |
| 228 } // if | |
| 229 pm = med3(pl, pm, pn, compar); | |
| 230 } // if | |
| 231 swap( (char *)base, pm ); | |
| 232 pa = pb = (char *) base + size; | |
| 233 | |
| 234 pc = pd = (char *) base + (nmemb - 1) * size; | |
| 235 for (;;) { | |
| 236 while (pb <= pc && (r = cmp_wrapper( compar, pb, base)) <= 0) { | |
| 237 if (r == 0) { | |
| 238 swap_cnt = 1; | |
| 239 swap(pa, pb); | |
| 240 pa += size; | |
| 241 } // if | |
| 242 pb += size; | |
| 243 } // while | |
| 244 while (pb <= pc && (r = cmp_wrapper( compar, pc, base)) >= 0) { | |
| 245 if (r == 0) { | |
| 246 swap_cnt = 1; | |
| 247 swap(pc, pd); | |
| 248 pd -= size; | |
| 249 } // if | |
| 250 pc -= size; | |
| 251 } // while | |
| 252 if (pb > pc) | |
| 253 break; | |
| 254 swap(pb, pc); | |
| 255 swap_cnt = 1; | |
| 256 pb += size; | |
| 257 pc -= size; | |
| 258 } // for | |
| 259 if (swap_cnt == 0) { // Switch to insertion sort | |
| 260 for (pm = (char *) base + size; | |
| 261 pm < (char *) base + nmemb * size; | |
| 262 pm += size) | |
| 263 for (pl = pm; pl > (char *) base && cmp_wrapper( compar, pl - size, pl) > 0; | |
| 264 pl -= size) | |
| 265 swap(pl, pl - size); | |
| 266 { | |
| 267 CYG_REPORT_RETURN(); | |
| 268 return; | |
| 269 } // for | |
| 270 } //if | |
| 271 | |
| 272 pn = (char *) base + nmemb * size; | |
| 273 r = min(pa - (char *)base, pb - pa); | |
| 274 vecswap((char *)base, pb - r, r); | |
| 275 r = min( (unsigned)(pd - pc), pn - pd - size ); | |
| 276 vecswap(pb, pn - r, r); | |
| 277 if ((unsigned)(r = pb - pa) > size) | |
| 278 _qsort(base, r / size, size, compar); | |
| 279 if ((unsigned)(r = pd - pc) > size) { | |
| 280 // Iterate rather than recurse to save stack space | |
| 281 base = pn - r; | |
| 282 nmemb = r / size; | |
| 283 goto loop; | |
| 284 } // if | |
| 285 /* qsort(pn - r, r / size, size, compar);*/ | |
| 286 | |
| 287 CYG_REPORT_RETURN(); | |
| 288 } // _qsort() | |
| 289 | |
| 290 #endif // ifdef CYGPKG_LIBC | |
| 291 | |
| 292 // EOF qsort.cxx |