Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
Loading...
Searching...
No Matches
_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
51namespace tbb {
52namespace interface10 {
53namespace internal {
54
55template <typename Value, typename Mutex>
57
58public:
59 using value_type = Value;
60 using size_type = std::size_t;
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
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
83
85
87
89 return reinterpret_cast<pointer>(&my_val);
90 }
91
93 return *storage();
94 }
95
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
109 return my_height;
110 }
111
112 bool fully_linked() const {
113 return my_fullyLinked.load(std::memory_order_acquire);
114 }
115
116 void mark_linked() {
117 my_fullyLinked.store(true, std::memory_order_release);
118 }
119
121 return lock_type(my_mutex);
122 }
123
124private:
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
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
143template <typename NodeType, bool is_const>
145 using node_type = NodeType;
147public:
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
171 template <typename T = void, typename = typename std::enable_if<is_const, T>::type>
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
189private:
191
193
194 template <typename Traits>
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
209template <typename NodeType, bool is_const1, bool is_const2>
211 return lhs.my_node_ptr == rhs.my_node_ptr;
212}
213
214template <typename NodeType, bool is_const1, bool is_const2>
216 return lhs.my_node_ptr != rhs.my_node_ptr;
217}
218
219template <typename Traits>
221protected:
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>;
234 using reverse_iterator = std::reverse_iterator<iterator>;
235 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
236
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
254public:
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) {
358 return internal_insert(std::move(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> >
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> >
488 }
489
491 return internal_find(key);
492 }
493
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
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
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
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) {
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
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
676private:
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>
694 return (it == end() || my_compare(key, traits_type::get_key(*it))) ? end() : it;
695 }
696
697 template <typename K>
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
907protected:
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
931private:
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>
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
1028 void internal_move_assign(concurrent_skip_list&& other, /*POCMA=*/std::true_type) {
1030 tbb::internal::allocator_move_assignment(my_node_allocator, other.my_node_allocator, std::true_type());
1031 internal_move(std::move(other));
1032 }
1033
1034 void internal_move_assign(concurrent_skip_list&& other, /*POCMA=*/std::false_type) {
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>
1061
1062 std::atomic<size_type> my_size;
1063}; // class concurrent_skip_list
1064
1065template <size_t MAX_LEVEL>
1067public:
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
1076private:
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
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition tbb_stddef.h:165
#define __TBB_STATIC_ASSERT(condition, msg)
Definition tbb_stddef.h:553
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
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
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
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
STL namespace.
The graph class.
bool operator==(const cache_aligned_allocator< T > &, const cache_aligned_allocator< U > &)
void move(tbb_thread &t1, tbb_thread &t2)
Definition tbb_thread.h:319
bool operator!=(const cache_aligned_allocator< T > &, const cache_aligned_allocator< U > &)
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
auto last(Container &c) -> decltype(begin(c))
auto first(Container &c) -> decltype(begin(c))
The enumerable_thread_specific container.
void set_next(size_type level, node_pointer next)
skip_list_node(skip_list_node &&)=delete
typename std::aligned_storage< sizeof(value_type), alignof(value_type)>::type aligned_storage_type
const atomic_node_pointer & my_next(size_type level) const
skip_list_node(const skip_list_node &)=delete
skip_list_node & operator=(const skip_list_node &)=delete
atomic_node_pointer & my_next(size_type level)
friend bool operator!=(const skip_list_iterator< T, M > &, const skip_list_iterator< T, U > &)
skip_list_iterator(const skip_list_iterator< node_type, false > &other)
skip_list_iterator(const skip_list_iterator< node_type, true > &other)
skip_list_iterator & operator=(const skip_list_iterator< node_type, false > &other)
friend bool operator==(const skip_list_iterator< T, M > &, const skip_list_iterator< T, U > &)
typename std::conditional< is_const, typename node_type::const_reference, typename node_type::reference >::type reference
typename std::conditional< is_const, typename node_type::const_pointer, typename node_type::pointer >::type pointer
void insert(InputIterator first, InputIterator last)
typename traits_type::random_level_generator_type random_level_generator_type
concurrent_skip_list & operator=(concurrent_skip_list &&other)
iterator insert(const_iterator, value_type &&value)
concurrent_skip_list & operator=(std::initializer_list< value_type > il)
void internal_move_assign(concurrent_skip_list &&other, std::true_type)
std::pair< iterator, iterator > equal_range(const key_type &key)
const_iterator internal_get_bound(const K &key, const comparator &cmp) const
bool try_insert_node(node_ptr new_node, array_type &prev_nodes, array_type &next_nodes)
iterator insert(const_iterator, const_reference value)
iterator emplace_hint(const_iterator, Args &&... args)
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
std::pair< iterator, bool > internal_insert_node(node_ptr new_node)
typename std::allocator_traits< allocator_type >::template rebind_traits< uint8_t > node_allocator_traits
bool try_lock_nodes(size_type height, array_type &prevs, array_type &next_nodes, lock_array &locks)
iterator unsafe_erase(const_iterator first, const_iterator last)
std::pair< iterator, bool > insert(node_type &&nh)
std::array< typename list_node_type::lock_type, MAX_LEVEL > lock_array
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
skip_list_iterator< list_node_type, false > iterator
std::reverse_iterator< const_iterator > const_reverse_iterator
typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t > node_allocator_type
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
skip_list_iterator< list_node_type, true > const_iterator
iterator internal_get_bound(const K &key, const comparator &cmp)
void insert(std::initializer_list< value_type > init)
concurrent_skip_list(InputIt first, InputIt last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
void internal_copy(const concurrent_skip_list &other)
const_iterator upper_bound(const key_type &key) const
std::allocator_traits< allocator_type > allocator_traits_type
pointer_type internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
std::pair< iterator, iterator > equal_range(const K &key)
std::pair< iterator, bool > emplace(Args &&... args)
std::pair< iterator, bool > insert(const value_type &value)
concurrent_skip_list & operator=(const concurrent_skip_list &other)
void fill_prev_next_arrays(array_type &prev_nodes, array_type &next_nodes, node_ptr prev, const key_type &key, const comparator &cmp)
skip_list_node< value_type, typename traits_type::mutex_type > list_node_type
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
std::pair< iterator, bool > internal_insert(Args &&... args)
std::pair< iterator, bool > insert(value_type &&value)
void fill_prev_next_by_ptr(array_type &prev_nodes, array_type &next_nodes, const_iterator it, const key_type &key, const comparator &cmp)
const_iterator lower_bound(const key_type &key) const
std::pair< node_ptr, node_ptr > internal_extract(const_iterator it)
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
typename allocator_traits_type::const_pointer const_pointer
void internal_move_assign(concurrent_skip_list &&other, std::false_type)
Base class for types that should not be assigned.
Definition tbb_stddef.h:322
Dummy type that distinguishes splitting constructor from copy constructor.
Definition tbb_stddef.h:416

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.