stack_allocator.hpp

//
// Copyright 2014 Felix Petriconi
//
// License: http://boost.org/LICENSE_1_0.txt, Boost License 1.0
//
// Authors: http://petriconi.net, Felix Petriconi
//
#pragma once

#include "allocator_base.hpp"

namespace alb {
  inline namespace v_100 {
    template <size_t MaxSize, size_t Alignment = 16> 
    
    class stack_allocator {
      alignas(Alignment) char _data[MaxSize];

      char *_p;

      bool is_last_used_block(const block &b) const noexcept {
        return (static_cast<char *>(b.ptr) + b.length == _p);
      }

    public:
      using allocator = stack_allocator;

      static const bool supports_truncated_deallocation = true;
      static const size_t max_size = MaxSize;
      static const size_t alignment = Alignment;

      stack_allocator() noexcept
        : _p(_data)
      {
      }

      block allocate(size_t n) noexcept {
        block result;

        if (n == 0) {
          return result;
        }

        const auto alignedLength = internal::round_to_alignment(Alignment, n);
        if (alignedLength + _p > _data + MaxSize) { // not enough memory left
          return result;
        }

        result.ptr = _p;
        result.length = alignedLength;

        _p += alignedLength;
        return result;
      }

      void deallocate(block &b) noexcept {
        if (!b) {
          return;
        }
        if (!owns(b)) {
          assert(false);
          return;
        }

        // If it was the most recent allocated MemoryBlock, then we can re-use the
        // memory. Otherwise this freed MemoryBlock is not available for further
        // allocations. Since all happens on the stack this is not a leak!
        if (is_last_used_block(b)) {
          _p = static_cast<char *>(b.ptr);
        }
        b.reset();
      }

      bool reallocate(block &b, size_t n) noexcept {
        if (b.length == n) {
          return true;
        }

        if (n == 0) {
          deallocate(b);
          return true;
        }

        if (!b) {
          b = allocate(n);
          return true;
        }

        const auto alignedLength = internal::round_to_alignment(Alignment, n);

        if (is_last_used_block(b)) {
          if (static_cast<char *>(b.ptr) + alignedLength <= _data + MaxSize) {
            b.length = alignedLength;
            _p = static_cast<char *>(b.ptr) + alignedLength;
            return true;
          }
          // out of memory
          return false;
        }
        if (b.length > n) {
          b.length = internal::round_to_alignment(Alignment, n);
          return true;
        }

        auto newBlock = allocate(alignedLength);
        // we cannot deallocate the old block, because it is in between used ones,
        //  so we have to "leak" here.
        if (newBlock) {
          internal::block_copy(b, newBlock);
          b = newBlock;
          return true;
        }
        return false;
      }

      bool expand(block &b, size_t delta) noexcept {
        if (delta == 0) {
          return true;
        }
        if (!b) {
          b = allocate(delta);
          return b.length != 0;
        }
        if (!is_last_used_block(b)) {
          return false;
        }
        auto alignedBytes = internal::round_to_alignment(Alignment, delta);
        if (_p + alignedBytes > _data + MaxSize) {
          return false;
        }
        _p += alignedBytes;
        b.length += alignedBytes;
        return true;
      }

      bool owns(const block &b) const noexcept {
        return b && (b.ptr >= _data && b.ptr < _data + MaxSize);
      }

      void deallocate_all() noexcept {
        _p = _data;
      }

    private:
      // disable move ctor and move assignment operators
      stack_allocator(stack_allocator &&) = delete;
      stack_allocator &operator=(stack_allocator &&) = delete;
      stack_allocator(const stack_allocator &) = delete;
      stack_allocator &operator=(const stack_allocator &) = delete;
      // disable heap allocation
      void *operator new(size_t) = delete;
      void *operator new[](size_t) = delete;
      void operator delete(void *) = delete;
      void operator delete[](void *) = delete;
      // disable address taking
      stack_allocator *operator&() = delete;
    };

    template <size_t MaxSize, size_t Alignment>
    const size_t stack_allocator<MaxSize, Alignment>::max_size;
    template <size_t MaxSize, size_t Alignment>
    const size_t stack_allocator<MaxSize, Alignment>::alignment;
  }
  using namespace v_100;
}