Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
_concurrent_skip_list_impl.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2019-2020 Intel Corporation
3 
4  Licensed under the Apache License, Version 2.0 (the "License");
5  you may not use this file except in compliance with the License.
6  You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15 */
16 
17 #ifndef __TBB_concurrent_skip_list_H
18 #define __TBB_concurrent_skip_list_H
19 
20 #if !defined(__TBB_concurrent_map_H) && !defined(__TBB_concurrent_set_H)
21 #error Do not #include this internal file directly; use public TBB headers instead.
22 #endif
23 
24 #include "../tbb_config.h"
25 #include "../tbb_stddef.h"
26 #include "../tbb_allocator.h"
27 #include "../spin_mutex.h"
28 #include "../tbb_exception.h"
29 #include "../enumerable_thread_specific.h"
30 #include "_allocator_traits.h"
31 #include "_template_helpers.h"
32 #include "_node_handle_impl.h"
33 #include <utility> // Need std::pair
34 #include <functional>
35 #include <initializer_list>
36 #include <memory> // Need std::allocator_traits
37 #include <atomic>
38 #include <mutex>
39 #include <vector>
40 #include <array>
41 #include <type_traits>
42 #include <cstdlib>
43 #include <random>
44 #include <tuple>
45 
46 #if _MSC_VER
47 #pragma warning(disable: 4189) // warning 4189 -- local variable is initialized but not referenced
48 #pragma warning(disable: 4127) // warning 4127 -- while (true) has a constant expression in it
49 #endif
50 
51 namespace tbb {
52 namespace interface10 {
53 namespace internal {
54 
55 template <typename Value, typename Mutex>
57 
58 public:
59  using value_type = Value;
60  using size_type = std::size_t;
61  using reference = value_type & ;
62  using const_reference = const value_type & ;
63  using pointer = value_type * ;
64  using const_pointer = const value_type *;
66  using atomic_node_pointer = std::atomic<node_pointer>;
67 
68  using mutex_type = Mutex;
69  using lock_type = std::unique_lock<mutex_type>;
70 
71  skip_list_node(size_type levels) : my_height(levels), my_fullyLinked(false) {
72  for (size_type lev = 0; lev < my_height; ++lev)
73  new(&my_next(lev)) atomic_node_pointer(nullptr);
74  __TBB_ASSERT(height() == levels, "Wrong node height");
75  }
76 
78  for(size_type lev = 0; lev < my_height; ++lev)
79  my_next(lev).~atomic();
80  }
81 
82  skip_list_node(const skip_list_node&) = delete;
83 
84  skip_list_node(skip_list_node&&) = delete;
85 
86  skip_list_node& operator=(const skip_list_node&) = delete;
87 
89  return reinterpret_cast<pointer>(&my_val);
90  }
91 
93  return *storage();
94  }
95 
96  node_pointer next(size_type level) const {
97  __TBB_ASSERT(level < height(), "Cannot get next on the level greater than height");
98  return my_next(level).load(std::memory_order_acquire);
99  }
100 
102  __TBB_ASSERT(level < height(), "Cannot set next on the level greater than height");
103 
104  my_next(level).store(next, std::memory_order_release);
105  }
106 
108  size_type height() const {
109  return my_height;
110  }
111 
112  bool fully_linked() const {
114  }
115 
116  void mark_linked() {
118  }
119 
121  return lock_type(my_mutex);
122  }
123 
124 private:
125  using aligned_storage_type = typename std::aligned_storage<sizeof(value_type), alignof(value_type)>::type;
126 
128  atomic_node_pointer* arr = reinterpret_cast<atomic_node_pointer*>(this + 1);
129  return arr[level];
130  }
131 
132  const atomic_node_pointer& my_next(size_type level) const {
133  const atomic_node_pointer* arr = reinterpret_cast<const atomic_node_pointer*>(this + 1);
134  return arr[level];
135  }
136 
140  std::atomic_bool my_fullyLinked;
141 };
142 
143 template <typename NodeType, bool is_const>
145  using node_type = NodeType;
146  using node_ptr = node_type*;
147 public:
148  using iterator_category = std::forward_iterator_tag;
149  using value_type = typename node_type::value_type;
150  using difference_type = std::ptrdiff_t;
151  using pointer = typename std::conditional<is_const, typename node_type::const_pointer,
152  typename node_type::pointer>::type;
153  using reference = typename std::conditional<is_const, typename node_type::const_reference,
154  typename node_type::reference>::type;
155 
157 
158  // TODO: the code above does not compile in VS2015 (seems like a bug) - consider enabling it for all other platforms
159  // template <typename T = void, typename = typename std::enable_if<is_const, T>::type>
160  // skip_list_iterator(const skip_list_iterator<node_type, false>& other) : my_node_ptr(other.my_node_ptr) {}
161 
162  // skip_list_iterator(const skip_list_iterator& other) : my_node_ptr(other.my_node_ptr) {}
163 
165 
167  my_node_ptr = other.my_node_ptr;
168  return *this;
169  }
170 
173 
174  reference operator*() const { return *(my_node_ptr->storage()); }
175  pointer operator->() const { return &**this; }
176 
178  __TBB_ASSERT(my_node_ptr != nullptr, NULL);
179  my_node_ptr = my_node_ptr->next(0);
180  return *this;
181  }
182 
184  skip_list_iterator tmp = *this;
185  ++*this;
186  return tmp;
187  }
188 
189 private:
191 
193 
194  template <typename Traits>
195  friend class concurrent_skip_list;
196 
197  friend class skip_list_iterator<NodeType, true>;
198 
199  friend class const_range;
200  friend class range;
201 
202  template <typename T, bool M, bool U>
204 
205  template <typename T, bool M, bool U>
207 };
208 
209 template <typename NodeType, bool is_const1, bool is_const2>
211  return lhs.my_node_ptr == rhs.my_node_ptr;
212 }
213 
214 template <typename NodeType, bool is_const1, bool is_const2>
216  return lhs.my_node_ptr != rhs.my_node_ptr;
217 }
218 
219 template <typename Traits>
221 protected:
222  using traits_type = Traits;
223  using allocator_type = typename traits_type::allocator_type;
224  using allocator_traits_type = std::allocator_traits<allocator_type>;
225  using key_compare = typename traits_type::compare_type;
226  using value_compare = typename traits_type::value_compare;
227  using key_type = typename traits_type::key_type;
228  using value_type = typename traits_type::value_type;
229  using node_type = typename traits_type::node_type;
231 
232  using iterator = skip_list_iterator<list_node_type, /*is_const=*/false>;
233  using const_iterator = skip_list_iterator<list_node_type, /*is_const=*/true>;
234  using reverse_iterator = std::reverse_iterator<iterator>;
235  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
236 
238  using const_reference = const value_type&;
239  using pointer = typename allocator_traits_type::pointer;
240  using const_pointer = typename allocator_traits_type::const_pointer;
241  using size_type = std::size_t;
242  using difference_type = std::ptrdiff_t;
243 
244  using random_level_generator_type = typename traits_type::random_level_generator_type;
245  using node_allocator_type = typename std::allocator_traits<allocator_type>::template rebind_alloc<uint8_t>;
246  using node_allocator_traits = typename std::allocator_traits<allocator_type>::template rebind_traits<uint8_t>;
248 
249  static constexpr size_type MAX_LEVEL = traits_type::MAX_LEVEL;
250 
251  using array_type = std::array<node_ptr, MAX_LEVEL>;
252  using lock_array = std::array<typename list_node_type::lock_type, MAX_LEVEL>;
253 
254 public:
255  static bool const allow_multimapping = traits_type::allow_multimapping;
256 
262  }
263 
264  explicit concurrent_skip_list(const key_compare& comp, const allocator_type& alloc = allocator_type())
265  : my_node_allocator(alloc), my_compare(comp), my_size(0)
266  {
268  }
269 
270  template<class InputIt>
271  concurrent_skip_list(InputIt first, InputIt last, const key_compare& comp = key_compare(),
272  const allocator_type& alloc = allocator_type())
273  : my_node_allocator(alloc), my_compare(comp), my_size(0)
274  {
277  }
278 
281  : my_node_allocator(node_allocator_traits::select_on_container_copy_construction(other.get_allocator())),
283  {
285  internal_copy(other);
286  __TBB_ASSERT(my_size == other.my_size, "Wrong size of copy-constructed container");
287  }
288 
290  : my_node_allocator(alloc), my_compare(other.my_compare),
292  {
294  internal_copy(other);
295  __TBB_ASSERT(my_size == other.my_size, "Wrong size of copy-constructed container");
296  }
297 
301  {
302  internal_move(std::move(other));
303  }
304 
306  : my_node_allocator(alloc), my_compare(other.my_compare),
308  {
309  if (alloc == other.get_allocator()) {
310  internal_move(std::move(other));
311  } else {
312  my_size = 0;
314  internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
315  }
316  }
317 
319  clear();
321  }
322 
324  if (this != &other) {
325  using pocca_type = typename node_allocator_traits::propagate_on_container_copy_assignment;
326  clear();
328  my_compare = other.my_compare;
330  internal_copy(other);
331  }
332  return *this;
333  }
334 
336  if (this != &other) {
337  using pocma_type = typename node_allocator_traits::propagate_on_container_move_assignment;
338  clear();
339  my_compare = other.my_compare;
340  my_rnd_generator = other.my_rnd_generator;
341  internal_move_assign(std::move(other), pocma_type());
342  }
343  return *this;
344  }
345 
346  concurrent_skip_list& operator=(std::initializer_list<value_type> il)
347  {
348  clear();
349  insert(il.begin(),il.end());
350  return *this;
351  }
352 
353  std::pair<iterator, bool> insert(const value_type& value) {
354  return internal_insert(value);
355  }
356 
357  std::pair<iterator, bool> insert(value_type&& value) {
359  }
360 
362  // Ignore hint
363  return insert(value).first;
364  }
365 
367  // Ignore hint
368  return insert(std::move(value)).first;
369  }
370 
371  template<typename InputIterator>
372  void insert(InputIterator first, InputIterator last) {
373  for (InputIterator it = first; it != last; ++it)
374  insert(*it);
375  }
376 
377  void insert(std::initializer_list<value_type> init) {
378  insert(init.begin(), init.end());
379  }
380 
381  std::pair<iterator, bool> insert(node_type&& nh) {
382  if(!nh.empty()) {
383  std::pair<iterator, bool> insert_result = internal_insert_node(nh.my_node);
384  if(insert_result.second) {
385  nh.deactivate();
386  }
387  return insert_result;
388  }
389  return std::pair<iterator, bool>(end(), false);
390  }
391 
393  // Ignore hint
394  return insert(std::move(nh)).first;
395  }
396 
397  template<typename... Args >
398  std::pair<iterator, bool> emplace(Args&&... args) {
399  return internal_insert(std::forward<Args>(args)...);
400  }
401 
402  template<typename... Args>
404  // Ignore hint
405  return emplace(std::forward<Args>(args)...).first;
406  }
407 
409  std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
410  if(extract_result.first) { // node was extracted
411  delete_node(extract_result.first);
412  return iterator(extract_result.second);
413  }
414  return end();
415  }
416 
418  return unsafe_erase(get_iterator(pos));
419  }
420 
421  template <typename K, typename = tbb::internal::is_transparent<key_compare, K>,
422  typename = typename std::enable_if<!std::is_convertible<K, iterator>::value &&
423  !std::is_convertible<K, const_iterator>::value>::type>
425  std::pair<iterator, iterator> range = equal_range(key);
426  size_type sz = std::distance(range.first, range.second);
427  unsafe_erase(range.first, range.second);
428  return sz;
429  }
430 
432  while(first != last) {
434  }
435  return get_iterator(first);
436  }
437 
439  std::pair<iterator, iterator> range = equal_range(key);
440  size_type sz = std::distance(range.first, range.second);
441  unsafe_erase(range.first, range.second);
442  return sz;
443  }
444 
446  std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
447  return extract_result.first ? node_type(extract_result.first) : node_type();
448  }
449 
451  return unsafe_extract(find(key));
452  }
453 
456  }
457 
460  }
461 
462  template <typename K, typename = typename tbb::internal::is_transparent<key_compare, K> >
465  }
466 
467  template <typename K, typename = typename tbb::internal::is_transparent<key_compare, K> >
468  const_iterator lower_bound(const K& key) const {
470  }
471 
474  }
475 
478  }
479 
480  template <typename K, typename = typename tbb::internal::is_transparent<key_compare, K> >
483  }
484 
485  template <typename K, typename = typename tbb::internal::is_transparent<key_compare, K> >
486  const_iterator upper_bound(const K& key) const {
488  }
489 
491  return internal_find(key);
492  }
493 
494  const_iterator find(const key_type& key) const {
495  return internal_find(key);
496  }
497 
498  template <typename K, typename = typename tbb::internal::is_transparent<key_compare, K> >
499  iterator find(const K& key) {
500  return internal_find(key);
501  }
502 
503  template <typename K, typename = typename tbb::internal::is_transparent<key_compare, K> >
504  const_iterator find(const K& key) const {
505  return internal_find(key);
506  }
507 
508  size_type count( const key_type& key ) const {
509  return internal_count(key);
510  }
511 
512  template <typename K, typename = typename tbb::internal::is_transparent<key_compare, K> >
513  size_type count(const K& key) const {
514  return internal_count(key);
515  }
516 
517  bool contains(const key_type& key) const {
518  return find(key) != end();
519  }
520 
521  template <typename K, typename = typename tbb::internal::is_transparent<key_compare, K> >
522  bool contains(const K& key) const {
523  return find(key) != end();
524  }
525 
526  void clear() noexcept {
527  __TBB_ASSERT(dummy_head->height() > 0, NULL);
528 
529  node_ptr current = dummy_head->next(0);
530  while (current) {
531  __TBB_ASSERT(current->height() > 0, NULL);
532  node_ptr next = current->next(0);
533  delete_node(current);
534  current = next;
535  }
536 
537  my_size = 0;
538  for (size_type i = 0; i < dummy_head->height(); ++i) {
539  dummy_head->set_next(i, nullptr);
540  }
541  }
542 
544  return iterator(dummy_head->next(0));
545  }
546 
548  return const_iterator(dummy_head->next(0));
549  }
550 
552  return const_iterator(dummy_head->next(0));
553  }
554 
556  return iterator(nullptr);
557  }
558 
559  const_iterator end() const {
560  return const_iterator(nullptr);
561  }
562 
564  return const_iterator(nullptr);
565  }
566 
567  size_type size() const {
568  return my_size.load(std::memory_order_relaxed);
569  }
570 
571  size_type max_size() const {
572  return my_node_allocator.max_size();
573  }
574 
575  bool empty() const {
576  return 0 == size();
577  }
578 
580  return my_node_allocator;
581  }
582 
583  void swap(concurrent_skip_list& other) {
584  using std::swap;
585  using pocs_type = typename node_allocator_traits::propagate_on_container_swap;
587  swap(my_compare, other.my_compare);
589  swap(dummy_head, other.dummy_head);
590 
591  size_type tmp = my_size;
592  my_size.store(other.my_size);
593  other.my_size.store(tmp);
594  }
595 
596  std::pair<iterator, iterator> equal_range(const key_type& key) {
597  return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
598  }
599 
600  std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
601  return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
602  }
603 
604  template <typename K, typename = typename tbb::internal::is_transparent<key_compare, K> >
605  std::pair<iterator, iterator> equal_range(const K& key) {
606  return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
607  }
608 
609  template <typename K, typename = typename tbb::internal::is_transparent<key_compare, K> >
610  std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
611  return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
612  }
613 
614  key_compare key_comp() const { return my_compare; }
615 
616  value_compare value_comp() const { return traits_type::value_comp(my_compare); }
617 
619  public:
623  private:
627 
628  public:
629 
630  bool empty() const {
631  return my_begin.my_node_ptr->next(0) == my_end.my_node_ptr;
632  }
633 
634  bool is_divisible() const {
635  return my_level != 0 ? my_begin.my_node_ptr->next(my_level - 1) != my_end.my_node_ptr : false;
636  }
637 
638  size_type size() const { return std::distance(my_begin, my_end);}
639 
641  : my_end(r.my_end) {
642  my_begin = iterator(r.my_begin.my_node_ptr->next(r.my_level - 1));
643  my_level = my_begin.my_node_ptr->height();
644  r.my_end = my_begin;
645  }
646 
648  : my_end(l.end()), my_begin(l.begin()), my_level(my_begin.my_node_ptr->height() ) {}
649 
650  iterator begin() const { return my_begin; }
651  iterator end() const { return my_end; }
652  size_t grainsize() const { return 1; }
653 
654  }; // class const_range_type
655 
656  class range_type : public const_range_type {
657  public:
659 
662 
663  iterator begin() const {
664  node_ptr node = const_range_type::begin().my_node_ptr;
665  return iterator(node);
666  }
667 
668  iterator end() const {
669  node_ptr node = const_range_type::end().my_node_ptr;
670  return iterator(node); }
671  }; // class range_type
672 
673  range_type range() { return range_type(*this); }
674  const_range_type range() const { return const_range_type(*this); }
675 
676 private:
678  dummy_head = other.dummy_head;
679  other.dummy_head = nullptr;
680  other.create_dummy_head();
681 
682  my_size = other.my_size.load();
683  other.my_size = 0;
684  }
685 
686  static const key_type& get_key(node_ptr n) {
687  __TBB_ASSERT(n, NULL);
688  return traits_type::get_key(n->value());
689  }
690 
691  template <typename K>
693  iterator it = lower_bound(key);
694  return (it == end() || my_compare(key, traits_type::get_key(*it))) ? end() : it;
695  }
696 
697  template <typename K>
698  const_iterator internal_find(const K& key) const {
700  return (it == end() || my_compare(key, traits_type::get_key(*it))) ? end() : it;
701  }
702 
703  template <typename K>
704  size_type internal_count( const K& key ) const {
705  if (allow_multimapping) {
706  std::pair<const_iterator, const_iterator> range = equal_range(key);
707  return std::distance(range.first, range.second);
708  }
709  return (find(key) == end()) ? size_type(0) : size_type(1);
710  }
711 
721  template <typename K, typename pointer_type, typename comparator>
722  pointer_type internal_find_position( size_type level, pointer_type& prev, const K& key,
723  const comparator& cmp) const {
724  __TBB_ASSERT(level < prev->height(), "Wrong level to find position");
725  pointer_type curr = prev->next(level);
726 
727  while (curr && cmp(get_key(curr), key)) {
728  prev = curr;
729  __TBB_ASSERT(level < prev->height(), NULL);
730  curr = prev->next(level);
731  }
732 
733  return curr;
734  }
735 
736  template <typename comparator>
737  void fill_prev_next_arrays(array_type& prev_nodes, array_type& next_nodes, node_ptr prev, const key_type& key,
738  const comparator& cmp) {
739  prev_nodes.fill(dummy_head);
740  next_nodes.fill(nullptr);
741 
742  for (size_type h = prev->height(); h > 0; --h) {
743  node_ptr next = internal_find_position(h - 1, prev, key, cmp);
744  prev_nodes[h - 1] = prev;
745  next_nodes[h - 1] = next;
746  }
747  }
748 
749  template <typename comparator>
750  void fill_prev_next_by_ptr(array_type& prev_nodes, array_type& next_nodes, const_iterator it, const key_type& key,
751  const comparator& cmp) {
752  node_ptr prev = dummy_head;
753  node_ptr erase_node = it.my_node_ptr;
754  size_type node_height = erase_node->height();
755 
756  for (size_type h = prev->height(); h >= node_height; --h) {
757  internal_find_position(h - 1, prev, key, cmp);
758  }
759 
760  for (size_type h = node_height; h > 0; --h) {
761  node_ptr curr = prev->next(h - 1);
762  while (const_iterator(curr) != it) {
763  prev = curr;
764  curr = prev->next(h - 1);
765  }
766  prev_nodes[h - 1] = prev;
767  }
768 
769  std::fill(next_nodes.begin(), next_nodes.begin() + node_height, erase_node);
770  }
771 
772  template<typename... Args>
773  std::pair<iterator, bool> internal_insert(Args&&... args) {
774  node_ptr new_node = create_node(std::forward<Args>(args)...);
775  std::pair<iterator, bool> insert_result = internal_insert_node(new_node);
776  if(!insert_result.second) {
777  delete_node(new_node);
778  }
779  return insert_result;
780  }
781 
782  std::pair<iterator, bool> internal_insert_node(node_ptr new_node) {
783  array_type prev_nodes;
784  array_type next_nodes;
785  __TBB_ASSERT(dummy_head->height() >= new_node->height(), "Wrong height for new node");
786 
787  do {
788  if (allow_multimapping) {
789  fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node),
791  } else {
792  fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node), my_compare);
793  }
794 
795  node_ptr next = next_nodes[0];
796  if (next && !allow_multimapping && !my_compare(get_key(new_node), get_key(next))) {
797  // TODO: do we really need to wait?
798  while (!next->fully_linked()) {
799  // TODO: atomic backoff
800  }
801 
802  return std::pair<iterator, bool>(iterator(next), false);
803  }
804  __TBB_ASSERT(allow_multimapping || !next || my_compare(get_key(new_node), get_key(next)),
805  "Wrong elements order");
806 
807  } while (!try_insert_node(new_node, prev_nodes, next_nodes));
808 
809  __TBB_ASSERT(new_node, NULL);
810  return std::pair<iterator, bool>(iterator(new_node), true);
811  }
812 
813  bool try_insert_node(node_ptr new_node, array_type& prev_nodes, array_type& next_nodes) {
814  __TBB_ASSERT(dummy_head->height() >= new_node->height(), NULL);
815 
816  lock_array locks;
817 
818  if (!try_lock_nodes(new_node->height(), prev_nodes, next_nodes, locks)) {
819  return false;
820  }
821 
823  ((prev_nodes[0] == dummy_head ||
824  my_compare(get_key(prev_nodes[0]), get_key(new_node))) &&
825  (next_nodes[0] == nullptr || my_compare(get_key(new_node), get_key(next_nodes[0])))),
826  "Wrong elements order");
827 
828  for (size_type level = 0; level < new_node->height(); ++level) {
829  __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
830  __TBB_ASSERT(prev_nodes[level]->next(level) == next_nodes[level], NULL);
831  new_node->set_next(level, next_nodes[level]);
832  prev_nodes[level]->set_next(level, new_node);
833  }
834  new_node->mark_linked();
835 
836  ++my_size;
837 
838  return true;
839  }
840 
841  bool try_lock_nodes(size_type height, array_type& prevs, array_type& next_nodes, lock_array& locks) {
842  for (size_type l = 0; l < height; ++l) {
843  if (l == 0 || prevs[l] != prevs[l - 1])
844  locks[l] = prevs[l]->acquire();
845 
846  node_ptr next = prevs[l]->next(l);
847  if ( next != next_nodes[l]) return false;
848  }
849 
850  return true;
851  }
852 
853  template <typename K, typename comparator>
854  const_iterator internal_get_bound(const K& key, const comparator& cmp) const {
855  node_ptr prev = dummy_head;
856  __TBB_ASSERT(dummy_head->height() > 0, NULL);
857  node_ptr next = nullptr;
858 
859  for (size_type h = prev->height(); h > 0; --h) {
860  next = internal_find_position(h - 1, prev, key, cmp);
861  }
862 
863  return const_iterator(next);
864  }
865 
866  template <typename K, typename comparator>
867  iterator internal_get_bound(const K& key, const comparator& cmp){
868  node_ptr prev = dummy_head;
869  __TBB_ASSERT(dummy_head->height() > 0, NULL);
870  node_ptr next = nullptr;
871 
872  for (size_type h = prev->height(); h > 0; --h) {
873  next = internal_find_position(h - 1, prev, key, cmp);
874  }
875 
876  return iterator(next);
877  }
878 
879  // Returns node_ptr to the extracted node and node_ptr to the next node after the extracted
880  std::pair<node_ptr, node_ptr> internal_extract(const_iterator it) {
881  if ( it != end() ) {
882  key_type key = traits_type::get_key(*it);
883  __TBB_ASSERT(dummy_head->height() > 0, NULL);
884 
885  array_type prev_nodes;
886  array_type next_nodes;
887 
888  fill_prev_next_by_ptr(prev_nodes, next_nodes, it, key, my_compare);
889 
890  node_ptr erase_node = next_nodes[0];
891  __TBB_ASSERT(erase_node != nullptr, NULL);
892  node_ptr next_node = erase_node->next(0);
893 
894  if (!my_compare(key, get_key(erase_node))) {
895  for(size_type level = 0; level < erase_node->height(); ++level) {
896  __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
897  __TBB_ASSERT(next_nodes[level] == erase_node, NULL);
898  prev_nodes[level]->set_next(level, erase_node->next(level));
899  }
900  --my_size;
901  return std::pair<node_ptr, node_ptr>(erase_node, next_node);
902  }
903  }
904  return std::pair<node_ptr, node_ptr>(nullptr, nullptr);
905  }
906 
907 protected:
908  template<typename SourceType>
909  void internal_merge(SourceType&& source) {
910  using source_type = typename std::decay<SourceType>::type;
911  using source_iterator = typename source_type::iterator;
912  __TBB_STATIC_ASSERT((std::is_same<node_type, typename source_type::node_type>::value), "Incompatible containers cannot be merged");
913 
914  for(source_iterator it = source.begin(); it != source.end();) {
915  source_iterator where = it++;
916  if (allow_multimapping || !contains(traits_type::get_key(*where))) {
917  std::pair<node_ptr, node_ptr> extract_result = source.internal_extract(where);
918 
919  //If the insertion fails - return the node into source
920  node_type handle(extract_result.first);
921  __TBB_ASSERT(!handle.empty(), "Extracted handle in merge is empty");
922 
923  if (!insert(std::move(handle)).second) {
924  source.insert(std::move(handle));
925  }
926  handle.deactivate();
927  }
928  }
929  }
930 
931 private:
932  void internal_copy(const concurrent_skip_list& other) {
933  internal_copy(other.begin(), other.end());
934  }
935 
936  template<typename Iterator>
937  void internal_copy(Iterator first, Iterator last) {
938  clear();
939  try {
940  for (auto it = first; it != last; ++it)
941  insert(*it);
942  }
943  catch (...) {
944  clear();
946  throw;
947  }
948  }
949 
952  return my_rnd_generator();
953  }
954 
956  return sizeof(list_node_type) + height*sizeof(typename list_node_type::atomic_node_pointer);
957  }
958 
960  template <typename... Args>
961  node_ptr create_node(Args&&... args) {
962  size_type levels = random_level();
963 
964  size_type sz = calc_node_size(levels);
965 
966  node_ptr node = reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
967 
968  try {
969  node_allocator_traits::construct(my_node_allocator, node, levels);
970 
971  }
972  catch(...) {
973  deallocate_node(node, sz);
974  throw;
975  }
976 
977  try {
978  node_allocator_traits::construct(my_node_allocator, node->storage(), std::forward<Args>(args)...);
979  }
980  catch (...) {
981  node_allocator_traits::destroy(my_node_allocator, node);
982  deallocate_node(node, sz);
983  throw;
984  }
985 
986  return node;
987  }
988 
991 
992  dummy_head = reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
993  // TODO: investigate linkage fail in debug without this workaround
994  auto max_level = MAX_LEVEL;
995 
996  try {
997  node_allocator_traits::construct(my_node_allocator, dummy_head, max_level);
998  }
999  catch(...) {
1001  throw;
1002  }
1003  }
1004 
1005  template <bool is_dummy = false>
1006  void delete_node(node_ptr node) {
1007  size_type sz = calc_node_size(node->height());
1008  // Destroy value
1009  if (!is_dummy) node_allocator_traits::destroy(my_node_allocator, node->storage());
1010  // Destroy node
1011  node_allocator_traits::destroy(my_node_allocator, node);
1012  // Deallocate memory
1013  deallocate_node(node, sz);
1014  }
1015 
1017  node_allocator_traits::deallocate(my_node_allocator, reinterpret_cast<uint8_t*>(node), sz);
1018  }
1019 
1021  delete_node<true>(dummy_head);
1022  }
1023 
1025  return iterator(it.my_node_ptr);
1026  }
1027 
1031  internal_move(std::move(other));
1032  }
1033 
1035  if (my_node_allocator == other.my_node_allocator) {
1037  internal_move(std::move(other));
1038  } else {
1039  internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
1040  }
1041  }
1042 
1045 
1046  not_greater_compare(const key_compare& less_compare) : my_less_compare(less_compare) {}
1047 
1048  template <typename K1, typename K2>
1049  bool operator()(const K1& first, const K2& second) const {
1050  return !my_less_compare(second, first);
1051  }
1052  };
1053 
1058 
1059  template<typename OtherTraits>
1060  friend class concurrent_skip_list;
1061 
1062  std::atomic<size_type> my_size;
1063 }; // class concurrent_skip_list
1064 
1065 template <size_t MAX_LEVEL>
1067 public:
1068  static constexpr size_t max_level = MAX_LEVEL;
1069 
1071 
1072  size_t operator()() {
1073  return (distribution(engines.local()) % MAX_LEVEL) + 1;
1074  }
1075 
1076 private:
1078  std::geometric_distribution<size_t> distribution;
1079 };
1080 
1081 } // namespace internal
1082 } // namespace interface10
1083 } // namespace tbb
1084 
1085 #endif // __TBB_concurrent_skip_list_H
tbb::internal::memory_order_acquire
@ memory_order_acquire
Definition: icc_generic.h:75
tbb::interface10::internal::skip_list_iterator::operator=
skip_list_iterator & operator=(const skip_list_iterator< node_type, false > &other)
Definition: _concurrent_skip_list_impl.h:166
tbb::interface10::internal::concurrent_skip_list::unsafe_extract
node_type unsafe_extract(const key_type &key)
Definition: _concurrent_skip_list_impl.h:450
tbb::interface10::internal::concurrent_skip_list::not_greater_compare::my_less_compare
const key_compare & my_less_compare
Definition: _concurrent_skip_list_impl.h:1044
tbb::interface10::internal::concurrent_skip_list::delete_node
void delete_node(node_ptr node)
Definition: _concurrent_skip_list_impl.h:1006
tbb::interface10::internal::concurrent_skip_list::insert
void insert(InputIterator first, InputIterator last)
Definition: _concurrent_skip_list_impl.h:372
tbb::interface10::internal::skip_list_iterator< list_node_type, true >::node_type
list_node_type node_type
Definition: _concurrent_skip_list_impl.h:145
tbb::interface10::internal::concurrent_skip_list::upper_bound
const_iterator upper_bound(const key_type &key) const
Definition: _concurrent_skip_list_impl.h:476
tbb::interface10::internal::concurrent_skip_list::operator=
concurrent_skip_list & operator=(concurrent_skip_list &&other)
Definition: _concurrent_skip_list_impl.h:335
internal
Definition: _flow_graph_async_msg_impl.h:24
tbb::interface10::internal::concurrent_skip_list::const_range_type::const_range_type
const_range_type(const_range_type &r, split)
Definition: _concurrent_skip_list_impl.h:640
tbb::interface10::internal::skip_list_iterator::range
friend class range
Definition: _concurrent_skip_list_impl.h:200
tbb::interface10::internal::concurrent_skip_list::const_pointer
typename allocator_traits_type::const_pointer const_pointer
Definition: _concurrent_skip_list_impl.h:240
tbb::interface10::internal::skip_list_node::storage
pointer storage()
Definition: _concurrent_skip_list_impl.h:88
tbb::interface10::internal::operator!=
bool operator!=(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)
Definition: _concurrent_skip_list_impl.h:215
tbb::interface10::internal::skip_list_node::skip_list_node
skip_list_node(size_type levels)
Definition: _concurrent_skip_list_impl.h:71
tbb::interface10::internal::concurrent_skip_list::try_lock_nodes
bool try_lock_nodes(size_type height, array_type &prevs, array_type &next_nodes, lock_array &locks)
Definition: _concurrent_skip_list_impl.h:841
tbb::interface10::internal::concurrent_skip_list::insert
iterator insert(const_iterator, const_reference value)
Definition: _concurrent_skip_list_impl.h:361
tbb::interface10::internal::concurrent_skip_list::const_range_type::is_divisible
bool is_divisible() const
Definition: _concurrent_skip_list_impl.h:634
tbb::interface10::internal::concurrent_skip_list::my_node_allocator
node_allocator_type my_node_allocator
Definition: _concurrent_skip_list_impl.h:1054
tbb::interface10::internal::concurrent_skip_list::const_reference
const value_type & const_reference
Definition: _concurrent_skip_list_impl.h:238
tbb::internal::allocator_copy_assignment
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
Definition: _allocator_traits.h:49
_node_handle_impl.h
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
tbb::interface10::internal::concurrent_skip_list::begin
const_iterator begin() const
Definition: _concurrent_skip_list_impl.h:547
tbb::interface10::internal::skip_list_iterator
Definition: _concurrent_skip_list_impl.h:144
tbb::interface10::internal::concurrent_skip_list::const_range_type::end
iterator end() const
Definition: _concurrent_skip_list_impl.h:651
tbb::interface10::internal::skip_list_iterator::operator++
skip_list_iterator operator++(int)
Definition: _concurrent_skip_list_impl.h:183
tbb::interface10::internal::skip_list_iterator::skip_list_iterator
skip_list_iterator(const skip_list_iterator< node_type, false > &other)
Definition: _concurrent_skip_list_impl.h:164
tbb::internal::no_assign
Base class for types that should not be assigned.
Definition: tbb_stddef.h:322
tbb::internal::allocator_move_assignment
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
Definition: _allocator_traits.h:59
tbb::interface10::internal::concurrent_skip_list::const_iterator
skip_list_iterator< list_node_type, true > const_iterator
Definition: _concurrent_skip_list_impl.h:233
tbb::interface10::internal::concurrent_skip_list::internal_get_bound
const_iterator internal_get_bound(const K &key, const comparator &cmp) const
Definition: _concurrent_skip_list_impl.h:854
tbb::interface10::internal::concurrent_geometric_level_generator::max_level
static constexpr size_t max_level
Definition: _concurrent_skip_list_impl.h:1068
tbb::interface10::internal::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(const concurrent_skip_list &other)
Definition: _concurrent_skip_list_impl.h:280
tbb::interface10::internal::concurrent_skip_list::end
const_iterator end() const
Definition: _concurrent_skip_list_impl.h:559
tbb::interface10::internal::concurrent_skip_list::iterator
skip_list_iterator< list_node_type, false > iterator
Definition: _concurrent_skip_list_impl.h:232
tbb::interface10::internal::concurrent_skip_list::unsafe_erase
iterator unsafe_erase(const_iterator first, const_iterator last)
Definition: _concurrent_skip_list_impl.h:431
tbb::interface10::internal::concurrent_skip_list::insert
std::pair< iterator, bool > insert(value_type &&value)
Definition: _concurrent_skip_list_impl.h:357
tbb::interface10::internal::skip_list_iterator::skip_list_iterator
skip_list_iterator()
Definition: _concurrent_skip_list_impl.h:156
tbb::interface10::internal::concurrent_skip_list::internal_count
size_type internal_count(const K &key) const
Definition: _concurrent_skip_list_impl.h:704
tbb::interface10::internal::skip_list_node::mutex_type
Mutex mutex_type
Definition: _concurrent_skip_list_impl.h:68
tbb::interface10::internal::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
Definition: _concurrent_skip_list_impl.h:264
tbb::interface10::internal::concurrent_skip_list::MAX_LEVEL
static constexpr size_type MAX_LEVEL
Definition: _concurrent_skip_list_impl.h:249
tbb::interface10::internal::concurrent_skip_list::lower_bound
const_iterator lower_bound(const key_type &key) const
Definition: _concurrent_skip_list_impl.h:458
tbb::interface10::internal::concurrent_skip_list::node_allocator_type
typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t > node_allocator_type
Definition: _concurrent_skip_list_impl.h:245
tbb
The graph class.
Definition: serial/tbb/parallel_for.h:46
tbb::internal::first
Container::iterator first(Container &c)
Definition: _range_iterator.h:46
tbb::interface10::internal::concurrent_skip_list::size_type
std::size_t size_type
Definition: _concurrent_skip_list_impl.h:241
tbb::internal::allocator_swap
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
Definition: _allocator_traits.h:69
tbb::interface10::internal::concurrent_skip_list::find
iterator find(const key_type &key)
Definition: _concurrent_skip_list_impl.h:490
tbb::interface10::internal::skip_list_node::const_reference
const value_type & const_reference
Definition: _concurrent_skip_list_impl.h:62
tbb::internal::last
Container::iterator last(Container &c)
Definition: _range_iterator.h:52
tbb::interface10::internal::concurrent_skip_list::get_key
static const key_type & get_key(node_ptr n)
Definition: _concurrent_skip_list_impl.h:686
tbb::interface10::internal::concurrent_skip_list::const_range_type::my_begin
const_iterator my_begin
Definition: _concurrent_skip_list_impl.h:625
tbb::interface10::internal::skip_list_iterator::operator==
friend bool operator==(const skip_list_iterator< T, M > &, const skip_list_iterator< T, U > &)
tbb::interface10::internal::skip_list_node::acquire
lock_type acquire()
Definition: _concurrent_skip_list_impl.h:120
tbb::internal::swap
void swap(atomic< T > &lhs, atomic< T > &rhs)
Definition: atomic.h:564
tbb::interface10::internal::skip_list_iterator< list_node_type, true >::node_ptr
node_type * node_ptr
Definition: _concurrent_skip_list_impl.h:146
tbb::interface10::internal::skip_list_node::set_next
void set_next(size_type level, node_pointer next)
Definition: _concurrent_skip_list_impl.h:101
tbb::interface10::internal::concurrent_skip_list::unsafe_extract
node_type unsafe_extract(const_iterator pos)
Definition: _concurrent_skip_list_impl.h:445
tbb::interface10::internal::concurrent_skip_list::value_compare
typename traits_type::value_compare value_compare
Definition: _concurrent_skip_list_impl.h:226
tbb::interface10::internal::concurrent_skip_list::allocator_type
typename traits_type::allocator_type allocator_type
Definition: _concurrent_skip_list_impl.h:223
tbb::interface6::enumerable_thread_specific
The enumerable_thread_specific container.
Definition: enumerable_thread_specific.h:63
tbb::interface10::internal::concurrent_skip_list::deallocate_node
void deallocate_node(node_ptr node, size_type sz)
Definition: _concurrent_skip_list_impl.h:1016
tbb::interface10::internal::concurrent_skip_list::const_range_type::empty
bool empty() const
Definition: _concurrent_skip_list_impl.h:630
tbb::interface10::internal::skip_list_iterator::skip_list_iterator
skip_list_iterator(const skip_list_iterator< node_type, true > &other)
Definition: _concurrent_skip_list_impl.h:172
tbb::interface10::internal::concurrent_skip_list::internal_copy
void internal_copy(Iterator first, Iterator last)
Definition: _concurrent_skip_list_impl.h:937
tbb::interface10::internal::concurrent_skip_list::const_range_type::my_end
const_iterator my_end
Definition: _concurrent_skip_list_impl.h:624
tbb::interface10::internal::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())
Definition: _concurrent_skip_list_impl.h:271
tbb::interface10::internal::concurrent_skip_list::empty
bool empty() const
Definition: _concurrent_skip_list_impl.h:575
tbb::interface10::internal::concurrent_skip_list::upper_bound
const_iterator upper_bound(const K &key) const
Definition: _concurrent_skip_list_impl.h:486
tbb::interface10::internal::skip_list_iterator< list_node_type, true >::reference
typename std::conditional< is_const, typename node_type::const_reference, typename node_type::reference >::type reference
Definition: _concurrent_skip_list_impl.h:154
tbb::interface10::internal::concurrent_skip_list::create_node
node_ptr create_node(Args &&... args)
Definition: _concurrent_skip_list_impl.h:961
tbb::interface10::internal::skip_list_iterator::my_node_ptr
node_ptr my_node_ptr
Definition: _concurrent_skip_list_impl.h:192
tbb::interface10::internal::concurrent_skip_list::not_greater_compare
Definition: _concurrent_skip_list_impl.h:1043
tbb::interface10::internal::concurrent_skip_list::~concurrent_skip_list
~concurrent_skip_list()
Definition: _concurrent_skip_list_impl.h:318
tbb::split
Dummy type that distinguishes splitting constructor from copy constructor.
Definition: tbb_stddef.h:416
tbb::interface10::internal::concurrent_skip_list::internal_copy
void internal_copy(const concurrent_skip_list &other)
Definition: _concurrent_skip_list_impl.h:932
tbb::interface10::internal::concurrent_skip_list::my_size
std::atomic< size_type > my_size
Definition: _concurrent_skip_list_impl.h:1062
tbb::interface10::internal::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
Definition: _concurrent_skip_list_impl.h:289
tbb::interface10::internal::skip_list_iterator::skip_list_iterator
skip_list_iterator(node_type *n)
Definition: _concurrent_skip_list_impl.h:190
tbb::interface10::internal::skip_list_iterator< list_node_type, true >::iterator_category
std::forward_iterator_tag iterator_category
Definition: _concurrent_skip_list_impl.h:148
tbb::interface10::internal::concurrent_skip_list::internal_get_bound
iterator internal_get_bound(const K &key, const comparator &cmp)
Definition: _concurrent_skip_list_impl.h:867
_template_helpers.h
tbb::interface10::internal::concurrent_skip_list::node_allocator_traits
typename std::allocator_traits< allocator_type >::template rebind_traits< uint8_t > node_allocator_traits
Definition: _concurrent_skip_list_impl.h:246
tbb::interface10::internal::concurrent_skip_list::my_rnd_generator
random_level_generator_type my_rnd_generator
Definition: _concurrent_skip_list_impl.h:1056
tbb::interface10::internal::concurrent_skip_list::get_allocator
allocator_type get_allocator() const
Definition: _concurrent_skip_list_impl.h:579
tbb::interface10::internal::skip_list_node::~skip_list_node
~skip_list_node()
Definition: _concurrent_skip_list_impl.h:77
tbb::interface10::internal::concurrent_skip_list::internal_move
void internal_move(concurrent_skip_list &&other)
Definition: _concurrent_skip_list_impl.h:677
tbb::interface10::internal::concurrent_skip_list::key_comp
key_compare key_comp() const
Definition: _concurrent_skip_list_impl.h:614
tbb::interface10::internal::concurrent_skip_list::upper_bound
iterator upper_bound(const key_type &key)
Definition: _concurrent_skip_list_impl.h:472
tbb::interface10::internal::concurrent_skip_list::value_comp
value_compare value_comp() const
Definition: _concurrent_skip_list_impl.h:616
tbb::interface10::internal::skip_list_node::pointer
value_type * pointer
Definition: _concurrent_skip_list_impl.h:63
tbb::interface10::internal::concurrent_skip_list::const_range_type
Definition: _concurrent_skip_list_impl.h:618
tbb::interface10::internal::concurrent_skip_list::const_reverse_iterator
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: _concurrent_skip_list_impl.h:235
tbb::interface10::internal::concurrent_skip_list::internal_insert
std::pair< iterator, bool > internal_insert(Args &&... args)
Definition: _concurrent_skip_list_impl.h:773
tbb::interface10::internal::concurrent_skip_list::cbegin
const_iterator cbegin() const
Definition: _concurrent_skip_list_impl.h:551
tbb::interface10::internal::concurrent_skip_list::internal_merge
void internal_merge(SourceType &&source)
Definition: _concurrent_skip_list_impl.h:909
tbb::interface10::internal::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(concurrent_skip_list &&other)
Definition: _concurrent_skip_list_impl.h:298
tbb::interface10::internal::concurrent_skip_list::begin
iterator begin()
Definition: _concurrent_skip_list_impl.h:543
tbb::interface10::internal::concurrent_skip_list::my_compare
key_compare my_compare
Definition: _concurrent_skip_list_impl.h:1055
tbb::interface10::internal::concurrent_skip_list::range
const_range_type range() const
Definition: _concurrent_skip_list_impl.h:674
tbb::interface10::internal::concurrent_skip_list::range_type::range_type
range_type(const concurrent_skip_list &l)
Definition: _concurrent_skip_list_impl.h:661
tbb::interface10::internal::skip_list_node::my_next
atomic_node_pointer & my_next(size_type level)
Definition: _concurrent_skip_list_impl.h:127
tbb::internal::memory_order_relaxed
@ memory_order_relaxed
Definition: icc_generic.h:75
tbb::interface10::internal::concurrent_skip_list::lock_array
std::array< typename list_node_type::lock_type, MAX_LEVEL > lock_array
Definition: _concurrent_skip_list_impl.h:252
tbb::interface10::internal::concurrent_skip_list::random_level_generator_type
typename traits_type::random_level_generator_type random_level_generator_type
Definition: _concurrent_skip_list_impl.h:244
tbb::interface10::internal::concurrent_skip_list::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: _concurrent_skip_list_impl.h:605
tbb::interface10::internal::concurrent_skip_list::const_range_type::grainsize
size_t grainsize() const
Definition: _concurrent_skip_list_impl.h:652
tbb::interface10::internal::concurrent_skip_list::operator=
concurrent_skip_list & operator=(std::initializer_list< value_type > il)
Definition: _concurrent_skip_list_impl.h:346
tbb::interface10::internal::skip_list_iterator< list_node_type, true >::pointer
typename std::conditional< is_const, typename node_type::const_pointer, typename node_type::pointer >::type pointer
Definition: _concurrent_skip_list_impl.h:152
tbb::interface10::internal::concurrent_skip_list::array_type
std::array< node_ptr, MAX_LEVEL > array_type
Definition: _concurrent_skip_list_impl.h:251
tbb::interface10::internal::concurrent_skip_list::size
size_type size() const
Definition: _concurrent_skip_list_impl.h:567
tbb::interface10::internal::skip_list_node::value_type
Value value_type
Definition: _concurrent_skip_list_impl.h:59
tbb::interface10::internal::skip_list_iterator::operator*
reference operator*() const
Definition: _concurrent_skip_list_impl.h:174
__TBB_STATIC_ASSERT
#define __TBB_STATIC_ASSERT(condition, msg)
Definition: tbb_stddef.h:553
tbb::interface10::internal::concurrent_skip_list::equal_range
std::pair< iterator, iterator > equal_range(const key_type &key)
Definition: _concurrent_skip_list_impl.h:596
tbb::interface10::internal::skip_list_node::const_pointer
const value_type * const_pointer
Definition: _concurrent_skip_list_impl.h:64
tbb::interface10::internal::skip_list_node::my_height
size_type my_height
Definition: _concurrent_skip_list_impl.h:139
tbb::move
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319
tbb::interface10::internal::concurrent_skip_list::not_greater_compare::not_greater_compare
not_greater_compare(const key_compare &less_compare)
Definition: _concurrent_skip_list_impl.h:1046
key
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle * key
Definition: ittnotify_static.h:198
tbb::interface10::internal::concurrent_skip_list::unsafe_erase
size_type unsafe_erase(const K &key)
Definition: _concurrent_skip_list_impl.h:424
tbb::interface10::internal::operator==
bool operator==(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)
Definition: _concurrent_skip_list_impl.h:210
tbb::interface10::internal::concurrent_skip_list::upper_bound
iterator upper_bound(const K &key)
Definition: _concurrent_skip_list_impl.h:481
tbb::interface10::internal::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
Definition: _concurrent_skip_list_impl.h:305
tbb::interface10::internal::concurrent_geometric_level_generator::engines
tbb::enumerable_thread_specific< std::mt19937_64 > engines
Definition: _concurrent_skip_list_impl.h:1077
tbb::interface10::internal::skip_list_iterator< list_node_type, true >::difference_type
std::ptrdiff_t difference_type
Definition: _concurrent_skip_list_impl.h:150
tbb::interface10::internal::skip_list_node::atomic_node_pointer
std::atomic< node_pointer > atomic_node_pointer
Definition: _concurrent_skip_list_impl.h:66
tbb::interface10::internal::concurrent_geometric_level_generator::concurrent_geometric_level_generator
concurrent_geometric_level_generator()
Definition: _concurrent_skip_list_impl.h:1070
tbb::interface10::internal::concurrent_skip_list::insert
void insert(std::initializer_list< value_type > init)
Definition: _concurrent_skip_list_impl.h:377
tbb::interface10::internal::concurrent_skip_list::emplace_hint
iterator emplace_hint(const_iterator, Args &&... args)
Definition: _concurrent_skip_list_impl.h:403
tbb::interface10::internal::concurrent_skip_list::const_range_type::size_type
typename concurrent_skip_list::size_type size_type
Definition: _concurrent_skip_list_impl.h:620
tbb::interface10::internal::skip_list_node::mark_linked
void mark_linked()
Definition: _concurrent_skip_list_impl.h:116
tbb::interface10::internal::skip_list_node::reference
value_type & reference
Definition: _concurrent_skip_list_impl.h:61
tbb::interface10::internal::concurrent_skip_list::internal_find
const_iterator internal_find(const K &key) const
Definition: _concurrent_skip_list_impl.h:698
tbb::interface10::internal::concurrent_skip_list::clear
void clear() noexcept
Definition: _concurrent_skip_list_impl.h:526
tbb::interface10::internal::concurrent_skip_list::cend
const_iterator cend() const
Definition: _concurrent_skip_list_impl.h:563
tbb::interface10::internal::skip_list_iterator< list_node_type, true >::value_type
typename node_type::value_type value_type
Definition: _concurrent_skip_list_impl.h:149
tbb::interface10::internal::skip_list_iterator::operator!=
friend bool operator!=(const skip_list_iterator< T, M > &, const skip_list_iterator< T, U > &)
tbb::interface10::internal::concurrent_skip_list::const_range_type::const_range_type
const_range_type(const concurrent_skip_list &l)
Definition: _concurrent_skip_list_impl.h:647
tbb::interface10::internal::concurrent_skip_list::range_type::range_type
range_type(range_type &r, split)
Definition: _concurrent_skip_list_impl.h:660
tbb::interface10::internal::concurrent_skip_list::calc_node_size
static size_type calc_node_size(size_type height)
Definition: _concurrent_skip_list_impl.h:955
tbb::interface10::internal::concurrent_skip_list::random_level
size_type random_level()
Definition: _concurrent_skip_list_impl.h:951
tbb::interface10::internal::skip_list_node::my_mutex
mutex_type my_mutex
Definition: _concurrent_skip_list_impl.h:137
tbb::interface10::internal::concurrent_skip_list::range_type::begin
iterator begin() const
Definition: _concurrent_skip_list_impl.h:663
tbb::interface10::internal::concurrent_skip_list::concurrent_skip_list
concurrent_skip_list()
Definition: _concurrent_skip_list_impl.h:260
tbb::interface10::internal::concurrent_skip_list::get_iterator
static iterator get_iterator(const_iterator it)
Definition: _concurrent_skip_list_impl.h:1024
tbb::interface10::internal::concurrent_skip_list::range_type::iterator
typename concurrent_skip_list::iterator iterator
Definition: _concurrent_skip_list_impl.h:658
tbb::interface10::internal::skip_list_iterator::const_range
friend class const_range
Definition: _concurrent_skip_list_impl.h:199
tbb::internal::memory_order_release
@ memory_order_release
Definition: icc_generic.h:76
tbb::interface10::internal::concurrent_skip_list::insert
std::pair< iterator, bool > insert(node_type &&nh)
Definition: _concurrent_skip_list_impl.h:381
tbb::interface10::internal::concurrent_skip_list::const_range_type::iterator
typename concurrent_skip_list::const_iterator iterator
Definition: _concurrent_skip_list_impl.h:622
tbb::interface10::internal::concurrent_skip_list::list_node_type
skip_list_node< value_type, typename traits_type::mutex_type > list_node_type
Definition: _concurrent_skip_list_impl.h:230
tbb::interface10::internal::concurrent_skip_list::swap
void swap(concurrent_skip_list &other)
Definition: _concurrent_skip_list_impl.h:583
tbb::interface10::internal::concurrent_skip_list::internal_move_assign
void internal_move_assign(concurrent_skip_list &&other, std::false_type)
Definition: _concurrent_skip_list_impl.h:1034
_allocator_traits.h
tbb::interface10::internal::concurrent_skip_list::find
const_iterator find(const key_type &key) const
Definition: _concurrent_skip_list_impl.h:494
tbb::interface10::internal::concurrent_skip_list::internal_find
iterator internal_find(const K &key)
Definition: _concurrent_skip_list_impl.h:692
tbb::interface10::internal::concurrent_skip_list::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: _concurrent_skip_list_impl.h:353
tbb::interface10::internal::concurrent_skip_list::key_type
typename traits_type::key_type key_type
Definition: _concurrent_skip_list_impl.h:227
tbb::interface10::internal::concurrent_skip_list::internal_move_assign
void internal_move_assign(concurrent_skip_list &&other, std::true_type)
Definition: _concurrent_skip_list_impl.h:1028
tbb::interface10::internal::concurrent_skip_list::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: _concurrent_skip_list_impl.h:398
tbb::internal::true_type
bool_constant< true > true_type
Definition: tbb_stddef.h:489
tbb::interface10::internal::concurrent_skip_list::equal_range
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
Definition: _concurrent_skip_list_impl.h:600
tbb::interface10::internal::concurrent_skip_list::lower_bound
iterator lower_bound(const key_type &key)
Definition: _concurrent_skip_list_impl.h:454
tbb::interface10::internal::concurrent_skip_list::const_range_type::begin
iterator begin() const
Definition: _concurrent_skip_list_impl.h:650
tbb::interface10::internal::skip_list_node
Definition: _concurrent_skip_list_impl.h:56
tbb::interface10::internal::concurrent_geometric_level_generator::distribution
std::geometric_distribution< size_t > distribution
Definition: _concurrent_skip_list_impl.h:1078
tbb::interface10::internal::concurrent_skip_list::lower_bound
iterator lower_bound(const K &key)
Definition: _concurrent_skip_list_impl.h:463
tbb::interface10::internal::concurrent_skip_list::difference_type
std::ptrdiff_t difference_type
Definition: _concurrent_skip_list_impl.h:242
tbb::interface10::internal::concurrent_skip_list::internal_insert_node
std::pair< iterator, bool > internal_insert_node(node_ptr new_node)
Definition: _concurrent_skip_list_impl.h:782
tbb::interface10::internal::concurrent_skip_list::internal_find_position
pointer_type internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
Definition: _concurrent_skip_list_impl.h:722
tbb::interface10::internal::concurrent_skip_list::allocator_traits_type
std::allocator_traits< allocator_type > allocator_traits_type
Definition: _concurrent_skip_list_impl.h:224
tbb::interface10::internal::concurrent_skip_list::range_type::end
iterator end() const
Definition: _concurrent_skip_list_impl.h:668
tbb::interface10::internal::concurrent_skip_list::try_insert_node
bool try_insert_node(node_ptr new_node, array_type &prev_nodes, array_type &next_nodes)
Definition: _concurrent_skip_list_impl.h:813
tbb::interface10::internal::concurrent_skip_list::traits_type
Traits traits_type
Definition: _concurrent_skip_list_impl.h:222
tbb::interface10::internal::concurrent_geometric_level_generator
Definition: _concurrent_skip_list_impl.h:1066
tbb::interface10::internal::concurrent_skip_list::contains
bool contains(const K &key) const
Definition: _concurrent_skip_list_impl.h:522
tbb::interface10::internal::concurrent_skip_list::find
iterator find(const K &key)
Definition: _concurrent_skip_list_impl.h:499
tbb::interface10::internal::concurrent_geometric_level_generator::operator()
size_t operator()()
Definition: _concurrent_skip_list_impl.h:1072
tbb::interface10::internal::skip_list_node::aligned_storage_type
typename std::aligned_storage< sizeof(value_type), alignof(value_type)>::type aligned_storage_type
Definition: _concurrent_skip_list_impl.h:125
tbb::interface10::internal::concurrent_skip_list::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: _concurrent_skip_list_impl.h:610
tbb::interface10::internal::concurrent_skip_list::key_compare
typename traits_type::compare_type key_compare
Definition: _concurrent_skip_list_impl.h:225
tbb::interface10::internal::concurrent_skip_list::delete_dummy_head
void delete_dummy_head()
Definition: _concurrent_skip_list_impl.h:1020
tbb::interface10::internal::concurrent_skip_list::fill_prev_next_by_ptr
void fill_prev_next_by_ptr(array_type &prev_nodes, array_type &next_nodes, const_iterator it, const key_type &key, const comparator &cmp)
Definition: _concurrent_skip_list_impl.h:750
value
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
Definition: ittnotify_static.h:192
tbb::interface10::internal::skip_list_node::fully_linked
bool fully_linked() const
Definition: _concurrent_skip_list_impl.h:112
tbb::interface10::internal::concurrent_skip_list::range_type
Definition: _concurrent_skip_list_impl.h:656
tbb::interface10::internal::concurrent_skip_list::range
range_type range()
Definition: _concurrent_skip_list_impl.h:673
tbb::interface10::internal::concurrent_skip_list::not_greater_compare::operator()
bool operator()(const K1 &first, const K2 &second) const
Definition: _concurrent_skip_list_impl.h:1049
tbb::interface10::internal::concurrent_skip_list::const_range_type::size
size_type size() const
Definition: _concurrent_skip_list_impl.h:638
tbb::interface10::internal::concurrent_skip_list::const_range_type::value_type
typename concurrent_skip_list::value_type value_type
Definition: _concurrent_skip_list_impl.h:621
tbb::interface10::internal::concurrent_skip_list::dummy_head
node_ptr dummy_head
Definition: _concurrent_skip_list_impl.h:1057
tbb::interface10::internal::skip_list_node::lock_type
std::unique_lock< mutex_type > lock_type
Definition: _concurrent_skip_list_impl.h:69
tbb::interface10::internal::concurrent_skip_list::pointer
typename allocator_traits_type::pointer pointer
Definition: _concurrent_skip_list_impl.h:239
tbb::interface10::internal::skip_list_node::my_fullyLinked
std::atomic_bool my_fullyLinked
Definition: _concurrent_skip_list_impl.h:140
tbb::interface10::internal::concurrent_skip_list::allow_multimapping
static const bool allow_multimapping
Definition: _concurrent_skip_list_impl.h:255
tbb::interface10::internal::concurrent_skip_list::reference
value_type & reference
Definition: _concurrent_skip_list_impl.h:237
tbb::interface10::internal::concurrent_skip_list::const_range_type::my_level
size_type my_level
Definition: _concurrent_skip_list_impl.h:626
tbb::internal::false_type
bool_constant< false > false_type
Definition: tbb_stddef.h:490
tbb::interface10::internal::concurrent_skip_list::lower_bound
const_iterator lower_bound(const K &key) const
Definition: _concurrent_skip_list_impl.h:468
tbb::interface10::internal::concurrent_skip_list::reverse_iterator
std::reverse_iterator< iterator > reverse_iterator
Definition: _concurrent_skip_list_impl.h:234
tbb::interface10::internal::concurrent_skip_list::count
size_type count(const K &key) const
Definition: _concurrent_skip_list_impl.h:513
tbb::interface10::internal::skip_list_node::next
node_pointer next(size_type level) const
Definition: _concurrent_skip_list_impl.h:96
tbb::interface10::internal::concurrent_skip_list::max_size
size_type max_size() const
Definition: _concurrent_skip_list_impl.h:571
tbb::interface10::internal::concurrent_skip_list::count
size_type count(const key_type &key) const
Definition: _concurrent_skip_list_impl.h:508
tbb::interface10::internal::concurrent_skip_list::unsafe_erase
iterator unsafe_erase(iterator pos)
Definition: _concurrent_skip_list_impl.h:408
tbb::interface10::internal::skip_list_node::value
reference value()
Definition: _concurrent_skip_list_impl.h:92
tbb::interface10::internal::concurrent_skip_list::find
const_iterator find(const K &key) const
Definition: _concurrent_skip_list_impl.h:504
tbb::interface10::internal::concurrent_skip_list::create_dummy_head
void create_dummy_head()
Definition: _concurrent_skip_list_impl.h:989
tbb::interface10::internal::skip_list_node::my_val
aligned_storage_type my_val
Definition: _concurrent_skip_list_impl.h:138
tbb::interface10::internal::skip_list_node::height
size_type height() const
Definition: _concurrent_skip_list_impl.h:108
tbb::interface10::internal::concurrent_skip_list::insert
iterator insert(const_iterator, value_type &&value)
Definition: _concurrent_skip_list_impl.h:366
tbb::interface10::internal::concurrent_skip_list::unsafe_erase
iterator unsafe_erase(const_iterator pos)
Definition: _concurrent_skip_list_impl.h:417
type
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
Definition: ittnotify_static.h:198
tbb::interface10::internal::skip_list_node::my_next
const atomic_node_pointer & my_next(size_type level) const
Definition: _concurrent_skip_list_impl.h:132
h
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function h
Definition: ittnotify_static.h:159
tbb::interface10::internal::skip_list_node::operator=
skip_list_node & operator=(const skip_list_node &)=delete
tbb::interface10::internal::concurrent_skip_list::internal_extract
std::pair< node_ptr, node_ptr > internal_extract(const_iterator it)
Definition: _concurrent_skip_list_impl.h:880
tbb::interface10::internal::concurrent_skip_list::contains
bool contains(const key_type &key) const
Definition: _concurrent_skip_list_impl.h:517
tbb::interface10::internal::concurrent_skip_list::value_type
typename traits_type::value_type value_type
Definition: _concurrent_skip_list_impl.h:228
tbb::interface10::internal::concurrent_skip_list::node_type
typename traits_type::node_type node_type
Definition: _concurrent_skip_list_impl.h:229
tbb::interface10::internal::concurrent_skip_list::insert
iterator insert(const_iterator, node_type &&nh)
Definition: _concurrent_skip_list_impl.h:392
tbb::interface10::internal::concurrent_skip_list::unsafe_erase
size_type unsafe_erase(const key_type &key)
Definition: _concurrent_skip_list_impl.h:438
tbb::interface10::internal::skip_list_iterator::operator->
pointer operator->() const
Definition: _concurrent_skip_list_impl.h:175
tbb::interface10::internal::concurrent_skip_list
Definition: _concurrent_skip_list_impl.h:220
tbb::interface10::internal::skip_list_node::size_type
std::size_t size_type
Definition: _concurrent_skip_list_impl.h:60
tbb::interface10::internal::concurrent_skip_list::end
iterator end()
Definition: _concurrent_skip_list_impl.h:555
tbb::interface10::internal::concurrent_skip_list::fill_prev_next_arrays
void fill_prev_next_arrays(array_type &prev_nodes, array_type &next_nodes, node_ptr prev, const key_type &key, const comparator &cmp)
Definition: _concurrent_skip_list_impl.h:737
tbb::interface10::internal::concurrent_skip_list::operator=
concurrent_skip_list & operator=(const concurrent_skip_list &other)
Definition: _concurrent_skip_list_impl.h:323
tbb::interface10::internal::skip_list_iterator::operator++
skip_list_iterator & operator++()
Definition: _concurrent_skip_list_impl.h:177

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.