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 "../allocators.h"
19 #include "swap.h"
20 
21 #if defined(__clang__)
22 RAPIDJSON_DIAG_PUSH
23 RAPIDJSON_DIAG_OFF(c++98-compat)
24 #endif
25 
26 RAPIDJSON_NAMESPACE_BEGIN
27 namespace internal {
28 
29 ///////////////////////////////////////////////////////////////////////////////
30 // Stack
31 
32 //! A type-unsafe stack for storing different types of data.
33 /*! \tparam Allocator Allocator for allocating stack memory.
34 */
35 template <typename Allocator>
36 class Stack {
37 public:
38     // Optimization note: Do not allocate memory for stack_ in constructor.
39     // Do it lazily when first Push() -> Expand() -> Resize().
Stack(Allocator * allocator,size_t stackCapacity)40     Stack(Allocator* allocator, size_t stackCapacity) : allocator_(allocator), ownAllocator_(0), stack_(0), stackTop_(0), stackEnd_(0), initialCapacity_(stackCapacity) {
41     }
42 
43 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS
Stack(Stack && rhs)44     Stack(Stack&& rhs)
45         : allocator_(rhs.allocator_),
46           ownAllocator_(rhs.ownAllocator_),
47           stack_(rhs.stack_),
48           stackTop_(rhs.stackTop_),
49           stackEnd_(rhs.stackEnd_),
50           initialCapacity_(rhs.initialCapacity_)
51     {
52         rhs.allocator_ = 0;
53         rhs.ownAllocator_ = 0;
54         rhs.stack_ = 0;
55         rhs.stackTop_ = 0;
56         rhs.stackEnd_ = 0;
57         rhs.initialCapacity_ = 0;
58     }
59 #endif
60 
~Stack()61     ~Stack() {
62         Destroy();
63     }
64 
65 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS
66     Stack& operator=(Stack&& rhs) {
67         if (&rhs != this)
68         {
69             Destroy();
70 
71             allocator_ = rhs.allocator_;
72             ownAllocator_ = rhs.ownAllocator_;
73             stack_ = rhs.stack_;
74             stackTop_ = rhs.stackTop_;
75             stackEnd_ = rhs.stackEnd_;
76             initialCapacity_ = rhs.initialCapacity_;
77 
78             rhs.allocator_ = 0;
79             rhs.ownAllocator_ = 0;
80             rhs.stack_ = 0;
81             rhs.stackTop_ = 0;
82             rhs.stackEnd_ = 0;
83             rhs.initialCapacity_ = 0;
84         }
85         return *this;
86     }
87 #endif
88 
Swap(Stack & rhs)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_);
96     }
97 
Clear()98     void Clear() { stackTop_ = stack_; }
99 
ShrinkToFit()100     void ShrinkToFit() {
101         if (Empty()) {
102             // If the stack is empty, completely deallocate the memory.
103             Allocator::Free(stack_);
104             stack_ = 0;
105             stackTop_ = 0;
106             stackEnd_ = 0;
107         }
108         else
109             Resize(GetSize());
110     }
111 
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.
114     template<typename T>
115     RAPIDJSON_FORCEINLINE void Reserve(size_t count = 1) {
116          // Expand the stack if needed
117         if (RAPIDJSON_UNLIKELY(stackTop_ + sizeof(T) * count > stackEnd_))
118             Expand<T>(count);
119     }
120 
121     template<typename T>
122     RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) {
123         Reserve<T>(count);
124         return PushUnsafe<T>(count);
125     }
126 
127     template<typename T>
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;
132         return ret;
133     }
134 
135     template<typename T>
Pop(size_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_);
140     }
141 
142     template<typename T>
Top()143     T* Top() {
144         RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
145         return reinterpret_cast<T*>(stackTop_ - sizeof(T));
146     }
147 
148     template<typename T>
Top()149     const T* Top() const {
150         RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
151         return reinterpret_cast<T*>(stackTop_ - sizeof(T));
152     }
153 
154     template<typename T>
End()155     T* End() { return reinterpret_cast<T*>(stackTop_); }
156 
157     template<typename T>
End()158     const T* End() const { return reinterpret_cast<T*>(stackTop_); }
159 
160     template<typename T>
Bottom()161     T* Bottom() { return reinterpret_cast<T*>(stack_); }
162 
163     template<typename T>
Bottom()164     const T* Bottom() const { return reinterpret_cast<T*>(stack_); }
165 
HasAllocator()166     bool HasAllocator() const {
167         return allocator_ != 0;
168     }
169 
GetAllocator()170     Allocator& GetAllocator() {
171         RAPIDJSON_ASSERT(allocator_);
172         return *allocator_;
173     }
174 
Empty()175     bool Empty() const { return stackTop_ == stack_; }
GetSize()176     size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
GetCapacity()177     size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }
178 
179 private:
180     template<typename T>
Expand(size_t count)181     void Expand(size_t count) {
182         // Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity.
183         size_t newCapacity;
184         if (stack_ == 0) {
185             if (!allocator_)
186                 ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator());
187             newCapacity = initialCapacity_;
188         } else {
189             newCapacity = GetCapacity();
190             newCapacity += (newCapacity + 1) / 2;
191         }
192         size_t newSize = GetSize() + sizeof(T) * count;
193         if (newCapacity < newSize)
194             newCapacity = newSize;
195 
196         Resize(newCapacity);
197     }
198 
Resize(size_t newCapacity)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;
204     }
205 
Destroy()206     void Destroy() {
207         Allocator::Free(stack_);
208         RAPIDJSON_DELETE(ownAllocator_); // Only delete if it is owned by the stack
209     }
210 
211     // Prohibit copy constructor & assignment operator.
212     Stack(const Stack&);
213     Stack& operator=(const Stack&);
214 
215     Allocator* allocator_;
216     Allocator* ownAllocator_;
217     char *stack_;
218     char *stackTop_;
219     char *stackEnd_;
220     size_t initialCapacity_;
221 };
222 
223 } // namespace internal
224 RAPIDJSON_NAMESPACE_END
225 
226 #if defined(__clang__)
227 RAPIDJSON_DIAG_POP
228 #endif
229 
230 #endif // RAPIDJSON_STACK_H_
231