bucketizer.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/reallocator.hpp"
#include <cassert>

namespace alb {
  inline namespace v_100 {
    template <class Allocator, unsigned MinSize, unsigned MaxSize, unsigned StepSize>
    class bucketizer {
    public:
      static constexpr bool supports_truncated_deallocation = false;
      static constexpr unsigned alignment = Allocator::alignment;

      static_assert(MinSize < MaxSize, "MinSize must be smaller than MaxSize");
      static_assert((MaxSize - MinSize + 1) % StepSize == 0, "Incorrect ranges or step size!");

      static constexpr unsigned number_of_buckets = ((MaxSize - MinSize + 1) / StepSize);
      static constexpr unsigned max_size = MaxSize;
      static constexpr unsigned min_size = MinSize;
      static constexpr unsigned step_size = StepSize;

      using allocator = Allocator;

      Allocator _buckets[number_of_buckets];

      bucketizer() noexcept
      {
        for (size_t i = 0; i < number_of_buckets; i++) {
          _buckets[i].set_min_max(MinSize + i * StepSize, MinSize + (i + 1) * StepSize - 1);
        }
      }

      static constexpr size_t good_size(size_t n) noexcept {
        return (number_of_buckets - (max_size - n)/step_size + 1) * step_size;
      }

      block allocate(size_t n) noexcept
      {
        size_t i = 0;
        while (i < number_of_buckets) {
          if (_buckets[i].min_size() <= n && n <= _buckets[i].max_size()) {
            return _buckets[i].allocate(n);
          }
          ++i;
        }
        return{};
      }

      bool owns(const block &b) const noexcept
      {
        return b && (MinSize <= b.length && b.length <= MaxSize);
      }

      bool reallocate(block &b, size_t n) noexcept
      {
        if (n != 0 && (n < MinSize || n > MaxSize)) {
          return false;
        }

        if (internal::is_reallocation_handled_default(*this, b, n)) {
          return true;
        }

        assert(owns(b));

        const auto alignedLength = internal::round_to_alignment(StepSize, n);
        auto currentAllocator = find_matching_allocator(b.length);
        auto newAllocator = find_matching_allocator(alignedLength);

        if (currentAllocator == newAllocator) {
          return true;
        }

        return internal::reallocate_with_copy(*currentAllocator, *newAllocator, b, alignedLength);
      }

      void deallocate(block &b) noexcept
      {
        if (!b) {
          return;
        }
        if (!owns(b)) {
          assert(!"It is not wise to let me deallocate a foreign Block!");
          return;
        }

        auto currentAllocator = find_matching_allocator(b.length);
        currentAllocator->deallocate(b);
      }

      template <typename U = Allocator>
      typename std::enable_if<traits::has_deallocate_all<U>::value, void>::type
        deallocate_all() noexcept
      {
        for (auto &item : _buckets) {
          traits::AllDeallocator<U>::do_it(item);
        }
      }

    private:
      Allocator *find_matching_allocator(size_t n) noexcept
      {
        assert(MinSize <= n && n <= MaxSize);
        auto v = alb::internal::round_to_alignment(StepSize, n);
        return &_buckets[(v - MinSize) / StepSize];
      }
    };

    template <class Allocator, unsigned MinSize, unsigned MaxSize, unsigned StepSize>
    const unsigned bucketizer<Allocator, MinSize, MaxSize, StepSize>::number_of_buckets;
  }
  using namespace v_100;
}