1 /**
2 * Implementation of dynamic array property support routines.
3 *
4 * Copyright: Copyright Digital Mars 2000 - 2015.
5 * License: Distributed under the
6 * $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
7 * (See accompanying file LICENSE)
8 * Authors: Walter Bright
9 * Source: $(DRUNTIMESRC src/rt/_adi.d)
10 */
11
12 module rt.adi;
13
14 //debug=adi; // uncomment to turn on debugging printf's
15
16 private
17 {
18 debug(adi) import core.stdc.stdio;
19 import core.stdc.string;
20 import core.stdc.stdlib;
21 import core.memory;
22 import rt.util.utf;
23
24 extern (C) void[] _adSort(void[] a, TypeInfo ti);
25 }
26
mallocUTF32(C)27 private dchar[] mallocUTF32(C)(in C[] s)
28 {
29 size_t j = 0;
30 auto p = cast(dchar*)malloc(dchar.sizeof * s.length);
31 auto r = p[0..s.length]; // r[] will never be longer than s[]
32 foreach (dchar c; s)
33 r[j++] = c;
34 return r[0 .. j];
35 }
36
37 /**********************************************
38 * Sort array of chars.
39 */
40
_adSortChar(char[]a)41 extern (C) char[] _adSortChar(char[] a)
42 {
43 if (a.length > 1)
44 {
45 auto da = mallocUTF32(a);
46 _adSort(*cast(void[]*)&da, typeid(da[0]));
47 size_t i = 0;
48 foreach (dchar d; da)
49 { char[4] buf;
50 auto t = toUTF8(buf, d);
51 a[i .. i + t.length] = t[];
52 i += t.length;
53 }
54 free(da.ptr);
55 }
56 return a;
57 }
58
59 /**********************************************
60 * Sort array of wchars.
61 */
62
_adSortWchar(wchar[]a)63 extern (C) wchar[] _adSortWchar(wchar[] a)
64 {
65 if (a.length > 1)
66 {
67 auto da = mallocUTF32(a);
68 _adSort(*cast(void[]*)&da, typeid(da[0]));
69 size_t i = 0;
70 foreach (dchar d; da)
71 { wchar[2] buf;
72 auto t = toUTF16(buf, d);
73 a[i .. i + t.length] = t[];
74 i += t.length;
75 }
76 free(da.ptr);
77 }
78 return a;
79 }
80
81 /***************************************
82 * Support for array equality test.
83 * Returns:
84 * 1 equal
85 * 0 not equal
86 */
87
_adEq(void[]a1,void[]a2,TypeInfo ti)88 extern (C) int _adEq(void[] a1, void[] a2, TypeInfo ti)
89 {
90 debug(adi) printf("_adEq(a1.length = %d, a2.length = %d)\n", a1.length, a2.length);
91 if (a1.length != a2.length)
92 return 0; // not equal
93 auto sz = ti.tsize;
94 auto p1 = a1.ptr;
95 auto p2 = a2.ptr;
96
97 if (sz == 1)
98 // We should really have a ti.isPOD() check for this
99 return (memcmp(p1, p2, a1.length) == 0);
100
101 for (size_t i = 0; i < a1.length; i++)
102 {
103 if (!ti.equals(p1 + i * sz, p2 + i * sz))
104 return 0; // not equal
105 }
106 return 1; // equal
107 }
108
_adEq2(void[]a1,void[]a2,TypeInfo ti)109 extern (C) int _adEq2(void[] a1, void[] a2, TypeInfo ti)
110 {
111 debug(adi) printf("_adEq2(a1.length = %d, a2.length = %d)\n", a1.length, a2.length);
112 if (a1.length != a2.length)
113 return 0; // not equal
114 if (!ti.equals(&a1, &a2))
115 return 0;
116 return 1;
117 }
118 unittest
119 {
120 debug(adi) printf("array.Eq unittest\n");
121
122 auto a = "hello"c;
123
124 assert(a != "hel");
125 assert(a != "helloo");
126 assert(a != "betty");
127 assert(a == "hello");
128 assert(a != "hxxxx");
129
130 float[] fa = [float.nan];
131 assert(fa != fa);
132 }
133
134 /***************************************
135 * Support for array compare test.
136 */
137
_adCmp(void[]a1,void[]a2,TypeInfo ti)138 extern (C) int _adCmp(void[] a1, void[] a2, TypeInfo ti)
139 {
140 debug(adi) printf("adCmp()\n");
141 auto len = a1.length;
142 if (a2.length < len)
143 len = a2.length;
144 auto sz = ti.tsize;
145 void *p1 = a1.ptr;
146 void *p2 = a2.ptr;
147
148 if (sz == 1)
149 { // We should really have a ti.isPOD() check for this
150 auto c = memcmp(p1, p2, len);
151 if (c)
152 return c;
153 }
154 else
155 {
156 for (size_t i = 0; i < len; i++)
157 {
158 auto c = ti.compare(p1 + i * sz, p2 + i * sz);
159 if (c)
160 return c;
161 }
162 }
163 if (a1.length == a2.length)
164 return 0;
165 return (a1.length > a2.length) ? 1 : -1;
166 }
167
_adCmp2(void[]a1,void[]a2,TypeInfo ti)168 extern (C) int _adCmp2(void[] a1, void[] a2, TypeInfo ti)
169 {
170 debug(adi) printf("_adCmp2(a1.length = %d, a2.length = %d)\n", a1.length, a2.length);
171 return ti.compare(&a1, &a2);
172 }
173 unittest
174 {
175 debug(adi) printf("array.Cmp unittest\n");
176
177 auto a = "hello"c;
178
179 assert(a > "hel");
180 assert(a >= "hel");
181 assert(a < "helloo");
182 assert(a <= "helloo");
183 assert(a > "betty");
184 assert(a >= "betty");
185 assert(a == "hello");
186 assert(a <= "hello");
187 assert(a >= "hello");
188 assert(a < "я");
189 }
190
191 /***************************************
192 * Support for array compare test.
193 */
194
_adCmpChar(void[]a1,void[]a2)195 extern (C) int _adCmpChar(void[] a1, void[] a2)
196 {
197 version (D_InlineAsm_X86)
198 {
199 asm
200 { naked ;
201
202 push EDI ;
203 push ESI ;
204
205 mov ESI,a1+4[4+ESP] ;
206 mov EDI,a2+4[4+ESP] ;
207
208 mov ECX,a1[4+ESP] ;
209 mov EDX,a2[4+ESP] ;
210
211 cmp ECX,EDX ;
212 jb GotLength ;
213
214 mov ECX,EDX ;
215
216 GotLength:
217 cmp ECX,4 ;
218 jb DoBytes ;
219
220 // Do alignment if neither is dword aligned
221 test ESI,3 ;
222 jz Aligned ;
223
224 test EDI,3 ;
225 jz Aligned ;
226 DoAlign:
227 mov AL,[ESI] ; //align ESI to dword bounds
228 mov DL,[EDI] ;
229
230 cmp AL,DL ;
231 jnz Unequal ;
232
233 inc ESI ;
234 inc EDI ;
235
236 test ESI,3 ;
237
238 lea ECX,[ECX-1] ;
239 jnz DoAlign ;
240 Aligned:
241 mov EAX,ECX ;
242
243 // do multiple of 4 bytes at a time
244
245 shr ECX,2 ;
246 jz TryOdd ;
247
248 repe ;
249 cmpsd ;
250
251 jnz UnequalQuad ;
252
253 TryOdd:
254 mov ECX,EAX ;
255 DoBytes:
256 // if still equal and not end of string, do up to 3 bytes slightly
257 // slower.
258
259 and ECX,3 ;
260 jz Equal ;
261
262 repe ;
263 cmpsb ;
264
265 jnz Unequal ;
266 Equal:
267 mov EAX,a1[4+ESP] ;
268 mov EDX,a2[4+ESP] ;
269
270 sub EAX,EDX ;
271 pop ESI ;
272
273 pop EDI ;
274 ret ;
275
276 UnequalQuad:
277 mov EDX,[EDI-4] ;
278 mov EAX,[ESI-4] ;
279
280 cmp AL,DL ;
281 jnz Unequal ;
282
283 cmp AH,DH ;
284 jnz Unequal ;
285
286 shr EAX,16 ;
287
288 shr EDX,16 ;
289
290 cmp AL,DL ;
291 jnz Unequal ;
292
293 cmp AH,DH ;
294 Unequal:
295 sbb EAX,EAX ;
296 pop ESI ;
297
298 or EAX,1 ;
299 pop EDI ;
300
301 ret ;
302 }
303 }
304 else
305 {
306 debug(adi) printf("adCmpChar()\n");
307 auto len = a1.length;
308 if (a2.length < len)
309 len = a2.length;
310 auto c = memcmp(cast(char *)a1.ptr, cast(char *)a2.ptr, len);
311 if (!c)
312 c = cast(int)a1.length - cast(int)a2.length;
313 return c;
314 }
315 }
316
317 unittest
318 {
319 debug(adi) printf("array.CmpChar unittest\n");
320
321 auto a = "hello"c;
322
323 assert(a > "hel");
324 assert(a >= "hel");
325 assert(a < "helloo");
326 assert(a <= "helloo");
327 assert(a > "betty");
328 assert(a >= "betty");
329 assert(a == "hello");
330 assert(a <= "hello");
331 assert(a >= "hello");
332 }
333