rt.compiler.gdc.rt.qsortg source code

1 module rt.compiler.gdc.rt.qsortg;
2 struct Array
3 {
4     size_t length;
5     void*  ptr;
6 }
7 
8 extern (C) Array _adSort(Array a, TypeInfo ti)
9 {
10     static const uint Qsort_Threshold = 7;
11 
12     struct StackEntry {
13         byte *l;
14         byte *r;
15     }
16 
17     size_t elem_size = ti.tsize();
18     size_t qsort_limit = elem_size * Qsort_Threshold;
19 
20     static assert(ubyte.sizeof == 1);
21     static assert(ubyte.max == 255);
22 
23     StackEntry[size_t.sizeof * 8] stack; // log2( size_t.max )
24     StackEntry * sp = stack.ptr;
25     byte* lbound = cast(byte *) a.ptr;
26     byte* rbound = cast(byte *) a.ptr + a.length * elem_size;
27     byte* li = void;
28     byte* ri = void;
29 
30     while (1)
31     {
32         if (rbound - lbound > qsort_limit)
33         {
34             ti.swap(lbound,
35                 lbound + (
36                           ((rbound - lbound) >>> 1) -
37                           (((rbound - lbound) >>> 1) % elem_size)
38                           ));
39 
40             li = lbound + elem_size;
41             ri = rbound - elem_size;
42 
43             if (ti.compare(li, ri) > 0)
44                 ti.swap(li, ri);
45             if (ti.compare(lbound, ri) > 0)
46                 ti.swap(lbound, ri);
47             if (ti.compare(li, lbound) > 0)
48                 ti.swap(li, lbound);
49 
50             while (1)
51             {
52                 do
53                     li += elem_size;
54                 while (ti.compare(li, lbound) < 0);
55                 do
56                     ri -= elem_size;
57                 while (ti.compare(ri, lbound) > 0);
58                 if (li > ri)
59                     break;
60                 ti.swap(li, ri);
61             }
62             ti.swap(lbound, ri);
63             if (ri - lbound > rbound - li)
64             {
65                 sp.l = lbound;
66                 sp.r = ri;
67                 lbound = li;
68             }
69             else
70             {
71                 sp.l = li;
72                 sp.r = rbound;
73                 rbound = ri;
74             }
75             ++sp;
76         } else {
77             // Use insertion sort
78             for (ri = lbound, li = lbound + elem_size;
79                  li < rbound;
80                  ri = li, li += elem_size)
81             {
82                 for ( ; ti.compare(ri, ri + elem_size) > 0;
83                       ri -= elem_size)
84                 {
85                     ti.swap(ri, ri + elem_size);
86                     if (ri == lbound)
87                         break;
88                 }
89             }
90             if (sp != stack.ptr)
91             {
92                 --sp;
93                 lbound = sp.l;
94                 rbound = sp.r;
95             }
96             else
97                 return a;
98         }
99     }
100 }
101 
102 unittest
103 {
104     static void check(int[] a) {
105         for (uint i = 1; i < a.length; i++)
106             assert(a[i-1] <= a[i]);
107     }
108 
109     static int[] t1 = [ 4, 3, 19, 7, 6, 20, 11, 1, 2, 5 ];
110     int[] a;
111 
112     a = t1;
113     a.sort;
114     check(a);
115 }