stack.h

Go to the documentation of this file.

// Tencent is pleased to support the open source community by making RapidJSON available.
// 
// Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
//
// Licensed under the MIT License (the "License"); you may not use this file except
// in compliance with the License. You may obtain a copy of the License at
//
// http://opensource.org/licenses/MIT
//
// Unless required by applicable law or agreed to in writing, software distributed 
// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR 
// CONDITIONS OF ANY KIND, either express or implied. See the License for the 
// specific language governing permissions and limitations under the License.

#ifndef RAPIDJSON_INTERNAL_STACK_H_
#define RAPIDJSON_INTERNAL_STACK_H_

#include "../allocators.h"
#include "swap.h"

#if defined(__clang__)
RAPIDJSON_DIAG_PUSH
RAPIDJSON_DIAG_OFF(c++98-compat)
#endif

RAPIDJSON_NAMESPACE_BEGIN
namespace internal {

// Stack


template <typename Allocator>
class Stack {
public:
 // Optimization note: Do not allocate memory for stack_ in constructor.
 // Do it lazily when first Push() -> Expand() -> Resize().
 Stack(Allocator* allocator, size_t stackCapacity) : allocator_(allocator), ownAllocator_(0), stack_(0), stackTop_(0), stackEnd_(0), initialCapacity_(stackCapacity) {
 }

#if RAPIDJSON_HAS_CXX11_RVALUE_REFS
 Stack(Stack&& rhs)
 : allocator_(rhs.allocator_),
 ownAllocator_(rhs.ownAllocator_),
 stack_(rhs.stack_),
 stackTop_(rhs.stackTop_),
 stackEnd_(rhs.stackEnd_),
 initialCapacity_(rhs.initialCapacity_)
 {
 rhs.allocator_ = 0;
 rhs.ownAllocator_ = 0;
 rhs.stack_ = 0;
 rhs.stackTop_ = 0;
 rhs.stackEnd_ = 0;
 rhs.initialCapacity_ = 0;
 }
#endif

 ~Stack() {
 Destroy();
 }

#if RAPIDJSON_HAS_CXX11_RVALUE_REFS
 Stack& operator=(Stack&& rhs) {
 if (&rhs != this)
 {
 Destroy();

 allocator_ = rhs.allocator_;
 ownAllocator_ = rhs.ownAllocator_;
 stack_ = rhs.stack_;
 stackTop_ = rhs.stackTop_;
 stackEnd_ = rhs.stackEnd_;
 initialCapacity_ = rhs.initialCapacity_;

 rhs.allocator_ = 0;
 rhs.ownAllocator_ = 0;
 rhs.stack_ = 0;
 rhs.stackTop_ = 0;
 rhs.stackEnd_ = 0;
 rhs.initialCapacity_ = 0;
 }
 return *this;
 }
#endif

 void Swap(Stack& rhs) RAPIDJSON_NOEXCEPT {
 internal::Swap(allocator_, rhs.allocator_);
 internal::Swap(ownAllocator_, rhs.ownAllocator_);
 internal::Swap(stack_, rhs.stack_);
 internal::Swap(stackTop_, rhs.stackTop_);
 internal::Swap(stackEnd_, rhs.stackEnd_);
 internal::Swap(initialCapacity_, rhs.initialCapacity_);
 }

 void Clear() { stackTop_ = stack_; }

 void ShrinkToFit() { 
 if (Empty()) {
 // If the stack is empty, completely deallocate the memory.
 Allocator::Free(stack_);
 stack_ = 0;
 stackTop_ = 0;
 stackEnd_ = 0;
 }
 else
 Resize(GetSize());
 }

 // Optimization note: try to minimize the size of this function for force inline.
 // Expansion is run very infrequently, so it is moved to another (probably non-inline) function.
 template<typename T>
 RAPIDJSON_FORCEINLINE void Reserve(size_t count = 1) {
 // Expand the stack if needed
 if (RAPIDJSON_UNLIKELY(stackTop_ + sizeof(T) * count > stackEnd_))
 Expand<T>(count);
 }

 template<typename T>
 RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) {
 Reserve<T>(count);
 return PushUnsafe<T>(count);
 }

 template<typename T>
 RAPIDJSON_FORCEINLINE T* PushUnsafe(size_t count = 1) {
 RAPIDJSON_ASSERT(stackTop_ + sizeof(T) * count <= stackEnd_);
 T* ret = reinterpret_cast<T*>(stackTop_);
 stackTop_ += sizeof(T) * count;
 return ret;
 }

 template<typename T>
 T* Pop(size_t count) {
 RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T));
 stackTop_ -= count * sizeof(T);
 return reinterpret_cast<T*>(stackTop_);
 }

 template<typename T>
 T* Top() { 
 RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
 return reinterpret_cast<T*>(stackTop_ - sizeof(T));
 }

 template<typename T>
 const T* Top() const {
 RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
 return reinterpret_cast<T*>(stackTop_ - sizeof(T));
 }

 template<typename T>
 T* End() { return reinterpret_cast<T*>(stackTop_); }

 template<typename T>
 const T* End() const { return reinterpret_cast<T*>(stackTop_); }

 template<typename T>
 T* Bottom() { return reinterpret_cast<T*>(stack_); }

 template<typename T>
 const T* Bottom() const { return reinterpret_cast<T*>(stack_); }

 bool HasAllocator() const {
 return allocator_ != 0;
 }

 Allocator& GetAllocator() {
 RAPIDJSON_ASSERT(allocator_);
 return *allocator_;
 }

 bool Empty() const { return stackTop_ == stack_; }
 size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
 size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }

private:
 template<typename T>
 void Expand(size_t count) {
 // Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity.
 size_t newCapacity;
 if (stack_ == 0) {
 if (!allocator_)
 ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator());
 newCapacity = initialCapacity_;
 } else {
 newCapacity = GetCapacity();
 newCapacity += (newCapacity + 1) / 2;
 }
 size_t newSize = GetSize() + sizeof(T) * count;
 if (newCapacity < newSize)
 newCapacity = newSize;

 Resize(newCapacity);
 }

 void Resize(size_t newCapacity) {
 const size_t size = GetSize(); // Backup the current size
 stack_ = static_cast<char*>(allocator_->Realloc(stack_, GetCapacity(), newCapacity));
 stackTop_ = stack_ + size;
 stackEnd_ = stack_ + newCapacity;
 }

 void Destroy() {
 Allocator::Free(stack_);
 RAPIDJSON_DELETE(ownAllocator_); // Only delete if it is owned by the stack
 }

 // Prohibit copy constructor & assignment operator.
 Stack(const Stack&);
 Stack& operator=(const Stack&);

 Allocator* allocator_;
 Allocator* ownAllocator_;
 char *stack_;
 char *stackTop_;
 char *stackEnd_;
 size_t initialCapacity_;
};

} // namespace internal
RAPIDJSON_NAMESPACE_END

#if defined(__clang__)
RAPIDJSON_DIAG_POP
#endif

#endif // RAPIDJSON_STACK_H_