stack.h
Go to the documentation of this file.
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 
27 namespace internal {
28 
30 // Stack
31 
33 
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().
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) {
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() {
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 
180 private:
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_;
222 };
223 
224 } // namespace internal
226 
227 #if defined(__clang__)
228 RAPIDJSON_DIAG_POP
229 #endif
230 
231 #endif // RAPIDJSON_STACK_H_
char * stack_
Definition: stack.h:218
Allocator * ownAllocator_
Definition: stack.h:217
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:411
RAPIDJSON_FORCEINLINE T * PushUnsafe(size_t count=1)
Definition: stack.h:128
void Expand(size_t count)
Definition: stack.h:182
#define RAPIDJSON_NAMESPACE_END
provide custom rapidjson namespace (closing expression)
Definition: rapidjson.h:124
const T * Top() const
Definition: stack.h:150
void Resize(size_t newCapacity)
Definition: stack.h:200
A type-unsafe stack for storing different types of data.
Definition: stack.h:36
bool Empty() const
Definition: stack.h:176
void Clear()
Definition: stack.h:98
#define RAPIDJSON_NAMESPACE_BEGIN
provide custom rapidjson namespace (opening expression)
Definition: rapidjson.h:121
Stack & operator=(const Stack &)
RAPIDJSON_FORCEINLINE T * Push(size_t count=1)
Definition: stack.h:122
void Destroy()
Definition: stack.h:207
#define RAPIDJSON_NEW(TypeName)
! customization point for global new
Definition: rapidjson.h:599
char * stackEnd_
Definition: stack.h:220
T * End()
Definition: stack.h:156
RAPIDJSON_FORCEINLINE void Reserve(size_t count=1)
Definition: stack.h:115
size_t GetSize() const
Definition: stack.h:177
size_t initialCapacity_
Definition: stack.h:221
void Swap(T &a, T &b) RAPIDJSON_NOEXCEPT
Custom swap() to avoid dependency on C++ <algorithm> header.
Definition: swap.h:33
#define RAPIDJSON_DELETE(x)
! customization point for global delete
Definition: rapidjson.h:603
Allocator * allocator_
Definition: stack.h:216
Allocator & GetAllocator()
Definition: stack.h:171
T * Bottom()
Definition: stack.h:162
bool HasAllocator() const
Definition: stack.h:167
char * stackTop_
Definition: stack.h:219
void ShrinkToFit()
Definition: stack.h:100
#define T(x)
size_t GetCapacity() const
Definition: stack.h:178
Stack(Allocator *allocator, size_t stackCapacity)
Definition: stack.h:40
const T * End() const
Definition: stack.h:159
T * Pop(size_t count)
Definition: stack.h:137
#define RAPIDJSON_UNLIKELY(x)
Compiler branching hint for expression with low probability to be true.
Definition: rapidjson.h:481
T * Top()
Definition: stack.h:144
void Swap(Stack &rhs) RAPIDJSON_NOEXCEPT
Definition: stack.h:89
const T * Bottom() const
Definition: stack.h:165


choreo_rapidjson
Author(s):
autogenerated on Thu Jul 18 2019 03:59:09