Re: qsort fix

I'll look at integrating this or another sort into PHP3. One thing I have to say I don't care for is that the implementation below is recursive, which seems likely to result in stack problems on large arrays. But maybe I'm just being paranoid. Jim On May 27, 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 > > -- 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