pointer_block.h

#pragma once
 
#include <pixie/storage/aligned.h>
 
#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <cstddef>
#include <limits>
#include <span>
#include <stdexcept>
#include <utility>

namespace pixie::permutations::detail {

template <class T, std::size_t StorageBits = 2048>
class PointerBlock {
  static_assert(StorageBits % (sizeof(CacheLine) * CHAR_BIT) == 0);
  static_assert(StorageBits / CHAR_BIT >=
                2 * sizeof(std::size_t) + sizeof(const T*));
 
 public:
  using value_type = const T*;
  static constexpr std::size_t capacity =
      (StorageBits / CHAR_BIT - 2 * sizeof(std::size_t)) / sizeof(value_type);
  static_assert(capacity <= std::numeric_limits<std::size_t>::max() / 2);
  PointerBlock() noexcept = default;
  explicit PointerBlock(std::span<const value_type> input) {
    if (input.size() > capacity) {
      throw std::length_error("PointerBlock: capacity");
    }
    std::copy(input.begin(), input.end(), storage_.values.begin());
    storage_.length = input.size();
  }
  std::size_t size() const noexcept { return storage_.length; }
  value_type operator[](std::size_t i) const noexcept {
    assert(i < size());
    return storage_.values[(storage_.origin + i) % size()];
  }
  void set_at(std::size_t i, value_type value) noexcept {
    assert(i < size());
    slot(i) = value;
  }
  void rotate_left(std::size_t left,
                   std::size_t right,
                   std::size_t distance) noexcept {
    assert(left <= right && right <= size());
    const auto n = right - left;
    if (n == 0 || (distance %= n) == 0) {
      return;
    }
    if (left == 0 && right == size()) {
      storage_.origin = (storage_.origin + distance) % size();
      return;
    }
    auto reverse = [&](std::size_t begin, std::size_t end) {
      while (begin < end && begin < --end) {
        std::swap(slot(begin++), slot(end));
      }
    };
    reverse(left, left + distance);
    reverse(left + distance, right);
    reverse(left, right);
  }
  void insert_at(std::size_t offset, value_type value) noexcept {
    assert(offset <= size() && size() < capacity);
    std::array<value_type, capacity> scratch;
    for (std::size_t i = 0; i < offset; ++i) {
      scratch[i] = (*this)[i];
    }
    scratch[offset] = value;
    const auto n = size();
    for (std::size_t i = offset; i < n; ++i) {
      scratch[i + 1] = (*this)[i];
    }
    std::copy_n(scratch.begin(), n + 1, storage_.values.begin());
    storage_.length = n + 1;
    storage_.origin = 0;
  }
  void redistribute(PointerBlock& right, std::size_t left_count) noexcept {
    const auto total = size() + right.size();
    assert(this != &right && left_count <= capacity && left_count <= total &&
           total - left_count <= capacity);
    std::array<value_type, 2 * capacity> scratch;
    for (std::size_t i = 0; i < size(); ++i) {
      scratch[i] = (*this)[i];
    }
    for (std::size_t i = 0; i < right.size(); ++i) {
      scratch[size() + i] = right[i];
    }
    std::copy_n(scratch.begin(), left_count, storage_.values.begin());
    std::copy_n(scratch.begin() + left_count, total - left_count,
                right.storage_.values.begin());
    storage_.length = left_count;
    right.storage_.length = total - left_count;
    storage_.origin = right.storage_.origin = 0;
  }
 
 private:
  struct alignas(CacheLine) Storage {
    std::size_t length = 0;
    std::size_t origin = 0;
    std::array<value_type, capacity> values{};
  };
  static_assert(sizeof(Storage) == StorageBits / CHAR_BIT);
  Storage storage_;
 
  value_type& slot(std::size_t i) noexcept {
    return storage_.values[(storage_.origin + i) % storage_.length];
  }
};
 
}  // namespace pixie::permutations::detail