158f0484fSRodney W. Grimes /*- 28a16b7a1SPedro F. Giffuni * SPDX-License-Identifier: BSD-3-Clause 38a16b7a1SPedro F. Giffuni * 458f0484fSRodney W. Grimes * Copyright (c) 1992, 1993 558f0484fSRodney W. Grimes * The Regents of the University of California. All rights reserved. 658f0484fSRodney W. Grimes * 758f0484fSRodney W. Grimes * Redistribution and use in source and binary forms, with or without 858f0484fSRodney W. Grimes * modification, are permitted provided that the following conditions 958f0484fSRodney W. Grimes * are met: 1058f0484fSRodney W. Grimes * 1. Redistributions of source code must retain the above copyright 1158f0484fSRodney W. Grimes * notice, this list of conditions and the following disclaimer. 1258f0484fSRodney W. Grimes * 2. Redistributions in binary form must reproduce the above copyright 1358f0484fSRodney W. Grimes * notice, this list of conditions and the following disclaimer in the 1458f0484fSRodney W. Grimes * documentation and/or other materials provided with the distribution. 15580b4d18SEd Maste * 3. Neither the name of the University nor the names of its contributors 1658f0484fSRodney W. Grimes * may be used to endorse or promote products derived from this software 1758f0484fSRodney W. Grimes * without specific prior written permission. 1858f0484fSRodney W. Grimes * 1958f0484fSRodney W. Grimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2058f0484fSRodney W. Grimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2158f0484fSRodney W. Grimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2258f0484fSRodney W. Grimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2358f0484fSRodney W. Grimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2458f0484fSRodney W. Grimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2558f0484fSRodney W. Grimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2658f0484fSRodney W. Grimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2758f0484fSRodney W. Grimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2858f0484fSRodney W. Grimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2958f0484fSRodney W. Grimes * SUCH DAMAGE. 3058f0484fSRodney W. Grimes */ 3158f0484fSRodney W. Grimes 3258f0484fSRodney W. Grimes #if defined(LIBC_SCCS) && !defined(lint) 3358f0484fSRodney W. Grimes static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93"; 3458f0484fSRodney W. Grimes #endif /* LIBC_SCCS and not lint */ 35333fc21eSDavid E. O'Brien #include <sys/cdefs.h> 36333fc21eSDavid E. O'Brien __FBSDID("$FreeBSD$"); 3758f0484fSRodney W. Grimes 380d2fabfcSEdward Tomasz Napierala #include <errno.h> 390d2fabfcSEdward Tomasz Napierala #include <stdint.h> 4058f0484fSRodney W. Grimes #include <stdlib.h> 410d2fabfcSEdward Tomasz Napierala #include <string.h> 420d2fabfcSEdward Tomasz Napierala #include "libc_private.h" 4358f0484fSRodney W. Grimes 440d2fabfcSEdward Tomasz Napierala #if defined(I_AM_QSORT_R) 45af3c7888SEd Schouten typedef int cmp_t(const void *, const void *, void *); 46af3c7888SEd Schouten #elif defined(I_AM_QSORT_R_COMPAT) 47eca67d51SGarrett Wollman typedef int cmp_t(void *, const void *, const void *); 480d2fabfcSEdward Tomasz Napierala #elif defined(I_AM_QSORT_S) 490d2fabfcSEdward Tomasz Napierala typedef int cmp_t(const void *, const void *, void *); 50eca67d51SGarrett Wollman #else 51c05ac53bSDavid E. O'Brien typedef int cmp_t(const void *, const void *); 52eca67d51SGarrett Wollman #endif 53eca67d51SGarrett Wollman static inline char *med3(char *, char *, char *, cmp_t *, void *); 5458f0484fSRodney W. Grimes 552eaea119SPedro F. Giffuni #define MIN(a, b) ((a) < (b) ? a : b) 5658f0484fSRodney W. Grimes 5758f0484fSRodney W. Grimes /* 5858f0484fSRodney W. Grimes * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". 5958f0484fSRodney W. Grimes */ 6058f0484fSRodney W. Grimes 6158f0484fSRodney W. Grimes static inline void 6266092616SKonstantin Belousov swapfunc(char *a, char *b, size_t es) 6358f0484fSRodney W. Grimes { 6466092616SKonstantin Belousov char t; 6566092616SKonstantin Belousov 6666092616SKonstantin Belousov do { 6766092616SKonstantin Belousov t = *a; 6866092616SKonstantin Belousov *a++ = *b; 6966092616SKonstantin Belousov *b++ = t; 7066092616SKonstantin Belousov } while (--es > 0); 7158f0484fSRodney W. Grimes } 7258f0484fSRodney W. Grimes 739382fabfSPedro F. Giffuni #define vecswap(a, b, n) \ 7466092616SKonstantin Belousov if ((n) > 0) swapfunc(a, b, n) 7558f0484fSRodney W. Grimes 760d2fabfcSEdward Tomasz Napierala #if defined(I_AM_QSORT_R) 77af3c7888SEd Schouten #define CMP(t, x, y) (cmp((x), (y), (t))) 78af3c7888SEd Schouten #elif defined(I_AM_QSORT_R_COMPAT) 79eca67d51SGarrett Wollman #define CMP(t, x, y) (cmp((t), (x), (y))) 800d2fabfcSEdward Tomasz Napierala #elif defined(I_AM_QSORT_S) 810d2fabfcSEdward Tomasz Napierala #define CMP(t, x, y) (cmp((x), (y), (t))) 82eca67d51SGarrett Wollman #else 83eca67d51SGarrett Wollman #define CMP(t, x, y) (cmp((x), (y))) 84eca67d51SGarrett Wollman #endif 85eca67d51SGarrett Wollman 8658f0484fSRodney W. Grimes static inline char * 87eca67d51SGarrett Wollman med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk 88af3c7888SEd Schouten #if !defined(I_AM_QSORT_R) && !defined(I_AM_QSORT_R_COMPAT) && !defined(I_AM_QSORT_S) 89eca67d51SGarrett Wollman __unused 90eca67d51SGarrett Wollman #endif 91eca67d51SGarrett Wollman ) 9258f0484fSRodney W. Grimes { 93eca67d51SGarrett Wollman return CMP(thunk, a, b) < 0 ? 94eca67d51SGarrett Wollman (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) 95eca67d51SGarrett Wollman :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c )); 9658f0484fSRodney W. Grimes } 9758f0484fSRodney W. Grimes 98cbcfe28fSAlex Richardson /* 99cbcfe28fSAlex Richardson * The actual qsort() implementation is static to avoid preemptible calls when 100cbcfe28fSAlex Richardson * recursing. Also give them different names for improved debugging. 101cbcfe28fSAlex Richardson */ 1020d2fabfcSEdward Tomasz Napierala #if defined(I_AM_QSORT_R) 103cbcfe28fSAlex Richardson #define local_qsort local_qsort_r 104af3c7888SEd Schouten #elif defined(I_AM_QSORT_R_COMPAT) 105af3c7888SEd Schouten #define local_qsort local_qsort_r_compat 1060d2fabfcSEdward Tomasz Napierala #elif defined(I_AM_QSORT_S) 107cbcfe28fSAlex Richardson #define local_qsort local_qsort_s 108eca67d51SGarrett Wollman #endif 109cbcfe28fSAlex Richardson static void 110cbcfe28fSAlex Richardson local_qsort(void *a, size_t n, size_t es, cmp_t *cmp, void *thunk) 11158f0484fSRodney W. Grimes { 11258f0484fSRodney W. Grimes char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 113ca1578f0SXin LI size_t d1, d2; 114ac48ad2eSDavid Schultz int cmp_result; 11566092616SKonstantin Belousov int swap_cnt; 11658f0484fSRodney W. Grimes 117d106f982SStefan Eßer if (__predict_false(n == 0)) 118d106f982SStefan Eßer return; 11966092616SKonstantin Belousov loop: 12058f0484fSRodney W. Grimes swap_cnt = 0; 12158f0484fSRodney W. Grimes if (n < 7) { 12209a8dfa2SBruce Evans for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 123eca67d51SGarrett Wollman for (pl = pm; 124eca67d51SGarrett Wollman pl > (char *)a && CMP(thunk, pl - es, pl) > 0; 12558f0484fSRodney W. Grimes pl -= es) 12666092616SKonstantin Belousov swapfunc(pl, pl - es, es); 12758f0484fSRodney W. Grimes return; 12858f0484fSRodney W. Grimes } 12909a8dfa2SBruce Evans pm = (char *)a + (n / 2) * es; 13058f0484fSRodney W. Grimes if (n > 7) { 13158f0484fSRodney W. Grimes pl = a; 13209a8dfa2SBruce Evans pn = (char *)a + (n - 1) * es; 13358f0484fSRodney W. Grimes if (n > 40) { 134ca1578f0SXin LI size_t d = (n / 8) * es; 135ca1578f0SXin LI 136eca67d51SGarrett Wollman pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk); 137eca67d51SGarrett Wollman pm = med3(pm - d, pm, pm + d, cmp, thunk); 138eca67d51SGarrett Wollman pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk); 13958f0484fSRodney W. Grimes } 140eca67d51SGarrett Wollman pm = med3(pl, pm, pn, cmp, thunk); 14158f0484fSRodney W. Grimes } 14266092616SKonstantin Belousov swapfunc(a, pm, es); 14309a8dfa2SBruce Evans pa = pb = (char *)a + es; 14458f0484fSRodney W. Grimes 14509a8dfa2SBruce Evans pc = pd = (char *)a + (n - 1) * es; 14658f0484fSRodney W. Grimes for (;;) { 147ac48ad2eSDavid Schultz while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) { 148ac48ad2eSDavid Schultz if (cmp_result == 0) { 14958f0484fSRodney W. Grimes swap_cnt = 1; 15066092616SKonstantin Belousov swapfunc(pa, pb, es); 15158f0484fSRodney W. Grimes pa += es; 15258f0484fSRodney W. Grimes } 15358f0484fSRodney W. Grimes pb += es; 15458f0484fSRodney W. Grimes } 155ac48ad2eSDavid Schultz while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) { 156ac48ad2eSDavid Schultz if (cmp_result == 0) { 15758f0484fSRodney W. Grimes swap_cnt = 1; 15866092616SKonstantin Belousov swapfunc(pc, pd, es); 15958f0484fSRodney W. Grimes pd -= es; 16058f0484fSRodney W. Grimes } 16158f0484fSRodney W. Grimes pc -= es; 16258f0484fSRodney W. Grimes } 16358f0484fSRodney W. Grimes if (pb > pc) 16458f0484fSRodney W. Grimes break; 16566092616SKonstantin Belousov swapfunc(pb, pc, es); 16658f0484fSRodney W. Grimes swap_cnt = 1; 16758f0484fSRodney W. Grimes pb += es; 16858f0484fSRodney W. Grimes pc -= es; 16958f0484fSRodney W. Grimes } 17058f0484fSRodney W. Grimes if (swap_cnt == 0) { /* Switch to insertion sort */ 17109a8dfa2SBruce Evans for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 172eca67d51SGarrett Wollman for (pl = pm; 173eca67d51SGarrett Wollman pl > (char *)a && CMP(thunk, pl - es, pl) > 0; 17458f0484fSRodney W. Grimes pl -= es) 17566092616SKonstantin Belousov swapfunc(pl, pl - es, es); 17658f0484fSRodney W. Grimes return; 17758f0484fSRodney W. Grimes } 17858f0484fSRodney W. Grimes 17909a8dfa2SBruce Evans pn = (char *)a + n * es; 180ca1578f0SXin LI d1 = MIN(pa - (char *)a, pb - pa); 181ca1578f0SXin LI vecswap(a, pb - d1, d1); 1827f8f79a5SConrad Meyer /* 1837f8f79a5SConrad Meyer * Cast es to preserve signedness of right-hand side of MIN() 1847f8f79a5SConrad Meyer * expression, to avoid sign ambiguity in the implied comparison. es 1857f8f79a5SConrad Meyer * is safely within [0, SSIZE_MAX]. 1867f8f79a5SConrad Meyer */ 1877f8f79a5SConrad Meyer d1 = MIN(pd - pc, pn - pd - (ssize_t)es); 188ca1578f0SXin LI vecswap(pb, pn - d1, d1); 189ca1578f0SXin LI 190ca1578f0SXin LI d1 = pb - pa; 191ca1578f0SXin LI d2 = pd - pc; 192ca1578f0SXin LI if (d1 <= d2) { 193ca1578f0SXin LI /* Recurse on left partition, then iterate on right partition */ 194ca1578f0SXin LI if (d1 > es) { 195cbcfe28fSAlex Richardson local_qsort(a, d1 / es, es, cmp, thunk); 196ca1578f0SXin LI } 197ca1578f0SXin LI if (d2 > es) { 19858f0484fSRodney W. Grimes /* Iterate rather than recurse to save stack space */ 199ca1578f0SXin LI /* qsort(pn - d2, d2 / es, es, cmp); */ 200ca1578f0SXin LI a = pn - d2; 201ca1578f0SXin LI n = d2 / es; 20258f0484fSRodney W. Grimes goto loop; 20358f0484fSRodney W. Grimes } 204ca1578f0SXin LI } else { 205ca1578f0SXin LI /* Recurse on right partition, then iterate on left partition */ 206ca1578f0SXin LI if (d2 > es) { 207cbcfe28fSAlex Richardson local_qsort(pn - d2, d2 / es, es, cmp, thunk); 208ca1578f0SXin LI } 209ca1578f0SXin LI if (d1 > es) { 210ca1578f0SXin LI /* Iterate rather than recurse to save stack space */ 211ca1578f0SXin LI /* qsort(a, d1 / es, es, cmp); */ 212ca1578f0SXin LI n = d1 / es; 213ca1578f0SXin LI goto loop; 214ca1578f0SXin LI } 215ca1578f0SXin LI } 21658f0484fSRodney W. Grimes } 217cbcfe28fSAlex Richardson 218cbcfe28fSAlex Richardson #if defined(I_AM_QSORT_R) 219cbcfe28fSAlex Richardson void 220af3c7888SEd Schouten (qsort_r)(void *a, size_t n, size_t es, cmp_t *cmp, void *thunk) 221cbcfe28fSAlex Richardson { 222cbcfe28fSAlex Richardson local_qsort_r(a, n, es, cmp, thunk); 223cbcfe28fSAlex Richardson } 224af3c7888SEd Schouten #elif defined(I_AM_QSORT_R_COMPAT) 225af3c7888SEd Schouten void 226af3c7888SEd Schouten __qsort_r_compat(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp) 227af3c7888SEd Schouten { 228af3c7888SEd Schouten local_qsort_r_compat(a, n, es, cmp, thunk); 229af3c7888SEd Schouten } 230cbcfe28fSAlex Richardson #elif defined(I_AM_QSORT_S) 231cbcfe28fSAlex Richardson errno_t 232cbcfe28fSAlex Richardson qsort_s(void *a, rsize_t n, rsize_t es, cmp_t *cmp, void *thunk) 233cbcfe28fSAlex Richardson { 234cbcfe28fSAlex Richardson if (n > RSIZE_MAX) { 235cbcfe28fSAlex Richardson __throw_constraint_handler_s("qsort_s : n > RSIZE_MAX", EINVAL); 236cbcfe28fSAlex Richardson return (EINVAL); 237cbcfe28fSAlex Richardson } else if (es > RSIZE_MAX) { 238cbcfe28fSAlex Richardson __throw_constraint_handler_s("qsort_s : es > RSIZE_MAX", 239cbcfe28fSAlex Richardson EINVAL); 240cbcfe28fSAlex Richardson return (EINVAL); 241cbcfe28fSAlex Richardson } else if (n != 0) { 242cbcfe28fSAlex Richardson if (a == NULL) { 243cbcfe28fSAlex Richardson __throw_constraint_handler_s("qsort_s : a == NULL", 244cbcfe28fSAlex Richardson EINVAL); 245cbcfe28fSAlex Richardson return (EINVAL); 246cbcfe28fSAlex Richardson } else if (cmp == NULL) { 247cbcfe28fSAlex Richardson __throw_constraint_handler_s("qsort_s : cmp == NULL", 248cbcfe28fSAlex Richardson EINVAL); 249cbcfe28fSAlex Richardson return (EINVAL); 250*27bb0d33SHans Petter Selasky } else if (es <= 0) { 251*27bb0d33SHans Petter Selasky __throw_constraint_handler_s("qsort_s : es <= 0", 252*27bb0d33SHans Petter Selasky EINVAL); 253*27bb0d33SHans Petter Selasky return (EINVAL); 254cbcfe28fSAlex Richardson } 255cbcfe28fSAlex Richardson } 256cbcfe28fSAlex Richardson 257cbcfe28fSAlex Richardson local_qsort_s(a, n, es, cmp, thunk); 258cbcfe28fSAlex Richardson return (0); 259cbcfe28fSAlex Richardson } 260cbcfe28fSAlex Richardson #else 261cbcfe28fSAlex Richardson void 262cbcfe28fSAlex Richardson qsort(void *a, size_t n, size_t es, cmp_t *cmp) 263cbcfe28fSAlex Richardson { 264cbcfe28fSAlex Richardson local_qsort(a, n, es, cmp, NULL); 265cbcfe28fSAlex Richardson } 266cbcfe28fSAlex Richardson #endif 267