| // Tencent is pleased to support the open source community by making RapidJSON available. |
| // |
| // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved. |
| // |
| // Licensed under the MIT License (the "License"); you may not use this file except |
| // in compliance with the License. You may obtain a copy of the License at |
| // |
| // http://opensource.org/licenses/MIT |
| // |
| // Unless required by applicable law or agreed to in writing, software distributed |
| // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR |
| // CONDITIONS OF ANY KIND, either express or implied. See the License for the |
| // specific language governing permissions and limitations under the License. |
| |
| #ifndef RAPIDJSON_INTERNAL_STACK_H_ |
| #define RAPIDJSON_INTERNAL_STACK_H_ |
| |
| #include "../allocators.h" |
| #include "swap.h" |
| |
| #if defined(__clang__) |
| RAPIDJSON_DIAG_PUSH |
| RAPIDJSON_DIAG_OFF(c++98-compat) |
| #endif |
| |
| 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) { |
| } |
| |
| #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 Swap(Stack& rhs) RAPIDJSON_NOEXCEPT { |
| internal::Swap(allocator_, rhs.allocator_); |
| internal::Swap(ownAllocator_, rhs.ownAllocator_); |
| internal::Swap(stack_, rhs.stack_); |
| internal::Swap(stackTop_, rhs.stackTop_); |
| internal::Swap(stackEnd_, rhs.stackEnd_); |
| internal::Swap(initialCapacity_, rhs.initialCapacity_); |
| } |
| |
| 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 void Reserve(size_t count = 1) { |
| // Expand the stack if needed |
| if (RAPIDJSON_UNLIKELY(stackTop_ + sizeof(T) * count > stackEnd_)) |
| Expand<T>(count); |
| } |
| |
| template<typename T> |
| RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) { |
| Reserve<T>(count); |
| return PushUnsafe<T>(count); |
| } |
| |
| template<typename T> |
| RAPIDJSON_FORCEINLINE T* PushUnsafe(size_t count = 1) { |
| RAPIDJSON_ASSERT(stackTop_); |
| RAPIDJSON_ASSERT(stackTop_ + sizeof(T) * count <= stackEnd_); |
| 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> |
| const T* Top() const { |
| RAPIDJSON_ASSERT(GetSize() >= sizeof(T)); |
| return reinterpret_cast<T*>(stackTop_ - sizeof(T)); |
| } |
| |
| template<typename T> |
| T* End() { return reinterpret_cast<T*>(stackTop_); } |
| |
| template<typename T> |
| const T* End() const { return reinterpret_cast<T*>(stackTop_); } |
| |
| template<typename T> |
| T* Bottom() { return reinterpret_cast<T*>(stack_); } |
| |
| template<typename T> |
| const T* Bottom() const { return reinterpret_cast<T*>(stack_); } |
| |
| bool HasAllocator() const { |
| return allocator_ != 0; |
| } |
| |
| Allocator& GetAllocator() { |
| RAPIDJSON_ASSERT(allocator_); |
| 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_ = static_cast<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 |
| |
| #if defined(__clang__) |
| RAPIDJSON_DIAG_POP |
| #endif |
| |
| #endif // RAPIDJSON_STACK_H_ |