containers.dynamicarray source code

1 /**
2  * Dynamic Array
3  * Copyright: © 2014 Economic Modeling Specialists, Intl.
4  * Authors: Brian Schott
5  * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
6  */
7 
8 module containers.dynamicarray;
9 
10 /**
11  * Array that is able to grow itself when items are appended to it. Uses
12  * reference counting to manage memory and malloc/free/realloc for managing its
13  * storage.
14  * Params:
15  *     T = the array element type
16  *     supportGC = true if the container should support holding references to
17  *         GC-allocated memory.
18  */
19 struct DynamicArray(T, bool supportGC = true)
20 {
21 	this(this) @disable;
22 
23 	~this()
24 	{
25 		if (arr is null)
26 			return;
27 		foreach (ref item; arr[0 .. l])
28 			typeid(T).destroy(&item);
29 		static if (shouldAddGCRange!T)
30 		{
31 			import core.memory : GC;
32 			GC.removeRange(arr.ptr);
33 		}
34 		Mallocator.it.deallocate(arr);
35 	}
36 
37 	/// Slice operator overload
38 	T[] opSlice() @nogc
39 	{
40 		return arr[0 .. l];
41 	}
42 
43 	/// ditto
44 	T[] opSlice(size_t a, size_t b) @nogc
45 	{
46 		return arr[a .. b];
47 	}
48 
49 	/// Index operator overload
50 	T opIndex(size_t i) @nogc
51 	{
52 		return arr[i];
53 	}
54 
55 	/**
56 	 * Inserts the given value into the end of the array.
57 	 */
58 	void insert(T value)
59 	{
60 		if (arr.length == 0)
61 		{
62 			arr = cast(T[]) Mallocator.it.allocate(T.sizeof * 4);
63 			static if (supportGC && shouldAddGCRange!T)
64 			{
65 				import core.memory: GC;
66 				GC.addRange(arr.ptr, arr.length * T.sizeof);
67 			}
68 		}
69 		else if (l >= arr.length)
70 		{
71 			immutable size_t c = arr.length > 512 ? arr.length + 1024 : arr.length << 1;
72 			void[] a = cast(void[]) arr;
73 			Mallocator.it.reallocate(a, c * T.sizeof);
74 			arr = cast(T[]) a;
75 			static if (supportGC && shouldAddGCRange!T)
76 			{
77 				import core.memory: GC;
78 				GC.removeRange(arr.ptr);
79 				GC.addRange(arr.ptr, arr.length * T.sizeof);
80 			}
81 		}
82 		arr[l++] = value;
83 	}
84 
85 	/// ditto
86 	alias put = insert;
87 
88 	/// Index assignment support
89 	void opIndexAssign(T value, size_t i) @nogc
90 	{
91 		arr[i] = value;
92 	}
93 
94 	/// Slice assignment support
95 	void opSliceAssign(T value) @nogc
96 	{
97 		arr[0 .. l] = value;
98 	}
99 
100 	/// ditto
101 	void opSliceAssign(T value, size_t i, size_t j) @nogc
102 	{
103 		arr[i .. j] = value;
104 	}
105 
106 	/// Returns: the number of items in the array
107 	size_t length() const nothrow pure @property @safe @nogc { return l; }
108 
109 private:
110 	import std.allocator: Mallocator;
111 	import containers.internal.node: shouldAddGCRange;
112 	T[] arr;
113 	size_t l;
114 }
115 
116 unittest
117 {
118 	import std.algorithm : equal;
119 	import std.range : iota;
120 	DynamicArray!int ints;
121 	foreach (i; 0 .. 100)
122 		ints.insert(i);
123 	assert (equal(ints[], iota(100)));
124 	assert (ints.length == 100);
125 	ints[0] = 100;
126 	assert (ints[0] == 100);
127 	ints[0 .. 5] = 20;
128 	foreach (i; ints[0 .. 5])
129 		assert (i == 20);
130 	ints[] = 432;
131 	foreach (i; ints[])
132 		assert (i == 432);
133 }