Mercurial > projects > ldc

comparison druntime/src/compiler/dmd/qsort.d @ 759:d3eb054172f9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added copy of druntime from DMD 2.020 modified for LDC.
author Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
date Tue, 11 Nov 2008 01:52:37 +0100
parents
children
comparison
equal deleted inserted replaced
758:f04dde6e882c 759:d3eb054172f9
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 }