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_INTERNAL_STACK_H_ 16 #define RAPIDJSON_INTERNAL_STACK_H_ 17 18 #include "../rapidjson.h" 19 #include "swap.h" 20 21 RAPIDJSON_NAMESPACE_BEGIN 22 namespace internal { 23 24 /////////////////////////////////////////////////////////////////////////////// 25 // Stack 26 27 //! A type-unsafe stack for storing different types of data. 28 /*! \tparam Allocator Allocator for allocating stack memory. 29 */ 30 template <typename Allocator> 31 class Stack { 32 public: 33 // Optimization note: Do not allocate memory for stack_ in constructor. 34 // Do it lazily when first Push() -> Expand() -> Resize(). 35 Stack(Allocator* allocator, size_t stackCapacity) : allocator_(allocator), ownAllocator_(0), stack_(0), stackTop_(0), stackEnd_(0), initialCapacity_(stackCapacity) { 36 RAPIDJSON_ASSERT(stackCapacity > 0); 37 } 38 39 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS 40 Stack(Stack&& rhs) 41 : allocator_(rhs.allocator_), 42 ownAllocator_(rhs.ownAllocator_), 43 stack_(rhs.stack_), 44 stackTop_(rhs.stackTop_), 45 stackEnd_(rhs.stackEnd_), 46 initialCapacity_(rhs.initialCapacity_) 47 { 48 rhs.allocator_ = 0; 49 rhs.ownAllocator_ = 0; 50 rhs.stack_ = 0; 51 rhs.stackTop_ = 0; 52 rhs.stackEnd_ = 0; 53 rhs.initialCapacity_ = 0; 54 } 55 #endif 56 57 ~Stack() { 58 Destroy(); 59 } 60 61 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS 62 Stack& operator=(Stack&& rhs) { 63 if (&rhs != this) 64 { 65 Destroy(); 66 67 allocator_ = rhs.allocator_; 68 ownAllocator_ = rhs.ownAllocator_; 69 stack_ = rhs.stack_; 70 stackTop_ = rhs.stackTop_; 71 stackEnd_ = rhs.stackEnd_; 72 initialCapacity_ = rhs.initialCapacity_; 73 74 rhs.allocator_ = 0; 75 rhs.ownAllocator_ = 0; 76 rhs.stack_ = 0; 77 rhs.stackTop_ = 0; 78 rhs.stackEnd_ = 0; 79 rhs.initialCapacity_ = 0; 80 } 81 return *this; 82 } 83 #endif 84 85 void Swap(Stack& rhs) RAPIDJSON_NOEXCEPT { 86 internal::Swap(allocator_, rhs.allocator_); 87 internal::Swap(ownAllocator_, rhs.ownAllocator_); 88 internal::Swap(stack_, rhs.stack_); 89 internal::Swap(stackTop_, rhs.stackTop_); 90 internal::Swap(stackEnd_, rhs.stackEnd_); 91 internal::Swap(initialCapacity_, rhs.initialCapacity_); 92 } 93 94 void Clear() { stackTop_ = stack_; } 95 96 void ShrinkToFit() { 97 if (Empty()) { 98 // If the stack is empty, completely deallocate the memory. 99 Allocator::Free(stack_); 100 stack_ = 0; 101 stackTop_ = 0; 102 stackEnd_ = 0; 103 } 104 else 105 Resize(GetSize()); 106 } 107 108 // Optimization note: try to minimize the size of this function for force inline. 109 // Expansion is run very infrequently, so it is moved to another (probably non-inline) function. 110 template<typename T> 111 RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) { 112 // Expand the stack if needed 113 if (stackTop_ + sizeof(T) * count >= stackEnd_) 114 Expand<T>(count); 115 116 T* ret = reinterpret_cast<T*>(stackTop_); 117 stackTop_ += sizeof(T) * count; 118 return ret; 119 } 120 121 template<typename T> 122 T* Pop(size_t count) { 123 RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T)); 124 stackTop_ -= count * sizeof(T); 125 return reinterpret_cast<T*>(stackTop_); 126 } 127 128 template<typename T> 129 T* Top() { 130 RAPIDJSON_ASSERT(GetSize() >= sizeof(T)); 131 return reinterpret_cast<T*>(stackTop_ - sizeof(T)); 132 } 133 134 template<typename T> 135 T* Bottom() { return (T*)stack_; } 136 137 bool HasAllocator() const { 138 return allocator_ != 0; 139 } 140 141 Allocator& GetAllocator() { 142 RAPIDJSON_ASSERT(allocator_); 143 return *allocator_; 144 } 145 bool Empty() const { return stackTop_ == stack_; } 146 size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); } 147 size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); } 148 149 private: 150 template<typename T> 151 void Expand(size_t count) { 152 // Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity. 153 size_t newCapacity; 154 if (stack_ == 0) { 155 if (!allocator_) 156 ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator()); 157 newCapacity = initialCapacity_; 158 } else { 159 newCapacity = GetCapacity(); 160 newCapacity += (newCapacity + 1) / 2; 161 } 162 size_t newSize = GetSize() + sizeof(T) * count; 163 if (newCapacity < newSize) 164 newCapacity = newSize; 165 166 Resize(newCapacity); 167 } 168 169 void Resize(size_t newCapacity) { 170 const size_t size = GetSize(); // Backup the current size 171 stack_ = (char*)allocator_->Realloc(stack_, GetCapacity(), newCapacity); 172 stackTop_ = stack_ + size; 173 stackEnd_ = stack_ + newCapacity; 174 } 175 176 void Destroy() { 177 Allocator::Free(stack_); 178 RAPIDJSON_DELETE(ownAllocator_); // Only delete if it is owned by the stack 179 } 180 181 // Prohibit copy constructor & assignment operator. 182 Stack(const Stack&); 183 Stack& operator=(const Stack&); 184 185 Allocator* allocator_; 186 Allocator* ownAllocator_; 187 char *stack_; 188 char *stackTop_; 189 char *stackEnd_; 190 size_t initialCapacity_; 191 }; 192 193 } // namespace internal 194 RAPIDJSON_NAMESPACE_END 195 196 #endif // RAPIDJSON_STACK_H_ 197
