PMDK C++ bindings  1.10
This is the C++ bindings documentation for PMDK's libpmemobj.
concurrent_skip_list_impl.hpp
1 // SPDX-License-Identifier: BSD-3-Clause
2 /* Copyright 2020, Intel Corporation */
3 
4 #ifndef PMEMOBJ_CONCURRENT_SKIP_LIST_IMPL_HPP
5 #define PMEMOBJ_CONCURRENT_SKIP_LIST_IMPL_HPP
6 
7 #include <algorithm>
8 #include <array>
9 #include <atomic>
10 #include <cstdlib>
11 #include <limits>
12 #include <mutex> /* for std::unique_lock */
13 #include <random>
14 #include <type_traits>
15 
19 #include <libpmemobj++/detail/pair.hpp>
20 #include <libpmemobj++/detail/persistent_pool_ptr.hpp>
22 #include <libpmemobj++/mutex.hpp>
24 #include <libpmemobj++/pool.hpp>
26 
27 /* Windows has a max and a min macros which collides with min() and max()
28  * methods of default_random_generator */
29 #if defined(_WIN32)
30 #if defined(max)
31 #undef max
32 #endif
33 #if defined(min)
34 #undef min
35 #endif
36 #endif
37 
38 namespace pmem
39 {
40 namespace detail
41 {
42 
43 #ifndef NDEBUG
44 inline void
45 try_insert_node_finish_marker()
46 {
47 }
48 #endif
49 
50 template <typename T>
51 inline void
52 store_with_release(persistent_pool_ptr<T> &dst, persistent_pool_ptr<T> src)
53 {
54 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
55  ANNOTATE_HAPPENS_BEFORE(&dst);
56 #endif
57  std::atomic_thread_fence(std::memory_order_release);
58 
59  dst = src;
60 }
61 
62 template <typename T>
63 inline persistent_pool_ptr<T>
64 load_with_acquire(const persistent_pool_ptr<T> &ptr)
65 {
66  persistent_pool_ptr<T> ret = ptr;
67  std::atomic_thread_fence(std::memory_order_acquire);
68 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
69  ANNOTATE_HAPPENS_AFTER(&ptr);
70 #endif
71  return ret;
72 }
73 
74 template <typename Compare>
75 using is_transparent = typename Compare::is_transparent;
76 
77 template <typename Compare>
78 using has_is_transparent = detail::supports<Compare, is_transparent>;
79 
84 template <typename MyAlloc, typename OtherAlloc>
85 inline void
86 allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator,
87  std::true_type)
88 {
89  my_allocator = other_allocator;
90 }
91 
96 template <typename MyAlloc, typename OtherAlloc>
97 inline void
98 allocator_copy_assignment(MyAlloc &, OtherAlloc &, std::false_type)
99 { /* NO COPY */
100 }
101 
106 template <typename MyAlloc, typename OtherAlloc>
107 inline void
108 allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator,
109  std::true_type)
110 {
111  my_allocator = std::move(other_allocator);
112 }
113 
118 template <typename MyAlloc, typename OtherAlloc>
119 inline void
120 allocator_move_assignment(MyAlloc &, OtherAlloc &, std::false_type)
121 { /* NO MOVE */
122 }
123 
128 template <typename MyAlloc, typename OtherAlloc>
129 inline void
130 allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator,
131  std::true_type)
132 {
133  std::swap(my_allocator, other_allocator);
134 }
135 
140 template <typename MyAlloc, typename OtherAlloc>
141 inline void
142 allocator_swap(MyAlloc &, OtherAlloc &, std::false_type)
143 { /* NO SWAP */
144 }
145 
146 template <typename Value, typename Mutex = pmem::obj::mutex,
147  typename LockType = std::unique_lock<Mutex>>
148 class skip_list_node {
149 public:
150  using value_type = Value;
151  using size_type = std::size_t;
152  using reference = value_type &;
153  using const_reference = const value_type &;
154  using pointer = value_type *;
155  using const_pointer = const value_type *;
156  using node_pointer = persistent_pool_ptr<skip_list_node>;
157  using mutex_type = Mutex;
158  using lock_type = LockType;
159 
160  skip_list_node(size_type levels) : height_(levels)
161  {
162  for (size_type lev = 0; lev < height_; ++lev)
163  detail::create<node_pointer>(&get_next(lev), nullptr);
164 
165  assert(height() == levels);
166 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
167  /*
168  * Valgrind does not understand atomic semantic and reports
169  * false-postives in drd and helgrind tools.
170  */
171  for (size_type lev = 0; lev < height_; ++lev) {
172  VALGRIND_HG_DISABLE_CHECKING(&get_next(lev),
173  sizeof(node_pointer));
174  }
175 #endif
176  }
177 
178  skip_list_node(size_type levels, const node_pointer *new_nexts)
179  : height_(levels)
180  {
181  for (size_type lev = 0; lev < height_; ++lev)
182  detail::create<node_pointer>(&get_next(lev),
183  new_nexts[lev]);
184 
185  assert(height() == levels);
186 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
187  /*
188  * Valgrind does not understand atomic semantic and reports
189  * false-postives in drd and helgrind tools.
190  */
191  for (size_type lev = 0; lev < height_; ++lev) {
192  VALGRIND_HG_DISABLE_CHECKING(&get_next(lev),
193  sizeof(node_pointer));
194  }
195 #endif
196  }
197 
198  ~skip_list_node()
199  {
200  for (size_type lev = 0; lev < height_; ++lev)
201  detail::destroy<node_pointer>(get_next(lev));
202  }
203 
204  skip_list_node(const skip_list_node &) = delete;
205 
206  skip_list_node &operator=(const skip_list_node &) = delete;
207 
208  pointer
209  get() noexcept
210  {
211  return &val;
212  }
213 
214  const_pointer
215  get() const noexcept
216  {
217  return &val;
218  }
219 
220  reference
221  value()
222  {
223  return *get();
224  }
225 
226  node_pointer
227  next(size_type level) const
228  {
229  assert(level < height());
230  return load_with_acquire(get_next(level));
231  }
232 
233  void
234  set_next(size_type level, node_pointer next)
235  {
236  assert(level < height());
237  store_with_release(get_next(level), next);
238  }
239 
240  void
241  set_next(obj::pool_base pop, size_type level, node_pointer next)
242  {
243  set_next(level, next);
244  pop.persist(&get_next(level), sizeof(node_pointer));
245  }
246 
247  void
248  set_nexts(const node_pointer *new_nexts, size_type h)
249  {
250  assert(h == height());
251  node_pointer *nexts = get_nexts();
252 
253  std::copy(new_nexts, new_nexts + h, nexts);
254  }
255 
256  void
257  set_nexts(obj::pool_base pop, const node_pointer *new_nexts,
258  size_type h)
259  {
260  set_nexts(new_nexts, h);
261 
262  node_pointer *nexts = get_nexts();
263  pop.persist(nexts, sizeof(node_pointer) * h);
264  }
265 
267  size_type
268  height() const
269  {
270  return height_;
271  }
272 
273  lock_type
274  acquire()
275  {
276  return lock_type(mutex);
277  }
278 
279 private:
280  node_pointer *
281  get_nexts()
282  {
283  return reinterpret_cast<node_pointer *>(this + 1);
284  }
285 
286  node_pointer &
287  get_next(size_type level)
288  {
289  node_pointer *arr = get_nexts();
290  return arr[level];
291  }
292 
293  const node_pointer &
294  get_next(size_type level) const
295  {
296  const node_pointer *arr =
297  reinterpret_cast<const node_pointer *>(this + 1);
298  return arr[level];
299  }
300 
301  mutex_type mutex;
302  union {
303  value_type val;
304  };
305  size_type height_;
306 };
307 
308 template <typename NodeType, bool is_const>
309 class skip_list_iterator {
310  using node_type = NodeType;
311  using node_ptr = typename std::conditional<is_const, const node_type *,
312  node_type *>::type;
313  friend class skip_list_iterator<node_type, true>;
314 
315 public:
316  using value_type = typename node_type::value_type;
317  using iterator_category = std::forward_iterator_tag;
318  using difference_type = std::ptrdiff_t;
319  using reference =
320  typename std::conditional<is_const,
321  typename node_type::const_reference,
322  typename node_type::reference>::type;
323  using pointer = typename std::conditional<is_const, const value_type *,
324  value_type *>::type;
325 
326  skip_list_iterator() : pool_uuid(0), node(nullptr)
327  {
328  }
329 
331  skip_list_iterator(const skip_list_iterator &other)
332  : pool_uuid(other.pool_uuid), node(other.node)
333  {
334  }
335 
337  template <typename U = void,
338  typename = typename std::enable_if<is_const, U>::type>
339  skip_list_iterator(const skip_list_iterator<node_type, false> &other)
340  : pool_uuid(other.pool_uuid), node(other.node)
341  {
342  }
343 
344  reference operator*() const
345  {
346  return *(node->get());
347  }
348 
349  pointer operator->() const
350  {
351  return node->get();
352  }
353 
354  skip_list_iterator &
355  operator++()
356  {
357  assert(node != nullptr);
358  node = node->next(0).get(pool_uuid);
359  return *this;
360  }
361 
362  skip_list_iterator
363  operator++(int)
364  {
365  skip_list_iterator tmp = *this;
366  ++*this;
367  return tmp;
368  }
369 
370 private:
371  skip_list_iterator(uint64_t pool_uuid, node_type *n)
372  : pool_uuid(pool_uuid), node(n)
373  {
374  }
375 
376  template <typename T = void,
377  typename = typename std::enable_if<is_const, T>::type>
378  skip_list_iterator(uint64_t pool_uuid, const node_type *n)
379  : pool_uuid(pool_uuid), node(n)
380  {
381  }
382 
383  uint64_t pool_uuid;
384 
385  node_ptr node;
386 
387  template <typename Traits>
388  friend class concurrent_skip_list;
389 
390  template <typename T, bool M, bool U>
391  friend bool operator==(const skip_list_iterator<T, M> &lhs,
392  const skip_list_iterator<T, U> &rhs);
393 
394  template <typename T, bool M, bool U>
395  friend bool operator!=(const skip_list_iterator<T, M> &lhs,
396  const skip_list_iterator<T, U> &rhs);
397 };
398 
399 template <typename T, bool M, bool U>
400 bool
401 operator==(const skip_list_iterator<T, M> &lhs,
402  const skip_list_iterator<T, U> &rhs)
403 {
404  return lhs.node == rhs.node;
405 }
406 
407 template <typename T, bool M, bool U>
408 bool
409 operator!=(const skip_list_iterator<T, M> &lhs,
410  const skip_list_iterator<T, U> &rhs)
411 {
412  return lhs.node != rhs.node;
413 }
414 
415 struct default_random_generator {
416  using gen_type = std::mt19937_64;
417  using result_type = typename gen_type::result_type;
418 
419  size_t
420  operator()()
421  {
422  static thread_local gen_type engine(
423  static_cast<size_t>(time(0)));
424 
425  return engine();
426  }
427 
428  static constexpr result_type
429  min()
430  {
431  return gen_type::min();
432  }
433 
434  static constexpr result_type
435  max()
436  {
437  return gen_type::max();
438  }
439 };
440 
441 template <typename RndGenerator, size_t MAX_LEVEL>
442 class geometric_level_generator {
443 public:
444  using rnd_generator_type = RndGenerator;
445 
446  static constexpr size_t max_level = MAX_LEVEL;
447 
448  size_t
449  operator()()
450  {
451  /* rnd_generator_type should be thread-safe random number
452  * generator. */
453  static rnd_generator_type gen;
454  /* std::geometric_distribution is not thread-safe. We mark it as
455  * a thread_local to avoid data races. */
456  static thread_local std::geometric_distribution<size_t> d;
457 
458  return (d(gen) % MAX_LEVEL) + 1;
459  }
460 };
461 
490 template <typename Traits>
492 protected:
493  using traits_type = Traits;
494  using key_type = typename traits_type::key_type;
495  using mapped_type = typename traits_type::mapped_type;
496  using value_type = typename traits_type::value_type;
497  using size_type = std::size_t;
498  using difference_type = std::ptrdiff_t;
499  using key_compare = typename traits_type::compare_type;
500  using allocator_type = typename traits_type::allocator_type;
501  using allocator_traits_type = std::allocator_traits<allocator_type>;
502 
503  using reference = value_type &;
504  using const_reference = const value_type &;
505  using pointer = typename allocator_traits_type::pointer;
506  using const_pointer = typename allocator_traits_type::const_pointer;
507 
508  using list_node_type = skip_list_node<value_type>;
509 
510  using iterator = skip_list_iterator<list_node_type, false>;
511  using const_iterator = skip_list_iterator<list_node_type, true>;
512 
513  using reverse_iterator = std::reverse_iterator<iterator>;
514  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
515 
516  static constexpr size_type MAX_LEVEL = traits_type::max_level;
517 
518  using random_level_generator_type = geometric_level_generator<
519  typename traits_type::random_generator_type, MAX_LEVEL>;
520  using node_allocator_type = typename std::allocator_traits<
521  allocator_type>::template rebind_alloc<uint8_t>;
522  using node_allocator_traits = typename std::allocator_traits<
523  allocator_type>::template rebind_traits<uint8_t>;
524  using node_ptr = list_node_type *;
525  using const_node_ptr = const list_node_type *;
526  using persistent_node_ptr = persistent_pool_ptr<list_node_type>;
527 
528  using prev_array_type = std::array<node_ptr, MAX_LEVEL>;
529  using next_array_type = std::array<persistent_node_ptr, MAX_LEVEL>;
530  using node_lock_type = typename list_node_type::lock_type;
531  using lock_array = std::array<node_lock_type, MAX_LEVEL>;
532 
533 public:
534  static constexpr bool allow_multimapping =
535  traits_type::allow_multimapping;
536 
546  {
548  init();
549  }
550 
568  const key_compare &comp,
569  const allocator_type &alloc = allocator_type())
570  : _node_allocator(alloc), _compare(comp)
571  {
573  init();
574  }
575 
599  template <class InputIt>
600  concurrent_skip_list(InputIt first, InputIt last,
601  const key_compare &comp = key_compare(),
602  const allocator_type &alloc = allocator_type())
603  : _node_allocator(alloc), _compare(comp)
604  {
606  init();
607  while (first != last)
608  internal_unsafe_emplace(*first++);
609  }
610 
629  : _node_allocator(node_allocator_traits::
630  select_on_container_copy_construction(
631  other._node_allocator)),
632  _compare(other._compare),
633  _rnd_generator(other._rnd_generator)
634  {
636  init();
637  internal_copy(other);
638  assert(_size == other._size);
639  }
640 
661  const allocator_type &alloc)
662  : _node_allocator(alloc),
663  _compare(other._compare),
664  _rnd_generator(other._rnd_generator)
665  {
667  init();
668  internal_copy(other);
669  assert(_size == other._size);
670  }
671 
691  : _node_allocator(std::move(other._node_allocator)),
692  _compare(other._compare),
693  _rnd_generator(other._rnd_generator)
694  {
696  init();
697  internal_move(std::move(other));
698  }
699 
720  const allocator_type &alloc)
721  : _node_allocator(alloc),
722  _compare(other._compare),
723  _rnd_generator(other._rnd_generator)
724  {
726  init();
727  if (alloc == other.get_allocator()) {
728  internal_move(std::move(other));
729  } else {
730  init();
731  internal_copy(std::make_move_iterator(other.begin()),
732  std::make_move_iterator(other.end()));
733  }
734  }
735 
742  void
744  {
745  tls_restore();
746 
747  assert(this->size() ==
748  size_type(std::distance(this->begin(), this->end())));
749  }
750 
763  void
765  {
766  if (dummy_head == nullptr)
767  return;
768 
769  auto pop = get_pool_base();
770  obj::transaction::run(pop, [&] {
771  clear();
772  delete_dummy_head();
773  });
774  }
775 
786  {
787  try {
788  free_data();
789  } catch (...) {
790  std::terminate();
791  }
792  }
793 
811  {
812  if (this == &other)
813  return *this;
814 
816  obj::transaction::run(pop, [&] {
817  using pocca_t = typename node_allocator_traits::
818  propagate_on_container_copy_assignment;
819  clear();
820  allocator_copy_assignment(_node_allocator,
821  other._node_allocator,
822  pocca_t());
823  _compare = other._compare;
824  _rnd_generator = other._rnd_generator;
825 
826  internal_copy(other);
827  });
828  return *this;
829  }
830 
853  {
854  if (this == &other)
855  return *this;
856 
858  obj::transaction::run(pop, [&] {
859  using pocma_t = typename node_allocator_traits::
860  propagate_on_container_move_assignment;
861  clear();
862  if (pocma_t::value ||
863  _node_allocator == other._node_allocator) {
864  delete_dummy_head();
865  allocator_move_assignment(_node_allocator,
866  other._node_allocator,
867  pocma_t());
868  _compare = other._compare;
869  _rnd_generator = other._rnd_generator;
870  internal_move(std::move(other));
871  } else {
872  internal_copy(
873  std::make_move_iterator(other.begin()),
874  std::make_move_iterator(other.end()));
875  }
876  });
877  return *this;
878  }
879 
892  operator=(std::initializer_list<value_type> il)
893  {
895  obj::transaction::run(pop, [&] {
896  clear();
897  for (auto it = il.begin(); it != il.end(); ++it)
899  });
900  return *this;
901  }
902 
919  std::pair<iterator, bool>
920  insert(const value_type &value)
921  {
922  return internal_insert(value.first, value);
923  }
924 
943  template <typename P,
944  typename std::enable_if<
945  std::is_constructible<value_type, P &&>::value>::type>
946  std::pair<iterator, bool>
947  insert(P &&value)
948  {
949  return emplace(std::forward<P>(value));
950  }
951 
968  std::pair<iterator, bool>
969  insert(value_type &&value)
970  {
971  return internal_insert(value.first, std::move(value));
972  }
973 
991  iterator
992  insert(const_iterator hint, const_reference value)
993  {
994  /* Ignore hint */
995  return insert(value).first;
996  }
997 
1018  template <typename P,
1019  typename std::enable_if<
1020  std::is_constructible<value_type, P &&>::value>::type>
1021  iterator
1022  insert(const_iterator hint, P &&value)
1023  {
1024  return emplace_hint(hint, std::forward<P>(value));
1025  }
1026 
1041  template <typename InputIterator>
1042  void
1043  insert(InputIterator first, InputIterator last)
1044  {
1045  for (InputIterator it = first; it != last; ++it)
1046  insert(*it);
1047  }
1048 
1062  void
1063  insert(std::initializer_list<value_type> ilist)
1064  {
1065  insert(ilist.begin(), ilist.end());
1066  }
1067 
1095  template <typename... Args>
1096  std::pair<iterator, bool>
1097  emplace(Args &&... args)
1098  {
1099  return internal_emplace(std::forward<Args>(args)...);
1100  }
1101 
1132  template <typename... Args>
1133  iterator
1134  emplace_hint(const_iterator hint, Args &&... args)
1135  {
1136  /* Ignore hint */
1137  return emplace(std::forward<Args>(args)...).first;
1138  }
1139 
1163  template <typename... Args>
1164  std::pair<iterator, bool>
1165  try_emplace(const key_type &k, Args &&... args)
1166  {
1167  return internal_try_emplace(k, std::forward<Args>(args)...);
1168  }
1169 
1193  template <typename... Args>
1194  std::pair<iterator, bool>
1195  try_emplace(key_type &&k, Args &&... args)
1196  {
1197  return internal_try_emplace(std::move(k),
1198  std::forward<Args>(args)...);
1199  }
1200 
1227  template <typename K, typename... Args>
1228  typename std::enable_if<
1229  has_is_transparent<key_compare>::value &&
1230  std::is_constructible<key_type, K &&>::value,
1231  std::pair<iterator, bool>>::type
1232  try_emplace(K &&k, Args &&... args)
1233  {
1234  return internal_try_emplace(std::forward<K>(k),
1235  std::forward<Args>(args)...);
1236  }
1237 
1254  iterator
1255  unsafe_erase(iterator pos)
1256  {
1257  check_outside_tx();
1258  auto &size_diff = tls_data.local().size_diff;
1259  return internal_erase(pos, size_diff);
1260  }
1261 
1278  iterator
1279  unsafe_erase(const_iterator pos)
1280  {
1281  return unsafe_erase(get_iterator(pos));
1282  }
1283 
1298  iterator
1299  unsafe_erase(const_iterator first, const_iterator last)
1300  {
1301  check_outside_tx();
1302  obj::pool_base pop = get_pool_base();
1303  auto &size_diff = tls_data.local().size_diff;
1304 
1305  obj::transaction::run(pop, [&] {
1306  while (first != last) {
1307  first = internal_erase(first, size_diff);
1308  }
1309  });
1310 
1311  return get_iterator(first);
1312  }
1313 
1326  size_type
1327  unsafe_erase(const key_type &key)
1328  {
1329  std::pair<iterator, iterator> range = equal_range(key);
1330  size_type sz = static_cast<size_type>(
1331  std::distance(range.first, range.second));
1332  unsafe_erase(range.first, range.second);
1333  return sz;
1334  }
1335 
1354  template <
1355  typename K,
1356  typename = typename std::enable_if<
1357  has_is_transparent<key_compare>::value &&
1358  !std::is_convertible<K, iterator>::value &&
1359  !std::is_convertible<K, const_iterator>::value,
1360  K>::type>
1361  size_type
1362  unsafe_erase(const K &key)
1363  {
1364  std::pair<iterator, iterator> range = equal_range(key);
1365  size_type sz = static_cast<size_type>(
1366  std::distance(range.first, range.second));
1367  unsafe_erase(range.first, range.second);
1368  return sz;
1369  }
1370 
1381  iterator
1382  lower_bound(const key_type &key)
1383  {
1384  return internal_get_bound(key, _compare);
1385  }
1386 
1397  const_iterator
1398  lower_bound(const key_type &key) const
1399  {
1400  return internal_get_bound(key, _compare);
1401  }
1402 
1416  template <typename K,
1417  typename = typename std::enable_if<
1418  has_is_transparent<key_compare>::value, K>::type>
1419  iterator
1420  lower_bound(const K &x)
1421  {
1422  return internal_get_bound(x, _compare);
1423  }
1424 
1438  template <typename K,
1439  typename = typename std::enable_if<
1440  has_is_transparent<key_compare>::value, K>::type>
1441  const_iterator
1442  lower_bound(const K &x) const
1443  {
1444  return internal_get_bound(x, _compare);
1445  }
1446 
1457  iterator
1458  upper_bound(const key_type &key)
1459  {
1460  return internal_get_bound(key, not_greater_compare(_compare));
1461  }
1462 
1473  const_iterator
1474  upper_bound(const key_type &key) const
1475  {
1476  return internal_get_bound(key, not_greater_compare(_compare));
1477  }
1478 
1492  template <typename K,
1493  typename = typename std::enable_if<
1494  has_is_transparent<key_compare>::value, K>::type>
1495  iterator
1496  upper_bound(const K &x)
1497  {
1498  return internal_get_bound(x, not_greater_compare(_compare));
1499  }
1500 
1514  template <typename K,
1515  typename = typename std::enable_if<
1516  has_is_transparent<key_compare>::value, K>::type>
1517  const_iterator
1518  upper_bound(const K &x) const
1519  {
1520  return internal_get_bound(x, not_greater_compare(_compare));
1521  }
1522 
1531  iterator
1532  find(const key_type &key)
1533  {
1534  return internal_find(key);
1535  }
1536 
1545  const_iterator
1546  find(const key_type &key) const
1547  {
1548  return internal_find(key);
1549  }
1550 
1563  template <typename K,
1564  typename = typename std::enable_if<
1565  has_is_transparent<key_compare>::value, K>::type>
1566  iterator
1567  find(const K &x)
1568  {
1569  return internal_find(x);
1570  }
1571 
1584  template <typename K,
1585  typename = typename std::enable_if<
1586  has_is_transparent<key_compare>::value, K>::type>
1587  const_iterator
1588  find(const K &x) const
1589  {
1590  return internal_find(x);
1591  }
1592 
1602  size_type
1603  count(const key_type &key) const
1604  {
1605  return internal_count(key);
1606  }
1607 
1620  template <typename K,
1621  typename = typename std::enable_if<
1622  has_is_transparent<key_compare>::value, K>::type>
1623  size_type
1624  count(const K &key) const
1625  {
1626  return internal_count(key);
1627  }
1628 
1637  bool
1638  contains(const key_type &key) const
1639  {
1640  return find(key) != end();
1641  }
1642 
1655  template <typename K,
1656  typename = typename std::enable_if<
1657  has_is_transparent<key_compare>::value, K>::type>
1658  bool
1659  contains(const K &x) const
1660  {
1661  return find(x) != end();
1662  }
1663 
1672  void
1674  {
1675  assert(dummy_head(pool_uuid)->height() > 0);
1676  obj::pool_base pop = get_pool_base();
1677 
1678  persistent_node_ptr current = dummy_head(pool_uuid)->next(0);
1679 
1680  obj::transaction::run(pop, [&] {
1681  while (current) {
1682  assert(current(pool_uuid)->height() > 0);
1683  persistent_node_ptr next =
1684  current(pool_uuid)->next(0);
1685  delete_node(current);
1686  current = next;
1687  }
1688 
1689  node_ptr head = dummy_head.get(pool_uuid);
1690  for (size_type i = 0; i < head->height(); ++i) {
1691  head->set_next(i, nullptr);
1692  }
1693 
1694  on_init_size = 0;
1695  tls_data.clear();
1696  obj::transaction::snapshot((size_t *)&_size);
1697  _size = 0;
1698  });
1699  }
1700 
1707  iterator
1709  {
1710  return iterator(
1711  pool_uuid,
1712  dummy_head.get(pool_uuid)->next(0).get(pool_uuid));
1713  }
1714 
1721  const_iterator
1722  begin() const
1723  {
1724  return const_iterator(
1725  pool_uuid,
1726  dummy_head.get(pool_uuid)->next(0).get(pool_uuid));
1727  }
1728 
1735  const_iterator
1736  cbegin() const
1737  {
1738  return const_iterator(
1739  pool_uuid,
1740  dummy_head.get(pool_uuid)->next(0).get(pool_uuid));
1741  }
1742 
1750  iterator
1752  {
1753  return iterator(pool_uuid, nullptr);
1754  }
1755 
1763  const_iterator
1764  end() const
1765  {
1766  return const_iterator(pool_uuid, nullptr);
1767  }
1768 
1776  const_iterator
1777  cend() const
1778  {
1779  return const_iterator(pool_uuid, nullptr);
1780  }
1781 
1788  size_type
1789  size() const
1790  {
1791  return _size.load(std::memory_order_relaxed);
1792  }
1793 
1801  size_type
1802  max_size() const
1803  {
1804  return std::numeric_limits<difference_type>::max();
1805  }
1806 
1813  bool
1814  empty() const
1815  {
1816  return 0 == size();
1817  }
1818 
1825  const allocator_type &
1827  {
1828  return _node_allocator;
1829  }
1830 
1836  allocator_type &
1838  {
1839  return _node_allocator;
1840  }
1841 
1849  void
1851  {
1852  obj::pool_base pop = get_pool_base();
1853  obj::transaction::run(pop, [&] {
1854  using pocs_t = typename node_allocator_traits::
1855  propagate_on_container_swap;
1856  allocator_swap(_node_allocator, other._node_allocator,
1857  pocs_t());
1858  std::swap(_compare, other._compare);
1859  std::swap(_rnd_generator, other._rnd_generator);
1860  std::swap(dummy_head, other.dummy_head);
1862 
1863  obj::transaction::snapshot((size_t *)&_size);
1864  obj::transaction::snapshot((size_t *)&(other._size));
1865  _size = other._size.exchange(_size,
1866  std::memory_order_relaxed);
1867  });
1868  }
1869 
1889  std::pair<iterator, iterator>
1890  equal_range(const key_type &key)
1891  {
1892  return std::pair<iterator, iterator>(lower_bound(key),
1893  upper_bound(key));
1894  }
1895 
1915  std::pair<const_iterator, const_iterator>
1916  equal_range(const key_type &key) const
1917  {
1918  return std::pair<const_iterator, const_iterator>(
1919  lower_bound(key), upper_bound(key));
1920  }
1921 
1944  template <typename K,
1945  typename = typename std::enable_if<
1946  has_is_transparent<key_compare>::value, K>::type>
1947  std::pair<iterator, iterator>
1948  equal_range(const K &x)
1949  {
1950  return std::pair<iterator, iterator>(lower_bound(x),
1951  upper_bound(x));
1952  }
1953 
1976  template <typename K,
1977  typename = typename std::enable_if<
1978  has_is_transparent<key_compare>::value, K>::type>
1979  std::pair<const_iterator, const_iterator>
1980  equal_range(const K &key) const
1981  {
1982  return std::pair<const_iterator, const_iterator>(
1983  lower_bound(key), upper_bound(key));
1984  }
1985 
1991  const key_compare &
1992  key_comp() const
1993  {
1994  return _compare;
1995  }
1996 
2002  key_compare &
2004  {
2005  return _compare;
2006  }
2007 
2008 private:
2009  /* Status flags stored in insert_stage field */
2010  enum insert_stage_type : uint8_t { not_started = 0, in_progress = 1 };
2011  /*
2012  * Structure of thread local data.
2013  * Size should be 64 bytes.
2014  */
2015  struct tls_entry_type {
2016  persistent_node_ptr ptr;
2017  obj::p<difference_type> size_diff;
2018  obj::p<insert_stage_type> insert_stage;
2019 
2020  char reserved[64 - sizeof(decltype(ptr)) -
2021  sizeof(decltype(size_diff)) -
2022  sizeof(decltype(insert_stage))];
2023  };
2024  static_assert(sizeof(tls_entry_type) == 64,
2025  "The size of tls_entry_type should be 64 bytes.");
2026 
2034  void
2036  {
2037  if (pmemobj_tx_stage() != TX_STAGE_WORK)
2039  "Function called out of transaction scope.");
2040  }
2041 
2042  /* Helper method which throws an exception when called in a tx */
2043  static inline void
2044  check_outside_tx()
2045  {
2046  if (pmemobj_tx_stage() != TX_STAGE_NONE)
2048  "Function called inside transaction scope.");
2049  }
2050 
2051  void
2052  init()
2053  {
2054  if (pool_uuid == 0)
2055  throw pmem::pool_error("Invalid pool handle.");
2056 
2057  _size = 0;
2058  on_init_size = 0;
2060  }
2061 
2062  void
2063  internal_move(concurrent_skip_list &&other)
2064  {
2065  assert(this->empty());
2066  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2067  dummy_head = other.dummy_head;
2068  other.dummy_head = nullptr;
2069  other.create_dummy_head();
2070 
2071  _size.store(other._size.load(std::memory_order_relaxed),
2072  std::memory_order_relaxed);
2073  on_init_size = other.on_init_size;
2074  }
2075 
2076  static const_reference
2077  get_val(const_node_ptr n)
2078  {
2079  assert(n);
2080  return *(n->get());
2081  }
2082 
2083  static reference
2084  get_val(node_ptr n)
2085  {
2086  assert(n);
2087  return *(n->get());
2088  }
2089 
2090  static const key_type &
2091  get_key(const_node_ptr n)
2092  {
2093  assert(n);
2094  return traits_type::get_key(get_val(n));
2095  }
2096 
2097  template <typename K>
2098  iterator
2099  internal_find(const K &key)
2100  {
2101  iterator it = lower_bound(key);
2102  return (it == end() || _compare(key, traits_type::get_key(*it)))
2103  ? end()
2104  : it;
2105  }
2106 
2107  template <typename K>
2108  const_iterator
2109  internal_find(const K &key) const
2110  {
2111  const_iterator it = lower_bound(key);
2112  return (it == end() || _compare(key, traits_type::get_key(*it)))
2113  ? end()
2114  : it;
2115  }
2116 
2117  template <typename K>
2118  size_type
2119  internal_count(const K &key) const
2120  {
2121  if (allow_multimapping) {
2122  std::pair<const_iterator, const_iterator> range =
2123  equal_range(key);
2124  return static_cast<size_type>(
2125  std::distance(range.first, range.second));
2126  }
2127  return (find(key) == end()) ? size_type(0) : size_type(1);
2128  }
2129 
2140  template <typename K, typename pointer_type, typename comparator>
2141  persistent_node_ptr
2142  internal_find_position(size_type level, pointer_type &prev,
2143  const K &key, const comparator &cmp) const
2144  {
2145  assert(level < prev->height());
2146  persistent_node_ptr next = prev->next(level);
2147  pointer_type curr = next.get(pool_uuid);
2148 
2149  while (curr && cmp(get_key(curr), key)) {
2150  prev = curr;
2151  assert(level < prev->height());
2152  next = prev->next(level);
2153  curr = next.get(pool_uuid);
2154  }
2155 
2156  return next;
2157  }
2158 
2169  template <typename K>
2170  void
2171  find_insert_pos(prev_array_type &prev_nodes,
2172  next_array_type &next_nodes, const K &key)
2173  {
2174  if (allow_multimapping) {
2175  fill_prev_next_arrays(prev_nodes, next_nodes, key,
2176  not_greater_compare(_compare));
2177  } else {
2178  fill_prev_next_arrays(prev_nodes, next_nodes, key,
2179  _compare);
2180  }
2181  }
2182 
2194  template <typename K, typename comparator>
2195  void
2196  fill_prev_next_arrays(prev_array_type &prev_nodes,
2197  next_array_type &next_nodes, const K &key,
2198  const comparator &cmp)
2199  {
2200  node_ptr prev = dummy_head.get(pool_uuid);
2201  prev_nodes.fill(prev);
2202  next_nodes.fill(nullptr);
2203 
2204  for (size_type h = prev->height(); h > 0; --h) {
2205  persistent_node_ptr next =
2206  internal_find_position(h - 1, prev, key, cmp);
2207  prev_nodes[h - 1] = prev;
2208  next_nodes[h - 1] = next;
2209  }
2210  }
2211 
2212  template <typename K, typename... Args>
2213  std::pair<iterator, bool>
2214  internal_try_emplace(K &&key, Args &&... args)
2215  {
2216  return internal_insert(
2217  key, std::piecewise_construct,
2218  std::forward_as_tuple(std::forward<K>(key)),
2219  std::forward_as_tuple(std::forward<Args>(args)...));
2220  }
2221 
2222  template <typename... Args>
2223  std::pair<iterator, bool>
2224  internal_emplace(Args &&... args)
2225  {
2226  check_outside_tx();
2227  tls_entry_type &tls_entry = tls_data.local();
2228  obj::pool_base pop = get_pool_base();
2229 
2230  obj::transaction::run(pop, [&] {
2231  assert(tls_entry.ptr == nullptr);
2232  tls_entry.ptr =
2233  create_node(std::forward<Args>(args)...);
2234  ++tls_entry.size_diff;
2235  tls_entry.insert_stage = not_started;
2236  });
2237 
2238  node_ptr n = tls_entry.ptr.get(pool_uuid);
2239  size_type height = n->height();
2240 
2241  std::pair<iterator, bool> insert_result = internal_insert_node(
2242  get_key(n), height,
2243  [&](const next_array_type &next_nodes)
2244  -> persistent_node_ptr & {
2245  assert(tls_entry.insert_stage == not_started);
2246  assert(tls_entry.ptr != nullptr);
2247 
2248  n->set_nexts(pop, next_nodes.data(), height);
2249 
2250  tls_entry.insert_stage = in_progress;
2251  pop.persist(&(tls_entry.insert_stage),
2252  sizeof(tls_entry.insert_stage));
2253 
2254  return tls_entry.ptr;
2255  });
2256 
2257  if (!insert_result.second) {
2258  assert(tls_entry.ptr != nullptr);
2259  assert(tls_entry.insert_stage == not_started);
2260 
2261  obj::transaction::run(pop, [&] {
2262  --tls_entry.size_diff;
2263  delete_node(tls_entry.ptr);
2264  tls_entry.ptr = nullptr;
2265  });
2266  }
2267 
2268  assert(tls_entry.ptr == nullptr);
2269  return insert_result;
2270  }
2271 
2276  template <typename... Args>
2277  std::pair<iterator, bool>
2278  internal_unsafe_emplace(Args &&... args)
2279  {
2281 
2282  persistent_node_ptr new_node =
2283  create_node(std::forward<Args>(args)...);
2284 
2285  node_ptr n = new_node.get(pool_uuid);
2286  size_type height = n->height();
2287 
2288  std::pair<iterator, bool> insert_result = internal_insert_node(
2289  get_key(n), height,
2290  [&](const next_array_type &next_nodes)
2291  -> persistent_node_ptr & {
2292  assert(new_node != nullptr);
2293 
2294  n->set_nexts(next_nodes.data(), height);
2295 
2296  return new_node;
2297  });
2298 
2299  if (insert_result.second) {
2300  ++on_init_size;
2301  } else {
2302  assert(new_node != nullptr);
2303 
2304  delete_node(new_node);
2305  }
2306 
2307  return insert_result;
2308  }
2309 
2313  template <typename K, typename... Args>
2314  std::pair<iterator, bool>
2315  internal_insert(const K &key, Args &&... args)
2316  {
2317  check_outside_tx();
2318  tls_entry_type &tls_entry = tls_data.local();
2319  assert(tls_entry.ptr == nullptr);
2320 
2321  size_type height = random_level();
2322 
2323  std::pair<iterator, bool> insert_result = internal_insert_node(
2324  key, height,
2325  [&](const next_array_type &next_nodes)
2326  -> persistent_node_ptr & {
2327  obj::pool_base pop = get_pool_base();
2328 
2329  obj::transaction::manual tx(pop);
2330  tls_entry.ptr = create_node(
2331  std::forward_as_tuple(
2332  height, next_nodes.data()),
2333  std::forward_as_tuple(
2334  std::forward<Args>(args)...));
2335 
2336  ++(tls_entry.size_diff);
2337  tls_entry.insert_stage = in_progress;
2339 
2340  assert(tls_entry.ptr != nullptr);
2341  return tls_entry.ptr;
2342  });
2343 
2344  assert(tls_entry.ptr == nullptr);
2345 
2346  return insert_result;
2347  }
2348 
2352  template <typename K, typename PrepareNode>
2353  std::pair<iterator, bool>
2354  internal_insert_node(const K &key, size_type height,
2355  PrepareNode &&prepare_new_node)
2356  {
2357  prev_array_type prev_nodes;
2358  next_array_type next_nodes;
2359  node_ptr n = nullptr;
2360 
2361  do {
2362  find_insert_pos(prev_nodes, next_nodes, key);
2363 
2364  node_ptr next = next_nodes[0].get(pool_uuid);
2365  if (next && !allow_multimapping &&
2366  !_compare(key, get_key(next))) {
2367 
2368  return std::pair<iterator, bool>(
2369  iterator(pool_uuid, next), false);
2370  }
2371 
2372  } while ((n = try_insert_node(prev_nodes, next_nodes, height,
2373  std::forward<PrepareNode>(
2374  prepare_new_node))) ==
2375  nullptr);
2376 
2377  assert(n);
2378  return std::pair<iterator, bool>(iterator(pool_uuid, n), true);
2379  }
2380 
2386  template <typename PrepareNode>
2387  node_ptr
2388  try_insert_node(prev_array_type &prev_nodes,
2389  const next_array_type &next_nodes, size_type height,
2390  PrepareNode &&prepare_new_node)
2391  {
2392  assert(dummy_head(pool_uuid)->height() >= height);
2393 
2394  lock_array locks;
2395  if (!try_lock_nodes(height, prev_nodes, next_nodes, locks)) {
2396  return nullptr;
2397  }
2398 
2399  node_lock_type new_node_lock;
2400 
2401  persistent_node_ptr &new_node = prepare_new_node(next_nodes);
2402  assert(new_node != nullptr);
2403  node_ptr n = new_node.get(pool_uuid);
2404 
2405  /*
2406  * We need to hold lock to the new node until changes
2407  * are committed to persistent domain. Otherwise, the
2408  * new node would be visible to concurrent inserts
2409  * before it is persisted.
2410  */
2411  new_node_lock = n->acquire();
2412 
2413  obj::pool_base pop = get_pool_base();
2414  /*
2415  * In the loop below we are linking a new node to all layers of
2416  * the skip list. Transaction is not required because in case of
2417  * failure the node is reachable via a pointer from persistent
2418  * TLS. During recovery, we will complete the insert. It is also
2419  * OK if concurrent readers will see not a fully-linked node
2420  * because during recovery the insert procedure will be
2421  * completed.
2422  */
2423  for (size_type level = 0; level < height; ++level) {
2424  assert(prev_nodes[level]->height() > level);
2425  assert(prev_nodes[level]->next(level) ==
2426  next_nodes[level]);
2427  assert(prev_nodes[level]->next(level) ==
2428  n->next(level));
2429  prev_nodes[level]->set_next(pop, level, new_node);
2430  }
2431 
2432 #ifndef NDEBUG
2433  try_insert_node_finish_marker();
2434 #endif
2435 
2436  new_node = nullptr;
2437  /* We need to persist the node pointer. Otherwise, on a restart,
2438  * this pointer might be not null but the node can be already
2439  * deleted. */
2440  pop.persist(&new_node, sizeof(new_node));
2441 
2442  ++_size;
2443 #if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
2444  VALGRIND_PMC_DO_FLUSH(&_size, sizeof(_size));
2445 #endif
2446 
2447  assert(n);
2448  return n;
2449  }
2450 
2455  bool
2456  check_prev_array(const prev_array_type &prevs, size_type height)
2457  {
2458  for (size_type l = 1; l < height; ++l) {
2459  if (prevs[l] == dummy_head.get(pool_uuid)) {
2460  continue;
2461  }
2462 
2463  assert(prevs[l - 1] != dummy_head.get(pool_uuid));
2464  assert(!_compare(get_key(prevs[l - 1]),
2465  get_key(prevs[l])));
2466  }
2467 
2468  return true;
2469  }
2470 
2471  bool
2472  try_lock_nodes(size_type height, prev_array_type &prevs,
2473  const next_array_type &nexts, lock_array &locks)
2474  {
2475  assert(check_prev_array(prevs, height));
2476 
2477  for (size_type l = 0; l < height; ++l) {
2478  if (l == 0 || prevs[l] != prevs[l - 1]) {
2479  locks[l] = prevs[l]->acquire();
2480  }
2481 
2482  persistent_node_ptr next = prevs[l]->next(l);
2483  if (next != nexts[l])
2484  /* Other thread inserted to this position and
2485  * modified the pointer before we acquired the
2486  * lock */
2487  return false;
2488  }
2489 
2490  return true;
2491  }
2492 
2504  template <typename K, typename comparator>
2505  const_iterator
2506  internal_get_bound(const K &key, const comparator &cmp) const
2507  {
2508  const_node_ptr prev = dummy_head.get(pool_uuid);
2509  assert(prev->height() > 0);
2510  persistent_node_ptr next = nullptr;
2511 
2512  for (size_type h = prev->height(); h > 0; --h) {
2513  next = internal_find_position(h - 1, prev, key, cmp);
2514  }
2515 
2516  return const_iterator(pool_uuid, next.get(pool_uuid));
2517  }
2518 
2530  template <typename K, typename comparator>
2531  iterator
2532  internal_get_bound(const K &key, const comparator &cmp)
2533  {
2534  node_ptr prev = dummy_head.get(pool_uuid);
2535  assert(prev->height() > 0);
2536  persistent_node_ptr next = nullptr;
2537 
2538  for (size_type h = prev->height(); h > 0; --h) {
2539  next = internal_find_position(h - 1, prev, key, cmp);
2540  }
2541 
2542  return iterator(pool_uuid, next.get(pool_uuid));
2543  }
2544 
2545  iterator
2546  internal_erase(const_iterator pos, obj::p<difference_type> &size_diff)
2547  {
2548  assert(pos != end());
2549 
2550  obj::pool_base pop = get_pool_base();
2551 
2552  std::pair<persistent_node_ptr, persistent_node_ptr>
2553  extract_result(nullptr, nullptr);
2554 
2555  obj::transaction::run(pop, [&] {
2556  extract_result = internal_extract(pos);
2557 
2558  /* Make sure that node was extracted */
2559  assert(extract_result.first != nullptr);
2560  delete_node(extract_result.first);
2561  --size_diff;
2562  obj::transaction::snapshot((size_type *)&_size);
2563  --_size;
2564  });
2565 
2566  return iterator(pool_uuid,
2567  extract_result.second.get(pool_uuid));
2568  }
2569 
2573  std::pair<persistent_node_ptr, persistent_node_ptr>
2574  internal_extract(const_iterator it)
2575  {
2576  assert(dummy_head(pool_uuid)->height() > 0);
2577  assert(it != end());
2578  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2579 
2580  const key_type &key = traits_type::get_key(*it);
2581 
2582  prev_array_type prev_nodes;
2583  next_array_type next_nodes;
2584 
2585  fill_prev_next_arrays(prev_nodes, next_nodes, key, _compare);
2586 
2587  node_ptr erase_node = next_nodes[0].get(pool_uuid);
2588  assert(erase_node != nullptr);
2589 
2590  if (!_compare(key, get_key(erase_node))) {
2591  /* XXX: this assertion will fail in case of multimap
2592  * because we take the first node with the same key.
2593  * Need to extend algorithm for mutimap. */
2594  assert(erase_node == it.node);
2595  return internal_extract_node(prev_nodes, next_nodes,
2596  erase_node);
2597  }
2598 
2599  return std::pair<persistent_node_ptr, persistent_node_ptr>(
2600  nullptr, nullptr);
2601  }
2602 
2603  std::pair<persistent_node_ptr, persistent_node_ptr>
2604  internal_extract_node(const prev_array_type &prev_nodes,
2605  const next_array_type &next_nodes,
2606  node_ptr erase_node)
2607  {
2608  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2609  assert(erase_node != nullptr);
2610  for (size_type level = 0; level < erase_node->height();
2611  ++level) {
2612  assert(prev_nodes[level]->height() > level);
2613  assert(next_nodes[level].get(pool_uuid) == erase_node);
2614  prev_nodes[level]->set_next(level,
2615  erase_node->next(level));
2616  }
2617 
2618  return std::pair<persistent_node_ptr, persistent_node_ptr>(
2619  next_nodes[0], erase_node->next(0));
2620  }
2621 
2626  obj::pool_base
2628  {
2629  PMEMobjpool *pop = pmemobj_pool_by_ptr(this);
2630  return obj::pool_base(pop);
2631  }
2632 
2633  void
2634  internal_copy(const concurrent_skip_list &other)
2635  {
2636  internal_copy(other.begin(), other.end());
2637  }
2638 
2639  template <typename Iterator>
2640  void
2641  internal_copy(Iterator first, Iterator last)
2642  {
2643  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2644 
2645  prev_array_type prev_nodes;
2646  prev_nodes.fill(dummy_head.get(pool_uuid));
2647  size_type sz = 0;
2648 
2649  for (; first != last; ++first, ++sz) {
2650  persistent_node_ptr new_node = create_node(*first);
2651  node_ptr n = new_node.get(pool_uuid);
2652  for (size_type level = 0; level < n->height();
2653  ++level) {
2654  prev_nodes[level]->set_next(level, new_node);
2655  prev_nodes[level] = n;
2656  }
2657  }
2658 
2659  on_init_size = sz;
2660  /*
2661  * As internal_swap can only be called from one thread, and
2662  * there can be an outer transaction we must make sure that size
2663  * change is transactional
2664  */
2665  obj::transaction::snapshot((size_type *)&_size);
2666  _size = sz;
2667  assert(std::is_sorted(
2668  this->begin(), this->end(),
2669  [&](const value_type &lhs, const value_type &rhs) {
2670  return lhs.first < rhs.first;
2671  }));
2672  }
2673 
2675  size_type
2677  {
2678  return _rnd_generator();
2679  }
2680 
2681  static size_type
2682  calc_node_size(size_type height)
2683  {
2684  return sizeof(list_node_type) +
2685  height * sizeof(typename list_node_type::node_pointer);
2686  }
2687 
2689  template <typename... Args>
2690  persistent_node_ptr
2691  create_node(Args &&... args)
2692  {
2693  size_type levels = random_level();
2694 
2695  return create_node(
2696  std::forward_as_tuple(levels),
2697  std::forward_as_tuple(std::forward<Args>(args)...));
2698  }
2699 
2700  template <typename... NodeArgs, typename... ValueArgs>
2701  persistent_node_ptr
2702  create_node(std::tuple<NodeArgs...> &&node_args,
2703  std::tuple<ValueArgs...> &&value_args)
2704  {
2705  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2706 
2707  persistent_node_ptr node = creates_dummy_node(
2708  std::forward<std::tuple<NodeArgs...>>(node_args),
2709  index_sequence_for<NodeArgs...>{});
2710 
2711  construct_value_type(
2712  node,
2713  std::forward<std::tuple<ValueArgs...>>(value_args),
2714  index_sequence_for<ValueArgs...>{});
2715 
2716  return node;
2717  }
2718 
2719  template <typename Tuple, size_t... I>
2720  void
2721  construct_value_type(persistent_node_ptr node, Tuple &&args,
2722  index_sequence<I...>)
2723  {
2724  node_ptr new_node = node.get(pool_uuid);
2725 
2726  node_allocator_traits::construct(
2727  _node_allocator, new_node->get(),
2728  std::get<I>(std::forward<Tuple>(args))...);
2729  }
2730 
2736  void
2738  {
2739  dummy_head = creates_dummy_node(MAX_LEVEL);
2740  }
2741 
2742  template <typename Tuple, size_t... I>
2743  persistent_node_ptr
2744  creates_dummy_node(Tuple &&args, index_sequence<I...>)
2745  {
2746  return creates_dummy_node(
2747  std::get<I>(std::forward<Tuple>(args))...);
2748  }
2749 
2759  template <typename... Args>
2760  persistent_node_ptr
2761  creates_dummy_node(size_type height, Args &&... args)
2762  {
2763  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2764  size_type sz = calc_node_size(height);
2765 
2766  persistent_node_ptr n =
2767  node_allocator_traits::allocate(_node_allocator, sz)
2768  .raw();
2769 
2770  assert(n != nullptr);
2771 
2772  node_allocator_traits::construct(_node_allocator,
2773  n.get(pool_uuid), height,
2774  std::forward<Args>(args)...);
2775 
2776  return n;
2777  }
2778 
2779  template <bool is_dummy = false>
2780  void
2781  delete_node(persistent_node_ptr &node)
2782  {
2783  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2784  node_ptr n = node.get(pool_uuid);
2785  size_type sz = calc_node_size(n->height());
2786 
2787  /* Destroy value */
2788  if (!is_dummy)
2789  node_allocator_traits::destroy(_node_allocator,
2790  n->get());
2791  /* Destroy node */
2792  node_allocator_traits::destroy(_node_allocator, n);
2793  /* Deallocate memory */
2794  deallocate_node(node, sz);
2795  node = nullptr;
2796  }
2797 
2798  void
2799  deallocate_node(persistent_node_ptr &node, size_type sz)
2800  {
2801  /*
2802  * Each node object has different size which depends on number
2803  * of layers the node is linked. Therefore, allocate/deallocate
2804  * just a raw byte array. persistent_ptr<uint8_t> is used as a
2805  * pointer to raw array of bytes.
2806  */
2808  node.get_persistent_ptr(pool_uuid).raw();
2809  node_allocator_traits::deallocate(_node_allocator, tmp, sz);
2810  }
2811 
2812  void
2813  delete_dummy_head()
2814  {
2815  assert(dummy_head != nullptr);
2816  delete_node<true>(dummy_head);
2817  assert(dummy_head == nullptr);
2818  }
2819 
2820  iterator
2821  get_iterator(const_iterator it)
2822  {
2823  return iterator(
2824  pool_uuid,
2825  const_cast<typename iterator::node_ptr>(it.node));
2826  }
2827 
2829  void
2831  {
2832  int64_t last_run_size = 0;
2833  obj::pool_base pop = get_pool_base();
2834 
2835  for (auto &tls_entry : tls_data) {
2836  persistent_node_ptr &node = tls_entry.ptr;
2837  auto &size_diff = tls_entry.size_diff;
2838  if (node) {
2839  /*
2840  * We are completing inserts which were in
2841  * progress before the crash because readers
2842  * might saw incompleted inserts before the
2843  * crash. We set the in_progress flag inside
2844  * try_insert_node function when we locked the
2845  * predecessors for the new node, therefore,
2846  * only single node with the same key might have
2847  * the in_progress status.
2848  */
2849  if (tls_entry.insert_stage == in_progress) {
2850  complete_insert(tls_entry);
2851  } else {
2852  obj::transaction::run(pop, [&] {
2853  --(tls_entry.size_diff);
2854  delete_node(node);
2855  node = nullptr;
2856  });
2857  }
2858  }
2859 
2860  assert(node == nullptr);
2861 
2862  last_run_size += size_diff;
2863  }
2864 
2865  /* Make sure that on_init_size + last_run_size >= 0 */
2866  assert(last_run_size >= 0 ||
2867  on_init_size >
2868  static_cast<size_type>(std::abs(last_run_size)));
2869  obj::transaction::run(pop, [&] {
2870  tls_data.clear();
2871  on_init_size += static_cast<size_t>(last_run_size);
2872  });
2873  _size = on_init_size;
2874 #if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
2875  VALGRIND_PMC_DO_FLUSH(&_size, sizeof(_size));
2876 #endif
2877  }
2878 
2879  void
2880  complete_insert(tls_entry_type &tls_entry)
2881  {
2882  persistent_node_ptr &node = tls_entry.ptr;
2883  assert(node != nullptr);
2884  assert(tls_entry.insert_stage == in_progress);
2885  prev_array_type prev_nodes;
2886  next_array_type next_nodes;
2887  node_ptr n = node.get(pool_uuid);
2888  const key_type &key = get_key(n);
2889  size_type height = n->height();
2890 
2891  fill_prev_next_arrays(prev_nodes, next_nodes, key, _compare);
2892  obj::pool_base pop = get_pool_base();
2893 
2894  /* Node was partially linked */
2895  for (size_type level = 0; level < height; ++level) {
2896  assert(prev_nodes[level]->height() > level);
2897  assert(prev_nodes[level]->next(level) ==
2898  next_nodes[level]);
2899 
2900  if (prev_nodes[level]->next(level) != node) {
2901  /* Otherwise, node already linked on
2902  * this layer */
2903  assert(n->next(level) == next_nodes[level]);
2904  prev_nodes[level]->set_next(pop, level, node);
2905  }
2906  }
2907 
2908  node = nullptr;
2909  pop.persist(&node, sizeof(node));
2910  }
2911 
2912  struct not_greater_compare {
2913  const key_compare &my_less_compare;
2914 
2915  not_greater_compare(const key_compare &less_compare)
2916  : my_less_compare(less_compare)
2917  {
2918  }
2919 
2920  template <typename K1, typename K2>
2921  bool
2922  operator()(const K1 &first, const K2 &second) const
2923  {
2924  return !my_less_compare(second, first);
2925  }
2926  };
2927 
2928  const uint64_t pool_uuid = pmemobj_oid(this).pool_uuid_lo;
2929  node_allocator_type _node_allocator;
2930  key_compare _compare;
2931  random_level_generator_type _rnd_generator;
2932  persistent_node_ptr dummy_head;
2933 
2934  enumerable_thread_specific<tls_entry_type> tls_data;
2935 
2936  std::atomic<size_type> _size;
2937 
2944 }; /* class concurrent_skip_list */
2945 
2946 template <typename Key, typename Value, typename KeyCompare,
2947  typename RND_GENERATOR, typename Allocator, bool AllowMultimapping,
2948  size_t MAX_LEVEL>
2949 class map_traits {
2950 public:
2951  static constexpr size_t max_level = MAX_LEVEL;
2952  using random_generator_type = RND_GENERATOR;
2953  using key_type = Key;
2954  using mapped_type = Value;
2955  using compare_type = KeyCompare;
2956  using value_type = pair<const key_type, mapped_type>;
2957  using reference = value_type &;
2958  using const_reference = const value_type &;
2959  using allocator_type = Allocator;
2960 
2967  constexpr static bool allow_multimapping = AllowMultimapping;
2968 
2969  static const key_type &
2970  get_key(const_reference val)
2971  {
2972  return val.first;
2973  }
2974 }; /* class map_traits */
2975 
2976 } /* namespace detail */
2977 } /* namespace pmem */
2978 
2979 #endif /* PMEMOBJ_CONCURRENT_SKIP_LIST_IMPL_HPP */
pmem::detail::concurrent_skip_list::fill_prev_next_arrays
void fill_prev_next_arrays(prev_array_type &prev_nodes, next_array_type &next_nodes, const K &key, const comparator &cmp)
The method finds successor and predecessr nodes on each level of the skip list for the given.
Definition: concurrent_skip_list_impl.hpp:2196
pmem::detail::allocator_swap
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, std::true_type)
Swap implementation for allocators if propagate_on_container_swap == true_type.
Definition: concurrent_skip_list_impl.hpp:130
pmem::detail::concurrent_skip_list::internal_extract
std::pair< persistent_node_ptr, persistent_node_ptr > internal_extract(const_iterator it)
Definition: concurrent_skip_list_impl.hpp:2574
pmem::detail::concurrent_skip_list::internal_get_bound
iterator internal_get_bound(const K &key, const comparator &cmp)
Returns an iterator pointing to the first element from the list for which cmp(element,...
Definition: concurrent_skip_list_impl.hpp:2532
pmem::detail::concurrent_skip_list::unsafe_erase
iterator unsafe_erase(const_iterator pos)
Removes the element at pos from the container.
Definition: concurrent_skip_list_impl.hpp:1279
pmem::obj::transaction::commit
static void commit()
Manually commit a transaction.
Definition: transaction.hpp:340
pmem::detail::concurrent_skip_list::upper_bound
iterator upper_bound(const K &x)
Returns an iterator pointing to the first element that compares greater to the value x.
Definition: concurrent_skip_list_impl.hpp:1496
pmem::detail::concurrent_skip_list::try_emplace
std::pair< iterator, bool > try_emplace(const key_type &k, Args &&... args)
If a key equivalent to k already exists in the container, does nothing.
Definition: concurrent_skip_list_impl.hpp:1165
pmem::obj::mutex
Persistent memory resident mutex implementation.
Definition: mutex.hpp:31
pmem::detail::concurrent_skip_list::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Inserts a new element to the container as close as possible to the position just before hint.
Definition: concurrent_skip_list_impl.hpp:1134
pmem::detail::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(const concurrent_skip_list &other)
Copy constructor.
Definition: concurrent_skip_list_impl.hpp:628
pmem::detail::concurrent_skip_list::insert
std::pair< iterator, bool > insert(P &&value)
Inserts value.
Definition: concurrent_skip_list_impl.hpp:947
pmem::detail::concurrent_skip_list::internal_insert_node
std::pair< iterator, bool > internal_insert_node(const K &key, size_type height, PrepareNode &&prepare_new_node)
Try to insert new node to the skip list in a thread-safe way.
Definition: concurrent_skip_list_impl.hpp:2354
pmem::detail::concurrent_skip_list::get_allocator
allocator_type & get_allocator()
Returns a reference to the allocator associated with the container.
Definition: concurrent_skip_list_impl.hpp:1837
pmem::detail::concurrent_skip_list::key_comp
key_compare & key_comp()
Returns a reference to the object that compares the keys.
Definition: concurrent_skip_list_impl.hpp:2003
pmem::detail::concurrent_skip_list::cend
const_iterator cend() const
Returns an iterator to the element following the last element of the map.
Definition: concurrent_skip_list_impl.hpp:1777
pmem::pool_error
Custom pool error class.
Definition: pexceptions.hpp:45
pmem::detail::concurrent_skip_list::lower_bound
iterator lower_bound(const K &x)
Returns an iterator pointing to the first element that compares not less (i.e.
Definition: concurrent_skip_list_impl.hpp:1420
pmem::detail::concurrent_skip_list::cbegin
const_iterator cbegin() const
Returns an iterator to the first element of the container.
Definition: concurrent_skip_list_impl.hpp:1736
pmem::obj::pool_base::persist
void persist(const void *addr, size_t len) noexcept
Performs persist operation on a given chunk of memory.
Definition: pool.hpp:283
pmem
Persistent memory namespace.
Definition: allocation_flag.hpp:15
pmem::detail::concurrent_skip_list::contains
bool contains(const K &x) const
Checks if there is an element with key that compares equivalent to the value x.
Definition: concurrent_skip_list_impl.hpp:1659
pmem::detail::concurrent_skip_list::unsafe_erase
size_type unsafe_erase(const key_type &key)
Removes the element (if one exists) with the key equivalent to key.
Definition: concurrent_skip_list_impl.hpp:1327
pmem::obj::p::swap
void swap(p &other)
Swaps two p objects of the same type.
Definition: p.hpp:140
common.hpp
Commonly used functionality.
pmem::detail::concurrent_skip_list::find
iterator find(const key_type &key)
Finds an element with key equivalent to key.
Definition: concurrent_skip_list_impl.hpp:1532
template_helpers.hpp
Commonly used SFINAE helpers.
pmem::detail::concurrent_skip_list::try_emplace
std::enable_if< has_is_transparent< key_compare >::value &&std::is_constructible< key_type, K && >::value, std::pair< iterator, bool > >::type try_emplace(K &&k, Args &&... args)
If a key equivalent to k already exists in the container, does nothing.
Definition: concurrent_skip_list_impl.hpp:1232
pmem::detail::concurrent_skip_list::get_allocator
const allocator_type & get_allocator() const
Returns a const reference to the allocator associated with the container.
Definition: concurrent_skip_list_impl.hpp:1826
pmem::detail::concurrent_skip_list::operator=
concurrent_skip_list & operator=(concurrent_skip_list &&other)
Move assignment operator.
Definition: concurrent_skip_list_impl.hpp:852
pmem::detail::allocator_move_assignment
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, std::true_type)
Move assignment implementation for allocator if propagate_on_container_move_assignment == true_type.
Definition: concurrent_skip_list_impl.hpp:108
pmem::obj::transaction::snapshot
static void snapshot(const T *addr, size_t num=1)
Takes a “snapshot” of given elements of type T number (1 by default), located at the given address pt...
Definition: transaction.hpp:484
pmem::detail::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(InputIt first, InputIt last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
Constructs the container with the contents of the range [first, last).
Definition: concurrent_skip_list_impl.hpp:600
pmem::detail::concurrent_skip_list::operator=
concurrent_skip_list & operator=(const concurrent_skip_list &other)
Copy assignment operator.
Definition: concurrent_skip_list_impl.hpp:810
pmem::obj::operator++
p< T > & operator++(p< T > &pp)
Prefix increment operator overload.
Definition: pext.hpp:48
pmem::detail::concurrent_skip_list::equal_range
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
Returns a range containing all elements with the given key in the container.
Definition: concurrent_skip_list_impl.hpp:1916
pmem::obj::operator==
bool operator==(standard_alloc_policy< T > const &, standard_alloc_policy< T2 > const &)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:406
pmem::detail::concurrent_skip_list::end
iterator end()
Returns an iterator to the element following the last element of the map.
Definition: concurrent_skip_list_impl.hpp:1751
pmem::detail::concurrent_skip_list::create_dummy_head
void create_dummy_head()
Creates dummy head.
Definition: concurrent_skip_list_impl.hpp:2737
pmem::detail::concurrent_skip_list::insert
std::pair< iterator, bool > insert(value_type &&value)
Inserts value using move semantic.
Definition: concurrent_skip_list_impl.hpp:969
pmem::obj::p< difference_type >
pmem::detail::concurrent_skip_list::lower_bound
const_iterator lower_bound(const key_type &key) const
Returns an iterator pointing to the first element that is not less than (i.e.
Definition: concurrent_skip_list_impl.hpp:1398
pmem::detail::concurrent_skip_list::find_insert_pos
void find_insert_pos(prev_array_type &prev_nodes, next_array_type &next_nodes, const K &key)
The method finds insert position for the given.
Definition: concurrent_skip_list_impl.hpp:2171
pmem::detail::concurrent_skip_list::contains
bool contains(const key_type &key) const
Checks if there is an element with key equivalent to key in the container.
Definition: concurrent_skip_list_impl.hpp:1638
pmem::detail::concurrent_skip_list
Persistent memory aware implementation of the concurrent skip list.
Definition: concurrent_skip_list_impl.hpp:491
pmem::detail::concurrent_skip_list::size
size_type size() const
Returns the number of elements in the container, i.e.
Definition: concurrent_skip_list_impl.hpp:1789
pool.hpp
C++ pmemobj pool.
pmem::detail::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
Constructs an empty container.
Definition: concurrent_skip_list_impl.hpp:567
pmem::detail::concurrent_skip_list::equal_range
std::pair< iterator, iterator > equal_range(const key_type &key)
Returns a range containing all elements with the given key in the container.
Definition: concurrent_skip_list_impl.hpp:1890
pmem::detail::concurrent_skip_list::find
const_iterator find(const key_type &key) const
Finds an element with key equivalent to key.
Definition: concurrent_skip_list_impl.hpp:1546
pmem::obj::transaction::run
static void run(pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:393
pmem::detail::concurrent_skip_list::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Inserts a new element into the container constructed in-place with the given args if there is no elem...
Definition: concurrent_skip_list_impl.hpp:1097
pmem::obj::swap
void swap(pmem::obj::array< T, N > &lhs, pmem::obj::array< T, N > &rhs)
Non-member swap function.
Definition: array.hpp:884
pmem::detail::allocator_copy_assignment
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, std::true_type)
Copy assignment implementation for allocator if propagate_on_container_copy_assignment == true_type.
Definition: concurrent_skip_list_impl.hpp:86
pmem::detail::concurrent_skip_list::free_data
void free_data()
Should be called before concurrent_skip_list destructor is called.
Definition: concurrent_skip_list_impl.hpp:764
pmem::detail::concurrent_skip_list::count
size_type count(const key_type &key) const
Returns the number of elements with key that compares equivalent to the specified argument.
Definition: concurrent_skip_list_impl.hpp:1603
pmem::obj::operator!=
bool operator!=(const allocator< T, P, Tr > &lhs, const OtherAllocator &rhs)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:522
pmem::detail::concurrent_skip_list::internal_get_bound
const_iterator internal_get_bound(const K &key, const comparator &cmp) const
Returns an iterator pointing to the first element from the list for which cmp(element,...
Definition: concurrent_skip_list_impl.hpp:2506
pmem::detail::concurrent_skip_list::upper_bound
iterator upper_bound(const key_type &key)
Returns an iterator pointing to the first element that is greater than key.
Definition: concurrent_skip_list_impl.hpp:1458
pmem::detail::concurrent_skip_list::try_insert_node
node_ptr try_insert_node(prev_array_type &prev_nodes, const next_array_type &next_nodes, size_type height, PrepareNode &&prepare_new_node)
Try to insert new node to the skip list.
Definition: concurrent_skip_list_impl.hpp:2388
pmem::detail::concurrent_skip_list::~concurrent_skip_list
~concurrent_skip_list()
Destructor.
Definition: concurrent_skip_list_impl.hpp:785
pmem::detail::concurrent_skip_list::try_emplace
std::pair< iterator, bool > try_emplace(key_type &&k, Args &&... args)
If a key equivalent to k already exists in the container, does nothing.
Definition: concurrent_skip_list_impl.hpp:1195
pmem::detail::concurrent_skip_list::operator=
concurrent_skip_list & operator=(std::initializer_list< value_type > il)
Replaces the contents with those identified by initializer list il.
Definition: concurrent_skip_list_impl.hpp:892
pmem::detail::concurrent_skip_list::key_comp
const key_compare & key_comp() const
Returns a const reference to the object that compares the keys.
Definition: concurrent_skip_list_impl.hpp:1992
pmem::detail::concurrent_skip_list::runtime_initialize
void runtime_initialize()
Intialize concurrent_skip_list after process restart.
Definition: concurrent_skip_list_impl.hpp:743
transaction.hpp
C++ pmemobj transactions.
pmem::detail::concurrent_skip_list::creates_dummy_node
persistent_node_ptr creates_dummy_node(size_type height, Args &&... args)
Creates new node, value_type should be constructed separately.
Definition: concurrent_skip_list_impl.hpp:2761
pmem::detail::concurrent_skip_list::upper_bound
const_iterator upper_bound(const K &x) const
Returns an iterator pointing to the first element that compares greater to the value x.
Definition: concurrent_skip_list_impl.hpp:1518
pmem::detail::concurrent_skip_list::insert
void insert(InputIterator first, InputIterator last)
Inserts elements from range [first, last).
Definition: concurrent_skip_list_impl.hpp:1043
pmem::detail::concurrent_skip_list::find
const_iterator find(const K &x) const
Finds an element with key that compares equivalent to the value x.
Definition: concurrent_skip_list_impl.hpp:1588
pmem::detail::concurrent_skip_list::internal_insert
std::pair< iterator, bool > internal_insert(const K &key, Args &&... args)
Construct and insert new node to the skip list in a thread-safe way.
Definition: concurrent_skip_list_impl.hpp:2315
pmem::detail::enumerable_thread_specific::local
reference local()
Returns data reference for the current thread.
Definition: enumerable_thread_specific.hpp:305
pmem::detail::concurrent_skip_list::upper_bound
const_iterator upper_bound(const key_type &key) const
Returns an iterator pointing to the first element that is greater than key.
Definition: concurrent_skip_list_impl.hpp:1474
pmem::detail::concurrent_skip_list::count
size_type count(const K &key) const
Returns the number of elements with key that compares equivalent to the specified argument.
Definition: concurrent_skip_list_impl.hpp:1624
pmem::detail::concurrent_skip_list::tls_restore
void tls_restore()
Process any information which was saved to tls and clears tls.
Definition: concurrent_skip_list_impl.hpp:2830
pmem::obj::persistent_ptr
Persistent pointer class.
Definition: persistent_ptr.hpp:183
pmem::detail::concurrent_skip_list::begin
iterator begin()
Returns an iterator to the first element of the container.
Definition: concurrent_skip_list_impl.hpp:1708
pmem::detail::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(concurrent_skip_list &&other)
Move constructor.
Definition: concurrent_skip_list_impl.hpp:690
pmem::detail::concurrent_skip_list::insert
std::pair< iterator, bool > insert(const value_type &value)
Inserts value in a thread-safe way.
Definition: concurrent_skip_list_impl.hpp:920
pmem::detail::concurrent_skip_list::lower_bound
iterator lower_bound(const key_type &key)
Returns an iterator pointing to the first element that is not less than (i.e.
Definition: concurrent_skip_list_impl.hpp:1382
pmem::obj::get
T & get(pmem::obj::array< T, N > &a)
Non-member get function.
Definition: array.hpp:894
pmem::detail::concurrent_skip_list::insert
void insert(std::initializer_list< value_type > ilist)
Inserts elements from initializer list ilist.
Definition: concurrent_skip_list_impl.hpp:1063
pmem::detail::concurrent_skip_list::check_prev_array
bool check_prev_array(const prev_array_type &prevs, size_type height)
Used only inside asserts.
Definition: concurrent_skip_list_impl.hpp:2456
pmem::detail::concurrent_skip_list::insert
iterator insert(const_iterator hint, P &&value)
Inserts value in the position as close as possible, just prior to hint.
Definition: concurrent_skip_list_impl.hpp:1022
pmem::detail::concurrent_skip_list::empty
bool empty() const
Checks if the container has no elements, i.e.
Definition: concurrent_skip_list_impl.hpp:1814
pmem::detail::concurrent_skip_list::lower_bound
const_iterator lower_bound(const K &x) const
Returns an iterator pointing to the first element that compares not less (i.e.
Definition: concurrent_skip_list_impl.hpp:1442
pmem::detail::concurrent_skip_list::internal_find_position
persistent_node_ptr internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
Finds position on the.
Definition: concurrent_skip_list_impl.hpp:2142
pmem::detail::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
Copy constructor.
Definition: concurrent_skip_list_impl.hpp:660
pmem::detail::enumerable_thread_specific::clear
void clear()
Removes all elements from the container.
Definition: enumerable_thread_specific.hpp:345
pmem::detail::concurrent_skip_list::internal_unsafe_emplace
std::pair< iterator, bool > internal_unsafe_emplace(Args &&... args)
Not thread-safe but can be called within a transaction.
Definition: concurrent_skip_list_impl.hpp:2278
life.hpp
Functions for destroying arrays.
pmem::detail::concurrent_skip_list::equal_range
std::pair< iterator, iterator > equal_range(const K &x)
Returns a range containing all elements with the given key in the container.
Definition: concurrent_skip_list_impl.hpp:1948
pmem::detail::concurrent_skip_list::max_size
size_type max_size() const
Returns the maximum number of elements the container is able to hold due to system or library impleme...
Definition: concurrent_skip_list_impl.hpp:1802
pmem::transaction_scope_error
Custom transaction error class.
Definition: pexceptions.hpp:158
pmem::detail::concurrent_skip_list::unsafe_erase
iterator unsafe_erase(const_iterator first, const_iterator last)
Removes the elements in the range [first; last), which must be a valid range in *this.
Definition: concurrent_skip_list_impl.hpp:1299
pmem::detail::concurrent_skip_list::end
const_iterator end() const
Returns an iterator to the element following the last element of the map.
Definition: concurrent_skip_list_impl.hpp:1764
pmem::detail::concurrent_skip_list::on_init_size
obj::p< size_type > on_init_size
This variable holds real size after the skip list is initialized.
Definition: concurrent_skip_list_impl.hpp:2943
pmem::detail::concurrent_skip_list::clear
void clear()
Erases all elements from the container transactionally.
Definition: concurrent_skip_list_impl.hpp:1673
pmem::detail::concurrent_skip_list::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Returns a range containing all elements with the given key in the container.
Definition: concurrent_skip_list_impl.hpp:1980
pmem::detail::concurrent_skip_list::unsafe_erase
size_type unsafe_erase(const K &key)
Removes the element (if one exists) with the key equivalent to key.
Definition: concurrent_skip_list_impl.hpp:1362
pmem::obj::pool_base
The non-template pool base class.
Definition: pool.hpp:46
pmem::detail::concurrent_skip_list::insert
iterator insert(const_iterator hint, const_reference value)
Inserts value in the position as close as possible, just prior to hint.
Definition: concurrent_skip_list_impl.hpp:992
pmem::detail::concurrent_skip_list::find
iterator find(const K &x)
Finds an element with key that compares equivalent to the value x.
Definition: concurrent_skip_list_impl.hpp:1567
pmem::detail::concurrent_skip_list::random_level
size_type random_level()
Generate random level.
Definition: concurrent_skip_list_impl.hpp:2676
pmem::detail::concurrent_skip_list::swap
void swap(concurrent_skip_list &other)
Exchanges the contents of the container with those of other transactionally.
Definition: concurrent_skip_list_impl.hpp:1850
persistent_ptr.hpp
Persistent smart pointer.
pmem::detail::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list()
Default constructor.
Definition: concurrent_skip_list_impl.hpp:545
pmem::detail::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
Move constructor.
Definition: concurrent_skip_list_impl.hpp:719
pmem::detail::concurrent_skip_list::begin
const_iterator begin() const
Returns an iterator to the first element of the container.
Definition: concurrent_skip_list_impl.hpp:1722
pmem::obj::transaction::manual
C++ manual scope transaction class.
Definition: transaction.hpp:71
enumerable_thread_specific.hpp
A persistent version of thread-local storage.
pmem::detail::concurrent_skip_list::unsafe_erase
iterator unsafe_erase(iterator pos)
Removes the element at pos from the container.
Definition: concurrent_skip_list_impl.hpp:1255
pmem::detail::concurrent_skip_list::create_node
persistent_node_ptr create_node(Args &&... args)
Creates new node.
Definition: concurrent_skip_list_impl.hpp:2691
pmem::detail::concurrent_skip_list::get_pool_base
obj::pool_base get_pool_base() const
Get the persistent memory pool where hashmap resides.
Definition: concurrent_skip_list_impl.hpp:2627
mutex.hpp
Pmem-resident mutex.
pmem::detail::concurrent_skip_list::check_tx_stage_work
void check_tx_stage_work() const
Private helper function.
Definition: concurrent_skip_list_impl.hpp:2035