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_ALL_HPP_INCLUDED 8 #define BOOST_UNORDERED_DETAIL_ALL_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/buckets.hpp> 16 #include <boost/unordered/detail/util.hpp> 17 #include <boost/type_traits/aligned_storage.hpp> 18 #include <boost/type_traits/alignment_of.hpp> 19 #include <cmath> 20 21 #if defined(BOOST_MSVC) 22 #pragma warning(push) 23 #pragma warning(disable:4127) // conditional expression is constant 24 #endif 25 26 #if defined(BOOST_UNORDERED_DEPRECATED_EQUALITY) 27 28 #if defined(__EDG__) 29 #elif defined(_MSC_VER) || defined(__BORLANDC__) || defined(__DMC__) 30 #pragma message("Warning: BOOST_UNORDERED_DEPRECATED_EQUALITY is no longer supported.") 31 #elif defined(__GNUC__) || defined(__HP_aCC) || \ 32 defined(__SUNPRO_CC) || defined(__IBMCPP__) 33 #warning "BOOST_UNORDERED_DEPRECATED_EQUALITY is no longer supported." 34 #endif 35 36 #endif 37 38 namespace boost { namespace unordered { namespace detail { 39 40 //////////////////////////////////////////////////////////////////////////// 41 // convert double to std::size_t 42 double_to_size(double f)43 inline std::size_t double_to_size(double f) 44 { 45 return f >= static_cast<double>( 46 (std::numeric_limits<std::size_t>::max)()) ? 47 (std::numeric_limits<std::size_t>::max)() : 48 static_cast<std::size_t>(f); 49 } 50 51 // The space used to store values in a node. 52 53 template <typename ValueType> 54 struct value_base 55 { 56 typedef ValueType value_type; 57 58 typename boost::aligned_storage< 59 sizeof(value_type), 60 boost::alignment_of<value_type>::value>::type data_; 61 addressboost::unordered::detail::value_base62 void* address() { 63 return this; 64 } 65 valueboost::unordered::detail::value_base66 value_type& value() { 67 return *(ValueType*) this; 68 } 69 value_ptrboost::unordered::detail::value_base70 value_type* value_ptr() { 71 return (ValueType*) this; 72 } 73 74 private: 75 76 value_base& operator=(value_base const&); 77 }; 78 79 template <typename NodeAlloc> 80 struct copy_nodes 81 { 82 typedef boost::unordered::detail::allocator_traits<NodeAlloc> 83 node_allocator_traits; 84 85 node_constructor<NodeAlloc> constructor; 86 copy_nodesboost::unordered::detail::copy_nodes87 explicit copy_nodes(NodeAlloc& a) : constructor(a) {} 88 createboost::unordered::detail::copy_nodes89 typename node_allocator_traits::pointer create( 90 typename node_allocator_traits::value_type::value_type const& v) 91 { 92 constructor.construct_with_value2(v); 93 return constructor.release(); 94 } 95 }; 96 97 template <typename NodeAlloc> 98 struct move_nodes 99 { 100 typedef boost::unordered::detail::allocator_traits<NodeAlloc> 101 node_allocator_traits; 102 103 node_constructor<NodeAlloc> constructor; 104 move_nodesboost::unordered::detail::move_nodes105 explicit move_nodes(NodeAlloc& a) : constructor(a) {} 106 createboost::unordered::detail::move_nodes107 typename node_allocator_traits::pointer create( 108 typename node_allocator_traits::value_type::value_type& v) 109 { 110 constructor.construct_with_value2(boost::move(v)); 111 return constructor.release(); 112 } 113 }; 114 115 template <typename Buckets> 116 struct assign_nodes 117 { 118 node_holder<typename Buckets::node_allocator> holder; 119 assign_nodesboost::unordered::detail::assign_nodes120 explicit assign_nodes(Buckets& b) : holder(b) {} 121 createboost::unordered::detail::assign_nodes122 typename Buckets::node_pointer create( 123 typename Buckets::value_type const& v) 124 { 125 return holder.copy_of(v); 126 } 127 }; 128 129 template <typename Buckets> 130 struct move_assign_nodes 131 { 132 node_holder<typename Buckets::node_allocator> holder; 133 move_assign_nodesboost::unordered::detail::move_assign_nodes134 explicit move_assign_nodes(Buckets& b) : holder(b) {} 135 createboost::unordered::detail::move_assign_nodes136 typename Buckets::node_pointer create( 137 typename Buckets::value_type& v) 138 { 139 return holder.move_copy_of(v); 140 } 141 }; 142 143 template <typename Types> 144 struct table : 145 boost::unordered::detail::functions< 146 typename Types::hasher, 147 typename Types::key_equal> 148 { 149 private: 150 table(table const&); 151 table& operator=(table const&); 152 public: 153 typedef typename Types::node node; 154 typedef typename Types::bucket bucket; 155 typedef typename Types::hasher hasher; 156 typedef typename Types::key_equal key_equal; 157 typedef typename Types::key_type key_type; 158 typedef typename Types::extractor extractor; 159 typedef typename Types::value_type value_type; 160 typedef typename Types::table table_impl; 161 typedef typename Types::link_pointer link_pointer; 162 typedef typename Types::policy policy; 163 164 typedef boost::unordered::detail::functions< 165 typename Types::hasher, 166 typename Types::key_equal> functions; 167 typedef typename functions::set_hash_functions set_hash_functions; 168 169 typedef typename Types::allocator allocator; 170 typedef typename boost::unordered::detail:: 171 rebind_wrap<allocator, node>::type node_allocator; 172 typedef typename boost::unordered::detail:: 173 rebind_wrap<allocator, bucket>::type bucket_allocator; 174 typedef boost::unordered::detail::allocator_traits<node_allocator> 175 node_allocator_traits; 176 typedef boost::unordered::detail::allocator_traits<bucket_allocator> 177 bucket_allocator_traits; 178 typedef typename node_allocator_traits::pointer 179 node_pointer; 180 typedef typename node_allocator_traits::const_pointer 181 const_node_pointer; 182 typedef typename bucket_allocator_traits::pointer 183 bucket_pointer; 184 typedef boost::unordered::detail::node_constructor<node_allocator> 185 node_constructor; 186 187 typedef boost::unordered::iterator_detail:: 188 iterator<node> iterator; 189 typedef boost::unordered::iterator_detail:: 190 c_iterator<node, const_node_pointer> c_iterator; 191 typedef boost::unordered::iterator_detail:: 192 l_iterator<node, policy> l_iterator; 193 typedef boost::unordered::iterator_detail:: 194 cl_iterator<node, const_node_pointer, policy> cl_iterator; 195 196 //////////////////////////////////////////////////////////////////////// 197 // Members 198 199 boost::unordered::detail::compressed<bucket_allocator, node_allocator> 200 allocators_; 201 std::size_t bucket_count_; 202 std::size_t size_; 203 float mlf_; 204 std::size_t max_load_; 205 bucket_pointer buckets_; 206 207 //////////////////////////////////////////////////////////////////////// 208 // Data access 209 bucket_allocboost::unordered::detail::table210 bucket_allocator const& bucket_alloc() const 211 { 212 return allocators_.first(); 213 } 214 node_allocboost::unordered::detail::table215 node_allocator const& node_alloc() const 216 { 217 return allocators_.second(); 218 } 219 bucket_allocboost::unordered::detail::table220 bucket_allocator& bucket_alloc() 221 { 222 return allocators_.first(); 223 } 224 node_allocboost::unordered::detail::table225 node_allocator& node_alloc() 226 { 227 return allocators_.second(); 228 } 229 max_bucket_countboost::unordered::detail::table230 std::size_t max_bucket_count() const 231 { 232 // -1 to account for the start bucket. 233 return policy::prev_bucket_count( 234 bucket_allocator_traits::max_size(bucket_alloc()) - 1); 235 } 236 get_bucketboost::unordered::detail::table237 bucket_pointer get_bucket(std::size_t bucket_index) const 238 { 239 BOOST_ASSERT(buckets_); 240 return buckets_ + static_cast<std::ptrdiff_t>(bucket_index); 241 } 242 get_previous_startboost::unordered::detail::table243 link_pointer get_previous_start() const 244 { 245 return get_bucket(bucket_count_)->first_from_start(); 246 } 247 get_previous_startboost::unordered::detail::table248 link_pointer get_previous_start(std::size_t bucket_index) const 249 { 250 return get_bucket(bucket_index)->next_; 251 } 252 beginboost::unordered::detail::table253 iterator begin() const 254 { 255 return size_ ? iterator(get_previous_start()->next_) : iterator(); 256 } 257 beginboost::unordered::detail::table258 iterator begin(std::size_t bucket_index) const 259 { 260 if (!size_) return iterator(); 261 link_pointer prev = get_previous_start(bucket_index); 262 return prev ? iterator(prev->next_) : iterator(); 263 } 264 hash_to_bucketboost::unordered::detail::table265 std::size_t hash_to_bucket(std::size_t hash_value) const 266 { 267 return policy::to_bucket(bucket_count_, hash_value); 268 } 269 load_factorboost::unordered::detail::table270 float load_factor() const 271 { 272 BOOST_ASSERT(bucket_count_ != 0); 273 return static_cast<float>(size_) 274 / static_cast<float>(bucket_count_); 275 } 276 bucket_sizeboost::unordered::detail::table277 std::size_t bucket_size(std::size_t index) const 278 { 279 iterator it = begin(index); 280 if (!it.node_) return 0; 281 282 std::size_t count = 0; 283 while(it.node_ && hash_to_bucket(it.node_->hash_) == index) 284 { 285 ++count; 286 ++it; 287 } 288 289 return count; 290 } 291 292 //////////////////////////////////////////////////////////////////////// 293 // Load methods 294 max_sizeboost::unordered::detail::table295 std::size_t max_size() const 296 { 297 using namespace std; 298 299 // size < mlf_ * count 300 return boost::unordered::detail::double_to_size(ceil( 301 static_cast<double>(mlf_) * 302 static_cast<double>(max_bucket_count()) 303 )) - 1; 304 } 305 recalculate_max_loadboost::unordered::detail::table306 void recalculate_max_load() 307 { 308 using namespace std; 309 310 // From 6.3.1/13: 311 // Only resize when size >= mlf_ * count 312 max_load_ = buckets_ ? boost::unordered::detail::double_to_size(ceil( 313 static_cast<double>(mlf_) * 314 static_cast<double>(bucket_count_) 315 )) : 0; 316 317 } 318 max_load_factorboost::unordered::detail::table319 void max_load_factor(float z) 320 { 321 BOOST_ASSERT(z > 0); 322 mlf_ = (std::max)(z, minimum_max_load_factor); 323 recalculate_max_load(); 324 } 325 min_buckets_for_sizeboost::unordered::detail::table326 std::size_t min_buckets_for_size(std::size_t size) const 327 { 328 BOOST_ASSERT(mlf_ >= minimum_max_load_factor); 329 330 using namespace std; 331 332 // From 6.3.1/13: 333 // size < mlf_ * count 334 // => count > size / mlf_ 335 // 336 // Or from rehash post-condition: 337 // count > size / mlf_ 338 339 return policy::new_bucket_count( 340 boost::unordered::detail::double_to_size(floor( 341 static_cast<double>(size) / 342 static_cast<double>(mlf_))) + 1); 343 } 344 345 //////////////////////////////////////////////////////////////////////// 346 // Constructors 347 tableboost::unordered::detail::table348 table(std::size_t num_buckets, 349 hasher const& hf, 350 key_equal const& eq, 351 node_allocator const& a) : 352 functions(hf, eq), 353 allocators_(a,a), 354 bucket_count_(policy::new_bucket_count(num_buckets)), 355 size_(0), 356 mlf_(1.0f), 357 max_load_(0), 358 buckets_() 359 {} 360 tableboost::unordered::detail::table361 table(table const& x, node_allocator const& a) : 362 functions(x), 363 allocators_(a,a), 364 bucket_count_(x.min_buckets_for_size(x.size_)), 365 size_(0), 366 mlf_(x.mlf_), 367 max_load_(0), 368 buckets_() 369 {} 370 tableboost::unordered::detail::table371 table(table& x, boost::unordered::detail::move_tag m) : 372 functions(x, m), 373 allocators_(x.allocators_, m), 374 bucket_count_(x.bucket_count_), 375 size_(x.size_), 376 mlf_(x.mlf_), 377 max_load_(x.max_load_), 378 buckets_(x.buckets_) 379 { 380 x.buckets_ = bucket_pointer(); 381 x.size_ = 0; 382 x.max_load_ = 0; 383 } 384 tableboost::unordered::detail::table385 table(table& x, node_allocator const& a, 386 boost::unordered::detail::move_tag m) : 387 functions(x, m), 388 allocators_(a, a), 389 bucket_count_(x.bucket_count_), 390 size_(0), 391 mlf_(x.mlf_), 392 max_load_(x.max_load_), 393 buckets_() 394 {} 395 396 //////////////////////////////////////////////////////////////////////// 397 // Initialisation. 398 initboost::unordered::detail::table399 void init(table const& x) 400 { 401 if (x.size_) { 402 create_buckets(bucket_count_); 403 copy_nodes<node_allocator> node_creator(node_alloc()); 404 table_impl::fill_buckets(x.begin(), *this, node_creator); 405 } 406 } 407 move_initboost::unordered::detail::table408 void move_init(table& x) 409 { 410 if(node_alloc() == x.node_alloc()) { 411 move_buckets_from(x); 412 } 413 else if(x.size_) { 414 // TODO: Could pick new bucket size? 415 create_buckets(bucket_count_); 416 417 move_nodes<node_allocator> node_creator(node_alloc()); 418 node_holder<node_allocator> nodes(x); 419 table_impl::fill_buckets(nodes.begin(), *this, node_creator); 420 } 421 } 422 423 //////////////////////////////////////////////////////////////////////// 424 // Create buckets 425 create_bucketsboost::unordered::detail::table426 void create_buckets(std::size_t new_count) 427 { 428 boost::unordered::detail::array_constructor<bucket_allocator> 429 constructor(bucket_alloc()); 430 431 // Creates an extra bucket to act as the start node. 432 constructor.construct(bucket(), new_count + 1); 433 434 if (buckets_) 435 { 436 // Copy the nodes to the new buckets, including the dummy 437 // node if there is one. 438 (constructor.get() + 439 static_cast<std::ptrdiff_t>(new_count))->next_ = 440 (buckets_ + static_cast<std::ptrdiff_t>( 441 bucket_count_))->next_; 442 destroy_buckets(); 443 } 444 else if (bucket::extra_node) 445 { 446 node_constructor a(node_alloc()); 447 a.construct(); 448 449 (constructor.get() + 450 static_cast<std::ptrdiff_t>(new_count))->next_ = 451 a.release(); 452 } 453 454 bucket_count_ = new_count; 455 buckets_ = constructor.release(); 456 recalculate_max_load(); 457 } 458 459 //////////////////////////////////////////////////////////////////////// 460 // Swap and Move 461 swap_allocatorsboost::unordered::detail::table462 void swap_allocators(table& other, false_type) 463 { 464 boost::unordered::detail::func::ignore_unused_variable_warning(other); 465 466 // According to 23.2.1.8, if propagate_on_container_swap is 467 // false the behaviour is undefined unless the allocators 468 // are equal. 469 BOOST_ASSERT(node_alloc() == other.node_alloc()); 470 } 471 swap_allocatorsboost::unordered::detail::table472 void swap_allocators(table& other, true_type) 473 { 474 allocators_.swap(other.allocators_); 475 } 476 477 // Only swaps the allocators if propagate_on_container_swap swapboost::unordered::detail::table478 void swap(table& x) 479 { 480 set_hash_functions op1(*this, x); 481 set_hash_functions op2(x, *this); 482 483 // I think swap can throw if Propagate::value, 484 // since the allocators' swap can throw. Not sure though. 485 swap_allocators(x, 486 boost::unordered::detail::integral_constant<bool, 487 allocator_traits<node_allocator>:: 488 propagate_on_container_swap::value>()); 489 490 boost::swap(buckets_, x.buckets_); 491 boost::swap(bucket_count_, x.bucket_count_); 492 boost::swap(size_, x.size_); 493 std::swap(mlf_, x.mlf_); 494 std::swap(max_load_, x.max_load_); 495 op1.commit(); 496 op2.commit(); 497 } 498 move_buckets_fromboost::unordered::detail::table499 void move_buckets_from(table& other) 500 { 501 BOOST_ASSERT(node_alloc() == other.node_alloc()); 502 BOOST_ASSERT(!buckets_); 503 buckets_ = other.buckets_; 504 bucket_count_ = other.bucket_count_; 505 size_ = other.size_; 506 other.buckets_ = bucket_pointer(); 507 other.size_ = 0; 508 other.max_load_ = 0; 509 } 510 511 //////////////////////////////////////////////////////////////////////// 512 // Delete/destruct 513 ~tableboost::unordered::detail::table514 ~table() 515 { 516 delete_buckets(); 517 } 518 delete_nodeboost::unordered::detail::table519 void delete_node(link_pointer prev) 520 { 521 node_pointer n = static_cast<node_pointer>(prev->next_); 522 prev->next_ = n->next_; 523 524 boost::unordered::detail::func::destroy_value_impl(node_alloc(), 525 n->value_ptr()); 526 boost::unordered::detail::func::destroy(boost::addressof(*n)); 527 node_allocator_traits::deallocate(node_alloc(), n, 1); 528 --size_; 529 } 530 delete_nodesboost::unordered::detail::table531 std::size_t delete_nodes(link_pointer prev, link_pointer end) 532 { 533 BOOST_ASSERT(prev->next_ != end); 534 535 std::size_t count = 0; 536 537 do { 538 delete_node(prev); 539 ++count; 540 } while (prev->next_ != end); 541 542 return count; 543 } 544 delete_bucketsboost::unordered::detail::table545 void delete_buckets() 546 { 547 if(buckets_) { 548 if (size_) delete_nodes(get_previous_start(), link_pointer()); 549 550 if (bucket::extra_node) { 551 node_pointer n = static_cast<node_pointer>( 552 get_bucket(bucket_count_)->next_); 553 boost::unordered::detail::func::destroy( 554 boost::addressof(*n)); 555 node_allocator_traits::deallocate(node_alloc(), n, 1); 556 } 557 558 destroy_buckets(); 559 buckets_ = bucket_pointer(); 560 max_load_ = 0; 561 } 562 563 BOOST_ASSERT(!size_); 564 } 565 clearboost::unordered::detail::table566 void clear() 567 { 568 if (!size_) return; 569 570 delete_nodes(get_previous_start(), link_pointer()); 571 clear_buckets(); 572 573 BOOST_ASSERT(!size_); 574 } 575 clear_bucketsboost::unordered::detail::table576 void clear_buckets() 577 { 578 bucket_pointer end = get_bucket(bucket_count_); 579 for(bucket_pointer it = buckets_; it != end; ++it) 580 { 581 it->next_ = node_pointer(); 582 } 583 } 584 destroy_bucketsboost::unordered::detail::table585 void destroy_buckets() 586 { 587 bucket_pointer end = get_bucket(bucket_count_ + 1); 588 for(bucket_pointer it = buckets_; it != end; ++it) 589 { 590 boost::unordered::detail::func::destroy( 591 boost::addressof(*it)); 592 } 593 594 bucket_allocator_traits::deallocate(bucket_alloc(), 595 buckets_, bucket_count_ + 1); 596 } 597 598 //////////////////////////////////////////////////////////////////////// 599 // Fix buckets after delete 600 // 601 fix_bucketboost::unordered::detail::table602 std::size_t fix_bucket(std::size_t bucket_index, link_pointer prev) 603 { 604 link_pointer end = prev->next_; 605 std::size_t bucket_index2 = bucket_index; 606 607 if (end) 608 { 609 bucket_index2 = hash_to_bucket( 610 static_cast<node_pointer>(end)->hash_); 611 612 // If begin and end are in the same bucket, then 613 // there's nothing to do. 614 if (bucket_index == bucket_index2) return bucket_index2; 615 616 // Update the bucket containing end. 617 get_bucket(bucket_index2)->next_ = prev; 618 } 619 620 // Check if this bucket is now empty. 621 bucket_pointer this_bucket = get_bucket(bucket_index); 622 if (this_bucket->next_ == prev) 623 this_bucket->next_ = link_pointer(); 624 625 return bucket_index2; 626 } 627 628 //////////////////////////////////////////////////////////////////////// 629 // Assignment 630 assignboost::unordered::detail::table631 void assign(table const& x) 632 { 633 if (this != boost::addressof(x)) 634 { 635 assign(x, 636 boost::unordered::detail::integral_constant<bool, 637 allocator_traits<node_allocator>:: 638 propagate_on_container_copy_assignment::value>()); 639 } 640 } 641 assignboost::unordered::detail::table642 void assign(table const& x, false_type) 643 { 644 // Strong exception safety. 645 set_hash_functions new_func_this(*this, x); 646 new_func_this.commit(); 647 mlf_ = x.mlf_; 648 recalculate_max_load(); 649 650 if (!size_ && !x.size_) return; 651 652 if (x.size_ >= max_load_) { 653 create_buckets(min_buckets_for_size(x.size_)); 654 } 655 else { 656 clear_buckets(); 657 } 658 659 // assign_nodes takes ownership of the container's elements, 660 // assigning to them if possible, and deleting any that are 661 // left over. 662 assign_nodes<table> node_creator(*this); 663 table_impl::fill_buckets(x.begin(), *this, node_creator); 664 } 665 assignboost::unordered::detail::table666 void assign(table const& x, true_type) 667 { 668 if (node_alloc() == x.node_alloc()) { 669 allocators_.assign(x.allocators_); 670 assign(x, false_type()); 671 } 672 else { 673 set_hash_functions new_func_this(*this, x); 674 675 // Delete everything with current allocators before assigning 676 // the new ones. 677 delete_buckets(); 678 allocators_.assign(x.allocators_); 679 680 // Copy over other data, all no throw. 681 new_func_this.commit(); 682 mlf_ = x.mlf_; 683 bucket_count_ = min_buckets_for_size(x.size_); 684 max_load_ = 0; 685 686 // Finally copy the elements. 687 if (x.size_) { 688 create_buckets(bucket_count_); 689 copy_nodes<node_allocator> node_creator(node_alloc()); 690 table_impl::fill_buckets(x.begin(), *this, node_creator); 691 } 692 } 693 } 694 move_assignboost::unordered::detail::table695 void move_assign(table& x) 696 { 697 if (this != boost::addressof(x)) 698 { 699 move_assign(x, 700 boost::unordered::detail::integral_constant<bool, 701 allocator_traits<node_allocator>:: 702 propagate_on_container_move_assignment::value>()); 703 } 704 } 705 move_assignboost::unordered::detail::table706 void move_assign(table& x, true_type) 707 { 708 delete_buckets(); 709 allocators_.move_assign(x.allocators_); 710 move_assign_no_alloc(x); 711 } 712 move_assignboost::unordered::detail::table713 void move_assign(table& x, false_type) 714 { 715 if (node_alloc() == x.node_alloc()) { 716 delete_buckets(); 717 move_assign_no_alloc(x); 718 } 719 else { 720 set_hash_functions new_func_this(*this, x); 721 new_func_this.commit(); 722 mlf_ = x.mlf_; 723 recalculate_max_load(); 724 725 if (!size_ && !x.size_) return; 726 727 if (x.size_ >= max_load_) { 728 create_buckets(min_buckets_for_size(x.size_)); 729 } 730 else { 731 clear_buckets(); 732 } 733 734 // move_assign_nodes takes ownership of the container's 735 // elements, assigning to them if possible, and deleting 736 // any that are left over. 737 move_assign_nodes<table> node_creator(*this); 738 node_holder<node_allocator> nodes(x); 739 table_impl::fill_buckets(nodes.begin(), *this, node_creator); 740 } 741 } 742 move_assign_no_allocboost::unordered::detail::table743 void move_assign_no_alloc(table& x) 744 { 745 set_hash_functions new_func_this(*this, x); 746 // No throw from here. 747 mlf_ = x.mlf_; 748 max_load_ = x.max_load_; 749 move_buckets_from(x); 750 new_func_this.commit(); 751 } 752 753 // Accessors 754 get_keyboost::unordered::detail::table755 key_type const& get_key(value_type const& x) const 756 { 757 return extractor::extract(x); 758 } 759 hashboost::unordered::detail::table760 std::size_t hash(key_type const& k) const 761 { 762 return policy::apply_hash(this->hash_function(), k); 763 } 764 765 // Find Node 766 767 template <typename Key, typename Hash, typename Pred> generic_find_nodeboost::unordered::detail::table768 iterator generic_find_node( 769 Key const& k, 770 Hash const& hf, 771 Pred const& eq) const 772 { 773 return static_cast<table_impl const*>(this)-> 774 find_node_impl(policy::apply_hash(hf, k), k, eq); 775 } 776 find_nodeboost::unordered::detail::table777 iterator find_node( 778 std::size_t key_hash, 779 key_type const& k) const 780 { 781 return static_cast<table_impl const*>(this)-> 782 find_node_impl(key_hash, k, this->key_eq()); 783 } 784 find_nodeboost::unordered::detail::table785 iterator find_node(key_type const& k) const 786 { 787 return static_cast<table_impl const*>(this)-> 788 find_node_impl(hash(k), k, this->key_eq()); 789 } 790 find_matching_nodeboost::unordered::detail::table791 iterator find_matching_node(iterator n) const 792 { 793 // TODO: Does this apply to C++11? 794 // 795 // For some stupid reason, I decided to support equality comparison 796 // when different hash functions are used. So I can't use the hash 797 // value from the node here. 798 799 return find_node(get_key(*n)); 800 } 801 802 // Reserve and rehash 803 804 void reserve_for_insert(std::size_t); 805 void rehash(std::size_t); 806 void reserve(std::size_t); 807 }; 808 809 //////////////////////////////////////////////////////////////////////////// 810 // Reserve & Rehash 811 812 // basic exception safety 813 template <typename Types> reserve_for_insert(std::size_t size)814 inline void table<Types>::reserve_for_insert(std::size_t size) 815 { 816 if (!buckets_) { 817 create_buckets((std::max)(bucket_count_, 818 min_buckets_for_size(size))); 819 } 820 // According to the standard this should be 'size >= max_load_', 821 // but I think this is better, defect report filed. 822 else if(size > max_load_) { 823 std::size_t num_buckets 824 = min_buckets_for_size((std::max)(size, 825 size_ + (size_ >> 1))); 826 827 if (num_buckets != bucket_count_) 828 static_cast<table_impl*>(this)->rehash_impl(num_buckets); 829 } 830 } 831 832 // if hash function throws, basic exception safety 833 // strong otherwise. 834 835 template <typename Types> rehash(std::size_t min_buckets)836 inline void table<Types>::rehash(std::size_t min_buckets) 837 { 838 using namespace std; 839 840 if(!size_) { 841 delete_buckets(); 842 bucket_count_ = policy::new_bucket_count(min_buckets); 843 } 844 else { 845 min_buckets = policy::new_bucket_count((std::max)(min_buckets, 846 boost::unordered::detail::double_to_size(floor( 847 static_cast<double>(size_) / 848 static_cast<double>(mlf_))) + 1)); 849 850 if(min_buckets != bucket_count_) 851 static_cast<table_impl*>(this)->rehash_impl(min_buckets); 852 } 853 } 854 855 template <typename Types> reserve(std::size_t num_elements)856 inline void table<Types>::reserve(std::size_t num_elements) 857 { 858 rehash(static_cast<std::size_t>( 859 std::ceil(static_cast<double>(num_elements) / mlf_))); 860 } 861 }}} 862 863 #if defined(BOOST_MSVC) 864 #pragma warning(pop) 865 #endif 866 867 #endif 868