1/* Fast open-addressing concurrent hash table.
2 *
3 * Copyright 2023-2024 Joaquin M Lopez Munoz.
4 * Copyright 2024 Braden Ganetsky.
5 * Distributed under the Boost Software License, Version 1.0.
6 * (See accompanying file LICENSE_1_0.txt or copy at
7 * http://www.boost.org/LICENSE_1_0.txt)
8 *
9 * See https://www.boost.org/libs/unordered for library home page.
10 */
11
12#ifndef BOOST_UNORDERED_DETAIL_FOA_CONCURRENT_TABLE_HPP
13#define BOOST_UNORDERED_DETAIL_FOA_CONCURRENT_TABLE_HPP
14
15#include <atomic>
16#include <boost/assert.hpp>
17#include <boost/config.hpp>
18#include <boost/core/ignore_unused.hpp>
19#include <boost/core/no_exceptions_support.hpp>
20#include <boost/core/serialization.hpp>
21#include <boost/cstdint.hpp>
22#include <boost/mp11/tuple.hpp>
23#include <boost/throw_exception.hpp>
24#include <boost/unordered/detail/archive_constructed.hpp>
25#include <boost/unordered/detail/bad_archive_exception.hpp>
26#include <boost/unordered/detail/foa/core.hpp>
27#include <boost/unordered/detail/foa/reentrancy_check.hpp>
28#include <boost/unordered/detail/foa/rw_spinlock.hpp>
29#include <boost/unordered/detail/foa/tuple_rotate_right.hpp>
30#include <boost/unordered/detail/serialization_version.hpp>
31#include <boost/unordered/detail/static_assert.hpp>
32#include <boost/unordered/detail/type_traits.hpp>
33#include <cstddef>
34#include <functional>
35#include <initializer_list>
36#include <iterator>
37#include <memory>
38#include <new>
39#include <type_traits>
40#include <tuple>
41#include <utility>
42
43#if !defined(BOOST_UNORDERED_DISABLE_PARALLEL_ALGORITHMS)
44#if defined(BOOST_UNORDERED_ENABLE_PARALLEL_ALGORITHMS)|| \
45 !defined(BOOST_NO_CXX17_HDR_EXECUTION)
46#define BOOST_UNORDERED_PARALLEL_ALGORITHMS
47#endif
48#endif
49
50#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
51#include <algorithm>
52#include <execution>
53#endif
54
55namespace boost{
56namespace unordered{
57namespace detail{
58
59#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
60
61template<typename ExecutionPolicy>
62using is_execution_policy=std::is_execution_policy<
63 typename std::remove_cv<
64 typename std::remove_reference<ExecutionPolicy>::type
65 >::type
66>;
67
68#else
69
70template<typename ExecutionPolicy>
71using is_execution_policy=std::false_type;
72
73#endif
74
75namespace foa{
76
77static constexpr std::size_t cacheline_size=64;
78
79template<typename T,std::size_t N>
80class cache_aligned_array
81{
82public:
83 cache_aligned_array(){for(std::size_t n=0;n<N;)::new (data(pos: n++)) T();}
84 ~cache_aligned_array(){for(auto n=N;n>0;)data(pos: n--)->~T();}
85 cache_aligned_array(const cache_aligned_array&)=delete;
86 cache_aligned_array& operator=(const cache_aligned_array&)=delete;
87
88 T& operator[](std::size_t pos)noexcept{return *data(pos);}
89
90private:
91 static constexpr std::size_t element_offset=
92 (sizeof(T)+cacheline_size-1)/cacheline_size*cacheline_size;
93
94 BOOST_UNORDERED_STATIC_ASSERT(alignof(T)<=cacheline_size);
95
96 T* data(std::size_t pos)noexcept
97 {
98 return reinterpret_cast<T*>(
99 (reinterpret_cast<uintptr_t>(&buf)+cacheline_size-1)/
100 cacheline_size*cacheline_size
101 +pos*element_offset);
102 }
103
104 unsigned char buf[element_offset*N+cacheline_size-1];
105};
106
107template<typename Mutex,std::size_t N>
108class multimutex
109{
110public:
111 constexpr std::size_t size()const noexcept{return N;}
112
113 Mutex& operator[](std::size_t pos)noexcept
114 {
115 BOOST_ASSERT(pos<N);
116 return mutexes[pos];
117 }
118
119 void lock()noexcept{for(std::size_t n=0;n<N;)mutexes[n++].lock();}
120 void unlock()noexcept{for(auto n=N;n>0;)mutexes[--n].unlock();}
121
122private:
123 cache_aligned_array<Mutex,N> mutexes;
124};
125
126/* std::shared_lock is C++14 */
127
128template<typename Mutex>
129class shared_lock
130{
131public:
132 shared_lock(Mutex& m_)noexcept:m(m_){m.lock_shared();}
133 ~shared_lock()noexcept{if(owns)m.unlock_shared();}
134
135 /* not used but VS in pre-C++17 mode needs to see it for RVO */
136 shared_lock(const shared_lock&);
137
138 void lock(){BOOST_ASSERT(!owns);m.lock_shared();owns=true;}
139 void unlock(){BOOST_ASSERT(owns);m.unlock_shared();owns=false;}
140
141private:
142 Mutex &m;
143 bool owns=true;
144};
145
146/* VS in pre-C++17 mode can't implement RVO for std::lock_guard due to
147 * its copy constructor being deleted.
148 */
149
150template<typename Mutex>
151class lock_guard
152{
153public:
154 lock_guard(Mutex& m_)noexcept:m(m_){m.lock();}
155 ~lock_guard()noexcept{m.unlock();}
156
157 /* not used but VS in pre-C++17 mode needs to see it for RVO */
158 lock_guard(const lock_guard&);
159
160private:
161 Mutex &m;
162};
163
164/* inspired by boost/multi_index/detail/scoped_bilock.hpp */
165
166template<typename Mutex>
167class scoped_bilock
168{
169public:
170 scoped_bilock(Mutex& m1,Mutex& m2)noexcept
171 {
172 bool mutex_lt=std::less<Mutex*>{}(&m1,&m2);
173
174 pm1=mutex_lt?&m1:&m2;
175 pm1->lock();
176 if(&m1==&m2){
177 pm2=nullptr;
178 }
179 else{
180 pm2=mutex_lt?&m2:&m1;
181 pm2->lock();
182 }
183 }
184
185 /* not used but VS in pre-C++17 mode needs to see it for RVO */
186 scoped_bilock(const scoped_bilock&);
187
188 ~scoped_bilock()noexcept
189 {
190 if(pm2)pm2->unlock();
191 pm1->unlock();
192 }
193
194private:
195 Mutex *pm1,*pm2;
196};
197
198/* use atomics for group metadata storage */
199
200template<typename Integral>
201struct atomic_integral
202{
203 operator Integral()const{return n.load(std::memory_order_relaxed);}
204 void operator=(Integral m){n.store(m,std::memory_order_relaxed);}
205 void operator|=(Integral m){n.fetch_or(m,std::memory_order_relaxed);}
206 void operator&=(Integral m){n.fetch_and(m,std::memory_order_relaxed);}
207
208 atomic_integral& operator=(atomic_integral const& rhs) {
209 n.store(rhs.n.load(std::memory_order_relaxed),std::memory_order_relaxed);
210 return *this;
211 }
212
213 std::atomic<Integral> n;
214};
215
216/* Group-level concurrency protection. It provides a rw mutex plus an
217 * atomic insertion counter for optimistic insertion (see
218 * unprotected_norehash_emplace_or_visit).
219 */
220
221struct group_access
222{
223 using mutex_type=rw_spinlock;
224 using shared_lock_guard=shared_lock<mutex_type>;
225 using exclusive_lock_guard=lock_guard<mutex_type>;
226 using insert_counter_type=std::atomic<boost::uint32_t>;
227
228 shared_lock_guard shared_access(){return shared_lock_guard{m};}
229 exclusive_lock_guard exclusive_access(){return exclusive_lock_guard{m};}
230 insert_counter_type& insert_counter(){return cnt;}
231
232private:
233 mutex_type m;
234 insert_counter_type cnt{0};
235};
236
237template<std::size_t Size>
238group_access* dummy_group_accesses()
239{
240 /* Default group_access array to provide to empty containers without
241 * incurring dynamic allocation. Mutexes won't actually ever be used,
242 * (no successful reduced hash match) and insertion counters won't ever
243 * be incremented (insertions won't succeed as capacity()==0).
244 */
245
246 static group_access accesses[Size];
247
248 return accesses;
249}
250
251/* subclasses table_arrays to add an additional group_access array */
252
253template<typename Value,typename Group,typename SizePolicy,typename Allocator>
254struct concurrent_table_arrays:table_arrays<Value,Group,SizePolicy,Allocator>
255{
256 using group_access_allocator_type=
257 typename boost::allocator_rebind<Allocator,group_access>::type;
258 using group_access_pointer=
259 typename boost::allocator_pointer<group_access_allocator_type>::type;
260
261 using super=table_arrays<Value,Group,SizePolicy,Allocator>;
262 using allocator_type=typename super::allocator_type;
263
264 concurrent_table_arrays(const super& arrays,group_access_pointer pga):
265 super{arrays},group_accesses_{pga}{}
266
267 group_access* group_accesses()const noexcept{
268 return boost::to_address(group_accesses_);
269 }
270
271 static concurrent_table_arrays new_(allocator_type al,std::size_t n)
272 {
273 super x{super::new_(al,n)};
274 BOOST_TRY{
275 return new_group_access(al: group_access_allocator_type(al),x);
276 }
277 BOOST_CATCH(...){
278 super::delete_(al,x);
279 BOOST_RETHROW
280 }
281 BOOST_CATCH_END
282 }
283
284 static void set_group_access(
285 group_access_allocator_type al,concurrent_table_arrays& arrays)
286 {
287 set_group_access(
288 al,arrays,std::is_same<group_access*,group_access_pointer>{});
289 }
290
291 static void set_group_access(
292 group_access_allocator_type al,
293 concurrent_table_arrays& arrays,
294 std::false_type /* fancy pointers */)
295 {
296 arrays.group_accesses_=
297 boost::allocator_allocate(al,arrays.groups_size_mask+1);
298
299 for(std::size_t i=0;i<arrays.groups_size_mask+1;++i){
300 ::new (arrays.group_accesses()+i) group_access();
301 }
302 }
303
304 static void set_group_access(
305 group_access_allocator_type al,
306 concurrent_table_arrays& arrays,
307 std::true_type /* optimize when elements() is null */)
308 {
309 if(!arrays.elements()){
310 arrays.group_accesses_=
311 dummy_group_accesses<SizePolicy::min_size()>();
312 } else {
313 set_group_access(al,arrays,std::false_type{});
314 }
315 }
316
317 static concurrent_table_arrays new_group_access(
318 group_access_allocator_type al,const super& x)
319 {
320 concurrent_table_arrays arrays{x,nullptr};
321 set_group_access(al,arrays);
322 return arrays;
323 }
324
325 static void delete_(allocator_type al,concurrent_table_arrays& arrays)noexcept
326 {
327 delete_group_access(al: group_access_allocator_type(al),arrays);
328 super::delete_(al,arrays);
329 }
330
331 static void delete_group_access(
332 group_access_allocator_type al,concurrent_table_arrays& arrays)noexcept
333 {
334 if(arrays.elements()){
335 boost::allocator_deallocate(
336 al,arrays.group_accesses_,arrays.groups_size_mask+1);
337 }
338 }
339
340 group_access_pointer group_accesses_;
341};
342
343struct atomic_size_control
344{
345 static constexpr auto atomic_size_t_size=sizeof(std::atomic<std::size_t>);
346 BOOST_UNORDERED_STATIC_ASSERT(atomic_size_t_size<cacheline_size);
347
348 atomic_size_control(std::size_t ml_,std::size_t size_):
349 pad0_{},ml{ml_},pad1_{},size{size_}{}
350 atomic_size_control(const atomic_size_control& x):
351 pad0_{},ml{x.ml.load()},pad1_{},size{x.size.load()}{}
352
353 /* padding to avoid false sharing internally and with sorrounding data */
354
355 unsigned char pad0_[cacheline_size-atomic_size_t_size];
356 std::atomic<std::size_t> ml;
357 unsigned char pad1_[cacheline_size-atomic_size_t_size];
358 std::atomic<std::size_t> size;
359};
360
361/* std::swap can't be used on non-assignable atomics */
362
363inline void
364swap_atomic_size_t(std::atomic<std::size_t>& x,std::atomic<std::size_t>& y)
365{
366 std::size_t tmp=x;
367 x=static_cast<std::size_t>(y);
368 y=tmp;
369}
370
371inline void swap(atomic_size_control& x,atomic_size_control& y)
372{
373 swap_atomic_size_t(x&: x.ml,y&: y.ml);
374 swap_atomic_size_t(x&: x.size,y&: y.size);
375}
376
377/* foa::concurrent_table serves as the foundation for end-user concurrent
378 * hash containers.
379 *
380 * The exposed interface (completed by the wrapping containers) is not that
381 * of a regular container (in fact, it does not model Container as understood
382 * by the C++ standard):
383 *
384 * - Iterators are not provided as they are not suitable for concurrent
385 * scenarios.
386 * - As a consequence, composite operations with regular containers
387 * (like, for instance, looking up an element and modifying it), must
388 * be provided natively without any intervening iterator/accesor.
389 * Visitation is a core concept in this design, either on its own (eg.
390 * visit(k) locates the element with key k *and* accesses it) or as part
391 * of a native composite operation (eg. try_emplace_or_visit). Visitation
392 * is constant or mutating depending on whether the used table function is
393 * const or not.
394 * - The API provides member functions for all the meaningful composite
395 * operations of the form "X (and|or) Y", where X, Y are one of the
396 * primitives FIND, ACCESS, INSERT or ERASE.
397 * - Parallel versions of [c]visit_all(f) and erase_if(f) are provided based
398 * on C++17 stdlib parallel algorithms.
399 *
400 * Consult boost::concurrent_flat_(map|set) docs for the full API reference.
401 * Heterogeneous lookup is suported by default, that is, without checking for
402 * any ::is_transparent typedefs --this checking is done by the wrapping
403 * containers.
404 *
405 * Thread-safe concurrency is implemented using a two-level lock system:
406 *
407 * - A first container-level lock is implemented with an array of
408 * rw spinlocks acting as a single rw mutex with very little
409 * cache-coherence traffic on read (each thread is assigned a different
410 * spinlock in the array). Container-level write locking is only used for
411 * rehashing and other container-wide operations (assignment, swap, etc.)
412 * - Each group of slots has an associated rw spinlock. A thread holds
413 * at most one group lock at any given time. Lookup is implemented in
414 * a (groupwise) lock-free manner until a reduced hash match is found, in
415 * which case the relevant group is locked and the slot is double-checked
416 * for occupancy and compared with the key.
417 * - Each group has also an associated so-called insertion counter used for
418 * the following optimistic insertion algorithm:
419 * - The value of the insertion counter for the initial group in the probe
420 * sequence is locally recorded (let's call this value c0).
421 * - Lookup is as described above. If lookup finds no equivalent element,
422 * search for an available slot for insertion successively locks/unlocks
423 * each group in the probing sequence.
424 * - When an available slot is located, it is preemptively occupied (its
425 * reduced hash value is set) and the insertion counter is atomically
426 * incremented: if no other thread has incremented the counter during the
427 * whole operation (which is checked by comparing with c0), then we're
428 * good to go and complete the insertion, otherwise we roll back and
429 * start over.
430 */
431
432template<typename,typename,typename,typename>
433class table; /* concurrent/non-concurrent interop */
434
435template <typename TypePolicy,typename Hash,typename Pred,typename Allocator>
436using concurrent_table_core_impl=table_core<
437 TypePolicy,group15<atomic_integral>,concurrent_table_arrays,
438 atomic_size_control,Hash,Pred,Allocator>;
439
440#include <boost/unordered/detail/foa/ignore_wshadow.hpp>
441
442#if defined(BOOST_MSVC)
443#pragma warning(push)
444#pragma warning(disable:4714) /* marked as __forceinline not inlined */
445#endif
446
447template<typename TypePolicy,typename Hash,typename Pred,typename Allocator>
448class concurrent_table:
449 concurrent_table_core_impl<TypePolicy,Hash,Pred,Allocator>
450{
451 using super=concurrent_table_core_impl<TypePolicy,Hash,Pred,Allocator>;
452 using type_policy=typename super::type_policy;
453 using group_type=typename super::group_type;
454 using super::N;
455 using prober=typename super::prober;
456 using arrays_type=typename super::arrays_type;
457 using size_ctrl_type=typename super::size_ctrl_type;
458 using compatible_nonconcurrent_table=table<TypePolicy,Hash,Pred,Allocator>;
459 friend compatible_nonconcurrent_table;
460
461public:
462 using key_type=typename super::key_type;
463 using init_type=typename super::init_type;
464 using value_type=typename super::value_type;
465 using element_type=typename super::element_type;
466 using hasher=typename super::hasher;
467 using key_equal=typename super::key_equal;
468 using allocator_type=typename super::allocator_type;
469 using size_type=typename super::size_type;
470 static constexpr std::size_t bulk_visit_size=16;
471
472private:
473 template<typename Value,typename T>
474 using enable_if_is_value_type=typename std::enable_if<
475 !std::is_same<init_type,value_type>::value&&
476 std::is_same<Value,value_type>::value,
477 T
478 >::type;
479
480public:
481 concurrent_table(
482 std::size_t n=default_bucket_count,const Hash& h_=Hash(),
483 const Pred& pred_=Pred(),const Allocator& al_=Allocator()):
484 super{n,h_,pred_,al_}
485 {}
486
487 concurrent_table(const concurrent_table& x):
488 concurrent_table(x,x.exclusive_access()){}
489 concurrent_table(concurrent_table&& x):
490 concurrent_table(std::move(x),x.exclusive_access()){}
491 concurrent_table(const concurrent_table& x,const Allocator& al_):
492 concurrent_table(x,al_,x.exclusive_access()){}
493 concurrent_table(concurrent_table&& x,const Allocator& al_):
494 concurrent_table(std::move(x),al_,x.exclusive_access()){}
495
496 template<typename ArraysType>
497 concurrent_table(
498 compatible_nonconcurrent_table&& x,
499 arrays_holder<ArraysType,Allocator>&& ah):
500 super{
501 std::move(x.h()),std::move(x.pred()),std::move(x.al()),
502 [&x]{return arrays_type::new_group_access(
503 x.al(),typename arrays_type::super{
504 x.arrays.groups_size_index,x.arrays.groups_size_mask,
505 to_pointer<typename arrays_type::group_type_pointer>(
506 reinterpret_cast<group_type*>(x.arrays.groups())),
507 x.arrays.elements_});},
508 size_ctrl_type{x.size_ctrl.ml,x.size_ctrl.size}}
509 {
510 x.arrays=ah.release();
511 x.size_ctrl.ml=x.initial_max_load();
512 x.size_ctrl.size=0;
513 }
514
515 concurrent_table(compatible_nonconcurrent_table&& x):
516 concurrent_table(std::move(x),x.make_empty_arrays())
517 {}
518
519 ~concurrent_table()=default;
520
521 concurrent_table& operator=(const concurrent_table& x)
522 {
523 auto lck=exclusive_access(*this,x);
524 super::operator=(x);
525 return *this;
526 }
527
528 concurrent_table& operator=(concurrent_table&& x)noexcept(
529 noexcept(std::declval<super&>() = std::declval<super&&>()))
530 {
531 auto lck=exclusive_access(*this,x);
532 super::operator=(std::move(x));
533 return *this;
534 }
535
536 concurrent_table& operator=(std::initializer_list<value_type> il) {
537 auto lck=exclusive_access();
538 super::clear();
539 super::noshrink_reserve(il.size());
540 for (auto const& v : il) {
541 this->unprotected_emplace(v);
542 }
543 return *this;
544 }
545
546 allocator_type get_allocator()const noexcept
547 {
548 auto lck=shared_access();
549 return super::get_allocator();
550 }
551
552 template<typename Key,typename F>
553 BOOST_FORCEINLINE std::size_t visit(const Key& x,F&& f)
554 {
555 return visit_impl(group_exclusive{},x,std::forward<F>(f));
556 }
557
558 template<typename Key,typename F>
559 BOOST_FORCEINLINE std::size_t visit(const Key& x,F&& f)const
560 {
561 return visit_impl(group_shared{},x,std::forward<F>(f));
562 }
563
564 template<typename Key,typename F>
565 BOOST_FORCEINLINE std::size_t cvisit(const Key& x,F&& f)const
566 {
567 return visit(x,std::forward<F>(f));
568 }
569
570 template<typename FwdIterator,typename F>
571 BOOST_FORCEINLINE
572 std::size_t visit(FwdIterator first,FwdIterator last,F&& f)
573 {
574 return bulk_visit_impl(group_exclusive{},first,last,std::forward<F>(f));
575 }
576
577 template<typename FwdIterator,typename F>
578 BOOST_FORCEINLINE
579 std::size_t visit(FwdIterator first,FwdIterator last,F&& f)const
580 {
581 return bulk_visit_impl(group_shared{},first,last,std::forward<F>(f));
582 }
583
584 template<typename FwdIterator,typename F>
585 BOOST_FORCEINLINE
586 std::size_t cvisit(FwdIterator first,FwdIterator last,F&& f)const
587 {
588 return visit(first,last,std::forward<F>(f));
589 }
590
591 template<typename F> std::size_t visit_all(F&& f)
592 {
593 return visit_all_impl(group_exclusive{},std::forward<F>(f));
594 }
595
596 template<typename F> std::size_t visit_all(F&& f)const
597 {
598 return visit_all_impl(group_shared{},std::forward<F>(f));
599 }
600
601 template<typename F> std::size_t cvisit_all(F&& f)const
602 {
603 return visit_all(std::forward<F>(f));
604 }
605
606#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
607 template<typename ExecutionPolicy,typename F>
608 void visit_all(ExecutionPolicy&& policy,F&& f)
609 {
610 visit_all_impl(
611 group_exclusive{},
612 std::forward<ExecutionPolicy>(policy),std::forward<F>(f));
613 }
614
615 template<typename ExecutionPolicy,typename F>
616 void visit_all(ExecutionPolicy&& policy,F&& f)const
617 {
618 visit_all_impl(
619 group_shared{},
620 std::forward<ExecutionPolicy>(policy),std::forward<F>(f));
621 }
622
623 template<typename ExecutionPolicy,typename F>
624 void cvisit_all(ExecutionPolicy&& policy,F&& f)const
625 {
626 visit_all(std::forward<ExecutionPolicy>(policy),std::forward<F>(f));
627 }
628#endif
629
630 template<typename F> bool visit_while(F&& f)
631 {
632 return visit_while_impl(group_exclusive{},std::forward<F>(f));
633 }
634
635 template<typename F> bool visit_while(F&& f)const
636 {
637 return visit_while_impl(group_shared{},std::forward<F>(f));
638 }
639
640 template<typename F> bool cvisit_while(F&& f)const
641 {
642 return visit_while(std::forward<F>(f));
643 }
644
645#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
646 template<typename ExecutionPolicy,typename F>
647 bool visit_while(ExecutionPolicy&& policy,F&& f)
648 {
649 return visit_while_impl(
650 group_exclusive{},
651 std::forward<ExecutionPolicy>(policy),std::forward<F>(f));
652 }
653
654 template<typename ExecutionPolicy,typename F>
655 bool visit_while(ExecutionPolicy&& policy,F&& f)const
656 {
657 return visit_while_impl(
658 group_shared{},
659 std::forward<ExecutionPolicy>(policy),std::forward<F>(f));
660 }
661
662 template<typename ExecutionPolicy,typename F>
663 bool cvisit_while(ExecutionPolicy&& policy,F&& f)const
664 {
665 return visit_while(
666 std::forward<ExecutionPolicy>(policy),std::forward<F>(f));
667 }
668#endif
669
670 bool empty()const noexcept{return size()==0;}
671
672 std::size_t size()const noexcept
673 {
674 auto lck=shared_access();
675 return unprotected_size();
676 }
677
678 using super::max_size;
679
680 template<typename... Args>
681 BOOST_FORCEINLINE bool emplace(Args&&... args)
682 {
683 return construct_and_emplace(std::forward<Args>(args)...);
684 }
685
686 /* Optimization for value_type and init_type, to avoid constructing twice */
687 template<typename Value>
688 BOOST_FORCEINLINE auto emplace(Value&& x)->typename std::enable_if<
689 detail::is_similar_to_any<Value,value_type,init_type>::value,bool>::type
690 {
691 return emplace_impl(std::forward<Value>(x));
692 }
693
694 /* Optimizations for maps for (k,v) to avoid eagerly constructing value */
695 template <typename K, typename V>
696 BOOST_FORCEINLINE auto emplace(K&& k, V&& v) ->
697 typename std::enable_if<is_emplace_kv_able<concurrent_table, K>::value,
698 bool>::type
699 {
700 alloc_cted_or_fwded_key_type<type_policy, Allocator, K&&> x(
701 this->al(), std::forward<K>(k));
702 return emplace_impl(
703 try_emplace_args_t{}, x.move_or_fwd(), std::forward<V>(v));
704 }
705
706 BOOST_FORCEINLINE bool
707 insert(const init_type& x){return emplace_impl(x);}
708
709 BOOST_FORCEINLINE bool
710 insert(init_type&& x){return emplace_impl(std::move(x));}
711
712 /* template<typename=void> tilts call ambiguities in favor of init_type */
713
714 template<typename=void>
715 BOOST_FORCEINLINE bool
716 insert(const value_type& x){return emplace_impl(x);}
717
718 template<typename=void>
719 BOOST_FORCEINLINE bool
720 insert(value_type&& x){return emplace_impl(std::move(x));}
721
722 template<typename Key,typename... Args>
723 BOOST_FORCEINLINE bool try_emplace(Key&& x,Args&&... args)
724 {
725 return emplace_impl(
726 try_emplace_args_t{},std::forward<Key>(x),std::forward<Args>(args)...);
727 }
728
729 template<typename Key,typename... Args>
730 BOOST_FORCEINLINE bool try_emplace_or_visit(Key&& x,Args&&... args)
731 {
732 return emplace_or_visit_flast(
733 group_exclusive{},
734 try_emplace_args_t{},std::forward<Key>(x),std::forward<Args>(args)...);
735 }
736
737 template<typename Key,typename... Args>
738 BOOST_FORCEINLINE bool try_emplace_or_cvisit(Key&& x,Args&&... args)
739 {
740 return emplace_or_visit_flast(
741 group_shared{},
742 try_emplace_args_t{},std::forward<Key>(x),std::forward<Args>(args)...);
743 }
744
745 template<typename... Args>
746 BOOST_FORCEINLINE bool emplace_or_visit(Args&&... args)
747 {
748 return construct_and_emplace_or_visit_flast(
749 group_exclusive{},std::forward<Args>(args)...);
750 }
751
752 template<typename... Args>
753 BOOST_FORCEINLINE bool emplace_or_cvisit(Args&&... args)
754 {
755 return construct_and_emplace_or_visit_flast(
756 group_shared{},std::forward<Args>(args)...);
757 }
758
759 template<typename F>
760 BOOST_FORCEINLINE bool insert_or_visit(const init_type& x,F&& f)
761 {
762 return emplace_or_visit_impl(group_exclusive{},std::forward<F>(f),x);
763 }
764
765 template<typename F>
766 BOOST_FORCEINLINE bool insert_or_cvisit(const init_type& x,F&& f)
767 {
768 return emplace_or_visit_impl(group_shared{},std::forward<F>(f),x);
769 }
770
771 template<typename F>
772 BOOST_FORCEINLINE bool insert_or_visit(init_type&& x,F&& f)
773 {
774 return emplace_or_visit_impl(
775 group_exclusive{},std::forward<F>(f),std::move(x));
776 }
777
778 template<typename F>
779 BOOST_FORCEINLINE bool insert_or_cvisit(init_type&& x,F&& f)
780 {
781 return emplace_or_visit_impl(
782 group_shared{},std::forward<F>(f),std::move(x));
783 }
784
785 /* SFINAE tilts call ambiguities in favor of init_type */
786
787 template<typename Value,typename F>
788 BOOST_FORCEINLINE auto insert_or_visit(const Value& x,F&& f)
789 ->enable_if_is_value_type<Value,bool>
790 {
791 return emplace_or_visit_impl(group_exclusive{},std::forward<F>(f),x);
792 }
793
794 template<typename Value,typename F>
795 BOOST_FORCEINLINE auto insert_or_cvisit(const Value& x,F&& f)
796 ->enable_if_is_value_type<Value,bool>
797 {
798 return emplace_or_visit_impl(group_shared{},std::forward<F>(f),x);
799 }
800
801 template<typename Value,typename F>
802 BOOST_FORCEINLINE auto insert_or_visit(Value&& x,F&& f)
803 ->enable_if_is_value_type<Value,bool>
804 {
805 return emplace_or_visit_impl(
806 group_exclusive{},std::forward<F>(f),std::move(x));
807 }
808
809 template<typename Value,typename F>
810 BOOST_FORCEINLINE auto insert_or_cvisit(Value&& x,F&& f)
811 ->enable_if_is_value_type<Value,bool>
812 {
813 return emplace_or_visit_impl(
814 group_shared{},std::forward<F>(f),std::move(x));
815 }
816
817 template<typename Key>
818 BOOST_FORCEINLINE std::size_t erase(const Key& x)
819 {
820 return erase_if(x,[](const value_type&){return true;});
821 }
822
823 template<typename Key,typename F>
824 BOOST_FORCEINLINE auto erase_if(const Key& x,F&& f)->typename std::enable_if<
825 !is_execution_policy<Key>::value,std::size_t>::type
826 {
827 auto lck=shared_access();
828 auto hash=this->hash_for(x);
829 std::size_t res=0;
830 unprotected_internal_visit(
831 group_exclusive{},x,this->position_for(hash),hash,
832 [&,this](group_type* pg,unsigned int n,element_type* p)
833 {
834 if(f(cast_for(group_exclusive{},type_policy::value_from(*p)))){
835 super::erase(pg,n,p);
836 res=1;
837 }
838 });
839 return res;
840 }
841
842 template<typename F>
843 std::size_t erase_if(F&& f)
844 {
845 auto lck=shared_access();
846 std::size_t res=0;
847 for_all_elements(
848 group_exclusive{},
849 [&,this](group_type* pg,unsigned int n,element_type* p){
850 if(f(cast_for(group_exclusive{},type_policy::value_from(*p)))){
851 super::erase(pg,n,p);
852 ++res;
853 }
854 });
855 return res;
856 }
857
858#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
859 template<typename ExecutionPolicy,typename F>
860 auto erase_if(ExecutionPolicy&& policy,F&& f)->typename std::enable_if<
861 is_execution_policy<ExecutionPolicy>::value,void>::type
862 {
863 auto lck=shared_access();
864 for_all_elements(
865 group_exclusive{},std::forward<ExecutionPolicy>(policy),
866 [&,this](group_type* pg,unsigned int n,element_type* p){
867 if(f(cast_for(group_exclusive{},type_policy::value_from(*p)))){
868 super::erase(pg,n,p);
869 }
870 });
871 }
872#endif
873
874 void swap(concurrent_table& x)
875 noexcept(noexcept(std::declval<super&>().swap(std::declval<super&>())))
876 {
877 auto lck=exclusive_access(*this,x);
878 super::swap(x);
879 }
880
881 void clear()noexcept
882 {
883 auto lck=exclusive_access();
884 super::clear();
885 }
886
887 // TODO: should we accept different allocator too?
888 template<typename Hash2,typename Pred2>
889 size_type merge(concurrent_table<TypePolicy,Hash2,Pred2,Allocator>& x)
890 {
891 using merge_table_type=concurrent_table<TypePolicy,Hash2,Pred2,Allocator>;
892 using super2=typename merge_table_type::super;
893
894 // for clang
895 boost::ignore_unused<super2>();
896
897 auto lck=exclusive_access(*this,x);
898 size_type s=super::size();
899 x.super2::for_all_elements( /* super2::for_all_elements -> unprotected */
900 [&,this](group_type* pg,unsigned int n,element_type* p){
901 typename merge_table_type::erase_on_exit e{x,pg,n,p};
902 if(!unprotected_emplace(type_policy::move(*p)))e.rollback();
903 });
904 return size_type{super::size()-s};
905 }
906
907 template<typename Hash2,typename Pred2>
908 void merge(concurrent_table<TypePolicy,Hash2,Pred2,Allocator>&& x){merge(x);}
909
910 hasher hash_function()const
911 {
912 auto lck=shared_access();
913 return super::hash_function();
914 }
915
916 key_equal key_eq()const
917 {
918 auto lck=shared_access();
919 return super::key_eq();
920 }
921
922 template<typename Key>
923 BOOST_FORCEINLINE std::size_t count(Key&& x)const
924 {
925 return (std::size_t)contains(std::forward<Key>(x));
926 }
927
928 template<typename Key>
929 BOOST_FORCEINLINE bool contains(Key&& x)const
930 {
931 return visit(std::forward<Key>(x),[](const value_type&){})!=0;
932 }
933
934 std::size_t capacity()const noexcept
935 {
936 auto lck=shared_access();
937 return super::capacity();
938 }
939
940 float load_factor()const noexcept
941 {
942 auto lck=shared_access();
943 if(super::capacity()==0)return 0;
944 else return float(unprotected_size())/
945 float(super::capacity());
946 }
947
948 using super::max_load_factor;
949
950 std::size_t max_load()const noexcept
951 {
952 auto lck=shared_access();
953 return super::max_load();
954 }
955
956 void rehash(std::size_t n)
957 {
958 auto lck=exclusive_access();
959 super::rehash(n);
960 }
961
962 void reserve(std::size_t n)
963 {
964 auto lck=exclusive_access();
965 super::reserve(n);
966 }
967
968 template<typename Predicate>
969 friend std::size_t erase_if(concurrent_table& x,Predicate&& pr)
970 {
971 return x.erase_if(std::forward<Predicate>(pr));
972 }
973
974 friend bool operator==(const concurrent_table& x,const concurrent_table& y)
975 {
976 auto lck=exclusive_access(x,y);
977 return static_cast<const super&>(x)==static_cast<const super&>(y);
978 }
979
980 friend bool operator!=(const concurrent_table& x,const concurrent_table& y)
981 {
982 return !(x==y);
983 }
984
985private:
986 template<typename,typename,typename,typename> friend class concurrent_table;
987
988 using mutex_type=rw_spinlock;
989 using multimutex_type=multimutex<mutex_type,128>; // TODO: adapt 128 to the machine
990 using shared_lock_guard=reentrancy_checked<shared_lock<mutex_type>>;
991 using exclusive_lock_guard=reentrancy_checked<lock_guard<multimutex_type>>;
992 using exclusive_bilock_guard=
993 reentrancy_bichecked<scoped_bilock<multimutex_type>>;
994 using group_shared_lock_guard=typename group_access::shared_lock_guard;
995 using group_exclusive_lock_guard=typename group_access::exclusive_lock_guard;
996 using group_insert_counter_type=typename group_access::insert_counter_type;
997
998 concurrent_table(const concurrent_table& x,exclusive_lock_guard):
999 super{x}{}
1000 concurrent_table(concurrent_table&& x,exclusive_lock_guard):
1001 super{std::move(x)}{}
1002 concurrent_table(
1003 const concurrent_table& x,const Allocator& al_,exclusive_lock_guard):
1004 super{x,al_}{}
1005 concurrent_table(
1006 concurrent_table&& x,const Allocator& al_,exclusive_lock_guard):
1007 super{std::move(x),al_}{}
1008
1009 inline shared_lock_guard shared_access()const
1010 {
1011 thread_local auto id=(++thread_counter)%mutexes.size();
1012
1013 return shared_lock_guard{this,mutexes[id]};
1014 }
1015
1016 inline exclusive_lock_guard exclusive_access()const
1017 {
1018 return exclusive_lock_guard{this,mutexes};
1019 }
1020
1021 static inline exclusive_bilock_guard exclusive_access(
1022 const concurrent_table& x,const concurrent_table& y)
1023 {
1024 return {&x,&y,x.mutexes,y.mutexes};
1025 }
1026
1027 template<typename Hash2,typename Pred2>
1028 static inline exclusive_bilock_guard exclusive_access(
1029 const concurrent_table& x,
1030 const concurrent_table<TypePolicy,Hash2,Pred2,Allocator>& y)
1031 {
1032 return {&x,&y,x.mutexes,y.mutexes};
1033 }
1034
1035 /* Tag-dispatched shared/exclusive group access */
1036
1037 using group_shared=std::false_type;
1038 using group_exclusive=std::true_type;
1039
1040 inline group_shared_lock_guard access(group_shared,std::size_t pos)const
1041 {
1042 return this->arrays.group_accesses()[pos].shared_access();
1043 }
1044
1045 inline group_exclusive_lock_guard access(
1046 group_exclusive,std::size_t pos)const
1047 {
1048 return this->arrays.group_accesses()[pos].exclusive_access();
1049 }
1050
1051 inline group_insert_counter_type& insert_counter(std::size_t pos)const
1052 {
1053 return this->arrays.group_accesses()[pos].insert_counter();
1054 }
1055
1056 /* Const casts value_type& according to the level of group access for
1057 * safe passing to visitation functions. When type_policy is set-like,
1058 * access is always const regardless of group access.
1059 */
1060
1061 static inline const value_type&
1062 cast_for(group_shared,value_type& x){return x;}
1063
1064 static inline typename std::conditional<
1065 std::is_same<key_type,value_type>::value,
1066 const value_type&,
1067 value_type&
1068 >::type
1069 cast_for(group_exclusive,value_type& x){return x;}
1070
1071 struct erase_on_exit
1072 {
1073 erase_on_exit(
1074 concurrent_table& x_,
1075 group_type* pg_,unsigned int pos_,element_type* p_):
1076 x(x_),pg(pg_),pos(pos_),p(p_){}
1077 ~erase_on_exit(){if(!rollback_)x.super::erase(pg,pos,p);}
1078
1079 void rollback(){rollback_=true;}
1080
1081 concurrent_table &x;
1082 group_type *pg;
1083 unsigned int pos;
1084 element_type *p;
1085 bool rollback_=false;
1086 };
1087
1088 template<typename GroupAccessMode,typename Key,typename F>
1089 BOOST_FORCEINLINE std::size_t visit_impl(
1090 GroupAccessMode access_mode,const Key& x,F&& f)const
1091 {
1092 auto lck=shared_access();
1093 auto hash=this->hash_for(x);
1094 return unprotected_visit(
1095 access_mode,x,this->position_for(hash),hash,std::forward<F>(f));
1096 }
1097
1098 template<typename GroupAccessMode,typename FwdIterator,typename F>
1099 BOOST_FORCEINLINE
1100 std::size_t bulk_visit_impl(
1101 GroupAccessMode access_mode,FwdIterator first,FwdIterator last,F&& f)const
1102 {
1103 auto lck=shared_access();
1104 std::size_t res=0;
1105 auto n=static_cast<std::size_t>(std::distance(first,last));
1106 while(n){
1107 auto m=n<2*bulk_visit_size?n:bulk_visit_size;
1108 res+=unprotected_bulk_visit(access_mode,first,m,std::forward<F>(f));
1109 n-=m;
1110 std::advance(
1111 first,
1112 static_cast<
1113 typename std::iterator_traits<FwdIterator>::difference_type>(m));
1114 }
1115 return res;
1116 }
1117
1118 template<typename GroupAccessMode,typename F>
1119 std::size_t visit_all_impl(GroupAccessMode access_mode,F&& f)const
1120 {
1121 auto lck=shared_access();
1122 std::size_t res=0;
1123 for_all_elements(access_mode,[&](element_type* p){
1124 f(cast_for(access_mode,type_policy::value_from(*p)));
1125 ++res;
1126 });
1127 return res;
1128 }
1129
1130#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
1131 template<typename GroupAccessMode,typename ExecutionPolicy,typename F>
1132 void visit_all_impl(
1133 GroupAccessMode access_mode,ExecutionPolicy&& policy,F&& f)const
1134 {
1135 auto lck=shared_access();
1136 for_all_elements(
1137 access_mode,std::forward<ExecutionPolicy>(policy),
1138 [&](element_type* p){
1139 f(cast_for(access_mode,type_policy::value_from(*p)));
1140 });
1141 }
1142#endif
1143
1144 template<typename GroupAccessMode,typename F>
1145 bool visit_while_impl(GroupAccessMode access_mode,F&& f)const
1146 {
1147 auto lck=shared_access();
1148 return for_all_elements_while(access_mode,[&](element_type* p){
1149 return f(cast_for(access_mode,type_policy::value_from(*p)));
1150 });
1151 }
1152
1153#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
1154 template<typename GroupAccessMode,typename ExecutionPolicy,typename F>
1155 bool visit_while_impl(
1156 GroupAccessMode access_mode,ExecutionPolicy&& policy,F&& f)const
1157 {
1158 auto lck=shared_access();
1159 return for_all_elements_while(
1160 access_mode,std::forward<ExecutionPolicy>(policy),
1161 [&](element_type* p){
1162 return f(cast_for(access_mode,type_policy::value_from(*p)));
1163 });
1164 }
1165#endif
1166
1167 template<typename GroupAccessMode,typename Key,typename F>
1168 BOOST_FORCEINLINE std::size_t unprotected_visit(
1169 GroupAccessMode access_mode,
1170 const Key& x,std::size_t pos0,std::size_t hash,F&& f)const
1171 {
1172 return unprotected_internal_visit(
1173 access_mode,x,pos0,hash,
1174 [&](group_type*,unsigned int,element_type* p)
1175 {f(cast_for(access_mode,type_policy::value_from(*p)));});
1176 }
1177
1178#if defined(BOOST_MSVC)
1179/* warning: forcing value to bool 'true' or 'false' in bool(pred()...) */
1180#pragma warning(push)
1181#pragma warning(disable:4800)
1182#endif
1183
1184 template<typename GroupAccessMode,typename Key,typename F>
1185 BOOST_FORCEINLINE std::size_t unprotected_internal_visit(
1186 GroupAccessMode access_mode,
1187 const Key& x,std::size_t pos0,std::size_t hash,F&& f)const
1188 {
1189 prober pb(pos0);
1190 do{
1191 auto pos=pb.get();
1192 auto pg=this->arrays.groups()+pos;
1193 auto mask=pg->match(hash);
1194 if(mask){
1195 auto p=this->arrays.elements()+pos*N;
1196 BOOST_UNORDERED_PREFETCH_ELEMENTS(p,N);
1197 auto lck=access(access_mode,pos);
1198 do{
1199 auto n=unchecked_countr_zero(mask);
1200 if(BOOST_LIKELY(
1201 pg->is_occupied(n)&&bool(this->pred()(x,this->key_from(p[n]))))){
1202 f(pg,n,p+n);
1203 return 1;
1204 }
1205 mask&=mask-1;
1206 }while(mask);
1207 }
1208 if(BOOST_LIKELY(pg->is_not_overflowed(hash))){
1209 return 0;
1210 }
1211 }
1212 while(BOOST_LIKELY(pb.next(this->arrays.groups_size_mask)));
1213 return 0;
1214 }
1215
1216 template<typename GroupAccessMode,typename FwdIterator,typename F>
1217 BOOST_FORCEINLINE std::size_t unprotected_bulk_visit(
1218 GroupAccessMode access_mode,FwdIterator first,std::size_t m,F&& f)const
1219 {
1220 BOOST_ASSERT(m<2*bulk_visit_size);
1221
1222 std::size_t res=0,
1223 hashes[2*bulk_visit_size-1],
1224 positions[2*bulk_visit_size-1];
1225 int masks[2*bulk_visit_size-1];
1226 auto it=first;
1227
1228 for(auto i=m;i--;++it){
1229 auto hash=hashes[i]=this->hash_for(*it);
1230 auto pos=positions[i]=this->position_for(hash);
1231 BOOST_UNORDERED_PREFETCH(this->arrays.groups()+pos);
1232 }
1233
1234 for(auto i=m;i--;){
1235 auto hash=hashes[i];
1236 auto pos=positions[i];
1237 auto mask=masks[i]=(this->arrays.groups()+pos)->match(hash);
1238 if(mask){
1239 BOOST_UNORDERED_PREFETCH(this->arrays.group_accesses()+pos);
1240 BOOST_UNORDERED_PREFETCH(
1241 this->arrays.elements()+pos*N+unchecked_countr_zero(mask));
1242 }
1243 }
1244
1245 it=first;
1246 for(auto i=m;i--;++it){
1247 auto pos=positions[i];
1248 prober pb(pos);
1249 auto pg=this->arrays.groups()+pos;
1250 auto mask=masks[i];
1251 element_type *p;
1252 if(!mask)goto post_mask;
1253 p=this->arrays.elements()+pos*N;
1254 for(;;){
1255 {
1256 auto lck=access(access_mode,pos);
1257 do{
1258 auto n=unchecked_countr_zero(x: mask);
1259 if(BOOST_LIKELY(
1260 pg->is_occupied(n)&&
1261 bool(this->pred()(*it,this->key_from(p[n]))))){
1262 f(cast_for(access_mode,type_policy::value_from(p[n])));
1263 ++res;
1264 goto next_key;
1265 }
1266 mask&=mask-1;
1267 }while(mask);
1268 }
1269 post_mask:
1270 do{
1271 if(BOOST_LIKELY(pg->is_not_overflowed(hashes[i]))||
1272 BOOST_UNLIKELY(!pb.next(this->arrays.groups_size_mask))){
1273 goto next_key;
1274 }
1275 pos=pb.get();
1276 pg=this->arrays.groups()+pos;
1277 mask=pg->match(hashes[i]);
1278 }while(!mask);
1279 p=this->arrays.elements()+pos*N;
1280 BOOST_UNORDERED_PREFETCH_ELEMENTS(p,N);
1281 }
1282 next_key:;
1283 }
1284 return res;
1285 }
1286
1287#if defined(BOOST_MSVC)
1288#pragma warning(pop) /* C4800 */
1289#endif
1290
1291 std::size_t unprotected_size()const
1292 {
1293 std::size_t m=this->size_ctrl.ml;
1294 std::size_t s=this->size_ctrl.size;
1295 return s<=m?s:m;
1296 }
1297
1298 template<typename... Args>
1299 BOOST_FORCEINLINE bool construct_and_emplace(Args&&... args)
1300 {
1301 return construct_and_emplace_or_visit(
1302 group_shared{},[](const value_type&){},std::forward<Args>(args)...);
1303 }
1304
1305 struct call_construct_and_emplace_or_visit
1306 {
1307 template<typename... Args>
1308 BOOST_FORCEINLINE bool operator()(
1309 concurrent_table* this_,Args&&... args)const
1310 {
1311 return this_->construct_and_emplace_or_visit(
1312 std::forward<Args>(args)...);
1313 }
1314 };
1315
1316 template<typename GroupAccessMode,typename... Args>
1317 BOOST_FORCEINLINE bool construct_and_emplace_or_visit_flast(
1318 GroupAccessMode access_mode,Args&&... args)
1319 {
1320 return mp11::tuple_apply(
1321 call_construct_and_emplace_or_visit{},
1322 std::tuple_cat(
1323 std::make_tuple(this,access_mode),
1324 tuple_rotate_right(std::forward_as_tuple(std::forward<Args>(args)...))
1325 )
1326 );
1327 }
1328
1329 template<typename GroupAccessMode,typename F,typename... Args>
1330 BOOST_FORCEINLINE bool construct_and_emplace_or_visit(
1331 GroupAccessMode access_mode,F&& f,Args&&... args)
1332 {
1333 auto lck=shared_access();
1334
1335 alloc_cted_insert_type<type_policy,Allocator,Args...> x(
1336 this->al(),std::forward<Args>(args)...);
1337 int res=unprotected_norehash_emplace_or_visit(
1338 access_mode,std::forward<F>(f),type_policy::move(x.value()));
1339 if(BOOST_LIKELY(res>=0))return res!=0;
1340
1341 lck.unlock();
1342
1343 rehash_if_full();
1344 return noinline_emplace_or_visit(
1345 access_mode,std::forward<F>(f),type_policy::move(x.value()));
1346 }
1347
1348 template<typename... Args>
1349 BOOST_FORCEINLINE bool emplace_impl(Args&&... args)
1350 {
1351 return emplace_or_visit_impl(
1352 group_shared{},[](const value_type&){},std::forward<Args>(args)...);
1353 }
1354
1355 template<typename GroupAccessMode,typename F,typename... Args>
1356 BOOST_NOINLINE bool noinline_emplace_or_visit(
1357 GroupAccessMode access_mode,F&& f,Args&&... args)
1358 {
1359 return emplace_or_visit_impl(
1360 access_mode,std::forward<F>(f),std::forward<Args>(args)...);
1361 }
1362
1363 struct call_emplace_or_visit_impl
1364 {
1365 template<typename... Args>
1366 BOOST_FORCEINLINE bool operator()(
1367 concurrent_table* this_,Args&&... args)const
1368 {
1369 return this_->emplace_or_visit_impl(std::forward<Args>(args)...);
1370 }
1371 };
1372
1373 template<typename GroupAccessMode,typename... Args>
1374 BOOST_FORCEINLINE bool emplace_or_visit_flast(
1375 GroupAccessMode access_mode,Args&&... args)
1376 {
1377 return mp11::tuple_apply(
1378 call_emplace_or_visit_impl{},
1379 std::tuple_cat(
1380 std::make_tuple(this,access_mode),
1381 tuple_rotate_right(std::forward_as_tuple(std::forward<Args>(args)...))
1382 )
1383 );
1384 }
1385
1386 template<typename GroupAccessMode,typename F,typename... Args>
1387 BOOST_FORCEINLINE bool emplace_or_visit_impl(
1388 GroupAccessMode access_mode,F&& f,Args&&... args)
1389 {
1390 for(;;){
1391 {
1392 auto lck=shared_access();
1393 int res=unprotected_norehash_emplace_or_visit(
1394 access_mode,std::forward<F>(f),std::forward<Args>(args)...);
1395 if(BOOST_LIKELY(res>=0))return res!=0;
1396 }
1397 rehash_if_full();
1398 }
1399 }
1400
1401 template<typename... Args>
1402 BOOST_FORCEINLINE bool unprotected_emplace(Args&&... args)
1403 {
1404 const auto &k=this->key_from(std::forward<Args>(args)...);
1405 auto hash=this->hash_for(k);
1406 auto pos0=this->position_for(hash);
1407
1408 if(this->find(k,pos0,hash))return false;
1409
1410 if(BOOST_LIKELY(this->size_ctrl.size<this->size_ctrl.ml)){
1411 this->unchecked_emplace_at(pos0,hash,std::forward<Args>(args)...);
1412 }
1413 else{
1414 this->unchecked_emplace_with_rehash(hash,std::forward<Args>(args)...);
1415 }
1416 return true;
1417 }
1418
1419 struct reserve_size
1420 {
1421 reserve_size(concurrent_table& x_):x(x_)
1422 {
1423 size_=++x.size_ctrl.size;
1424 }
1425
1426 ~reserve_size()
1427 {
1428 if(!commit_)--x.size_ctrl.size;
1429 }
1430
1431 bool succeeded()const{return size_<=x.size_ctrl.ml;}
1432
1433 void commit(){commit_=true;}
1434
1435 concurrent_table &x;
1436 std::size_t size_;
1437 bool commit_=false;
1438 };
1439
1440 struct reserve_slot
1441 {
1442 reserve_slot(group_type* pg_,std::size_t pos_,std::size_t hash):
1443 pg{pg_},pos{pos_}
1444 {
1445 pg->set(pos,hash);
1446 }
1447
1448 ~reserve_slot()
1449 {
1450 if(!commit_)pg->reset(pos);
1451 }
1452
1453 void commit(){commit_=true;}
1454
1455 group_type *pg;
1456 std::size_t pos;
1457 bool commit_=false;
1458 };
1459
1460 template<typename GroupAccessMode,typename F,typename... Args>
1461 BOOST_FORCEINLINE int
1462 unprotected_norehash_emplace_or_visit(
1463 GroupAccessMode access_mode,F&& f,Args&&... args)
1464 {
1465 const auto &k=this->key_from(std::forward<Args>(args)...);
1466 auto hash=this->hash_for(k);
1467 auto pos0=this->position_for(hash);
1468
1469 for(;;){
1470 startover:
1471 boost::uint32_t counter=insert_counter(pos: pos0);
1472 if(unprotected_visit(
1473 access_mode,k,pos0,hash,std::forward<F>(f)))return 0;
1474
1475 reserve_size rsize(*this);
1476 if(BOOST_LIKELY(rsize.succeeded())){
1477 for(prober pb(pos0);;pb.next(this->arrays.groups_size_mask)){
1478 auto pos=pb.get();
1479 auto pg=this->arrays.groups()+pos;
1480 auto lck=access(group_exclusive{},pos);
1481 auto mask=pg->match_available();
1482 if(BOOST_LIKELY(mask!=0)){
1483 auto n=unchecked_countr_zero(mask);
1484 reserve_slot rslot{pg,n,hash};
1485 if(BOOST_UNLIKELY(insert_counter(pos0)++!=counter)){
1486 /* other thread inserted from pos0, need to start over */
1487 goto startover;
1488 }
1489 auto p=this->arrays.elements()+pos*N+n;
1490 this->construct_element(p,std::forward<Args>(args)...);
1491 rslot.commit();
1492 rsize.commit();
1493 return 1;
1494 }
1495 pg->mark_overflow(hash);
1496 }
1497 }
1498 else return -1;
1499 }
1500 }
1501
1502 void rehash_if_full()
1503 {
1504 auto lck=exclusive_access();
1505 if(this->size_ctrl.size==this->size_ctrl.ml){
1506 this->unchecked_rehash_for_growth();
1507 }
1508 }
1509
1510 template<typename GroupAccessMode,typename F>
1511 auto for_all_elements(GroupAccessMode access_mode,F f)const
1512 ->decltype(f(nullptr),void())
1513 {
1514 for_all_elements(
1515 access_mode,[&](group_type*,unsigned int,element_type* p){f(p);});
1516 }
1517
1518 template<typename GroupAccessMode,typename F>
1519 auto for_all_elements(GroupAccessMode access_mode,F f)const
1520 ->decltype(f(nullptr,0,nullptr),void())
1521 {
1522 for_all_elements_while(
1523 access_mode,[&](group_type* pg,unsigned int n,element_type* p)
1524 {f(pg,n,p);return true;});
1525 }
1526
1527 template<typename GroupAccessMode,typename F>
1528 auto for_all_elements_while(GroupAccessMode access_mode,F f)const
1529 ->decltype(f(nullptr),bool())
1530 {
1531 return for_all_elements_while(
1532 access_mode,[&](group_type*,unsigned int,element_type* p){return f(p);});
1533 }
1534
1535 template<typename GroupAccessMode,typename F>
1536 auto for_all_elements_while(GroupAccessMode access_mode,F f)const
1537 ->decltype(f(nullptr,0,nullptr),bool())
1538 {
1539 auto p=this->arrays.elements();
1540 if(p){
1541 for(auto pg=this->arrays.groups(),last=pg+this->arrays.groups_size_mask+1;
1542 pg!=last;++pg,p+=N){
1543 auto lck=access(access_mode,(std::size_t)(pg-this->arrays.groups()));
1544 auto mask=this->match_really_occupied(pg,last);
1545 while(mask){
1546 auto n=unchecked_countr_zero(mask);
1547 if(!f(pg,n,p+n))return false;
1548 mask&=mask-1;
1549 }
1550 }
1551 }
1552 return true;
1553 }
1554
1555#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
1556 template<typename GroupAccessMode,typename ExecutionPolicy,typename F>
1557 auto for_all_elements(
1558 GroupAccessMode access_mode,ExecutionPolicy&& policy,F f)const
1559 ->decltype(f(nullptr),void())
1560 {
1561 for_all_elements(
1562 access_mode,std::forward<ExecutionPolicy>(policy),
1563 [&](group_type*,unsigned int,element_type* p){f(p);});
1564 }
1565
1566 template<typename GroupAccessMode,typename ExecutionPolicy,typename F>
1567 auto for_all_elements(
1568 GroupAccessMode access_mode,ExecutionPolicy&& policy,F f)const
1569 ->decltype(f(nullptr,0,nullptr),void())
1570 {
1571 if(!this->arrays.elements())return;
1572 auto first=this->arrays.groups(),
1573 last=first+this->arrays.groups_size_mask+1;
1574 std::for_each(std::forward<ExecutionPolicy>(policy),first,last,
1575 [&,this](group_type& g){
1576 auto pos=static_cast<std::size_t>(&g-first);
1577 auto p=this->arrays.elements()+pos*N;
1578 auto lck=access(access_mode,pos);
1579 auto mask=this->match_really_occupied(&g,last);
1580 while(mask){
1581 auto n=unchecked_countr_zero(mask);
1582 f(&g,n,p+n);
1583 mask&=mask-1;
1584 }
1585 }
1586 );
1587 }
1588
1589 template<typename GroupAccessMode,typename ExecutionPolicy,typename F>
1590 bool for_all_elements_while(
1591 GroupAccessMode access_mode,ExecutionPolicy&& policy,F f)const
1592 {
1593 if(!this->arrays.elements())return true;
1594 auto first=this->arrays.groups(),
1595 last=first+this->arrays.groups_size_mask+1;
1596 return std::all_of(std::forward<ExecutionPolicy>(policy),first,last,
1597 [&,this](group_type& g){
1598 auto pos=static_cast<std::size_t>(&g-first);
1599 auto p=this->arrays.elements()+pos*N;
1600 auto lck=access(access_mode,pos);
1601 auto mask=this->match_really_occupied(&g,last);
1602 while(mask){
1603 auto n=unchecked_countr_zero(mask);
1604 if(!f(p+n))return false;
1605 mask&=mask-1;
1606 }
1607 return true;
1608 }
1609 );
1610 }
1611#endif
1612
1613 friend class boost::serialization::access;
1614
1615 template<typename Archive>
1616 void serialize(Archive& ar,unsigned int version)
1617 {
1618 core::split_member(ar,*this,version);
1619 }
1620
1621 template<typename Archive>
1622 void save(Archive& ar,unsigned int version)const
1623 {
1624 save(
1625 ar,version,
1626 std::integral_constant<bool,std::is_same<key_type,value_type>::value>{});
1627 }
1628
1629 template<typename Archive>
1630 void save(Archive& ar,unsigned int,std::true_type /* set */)const
1631 {
1632 auto lck=exclusive_access();
1633 const std::size_t s=super::size();
1634 const serialization_version<value_type> value_version;
1635
1636 ar<<core::make_nvp(n: "count",v: s);
1637 ar<<core::make_nvp("value_version",value_version);
1638
1639 super::for_all_elements([&,this](element_type* p){
1640 auto& x=type_policy::value_from(*p);
1641 core::save_construct_data_adl(ar,std::addressof(x),value_version);
1642 ar<<serialization::make_nvp("item",x);
1643 });
1644 }
1645
1646 template<typename Archive>
1647 void save(Archive& ar,unsigned int,std::false_type /* map */)const
1648 {
1649 using raw_key_type=typename std::remove_const<key_type>::type;
1650 using raw_mapped_type=typename std::remove_const<
1651 typename TypePolicy::mapped_type>::type;
1652
1653 auto lck=exclusive_access();
1654 const std::size_t s=super::size();
1655 const serialization_version<raw_key_type> key_version;
1656 const serialization_version<raw_mapped_type> mapped_version;
1657
1658 ar<<core::make_nvp(n: "count",v: s);
1659 ar<<core::make_nvp("key_version",key_version);
1660 ar<<core::make_nvp("mapped_version",mapped_version);
1661
1662 super::for_all_elements([&,this](element_type* p){
1663 /* To remain lib-independent from Boost.Serialization and not rely on
1664 * the user having included the serialization code for std::pair
1665 * (boost/serialization/utility.hpp), we serialize the key and the
1666 * mapped value separately.
1667 */
1668
1669 auto& x=type_policy::value_from(*p);
1670 core::save_construct_data_adl(
1671 ar,std::addressof(x.first),key_version);
1672 ar<<serialization::make_nvp("key",x.first);
1673 core::save_construct_data_adl(
1674 ar,std::addressof(x.second),mapped_version);
1675 ar<<serialization::make_nvp("mapped",x.second);
1676 });
1677 }
1678
1679 template<typename Archive>
1680 void load(Archive& ar,unsigned int version)
1681 {
1682 load(
1683 ar,version,
1684 std::integral_constant<bool,std::is_same<key_type,value_type>::value>{});
1685 }
1686
1687 template<typename Archive>
1688 void load(Archive& ar,unsigned int,std::true_type /* set */)
1689 {
1690 auto lck=exclusive_access();
1691 std::size_t s;
1692 serialization_version<value_type> value_version;
1693
1694 ar>>core::make_nvp(n: "count",v&: s);
1695 ar>>core::make_nvp("value_version",value_version);
1696
1697 super::clear();
1698 super::reserve(s);
1699
1700 for(std::size_t n=0;n<s;++n){
1701 archive_constructed<value_type> value("item",ar,value_version);
1702 auto& x=value.get();
1703 auto hash=this->hash_for(x);
1704 auto pos0=this->position_for(hash);
1705
1706 if(this->find(x,pos0,hash))throw_exception(e: bad_archive_exception());
1707 auto loc=this->unchecked_emplace_at(pos0,hash,std::move(x));
1708 ar.reset_object_address(std::addressof(*loc.p),std::addressof(x));
1709 }
1710 }
1711
1712 template<typename Archive>
1713 void load(Archive& ar,unsigned int,std::false_type /* map */)
1714 {
1715 using raw_key_type=typename std::remove_const<key_type>::type;
1716 using raw_mapped_type=typename std::remove_const<
1717 typename TypePolicy::mapped_type>::type;
1718
1719 auto lck=exclusive_access();
1720 std::size_t s;
1721 serialization_version<raw_key_type> key_version;
1722 serialization_version<raw_mapped_type> mapped_version;
1723
1724 ar>>core::make_nvp(n: "count",v&: s);
1725 ar>>core::make_nvp("key_version",key_version);
1726 ar>>core::make_nvp("mapped_version",mapped_version);
1727
1728 super::clear();
1729 super::reserve(s);
1730
1731 for(std::size_t n=0;n<s;++n){
1732 archive_constructed<raw_key_type> key("key",ar,key_version);
1733 archive_constructed<raw_mapped_type> mapped("mapped",ar,mapped_version);
1734 auto& k=key.get();
1735 auto& m=mapped.get();
1736 auto hash=this->hash_for(k);
1737 auto pos0=this->position_for(hash);
1738
1739 if(this->find(k,pos0,hash))throw_exception(e: bad_archive_exception());
1740 auto loc=this->unchecked_emplace_at(pos0,hash,std::move(k),std::move(m));
1741 ar.reset_object_address(std::addressof(loc.p->first),std::addressof(k));
1742 ar.reset_object_address(std::addressof(loc.p->second),std::addressof(m));
1743 }
1744 }
1745
1746 static std::atomic<std::size_t> thread_counter;
1747 mutable multimutex_type mutexes;
1748};
1749
1750template<typename T,typename H,typename P,typename A>
1751std::atomic<std::size_t> concurrent_table<T,H,P,A>::thread_counter={};
1752
1753#if defined(BOOST_MSVC)
1754#pragma warning(pop) /* C4714 */
1755#endif
1756
1757#include <boost/unordered/detail/foa/restore_wshadow.hpp>
1758
1759} /* namespace foa */
1760} /* namespace detail */
1761} /* namespace unordered */
1762} /* namespace boost */
1763
1764#endif
1765

source code of boost/libs/unordered/include/boost/unordered/detail/foa/concurrent_table.hpp