Re: qsort fix

Zeev Suraski wrote: > You've sent this to php3-dev@, which isn't php-dev@. Oops, sorry. > > About the fix, what does it come to fix exactly? A broken libc qsort() > implementation? > Yes, on Solaris 7 qsort causes the program to segfault about 75% of the time when using a comparison function that randomly returns -1 or 1. I played around with several arrays, and it doesn't seem to be related to array size or content. I don't have any boxes running older versions of solaris, so I don't know if they are affected. > > 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 -- 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