1226031Sstas/*- 2226031Sstas * Copyright (c) 1992, 1993 3226031Sstas * The Regents of the University of California. All rights reserved. 4226031Sstas * 5226031Sstas * Redistribution and use in source and binary forms, with or without 6226031Sstas * modification, are permitted provided that the following conditions 7226031Sstas * are met: 8226031Sstas * 1. Redistributions of source code must retain the above copyright 9226031Sstas * notice, this list of conditions and the following disclaimer. 10226031Sstas * 2. Redistributions in binary form must reproduce the above copyright 11226031Sstas * notice, this list of conditions and the following disclaimer in the 12226031Sstas * documentation and/or other materials provided with the distribution. 13226031Sstas * 4. Neither the name of the University nor the names of its contributors 14226031Sstas * may be used to endorse or promote products derived from this software 15226031Sstas * without specific prior written permission. 16226031Sstas * 17226031Sstas * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18226031Sstas * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19226031Sstas * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20226031Sstas * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21226031Sstas * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22226031Sstas * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23226031Sstas * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24226031Sstas * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25226031Sstas * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26226031Sstas * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27226031Sstas * SUCH DAMAGE. 28226031Sstas */ 29226031Sstas 30226031Sstas#if 0 31226031Sstas#if defined(LIBC_SCCS) && !defined(lint) 32226031Sstasstatic char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93"; 33226031Sstas#endif /* LIBC_SCCS and not lint */ 34226031Sstas#include <sys/cdefs.h> 35226031Sstas__FBSDID("$FreeBSD$"); 36226031Sstas#endif 37226031Sstas 38226031Sstas#include <config.h> 39226031Sstas 40226031Sstas#ifdef NEED_QSORT 41226031Sstas 42226031Sstas#include "roken.h" 43226031Sstas 44226031Sstas#include <stdlib.h> 45226031Sstas 46226031Sstas#ifdef I_AM_QSORT_R 47226031Sstastypedef int cmp_t(void *, const void *, const void *); 48226031Sstas#else 49226031Sstastypedef int cmp_t(const void *, const void *); 50226031Sstas#endif 51226031Sstasstatic inline char *med3(char *, char *, char *, cmp_t *, void *); 52226031Sstasstatic inline void swapfunc(char *, char *, int, int); 53226031Sstas 54226031Sstas/* 55226031Sstas * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". 56226031Sstas */ 57226031Sstas#define swapcode(TYPE, parmi, parmj, n) { \ 58226031Sstas long i = (n) / sizeof (TYPE); \ 59226031Sstas TYPE *pi = (TYPE *) (parmi); \ 60226031Sstas TYPE *pj = (TYPE *) (parmj); \ 61226031Sstas do { \ 62226031Sstas TYPE t = *pi; \ 63226031Sstas *pi++ = *pj; \ 64226031Sstas *pj++ = t; \ 65226031Sstas } while (--i > 0); \ 66226031Sstas} 67226031Sstas 68226031Sstas#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ 69226031Sstas es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; 70226031Sstas 71226031Sstasstatic inline void 72226031Sstasswapfunc(a, b, n, swaptype) 73226031Sstas char *a, *b; 74226031Sstas int n, swaptype; 75226031Sstas{ 76226031Sstas if(swaptype <= 1) 77226031Sstas swapcode(long, a, b, n) 78226031Sstas else 79226031Sstas swapcode(char, a, b, n) 80226031Sstas} 81226031Sstas 82226031Sstas#define swap(a, b) \ 83226031Sstas if (swaptype == 0) { \ 84226031Sstas long t = *(long *)(a); \ 85226031Sstas *(long *)(a) = *(long *)(b); \ 86226031Sstas *(long *)(b) = t; \ 87226031Sstas } else \ 88226031Sstas swapfunc(a, b, es, swaptype) 89226031Sstas 90226031Sstas#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) 91226031Sstas 92226031Sstas#ifdef I_AM_QSORT_R 93226031Sstas#define CMP(t, x, y) (cmp((t), (x), (y))) 94226031Sstas#else 95226031Sstas#define CMP(t, x, y) (cmp((x), (y))) 96226031Sstas#endif 97226031Sstas 98226031Sstasstatic inline char * 99226031Sstasmed3(char *a, char *b, char *c, cmp_t *cmp, void *thunk 100226031Sstas#ifndef I_AM_QSORT_R 101226031Sstas/* __unused */ 102226031Sstas#endif 103226031Sstas) 104226031Sstas{ 105226031Sstas return CMP(thunk, a, b) < 0 ? 106226031Sstas (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) 107226031Sstas :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c )); 108226031Sstas} 109226031Sstas 110226031Sstas#ifdef I_AM_QSORT_R 111226031Sstasvoid 112226031Sstasrk_qsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp) 113226031Sstas#else 114226031Sstas#define thunk NULL 115226031Sstasvoid 116226031Sstasrk_qsort(void *a, size_t n, size_t es, cmp_t *cmp) 117226031Sstas#endif 118226031Sstas{ 119226031Sstas char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 120226031Sstas size_t d, r; 121226031Sstas int cmp_result; 122226031Sstas int swaptype, swap_cnt; 123226031Sstas 124226031Sstasloop: SWAPINIT(a, es); 125226031Sstas swap_cnt = 0; 126226031Sstas if (n < 7) { 127226031Sstas for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 128226031Sstas for (pl = pm; 129226031Sstas pl > (char *)a && CMP(thunk, pl - es, pl) > 0; 130226031Sstas pl -= es) 131226031Sstas swap(pl, pl - es); 132226031Sstas return; 133226031Sstas } 134226031Sstas pm = (char *)a + (n / 2) * es; 135226031Sstas if (n > 7) { 136226031Sstas pl = a; 137226031Sstas pn = (char *)a + (n - 1) * es; 138226031Sstas if (n > 40) { 139226031Sstas d = (n / 8) * es; 140226031Sstas pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk); 141226031Sstas pm = med3(pm - d, pm, pm + d, cmp, thunk); 142226031Sstas pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk); 143226031Sstas } 144226031Sstas pm = med3(pl, pm, pn, cmp, thunk); 145226031Sstas } 146226031Sstas swap(a, pm); 147226031Sstas pa = pb = (char *)a + es; 148226031Sstas 149226031Sstas pc = pd = (char *)a + (n - 1) * es; 150226031Sstas for (;;) { 151226031Sstas while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) { 152226031Sstas if (cmp_result == 0) { 153226031Sstas swap_cnt = 1; 154226031Sstas swap(pa, pb); 155226031Sstas pa += es; 156226031Sstas } 157226031Sstas pb += es; 158226031Sstas } 159226031Sstas while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) { 160226031Sstas if (cmp_result == 0) { 161226031Sstas swap_cnt = 1; 162226031Sstas swap(pc, pd); 163226031Sstas pd -= es; 164226031Sstas } 165226031Sstas pc -= es; 166226031Sstas } 167226031Sstas if (pb > pc) 168226031Sstas break; 169226031Sstas swap(pb, pc); 170226031Sstas swap_cnt = 1; 171226031Sstas pb += es; 172226031Sstas pc -= es; 173226031Sstas } 174226031Sstas if (swap_cnt == 0) { /* Switch to insertion sort */ 175226031Sstas for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 176226031Sstas for (pl = pm; 177226031Sstas pl > (char *)a && CMP(thunk, pl - es, pl) > 0; 178226031Sstas pl -= es) 179226031Sstas swap(pl, pl - es); 180226031Sstas return; 181226031Sstas } 182226031Sstas 183226031Sstas pn = (char *)a + n * es; 184226031Sstas r = min(pa - (char *)a, pb - pa); 185226031Sstas vecswap(a, pb - r, r); 186226031Sstas r = min(pd - pc, pn - pd - es); 187226031Sstas vecswap(pb, pn - r, r); 188226031Sstas if ((r = pb - pa) > es) 189226031Sstas#ifdef I_AM_QSORT_R 190226031Sstas rk_qsort_r(a, r / es, es, thunk, cmp); 191226031Sstas#else 192226031Sstas rk_qsort(a, r / es, es, cmp); 193226031Sstas#endif 194226031Sstas if ((r = pd - pc) > es) { 195226031Sstas /* Iterate rather than recurse to save stack space */ 196226031Sstas a = pn - r; 197226031Sstas n = r / es; 198226031Sstas goto loop; 199226031Sstas } 200226031Sstas/* rk_qsort(pn - r, r / es, es, cmp);*/ 201226031Sstas} 202226031Sstas 203226031Sstas#endif /* NEED_QSORT */ 204