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_ + 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>
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>
143    T* Top() { 
144        RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
145        return reinterpret_cast<T*>(stackTop_ - sizeof(T));
146    }
147
148    template<typename T>
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>
155    T* End() { return reinterpret_cast<T*>(stackTop_); }
156
157    template<typename T>
158    const T* End() const { return reinterpret_cast<T*>(stackTop_); }
159
160    template<typename T>
161    T* Bottom() { return reinterpret_cast<T*>(stack_); }
162
163    template<typename T>
164    const T* Bottom() const { return reinterpret_cast<T*>(stack_); }
165
166    bool HasAllocator() const {
167        return allocator_ != 0;
168    }
169
170    Allocator& GetAllocator() {
171        RAPIDJSON_ASSERT(allocator_);
172        return *allocator_;
173    }
174
175    bool Empty() const { return stackTop_ == stack_; }
176    size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
177    size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }
178
179private:
180    template<typename T>
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
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
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
224RAPIDJSON_NAMESPACE_END
225
226#if defined(__clang__)
227RAPIDJSON_DIAG_POP
228#endif
229
230#endif // RAPIDJSON_STACK_H_