Hi,

At Tue, 11 Oct 2005 22:46:31 +0900,
Yukihiro Matsumoto wrote in [ruby-core:06233]:
> |What about for 1.8?  I guess ANSI incompatible qsort() should
> |be removed.
> 
> Yes.  Rename it ruby_sort() or whatever you like.

Then, I'll just remove qsort() macro in util.h and use
ruby_qsort() directly.

Another idea is to make the function VALUE specific.


Index: array.c =================================================================== RCS file: /cvs/ruby/src/ruby/array.c,v retrieving revision 1.181 diff -U2 -p -r1.181 array.c --- array.c 11 Oct 2005 12:30:47 -0000 1.181 +++ array.c 12 Oct 2005 02:05:38 -0000 @@ -1475,7 +1475,6 @@ ary_sort_check(struct ary_sort_data *dat static int -sort_1(const void *ap, const void *bp, void *data) +sort_1(VALUE a, VALUE b, void *data) { - VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp; VALUE retval = rb_yield_values(2, a, b); int n; @@ -1487,8 +1486,7 @@ sort_1(const void *ap, const void *bp, v static int -sort_2(const void *ap, const void *bp, void *data) +sort_2(VALUE a, VALUE b, void *data) { VALUE retval; - VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp; int n; @@ -1516,5 +1514,5 @@ sort_internal(VALUE ary) data.ary = ary; data.ptr = RARRAY(ary)->ptr; data.len = RARRAY(ary)->len; - ruby_qsort(RARRAY(ary)->ptr, RARRAY(ary)->len, sizeof(VALUE), + ruby_qsort(RARRAY(ary)->ptr, RARRAY(ary)->len, rb_block_given_p()?sort_1:sort_2, &data); return ary; Index: enum.c =================================================================== RCS file: /cvs/ruby/src/ruby/enum.c,v retrieving revision 1.64 diff -U2 -p -r1.64 enum.c --- enum.c 11 Oct 2005 12:30:47 -0000 1.64 +++ enum.c 12 Oct 2005 02:06:58 -0000 @@ -434,8 +434,8 @@ sort_by_i(VALUE i, VALUE ary) static int -sort_by_cmp(const void *ap, const void *bp, void *data) +sort_by_cmp(VALUE ap, VALUE bp, void *data) { - VALUE a = (*(NODE *const *)ap)->u1.value; - VALUE b = (*(NODE *const *)bp)->u1.value; + VALUE a = ((NODE *)ap)->u1.value; + VALUE b = ((NODE *)bp)->u1.value; return rb_cmpint(rb_funcall(a, id_cmp, 1, b), a, b); @@ -528,5 +528,5 @@ enum_sort_by(VALUE obj) rb_iterate(rb_each, obj, sort_by_i, ary); if (RARRAY(ary)->len > 1) { - ruby_qsort(RARRAY(ary)->ptr, RARRAY(ary)->len, sizeof(VALUE), sort_by_cmp, 0); + ruby_qsort(RARRAY(ary)->ptr, RARRAY(ary)->len, sort_by_cmp, 0); } if (RBASIC(ary)->klass) { Index: util.c =================================================================== RCS file: /cvs/ruby/src/ruby/util.c,v retrieving revision 1.48 diff -U2 -p -r1.48 util.c --- util.c 11 Oct 2005 12:30:48 -0000 1.48 +++ util.c 12 Oct 2005 03:01:24 -0000 @@ -383,75 +383,4 @@ __crt0_glob_function(char *path) #endif -/* mm.c */ - -#define A ((int*)a) -#define B ((int*)b) -#define C ((int*)c) -#define D ((int*)d) - -#define mmprepare(base, size) do {\ - if (((long)base & (0x3)) == 0)\ - if (size >= 16) mmkind = 1;\ - else mmkind = 0;\ - else mmkind = -1;\ - high = (size & (~0xf));\ - low = (size & 0x0c);\ -} while (0)\ - -#define mmarg mmkind, size, high, low - -static void mmswap_(a, b, mmarg) - register char *a, *b; - int mmarg; -{ - register int s; - if (a == b) return; - if (mmkind >= 0) { - if (mmkind > 0) { - register char *t = a + high; - do { - s = A[0]; A[0] = B[0]; B[0] = s; - s = A[1]; A[1] = B[1]; B[1] = s; - s = A[2]; A[2] = B[2]; B[2] = s; - s = A[3]; A[3] = B[3]; B[3] = s; a += 16; b += 16; - } while (a < t); - } - if (low != 0) { s = A[0]; A[0] = B[0]; B[0] = s; - if (low >= 8) { s = A[1]; A[1] = B[1]; B[1] = s; - if (low == 12) {s = A[2]; A[2] = B[2]; B[2] = s;}}} - } - else { - register char *t = a + size; - do {s = *a; *a++ = *b; *b++ = s;} while (a < t); - } -} -#define mmswap(a,b) mmswap_((a),(b),mmarg) - -static void mmrot3_(a, b, c, mmarg) - register char *a, *b, *c; - int mmarg; -{ - register int s; - if (mmkind >= 0) { - if (mmkind > 0) { - register char *t = a + high; - do { - s = A[0]; A[0] = B[0]; B[0] = C[0]; C[0] = s; - s = A[1]; A[1] = B[1]; B[1] = C[1]; C[1] = s; - s = A[2]; A[2] = B[2]; B[2] = C[2]; C[2] = s; - s = A[3]; A[3] = B[3]; B[3] = C[3]; C[3] = s; a += 16; b += 16; c += 16; - } while (a < t); - } - if (low != 0) { s = A[0]; A[0] = B[0]; B[0] = C[0]; C[0] = s; - if (low >= 8) { s = A[1]; A[1] = B[1]; B[1] = C[1]; C[1] = s; - if (low == 12) {s = A[2]; A[2] = B[2]; B[2] = C[2]; C[2] = s;}}} - } - else { - register char *t = a + size; - do {s = *a; *a++ = *b; *b++ = *c; *c++ = s;} while (a < t); - } -} -#define mmrot3(a,b,c) mmrot3_((a),(b),(c),mmarg) - /* qs6.c */ /*****************************************************/ @@ -463,26 +392,27 @@ static void mmrot3_(a, b, c, mmarg) /*****************************************************/ -typedef struct { char *LL, *RR; } stack_node; /* Stack structure for L,l,R,r */ +typedef struct { VALUE *LL, *RR; } stack_node; /* Stack structure for L,l,R,r */ #define PUSH(ll,rr) do { top->LL = (ll); top->RR = (rr); ++top; } while (0) /* Push L,l,R,r */ #define POP(ll,rr) do { --top; ll = top->LL; rr = top->RR; } while (0) /* Pop L,l,R,r */ -#define med3(a,b,c) ((*cmp)(a,b,d)<0 ? \ - ((*cmp)(b,c,d)<0 ? b : ((*cmp)(a,c,d)<0 ? c : a)) : \ - ((*cmp)(b,c,d)>0 ? b : ((*cmp)(a,c,d)<0 ? a : c))) +#define med3(a,b,c) (compare(a,b)<0 ? \ + (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) : \ + (compare(b,c)>0 ? b : (compare(a,c)<0 ? a : c))) void -ruby_qsort(void* base, const int nel, const int size, - int (*cmp)(const void*, const void*, void*), void *d) +ruby_qsort(VALUE *base, const int nel, int (*cmp)(VALUE, VALUE, void*), void *d) { - register char *l, *r, *m; /* l,r:left,right group m:median point */ + register VALUE *l, *r, *m; /* l,r:left,right group m:median point */ register int t, eq_l, eq_r; /* eq_l: all items in left group are equal to S */ - char *L = base; /* left end of curren region */ - char *R = (char*)base + size*(nel-1); /* right end of current region */ + VALUE *L = base; /* left end of curren region */ + VALUE *R = base + (nel-1); /* right end of current region */ + VALUE tmp; /* for mmswap */ int chklim = 63; /* threshold of ordering element check */ stack_node stack[32], *top = stack; /* 32 is enough for 32bit CPU */ - int mmkind, high, low; +# define mmswap(a, b) (tmp = *(a), *(a) = *(b), *(b) = tmp) +# define mmrot3(a, b, c) (tmp = *(a), *(a) = *(b), *(b) = *(c), *(c) = tmp) +# define compare(a, b) (*cmp)(*(a), *(b), d) if (nel <= 1) return; /* need not to sort */ - mmprepare(base, size); goto start; @@ -493,21 +423,21 @@ ruby_qsort(void* base, const int nel, co for (;;) { start: - if (L + size == R) { /* 2 elements */ - if ((*cmp)(L,R,d) > 0) mmswap(L,R); goto nxt; + if (L + 1 == R) { /* 2 elements */ + if (compare(L,R) > 0) mmswap(L,R); goto nxt; } l = L; r = R; - t = (r - l + size) / size; /* number of elements */ - m = l + size * (t >> 1); /* calculate median value */ + t = (r - l + 1); /* number of elements */ + m = l + (t >> 1); /* calculate median value */ if (t >= 60) { - register char *m1; - register char *m3; + register VALUE *m1; + register VALUE *m3; if (t >= 200) { - t = size*(t>>3); /* number of bytes in splitting 8 */ + t >>= 3; /* number of bytes in splitting 8 */ { - register char *p1 = l + t; - register char *p2 = p1 + t; - register char *p3 = p2 + t; + register VALUE *p1 = l + t; + register VALUE *p2 = p1 + t; + register VALUE *p3 = p2 + t; m1 = med3(p1, p2, p3); p1 = m + t; @@ -518,5 +448,5 @@ ruby_qsort(void* base, const int nel, co } else { - t = size*(t>>2); /* number of bytes in splitting 4 */ + t >>= 2; /* number of bytes in splitting 4 */ m1 = l + t; m3 = m + t; @@ -525,10 +455,10 @@ ruby_qsort(void* base, const int nel, co } - if ((t = (*cmp)(l,m,d)) < 0) { /*3-5-?*/ - if ((t = (*cmp)(m,r,d)) < 0) { /*3-5-7*/ + if ((t = compare(l,m)) < 0) { /*3-5-?*/ + if ((t = compare(m,r)) < 0) { /*3-5-7*/ if (chklim && nel >= chklim) { /* check if already ascending order */ - char *p; + VALUE *p; chklim = 0; - for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) > 0) goto fail; + for (p=l; p<r; p++) if (compare(p,p+1) > 0) goto fail; goto nxt; } @@ -536,5 +466,5 @@ ruby_qsort(void* base, const int nel, co } if (t > 0) { - if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;} /*3-5-4*/ + if (compare(l,r) <= 0) {mmswap(m,r); goto loopA;} /*3-5-4*/ mmrot3(r,m,l); goto loopA; /*3-5-2*/ } @@ -543,10 +473,10 @@ ruby_qsort(void* base, const int nel, co if (t > 0) { /*7-5-?*/ - if ((t = (*cmp)(m,r,d)) > 0) { /*7-5-3*/ + if ((t = compare(m,r)) > 0) { /*7-5-3*/ if (chklim && nel >= chklim) { /* check if already ascending order */ - char *p; + VALUE *p; chklim = 0; - for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) < 0) goto fail2; - while (l<r) {mmswap(l,r); l+=size; r-=size;} /* reverse region */ + for (p=l; p<r; p++) if (compare(p,p+1) < 0) goto fail2; + while (l<r) {mmswap(l,r); l++; r--;} /* reverse region */ goto nxt; } @@ -554,5 +484,5 @@ ruby_qsort(void* base, const int nel, co } if (t < 0) { - if ((*cmp)(l,r,d) <= 0) {mmswap(l,m); goto loopB;} /*7-5-8*/ + if (compare(l,r) <= 0) {mmswap(l,m); goto loopB;} /*7-5-8*/ mmrot3(l,m,r); goto loopA; /*7-5-6*/ } @@ -560,13 +490,14 @@ ruby_qsort(void* base, const int nel, co } - if ((t = (*cmp)(m,r,d)) < 0) {goto loopA;} /*5-5-7*/ + if ((t = compare(m,r)) < 0) {goto loopA;} /*5-5-7*/ if (t > 0) {mmswap(l,r); goto loopB;} /*5-5-3*/ /* determining splitting type in case 5-5-5 */ /*5-5-5*/ for (;;) { - if ((l += size) == r) goto nxt; /*5-5-5*/ + if (++l == r) goto nxt; /*5-5-5*/ if (l == m) continue; - if ((t = (*cmp)(l,m,d)) > 0) {mmswap(l,r); l = L; goto loopA;}/*575-5*/ - if (t < 0) {mmswap(L,l); l = L; goto loopB;} /*535-5*/ + t = compare(l,m); + if (t > 0) {mmswap(l,r); l = L; goto loopA;} /*575-5*/ + if (t < 0) {mmswap(L,l); l = L; goto loopB;} /*535-5*/ } @@ -574,15 +505,15 @@ ruby_qsort(void* base, const int nel, co for (;;) { for (;;) { - if ((l += size) == r) - {l -= size; if (l != m) mmswap(m,l); l -= size; goto fin;} + if (++l == r) + {--l; if (l != m) mmswap(m,l); --l; goto fin;} if (l == m) continue; - if ((t = (*cmp)(l,m,d)) > 0) {eq_r = 0; break;} + if ((t = compare(l,m)) > 0) {eq_r = 0; break;} if (t < 0) eq_l = 0; } for (;;) { - if (l == (r -= size)) - {l -= size; if (l != m) mmswap(m,l); l -= size; goto fin;} + if (l == --r) + {--l; if (l != m) mmswap(m,l); --l; goto fin;} if (r == m) {m = l; break;} - if ((t = (*cmp)(r,m,d)) < 0) {eq_l = 0; break;} + if ((t = compare(r,m)) < 0) {eq_l = 0; break;} if (t == 0) break; } @@ -593,15 +524,15 @@ ruby_qsort(void* base, const int nel, co for (;;) { for (;;) { - if (l == (r -= size)) - {r += size; if (r != m) mmswap(r,m); r += size; goto fin;} + if (l == --r) + {++r; if (r != m) mmswap(r,m); ++r; goto fin;} if (r == m) continue; - if ((t = (*cmp)(r,m,d)) < 0) {eq_l = 0; break;} + if ((t = compare(r,m)) < 0) {eq_l = 0; break;} if (t > 0) eq_r = 0; } for (;;) { - if ((l += size) == r) - {r += size; if (r != m) mmswap(r,m); r += size; goto fin;} + if (++l == r) + {++r; if (r != m) mmswap(r,m); ++r; goto fin;} if (l == m) {m = r; break;} - if ((t = (*cmp)(l,m,d)) > 0) {eq_r = 0; break;} + if ((t = compare(l,m)) > 0) {eq_r = 0; break;} if (t == 0) break; } Index: util.h =================================================================== RCS file: /cvs/ruby/src/ruby/util.h,v retrieving revision 1.18 diff -U2 -p -r1.18 util.h --- util.h 11 Oct 2005 12:30:48 -0000 1.18 +++ util.h 12 Oct 2005 02:35:18 -0000 @@ -44,5 +44,5 @@ void ruby_add_suffix(VALUE str, char *su #endif -void ruby_qsort(void*, const int, const int, int (*)(const void*,const void*,void*), void*); +void ruby_qsort(VALUE *, const int, int (*)(VALUE, VALUE, void*), void*); void ruby_setenv(const char*, const char*);
-- Nobu Nakada