载入中...
搜索中...
未找到
stack.h
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__)
22RAPIDJSON_DIAG_PUSH
23RAPIDJSON_DIAG_OFF(c++98-compat)
24#endif
25
26RAPIDJSON_NAMESPACE_BEGIN
27namespace 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*/
35template <typename Allocator>
36class Stack {
37public:
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) {
41 }
42
43#if RAPIDJSON_HAS_CXX11_RVALUE_REFS
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
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
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
98 void Clear() { stackTop_ = stack_; }
99
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_);
130 RAPIDJSON_ASSERT(stackTop_ + sizeof(T) * count <= stackEnd_);
131 T* ret = reinterpret_cast<T*>(stackTop_);
132 stackTop_ += sizeof(T) * count;
133 return ret;
134 }
135
136 template<typename T>
137 T* Pop(size_t count) {
138 RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T));
139 stackTop_ -= count * sizeof(T);
140 return reinterpret_cast<T*>(stackTop_);
141 }
142
143 template<typename T>
144 T* Top() {
145 RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
146 return reinterpret_cast<T*>(stackTop_ - sizeof(T));
147 }
148
149 template<typename T>
150 const T* Top() const {
151 RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
152 return reinterpret_cast<T*>(stackTop_ - sizeof(T));
153 }
154
155 template<typename T>
156 T* End() { return reinterpret_cast<T*>(stackTop_); }
157
158 template<typename T>
159 const T* End() const { return reinterpret_cast<T*>(stackTop_); }
160
161 template<typename T>
162 T* Bottom() { return reinterpret_cast<T*>(stack_); }
163
164 template<typename T>
165 const T* Bottom() const { return reinterpret_cast<T*>(stack_); }
166
167 bool HasAllocator() const {
168 return allocator_ != 0;
169 }
170
171 Allocator& GetAllocator() {
172 RAPIDJSON_ASSERT(allocator_);
173 return *allocator_;
174 }
175
176 bool Empty() const { return stackTop_ == stack_; }
177 size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
178 size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }
179
180private:
181 template<typename T>
182 void Expand(size_t count) {
183 // Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity.
184 size_t newCapacity;
185 if (stack_ == 0) {
186 if (!allocator_)
187 ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator)();
188 newCapacity = initialCapacity_;
189 } else {
190 newCapacity = GetCapacity();
191 newCapacity += (newCapacity + 1) / 2;
192 }
193 size_t newSize = GetSize() + sizeof(T) * count;
194 if (newCapacity < newSize)
195 newCapacity = newSize;
196
197 Resize(newCapacity);
198 }
199
200 void Resize(size_t newCapacity) {
201 const size_t size = GetSize(); // Backup the current size
202 stack_ = static_cast<char*>(allocator_->Realloc(stack_, GetCapacity(), newCapacity));
203 stackTop_ = stack_ + size;
204 stackEnd_ = stack_ + newCapacity;
205 }
206
207 void Destroy() {
208 Allocator::Free(stack_);
209 RAPIDJSON_DELETE(ownAllocator_); // Only delete if it is owned by the stack
210 }
211
212 // Prohibit copy constructor & assignment operator.
213 Stack(const Stack&);
214 Stack& operator=(const Stack&);
215
216 Allocator* allocator_;
217 Allocator* ownAllocator_;
218 char *stack_;
219 char *stackTop_;
220 char *stackEnd_;
221 size_t initialCapacity_;
222};
223
224} // namespace internal
225RAPIDJSON_NAMESPACE_END
226
227#if defined(__clang__)
228RAPIDJSON_DIAG_POP
229#endif
230
231#endif // RAPIDJSON_STACK_H_
Concept for allocating, resizing and freeing memory block.
#define RAPIDJSON_UNLIKELY(x)
Compiler branching hint for expression with low probability to be true.
Definition rapidjson.h:481
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition rapidjson.h:411
#define RAPIDJSON_DELETE(x)
! customization point for global delete
Definition rapidjson.h:603
#define RAPIDJSON_NEW(TypeName)
! customization point for global new
Definition rapidjson.h:599