1 // Tencent is pleased to support the open source community by making RapidJSON available.
3 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
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
8 // http://opensource.org/licenses/MIT
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.
15 #ifndef RAPIDJSON_INTERNAL_STACK_H_
16 #define RAPIDJSON_INTERNAL_STACK_H_
18 #include "../allocators.h"
21 #if defined(__clang__)
23 RAPIDJSON_DIAG_OFF(c++98-compat)
26 RAPIDJSON_NAMESPACE_BEGIN
29 ///////////////////////////////////////////////////////////////////////////////
32 //! A type-unsafe stack for storing different types of data.
33 /*! \tparam Allocator Allocator for allocating stack memory.
35 template <typename Allocator>
38 // Optimization note: Do not allocate memory for stack_ in constructor.
39 // Do it lazily when first Push() -> Expand() -> Resize().
40 Stack(Allocator* allocator, size_t stackCapacity) : allocator_(allocator), ownAllocator_(0), stack_(0), stackTop_(0), stackEnd_(0), initialCapacity_(stackCapacity) {
43 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS
45 : allocator_(rhs.allocator_),
46 ownAllocator_(rhs.ownAllocator_),
48 stackTop_(rhs.stackTop_),
49 stackEnd_(rhs.stackEnd_),
50 initialCapacity_(rhs.initialCapacity_)
53 rhs.ownAllocator_ = 0;
57 rhs.initialCapacity_ = 0;
65 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS
66 Stack& operator=(Stack&& rhs) {
71 allocator_ = rhs.allocator_;
72 ownAllocator_ = rhs.ownAllocator_;
74 stackTop_ = rhs.stackTop_;
75 stackEnd_ = rhs.stackEnd_;
76 initialCapacity_ = rhs.initialCapacity_;
79 rhs.ownAllocator_ = 0;
83 rhs.initialCapacity_ = 0;
89 void Swap(Stack& rhs) RAPIDJSON_NOEXCEPT {
90 internal::Swap(allocator_, rhs.allocator_);
91 internal::Swap(ownAllocator_, rhs.ownAllocator_);
92 internal::Swap(stack_, rhs.stack_);
93 internal::Swap(stackTop_, rhs.stackTop_);
94 internal::Swap(stackEnd_, rhs.stackEnd_);
95 internal::Swap(initialCapacity_, rhs.initialCapacity_);
98 void Clear() { stackTop_ = stack_; }
102 // If the stack is empty, completely deallocate the memory.
103 Allocator::Free(stack_);
112 // Optimization note: try to minimize the size of this function for force inline.
113 // Expansion is run very infrequently, so it is moved to another (probably non-inline) function.
115 RAPIDJSON_FORCEINLINE void Reserve(size_t count = 1) {
116 // Expand the stack if needed
117 if (RAPIDJSON_UNLIKELY(stackTop_ + sizeof(T) * count > stackEnd_))
122 RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) {
124 return PushUnsafe<T>(count);
128 RAPIDJSON_FORCEINLINE T* PushUnsafe(size_t count = 1) {
129 RAPIDJSON_ASSERT(stackTop_ + sizeof(T) * count <= stackEnd_);
130 T* ret = reinterpret_cast<T*>(stackTop_);
131 stackTop_ += sizeof(T) * count;
136 T* Pop(size_t count) {
137 RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T));
138 stackTop_ -= count * sizeof(T);
139 return reinterpret_cast<T*>(stackTop_);
144 RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
145 return reinterpret_cast<T*>(stackTop_ - sizeof(T));
149 const T* Top() const {
150 RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
151 return reinterpret_cast<T*>(stackTop_ - sizeof(T));
155 T* End() { return reinterpret_cast<T*>(stackTop_); }
158 const T* End() const { return reinterpret_cast<T*>(stackTop_); }
161 T* Bottom() { return reinterpret_cast<T*>(stack_); }
164 const T* Bottom() const { return reinterpret_cast<T*>(stack_); }
166 bool HasAllocator() const {
167 return allocator_ != 0;
170 Allocator& GetAllocator() {
171 RAPIDJSON_ASSERT(allocator_);
175 bool Empty() const { return stackTop_ == stack_; }
176 size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
177 size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }
181 void Expand(size_t count) {
182 // Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity.
186 ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator());
187 newCapacity = initialCapacity_;
189 newCapacity = GetCapacity();
190 newCapacity += (newCapacity + 1) / 2;
192 size_t newSize = GetSize() + sizeof(T) * count;
193 if (newCapacity < newSize)
194 newCapacity = newSize;
199 void Resize(size_t newCapacity) {
200 const size_t size = GetSize(); // Backup the current size
201 stack_ = static_cast<char*>(allocator_->Realloc(stack_, GetCapacity(), newCapacity));
202 stackTop_ = stack_ + size;
203 stackEnd_ = stack_ + newCapacity;
207 Allocator::Free(stack_);
208 RAPIDJSON_DELETE(ownAllocator_); // Only delete if it is owned by the stack
211 // Prohibit copy constructor & assignment operator.
213 Stack& operator=(const Stack&);
215 Allocator* allocator_;
216 Allocator* ownAllocator_;
220 size_t initialCapacity_;
223 } // namespace internal
224 RAPIDJSON_NAMESPACE_END
226 #if defined(__clang__)
230 #endif // RAPIDJSON_STACK_H_