| // Copyright (C) 2011 Milo Yip |
| // |
| // Permission is hereby granted, free of charge, to any person obtaining a copy |
| // of this software and associated documentation files (the "Software"), to deal |
| // in the Software without restriction, including without limitation the rights |
| // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
| // copies of the Software, and to permit persons to whom the Software is |
| // furnished to do so, subject to the following conditions: |
| // |
| // The above copyright notice and this permission notice shall be included in |
| // all copies or substantial portions of the Software. |
| // |
| // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
| // THE SOFTWARE. |
| |
| #ifndef RAPIDJSON_INTERNAL_STACK_H_ |
| #define RAPIDJSON_INTERNAL_STACK_H_ |
| |
| RAPIDJSON_NAMESPACE_BEGIN |
| namespace internal { |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // Stack |
| |
| //! A type-unsafe stack for storing different types of data. |
| /*! \tparam Allocator Allocator for allocating stack memory. |
| */ |
| template <typename Allocator> |
| class Stack { |
| public: |
| // Optimization note: Do not allocate memory for stack_ in constructor. |
| // Do it lazily when first Push() -> Expand() -> Resize(). |
| Stack(Allocator* allocator, size_t stackCapacity) : allocator_(allocator), ownAllocator_(0), stack_(0), stackTop_(0), stackEnd_(0), initialCapacity_(stackCapacity) { |
| RAPIDJSON_ASSERT(stackCapacity > 0); |
| } |
| |
| #if RAPIDJSON_HAS_CXX11_RVALUE_REFS |
| Stack(Stack&& rhs) |
| : allocator_(rhs.allocator_), |
| ownAllocator_(rhs.ownAllocator_), |
| stack_(rhs.stack_), |
| stackTop_(rhs.stackTop_), |
| stackEnd_(rhs.stackEnd_), |
| initialCapacity_(rhs.initialCapacity_) |
| { |
| rhs.allocator_ = 0; |
| rhs.ownAllocator_ = 0; |
| rhs.stack_ = 0; |
| rhs.stackTop_ = 0; |
| rhs.stackEnd_ = 0; |
| rhs.initialCapacity_ = 0; |
| } |
| #endif |
| |
| ~Stack() { |
| Destroy(); |
| } |
| |
| #if RAPIDJSON_HAS_CXX11_RVALUE_REFS |
| Stack& operator=(Stack&& rhs) { |
| if (&rhs != this) |
| { |
| Destroy(); |
| |
| allocator_ = rhs.allocator_; |
| ownAllocator_ = rhs.ownAllocator_; |
| stack_ = rhs.stack_; |
| stackTop_ = rhs.stackTop_; |
| stackEnd_ = rhs.stackEnd_; |
| initialCapacity_ = rhs.initialCapacity_; |
| |
| rhs.allocator_ = 0; |
| rhs.ownAllocator_ = 0; |
| rhs.stack_ = 0; |
| rhs.stackTop_ = 0; |
| rhs.stackEnd_ = 0; |
| rhs.initialCapacity_ = 0; |
| } |
| return *this; |
| } |
| #endif |
| |
| void Clear() { stackTop_ = stack_; } |
| |
| void ShrinkToFit() { |
| if (Empty()) { |
| // If the stack is empty, completely deallocate the memory. |
| Allocator::Free(stack_); |
| stack_ = 0; |
| stackTop_ = 0; |
| stackEnd_ = 0; |
| } |
| else |
| Resize(GetSize()); |
| } |
| |
| // Optimization note: try to minimize the size of this function for force inline. |
| // Expansion is run very infrequently, so it is moved to another (probably non-inline) function. |
| template<typename T> |
| RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) { |
| // Expand the stack if needed |
| if (stackTop_ + sizeof(T) * count >= stackEnd_) |
| Expand<T>(count); |
| |
| T* ret = reinterpret_cast<T*>(stackTop_); |
| stackTop_ += sizeof(T) * count; |
| return ret; |
| } |
| |
| template<typename T> |
| T* Pop(size_t count) { |
| RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T)); |
| stackTop_ -= count * sizeof(T); |
| return reinterpret_cast<T*>(stackTop_); |
| } |
| |
| template<typename T> |
| T* Top() { |
| RAPIDJSON_ASSERT(GetSize() >= sizeof(T)); |
| return reinterpret_cast<T*>(stackTop_ - sizeof(T)); |
| } |
| |
| template<typename T> |
| T* Bottom() { return (T*)stack_; } |
| |
| Allocator& GetAllocator() { return *allocator_; } |
| bool Empty() const { return stackTop_ == stack_; } |
| size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); } |
| size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); } |
| |
| private: |
| template<typename T> |
| void Expand(size_t count) { |
| // Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity. |
| size_t newCapacity; |
| if (stack_ == 0) { |
| if (!allocator_) |
| ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator()); |
| newCapacity = initialCapacity_; |
| } else { |
| newCapacity = GetCapacity(); |
| newCapacity += (newCapacity + 1) / 2; |
| } |
| size_t newSize = GetSize() + sizeof(T) * count; |
| if (newCapacity < newSize) |
| newCapacity = newSize; |
| |
| Resize(newCapacity); |
| } |
| |
| void Resize(size_t newCapacity) { |
| const size_t size = GetSize(); // Backup the current size |
| stack_ = (char*)allocator_->Realloc(stack_, GetCapacity(), newCapacity); |
| stackTop_ = stack_ + size; |
| stackEnd_ = stack_ + newCapacity; |
| } |
| |
| void Destroy() { |
| Allocator::Free(stack_); |
| RAPIDJSON_DELETE(ownAllocator_); // Only delete if it is owned by the stack |
| } |
| |
| // Prohibit copy constructor & assignment operator. |
| Stack(const Stack&); |
| Stack& operator=(const Stack&); |
| |
| Allocator* allocator_; |
| Allocator* ownAllocator_; |
| char *stack_; |
| char *stackTop_; |
| char *stackEnd_; |
| size_t initialCapacity_; |
| }; |
| |
| } // namespace internal |
| RAPIDJSON_NAMESPACE_END |
| |
| #endif // RAPIDJSON_STACK_H_ |