slot_order16.h

Go to the documentation of this file.

#pragma once

 
#include <array>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
 
namespace pixie::experimental {

class SlotOrder16 {
 public:
  static constexpr std::size_t capacity = 16;
  explicit SlotOrder16(std::size_t count = 0) noexcept
      : order_(0xfedcba9876543210ULL & mask(unsigned(count * 4))),
        occupied_(std::uint16_t(mask(unsigned(count)))),
        count_(std::uint8_t(count)) {
    assert(count <= 16);
  }

  std::size_t size() const noexcept { return count_; }

  unsigned operator[](std::size_t index) const noexcept {
    assert(index < size());
    return unsigned((order_ >> (4 * index)) & 15);
  }

  std::uint16_t occupied() const noexcept { return occupied_; }

  bool valid() const noexcept {
    if (size() > capacity) {
      return false;
    }
    unsigned seen = 0;
    for (std::size_t i = 0; i < size(); ++i) {
      const auto bit = 1u << (*this)[i];
      if (seen & bit) {
        return false;
      }
      seen |= bit;
    }
    return seen == occupied_;
  }

  std::size_t rotate_children(std::array<void*, capacity>&,
                              std::size_t left,
                              std::size_t right,
                              std::size_t distance) noexcept {
    rotate_left(left, right, distance);
    return 0;
  }

  void rotate_left(std::size_t left,
                   std::size_t right,
                   std::size_t distance) noexcept {
    assert(left <= right && right <= size());
    const auto length = right - left;
    if (length == 0 || (distance %= length) == 0) {
      return;
    }
    const auto bits = unsigned(4 * length);
    const auto shift = unsigned(4 * left);
    const auto region_mask = mask(bits);
    const auto region = (order_ >> shift) & region_mask;
    const auto rotated =
        (region >> (4 * distance)) | (region << (4 * (length - distance)));
    order_ =
        (order_ & ~(region_mask << shift)) | ((rotated & region_mask) << shift);
  }

  unsigned insert(std::size_t position) noexcept {
    assert(position <= size() && size() < 16);
    const auto slot =
        unsigned(std::countr_zero(unsigned(std::uint16_t(~occupied_))));
    order_ |= std::uint64_t(slot) << (4 * count_);
    occupied_ |= std::uint16_t(1u << slot);
    ++count_;
    rotate_left(position, size(), size() - position - 1);
    return slot;
  }

  unsigned erase(std::size_t position) noexcept {
    assert(position < size());
    const auto slot = (*this)[position];
    rotate_left(position, size(), 1);
    --count_;
    order_ &= mask(unsigned(4 * count_));
    occupied_ &= std::uint16_t(~(1u << slot));
    return slot;
  }
 
 private:
  static constexpr std::uint64_t mask(unsigned bits) noexcept {
    return bits >= 64 ? ~std::uint64_t{0} : (std::uint64_t{1} << bits) - 1;
  }
  std::uint64_t order_;
  std::uint16_t occupied_;
  std::uint8_t count_;
};
 
}  // namespace pixie::experimental