1/** @file 2 Quick Sort utility function. 3 4 This utility makes use of a comparison function to search arrays of 5 unspecified type. Where an argument declared as size_t nmemb specifies the 6 length of the array for a function, nmemb can have the value zero on a call 7 to that function; the comparison function is not called, a search finds no 8 matching element. Pointer arguments on such a call shall still have valid 9 values. 10 11 The implementation shall ensure that both arguments of the comparison 12 function are pointers to elements of the array. 13 14 The comparison function shall not alter the contents of the array. The 15 implementation may reorder elements of the array between calls to the 16 comparison function, but shall not alter the contents of any individual 17 element. 18 19 When the same objects (consisting of size bytes, irrespective of their 20 current positions in the array) are passed more than once to the comparison 21 function, the results shall be consistent with one another. That is, they 22 define a total ordering on the array. 23 24 A sequence point occurs immediately before and immediately after each call to 25 the comparison function, and also between any call to the comparison function 26 and any movement of the objects passed as arguments to that call. 27 28 Copyright (c) 2010, Intel Corporation. All rights reserved.<BR> 29 * Copyright (c) 1992, 1993 30 * The Regents of the University of California. All rights reserved. 31 * 32 * Redistribution and use in source and binary forms, with or without 33 * modification, are permitted provided that the following conditions 34 * are met: 35 * 1. Redistributions of source code must retain the above copyright 36 * notice, this list of conditions and the following disclaimer. 37 * 2. Redistributions in binary form must reproduce the above copyright 38 * notice, this list of conditions and the following disclaimer in the 39 * documentation and/or other materials provided with the distribution. 40 * 4. Neither the name of the University nor the names of its contributors 41 * may be used to endorse or promote products derived from this software 42 * without specific prior written permission. 43 * 44 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 45 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 46 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 47 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 48 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 49 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 50 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 51 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 52 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 53 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 54 * SUCH DAMAGE. 55 56 ("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15.2.1.2.1 2009/10/25 01:10:29 kensmith Exp $"); 57 */ 58#include <LibConfig.h> 59 60#include <stdlib.h> 61 62typedef int cmp_t(const void *, const void *); 63 64static __inline char *med3(char *, char *, char *, cmp_t *); 65static __inline void swapfunc(char *, char *, size_t, int); 66 67/* 68 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". 69 */ 70#define swapcode(TYPE, parmi, parmj, n) { \ 71 size_t i = (n) / sizeof (TYPE); \ 72 TYPE *pi = (TYPE *) (parmi); \ 73 TYPE *pj = (TYPE *) (parmj); \ 74 do { \ 75 TYPE t = *pi; \ 76 *pi++ = *pj; \ 77 *pj++ = t; \ 78 } while (--i > 0); \ 79} 80 81#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ 82 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; 83 84static __inline void 85swapfunc(char *a, char *b, size_t n, int swaptype) 86{ 87 if(swaptype <= 1) 88 swapcode(long, a, b, n) 89 else 90 swapcode(char, a, b, n) 91} 92 93#define swap(a, b) \ 94 if (swaptype == 0) { \ 95 long t = *(long *)(a); \ 96 *(long *)(a) = *(long *)(b); \ 97 *(long *)(b) = t; \ 98 } else \ 99 swapfunc(a, b, es, swaptype) 100 101#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) 102 103static __inline char * 104med3(char *a, char *b, char *c, cmp_t *cmp ) 105{ 106 return cmp(a, b) < 0 ? 107 (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) 108 :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); 109} 110 111/* The qsort function sorts an array of nmemb objects, the initial element of 112 which is pointed to by base. The size of each object is specified by size. 113 114 The contents of the array are sorted into ascending order according to a 115 comparison function pointed to by compar, which is called with two 116 arguments that point to the objects being compared. The function shall 117 return an integer less than, equal to, or greater than zero if the first 118 argument is considered to be respectively less than, equal to, or greater 119 than the second. 120 121 If two elements compare as equal, their order in the resulting sorted array 122 is unspecified. 123*/ 124void 125qsort(void *a, size_t n, size_t es, cmp_t *cmp) 126{ 127 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 128 size_t d, r; 129 int cmp_result; 130 int swaptype, swap_cnt; 131 132loop: SWAPINIT(a, es); 133 swap_cnt = 0; 134 if (n < 7) { 135 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 136 for (pl = pm; 137 pl > (char *)a && cmp(pl - es, pl) > 0; 138 pl -= es) 139 swap(pl, pl - es); 140 return; 141 } 142 pm = (char *)a + (n / 2) * es; 143 if (n > 7) { 144 pl = a; 145 pn = (char *)a + (n - 1) * es; 146 if (n > 40) { 147 d = (n / 8) * es; 148 pl = med3(pl, pl + d, pl + 2 * d, cmp); 149 pm = med3(pm - d, pm, pm + d, cmp); 150 pn = med3(pn - 2 * d, pn - d, pn, cmp); 151 } 152 pm = med3(pl, pm, pn, cmp); 153 } 154 swap(a, pm); 155 pa = pb = (char *)a + es; 156 157 pc = pd = (char *)a + (n - 1) * es; 158 for (;;) { 159 while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) { 160 if (cmp_result == 0) { 161 swap_cnt = 1; 162 swap(pa, pb); 163 pa += es; 164 } 165 pb += es; 166 } 167 while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) { 168 if (cmp_result == 0) { 169 swap_cnt = 1; 170 swap(pc, pd); 171 pd -= es; 172 } 173 pc -= es; 174 } 175 if (pb > pc) 176 break; 177 swap(pb, pc); 178 swap_cnt = 1; 179 pb += es; 180 pc -= es; 181 } 182 if (swap_cnt == 0) { /* Switch to insertion sort */ 183 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 184 for (pl = pm; 185 pl > (char *)a && cmp(pl - es, pl) > 0; 186 pl -= es) 187 swap(pl, pl - es); 188 return; 189 } 190 191 pn = (char *)a + n * es; 192 r = MIN(pa - (char *)a, pb - pa); 193 vecswap(a, pb - r, r); 194 r = MIN((size_t)(pd - pc), ((size_t)(pn - pd)) - es); 195 vecswap(pb, pn - r, r); 196 if ((size_t)(r = pb - pa) > es) 197 qsort(a, r / es, es, cmp); 198 if ((size_t)(r = pd - pc) > es) { 199 /* Iterate rather than recurse to save stack space */ 200 a = pn - r; 201 n = r / es; 202 goto loop; 203 } 204/* qsort(pn - r, r / es, es, cmp);*/ 205} 206