6 #ifndef XENIUM_VYUKOV_HASH_MAP_IMPL
7 #error "This is an impl file and must not be included directly!"
10 namespace xenium {
namespace impl {
13 struct vyukov_hash_map_common {
16 template <
class Accessor>
17 static void reset(Accessor&& acc) { acc.reset(); }
21 struct vyukov_hash_map_trivial_key : vyukov_hash_map_common<Key> {
23 static bool compare_trivial_key(Cell& key_cell,
const Key& key, hash_t ) {
24 return key_cell.load(std::memory_order_relaxed) == key;
27 template <
class Accessor>
28 static bool compare_nontrivial_key(
const Accessor&,
const Key&) {
return true; }
31 static hash_t rehash(
const Key& k) {
return Hash{}(k); }
35 struct vyukov_hash_map_nontrivial_key : vyukov_hash_map_common<Key> {
37 static bool compare_trivial_key(Cell& key_cell,
const Key& , hash_t hash) {
38 return key_cell.load(std::memory_order_relaxed) == hash;
41 template <
class Accessor>
42 static bool compare_nontrivial_key(
const Accessor& acc,
const Key& key) {
43 return acc.key() == key;
47 static hash_t rehash(hash_t h) {
return h; }
50 template <
class Key,
class Value,
class VReclaimer,
class ValueReclaimer,
class Reclaimer>
51 struct vyukov_hash_map_traits<Key, managed_ptr<Value, VReclaimer>, ValueReclaimer, Reclaimer, true, true> :
52 bits::vyukov_hash_map_trivial_key<Key>
54 static_assert(!parameter::is_set<ValueReclaimer>::value,
55 "value_reclaimer policy can only be used with non-trivial key/value types");
57 using value_type = Value*;
58 using storage_key_type = std::atomic<Key>;
59 using storage_value_type =
typename VReclaimer::template concurrent_ptr<Value>;
60 using iterator_value_type = std::pair<const Key, Value*>;
61 using iterator_reference = iterator_value_type;
66 Value* operator->() const noexcept {
return guard.get(); }
67 Value& operator*() const noexcept {
return guard.get(); }
68 void reset() { guard.reset(); }
69 void reclaim() { guard.reclaim(); }
71 accessor(storage_value_type& v, std::memory_order order):
72 guard(acquire_guard(v, order))
74 typename storage_value_type::guard_ptr guard;
75 friend struct vyukov_hash_map_traits;
78 static accessor acquire(storage_value_type& v, std::memory_order order) {
79 return accessor(v, order);
82 template <
bool AcquireAccessor>
83 static void store_item(storage_key_type& key_cell, storage_value_type& value_cell,
84 hash_t , Key k, Value* v, std::memory_order order, accessor& acc)
86 key_cell.store(k, std::memory_order_relaxed);
87 value_cell.store(v, order);
89 acc.guard =
typename storage_value_type::guard_ptr(v);
92 template <
bool AcquireAccessor>
93 static bool compare_key(storage_key_type& key_cell, storage_value_type& value_cell,
const Key& key,
94 hash_t , accessor& acc)
96 if (key_cell.load(std::memory_order_relaxed) != key)
99 acc.guard =
typename storage_value_type::guard_ptr(value_cell.load(std::memory_order_relaxed));
103 static iterator_reference deref_iterator(storage_key_type& k, storage_value_type& v) {
104 return {k.load(std::memory_order_relaxed), v.load(std::memory_order_relaxed).get()};
107 static void reclaim(accessor& a) { a.guard.reclaim(); }
108 static void reclaim_internal(accessor&) {}
111 template <
class Key,
class Value,
class VReclaimer,
class ValueReclaimer,
class Reclaimer>
112 struct vyukov_hash_map_traits<Key, managed_ptr<Value, VReclaimer>, ValueReclaimer, Reclaimer, false, true> :
113 bits::vyukov_hash_map_nontrivial_key<Key>
115 using reclaimer = std::conditional_t<parameter::is_set<ValueReclaimer>::value, ValueReclaimer, Reclaimer>;
117 struct node : reclaimer::template enable_concurrent_ptr<node> {
118 node(Key&& key, Value* value):
120 value(std::move(value))
124 typename VReclaimer::template concurrent_ptr<Value> value;
127 using value_type = Value*;
128 using storage_key_type = std::atomic<size_t>;
129 using storage_value_type =
typename reclaimer::template concurrent_ptr<node>;
130 using iterator_value_type = std::pair<const Key&, value_type>;
131 using iterator_reference = iterator_value_type;
135 accessor() =
default;
136 Value* operator->() const noexcept {
return value_guard.get(); }
137 Value& operator*() const noexcept {
return *value_guard.get(); }
143 accessor(storage_value_type& v, std::memory_order order):
144 node_guard(acquire_guard(v, order)),
145 value_guard(acquire_guard(node_guard->value, order))
147 const Key& key()
const {
return node_guard->key; }
149 typename storage_value_type::guard_ptr node_guard;
150 typename VReclaimer::template concurrent_ptr<Value>::guard_ptr value_guard;
151 friend struct vyukov_hash_map_traits;
152 friend struct bits::vyukov_hash_map_nontrivial_key<Key>;
155 static accessor acquire(storage_value_type& v, std::memory_order order) {
156 return accessor(v, order);
159 template <
bool AcquireAccessor>
160 static void store_item(storage_key_type& key_cell, storage_value_type& value_cell,
161 hash_t hash, Key&& k, Value* v, std::memory_order order, accessor& acc)
163 auto n =
new node(std::move(k), v);
164 if (AcquireAccessor) {
165 acc.node_guard =
typename storage_value_type::guard_ptr(n);
166 acc.value_guard =
typename VReclaimer::template concurrent_ptr<Value>::guard_ptr(v);
168 key_cell.store(hash, std::memory_order_relaxed);
169 value_cell.store(n, order);
172 template <
bool AcquireAccessor>
173 static bool compare_key(storage_key_type& key_cell, storage_value_type& value_cell,
174 const Key& key, hash_t hash, accessor& acc)
176 if (key_cell.load(std::memory_order_relaxed) != hash)
178 acc.node_guard =
typename storage_value_type::guard_ptr(value_cell.load(std::memory_order_relaxed));
179 if (acc.node_guard->key == key) {
181 acc.value_guard =
typename VReclaimer::template concurrent_ptr<Value>::guard_ptr(acc.node_guard->value.load(std::memory_order_relaxed));
187 static iterator_reference deref_iterator(storage_key_type&, storage_value_type& v) {
188 auto node = v.load(std::memory_order_relaxed);
189 return {node->key, node->value.load(std::memory_order_relaxed).get() };
192 static void reclaim(accessor& a) {
193 a.value_guard.reclaim();
194 a.node_guard.reclaim();
196 static void reclaim_internal(accessor& a) {
200 auto g = a.node_guard;
205 template <
class Key,
class Value,
class ValueReclaimer,
class Reclaimer>
206 struct vyukov_hash_map_traits<Key, Value, ValueReclaimer, Reclaimer, true, true> :
207 bits::vyukov_hash_map_trivial_key<Key>
209 static_assert(!parameter::is_set<ValueReclaimer>::value,
210 "value_reclaimer policy can only be used with non-trivial key/value types");
212 using value_type = Value;
213 using storage_key_type = std::atomic<Key>;
214 using storage_value_type = std::atomic<Value>;
215 using iterator_value_type = std::pair<const Key, Value>;
216 using iterator_reference = iterator_value_type;
220 accessor() =
default;
221 const value_type& operator*() const noexcept {
return v; }
223 accessor(storage_value_type& v, std::memory_order order):
227 friend struct vyukov_hash_map_traits;
230 static void reset(accessor&&) {}
231 static accessor acquire(storage_value_type& v, std::memory_order order) {
return accessor(v, order); }
233 template <
bool AcquireAccessor>
234 static void store_item(storage_key_type& key_cell, storage_value_type& value_cell,
235 hash_t , Key k, Value v, std::memory_order order, accessor& acc)
237 key_cell.store(k, std::memory_order_relaxed);
238 value_cell.store(v, order);
243 template <
bool AcquireAccessor>
244 static bool compare_key(storage_key_type& key_cell, storage_value_type& value_cell,
245 const Key& key, hash_t , accessor& acc)
247 if (key_cell.load(std::memory_order_relaxed) != key)
250 acc.v = value_cell.load(std::memory_order_relaxed);
254 static iterator_reference deref_iterator(storage_key_type& k, storage_value_type& v) {
255 return {k.load(std::memory_order_relaxed), v.load(std::memory_order_relaxed)};
258 static void reclaim(accessor&) {}
259 static void reclaim_internal(accessor&) {}
262 template <
class Key,
class Value,
class ValueReclaimer,
class Reclaimer>
263 struct vyukov_hash_map_traits<Key, Value, ValueReclaimer, Reclaimer, true, false> :
264 bits::vyukov_hash_map_trivial_key<Key>
266 using reclaimer = std::conditional_t<parameter::is_set<ValueReclaimer>::value, ValueReclaimer, Reclaimer>;
268 struct node : reclaimer::template enable_concurrent_ptr<node> {
269 node(Value&& value): value(std::move(value)) {}
273 using value_type = Value;
274 using storage_key_type = std::atomic<Key>;
275 using storage_value_type =
typename reclaimer::template concurrent_ptr<node>;
276 using iterator_value_type = std::pair<const Key, Value&>;
277 using iterator_reference = iterator_value_type;
281 accessor() =
default;
282 Value* operator->() const noexcept {
return &guard->value; }
283 Value& operator*() const noexcept {
return guard->value; }
284 void reset() { guard.reset(); }
286 accessor(storage_value_type& v, std::memory_order order):
287 guard(acquire_guard(v, order))
289 typename storage_value_type::guard_ptr guard;
290 friend struct vyukov_hash_map_traits;
293 static accessor acquire(storage_value_type& v, std::memory_order order) {
294 return accessor(v, order);
297 template <
bool AcquireAccessor>
298 static bool compare_key(storage_key_type& key_cell, storage_value_type& value_cell,
299 const Key& key, hash_t , accessor& acc)
301 if (key_cell.load(std::memory_order_relaxed) != key)
304 acc.guard =
typename storage_value_type::guard_ptr(value_cell.load(std::memory_order_relaxed));
308 template <
bool AcquireAccessor>
309 static void store_item(storage_key_type& key_cell, storage_value_type& value_cell,
310 hash_t , Key&& k, Value&& v, std::memory_order order, accessor& acc)
312 auto n =
new node(std::move(v));
314 acc.guard =
typename storage_value_type::guard_ptr(n);
315 key_cell.store(k, std::memory_order_relaxed);
316 value_cell.store(n, order);
319 static iterator_reference deref_iterator(storage_key_type& k, storage_value_type& v) {
320 auto node = v.load(std::memory_order_relaxed);
321 return {k.load(std::memory_order_relaxed), node->value};
324 static void reclaim(accessor& a) { a.guard.reclaim(); }
325 static void reclaim_internal(accessor& a) {
334 template <
class Key,
class Value,
class ValueReclaimer,
class Reclaimer,
bool TrivialValue>
335 struct vyukov_hash_map_traits<Key, Value, ValueReclaimer, Reclaimer, false, TrivialValue> :
336 bits::vyukov_hash_map_nontrivial_key<Key>
338 using reclaimer = std::conditional_t<parameter::is_set<ValueReclaimer>::value, ValueReclaimer, Reclaimer>;
340 struct node : reclaimer::template enable_concurrent_ptr<node> {
341 node(Key&& key, Value&& value):
342 data(std::move(key), std::move(value))
345 std::pair<const Key, Value> data;
348 using value_type = Value;
349 using storage_key_type = std::atomic<hash_t>;
350 using storage_value_type =
typename reclaimer::template concurrent_ptr<node>;
351 using iterator_value_type = std::pair<const Key, Value>;
352 using iterator_reference = iterator_value_type&;
356 accessor() =
default;
357 Value* operator->() const noexcept {
return &guard->data.second; }
358 Value& operator*() const noexcept {
return guard->data.second; }
359 void reset() { guard.reset(); }
361 accessor(storage_value_type& v, std::memory_order order):
362 guard(acquire_guard(v, order))
364 const Key& key()
const {
return guard->data.first; }
365 typename storage_value_type::guard_ptr guard;
366 friend struct vyukov_hash_map_traits;
367 friend struct bits::vyukov_hash_map_nontrivial_key<Key>;
370 static accessor acquire(storage_value_type& v, std::memory_order order) {
371 return accessor(v, order);
374 template <
bool AcquireAccessor>
375 static void store_item(storage_key_type& key_cell, storage_value_type& value_cell,
376 hash_t hash, Key&& k, Value&& v, std::memory_order order, accessor& acc)
378 auto n =
new node(std::move(k), std::move(v));
380 acc.guard =
typename storage_value_type::guard_ptr(n);
381 key_cell.store(hash, std::memory_order_relaxed);
382 value_cell.store(n, order);
385 template <
bool AcquireAccessor>
386 static bool compare_key(storage_key_type& key_cell, storage_value_type& value_cell,
387 const Key& key, hash_t hash, accessor& acc)
389 if (key_cell.load(std::memory_order_relaxed) != hash)
391 acc.guard =
typename storage_value_type::guard_ptr(value_cell.load(std::memory_order_relaxed));
392 return acc.guard->data.first == key;
395 static iterator_reference deref_iterator(storage_key_type&, storage_value_type& v) {
396 auto node = v.load(std::memory_order_relaxed);
400 static void reclaim(accessor& a) { a.guard.reclaim(); }
401 static void reclaim_internal(accessor& a) {