stack.h

Engine/source/persistence/rapidjson/internal/stack.h

More...

Classes:

Namespaces:

Detailed Description

  1
  2// Tencent is pleased to support the open source community by making RapidJSON available.
  3// 
  4// Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
  5//
  6// Licensed under the MIT License (the "License"); you may not use this file except
  7// in compliance with the License. You may obtain a copy of the License at
  8//
  9// http://opensource.org/licenses/MIT
 10//
 11// Unless required by applicable law or agreed to in writing, software distributed 
 12// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR 
 13// CONDITIONS OF ANY KIND, either express or implied. See the License for the 
 14// specific language governing permissions and limitations under the License.
 15
 16#ifndef RAPIDJSON_INTERNAL_STACK_H_
 17#define RAPIDJSON_INTERNAL_STACK_H_
 18
 19#include "../allocators.h"
 20#include "swap.h"
 21#include <cstddef>
 22
 23#if defined(__clang__)
 24RAPIDJSON_DIAG_PUSH
 25RAPIDJSON_DIAG_OFF(c++98-compat)
 26#endif
 27
 28RAPIDJSON_NAMESPACE_BEGIN
 29namespace internal {
 30
 31///////////////////////////////////////////////////////////////////////////////
 32// Stack
 33
 34//! A type-unsafe stack for storing different types of data.
 35/*! \tparam Allocator Allocator for allocating stack memory.
 36*/
 37template <typename Allocator>
 38class Stack {
 39public:
 40    // Optimization note: Do not allocate memory for stack_ in constructor.
 41    // Do it lazily when first Push() -> Expand() -> Resize().
 42    Stack(Allocator* allocator, size_t stackCapacity) : allocator_(allocator), ownAllocator_(0), stack_(0), stackTop_(0), stackEnd_(0), initialCapacity_(stackCapacity) {
 43    }
 44
 45#if RAPIDJSON_HAS_CXX11_RVALUE_REFS
 46    Stack(Stack&& rhs)
 47        : allocator_(rhs.allocator_),
 48          ownAllocator_(rhs.ownAllocator_),
 49          stack_(rhs.stack_),
 50          stackTop_(rhs.stackTop_),
 51          stackEnd_(rhs.stackEnd_),
 52          initialCapacity_(rhs.initialCapacity_)
 53    {
 54        rhs.allocator_ = 0;
 55        rhs.ownAllocator_ = 0;
 56        rhs.stack_ = 0;
 57        rhs.stackTop_ = 0;
 58        rhs.stackEnd_ = 0;
 59        rhs.initialCapacity_ = 0;
 60    }
 61#endif
 62
 63    ~Stack() {
 64        Destroy();
 65    }
 66
 67#if RAPIDJSON_HAS_CXX11_RVALUE_REFS
 68    Stack& operator=(Stack&& rhs) {
 69        if (&rhs != this)
 70        {
 71            Destroy();
 72
 73            allocator_ = rhs.allocator_;
 74            ownAllocator_ = rhs.ownAllocator_;
 75            stack_ = rhs.stack_;
 76            stackTop_ = rhs.stackTop_;
 77            stackEnd_ = rhs.stackEnd_;
 78            initialCapacity_ = rhs.initialCapacity_;
 79
 80            rhs.allocator_ = 0;
 81            rhs.ownAllocator_ = 0;
 82            rhs.stack_ = 0;
 83            rhs.stackTop_ = 0;
 84            rhs.stackEnd_ = 0;
 85            rhs.initialCapacity_ = 0;
 86        }
 87        return *this;
 88    }
 89#endif
 90
 91    void Swap(Stack& rhs) RAPIDJSON_NOEXCEPT {
 92        internal::Swap(allocator_, rhs.allocator_);
 93        internal::Swap(ownAllocator_, rhs.ownAllocator_);
 94        internal::Swap(stack_, rhs.stack_);
 95        internal::Swap(stackTop_, rhs.stackTop_);
 96        internal::Swap(stackEnd_, rhs.stackEnd_);
 97        internal::Swap(initialCapacity_, rhs.initialCapacity_);
 98    }
 99
100    void Clear() { stackTop_ = stack_; }
101
102    void ShrinkToFit() { 
103        if (Empty()) {
104            // If the stack is empty, completely deallocate the memory.
105            Allocator::Free(stack_); // NOLINT (+clang-analyzer-unix.Malloc)
106            stack_ = 0;
107            stackTop_ = 0;
108            stackEnd_ = 0;
109        }
110        else
111            Resize(GetSize());
112    }
113
114    // Optimization note: try to minimize the size of this function for force inline.
115    // Expansion is run very infrequently, so it is moved to another (probably non-inline) function.
116    template<typename T>
117    RAPIDJSON_FORCEINLINE void Reserve(size_t count = 1) {
118         // Expand the stack if needed
119        if (RAPIDJSON_UNLIKELY(static_cast<std::ptrdiff_t>(sizeof(T) * count) > (stackEnd_ - stackTop_)))
120            Expand<T>(count);
121    }
122
123    template<typename T>
124    RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) {
125        Reserve<T>(count);
126        return PushUnsafe<T>(count);
127    }
128
129    template<typename T>
130    RAPIDJSON_FORCEINLINE T* PushUnsafe(size_t count = 1) {
131        RAPIDJSON_ASSERT(stackTop_);
132        RAPIDJSON_ASSERT(static_cast<std::ptrdiff_t>(sizeof(T) * count) <= (stackEnd_ - stackTop_));
133        T* ret = reinterpret_cast<T*>(stackTop_);
134        stackTop_ += sizeof(T) * count;
135        return ret;
136    }
137
138    template<typename T>
139    T* Pop(size_t count) {
140        RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T));
141        stackTop_ -= count * sizeof(T);
142        return reinterpret_cast<T*>(stackTop_);
143    }
144
145    template<typename T>
146    T* Top() { 
147        RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
148        return reinterpret_cast<T*>(stackTop_ - sizeof(T));
149    }
150
151    template<typename T>
152    const T* Top() const {
153        RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
154        return reinterpret_cast<T*>(stackTop_ - sizeof(T));
155    }
156
157    template<typename T>
158    T* End() { return reinterpret_cast<T*>(stackTop_); }
159
160    template<typename T>
161    const T* End() const { return reinterpret_cast<T*>(stackTop_); }
162
163    template<typename T>
164    T* Bottom() { return reinterpret_cast<T*>(stack_); }
165
166    template<typename T>
167    const T* Bottom() const { return reinterpret_cast<T*>(stack_); }
168
169    bool HasAllocator() const {
170        return allocator_ != 0;
171    }
172
173    Allocator& GetAllocator() {
174        RAPIDJSON_ASSERT(allocator_);
175        return *allocator_;
176    }
177
178    bool Empty() const { return stackTop_ == stack_; }
179    size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
180    size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }
181
182private:
183    template<typename T>
184    void Expand(size_t count) {
185        // Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity.
186        size_t newCapacity;
187        if (stack_ == 0) {
188            if (!allocator_)
189                ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator)();
190            newCapacity = initialCapacity_;
191        } else {
192            newCapacity = GetCapacity();
193            newCapacity += (newCapacity + 1) / 2;
194        }
195        size_t newSize = GetSize() + sizeof(T) * count;
196        if (newCapacity < newSize)
197            newCapacity = newSize;
198
199        Resize(newCapacity);
200    }
201
202    void Resize(size_t newCapacity) {
203        const size_t size = GetSize();  // Backup the current size
204        stack_ = static_cast<char*>(allocator_->Realloc(stack_, GetCapacity(), newCapacity));
205        stackTop_ = stack_ + size;
206        stackEnd_ = stack_ + newCapacity;
207    }
208
209    void Destroy() {
210        Allocator::Free(stack_);
211        RAPIDJSON_DELETE(ownAllocator_); // Only delete if it is owned by the stack
212    }
213
214    // Prohibit copy constructor & assignment operator.
215    Stack(const Stack&);
216    Stack& operator=(const Stack&);
217
218    Allocator* allocator_;
219    Allocator* ownAllocator_;
220    char *stack_;
221    char *stackTop_;
222    char *stackEnd_;
223    size_t initialCapacity_;
224};
225
226} // namespace internal
227RAPIDJSON_NAMESPACE_END
228
229#if defined(__clang__)
230RAPIDJSON_DIAG_POP
231#endif
232
233#endif // RAPIDJSON_STACK_H_
234