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