1 2 // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. 3 // Copyright (C) 2005-2011 Daniel James 4 // Distributed under the Boost Software License, Version 1.0. (See accompanying 5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 7 #ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED 8 #define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED 9 10 #include <boost/config.hpp> 11 #if defined(BOOST_HAS_PRAGMA_ONCE) 12 #pragma once 13 #endif 14 15 #include <boost/unordered/detail/util.hpp> 16 #include <boost/unordered/detail/allocate.hpp> 17 18 namespace boost { namespace unordered { namespace detail { 19 20 template <typename Types> struct table; 21 template <typename NodePointer> struct bucket; 22 struct ptr_bucket; 23 template <typename Types> struct table_impl; 24 template <typename Types> struct grouped_table_impl; 25 26 }}} 27 28 // The 'iterator_detail' namespace was a misguided attempt at avoiding ADL 29 // in the detail namespace. It didn't work because the template parameters 30 // were in detail. I'm not changing it at the moment to be safe. I might 31 // do in the future if I change the iterator types. 32 namespace boost { namespace unordered { namespace iterator_detail { 33 34 //////////////////////////////////////////////////////////////////////////// 35 // Iterators 36 // 37 // all no throw 38 39 template <typename Node> struct iterator; 40 template <typename Node> struct c_iterator; 41 template <typename Node, typename Policy> struct l_iterator; 42 template <typename Node, typename Policy> 43 struct cl_iterator; 44 45 // Local Iterators 46 // 47 // all no throw 48 49 template <typename Node, typename Policy> 50 struct l_iterator 51 : public std::iterator< 52 std::forward_iterator_tag, 53 typename Node::value_type, 54 std::ptrdiff_t, 55 typename Node::value_type*, 56 typename Node::value_type&> 57 { 58 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) 59 template <typename Node2, typename Policy2> 60 friend struct boost::unordered::iterator_detail::cl_iterator; 61 private: 62 #endif 63 typedef typename Node::node_pointer node_pointer; 64 typedef boost::unordered::iterator_detail::iterator<Node> n_iterator; 65 node_pointer ptr_; 66 std::size_t bucket_; 67 std::size_t bucket_count_; 68 69 public: 70 71 typedef typename Node::value_type value_type; 72 l_iteratorboost::unordered::iterator_detail::l_iterator73 l_iterator() BOOST_NOEXCEPT : ptr_() {} 74 l_iteratorboost::unordered::iterator_detail::l_iterator75 l_iterator(n_iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT 76 : ptr_(x.node_), bucket_(b), bucket_count_(c) {} 77 operator *boost::unordered::iterator_detail::l_iterator78 value_type& operator*() const { 79 return ptr_->value(); 80 } 81 operator ->boost::unordered::iterator_detail::l_iterator82 value_type* operator->() const { 83 return ptr_->value_ptr(); 84 } 85 operator ++boost::unordered::iterator_detail::l_iterator86 l_iterator& operator++() { 87 ptr_ = static_cast<node_pointer>(ptr_->next_); 88 if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_) 89 != bucket_) 90 ptr_ = node_pointer(); 91 return *this; 92 } 93 operator ++boost::unordered::iterator_detail::l_iterator94 l_iterator operator++(int) { 95 l_iterator tmp(*this); 96 ++(*this); 97 return tmp; 98 } 99 operator ==boost::unordered::iterator_detail::l_iterator100 bool operator==(l_iterator x) const BOOST_NOEXCEPT { 101 return ptr_ == x.ptr_; 102 } 103 operator !=boost::unordered::iterator_detail::l_iterator104 bool operator!=(l_iterator x) const BOOST_NOEXCEPT { 105 return ptr_ != x.ptr_; 106 } 107 }; 108 109 template <typename Node, typename Policy> 110 struct cl_iterator 111 : public std::iterator< 112 std::forward_iterator_tag, 113 typename Node::value_type, 114 std::ptrdiff_t, 115 typename Node::value_type const*, 116 typename Node::value_type const&> 117 { 118 friend struct boost::unordered::iterator_detail::l_iterator 119 <Node, Policy>; 120 private: 121 122 typedef typename Node::node_pointer node_pointer; 123 typedef boost::unordered::iterator_detail::iterator<Node> n_iterator; 124 node_pointer ptr_; 125 std::size_t bucket_; 126 std::size_t bucket_count_; 127 128 public: 129 130 typedef typename Node::value_type value_type; 131 cl_iteratorboost::unordered::iterator_detail::cl_iterator132 cl_iterator() BOOST_NOEXCEPT : ptr_() {} 133 cl_iteratorboost::unordered::iterator_detail::cl_iterator134 cl_iterator(n_iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT : 135 ptr_(x.node_), bucket_(b), bucket_count_(c) {} 136 cl_iteratorboost::unordered::iterator_detail::cl_iterator137 cl_iterator(boost::unordered::iterator_detail::l_iterator< 138 Node, Policy> const& x) BOOST_NOEXCEPT : 139 ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_) 140 {} 141 operator *boost::unordered::iterator_detail::cl_iterator142 value_type const& operator*() const { 143 return ptr_->value(); 144 } 145 operator ->boost::unordered::iterator_detail::cl_iterator146 value_type const* operator->() const { 147 return ptr_->value_ptr(); 148 } 149 operator ++boost::unordered::iterator_detail::cl_iterator150 cl_iterator& operator++() { 151 ptr_ = static_cast<node_pointer>(ptr_->next_); 152 if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_) 153 != bucket_) 154 ptr_ = node_pointer(); 155 return *this; 156 } 157 operator ++boost::unordered::iterator_detail::cl_iterator158 cl_iterator operator++(int) { 159 cl_iterator tmp(*this); 160 ++(*this); 161 return tmp; 162 } 163 operator ==(cl_iterator const & x,cl_iterator const & y)164 friend bool operator==(cl_iterator const& x, cl_iterator const& y) 165 BOOST_NOEXCEPT 166 { 167 return x.ptr_ == y.ptr_; 168 } 169 operator !=(cl_iterator const & x,cl_iterator const & y)170 friend bool operator!=(cl_iterator const& x, cl_iterator const& y) 171 BOOST_NOEXCEPT 172 { 173 return x.ptr_ != y.ptr_; 174 } 175 }; 176 177 template <typename Node> 178 struct iterator 179 : public std::iterator< 180 std::forward_iterator_tag, 181 typename Node::value_type, 182 std::ptrdiff_t, 183 typename Node::value_type*, 184 typename Node::value_type&> 185 { 186 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) 187 template <typename> 188 friend struct boost::unordered::iterator_detail::c_iterator; 189 template <typename, typename> 190 friend struct boost::unordered::iterator_detail::l_iterator; 191 template <typename, typename> 192 friend struct boost::unordered::iterator_detail::cl_iterator; 193 template <typename> 194 friend struct boost::unordered::detail::table; 195 template <typename> 196 friend struct boost::unordered::detail::table_impl; 197 template <typename> 198 friend struct boost::unordered::detail::grouped_table_impl; 199 private: 200 #endif 201 typedef typename Node::node_pointer node_pointer; 202 node_pointer node_; 203 204 public: 205 206 typedef typename Node::value_type value_type; 207 iteratorboost::unordered::iterator_detail::iterator208 iterator() BOOST_NOEXCEPT : node_() {} 209 iteratorboost::unordered::iterator_detail::iterator210 explicit iterator(typename Node::link_pointer x) BOOST_NOEXCEPT : 211 node_(static_cast<node_pointer>(x)) {} 212 operator *boost::unordered::iterator_detail::iterator213 value_type& operator*() const { 214 return node_->value(); 215 } 216 operator ->boost::unordered::iterator_detail::iterator217 value_type* operator->() const { 218 return node_->value_ptr(); 219 } 220 operator ++boost::unordered::iterator_detail::iterator221 iterator& operator++() { 222 node_ = static_cast<node_pointer>(node_->next_); 223 return *this; 224 } 225 operator ++boost::unordered::iterator_detail::iterator226 iterator operator++(int) { 227 iterator tmp(node_); 228 node_ = static_cast<node_pointer>(node_->next_); 229 return tmp; 230 } 231 operator ==boost::unordered::iterator_detail::iterator232 bool operator==(iterator const& x) const BOOST_NOEXCEPT { 233 return node_ == x.node_; 234 } 235 operator !=boost::unordered::iterator_detail::iterator236 bool operator!=(iterator const& x) const BOOST_NOEXCEPT { 237 return node_ != x.node_; 238 } 239 }; 240 241 template <typename Node> 242 struct c_iterator 243 : public std::iterator< 244 std::forward_iterator_tag, 245 typename Node::value_type, 246 std::ptrdiff_t, 247 typename Node::value_type const*, 248 typename Node::value_type const&> 249 { 250 friend struct boost::unordered::iterator_detail::iterator<Node>; 251 252 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) 253 template <typename> 254 friend struct boost::unordered::detail::table; 255 template <typename> 256 friend struct boost::unordered::detail::table_impl; 257 template <typename> 258 friend struct boost::unordered::detail::grouped_table_impl; 259 260 private: 261 #endif 262 typedef typename Node::node_pointer node_pointer; 263 typedef boost::unordered::iterator_detail::iterator<Node> n_iterator; 264 node_pointer node_; 265 266 public: 267 268 typedef typename Node::value_type value_type; 269 c_iteratorboost::unordered::iterator_detail::c_iterator270 c_iterator() BOOST_NOEXCEPT : node_() {} 271 c_iteratorboost::unordered::iterator_detail::c_iterator272 explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT : 273 node_(static_cast<node_pointer>(x)) {} 274 c_iteratorboost::unordered::iterator_detail::c_iterator275 c_iterator(n_iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {} 276 operator *boost::unordered::iterator_detail::c_iterator277 value_type const& operator*() const { 278 return node_->value(); 279 } 280 operator ->boost::unordered::iterator_detail::c_iterator281 value_type const* operator->() const { 282 return node_->value_ptr(); 283 } 284 operator ++boost::unordered::iterator_detail::c_iterator285 c_iterator& operator++() { 286 node_ = static_cast<node_pointer>(node_->next_); 287 return *this; 288 } 289 operator ++boost::unordered::iterator_detail::c_iterator290 c_iterator operator++(int) { 291 c_iterator tmp(node_); 292 node_ = static_cast<node_pointer>(node_->next_); 293 return tmp; 294 } 295 operator ==(c_iterator const & x,c_iterator const & y)296 friend bool operator==(c_iterator const& x, c_iterator const& y) 297 BOOST_NOEXCEPT 298 { 299 return x.node_ == y.node_; 300 } 301 operator !=(c_iterator const & x,c_iterator const & y)302 friend bool operator!=(c_iterator const& x, c_iterator const& y) 303 BOOST_NOEXCEPT 304 { 305 return x.node_ != y.node_; 306 } 307 }; 308 }}} 309 310 namespace boost { namespace unordered { namespace detail { 311 312 /////////////////////////////////////////////////////////////////// 313 // 314 // Node Holder 315 // 316 // Temporary store for nodes. Deletes any that aren't used. 317 318 template <typename NodeAlloc> 319 struct node_holder 320 { 321 private: 322 typedef NodeAlloc node_allocator; 323 typedef boost::unordered::detail::allocator_traits<NodeAlloc> 324 node_allocator_traits; 325 typedef typename node_allocator_traits::value_type node; 326 typedef typename node_allocator_traits::pointer node_pointer; 327 typedef typename node::value_type value_type; 328 typedef typename node::link_pointer link_pointer; 329 typedef boost::unordered::iterator_detail::iterator<node> iterator; 330 331 node_constructor<NodeAlloc> constructor_; 332 node_pointer nodes_; 333 334 public: 335 336 template <typename Table> node_holderboost::unordered::detail::node_holder337 explicit node_holder(Table& b) : 338 constructor_(b.node_alloc()), 339 nodes_() 340 { 341 if (b.size_) { 342 typename Table::link_pointer prev = b.get_previous_start(); 343 nodes_ = static_cast<node_pointer>(prev->next_); 344 prev->next_ = link_pointer(); 345 b.size_ = 0; 346 } 347 } 348 349 ~node_holder(); 350 pop_nodeboost::unordered::detail::node_holder351 node_pointer pop_node() 352 { 353 node_pointer n = nodes_; 354 nodes_ = static_cast<node_pointer>(nodes_->next_); 355 n->init(n); 356 n->next_ = link_pointer(); 357 return n; 358 } 359 360 template <typename T> copy_ofboost::unordered::detail::node_holder361 inline node_pointer copy_of(T const& v) { 362 if (nodes_) { 363 node_tmp<NodeAlloc> a(pop_node(), constructor_.alloc_); 364 a.node_->value() = v; 365 return a.release(); 366 } 367 else { 368 constructor_.create_node(); 369 boost::unordered::detail::func::call_construct( 370 constructor_.alloc_, constructor_.node_->value_ptr(), v); 371 return constructor_.release(); 372 } 373 } 374 375 template <typename T1, typename T2> copy_ofboost::unordered::detail::node_holder376 inline node_pointer copy_of(std::pair<T1 const, T2> const& v) { 377 if (nodes_) { 378 constructor_.reclaim(pop_node()); 379 } 380 else { 381 constructor_.create_node(); 382 } 383 boost::unordered::detail::func::call_construct( 384 constructor_.alloc_, constructor_.node_->value_ptr(), v); 385 return constructor_.release(); 386 } 387 388 template <typename T> move_copy_ofboost::unordered::detail::node_holder389 inline node_pointer move_copy_of(T& v) { 390 if (nodes_) { 391 node_tmp<NodeAlloc> a(pop_node(), constructor_.alloc_); 392 a.node_->value() = boost::move(v); 393 return a.release(); 394 } 395 else { 396 constructor_.create_node(); 397 boost::unordered::detail::func::call_construct( 398 constructor_.alloc_, constructor_.node_->value_ptr(), 399 boost::move(v)); 400 return constructor_.release(); 401 } 402 } 403 404 template <typename T1, typename T2> move_copy_ofboost::unordered::detail::node_holder405 inline node_pointer move_copy_of(std::pair<T1 const, T2>& v) { 406 if (nodes_) { 407 constructor_.reclaim(pop_node()); 408 } 409 else { 410 constructor_.create_node(); 411 } 412 boost::unordered::detail::func::call_construct( 413 constructor_.alloc_, constructor_.node_->value_ptr(), 414 boost::move(v)); 415 return constructor_.release(); 416 } 417 beginboost::unordered::detail::node_holder418 iterator begin() const 419 { 420 return iterator(nodes_); 421 } 422 }; 423 424 template <typename Alloc> ~node_holder()425 node_holder<Alloc>::~node_holder() 426 { 427 while (nodes_) { 428 node_pointer p = nodes_; 429 nodes_ = static_cast<node_pointer>(p->next_); 430 431 boost::unordered::detail::func::destroy_value_impl(constructor_.alloc_, 432 p->value_ptr()); 433 boost::unordered::detail::func::destroy(boost::addressof(*p)); 434 node_allocator_traits::deallocate(constructor_.alloc_, p, 1); 435 } 436 } 437 438 /////////////////////////////////////////////////////////////////// 439 // 440 // Bucket 441 442 template <typename NodePointer> 443 struct bucket 444 { 445 typedef NodePointer link_pointer; 446 link_pointer next_; 447 bucketboost::unordered::detail::bucket448 bucket() : next_() {} 449 first_from_startboost::unordered::detail::bucket450 link_pointer first_from_start() 451 { 452 return next_; 453 } 454 455 enum { extra_node = true }; 456 }; 457 458 struct ptr_bucket 459 { 460 typedef ptr_bucket* link_pointer; 461 link_pointer next_; 462 ptr_bucketboost::unordered::detail::ptr_bucket463 ptr_bucket() : next_(0) {} 464 first_from_startboost::unordered::detail::ptr_bucket465 link_pointer first_from_start() 466 { 467 return this; 468 } 469 470 enum { extra_node = false }; 471 }; 472 473 /////////////////////////////////////////////////////////////////// 474 // 475 // Hash Policy 476 477 template <typename SizeT> 478 struct prime_policy 479 { 480 template <typename Hash, typename T> apply_hashboost::unordered::detail::prime_policy481 static inline SizeT apply_hash(Hash const& hf, T const& x) { 482 return hf(x); 483 } 484 to_bucketboost::unordered::detail::prime_policy485 static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) { 486 return hash % bucket_count; 487 } 488 new_bucket_countboost::unordered::detail::prime_policy489 static inline SizeT new_bucket_count(SizeT min) { 490 return boost::unordered::detail::next_prime(min); 491 } 492 prev_bucket_countboost::unordered::detail::prime_policy493 static inline SizeT prev_bucket_count(SizeT max) { 494 return boost::unordered::detail::prev_prime(max); 495 } 496 }; 497 498 template <typename SizeT> 499 struct mix64_policy 500 { 501 template <typename Hash, typename T> apply_hashboost::unordered::detail::mix64_policy502 static inline SizeT apply_hash(Hash const& hf, T const& x) { 503 SizeT key = hf(x); 504 key = (~key) + (key << 21); // key = (key << 21) - key - 1; 505 key = key ^ (key >> 24); 506 key = (key + (key << 3)) + (key << 8); // key * 265 507 key = key ^ (key >> 14); 508 key = (key + (key << 2)) + (key << 4); // key * 21 509 key = key ^ (key >> 28); 510 key = key + (key << 31); 511 return key; 512 } 513 to_bucketboost::unordered::detail::mix64_policy514 static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) { 515 return hash & (bucket_count - 1); 516 } 517 new_bucket_countboost::unordered::detail::mix64_policy518 static inline SizeT new_bucket_count(SizeT min) { 519 if (min <= 4) return 4; 520 --min; 521 min |= min >> 1; 522 min |= min >> 2; 523 min |= min >> 4; 524 min |= min >> 8; 525 min |= min >> 16; 526 min |= min >> 32; 527 return min + 1; 528 } 529 prev_bucket_countboost::unordered::detail::mix64_policy530 static inline SizeT prev_bucket_count(SizeT max) { 531 max |= max >> 1; 532 max |= max >> 2; 533 max |= max >> 4; 534 max |= max >> 8; 535 max |= max >> 16; 536 max |= max >> 32; 537 return (max >> 1) + 1; 538 } 539 }; 540 541 template <int digits, int radix> 542 struct pick_policy_impl { 543 typedef prime_policy<std::size_t> type; 544 }; 545 546 template <> 547 struct pick_policy_impl<64, 2> { 548 typedef mix64_policy<std::size_t> type; 549 }; 550 551 template <typename T> 552 struct pick_policy : 553 pick_policy_impl< 554 std::numeric_limits<std::size_t>::digits, 555 std::numeric_limits<std::size_t>::radix> {}; 556 557 // While the mix policy is generally faster, the prime policy is a lot 558 // faster when a large number consecutive integers are used, because 559 // there are no collisions. Since that is probably quite common, use 560 // prime policy for integeral types. But not the smaller ones, as they 561 // don't have enough unique values for this to be an issue. 562 563 template <> 564 struct pick_policy<int> { 565 typedef prime_policy<std::size_t> type; 566 }; 567 568 template <> 569 struct pick_policy<unsigned int> { 570 typedef prime_policy<std::size_t> type; 571 }; 572 573 template <> 574 struct pick_policy<long> { 575 typedef prime_policy<std::size_t> type; 576 }; 577 578 template <> 579 struct pick_policy<unsigned long> { 580 typedef prime_policy<std::size_t> type; 581 }; 582 583 // TODO: Maybe not if std::size_t is smaller than long long. 584 #if !defined(BOOST_NO_LONG_LONG) 585 template <> 586 struct pick_policy<long long> { 587 typedef prime_policy<std::size_t> type; 588 }; 589 590 template <> 591 struct pick_policy<unsigned long long> { 592 typedef prime_policy<std::size_t> type; 593 }; 594 #endif 595 596 //////////////////////////////////////////////////////////////////////////// 597 // Functions 598 599 // Assigning and swapping the equality and hash function objects 600 // needs strong exception safety. To implement that normally we'd 601 // require one of them to be known to not throw and the other to 602 // guarantee strong exception safety. Unfortunately they both only 603 // have basic exception safety. So to acheive strong exception 604 // safety we have storage space for two copies, and assign the new 605 // copies to the unused space. Then switch to using that to use 606 // them. This is implemented in 'set_hash_functions' which 607 // atomically assigns the new function objects in a strongly 608 // exception safe manner. 609 610 template <class H, class P, bool NoThrowMoveAssign> 611 class set_hash_functions; 612 613 template <class H, class P> 614 class functions 615 { 616 public: 617 static const bool nothrow_move_assignable = 618 boost::is_nothrow_move_assignable<H>::value && 619 boost::is_nothrow_move_assignable<P>::value; 620 static const bool nothrow_move_constructible = 621 boost::is_nothrow_move_constructible<H>::value && 622 boost::is_nothrow_move_constructible<P>::value; 623 624 private: 625 friend class boost::unordered::detail::set_hash_functions<H, P, 626 nothrow_move_assignable>; 627 functions& operator=(functions const&); 628 629 typedef compressed<H, P> function_pair; 630 631 typedef typename boost::aligned_storage< 632 sizeof(function_pair), 633 boost::alignment_of<function_pair>::value>::type aligned_function; 634 635 bool current_; // The currently active functions. 636 aligned_function funcs_[2]; 637 current() const638 function_pair const& current() const { 639 return *static_cast<function_pair const*>( 640 static_cast<void const*>(&funcs_[current_])); 641 } 642 current()643 function_pair& current() { 644 return *static_cast<function_pair*>( 645 static_cast<void*>(&funcs_[current_])); 646 } 647 construct(bool which,H const & hf,P const & eq)648 void construct(bool which, H const& hf, P const& eq) 649 { 650 new((void*) &funcs_[which]) function_pair(hf, eq); 651 } 652 construct(bool which,function_pair const & f,boost::unordered::detail::false_type=boost::unordered::detail::false_type ())653 void construct(bool which, function_pair const& f, 654 boost::unordered::detail::false_type = 655 boost::unordered::detail::false_type()) 656 { 657 new((void*) &funcs_[which]) function_pair(f); 658 } 659 construct(bool which,function_pair & f,boost::unordered::detail::true_type)660 void construct(bool which, function_pair& f, 661 boost::unordered::detail::true_type) 662 { 663 new((void*) &funcs_[which]) function_pair(f, 664 boost::unordered::detail::move_tag()); 665 } 666 destroy(bool which)667 void destroy(bool which) 668 { 669 boost::unordered::detail::func::destroy((function_pair*)(&funcs_[which])); 670 } 671 672 public: 673 674 typedef boost::unordered::detail::set_hash_functions<H, P, 675 nothrow_move_assignable> set_hash_functions; 676 functions(H const & hf,P const & eq)677 functions(H const& hf, P const& eq) 678 : current_(false) 679 { 680 construct(current_, hf, eq); 681 } 682 functions(functions const & bf)683 functions(functions const& bf) 684 : current_(false) 685 { 686 construct(current_, bf.current()); 687 } 688 functions(functions & bf,boost::unordered::detail::move_tag)689 functions(functions& bf, boost::unordered::detail::move_tag) 690 : current_(false) 691 { 692 construct(current_, bf.current(), 693 boost::unordered::detail::integral_constant<bool, 694 nothrow_move_constructible>()); 695 } 696 ~functions()697 ~functions() { 698 this->destroy(current_); 699 } 700 hash_function() const701 H const& hash_function() const { 702 return current().first(); 703 } 704 key_eq() const705 P const& key_eq() const { 706 return current().second(); 707 } 708 }; 709 710 template <class H, class P> 711 class set_hash_functions<H, P, false> 712 { 713 set_hash_functions(set_hash_functions const&); 714 set_hash_functions& operator=(set_hash_functions const&); 715 716 typedef functions<H, P> functions_type; 717 718 functions_type& functions_; 719 bool tmp_functions_; 720 721 public: 722 set_hash_functions(functions_type & f,H const & h,P const & p)723 set_hash_functions(functions_type& f, H const& h, P const& p) 724 : functions_(f), 725 tmp_functions_(!f.current_) 726 { 727 f.construct(tmp_functions_, h, p); 728 } 729 set_hash_functions(functions_type & f,functions_type const & other)730 set_hash_functions(functions_type& f, functions_type const& other) 731 : functions_(f), 732 tmp_functions_(!f.current_) 733 { 734 f.construct(tmp_functions_, other.current()); 735 } 736 ~set_hash_functions()737 ~set_hash_functions() 738 { 739 functions_.destroy(tmp_functions_); 740 } 741 commit()742 void commit() 743 { 744 functions_.current_ = tmp_functions_; 745 tmp_functions_ = !tmp_functions_; 746 } 747 }; 748 749 template <class H, class P> 750 class set_hash_functions<H, P, true> 751 { 752 set_hash_functions(set_hash_functions const&); 753 set_hash_functions& operator=(set_hash_functions const&); 754 755 typedef functions<H, P> functions_type; 756 757 functions_type& functions_; 758 H hash_; 759 P pred_; 760 761 public: 762 set_hash_functions(functions_type & f,H const & h,P const & p)763 set_hash_functions(functions_type& f, H const& h, P const& p) : 764 functions_(f), 765 hash_(h), 766 pred_(p) {} 767 set_hash_functions(functions_type & f,functions_type const & other)768 set_hash_functions(functions_type& f, functions_type const& other) : 769 functions_(f), 770 hash_(other.hash_function()), 771 pred_(other.key_eq()) {} 772 commit()773 void commit() 774 { 775 functions_.current().first() = boost::move(hash_); 776 functions_.current().second() = boost::move(pred_); 777 } 778 }; 779 780 //////////////////////////////////////////////////////////////////////////// 781 // rvalue parameters when type can't be a BOOST_RV_REF(T) parameter 782 // e.g. for int 783 784 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 785 # define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T) 786 #else 787 struct please_ignore_this_overload { 788 typedef please_ignore_this_overload type; 789 }; 790 791 template <typename T> 792 struct rv_ref_impl { 793 typedef BOOST_RV_REF(T) type; 794 }; 795 796 template <typename T> 797 struct rv_ref : 798 boost::detail::if_true< 799 boost::is_class<T>::value 800 >::BOOST_NESTED_TEMPLATE then < 801 boost::unordered::detail::rv_ref_impl<T>, 802 please_ignore_this_overload 803 >::type 804 {}; 805 806 # define BOOST_UNORDERED_RV_REF(T) \ 807 typename boost::unordered::detail::rv_ref<T>::type 808 #endif 809 }}} 810 811 #endif 812