immer_sequence.h

Go to the documentation of this file.

#pragma once

 
#include <pixie/permutable_sequence.h>
 
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <immer/flex_vector.hpp>
#include <immer/flex_vector_transient.hpp>
#include <limits>
#include <stdexcept>
#include <type_traits>
#include <utility>
 
namespace pixie {

template <std::copy_constructible T = std::uint64_t,
          class HeapPolicy = immer::default_heap_policy>
class ImmerPermutableSequence
    : public PermutableSequenceBase<ImmerPermutableSequence<T, HeapPolicy>,
                                    T,
                                    T> {
  using Base = PermutableSequenceBase<ImmerPermutableSequence, T, T>;
  friend Base;
  using Policy = immer::memory_policy<HeapPolicy,
                                      immer::default_refcount_policy,
                                      immer::default_lock_policy>;
  using Vector = immer::flex_vector<T, Policy>;
  using Tree = std::remove_cvref_t<decltype(std::declval<Vector>().impl())>;
  using Node = typename Tree::node_t;
  static_assert(Node::keep_headroom);
  static_assert(alignof(T) <= alignof(std::max_align_t));
 
 public:
  static constexpr std::size_t fanout = std::size_t{1} << Vector::bits;
  static constexpr std::size_t leaf_capacity = std::size_t{1}
                                               << Vector::bits_leaf;

  ImmerPermutableSequence() noexcept = default;
  ImmerPermutableSequence(const ImmerPermutableSequence&) = delete;
  ImmerPermutableSequence& operator=(const ImmerPermutableSequence&) = delete;
  ImmerPermutableSequence(ImmerPermutableSequence&& other) noexcept
      : values_(std::exchange(other.values_, Vector{})) {}

  ImmerPermutableSequence& operator=(ImmerPermutableSequence&& other) noexcept {
    if (this != &other) {
      values_ = std::exchange(other.values_, Vector{});
    }
    return *this;
  }

  struct MemoryUsage {
    std::size_t blocks = 0;
    std::size_t nodes = 0;
    std::size_t block_bytes = 0;
    std::size_t node_bytes = 0;
    std::size_t total_bytes = sizeof(ImmerPermutableSequence);
  };

  MemoryUsage memory_usage() const noexcept {
    MemoryUsage result;
    if (!values_.empty()) {
      const auto& tree = values_.impl();
      const auto tail_offset = tree.tail_offset();
      if (tail_offset != 0) {
        count_tree(tree.root, tree.shift, tail_offset, result);
      }
      ++result.blocks;
      add(result.block_bytes, Node::max_sizeof_leaf);
    }
    add(result.total_bytes, result.block_bytes);
    add(result.total_bytes, result.node_bytes);
    return result;
  }
 
 private:
  template <std::ranges::input_range Range>
    requires std::
        constructible_from<T, std::ranges::range_rvalue_reference_t<Range>>
      static ImmerPermutableSequence from_range_impl(Range&& range) {
    auto transient = Vector{}.transient();
    auto it = std::ranges::begin(range);
    const auto end = std::ranges::end(range);
    for (; it != end; ++it) {
      if (transient.size() == Vector::max_size()) {
        throw std::length_error("ImmerPermutableSequence: size limit");
      }
      transient.push_back(T(std::ranges::iter_move(it)));
    }
    ImmerPermutableSequence result;
    result.values_ = std::move(transient).persistent();
    return result;
  }
 
  std::size_t size_impl() const noexcept { return values_.size(); }
  T value_at_impl(std::size_t position) const {
    if (position >= values_.size()) {
      throw std::out_of_range("ImmerPermutableSequence: read position");
    }
    return values_[position];
  }
  void insert_at_impl(std::size_t position, T value) {
    if (position > values_.size()) {
      throw std::out_of_range("ImmerPermutableSequence: insert position");
    }
    check_growth(1);
    // Keep the original root for rollback; consume the temporary slices.
    values_ = values_.insert(position, std::move(value));
  }
  void rotate_left_impl(std::size_t left,
                        std::size_t right,
                        std::size_t distance) {
    if (left > right || right > values_.size()) {
      throw std::out_of_range("ImmerPermutableSequence: rotation range");
    }
    if (left == right || (distance %= right - left) == 0) {
      return;
    }
    auto prefix = values_.take(left);
    auto first = values_.drop(left).take(distance);
    auto second = values_.drop(left + distance).take(right - left - distance);
    auto suffix = values_.drop(right);
    auto result = std::move(prefix) + std::move(second) + std::move(first) +
                  std::move(suffix);
    values_ = std::move(result);
  }
  void merge_impl(ImmerPermutableSequence& donor) {
    if (this == &donor || donor.empty()) {
      return;
    }
    check_growth(donor.size());
    if (this->empty()) {
      *this = std::move(donor);
      return;
    }
    auto result = values_ + donor.values_;
    values_ = std::move(result);
    donor.values_ = Vector{};
  }
  std::size_t memory_usage_bytes_impl() const noexcept {
    return memory_usage().total_bytes;
  }
  void check_growth(std::size_t count) const {
    if (count > Vector::max_size() - values_.size()) {
      throw std::length_error("ImmerPermutableSequence: size limit");
    }
  }
  static void add(std::size_t& total, std::size_t bytes) noexcept {
    const auto maximum = std::numeric_limits<std::size_t>::max();
    total = bytes > maximum - total ? maximum : total + bytes;
  }
  static void count_tree(Node* node,
                         unsigned shift,
                         std::size_t size,
                         MemoryUsage& result) noexcept {
    if (shift < Vector::bits_leaf) {
      ++result.blocks;
      add(result.block_bytes, Node::max_sizeof_leaf);
      return;
    }
    ++result.nodes;
    const auto* relaxed = node->relaxed();
    add(result.node_bytes,
        relaxed ? Node::max_sizeof_inner_r : Node::max_sizeof_inner);
    if (relaxed && !Node::embed_relaxed) {
      add(result.node_bytes, Node::max_sizeof_relaxed);
    }
    const auto child_capacity = std::size_t{1} << shift;
    const auto count =
        relaxed ? relaxed->d.count : 1 + (size - 1) / child_capacity;
    std::size_t prefix = 0;
    for (std::size_t i = 0; i < count; ++i) {
      const auto end = relaxed ? relaxed->d.sizes[i]
                               : std::min(size, prefix + child_capacity);
      if (shift == Vector::bits_leaf) {
        ++result.blocks;
        add(result.block_bytes, Node::max_sizeof_leaf);
      } else {
        count_tree(node->inner()[i], shift - Vector::bits, end - prefix,
                   result);
      }
      prefix = end;
    }
  }
 
  Vector values_;
};
}  // namespace pixie