allocators.h

00001 // Tencent is pleased to support the open source community by making RapidJSON available.
00002 // 
00003 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
00004 //
00005 // Licensed under the MIT License (the "License"); you may not use this file except
00006 // in compliance with the License. You may obtain a copy of the License at
00007 //
00008 // http://opensource.org/licenses/MIT
00009 //
00010 // Unless required by applicable law or agreed to in writing, software distributed 
00011 // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR 
00012 // CONDITIONS OF ANY KIND, either express or implied. See the License for the 
00013 // specific language governing permissions and limitations under the License.
00014 
00015 #ifndef RAPIDJSON_ALLOCATORS_H_
00016 #define RAPIDJSON_ALLOCATORS_H_
00017 
00018 #include "rapidjson.h"
00019 
00020 RAPIDJSON_NAMESPACE_BEGIN
00021 
00022 ///////////////////////////////////////////////////////////////////////////////
00023 // Allocator
00024 
00025 /*! \class rapidjson::Allocator
00026     \brief Concept for allocating, resizing and freeing memory block.
00027     
00028     Note that Malloc() and Realloc() are non-static but Free() is static.
00029     
00030     So if an allocator need to support Free(), it needs to put its pointer in 
00031     the header of memory block.
00032 
00033 \code
00034 concept Allocator {
00035     static const bool kNeedFree;    //!< Whether this allocator needs to call Free().
00036 
00037     // Allocate a memory block.
00038     // \param size of the memory block in bytes.
00039     // \returns pointer to the memory block.
00040     void* Malloc(size_t size);
00041 
00042     // Resize a memory block.
00043     // \param originalPtr The pointer to current memory block. Null pointer is permitted.
00044     // \param originalSize The current size in bytes. (Design issue: since some allocator may not book-keep this, explicitly pass to it can save memory.)
00045     // \param newSize the new size in bytes.
00046     void* Realloc(void* originalPtr, size_t originalSize, size_t newSize);
00047 
00048     // Free a memory block.
00049     // \param pointer to the memory block. Null pointer is permitted.
00050     static void Free(void *ptr);
00051 };
00052 \endcode
00053 */
00054 
00055 ///////////////////////////////////////////////////////////////////////////////
00056 // CrtAllocator
00057 
00058 //! C-runtime library allocator.
00059 /*! This class is just wrapper for standard C library memory routines.
00060     \note implements Allocator concept
00061 */
00062 class CrtAllocator {
00063 public:
00064     static const bool kNeedFree = true;
00065     void* Malloc(size_t size) { 
00066         if (size) //  behavior of malloc(0) is implementation defined.
00067             return std::malloc(size);
00068         else
00069             return NULL; // standardize to returning NULL.
00070     }
00071     void* Realloc(void* originalPtr, size_t originalSize, size_t newSize) {
00072         (void)originalSize;
00073         if (newSize == 0) {
00074             std::free(originalPtr);
00075             return NULL;
00076         }
00077         return std::realloc(originalPtr, newSize);
00078     }
00079     static void Free(void *ptr) { std::free(ptr); }
00080 };
00081 
00082 ///////////////////////////////////////////////////////////////////////////////
00083 // MemoryPoolAllocator
00084 
00085 //! Default memory allocator used by the parser and DOM.
00086 /*! This allocator allocate memory blocks from pre-allocated memory chunks. 
00087 
00088     It does not free memory blocks. And Realloc() only allocate new memory.
00089 
00090     The memory chunks are allocated by BaseAllocator, which is CrtAllocator by default.
00091 
00092     User may also supply a buffer as the first chunk.
00093 
00094     If the user-buffer is full then additional chunks are allocated by BaseAllocator.
00095 
00096     The user-buffer is not deallocated by this allocator.
00097 
00098     \tparam BaseAllocator the allocator type for allocating memory chunks. Default is CrtAllocator.
00099     \note implements Allocator concept
00100 */
00101 template <typename BaseAllocator = CrtAllocator>
00102 class MemoryPoolAllocator {
00103 public:
00104     static const bool kNeedFree = false;    //!< Tell users that no need to call Free() with this allocator. (concept Allocator)
00105 
00106     //! Constructor with chunkSize.
00107     /*! \param chunkSize The size of memory chunk. The default is kDefaultChunkSize.
00108         \param baseAllocator The allocator for allocating memory chunks.
00109     */
00110     MemoryPoolAllocator(size_t chunkSize = kDefaultChunkCapacity, BaseAllocator* baseAllocator = 0) : 
00111         chunkHead_(0), chunk_capacity_(chunkSize), userBuffer_(0), baseAllocator_(baseAllocator), ownBaseAllocator_(0)
00112     {
00113     }
00114 
00115     //! Constructor with user-supplied buffer.
00116     /*! The user buffer will be used firstly. When it is full, memory pool allocates new chunk with chunk size.
00117 
00118         The user buffer will not be deallocated when this allocator is destructed.
00119 
00120         \param buffer User supplied buffer.
00121         \param size Size of the buffer in bytes. It must at least larger than sizeof(ChunkHeader).
00122         \param chunkSize The size of memory chunk. The default is kDefaultChunkSize.
00123         \param baseAllocator The allocator for allocating memory chunks.
00124     */
00125     MemoryPoolAllocator(void *buffer, size_t size, size_t chunkSize = kDefaultChunkCapacity, BaseAllocator* baseAllocator = 0) :
00126         chunkHead_(0), chunk_capacity_(chunkSize), userBuffer_(buffer), baseAllocator_(baseAllocator), ownBaseAllocator_(0)
00127     {
00128         RAPIDJSON_ASSERT(buffer != 0);
00129         RAPIDJSON_ASSERT(size > sizeof(ChunkHeader));
00130         chunkHead_ = reinterpret_cast<ChunkHeader*>(buffer);
00131         chunkHead_->capacity = size - sizeof(ChunkHeader);
00132         chunkHead_->size = 0;
00133         chunkHead_->next = 0;
00134     }
00135 
00136     //! Destructor.
00137     /*! This deallocates all memory chunks, excluding the user-supplied buffer.
00138     */
00139     ~MemoryPoolAllocator() {
00140         Clear();
00141         RAPIDJSON_DELETE(ownBaseAllocator_);
00142     }
00143 
00144     //! Deallocates all memory chunks, excluding the user-supplied buffer.
00145     void Clear() {
00146         while (chunkHead_ && chunkHead_ != userBuffer_) {
00147             ChunkHeader* next = chunkHead_->next;
00148             baseAllocator_->Free(chunkHead_);
00149             chunkHead_ = next;
00150         }
00151         if (chunkHead_ && chunkHead_ == userBuffer_)
00152             chunkHead_->size = 0; // Clear user buffer
00153     }
00154 
00155     //! Computes the total capacity of allocated memory chunks.
00156     /*! \return total capacity in bytes.
00157     */
00158     size_t Capacity() const {
00159         size_t capacity = 0;
00160         for (ChunkHeader* c = chunkHead_; c != 0; c = c->next)
00161             capacity += c->capacity;
00162         return capacity;
00163     }
00164 
00165     //! Computes the memory blocks allocated.
00166     /*! \return total used bytes.
00167     */
00168     size_t Size() const {
00169         size_t size = 0;
00170         for (ChunkHeader* c = chunkHead_; c != 0; c = c->next)
00171             size += c->size;
00172         return size;
00173     }
00174 
00175     //! Allocates a memory block. (concept Allocator)
00176     void* Malloc(size_t size) {
00177         if (!size)
00178             return NULL;
00179 
00180         size = RAPIDJSON_ALIGN(size);
00181         if (chunkHead_ == 0 || chunkHead_->size + size > chunkHead_->capacity)
00182             if (!AddChunk(chunk_capacity_ > size ? chunk_capacity_ : size))
00183                 return NULL;
00184 
00185         void *buffer = reinterpret_cast<char *>(chunkHead_) + RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + chunkHead_->size;
00186         chunkHead_->size += size;
00187         return buffer;
00188     }
00189 
00190     //! Resizes a memory block (concept Allocator)
00191     void* Realloc(void* originalPtr, size_t originalSize, size_t newSize) {
00192         if (originalPtr == 0)
00193             return Malloc(newSize);
00194 
00195         if (newSize == 0)
00196             return NULL;
00197 
00198         originalSize = RAPIDJSON_ALIGN(originalSize);
00199         newSize = RAPIDJSON_ALIGN(newSize);
00200 
00201         // Do not shrink if new size is smaller than original
00202         if (originalSize >= newSize)
00203             return originalPtr;
00204 
00205         // Simply expand it if it is the last allocation and there is sufficient space
00206         if (originalPtr == reinterpret_cast<char *>(chunkHead_) + RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + chunkHead_->size - originalSize) {
00207             size_t increment = static_cast<size_t>(newSize - originalSize);
00208             if (chunkHead_->size + increment <= chunkHead_->capacity) {
00209                 chunkHead_->size += increment;
00210                 return originalPtr;
00211             }
00212         }
00213 
00214         // Realloc process: allocate and copy memory, do not free original buffer.
00215         if (void* newBuffer = Malloc(newSize)) {
00216             if (originalSize)
00217                 std::memcpy(newBuffer, originalPtr, originalSize);
00218             return newBuffer;
00219         }
00220         else
00221             return NULL;
00222     }
00223 
00224     //! Frees a memory block (concept Allocator)
00225     static void Free(void *ptr) { (void)ptr; } // Do nothing
00226 
00227 private:
00228     //! Copy constructor is not permitted.
00229     MemoryPoolAllocator(const MemoryPoolAllocator& rhs) /* = delete */;
00230     //! Copy assignment operator is not permitted.
00231     MemoryPoolAllocator& operator=(const MemoryPoolAllocator& rhs) /* = delete */;
00232 
00233     //! Creates a new chunk.
00234     /*! \param capacity Capacity of the chunk in bytes.
00235         \return true if success.
00236     */
00237     bool AddChunk(size_t capacity) {
00238         if (!baseAllocator_)
00239             ownBaseAllocator_ = baseAllocator_ = RAPIDJSON_NEW(BaseAllocator());
00240         if (ChunkHeader* chunk = reinterpret_cast<ChunkHeader*>(baseAllocator_->Malloc(RAPIDJSON_ALIGN(sizeof(ChunkHeader)) + capacity))) {
00241             chunk->capacity = capacity;
00242             chunk->size = 0;
00243             chunk->next = chunkHead_;
00244             chunkHead_ =  chunk;
00245             return true;
00246         }
00247         else
00248             return false;
00249     }
00250 
00251     static const int kDefaultChunkCapacity = 64 * 1024; //!< Default chunk capacity.
00252 
00253     //! Chunk header for perpending to each chunk.
00254     /*! Chunks are stored as a singly linked list.
00255     */
00256     struct ChunkHeader {
00257         size_t capacity;    //!< Capacity of the chunk in bytes (excluding the header itself).
00258         size_t size;        //!< Current size of allocated memory in bytes.
00259         ChunkHeader *next;  //!< Next chunk in the linked list.
00260     };
00261 
00262     ChunkHeader *chunkHead_;    //!< Head of the chunk linked-list. Only the head chunk serves allocation.
00263     size_t chunk_capacity_;     //!< The minimum capacity of chunk when they are allocated.
00264     void *userBuffer_;          //!< User supplied buffer.
00265     BaseAllocator* baseAllocator_;  //!< base allocator for allocating memory chunks.
00266     BaseAllocator* ownBaseAllocator_;   //!< base allocator created by this object.
00267 };
00268 
00269 RAPIDJSON_NAMESPACE_END
00270 
00271 #endif // RAPIDJSON_ENCODINGS_H_