1#pragma once
2
3#include <Havok/Common/Base/Container/Array/hkArrayUtil.h>
4#include <Havok/Common/Base/Container/hkContainerAllocators.h>
5#include <Havok/Common/Base/Memory/Util/hkMemUtil.h>
6#include <Havok/Common/Base/Types/hkBaseDefs.h>
7#include <Havok/Common/Base/Types/hkBaseTypes.h>
8#include <type_traits>
9
10/// Base class for hkArray (a std::vector-like container).
11template <typename T>
12class hkArrayBase {
13public:
14 HK_DECLARE_CLASS_ALLOCATOR(hkArrayBase<T>)
15
16 enum : unsigned int {
17 CAPACITY_MASK = 0x3FFFFFFF,
18 FLAG_MASK = 0xC0000000,
19 DONT_DEALLOCATE_FLAG = 0x80000000,
20 };
21
22 HK_FORCE_INLINE hkArrayBase();
23 // NOLINTNEXTLINE(cppcoreguidelines-pro-type-member-init)
24 explicit hkArrayBase(hkFinishLoadedObjectFlag f) {}
25 HK_FORCE_INLINE hkArrayBase(T* buffer, int size, int capacity);
26
27 HK_FORCE_INLINE ~hkArrayBase();
28
29 hkArrayBase(const hkArrayBase&) = delete;
30 auto operator=(const hkArrayBase&) = delete;
31
32 HK_FORCE_INLINE int getSize() const;
33 HK_FORCE_INLINE int size() const;
34 HK_FORCE_INLINE int getCapacity() const;
35 HK_FORCE_INLINE int getCapacityAndFlags() const;
36 HK_FORCE_INLINE hkBool isEmpty() const;
37
38 HK_FORCE_INLINE T* data() { return m_data; }
39 HK_FORCE_INLINE const T* data() const { return m_data; }
40
41 HK_FORCE_INLINE T& operator[](int i);
42 HK_FORCE_INLINE const T& operator[](int i) const;
43
44 HK_FORCE_INLINE T& back();
45 HK_FORCE_INLINE const T& back() const;
46
47 HK_FORCE_INLINE void clear();
48 HK_FORCE_INLINE void _clearAndDeallocate(hkMemoryAllocator& allocator);
49 HK_FORCE_INLINE void removeAt(int index);
50 HK_FORCE_INLINE void removeAtAndCopy(int index);
51 HK_FORCE_INLINE void removeAtAndCopy(int index, int numToRemove);
52
53 HK_FORCE_INLINE int indexOf(const T& t, int start = 0, int end = -1) const;
54 HK_FORCE_INLINE int lastIndexOf(const T& t) const;
55
56 HK_FORCE_INLINE void popBack(int numElemsToRemove = 1);
57 HK_FORCE_INLINE void _pushBack(hkMemoryAllocator& alloc, const T& e);
58 HK_FORCE_INLINE void pushBackUnchecked(const T& e);
59 HK_FORCE_INLINE hkBool tryPushBack(const T& t);
60
61 HK_FORCE_INLINE hkResult _reserve(hkMemoryAllocator& alloc, int n);
62 HK_FORCE_INLINE hkResult _reserveExactly(hkMemoryAllocator& alloc, int n);
63
64 HK_FORCE_INLINE void _setSize(hkMemoryAllocator& alloc, int size);
65 HK_FORCE_INLINE void _setSize(hkMemoryAllocator& alloc, int n, const T& fill);
66 HK_FORCE_INLINE hkResult _trySetSize(hkMemoryAllocator& alloc, int size);
67 HK_FORCE_INLINE void setSizeUnchecked(int size);
68
69 HK_FORCE_INLINE T& _expandOne(hkMemoryAllocator& alloc);
70 HK_FORCE_INLINE T* _expandBy(hkMemoryAllocator& alloc, int n);
71 HK_FORCE_INLINE T* expandByUnchecked(int n);
72 HK_FORCE_INLINE T* _expandAt(hkMemoryAllocator& alloc, int index, int numToInsert);
73
74 void _insertAt(hkMemoryAllocator& alloc, int i, const T* a, int numElems);
75 void _insertAt(hkMemoryAllocator& alloc, int i, const T& t);
76
77 void _append(hkMemoryAllocator& alloc, const T* a, int numElems);
78 void _spliceInto(hkMemoryAllocator& alloc, int i, int ndel, const T* p, int numElems);
79
80 HK_FORCE_INLINE void removeAllAndCopy(const T& t);
81
82 using iterator = T*;
83 using const_iterator = const T*;
84
85 HK_FORCE_INLINE iterator begin();
86 HK_FORCE_INLINE iterator end();
87 HK_FORCE_INLINE const_iterator begin() const;
88 HK_FORCE_INLINE const_iterator end() const;
89
90 static HK_FORCE_INLINE void copy(T* dst, const T* src, int n);
91
92 HK_FORCE_INLINE void setDataAutoFree(T* ptr, int size, int capacity);
93 HK_FORCE_INLINE void setDataUserFree(T* ptr, int size, int capacity);
94 HK_FORCE_INLINE void _setDataUnchecked(T* ptr, int size, int capacityAndFlags);
95 HK_FORCE_INLINE void _optimizeCapacity(hkMemoryAllocator& alloc, int numFreeElemsLeft,
96 hkBool32 shrinkExact = false);
97
98protected:
99 HK_FORCE_INLINE hkArrayBase<T>& copyFromArray(hkMemoryAllocator& allocator,
100 const hkArrayBase<T>& src);
101
102 T* m_data;
103 int m_size;
104 int m_capacityAndFlags;
105};
106
107/// A dynamically resizable array, similar to std::vector.
108// FIXME: incomplete
109template <typename T, typename Allocator = hkContainerHeapAllocator>
110class hkArray : public hkArrayBase<T> {
111public:
112 using AllocatorType = Allocator;
113
114 HK_FORCE_INLINE hkArray() = default;
115 HK_FORCE_INLINE hkArray(T* buffer, int size, int capacity)
116 : hkArrayBase<T>(buffer, size, capacity) {}
117 explicit hkArray(hkFinishLoadedObjectFlag f) : hkArrayBase<T>(f) {}
118
119 HK_FORCE_INLINE ~hkArray() { clearAndDeallocate(); }
120
121 HK_FORCE_INLINE hkArray& operator=(const hkArrayBase<T>& other);
122 HK_FORCE_INLINE hkArray& operator=(const hkArray& other);
123
124 HK_FORCE_INLINE void clearAndDeallocate();
125 HK_FORCE_INLINE void pushBack(const T& e);
126 HK_FORCE_INLINE hkResult reserve(int size);
127 HK_FORCE_INLINE hkResult reserveExactly(int size);
128 HK_FORCE_INLINE void setSize(int size);
129 HK_FORCE_INLINE void setSize(int size, const T& fill);
130
131protected:
132 HK_FORCE_INLINE hkArray(const hkArray& other);
133};
134
135template <typename T, unsigned N, typename Allocator = hkContainerHeapAllocator>
136class hkInplaceArray : public hkArray<T, Allocator> {
137public:
138 HK_DECLARE_CLASS_ALLOCATOR(hkInplaceArray)
139
140 HK_FORCE_INLINE explicit hkInplaceArray(int size = 0);
141 HK_FORCE_INLINE hkInplaceArray(const hkInplaceArray& other);
142 explicit hkInplaceArray(hkFinishLoadedObjectFlag f) : hkArray<T, Allocator>(f) {}
143 HK_FORCE_INLINE ~hkInplaceArray() = default;
144
145 using hkArray<T, Allocator>::operator=;
146
147 HK_FORCE_INLINE void optimizeCapacity(int numFreeElemsLeft, hkBool32 shrinkExact = false);
148
149 HK_FORCE_INLINE hkBool wasReallocated() const;
150
151 HK_FORCE_INLINE int stillInplaceUsingMask() const;
152
153 T m_storage[N];
154};
155
156template <typename T>
157inline hkArrayBase<T>::hkArrayBase()
158 : m_data(nullptr), m_size(0), m_capacityAndFlags(DONT_DEALLOCATE_FLAG) {}
159
160template <typename T>
161inline hkArrayBase<T>::hkArrayBase(T* buffer, int size, int capacity)
162 : m_data(buffer), m_size(size), m_capacityAndFlags(capacity | DONT_DEALLOCATE_FLAG) {}
163
164template <typename T>
165inline hkArrayBase<T>::~hkArrayBase() = default;
166
167template <typename T>
168inline int hkArrayBase<T>::getSize() const {
169 return m_size;
170}
171
172template <typename T>
173inline int hkArrayBase<T>::size() const {
174 return getSize();
175}
176
177template <typename T>
178inline int hkArrayBase<T>::getCapacity() const {
179 return m_capacityAndFlags & static_cast<int>(CAPACITY_MASK);
180}
181
182template <typename T>
183inline int hkArrayBase<T>::getCapacityAndFlags() const {
184 return m_capacityAndFlags;
185}
186
187template <typename T>
188inline hkBool hkArrayBase<T>::isEmpty() const {
189 return m_size == 0;
190}
191
192template <typename T>
193inline T& hkArrayBase<T>::operator[](int i) {
194 return m_data[i];
195}
196
197template <typename T>
198inline const T& hkArrayBase<T>::operator[](int i) const {
199 return m_data[i];
200}
201
202template <typename T>
203inline T& hkArrayBase<T>::back() {
204 return m_data[m_size - 1];
205}
206
207template <typename T>
208inline const T& hkArrayBase<T>::back() const {
209 return m_data[m_size - 1];
210}
211
212template <typename T>
213inline void hkArrayBase<T>::clear() {
214 hkArrayUtil::destruct(m_data, m_size);
215 m_size = 0;
216}
217
218template <typename T>
219inline void hkArrayBase<T>::_clearAndDeallocate(hkMemoryAllocator& allocator) {
220 clear();
221 if ((m_capacityAndFlags & DONT_DEALLOCATE_FLAG) == 0) {
222 const int SIZE_ELEM = hkSizeOfTypeOrVoid<T>::val;
223 int numBytes = getCapacity() * SIZE_ELEM;
224 void* storage = const_cast<std::remove_const_t<T>*>(m_data);
225 allocator.bufFree(storage, numBytes);
226 }
227 m_data = nullptr;
228 m_capacityAndFlags = DONT_DEALLOCATE_FLAG;
229}
230
231template <typename T>
232inline void hkArrayBase<T>::removeAt(int index) {
233 hkArrayUtil::destruct(&m_data[index], 1);
234 m_size--;
235 if (m_size != index)
236 hkMemUtil::memCpyOneAligned<sizeof(T), alignof(T)>(m_data + index, m_data + m_size);
237}
238
239template <typename T>
240inline void hkArrayBase<T>::removeAtAndCopy(int index) {
241 removeAtAndCopy(index, 1);
242}
243
244template <typename T>
245inline void hkArrayBase<T>::removeAtAndCopy(int index, int numToRemove) {
246 hkArrayUtil::destruct(m_data + index, numToRemove);
247 m_size -= numToRemove;
248 hkMemUtil::memCpy<alignof(T)>(m_data + index, m_data + index + numToRemove,
249 (m_size - index) * sizeof(T));
250}
251
252template <typename T>
253inline int hkArrayBase<T>::indexOf(const T& t, int start, int end) const {
254 if (end < 0)
255 end = m_size;
256
257 for (int i = start; i < end; ++i) {
258 if (m_data[i] == t)
259 return i;
260 }
261 return -1;
262}
263
264template <typename T>
265inline void hkArrayBase<T>::popBack(int numElemsToRemove) {
266 hkArrayUtil::destruct(m_data + m_size - numElemsToRemove, numElemsToRemove);
267 m_size -= numElemsToRemove;
268}
269
270template <typename T>
271inline void hkArrayBase<T>::_pushBack(hkMemoryAllocator& alloc, const T& e) {
272 if (m_size == getCapacity()) {
273 hkArrayUtil::_reserveMore(alloc, this, sizeof(T));
274 }
275 pushBackUnchecked(e);
276}
277
278template <typename T>
279inline void hkArrayBase<T>::pushBackUnchecked(const T& e) {
280 hkArrayUtil::constructWithCopy<T>(m_data + m_size, 1, e);
281 m_size++;
282}
283
284template <typename T>
285inline hkBool hkArrayBase<T>::tryPushBack(const T& t) {
286 if (m_size < getCapacity()) {
287 hkArrayUtil::constructWithCopy(m_data + m_size, 1, t);
288 m_size++;
289 return true;
290 }
291 return false;
292}
293
294template <typename T>
295inline hkResult hkArrayBase<T>::_reserve(hkMemoryAllocator& alloc, int n) {
296 const int capacity = getCapacity();
297 if (capacity < n) {
298 int newCapacity = 2 * capacity;
299 int newSize = n < newCapacity ? newCapacity : n;
300 return hkArrayUtil::_reserve(alloc, this, newSize, sizeof(T));
301 }
302 return HK_SUCCESS;
303}
304
305template <typename T>
306inline hkResult hkArrayBase<T>::_reserveExactly(hkMemoryAllocator& alloc, int n) {
307 if (getCapacity() < n)
308 return hkArrayUtil::_reserve(alloc, this, n, sizeof(T));
309 return HK_SUCCESS;
310}
311
312template <typename T>
313inline void hkArrayBase<T>::_setSize(hkMemoryAllocator& alloc, int n) {
314 _reserve(alloc, n);
315 hkArrayUtil::destruct(m_data + n, m_size - n);
316 hkArrayUtil::construct(m_data + m_size, n - m_size);
317 m_size = n;
318}
319
320template <typename T>
321inline void hkArrayBase<T>::_setSize(hkMemoryAllocator& alloc, int n, const T& fill) {
322 _reserve(alloc, n);
323 hkArrayUtil::destruct(m_data + n, m_size - n);
324 hkArrayUtil::constructWithCopy(m_data + m_size, n - m_size, fill);
325 m_size = n;
326}
327
328template <typename T>
329inline typename hkArrayBase<T>::iterator hkArrayBase<T>::begin() {
330 return m_data;
331}
332
333template <typename T>
334inline typename hkArrayBase<T>::iterator hkArrayBase<T>::end() {
335 return m_data + m_size;
336}
337
338template <typename T>
339inline typename hkArrayBase<T>::const_iterator hkArrayBase<T>::begin() const {
340 return m_data;
341}
342
343template <typename T>
344inline typename hkArrayBase<T>::const_iterator hkArrayBase<T>::end() const {
345 return m_data + m_size;
346}
347
348template <typename T>
349inline void hkArrayBase<T>::copy(T* dst, const T* src, int n) {
350 for (int i = 0; i < n; ++i) {
351 dst[i] = src[i];
352 }
353}
354
355template <typename T>
356inline void hkArrayBase<T>::_setDataUnchecked(T* ptr, int size, int capacityAndFlags) {
357 m_data = ptr;
358 m_size = size;
359 m_capacityAndFlags = capacityAndFlags;
360}
361
362template <typename T>
363inline void hkArrayBase<T>::setDataAutoFree(T* ptr, int size, int capacity) {
364 static_assert(std::is_pod_v<T>, "T must be a POD type");
365 _setDataUnchecked(ptr, size, capacity);
366}
367
368template <typename T>
369inline void hkArrayBase<T>::setDataUserFree(T* ptr, int size, int capacity) {
370 static_assert(std::is_pod_v<T>, "T must be a POD type");
371 _setDataUnchecked(ptr, size, capacity | DONT_DEALLOCATE_FLAG);
372}
373
374template <typename T>
375inline hkArrayBase<T>& hkArrayBase<T>::copyFromArray(hkMemoryAllocator& allocator,
376 const hkArrayBase<T>& src) {
377 if constexpr (std::is_pod_v<T>) {
378 if (getCapacity() < src.getSize()) {
379 if ((m_capacityAndFlags & DONT_DEALLOCATE_FLAG) == 0) {
380 allocator._bufFree<T>(m_data, getCapacity());
381 }
382 int n = src.getSize();
383 m_data = allocator._bufAlloc<T>(n);
384 m_capacityAndFlags = n;
385 }
386 m_size = src.getSize();
387 copy(m_data, src.m_data, m_size);
388
389 } else {
390 const int oldSize = m_size;
391 const int newSize = src.getSize();
392 const int copiedSize = newSize > oldSize ? oldSize : newSize;
393
394 _reserve(allocator, newSize);
395 hkArrayUtil::destruct(m_data + newSize, oldSize - newSize);
396 copy(m_data, src.m_data, copiedSize);
397 hkArrayUtil::constructWithArray(m_data + copiedSize, newSize - copiedSize,
398 src.m_data + copiedSize);
399 m_size = newSize;
400 }
401 return *this;
402}
403
404template <typename T, typename Allocator>
405inline hkArray<T, Allocator>& hkArray<T, Allocator>::operator=(const hkArrayBase<T>& a) {
406 this->copyFromArray(Allocator().get(), a);
407 return *this;
408}
409
410template <typename T, typename Allocator>
411inline hkArray<T, Allocator>& hkArray<T, Allocator>::operator=(const hkArray& a) {
412 this->copyFromArray(Allocator().get(), a);
413 return *this;
414}
415
416template <typename T, typename Allocator>
417inline void hkArray<T, Allocator>::clearAndDeallocate() {
418 this->_clearAndDeallocate(AllocatorType().get());
419}
420
421template <typename T, typename Allocator>
422inline void hkArray<T, Allocator>::pushBack(const T& e) {
423 this->_pushBack(AllocatorType().get(), e);
424}
425
426template <typename T, typename Allocator>
427inline void hkArray<T, Allocator>::setSize(int size) {
428 this->_setSize(AllocatorType().get(), size);
429}
430
431template <typename T, typename Allocator>
432inline void hkArray<T, Allocator>::setSize(int size, const T& fill) {
433 this->_setSize(AllocatorType().get(), size, fill);
434}
435
436template <typename T, typename Allocator>
437inline hkResult hkArray<T, Allocator>::reserve(int size) {
438 return this->_reserve(AllocatorType().get(), size);
439}
440
441template <typename T, typename Allocator>
442inline hkResult hkArray<T, Allocator>::reserveExactly(int size) {
443 return this->_reserveExactly(AllocatorType().get(), size);
444}
445
446template <typename T, unsigned N, typename Allocator>
447inline hkInplaceArray<T, N, Allocator>::hkInplaceArray(int size)
448 : hkArray<T, Allocator>(m_storage, size, N) {}
449
450template <typename T, unsigned N, typename Allocator>
451inline hkInplaceArray<T, N, Allocator>::hkInplaceArray(const hkInplaceArray& other)
452 : hkArray<T, Allocator>(m_storage, 0, N) {
453 *this = other;
454}
455
456template <typename T, unsigned N, typename Allocator>
457inline hkBool hkInplaceArray<T, N, Allocator>::wasReallocated() const {
458 return this->m_data != m_storage;
459}
460
461template <typename T, unsigned N, typename Allocator>
462inline int hkInplaceArray<T, N, Allocator>::stillInplaceUsingMask() const {
463 return hkArray<T, Allocator>::m_capacityAndFlags & hkArrayBase<T>::DONT_DEALLOCATE_FLAG;
464}
465