/
bucketers.hpp
84 lines (66 loc) · 2.56 KB
/
bucketers.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#pragma once
#include "include/utils/util.hpp"
namespace pthash {
struct skew_bucketer {
skew_bucketer() {}
void init(uint64_t num_buckets) {
m_num_dense_buckets = constants::b * num_buckets;
m_num_sparse_buckets = num_buckets - m_num_dense_buckets;
m_M_num_dense_buckets = fastmod::computeM_u64(m_num_dense_buckets);
m_M_num_sparse_buckets = fastmod::computeM_u64(m_num_sparse_buckets);
}
inline uint64_t bucket(uint64_t hash) const {
static const uint64_t T = constants::a * UINT64_MAX;
return (hash < T) ? fastmod::fastmod_u64(hash, m_M_num_dense_buckets, m_num_dense_buckets)
: m_num_dense_buckets + fastmod::fastmod_u64(hash, m_M_num_sparse_buckets,
m_num_sparse_buckets);
}
uint64_t num_buckets() const {
return m_num_dense_buckets + m_num_sparse_buckets;
}
size_t num_bits() const {
return 8 * (sizeof(m_num_dense_buckets) + sizeof(m_num_sparse_buckets) +
sizeof(m_M_num_dense_buckets) + sizeof(m_M_num_sparse_buckets));
}
void swap(skew_bucketer& other) {
std::swap(m_num_dense_buckets, other.m_num_dense_buckets);
std::swap(m_num_sparse_buckets, other.m_num_sparse_buckets);
std::swap(m_M_num_dense_buckets, other.m_M_num_dense_buckets);
std::swap(m_M_num_sparse_buckets, other.m_M_num_sparse_buckets);
}
template <typename Visitor>
void visit(Visitor& visitor) {
visitor.visit(m_num_dense_buckets);
visitor.visit(m_num_sparse_buckets);
visitor.visit(m_M_num_dense_buckets);
visitor.visit(m_M_num_sparse_buckets);
}
private:
uint64_t m_num_dense_buckets, m_num_sparse_buckets;
__uint128_t m_M_num_dense_buckets, m_M_num_sparse_buckets;
};
struct uniform_bucketer {
uniform_bucketer() {}
void init(uint64_t num_buckets) {
m_num_buckets = num_buckets;
m_M_num_buckets = fastmod::computeM_u64(m_num_buckets);
}
inline uint64_t bucket(uint64_t hash) const {
return fastmod::fastmod_u64(hash, m_M_num_buckets, m_num_buckets);
}
uint64_t num_buckets() const {
return m_num_buckets;
}
size_t num_bits() const {
return 8 * (sizeof(m_num_buckets) + sizeof(m_M_num_buckets));
}
template <typename Visitor>
void visit(Visitor& visitor) {
visitor.visit(m_num_buckets);
visitor.visit(m_M_num_buckets);
}
private:
uint64_t m_num_buckets;
__uint128_t m_M_num_buckets;
};
} // namespace pthash