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
version(CRuntime_Glibc)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
_adSort(return scope void[]a,TypeInfo ti)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 }
version(FreeBSD)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 }
version(DragonFlyBSD)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 }
version(Darwin)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 }
version(CRuntime_UClibc)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
_adSort(return scope void[]a,TypeInfo ti)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 }
167