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 // CrtAllocator 57 58 //! C-runtime library allocator. 59 /*! This class is just wrapper for standard C library memory routines. 60 \note implements Allocator concept 61 */ 62 class CrtAllocator { 63 public: 64 static const bool kNeedFree = true; 65 void* Malloc(size_t size) { 66 if (size) // behavior of malloc(0) is implementation defined. 67 return std::malloc(size); 68 else 69 return NULL; // standardize to returning NULL. 70 } 71 void* Realloc(void* originalPtr, size_t originalSize, size_t newSize) { 72 (void)originalSize; 73 if (newSize == 0) { 74 std::free(originalPtr); 75 return NULL; 76 } 77 return std::realloc(originalPtr, newSize); 78 } 79 static void Free(void *ptr) { std::free(ptr); } 80 }; 81 82 /////////////////////////////////////////////////////////////////////////////// 83 // MemoryPoolAllocator 84 85 //! Default memory allocator used by the parser and DOM. 86 /*! This allocator allocate memory blocks from pre-allocated memory chunks. 87 88 It does not free memory blocks. And Realloc() only allocate new memory. 89 90 The memory chunks are allocated by BaseAllocator, which is CrtAllocator by default. 91 92 User may also supply a buffer as the first chunk. 93 94 If the user-buffer is full then additional chunks are allocated by BaseAllocator. 95 96 The user-buffer is not deallocated by this allocator. 97 98 \tparam BaseAllocator the allocator type for allocating memory chunks. Default is CrtAllocator. 99 \note implements Allocator concept 100 */ 101 template <typename BaseAllocator = CrtAllocator> 102 class MemoryPoolAllocator { 103 public: 104 static const bool kNeedFree = false; //!< Tell users that no need to call Free() with this allocator. (concept Allocator) 105 106 //! Constructor with chunkSize. 107 /*! \param chunkSize The size of memory chunk. The default is kDefaultChunkSize. 108 \param baseAllocator The allocator for allocating memory chunks. 109 */ 110 MemoryPoolAllocator(size_t chunkSize = kDefaultChunkCapacity, BaseAllocator* baseAllocator = 0) : 111 chunkHead_(0), chunk_capacity_(chunkSize), userBuffer_(0), baseAllocator_(baseAllocator), ownBaseAllocator_(0) 112 { 113 } 114 115 //! Constructor with user-supplied buffer. 116 /*! The user buffer will be used firstly. When it is full, memory pool allocates new chunk with chunk size. 117 118 The user buffer will not be deallocated when this allocator is destructed. 119 120 \param buffer User supplied buffer. 121 \param size Size of the buffer in bytes. It must at least larger than sizeof(ChunkHeader). 122 \param chunkSize The size of memory chunk. The default is kDefaultChunkSize. 123 \param baseAllocator The allocator for allocating memory chunks. 124 */ 125 MemoryPoolAllocator(void *buffer, size_t size, size_t chunkSize = kDefaultChunkCapacity, BaseAllocator* baseAllocator = 0) : 126 chunkHead_(0), chunk_capacity_(chunkSize), userBuffer_(buffer), baseAllocator_(baseAllocator), ownBaseAllocator_(0) 127 { 128 RAPIDJSON_ASSERT(buffer != 0); 129 RAPIDJSON_ASSERT(size > sizeof(ChunkHeader)); 130 chunkHead_ = reinterpret_cast<ChunkHeader*>(buffer); 131 chunkHead_->capacity = size - sizeof(ChunkHeader); 132 chunkHead_->size = 0; 133 chunkHead_->next = 0; 134 } 135 136 //! Destructor. 137 /*! This deallocates all memory chunks, excluding the user-supplied buffer. 138 */ 139 ~MemoryPoolAllocator() { 140 Clear(); 141 RAPIDJSON_DELETE(ownBaseAllocator_); 142 } 143 144 //! Deallocates all memory chunks, excluding the user-supplied buffer. 145 void Clear() { 146 while (chunkHead_ && chunkHead_ != userBuffer_) { 147 ChunkHeader* next = chunkHead_->next; 148 baseAllocator_->Free(chunkHead_); 149 chunkHead_ = next; 150 } 151 if (chunkHead_ && chunkHead_ == userBuffer_) 152 chunkHead_->size = 0; // Clear user buffer 153 } 154 155 //! Computes the total capacity of allocated memory chunks. 156 /*! \return total capacity in bytes. 157 */ 158 size_t Capacity() const { 159 size_t capacity = 0; 160 for (ChunkHeader* c = chunkHead_; c != 0; c = c->next) 161 capacity += c->capacity; 162 return capacity; 163 } 164 165 //! Computes the memory blocks allocated. 166 /*! \return total used bytes. 167 */ 168 size_t Size() const { 169 size_t size = 0; 170 for (ChunkHeader* c = chunkHead_; c != 0; c = c->next) 171 size += c->size; 172 return size; 173 } 174 175 //! Allocates a memory block. (concept Allocator) 176 void* Malloc(size_t size) { 177 if (!size) 178 return NULL; 179 180 size = RAPIDJSON_ALIGN(size); 181 if (chunkHead_ == 0 || chunkHead_->size + size > chunkHead_->capacity) 182 AddChunk(chunk_capacity_ > size ? chunk_capacity_ : size); 183 184 void *buffer = reinterpret_cast<char *>(chunkHead_) + RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + chunkHead_->size; 185 chunkHead_->size += size; 186 return buffer; 187 } 188 189 //! Resizes a memory block (concept Allocator) 190 void* Realloc(void* originalPtr, size_t originalSize, size_t newSize) { 191 if (originalPtr == 0) 192 return Malloc(newSize); 193 194 if (newSize == 0) 195 return NULL; 196 197 // Do not shrink if new size is smaller than original 198 if (originalSize >= newSize) 199 return originalPtr; 200 201 // Simply expand it if it is the last allocation and there is sufficient space 202 if (originalPtr == (char *)(chunkHead_) + RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + chunkHead_->size - originalSize) { 203 size_t increment = static_cast<size_t>(newSize - originalSize); 204 increment = RAPIDJSON_ALIGN(increment); 205 if (chunkHead_->size + increment <= chunkHead_->capacity) { 206 chunkHead_->size += increment; 207 return originalPtr; 208 } 209 } 210 211 // Realloc process: allocate and copy memory, do not free original buffer. 212 void* newBuffer = Malloc(newSize); 213 RAPIDJSON_ASSERT(newBuffer != 0); // Do not handle out-of-memory explicitly. 214 if (originalSize) 215 std::memcpy(newBuffer, originalPtr, originalSize); 216 return newBuffer; 217 } 218 219 //! Frees a memory block (concept Allocator) 220 static void Free(void *ptr) { (void)ptr; } // Do nothing 221 222 private: 223 //! Copy constructor is not permitted. 224 MemoryPoolAllocator(const MemoryPoolAllocator& rhs) /* = delete */; 225 //! Copy assignment operator is not permitted. 226 MemoryPoolAllocator& operator=(const MemoryPoolAllocator& rhs) /* = delete */; 227 228 //! Creates a new chunk. 229 /*! \param capacity Capacity of the chunk in bytes. 230 */ 231 void AddChunk(size_t capacity) { 232 if (!baseAllocator_) 233 ownBaseAllocator_ = baseAllocator_ = RAPIDJSON_NEW(BaseAllocator()); 234 ChunkHeader* chunk = reinterpret_cast<ChunkHeader*>(baseAllocator_->Malloc(RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + capacity)); 235 chunk->capacity = capacity; 236 chunk->size = 0; 237 chunk->next = chunkHead_; 238 chunkHead_ = chunk; 239 } 240 241 static const int kDefaultChunkCapacity = 64 * 1024; //!< Default chunk capacity. 242 243 //! Chunk header for perpending to each chunk. 244 /*! Chunks are stored as a singly linked list. 245 */ 246 struct ChunkHeader { 247 size_t capacity; //!< Capacity of the chunk in bytes (excluding the header itself). 248 size_t size; //!< Current size of allocated memory in bytes. 249 ChunkHeader *next; //!< Next chunk in the linked list. 250 }; 251 252 ChunkHeader *chunkHead_; //!< Head of the chunk linked-list. Only the head chunk serves allocation. 253 size_t chunk_capacity_; //!< The minimum capacity of chunk when they are allocated. 254 void *userBuffer_; //!< User supplied buffer. 255 BaseAllocator* baseAllocator_; //!< base allocator for allocating memory chunks. 256 BaseAllocator* ownBaseAllocator_; //!< base allocator created by this object. 257 }; 258 259 RAPIDJSON_NAMESPACE_END 260 261 #endif // RAPIDJSON_ENCODINGS_H_ 262
