stack.h
1 // Copyright (C) 2011 Milo Yip
2 //
3 // Permission is hereby granted, free of charge, to any person obtaining a copy
4 // of this software and associated documentation files (the "Software"), to deal
5 // in the Software without restriction, including without limitation the rights
6 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7 // copies of the Software, and to permit persons to whom the Software is
8 // furnished to do so, subject to the following conditions:
9 //
10 // The above copyright notice and this permission notice shall be included in
11 // all copies or substantial portions of the Software.
12 //
13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19 // THE SOFTWARE.
20 
21 #ifndef RAPIDJSON_INTERNAL_STACK_H_
22 #define RAPIDJSON_INTERNAL_STACK_H_
23 
24 namespace rapidjson {
25 namespace internal {
26 
27 ///////////////////////////////////////////////////////////////////////////////
28 // Stack
29 
30 //! A type-unsafe stack for storing different types of data.
31 /*! \tparam Allocator Allocator for allocating stack memory.
32 */
33 template <typename Allocator>
34 class Stack {
35 public:
36  // Optimization note: Do not allocate memory for stack_ in constructor.
37  // Do it lazily when first Push() -> Expand() -> Resize().
38  Stack(Allocator* allocator, size_t stackCapacity) : allocator_(allocator), ownAllocator_(0), stack_(0), stackTop_(0), stackEnd_(0), initialCapacity_(stackCapacity) {
39  RAPIDJSON_ASSERT(stackCapacity > 0);
40  }
41 
42 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS
43  Stack(Stack&& rhs)
44  : allocator_(rhs.allocator_),
45  ownAllocator_(rhs.ownAllocator_),
46  stack_(rhs.stack_),
47  stackTop_(rhs.stackTop_),
48  stackEnd_(rhs.stackEnd_),
49  initialCapacity_(rhs.initialCapacity_)
50  {
51  rhs.allocator_ = 0;
52  rhs.ownAllocator_ = 0;
53  rhs.stack_ = 0;
54  rhs.stackTop_ = 0;
55  rhs.stackEnd_ = 0;
56  rhs.initialCapacity_ = 0;
57  }
58 #endif
59 
60  ~Stack() {
61  Destroy();
62  }
63 
64 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS
65  Stack& operator=(Stack&& rhs) {
66  if (&rhs != this)
67  {
68  Destroy();
69 
70  allocator_ = rhs.allocator_;
71  ownAllocator_ = rhs.ownAllocator_;
72  stack_ = rhs.stack_;
73  stackTop_ = rhs.stackTop_;
74  stackEnd_ = rhs.stackEnd_;
75  initialCapacity_ = rhs.initialCapacity_;
76 
77  rhs.allocator_ = 0;
78  rhs.ownAllocator_ = 0;
79  rhs.stack_ = 0;
80  rhs.stackTop_ = 0;
81  rhs.stackEnd_ = 0;
82  rhs.initialCapacity_ = 0;
83  }
84  return *this;
85  }
86 #endif
87 
88  void Clear() { stackTop_ = stack_; }
89 
90  void ShrinkToFit() {
91  if (Empty()) {
92  // If the stack is empty, completely deallocate the memory.
93  Allocator::Free(stack_);
94  stack_ = 0;
95  stackTop_ = 0;
96  stackEnd_ = 0;
97  }
98  else
99  Resize(GetSize());
100  }
101 
102  // Optimization note: try to minimize the size of this function for force inline.
103  // Expansion is run very infrequently, so it is moved to another (probably non-inline) function.
104  template<typename T>
105  RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) {
106  // Expand the stack if needed
107  if (stackTop_ + sizeof(T) * count >= stackEnd_)
108  Expand<T>(count);
109 
110  T* ret = reinterpret_cast<T*>(stackTop_);
111  stackTop_ += sizeof(T) * count;
112  return ret;
113  }
114 
115  template<typename T>
116  T* Pop(size_t count) {
117  RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T));
118  stackTop_ -= count * sizeof(T);
119  return reinterpret_cast<T*>(stackTop_);
120  }
121 
122  template<typename T>
123  T* Top() {
124  RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
125  return reinterpret_cast<T*>(stackTop_ - sizeof(T));
126  }
127 
128  template<typename T>
129  T* Bottom() { return (T*)stack_; }
130 
131  Allocator& GetAllocator() { return *allocator_; }
132  bool Empty() const { return stackTop_ == stack_; }
133  size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
134  size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }
135 
136 private:
137  template<typename T>
138  void Expand(size_t count) {
139  // Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity.
140  size_t newCapacity;
141  if (stack_ == 0) {
142  if (!allocator_)
143  ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator());
144  newCapacity = initialCapacity_;
145  } else {
146  newCapacity = GetCapacity();
147  newCapacity += (newCapacity + 1) / 2;
148  }
149  size_t newSize = GetSize() + sizeof(T) * count;
150  if (newCapacity < newSize)
151  newCapacity = newSize;
152 
153  Resize(newCapacity);
154  }
155 
156  void Resize(size_t newCapacity) {
157  const size_t size = GetSize(); // Backup the current size
158  stack_ = (char*)allocator_->Realloc(stack_, GetCapacity(), newCapacity);
159  stackTop_ = stack_ + size;
160  stackEnd_ = stack_ + newCapacity;
161  }
162 
163  void Destroy() {
164  Allocator::Free(stack_);
165  RAPIDJSON_DELETE(ownAllocator_); // Only delete if it is owned by the stack
166  }
167 
168  // Prohibit copy constructor & assignment operator.
169  Stack(const Stack&);
170  Stack& operator=(const Stack&);
171 
172  Allocator* allocator_;
173  Allocator* ownAllocator_;
174  char *stack_;
175  char *stackTop_;
176  char *stackEnd_;
177  size_t initialCapacity_;
178 };
179 
180 } // namespace internal
181 } // namespace rapidjson
182 
183 #endif // RAPIDJSON_STACK_H_
#define RAPIDJSON_NEW(x)
! customization point for global new
Definition: rapidjson.h:408
#define RAPIDJSON_DELETE(x)
! customization point for global delete
Definition: rapidjson.h:412
main RapidJSON namespace
Definition: rapidjson.h:241
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:269