132
|
1 //_ adi.d
|
|
2
|
|
3 /**
|
|
4 * Part of the D programming language runtime library.
|
|
5 * Dynamic array property support routines
|
|
6 */
|
|
7
|
|
8 /*
|
|
9 * Copyright (C) 2000-2006 by Digital Mars, www.digitalmars.com
|
|
10 * Written by Walter Bright
|
|
11 *
|
|
12 * This software is provided 'as-is', without any express or implied
|
|
13 * warranty. In no event will the authors be held liable for any damages
|
|
14 * arising from the use of this software.
|
|
15 *
|
|
16 * Permission is granted to anyone to use this software for any purpose,
|
|
17 * including commercial applications, and to alter it and redistribute it
|
|
18 * freely, in both source and binary form, subject to the following
|
|
19 * restrictions:
|
|
20 *
|
|
21 * o The origin of this software must not be misrepresented; you must not
|
|
22 * claim that you wrote the original software. If you use this software
|
|
23 * in a product, an acknowledgment in the product documentation would be
|
|
24 * appreciated but is not required.
|
|
25 * o Altered source versions must be plainly marked as such, and must not
|
|
26 * be misrepresented as being the original software.
|
|
27 * o This notice may not be removed or altered from any source
|
|
28 * distribution.
|
|
29 */
|
|
30
|
|
31 /*
|
|
32 * Modified by Sean Kelly <sean@f4.ca> for use with Tango.
|
|
33 */
|
|
34
|
|
35
|
|
36 //debug=adi; // uncomment to turn on debugging printf's
|
|
37
|
|
38 private
|
|
39 {
|
|
40 import tango.stdc.string;
|
|
41 import tango.stdc.stdlib;
|
|
42 import util.utf;
|
|
43
|
|
44 enum BlkAttr : uint
|
|
45 {
|
|
46 FINALIZE = 0b0000_0001,
|
|
47 NO_SCAN = 0b0000_0010,
|
|
48 NO_MOVE = 0b0000_0100,
|
|
49 ALL_BITS = 0b1111_1111
|
|
50 }
|
|
51
|
|
52 extern (C) void* gc_malloc( size_t sz, uint ba = 0 );
|
|
53 extern (C) void* gc_calloc( size_t sz, uint ba = 0 );
|
|
54 extern (C) void gc_free( void* p );
|
|
55 }
|
|
56
|
|
57
|
|
58 struct Array
|
|
59 {
|
|
60 size_t length;
|
|
61 void* ptr;
|
|
62 }
|
|
63
|
|
64 /**********************************************
|
|
65 * Reverse array of chars.
|
|
66 * Handled separately because embedded multibyte encodings should not be
|
|
67 * reversed.
|
|
68 */
|
|
69
|
|
70 extern (C) long _adReverseChar(char[] a)
|
|
71 {
|
|
72 if (a.length > 1)
|
|
73 {
|
|
74 char[6] tmp;
|
|
75 char[6] tmplo;
|
|
76 char* lo = a.ptr;
|
|
77 char* hi = &a[length - 1];
|
|
78
|
|
79 while (lo < hi)
|
|
80 { auto clo = *lo;
|
|
81 auto chi = *hi;
|
|
82
|
|
83 debug(adi) printf("lo = %d, hi = %d\n", lo, hi);
|
|
84 if (clo <= 0x7F && chi <= 0x7F)
|
|
85 {
|
|
86 debug(adi) printf("\tascii\n");
|
|
87 *lo = chi;
|
|
88 *hi = clo;
|
|
89 lo++;
|
|
90 hi--;
|
|
91 continue;
|
|
92 }
|
|
93
|
|
94 uint stridelo = UTF8stride[clo];
|
|
95
|
|
96 uint stridehi = 1;
|
|
97 while ((chi & 0xC0) == 0x80)
|
|
98 {
|
|
99 chi = *--hi;
|
|
100 stridehi++;
|
|
101 assert(hi >= lo);
|
|
102 }
|
|
103 if (lo == hi)
|
|
104 break;
|
|
105
|
|
106 debug(adi) printf("\tstridelo = %d, stridehi = %d\n", stridelo, stridehi);
|
|
107 if (stridelo == stridehi)
|
|
108 {
|
|
109
|
|
110 memcpy(tmp.ptr, lo, stridelo);
|
|
111 memcpy(lo, hi, stridelo);
|
|
112 memcpy(hi, tmp.ptr, stridelo);
|
|
113 lo += stridelo;
|
|
114 hi--;
|
|
115 continue;
|
|
116 }
|
|
117
|
|
118 /* Shift the whole array. This is woefully inefficient
|
|
119 */
|
|
120 memcpy(tmp.ptr, hi, stridehi);
|
|
121 memcpy(tmplo.ptr, lo, stridelo);
|
|
122 memmove(lo + stridehi, lo + stridelo , cast(size_t)(hi - lo) - stridelo);
|
|
123 memcpy(lo, tmp.ptr, stridehi);
|
|
124 memcpy(hi + stridehi - stridelo, tmplo.ptr, stridelo);
|
|
125
|
|
126 lo += stridehi;
|
|
127 hi = hi - 1 + (stridehi - stridelo);
|
|
128 }
|
|
129 }
|
|
130 return *cast(long*)(&a);
|
|
131 }
|
|
132
|
|
133 unittest
|
|
134 {
|
|
135 auto a = "abcd"c;
|
|
136
|
|
137 auto r = a.dup.reverse;
|
|
138 //writefln(r);
|
|
139 assert(r == "dcba");
|
|
140
|
|
141 a = "a\u1235\u1234c";
|
|
142 //writefln(a);
|
|
143 r = a.dup.reverse;
|
|
144 //writefln(r);
|
|
145 assert(r == "c\u1234\u1235a");
|
|
146
|
|
147 a = "ab\u1234c";
|
|
148 //writefln(a);
|
|
149 r = a.dup.reverse;
|
|
150 //writefln(r);
|
|
151 assert(r == "c\u1234ba");
|
|
152
|
|
153 a = "\u3026\u2021\u3061\n";
|
|
154 r = a.dup.reverse;
|
|
155 assert(r == "\n\u3061\u2021\u3026");
|
|
156 }
|
|
157
|
|
158
|
|
159 /**********************************************
|
|
160 * Reverse array of wchars.
|
|
161 * Handled separately because embedded multiword encodings should not be
|
|
162 * reversed.
|
|
163 */
|
|
164
|
|
165 extern (C) long _adReverseWchar(wchar[] a)
|
|
166 {
|
|
167 if (a.length > 1)
|
|
168 {
|
|
169 wchar[2] tmp;
|
|
170 wchar* lo = a.ptr;
|
|
171 wchar* hi = &a[length - 1];
|
|
172
|
|
173 while (lo < hi)
|
|
174 { auto clo = *lo;
|
|
175 auto chi = *hi;
|
|
176
|
|
177 if ((clo < 0xD800 || clo > 0xDFFF) &&
|
|
178 (chi < 0xD800 || chi > 0xDFFF))
|
|
179 {
|
|
180 *lo = chi;
|
|
181 *hi = clo;
|
|
182 lo++;
|
|
183 hi--;
|
|
184 continue;
|
|
185 }
|
|
186
|
|
187 int stridelo = 1 + (clo >= 0xD800 && clo <= 0xDBFF);
|
|
188
|
|
189 int stridehi = 1;
|
|
190 if (chi >= 0xDC00 && chi <= 0xDFFF)
|
|
191 {
|
|
192 chi = *--hi;
|
|
193 stridehi++;
|
|
194 assert(hi >= lo);
|
|
195 }
|
|
196 if (lo == hi)
|
|
197 break;
|
|
198
|
|
199 if (stridelo == stridehi)
|
|
200 { int stmp;
|
|
201
|
|
202 assert(stridelo == 2);
|
|
203 assert(stmp.sizeof == 2 * (*lo).sizeof);
|
|
204 stmp = *cast(int*)lo;
|
|
205 *cast(int*)lo = *cast(int*)hi;
|
|
206 *cast(int*)hi = stmp;
|
|
207 lo += stridelo;
|
|
208 hi--;
|
|
209 continue;
|
|
210 }
|
|
211
|
|
212 /* Shift the whole array. This is woefully inefficient
|
|
213 */
|
|
214 memcpy(tmp.ptr, hi, stridehi * wchar.sizeof);
|
|
215 memcpy(hi + stridehi - stridelo, lo, stridelo * wchar.sizeof);
|
|
216 memmove(lo + stridehi, lo + stridelo , (hi - (lo + stridelo)) * wchar.sizeof);
|
|
217 memcpy(lo, tmp.ptr, stridehi * wchar.sizeof);
|
|
218
|
|
219 lo += stridehi;
|
|
220 hi = hi - 1 + (stridehi - stridelo);
|
|
221 }
|
|
222 }
|
|
223 return *cast(long*)(&a);
|
|
224 }
|
|
225
|
|
226 unittest
|
|
227 {
|
|
228 wstring a = "abcd";
|
|
229 wstring r;
|
|
230
|
|
231 r = a.dup.reverse;
|
|
232 assert(r == "dcba");
|
|
233
|
|
234 a = "a\U00012356\U00012346c";
|
|
235 r = a.dup.reverse;
|
|
236 assert(r == "c\U00012346\U00012356a");
|
|
237
|
|
238 a = "ab\U00012345c";
|
|
239 r = a.dup.reverse;
|
|
240 assert(r == "c\U00012345ba");
|
|
241 }
|
|
242
|
|
243
|
|
244 /**********************************************
|
|
245 * Support for array.reverse property.
|
|
246 */
|
|
247
|
|
248 extern (C) long _adReverse(Array a, size_t szelem)
|
|
249 out (result)
|
|
250 {
|
|
251 assert(result is *cast(long*)(&a));
|
|
252 }
|
|
253 body
|
|
254 {
|
|
255 if (a.length >= 2)
|
|
256 {
|
|
257 byte* tmp;
|
|
258 byte[16] buffer;
|
|
259
|
|
260 void* lo = a.ptr;
|
|
261 void* hi = a.ptr + (a.length - 1) * szelem;
|
|
262
|
|
263 tmp = buffer.ptr;
|
|
264 if (szelem > 16)
|
|
265 {
|
|
266 //version (Win32)
|
|
267 tmp = cast(byte*) alloca(szelem);
|
|
268 //else
|
|
269 //tmp = gc_malloc(szelem);
|
|
270 }
|
|
271
|
|
272 for (; lo < hi; lo += szelem, hi -= szelem)
|
|
273 {
|
|
274 memcpy(tmp, lo, szelem);
|
|
275 memcpy(lo, hi, szelem);
|
|
276 memcpy(hi, tmp, szelem);
|
|
277 }
|
|
278
|
|
279 version (Win32)
|
|
280 {
|
|
281 }
|
|
282 else
|
|
283 {
|
|
284 //if (szelem > 16)
|
|
285 // BUG: bad code is generate for delete pointer, tries
|
|
286 // to call delclass.
|
|
287 //gc_free(tmp);
|
|
288 }
|
|
289 }
|
|
290 return *cast(long*)(&a);
|
|
291 }
|
|
292
|
|
293 unittest
|
|
294 {
|
|
295 debug(adi) printf("array.reverse.unittest\n");
|
|
296
|
|
297 int[] a = new int[5];
|
|
298 int[] b;
|
|
299 size_t i;
|
|
300
|
|
301 for (i = 0; i < 5; i++)
|
|
302 a[i] = i;
|
|
303 b = a.reverse;
|
|
304 assert(b is a);
|
|
305 for (i = 0; i < 5; i++)
|
|
306 assert(a[i] == 4 - i);
|
|
307
|
|
308 struct X20
|
|
309 { // More than 16 bytes in size
|
|
310 int a;
|
|
311 int b, c, d, e;
|
|
312 }
|
|
313
|
|
314 X20[] c = new X20[5];
|
|
315 X20[] d;
|
|
316
|
|
317 for (i = 0; i < 5; i++)
|
|
318 { c[i].a = i;
|
|
319 c[i].e = 10;
|
|
320 }
|
|
321 d = c.reverse;
|
|
322 assert(d is c);
|
|
323 for (i = 0; i < 5; i++)
|
|
324 {
|
|
325 assert(c[i].a == 4 - i);
|
|
326 assert(c[i].e == 10);
|
|
327 }
|
|
328 }
|
|
329
|
|
330 /**********************************************
|
|
331 * Sort array of chars.
|
|
332 */
|
|
333
|
|
334 extern (C) long _adSortChar(char[] a)
|
|
335 {
|
|
336 if (a.length > 1)
|
|
337 {
|
|
338 dchar[] da = toUTF32(a);
|
|
339 da.sort;
|
|
340 size_t i = 0;
|
|
341 foreach (dchar d; da)
|
|
342 { char[4] buf;
|
|
343 auto t = toUTF8(buf, d);
|
|
344 a[i .. i + t.length] = t[];
|
|
345 i += t.length;
|
|
346 }
|
|
347 delete da;
|
|
348 }
|
|
349 return *cast(long*)(&a);
|
|
350 }
|
|
351
|
|
352 /**********************************************
|
|
353 * Sort array of wchars.
|
|
354 */
|
|
355
|
|
356 extern (C) long _adSortWchar(wchar[] a)
|
|
357 {
|
|
358 if (a.length > 1)
|
|
359 {
|
|
360 dchar[] da = toUTF32(a);
|
|
361 da.sort;
|
|
362 size_t i = 0;
|
|
363 foreach (dchar d; da)
|
|
364 { wchar[2] buf;
|
|
365 auto t = toUTF16(buf, d);
|
|
366 a[i .. i + t.length] = t[];
|
|
367 i += t.length;
|
|
368 }
|
|
369 delete da;
|
|
370 }
|
|
371 return *cast(long*)(&a);
|
|
372 }
|
|
373
|
|
374 /***************************************
|
|
375 * Support for array equality test.
|
|
376 */
|
|
377
|
|
378 extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
|
|
379 {
|
|
380 debug(adi) printf("_adEq(a1.length = %d, a2.length = %d)\n", a1.length, a2.length);
|
|
381 if (a1.length != a2.length)
|
|
382 return 0; // not equal
|
|
383 auto sz = ti.tsize();
|
|
384 auto p1 = a1.ptr;
|
|
385 auto p2 = a2.ptr;
|
|
386
|
|
387 /+
|
|
388 for (int i = 0; i < a1.length; i++)
|
|
389 {
|
|
390 printf("%4x %4x\n", (cast(short*)p1)[i], (cast(short*)p2)[i]);
|
|
391 }
|
|
392 +/
|
|
393
|
|
394 if (sz == 1)
|
|
395 // We should really have a ti.isPOD() check for this
|
|
396 return (memcmp(p1, p2, a1.length) == 0);
|
|
397
|
|
398 for (size_t i = 0; i < a1.length; i++)
|
|
399 {
|
|
400 if (!ti.equals(p1 + i * sz, p2 + i * sz))
|
|
401 return 0; // not equal
|
|
402 }
|
|
403 return 1; // equal
|
|
404 }
|
|
405
|
|
406 unittest
|
|
407 {
|
|
408 debug(adi) printf("array.Eq unittest\n");
|
|
409
|
|
410 auto a = "hello"c;
|
|
411
|
|
412 assert(a != "hel");
|
|
413 assert(a != "helloo");
|
|
414 assert(a != "betty");
|
|
415 assert(a == "hello");
|
|
416 assert(a != "hxxxx");
|
|
417 }
|
|
418
|
|
419 /***************************************
|
|
420 * Support for array compare test.
|
|
421 */
|
|
422
|
|
423 extern (C) int _adCmp(Array a1, Array a2, TypeInfo ti)
|
|
424 {
|
|
425 debug(adi) printf("adCmp()\n");
|
|
426 auto len = a1.length;
|
|
427 if (a2.length < len)
|
|
428 len = a2.length;
|
|
429 auto sz = ti.tsize();
|
|
430 void *p1 = a1.ptr;
|
|
431 void *p2 = a2.ptr;
|
|
432
|
|
433 if (sz == 1)
|
|
434 { // We should really have a ti.isPOD() check for this
|
|
435 auto c = memcmp(p1, p2, len);
|
|
436 if (c)
|
|
437 return c;
|
|
438 }
|
|
439 else
|
|
440 {
|
|
441 for (size_t i = 0; i < len; i++)
|
|
442 {
|
|
443 auto c = ti.compare(p1 + i * sz, p2 + i * sz);
|
|
444 if (c)
|
|
445 return c;
|
|
446 }
|
|
447 }
|
|
448 if (a1.length == a2.length)
|
|
449 return 0;
|
|
450 return (a1.length > a2.length) ? 1 : -1;
|
|
451 }
|
|
452
|
|
453 unittest
|
|
454 {
|
|
455 debug(adi) printf("array.Cmp unittest\n");
|
|
456
|
|
457 auto a = "hello"c;
|
|
458
|
|
459 assert(a > "hel");
|
|
460 assert(a >= "hel");
|
|
461 assert(a < "helloo");
|
|
462 assert(a <= "helloo");
|
|
463 assert(a > "betty");
|
|
464 assert(a >= "betty");
|
|
465 assert(a == "hello");
|
|
466 assert(a <= "hello");
|
|
467 assert(a >= "hello");
|
|
468 }
|
|
469
|
|
470 /***************************************
|
|
471 * Support for array compare test.
|
|
472 */
|
|
473
|
|
474 extern (C) int _adCmpChar(Array a1, Array a2)
|
|
475 {
|
141
|
476 version (D_InlineAsm_X86)
|
132
|
477 {
|
|
478 asm
|
|
479 { naked ;
|
|
480
|
|
481 push EDI ;
|
|
482 push ESI ;
|
|
483
|
|
484 mov ESI,a1+4[4+ESP] ;
|
|
485 mov EDI,a2+4[4+ESP] ;
|
|
486
|
|
487 mov ECX,a1[4+ESP] ;
|
|
488 mov EDX,a2[4+ESP] ;
|
|
489
|
|
490 cmp ECX,EDX ;
|
|
491 jb GotLength ;
|
|
492
|
|
493 mov ECX,EDX ;
|
|
494
|
|
495 GotLength:
|
|
496 cmp ECX,4 ;
|
|
497 jb DoBytes ;
|
|
498
|
|
499 // Do alignment if neither is dword aligned
|
|
500 test ESI,3 ;
|
|
501 jz Aligned ;
|
|
502
|
|
503 test EDI,3 ;
|
|
504 jz Aligned ;
|
|
505 DoAlign:
|
|
506 mov AL,[ESI] ; //align ESI to dword bounds
|
|
507 mov DL,[EDI] ;
|
|
508
|
|
509 cmp AL,DL ;
|
|
510 jnz Unequal ;
|
|
511
|
|
512 inc ESI ;
|
|
513 inc EDI ;
|
|
514
|
|
515 test ESI,3 ;
|
|
516
|
|
517 lea ECX,[ECX-1] ;
|
|
518 jnz DoAlign ;
|
|
519 Aligned:
|
|
520 mov EAX,ECX ;
|
|
521
|
|
522 // do multiple of 4 bytes at a time
|
|
523
|
|
524 shr ECX,2 ;
|
|
525 jz TryOdd ;
|
|
526
|
|
527 repe ;
|
|
528 cmpsd ;
|
|
529
|
|
530 jnz UnequalQuad ;
|
|
531
|
|
532 TryOdd:
|
|
533 mov ECX,EAX ;
|
|
534 DoBytes:
|
|
535 // if still equal and not end of string, do up to 3 bytes slightly
|
|
536 // slower.
|
|
537
|
|
538 and ECX,3 ;
|
|
539 jz Equal ;
|
|
540
|
|
541 repe ;
|
|
542 cmpsb ;
|
|
543
|
|
544 jnz Unequal ;
|
|
545 Equal:
|
|
546 mov EAX,a1[4+ESP] ;
|
|
547 mov EDX,a2[4+ESP] ;
|
|
548
|
|
549 sub EAX,EDX ;
|
|
550 pop ESI ;
|
|
551
|
|
552 pop EDI ;
|
|
553 ret ;
|
|
554
|
|
555 UnequalQuad:
|
|
556 mov EDX,[EDI-4] ;
|
|
557 mov EAX,[ESI-4] ;
|
|
558
|
|
559 cmp AL,DL ;
|
|
560 jnz Unequal ;
|
|
561
|
|
562 cmp AH,DH ;
|
|
563 jnz Unequal ;
|
|
564
|
|
565 shr EAX,16 ;
|
|
566
|
|
567 shr EDX,16 ;
|
|
568
|
|
569 cmp AL,DL ;
|
|
570 jnz Unequal ;
|
|
571
|
|
572 cmp AH,DH ;
|
|
573 Unequal:
|
|
574 sbb EAX,EAX ;
|
|
575 pop ESI ;
|
|
576
|
|
577 or EAX,1 ;
|
|
578 pop EDI ;
|
|
579
|
|
580 ret ;
|
|
581 }
|
|
582 }
|
|
583 else
|
|
584 {
|
|
585 int len;
|
|
586 int c;
|
|
587
|
|
588 debug(adi) printf("adCmpChar()\n");
|
|
589 len = cast(int)a1.length;
|
|
590 if (a2.length < len)
|
|
591 len = cast(int)a2.length;
|
|
592 c = memcmp(cast(char *)a1.ptr, cast(char *)a2.ptr, len);
|
|
593 if (!c)
|
|
594 c = cast(int)a1.length - cast(int)a2.length;
|
|
595 return c;
|
|
596 }
|
|
597 }
|
|
598
|
|
599 unittest
|
|
600 {
|
|
601 debug(adi) printf("array.CmpChar unittest\n");
|
|
602
|
|
603 auto a = "hello"c;
|
|
604
|
|
605 assert(a > "hel");
|
|
606 assert(a >= "hel");
|
|
607 assert(a < "helloo");
|
|
608 assert(a <= "helloo");
|
|
609 assert(a > "betty");
|
|
610 assert(a >= "betty");
|
|
611 assert(a == "hello");
|
|
612 assert(a <= "hello");
|
|
613 assert(a >= "hello");
|
|
614 }
|