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// 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*/
 62class CrtAllocator {
 63public:
 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*/
101template <typename BaseAllocator = CrtAllocator>
102class MemoryPoolAllocator {
103public:
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
227private:
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
269RAPIDJSON_NAMESPACE_END
270
271#endif // RAPIDJSON_ENCODINGS_H_