1 /**
2 * Compiler implementation of the
3 * $(LINK2 http://www.dlang.org, D programming language).
4 *
5 * Copyright: Copyright (C) 2018-2021 by The D Language Foundation, All Rights Reserved
6 * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright)
7 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
8 * Source: $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/barrayf.d, backend/barray.d)
9 * Documentation: https://dlang.org/phobos/dmd_backend_barray.html
10 */
11
12 module dmd.backend.barray;
13
14 import core.stdc.stdio;
15 import core.stdc.stdlib;
16 import core.stdc.string;
17
18 nothrow:
19
20 extern (C++): private void err_nomem();
21
22 /*************************************
23 * A reusable array that ratchets up in capacity.
24 */
25 struct Barray(T)
26 {
27 /**********************
28 * Set useable length of array.
29 * Params:
30 * length = minimum number of elements in array
31 */
32 void setLength(size_t length)
33 {
34 static void enlarge(ref Barray barray, size_t length)
35 {
36 pragma(inline, false);
37 auto newcap = (barray.capacity == 0) ? length : length + (length >> 1);
38 barray.capacity = (newcap + 15) & ~15;
39 T* p = cast(T*)realloc(barray.array.ptr, barray.capacity * T.sizeof);
40 if (length && !p)
41 {
42 version (unittest)
43 assert(0);
44 else
45 err_nomem();
46 }
47 barray.array = p[0 .. length];
48 }
49
50 if (length <= capacity)
51 array = array.ptr[0 .. length]; // the fast path
52 else
53 enlarge(this, length); // the slow path
54 }
55
56 /**********************
57 * Resets length of array to 0 without
58 * free'ing the array memory. This
59 * sets it up for re-using the memory.
60 */
61 void reset()
62 {
63 setLength(0);
64 }
65
66 /*******************
67 * Append element t to array.
68 * Params:
69 * t = element to append
70 */
71 void push(T t)
72 {
73 const i = length;
74 setLength(i + 1);
75 array[i] = t;
76 }
77
78 /*******************
79 * Append a 0-initialized element of T to array
80 * Returns:
81 * pointer to appended element
82 */
83 T* push()
84 {
85 const i = length;
86 setLength(i + 1);
87 auto p = &array[i];
88 memset(p, 0, T.sizeof);
89 return p;
90 }
91
92 /**********************
93 * Move the last element from the array into [i].
94 * Reduce the array length by one.
95 * Params:
96 * i = index of element to remove
97 */
98 void remove(size_t i)
99 {
100 const len = length - 1;
101 if (i != len)
102 {
103 array[i] = array[len];
104 }
105 setLength(len);
106 }
107
108 /******************
109 * Release all memory used.
110 */
111 void dtor()
112 {
113 free(array.ptr);
114 array = null;
115 capacity = 0;
116 }
117
118 alias array this;
119 T[] array;
120
121 private:
122 size_t capacity;
123 }
124
125 unittest
126 {
127 Barray!int a;
128 a.setLength(10);
129 assert(a.length == 10);
130 a.setLength(4);
131 assert(a.length == 4);
132 foreach (i, ref v; a[])
133 v = cast(int) i * 2;
134 foreach (i, ref const v; a[])
135 assert(v == i * 2);
136 a.remove(3);
137 assert(a.length == 3);
138 a.push(50);
139 a.remove(1);
140 assert(a[1] == 50);
141 a.dtor();
142 assert(a.length == 0);
143 }
144
145 /**************************************
146 * While Barray is good for reusing a Barray's previous allocation,
147 * it doesn't work if an element of the Barray is itself a Barray.
148 * Rarray aims to fix that.
149 */
150
151 struct Rarray(T)
152 {
153 /*******************
154 * Append an uninitialized element of T to array.
155 * This leaves allocations used by T intact.
156 * Returns:
157 * pointer to appended element
158 */
159 T* push()
160 {
161 const i = length;
162 ++length;
163 if (i < barray.length)
164 {
165 return &barray.array[i];
166 }
167 return barray.push();
168 }
169
170 ref inout(T) opIndex(size_t i) inout nothrow pure @nogc
171 {
172 assert(i < length);
173 return barray[i];
174 }
175
176 extern (D) inout(T)[] opSlice() inout nothrow pure @nogc
177 {
178 return barray[0 .. length];
179 }
180
181 extern (D) inout(T)[] opSlice(size_t a, size_t b) inout nothrow pure @nogc
182 {
183 assert(a <= b && b <= length);
184 return barray[a .. b];
185 }
186
187 /**********************
188 * Resets length of array to 0 without
189 * free'ing the array memory. This
190 * sets it up for re-using the memory.
191 */
192 void reset()
193 {
194 length = 0;
195 }
196
197 /******************
198 * Release all memory used.
199 */
200 void dtor()
201 {
202 reset();
203 barray.dtor();
204 }
205
206 alias opDollar = length;
207
208 /* barray[0 .. barray.capacity] allocated length
209 * barray[0 .. barray.length] initialized length
210 * barray[0 .. length] in use length
211 * 0 <= length <= barray.length <= barray.capacity
212 */
213 Barray!T barray;
214
215 size_t length; // <= barray.length
216 }