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