Re: qsort fix

You've sent this to php3-dev@, which isn't php-dev@. About the fix, what does it come to fix exactly? A broken libc qsort() implementation? Zeev On Thu, 27 May 1999, Chad Cunningham wrote: > Below is the function I used for qsort to get it working on solaris. > Note that I took the cheap way out and just threw it in php3_hash.c. I > tested it on Solaris7 and RedHat6, works very well (i.e. no core dumps > :). I also did some tests with a c program and found it to be faster > than the standard c qsort function. > > > [ccunning@NEW93109230 src]$ diff php-3.0.8-devel/php3_hash.c > php-3.0.8/php3_hash.c > 37a38 > > > 93,176d93 > < #include <stdlib.h> > < > < #define SWAPINIT(a, es) swaptype = \ > < (a - (char*) 0) % sizeof(long) || es % sizeof(long) ? 2 : \ > < es == sizeof(long) ? 0 : 1; > < #define swapcode(TYPE, parmi, parmj, n) { \ > < long i = (n) / sizeof(TYPE); \ > < register TYPE *pi = (TYPE *) (parmi); \ > < register TYPE *pj = (TYPE *) (parmj); \ > < do { \ > < register TYPE t = *pi; \ > < *pi++ = *pj; \ > < *pj++ = t; \ > < } while (--i > 0); \ > < } > < void swapfunc(char *a, char *b, int n, int 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) > < > < #define min(x, y) ((x)<=(y) ? (x) : (y)) > < > < char *med3(char *a, char *b, char *c, int (*cmp)()) > < { return cmp(a, b) < 0 ? > < (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ) ) > < : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ) > ); > < } > < > < void php_qsort(char *a, unsigned n, int es, int (*cmp)()) > < { > < char *pa, *pb, *pc, *pd, *pl, *pm, *pn; > < int d, r, swaptype; > < > < SWAPINIT(a, es); > < if (n < 7) { /* Insertion sort on small arrays */ > < for (pm = a + es; pm < a + n*es; pm += es) > < for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl > -= es) > < swap(pl, pl-es); > < return; > < } > < pm = a + (n/2) * es; > < if (n > 7) { > < pl = a; > < pn = a + (n-1) * es; > < if (n > 40) { /* On big arrays, pseudomedian of 9 */ > < d = (n/8) * es; > < pl = med3(pl, pl+d, pl+2*d, cmp); > < pm = med3(pm-d, pm, pm+d, cmp); > < pn = med3(pn-2*d, pn-d, pn, cmp); > < } > < pm = med3(pl, pm, pn, cmp); /* On mid arrays, med of 3 > */ > < } > < swap(a, pm); /* On tiny arrays, partition around middle */ > < pa = pb = a + es; > < pc = pd = a + (n-1)*es; > < for (;;) { > < while (pb <= pc && (r = cmp(pb, a)) <= 0) { > < if (r == 0) { swap(pa, pb); pa += es; } > < pb += es; > < } > < while (pb <= pc && (r = cmp(pc, a)) >= 0) { > < if (r == 0) { swap(pc, pd); pd -= es; } > < pc -= es; > < } > < if (pb > pc) break; > < swap(pb, pc); > < pb += es; > < pc -= es; > < } > < pn = a + n*es; > < r = min(pa-a, pb-pa); vecswap(a, pb-r, r); > < r = min(pd-pc, pn-pd-es); vecswap(pb, pn-r, r); > < if ((r = pb-pa) > es) php_qsort(a, r/es, es, cmp); > < if ((r = pd-pc) > es) php_qsort(pn-r, r/es, es, cmp); > < } > < > 1084c1001 > < php_qsort((void *) arTmp, i, sizeof(Bucket *), compar); > --- > > qsort((void *) arTmp, i, sizeof(Bucket *), compar); > > > > -- > > Chad Cunningham > ccunning@math.ohio-state.edu > > -- ----------------------------------------------------- Zeev Suraski <zeev@zend.com> For a PGP public key, finger bourbon@netvision.net.il -- PHP Development Mailing List http://www.php.net/ To unsubscribe send an empty message to php-dev-unsubscribe@lists.php.net For help: php-dev-help@lists.php.net