1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5#pragma once
6
7// An array of T that expands automatically (and never shrinks) to accomodate
8// any index access. Elements added as a result of automatic expansion are
9// value-initialized (that is, they are assigned T()).
10template <class T>
11class JitExpandArray
12{
13protected:
14 CompAllocator m_alloc; // The allocator object that should be used to allocate members.
15 T* m_members; // Pointer to the element array.
16 unsigned m_size; // The size of the element array.
17 unsigned m_minSize; // The minimum size of the element array.
18
19 // Ensure that the element array is large enough for the specified index to be valid.
20 void EnsureCoversInd(unsigned idx);
21
22 //------------------------------------------------------------------------
23 // InitializeRange: Value-initialize the specified range of elements.
24 //
25 // Arguments:
26 // low - inclusive lower bound of the range to initialize
27 // high - exclusive upper bound of the range to initialize
28 //
29 // Assumptions:
30 // Assumes that the element array has aready been allocated
31 // and that low and high are valid indices. The array is not
32 // expanded to accomodate invalid indices.
33 //
34 void InitializeRange(unsigned low, unsigned high)
35 {
36 assert(m_members != nullptr);
37 assert((low <= high) && (high <= m_size));
38 for (unsigned i = low; i < high; i++)
39 {
40 m_members[i] = T();
41 }
42 }
43
44public:
45 //------------------------------------------------------------------------
46 // JitExpandArray: Construct an empty JitExpandArray object.
47 //
48 // Arguments:
49 // alloc - the allocator used to allocate the element array
50 // minSize - the initial size of the element array
51 //
52 // Notes:
53 // Initially no memory is allocated for the element array. The first
54 // time an array element (having index `idx`) is accessed, an array
55 // of size max(`minSize`, `idx`) is allocated.
56 //
57 JitExpandArray(CompAllocator alloc, unsigned minSize = 1)
58 : m_alloc(alloc), m_members(nullptr), m_size(0), m_minSize(minSize)
59 {
60 assert(minSize > 0);
61 }
62
63 //------------------------------------------------------------------------
64 // ~JitExpandArray: Destruct the JitExpandArray object.
65 //
66 // Notes:
67 // Frees the element array. Destructors of elements stored in the
68 // array are NOT invoked.
69 //
70 ~JitExpandArray()
71 {
72 if (m_members != nullptr)
73 {
74 m_alloc.deallocate(m_members);
75 }
76 }
77
78 //------------------------------------------------------------------------
79 // Init: Re-initialize the array to the empty state.
80 //
81 // Arguments:
82 // alloc - the allocator used to allocate the element array
83 // minSize - the initial size of the element array
84 //
85 // Notes:
86 // This is equivalent to calling the destructor and then constructing
87 // the array again.
88 //
89 void Init(CompAllocator alloc, unsigned minSize = 1)
90 {
91 if (m_members != nullptr)
92 {
93 m_alloc.deallocate(m_members);
94 }
95 m_alloc = alloc;
96 m_members = nullptr;
97 m_size = 0;
98 m_minSize = minSize;
99 }
100
101 //------------------------------------------------------------------------
102 // Reset: Change the minimum size and value-initialize all the elements.
103 //
104 // Arguments:
105 // minSize - the initial size of the element array
106 //
107 // Notes:
108 // Ensures that an element array of at least `minSize` elements
109 // has been allocated.
110 //
111 void Reset(unsigned minSize)
112 {
113 m_minSize = minSize;
114 Reset();
115 }
116
117 //------------------------------------------------------------------------
118 // Reset: Value-initialize all the array elements.
119 //
120 // Notes:
121 // Ensures that an element array of at least `m_minSize` elements
122 // has been allocated.
123 //
124 void Reset()
125 {
126 if (m_minSize > m_size)
127 {
128 EnsureCoversInd(m_minSize - 1);
129 }
130 InitializeRange(0, m_size);
131 }
132
133 //------------------------------------------------------------------------
134 // Get: Get a copy of the element at index `idx`.
135 //
136 // Arguments:
137 // idx - the element index
138 //
139 // Return Value:
140 // A copy of the element at index `idx`.
141 //
142 // Notes:
143 // Expands the element array, if necessary, to contain `idx`.
144 // The result will be a value-initialized T if a value wasn't
145 // previously assigned to the specififed index.
146 //
147 T Get(unsigned idx)
148 {
149 EnsureCoversInd(idx);
150 return m_members[idx];
151 }
152
153 //------------------------------------------------------------------------
154 // GetRef: Get a reference to the element at index `idx`.
155 //
156 // Arguments:
157 // idx - the element index
158 //
159 // Return Value:
160 // A reference to the element at index `idx`.
161 //
162 // Notes:
163 // Like `Get`, but returns a reference, so suitable for use as
164 // the LHS of an assignment.
165 //
166 T& GetRef(unsigned idx)
167 {
168 EnsureCoversInd(idx);
169 return m_members[idx];
170 }
171
172 //------------------------------------------------------------------------
173 // Set: Assign a copy of `val` to the element at index `idx`.
174 //
175 // Arguments:
176 // idx - the element index
177 // val - the value to assign
178 //
179 // Notes:
180 // Expands the element array, if necessary, to contain `idx`.
181 //
182 void Set(unsigned idx, T val)
183 {
184 EnsureCoversInd(idx);
185 m_members[idx] = val;
186 }
187
188 //------------------------------------------------------------------------
189 // operator[]: Get a reference to the element at index `idx`.
190 //
191 // Arguments:
192 // idx - the element index
193 //
194 // Return Value:
195 // A reference to the element at index `idx`.
196 //
197 // Notes:
198 // Same as `GetRef`.
199 //
200 T& operator[](unsigned idx)
201 {
202 EnsureCoversInd(idx);
203 return m_members[idx];
204 }
205};
206
207template <class T>
208class JitExpandArrayStack : public JitExpandArray<T>
209{
210 unsigned m_used; // The stack depth
211
212public:
213 //------------------------------------------------------------------------
214 // JitExpandArrayStack: Construct an empty JitExpandArrayStack object.
215 //
216 // Arguments:
217 // alloc - the allocator used to allocate the element array
218 // minSize - the initial size of the element array
219 //
220 // Notes:
221 // See JitExpandArray constructor notes.
222 //
223 JitExpandArrayStack(CompAllocator alloc, unsigned minSize = 1) : JitExpandArray<T>(alloc, minSize), m_used(0)
224 {
225 }
226
227 //------------------------------------------------------------------------
228 // Set: Assign value a copy of `val` to the element at index `idx`.
229 //
230 // Arguments:
231 // idx - the index of element
232 // val - the value to assign
233 //
234 // Notes:
235 // Expands the element array, if necessary, to contain `idx`.
236 // If `idx` is larger than the current stack depth then this
237 // is the equivalent of series of Push(T()) followed by a Push(val).
238 //
239 void Set(unsigned idx, T val)
240 {
241 JitExpandArray<T>::Set(idx, val);
242 m_used = max((idx + 1), m_used);
243 }
244
245 //------------------------------------------------------------------------
246 // Reset: Remove all the elements from the stack.
247 //
248 void Reset()
249 {
250 JitExpandArray<T>::Reset();
251 m_used = 0;
252 }
253
254 //------------------------------------------------------------------------
255 // Push: Push a copy of the specified value onto the stack.
256 //
257 // Arguments:
258 // val - the value
259 //
260 // Return Value:
261 // The index of the pushed value.
262 //
263 unsigned Push(T val)
264 {
265 unsigned res = m_used;
266 JitExpandArray<T>::Set(m_used, val);
267 m_used++;
268 return res;
269 }
270
271 //------------------------------------------------------------------------
272 // Pop: Remove the top element of the stack.
273 //
274 // Return Value:
275 // A copy of the removed element.
276 //
277 // Assumptions:
278 // The stack must not be empty.
279 //
280 T Pop()
281 {
282 assert(Size() > 0);
283 m_used--;
284 return this->m_members[m_used];
285 }
286
287 //------------------------------------------------------------------------
288 // Top: Get a copy of the top element.
289 //
290 // Return Value:
291 // A copy of the top element.
292 //
293 // Assumptions:
294 // The stack must not be empty.
295 //
296 T Top()
297 {
298 assert(Size() > 0);
299 return this->m_members[m_used - 1];
300 }
301
302 //------------------------------------------------------------------------
303 // TopRef: Get a reference to the top element.
304 //
305 // Return Value:
306 // A reference to the top element.
307 //
308 // Assumptions:
309 // The stack must not be empty.
310 //
311 T& TopRef()
312 {
313 assert(Size() > 0);
314 return this->m_members[m_used - 1];
315 }
316
317 //------------------------------------------------------------------------
318 // GetNoExpand: Get a copy of the element at index `idx`.
319 //
320 // Arguments:
321 // idx - the element index
322 //
323 // Return Value:
324 // A copy of the element at index `idx`.
325 //
326 // Notes:
327 // Unlike `Get` this does not expand the array if the index is not valid.
328 //
329 // Assumptions:
330 // The element index does not exceed the current stack depth.
331 //
332 T GetNoExpand(unsigned idx)
333 {
334 assert(idx < m_used);
335 return this->m_members[idx];
336 }
337
338 //------------------------------------------------------------------------
339 // Remove: Remove the element at index `idx`.
340 //
341 // Arguments:
342 // idx - the element index
343 //
344 // Notes:
345 // Shifts contents of the array beyond `idx`, if any, to occupy the free
346 // slot created at `idx`. O(n) worst case operation, no memory is allocated.
347 // Elements are bitwise copied, copy constructors are NOT invoked.
348 //
349 // Assumptions:
350 // The element index does not exceed the current stack depth.
351 //
352 void Remove(unsigned idx)
353 {
354 assert(idx < m_used);
355 if (idx < m_used - 1)
356 {
357 memmove(&this->m_members[idx], &this->m_members[idx + 1], (m_used - idx - 1) * sizeof(T));
358 }
359 m_used--;
360 }
361
362 //------------------------------------------------------------------------
363 // Size: Get the current stack depth.
364 //
365 // Return Value:
366 // The stack depth.
367 //
368 unsigned Size()
369 {
370 return m_used;
371 }
372};
373
374//------------------------------------------------------------------------
375// EnsureCoversInd: Ensure that the array is large enough for the specified
376// index to be valid.
377//
378// Arguments:
379// idx - the element index
380//
381// Notes:
382// If the array is expanded then
383// - the existing elements are bitwise copied (copy constructors are NOT invoked)
384// - the newly added elements are value-initialized
385//
386template <class T>
387void JitExpandArray<T>::EnsureCoversInd(unsigned idx)
388{
389 if (idx >= m_size)
390 {
391 unsigned oldSize = m_size;
392 T* oldMembers = m_members;
393 m_size = max(idx + 1, max(m_minSize, m_size * 2));
394 m_members = m_alloc.allocate<T>(m_size);
395 if (oldMembers != nullptr)
396 {
397 memcpy(m_members, oldMembers, oldSize * sizeof(T));
398 m_alloc.deallocate(oldMembers);
399 }
400 InitializeRange(oldSize, m_size);
401 }
402}
403