PMDK C++ bindings  1.12-git53.g67ba2be4
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>
21 #include <libpmemobj++/mutex.hpp>
23 #include <libpmemobj++/pool.hpp>
25 
26 #include <libpmemobj++/experimental/atomic_self_relative_ptr.hpp>
28 
29 /* Windows has a max and a min macros which collides with min() and max()
30  * methods of default_random_generator */
31 #if defined(_WIN32)
32 #if defined(max)
33 #undef max
34 #endif
35 #if defined(min)
36 #undef min
37 #endif
38 #endif
39 
40 namespace pmem
41 {
42 namespace detail
43 {
44 
45 #ifndef NDEBUG
46 inline void
47 try_insert_node_finish_marker()
48 {
49 }
50 #endif
51 
56 template <typename MyAlloc, typename OtherAlloc>
57 inline void
58 allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator,
59  std::true_type)
60 {
61  my_allocator = other_allocator;
62 }
63 
68 template <typename MyAlloc, typename OtherAlloc>
69 inline void
70 allocator_copy_assignment(MyAlloc &, OtherAlloc &, std::false_type)
71 { /* NO COPY */
72 }
73 
78 template <typename MyAlloc, typename OtherAlloc>
79 inline void
80 allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator,
81  std::true_type)
82 {
83  my_allocator = std::move(other_allocator);
84 }
85 
90 template <typename MyAlloc, typename OtherAlloc>
91 inline void
92 allocator_move_assignment(MyAlloc &, OtherAlloc &, std::false_type)
93 { /* NO MOVE */
94 }
95 
100 template <typename MyAlloc, typename OtherAlloc>
101 inline void
102 allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator,
103  std::true_type)
104 {
105  std::swap(my_allocator, other_allocator);
106 }
107 
112 template <typename MyAlloc, typename OtherAlloc>
113 inline void
114 allocator_swap(MyAlloc &, OtherAlloc &, std::false_type)
115 { /* NO SWAP */
116 }
117 
118 template <typename Value, typename Mutex = pmem::obj::mutex,
119  typename LockType = std::unique_lock<Mutex>>
120 class skip_list_node {
121 public:
122  using value_type = Value;
123  using size_type = std::size_t;
124  using reference = value_type &;
125  using const_reference = const value_type &;
126  using pointer = value_type *;
127  using const_pointer = const value_type *;
128  using node_pointer =
130  using atomic_node_pointer = std::atomic<node_pointer>;
131  using mutex_type = Mutex;
132  using lock_type = LockType;
133 
134  skip_list_node(size_type levels) : height_(levels)
135  {
136  for (size_type lev = 0; lev < height_; ++lev)
137  detail::create<atomic_node_pointer>(&get_next(lev),
138  nullptr);
139 
140  assert(height() == levels);
141 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
142  /*
143  * Valgrind does not understand atomic semantic and reports
144  * false-postives in drd and helgrind tools.
145  */
146  for (size_type lev = 0; lev < height_; ++lev) {
147  VALGRIND_HG_DISABLE_CHECKING(&get_next(lev),
148  sizeof(get_next(lev)));
149  }
150 #endif
151  }
152 
153  skip_list_node(size_type levels, const node_pointer *new_nexts)
154  : height_(levels)
155  {
156  for (size_type lev = 0; lev < height_; ++lev)
157  detail::create<atomic_node_pointer>(&get_next(lev),
158  new_nexts[lev]);
159 
160  assert(height() == levels);
161 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
162  /*
163  * Valgrind does not understand atomic semantic and reports
164  * false-postives in drd and helgrind tools.
165  */
166  for (size_type lev = 0; lev < height_; ++lev) {
167  VALGRIND_HG_DISABLE_CHECKING(&get_next(lev),
168  sizeof(get_next(lev)));
169  }
170 #endif
171  }
172 
173  ~skip_list_node()
174  {
175  for (size_type lev = 0; lev < height_; ++lev)
176  detail::destroy<atomic_node_pointer>(get_next(lev));
177  }
178 
179  skip_list_node(const skip_list_node &) = delete;
180 
181  skip_list_node &operator=(const skip_list_node &) = delete;
182 
183  pointer
184  get() noexcept
185  {
186  return &val;
187  }
188 
189  const_pointer
190  get() const noexcept
191  {
192  return &val;
193  }
194 
195  reference
196  value()
197  {
198  return *get();
199  }
200 
201  node_pointer
202  next(size_type level) const
203  {
204  assert(level < height());
205  return get_next(level).load(std::memory_order_acquire);
206  }
207 
212  void
213  set_next_tx(size_type level, node_pointer next)
214  {
215  assert(level < height());
216  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
217  auto &node = get_next(level);
218  obj::flat_transaction::snapshot<atomic_node_pointer>(&node);
219  node.store(next, std::memory_order_release);
220  }
221 
222  void
223  set_next(obj::pool_base pop, size_type level, node_pointer next)
224  {
225  assert(level < height());
226  auto &node = get_next(level);
227  node.store(next, std::memory_order_release);
228  pop.persist(&node, sizeof(node));
229  }
230 
231  void
232  set_nexts(const node_pointer *new_nexts, size_type h)
233  {
234  assert(h == height());
235  auto *nexts = get_nexts();
236 
237  for (size_type i = 0; i < h; i++) {
238  nexts[i].store(new_nexts[i], std::memory_order_relaxed);
239  }
240  }
241 
242  void
243  set_nexts(obj::pool_base pop, const node_pointer *new_nexts,
244  size_type h)
245  {
246  set_nexts(new_nexts, h);
247 
248  auto *nexts = get_nexts();
249  pop.persist(nexts, sizeof(nexts[0]) * h);
250  }
251 
253  size_type
254  height() const
255  {
256  return height_;
257  }
258 
259  lock_type
260  acquire()
261  {
262  return lock_type(mutex);
263  }
264 
265 private:
266  atomic_node_pointer *
267  get_nexts()
268  {
269  return reinterpret_cast<atomic_node_pointer *>(this + 1);
270  }
271 
272  atomic_node_pointer &
273  get_next(size_type level)
274  {
275  auto *arr = get_nexts();
276  return arr[level];
277  }
278 
279  const atomic_node_pointer &
280  get_next(size_type level) const
281  {
282  auto *arr =
283  reinterpret_cast<const atomic_node_pointer *>(this + 1);
284  return arr[level];
285  }
286 
287  mutex_type mutex;
288  union {
289  value_type val;
290  };
291  size_type height_;
292 };
293 
294 template <typename NodeType, bool is_const>
295 class skip_list_iterator {
296  using node_type = NodeType;
297  using node_ptr = typename std::conditional<is_const, const node_type *,
298  node_type *>::type;
299  friend class skip_list_iterator<node_type, true>;
300 
301 public:
302  using value_type = typename node_type::value_type;
303  using iterator_category = std::forward_iterator_tag;
304  using difference_type = std::ptrdiff_t;
305  using reference =
306  typename std::conditional<is_const,
307  typename node_type::const_reference,
308  typename node_type::reference>::type;
309  using pointer = typename std::conditional<is_const, const value_type *,
310  value_type *>::type;
311 
312  skip_list_iterator() : node(nullptr)
313  {
314  }
315 
317  skip_list_iterator(const skip_list_iterator &other) : node(other.node)
318  {
319  }
320 
322  template <typename U = void,
323  typename = typename std::enable_if<is_const, U>::type>
324  skip_list_iterator(const skip_list_iterator<node_type, false> &other)
325  : node(other.node)
326  {
327  }
328 
329  reference operator*() const
330  {
331  return *(node->get());
332  }
333 
334  pointer operator->() const
335  {
336  return node->get();
337  }
338 
339  skip_list_iterator &
340  operator++()
341  {
342  assert(node != nullptr);
343  node = node->next(0).get();
344  return *this;
345  }
346 
347  skip_list_iterator
348  operator++(int)
349  {
350  skip_list_iterator tmp = *this;
351  ++*this;
352  return tmp;
353  }
354 
355  skip_list_iterator &
356  operator=(const skip_list_iterator &other)
357  {
358  node = other.node;
359  return *this;
360  }
361 
362 private:
363  explicit skip_list_iterator(node_type *n) : node(n)
364  {
365  }
366 
367  template <typename T = void,
368  typename = typename std::enable_if<is_const, T>::type>
369  explicit skip_list_iterator(const node_type *n) : node(n)
370  {
371  }
372 
373  node_ptr node;
374 
375  template <typename Traits>
376  friend class concurrent_skip_list;
377 
378  template <typename T, bool M, bool U>
379  friend bool operator==(const skip_list_iterator<T, M> &lhs,
380  const skip_list_iterator<T, U> &rhs);
381 
382  template <typename T, bool M, bool U>
383  friend bool operator!=(const skip_list_iterator<T, M> &lhs,
384  const skip_list_iterator<T, U> &rhs);
385 };
386 
387 template <typename T, bool M, bool U>
388 bool
389 operator==(const skip_list_iterator<T, M> &lhs,
390  const skip_list_iterator<T, U> &rhs)
391 {
392  return lhs.node == rhs.node;
393 }
394 
395 template <typename T, bool M, bool U>
396 bool
397 operator!=(const skip_list_iterator<T, M> &lhs,
398  const skip_list_iterator<T, U> &rhs)
399 {
400  return lhs.node != rhs.node;
401 }
402 
403 struct default_random_generator {
404  using gen_type = std::mt19937_64;
405  using result_type = typename gen_type::result_type;
406 
407  size_t
408  operator()()
409  {
410  static thread_local gen_type engine(
411  static_cast<size_t>(time(0)));
412 
413  return engine();
414  }
415 
416  static constexpr result_type
417  min()
418  {
419  return gen_type::min();
420  }
421 
422  static constexpr result_type
423  max()
424  {
425  return gen_type::max();
426  }
427 };
428 
429 template <typename RndGenerator, size_t MAX_LEVEL>
430 class geometric_level_generator {
431 public:
432  using rnd_generator_type = RndGenerator;
433 
434  static constexpr size_t max_level = MAX_LEVEL;
435 
436  size_t
437  operator()()
438  {
439  /* rnd_generator_type should be thread-safe random number
440  * generator. */
441  static rnd_generator_type gen;
442  /* std::geometric_distribution is not thread-safe. We mark it as
443  * a thread_local to avoid data races. */
444  static thread_local std::geometric_distribution<size_t> d;
445 
446  return (d(gen) % MAX_LEVEL) + 1;
447  }
448 };
449 
478 template <typename Traits>
480 protected:
481  using traits_type = Traits;
482  using key_type = typename traits_type::key_type;
483  using mapped_type = typename traits_type::mapped_type;
484  using value_type = typename traits_type::value_type;
485  using size_type = std::size_t;
486  using difference_type = std::ptrdiff_t;
487  using key_compare = typename traits_type::compare_type;
488  using allocator_type = typename traits_type::allocator_type;
489  using allocator_traits_type = std::allocator_traits<allocator_type>;
490 
491  using reference = value_type &;
492  using const_reference = const value_type &;
493  using pointer = typename allocator_traits_type::pointer;
494  using const_pointer = typename allocator_traits_type::const_pointer;
495 
496  using list_node_type = skip_list_node<value_type>;
497 
498  using iterator = skip_list_iterator<list_node_type, false>;
499  using const_iterator = skip_list_iterator<list_node_type, true>;
500 
501  static constexpr size_type MAX_LEVEL = traits_type::max_level;
502 
503  using random_level_generator_type = geometric_level_generator<
504  typename traits_type::random_generator_type, MAX_LEVEL>;
505  using node_allocator_type = typename std::allocator_traits<
506  allocator_type>::template rebind_alloc<uint8_t>;
507  using node_allocator_traits = typename std::allocator_traits<
508  allocator_type>::template rebind_traits<uint8_t>;
509  using node_ptr = list_node_type *;
510  using const_node_ptr = const list_node_type *;
511  using persistent_node_ptr =
513 
514  using prev_array_type = std::array<node_ptr, MAX_LEVEL>;
515  using next_array_type = std::array<persistent_node_ptr, MAX_LEVEL>;
516  using node_lock_type = typename list_node_type::lock_type;
517  using lock_array = std::array<node_lock_type, MAX_LEVEL>;
518 
519 public:
520  static constexpr bool allow_multimapping =
521  traits_type::allow_multimapping;
522 
532  {
534  init();
535  }
536 
554  const key_compare &comp,
555  const allocator_type &alloc = allocator_type())
556  : _node_allocator(alloc), _compare(comp)
557  {
559  init();
560  }
561 
585  template <class InputIt>
586  concurrent_skip_list(InputIt first, InputIt last,
587  const key_compare &comp = key_compare(),
588  const allocator_type &alloc = allocator_type())
589  : _node_allocator(alloc), _compare(comp)
590  {
592  init();
593  while (first != last)
594  internal_unsafe_emplace(*first++);
595  }
596 
615  : _node_allocator(node_allocator_traits::
616  select_on_container_copy_construction(
617  other._node_allocator)),
618  _compare(other._compare),
619  _rnd_generator(other._rnd_generator)
620  {
622  init();
623  internal_copy(other);
624  assert(_size == other._size);
625  }
626 
647  const allocator_type &alloc)
648  : _node_allocator(alloc),
649  _compare(other._compare),
650  _rnd_generator(other._rnd_generator)
651  {
653  init();
654  internal_copy(other);
655  assert(_size == other._size);
656  }
657 
677  : _node_allocator(std::move(other._node_allocator)),
678  _compare(other._compare),
679  _rnd_generator(other._rnd_generator)
680  {
682  init();
683  internal_move(std::move(other));
684  }
685 
706  const allocator_type &alloc)
707  : _node_allocator(alloc),
708  _compare(other._compare),
709  _rnd_generator(other._rnd_generator)
710  {
712  init();
713  if (alloc == other.get_allocator()) {
714  internal_move(std::move(other));
715  } else {
716  init();
717  internal_copy(std::make_move_iterator(other.begin()),
718  std::make_move_iterator(other.end()));
719  }
720  }
721 
728  void
730  {
731  tls_restore();
732 
733  assert(this->size() ==
734  size_type(std::distance(this->begin(), this->end())));
735  }
736 
749  void
751  {
752  if (dummy_head == nullptr)
753  return;
754 
755  auto pop = get_pool_base();
756  obj::flat_transaction::run(pop, [&] {
757  clear();
758  delete_dummy_head();
759  });
760  }
761 
772  {
773  try {
774  free_data();
775  } catch (...) {
776  std::terminate();
777  }
778  }
779 
797  {
798  if (this == &other)
799  return *this;
800 
802  obj::flat_transaction::run(pop, [&] {
803  using pocca_t = typename node_allocator_traits::
804  propagate_on_container_copy_assignment;
805  clear();
806  allocator_copy_assignment(_node_allocator,
807  other._node_allocator,
808  pocca_t());
809  _compare = other._compare;
810  _rnd_generator = other._rnd_generator;
811 
812  internal_copy(other);
813  });
814  return *this;
815  }
816 
839  {
840  if (this == &other)
841  return *this;
842 
844  obj::flat_transaction::run(pop, [&] {
845  using pocma_t = typename node_allocator_traits::
846  propagate_on_container_move_assignment;
847  clear();
848  if (pocma_t::value ||
849  _node_allocator == other._node_allocator) {
850  delete_dummy_head();
851  allocator_move_assignment(_node_allocator,
852  other._node_allocator,
853  pocma_t());
854  _compare = other._compare;
855  _rnd_generator = other._rnd_generator;
856  internal_move(std::move(other));
857  } else {
858  internal_copy(
859  std::make_move_iterator(other.begin()),
860  std::make_move_iterator(other.end()));
861  }
862  });
863  return *this;
864  }
865 
878  operator=(std::initializer_list<value_type> il)
879  {
881  obj::flat_transaction::run(pop, [&] {
882  clear();
883  for (auto it = il.begin(); it != il.end(); ++it)
885  });
886  return *this;
887  }
888 
905  std::pair<iterator, bool>
906  insert(const value_type &value)
907  {
908  return internal_insert(value.first, value);
909  }
910 
929  template <typename P,
930  typename std::enable_if<
931  std::is_constructible<value_type, P &&>::value>::type>
932  std::pair<iterator, bool>
933  insert(P &&value)
934  {
935  return emplace(std::forward<P>(value));
936  }
937 
954  std::pair<iterator, bool>
955  insert(value_type &&value)
956  {
957  return internal_insert(value.first, std::move(value));
958  }
959 
977  iterator
978  insert(const_iterator hint, const_reference value)
979  {
980  /* Ignore hint */
981  return insert(value).first;
982  }
983 
1004  template <typename P,
1005  typename std::enable_if<
1006  std::is_constructible<value_type, P &&>::value>::type>
1007  iterator
1008  insert(const_iterator hint, P &&value)
1009  {
1010  return emplace_hint(hint, std::forward<P>(value));
1011  }
1012 
1027  template <typename InputIterator>
1028  void
1029  insert(InputIterator first, InputIterator last)
1030  {
1031  for (InputIterator it = first; it != last; ++it)
1032  insert(*it);
1033  }
1034 
1048  void
1049  insert(std::initializer_list<value_type> ilist)
1050  {
1051  insert(ilist.begin(), ilist.end());
1052  }
1053 
1081  template <typename... Args>
1082  std::pair<iterator, bool>
1083  emplace(Args &&... args)
1084  {
1085  return internal_emplace(std::forward<Args>(args)...);
1086  }
1087 
1118  template <typename... Args>
1119  iterator
1120  emplace_hint(const_iterator hint, Args &&... args)
1121  {
1122  /* Ignore hint */
1123  return emplace(std::forward<Args>(args)...).first;
1124  }
1125 
1149  template <typename... Args>
1150  std::pair<iterator, bool>
1151  try_emplace(const key_type &k, Args &&... args)
1152  {
1153  return internal_try_emplace(k, std::forward<Args>(args)...);
1154  }
1155 
1179  template <typename... Args>
1180  std::pair<iterator, bool>
1181  try_emplace(key_type &&k, Args &&... args)
1182  {
1183  return internal_try_emplace(std::move(k),
1184  std::forward<Args>(args)...);
1185  }
1186 
1213  template <typename K, typename... Args>
1214  typename std::enable_if<
1215  has_is_transparent<key_compare>::value &&
1216  std::is_constructible<key_type, K &&>::value,
1217  std::pair<iterator, bool>>::type
1218  try_emplace(K &&k, Args &&... args)
1219  {
1220  return internal_try_emplace(std::forward<K>(k),
1221  std::forward<Args>(args)...);
1222  }
1223 
1240  iterator
1241  unsafe_erase(iterator pos)
1242  {
1243  check_outside_tx();
1244  auto &size_diff = tls_data.local().size_diff;
1245  return internal_erase(pos, size_diff);
1246  }
1247 
1264  iterator
1265  unsafe_erase(const_iterator pos)
1266  {
1267  return unsafe_erase(get_iterator(pos));
1268  }
1269 
1284  iterator
1285  unsafe_erase(const_iterator first, const_iterator last)
1286  {
1287  check_outside_tx();
1288  obj::pool_base pop = get_pool_base();
1289  auto &size_diff = tls_data.local().size_diff;
1290 
1291  obj::flat_transaction::run(pop, [&] {
1292  while (first != last) {
1293  first = internal_erase(first, size_diff);
1294  }
1295  });
1296 
1297  return get_iterator(first);
1298  }
1299 
1312  size_type
1313  unsafe_erase(const key_type &key)
1314  {
1315  std::pair<iterator, iterator> range = equal_range(key);
1316  size_type sz = static_cast<size_type>(
1317  std::distance(range.first, range.second));
1318  unsafe_erase(range.first, range.second);
1319  return sz;
1320  }
1321 
1340  template <
1341  typename K,
1342  typename = typename std::enable_if<
1343  has_is_transparent<key_compare>::value &&
1344  !std::is_convertible<K, iterator>::value &&
1345  !std::is_convertible<K, const_iterator>::value,
1346  K>::type>
1347  size_type
1348  unsafe_erase(const K &key)
1349  {
1350  std::pair<iterator, iterator> range = equal_range(key);
1351  size_type sz = static_cast<size_type>(
1352  std::distance(range.first, range.second));
1353  unsafe_erase(range.first, range.second);
1354  return sz;
1355  }
1356 
1367  iterator
1368  lower_bound(const key_type &key)
1369  {
1370  return internal_get_bound(key, _compare);
1371  }
1372 
1383  const_iterator
1384  lower_bound(const key_type &key) const
1385  {
1386  return internal_get_bound(key, _compare);
1387  }
1388 
1402  template <typename K,
1403  typename = typename std::enable_if<
1404  has_is_transparent<key_compare>::value, K>::type>
1405  iterator
1406  lower_bound(const K &x)
1407  {
1408  return internal_get_bound(x, _compare);
1409  }
1410 
1424  template <typename K,
1425  typename = typename std::enable_if<
1426  has_is_transparent<key_compare>::value, K>::type>
1427  const_iterator
1428  lower_bound(const K &x) const
1429  {
1430  return internal_get_bound(x, _compare);
1431  }
1432 
1443  iterator
1444  find_higher_eq(const key_type &key)
1445  {
1446  return internal_get_bound(key, _compare);
1447  }
1448 
1459  const_iterator
1460  find_higher_eq(const key_type &key) const
1461  {
1462  return internal_get_bound(key, _compare);
1463  }
1464 
1479  template <typename K,
1480  typename = typename std::enable_if<
1481  has_is_transparent<key_compare>::value, K>::type>
1482  iterator
1483  find_higher_eq(const K &x)
1484  {
1485  return internal_get_bound(x, _compare);
1486  }
1487 
1502  template <typename K,
1503  typename = typename std::enable_if<
1504  has_is_transparent<key_compare>::value, K>::type>
1505  const_iterator
1506  find_higher_eq(const K &x) const
1507  {
1508  return internal_get_bound(x, _compare);
1509  }
1510 
1521  iterator
1522  upper_bound(const key_type &key)
1523  {
1524  return internal_get_bound(key, not_greater_compare(_compare));
1525  }
1526 
1537  const_iterator
1538  upper_bound(const key_type &key) const
1539  {
1540  return internal_get_bound(key, not_greater_compare(_compare));
1541  }
1542 
1556  template <typename K,
1557  typename = typename std::enable_if<
1558  has_is_transparent<key_compare>::value, K>::type>
1559  iterator
1560  upper_bound(const K &x)
1561  {
1562  return internal_get_bound(x, not_greater_compare(_compare));
1563  }
1564 
1578  template <typename K,
1579  typename = typename std::enable_if<
1580  has_is_transparent<key_compare>::value, K>::type>
1581  const_iterator
1582  upper_bound(const K &x) const
1583  {
1584  return internal_get_bound(x, not_greater_compare(_compare));
1585  }
1586 
1597  iterator
1598  find_higher(const key_type &key)
1599  {
1600  return internal_get_bound(key, not_greater_compare(_compare));
1601  }
1602 
1613  const_iterator
1614  find_higher(const key_type &key) const
1615  {
1616  return internal_get_bound(key, not_greater_compare(_compare));
1617  }
1618 
1632  template <typename K,
1633  typename = typename std::enable_if<
1634  has_is_transparent<key_compare>::value, K>::type>
1635  iterator
1636  find_higher(const K &x)
1637  {
1638  return internal_get_bound(x, not_greater_compare(_compare));
1639  }
1640 
1654  template <typename K,
1655  typename = typename std::enable_if<
1656  has_is_transparent<key_compare>::value, K>::type>
1657  const_iterator
1658  find_higher(const K &x) const
1659  {
1660  return internal_get_bound(x, not_greater_compare(_compare));
1661  }
1662 
1673  iterator
1674  find_lower(const key_type &key)
1675  {
1676  auto it = internal_get_biggest_less_than(key, _compare);
1677  return iterator(
1678  const_cast<typename iterator::node_ptr>(it.node));
1679  }
1680 
1691  const_iterator
1692  find_lower(const key_type &key) const
1693  {
1694  return internal_get_biggest_less_than(key, _compare);
1695  }
1696 
1710  template <typename K,
1711  typename = typename std::enable_if<
1712  has_is_transparent<key_compare>::value, K>::type>
1713  iterator
1714  find_lower(const K &key)
1715  {
1716  auto it = internal_get_biggest_less_than(key, _compare);
1717  return iterator(
1718  const_cast<typename iterator::node_ptr>(it.node));
1719  }
1720 
1734  template <typename K,
1735  typename = typename std::enable_if<
1736  has_is_transparent<key_compare>::value, K>::type>
1737  const_iterator
1738  find_lower(const K &key) const
1739  {
1740  return internal_get_biggest_less_than(key, _compare);
1741  }
1742 
1753  iterator
1754  find_lower_eq(const key_type &key)
1755  {
1757  key, not_greater_compare(_compare));
1758  return iterator(
1759  const_cast<typename iterator::node_ptr>(it.node));
1760  }
1761 
1772  const_iterator
1773  find_lower_eq(const key_type &key) const
1774  {
1776  key, not_greater_compare(_compare));
1777  }
1778 
1792  template <typename K,
1793  typename = typename std::enable_if<
1794  has_is_transparent<key_compare>::value, K>::type>
1795  iterator
1796  find_lower_eq(const K &key)
1797  {
1799  key, not_greater_compare(_compare));
1800  return iterator(
1801  const_cast<typename iterator::node_ptr>(it.node));
1802  }
1803 
1817  template <typename K,
1818  typename = typename std::enable_if<
1819  has_is_transparent<key_compare>::value, K>::type>
1820  const_iterator
1821  find_lower_eq(const K &key) const
1822  {
1824  key, not_greater_compare(_compare));
1825  }
1826 
1835  iterator
1836  find(const key_type &key)
1837  {
1838  return internal_find(key);
1839  }
1840 
1849  const_iterator
1850  find(const key_type &key) const
1851  {
1852  return internal_find(key);
1853  }
1854 
1867  template <typename K,
1868  typename = typename std::enable_if<
1869  has_is_transparent<key_compare>::value, K>::type>
1870  iterator
1871  find(const K &x)
1872  {
1873  return internal_find(x);
1874  }
1875 
1888  template <typename K,
1889  typename = typename std::enable_if<
1890  has_is_transparent<key_compare>::value, K>::type>
1891  const_iterator
1892  find(const K &x) const
1893  {
1894  return internal_find(x);
1895  }
1896 
1906  size_type
1907  count(const key_type &key) const
1908  {
1909  return internal_count(key);
1910  }
1911 
1924  template <typename K,
1925  typename = typename std::enable_if<
1926  has_is_transparent<key_compare>::value, K>::type>
1927  size_type
1928  count(const K &key) const
1929  {
1930  return internal_count(key);
1931  }
1932 
1941  bool
1942  contains(const key_type &key) const
1943  {
1944  return find(key) != end();
1945  }
1946 
1959  template <typename K,
1960  typename = typename std::enable_if<
1961  has_is_transparent<key_compare>::value, K>::type>
1962  bool
1963  contains(const K &x) const
1964  {
1965  return find(x) != end();
1966  }
1967 
1976  void
1978  {
1979  assert(dummy_head->height() > 0);
1980  obj::pool_base pop = get_pool_base();
1981 
1982  persistent_node_ptr current = dummy_head->next(0);
1983 
1984  obj::flat_transaction::run(pop, [&] {
1985  while (current) {
1986  assert(current->height() > 0);
1987  persistent_node_ptr next = current->next(0);
1988  delete_node(current);
1989  current = next;
1990  }
1991 
1992  node_ptr head = dummy_head.get();
1993  for (size_type i = 0; i < head->height(); ++i) {
1994  head->set_next_tx(i, nullptr);
1995  }
1996 
1997  on_init_size = 0;
1998  tls_data.clear();
1999  obj::flat_transaction::snapshot((size_t *)&_size);
2000  _size = 0;
2001  });
2002  }
2003 
2010  iterator
2012  {
2013  return iterator(dummy_head.get()->next(0).get());
2014  }
2015 
2022  const_iterator
2023  begin() const
2024  {
2025  return const_iterator(dummy_head.get()->next(0).get());
2026  }
2027 
2034  const_iterator
2035  cbegin() const
2036  {
2037  return const_iterator(dummy_head.get()->next(0).get());
2038  }
2039 
2047  iterator
2049  {
2050  return iterator(nullptr);
2051  }
2052 
2060  const_iterator
2061  end() const
2062  {
2063  return const_iterator(nullptr);
2064  }
2065 
2073  const_iterator
2074  cend() const
2075  {
2076  return const_iterator(nullptr);
2077  }
2078 
2085  size_type
2086  size() const
2087  {
2088  return _size.load(std::memory_order_relaxed);
2089  }
2090 
2098  size_type
2099  max_size() const
2100  {
2101  return std::numeric_limits<difference_type>::max();
2102  }
2103 
2110  bool
2111  empty() const
2112  {
2113  return 0 == size();
2114  }
2115 
2128  void
2130  {
2131  obj::pool_base pop = get_pool_base();
2132  obj::flat_transaction::run(pop, [&] {
2133  using pocs_t = typename node_allocator_traits::
2134  propagate_on_container_swap;
2135  allocator_swap(_node_allocator, other._node_allocator,
2136  pocs_t());
2137  std::swap(_compare, other._compare);
2138  std::swap(_rnd_generator, other._rnd_generator);
2139  std::swap(dummy_head, other.dummy_head);
2141 
2142  obj::flat_transaction::snapshot((size_t *)&_size);
2144  (size_t *)&(other._size));
2145  _size = other._size.exchange(_size,
2146  std::memory_order_relaxed);
2147  });
2148  }
2149 
2169  std::pair<iterator, iterator>
2170  equal_range(const key_type &key)
2171  {
2172  return std::pair<iterator, iterator>(lower_bound(key),
2173  upper_bound(key));
2174  }
2175 
2195  std::pair<const_iterator, const_iterator>
2196  equal_range(const key_type &key) const
2197  {
2198  return std::pair<const_iterator, const_iterator>(
2199  lower_bound(key), upper_bound(key));
2200  }
2201 
2224  template <typename K,
2225  typename = typename std::enable_if<
2226  has_is_transparent<key_compare>::value, K>::type>
2227  std::pair<iterator, iterator>
2228  equal_range(const K &x)
2229  {
2230  return std::pair<iterator, iterator>(lower_bound(x),
2231  upper_bound(x));
2232  }
2233 
2256  template <typename K,
2257  typename = typename std::enable_if<
2258  has_is_transparent<key_compare>::value, K>::type>
2259  std::pair<const_iterator, const_iterator>
2260  equal_range(const K &key) const
2261  {
2262  return std::pair<const_iterator, const_iterator>(
2263  lower_bound(key), upper_bound(key));
2264  }
2265 
2271  const key_compare &
2272  key_comp() const
2273  {
2274  return _compare;
2275  }
2276 
2282  key_compare &
2284  {
2285  return _compare;
2286  }
2287 
2288 private:
2289  /* Status flags stored in insert_stage field */
2290  enum insert_stage_type : uint8_t { not_started = 0, in_progress = 1 };
2291  /*
2292  * Structure of thread local data.
2293  * Size should be 64 bytes.
2294  */
2295  struct tls_entry_type {
2296  persistent_node_ptr ptr;
2297  obj::p<difference_type> size_diff;
2298  obj::p<insert_stage_type> insert_stage;
2299 
2300  char reserved[64 - sizeof(decltype(ptr)) -
2301  sizeof(decltype(size_diff)) -
2302  sizeof(decltype(insert_stage))];
2303  };
2304  static_assert(sizeof(tls_entry_type) == 64,
2305  "The size of tls_entry_type should be 64 bytes.");
2306 
2314  void
2316  {
2317  if (pmemobj_tx_stage() != TX_STAGE_WORK)
2319  "Function called out of transaction scope.");
2320  }
2321 
2322  /* Helper method which throws an exception when called in a tx */
2323  static inline void
2324  check_outside_tx()
2325  {
2326  if (pmemobj_tx_stage() != TX_STAGE_NONE)
2328  "Function called inside transaction scope.");
2329  }
2330 
2331  void
2332  init()
2333  {
2334  if (pool_uuid == 0)
2335  throw pmem::pool_error("Invalid pool handle.");
2336 
2337  _size = 0;
2338  on_init_size = 0;
2340  }
2341 
2342  void
2343  internal_move(concurrent_skip_list &&other)
2344  {
2345  assert(this->empty());
2346  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2347  dummy_head = other.dummy_head;
2348  other.dummy_head = nullptr;
2349  other.create_dummy_head();
2350 
2351  _size.store(other._size.load(std::memory_order_relaxed),
2352  std::memory_order_relaxed);
2353  on_init_size = other.on_init_size;
2354  }
2355 
2356  static const_reference
2357  get_val(const_node_ptr n)
2358  {
2359  assert(n);
2360  return *(n->get());
2361  }
2362 
2363  static reference
2364  get_val(node_ptr n)
2365  {
2366  assert(n);
2367  return *(n->get());
2368  }
2369 
2370  static const key_type &
2371  get_key(const_node_ptr n)
2372  {
2373  assert(n);
2374  return traits_type::get_key(get_val(n));
2375  }
2376 
2377  template <typename K>
2378  iterator
2379  internal_find(const K &key)
2380  {
2381  iterator it = lower_bound(key);
2382  return (it == end() || _compare(key, traits_type::get_key(*it)))
2383  ? end()
2384  : it;
2385  }
2386 
2387  template <typename K>
2388  const_iterator
2389  internal_find(const K &key) const
2390  {
2391  const_iterator it = lower_bound(key);
2392  return (it == end() || _compare(key, traits_type::get_key(*it)))
2393  ? end()
2394  : it;
2395  }
2396 
2397  template <typename K>
2398  size_type
2399  internal_count(const K &key) const
2400  {
2401  if (allow_multimapping) {
2402  std::pair<const_iterator, const_iterator> range =
2403  equal_range(key);
2404  return static_cast<size_type>(
2405  std::distance(range.first, range.second));
2406  }
2407  return (find(key) == end()) ? size_type(0) : size_type(1);
2408  }
2409 
2420  template <typename K, typename pointer_type, typename comparator>
2421  persistent_node_ptr
2422  internal_find_position(size_type level, pointer_type &prev,
2423  const K &key, const comparator &cmp) const
2424  {
2425  assert(level < prev->height());
2426  persistent_node_ptr next = prev->next(level);
2427  pointer_type curr = next.get();
2428 
2429  while (curr && cmp(get_key(curr), key)) {
2430  prev = curr;
2431  assert(level < prev->height());
2432  next = prev->next(level);
2433  curr = next.get();
2434  }
2435 
2436  return next;
2437  }
2438 
2449  template <typename K>
2450  void
2451  find_insert_pos(prev_array_type &prev_nodes,
2452  next_array_type &next_nodes, const K &key)
2453  {
2454  if (allow_multimapping) {
2455  fill_prev_next_arrays(prev_nodes, next_nodes, key,
2456  not_greater_compare(_compare));
2457  } else {
2458  fill_prev_next_arrays(prev_nodes, next_nodes, key,
2459  _compare);
2460  }
2461  }
2462 
2474  template <typename K, typename comparator>
2475  void
2476  fill_prev_next_arrays(prev_array_type &prev_nodes,
2477  next_array_type &next_nodes, const K &key,
2478  const comparator &cmp)
2479  {
2480  node_ptr prev = dummy_head.get();
2481  prev_nodes.fill(prev);
2482  next_nodes.fill(nullptr);
2483 
2484  for (size_type h = prev->height(); h > 0; --h) {
2485  persistent_node_ptr next =
2486  internal_find_position(h - 1, prev, key, cmp);
2487  prev_nodes[h - 1] = prev;
2488  next_nodes[h - 1] = next;
2489  }
2490  }
2491 
2492  template <typename K, typename... Args>
2493  std::pair<iterator, bool>
2494  internal_try_emplace(K &&key, Args &&... args)
2495  {
2496  return internal_insert(
2497  key, std::piecewise_construct,
2498  std::forward_as_tuple(std::forward<K>(key)),
2499  std::forward_as_tuple(std::forward<Args>(args)...));
2500  }
2501 
2502  template <typename... Args>
2503  std::pair<iterator, bool>
2504  internal_emplace(Args &&... args)
2505  {
2506  check_outside_tx();
2507  tls_entry_type &tls_entry = tls_data.local();
2508  obj::pool_base pop = get_pool_base();
2509 
2510  obj::flat_transaction::run(pop, [&] {
2511  assert(tls_entry.ptr == nullptr);
2512  tls_entry.ptr =
2513  create_node(std::forward<Args>(args)...);
2514  ++tls_entry.size_diff;
2515  tls_entry.insert_stage = not_started;
2516  });
2517 
2518  node_ptr n = tls_entry.ptr.get();
2519  size_type height = n->height();
2520 
2521  std::pair<iterator, bool> insert_result = internal_insert_node(
2522  get_key(n), height,
2523  [&](const next_array_type &next_nodes)
2524  -> persistent_node_ptr & {
2525  assert(tls_entry.insert_stage == not_started);
2526  assert(tls_entry.ptr != nullptr);
2527 
2528  n->set_nexts(pop, next_nodes.data(), height);
2529 
2530  tls_entry.insert_stage = in_progress;
2531  pop.persist(&(tls_entry.insert_stage),
2532  sizeof(tls_entry.insert_stage));
2533 
2534  return tls_entry.ptr;
2535  });
2536 
2537  if (!insert_result.second) {
2538  assert(tls_entry.ptr != nullptr);
2539  assert(tls_entry.insert_stage == not_started);
2540 
2541  obj::flat_transaction::run(pop, [&] {
2542  --tls_entry.size_diff;
2543  delete_node(tls_entry.ptr);
2544  tls_entry.ptr = nullptr;
2545  });
2546  }
2547 
2548  assert(tls_entry.ptr == nullptr);
2549  return insert_result;
2550  }
2551 
2556  template <typename... Args>
2557  std::pair<iterator, bool>
2558  internal_unsafe_emplace(Args &&... args)
2559  {
2561 
2562  persistent_node_ptr new_node =
2563  create_node(std::forward<Args>(args)...);
2564 
2565  node_ptr n = new_node.get();
2566  size_type height = n->height();
2567 
2568  std::pair<iterator, bool> insert_result = internal_insert_node(
2569  get_key(n), height,
2570  [&](const next_array_type &next_nodes)
2571  -> persistent_node_ptr & {
2572  assert(new_node != nullptr);
2573 
2574  n->set_nexts(next_nodes.data(), height);
2575 
2576  return new_node;
2577  });
2578 
2579  if (insert_result.second) {
2580  ++on_init_size;
2581  } else {
2582  assert(new_node != nullptr);
2583 
2584  delete_node(new_node);
2585  }
2586 
2587  return insert_result;
2588  }
2589 
2593  template <typename K, typename... Args>
2594  std::pair<iterator, bool>
2595  internal_insert(const K &key, Args &&... args)
2596  {
2597  check_outside_tx();
2598  tls_entry_type &tls_entry = tls_data.local();
2599  assert(tls_entry.ptr == nullptr);
2600 
2601  size_type height = random_level();
2602 
2603  std::pair<iterator, bool> insert_result = internal_insert_node(
2604  key, height,
2605  [&](const next_array_type &next_nodes)
2606  -> persistent_node_ptr & {
2607  obj::pool_base pop = get_pool_base();
2608 
2610  tls_entry.ptr = create_node(
2611  std::forward_as_tuple(
2612  height, next_nodes.data()),
2613  std::forward_as_tuple(
2614  std::forward<Args>(args)...));
2615 
2616  ++(tls_entry.size_diff);
2617  tls_entry.insert_stage = in_progress;
2619 
2620  assert(tls_entry.ptr != nullptr);
2621  return tls_entry.ptr;
2622  });
2623 
2624  assert(tls_entry.ptr == nullptr);
2625 
2626  return insert_result;
2627  }
2628 
2632  template <typename K, typename PrepareNode>
2633  std::pair<iterator, bool>
2634  internal_insert_node(const K &key, size_type height,
2635  PrepareNode &&prepare_new_node)
2636  {
2637  prev_array_type prev_nodes;
2638  next_array_type next_nodes;
2639  node_ptr n = nullptr;
2640 
2641  do {
2642  find_insert_pos(prev_nodes, next_nodes, key);
2643 
2644  node_ptr next = next_nodes[0].get();
2645  if (next && !allow_multimapping &&
2646  !_compare(key, get_key(next))) {
2647 
2648  return std::pair<iterator, bool>(iterator(next),
2649  false);
2650  }
2651 
2652  } while ((n = try_insert_node(prev_nodes, next_nodes, height,
2653  std::forward<PrepareNode>(
2654  prepare_new_node))) ==
2655  nullptr);
2656 
2657  assert(n);
2658  return std::pair<iterator, bool>(iterator(n), true);
2659  }
2660 
2666  template <typename PrepareNode>
2667  node_ptr
2668  try_insert_node(prev_array_type &prev_nodes,
2669  const next_array_type &next_nodes, size_type height,
2670  PrepareNode &&prepare_new_node)
2671  {
2672  assert(dummy_head->height() >= height);
2673 
2674  lock_array locks;
2675  if (!try_lock_nodes(height, prev_nodes, next_nodes, locks)) {
2676  return nullptr;
2677  }
2678 
2679  node_lock_type new_node_lock;
2680 
2681  persistent_node_ptr &new_node = prepare_new_node(next_nodes);
2682  assert(new_node != nullptr);
2683  node_ptr n = new_node.get();
2684 
2685  /*
2686  * We need to hold lock to the new node until changes
2687  * are committed to persistent domain. Otherwise, the
2688  * new node would be visible to concurrent inserts
2689  * before it is persisted.
2690  */
2691  new_node_lock = n->acquire();
2692 
2693  obj::pool_base pop = get_pool_base();
2694  /*
2695  * In the loop below we are linking a new node to all layers of
2696  * the skip list. Transaction is not required because in case of
2697  * failure the node is reachable via a pointer from persistent
2698  * TLS. During recovery, we will complete the insert. It is also
2699  * OK if concurrent readers will see not a fully-linked node
2700  * because during recovery the insert procedure will be
2701  * completed.
2702  */
2703  for (size_type level = 0; level < height; ++level) {
2704  assert(prev_nodes[level]->height() > level);
2705  assert(prev_nodes[level]->next(level) ==
2706  next_nodes[level]);
2707  assert(prev_nodes[level]->next(level) ==
2708  n->next(level));
2709  prev_nodes[level]->set_next(pop, level, new_node);
2710  }
2711 
2712 #ifndef NDEBUG
2713  try_insert_node_finish_marker();
2714 #endif
2715 
2716  new_node = nullptr;
2717  /* We need to persist the node pointer. Otherwise, on a restart,
2718  * this pointer might be not null but the node can be already
2719  * deleted. */
2720  pop.persist(&new_node, sizeof(new_node));
2721 
2722  ++_size;
2723 #if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
2724  VALGRIND_PMC_DO_FLUSH(&_size, sizeof(_size));
2725 #endif
2726 
2727  assert(n);
2728  return n;
2729  }
2730 
2735  bool
2736  check_prev_array(const prev_array_type &prevs, size_type height)
2737  {
2738  for (size_type l = 1; l < height; ++l) {
2739  if (prevs[l] == dummy_head.get()) {
2740  continue;
2741  }
2742 
2743  assert(prevs[l - 1] != dummy_head.get());
2744  assert(!_compare(get_key(prevs[l - 1]),
2745  get_key(prevs[l])));
2746  }
2747 
2748  return true;
2749  }
2750 
2751  bool
2752  try_lock_nodes(size_type height, prev_array_type &prevs,
2753  const next_array_type &nexts, lock_array &locks)
2754  {
2755  assert(check_prev_array(prevs, height));
2756 
2757  for (size_type l = 0; l < height; ++l) {
2758  if (l == 0 || prevs[l] != prevs[l - 1]) {
2759  locks[l] = prevs[l]->acquire();
2760  }
2761 
2762  persistent_node_ptr next = prevs[l]->next(l);
2763  if (next != nexts[l])
2764  /* Other thread inserted to this position and
2765  * modified the pointer before we acquired the
2766  * lock */
2767  return false;
2768  }
2769 
2770  return true;
2771  }
2772 
2784  template <typename K, typename comparator>
2785  const_iterator
2786  internal_get_bound(const K &key, const comparator &cmp) const
2787  {
2788  const_node_ptr prev = dummy_head.get();
2789  assert(prev->height() > 0);
2790  persistent_node_ptr next = nullptr;
2791 
2792  for (size_type h = prev->height(); h > 0; --h) {
2793  next = internal_find_position(h - 1, prev, key, cmp);
2794  }
2795 
2796  return const_iterator(next.get());
2797  }
2798 
2810  template <typename K, typename comparator>
2811  iterator
2812  internal_get_bound(const K &key, const comparator &cmp)
2813  {
2814  node_ptr prev = dummy_head.get();
2815  assert(prev->height() > 0);
2816  persistent_node_ptr next = nullptr;
2817 
2818  for (size_type h = prev->height(); h > 0; --h) {
2819  next = internal_find_position(h - 1, prev, key, cmp);
2820  }
2821 
2822  return iterator(next.get());
2823  }
2824 
2836  template <typename K, typename comparator>
2837  const_iterator
2839  const comparator &cmp) const
2840  {
2841  const_node_ptr prev = dummy_head.get();
2842  assert(prev->height() > 0);
2843 
2844  for (size_type h = prev->height(); h > 0; --h) {
2845  internal_find_position(h - 1, prev, key, cmp);
2846  }
2847 
2848  if (prev == dummy_head.get())
2849  return end();
2850 
2851  return const_iterator(prev);
2852  }
2853 
2854  iterator
2855  internal_erase(const_iterator pos, obj::p<difference_type> &size_diff)
2856  {
2857  assert(pos != end());
2858 
2859  obj::pool_base pop = get_pool_base();
2860 
2861  std::pair<persistent_node_ptr, persistent_node_ptr>
2862  extract_result(nullptr, nullptr);
2863 
2864  obj::flat_transaction::run(pop, [&] {
2865  extract_result = internal_extract(pos);
2866 
2867  /* Make sure that node was extracted */
2868  assert(extract_result.first != nullptr);
2869  delete_node(extract_result.first);
2870  --size_diff;
2871  obj::flat_transaction::snapshot((size_type *)&_size);
2872  --_size;
2873  });
2874 
2875  return iterator(extract_result.second.get());
2876  }
2877 
2881  std::pair<persistent_node_ptr, persistent_node_ptr>
2882  internal_extract(const_iterator it)
2883  {
2884  assert(dummy_head->height() > 0);
2885  assert(it != end());
2886  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2887 
2888  const key_type &key = traits_type::get_key(*it);
2889 
2890  prev_array_type prev_nodes;
2891  next_array_type next_nodes;
2892 
2893  fill_prev_next_arrays(prev_nodes, next_nodes, key, _compare);
2894 
2895  node_ptr erase_node = next_nodes[0].get();
2896  assert(erase_node != nullptr);
2897 
2898  if (!_compare(key, get_key(erase_node))) {
2899  /* XXX: this assertion will fail in case of multimap
2900  * because we take the first node with the same key.
2901  * Need to extend algorithm for mutimap. */
2902  assert(erase_node == it.node);
2903  return internal_extract_node(prev_nodes, next_nodes,
2904  erase_node);
2905  }
2906 
2907  return std::pair<persistent_node_ptr, persistent_node_ptr>(
2908  nullptr, nullptr);
2909  }
2910 
2911  std::pair<persistent_node_ptr, persistent_node_ptr>
2912  internal_extract_node(const prev_array_type &prev_nodes,
2913  const next_array_type &next_nodes,
2914  node_ptr erase_node)
2915  {
2916  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2917  assert(erase_node != nullptr);
2918  for (size_type level = 0; level < erase_node->height();
2919  ++level) {
2920  assert(prev_nodes[level]->height() > level);
2921  assert(next_nodes[level].get() == erase_node);
2922  prev_nodes[level]->set_next_tx(level,
2923  erase_node->next(level));
2924  }
2925 
2926  return std::pair<persistent_node_ptr, persistent_node_ptr>(
2927  next_nodes[0], erase_node->next(0));
2928  }
2929 
2934  obj::pool_base
2936  {
2937  PMEMobjpool *pop = pmemobj_pool_by_ptr(this);
2938  return obj::pool_base(pop);
2939  }
2940 
2941  void
2942  internal_copy(const concurrent_skip_list &other)
2943  {
2944  internal_copy(other.begin(), other.end());
2945  }
2946 
2947  template <typename Iterator>
2948  void
2949  internal_copy(Iterator first, Iterator last)
2950  {
2951  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2952 
2953  prev_array_type prev_nodes;
2954  prev_nodes.fill(dummy_head.get());
2955  size_type sz = 0;
2956 
2957  for (; first != last; ++first, ++sz) {
2958  persistent_node_ptr new_node = create_node(*first);
2959  node_ptr n = new_node.get();
2960  for (size_type level = 0; level < n->height();
2961  ++level) {
2962  prev_nodes[level]->set_next_tx(level, new_node);
2963  prev_nodes[level] = n;
2964  }
2965  }
2966 
2967  on_init_size = sz;
2968  /*
2969  * As internal_swap can only be called from one thread, and
2970  * there can be an outer transaction we must make sure that size
2971  * change is transactional
2972  */
2973  obj::flat_transaction::snapshot((size_type *)&_size);
2974  _size = sz;
2975  assert(std::is_sorted(
2976  this->begin(), this->end(),
2977  [&](const value_type &lhs, const value_type &rhs) {
2978  return lhs.first < rhs.first;
2979  }));
2980  }
2981 
2983  size_type
2985  {
2986  return _rnd_generator();
2987  }
2988 
2989  static size_type
2990  calc_node_size(size_type height)
2991  {
2992  return sizeof(list_node_type) +
2993  height * sizeof(typename list_node_type::node_pointer);
2994  }
2995 
2997  template <typename... Args>
2998  persistent_node_ptr
2999  create_node(Args &&... args)
3000  {
3001  size_type levels = random_level();
3002 
3003  return create_node(
3004  std::forward_as_tuple(levels),
3005  std::forward_as_tuple(std::forward<Args>(args)...));
3006  }
3007 
3008  template <typename... NodeArgs, typename... ValueArgs>
3009  persistent_node_ptr
3010  create_node(std::tuple<NodeArgs...> &&node_args,
3011  std::tuple<ValueArgs...> &&value_args)
3012  {
3013  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
3014 
3015  persistent_node_ptr node = creates_dummy_node(
3016  std::forward<std::tuple<NodeArgs...>>(node_args),
3017  index_sequence_for<NodeArgs...>{});
3018 
3019  construct_value_type(
3020  node,
3021  std::forward<std::tuple<ValueArgs...>>(value_args),
3022  index_sequence_for<ValueArgs...>{});
3023 
3024  return node;
3025  }
3026 
3027  template <typename Tuple, size_t... I>
3028  void
3029  construct_value_type(persistent_node_ptr node, Tuple &&args,
3030  index_sequence<I...>)
3031  {
3032  node_ptr new_node = node.get();
3033 
3034  node_allocator_traits::construct(
3035  _node_allocator, new_node->get(),
3036  std::get<I>(std::forward<Tuple>(args))...);
3037  }
3038 
3044  void
3046  {
3047  dummy_head = creates_dummy_node(MAX_LEVEL);
3048  }
3049 
3050  template <typename Tuple, size_t... I>
3051  persistent_node_ptr
3052  creates_dummy_node(Tuple &&args, index_sequence<I...>)
3053  {
3054  return creates_dummy_node(
3055  std::get<I>(std::forward<Tuple>(args))...);
3056  }
3057 
3067  template <typename... Args>
3068  persistent_node_ptr
3069  creates_dummy_node(size_type height, Args &&... args)
3070  {
3071  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
3072  size_type sz = calc_node_size(height);
3073 
3075  node_allocator_traits::allocate(_node_allocator, sz)
3076  .raw();
3077 
3078  assert(n != nullptr);
3079 
3080  node_allocator_traits::construct(_node_allocator, n.get(),
3081  height,
3082  std::forward<Args>(args)...);
3083 
3084  return n;
3085  }
3086 
3087  template <bool is_dummy = false>
3088  void
3089  delete_node(persistent_node_ptr &node)
3090  {
3091  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
3092  node_ptr n = node.get();
3093  size_type sz = calc_node_size(n->height());
3094 
3095  /* Destroy value */
3096  if (!is_dummy)
3097  node_allocator_traits::destroy(_node_allocator,
3098  n->get());
3099  /* Destroy node */
3100  node_allocator_traits::destroy(_node_allocator, n);
3101  /* Deallocate memory */
3102  deallocate_node(node, sz);
3103  node = nullptr;
3104  }
3105 
3106  void
3107  deallocate_node(persistent_node_ptr &node, size_type sz)
3108  {
3109  /*
3110  * Each node object has different size which depends on number
3111  * of layers the node is linked. Therefore, allocate/deallocate
3112  * just a raw byte array. persistent_ptr<uint8_t> is used as a
3113  * pointer to raw array of bytes.
3114  */
3116  node.to_persistent_ptr().raw();
3117  node_allocator_traits::deallocate(_node_allocator, tmp, sz);
3118  }
3119 
3120  void
3121  delete_dummy_head()
3122  {
3123  assert(dummy_head != nullptr);
3124  delete_node<true>(dummy_head);
3125  assert(dummy_head == nullptr);
3126  }
3127 
3128  iterator
3129  get_iterator(const_iterator it)
3130  {
3131  return iterator(
3132  const_cast<typename iterator::node_ptr>(it.node));
3133  }
3134 
3136  void
3138  {
3139  int64_t last_run_size = 0;
3140  obj::pool_base pop = get_pool_base();
3141 
3142  for (auto &tls_entry : tls_data) {
3143  persistent_node_ptr &node = tls_entry.ptr;
3144  auto &size_diff = tls_entry.size_diff;
3145  if (node) {
3146  /*
3147  * We are completing inserts which were in
3148  * progress before the crash because readers
3149  * might saw incompleted inserts before the
3150  * crash. We set the in_progress flag inside
3151  * try_insert_node function when we locked the
3152  * predecessors for the new node, therefore,
3153  * only single node with the same key might have
3154  * the in_progress status.
3155  */
3156  if (tls_entry.insert_stage == in_progress) {
3157  complete_insert(tls_entry);
3158  } else {
3159  obj::flat_transaction::run(pop, [&] {
3160  --(tls_entry.size_diff);
3161  delete_node(node);
3162  node = nullptr;
3163  });
3164  }
3165  }
3166 
3167  assert(node == nullptr);
3168 
3169  last_run_size += size_diff;
3170  }
3171 
3172  /* Make sure that on_init_size + last_run_size >= 0 */
3173  assert(last_run_size >= 0 ||
3174  on_init_size >
3175  static_cast<size_type>(std::abs(last_run_size)));
3176  obj::flat_transaction::run(pop, [&] {
3177  tls_data.clear();
3178  on_init_size += static_cast<size_t>(last_run_size);
3179  });
3180  _size = on_init_size;
3181 #if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
3182  VALGRIND_PMC_DO_FLUSH(&_size, sizeof(_size));
3183 #endif
3184  }
3185 
3186  void
3187  complete_insert(tls_entry_type &tls_entry)
3188  {
3189  persistent_node_ptr &node = tls_entry.ptr;
3190  assert(node != nullptr);
3191  assert(tls_entry.insert_stage == in_progress);
3192  prev_array_type prev_nodes;
3193  next_array_type next_nodes;
3194  node_ptr n = node.get();
3195  const key_type &key = get_key(n);
3196  size_type height = n->height();
3197 
3198  fill_prev_next_arrays(prev_nodes, next_nodes, key, _compare);
3199  obj::pool_base pop = get_pool_base();
3200 
3201  /* Node was partially linked */
3202  for (size_type level = 0; level < height; ++level) {
3203  assert(prev_nodes[level]->height() > level);
3204  assert(prev_nodes[level]->next(level) ==
3205  next_nodes[level]);
3206 
3207  if (prev_nodes[level]->next(level) != node) {
3208  /* Otherwise, node already linked on
3209  * this layer */
3210  assert(n->next(level) == next_nodes[level]);
3211  prev_nodes[level]->set_next(pop, level, node);
3212  }
3213  }
3214 
3215  node = nullptr;
3216  pop.persist(&node, sizeof(node));
3217  }
3218 
3219  struct not_greater_compare {
3220  const key_compare &my_less_compare;
3221 
3222  not_greater_compare(const key_compare &less_compare)
3223  : my_less_compare(less_compare)
3224  {
3225  }
3226 
3227  template <typename K1, typename K2>
3228  bool
3229  operator()(const K1 &first, const K2 &second) const
3230  {
3231  return !my_less_compare(second, first);
3232  }
3233  };
3234 
3235  const uint64_t pool_uuid = pmemobj_oid(this).pool_uuid_lo;
3236  node_allocator_type _node_allocator;
3237  key_compare _compare;
3238  random_level_generator_type _rnd_generator;
3239  persistent_node_ptr dummy_head;
3240 
3241  enumerable_thread_specific<tls_entry_type> tls_data;
3242 
3243  std::atomic<size_type> _size;
3244 
3251 }; /* class concurrent_skip_list */
3252 
3253 template <typename Key, typename Value, typename KeyCompare,
3254  typename RND_GENERATOR, typename Allocator, bool AllowMultimapping,
3255  size_t MAX_LEVEL>
3256 class map_traits {
3257 public:
3258  static constexpr size_t max_level = MAX_LEVEL;
3259  using random_generator_type = RND_GENERATOR;
3260  using key_type = Key;
3261  using mapped_type = Value;
3262  using compare_type = KeyCompare;
3263  using value_type = pair<const key_type, mapped_type>;
3264  using reference = value_type &;
3265  using const_reference = const value_type &;
3266  using allocator_type = Allocator;
3267 
3274  constexpr static bool allow_multimapping = AllowMultimapping;
3275 
3276  static const key_type &
3277  get_key(const_reference val)
3278  {
3279  return val.first;
3280  }
3281 }; /* class map_traits */
3282 
3283 } /* namespace detail */
3284 } /* namespace pmem */
3285 
3286 #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 predecessor nodes on each level of the skip list for the given.
Definition: concurrent_skip_list_impl.hpp:2476
pmem::detail::concurrent_skip_list::find_higher
iterator find_higher(const K &x)
Returns an iterator pointing to the first element that compares greater to the value x.
Definition: concurrent_skip_list_impl.hpp:1636
pmem::detail::concurrent_skip_list::find_lower
iterator find_lower(const K &key)
Returns an iterator pointing to the biggest element that is less than key.
Definition: concurrent_skip_list_impl.hpp:1714
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:102
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:2882
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:2812
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:1265
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:1560
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:1151
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:1120
pmem::detail::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(const concurrent_skip_list &other)
Copy constructor.
Definition: concurrent_skip_list_impl.hpp:614
pmem::detail::concurrent_skip_list::insert
std::pair< iterator, bool > insert(P &&value)
Inserts value.
Definition: concurrent_skip_list_impl.hpp:933
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:2634
pmem::detail::concurrent_skip_list::find_lower
iterator find_lower(const key_type &key)
Returns an iterator pointing to the biggest element that is less than key.
Definition: concurrent_skip_list_impl.hpp:1674
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:2283
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:2074
pmem::pool_error
Custom pool error class.
Definition: pexceptions.hpp:45
pmem::obj::experimental::self_relative_ptr::get
element_type * get() const noexcept
Get the direct pointer.
Definition: self_relative_ptr.hpp:159
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:1406
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:2035
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:1963
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:1313
pmem::obj::p::swap
void swap(p &other)
Swaps two p objects of the same type.
Definition: p.hpp:140
pmem::detail::concurrent_skip_list::find_higher_eq
iterator find_higher_eq(const K &x)
Returns an iterator pointing to the first element that compares not less (i.e.
Definition: concurrent_skip_list_impl.hpp:1483
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:1836
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:1218
pmem::detail::concurrent_skip_list::operator=
concurrent_skip_list & operator=(concurrent_skip_list &&other)
Move assignment operator.
Definition: concurrent_skip_list_impl.hpp:838
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:80
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:586
pmem::detail::concurrent_skip_list::operator=
concurrent_skip_list & operator=(const concurrent_skip_list &other)
Copy assignment operator.
Definition: concurrent_skip_list_impl.hpp:796
pmem::obj::experimental::self_relative_ptr
Persistent self-relative pointer class.
Definition: self_relative_ptr.hpp:44
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:2196
pmem::detail::concurrent_skip_list::find_lower
const_iterator find_lower(const key_type &key) const
Returns a const iterator pointing to the biggest element that is less than key.
Definition: concurrent_skip_list_impl.hpp:1692
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:420
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:2048
pmem::detail::concurrent_skip_list::create_dummy_head
void create_dummy_head()
Creates dummy head.
Definition: concurrent_skip_list_impl.hpp:3045
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:955
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:1384
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:2451
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:1942
pmem::detail::concurrent_skip_list::find_lower_eq
const_iterator find_lower_eq(const K &key) const
Returns a const iterator pointing to the biggest element that is less than or equal to key.
Definition: concurrent_skip_list_impl.hpp:1821
pmem::detail::concurrent_skip_list
Persistent memory aware implementation of the concurrent skip list.
Definition: concurrent_skip_list_impl.hpp:479
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:2086
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:553
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:2170
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:1850
pmem::detail::concurrent_skip_list::find_higher_eq
iterator find_higher_eq(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:1444
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:1083
pmem::obj::swap
void swap(pmem::obj::array< T, N > &lhs, pmem::obj::array< T, N > &rhs)
Non-member swap function.
Definition: array.hpp:880
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:58
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:750
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:1907
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:536
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:2786
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:1522
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:2668
pmem::detail::concurrent_skip_list::~concurrent_skip_list
~concurrent_skip_list()
Destructor.
Definition: concurrent_skip_list_impl.hpp:771
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:1181
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:878
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:2272
pmem::detail::concurrent_skip_list::runtime_initialize
void runtime_initialize()
Intialize concurrent_skip_list after process restart.
Definition: concurrent_skip_list_impl.hpp:729
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:3069
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:1582
pmem::detail::concurrent_skip_list::insert
void insert(InputIterator first, InputIterator last)
Inserts elements from range [first, last).
Definition: concurrent_skip_list_impl.hpp:1029
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:1892
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:2595
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:1538
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:1928
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:3137
pmem::obj::persistent_ptr
Persistent pointer class.
Definition: persistent_ptr.hpp:152
pmem::detail::transaction_base< true >::commit
static void commit()
Manually commit a transaction.
Definition: transaction.hpp:325
pmem::detail::concurrent_skip_list::find_lower_eq
iterator find_lower_eq(const key_type &key)
Returns an iterator pointing to the biggest element that is less than or equal to key.
Definition: concurrent_skip_list_impl.hpp:1754
pmem::detail::concurrent_skip_list::begin
iterator begin()
Returns an iterator to the first element of the container.
Definition: concurrent_skip_list_impl.hpp:2011
pmem::detail::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(concurrent_skip_list &&other)
Move constructor.
Definition: concurrent_skip_list_impl.hpp:676
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:906
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:1368
pmem::obj::get
T & get(pmem::obj::array< T, N > &a)
Non-member get function.
Definition: array.hpp:890
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:1049
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:2736
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:1008
pmem::detail::concurrent_skip_list::empty
bool empty() const
Checks if the container has no elements, i.e.
Definition: concurrent_skip_list_impl.hpp:2111
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:1428
pmem::detail::concurrent_skip_list::find_higher
const_iterator find_higher(const key_type &key) const
Returns an iterator pointing to the first element that is greater than key.
Definition: concurrent_skip_list_impl.hpp:1614
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:2422
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:646
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::find_lower_eq
iterator find_lower_eq(const K &key)
Returns an iterator pointing to the biggest element that is less than or equal to key.
Definition: concurrent_skip_list_impl.hpp:1796
self_relative_ptr.hpp
Persistent self-relative smart pointer.
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:2558
pmem::detail::concurrent_skip_list::find_lower_eq
const_iterator find_lower_eq(const key_type &key) const
Returns a const iterator pointing to the biggest element that is less than or equal to key.
Definition: concurrent_skip_list_impl.hpp:1773
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:2228
pmem::detail::concurrent_skip_list::find_lower
const_iterator find_lower(const K &key) const
Returns a const iterator pointing to the biggest element that is less than key.
Definition: concurrent_skip_list_impl.hpp:1738
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:2099
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:1285
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:2061
pmem::detail::concurrent_skip_list::find_higher
iterator find_higher(const key_type &key)
Returns an iterator pointing to the first element that is greater than key.
Definition: concurrent_skip_list_impl.hpp:1598
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:3250
pmem::detail::concurrent_skip_list::find_higher
const_iterator find_higher(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:1658
pmem::detail::concurrent_skip_list::clear
void clear()
Erases all elements from the container transactionally.
Definition: concurrent_skip_list_impl.hpp:1977
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:2260
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:1348
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:978
pmem::detail::concurrent_skip_list::find_higher_eq
const_iterator find_higher_eq(const K &x) const
Returns an iterator pointing to the first element that compares not less (i.e.
Definition: concurrent_skip_list_impl.hpp:1506
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:1871
pmem::detail::concurrent_skip_list::random_level
size_type random_level()
Generate random level.
Definition: concurrent_skip_list_impl.hpp:2984
pmem::detail::concurrent_skip_list::swap
void swap(concurrent_skip_list &other)
XXX: Implement get_allocator() interface.
Definition: concurrent_skip_list_impl.hpp:2129
pmem::detail::concurrent_skip_list::internal_get_biggest_less_than
const_iterator internal_get_biggest_less_than(const K &key, const comparator &cmp) const
Returns an iterator pointing to the last element from the list for which cmp(element,...
Definition: concurrent_skip_list_impl.hpp:2838
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:531
pmem::obj::flat_transaction::manual
typename detail::transaction_base< true >::manual manual
C++ manual scope transaction class.
Definition: transaction.hpp:756
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:705
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:2023
pmem::obj::flat_transaction::run
static void run(obj::pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:817
pmem::detail::transaction_base< true >::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:428
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:1241
pmem::detail::concurrent_skip_list::create_node
persistent_node_ptr create_node(Args &&... args)
Creates new node.
Definition: concurrent_skip_list_impl.hpp:2999
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:2935
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:2315
pmem::detail::concurrent_skip_list::find_higher_eq
const_iterator find_higher_eq(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:1460