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