cache.tcc

Go to the documentation of this file.

 
#if !defined(ULTRA_CACHE_H)
#  error "Don't include this file directly, include the specific .h instead"
#endif
 
#if !defined(ULTRA_CACHE_TCC)
#define      ULTRA_CACHE_TCC
 
namespace internal
{

[[nodiscard]] inline std::size_t div_ceil(std::size_t x, std::size_t y)
{
  // Most common architecture's divide instruction also includes remainder in
  // its result so this really needs only one division and would be very fast.
  return x/y + (x%y != 0);
 
  // `(x + y - 1) / y` is an alternative (but could overflow).
}
 
}  // namespace internal
 
template<Fitness F, std::size_t LOCK_GROUP_SIZE>
std::size_t cache<F, LOCK_GROUP_SIZE>::table_size(bitwidth n)
{
  Expects(n <= max_cache_bitwidth);
  return 1uz << n;
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
cache<F, LOCK_GROUP_SIZE>::cache(bitwidth n)
  : table_(table_size(n)),
    locks_(internal::div_ceil(table_.size(), LOCK_GROUP_SIZE)),
    k_mask(table_.size() - 1)
{
  Ensures(is_valid());
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
void cache<F, LOCK_GROUP_SIZE>::resize(bitwidth n)
{
  const std::size_t nelem(table_size(n));
 
  table_ = decltype(table_)(nelem);
  locks_ = decltype(locks_)(internal::div_ceil(nelem, LOCK_GROUP_SIZE));
  k_mask = nelem - 1;
 
  Ensures(is_valid());
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
std::size_t cache<F, LOCK_GROUP_SIZE>::index(const hash_t &h) const noexcept
{
  Expects(bits());
  return h.data[0] & k_mask;
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
std::size_t
cache<F, LOCK_GROUP_SIZE>::lock_index(std::size_t idx) const noexcept
{
  return idx / LOCK_GROUP_SIZE;
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
void cache<F, LOCK_GROUP_SIZE>::clear() noexcept
{
  if (++seal_ == 0)
  {
    for (auto &slot : table_)
      slot.seal = 0;
 
    seal_ = 1;
  }
 
  Ensures(is_valid());
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
void cache<F, LOCK_GROUP_SIZE>::clear(const hash_t &h)
{
  const auto idx(index(h));
  auto &mutex(locks_[lock_index(idx)]);
 
  std::lock_guard lock(mutex);
 
  // Invalidates the slot since the first valid value for seal is `1`.
  table_[idx].seal = 0;
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
std::optional<F> cache<F, LOCK_GROUP_SIZE>::find(const hash_t &h) const
{
  const auto idx(index(h));
  auto &mutex(locks_[lock_index(idx)]);
 
  {
    std::shared_lock lock(mutex);
 
    if (const slot &s(table_[idx]); s.seal == seal_ && s.hash == h)
      return s.fitness;
  }
 
  return std::nullopt;
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
void cache<F, LOCK_GROUP_SIZE>::insert(const hash_t &h, const F &fitness)
{
  const auto idx(index(h));
  auto &mutex(locks_[lock_index(idx)]);
 
  std::lock_guard lock(mutex);
 
  table_[idx] = {h, fitness, seal_};
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
bool cache<F, LOCK_GROUP_SIZE>::load(std::istream &in)
{
  clear();
 
  std::size_t n;
  if (!(in >> n))
    return false;
 
  while (n)
  {
    slot s;
    s.seal = seal_;
 
    if (!s.hash.load(in))
      return false;
    if (!ultra::load(in, &s.fitness))
      return false;
 
    table_[index(s.hash)] = s;
 
    --n;
  }
 
  return true;
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
bool cache<F, LOCK_GROUP_SIZE>::save(std::ostream &out) const
{
  std::size_t num(std::ranges::count_if(
                    table_, [this](const auto &s) {return s.seal == seal_;}));
 
  out << num << '\n';
 
  for (const auto &s : table_)
    if (s.seal == seal_)
    {
      if (!s.hash.save(out))
        return false;
      if (!ultra::save(out, s.fitness))
        return false;
 
      --num;
    }
 
  Expects(num == 0);
  return out.good();
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
bitwidth cache<F, LOCK_GROUP_SIZE>::bits() const
{
  return std::bit_width(k_mask);
}

template<Fitness F, std::size_t LOCK_GROUP_SIZE>
bool cache<F, LOCK_GROUP_SIZE>::is_valid() const
{
  if (seal_ == 0)
    return false;
 
  if (table_.empty())
    return k_mask == 0;
 
  return std::has_single_bit(table_.size()) && table_.size() - 1 == k_mask;
}
 
#endif  // include guard