BLI_hash_tables.hh

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */
 
#pragma once

 
#include <algorithm>
 
#include "BLI_utildefines.h"
#include "BLI_vector.hh"
 
namespace blender {
 
/* -------------------------------------------------------------------- */
 
template<typename IntT> constexpr IntT ceil_division(const IntT x, const IntT y)
{
  BLI_assert(x >= 0);
  BLI_assert(y >= 0);
  return x / y + ((x % y) != 0);
}
 
template<typename IntT> constexpr IntT floor_division(const IntT x, const IntT y)
{
  BLI_assert(x >= 0);
  BLI_assert(y >= 0);
  return x / y;
}
 
constexpr int64_t ceil_division_by_fraction(const int64_t x,
                                            const int64_t numerator,
                                            const int64_t denominator)
{
  return int64_t(ceil_division(uint64_t(x) * uint64_t(denominator), uint64_t(numerator)));
}
 
constexpr int64_t floor_multiplication_with_fraction(const int64_t x,
                                                     const int64_t numerator,
                                                     const int64_t denominator)
{
  return int64_t((uint64_t(x) * uint64_t(numerator) / uint64_t(denominator)));
}
 
constexpr int64_t total_slot_amount_for_usable_slots(const int64_t min_usable_slots,
                                                     const int64_t max_load_factor_numerator,
                                                     const int64_t max_load_factor_denominator)
{
  return power_of_2_max(ceil_division_by_fraction(
      min_usable_slots, max_load_factor_numerator, max_load_factor_denominator));
}

 
/* -------------------------------------------------------------------- */
 
class LoadFactor {
 private:
  uint8_t numerator_;
  uint8_t denominator_;
 
 public:
  constexpr LoadFactor(uint8_t numerator, uint8_t denominator)
      : numerator_(numerator), denominator_(denominator)
  {
    BLI_assert(numerator > 0);
    BLI_assert(numerator < denominator);
  }
 
  constexpr void compute_total_and_usable_slots(int64_t min_total_slots,
                                                int64_t min_usable_slots,
                                                int64_t *r_total_slots,
                                                int64_t *r_usable_slots) const
  {
    BLI_assert(is_power_of_2(int(min_total_slots)));
 
    int64_t total_slots = this->compute_total_slots(min_usable_slots, numerator_, denominator_);
    total_slots = std::max(total_slots, min_total_slots);
    const int64_t usable_slots = floor_multiplication_with_fraction(
        total_slots, numerator_, denominator_);
    BLI_assert(min_usable_slots <= usable_slots);
 
    *r_total_slots = total_slots;
    *r_usable_slots = usable_slots;
  }
 
  static constexpr int64_t compute_total_slots(int64_t min_usable_slots,
                                               uint8_t numerator,
                                               uint8_t denominator)
  {
    return total_slot_amount_for_usable_slots(min_usable_slots, numerator, denominator);
  }
};

 
/* -------------------------------------------------------------------- */

template<typename Key, Key EmptyValue, Key RemovedValue> struct TemplatedKeyInfo {
  static Key get_empty()
  {
    return EmptyValue;
  }

  static void remove(Key &key)
  {
    key = RemovedValue;
  }

  static bool is_empty(const Key &key)
  {
    return key == EmptyValue;
  }

  static bool is_removed(const Key &key)
  {
    return key == RemovedValue;
  }

  static bool is_not_empty_or_removed(const Key &key)
  {
    return key != EmptyValue && key != RemovedValue;
  }
};

template<typename Pointer> struct PointerKeyInfo {
  static Pointer get_empty()
  {
    return (Pointer)UINTPTR_MAX;
  }
 
  static void remove(Pointer &pointer)
  {
    pointer = (Pointer)(UINTPTR_MAX - 1);
  }
 
  static bool is_empty(Pointer pointer)
  {
    return uintptr_t(pointer) == UINTPTR_MAX;
  }
 
  static bool is_removed(Pointer pointer)
  {
    return uintptr_t(pointer) == UINTPTR_MAX - 1;
  }
 
  static bool is_not_empty_or_removed(Pointer pointer)
  {
    return uintptr_t(pointer) < UINTPTR_MAX - 1;
  }
};

 
/* -------------------------------------------------------------------- */
 
class HashTableStats {
 private:
  Vector<int64_t> keys_by_collision_count_;
  int64_t total_collisions_;
  float average_collisions_;
  int64_t size_;
  int64_t capacity_;
  int64_t removed_amount_;
  float load_factor_;
  float removed_load_factor_;
  int64_t size_per_element_;
  int64_t size_in_bytes_;
  const void *address_;
 
 public:
  template<typename HashTable, typename Keys>
  HashTableStats(const HashTable &hash_table, const Keys &keys)
  {
    total_collisions_ = 0;
    size_ = hash_table.size();
    capacity_ = hash_table.capacity();
    removed_amount_ = hash_table.removed_amount();
    size_per_element_ = hash_table.size_per_element();
    size_in_bytes_ = hash_table.size_in_bytes();
    address_ = static_cast<const void *>(&hash_table);
 
    for (const auto &key : keys) {
      int64_t collisions = hash_table.count_collisions(key);
      if (keys_by_collision_count_.size() <= collisions) {
        keys_by_collision_count_.append_n_times(0,
                                                collisions - keys_by_collision_count_.size() + 1);
      }
      keys_by_collision_count_[collisions]++;
      total_collisions_ += collisions;
    }
 
    average_collisions_ = (size_ == 0) ? 0 : (float)total_collisions_ / (float)size_;
    load_factor_ = (float)size_ / (float)capacity_;
    removed_load_factor_ = (float)removed_amount_ / (float)capacity_;
  }
 
  void print(const char *name) const;
};


template<typename T> struct DefaultEquality {
  template<typename T1, typename T2> bool operator()(const T1 &a, const T2 &b) const
  {
    return a == b;
  }
};

struct PointerComparison {
  template<typename T1, typename T2> bool operator()(const T1 &a, const T2 &b) const
  {
    return &*a == &*b;
  }
};
 
template<typename T> struct DefaultEquality<std::unique_ptr<T>> : public PointerComparison {};
template<typename T> struct DefaultEquality<std::shared_ptr<T>> : public PointerComparison {};
 
struct SequenceComparison {
  template<typename T1, typename T2> bool operator()(const T1 &a, const T2 &b) const
  {
    const auto a_begin = a.begin();
    const auto a_end = a.end();
    const auto b_begin = b.begin();
    const auto b_end = b.end();
    if (a_end - a_begin != b_end - b_begin) {
      return false;
    }
    return std::equal(a_begin, a_end, b_begin);
  }
};
 
template<typename T, int64_t InlineBufferCapacity, typename Allocator>
struct DefaultEquality<Vector<T, InlineBufferCapacity, Allocator>> : public SequenceComparison {};
 
}  // namespace blender