1 | // |
2 | // Copyright (c) 2009-2010 Mikko Mononen memon@inside.org |
3 | // |
4 | // This software is provided 'as-is', without any express or implied |
5 | // warranty. In no event will the authors be held liable for any damages |
6 | // arising from the use of this software. |
7 | // Permission is granted to anyone to use this software for any purpose, |
8 | // including commercial applications, and to alter it and redistribute it |
9 | // freely, subject to the following restrictions: |
10 | // 1. The origin of this software must not be misrepresented; you must not |
11 | // claim that you wrote the original software. If you use this software |
12 | // in a product, an acknowledgment in the product documentation would be |
13 | // appreciated but is not required. |
14 | // 2. Altered source versions must be plainly marked as such, and must not be |
15 | // misrepresented as being the original software. |
16 | // 3. This notice may not be removed or altered from any source distribution. |
17 | // |
18 | |
19 | #ifndef RECASTALLOC_H |
20 | #define RECASTALLOC_H |
21 | |
22 | #include "RecastAssert.h" |
23 | |
24 | #include <stdlib.h> |
25 | #include <stdint.h> |
26 | |
27 | /// Provides hint values to the memory allocator on how long the |
28 | /// memory is expected to be used. |
29 | enum rcAllocHint |
30 | { |
31 | RC_ALLOC_PERM, ///< Memory will persist after a function call. |
32 | RC_ALLOC_TEMP ///< Memory used temporarily within a function. |
33 | }; |
34 | |
35 | /// A memory allocation function. |
36 | // @param[in] size The size, in bytes of memory, to allocate. |
37 | // @param[in] rcAllocHint A hint to the allocator on how long the memory is expected to be in use. |
38 | // @return A pointer to the beginning of the allocated memory block, or null if the allocation failed. |
39 | /// @see rcAllocSetCustom |
40 | typedef void* (rcAllocFunc)(size_t size, rcAllocHint hint); |
41 | |
42 | /// A memory deallocation function. |
43 | /// @param[in] ptr A pointer to a memory block previously allocated using #rcAllocFunc. |
44 | /// @see rcAllocSetCustom |
45 | typedef void (rcFreeFunc)(void* ptr); |
46 | |
47 | /// Sets the base custom allocation functions to be used by Recast. |
48 | /// @param[in] allocFunc The memory allocation function to be used by #rcAlloc |
49 | /// @param[in] freeFunc The memory de-allocation function to be used by #rcFree |
50 | /// |
51 | /// @see rcAlloc, rcFree |
52 | void rcAllocSetCustom(rcAllocFunc *allocFunc, rcFreeFunc *freeFunc); |
53 | |
54 | /// Allocates a memory block. |
55 | /// |
56 | /// @param[in] size The size, in bytes of memory, to allocate. |
57 | /// @param[in] hint A hint to the allocator on how long the memory is expected to be in use. |
58 | /// @return A pointer to the beginning of the allocated memory block, or null if the allocation failed. |
59 | /// |
60 | /// @see rcFree, rcAllocSetCustom |
61 | void* rcAlloc(size_t size, rcAllocHint hint); |
62 | |
63 | /// Deallocates a memory block. If @p ptr is NULL, this does nothing. |
64 | /// |
65 | /// @warning This function leaves the value of @p ptr unchanged. So it still |
66 | /// points to the same (now invalid) location, and not to null. |
67 | /// |
68 | /// @param[in] ptr A pointer to a memory block previously allocated using #rcAlloc. |
69 | /// |
70 | /// @see rcAlloc, rcAllocSetCustom |
71 | void rcFree(void* ptr); |
72 | |
73 | /// An implementation of operator new usable for placement new. The default one is part of STL (which we don't use). |
74 | /// rcNewTag is a dummy type used to differentiate our operator from the STL one, in case users import both Recast |
75 | /// and STL. |
76 | struct rcNewTag {}; |
77 | inline void* operator new(size_t, const rcNewTag&, void* p) { return p; } |
78 | inline void operator delete(void*, const rcNewTag&, void*) {} |
79 | |
80 | /// Signed to avoid warnnings when comparing to int loop indexes, and common error with comparing to zero. |
81 | /// MSVC2010 has a bug where ssize_t is unsigned (!!!). |
82 | typedef intptr_t rcSizeType; |
83 | #define RC_SIZE_MAX INTPTR_MAX |
84 | |
85 | /// Macros to hint to the compiler about the likeliest branch. Please add a benchmark that demonstrates a performance |
86 | /// improvement before introducing use cases. |
87 | #if defined(__GNUC__) || defined(__clang__) |
88 | #define rcLikely(x) __builtin_expect((x), true) |
89 | #define rcUnlikely(x) __builtin_expect((x), false) |
90 | #else |
91 | #define rcLikely(x) (x) |
92 | #define rcUnlikely(x) (x) |
93 | #endif |
94 | |
95 | /// Variable-sized storage type. Mimics the interface of std::vector<T> with some notable differences: |
96 | /// * Uses rcAlloc()/rcFree() to handle storage. |
97 | /// * No support for a custom allocator. |
98 | /// * Uses signed size instead of size_t to avoid warnings in for loops: "for (int i = 0; i < foo.size(); i++)" |
99 | /// * Omits methods of limited utility: insert/erase, (bad performance), at (we don't use exceptions), operator=. |
100 | /// * assign() and the pre-sizing constructor follow C++11 semantics -- they don't construct a temporary if no value is provided. |
101 | /// * push_back() and resize() support adding values from the current vector. Range-based constructors and assign(begin, end) do not. |
102 | /// * No specialization for bool. |
103 | template <typename T, rcAllocHint H> |
104 | class rcVectorBase { |
105 | rcSizeType m_size; |
106 | rcSizeType m_cap; |
107 | T* m_data; |
108 | // Constructs a T at the give address with either the copy constructor or the default. |
109 | static void construct(T* p, const T& v) { ::new(rcNewTag(), (void*)p) T(v); } |
110 | static void construct(T* p) { ::new(rcNewTag(), (void*)p) T; } |
111 | static void construct_range(T* begin, T* end); |
112 | static void construct_range(T* begin, T* end, const T& value); |
113 | static void copy_range(T* dst, const T* begin, const T* end); |
114 | void destroy_range(rcSizeType begin, rcSizeType end); |
115 | // Creates an array of the given size, copies all of this vector's data into it, and returns it. |
116 | T* allocate_and_copy(rcSizeType size); |
117 | void resize_impl(rcSizeType size, const T* value); |
118 | // Requires: min_capacity > m_cap. |
119 | rcSizeType get_new_capacity(rcSizeType min_capacity); |
120 | public: |
121 | typedef rcSizeType size_type; |
122 | typedef T value_type; |
123 | |
124 | rcVectorBase() : m_size(0), m_cap(0), m_data(0) {} |
125 | rcVectorBase(const rcVectorBase<T, H>& other) : m_size(0), m_cap(0), m_data(0) { assign(other.begin(), other.end()); } |
126 | explicit rcVectorBase(rcSizeType count) : m_size(0), m_cap(0), m_data(0) { resize(count); } |
127 | rcVectorBase(rcSizeType count, const T& value) : m_size(0), m_cap(0), m_data(0) { resize(count, value); } |
128 | rcVectorBase(const T* begin, const T* end) : m_size(0), m_cap(0), m_data(0) { assign(begin, end); } |
129 | ~rcVectorBase() { destroy_range(0, m_size); rcFree(m_data); } |
130 | |
131 | // Unlike in std::vector, we return a bool to indicate whether the alloc was successful. |
132 | bool reserve(rcSizeType size); |
133 | |
134 | void assign(rcSizeType count, const T& value) { clear(); resize(count, value); } |
135 | void assign(const T* begin, const T* end); |
136 | |
137 | void resize(rcSizeType size) { resize_impl(size, NULL); } |
138 | void resize(rcSizeType size, const T& value) { resize_impl(size, &value); } |
139 | // Not implemented as resize(0) because resize requires T to be default-constructible. |
140 | void clear() { destroy_range(0, m_size); m_size = 0; } |
141 | |
142 | void push_back(const T& value); |
143 | void pop_back() { rcAssert(m_size > 0); back().~T(); m_size--; } |
144 | |
145 | rcSizeType size() const { return m_size; } |
146 | rcSizeType capacity() const { return m_cap; } |
147 | bool empty() const { return size() == 0; } |
148 | |
149 | const T& operator[](rcSizeType i) const { rcAssert(i >= 0 && i < m_size); return m_data[i]; } |
150 | T& operator[](rcSizeType i) { rcAssert(i >= 0 && i < m_size); return m_data[i]; } |
151 | |
152 | const T& front() const { rcAssert(m_size); return m_data[0]; } |
153 | T& front() { rcAssert(m_size); return m_data[0]; } |
154 | const T& back() const { rcAssert(m_size); return m_data[m_size - 1]; } |
155 | T& back() { rcAssert(m_size); return m_data[m_size - 1]; } |
156 | const T* data() const { return m_data; } |
157 | T* data() { return m_data; } |
158 | |
159 | T* begin() { return m_data; } |
160 | T* end() { return m_data + m_size; } |
161 | const T* begin() const { return m_data; } |
162 | const T* end() const { return m_data + m_size; } |
163 | |
164 | void swap(rcVectorBase<T, H>& other); |
165 | |
166 | // Explicitly deleted. |
167 | rcVectorBase& operator=(const rcVectorBase<T, H>& other); |
168 | }; |
169 | |
170 | template<typename T, rcAllocHint H> |
171 | bool rcVectorBase<T, H>::reserve(rcSizeType count) { |
172 | if (count <= m_cap) { |
173 | return true; |
174 | } |
175 | T* new_data = allocate_and_copy(count); |
176 | if (!new_data) { |
177 | return false; |
178 | } |
179 | destroy_range(0, m_size); |
180 | rcFree(m_data); |
181 | m_data = new_data; |
182 | m_cap = count; |
183 | return true; |
184 | } |
185 | template <typename T, rcAllocHint H> |
186 | T* rcVectorBase<T, H>::allocate_and_copy(rcSizeType size) { |
187 | rcAssert(RC_SIZE_MAX / static_cast<rcSizeType>(sizeof(T)) >= size); |
188 | T* new_data = static_cast<T*>(rcAlloc(sizeof(T) * size, H)); |
189 | if (new_data) { |
190 | copy_range(new_data, m_data, m_data + m_size); |
191 | } |
192 | return new_data; |
193 | } |
194 | template <typename T, rcAllocHint H> |
195 | void rcVectorBase<T, H>::assign(const T* begin, const T* end) { |
196 | clear(); |
197 | reserve(end - begin); |
198 | m_size = end - begin; |
199 | copy_range(m_data, begin, end); |
200 | } |
201 | template <typename T, rcAllocHint H> |
202 | void rcVectorBase<T, H>::push_back(const T& value) { |
203 | // rcLikely increases performance by ~50% on BM_rcVector_PushPreallocated, |
204 | // and by ~2-5% on BM_rcVector_Push. |
205 | if (rcLikely(m_size < m_cap)) { |
206 | construct(m_data + m_size++, value); |
207 | return; |
208 | } |
209 | |
210 | const rcSizeType new_cap = get_new_capacity(m_cap + 1); |
211 | T* data = allocate_and_copy(new_cap); |
212 | // construct between allocate and destroy+free in case value is |
213 | // in this vector. |
214 | construct(data + m_size, value); |
215 | destroy_range(0, m_size); |
216 | m_size++; |
217 | m_cap = new_cap; |
218 | rcFree(m_data); |
219 | m_data = data; |
220 | } |
221 | |
222 | template <typename T, rcAllocHint H> |
223 | rcSizeType rcVectorBase<T, H>::get_new_capacity(rcSizeType min_capacity) { |
224 | rcAssert(min_capacity <= RC_SIZE_MAX); |
225 | if (rcUnlikely(m_cap >= RC_SIZE_MAX / 2)) |
226 | return RC_SIZE_MAX; |
227 | return 2 * m_cap > min_capacity ? 2 * m_cap : min_capacity; |
228 | } |
229 | |
230 | template <typename T, rcAllocHint H> |
231 | void rcVectorBase<T, H>::resize_impl(rcSizeType size, const T* value) { |
232 | if (size < m_size) { |
233 | destroy_range(size, m_size); |
234 | m_size = size; |
235 | } else if (size > m_size) { |
236 | if (size <= m_cap) { |
237 | if (value) { |
238 | construct_range(m_data + m_size, m_data + size, *value); |
239 | } else { |
240 | construct_range(m_data + m_size, m_data + size); |
241 | } |
242 | m_size = size; |
243 | } else { |
244 | const rcSizeType new_cap = get_new_capacity(size); |
245 | T* new_data = allocate_and_copy(new_cap); |
246 | // We defer deconstructing/freeing old data until after constructing |
247 | // new elements in case "value" is there. |
248 | if (value) { |
249 | construct_range(new_data + m_size, new_data + size, *value); |
250 | } else { |
251 | construct_range(new_data + m_size, new_data + size); |
252 | } |
253 | destroy_range(0, m_size); |
254 | rcFree(m_data); |
255 | m_data = new_data; |
256 | m_cap = new_cap; |
257 | m_size = size; |
258 | } |
259 | } |
260 | } |
261 | template <typename T, rcAllocHint H> |
262 | void rcVectorBase<T, H>::swap(rcVectorBase<T, H>& other) { |
263 | // TODO: Reorganize headers so we can use rcSwap here. |
264 | rcSizeType tmp_cap = other.m_cap; |
265 | rcSizeType tmp_size = other.m_size; |
266 | T* tmp_data = other.m_data; |
267 | |
268 | other.m_cap = m_cap; |
269 | other.m_size = m_size; |
270 | other.m_data = m_data; |
271 | |
272 | m_cap = tmp_cap; |
273 | m_size = tmp_size; |
274 | m_data = tmp_data; |
275 | } |
276 | // static |
277 | template <typename T, rcAllocHint H> |
278 | void rcVectorBase<T, H>::construct_range(T* begin, T* end) { |
279 | for (T* p = begin; p < end; p++) { |
280 | construct(p); |
281 | } |
282 | } |
283 | // static |
284 | template <typename T, rcAllocHint H> |
285 | void rcVectorBase<T, H>::construct_range(T* begin, T* end, const T& value) { |
286 | for (T* p = begin; p < end; p++) { |
287 | construct(p, value); |
288 | } |
289 | } |
290 | // static |
291 | template <typename T, rcAllocHint H> |
292 | void rcVectorBase<T, H>::copy_range(T* dst, const T* begin, const T* end) { |
293 | for (rcSizeType i = 0 ; i < end - begin; i++) { |
294 | construct(dst + i, begin[i]); |
295 | } |
296 | } |
297 | template <typename T, rcAllocHint H> |
298 | void rcVectorBase<T, H>::destroy_range(rcSizeType begin, rcSizeType end) { |
299 | for (rcSizeType i = begin; i < end; i++) { |
300 | m_data[i].~T(); |
301 | } |
302 | } |
303 | |
304 | template <typename T> |
305 | class rcTempVector : public rcVectorBase<T, RC_ALLOC_TEMP> { |
306 | typedef rcVectorBase<T, RC_ALLOC_TEMP> Base; |
307 | public: |
308 | rcTempVector() : Base() {} |
309 | explicit rcTempVector(rcSizeType size) : Base(size) {} |
310 | rcTempVector(rcSizeType size, const T& value) : Base(size, value) {} |
311 | rcTempVector(const rcTempVector<T>& other) : Base(other) {} |
312 | rcTempVector(const T* begin, const T* end) : Base(begin, end) {} |
313 | }; |
314 | template <typename T> |
315 | class rcPermVector : public rcVectorBase<T, RC_ALLOC_PERM> { |
316 | typedef rcVectorBase<T, RC_ALLOC_PERM> Base; |
317 | public: |
318 | rcPermVector() : Base() {} |
319 | explicit rcPermVector(rcSizeType size) : Base(size) {} |
320 | rcPermVector(rcSizeType size, const T& value) : Base(size, value) {} |
321 | rcPermVector(const rcPermVector<T>& other) : Base(other) {} |
322 | rcPermVector(const T* begin, const T* end) : Base(begin, end) {} |
323 | }; |
324 | |
325 | |
326 | /// Legacy class. Prefer rcVector<int>. |
327 | class rcIntArray |
328 | { |
329 | rcTempVector<int> m_impl; |
330 | public: |
331 | rcIntArray() {} |
332 | rcIntArray(int n) : m_impl(n, 0) {} |
333 | void push(int item) { m_impl.push_back(item); } |
334 | void resize(int size) { m_impl.resize(size); } |
335 | void clear() { m_impl.clear(); } |
336 | int pop() |
337 | { |
338 | int v = m_impl.back(); |
339 | m_impl.pop_back(); |
340 | return v; |
341 | } |
342 | int size() const { return static_cast<int>(m_impl.size()); } |
343 | int& operator[](int index) { return m_impl[index]; } |
344 | int operator[](int index) const { return m_impl[index]; } |
345 | }; |
346 | |
347 | /// A simple helper class used to delete an array when it goes out of scope. |
348 | /// @note This class is rarely if ever used by the end user. |
349 | template<class T> class rcScopedDelete |
350 | { |
351 | T* ptr; |
352 | public: |
353 | |
354 | /// Constructs an instance with a null pointer. |
355 | inline rcScopedDelete() : ptr(0) {} |
356 | |
357 | /// Constructs an instance with the specified pointer. |
358 | /// @param[in] p An pointer to an allocated array. |
359 | inline rcScopedDelete(T* p) : ptr(p) {} |
360 | inline ~rcScopedDelete() { rcFree(ptr); } |
361 | |
362 | /// The root array pointer. |
363 | /// @return The root array pointer. |
364 | inline operator T*() { return ptr; } |
365 | |
366 | private: |
367 | // Explicitly disabled copy constructor and copy assignment operator. |
368 | rcScopedDelete(const rcScopedDelete&); |
369 | rcScopedDelete& operator=(const rcScopedDelete&); |
370 | }; |
371 | |
372 | #endif |
373 | |