112151Sphk/*- 212151Sphk * Copyright (c) 1992, 1993 312151Sphk * The Regents of the University of California. All rights reserved. 412151Sphk * 512151Sphk * Redistribution and use in source and binary forms, with or without 612151Sphk * modification, are permitted provided that the following conditions 712151Sphk * are met: 812151Sphk * 1. Redistributions of source code must retain the above copyright 912151Sphk * notice, this list of conditions and the following disclaimer. 1012151Sphk * 2. Redistributions in binary form must reproduce the above copyright 1112151Sphk * notice, this list of conditions and the following disclaimer in the 1212151Sphk * documentation and/or other materials provided with the distribution. 1312151Sphk * 4. Neither the name of the University nor the names of its contributors 1412151Sphk * may be used to endorse or promote products derived from this software 1512151Sphk * without specific prior written permission. 1612151Sphk * 1712151Sphk * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 1812151Sphk * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1912151Sphk * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2012151Sphk * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2112151Sphk * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2212151Sphk * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2312151Sphk * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2412151Sphk * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2512151Sphk * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2612151Sphk * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2712151Sphk * SUCH DAMAGE. 2812151Sphk */ 2912151Sphk 30116189Sobrien#include <sys/cdefs.h> 31116189Sobrien__FBSDID("$FreeBSD: stable/10/sys/libkern/qsort.c 319291 2017-05-31 06:26:37Z delphij $"); 32116189Sobrien 33132228Sglebius#include <sys/param.h> 3437289Sphk#include <sys/libkern.h> 3512151Sphk 36319291Sdelphij#ifdef I_AM_QSORT_R 37319291Sdelphijtypedef int cmp_t(void *, const void *, const void *); 38132228Sglebius#else 39319291Sdelphijtypedef int cmp_t(const void *, const void *); 40132228Sglebius#endif 41319291Sdelphijstatic inline char *med3(char *, char *, char *, cmp_t *, void *); 42319291Sdelphijstatic inline void swapfunc(char *, char *, size_t, int, int); 4312151Sphk 4412151Sphk/* 4512151Sphk * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". 4612151Sphk */ 47319291Sdelphij#define swapcode(TYPE, parmi, parmj, n) { \ 48319291Sdelphij size_t i = (n) / sizeof (TYPE); \ 49319291Sdelphij TYPE *pi = (TYPE *) (parmi); \ 50319291Sdelphij TYPE *pj = (TYPE *) (parmj); \ 5112151Sphk do { \ 52319291Sdelphij TYPE t = *pi; \ 5312151Sphk *pi++ = *pj; \ 5412151Sphk *pj++ = t; \ 55319291Sdelphij } while (--i > 0); \ 5612151Sphk} 5712151Sphk 58319291Sdelphij#define SWAPINIT(TYPE, a, es) swaptype_ ## TYPE = \ 59319291Sdelphij ((char *)a - (char *)0) % sizeof(TYPE) || \ 60319291Sdelphij es % sizeof(TYPE) ? 2 : es == sizeof(TYPE) ? 0 : 1; 6112151Sphk 62319291Sdelphijstatic inline void 63319291Sdelphijswapfunc(char *a, char *b, size_t n, int swaptype_long, int swaptype_int) 6412151Sphk{ 65319291Sdelphij if (swaptype_long <= 1) 6612151Sphk swapcode(long, a, b, n) 67319291Sdelphij else if (swaptype_int <= 1) 68319291Sdelphij swapcode(int, a, b, n) 6912151Sphk else 7012151Sphk swapcode(char, a, b, n) 7112151Sphk} 7212151Sphk 73319291Sdelphij#define swap(a, b) \ 74319291Sdelphij if (swaptype_long == 0) { \ 7512151Sphk long t = *(long *)(a); \ 7612151Sphk *(long *)(a) = *(long *)(b); \ 7712151Sphk *(long *)(b) = t; \ 78319291Sdelphij } else if (swaptype_int == 0) { \ 79319291Sdelphij int t = *(int *)(a); \ 80319291Sdelphij *(int *)(a) = *(int *)(b); \ 81319291Sdelphij *(int *)(b) = t; \ 8212151Sphk } else \ 83319291Sdelphij swapfunc(a, b, es, swaptype_long, swaptype_int) 8412151Sphk 85319291Sdelphij#define vecswap(a, b, n) \ 86319291Sdelphij if ((n) > 0) swapfunc(a, b, n, swaptype_long, swaptype_int) 8712151Sphk 88132228Sglebius#ifdef I_AM_QSORT_R 89132228Sglebius#define CMP(t, x, y) (cmp((t), (x), (y))) 90132228Sglebius#else 91132228Sglebius#define CMP(t, x, y) (cmp((x), (y))) 92132228Sglebius#endif 93132228Sglebius 94319291Sdelphijstatic inline char * 95132228Sglebiusmed3(char *a, char *b, char *c, cmp_t *cmp, void *thunk 96319291Sdelphij#ifndef I_AM_QSORT_R 97132228Sglebius__unused 98132228Sglebius#endif 99132228Sglebius) 10012151Sphk{ 101132228Sglebius return CMP(thunk, a, b) < 0 ? 102132228Sglebius (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) 103319291Sdelphij :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c )); 10412151Sphk} 10512151Sphk 106132228Sglebius#ifdef I_AM_QSORT_R 10712151Sphkvoid 108132228Sglebiusqsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp) 109132228Sglebius#else 110132228Sglebius#define thunk NULL 111132228Sglebiusvoid 112132228Sglebiusqsort(void *a, size_t n, size_t es, cmp_t *cmp) 113132228Sglebius#endif 11412151Sphk{ 11512151Sphk char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 116319291Sdelphij size_t d1, d2; 117319291Sdelphij int cmp_result; 118319291Sdelphij int swaptype_long, swaptype_int, swap_cnt; 11912151Sphk 120319291Sdelphijloop: SWAPINIT(long, a, es); 121319291Sdelphij SWAPINIT(int, a, es); 12212151Sphk swap_cnt = 0; 12312151Sphk if (n < 7) { 12417971Sbde for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 125319291Sdelphij for (pl = pm; 126319291Sdelphij pl > (char *)a && CMP(thunk, pl - es, pl) > 0; 12712151Sphk pl -= es) 12812151Sphk swap(pl, pl - es); 12912151Sphk return; 13012151Sphk } 13117971Sbde pm = (char *)a + (n / 2) * es; 13212151Sphk if (n > 7) { 13312151Sphk pl = a; 13417971Sbde pn = (char *)a + (n - 1) * es; 13512151Sphk if (n > 40) { 136319291Sdelphij size_t d = (n / 8) * es; 137319291Sdelphij 138132228Sglebius pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk); 139132228Sglebius pm = med3(pm - d, pm, pm + d, cmp, thunk); 140132228Sglebius pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk); 14112151Sphk } 142132228Sglebius pm = med3(pl, pm, pn, cmp, thunk); 14312151Sphk } 14412151Sphk swap(a, pm); 14517971Sbde pa = pb = (char *)a + es; 14612151Sphk 14717971Sbde pc = pd = (char *)a + (n - 1) * es; 14812151Sphk for (;;) { 149319291Sdelphij while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) { 150319291Sdelphij if (cmp_result == 0) { 15112151Sphk swap_cnt = 1; 15212151Sphk swap(pa, pb); 15312151Sphk pa += es; 15412151Sphk } 15512151Sphk pb += es; 15612151Sphk } 157319291Sdelphij while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) { 158319291Sdelphij if (cmp_result == 0) { 15912151Sphk swap_cnt = 1; 16012151Sphk swap(pc, pd); 16112151Sphk pd -= es; 16212151Sphk } 16312151Sphk pc -= es; 16412151Sphk } 16512151Sphk if (pb > pc) 16612151Sphk break; 16712151Sphk swap(pb, pc); 16812151Sphk swap_cnt = 1; 16912151Sphk pb += es; 17012151Sphk pc -= es; 17112151Sphk } 17212151Sphk if (swap_cnt == 0) { /* Switch to insertion sort */ 17317971Sbde for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 174319291Sdelphij for (pl = pm; 175319291Sdelphij pl > (char *)a && CMP(thunk, pl - es, pl) > 0; 17612151Sphk pl -= es) 17712151Sphk swap(pl, pl - es); 17812151Sphk return; 17912151Sphk } 18012151Sphk 18117971Sbde pn = (char *)a + n * es; 182319291Sdelphij d1 = MIN(pa - (char *)a, pb - pa); 183319291Sdelphij vecswap(a, pb - d1, d1); 184319291Sdelphij d1 = MIN(pd - pc, pn - pd - es); 185319291Sdelphij vecswap(pb, pn - d1, d1); 186319291Sdelphij 187319291Sdelphij d1 = pb - pa; 188319291Sdelphij d2 = pd - pc; 189319291Sdelphij if (d1 <= d2) { 190319291Sdelphij /* Recurse on left partition, then iterate on right partition */ 191319291Sdelphij if (d1 > es) { 192319291Sdelphij#ifdef I_AM_QSORT_R 193319291Sdelphij qsort_r(a, d1 / es, es, thunk, cmp); 194132228Sglebius#else 195319291Sdelphij qsort(a, d1 / es, es, cmp); 196132228Sglebius#endif 197319291Sdelphij } 198319291Sdelphij if (d2 > es) { 199319291Sdelphij /* Iterate rather than recurse to save stack space */ 200319291Sdelphij /* qsort(pn - d2, d2 / es, es, cmp); */ 201319291Sdelphij a = pn - d2; 202319291Sdelphij n = d2 / es; 203319291Sdelphij goto loop; 204319291Sdelphij } 205319291Sdelphij } else { 206319291Sdelphij /* Recurse on right partition, then iterate on left partition */ 207319291Sdelphij if (d2 > es) { 208319291Sdelphij#ifdef I_AM_QSORT_R 209319291Sdelphij qsort_r(pn - d2, d2 / es, es, thunk, cmp); 210319291Sdelphij#else 211319291Sdelphij qsort(pn - d2, d2 / es, es, cmp); 212319291Sdelphij#endif 213319291Sdelphij } 214319291Sdelphij if (d1 > es) { 215319291Sdelphij /* Iterate rather than recurse to save stack space */ 216319291Sdelphij /* qsort(a, d1 / es, es, cmp); */ 217319291Sdelphij n = d1 / es; 218319291Sdelphij goto loop; 219319291Sdelphij } 22012151Sphk } 22112151Sphk} 222