OS/390 cleanable gunk.

[p5sagit/p5-mst-13.2.git] / pp_sort.c

diff --git a/pp_sort.c b/pp_sort.c
index d4e4d8b..797cb22 100644 (file)
--- a/pp_sort.c
+++ b/pp_sort.c
@@ -34,6 +34,10 @@ static I32 amagic_cmp_locale(pTHX_ SV *a, SV *b);
       (hintsvp = hv_fetch(GvHV(PL_hintgv), "SORT", 4, FALSE))) ? \
          (I32)SvIV(*hintsvp) : 0)
 
+#ifndef SMALLSORT
+#define        SMALLSORT (200)
+#endif
+
 /*
  * The mergesort implementation is by Peter M. Mcilroy <pmcilroy@lucent.com>.
  *
@@ -281,9 +285,11 @@ S_mergesortsv(pTHX_ gptr *list1, size_t nmemb, SVCOMPARE_t cmp)
     gptr *aux, *list2, *p2, *last;
     gptr *base = list1;
     gptr *p1;
+    gptr small[SMALLSORT];
 
     if (nmemb <= 1) return;    /* sorted trivially */
-    New(799,list2,nmemb,gptr); /* allocate auxilliary array */
+    if (nmemb <= SMALLSORT) list2 = small;     /* use stack for aux array */
+    else { New(799,list2,nmemb,gptr); }                /* allocate auxilliary array */
     aux = list2;
     dynprep(aTHX_ list1, list2, nmemb, cmp);
     last = PINDEX(list2, nmemb);
@@ -395,7 +401,7 @@ S_mergesortsv(pTHX_ gptr *list1, size_t nmemb, SVCOMPARE_t cmp)
        last = PINDEX(list1, nmemb);
        FROMTOUPTO(list1, list2, last);
     }
-    Safefree(aux);
+    if (aux != small) Safefree(aux);   /* free iff allocated */
     return;
 }
 
@@ -476,6 +482,17 @@ S_mergesortsv(pTHX_ gptr *list1, size_t nmemb, SVCOMPARE_t cmp)
 #define QSORT_BREAK_EVEN 6
 #endif
 
+/* QSORT_PLAY_SAFE is the size of the largest partition we're willing
+   to go quadratic on.  We innoculate larger partitions against
+   quadratic behavior by shuffling them before sorting.  This is not
+   an absolute guarantee of non-quadratic behavior, but it would take
+   staggeringly bad luck to pick extreme elements as the pivot
+   from randomized data.
+*/
+#ifndef QSORT_PLAY_SAFE
+#define QSORT_PLAY_SAFE 255
+#endif
+
 /* ************************************************************* Data Types */
 
 /* hold left and right index values of a partition waiting to be sorted (the
@@ -607,6 +624,18 @@ S_qsortsvu(pTHX_ SV ** array, size_t num_elts, SVCOMPARE_t compare)
       return;
    }
 
+   /* Innoculate large partitions against quadratic behavior */
+   if (num_elts > QSORT_PLAY_SAFE) {
+      register size_t n, j;
+      register SV **q;
+      for (n = num_elts, q = array; n > 1; ) {
+         j = n-- * Drand01();
+         temp = q[j];
+         q[j] = q[n];
+         q[n] = temp;
+      }
+   }
+
    /* Setup the initial partition definition and fall into the sorting loop
    */
    part_left = 0;
@@ -1078,10 +1107,6 @@ S_qsortsvu(pTHX_ SV ** array, size_t num_elts, SVCOMPARE_t compare)
    /* Believe it or not, the array is sorted at this point! */
 }
 
-#ifndef SMALLSORT
-#define        SMALLSORT (200)
-#endif
-
 /* Stabilize what is, presumably, an otherwise unstable sort method.
  * We do that by allocating (or having on hand) an array of pointers
  * that is the same size as the original array of elements to be sorted.
@@ -1152,28 +1177,26 @@ S_qsortsv(pTHX_ gptr *list1, size_t nmemb, SVCOMPARE_t cmp)
 {
     SV **hintsvp;
 
-    if (SORTHINTS(hintsvp) & HINT_SORT_FAST)
-        S_qsortsvu(aTHX_ list1, nmemb, cmp);
-    else {
+    if (SORTHINTS(hintsvp) & HINT_SORT_STABLE) {
         register gptr **pp, *q;
         register size_t n, j, i;
         gptr *small[SMALLSORT], **indir, tmp;
         SVCOMPARE_t savecmp;
         if (nmemb <= 1) return;     /* sorted trivially */
-        
+
         /* Small arrays can use the stack, big ones must be allocated */
         if (nmemb <= SMALLSORT) indir = small;
         else { New(1799, indir, nmemb, gptr *); }
-        
+
         /* Copy pointers to original array elements into indirect array */
         for (n = nmemb, pp = indir, q = list1; n--; ) *pp++ = q++;
-        
+
         savecmp = RealCmp;     /* Save current comparison routine, if any */
         RealCmp = cmp; /* Put comparison routine where cmpindir can find it */
-        
+
         /* sort, with indirection */
         S_qsortsvu(aTHX_ (gptr *)indir, nmemb, cmpindir);
-        
+
         pp = indir;
         q = list1;
         for (n = nmemb; n--; ) {
@@ -1215,19 +1238,21 @@ S_qsortsv(pTHX_ gptr *list1, size_t nmemb, SVCOMPARE_t cmp)
         if (indir != small) { Safefree(indir); }
         /* restore prevailing comparison routine */
         RealCmp = savecmp;
+    } else {
+        S_qsortsvu(aTHX_ list1, nmemb, cmp);
     }
 }
- 
-/* 
+
+/*
 =for apidoc sortsv
 
 Sort an array. Here is an example:
 
-    sortsv(AvARRAY(av), av_len(av)+1, Perl_sv_cmp_locale); 
+    sortsv(AvARRAY(av), av_len(av)+1, Perl_sv_cmp_locale);
 
 =cut
 */
-    
+
 void
 Perl_sortsv(pTHX_ SV **array, size_t nmemb, SVCOMPARE_t cmp)
 {
@@ -1235,7 +1260,7 @@ Perl_sortsv(pTHX_ SV **array, size_t nmemb, SVCOMPARE_t cmp)
         S_mergesortsv;
     SV **hintsvp;
     I32 hints;
-    
+
     if ((hints = SORTHINTS(hintsvp))) {
         if (hints & HINT_SORT_QUICKSORT)
              sortsvp = S_qsortsv;
@@ -1246,7 +1271,7 @@ Perl_sortsv(pTHX_ SV **array, size_t nmemb, SVCOMPARE_t cmp)
                   sortsvp = S_mergesortsv;
         }
     }
-    
+
     sortsvp(aTHX_ array, nmemb, cmp);
 }
 
@@ -1553,7 +1578,7 @@ amagic_ncmp(pTHX_ register SV *a, register SV *b)
     tryCALL_AMAGICbin(a,b,ncmp,&tmpsv);
     if (tmpsv) {
        NV d;
-       
+ 
         if (SvIOK(tmpsv)) {
             I32 i = SvIVX(tmpsv);
             if (i > 0)
@@ -1575,7 +1600,7 @@ amagic_i_ncmp(pTHX_ register SV *a, register SV *b)
     tryCALL_AMAGICbin(a,b,ncmp,&tmpsv);
     if (tmpsv) {
        NV d;
-       
+
         if (SvIOK(tmpsv)) {
             I32 i = SvIVX(tmpsv);
             if (i > 0)
@@ -1597,7 +1622,7 @@ amagic_cmp(pTHX_ register SV *str1, register SV *str2)
     tryCALL_AMAGICbin(str1,str2,scmp,&tmpsv);
     if (tmpsv) {
        NV d;
-       
+ 
         if (SvIOK(tmpsv)) {
             I32 i = SvIVX(tmpsv);
             if (i > 0)
@@ -1619,7 +1644,7 @@ amagic_cmp_locale(pTHX_ register SV *str1, register SV *str2)
     tryCALL_AMAGICbin(str1,str2,scmp,&tmpsv);
     if (tmpsv) {
        NV d;
-       
+ 
         if (SvIOK(tmpsv)) {
             I32 i = SvIVX(tmpsv);
             if (i > 0)