From: Michael Neumann <neumann@...>
Date: 2000-08-23T21:29:38+09:00
Subject: [ruby-talk:4564] Re: methods w/ ! giving nil


From: "Yukihiro Matsumoto" <matz@zetabits.com>


> Hi,
>
> In message "[ruby-talk:4525] Re: methods w/ ! giving nil"
>     on 00/08/21, Hugh Sasse Staff Elec Eng <hgs@dmu.ac.uk> writes:
>
> |That makes sense.  Could Ruby have its own qsort routine (in C) that
> |achieves this notification?
>
> Actually Ruby does have its own qsort routine in C (in util.c), which
> is compatible with original qsort(3).  Only problem left is re-design
> and hack the routine.   I'm afraid it's a tough task, for me at least.

To check, if the qsort-routine changes the array, you can set a flag if
"mmswap" is called (variable "changed").
I've changed "ruby_qsort" in utils.c to return 0 if nothing changed, and 1
if changed.
I think it won't be significantly slower than the original.
Here's the code:

int ruby_qsort (base, nel, size, cmp) void* base; int nel; int size; int
(*cmp)();
{
 register char *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 */
 int  chklim = 63;                      /* threshold of ordering element
check */
 stack_node stack[32], *top = stack;    /* 32 is enough for 32bit CPU */

 int changed = 0;


 if (nel <= 1) return changed;        /* need not to sort */
 mmprepare(base, size);
 goto start;

 nxt:
 if (stack == top) return changed;    /* return if stack is empty */
 POP(L,R);

 for (;;) {
   start:
   if (L + size == R) {if ((*cmp)(L,R) > 0) {mmswap(L,R);changed=1;} goto
nxt;}/* 2 elements */

   l = L; r = R;
   t = (r - l + size) / size;  /* number of elements */
   m = l + size * (t >> 1);    /* calculate median value */

   if (t >= 60) {
     register char *m1;
     register char *m3;
     if (t >= 200) {
       t = size*(t>>3); /* number of bytes in splitting 8 */
       {
       register char *p1 = l  + t;
       register char *p2 = p1 + t;
       register char *p3 = p2 + t;
       m1 = med3(p1, p2, p3);
       p1 = m  + t;
       p2 = p1 + t;
       p3 = p2 + t;
       m3 = med3(p1, p2, p3);
       }
     }else{
       t = size*(t>>2); /* number of bytes in splitting 4 */
       m1 = l + t;
       m3 = m + t;
     }
     m = med3(m1, m, m3);
   }

   if ((t = (*cmp)(l,m)) < 0) {                             /*3-5-?*/
     if ((t = (*cmp)(m,r)) < 0) {                           /*3-5-7*/
       if (chklim && nel >= chklim) {   /* check if already ascending order
*/
         char *p;
         chklim = 0;
         for (p=l; p<r; p+=size) if ((*cmp)(p,p+size) > 0) goto fail;
         goto nxt;
       }
       fail: goto loopA;                                    /*3-5-7*/
     }
     if (t > 0) {
       if ((*cmp)(l,r) <= 0) {mmswap(m,r);changed=1; goto loopA;}
/*3-5-4*/
       mmrot3(r,m,l); goto loopA;                           /*3-5-2*/
     }
     goto loopB;                                            /*3-5-5*/
   }

   if (t > 0) {                                             /*7-5-?*/
     if ((t = (*cmp)(m,r)) > 0) {                           /*7-5-3*/
       if (chklim && nel >= chklim) {   /* check if already ascending order
*/
         char *p;
         chklim = 0;
         for (p=l; p<r; p+=size) if ((*cmp)(p,p+size) < 0) goto fail2;
         while (l<r) {mmswap(l,r); changed=1; l+=size; r-=size;}  /* reverse
region */
         goto nxt;
       }
       fail2: mmswap(l,r); changed=1; goto loopA;
/*7-5-3*/
     }
     if (t < 0) {
       if ((*cmp)(l,r) <= 0) {mmswap(l,m); changed=1; goto loopB;}
/*7-5-8*/
       mmrot3(l,m,r); goto loopA;                           /*7-5-6*/
     }
     mmswap(l,r); changed=1; goto loopA;
/*7-5-5*/
   }

   if ((t = (*cmp)(m,r)) < 0)  {goto loopA;}                /*5-5-7*/
   if (t > 0) {mmswap(l,r); changed=1; goto loopB;}
/*5-5-3*/

   /* deteming splitting type in case 5-5-5 */              /*5-5-5*/
   for (;;) {
     if ((l += size) == r)      goto nxt;                   /*5-5-5*/
     if (l == m) continue;
     if ((t = (*cmp)(l,m)) > 0) {mmswap(l,r);changed=1; l = L; goto loopA;}
/*575-5*/
     if (t < 0)                 {mmswap(L,l);changed=1; l = L; goto loopB;}
/*535-5*/
   }

   loopA: eq_l = 1; eq_r = 1;  /* splitting type A */ /* left <= median <
right */
   for (;;) {
     for (;;) {
       if ((l += size) == r)
         {l -= size; if (l != m) {mmswap(m,l);changed=1;} l -= size; goto
fin;}
       if (l == m) continue;
       if ((t = (*cmp)(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);changed=1;} l -= size; goto
fin;}
       if (r == m) {m = l; break;}
       if ((t = (*cmp)(r,m)) < 0) {eq_l = 0; break;}
       if (t == 0) break;
     }
     mmswap(l,r);changed=1;    /* swap left and right */
   }

   loopB: eq_l = 1; eq_r = 1;  /* splitting type B */ /* left < median <=
right */
   for (;;) {
     for (;;) {
       if (l == (r -= size))
         {r += size; if (r != m) {mmswap(r,m);changed=1;} r += size; goto
fin;}
       if (r == m) continue;
       if ((t = (*cmp)(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);changed=1;} r += size; goto
fin;}
       if (l == m) {m = r; break;}
       if ((t = (*cmp)(l,m)) > 0) {eq_r = 0; break;}
       if (t == 0) break;
     }
     mmswap(l,r);changed=1;    /* swap left and right */
   }

   fin:
   if (eq_l == 0)                         /* need to sort left side */
     if (eq_r == 0)                       /* need to sort right side */
       if (l-L < R-r) {PUSH(r,R); R = l;} /* sort left side first */
       else           {PUSH(L,l); L = r;} /* sort right side first */
     else R = l;                          /* need to sort left side only */
   else if (eq_r == 0) L = r;             /* need to sort right side only */
   else goto nxt;                         /* need not to sort both sides */
 }

 return changed;
}



--------------------

Michael


>
> matz.
>