allocators.h
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 
20 RAPIDJSON_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
34 concept 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_DEFUALT_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 */
75 class CrtAllocator {
76 public:
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 */
114 template <typename BaseAllocator = CrtAllocator>
116 public:
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  */
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 
240 private:
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 
282 RAPIDJSON_NAMESPACE_END
283 
284 #endif // RAPIDJSON_ENCODINGS_H_
~MemoryPoolAllocator()
Destructor.
Definition: allocators.h:152
void * Realloc(void *originalPtr, size_t originalSize, size_t newSize)
Resizes a memory block (concept Allocator)
Definition: allocators.h:204
MemoryPoolAllocator(void *buffer, size_t size, size_t chunkSize=kDefaultChunkCapacity, BaseAllocator *baseAllocator=0)
Constructor with user-supplied buffer.
Definition: allocators.h:138
size_t Capacity() const
Computes the total capacity of allocated memory chunks.
Definition: allocators.h:171
void Clear()
Deallocates all memory chunks, excluding the user-supplied buffer.
Definition: allocators.h:158
MemoryPoolAllocator(size_t chunkSize=kDefaultChunkCapacity, BaseAllocator *baseAllocator=0)
Constructor with chunkSize.
Definition: allocators.h:123
C-runtime library allocator.
Definition: allocators.h:75
#define RAPIDJSON_NEW(TypeName)
! customization point for global new
Definition: rapidjson.h:603
void * Malloc(size_t size)
Allocates a memory block. (concept Allocator)
Definition: allocators.h:189
#define RAPIDJSON_ALIGN(x)
Data alignment of the machine.
Definition: rapidjson.h:280
#define RAPIDJSON_DELETE(x)
! customization point for global delete
Definition: rapidjson.h:607
common definitions and configuration
size_t Size() const
Computes the memory blocks allocated.
Definition: allocators.h:181
Default memory allocator used by the parser and DOM.
Definition: allocators.h:115
static void Free(void *ptr)
Frees a memory block (concept Allocator)
Definition: allocators.h:238
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:411