15 #include <string_view>
19 template <
typename KEY,
typename VALUE>
29 void reduced_hash(
const std::string_view& value, uint8_t& hash);
30 void reduced_hash(
const std::string_view& value, uint16_t& hash);
31 void reduced_hash(
const std::string_view& value, uint32_t& hash);
32 void reduced_hash(
const std::string_view& value, uint64_t& hash);
54 typename KEY,
typename VALUE,
unsigned int NUM_BYTES_HASH_TABLE = 1,
55 unsigned int NUM_HAS_TABLE_COLLISIONS_ALLOWED = 5,
56 typename VECTOR_T = std::array<
57 std::array<ts_map_entry<KEY, VALUE>, NUM_HAS_TABLE_COLLISIONS_ALLOWED>,
58 1u << (8 * NUM_BYTES_HASH_TABLE)>>
65 KEY, VALUE, NUM_BYTES_HASH_TABLE, NUM_HAS_TABLE_COLLISIONS_ALLOWED,
69 using vec_t = VECTOR_T;
75 const_iterator() :
m_vec(nullptr), m_parent(nullptr) {}
77 const VECTOR_T& vec,
const self_t& parent,
int idx_outer,
79 :
m_vec(const_cast<VECTOR_T*>(&vec)),
80 m_parent(const_cast<self_t*>(&parent)),
81 m_idx_outer(idx_outer),
82 m_idx_inner(idx_inner)
85 const_iterator(
const const_iterator& o) { *
this = o; }
86 const_iterator& operator=(
const const_iterator& o)
89 m_idx_outer = o.m_idx_outer;
90 m_idx_inner = o.m_idx_inner;
95 return m_vec == o.m_vec && m_idx_outer == o.m_idx_outer &&
96 m_idx_inner == o.m_idx_inner;
98 bool operator!=(
const const_iterator& o)
const {
return !(*
this == o); }
101 return (*
m_vec)[m_idx_outer][m_idx_inner];
103 const value_type* operator->()
const
105 return &(*m_vec)[m_idx_outer][m_idx_inner];
109 const_iterator aux = *
this;
122 int m_idx_outer{0}, m_idx_inner{0};
130 static_cast<int>(NUM_HAS_TABLE_COLLISIONS_ALLOWED))
135 }
while (m_idx_outer <
static_cast<int>(m_parent->m_vec.size()) &&
136 !(*
m_vec)[m_idx_outer][m_idx_inner].used);
140 struct iterator :
public const_iterator
143 iterator() : const_iterator() {}
144 iterator(VECTOR_T& vec, self_t& parent,
int idx_outer,
int idx_inner)
145 : const_iterator(vec, parent, idx_outer, idx_inner)
151 [const_iterator::m_idx_inner];
153 value_type* operator->()
155 return &(*const_iterator::m_vec)[const_iterator::m_idx_outer]
156 [const_iterator::m_idx_inner];
160 iterator aux = *
this;
166 const_iterator::incr();
186 for (
size_t oi = 0; oi <
m_vec.size(); oi++)
187 for (
size_t ii = 0; ii < NUM_HAS_TABLE_COLLISIONS_ALLOWED; ii++)
188 m_vec[oi][ii] = value_type();
198 std::array<ts_map_entry<KEY, VALUE>, NUM_HAS_TABLE_COLLISIONS_ALLOWED>&
199 match_arr =
m_vec[hash];
200 for (
unsigned int i = 0; i < NUM_HAS_TABLE_COLLISIONS_ALLOWED; i++)
202 if (!match_arr[i].used)
205 match_arr[i].used =
true;
206 match_arr[i].first = key;
207 return &match_arr[i].second;
209 if (match_arr[i].first == key)
return &match_arr[i].second;
220 throw std::runtime_error(
"ts_hash_map: too many hash collisions!");
224 const_iterator
find(
const KEY& key)
const
231 match_arr =
m_vec[hash];
232 for (
unsigned int i = 0; i < NUM_HAS_TABLE_COLLISIONS_ALLOWED; i++)
234 if (match_arr[i].used && match_arr[i].first == key)
235 return const_iterator(
m_vec, *
this, hash, i);
242 const_iterator it(
m_vec, *
this, 0, -1);
246 const_iterator
end()
const
248 return const_iterator(
m_vec, *
this,
m_vec.size(), 0);
252 iterator it(
m_vec, *
this, 0, -1);
256 iterator
end() {
return iterator(
m_vec, *
this,
m_vec.size(), 0); }