xenium
Loading...
Searching...
No Matches
vyukov_hash_map_traits.hpp
1//
2// Copyright (c) 2018-2020 Manuel Pöter.
3// Licensed under the MIT License. See LICENSE file in the project root for full license information.
4//
5
6#ifndef XENIUM_VYUKOV_HASH_MAP_IMPL
7#error "This is an impl file and must not be included directly!"
8#endif
9
10namespace xenium { namespace impl {
11 namespace bits {
12 template <class Key>
13 struct vyukov_hash_map_common {
14 using key_type = Key;
15
16 template <class Accessor>
17 static void reset(Accessor&& acc) { acc.reset(); }
18 };
19
20 template <class Key>
21 struct vyukov_hash_map_trivial_key : vyukov_hash_map_common<Key> {
22 template <class Cell>
23 static bool compare_trivial_key(Cell& key_cell, const Key& key, hash_t /*hash*/) {
24 return key_cell.load(std::memory_order_relaxed) == key;
25 }
26
27 template <class Accessor>
28 static bool compare_nontrivial_key(const Accessor&, const Key&) { return true; }
29
30 template <class Hash>
31 static hash_t rehash(const Key& k) { return Hash{}(k); }
32 };
33
34 template <class Key>
35 struct vyukov_hash_map_nontrivial_key : vyukov_hash_map_common<Key> {
36 template <class Cell>
37 static bool compare_trivial_key(Cell& key_cell, const Key& /*key*/, hash_t hash) {
38 return key_cell.load(std::memory_order_relaxed) == hash;
39 }
40
41 template <class Accessor>
42 static bool compare_nontrivial_key(const Accessor& acc, const Key& key) {
43 return acc.key() == key;
44 }
45
46 template <class Hash>
47 static hash_t rehash(hash_t h) { return h; }
48 };
49 }
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>
53 {
54 static_assert(!parameter::is_set<ValueReclaimer>::value,
55 "value_reclaimer policy can only be used with non-trivial key/value types");
56
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;
62
63 class accessor {
64 public:
65 accessor() = default;
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(); }
70 private:
71 accessor(storage_value_type& v, std::memory_order order):
72 guard(acquire_guard(v, order))
73 {}
74 typename storage_value_type::guard_ptr guard;
75 friend struct vyukov_hash_map_traits;
76 };
77
78 static accessor acquire(storage_value_type& v, std::memory_order order) {
79 return accessor(v, order);
80 }
81
82 template <bool AcquireAccessor>
83 static void store_item(storage_key_type& key_cell, storage_value_type& value_cell,
84 hash_t /*hash*/, Key k, Value* v, std::memory_order order, accessor& acc)
85 {
86 key_cell.store(k, std::memory_order_relaxed);
87 value_cell.store(v, order);
88 if (AcquireAccessor)
89 acc.guard = typename storage_value_type::guard_ptr(v);
90 }
91
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 /*hash*/, accessor& acc)
95 {
96 if (key_cell.load(std::memory_order_relaxed) != key)
97 return false;
98 if (AcquireAccessor)
99 acc.guard = typename storage_value_type::guard_ptr(value_cell.load(std::memory_order_relaxed));
100 return true;
101 }
102
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()};
105 }
106
107 static void reclaim(accessor& a) { a.guard.reclaim(); }
108 static void reclaim_internal(accessor&) {} // noop
109 };
110
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>
114 {
115 using reclaimer = std::conditional_t<parameter::is_set<ValueReclaimer>::value, ValueReclaimer, Reclaimer>;
116
117 struct node : reclaimer::template enable_concurrent_ptr<node> {
118 node(Key&& key, Value* value):
119 key(std::move(key)),
120 value(std::move(value))
121 {}
122
123 Key key;
124 typename VReclaimer::template concurrent_ptr<Value> value;
125 };
126
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;
132
133 class accessor {
134 public:
135 accessor() = default;
136 Value* operator->() const noexcept { return value_guard.get(); }
137 Value& operator*() const noexcept { return *value_guard.get(); }
138 void reset() {
139 value_guard.reset();
140 node_guard.reset();
141 }
142 private:
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))
146 {}
147 const Key& key() const { return node_guard->key; }
148 //accessor(typename storage_value_type::marked_ptr v) : guard(v) {}
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>;
153 };
154
155 static accessor acquire(storage_value_type& v, std::memory_order order) {
156 return accessor(v, order);
157 }
158
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)
162 {
163 auto n = new node(std::move(k), v);
164 if (AcquireAccessor) {
165 acc.node_guard = typename storage_value_type::guard_ptr(n); // TODO - is this necessary?
166 acc.value_guard = typename VReclaimer::template concurrent_ptr<Value>::guard_ptr(v);
167 }
168 key_cell.store(hash, std::memory_order_relaxed);
169 value_cell.store(n, order);
170 }
171
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)
175 {
176 if (key_cell.load(std::memory_order_relaxed) != hash)
177 return false;
178 acc.node_guard = typename storage_value_type::guard_ptr(value_cell.load(std::memory_order_relaxed));
179 if (acc.node_guard->key == key) {
180 if (AcquireAccessor)
181 acc.value_guard = typename VReclaimer::template concurrent_ptr<Value>::guard_ptr(acc.node_guard->value.load(std::memory_order_relaxed));
182 return true;
183 }
184 return false;
185 }
186
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() };
190 }
191
192 static void reclaim(accessor& a) {
193 a.value_guard.reclaim();
194 a.node_guard.reclaim();
195 }
196 static void reclaim_internal(accessor& a) {
197 // copy guard to avoid resetting the accessor's guard_ptr.
198 // TODO - this could be simplified by avoiding reset of
199 // guard_ptrs in reclaim().
200 auto g = a.node_guard;
201 g.reclaim();
202 }
203 };
204
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>
208 {
209 static_assert(!parameter::is_set<ValueReclaimer>::value,
210 "value_reclaimer policy can only be used with non-trivial key/value types");
211
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;
217
218 class accessor {
219 public:
220 accessor() = default;
221 const value_type& operator*() const noexcept { return v; }
222 private:
223 accessor(storage_value_type& v, std::memory_order order):
224 v(v.load(order))
225 {}
226 value_type v;
227 friend struct vyukov_hash_map_traits;
228 };
229
230 static void reset(accessor&&) {}
231 static accessor acquire(storage_value_type& v, std::memory_order order) { return accessor(v, order); }
232
233 template <bool AcquireAccessor>
234 static void store_item(storage_key_type& key_cell, storage_value_type& value_cell,
235 hash_t /*hash*/, Key k, Value v, std::memory_order order, accessor& acc)
236 {
237 key_cell.store(k, std::memory_order_relaxed);
238 value_cell.store(v, order);
239 if (AcquireAccessor)
240 acc.v = v;
241 }
242
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 /*hash*/, accessor& acc)
246 {
247 if (key_cell.load(std::memory_order_relaxed) != key)
248 return false;
249 if (AcquireAccessor)
250 acc.v = value_cell.load(std::memory_order_relaxed);
251 return true;
252 }
253
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)};
256 }
257
258 static void reclaim(accessor&) {} // noop
259 static void reclaim_internal(accessor&) {} // noop
260 };
261
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>
265 {
266 using reclaimer = std::conditional_t<parameter::is_set<ValueReclaimer>::value, ValueReclaimer, Reclaimer>;
267
268 struct node : reclaimer::template enable_concurrent_ptr<node> {
269 node(Value&& value): value(std::move(value)) {}
270 Value value;
271 };
272
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;
278
279 class accessor {
280 public:
281 accessor() = default;
282 Value* operator->() const noexcept { return &guard->value; }
283 Value& operator*() const noexcept { return guard->value; }
284 void reset() { guard.reset(); }
285 private:
286 accessor(storage_value_type& v, std::memory_order order):
287 guard(acquire_guard(v, order))
288 {}
289 typename storage_value_type::guard_ptr guard;
290 friend struct vyukov_hash_map_traits;
291 };
292
293 static accessor acquire(storage_value_type& v, std::memory_order order) {
294 return accessor(v, order);
295 }
296
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 /*hash*/, accessor& acc)
300 {
301 if (key_cell.load(std::memory_order_relaxed) != key)
302 return false;
303 if (AcquireAccessor)
304 acc.guard = typename storage_value_type::guard_ptr(value_cell.load(std::memory_order_relaxed));
305 return true;
306 }
307
308 template <bool AcquireAccessor>
309 static void store_item(storage_key_type& key_cell, storage_value_type& value_cell,
310 hash_t /*hash*/, Key&& k, Value&& v, std::memory_order order, accessor& acc)
311 {
312 auto n = new node(std::move(v));
313 if (AcquireAccessor)
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);
317 }
318
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};
322 }
323
324 static void reclaim(accessor& a) { a.guard.reclaim(); }
325 static void reclaim_internal(accessor& a) {
326 // copy guard to avoid resetting the accessor's guard_ptr.
327 // TODO - this could be simplified by avoiding reset of
328 // guard_ptrs in reclaim().
329 auto g = a.guard;
330 g.reclaim();
331 }
332 };
333
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>
337 {
338 using reclaimer = std::conditional_t<parameter::is_set<ValueReclaimer>::value, ValueReclaimer, Reclaimer>;
339
340 struct node : reclaimer::template enable_concurrent_ptr<node> {
341 node(Key&& key, Value&& value):
342 data(std::move(key), std::move(value))
343 {}
344
345 std::pair<const Key, Value> data;
346 };
347
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&;
353
354 class accessor {
355 public:
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(); }
360 private:
361 accessor(storage_value_type& v, std::memory_order order):
362 guard(acquire_guard(v, order))
363 {}
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>;
368 };
369
370 static accessor acquire(storage_value_type& v, std::memory_order order) {
371 return accessor(v, order);
372 }
373
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)
377 {
378 auto n = new node(std::move(k), std::move(v));
379 if (AcquireAccessor)
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);
383 }
384
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)
388 {
389 if (key_cell.load(std::memory_order_relaxed) != hash)
390 return false;
391 acc.guard = typename storage_value_type::guard_ptr(value_cell.load(std::memory_order_relaxed));
392 return acc.guard->data.first == key;
393 }
394
395 static iterator_reference deref_iterator(storage_key_type&, storage_value_type& v) {
396 auto node = v.load(std::memory_order_relaxed);
397 return node->data;
398 }
399
400 static void reclaim(accessor& a) { a.guard.reclaim(); }
401 static void reclaim_internal(accessor& a) {
402 // copy guard to avoid resetting the accessor's guard_ptr.
403 // TODO - this could be simplified by avoiding reset of
404 // guard_ptrs in reclaim().
405 auto g = a.guard;
406 g.reclaim();
407 }
408 };
409}}