third-party/rapidjson/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 // 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             if (!AddChunk(chunk_capacity_ > size ? chunk_capacity_ : size))
 183                 return NULL;
 184
 185         void *buffer = reinterpret_cast<char *>(chunkHead_) + RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + chunkHead_->size;
 186         chunkHead_->size += size;
 187         return buffer;
 188     }
 189
 190     //! Resizes a memory block (concept Allocator)
 191     void* Realloc(void* originalPtr, size_t originalSize, size_t newSize) {
 192         if (originalPtr == 0)
 193             return Malloc(newSize);
 194
 195         if (newSize == 0)
 196             return NULL;
 197
 198         originalSize = RAPIDJSON_ALIGN(originalSize);
 199         newSize = RAPIDJSON_ALIGN(newSize);
 200
 201         // Do not shrink if new size is smaller than original
 202         if (originalSize >= newSize)
 203             return originalPtr;
 204
 205         // Simply expand it if it is the last allocation and there is sufficient space
 206         if (originalPtr == reinterpret_cast<char *>(chunkHead_) + RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + chunkHead_->size - originalSize) {
 207             size_t increment = static_cast<size_t>(newSize - originalSize);
 208             if (chunkHead_->size + increment <= chunkHead_->capacity) {
 209                 chunkHead_->size += increment;
 210                 return originalPtr;
 211             }
 212         }
 213
 214         // Realloc process: allocate and copy memory, do not free original buffer.
 215         if (void* newBuffer = Malloc(newSize)) {
 216             if (originalSize)
 217                 std::memcpy(newBuffer, originalPtr, originalSize);
 218             return newBuffer;
 219         }
 220         else
 221             return NULL;
 222     }
 223
 224     //! Frees a memory block (concept Allocator)
 225     static void Free(void *ptr) { (void)ptr; } // Do nothing
 226
 227 private:
 228     //! Copy constructor is not permitted.
 229     MemoryPoolAllocator(const MemoryPoolAllocator& rhs) /* = delete */;
 230     //! Copy assignment operator is not permitted.
 231     MemoryPoolAllocator& operator=(const MemoryPoolAllocator& rhs) /* = delete */;
 232
 233     //! Creates a new chunk.
 234     /*! \param capacity Capacity of the chunk in bytes.
 235         \return true if success.
 236     */
 237     bool AddChunk(size_t capacity) {
 238         if (!baseAllocator_)
 239             ownBaseAllocator_ = baseAllocator_ = RAPIDJSON_NEW(BaseAllocator());
 240         if (ChunkHeader* chunk = reinterpret_cast<ChunkHeader*>(baseAllocator_->Malloc(RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + capacity))) {
 241             chunk->capacity = capacity;
 242             chunk->size = 0;
 243             chunk->next = chunkHead_;
 244             chunkHead_ =  chunk;
 245             return true;
 246         }
 247         else
 248             return false;
 249     }
 250
 251     static const int kDefaultChunkCapacity = 64 * 1024; //!< Default chunk capacity.
 252
 253     //! Chunk header for perpending to each chunk.
 254     /*! Chunks are stored as a singly linked list.
 255     */
 256     struct ChunkHeader {
 257         size_t capacity;    //!< Capacity of the chunk in bytes (excluding the header itself).
 258         size_t size;        //!< Current size of allocated memory in bytes.
 259         ChunkHeader *next;  //!< Next chunk in the linked list.
 260     };
 261
 262     ChunkHeader *chunkHead_;    //!< Head of the chunk linked-list. Only the head chunk serves allocation.
 263     size_t chunk_capacity_;     //!< The minimum capacity of chunk when they are allocated.
 264     void *userBuffer_;          //!< User supplied buffer.
 265     BaseAllocator* baseAllocator_;  //!< base allocator for allocating memory chunks.
 266     BaseAllocator* ownBaseAllocator_;   //!< base allocator created by this object.
 267 };
 268
 269 RAPIDJSON_NAMESPACE_END
 270
 271 #endif // RAPIDJSON_ENCODINGS_H_