1 #ifndef MINIMAL_PERFECT_HASH_HH
2 #define MINIMAL_PERFECT_HASH_HH
57 template<
size_t M,
typename Hash>
61 static constexpr
auto M2 = M / 2;
63 std::array<uint8_t, M >
tab1;
64 std::array<uint8_t, M2>
tab2;
67 template<
typename Key>
68 [[nodiscard]] constexpr uint8_t
lookupIndex(
const Key& key)
const {
69 const uint32_t h =
hash(key);
70 const uint8_t d =
tab1[h % M];
71 if ((d & 0x80) == 0) {
74 return tab2[(h >> (d & 31)) %
M2];
79 template<
size_t N,
typename Hash,
typename GetKey>
80 [[nodiscard]] constexpr
auto create(
const Hash& hash,
const GetKey& getKey)
82 static_assert(
N < 128);
84 constexpr
auto bucket_max = size_t(2 *
cstd::sqrt(M));
90 std::array<static_vector<uint8_t, bucket_max>, r.tab1.size()> buckets;
92 buckets[hash(getKey(i)) % r.tab1.size()].push_back(uint8_t(i));
96 cstd::sort(buckets, [](
const auto&
x,
const auto& y) {
97 return x.size() > y.size();
101 constexpr
auto UNUSED = uint8_t(-1);
103 for (
const auto& bucket : buckets) {
104 auto const bSize = bucket.size();
105 if (bSize == 0)
break;
106 auto hash1 = hash(getKey(bucket[0])) % r.tab1.size();
109 r.tab1[hash1] = bucket[0];
116 while (bucket_slots.
size() < bSize) {
117 auto hash2 = hash(getKey(bucket[bucket_slots.
size()]));
118 assert((hash2 % r.tab1.size()) == hash1);
119 auto slot = (hash2 >> shift) % r.tab2.size();
123 bucket_slots.
clear();
130 r.tab1[hash1] = shift | 0x80;
131 for (
auto i :
xrange(bSize)) {
132 r.tab2[bucket_slots[i]] = bucket[i];
constexpr size_t size() const
constexpr void push_back(const T &a)
constexpr T ceil2(T x) noexcept
Returns the smallest number that is both >=a and a power of two.
constexpr bool ispow2(T x) noexcept
Is the given number an integral power of two? That is, does it have exactly one 1-bit in binary repre...
constexpr auto create(const Hash &hash, const GetKey &getKey)
constexpr void sort(RAIt first, RAIt last, Compare cmp=Compare{})
constexpr void fill(ForwardIt first, ForwardIt last, const T &value)
constexpr double sqrt(double x)
constexpr void replace(ForwardIt first, ForwardIt last, const T &old_value, const T &new_value)
constexpr KeyMatrixPosition x
Keyboard bindings.
constexpr bool contains(ITER first, ITER last, const VAL &val)
Check if a range contains a given value, using linear search.
std::array< uint8_t, M > tab1
std::array< uint8_t, M2 > tab2
constexpr uint8_t lookupIndex(const Key &key) const
constexpr auto xrange(T e)