freelist.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"
#include "internal/dynastic.hpp"
#include "internal/stack.hpp"
#include "internal/reallocator.hpp"

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable : 4189)
#endif

#include <boost/lockfree/stack.hpp>

namespace alb {
  inline namespace v_100 {
    template <bool Shared, class Allocator, size_t MinSize, size_t MaxSize, unsigned PoolSize,
      unsigned NumberOfBatchAllocations>
    class freelist_base {
      typename traits::type_switch < boost::lockfree::stack<void *, boost::lockfree::fixed_sized<true>,
        boost::lockfree::capacity<PoolSize >> ,
        internal::stack<void *, PoolSize>, Shared>::type root_;

      internal::dynastic<(MinSize == internal::DynasticDynamicSet ? internal::DynasticDynamicSet
        : MinSize),
        internal::DynasticDynamicSet> _lowerBound;
      internal::dynastic<(MaxSize == internal::DynasticDynamicSet ? internal::DynasticDynamicSet
        : MaxSize),
        internal::DynasticDynamicSet> _upperBound;


      Allocator allocator_;

    public:
      using allocator = Allocator;
      static constexpr unsigned pool_size = PoolSize;
      static constexpr unsigned number_of_batch_allocations = NumberOfBatchAllocations;
      static constexpr bool supports_truncated_deallocation = Allocator::supports_truncated_deallocation;
      static constexpr unsigned alignment = Allocator::alignment;

      freelist_base() noexcept
      {}

      freelist_base(size_t minSize, size_t maxSize) noexcept {
        _lowerBound.value(minSize);
        _upperBound.value(maxSize);
      }

      ~freelist_base() {
        void *curBlock = nullptr;
        while (root_.pop(curBlock)) {
          block oldBlock(curBlock, _upperBound.value());
          allocator_.deallocate(oldBlock);
        }
      }


      void set_min_max(size_t minSize, size_t maxSize) noexcept {
        assert(_lowerBound.value() == internal::DynasticUndefined);
        // "Changing the lower bound during after initialization is not wise!"

        assert(_upperBound.value() == internal::DynasticUndefined);
        // "Changing the upper bound during after initialization is not wise!"

        _lowerBound.value(minSize);
        _upperBound.value(maxSize);
      }

      size_t min_size() const noexcept {
        return _lowerBound.value();
      }

      size_t max_size() const noexcept {
        return _upperBound.value();
      }

      block allocate(size_t n) noexcept {
        block result;

        assert(_lowerBound.value() != ::std::numeric_limits<size_t>::max()); // "The lower bound was not initialized!");
        assert(_upperBound.value() != ::std::numeric_limits<size_t>::max()); // "The upper bound was not initialized!");

        if (_lowerBound.value() <= n && n <= _upperBound.value()) {
          void *freeBlock = nullptr;

          if (root_.pop(freeBlock)) {
            result.ptr = freeBlock;
            result.length = _upperBound.value();
            return result;
          }

          size_t blockSize = _upperBound.value();
          if (supports_truncated_deallocation) {
            // allocating in a bunch to gain of having the allocator code in the
            // cache
            auto batchAllocatedBlocks = allocator_.allocate(blockSize * NumberOfBatchAllocations);

            if (batchAllocatedBlocks) {
              // we use the very first block directly so we start at 1
              for (size_t i = 1; i < NumberOfBatchAllocations; i++) {
                if (!root_.push(static_cast<char *>(batchAllocatedBlocks.ptr) + i * blockSize)) {
                  assert(false);
                  alb::block oldBlock(static_cast<char *>(batchAllocatedBlocks.ptr) + i * blockSize,
                    blockSize);
                  allocator_.deallocate(oldBlock);
                }
              }
              // returning the first within block
              result.ptr = batchAllocatedBlocks.ptr;
              result.length = blockSize;
              return result;
            }
            result = allocator_.allocate(blockSize);
            return result;
          }
          for (size_t i = 0; i < NumberOfBatchAllocations - 1; i++) {
            result = allocator_.allocate(blockSize);
            if (!root_.push(result.ptr)) { // the list is full in the meantime, so we
                                      // exit early
              return result;
            }
          }
          result = allocator_.allocate(blockSize);
        }

        return result;
      }

      bool reallocate(block &b, size_t n) noexcept {
        if (internal::is_reallocation_handled_default(*this, b, n)) {
          return true;
        }
        return false;
      }

      bool owns(const block &b) const noexcept {
        return b && _lowerBound.value() <= b.length && b.length <= _upperBound.value();
      }

      void deallocate(block &b) noexcept {
        if (b && owns(b)) {
          if (root_.push(b.ptr)) {
            b.reset();
            return;
          }
          allocator_.deallocate(b);
        }
      }
    };

    template <class Allocator, size_t MinSize, size_t MaxSize, size_t PoolSize = 1024,
      size_t NumberOfBatchAllocations = 8>
    class shared_freelist : public freelist_base<true, Allocator, MinSize, MaxSize, PoolSize,
      NumberOfBatchAllocations> 
    {
    public:
      shared_freelist() noexcept
        : freelist_base<true, Allocator, MinSize, MaxSize, PoolSize, NumberOfBatchAllocations>()
      {}

      shared_freelist(size_t minSize, size_t maxSize) noexcept
        : freelist_base<true, Allocator, MinSize, MaxSize, PoolSize, NumberOfBatchAllocations>(
          minSize, maxSize)
      {}
    };

    template <class Allocator, size_t MinSize, size_t MaxSize, size_t PoolSize = 1024,
      size_t NumberOfBatchAllocations = 8>
    class freelist : public freelist_base<false, Allocator, MinSize, MaxSize, PoolSize,
      NumberOfBatchAllocations> 
    {
    public:
      freelist() noexcept
        : freelist_base<false, Allocator, MinSize, MaxSize, PoolSize, NumberOfBatchAllocations>()
      {}

      freelist(size_t minSize, size_t maxSize) noexcept
        : freelist_base<false, Allocator, MinSize, MaxSize, PoolSize, NumberOfBatchAllocations>(
          minSize, maxSize)
      {}
    };
  }

  using namespace v_100;
}

#ifdef _MSC_VER
#pragma warning(pop)
#endif