stack.h

00001 // Tencent is pleased to support the open source community by making RapidJSON available.
00002 // 
00003 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
00004 //
00005 // Licensed under the MIT License (the "License"); you may not use this file except
00006 // in compliance with the License. You may obtain a copy of the License at
00007 //
00008 // http://opensource.org/licenses/MIT
00009 //
00010 // Unless required by applicable law or agreed to in writing, software distributed 
00011 // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR 
00012 // CONDITIONS OF ANY KIND, either express or implied. See the License for the 
00013 // specific language governing permissions and limitations under the License.
00014 
00015 #ifndef RAPIDJSON_INTERNAL_STACK_H_
00016 #define RAPIDJSON_INTERNAL_STACK_H_
00017 
00018 #include "../allocators.h"
00019 #include "swap.h"
00020 
00021 #if defined(__clang__)
00022 RAPIDJSON_DIAG_PUSH
00023 RAPIDJSON_DIAG_OFF(c++98-compat)
00024 #endif
00025 
00026 RAPIDJSON_NAMESPACE_BEGIN
00027 namespace internal {
00028 
00029 ///////////////////////////////////////////////////////////////////////////////
00030 // Stack
00031 
00032 //! A type-unsafe stack for storing different types of data.
00033 /*! \tparam Allocator Allocator for allocating stack memory.
00034 */
00035 template <typename Allocator>
00036 class Stack {
00037 public:
00038     // Optimization note: Do not allocate memory for stack_ in constructor.
00039     // Do it lazily when first Push() -> Expand() -> Resize().
00040     Stack(Allocator* allocator, size_t stackCapacity) : allocator_(allocator), ownAllocator_(0), stack_(0), stackTop_(0), stackEnd_(0), initialCapacity_(stackCapacity) {
00041     }
00042 
00043 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS
00044     Stack(Stack&& rhs)
00045         : allocator_(rhs.allocator_),
00046           ownAllocator_(rhs.ownAllocator_),
00047           stack_(rhs.stack_),
00048           stackTop_(rhs.stackTop_),
00049           stackEnd_(rhs.stackEnd_),
00050           initialCapacity_(rhs.initialCapacity_)
00051     {
00052         rhs.allocator_ = 0;
00053         rhs.ownAllocator_ = 0;
00054         rhs.stack_ = 0;
00055         rhs.stackTop_ = 0;
00056         rhs.stackEnd_ = 0;
00057         rhs.initialCapacity_ = 0;
00058     }
00059 #endif
00060 
00061     ~Stack() {
00062         Destroy();
00063     }
00064 
00065 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS
00066     Stack& operator=(Stack&& rhs) {
00067         if (&rhs != this)
00068         {
00069             Destroy();
00070 
00071             allocator_ = rhs.allocator_;
00072             ownAllocator_ = rhs.ownAllocator_;
00073             stack_ = rhs.stack_;
00074             stackTop_ = rhs.stackTop_;
00075             stackEnd_ = rhs.stackEnd_;
00076             initialCapacity_ = rhs.initialCapacity_;
00077 
00078             rhs.allocator_ = 0;
00079             rhs.ownAllocator_ = 0;
00080             rhs.stack_ = 0;
00081             rhs.stackTop_ = 0;
00082             rhs.stackEnd_ = 0;
00083             rhs.initialCapacity_ = 0;
00084         }
00085         return *this;
00086     }
00087 #endif
00088 
00089     void Swap(Stack& rhs) RAPIDJSON_NOEXCEPT {
00090         internal::Swap(allocator_, rhs.allocator_);
00091         internal::Swap(ownAllocator_, rhs.ownAllocator_);
00092         internal::Swap(stack_, rhs.stack_);
00093         internal::Swap(stackTop_, rhs.stackTop_);
00094         internal::Swap(stackEnd_, rhs.stackEnd_);
00095         internal::Swap(initialCapacity_, rhs.initialCapacity_);
00096     }
00097 
00098     void Clear() { stackTop_ = stack_; }
00099 
00100     void ShrinkToFit() { 
00101         if (Empty()) {
00102             // If the stack is empty, completely deallocate the memory.
00103             Allocator::Free(stack_);
00104             stack_ = 0;
00105             stackTop_ = 0;
00106             stackEnd_ = 0;
00107         }
00108         else
00109             Resize(GetSize());
00110     }
00111 
00112     // Optimization note: try to minimize the size of this function for force inline.
00113     // Expansion is run very infrequently, so it is moved to another (probably non-inline) function.
00114     template<typename T>
00115     RAPIDJSON_FORCEINLINE void Reserve(size_t count = 1) {
00116          // Expand the stack if needed
00117         if (RAPIDJSON_UNLIKELY(stackTop_ + sizeof(T) * count > stackEnd_))
00118             Expand<T>(count);
00119     }
00120 
00121     template<typename T>
00122     RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) {
00123         Reserve<T>(count);
00124         return PushUnsafe<T>(count);
00125     }
00126 
00127     template<typename T>
00128     RAPIDJSON_FORCEINLINE T* PushUnsafe(size_t count = 1) {
00129         RAPIDJSON_ASSERT(stackTop_ + sizeof(T) * count <= stackEnd_);
00130         T* ret = reinterpret_cast<T*>(stackTop_);
00131         stackTop_ += sizeof(T) * count;
00132         return ret;
00133     }
00134 
00135     template<typename T>
00136     T* Pop(size_t count) {
00137         RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T));
00138         stackTop_ -= count * sizeof(T);
00139         return reinterpret_cast<T*>(stackTop_);
00140     }
00141 
00142     template<typename T>
00143     T* Top() { 
00144         RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
00145         return reinterpret_cast<T*>(stackTop_ - sizeof(T));
00146     }
00147 
00148     template<typename T>
00149     const T* Top() const {
00150         RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
00151         return reinterpret_cast<T*>(stackTop_ - sizeof(T));
00152     }
00153 
00154     template<typename T>
00155     T* End() { return reinterpret_cast<T*>(stackTop_); }
00156 
00157     template<typename T>
00158     const T* End() const { return reinterpret_cast<T*>(stackTop_); }
00159 
00160     template<typename T>
00161     T* Bottom() { return reinterpret_cast<T*>(stack_); }
00162 
00163     template<typename T>
00164     const T* Bottom() const { return reinterpret_cast<T*>(stack_); }
00165 
00166     bool HasAllocator() const {
00167         return allocator_ != 0;
00168     }
00169 
00170     Allocator& GetAllocator() {
00171         RAPIDJSON_ASSERT(allocator_);
00172         return *allocator_;
00173     }
00174 
00175     bool Empty() const { return stackTop_ == stack_; }
00176     size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
00177     size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }
00178 
00179 private:
00180     template<typename T>
00181     void Expand(size_t count) {
00182         // Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity.
00183         size_t newCapacity;
00184         if (stack_ == 0) {
00185             if (!allocator_)
00186                 ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator());
00187             newCapacity = initialCapacity_;
00188         } else {
00189             newCapacity = GetCapacity();
00190             newCapacity += (newCapacity + 1) / 2;
00191         }
00192         size_t newSize = GetSize() + sizeof(T) * count;
00193         if (newCapacity < newSize)
00194             newCapacity = newSize;
00195 
00196         Resize(newCapacity);
00197     }
00198 
00199     void Resize(size_t newCapacity) {
00200         const size_t size = GetSize();  // Backup the current size
00201         stack_ = static_cast<char*>(allocator_->Realloc(stack_, GetCapacity(), newCapacity));
00202         stackTop_ = stack_ + size;
00203         stackEnd_ = stack_ + newCapacity;
00204     }
00205 
00206     void Destroy() {
00207         Allocator::Free(stack_);
00208         RAPIDJSON_DELETE(ownAllocator_); // Only delete if it is owned by the stack
00209     }
00210 
00211     // Prohibit copy constructor & assignment operator.
00212     Stack(const Stack&);
00213     Stack& operator=(const Stack&);
00214 
00215     Allocator* allocator_;
00216     Allocator* ownAllocator_;
00217     char *stack_;
00218     char *stackTop_;
00219     char *stackEnd_;
00220     size_t initialCapacity_;
00221 };
00222 
00223 } // namespace internal
00224 RAPIDJSON_NAMESPACE_END
00225 
00226 #if defined(__clang__)
00227 RAPIDJSON_DIAG_POP
00228 #endif
00229 
00230 #endif // RAPIDJSON_STACK_H_