1 /* 2 * Copyright (c) 1992, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * SPDX-License-Identifier: BSD-3-Clause 6 */ 7 8 #include "yportenv.h" 9 /* #include <linux/string.h> */ 10 11 /* 12 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". 13 */ 14 #define swapcode(TYPE, parmi, parmj, n) do { \ 15 long i = (n) / sizeof(TYPE); \ 16 register TYPE *pi = (TYPE *) (parmi); \ 17 register TYPE *pj = (TYPE *) (parmj); \ 18 do { \ 19 register TYPE t = *pi; \ 20 *pi++ = *pj; \ 21 *pj++ = t; \ 22 } while (--i > 0); \ 23 } while (0) 24 25 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ 26 es % sizeof(long) ? 2 : es == sizeof(long) ? 0 : 1; 27 28 static inline void 29 swapfunc(char *a, char *b, int n, int swaptype) 30 { 31 if (swaptype <= 1) 32 swapcode(long, a, b, n); 33 else 34 swapcode(char, a, b, n); 35 } 36 37 #define yswap(a, b) do { \ 38 if (swaptype == 0) { \ 39 long t = *(long *)(a); \ 40 *(long *)(a) = *(long *)(b); \ 41 *(long *)(b) = t; \ 42 } else \ 43 swapfunc(a, b, es, swaptype); \ 44 } while (0) 45 46 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) 47 48 static inline char * 49 med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *)) 50 { 51 return cmp(a, b) < 0 ? 52 (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a)) 53 : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c)); 54 } 55 56 #ifndef min 57 #define min(a, b) (((a) < (b)) ? (a) : (b)) 58 #endif 59 60 void 61 yaffs_qsort(void *aa, size_t n, size_t es, 62 int (*cmp)(const void *, const void *)) 63 { 64 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 65 int d, r, swaptype, swap_cnt; 66 register char *a = aa; 67 68 loop: SWAPINIT(a, es); 69 swap_cnt = 0; 70 if (n < 7) { 71 for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es) 72 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 73 pl -= es) 74 yswap(pl, pl - es); 75 return; 76 } 77 pm = (char *)a + (n / 2) * es; 78 if (n > 7) { 79 pl = (char *)a; 80 pn = (char *)a + (n - 1) * es; 81 if (n > 40) { 82 d = (n / 8) * es; 83 pl = med3(pl, pl + d, pl + 2 * d, cmp); 84 pm = med3(pm - d, pm, pm + d, cmp); 85 pn = med3(pn - 2 * d, pn - d, pn, cmp); 86 } 87 pm = med3(pl, pm, pn, cmp); 88 } 89 yswap(a, pm); 90 pa = pb = (char *)a + es; 91 92 pc = pd = (char *)a + (n - 1) * es; 93 for (;;) { 94 while (pb <= pc && (r = cmp(pb, a)) <= 0) { 95 if (r == 0) { 96 swap_cnt = 1; 97 yswap(pa, pb); 98 pa += es; 99 } 100 pb += es; 101 } 102 while (pb <= pc && (r = cmp(pc, a)) >= 0) { 103 if (r == 0) { 104 swap_cnt = 1; 105 yswap(pc, pd); 106 pd -= es; 107 } 108 pc -= es; 109 } 110 if (pb > pc) 111 break; 112 yswap(pb, pc); 113 swap_cnt = 1; 114 pb += es; 115 pc -= es; 116 } 117 if (swap_cnt == 0) { /* Switch to insertion sort */ 118 for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) 119 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 120 pl -= es) 121 yswap(pl, pl - es); 122 return; 123 } 124 125 pn = (char *)a + n * es; 126 r = min(pa - (char *)a, pb - pa); 127 vecswap(a, pb - r, r); 128 r = min((long)(pd - pc), (long)(pn - pd - es)); 129 vecswap(pb, pn - r, r); 130 r = pb - pa; 131 if (r > es) 132 yaffs_qsort(a, r / es, es, cmp); 133 r = pd - pc; 134 if (r > es) { 135 /* Iterate rather than recurse to save stack space */ 136 a = pn - r; 137 n = r / es; 138 goto loop; 139 } 140 /* yaffs_qsort(pn - r, r / es, es, cmp);*/ 141 } 142