xenium
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 
10 namespace 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 }}