00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035 #if defined(LIBC_SCCS) && !defined(lint)
00036 static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
00037 #endif
00038 #include <sys/cdefs.h>
00039
00040
00041
00042 #include <stdlib.h>
00043
00044 typedef int cmp_t(const void *, const void *, void *);
00045 static inline char *med3(char *, char *, char *, cmp_t *, void *);
00046 static inline void swapfunc(char *, char *, int, int);
00047
00048 #define min(a, b) (a) < (b) ? a : b
00049
00050
00051
00052
00053 #define swapcode(TYPE, parmi, parmj, n) { \
00054 long i = (n) / sizeof (TYPE); \
00055 TYPE *pi = (TYPE *) (parmi); \
00056 TYPE *pj = (TYPE *) (parmj); \
00057 do { \
00058 TYPE t = *pi; \
00059 *pi++ = *pj; \
00060 *pj++ = t; \
00061 } while (--i > 0); \
00062 }
00063
00064 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
00065 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
00066
00067 static inline void
00068 swapfunc(a, b, n, swaptype)
00069 char *a, *b;
00070 int n, swaptype;
00071 {
00072 if(swaptype <= 1)
00073 swapcode(long, a, b, n)
00074 else
00075 swapcode(char, a, b, n)
00076 }
00077
00078 #define swap(a, b) \
00079 if (swaptype == 0) { \
00080 long t = *(long *)(a); \
00081 *(long *)(a) = *(long *)(b); \
00082 *(long *)(b) = t; \
00083 } else \
00084 swapfunc(a, b, es, swaptype)
00085
00086 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
00087
00088 #define CMP(t, x, y) (cmp((x), (y), (t)))
00089
00090 static inline char *
00091 med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk)
00092 {
00093 return CMP(thunk, a, b) < 0 ?
00094 (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
00095 :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
00096 }
00097
00098 void
00099 sat_sort(void *a, size_t n, size_t es, cmp_t *cmp, void *thunk)
00100 {
00101 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
00102 size_t d, r;
00103 int cmp_result;
00104 int swaptype, swap_cnt;
00105
00106 loop: SWAPINIT(a, es);
00107 swap_cnt = 0;
00108 if (n < 7) {
00109 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
00110 for (pl = pm;
00111 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
00112 pl -= es)
00113 swap(pl, pl - es);
00114 return;
00115 }
00116 pm = (char *)a + (n / 2) * es;
00117 if (n > 7) {
00118 pl = a;
00119 pn = (char *)a + (n - 1) * es;
00120 if (n > 40) {
00121 d = (n / 8) * es;
00122 pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
00123 pm = med3(pm - d, pm, pm + d, cmp, thunk);
00124 pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
00125 }
00126 pm = med3(pl, pm, pn, cmp, thunk);
00127 }
00128 swap(a, pm);
00129 pa = pb = (char *)a + es;
00130
00131 pc = pd = (char *)a + (n - 1) * es;
00132 for (;;) {
00133 while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
00134 if (cmp_result == 0) {
00135 swap_cnt = 1;
00136 swap(pa, pb);
00137 pa += es;
00138 }
00139 pb += es;
00140 }
00141 while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
00142 if (cmp_result == 0) {
00143 swap_cnt = 1;
00144 swap(pc, pd);
00145 pd -= es;
00146 }
00147 pc -= es;
00148 }
00149 if (pb > pc)
00150 break;
00151 swap(pb, pc);
00152 swap_cnt = 1;
00153 pb += es;
00154 pc -= es;
00155 }
00156 if (swap_cnt == 0) {
00157 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
00158 for (pl = pm;
00159 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
00160 pl -= es)
00161 swap(pl, pl - es);
00162 return;
00163 }
00164
00165 pn = (char *)a + n * es;
00166 r = min(pa - (char *)a, pb - pa);
00167 vecswap(a, pb - r, r);
00168 r = min(pd - pc, pn - pd - es);
00169 vecswap(pb, pn - r, r);
00170 if ((r = pb - pa) > es)
00171 sat_sort(a, r / es, es, cmp, thunk);
00172 if ((r = pd - pc) > es) {
00173
00174 a = pn - r;
00175 n = r / es;
00176 goto loop;
00177 }
00178
00179 }