Mercurial > projects > ldc

comparison druntime/src/compiler/ldc/lifetime.d @ 759:d3eb054172f9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added copy of druntime from DMD 2.020 modified for LDC.
author Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
date Tue, 11 Nov 2008 01:52:37 +0100
parents
children
comparison
equal deleted inserted replaced
758:f04dde6e882c 759:d3eb054172f9
1 /**
2 * This module contains all functions related to an object's lifetime:
3 * allocation, resizing, deallocation, and finalization.
4 *
5 * Copyright: Copyright (C) 2004-2007 Digital Mars, www.digitalmars.com.
6 * All rights reserved.
7 * License:
8 * This software is provided 'as-is', without any express or implied
9 * warranty. In no event will the authors be held liable for any damages
10 * arising from the use of this software.
11 *
12 * Permission is granted to anyone to use this software for any purpose,
13 * including commercial applications, and to alter it and redistribute it
14 * freely, in both source and binary form, subject to the following
15 * restrictions:
16 *
17 * o The origin of this software must not be misrepresented; you must not
18 * claim that you wrote the original software. If you use this software
19 * in a product, an acknowledgment in the product documentation would be
20 * appreciated but is not required.
21 * o Altered source versions must be plainly marked as such, and must not
22 * be misrepresented as being the original software.
23 * o This notice may not be removed or altered from any source
24 * distribution.
25 * Authors: Walter Bright, Sean Kelly, Tomas Lindquist Olsen
26 */
27 module lifetime;
28
29 //debug=PRINTF;
30 //debug=PRINTF2;
31
32 private
33 {
34 version( D_Version2 )
35 {
36 import stdc.stdlib;
37 import stdc.string;
38 import stdc.stdarg;
39 debug(PRINTF) import stdc.stdio;
40 else debug(PRINTF2) import stdc.stdio;
41 }
42 else
43 {
44 import tango.stdc.stdlib;
45 import tango.stdc.string;
46 import tango.stdc.stdarg;
47 debug(PRINTF) import tango.stdc.stdio;
48 else debug(PRINTF2) import tango.stdc.stdio;
49 }
50 }
51
52
53 private
54 {
55 enum BlkAttr : uint
56 {
57 FINALIZE = 0b0000_0001,
58 NO_SCAN = 0b0000_0010,
59 NO_MOVE = 0b0000_0100,
60 ALL_BITS = 0b1111_1111
61 }
62
63 struct BlkInfo
64 {
65 void* base;
66 size_t size;
67 uint attr;
68 }
69
70 extern (C) uint gc_getAttr( void* p );
71 extern (C) uint gc_setAttr( void* p, uint a );
72 extern (C) uint gc_clrAttr( void* p, uint a );
73
74 extern (C) void* gc_malloc( size_t sz, uint ba = 0 );
75 extern (C) void* gc_calloc( size_t sz, uint ba = 0 );
76 extern (C) size_t gc_extend( void* p, size_t mx, size_t sz );
77 extern (C) void gc_free( void* p );
78
79 extern (C) void* gc_addrOf( void* p );
80 extern (C) size_t gc_sizeOf( void* p );
81 extern (C) BlkInfo gc_query( void* p );
82
83 extern (C) bool onCollectResource( Object o );
84 extern (C) void onFinalizeError( ClassInfo c, Exception e );
85 extern (C) void onOutOfMemoryError();
86
87 extern (C) void _d_monitordelete(Object h, bool det = true);
88
89 enum
90 {
91 PAGESIZE = 4096
92 }
93
94 alias bool function(Object) CollectHandler;
95 CollectHandler collectHandler = null;
96 }
97
98
99 /**
100 *
101 */
102 extern (C) Object _d_allocclass(ClassInfo ci)
103 {
104 void* p;
105
106 debug(PRINTF2) printf("_d_allocclass(ci = %p, %s)\n", ci, cast(char *)ci.name.ptr);
107 /+
108 if (ci.flags & 1) // if COM object
109 { /* COM objects are not garbage collected, they are reference counted
110 * using AddRef() and Release(). They get free'd by C's free()
111 * function called by Release() when Release()'s reference count goes
112 * to zero.
113 */
114 p = tango.stdc.stdlib.malloc(ci.init.length);
115 if (!p)
116 onOutOfMemoryError();
117 }
118 else
119 +/
120 {
121 p = gc_malloc(ci.init.length,
122 BlkAttr.FINALIZE | (ci.flags & 2 ? BlkAttr.NO_SCAN : 0));
123 debug(PRINTF2) printf(" p = %p\n", p);
124 }
125
126 debug(PRINTF2)
127 {
128 printf("p = %p\n", p);
129 printf("ci = %p, ci.init = %p, len = %d\n", ci, ci.init.ptr, ci.init.length);
130 printf("vptr = %p\n", *cast(void**) ci.init.ptr);
131 printf("vtbl[0] = %p\n", (*cast(void***) ci.init.ptr)[0]);
132 printf("vtbl[1] = %p\n", (*cast(void***) ci.init.ptr)[1]);
133 printf("init[0] = %p\n", (cast(uint**) ci.init.ptr)[0]);
134 printf("init[1] = %p\n", (cast(uint**) ci.init.ptr)[1]);
135 printf("init[2] = %p\n", (cast(uint**) ci.init.ptr)[2]);
136 printf("init[3] = %p\n", (cast(uint**) ci.init.ptr)[3]);
137 printf("init[4] = %p\n", (cast(uint**) ci.init.ptr)[4]);
138 }
139
140 // initialize it
141 // ldc does this inline
142 //(cast(byte*) p)[0 .. ci.init.length] = ci.init[];
143
144 debug(PRINTF) printf("initialization done\n");
145 return cast(Object) p;
146 }
147
148 /**
149 *
150 */
151 extern (C) void _d_delinterface(void* p)
152 {
153 if (p)
154 {
155 Interface* pi = **cast(Interface ***)p;
156 Object o = cast(Object)(p - pi.offset);
157
158 _d_delclass(o);
159 //*p = null;
160 }
161 }
162
163 // used for deletion
164 private extern (D) alias void function(Object) fp_t;
165
166
167 /**
168 *
169 */
170 extern (C) void _d_delclass(Object p)
171 {
172 if (p)
173 {
174 debug(PRINTF) printf("_d_delclass(%p)\n", p);
175
176 ClassInfo **pc = cast(ClassInfo **)p;
177 if (*pc)
178 {
179 ClassInfo c = **pc;
180
181 rt_finalize(cast(void*) p);
182
183 if (c.deallocator)
184 {
185 fp_t fp = cast(fp_t)c.deallocator;
186 (*fp)(p); // call deallocator
187 //*p = null;
188 return;
189 }
190 }
191 else
192 {
193 rt_finalize(cast(void*) p);
194 }
195 gc_free(cast(void*) p);
196 //*p = null;
197 }
198 }
199
200 /+
201
202 /**
203 *
204 */
205 struct Array
206 {
207 size_t length;
208 void* data;
209 }
210
211 +/
212
213 /**
214 * Allocate a new array of length elements.
215 * ti is the type of the resulting array, or pointer to element.
216 * The resulting array is initialized to 0
217 */
218 extern (C) void* _d_newarrayT(TypeInfo ti, size_t length)
219 {
220 void* p;
221 auto size = ti.next.tsize(); // array element size
222
223 debug(PRINTF) printf("_d_newarrayT(length = %u, size = %d)\n", length, size);
224 if (length == 0 || size == 0)
225 return null;
226
227 version (D_InlineAsm_X86)
228 {
229 asm
230 {
231 mov EAX,size ;
232 mul EAX,length ;
233 mov size,EAX ;
234 jc Loverflow ;
235 }
236 }
237 else
238 size *= length;
239 p = gc_malloc(size + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
240 debug(PRINTF) printf(" p = %p\n", p);
241 memset(p, 0, size);
242 return p;
243
244 Loverflow:
245 onOutOfMemoryError();
246 return null;
247 }
248
249 /**
250 * As _d_newarrayT, but
251 * for when the array has a non-zero initializer.
252 */
253 extern (C) void* _d_newarrayiT(TypeInfo ti, size_t length)
254 {
255 void* result;
256 auto size = ti.next.tsize(); // array element size
257
258 debug(PRINTF) printf("_d_newarrayiT(length = %d, size = %d)\n", length, size);
259
260 if (length == 0 || size == 0)
261 result = null;
262 else
263 {
264 auto initializer = ti.next.init();
265 auto isize = initializer.length;
266 auto q = initializer.ptr;
267 version (D_InlineAsm_X86)
268 {
269 asm
270 {
271 mov EAX,size ;
272 mul EAX,length ;
273 mov size,EAX ;
274 jc Loverflow ;
275 }
276 }
277 else
278 size *= length;
279 auto p = gc_malloc(size + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
280 debug(PRINTF) printf(" p = %p\n", p);
281 if (isize == 1)
282 memset(p, *cast(ubyte*)q, size);
283 else if (isize == int.sizeof)
284 {
285 int init = *cast(int*)q;
286 size /= int.sizeof;
287 for (size_t u = 0; u < size; u++)
288 {
289 (cast(int*)p)[u] = init;
290 }
291 }
292 else
293 {
294 for (size_t u = 0; u < size; u += isize)
295 {
296 memcpy(p + u, q, isize);
297 }
298 }
299 result = p;
300 }
301 return result;
302
303 Loverflow:
304 onOutOfMemoryError();
305 return null;
306 }
307
308 /**
309 * As _d_newarrayT, but without initialization
310 */
311 extern (C) void* _d_newarrayvT(TypeInfo ti, size_t length)
312 {
313 void* p;
314 auto size = ti.next.tsize(); // array element size
315
316 debug(PRINTF) printf("_d_newarrayvT(length = %u, size = %d)\n", length, size);
317 if (length == 0 || size == 0)
318 return null;
319
320 version (D_InlineAsm_X86)
321 {
322 asm
323 {
324 mov EAX,size ;
325 mul EAX,length ;
326 mov size,EAX ;
327 jc Loverflow ;
328 }
329 }
330 else
331 size *= length;
332 p = gc_malloc(size + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
333 debug(PRINTF) printf(" p = %p\n", p);
334 return p;
335
336 Loverflow:
337 onOutOfMemoryError();
338 return null;
339 }
340
341 /**
342 * Allocate a new array of arrays of arrays of arrays ...
343 * ti is the type of the resulting array.
344 * ndims is the number of nested arrays.
345 * dims it the array of dimensions, its size is ndims.
346 * The resulting array is initialized to 0
347 */
348 extern (C) void* _d_newarraymT(TypeInfo ti, int ndims, size_t* dims)
349 {
350 void* result;
351
352 debug(PRINTF) printf("_d_newarraymT(ndims = %d)\n", ndims);
353 if (ndims == 0)
354 result = null;
355 else
356 {
357 static void[] foo(TypeInfo ti, size_t* pdim, int ndims)
358 {
359 size_t dim = *pdim;
360 void[] p;
361
362 debug(PRINTF) printf("foo(ti = %p, ti.next = %p, dim = %d, ndims = %d\n", ti, ti.next, dim, ndims);
363 if (ndims == 1)
364 {
365 auto r = _d_newarrayT(ti, dim);
366 return r[0 .. dim];
367 }
368 else
369 {
370 p = gc_malloc(dim * (void[]).sizeof + 1)[0 .. dim];
371 for (int i = 0; i < dim; i++)
372 {
373 (cast(void[]*)p.ptr)[i] = foo(ti.next, pdim + 1, ndims - 1);
374 }
375 }
376 return p;
377 }
378
379 result = foo(ti, dims, ndims).ptr;
380 debug(PRINTF) printf("result = %p\n", result);
381
382 version (none)
383 {
384 for (int i = 0; i < ndims; i++)
385 {
386 printf("index %d: %d\n", i, *dims++);
387 }
388 }
389 }
390 return result;
391 }
392
393
394 /**
395 * As _d_newarraymT, but
396 * for when the array has a non-zero initializer.
397 */
398 extern (C) void* _d_newarraymiT(TypeInfo ti, int ndims, size_t* dims)
399 {
400 void* result;
401
402 debug(PRINTF) printf("_d_newarraymiT(ndims = %d)\n", ndims);
403 if (ndims == 0)
404 result = null;
405 else
406 {
407 static void[] foo(TypeInfo ti, size_t* pdim, int ndims)
408 {
409 size_t dim = *pdim;
410 void[] p;
411
412 if (ndims == 1)
413 {
414 auto r = _d_newarrayiT(ti, dim);
415 p = r[0 .. dim];
416 }
417 else
418 {
419 p = gc_malloc(dim * (void[]).sizeof + 1)[0 .. dim];
420 for (int i = 0; i < dim; i++)
421 {
422 (cast(void[]*)p.ptr)[i] = foo(ti.next, pdim + 1, ndims - 1);
423 }
424 }
425 return p;
426 }
427
428 result = foo(ti, dims, ndims).ptr;
429 debug(PRINTF) printf("result = %p\n", result);
430
431 version (none)
432 {
433 for (int i = 0; i < ndims; i++)
434 {
435 printf("index %d: %d\n", i, *dims++);
436 printf("init = %d\n", *dims++);
437 }
438 }
439 }
440 return result;
441 }
442
443 /**
444 * As _d_newarraymT, but without initialization
445 */
446 extern (C) void* _d_newarraymvT(TypeInfo ti, int ndims, size_t* dims)
447 {
448 void* result;
449
450 debug(PRINTF) printf("_d_newarraymvT(ndims = %d)\n", ndims);
451 if (ndims == 0)
452 result = null;
453 else
454 {
455 static void[] foo(TypeInfo ti, size_t* pdim, int ndims)
456 {
457 size_t dim = *pdim;
458 void[] p;
459
460 debug(PRINTF) printf("foo(ti = %p, ti.next = %p, dim = %d, ndims = %d\n", ti, ti.next, dim, ndims);
461 if (ndims == 1)
462 {
463 auto r = _d_newarrayvT(ti, dim);
464 return r[0 .. dim];
465 }
466 else
467 {
468 p = gc_malloc(dim * (void[]).sizeof + 1)[0 .. dim];
469 for (int i = 0; i < dim; i++)
470 {
471 (cast(void[]*)p.ptr)[i] = foo(ti.next, pdim + 1, ndims - 1);
472 }
473 }
474 return p;
475 }
476
477 result = foo(ti, dims, ndims).ptr;
478 debug(PRINTF) printf("result = %p\n", result);
479
480 version (none)
481 {
482 for (int i = 0; i < ndims; i++)
483 {
484 printf("index %d: %d\n", i, *dims++);
485 }
486 }
487 }
488 return result;
489 }
490
491 /+
492
493 /**
494 *
495 */
496 void* _d_allocmemory(size_t nbytes)
497 {
498 return gc_malloc(nbytes);
499 }
500
501 +/
502
503 /**
504 * for allocating a single POD value
505 */
506 extern (C) void* _d_allocmemoryT(TypeInfo ti)
507 {
508 return gc_malloc(ti.tsize(), !(ti.flags() & 1) ? BlkAttr.NO_SCAN : 0);
509 }
510
511 /**
512 *
513 */
514 extern (C) void _d_delarray(size_t plength, void* pdata)
515 {
516 // if (p)
517 // {
518 assert(!plength || pdata);
519
520 if (pdata)
521 gc_free(pdata);
522 // p.data = null;
523 // p.length = 0;
524 // }
525 }
526
527 /**
528 *
529 */
530 extern (C) void _d_delmemory(void* p)
531 {
532 if (p)
533 {
534 gc_free(p);
535 //*p = null;
536 }
537 }
538
539 /**
540 *
541 */
542 extern (C) void _d_callinterfacefinalizer(void *p)
543 {
544 if (p)
545 {
546 Interface *pi = **cast(Interface ***)p;
547 Object o = cast(Object)(p - pi.offset);
548 rt_finalize(cast(void*)o);
549 }
550 }
551
552 /**
553 *
554 */
555 extern (C) void _d_callfinalizer(void* p)
556 {
557 rt_finalize( p );
558 }
559
560
561 /**
562 *
563 */
564 extern (C) void rt_setCollectHandler(CollectHandler h)
565 {
566 collectHandler = h;
567 }
568
569 /**
570 *
571 */
572 extern (C) void rt_finalize(void* p, bool det = true)
573 {
574 debug(PRINTF) printf("rt_finalize(p = %p)\n", p);
575
576 if (p) // not necessary if called from gc
577 {
578 ClassInfo** pc = cast(ClassInfo**)p;
579
580 if (*pc)
581 {
582 ClassInfo c = **pc;
583
584 try
585 {
586 if (det || collectHandler is null || collectHandler(cast(Object)p))
587 {
588 do
589 {
590 if (c.destructor)
591 {
592 debug(PRINTF) printf("calling dtor of %.*s\n", c.name.length, c.name.ptr);
593 fp_t fp = cast(fp_t)c.destructor;
594 (*fp)(cast(Object)p); // call destructor
595 }
596 c = c.base;
597 } while (c);
598 }
599 if ((cast(void**)p)[1]) // if monitor is not null
600 _d_monitordelete(cast(Object)p, det);
601 }
602 catch (Exception e)
603 {
604 onFinalizeError(**pc, e);
605 }
606 finally
607 {
608 *pc = null; // zero vptr
609 }
610 }
611 }
612 }
613
614 /**
615 * Resize dynamic arrays with 0 initializers.
616 */
617 extern (C) byte* _d_arraysetlengthT(TypeInfo ti, size_t newlength, size_t plength, byte* pdata)
618 in
619 {
620 assert(ti);
621 assert(!plength || pdata);
622 }
623 body
624 {
625 byte* newdata;
626 size_t sizeelem = ti.next.tsize();
627
628 debug(PRINTF)
629 {
630 printf("_d_arraysetlengthT(sizeelem = %d, newlength = %d)\n", sizeelem, newlength);
631 printf("\tp.data = %p, p.length = %d\n", pdata, plength);
632 }
633
634 if (newlength)
635 {
636 version (D_InlineAsm_X86)
637 {
638 size_t newsize = void;
639
640 asm
641 {
642 mov EAX, newlength;
643 mul EAX, sizeelem;
644 mov newsize, EAX;
645 jc Loverflow;
646 }
647 }
648 else
649 {
650 size_t newsize = sizeelem * newlength;
651
652 if (newsize / newlength != sizeelem)
653 goto Loverflow;
654 }
655
656 debug(PRINTF) printf("newsize = %x, newlength = %x\n", newsize, newlength);
657
658 if (pdata)
659 {
660 newdata = pdata;
661 if (newlength > plength)
662 {
663 size_t size = plength * sizeelem;
664 auto info = gc_query(pdata);
665
666 if (info.size <= newsize || info.base != pdata)
667 {
668 if (info.size >= PAGESIZE && info.base == pdata)
669 { // Try to extend in-place
670 auto u = gc_extend(pdata, (newsize + 1) - info.size, (newsize + 1) - info.size);
671 if (u)
672 {
673 goto L1;
674 }
675 }
676 newdata = cast(byte *)gc_malloc(newsize + 1, info.attr);
677 newdata[0 .. size] = pdata[0 .. size];
678 }
679 L1:
680 newdata[size .. newsize] = 0;
681 }
682 }
683 else
684 {
685 newdata = cast(byte *)gc_calloc(newsize + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
686 }
687 }
688 else
689 {
690 newdata = pdata;
691 }
692
693 return newdata;
694
695 Loverflow:
696 onOutOfMemoryError();
697 return null;
698 }
699
700
701 /**
702 * Resize arrays for non-zero initializers.
703 * p pointer to array lvalue to be updated
704 * newlength new .length property of array
705 * sizeelem size of each element of array
706 * initsize size of initializer
707 * ... initializer
708 */
709 extern (C) byte* _d_arraysetlengthiT(TypeInfo ti, size_t newlength, size_t plength, byte* pdata)
710 in
711 {
712 assert(!plength || pdata);
713 }
714 body
715 {
716 byte* newdata;
717 TypeInfo tinext = ti.next;
718 size_t sizeelem = tinext.tsize();
719 void[] initializer = tinext.init();
720 size_t initsize = initializer.length;
721
722 assert(sizeelem);
723 assert(initsize);
724 assert(initsize <= sizeelem);
725 assert((sizeelem / initsize) * initsize == sizeelem);
726
727 debug(PRINTF)
728 {
729 printf("_d_arraysetlengthiT(sizeelem = %d, newlength = %d, initsize = %d)\n", sizeelem, newlength, initsize);
730 printf("\tp.data = %p, p.length = %d\n", pdata, plength);
731 }
732
733 if (newlength)
734 {
735 version (D_InlineAsm_X86)
736 {
737 size_t newsize = void;
738
739 asm
740 {
741 mov EAX,newlength ;
742 mul EAX,sizeelem ;
743 mov newsize,EAX ;
744 jc Loverflow ;
745 }
746 }
747 else
748 {
749 size_t newsize = sizeelem * newlength;
750
751 if (newsize / newlength != sizeelem)
752 goto Loverflow;
753 }
754 debug(PRINTF) printf("newsize = %x, newlength = %x\n", newsize, newlength);
755
756 size_t size = plength * sizeelem;
757
758 if (pdata)
759 {
760 newdata = pdata;
761 if (newlength > plength)
762 {
763 auto info = gc_query(pdata);
764
765 if (info.size <= newsize || info.base != pdata)
766 {
767 if (info.size >= PAGESIZE && info.base == pdata)
768 { // Try to extend in-place
769 auto u = gc_extend(pdata, (newsize + 1) - info.size, (newsize + 1) - info.size);
770 if (u)
771 {
772 goto L1;
773 }
774 }
775 newdata = cast(byte *)gc_malloc(newsize + 1, info.attr);
776 newdata[0 .. size] = pdata[0 .. size];
777 L1: ;
778 }
779 }
780 }
781 else
782 {
783 newdata = cast(byte *)gc_malloc(newsize + 1, !(tinext.flags() & 1) ? BlkAttr.NO_SCAN : 0);
784 }
785
786 auto q = initializer.ptr; // pointer to initializer
787
788 if (newsize > size)
789 {
790 if (initsize == 1)
791 {
792 debug(PRINTF) printf("newdata = %p, size = %d, newsize = %d, *q = %d\n", newdata, size, newsize, *cast(byte*)q);
793 newdata[size .. newsize] = *(cast(byte*)q);
794 }
795 else
796 {
797 for (size_t u = size; u < newsize; u += initsize)
798 {
799 memcpy(newdata + u, q, initsize);
800 }
801 }
802 }
803 }
804 else
805 {
806 newdata = pdata;
807 }
808
809 return newdata;
810
811 Loverflow:
812 onOutOfMemoryError();
813 return null;
814 }
815
816 /+
817
818 /**
819 * Append y[] to array x[].
820 * size is size of each array element.
821 */
822 extern (C) long _d_arrayappendT(TypeInfo ti, Array *px, byte[] y)
823 {
824 auto sizeelem = ti.next.tsize(); // array element size
825 auto info = gc_query(px.data);
826 auto length = px.length;
827 auto newlength = length + y.length;
828 auto newsize = newlength * sizeelem;
829
830 if (info.size < newsize || info.base != px.data)
831 { byte* newdata;
832
833 if (info.size >= PAGESIZE && info.base == px.data)
834 { // Try to extend in-place
835 auto u = gc_extend(px.data, (newsize + 1) - info.size, (newsize + 1) - info.size);
836 if (u)
837 {
838 goto L1;
839 }
840 }
841 newdata = cast(byte *)gc_malloc(newCapacity(newlength, sizeelem) + 1, info.attr);
842 memcpy(newdata, px.data, length * sizeelem);
843 px.data = newdata;
844 }
845 L1:
846 px.length = newlength;
847 memcpy(px.data + length * sizeelem, y.ptr, y.length * sizeelem);
848 return *cast(long*)px;
849 }
850
851
852 /**
853 *
854 */
855 size_t newCapacity(size_t newlength, size_t size)
856 {
857 version(none)
858 {
859 size_t newcap = newlength * size;
860 }
861 else
862 {
863 /*
864 * Better version by Dave Fladebo:
865 * This uses an inverse logorithmic algorithm to pre-allocate a bit more
866 * space for larger arrays.
867 * - Arrays smaller than PAGESIZE bytes are left as-is, so for the most
868 * common cases, memory allocation is 1 to 1. The small overhead added
869 * doesn't affect small array perf. (it's virtually the same as
870 * current).
871 * - Larger arrays have some space pre-allocated.
872 * - As the arrays grow, the relative pre-allocated space shrinks.
873 * - The logorithmic algorithm allocates relatively more space for
874 * mid-size arrays, making it very fast for medium arrays (for
875 * mid-to-large arrays, this turns out to be quite a bit faster than the
876 * equivalent realloc() code in C, on Linux at least. Small arrays are
877 * just as fast as GCC).
878 * - Perhaps most importantly, overall memory usage and stress on the GC
879 * is decreased significantly for demanding environments.
880 */
881 size_t newcap = newlength * size;
882 size_t newext = 0;
883
884 if (newcap > PAGESIZE)
885 {
886 //double mult2 = 1.0 + (size / log10(pow(newcap * 2.0,2.0)));
887
888 // redo above line using only integer math
889
890 static int log2plus1(size_t c)
891 { int i;
892
893 if (c == 0)
894 i = -1;
895 else
896 for (i = 1; c >>= 1; i++)
897 {
898 }
899 return i;
900 }
901
902 /* The following setting for mult sets how much bigger
903 * the new size will be over what is actually needed.
904 * 100 means the same size, more means proportionally more.
905 * More means faster but more memory consumption.
906 */
907 //long mult = 100 + (1000L * size) / (6 * log2plus1(newcap));
908 long mult = 100 + (1000L * size) / log2plus1(newcap);
909
910 // testing shows 1.02 for large arrays is about the point of diminishing return
911 if (mult < 102)
912 mult = 102;
913 newext = cast(size_t)((newcap * mult) / 100);
914 newext -= newext % size;
915 debug(PRINTF) printf("mult: %2.2f, alloc: %2.2f\n",mult/100.0,newext / cast(double)size);
916 }
917 newcap = newext > newcap ? newext : newcap;
918 debug(PRINTF) printf("newcap = %d, newlength = %d, size = %d\n", newcap, newlength, size);
919 }
920 return newcap;
921 }
922
923
924 /**
925 *
926 */
927 extern (C) byte[] _d_arrayappendcT(TypeInfo ti, inout byte[] x, ...)
928 {
929 auto sizeelem = ti.next.tsize(); // array element size
930 auto info = gc_query(x.ptr);
931 auto length = x.length;
932 auto newlength = length + 1;
933 auto newsize = newlength * sizeelem;
934
935 assert(info.size == 0 || length * sizeelem <= info.size);
936
937 debug(PRINTF) printf("_d_arrayappendcT(sizeelem = %d, ptr = %p, length = %d, cap = %d)\n", sizeelem, x.ptr, x.length, info.size);
938
939 if (info.size <= newsize || info.base != x.ptr)
940 { byte* newdata;
941
942 if (info.size >= PAGESIZE && info.base == x.ptr)
943 { // Try to extend in-place
944 auto u = gc_extend(x.ptr, (newsize + 1) - info.size, (newsize + 1) - info.size);
945 if (u)
946 {
947 goto L1;
948 }
949 }
950 debug(PRINTF) printf("_d_arrayappendcT(length = %d, newlength = %d, cap = %d)\n", length, newlength, info.size);
951 auto newcap = newCapacity(newlength, sizeelem);
952 assert(newcap >= newlength * sizeelem);
953 newdata = cast(byte *)gc_malloc(newcap + 1, info.attr);
954 memcpy(newdata, x.ptr, length * sizeelem);
955 (cast(void**)(&x))[1] = newdata;
956 }
957 L1:
958 byte *argp = cast(byte *)(&ti + 2);
959
960 *cast(size_t *)&x = newlength;
961 x.ptr[length * sizeelem .. newsize] = argp[0 .. sizeelem];
962 assert((cast(size_t)x.ptr & 15) == 0);
963 assert(gc_sizeOf(x.ptr) > x.length * sizeelem);
964 return x;
965 }
966
967
968 /**
969 *
970 */
971 extern (C) byte[] _d_arraycatT(TypeInfo ti, byte[] x, byte[] y)
972 out (result)
973 {
974 auto sizeelem = ti.next.tsize(); // array element size
975 debug(PRINTF) printf("_d_arraycatT(%d,%p ~ %d,%p sizeelem = %d => %d,%p)\n", x.length, x.ptr, y.length, y.ptr, sizeelem, result.length, result.ptr);
976 assert(result.length == x.length + y.length);
977 for (size_t i = 0; i < x.length * sizeelem; i++)
978 assert((cast(byte*)result)[i] == (cast(byte*)x)[i]);
979 for (size_t i = 0; i < y.length * sizeelem; i++)
980 assert((cast(byte*)result)[x.length * sizeelem + i] == (cast(byte*)y)[i]);
981
982 size_t cap = gc_sizeOf(result.ptr);
983 assert(!cap || cap > result.length * sizeelem);
984 }
985 body
986 {
987 version (none)
988 {
989 /* Cannot use this optimization because:
990 * char[] a, b;
991 * char c = 'a';
992 * b = a ~ c;
993 * c = 'b';
994 * will change the contents of b.
995 */
996 if (!y.length)
997 return x;
998 if (!x.length)
999 return y;
1000 }
1001
1002 debug(PRINTF) printf("_d_arraycatT(%d,%p ~ %d,%p)\n", x.length, x.ptr, y.length, y.ptr);
1003 auto sizeelem = ti.next.tsize(); // array element size
1004 debug(PRINTF) printf("_d_arraycatT(%d,%p ~ %d,%p sizeelem = %d)\n", x.length, x.ptr, y.length, y.ptr, sizeelem);
1005 size_t xlen = x.length * sizeelem;
1006 size_t ylen = y.length * sizeelem;
1007 size_t len = xlen + ylen;
1008
1009 if (!len)
1010 return null;
1011
1012 byte* p = cast(byte*)gc_malloc(len + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
1013 memcpy(p, x.ptr, xlen);
1014 memcpy(p + xlen, y.ptr, ylen);
1015 p[len] = 0;
1016 return p[0 .. x.length + y.length];
1017 }
1018
1019
1020 /**
1021 *
1022 */
1023 extern (C) byte[] _d_arraycatnT(TypeInfo ti, uint n, ...)
1024 { void* a;
1025 size_t length;
1026 byte[]* p;
1027 uint i;
1028 byte[] b;
1029 auto size = ti.next.tsize(); // array element size
1030
1031 p = cast(byte[]*)(&n + 1);
1032
1033 for (i = 0; i < n; i++)
1034 {
1035 b = *p++;
1036 length += b.length;
1037 }
1038 if (!length)
1039 return null;
1040
1041 a = gc_malloc(length * size, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
1042 p = cast(byte[]*)(&n + 1);
1043
1044 uint j = 0;
1045 for (i = 0; i < n; i++)
1046 {
1047 b = *p++;
1048 if (b.length)
1049 {
1050 memcpy(a + j, b.ptr, b.length * size);
1051 j += b.length * size;
1052 }
1053 }
1054
1055 byte[] result;
1056 *cast(int *)&result = length; // jam length
1057 (cast(void **)&result)[1] = a; // jam ptr
1058 return result;
1059 }
1060
1061
1062 /**
1063 *
1064 */
1065 extern (C) void* _d_arrayliteralT(TypeInfo ti, size_t length, ...)
1066 {
1067 auto sizeelem = ti.next.tsize(); // array element size
1068 void* result;
1069
1070 debug(PRINTF) printf("_d_arrayliteralT(sizeelem = %d, length = %d)\n", sizeelem, length);
1071 if (length == 0 || sizeelem == 0)
1072 result = null;
1073 else
1074 {
1075 result = gc_malloc(length * sizeelem, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
1076
1077 va_list q;
1078 va_start!(size_t)(q, length);
1079
1080 size_t stacksize = (sizeelem + int.sizeof - 1) & ~(int.sizeof - 1);
1081
1082 if (stacksize == sizeelem)
1083 {
1084 memcpy(result, q, length * sizeelem);
1085 }
1086 else
1087 {
1088 for (size_t i = 0; i < length; i++)
1089 {
1090 memcpy(result + i * sizeelem, q, sizeelem);
1091 q += stacksize;
1092 }
1093 }
1094
1095 va_end(q);
1096 }
1097 return result;
1098 }
1099
1100 +/
1101
1102
1103 /**
1104 * Support for array.dup property.
1105 * The actual type is painted on the return value by the frontend
1106 * Given length is number of elements
1107 * Returned length is number of elements
1108 */
1109
1110
1111 /**
1112 *
1113 */
1114 extern (C) void[] _adDupT(TypeInfo ti, void[] a)
1115 out (result)
1116 {
1117 auto sizeelem = ti.next.tsize(); // array element size
1118 assert(memcmp(result.ptr, a.ptr, a.length * sizeelem) == 0);
1119 }
1120 body
1121 {
1122 void* ptr;
1123
1124 if (a.length)
1125 {
1126 auto sizeelem = ti.next.tsize(); // array element size
1127 auto size = a.length * sizeelem;
1128 ptr = gc_malloc(size, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
1129 memcpy(ptr, a.ptr, size);
1130 }
1131 return ptr[0 .. a.length];
1132 }
1133
1134
1135 unittest
1136 {
1137 int[] a;
1138 int[] b;
1139 int i;
1140
1141 a = new int[3];
1142 a[0] = 1; a[1] = 2; a[2] = 3;
1143 b = a.dup;
1144 assert(b.length == 3);
1145 for (i = 0; i < 3; i++)
1146 assert(b[i] == i + 1);
1147 }