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 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:
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 
156  skip_list_iterator() : my_node_ptr(nullptr) {}
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 
164  skip_list_iterator(const skip_list_iterator<node_type, false>& other) : my_node_ptr(other.my_node_ptr) {}
165 
167  skip_list_iterator(const skip_list_iterator<node_type, true>& other) : my_node_ptr(other.my_node_ptr) {}
168 
169  reference operator*() const { return *(my_node_ptr->storage()); }
170  pointer operator->() const { return &**this; }
171 
173  __TBB_ASSERT(my_node_ptr != nullptr, NULL);
174  my_node_ptr = my_node_ptr->next(0);
175  return *this;
176  }
177 
179  skip_list_iterator tmp = *this;
180  ++*this;
181  return tmp;
182  }
183 
184 private:
185  skip_list_iterator(node_type* n) : my_node_ptr(n) {}
186 
188 
189  template <typename Traits>
190  friend class concurrent_skip_list;
191 
192  friend class skip_list_iterator<NodeType, true>;
193 
194  friend class const_range;
195  friend class range;
196 
197  template <typename T, bool M, bool U>
199 
200  template <typename T, bool M, bool U>
202 };
203 
204 template <typename NodeType, bool is_const1, bool is_const2>
206  return lhs.my_node_ptr == rhs.my_node_ptr;
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 Traits>
216 protected:
217  using traits_type = Traits;
218  using allocator_type = typename traits_type::allocator_type;
219  using allocator_traits_type = std::allocator_traits<allocator_type>;
220  using key_compare = typename traits_type::compare_type;
221  using value_compare = typename traits_type::value_compare;
222  using key_type = typename traits_type::key_type;
223  using value_type = typename traits_type::value_type;
224  using node_type = typename traits_type::node_type;
226 
227  using iterator = skip_list_iterator<list_node_type, /*is_const=*/false>;
228  using const_iterator = skip_list_iterator<list_node_type, /*is_const=*/true>;
229  using reverse_iterator = std::reverse_iterator<iterator>;
230  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
231 
233  using const_reference = const value_type&;
234  using pointer = typename allocator_traits_type::pointer;
235  using const_pointer = typename allocator_traits_type::const_pointer;
236  using size_type = std::size_t;
237  using difference_type = std::ptrdiff_t;
238 
239  using random_level_generator_type = typename traits_type::random_level_generator_type;
240  using node_allocator_type = typename std::allocator_traits<allocator_type>::template rebind_alloc<uint8_t>;
241  using node_allocator_traits = typename std::allocator_traits<allocator_type>::template rebind_traits<uint8_t>;
242  using node_ptr = list_node_type*;
243 
244  static constexpr size_type MAX_LEVEL = traits_type::MAX_LEVEL;
245 
246  using array_type = std::array<node_ptr, MAX_LEVEL>;
247  using lock_array = std::array<typename list_node_type::lock_type, MAX_LEVEL>;
248 
249 public:
250  static bool const allow_multimapping = traits_type::allow_multimapping;
251 
255  concurrent_skip_list() : my_size(0) {
256  create_dummy_head();
257  }
258 
259  explicit concurrent_skip_list(const key_compare& comp, const allocator_type& alloc = allocator_type())
260  : my_node_allocator(alloc), my_compare(comp), my_size(0)
261  {
262  create_dummy_head();
263  }
264 
265  template<class InputIt>
266  concurrent_skip_list(InputIt first, InputIt last, const key_compare& comp = key_compare(),
267  const allocator_type& alloc = allocator_type())
268  : my_node_allocator(alloc), my_compare(comp), my_size(0)
269  {
270  create_dummy_head();
271  internal_copy(first, last);
272  }
273 
276  : my_node_allocator(node_allocator_traits::select_on_container_copy_construction(other.get_allocator())),
277  my_compare(other.my_compare), my_rnd_generator(other.my_rnd_generator), my_size(0)
278  {
279  create_dummy_head();
280  internal_copy(other);
281  __TBB_ASSERT(my_size == other.my_size, "Wrong size of copy-constructed container");
282  }
283 
285  : my_node_allocator(alloc), my_compare(other.my_compare),
286  my_rnd_generator(other.my_rnd_generator), my_size(0)
287  {
288  create_dummy_head();
289  internal_copy(other);
290  __TBB_ASSERT(my_size == other.my_size, "Wrong size of copy-constructed container");
291  }
292 
294  : my_node_allocator(std::move(other.my_node_allocator)), my_compare(other.my_compare),
295  my_rnd_generator(other.my_rnd_generator)
296  {
297  internal_move(std::move(other));
298  }
299 
301  : my_node_allocator(alloc), my_compare(other.my_compare),
302  my_rnd_generator(other.my_rnd_generator)
303  {
304  if (alloc == other.get_allocator()) {
305  internal_move(std::move(other));
306  } else {
307  my_size = 0;
308  create_dummy_head();
309  internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
310  }
311  }
312 
314  clear();
315  delete_dummy_head();
316  }
317 
319  if (this != &other) {
320  using pocca_type = typename node_allocator_traits::propagate_on_container_copy_assignment;
321  clear();
322  tbb::internal::allocator_copy_assignment(my_node_allocator, other.my_node_allocator, pocca_type());
323  my_compare = other.my_compare;
324  my_rnd_generator = other.my_rnd_generator;
325  internal_copy(other);
326  }
327  return *this;
328  }
329 
331  if (this != &other) {
332  using pocma_type = typename node_allocator_traits::propagate_on_container_move_assignment;
333  clear();
334  my_compare = other.my_compare;
335  my_rnd_generator = other.my_rnd_generator;
336  internal_move_assign(std::move(other), pocma_type());
337  }
338  return *this;
339  }
340 
341  concurrent_skip_list& operator=(std::initializer_list<value_type> il)
342  {
343  clear();
344  insert(il.begin(),il.end());
345  return *this;
346  }
347 
348  std::pair<iterator, bool> insert(const value_type& value) {
349  return internal_insert(value);
350  }
351 
352  std::pair<iterator, bool> insert(value_type&& value) {
353  return internal_insert(std::move(value));
354  }
355 
357  // Ignore hint
358  return insert(value).first;
359  }
360 
362  // Ignore hint
363  return insert(std::move(value)).first;
364  }
365 
366  template<typename InputIterator>
367  void insert(InputIterator first, InputIterator last) {
368  for (InputIterator it = first; it != last; ++it)
369  insert(*it);
370  }
371 
372  void insert(std::initializer_list<value_type> init) {
373  insert(init.begin(), init.end());
374  }
375 
376  std::pair<iterator, bool> insert(node_type&& nh) {
377  if(!nh.empty()) {
378  std::pair<iterator, bool> insert_result = internal_insert_node(nh.my_node);
379  if(insert_result.second) {
380  nh.deactivate();
381  }
382  return insert_result;
383  }
384  return std::pair<iterator, bool>(end(), false);
385  }
386 
388  // Ignore hint
389  return insert(std::move(nh)).first;
390  }
391 
392  template<typename... Args >
393  std::pair<iterator, bool> emplace(Args&&... args) {
394  return internal_insert(std::forward<Args>(args)...);
395  }
396 
397  template<typename... Args>
399  // Ignore hint
400  return emplace(std::forward<Args>(args)...).first;
401  }
402 
404  std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
405  if(extract_result.first) { // node was extracted
406  delete_node(extract_result.first);
407  return extract_result.second;
408  }
409  return end();
410  }
411 
413  while(first != last) {
414  first = unsafe_erase(get_iterator(first));
415  }
416  return get_iterator(first);
417  }
418 
420  std::pair<iterator, iterator> range = equal_range(key);
421  size_type sz = std::distance(range.first, range.second);
422  unsafe_erase(range.first, range.second);
423  return sz;
424  }
425 
427  std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
428  return extract_result.first ? node_type(extract_result.first) : node_type();
429  }
430 
432  return unsafe_extract(find(key));
433  }
434 
436  return internal_get_bound(key, my_compare);
437  }
438 
440  return internal_get_bound(key, my_compare);
441  }
442 
445  return internal_get_bound(key, my_compare);
446  }
447 
449  const_iterator lower_bound(const K& key) const {
450  return internal_get_bound(key, my_compare);
451  }
452 
454  return internal_get_bound(key, not_greater_compare(my_compare));
455  }
456 
458  return internal_get_bound(key, not_greater_compare(my_compare));
459  }
460 
463  return internal_get_bound(key, not_greater_compare(my_compare));
464  }
465 
467  const_iterator upper_bound(const K& key) const {
468  return internal_get_bound(key, not_greater_compare(my_compare));
469  }
470 
472  return internal_find(key);
473  }
474 
475  const_iterator find(const key_type& key) const {
476  return internal_find(key);
477  }
478 
480  iterator find(const K& key) {
481  return internal_find(key);
482  }
483 
485  const_iterator find(const K& key) const {
486  return internal_find(key);
487  }
488 
489  size_type count( const key_type& key ) const {
490  return internal_count(key);
491  }
492 
494  size_type count(const K& key) const {
495  return internal_count(key);
496  }
497 
498  bool contains(const key_type& key) const {
499  return find(key) != end();
500  }
501 
503  bool contains(const K& key) const {
504  return find(key) != end();
505  }
506 
507  void clear() noexcept {
508  __TBB_ASSERT(dummy_head->height() > 0, NULL);
509 
510  node_ptr current = dummy_head->next(0);
511  while (current) {
512  __TBB_ASSERT(current->height() > 0, NULL);
513  node_ptr next = current->next(0);
514  delete_node(current);
515  current = next;
516  }
517 
518  my_size = 0;
519  for (size_type i = 0; i < dummy_head->height(); ++i) {
520  dummy_head->set_next(i, nullptr);
521  }
522  }
523 
525  return iterator(dummy_head->next(0));
526  }
527 
529  return const_iterator(dummy_head->next(0));
530  }
531 
533  return const_iterator(dummy_head->next(0));
534  }
535 
537  return iterator(nullptr);
538  }
539 
540  const_iterator end() const {
541  return const_iterator(nullptr);
542  }
543 
545  return const_iterator(nullptr);
546  }
547 
548  size_type size() const {
549  return my_size.load(std::memory_order_relaxed);
550  }
551 
552  size_type max_size() const {
553  return my_node_allocator.max_size();
554  }
555 
556  bool empty() const {
557  return 0 == size();
558  }
559 
561  return my_node_allocator;
562  }
563 
564  void swap(concurrent_skip_list& other) {
565  using std::swap;
566  using pocs_type = typename node_allocator_traits::propagate_on_container_swap;
567  tbb::internal::allocator_swap(my_node_allocator, other.my_node_allocator, pocs_type());
568  swap(my_compare, other.my_compare);
569  swap(my_rnd_generator, other.my_rnd_generator);
570  swap(dummy_head, other.dummy_head);
571 
572  size_type tmp = my_size;
573  my_size.store(other.my_size);
574  other.my_size.store(tmp);
575  }
576 
577  std::pair<iterator, iterator> equal_range(const key_type& key) {
578  return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
579  }
580 
581  std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
582  return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
583  }
584 
586  std::pair<iterator, iterator> equal_range(const K& key) {
587  return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
588  }
589 
590  template<typename K, typename = typename std::enable_if<tbb::internal::has_is_transparent<key_compare>::value, K>::type>
591  std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
592  return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
593  }
594 
595  key_compare key_comp() const { return my_compare; }
596 
597  value_compare value_comp() const { return traits_type::value_comp(my_compare); }
598 
600  public:
604  private:
608 
609  public:
610 
611  bool empty() const {
612  return my_begin.my_node_ptr->next(0) == my_end.my_node_ptr;
613  }
614 
615  bool is_divisible() const {
616  return my_level != 0 ? my_begin.my_node_ptr->next(my_level - 1) != my_end.my_node_ptr : false;
617  }
618 
619  size_type size() const { return std::distance(my_begin, my_end);}
620 
622  : my_end(r.my_end) {
623  my_begin = iterator(r.my_begin.my_node_ptr->next(r.my_level - 1));
624  my_level = my_begin.my_node_ptr->height();
625  r.my_end = my_begin;
626  }
627 
629  : my_end(l.end()), my_begin(l.begin()), my_level(my_begin.my_node_ptr->height() ) {}
630 
631  iterator begin() const { return my_begin; }
632  iterator end() const { return my_end; }
633  size_t grainsize() const { return 1; }
634 
635  }; // class const_range_type
636 
637  class range_type : public const_range_type {
638  public:
640 
643 
644  iterator begin() const {
645  node_ptr node = const_range_type::begin().my_node_ptr;
646  return iterator(node);
647  }
648 
649  iterator end() const {
650  node_ptr node = const_range_type::end().my_node_ptr;
651  return iterator(node); }
652  }; // class range_type
653 
654  range_type range() { return range_type(*this); }
655  const_range_type range() const { return const_range_type(*this); }
656 
657 private:
659  dummy_head = other.dummy_head;
660  other.dummy_head = nullptr;
661  other.create_dummy_head();
662 
663  my_size = other.my_size.load();
664  other.my_size = 0;
665  }
666 
667  static const key_type& get_key(node_ptr n) {
668  __TBB_ASSERT(n, NULL);
669  return traits_type::get_key(n->value());
670  }
671 
672  template <typename K>
674  iterator it = lower_bound(key);
675  return (it == end() || my_compare(key, traits_type::get_key(*it))) ? end() : it;
676  }
677 
678  template <typename K>
679  const_iterator internal_find(const K& key) const {
680  const_iterator it = lower_bound(key);
681  return (it == end() || my_compare(key, traits_type::get_key(*it))) ? end() : it;
682  }
683 
684  template <typename K>
685  size_type internal_count( const K& key ) const {
686  if (allow_multimapping) {
687  std::pair<const_iterator, const_iterator> range = equal_range(key);
688  return std::distance(range.first, range.second);
689  }
690  return (find(key) == end()) ? size_type(0) : size_type(1);
691  }
692 
702  template <typename K, typename pointer_type, typename comparator>
703  pointer_type internal_find_position( size_type level, pointer_type& prev, const K& key,
704  const comparator& cmp) const {
705  __TBB_ASSERT(level < prev->height(), "Wrong level to find position");
706  pointer_type curr = prev->next(level);
707 
708  while (curr && cmp(get_key(curr), key)) {
709  prev = curr;
710  __TBB_ASSERT(level < prev->height(), NULL);
711  curr = prev->next(level);
712  }
713 
714  return curr;
715  }
716 
717  template <typename comparator>
718  void fill_prev_next_arrays(array_type& prev_nodes, array_type& next_nodes, node_ptr prev, const key_type& key,
719  const comparator& cmp) {
720  prev_nodes.fill(dummy_head);
721  next_nodes.fill(nullptr);
722 
723  for (size_type h = prev->height(); h > 0; --h) {
724  node_ptr next = internal_find_position(h - 1, prev, key, cmp);
725  prev_nodes[h - 1] = prev;
726  next_nodes[h - 1] = next;
727  }
728  }
729 
730  template<typename... Args>
731  std::pair<iterator, bool> internal_insert(Args&&... args) {
732  node_ptr new_node = create_node(std::forward<Args>(args)...);
733  std::pair<iterator, bool> insert_result = internal_insert_node(new_node);
734  if(!insert_result.second) {
735  delete_node(new_node);
736  }
737  return insert_result;
738  }
739 
740  std::pair<iterator, bool> internal_insert_node(node_ptr new_node) {
741  array_type prev_nodes;
742  array_type next_nodes;
743  __TBB_ASSERT(dummy_head->height() >= new_node->height(), "Wrong height for new node");
744 
745  do {
746  if (allow_multimapping) {
747  fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node),
748  not_greater_compare(my_compare));
749  } else {
750  fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node), my_compare);
751  }
752 
753  node_ptr next = next_nodes[0];
754  if (next && !allow_multimapping && !my_compare(get_key(new_node), get_key(next))) {
755  // TODO: do we really need to wait?
756  while (!next->fully_linked()) {
757  // TODO: atomic backoff
758  }
759 
760  return std::pair<iterator, bool>(iterator(next), false);
761  }
762  __TBB_ASSERT(allow_multimapping || !next || my_compare(get_key(new_node), get_key(next)),
763  "Wrong elements order");
764 
765  } while (!try_insert_node(new_node, prev_nodes, next_nodes));
766 
767  __TBB_ASSERT(new_node, NULL);
768  return std::pair<iterator, bool>(iterator(new_node), true);
769  }
770 
771  bool try_insert_node(node_ptr new_node, array_type& prev_nodes, array_type& next_nodes) {
772  __TBB_ASSERT(dummy_head->height() >= new_node->height(), NULL);
773 
774  lock_array locks;
775 
776  if (!try_lock_nodes(new_node->height(), prev_nodes, next_nodes, locks)) {
777  return false;
778  }
779 
780  __TBB_ASSERT(allow_multimapping ||
781  ((prev_nodes[0] == dummy_head ||
782  my_compare(get_key(prev_nodes[0]), get_key(new_node))) &&
783  (next_nodes[0] == nullptr || my_compare(get_key(new_node), get_key(next_nodes[0])))),
784  "Wrong elements order");
785 
786  for (size_type level = 0; level < new_node->height(); ++level) {
787  __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
788  __TBB_ASSERT(prev_nodes[level]->next(level) == next_nodes[level], NULL);
789  new_node->set_next(level, next_nodes[level]);
790  prev_nodes[level]->set_next(level, new_node);
791  }
792  new_node->mark_linked();
793 
794  ++my_size;
795 
796  return true;
797  }
798 
799  bool try_lock_nodes(size_type height, array_type& prevs, array_type& next_nodes, lock_array& locks) {
800  for (size_type l = 0; l < height; ++l) {
801  if (l == 0 || prevs[l] != prevs[l - 1])
802  locks[l] = prevs[l]->acquire();
803 
804  node_ptr next = prevs[l]->next(l);
805  if ( next != next_nodes[l]) return false;
806  }
807 
808  return true;
809  }
810 
811  template <typename K, typename comparator>
812  const_iterator internal_get_bound(const K& key, const comparator& cmp) const {
813  node_ptr prev = dummy_head;
814  __TBB_ASSERT(dummy_head->height() > 0, NULL);
815  node_ptr next = nullptr;
816 
817  for (size_type h = prev->height(); h > 0; --h) {
818  next = internal_find_position(h - 1, prev, key, cmp);
819  }
820 
821  return const_iterator(next);
822  }
823 
824  template <typename K, typename comparator>
825  iterator internal_get_bound(const K& key, const comparator& cmp){
826  node_ptr prev = dummy_head;
827  __TBB_ASSERT(dummy_head->height() > 0, NULL);
828  node_ptr next = nullptr;
829 
830  for (size_type h = prev->height(); h > 0; --h) {
831  next = internal_find_position(h - 1, prev, key, cmp);
832  }
833 
834  return iterator(next);
835  }
836 
837  // Returns node_ptr to the extracted node and node_ptr to the next node after the extracted
838  std::pair<node_ptr, node_ptr> internal_extract(const_iterator it) {
839  if ( it != end() ) {
840  key_type key = traits_type::get_key(*it);
841  node_ptr prev = dummy_head;
842  __TBB_ASSERT(dummy_head->height() > 0, NULL);
843 
844  array_type prev_nodes;
845  array_type next_nodes;
846 
847  fill_prev_next_arrays(prev_nodes, next_nodes, prev, key, my_compare);
848 
849  node_ptr erase_node = next_nodes[0];
850  node_ptr next_node = erase_node->next(0);
851 
852  if (erase_node && !my_compare(key, get_key(erase_node))) {
853  for(size_type level = 0; level < erase_node->height(); ++level) {
854  __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
855  __TBB_ASSERT(next_nodes[level] == erase_node, NULL);
856  prev_nodes[level]->set_next(level, erase_node->next(level));
857  }
858  --my_size;
859  return std::pair<node_ptr, node_ptr>(erase_node, next_node);
860  }
861  }
862  return std::pair<node_ptr, node_ptr>(nullptr, nullptr);
863  }
864 
865 protected:
866  template<typename SourceType>
867  void internal_merge(SourceType&& source) {
868  using source_type = typename std::decay<SourceType>::type;
869  using source_iterator = typename source_type::iterator;
870  __TBB_STATIC_ASSERT((std::is_same<node_type, typename source_type::node_type>::value), "Incompatible containers cannot be merged");
871 
872  for(source_iterator it = source.begin(); it != source.end();) {
873  source_iterator where = it++;
874  if (allow_multimapping || !contains(traits_type::get_key(*where))) {
875  std::pair<node_ptr, node_ptr> extract_result = source.internal_extract(where);
876 
877  //If the insertion fails - return the node into source
878  node_type handle(extract_result.first);
879  __TBB_ASSERT(!handle.empty(), "Extracted handle in merge is empty");
880 
881  if (!insert(std::move(handle)).second) {
882  source.insert(std::move(handle));
883  }
884  handle.deactivate();
885  }
886  }
887  }
888 
889 private:
890  void internal_copy(const concurrent_skip_list& other) {
891  internal_copy(other.begin(), other.end());
892  }
893 
894  template<typename Iterator>
895  void internal_copy(Iterator first, Iterator last) {
896  clear();
897  try {
898  for (auto it = first; it != last; ++it)
899  insert(*it);
900  }
901  catch (...) {
902  clear();
903  delete_dummy_head();
904  throw;
905  }
906  }
907 
910  return my_rnd_generator();
911  }
912 
914  return sizeof(list_node_type) + height*sizeof(typename list_node_type::atomic_node_pointer);
915  }
916 
918  template <typename... Args>
919  node_ptr create_node(Args&&... args) {
920  size_type levels = random_level();
921 
922  size_type sz = calc_node_size(levels);
923 
924  node_ptr node = reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
925 
926  try {
927  node_allocator_traits::construct(my_node_allocator, node, levels);
928 
929  }
930  catch(...) {
931  deallocate_node(node, sz);
932  throw;
933  }
934 
935  try {
936  node_allocator_traits::construct(my_node_allocator, node->storage(), std::forward<Args>(args)...);
937  }
938  catch (...) {
939  node_allocator_traits::destroy(my_node_allocator, node);
940  deallocate_node(node, sz);
941  throw;
942  }
943 
944  return node;
945  }
946 
948  size_type sz = calc_node_size(MAX_LEVEL);
949 
950  dummy_head = reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
951  // TODO: investigate linkage fail in debug without this workaround
952  auto max_level = MAX_LEVEL;
953 
954  try {
955  node_allocator_traits::construct(my_node_allocator, dummy_head, max_level);
956  }
957  catch(...) {
958  deallocate_node(dummy_head, sz);
959  throw;
960  }
961  }
962 
963  template <bool is_dummy = false>
964  void delete_node(node_ptr node) {
965  size_type sz = calc_node_size(node->height());
966  // Destroy value
967  if (!is_dummy) node_allocator_traits::destroy(my_node_allocator, node->storage());
968  // Destroy node
969  node_allocator_traits::destroy(my_node_allocator, node);
970  // Deallocate memory
971  deallocate_node(node, sz);
972  }
973 
975  node_allocator_traits::deallocate(my_node_allocator, reinterpret_cast<uint8_t*>(node), sz);
976  }
977 
979  delete_node<true>(dummy_head);
980  }
981 
983  return iterator(it.my_node_ptr);
984  }
985 
987  delete_dummy_head();
988  tbb::internal::allocator_move_assignment(my_node_allocator, other.my_node_allocator, std::true_type());
989  internal_move(std::move(other));
990  }
991 
993  if (my_node_allocator == other.my_node_allocator) {
994  delete_dummy_head();
995  internal_move(std::move(other));
996  } else {
997  internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
998  }
999  }
1000 
1003 
1004  not_greater_compare(const key_compare& less_compare) : my_less_compare(less_compare) {}
1005 
1006  template <typename K1, typename K2>
1007  bool operator()(const K1& first, const K2& second) const {
1008  return !my_less_compare(second, first);
1009  }
1010  };
1011 
1016 
1017  template<typename OtherTraits>
1018  friend class concurrent_skip_list;
1019 
1020  std::atomic<size_type> my_size;
1021 }; // class concurrent_skip_list
1022 
1023 template <size_t MAX_LEVEL>
1025 public:
1026  static constexpr size_t max_level = MAX_LEVEL;
1027 
1028  concurrent_geometric_level_generator() : engines(time(NULL)) {}
1029 
1030  size_t operator()() {
1031  return (distribution(engines.local()) % MAX_LEVEL) + 1;
1032  }
1033 
1034 private:
1036  std::geometric_distribution<size_t> distribution;
1037 };
1038 
1039 } // namespace internal
1040 } // namespace interface10
1041 } // namespace tbb
1042 
1043 #endif // __TBB_concurrent_skip_list_H
pointer_type internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
iterator unsafe_erase(const_iterator first, const_iterator last)
const_iterator lower_bound(const key_type &key) const
typename std::aligned_storage< sizeof(value_type), alignof(value_type)>::type aligned_storage_type
iterator internal_get_bound(const K &key, const comparator &cmp)
const atomic_node_pointer & my_next(size_type level) const
skip_list_iterator< list_node_type, false > iterator
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
typename allocator_traits_type::const_pointer const_pointer
auto last(Container &c) -> decltype(begin(c))
bool_constant< false > false_type
Definition: tbb_stddef.h:469
void internal_copy(const concurrent_skip_list &other)
typename std::conditional< is_const, typename node_type::const_pointer, typename node_type::pointer >::type pointer
skip_list_node & operator=(const skip_list_node &)=delete
void insert(InputIterator first, InputIterator last)
std::pair< iterator, iterator > equal_range(const K &key)
concurrent_skip_list & operator=(concurrent_skip_list &&other)
void set_next(size_type level, node_pointer next)
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
std::pair< node_ptr, node_ptr > internal_extract(const_iterator it)
concurrent_skip_list & operator=(std::initializer_list< value_type > il)
auto first(Container &c) -> decltype(begin(c))
The graph class.
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
#define __TBB_STATIC_ASSERT(condition, msg)
Definition: tbb_stddef.h:532
bool try_lock_nodes(size_type height, array_type &prevs, array_type &next_nodes, lock_array &locks)
std::pair< iterator, iterator > equal_range(const key_type &key)
typename std::conditional< is_const, typename node_type::const_reference, typename node_type::reference >::type reference
std::pair< iterator, bool > insert(value_type &&value)
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
const_iterator find(const key_type &key) const
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
std::array< typename list_node_type::lock_type, MAX_LEVEL > lock_array
typename std::allocator_traits< allocator_type >::template rebind_traits< uint8_t > node_allocator_traits
atomic_node_pointer & my_next(size_type level)
Dummy type that distinguishes splitting constructor from copy constructor.
Definition: tbb_stddef.h:395
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
std::pair< iterator, bool > insert(const value_type &value)
const_iterator internal_get_bound(const K &key, const comparator &cmp) const
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
concurrent_skip_list & operator=(const concurrent_skip_list &other)
const_iterator upper_bound(const key_type &key) const
void internal_move_assign(concurrent_skip_list &&other, std::false_type)
skip_list_iterator(const skip_list_iterator< node_type, true > &other)
iterator insert(const_iterator, value_type &&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 ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle * key
concurrent_skip_list(InputIt first, InputIt last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
iterator insert(const_iterator, const_reference value)
bool operator!=(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)
void insert(std::initializer_list< value_type > init)
skip_list_iterator(const skip_list_iterator< node_type, false > &other)
STL namespace.
std::pair< iterator, bool > insert(node_type &&nh)
std::allocator_traits< allocator_type > allocator_traits_type
The enumerable_thread_specific container.
typename traits_type::random_level_generator_type random_level_generator_type
iterator emplace_hint(const_iterator, Args &&... args)
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
std::pair< iterator, bool > internal_insert(Args &&... args)
Base class for types that should not be assigned.
Definition: tbb_stddef.h:320
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 begin
skip_list_iterator< list_node_type, true > const_iterator
void fill_prev_next_arrays(array_type &prev_nodes, array_type &next_nodes, node_ptr prev, const key_type &key, const comparator &cmp)
std::reverse_iterator< const_iterator > const_reverse_iterator
bool try_insert_node(node_ptr new_node, array_type &prev_nodes, array_type &next_nodes)
iterator insert(const_iterator, node_type &&nh)
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 end
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
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_id __itt_string_handle __itt_metadata_type type
std::pair< iterator, bool > emplace(Args &&... args)
std::pair< iterator, bool > internal_insert_node(node_ptr new_node)
typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t > node_allocator_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 size
void internal_move_assign(concurrent_skip_list &&other, std::true_type)
void swap(atomic< T > &lhs, atomic< T > &rhs)
Definition: atomic.h:535
bool_constant< true > true_type
Definition: tbb_stddef.h:468
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
bool operator==(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)

Copyright © 2005-2019 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.