15f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian/* $OpenBSD: qsort.c,v 1.10 2005/08/08 08:05:37 espie Exp $ */ 21dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project/*- 31dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Copyright (c) 1992, 1993 41dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * The Regents of the University of California. All rights reserved. 51dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 61dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Redistribution and use in source and binary forms, with or without 71dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * modification, are permitted provided that the following conditions 81dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * are met: 91dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 1. Redistributions of source code must retain the above copyright 101dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * notice, this list of conditions and the following disclaimer. 111dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 121dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * notice, this list of conditions and the following disclaimer in the 131dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * documentation and/or other materials provided with the distribution. 145f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian * 3. Neither the name of the University nor the names of its contributors 151dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * may be used to endorse or promote products derived from this software 161dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * without specific prior written permission. 171dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 181dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 191dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 201dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 211dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 221dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 231dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 241dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 251dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 261dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 271dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 281dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * SUCH DAMAGE. 291dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project */ 301dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 315f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian#include <sys/types.h> 321dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#include <stdlib.h> 331dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 345f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopianstatic __inline char *med3(char *, char *, char *, int (*)(const void *, const void *)); 355f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopianstatic __inline void swapfunc(char *, char *, int, int); 361dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 371dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define min(a, b) (a) < (b) ? a : b 381dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 391dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project/* 401dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". 411dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project */ 42e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa#define swapcode(TYPE, parmi, parmj, n) { \ 43e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa long i = (n) / sizeof (TYPE); \ 44e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa TYPE *pi = (TYPE *) (parmi); \ 45e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa TYPE *pj = (TYPE *) (parmj); \ 46e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa do { \ 475f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian TYPE t = *pi; \ 481dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project *pi++ = *pj; \ 491dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project *pj++ = t; \ 501dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } while (--i > 0); \ 511dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project} 521dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 531dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ 541dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; 551dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 565f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopianstatic __inline void 575f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopianswapfunc(char *a, char *b, int n, int swaptype) 581dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project{ 59e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa if (swaptype <= 1) 601dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swapcode(long, a, b, n) 611dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project else 621dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swapcode(char, a, b, n) 631dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project} 641dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 651dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define swap(a, b) \ 661dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (swaptype == 0) { \ 671dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project long t = *(long *)(a); \ 681dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project *(long *)(a) = *(long *)(b); \ 691dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project *(long *)(b) = t; \ 701dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } else \ 711dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swapfunc(a, b, es, swaptype) 721dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 73e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) 741dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 755f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopianstatic __inline char * 765f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopianmed3(char *a, char *b, char *c, int (*cmp)(const void *, const void *)) 771dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project{ 785f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian return cmp(a, b) < 0 ? 795f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) 805f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); 811dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project} 821dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 831dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectvoid 845f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopianqsort(void *aa, size_t n, size_t es, int (*cmp)(const void *, const void *)) 851dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project{ 861dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 875f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian int d, r, swaptype, swap_cnt; 885f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian char *a = aa; 891dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 901dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectloop: SWAPINIT(a, es); 911dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swap_cnt = 0; 921dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (n < 7) { 935f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es) 945f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 951dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pl -= es) 961dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swap(pl, pl - es); 971dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project return; 981dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 991dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pm = (char *)a + (n / 2) * es; 1001dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (n > 7) { 1015f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian pl = (char *)a; 1021dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pn = (char *)a + (n - 1) * es; 1031dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (n > 40) { 1041dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project d = (n / 8) * es; 1055f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian pl = med3(pl, pl + d, pl + 2 * d, cmp); 1065f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian pm = med3(pm - d, pm, pm + d, cmp); 1075f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian pn = med3(pn - 2 * d, pn - d, pn, cmp); 1081dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 1095f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian pm = med3(pl, pm, pn, cmp); 1101dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 1111dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swap(a, pm); 1121dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pa = pb = (char *)a + es; 113e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa 1141dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pc = pd = (char *)a + (n - 1) * es; 1151dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project for (;;) { 1165f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian while (pb <= pc && (r = cmp(pb, a)) <= 0) { 1175f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian if (r == 0) { 1181dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swap_cnt = 1; 1191dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swap(pa, pb); 1201dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pa += es; 121e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa } 1221dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pb += es; 1231dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 1245f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian while (pb <= pc && (r = cmp(pc, a)) >= 0) { 1255f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian if (r == 0) { 1261dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swap_cnt = 1; 1271dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swap(pc, pd); 1281dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pd -= es; 1291dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 1301dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pc -= es; 1311dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 1321dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (pb > pc) 1331dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project break; 1341dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swap(pb, pc); 1351dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swap_cnt = 1; 1361dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pb += es; 1371dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pc -= es; 1381dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 1391dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (swap_cnt == 0) { /* Switch to insertion sort */ 1405f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) 141e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 1421dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pl -= es) 1431dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project swap(pl, pl - es); 1441dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project return; 145e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa } 1461dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1471dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project pn = (char *)a + n * es; 1481dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project r = min(pa - (char *)a, pb - pa); 1491dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project vecswap(a, pb - r, r); 1501dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project r = min(pd - pc, pn - pd - (int)es); 1511dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project vecswap(pb, pn - r, r); 1525f53a18204ec991f5a77872806eeaa185936aa8cMathias Agopian if ((r = pb - pa) > (int)es) 1531dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project qsort(a, r / es, es, cmp); 154e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa if ((r = pd - pc) > (int)es) { 1551dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project /* Iterate rather than recurse to save stack space */ 1561dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project a = pn - r; 1571dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project n = r / es; 1581dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project goto loop; 1591dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 160e734769276045c0cb89d4620fdd4ef35a0e6c335André Goddard Rosa /* qsort(pn - r, r / es, es, cmp); */ 1611dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project} 162