Mercurial > ecos

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