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().
Stack(Allocator * allocator,size_t stackCapacity)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
Stack(Stack && rhs)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 
~Stack()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 
Swap(Stack & rhs)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 
Clear()94     void Clear() { stackTop_ = stack_; }
95 
ShrinkToFit()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>
Pop(size_t count)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>
Top()129     T* Top() {
130         RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
131         return reinterpret_cast<T*>(stackTop_ - sizeof(T));
132     }
133 
134     template<typename T>
Bottom()135     T* Bottom() { return (T*)stack_; }
136 
HasAllocator()137     bool HasAllocator() const {
138         return allocator_ != 0;
139     }
140 
GetAllocator()141     Allocator& GetAllocator() {
142         RAPIDJSON_ASSERT(allocator_);
143         return *allocator_;
144     }
Empty()145     bool Empty() const { return stackTop_ == stack_; }
GetSize()146     size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
GetCapacity()147     size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }
148 
149 private:
150     template<typename T>
Expand(size_t count)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 
Resize(size_t newCapacity)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 
Destroy()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