qsort.c revision 1.1.2.2
1 1.1.2.2 he /*- 2 1.1.2.2 he * Copyright (c) 1992, 1993 3 1.1.2.2 he * The Regents of the University of California. All rights reserved. 4 1.1.2.2 he * 5 1.1.2.2 he * Redistribution and use in source and binary forms, with or without 6 1.1.2.2 he * modification, are permitted provided that the following conditions 7 1.1.2.2 he * are met: 8 1.1.2.2 he * 1. Redistributions of source code must retain the above copyright 9 1.1.2.2 he * notice, this list of conditions and the following disclaimer. 10 1.1.2.2 he * 2. Redistributions in binary form must reproduce the above copyright 11 1.1.2.2 he * notice, this list of conditions and the following disclaimer in the 12 1.1.2.2 he * documentation and/or other materials provided with the distribution. 13 1.1.2.2 he * 3. All advertising materials mentioning features or use of this software 14 1.1.2.2 he * must display the following acknowledgement: 15 1.1.2.2 he * This product includes software developed by the University of 16 1.1.2.2 he * California, Berkeley and its contributors. 17 1.1.2.2 he * 4. Neither the name of the University nor the names of its contributors 18 1.1.2.2 he * may be used to endorse or promote products derived from this software 19 1.1.2.2 he * without specific prior written permission. 20 1.1.2.2 he * 21 1.1.2.2 he * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 1.1.2.2 he * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 1.1.2.2 he * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 1.1.2.2 he * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 1.1.2.2 he * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 1.1.2.2 he * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 1.1.2.2 he * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 1.1.2.2 he * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 1.1.2.2 he * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 1.1.2.2 he * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 1.1.2.2 he * SUCH DAMAGE. 32 1.1.2.2 he * 33 1.1.2.2 he * $FreeBSD: src/sys/libkern/qsort.c,v 1.12 2002/11/09 12:55:06 alfred Exp $ 34 1.1.2.2 he * $NetBSD: qsort.c,v 1.1.2.2 2004/05/22 17:12:43 he Exp $ 35 1.1.2.2 he */ 36 1.1.2.2 he 37 1.1.2.2 he #include <sys/cdefs.h> 38 1.1.2.2 he #include <sys/types.h> 39 1.1.2.2 he 40 1.1.2.2 he typedef int cmp_t(const void *, const void *); 41 1.1.2.2 he static __inline char *med3(char *, char *, char *, cmp_t *); 42 1.1.2.2 he static __inline void swapfunc(char *, char *, int, int); 43 1.1.2.2 he 44 1.1.2.2 he #define min(a, b) (a) < (b) ? (a) : (b) 45 1.1.2.2 he 46 1.1.2.2 he void qsort(void *a, size_t n, size_t es, cmp_t *cmp); 47 1.1.2.2 he 48 1.1.2.2 he /* 49 1.1.2.2 he * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". 50 1.1.2.2 he */ 51 1.1.2.2 he #define swapcode(TYPE, parmi, parmj, n) { \ 52 1.1.2.2 he long i = (n) / sizeof (TYPE); \ 53 1.1.2.2 he register TYPE *pi = (TYPE *) (parmi); \ 54 1.1.2.2 he register TYPE *pj = (TYPE *) (parmj); \ 55 1.1.2.2 he do { \ 56 1.1.2.2 he register TYPE t = *pi; \ 57 1.1.2.2 he *pi++ = *pj; \ 58 1.1.2.2 he *pj++ = t; \ 59 1.1.2.2 he } while (--i > 0); \ 60 1.1.2.2 he } 61 1.1.2.2 he 62 1.1.2.2 he #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ 63 1.1.2.2 he es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; 64 1.1.2.2 he 65 1.1.2.2 he static __inline void 66 1.1.2.2 he swapfunc(a, b, n, swaptype) 67 1.1.2.2 he char *a, *b; 68 1.1.2.2 he int n, swaptype; 69 1.1.2.2 he { 70 1.1.2.2 he if(swaptype <= 1) 71 1.1.2.2 he swapcode(long, a, b, n) 72 1.1.2.2 he else 73 1.1.2.2 he swapcode(char, a, b, n) 74 1.1.2.2 he } 75 1.1.2.2 he 76 1.1.2.2 he #define swap(a, b) \ 77 1.1.2.2 he if (swaptype == 0) { \ 78 1.1.2.2 he long t = *(long *)(a); \ 79 1.1.2.2 he *(long *)(a) = *(long *)(b); \ 80 1.1.2.2 he *(long *)(b) = t; \ 81 1.1.2.2 he } else \ 82 1.1.2.2 he swapfunc(a, b, es, swaptype) 83 1.1.2.2 he 84 1.1.2.2 he #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) 85 1.1.2.2 he 86 1.1.2.2 he static __inline char * 87 1.1.2.2 he med3(a, b, c, cmp) 88 1.1.2.2 he char *a, *b, *c; 89 1.1.2.2 he cmp_t *cmp; 90 1.1.2.2 he { 91 1.1.2.2 he return cmp(a, b) < 0 ? 92 1.1.2.2 he (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) 93 1.1.2.2 he :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); 94 1.1.2.2 he } 95 1.1.2.2 he 96 1.1.2.2 he void 97 1.1.2.2 he qsort(void *a, size_t n, size_t es, cmp_t *cmp) 98 1.1.2.2 he { 99 1.1.2.2 he char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 100 1.1.2.2 he int d, r, swaptype, swap_cnt; 101 1.1.2.2 he 102 1.1.2.2 he loop: SWAPINIT(a, es); 103 1.1.2.2 he swap_cnt = 0; 104 1.1.2.2 he if (n < 7) { 105 1.1.2.2 he for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 106 1.1.2.2 he for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; 107 1.1.2.2 he pl -= es) 108 1.1.2.2 he swap(pl, pl - es); 109 1.1.2.2 he return; 110 1.1.2.2 he } 111 1.1.2.2 he pm = (char *)a + (n / 2) * es; 112 1.1.2.2 he if (n > 7) { 113 1.1.2.2 he pl = a; 114 1.1.2.2 he pn = (char *)a + (n - 1) * es; 115 1.1.2.2 he if (n > 40) { 116 1.1.2.2 he d = (n / 8) * es; 117 1.1.2.2 he pl = med3(pl, pl + d, pl + 2 * d, cmp); 118 1.1.2.2 he pm = med3(pm - d, pm, pm + d, cmp); 119 1.1.2.2 he pn = med3(pn - 2 * d, pn - d, pn, cmp); 120 1.1.2.2 he } 121 1.1.2.2 he pm = med3(pl, pm, pn, cmp); 122 1.1.2.2 he } 123 1.1.2.2 he swap(a, pm); 124 1.1.2.2 he pa = pb = (char *)a + es; 125 1.1.2.2 he 126 1.1.2.2 he pc = pd = (char *)a + (n - 1) * es; 127 1.1.2.2 he for (;;) { 128 1.1.2.2 he while (pb <= pc && (r = cmp(pb, a)) <= 0) { 129 1.1.2.2 he if (r == 0) { 130 1.1.2.2 he swap_cnt = 1; 131 1.1.2.2 he swap(pa, pb); 132 1.1.2.2 he pa += es; 133 1.1.2.2 he } 134 1.1.2.2 he pb += es; 135 1.1.2.2 he } 136 1.1.2.2 he while (pb <= pc && (r = cmp(pc, a)) >= 0) { 137 1.1.2.2 he if (r == 0) { 138 1.1.2.2 he swap_cnt = 1; 139 1.1.2.2 he swap(pc, pd); 140 1.1.2.2 he pd -= es; 141 1.1.2.2 he } 142 1.1.2.2 he pc -= es; 143 1.1.2.2 he } 144 1.1.2.2 he if (pb > pc) 145 1.1.2.2 he break; 146 1.1.2.2 he swap(pb, pc); 147 1.1.2.2 he swap_cnt = 1; 148 1.1.2.2 he pb += es; 149 1.1.2.2 he pc -= es; 150 1.1.2.2 he } 151 1.1.2.2 he if (swap_cnt == 0) { /* Switch to insertion sort */ 152 1.1.2.2 he for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 153 1.1.2.2 he for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; 154 1.1.2.2 he pl -= es) 155 1.1.2.2 he swap(pl, pl - es); 156 1.1.2.2 he return; 157 1.1.2.2 he } 158 1.1.2.2 he 159 1.1.2.2 he pn = (char *)a + n * es; 160 1.1.2.2 he r = min(pa - (char *)a, pb - pa); 161 1.1.2.2 he vecswap(a, pb - r, r); 162 1.1.2.2 he r = min(pd - pc, pn - pd - es); 163 1.1.2.2 he vecswap(pb, pn - r, r); 164 1.1.2.2 he if ((r = pb - pa) > es) 165 1.1.2.2 he qsort(a, r / es, es, cmp); 166 1.1.2.2 he if ((r = pd - pc) > es) { 167 1.1.2.2 he /* Iterate rather than recurse to save stack space */ 168 1.1.2.2 he a = pn - r; 169 1.1.2.2 he n = r / es; 170 1.1.2.2 he goto loop; 171 1.1.2.2 he } 172 1.1.2.2 he /* qsort(pn - r, r / es, es, cmp);*/ 173 1.1.2.2 he } 174
Indexes created Tue Sep 30 20:09:53 GMT 2025