1// Tencent is pleased to support the open source community by making RapidJSON available.
2//
3// Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
4//
5// Licensed under the MIT License (the "License"); you may not use this file except
6// in compliance with the License. You may obtain a copy of the License at
7//
8// http://opensource.org/licenses/MIT
9//
10// Unless required by applicable law or agreed to in writing, software distributed
11// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
12// CONDITIONS OF ANY KIND, either express or implied. See the License for the
13// specific language governing permissions and limitations under the License.
14
15#ifndef RAPIDJSON_ALLOCATORS_H_
16#define RAPIDJSON_ALLOCATORS_H_
17
18#include "rapidjson.h"
19
20RAPIDJSON_NAMESPACE_BEGIN
21
22///////////////////////////////////////////////////////////////////////////////
23// Allocator
24
25/*! \class rapidjson::Allocator
26 \brief Concept for allocating, resizing and freeing memory block.
27
28 Note that Malloc() and Realloc() are non-static but Free() is static.
29
30 So if an allocator need to support Free(), it needs to put its pointer in
31 the header of memory block.
32
33\code
34concept Allocator {
35 static const bool kNeedFree; //!< Whether this allocator needs to call Free().
36
37 // Allocate a memory block.
38 // \param size of the memory block in bytes.
39 // \returns pointer to the memory block.
40 void* Malloc(size_t size);
41
42 // Resize a memory block.
43 // \param originalPtr The pointer to current memory block. Null pointer is permitted.
44 // \param originalSize The current size in bytes. (Design issue: since some allocator may not book-keep this, explicitly pass to it can save memory.)
45 // \param newSize the new size in bytes.
46 void* Realloc(void* originalPtr, size_t originalSize, size_t newSize);
47
48 // Free a memory block.
49 // \param pointer to the memory block. Null pointer is permitted.
50 static void Free(void *ptr);
51};
52\endcode
53*/
54
55
56/*! \def RAPIDJSON_ALLOCATOR_DEFAULT_CHUNK_CAPACITY
57 \ingroup RAPIDJSON_CONFIG
58 \brief User-defined kDefaultChunkCapacity definition.
59
60 User can define this as any \c size that is a power of 2.
61*/
62
63#ifndef RAPIDJSON_ALLOCATOR_DEFAULT_CHUNK_CAPACITY
64#define RAPIDJSON_ALLOCATOR_DEFAULT_CHUNK_CAPACITY (64 * 1024)
65#endif
66
67
68///////////////////////////////////////////////////////////////////////////////
69// CrtAllocator
70
71//! C-runtime library allocator.
72/*! This class is just wrapper for standard C library memory routines.
73 \note implements Allocator concept
74*/
75class CrtAllocator {
76public:
77 static const bool kNeedFree = true;
78 void* Malloc(size_t size) {
79 if (size) // behavior of malloc(0) is implementation defined.
80 return std::malloc(size);
81 else
82 return NULL; // standardize to returning NULL.
83 }
84 void* Realloc(void* originalPtr, size_t originalSize, size_t newSize) {
85 (void)originalSize;
86 if (newSize == 0) {
87 std::free(originalPtr);
88 return NULL;
89 }
90 return std::realloc(originalPtr, newSize);
91 }
92 static void Free(void *ptr) { std::free(ptr); }
93};
94
95///////////////////////////////////////////////////////////////////////////////
96// MemoryPoolAllocator
97
98//! Default memory allocator used by the parser and DOM.
99/*! This allocator allocate memory blocks from pre-allocated memory chunks.
100
101 It does not free memory blocks. And Realloc() only allocate new memory.
102
103 The memory chunks are allocated by BaseAllocator, which is CrtAllocator by default.
104
105 User may also supply a buffer as the first chunk.
106
107 If the user-buffer is full then additional chunks are allocated by BaseAllocator.
108
109 The user-buffer is not deallocated by this allocator.
110
111 \tparam BaseAllocator the allocator type for allocating memory chunks. Default is CrtAllocator.
112 \note implements Allocator concept
113*/
114template <typename BaseAllocator = CrtAllocator>
115class MemoryPoolAllocator {
116public:
117 static const bool kNeedFree = false; //!< Tell users that no need to call Free() with this allocator. (concept Allocator)
118
119 //! Constructor with chunkSize.
120 /*! \param chunkSize The size of memory chunk. The default is kDefaultChunkSize.
121 \param baseAllocator The allocator for allocating memory chunks.
122 */
123 MemoryPoolAllocator(size_t chunkSize = kDefaultChunkCapacity, BaseAllocator* baseAllocator = 0) :
124 chunkHead_(0), chunk_capacity_(chunkSize), userBuffer_(0), baseAllocator_(baseAllocator), ownBaseAllocator_(0)
125 {
126 }
127
128 //! Constructor with user-supplied buffer.
129 /*! The user buffer will be used firstly. When it is full, memory pool allocates new chunk with chunk size.
130
131 The user buffer will not be deallocated when this allocator is destructed.
132
133 \param buffer User supplied buffer.
134 \param size Size of the buffer in bytes. It must at least larger than sizeof(ChunkHeader).
135 \param chunkSize The size of memory chunk. The default is kDefaultChunkSize.
136 \param baseAllocator The allocator for allocating memory chunks.
137 */
138 MemoryPoolAllocator(void *buffer, size_t size, size_t chunkSize = kDefaultChunkCapacity, BaseAllocator* baseAllocator = 0) :
139 chunkHead_(0), chunk_capacity_(chunkSize), userBuffer_(buffer), baseAllocator_(baseAllocator), ownBaseAllocator_(0)
140 {
141 RAPIDJSON_ASSERT(buffer != 0);
142 RAPIDJSON_ASSERT(size > sizeof(ChunkHeader));
143 chunkHead_ = reinterpret_cast<ChunkHeader*>(buffer);
144 chunkHead_->capacity = size - sizeof(ChunkHeader);
145 chunkHead_->size = 0;
146 chunkHead_->next = 0;
147 }
148
149 //! Destructor.
150 /*! This deallocates all memory chunks, excluding the user-supplied buffer.
151 */
152 ~MemoryPoolAllocator() {
153 Clear();
154 RAPIDJSON_DELETE(ownBaseAllocator_);
155 }
156
157 //! Deallocates all memory chunks, excluding the user-supplied buffer.
158 void Clear() {
159 while (chunkHead_ && chunkHead_ != userBuffer_) {
160 ChunkHeader* next = chunkHead_->next;
161 baseAllocator_->Free(chunkHead_);
162 chunkHead_ = next;
163 }
164 if (chunkHead_ && chunkHead_ == userBuffer_)
165 chunkHead_->size = 0; // Clear user buffer
166 }
167
168 //! Computes the total capacity of allocated memory chunks.
169 /*! \return total capacity in bytes.
170 */
171 size_t Capacity() const {
172 size_t capacity = 0;
173 for (ChunkHeader* c = chunkHead_; c != 0; c = c->next)
174 capacity += c->capacity;
175 return capacity;
176 }
177
178 //! Computes the memory blocks allocated.
179 /*! \return total used bytes.
180 */
181 size_t Size() const {
182 size_t size = 0;
183 for (ChunkHeader* c = chunkHead_; c != 0; c = c->next)
184 size += c->size;
185 return size;
186 }
187
188 //! Allocates a memory block. (concept Allocator)
189 void* Malloc(size_t size) {
190 if (!size)
191 return NULL;
192
193 size = RAPIDJSON_ALIGN(size);
194 if (chunkHead_ == 0 || chunkHead_->size + size > chunkHead_->capacity)
195 if (!AddChunk(chunk_capacity_ > size ? chunk_capacity_ : size))
196 return NULL;
197
198 void *buffer = reinterpret_cast<char *>(chunkHead_) + RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + chunkHead_->size;
199 chunkHead_->size += size;
200 return buffer;
201 }
202
203 //! Resizes a memory block (concept Allocator)
204 void* Realloc(void* originalPtr, size_t originalSize, size_t newSize) {
205 if (originalPtr == 0)
206 return Malloc(newSize);
207
208 if (newSize == 0)
209 return NULL;
210
211 originalSize = RAPIDJSON_ALIGN(originalSize);
212 newSize = RAPIDJSON_ALIGN(newSize);
213
214 // Do not shrink if new size is smaller than original
215 if (originalSize >= newSize)
216 return originalPtr;
217
218 // Simply expand it if it is the last allocation and there is sufficient space
219 if (originalPtr == reinterpret_cast<char *>(chunkHead_) + RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + chunkHead_->size - originalSize) {
220 size_t increment = static_cast<size_t>(newSize - originalSize);
221 if (chunkHead_->size + increment <= chunkHead_->capacity) {
222 chunkHead_->size += increment;
223 return originalPtr;
224 }
225 }
226
227 // Realloc process: allocate and copy memory, do not free original buffer.
228 if (void* newBuffer = Malloc(newSize)) {
229 if (originalSize)
230 std::memcpy(newBuffer, originalPtr, originalSize);
231 return newBuffer;
232 }
233 else
234 return NULL;
235 }
236
237 //! Frees a memory block (concept Allocator)
238 static void Free(void *ptr) { (void)ptr; } // Do nothing
239
240private:
241 //! Copy constructor is not permitted.
242 MemoryPoolAllocator(const MemoryPoolAllocator& rhs) /* = delete */;
243 //! Copy assignment operator is not permitted.
244 MemoryPoolAllocator& operator=(const MemoryPoolAllocator& rhs) /* = delete */;
245
246 //! Creates a new chunk.
247 /*! \param capacity Capacity of the chunk in bytes.
248 \return true if success.
249 */
250 bool AddChunk(size_t capacity) {
251 if (!baseAllocator_)
252 ownBaseAllocator_ = baseAllocator_ = RAPIDJSON_NEW(BaseAllocator)();
253 if (ChunkHeader* chunk = reinterpret_cast<ChunkHeader*>(baseAllocator_->Malloc(RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + capacity))) {
254 chunk->capacity = capacity;
255 chunk->size = 0;
256 chunk->next = chunkHead_;
257 chunkHead_ = chunk;
258 return true;
259 }
260 else
261 return false;
262 }
263
264 static const int kDefaultChunkCapacity = RAPIDJSON_ALLOCATOR_DEFAULT_CHUNK_CAPACITY; //!< Default chunk capacity.
265
266 //! Chunk header for perpending to each chunk.
267 /*! Chunks are stored as a singly linked list.
268 */
269 struct ChunkHeader {
270 size_t capacity; //!< Capacity of the chunk in bytes (excluding the header itself).
271 size_t size; //!< Current size of allocated memory in bytes.
272 ChunkHeader *next; //!< Next chunk in the linked list.
273 };
274
275 ChunkHeader *chunkHead_; //!< Head of the chunk linked-list. Only the head chunk serves allocation.
276 size_t chunk_capacity_; //!< The minimum capacity of chunk when they are allocated.
277 void *userBuffer_; //!< User supplied buffer.
278 BaseAllocator* baseAllocator_; //!< base allocator for allocating memory chunks.
279 BaseAllocator* ownBaseAllocator_; //!< base allocator created by this object.
280};
281
282RAPIDJSON_NAMESPACE_END
283
284#endif // RAPIDJSON_ENCODINGS_H_
285