1 /**
2 * This is a public domain version of qsort.d. All it does is call C's
3 * qsort().
4 *
5 * Copyright: Copyright Digital Mars 2000 - 2010.
6 * License: $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
7 * Authors: Walter Bright, Martin Nowak
8 */
9 module core.internal.qsort;
10
11 //debug=qsort;
12
13 import core.stdc.stdlib;
14
15 version (OSX)
16 version = Darwin;
17 else version (iOS)
18 version = Darwin;
19 else version (TVOS)
20 version = Darwin;
21 else version (WatchOS)
22 version = Darwin;
23
24 // qsort_r was added in glibc in 2.8. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88127
version(CRuntime_Glibc)25 version (CRuntime_Glibc)
26 {
27 version (GNU)
28 {
29 import gcc.config : Have_Qsort_R;
30 enum Glibc_Qsort_R = Have_Qsort_R;
31 }
32 else
33 {
34 enum Glibc_Qsort_R = true;
35 }
36 }
37 else
38 {
39 enum Glibc_Qsort_R = false;
40 }
41
42 static if (Glibc_Qsort_R)
43 {
44 alias extern (C) int function(scope const void *, scope const void *, scope void *) Cmp;
45 extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, Cmp cmp, scope void *arg);
46
_adSort(return scope void[]a,TypeInfo ti)47 extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
48 {
49 extern (C) int cmp(scope const void* p1, scope const void* p2, scope void* ti)
50 {
51 return (cast(TypeInfo)ti).compare(p1, p2);
52 }
53 qsort_r(a.ptr, a.length, ti.tsize, &cmp, cast(void*)ti);
54 return a;
55 }
56 }
version(FreeBSD)57 else version (FreeBSD)
58 {
59 alias extern (C) int function(scope void *, scope const void *, scope const void *) Cmp;
60 extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, scope void *thunk, Cmp cmp);
61
62 extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
63 {
64 extern (C) int cmp(scope void* ti, scope const void* p1, scope const void* p2)
65 {
66 return (cast(TypeInfo)ti).compare(p1, p2);
67 }
68 qsort_r(a.ptr, a.length, ti.tsize, cast(void*)ti, &cmp);
69 return a;
70 }
71 }
version(DragonFlyBSD)72 else version (DragonFlyBSD)
73 {
74 alias extern (C) int function(scope void *, scope const void *, scope const void *) Cmp;
75 extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, scope void *thunk, Cmp cmp);
76
77 extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
78 {
79 extern (C) int cmp(scope void* ti, scope const void* p1, scope const void* p2)
80 {
81 return (cast(TypeInfo)ti).compare(p1, p2);
82 }
83 qsort_r(a.ptr, a.length, ti.tsize, cast(void*)ti, &cmp);
84 return a;
85 }
86 }
version(Darwin)87 else version (Darwin)
88 {
89 alias extern (C) int function(scope void *, scope const void *, scope const void *) Cmp;
90 extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, scope void *thunk, Cmp cmp);
91
92 extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
93 {
94 extern (C) int cmp(scope void* ti, scope const void* p1, scope const void* p2)
95 {
96 return (cast(TypeInfo)ti).compare(p1, p2);
97 }
98 qsort_r(a.ptr, a.length, ti.tsize, cast(void*)ti, &cmp);
99 return a;
100 }
101 }
version(CRuntime_UClibc)102 else version (CRuntime_UClibc)
103 {
104 alias extern (C) int function(scope const void *, scope const void *, scope void *) __compar_d_fn_t;
105 extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, __compar_d_fn_t cmp, scope void *arg);
106
107 extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
108 {
109 extern (C) int cmp(scope const void* p1, scope const void* p2, scope void* ti)
110 {
111 return (cast(TypeInfo)ti).compare(p1, p2);
112 }
113 qsort_r(a.ptr, a.length, ti.tsize, &cmp, cast(void*)ti);
114 return a;
115 }
116 }
117 else
118 {
119 private TypeInfo tiglobal;
120
_adSort(return scope void[]a,TypeInfo ti)121 extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
122 {
123 extern (C) int cmp(scope const void* p1, scope const void* p2)
124 {
125 return tiglobal.compare(p1, p2);
126 }
127 tiglobal = ti;
128 qsort(a.ptr, a.length, ti.tsize, &cmp);
129 return a;
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 _adSort(*cast(void[]*)&a, typeid(a[0]));
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 }
159
160 unittest
161 {
162 debug(qsort) printf("struct.sort.unittest()\n");
163
164 static struct TestStruct
165 {
166 int value;
167
opCmpTestStruct168 int opCmp(const TestStruct rhs) const
169 {
170 return value <= rhs.value ?
171 value < rhs.value ? -1 : 0 : 1;
172 }
173 }
174
175 TestStruct[] a = new TestStruct[10];
176
177 a[0] = TestStruct(23);
178 a[1] = TestStruct(1);
179 a[2] = TestStruct(64);
180 a[3] = TestStruct(5);
181 a[4] = TestStruct(6);
182 a[5] = TestStruct(5);
183 a[6] = TestStruct(17);
184 a[7] = TestStruct(3);
185 a[8] = TestStruct(0);
186 a[9] = TestStruct(-1);
187
188 _adSort(*cast(void[]*)&a, typeid(TestStruct));
189
190 for (int i = 0; i < a.length - 1; i++)
191 {
192 //printf("i = %d", i);
193 //printf(" %d %d\n", a[i], a[i + 1]);
194 assert(a[i] <= a[i + 1]);
195 }
196 }
197