|
145
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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 }
|
