allocators.h
1 // Copyright (C) 2011 Milo Yip
2 //
3 // Permission is hereby granted, free of charge, to any person obtaining a copy
4 // of this software and associated documentation files (the "Software"), to deal
5 // in the Software without restriction, including without limitation the rights
6 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7 // copies of the Software, and to permit persons to whom the Software is
8 // furnished to do so, subject to the following conditions:
9 //
10 // The above copyright notice and this permission notice shall be included in
11 // all copies or substantial portions of the Software.
12 //
13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19 // THE SOFTWARE.
20 
21 #ifndef RAPIDJSON_ALLOCATORS_H_
22 #define RAPIDJSON_ALLOCATORS_H_
23 
24 #include "rapidjson.h"
25 
26 namespace rapidjson {
27 
28 ///////////////////////////////////////////////////////////////////////////////
29 // Allocator
30 
31 /*! \class rapidjson::Allocator
32  \brief Concept for allocating, resizing and freeing memory block.
33 
34  Note that Malloc() and Realloc() are non-static but Free() is static.
35 
36  So if an allocator need to support Free(), it needs to put its pointer in
37  the header of memory block.
38 
39 \code
40 concept Allocator {
41  static const bool kNeedFree; //!< Whether this allocator needs to call Free().
42 
43  // Allocate a memory block.
44  // \param size of the memory block in bytes.
45  // \returns pointer to the memory block.
46  void* Malloc(size_t size);
47 
48  // Resize a memory block.
49  // \param originalPtr The pointer to current memory block. Null pointer is permitted.
50  // \param originalSize The current size in bytes. (Design issue: since some allocator may not book-keep this, explicitly pass to it can save memory.)
51  // \param newSize the new size in bytes.
52  void* Realloc(void* originalPtr, size_t originalSize, size_t newSize);
53 
54  // Free a memory block.
55  // \param pointer to the memory block. Null pointer is permitted.
56  static void Free(void *ptr);
57 };
58 \endcode
59 */
60 
61 ///////////////////////////////////////////////////////////////////////////////
62 // CrtAllocator
63 
64 //! C-runtime library allocator.
65 /*! This class is just wrapper for standard C library memory routines.
66  \note implements Allocator concept
67 */
68 class CrtAllocator {
69 public:
70  static const bool kNeedFree = true;
71  void* Malloc(size_t size) { return std::malloc(size); }
72  void* Realloc(void* originalPtr, size_t originalSize, size_t newSize) { (void)originalSize; return std::realloc(originalPtr, newSize); }
73  static void Free(void *ptr) { std::free(ptr); }
74 };
75 
76 ///////////////////////////////////////////////////////////////////////////////
77 // MemoryPoolAllocator
78 
79 //! Default memory allocator used by the parser and DOM.
80 /*! This allocator allocate memory blocks from pre-allocated memory chunks.
81 
82  It does not free memory blocks. And Realloc() only allocate new memory.
83 
84  The memory chunks are allocated by BaseAllocator, which is CrtAllocator by default.
85 
86  User may also supply a buffer as the first chunk.
87 
88  If the user-buffer is full then additional chunks are allocated by BaseAllocator.
89 
90  The user-buffer is not deallocated by this allocator.
91 
92  \tparam BaseAllocator the allocator type for allocating memory chunks. Default is CrtAllocator.
93  \note implements Allocator concept
94 */
95 template <typename BaseAllocator = CrtAllocator>
97 public:
98  static const bool kNeedFree = false; //!< Tell users that no need to call Free() with this allocator. (concept Allocator)
99 
100  //! Constructor with chunkSize.
101  /*! \param chunkSize The size of memory chunk. The default is kDefaultChunkSize.
102  \param baseAllocator The allocator for allocating memory chunks.
103  */
104  MemoryPoolAllocator(size_t chunkSize = kDefaultChunkCapacity, BaseAllocator* baseAllocator = 0) :
105  chunkHead_(0), chunk_capacity_(chunkSize), userBuffer_(0), baseAllocator_(baseAllocator), ownBaseAllocator_(0)
106  {
107  }
108 
109  //! Constructor with user-supplied buffer.
110  /*! The user buffer will be used firstly. When it is full, memory pool allocates new chunk with chunk size.
111 
112  The user buffer will not be deallocated when this allocator is destructed.
113 
114  \param buffer User supplied buffer.
115  \param size Size of the buffer in bytes. It must at least larger than sizeof(ChunkHeader).
116  \param chunkSize The size of memory chunk. The default is kDefaultChunkSize.
117  \param baseAllocator The allocator for allocating memory chunks.
118  */
119  MemoryPoolAllocator(void *buffer, size_t size, size_t chunkSize = kDefaultChunkCapacity, BaseAllocator* baseAllocator = 0) :
120  chunkHead_(0), chunk_capacity_(chunkSize), userBuffer_(buffer), baseAllocator_(baseAllocator), ownBaseAllocator_(0)
121  {
122  RAPIDJSON_ASSERT(buffer != 0);
123  RAPIDJSON_ASSERT(size > sizeof(ChunkHeader));
124  chunkHead_ = reinterpret_cast<ChunkHeader*>(buffer);
125  chunkHead_->capacity = size - sizeof(ChunkHeader);
126  chunkHead_->size = 0;
127  chunkHead_->next = 0;
128  }
129 
130  //! Destructor.
131  /*! This deallocates all memory chunks, excluding the user-supplied buffer.
132  */
134  Clear();
135  RAPIDJSON_DELETE(ownBaseAllocator_);
136  }
137 
138  //! Deallocates all memory chunks, excluding the user-supplied buffer.
139  void Clear() {
140  while(chunkHead_ != 0 && chunkHead_ != userBuffer_) {
141  ChunkHeader* next = chunkHead_->next;
142  baseAllocator_->Free(chunkHead_);
143  chunkHead_ = next;
144  }
145  }
146 
147  //! Computes the total capacity of allocated memory chunks.
148  /*! \return total capacity in bytes.
149  */
150  size_t Capacity() const {
151  size_t capacity = 0;
152  for (ChunkHeader* c = chunkHead_; c != 0; c = c->next)
153  capacity += c->capacity;
154  return capacity;
155  }
156 
157  //! Computes the memory blocks allocated.
158  /*! \return total used bytes.
159  */
160  size_t Size() const {
161  size_t size = 0;
162  for (ChunkHeader* c = chunkHead_; c != 0; c = c->next)
163  size += c->size;
164  return size;
165  }
166 
167  //! Allocates a memory block. (concept Allocator)
168  void* Malloc(size_t size) {
169  size = RAPIDJSON_ALIGN(size);
170  if (chunkHead_ == 0 || chunkHead_->size + size > chunkHead_->capacity)
171  AddChunk(chunk_capacity_ > size ? chunk_capacity_ : size);
172 
173  void *buffer = reinterpret_cast<char *>(chunkHead_ + 1) + chunkHead_->size;
174  chunkHead_->size += size;
175  return buffer;
176  }
177 
178  //! Resizes a memory block (concept Allocator)
179  void* Realloc(void* originalPtr, size_t originalSize, size_t newSize) {
180  if (originalPtr == 0)
181  return Malloc(newSize);
182 
183  // Do not shrink if new size is smaller than original
184  if (originalSize >= newSize)
185  return originalPtr;
186 
187  // Simply expand it if it is the last allocation and there is sufficient space
188  if (originalPtr == (char *)(chunkHead_ + 1) + chunkHead_->size - originalSize) {
189  size_t increment = static_cast<size_t>(newSize - originalSize);
190  increment = RAPIDJSON_ALIGN(increment);
191  if (chunkHead_->size + increment <= chunkHead_->capacity) {
192  chunkHead_->size += increment;
193  return originalPtr;
194  }
195  }
196 
197  // Realloc process: allocate and copy memory, do not free original buffer.
198  void* newBuffer = Malloc(newSize);
199  RAPIDJSON_ASSERT(newBuffer != 0); // Do not handle out-of-memory explicitly.
200  return std::memcpy(newBuffer, originalPtr, originalSize);
201  }
202 
203  //! Frees a memory block (concept Allocator)
204  static void Free(void *ptr) { (void)ptr; } // Do nothing
205 
206 private:
207  //! Copy constructor is not permitted.
208  MemoryPoolAllocator(const MemoryPoolAllocator& rhs) /* = delete */;
209  //! Copy assignment operator is not permitted.
210  MemoryPoolAllocator& operator=(const MemoryPoolAllocator& rhs) /* = delete */;
211 
212  //! Creates a new chunk.
213  /*! \param capacity Capacity of the chunk in bytes.
214  */
215  void AddChunk(size_t capacity) {
216  if (!baseAllocator_)
217  ownBaseAllocator_ = baseAllocator_ = RAPIDJSON_NEW(BaseAllocator());
218  ChunkHeader* chunk = reinterpret_cast<ChunkHeader*>(baseAllocator_->Malloc(sizeof(ChunkHeader) + capacity));
219  chunk->capacity = capacity;
220  chunk->size = 0;
221  chunk->next = chunkHead_;
222  chunkHead_ = chunk;
223  }
224 
225  static const int kDefaultChunkCapacity = 64 * 1024; //!< Default chunk capacity.
226 
227  //! Chunk header for perpending to each chunk.
228  /*! Chunks are stored as a singly linked list.
229  */
230  struct ChunkHeader {
231  size_t capacity; //!< Capacity of the chunk in bytes (excluding the header itself).
232  size_t size; //!< Current size of allocated memory in bytes.
233  ChunkHeader *next; //!< Next chunk in the linked list.
234  };
235 
236  ChunkHeader *chunkHead_; //!< Head of the chunk linked-list. Only the head chunk serves allocation.
237  size_t chunk_capacity_; //!< The minimum capacity of chunk when they are allocated.
238  void *userBuffer_; //!< User supplied buffer.
239  BaseAllocator* baseAllocator_; //!< base allocator for allocating memory chunks.
240  BaseAllocator* ownBaseAllocator_; //!< base allocator created by this object.
241 };
242 
243 } // namespace rapidjson
244 
245 #endif // RAPIDJSON_ENCODINGS_H_
~MemoryPoolAllocator()
Destructor.
Definition: allocators.h:133
void * Realloc(void *originalPtr, size_t originalSize, size_t newSize)
Resizes a memory block (concept Allocator)
Definition: allocators.h:179
MemoryPoolAllocator(void *buffer, size_t size, size_t chunkSize=kDefaultChunkCapacity, BaseAllocator *baseAllocator=0)
Constructor with user-supplied buffer.
Definition: allocators.h:119
size_t Capacity() const
Computes the total capacity of allocated memory chunks.
Definition: allocators.h:150
void Clear()
Deallocates all memory chunks, excluding the user-supplied buffer.
Definition: allocators.h:139
MemoryPoolAllocator(size_t chunkSize=kDefaultChunkCapacity, BaseAllocator *baseAllocator=0)
Constructor with chunkSize.
Definition: allocators.h:104
C-runtime library allocator.
Definition: allocators.h:68
void * Malloc(size_t size)
Allocates a memory block. (concept Allocator)
Definition: allocators.h:168
#define RAPIDJSON_NEW(x)
! customization point for global new
Definition: rapidjson.h:408
#define RAPIDJSON_ALIGN(x)
Data alignment of the machine.
Definition: rapidjson.h:173
#define RAPIDJSON_DELETE(x)
! customization point for global delete
Definition: rapidjson.h:412
main RapidJSON namespace
Definition: rapidjson.h:241
common definitions and configuration
size_t Size() const
Computes the memory blocks allocated.
Definition: allocators.h:160
Default memory allocator used by the parser and DOM.
Definition: allocators.h:96
static void Free(void *ptr)
Frees a memory block (concept Allocator)
Definition: allocators.h:204
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:269