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.
29enum 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
40typedef 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
45typedef 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
52void 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
61void* 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
71void 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.
76struct rcNewTag {};
77inline void* operator new(size_t, const rcNewTag&, void* p) { return p; }
78inline 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 (!!!).
82typedef 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.
103template <typename T, rcAllocHint H>
104class 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
170template<typename T, rcAllocHint H>
171bool 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}
185template <typename T, rcAllocHint H>
186T* 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}
194template <typename T, rcAllocHint H>
195void 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}
201template <typename T, rcAllocHint H>
202void 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
222template <typename T, rcAllocHint H>
223rcSizeType 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
230template <typename T, rcAllocHint H>
231void 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}
261template <typename T, rcAllocHint H>
262void 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
277template <typename T, rcAllocHint H>
278void rcVectorBase<T, H>::construct_range(T* begin, T* end) {
279 for (T* p = begin; p < end; p++) {
280 construct(p);
281 }
282}
283// static
284template <typename T, rcAllocHint H>
285void 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
291template <typename T, rcAllocHint H>
292void 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}
297template <typename T, rcAllocHint H>
298void 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
304template <typename T>
305class rcTempVector : public rcVectorBase<T, RC_ALLOC_TEMP> {
306 typedef rcVectorBase<T, RC_ALLOC_TEMP> Base;
307public:
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};
314template <typename T>
315class rcPermVector : public rcVectorBase<T, RC_ALLOC_PERM> {
316 typedef rcVectorBase<T, RC_ALLOC_PERM> Base;
317public:
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>.
327class rcIntArray
328{
329 rcTempVector<int> m_impl;
330public:
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.
349template<class T> class rcScopedDelete
350{
351 T* ptr;
352public:
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
366private:
367 // Explicitly disabled copy constructor and copy assignment operator.
368 rcScopedDelete(const rcScopedDelete&);
369 rcScopedDelete& operator=(const rcScopedDelete&);
370};
371
372#endif
373