Something went wrong. Try again.
Cider Isn't Darwin Emulation, Really
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255/*- * Copyright (c) 1992, 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */
#if defined(LIBC_SCCS) && !defined(lint)static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";#endif /* LIBC_SCCS and not lint */#include <sys/cdefs.h>__FBSDID("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15 2008/01/14 09:21:34 das Exp $");
#include <stdlib.h>#include <string.h>
#ifdef I_AM_QSORT_Rtypedef int cmp_t(void *, const void *, const void *);#elsetypedef int cmp_t(const void *, const void *);#endif#ifdef I_AM_QSORT_Bstatic inline char *med3(char *, char *, char *, cmp_t ^, void *) __attribute__((always_inline));#elsestatic inline char *med3(char *, char *, char *, cmp_t *, void *) __attribute__((always_inline));#endifstatic inline void swapfunc(char *, char *, int, int) __attribute__((always_inline));
#define min(a, b) (a) < (b) ? a : b
/* * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". */#define swapcode(TYPE, parmi, parmj, n) { \ long i = (n) / sizeof (TYPE); \ TYPE *pi = (TYPE *) (parmi); \ TYPE *pj = (TYPE *) (parmj); \ do { \ TYPE t = *pi; \ *pi++ = *pj; \ *pj++ = t; \ } while (--i > 0); \}
#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
static inline voidswapfunc(a, b, n, swaptype) char *a, *b; int n, swaptype;{ if(swaptype <= 1) swapcode(long, a, b, n) else swapcode(char, a, b, n)}
#define swap(a, b) \ if (swaptype == 0) { \ long t = *(long *)(a); \ *(long *)(a) = *(long *)(b); \ *(long *)(b) = t; \ } else \ swapfunc(a, b, es, swaptype)
#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
#ifdef I_AM_QSORT_R#define CMP(t, x, y) (cmp((t), (x), (y)))#else#define CMP(t, x, y) (cmp((x), (y)))#endif
static inline char *med3(char *a, char *b, char *c,#ifdef I_AM_QSORT_Bcmp_t ^cmp,#elsecmp_t *cmp,#endifvoid *thunk#ifndef I_AM_QSORT_R__unused#endif){ return CMP(thunk, a, b) < 0 ? (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));}
#ifdef __LP64__#define DEPTH(x) (2 * (flsl((long)(x)) - 1))#else /* !__LP64__ */#define DEPTH(x) (2 * (fls((int)(x)) - 1))#endif /* __LP64__ */
#ifdef I_AM_QSORT_Rint __heapsort_r(void *, size_t, size_t, void *, int (*)(void *, const void *, const void *));#endif
static void_qsort(void *a, size_t n, size_t es,#ifdef I_AM_QSORT_Rvoid *thunk,#else#define thunk NULL#endif#ifdef I_AM_QSORT_Bcmp_t ^cmp,#elsecmp_t *cmp,#endifint depth_limit){ char *pa, *pb, *pc, *pd, *pl, *pm, *pn; size_t d, r; int cmp_result; int swaptype, swap_cnt;
loop: if (depth_limit-- <= 0) {#ifdef I_AM_QSORT_B heapsort_b(a, n, es, cmp);#elif defined(I_AM_QSORT_R) __heapsort_r(a, n, es, thunk, cmp);#else heapsort(a, n, es, cmp);#endif return; } SWAPINIT(a, es); swap_cnt = 0; if (n < 7) { for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) for (pl = pm; pl > (char *)a && CMP(thunk, pl - es, pl) > 0; pl -= es) swap(pl, pl - es); return; } pm = (char *)a + (n / 2) * es; if (n > 7) { pl = a; pn = (char *)a + (n - 1) * es; if (n > 40) { d = (n / 8) * es; pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk); pm = med3(pm - d, pm, pm + d, cmp, thunk); pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk); } pm = med3(pl, pm, pn, cmp, thunk); } swap(a, pm); pa = pb = (char *)a + es;
pc = pd = (char *)a + (n - 1) * es; for (;;) { while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) { if (cmp_result == 0) { swap_cnt = 1; swap(pa, pb); pa += es; } pb += es; } while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) { if (cmp_result == 0) { swap_cnt = 1; swap(pc, pd); pd -= es; } pc -= es; } if (pb > pc) break; swap(pb, pc); swap_cnt = 1; pb += es; pc -= es; }
pn = (char *)a + n * es; r = min(pa - (char *)a, pb - pa); vecswap(a, pb - r, r); r = min(pd - pc, pn - pd - es); vecswap(pb, pn - r, r);
if (swap_cnt == 0) { /* Switch to insertion sort */ r = 1 + n / 4; /* n >= 7, so r >= 2 */ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) for (pl = pm; pl > (char *)a && CMP(thunk, pl - es, pl) > 0; pl -= es) { swap(pl, pl - es); if (++swap_cnt > r) goto nevermind; } return; }
nevermind: if ((r = pb - pa) > es)#ifdef I_AM_QSORT_R _qsort(a, r / es, es, thunk, cmp, depth_limit);#else _qsort(a, r / es, es, cmp, depth_limit);#endif if ((r = pd - pc) > es) { /* Iterate rather than recurse to save stack space */ a = pn - r; n = r / es; goto loop; }/* qsort(pn - r, r / es, es, cmp);*/}
void#ifdef I_AM_QSORT_Rqsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp)#elif defined(I_AM_QSORT_B)qsort_b(void *a, size_t n, size_t es, cmp_t ^cmp)#elseqsort(void *a, size_t n, size_t es, cmp_t *cmp)#endif{ _qsort(a, n, es,#ifdef I_AM_QSORT_R thunk,#endif cmp, DEPTH(n));}