Mercurial > projects > ldc

comparison druntime/src/compiler/ldc/adi.d @ 1458:e0b2d67cfe7c

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