Mercurial > projects > ldc

comparison runtime/internal/adi.d @ 443:44f08170f4ef

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Removed tango from the repository and instead added a runtime dir with the files needed to patch and build tango from svn. Reworked the LLVMDC specific pragmas.
author Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
date Fri, 01 Aug 2008 00:32:06 +0200
parents
children a34078905d01
comparison
equal deleted inserted replaced
442:76078c8ab5b9 443:44f08170f4ef
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) Array _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 Array(a.length, a.ptr);
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) Array _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 Array(a.length, a.ptr);
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) Array _adReverse(Array a, size_t szelem)
249 out (result)
250 {
251 assert(result.ptr is a.ptr);
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 = cast(byte*) 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 Array(a.length, a.ptr);
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) Array _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 Array(a.length, a.ptr);
350 }
351
352 /**********************************************
353 * Sort array of wchars.
354 */
355
356 extern (C) Array _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 Array(a.length, a.ptr);
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
382 if (a1.length != a2.length)
383 return 0; // not equal
384 else if (a1.ptr == a2.ptr)
385 return 1; // equal
386
387 // let typeinfo decide
388 return ti.equals(&a1, &a2);
389 }
390
391 unittest
392 {
393 debug(adi) printf("array.Eq unittest\n");
394
395 auto a = "hello"c;
396
397 assert(a != "hel");
398 assert(a != "helloo");
399 assert(a != "betty");
400 assert(a == "hello");
401 assert(a != "hxxxx");
402 }
403
404 /***************************************
405 * Support for array compare test.
406 */
407
408 extern (C) int _adCmp(Array a1, Array a2, TypeInfo ti)
409 {
410 debug(adi) printf("adCmp()\n");
411
412 if (a1.ptr == a2.ptr &&
413 a1.length == a2.length)
414 return 0;
415
416 auto len = a1.length;
417 if (a2.length < len)
418 len = a2.length;
419
420 // let typeinfo decide
421 return ti.compare(&a1, &a2);
422 }
423
424 unittest
425 {
426 debug(adi) printf("array.Cmp unittest\n");
427
428 auto a = "hello"c;
429
430 assert(a > "hel");
431 assert(a >= "hel");
432 assert(a < "helloo");
433 assert(a <= "helloo");
434 assert(a > "betty");
435 assert(a >= "betty");
436 assert(a == "hello");
437 assert(a <= "hello");
438 assert(a >= "hello");
439 }
440
441 /***************************************
442 * Support for array compare test.
443 */
444
445 extern (C) int _adCmpChar(Array a1, Array a2)
446 {
447 version(D_InlineAsm_X86)
448 {
449 //version = Asm86;
450 }
451 version (Asm86)
452 {
453 asm
454 { naked ;
455
456 push EDI ;
457 push ESI ;
458
459 mov ESI,a1+4[4+ESP] ;
460 mov EDI,a2+4[4+ESP] ;
461
462 mov ECX,a1[4+ESP] ;
463 mov EDX,a2[4+ESP] ;
464
465 cmp ECX,EDX ;
466 jb GotLength ;
467
468 mov ECX,EDX ;
469
470 GotLength:
471 cmp ECX,4 ;
472 jb DoBytes ;
473
474 // Do alignment if neither is dword aligned
475 test ESI,3 ;
476 jz Aligned ;
477
478 test EDI,3 ;
479 jz Aligned ;
480 DoAlign:
481 mov AL,[ESI] ; //align ESI to dword bounds
482 mov DL,[EDI] ;
483
484 cmp AL,DL ;
485 jnz Unequal ;
486
487 inc ESI ;
488 inc EDI ;
489
490 test ESI,3 ;
491
492 lea ECX,[ECX-1] ;
493 jnz DoAlign ;
494 Aligned:
495 mov EAX,ECX ;
496
497 // do multiple of 4 bytes at a time
498
499 shr ECX,2 ;
500 jz TryOdd ;
501
502 repe ;
503 cmpsd ;
504
505 jnz UnequalQuad ;
506
507 TryOdd:
508 mov ECX,EAX ;
509 DoBytes:
510 // if still equal and not end of string, do up to 3 bytes slightly
511 // slower.
512
513 and ECX,3 ;
514 jz Equal ;
515
516 repe ;
517 cmpsb ;
518
519 jnz Unequal ;
520 Equal:
521 mov EAX,a1[4+ESP] ;
522 mov EDX,a2[4+ESP] ;
523
524 sub EAX,EDX ;
525 pop ESI ;
526
527 pop EDI ;
528 ret ;
529
530 UnequalQuad:
531 mov EDX,[EDI-4] ;
532 mov EAX,[ESI-4] ;
533
534 cmp AL,DL ;
535 jnz Unequal ;
536
537 cmp AH,DH ;
538 jnz Unequal ;
539
540 shr EAX,16 ;
541
542 shr EDX,16 ;
543
544 cmp AL,DL ;
545 jnz Unequal ;
546
547 cmp AH,DH ;
548 Unequal:
549 sbb EAX,EAX ;
550 pop ESI ;
551
552 or EAX,1 ;
553 pop EDI ;
554
555 ret ;
556 }
557 }
558 else
559 {
560 int len;
561 int c;
562
563 debug(adi) printf("adCmpChar()\n");
564 len = cast(int)a1.length;
565 if (a2.length < len)
566 len = cast(int)a2.length;
567 c = memcmp(cast(char *)a1.ptr, cast(char *)a2.ptr, len);
568 if (!c)
569 c = cast(int)a1.length - cast(int)a2.length;
570 return c;
571 }
572 }
573
574 unittest
575 {
576 debug(adi) printf("array.CmpChar unittest\n");
577
578 auto a = "hello"c;
579
580 assert(a > "hel");
581 assert(a >= "hel");
582 assert(a < "helloo");
583 assert(a <= "helloo");
584 assert(a > "betty");
585 assert(a >= "betty");
586 assert(a == "hello");
587 assert(a <= "hello");
588 assert(a >= "hello");
589 }