src/compiler/dmd/qsort.d

   1 /*
   2         Portions of this file are:
   3         Copyright Prototronics, 1987
   4         Totem Lake P.O. 8117
   5         Kirkland, Washington 98034
   6         (206) 820-1972
   7         Licensed to Digital Mars.
   8
   9         June 11, 1987 from Ray Gardner's
  10         Denver, Colorado) public domain version
  11
  12         Use qsort2.d instead of this file if a redistributable version of
  13         _adSort() is required.
  14 */
  15
  16 module rt.qsort;
  17
  18 /*
  19 **    Sorts an array starting at base, of length nbr_elements, each
  20 **    element of size width_bytes, ordered via compare_function; which
  21 **    is called as  (*comp_fp)(ptr_to_element1, ptr_to_element2)
  22 **    and returns < 0 if element1 < element2, 0 if element1 = element2,
  23 **    > 0 if element1 > element2.  Most of the refinements are due to
  24 **    R. Sedgewick.  See "Implementing Quicksort Programs", Comm. ACM,
  25 **    Oct. 1978, and Corrigendum, Comm. ACM, June 1979.
  26 */
  27
  28 //debug=qsort;          // uncomment to turn on debugging printf's
  29
  30
  31 struct Array
  32 {
  33     size_t length;
  34     void*  ptr;
  35 }
  36
  37
  38 private const int _maxspan = 7; // subarrays of _maxspan or fewer elements
  39                                 // will be sorted by a simple insertion sort
  40
  41 /* Adjust _maxspan according to relative cost of a swap and a compare.  Reduce
  42 _maxspan (not less than 1) if a swap is very expensive such as when you have
  43 an array of large structures to be sorted, rather than an array of pointers to
  44 structures.  The default value is optimized for a high cost for compares. */
  45
  46
  47 extern (C) long _adSort(Array a, TypeInfo ti)
  48 {
  49   byte* base;
  50   byte*[40] stack;              // stack
  51   byte** sp;                    // stack pointer
  52   byte* i, j, limit;            // scan and limit pointers
  53   uint thresh;                  // size of _maxspan elements in bytes
  54   uint width = ti.tsize();
  55
  56   base = cast(byte *)a.ptr;
  57   thresh = _maxspan * width;             // init threshold
  58   sp = stack.ptr;                        // init stack pointer
  59   limit = base + a.length * width;       // pointer past end of array
  60   while (1)                              // repeat until done then return
  61   {
  62     while (limit - base > thresh)        // if more than _maxspan elements
  63     {
  64       //swap middle, base
  65       ti.swap((cast(uint)(limit - base) >> 1) -
  66            (((cast(uint)(limit - base) >> 1)) % width) + base, base);
  67
  68       i = base + width;                 // i scans from left to right
  69       j = limit - width;                // j scans from right to left
  70
  71       if (ti.compare(i, j) > 0)         // Sedgewick's
  72         ti.swap(i, j);                  //    three-element sort
  73       if (ti.compare(base, j) > 0)      // sets things up
  74         ti.swap(base, j);               // so that
  75       if (ti.compare(i, base) > 0)      // *i <= *base <= *j
  76         ti.swap(i, base);               // *base is the pivot element
  77
  78       while (1)
  79       {
  80         do                              // move i right until *i >= pivot
  81           i += width;
  82         while (ti.compare(i, base) < 0);
  83         do                              // move j left until *j <= pivot
  84           j -= width;
  85         while (ti.compare(j, base) > 0);
  86         if (i > j)                      // break loop if pointers crossed
  87           break;
  88         ti.swap(i, j);                  // else swap elements, keep scanning
  89       }
  90       ti.swap(base, j);                 // move pivot into correct place
  91       if (j - base > limit - i)         // if left subarray is larger...
  92       {
  93         sp[0] = base;                   // stack left subarray base
  94         sp[1] = j;                      //    and limit
  95         base = i;                       // sort the right subarray
  96       }
  97       else                              // else right subarray is larger
  98       {
  99         sp[0] = i;                      // stack right subarray base
 100         sp[1] = limit;                  //    and limit
 101         limit = j;                      // sort the left subarray
 102       }
 103       sp += 2;                          // increment stack pointer
 104       assert(sp < cast(byte**)stack + stack.length);
 105     }
 106
 107     // Insertion sort on remaining subarray
 108     i = base + width;
 109     while (i < limit)
 110     {
 111       j = i;
 112       while (j > base && ti.compare(j - width, j) > 0)
 113       {
 114         ti.swap(j - width, j);
 115         j -= width;
 116       }
 117       i += width;
 118     }
 119
 120     if (sp > stack.ptr)                 // if any entries on stack...
 121     {
 122       sp -= 2;                          // pop the base and limit
 123       base = sp[0];
 124       limit = sp[1];
 125     }
 126     else                                // else stack empty, all done
 127       return *cast(long*)(&a);
 128   }
 129   assert(0);
 130 }
 131
 132
 133 unittest
 134 {
 135     debug(qsort) printf("array.sort.unittest()\n");
 136
 137     int a[] = new int[10];
 138
 139     a[0] = 23;
 140     a[1] = 1;
 141     a[2] = 64;
 142     a[3] = 5;
 143     a[4] = 6;
 144     a[5] = 5;
 145     a[6] = 17;
 146     a[7] = 3;
 147     a[8] = 0;
 148     a[9] = -1;
 149
 150     a.sort;
 151
 152     for (int i = 0; i < a.length - 1; i++)
 153     {
 154         //printf("i = %d", i);
 155         //printf(" %d %d\n", a[i], a[i + 1]);
 156         assert(a[i] <= a[i + 1]);
 157     }
 158 }