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"
#include <cstddef>

#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_);  // NOLINT (+clang-analyzer-unix.Malloc)
      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(static_cast<std::ptrdiff_t>(sizeof(T) * count) > (stackEnd_ - stackTop_)))
      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_);
    RAPIDJSON_ASSERT(static_cast<std::ptrdiff_t>(sizeof(T) * count) <= (stackEnd_ - stackTop_));
    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_