1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2006-2009 4 // 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 http://www.boost.org/libs/intrusive for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 #ifndef BOOST_INTRUSIVE_HASHTABLE_HPP 13 #define BOOST_INTRUSIVE_HASHTABLE_HPP 14 15 #include <boost/intrusive/detail/config_begin.hpp> 16 //std C++ 17 #include <functional> //std::equal_to 18 #include <utility> //std::pair 19 #include <algorithm> //std::swap, std::lower_bound, std::upper_bound 20 #include <cstddef> //std::size_t 21 #include <iterator> //std::iterator_traits 22 //boost 23 #include <boost/intrusive/detail/assert.hpp> 24 #include <boost/static_assert.hpp> 25 #include <boost/functional/hash.hpp> 26 #include <boost/pointer_cast.hpp> 27 //General intrusive utilities 28 #include <boost/intrusive/intrusive_fwd.hpp> 29 #include <boost/intrusive/detail/pointer_to_other.hpp> 30 #include <boost/intrusive/detail/hashtable_node.hpp> 31 #include <boost/intrusive/detail/transform_iterator.hpp> 32 #include <boost/intrusive/link_mode.hpp> 33 #include <boost/intrusive/detail/ebo_functor_holder.hpp> 34 #include <boost/intrusive/detail/clear_on_destructor_base.hpp> 35 //Implementation utilities 36 #include <boost/intrusive/trivial_value_traits.hpp> 37 #include <boost/intrusive/unordered_set_hook.hpp> 38 #include <boost/intrusive/slist.hpp> 39 #include <boost/intrusive/detail/mpl.hpp> 40 41 namespace boost { 42 namespace intrusive { 43 44 /// @cond 45 46 namespace detail { 47 48 struct hash_bool_flags 49 { 50 static const std::size_t unique_keys_pos = 1u; 51 static const std::size_t constant_time_size_pos = 2u; 52 static const std::size_t power_2_buckets_pos = 4u; 53 static const std::size_t cache_begin_pos = 8u; 54 static const std::size_t compare_hash_pos = 16u; 55 static const std::size_t incremental_pos = 32u; 56 }; 57 58 template 59 < class ValueTraits 60 , class Hash 61 , class Equal 62 , class SizeType 63 , class BucketTraits 64 , std::size_t BoolFlags 65 > 66 struct usetopt 67 { 68 typedef ValueTraits value_traits; 69 typedef Hash hash; 70 typedef Equal equal; 71 typedef SizeType size_type; 72 typedef BucketTraits bucket_traits; 73 static const std::size_t bool_flags = BoolFlags; 74 }; 75 76 template 77 < class UsetOpt 78 , std::size_t BoolMask 79 > 80 struct usetopt_mask 81 { 82 typedef usetopt 83 <typename UsetOpt::value_traits 84 ,typename UsetOpt::hash 85 ,typename UsetOpt::equal 86 ,typename UsetOpt::size_type 87 ,typename UsetOpt::bucket_traits 88 ,UsetOpt::bool_flags & BoolMask 89 > type; 90 }; 91 92 template <class NodeTraits> 93 struct hash_reduced_slist_node_traits 94 { 95 template <class U> static detail::one test(...); 96 template <class U> static detail::two test(typename U::reduced_slist_node_traits* = 0); 97 static const bool value = sizeof(test<NodeTraits>(0)) == sizeof(detail::two); 98 }; 99 100 template <class NodeTraits> 101 struct apply_reduced_slist_node_traits 102 { 103 typedef typename NodeTraits::reduced_slist_node_traits type; 104 }; 105 106 template <class NodeTraits> 107 struct reduced_slist_node_traits 108 { 109 typedef typename detail::eval_if_c 110 < hash_reduced_slist_node_traits<NodeTraits>::value 111 , apply_reduced_slist_node_traits<NodeTraits> 112 , detail::identity<NodeTraits> 113 >::type type; 114 }; 115 116 template<class NodeTraits> 117 struct get_slist_impl 118 { 119 typedef trivial_value_traits<NodeTraits, normal_link> trivial_traits; 120 121 //Reducing symbol length 122 struct type : make_slist 123 < typename NodeTraits::node 124 , boost::intrusive::value_traits<trivial_traits> 125 , boost::intrusive::constant_time_size<false> 126 , boost::intrusive::size_type<std::size_t> 127 >::type 128 {}; 129 }; 130 131 template<class SupposedValueTraits> 132 struct real_from_supposed_value_traits 133 { 134 typedef typename detail::eval_if_c 135 < detail::external_value_traits_is_true 136 <SupposedValueTraits>::value 137 , detail::eval_value_traits 138 <SupposedValueTraits> 139 , detail::identity 140 <SupposedValueTraits> 141 >::type type; 142 }; 143 144 template<class SupposedValueTraits> 145 struct get_slist_impl_from_supposed_value_traits 146 { 147 typedef typename 148 real_from_supposed_value_traits 149 < SupposedValueTraits>::type real_value_traits; 150 typedef typename detail::get_node_traits 151 <real_value_traits>::type node_traits; 152 typedef typename get_slist_impl 153 <typename reduced_slist_node_traits 154 <node_traits>::type 155 >::type type; 156 }; 157 158 template<class SupposedValueTraits> 159 struct unordered_bucket_impl 160 { 161 typedef typename 162 get_slist_impl_from_supposed_value_traits 163 <SupposedValueTraits>::type slist_impl; 164 typedef detail::bucket_impl<slist_impl> implementation_defined; 165 typedef implementation_defined type; 166 }; 167 168 template<class SupposedValueTraits> 169 struct unordered_bucket_ptr_impl 170 { 171 typedef typename detail::get_node_traits 172 <SupposedValueTraits>::type::node_ptr node_ptr; 173 typedef typename unordered_bucket_impl 174 <SupposedValueTraits>::type bucket_type; 175 typedef typename boost::pointer_to_other 176 <node_ptr, bucket_type>::type implementation_defined; 177 typedef implementation_defined type; 178 }; 179 180 template <class T> 181 struct store_hash_bool 182 { 183 template<bool Add> 184 struct two_or_three {one _[2 + Add];}; 185 template <class U> static one test(...); 186 template <class U> static two_or_three<U::store_hash> test (int); 187 static const std::size_t value = sizeof(test<T>(0)); 188 }; 189 190 template <class T> 191 struct store_hash_is_true 192 { 193 static const bool value = store_hash_bool<T>::value > sizeof(one)*2; 194 }; 195 196 template <class T> 197 struct optimize_multikey_bool 198 { 199 template<bool Add> 200 struct two_or_three {one _[2 + Add];}; 201 template <class U> static one test(...); 202 template <class U> static two_or_three<U::optimize_multikey> test (int); 203 static const std::size_t value = sizeof(test<T>(0)); 204 }; 205 206 template <class T> 207 struct optimize_multikey_is_true 208 { 209 static const bool value = optimize_multikey_bool<T>::value > sizeof(one)*2; 210 }; 211 212 template<class Config> 213 struct bucket_plus_size 214 : public detail::size_holder 215 < 0 != (Config::bool_flags & hash_bool_flags::constant_time_size_pos) 216 , typename Config::size_type> 217 { 218 typedef detail::size_holder 219 < 0 != (Config::bool_flags & hash_bool_flags::constant_time_size_pos) 220 , typename Config::size_type> size_traits; 221 typedef typename Config::bucket_traits bucket_traits; 222 bucket_plus_sizeboost::intrusive::detail::bucket_plus_size223 bucket_plus_size(const bucket_traits &b_traits) 224 : bucket_traits_(b_traits) 225 {} 226 bucket_traits bucket_traits_; 227 }; 228 229 template<class Config> 230 struct bucket_hash_t 231 : public detail::ebo_functor_holder<typename Config::hash> 232 { 233 typedef typename Config::hash hasher; 234 typedef detail::size_holder 235 < 0 != (Config::bool_flags & hash_bool_flags::constant_time_size_pos) 236 , typename Config::size_type> size_traits; 237 typedef typename Config::bucket_traits bucket_traits; 238 bucket_hash_tboost::intrusive::detail::bucket_hash_t239 bucket_hash_t(const bucket_traits &b_traits, const hasher & h) 240 : detail::ebo_functor_holder<hasher>(h), bucket_plus_size_(b_traits) 241 {} 242 243 bucket_plus_size<Config> bucket_plus_size_; 244 }; 245 246 template<class Config, bool> 247 struct bucket_hash_equal_t : public detail::ebo_functor_holder<typename Config::equal> 248 { 249 typedef typename Config::equal equal; 250 typedef typename Config::hash hasher; 251 typedef typename Config::bucket_traits bucket_traits; 252 bucket_hash_equal_tboost::intrusive::detail::bucket_hash_equal_t253 bucket_hash_equal_t(const bucket_traits &b_traits, const hasher & h, const equal &e) 254 : detail::ebo_functor_holder<typename Config::equal>(e), bucket_hash(b_traits, h) 255 {} 256 bucket_hash_t<Config> bucket_hash; 257 }; 258 259 template<class Config> //cache_begin == true version 260 struct bucket_hash_equal_t<Config, true> 261 : public detail::ebo_functor_holder<typename Config::equal> 262 { 263 typedef typename Config::equal equal; 264 typedef typename Config::hash hasher; 265 typedef typename Config::bucket_traits bucket_traits; 266 typedef typename unordered_bucket_ptr_impl 267 <typename Config::value_traits>::type bucket_ptr; 268 bucket_hash_equal_tboost::intrusive::detail::bucket_hash_equal_t269 bucket_hash_equal_t(const bucket_traits &b_traits, const hasher & h, const equal &e) 270 : detail::ebo_functor_holder<typename Config::equal>(e), bucket_hash(b_traits, h) 271 {} 272 bucket_hash_t<Config> bucket_hash; 273 bucket_ptr cached_begin_; 274 }; 275 276 template<class Config> 277 struct hashtable_data_t : public Config::value_traits 278 { 279 static const std::size_t bool_flags = Config::bool_flags; 280 typedef typename Config::value_traits value_traits; 281 typedef typename Config::equal equal; 282 typedef typename Config::hash hasher; 283 typedef typename Config::bucket_traits bucket_traits; 284 hashtable_data_tboost::intrusive::detail::hashtable_data_t285 hashtable_data_t( const bucket_traits &b_traits, const hasher & h 286 , const equal &e, const value_traits &val_traits) 287 : Config::value_traits(val_traits), internal_(b_traits, h, e) 288 {} 289 typedef typename detail::usetopt_mask 290 < Config 291 , detail::hash_bool_flags::constant_time_size_pos 292 | detail::hash_bool_flags::incremental_pos 293 >::type masked_config_t; 294 struct internal 295 : public detail::size_holder 296 < 0 != (Config::bool_flags & hash_bool_flags::incremental_pos) 297 , typename Config::size_type> 298 { internalboost::intrusive::detail::hashtable_data_t::internal299 internal(const bucket_traits &b_traits, const hasher & h, const equal &e) 300 : bucket_hash_equal_(b_traits, h, e) 301 {} 302 303 bucket_hash_equal_t 304 < masked_config_t 305 , 0 != (bool_flags & hash_bool_flags::cache_begin_pos) 306 > bucket_hash_equal_; 307 } internal_; 308 }; 309 310 struct insert_commit_data_impl 311 { 312 std::size_t hash; 313 }; 314 315 template<class NodeTraits> 316 struct group_functions 317 { 318 typedef NodeTraits node_traits; 319 typedef unordered_group_adapter<node_traits> group_traits; 320 typedef typename node_traits::node_ptr node_ptr; 321 typedef typename node_traits::node node; 322 typedef typename reduced_slist_node_traits 323 <node_traits>::type reduced_node_traits; 324 typedef typename reduced_node_traits::node_ptr slist_node_ptr; 325 typedef typename reduced_node_traits::node slist_node; 326 typedef circular_slist_algorithms<group_traits> group_algorithms; 327 dcast_bucket_ptrboost::intrusive::detail::group_functions328 static node_ptr dcast_bucket_ptr(slist_node_ptr p) 329 { 330 // This still fails in gcc < 4.4 so forget about it 331 // using ::boost::static_pointer_cast; 332 // return static_pointer_cast<node>(p); 333 return node_ptr(&static_cast<node&>(*p)); 334 } 335 priv_get_bucket_before_beginboost::intrusive::detail::group_functions336 static slist_node_ptr priv_get_bucket_before_begin 337 (slist_node_ptr bucket_beg, slist_node_ptr bucket_end, node_ptr p) 338 { 339 //First find the last node of p's group. 340 //This requires checking the first node of the next group or 341 //the bucket node. 342 node_ptr prev_node = p; 343 node_ptr nxt(node_traits::get_next(p)); 344 while(!(bucket_beg <= nxt && nxt <= bucket_end) && 345 (group_traits::get_next(nxt) == prev_node)){ 346 prev_node = nxt; 347 nxt = node_traits::get_next(nxt); 348 } 349 350 //If we've reached the bucket node just return it. 351 if(bucket_beg <= nxt && nxt <= bucket_end){ 352 return nxt; 353 } 354 355 //Otherwise, iterate using group links until the bucket node 356 node_ptr first_node_of_group = nxt; 357 node_ptr last_node_group = group_traits::get_next(first_node_of_group); 358 slist_node_ptr possible_end = node_traits::get_next(last_node_group); 359 360 while(!(bucket_beg <= possible_end && possible_end <= bucket_end)){ 361 first_node_of_group = dcast_bucket_ptr(possible_end); 362 last_node_group = group_traits::get_next(first_node_of_group); 363 possible_end = node_traits::get_next(last_node_group); 364 } 365 return possible_end; 366 } 367 priv_get_prev_to_first_in_groupboost::intrusive::detail::group_functions368 static node_ptr priv_get_prev_to_first_in_group(slist_node_ptr bucket_node, node_ptr first_in_group) 369 { 370 //Just iterate using group links and obtain the node 371 //before "first_in_group)" 372 node_ptr prev_node = dcast_bucket_ptr(bucket_node); 373 node_ptr nxt(node_traits::get_next(prev_node)); 374 while(nxt != first_in_group){ 375 prev_node = group_traits::get_next(nxt); 376 nxt = node_traits::get_next(prev_node); 377 } 378 return prev_node; 379 } 380 priv_get_first_in_group_of_last_in_groupboost::intrusive::detail::group_functions381 static node_ptr priv_get_first_in_group_of_last_in_group(node_ptr last_in_group) 382 { 383 //Just iterate using group links and obtain the node 384 //before "last_in_group" 385 node_ptr possible_first = group_traits::get_next(last_in_group); 386 node_ptr possible_first_prev = group_traits::get_next(possible_first); 387 // The deleted node is at the end of the group, so the 388 // node in the group pointing to it is at the beginning 389 // of the group. Find that to change its pointer. 390 while(possible_first_prev != last_in_group){ 391 possible_first = possible_first_prev; 392 possible_first_prev = group_traits::get_next(possible_first); 393 } 394 return possible_first; 395 } 396 397 priv_erase_from_groupboost::intrusive::detail::group_functions398 static void priv_erase_from_group(slist_node_ptr end_ptr, node_ptr to_erase_ptr, detail::true_) 399 { 400 node_ptr nxt_ptr(node_traits::get_next(to_erase_ptr)); 401 node_ptr prev_in_group_ptr(group_traits::get_next(to_erase_ptr)); 402 bool last_in_group = (end_ptr == nxt_ptr) || 403 (group_traits::get_next(nxt_ptr) != to_erase_ptr); 404 bool first_in_group = node_traits::get_next(prev_in_group_ptr) != to_erase_ptr; 405 406 if(first_in_group && last_in_group){ 407 group_algorithms::init(to_erase_ptr); 408 } 409 else if(first_in_group){ 410 group_algorithms::unlink_after(nxt_ptr); 411 } 412 else if(last_in_group){ 413 node_ptr first_in_group = 414 priv_get_first_in_group_of_last_in_group(to_erase_ptr); 415 group_algorithms::unlink_after(first_in_group); 416 } 417 else{ 418 group_algorithms::unlink_after(nxt_ptr); 419 } 420 } 421 priv_erase_from_groupboost::intrusive::detail::group_functions422 static void priv_erase_from_group(slist_node_ptr, node_ptr, detail::false_) 423 {} 424 priv_get_last_in_groupboost::intrusive::detail::group_functions425 static node_ptr priv_get_last_in_group(node_ptr first_in_group, detail::true_) 426 { return group_traits::get_next(first_in_group); } 427 priv_get_last_in_groupboost::intrusive::detail::group_functions428 static node_ptr priv_get_last_in_group(node_ptr n, detail::false_) 429 { return n; } 430 }; 431 432 template<class BucketType, class SplitTraits> 433 class incremental_rehash_rollback 434 { 435 private: 436 typedef BucketType bucket_type; 437 typedef SplitTraits split_traits; 438 439 incremental_rehash_rollback(); 440 incremental_rehash_rollback & operator=(const incremental_rehash_rollback &); 441 incremental_rehash_rollback (const incremental_rehash_rollback &); 442 443 public: incremental_rehash_rollback(bucket_type & source_bucket,bucket_type & destiny_bucket,split_traits & split_traits)444 incremental_rehash_rollback 445 (bucket_type &source_bucket, bucket_type &destiny_bucket, split_traits &split_traits) 446 : source_bucket_(source_bucket), destiny_bucket_(destiny_bucket) 447 , split_traits_(split_traits), released_(false) 448 {} 449 release()450 void release() 451 { released_ = true; } 452 ~incremental_rehash_rollback()453 ~incremental_rehash_rollback() 454 { 455 if(!released_){ 456 //If an exception is thrown, just put all moved nodes back in the old bucket 457 //and move back the split mark. 458 destiny_bucket_.splice_after(destiny_bucket_.before_begin(), source_bucket_); 459 split_traits_.decrement(); 460 } 461 } 462 463 private: 464 bucket_type &source_bucket_; 465 bucket_type &destiny_bucket_; 466 split_traits &split_traits_; 467 bool released_; 468 }; 469 470 } //namespace detail { 471 472 //!This metafunction will obtain the type of a bucket 473 //!from the value_traits or hook option to be used with 474 //!a hash container. 475 template<class ValueTraitsOrHookOption> 476 struct unordered_bucket 477 : public detail::unordered_bucket_impl 478 <typename ValueTraitsOrHookOption:: 479 template pack<none>::value_traits 480 > 481 {}; 482 483 //!This metafunction will obtain the type of a bucket pointer 484 //!from the value_traits or hook option to be used with 485 //!a hash container. 486 template<class ValueTraitsOrHookOption> 487 struct unordered_bucket_ptr 488 : public detail::unordered_bucket_ptr_impl 489 <typename ValueTraitsOrHookOption:: 490 template pack<none>::value_traits 491 > 492 {}; 493 494 //!This metafunction will obtain the type of the default bucket traits 495 //!(when the user does not specify the bucket_traits<> option) from the 496 //!value_traits or hook option to be used with 497 //!a hash container. 498 template<class ValueTraitsOrHookOption> 499 struct unordered_default_bucket_traits 500 { 501 typedef typename ValueTraitsOrHookOption:: 502 template pack<none>::value_traits supposed_value_traits; 503 typedef typename detail:: 504 get_slist_impl_from_supposed_value_traits 505 <supposed_value_traits>::type slist_impl; 506 typedef detail::bucket_traits_impl 507 <slist_impl> implementation_defined; 508 typedef implementation_defined type; 509 }; 510 511 struct default_bucket_traits; 512 513 template <class T> 514 struct uset_defaults 515 : pack_options 516 < none 517 , base_hook<detail::default_uset_hook> 518 , constant_time_size<true> 519 , size_type<std::size_t> 520 , equal<std::equal_to<T> > 521 , hash<boost::hash<T> > 522 , bucket_traits<default_bucket_traits> 523 , power_2_buckets<false> 524 , cache_begin<false> 525 , compare_hash<false> 526 , incremental<false> 527 >::type 528 {}; 529 530 /// @endcond 531 532 //! The class template hashtable is an intrusive hash table container, that 533 //! is used to construct intrusive unordered_set and unordered_multiset containers. The 534 //! no-throw guarantee holds only, if the Equal object and Hasher don't throw. 535 //! 536 //! hashtable is a semi-intrusive container: each object to be stored in the 537 //! container must contain a proper hook, but the container also needs 538 //! additional auxiliary memory to work: hashtable needs a pointer to an array 539 //! of type `bucket_type` to be passed in the constructor. This bucket array must 540 //! have at least the same lifetime as the container. This makes the use of 541 //! hashtable more complicated than purely intrusive containers. 542 //! `bucket_type` is default-constructible, copyable and assignable 543 //! 544 //! The template parameter \c T is the type to be managed by the container. 545 //! The user can specify additional options and if no options are provided 546 //! default options are used. 547 //! 548 //! The container supports the following options: 549 //! \c base_hook<>/member_hook<>/value_traits<>, 550 //! \c constant_time_size<>, \c size_type<>, \c hash<> and \c equal<> 551 //! \c bucket_traits<>, power_2_buckets<>, cache_begin<> and incremental<>. 552 //! 553 //! hashtable only provides forward iterators but it provides 4 iterator types: 554 //! iterator and const_iterator to navigate through the whole container and 555 //! local_iterator and const_local_iterator to navigate through the values 556 //! stored in a single bucket. Local iterators are faster and smaller. 557 //! 558 //! It's not recommended to use non constant-time size hashtables because several 559 //! key functions, like "empty()", become non-constant time functions. Non 560 //! constant_time size hashtables are mainly provided to support auto-unlink hooks. 561 //! 562 //! hashtables, does not make automatic rehashings nor 563 //! offers functions related to a load factor. Rehashing can be explicitly requested 564 //! and the user must provide a new bucket array that will be used from that moment. 565 //! 566 //! Since no automatic rehashing is done, iterators are never invalidated when 567 //! inserting or erasing elements. Iterators are only invalidated when rehashing. 568 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 569 template<class T, class ...Options> 570 #else 571 template<class Config> 572 #endif 573 class hashtable_impl 574 : private detail::clear_on_destructor_base<hashtable_impl<Config> > 575 { 576 template<class C> friend class detail::clear_on_destructor_base; 577 public: 578 typedef typename Config::value_traits value_traits; 579 580 /// @cond 581 static const bool external_value_traits = 582 detail::external_value_traits_is_true<value_traits>::value; 583 typedef typename detail::eval_if_c 584 < external_value_traits 585 , detail::eval_value_traits<value_traits> 586 , detail::identity<value_traits> 587 >::type real_value_traits; 588 typedef typename Config::bucket_traits bucket_traits; 589 static const bool external_bucket_traits = 590 detail::external_bucket_traits_is_true<bucket_traits>::value; 591 typedef typename detail::eval_if_c 592 < external_bucket_traits 593 , detail::eval_bucket_traits<bucket_traits> 594 , detail::identity<bucket_traits> 595 >::type real_bucket_traits; 596 typedef typename detail::get_slist_impl 597 <typename detail::reduced_slist_node_traits 598 <typename real_value_traits::node_traits>::type 599 >::type slist_impl; 600 /// @endcond 601 602 typedef typename real_value_traits::pointer pointer; 603 typedef typename real_value_traits::const_pointer const_pointer; 604 typedef typename real_value_traits::value_type value_type; 605 typedef typename std::iterator_traits<pointer>::reference reference; 606 typedef typename std::iterator_traits<const_pointer>::reference const_reference; 607 typedef typename std::iterator_traits<pointer>::difference_type difference_type; 608 typedef typename Config::size_type size_type; 609 typedef value_type key_type; 610 typedef typename Config::equal key_equal; 611 typedef typename Config::hash hasher; 612 typedef detail::bucket_impl<slist_impl> bucket_type; 613 typedef typename boost::pointer_to_other 614 <pointer, bucket_type>::type bucket_ptr; 615 typedef typename slist_impl::iterator siterator; 616 typedef typename slist_impl::const_iterator const_siterator; 617 typedef detail::hashtable_iterator<hashtable_impl, false> iterator; 618 typedef detail::hashtable_iterator<hashtable_impl, true> const_iterator; 619 typedef typename real_value_traits::node_traits node_traits; 620 typedef typename node_traits::node node; 621 typedef typename boost::pointer_to_other 622 <pointer, node>::type node_ptr; 623 typedef typename boost::pointer_to_other 624 <node_ptr, const node>::type const_node_ptr; 625 typedef typename slist_impl::node_algorithms node_algorithms; 626 627 static const bool stateful_value_traits = detail::is_stateful_value_traits<real_value_traits>::value; 628 static const bool store_hash = detail::store_hash_is_true<node_traits>::value; 629 630 static const bool unique_keys = 0 != (Config::bool_flags & detail::hash_bool_flags::unique_keys_pos); 631 static const bool constant_time_size = 0 != (Config::bool_flags & detail::hash_bool_flags::constant_time_size_pos); 632 static const bool cache_begin = 0 != (Config::bool_flags & detail::hash_bool_flags::cache_begin_pos); 633 static const bool compare_hash = 0 != (Config::bool_flags & detail::hash_bool_flags::compare_hash_pos); 634 static const bool incremental = 0 != (Config::bool_flags & detail::hash_bool_flags::incremental_pos); 635 static const bool power_2_buckets = incremental || (0 != (Config::bool_flags & detail::hash_bool_flags::power_2_buckets_pos)); 636 637 static const bool optimize_multikey 638 = detail::optimize_multikey_is_true<node_traits>::value && !unique_keys; 639 640 /// @cond 641 private: 642 643 //Configuration error: compare_hash<> can't be specified without store_hash<> 644 //See documentation for more explanations 645 BOOST_STATIC_ASSERT((!compare_hash || store_hash)); 646 647 typedef typename slist_impl::node_ptr slist_node_ptr; 648 typedef typename boost::pointer_to_other 649 <slist_node_ptr, void>::type void_pointer; 650 //We'll define group traits, but these won't be instantiated if 651 //optimize_multikey is not true 652 typedef unordered_group_adapter<node_traits> group_traits; 653 typedef circular_slist_algorithms<group_traits> group_algorithms; 654 typedef detail::bool_<store_hash> store_hash_t; 655 typedef detail::bool_<optimize_multikey> optimize_multikey_t; 656 typedef detail::bool_<cache_begin> cache_begin_t; 657 typedef detail::bool_<power_2_buckets> power_2_buckets_t; 658 typedef detail::size_holder<constant_time_size, size_type> size_traits; 659 typedef detail::size_holder<incremental, size_type> split_traits; 660 typedef detail::group_functions<node_traits> group_functions_t; 661 662 static const std::size_t hashtable_data_bool_flags_mask = 663 ( detail::hash_bool_flags::cache_begin_pos 664 | detail::hash_bool_flags::constant_time_size_pos 665 | detail::hash_bool_flags::incremental_pos 666 ); 667 typedef typename detail::usetopt_mask 668 <Config, hashtable_data_bool_flags_mask>::type masked_config_t; 669 detail::hashtable_data_t<masked_config_t> data_; 670 671 template<bool IsConst> 672 struct downcast_node_to_value 673 : public detail::node_to_value<hashtable_impl, IsConst> 674 { 675 typedef detail::node_to_value<hashtable_impl, IsConst> base_t; 676 typedef typename base_t::result_type result_type; 677 typedef typename detail::add_const_if_c 678 <typename slist_impl::node, IsConst>::type &first_argument_type; 679 typedef typename detail::add_const_if_c 680 <node, IsConst>::type &intermediate_argument_type; 681 downcast_node_to_valueboost::intrusive::hashtable_impl::downcast_node_to_value682 downcast_node_to_value(const hashtable_impl *cont) 683 : base_t(cont) 684 {} 685 operator ()boost::intrusive::hashtable_impl::downcast_node_to_value686 result_type operator()(first_argument_type arg) const 687 { return this->base_t::operator()(static_cast<intermediate_argument_type>(arg)); } 688 }; 689 690 template<class F> 691 struct node_cast_adaptor 692 : private detail::ebo_functor_holder<F> 693 { 694 typedef detail::ebo_functor_holder<F> base_t; 695 696 template<class ConvertibleToF> node_cast_adaptorboost::intrusive::hashtable_impl::node_cast_adaptor697 node_cast_adaptor(const ConvertibleToF &c2f, const hashtable_impl *cont) 698 : base_t(base_t(c2f, cont)) 699 {} 700 operator ()boost::intrusive::hashtable_impl::node_cast_adaptor701 typename base_t::node_ptr operator()(const typename slist_impl::node &to_clone) 702 { return base_t::operator()(static_cast<const node &>(to_clone)); } 703 operator ()boost::intrusive::hashtable_impl::node_cast_adaptor704 void operator()(typename slist_impl::node_ptr to_clone) 705 { base_t::operator()(node_ptr(&static_cast<node &>(*to_clone))); } 706 }; 707 708 private: 709 //noncopyable 710 hashtable_impl (const hashtable_impl&); 711 hashtable_impl operator =(const hashtable_impl&); 712 713 enum { safemode_or_autounlink = 714 (int)real_value_traits::link_mode == (int)auto_unlink || 715 (int)real_value_traits::link_mode == (int)safe_link }; 716 717 //Constant-time size is incompatible with auto-unlink hooks! 718 BOOST_STATIC_ASSERT(!(constant_time_size && ((int)real_value_traits::link_mode == (int)auto_unlink))); 719 //Cache begin is incompatible with auto-unlink hooks! 720 BOOST_STATIC_ASSERT(!(cache_begin && ((int)real_value_traits::link_mode == (int)auto_unlink))); 721 722 template<class Disposer> 723 node_cast_adaptor<detail::node_disposer<Disposer, hashtable_impl> > make_node_disposer(const Disposer & disposer) const724 make_node_disposer(const Disposer &disposer) const 725 { return node_cast_adaptor<detail::node_disposer<Disposer, hashtable_impl> >(disposer, this); } 726 727 /// @endcond 728 729 public: 730 typedef detail::insert_commit_data_impl insert_commit_data; 731 732 typedef detail::transform_iterator 733 < typename slist_impl::iterator 734 , downcast_node_to_value<false> > local_iterator; 735 736 typedef detail::transform_iterator 737 < typename slist_impl::iterator 738 , downcast_node_to_value<true> > const_local_iterator; 739 740 /// @cond 741 get_real_value_traits(detail::bool_<false>) const742 const real_value_traits &get_real_value_traits(detail::bool_<false>) const 743 { return this->data_; } 744 get_real_value_traits(detail::bool_<true>) const745 const real_value_traits &get_real_value_traits(detail::bool_<true>) const 746 { return data_.get_value_traits(*this); } 747 get_real_value_traits(detail::bool_<false>)748 real_value_traits &get_real_value_traits(detail::bool_<false>) 749 { return this->data_; } 750 get_real_value_traits(detail::bool_<true>)751 real_value_traits &get_real_value_traits(detail::bool_<true>) 752 { return data_.get_value_traits(*this); } 753 754 /// @endcond 755 756 public: 757 get_real_value_traits() const758 const real_value_traits &get_real_value_traits() const 759 { return this->get_real_value_traits(detail::bool_<external_value_traits>()); } 760 get_real_value_traits()761 real_value_traits &get_real_value_traits() 762 { return this->get_real_value_traits(detail::bool_<external_value_traits>()); } 763 764 //! <b>Requires</b>: buckets must not be being used by any other resource. 765 //! 766 //! <b>Effects</b>: Constructs an empty unordered_set, storing a reference 767 //! to the bucket array and copies of the key_hasher and equal_func functors. 768 //! 769 //! <b>Complexity</b>: Constant. 770 //! 771 //! <b>Throws</b>: If value_traits::node_traits::node 772 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 773 //! or the copy constructor or invocation of hash_func or equal_func throws. 774 //! 775 //! <b>Notes</b>: buckets array must be disposed only after 776 //! *this is disposed. hashtable_impl(const bucket_traits & b_traits,const hasher & hash_func=hasher (),const key_equal & equal_func=key_equal (),const value_traits & v_traits=value_traits ())777 hashtable_impl ( const bucket_traits &b_traits 778 , const hasher & hash_func = hasher() 779 , const key_equal &equal_func = key_equal() 780 , const value_traits &v_traits = value_traits()) 781 : data_(b_traits, hash_func, equal_func, v_traits) 782 { 783 priv_initialize_buckets(); 784 this->priv_size_traits().set_size(size_type(0)); 785 size_type bucket_size = this->priv_buckets_len(); 786 BOOST_INTRUSIVE_INVARIANT_ASSERT(bucket_size != 0); 787 //Check power of two bucket array if the option is activated 788 BOOST_INTRUSIVE_INVARIANT_ASSERT 789 (!power_2_buckets || (0 == (bucket_size & (bucket_size-1)))); 790 priv_split_traits().set_size(bucket_size>>1); 791 } 792 793 //! <b>Effects</b>: Detaches all elements from this. The objects in the unordered_set 794 //! are not deleted (i.e. no destructors are called). 795 //! 796 //! <b>Complexity</b>: Linear to the number of elements in the unordered_set, if 797 //! it's a safe-mode or auto-unlink value. Otherwise constant. 798 //! 799 //! <b>Throws</b>: Nothing. ~hashtable_impl()800 ~hashtable_impl() 801 {} 802 803 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the unordered_set. 804 //! 805 //! <b>Complexity</b>: Amortized constant time. 806 //! Worst case (empty unordered_set): O(this->bucket_count()) 807 //! 808 //! <b>Throws</b>: Nothing. begin()809 iterator begin() 810 { return iterator(this->priv_begin(), this); } 811 812 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning 813 //! of the unordered_set. 814 //! 815 //! <b>Complexity</b>: Amortized constant time. 816 //! Worst case (empty unordered_set): O(this->bucket_count()) 817 //! 818 //! <b>Throws</b>: Nothing. begin() const819 const_iterator begin() const 820 { return this->cbegin(); } 821 822 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning 823 //! of the unordered_set. 824 //! 825 //! <b>Complexity</b>: Amortized constant time. 826 //! Worst case (empty unordered_set): O(this->bucket_count()) 827 //! 828 //! <b>Throws</b>: Nothing. cbegin() const829 const_iterator cbegin() const 830 { return const_iterator(this->priv_begin(), this); } 831 832 //! <b>Effects</b>: Returns an iterator pointing to the end of the unordered_set. 833 //! 834 //! <b>Complexity</b>: Constant. 835 //! 836 //! <b>Throws</b>: Nothing. end()837 iterator end() 838 { return iterator(priv_invalid_local_it(), 0); } 839 840 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set. 841 //! 842 //! <b>Complexity</b>: Constant. 843 //! 844 //! <b>Throws</b>: Nothing. end() const845 const_iterator end() const 846 { return this->cend(); } 847 848 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set. 849 //! 850 //! <b>Complexity</b>: Constant. 851 //! 852 //! <b>Throws</b>: Nothing. cend() const853 const_iterator cend() const 854 { return const_iterator(priv_invalid_local_it(), 0); } 855 856 //! <b>Effects</b>: Returns the hasher object used by the unordered_set. 857 //! 858 //! <b>Complexity</b>: Constant. 859 //! 860 //! <b>Throws</b>: If hasher copy-constructor throws. hash_function() const861 hasher hash_function() const 862 { return this->priv_hasher(); } 863 864 //! <b>Effects</b>: Returns the key_equal object used by the unordered_set. 865 //! 866 //! <b>Complexity</b>: Constant. 867 //! 868 //! <b>Throws</b>: If key_equal copy-constructor throws. key_eq() const869 key_equal key_eq() const 870 { return this->priv_equal(); } 871 872 //! <b>Effects</b>: Returns true if the container is empty. 873 //! 874 //! <b>Complexity</b>: if constant-time size and cache_begin options are disabled, 875 //! average constant time (worst case, with empty() == true: O(this->bucket_count()). 876 //! Otherwise constant. 877 //! 878 //! <b>Throws</b>: Nothing. empty() const879 bool empty() const 880 { 881 if(constant_time_size){ 882 return !this->size(); 883 } 884 else if(cache_begin){ 885 return this->begin() == this->end(); 886 } 887 else{ 888 size_type buckets_len = this->priv_buckets_len(); 889 const bucket_type *b = detail::boost_intrusive_get_pointer(this->priv_buckets()); 890 for (size_type n = 0; n < buckets_len; ++n, ++b){ 891 if(!b->empty()){ 892 return false; 893 } 894 } 895 return true; 896 } 897 } 898 899 //! <b>Effects</b>: Returns the number of elements stored in the unordered_set. 900 //! 901 //! <b>Complexity</b>: Linear to elements contained in *this if 902 //! constant_time_size is false. Constant-time otherwise. 903 //! 904 //! <b>Throws</b>: Nothing. size() const905 size_type size() const 906 { 907 if(constant_time_size) 908 return this->priv_size_traits().get_size(); 909 else{ 910 size_type len = 0; 911 size_type buckets_len = this->priv_buckets_len(); 912 const bucket_type *b = detail::boost_intrusive_get_pointer(this->priv_buckets()); 913 for (size_type n = 0; n < buckets_len; ++n, ++b){ 914 len += b->size(); 915 } 916 return len; 917 } 918 } 919 920 //! <b>Requires</b>: the hasher and the equality function unqualified swap 921 //! call should not throw. 922 //! 923 //! <b>Effects</b>: Swaps the contents of two unordered_sets. 924 //! Swaps also the contained bucket array and equality and hasher functors. 925 //! 926 //! <b>Complexity</b>: Constant. 927 //! 928 //! <b>Throws</b>: If the swap() call for the comparison or hash functors 929 //! found using ADL throw. Basic guarantee. swap(hashtable_impl & other)930 void swap(hashtable_impl& other) 931 { 932 using std::swap; 933 //These can throw 934 swap(this->priv_equal(), other.priv_equal()); 935 swap(this->priv_hasher(), other.priv_hasher()); 936 //These can't throw 937 swap(this->priv_real_bucket_traits(), other.priv_real_bucket_traits()); 938 priv_swap_cache(cache_begin_t(), other); 939 if(constant_time_size){ 940 size_type backup = this->priv_size_traits().get_size(); 941 this->priv_size_traits().set_size(other.priv_size_traits().get_size()); 942 other.priv_size_traits().set_size(backup); 943 } 944 else if(incremental){ 945 size_type backup = this->priv_split_traits().get_size(); 946 this->priv_split_traits().set_size(other.priv_split_traits().get_size()); 947 other.priv_split_traits().set_size(backup); 948 } 949 } 950 951 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw 952 //! Cloner should yield to nodes that compare equal and produce the same 953 //! hash than the original node. 954 //! 955 //! <b>Effects</b>: Erases all the elements from *this 956 //! calling Disposer::operator()(pointer), clones all the 957 //! elements from src calling Cloner::operator()(const_reference ) 958 //! and inserts them on *this. The hash function and the equality 959 //! predicate are copied from the source. 960 //! 961 //! If store_hash option is true, this method does not use the hash function. 962 //! 963 //! If any operation throws, all cloned elements are unlinked and disposed 964 //! calling Disposer::operator()(pointer). 965 //! 966 //! <b>Complexity</b>: Linear to erased plus inserted elements. 967 //! 968 //! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying 969 //! throws. Basic guarantee. 970 template <class Cloner, class Disposer> clone_from(const hashtable_impl & src,Cloner cloner,Disposer disposer)971 void clone_from(const hashtable_impl &src, Cloner cloner, Disposer disposer) 972 { 973 this->clear_and_dispose(disposer); 974 if(!constant_time_size || !src.empty()){ 975 const size_type src_bucket_count = src.bucket_count(); 976 const size_type dst_bucket_count = this->bucket_count(); 977 //Check power of two bucket array if the option is activated 978 BOOST_INTRUSIVE_INVARIANT_ASSERT 979 (!power_2_buckets || (0 == (src_bucket_count & (src_bucket_count-1)))); 980 BOOST_INTRUSIVE_INVARIANT_ASSERT 981 (!power_2_buckets || (0 == (dst_bucket_count & (dst_bucket_count-1)))); 982 983 //If src bucket count is bigger or equal, structural copy is possible 984 if(!incremental && (src_bucket_count >= dst_bucket_count)){ 985 //First clone the first ones 986 const bucket_ptr src_buckets = src.priv_buckets(); 987 const bucket_ptr dst_buckets = this->priv_buckets(); 988 size_type constructed; 989 typedef node_cast_adaptor<detail::node_disposer<Disposer, hashtable_impl> > NodeDisposer; 990 typedef node_cast_adaptor<detail::node_cloner<Cloner, hashtable_impl> > NodeCloner; 991 NodeDisposer node_disp(disposer, this); 992 993 detail::exception_array_disposer<bucket_type, NodeDisposer> 994 rollback(dst_buckets[0], node_disp, constructed); 995 for( constructed = 0 996 ; constructed < dst_bucket_count 997 ; ++constructed){ 998 dst_buckets[constructed].clone_from 999 ( src_buckets[constructed] 1000 , NodeCloner(cloner, this), node_disp); 1001 } 1002 if(src_bucket_count != dst_bucket_count){ 1003 //Now insert the remaining ones using the modulo trick 1004 for(//"constructed" comes from the previous loop 1005 ; constructed < src_bucket_count 1006 ; ++constructed){ 1007 bucket_type &dst_b = 1008 dst_buckets[priv_hash_to_bucket(constructed, dst_bucket_count, dst_bucket_count)]; 1009 bucket_type &src_b = src_buckets[constructed]; 1010 for( siterator b(src_b.begin()), e(src_b.end()) 1011 ; b != e 1012 ; ++b){ 1013 dst_b.push_front(*(NodeCloner(cloner, this)(*b.pointed_node()))); 1014 } 1015 } 1016 } 1017 this->priv_hasher() = src.priv_hasher(); 1018 this->priv_equal() = src.priv_equal(); 1019 rollback.release(); 1020 this->priv_size_traits().set_size(src.priv_size_traits().get_size()); 1021 this->priv_split_traits().set_size(dst_bucket_count); 1022 priv_insertion_update_cache(0u); 1023 priv_erasure_update_cache(); 1024 } 1025 else if(store_hash){ 1026 //Unlike previous cloning algorithm, this can throw 1027 //if cloner, hasher or comparison functor throw 1028 const_iterator b(src.begin()), e(src.end()); 1029 detail::exception_disposer<hashtable_impl, Disposer> 1030 rollback(*this, disposer); 1031 for(; b != e; ++b){ 1032 std::size_t hash_value = this->priv_stored_or_compute_hash(*b, store_hash_t());; 1033 this->priv_insert_equal_with_hash(*cloner(*b), hash_value); 1034 } 1035 rollback.release(); 1036 } 1037 else{ 1038 //Unlike previous cloning algorithm, this can throw 1039 //if cloner, hasher or comparison functor throw 1040 const_iterator b(src.begin()), e(src.end()); 1041 detail::exception_disposer<hashtable_impl, Disposer> 1042 rollback(*this, disposer); 1043 for(; b != e; ++b){ 1044 this->insert_equal(*cloner(*b)); 1045 } 1046 rollback.release(); 1047 } 1048 } 1049 } 1050 1051 //! <b>Requires</b>: value must be an lvalue 1052 //! 1053 //! <b>Effects</b>: Inserts the value into the unordered_set. 1054 //! 1055 //! <b>Returns</b>: An iterator to the inserted value. 1056 //! 1057 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1058 //! 1059 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee. 1060 //! 1061 //! <b>Note</b>: Does not affect the validity of iterators and references. 1062 //! No copy-constructors are called. insert_equal(reference value)1063 iterator insert_equal(reference value) 1064 { 1065 size_type bucket_num; 1066 std::size_t hash_value; 1067 siterator prev; 1068 siterator it = this->priv_find 1069 (value, this->priv_hasher(), this->priv_equal(), bucket_num, hash_value, prev); 1070 return priv_insert_equal_find(value, bucket_num, hash_value, it); 1071 } 1072 1073 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue 1074 //! of type value_type. 1075 //! 1076 //! <b>Effects</b>: Equivalent to this->insert_equal(t) for each element in [b, e). 1077 //! 1078 //! <b>Complexity</b>: Average case O(N), where N is std::distance(b, e). 1079 //! Worst case O(N*this->size()). 1080 //! 1081 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee. 1082 //! 1083 //! <b>Note</b>: Does not affect the validity of iterators and references. 1084 //! No copy-constructors are called. 1085 template<class Iterator> insert_equal(Iterator b,Iterator e)1086 void insert_equal(Iterator b, Iterator e) 1087 { 1088 for (; b != e; ++b) 1089 this->insert_equal(*b); 1090 } 1091 1092 //! <b>Requires</b>: value must be an lvalue 1093 //! 1094 //! <b>Effects</b>: Tries to inserts value into the unordered_set. 1095 //! 1096 //! <b>Returns</b>: If the value 1097 //! is not already present inserts it and returns a pair containing the 1098 //! iterator to the new value and true. If there is an equivalent value 1099 //! returns a pair containing an iterator to the already present value 1100 //! and false. 1101 //! 1102 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1103 //! 1104 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee. 1105 //! 1106 //! <b>Note</b>: Does not affect the validity of iterators and references. 1107 //! No copy-constructors are called. insert_unique(reference value)1108 std::pair<iterator, bool> insert_unique(reference value) 1109 { 1110 insert_commit_data commit_data; 1111 std::pair<iterator, bool> ret = this->insert_unique_check 1112 (value, this->priv_hasher(), this->priv_equal(), commit_data); 1113 if(!ret.second) 1114 return ret; 1115 return std::pair<iterator, bool> 1116 (this->insert_unique_commit(value, commit_data), true); 1117 } 1118 1119 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue 1120 //! of type value_type. 1121 //! 1122 //! <b>Effects</b>: Equivalent to this->insert_unique(t) for each element in [b, e). 1123 //! 1124 //! <b>Complexity</b>: Average case O(N), where N is std::distance(b, e). 1125 //! Worst case O(N*this->size()). 1126 //! 1127 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee. 1128 //! 1129 //! <b>Note</b>: Does not affect the validity of iterators and references. 1130 //! No copy-constructors are called. 1131 template<class Iterator> insert_unique(Iterator b,Iterator e)1132 void insert_unique(Iterator b, Iterator e) 1133 { 1134 for (; b != e; ++b) 1135 this->insert_unique(*b); 1136 } 1137 1138 //! <b>Requires</b>: "hash_func" must be a hash function that induces 1139 //! the same hash values as the stored hasher. The difference is that 1140 //! "hash_func" hashes the given key instead of the value_type. 1141 //! 1142 //! "equal_func" must be a equality function that induces 1143 //! the same equality as key_equal. The difference is that 1144 //! "equal_func" compares an arbitrary key with the contained values. 1145 //! 1146 //! <b>Effects</b>: Checks if a value can be inserted in the unordered_set, using 1147 //! a user provided key instead of the value itself. 1148 //! 1149 //! <b>Returns</b>: If there is an equivalent value 1150 //! returns a pair containing an iterator to the already present value 1151 //! and false. If the value can be inserted returns true in the returned 1152 //! pair boolean and fills "commit_data" that is meant to be used with 1153 //! the "insert_commit" function. 1154 //! 1155 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1156 //! 1157 //! <b>Throws</b>: If hash_func or equal_func throw. Strong guarantee. 1158 //! 1159 //! <b>Notes</b>: This function is used to improve performance when constructing 1160 //! a value_type is expensive: if there is an equivalent value 1161 //! the constructed object must be discarded. Many times, the part of the 1162 //! node that is used to impose the hash or the equality is much cheaper to 1163 //! construct than the value_type and this function offers the possibility to 1164 //! use that the part to check if the insertion will be successful. 1165 //! 1166 //! If the check is successful, the user can construct the value_type and use 1167 //! "insert_commit" to insert the object in constant-time. 1168 //! 1169 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more 1170 //! objects are inserted or erased from the unordered_set. 1171 //! 1172 //! After a successful rehashing insert_commit_data remains valid. 1173 template<class KeyType, class KeyHasher, class KeyValueEqual> insert_unique_check(const KeyType & key,KeyHasher hash_func,KeyValueEqual equal_func,insert_commit_data & commit_data)1174 std::pair<iterator, bool> insert_unique_check 1175 ( const KeyType &key 1176 , KeyHasher hash_func 1177 , KeyValueEqual equal_func 1178 , insert_commit_data &commit_data) 1179 { 1180 size_type bucket_num; 1181 siterator prev; 1182 siterator prev_pos = 1183 this->priv_find(key, hash_func, equal_func, bucket_num, commit_data.hash, prev); 1184 bool success = prev_pos == priv_invalid_local_it(); 1185 if(success){ 1186 prev_pos = prev; 1187 } 1188 return std::pair<iterator, bool>(iterator(prev_pos, this),success); 1189 } 1190 1191 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data 1192 //! must have been obtained from a previous call to "insert_check". 1193 //! No objects should have been inserted or erased from the unordered_set between 1194 //! the "insert_check" that filled "commit_data" and the call to "insert_commit". 1195 //! 1196 //! <b>Effects</b>: Inserts the value in the unordered_set using the information obtained 1197 //! from the "commit_data" that a previous "insert_check" filled. 1198 //! 1199 //! <b>Returns</b>: An iterator to the newly inserted object. 1200 //! 1201 //! <b>Complexity</b>: Constant time. 1202 //! 1203 //! <b>Throws</b>: Nothing. 1204 //! 1205 //! <b>Notes</b>: This function has only sense if a "insert_check" has been 1206 //! previously executed to fill "commit_data". No value should be inserted or 1207 //! erased between the "insert_check" and "insert_commit" calls. 1208 //! 1209 //! After a successful rehashing insert_commit_data remains valid. insert_unique_commit(reference value,const insert_commit_data & commit_data)1210 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data) 1211 { 1212 size_type bucket_num = priv_hash_to_bucket(commit_data.hash); 1213 bucket_type &b = this->priv_buckets()[bucket_num]; 1214 this->priv_size_traits().increment(); 1215 node_ptr n = node_ptr(&priv_value_to_node(value)); 1216 this->priv_store_hash(n, commit_data.hash, store_hash_t()); 1217 if(safemode_or_autounlink) 1218 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n)); 1219 priv_insertion_update_cache(bucket_num); 1220 this->priv_insert_in_group(node_ptr(0), n, optimize_multikey_t()); 1221 return iterator(b.insert_after(b.before_begin(), *n), this); 1222 } 1223 1224 //! <b>Effects</b>: Erases the element pointed to by i. 1225 //! 1226 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1227 //! 1228 //! <b>Throws</b>: Nothing. 1229 //! 1230 //! <b>Note</b>: Invalidates the iterators (but not the references) 1231 //! to the erased element. No destructors are called. erase(const_iterator i)1232 void erase(const_iterator i) 1233 { this->erase_and_dispose(i, detail::null_disposer()); } 1234 1235 //! <b>Effects</b>: Erases the range pointed to by b end e. 1236 //! 1237 //! <b>Complexity</b>: Average case O(std::distance(b, e)), 1238 //! worst case O(this->size()). 1239 //! 1240 //! <b>Throws</b>: Nothing. 1241 //! 1242 //! <b>Note</b>: Invalidates the iterators (but not the references) 1243 //! to the erased elements. No destructors are called. erase(const_iterator b,const_iterator e)1244 void erase(const_iterator b, const_iterator e) 1245 { this->erase_and_dispose(b, e, detail::null_disposer()); } 1246 1247 //! <b>Effects</b>: Erases all the elements with the given value. 1248 //! 1249 //! <b>Returns</b>: The number of erased elements. 1250 //! 1251 //! <b>Complexity</b>: Average case O(this->count(value)). 1252 //! Worst case O(this->size()). 1253 //! 1254 //! <b>Throws</b>: If the internal hasher or the equality functor throws. 1255 //! Basic guarantee. 1256 //! 1257 //! <b>Note</b>: Invalidates the iterators (but not the references) 1258 //! to the erased elements. No destructors are called. erase(const_reference value)1259 size_type erase(const_reference value) 1260 { return this->erase(value, this->priv_hasher(), this->priv_equal()); } 1261 1262 //! <b>Requires</b>: "hash_func" must be a hash function that induces 1263 //! the same hash values as the stored hasher. The difference is that 1264 //! "hash_func" hashes the given key instead of the value_type. 1265 //! 1266 //! "equal_func" must be a equality function that induces 1267 //! the same equality as key_equal. The difference is that 1268 //! "equal_func" compares an arbitrary key with the contained values. 1269 //! 1270 //! <b>Effects</b>: Erases all the elements that have the same hash and 1271 //! compare equal with the given key. 1272 //! 1273 //! <b>Returns</b>: The number of erased elements. 1274 //! 1275 //! <b>Complexity</b>: Average case O(this->count(value)). 1276 //! Worst case O(this->size()). 1277 //! 1278 //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee. 1279 //! 1280 //! <b>Note</b>: Invalidates the iterators (but not the references) 1281 //! to the erased elements. No destructors are called. 1282 template<class KeyType, class KeyHasher, class KeyValueEqual> erase(const KeyType & key,KeyHasher hash_func,KeyValueEqual equal_func)1283 size_type erase(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) 1284 { return this->erase_and_dispose(key, hash_func, equal_func, detail::null_disposer()); } 1285 1286 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1287 //! 1288 //! <b>Effects</b>: Erases the element pointed to by i. 1289 //! Disposer::operator()(pointer) is called for the removed element. 1290 //! 1291 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1292 //! 1293 //! <b>Throws</b>: Nothing. 1294 //! 1295 //! <b>Note</b>: Invalidates the iterators 1296 //! to the erased elements. 1297 template<class Disposer> erase_and_dispose(const_iterator i,Disposer disposer,typename detail::enable_if_c<!detail::is_convertible<Disposer,const_iterator>::value>::type * =0)1298 void erase_and_dispose(const_iterator i, Disposer disposer 1299 /// @cond 1300 , typename detail::enable_if_c<!detail::is_convertible<Disposer, const_iterator>::value >::type * = 0 1301 /// @endcond 1302 ) 1303 { 1304 priv_erase(i, disposer, optimize_multikey_t()); 1305 this->priv_size_traits().decrement(); 1306 priv_erasure_update_cache(); 1307 } 1308 1309 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1310 //! 1311 //! <b>Effects</b>: Erases the range pointed to by b end e. 1312 //! Disposer::operator()(pointer) is called for the removed elements. 1313 //! 1314 //! <b>Complexity</b>: Average case O(std::distance(b, e)), 1315 //! worst case O(this->size()). 1316 //! 1317 //! <b>Throws</b>: Nothing. 1318 //! 1319 //! <b>Note</b>: Invalidates the iterators 1320 //! to the erased elements. 1321 template<class Disposer> erase_and_dispose(const_iterator b,const_iterator e,Disposer disposer)1322 void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) 1323 { 1324 if(b != e){ 1325 //Get the bucket number and local iterator for both iterators 1326 siterator first_local_it(b.slist_it()); 1327 size_type first_bucket_num = this->priv_get_bucket_num(first_local_it); 1328 1329 siterator before_first_local_it 1330 = priv_get_previous(priv_buckets()[first_bucket_num], first_local_it); 1331 size_type last_bucket_num; 1332 siterator last_local_it; 1333 1334 //For the end iterator, we will assign the end iterator 1335 //of the last bucket 1336 if(e == this->end()){ 1337 last_bucket_num = this->bucket_count() - 1; 1338 last_local_it = priv_buckets()[last_bucket_num].end(); 1339 } 1340 else{ 1341 last_local_it = e.slist_it(); 1342 last_bucket_num = this->priv_get_bucket_num(last_local_it); 1343 } 1344 priv_erase_range(before_first_local_it, first_bucket_num, last_local_it, last_bucket_num, disposer); 1345 priv_erasure_update_cache(first_bucket_num, last_bucket_num); 1346 } 1347 } 1348 1349 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1350 //! 1351 //! <b>Effects</b>: Erases all the elements with the given value. 1352 //! Disposer::operator()(pointer) is called for the removed elements. 1353 //! 1354 //! <b>Returns</b>: The number of erased elements. 1355 //! 1356 //! <b>Complexity</b>: Average case O(this->count(value)). 1357 //! Worst case O(this->size()). 1358 //! 1359 //! <b>Throws</b>: If the internal hasher or the equality functor throws. 1360 //! Basic guarantee. 1361 //! 1362 //! <b>Note</b>: Invalidates the iterators (but not the references) 1363 //! to the erased elements. No destructors are called. 1364 template<class Disposer> erase_and_dispose(const_reference value,Disposer disposer)1365 size_type erase_and_dispose(const_reference value, Disposer disposer) 1366 { return this->erase_and_dispose(value, priv_hasher(), priv_equal(), disposer); } 1367 1368 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1369 //! 1370 //! <b>Effects</b>: Erases all the elements with the given key. 1371 //! according to the comparison functor "equal_func". 1372 //! Disposer::operator()(pointer) is called for the removed elements. 1373 //! 1374 //! <b>Returns</b>: The number of erased elements. 1375 //! 1376 //! <b>Complexity</b>: Average case O(this->count(value)). 1377 //! Worst case O(this->size()). 1378 //! 1379 //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee. 1380 //! 1381 //! <b>Note</b>: Invalidates the iterators 1382 //! to the erased elements. 1383 template<class KeyType, class KeyHasher, class KeyValueEqual, class Disposer> erase_and_dispose(const KeyType & key,KeyHasher hash_func,KeyValueEqual equal_func,Disposer disposer)1384 size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func 1385 ,KeyValueEqual equal_func, Disposer disposer) 1386 { 1387 size_type bucket_num; 1388 std::size_t h; 1389 siterator prev; 1390 siterator it = 1391 this->priv_find(key, hash_func, equal_func, bucket_num, h, prev); 1392 bool success = it != priv_invalid_local_it(); 1393 size_type count(0); 1394 if(!success){ 1395 return 0; 1396 } 1397 else if(optimize_multikey){ 1398 siterator last = bucket_type::s_iterator_to 1399 (*node_traits::get_next(group_functions_t::priv_get_last_in_group 1400 (dcast_bucket_ptr(it.pointed_node()), optimize_multikey_t()))); 1401 this->priv_erase_range_impl(bucket_num, prev, last, disposer, count); 1402 } 1403 else{ 1404 //If found erase all equal values 1405 bucket_type &b = this->priv_buckets()[bucket_num]; 1406 for(siterator end = b.end(); it != end; ++count, ++it){ 1407 slist_node_ptr n(it.pointed_node()); 1408 const value_type &v = priv_value_from_slist_node(n); 1409 if(compare_hash){ 1410 std::size_t vh = this->priv_stored_or_compute_hash(v, store_hash_t()); 1411 if(h != vh || !equal_func(key, v)){ 1412 break; 1413 } 1414 } 1415 else if(!equal_func(key, v)){ 1416 break; 1417 } 1418 this->priv_size_traits().decrement(); 1419 } 1420 b.erase_after_and_dispose(prev, it, make_node_disposer(disposer)); 1421 } 1422 priv_erasure_update_cache(); 1423 return count; 1424 } 1425 1426 //! <b>Effects</b>: Erases all of the elements. 1427 //! 1428 //! <b>Complexity</b>: Linear to the number of elements on the container. 1429 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. 1430 //! 1431 //! <b>Throws</b>: Nothing. 1432 //! 1433 //! <b>Note</b>: Invalidates the iterators (but not the references) 1434 //! to the erased elements. No destructors are called. clear()1435 void clear() 1436 { 1437 priv_clear_buckets(); 1438 this->priv_size_traits().set_size(size_type(0)); 1439 } 1440 1441 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1442 //! 1443 //! <b>Effects</b>: Erases all of the elements. 1444 //! 1445 //! <b>Complexity</b>: Linear to the number of elements on the container. 1446 //! Disposer::operator()(pointer) is called for the removed elements. 1447 //! 1448 //! <b>Throws</b>: Nothing. 1449 //! 1450 //! <b>Note</b>: Invalidates the iterators (but not the references) 1451 //! to the erased elements. No destructors are called. 1452 template<class Disposer> clear_and_dispose(Disposer disposer)1453 void clear_and_dispose(Disposer disposer) 1454 { 1455 if(!constant_time_size || !this->empty()){ 1456 size_type num_buckets = this->bucket_count(); 1457 bucket_ptr b = this->priv_buckets(); 1458 for(; num_buckets--; ++b){ 1459 b->clear_and_dispose(make_node_disposer(disposer)); 1460 } 1461 this->priv_size_traits().set_size(size_type(0)); 1462 } 1463 priv_initialize_cache(); 1464 } 1465 1466 //! <b>Effects</b>: Returns the number of contained elements with the given value 1467 //! 1468 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1469 //! 1470 //! <b>Throws</b>: If the internal hasher or the equality functor throws. count(const_reference value) const1471 size_type count(const_reference value) const 1472 { return this->count(value, this->priv_hasher(), this->priv_equal()); } 1473 1474 //! <b>Requires</b>: "hash_func" must be a hash function that induces 1475 //! the same hash values as the stored hasher. The difference is that 1476 //! "hash_func" hashes the given key instead of the value_type. 1477 //! 1478 //! "equal_func" must be a equality function that induces 1479 //! the same equality as key_equal. The difference is that 1480 //! "equal_func" compares an arbitrary key with the contained values. 1481 //! 1482 //! <b>Effects</b>: Returns the number of contained elements with the given key 1483 //! 1484 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1485 //! 1486 //! <b>Throws</b>: If hash_func or equal throw. 1487 template<class KeyType, class KeyHasher, class KeyValueEqual> count(const KeyType & key,const KeyHasher & hash_func,const KeyValueEqual & equal_func) const1488 size_type count(const KeyType &key, const KeyHasher &hash_func, const KeyValueEqual &equal_func) const 1489 { 1490 size_type bucket_n1, bucket_n2, count; 1491 this->priv_equal_range(key, hash_func, equal_func, bucket_n1, bucket_n2, count); 1492 return count; 1493 } 1494 1495 //! <b>Effects</b>: Finds an iterator to the first element is equal to 1496 //! "value" or end() if that element does not exist. 1497 //! 1498 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1499 //! 1500 //! <b>Throws</b>: If the internal hasher or the equality functor throws. find(const_reference value)1501 iterator find(const_reference value) 1502 { return this->find(value, this->priv_hasher(), this->priv_equal()); } 1503 1504 //! <b>Requires</b>: "hash_func" must be a hash function that induces 1505 //! the same hash values as the stored hasher. The difference is that 1506 //! "hash_func" hashes the given key instead of the value_type. 1507 //! 1508 //! "equal_func" must be a equality function that induces 1509 //! the same equality as key_equal. The difference is that 1510 //! "equal_func" compares an arbitrary key with the contained values. 1511 //! 1512 //! <b>Effects</b>: Finds an iterator to the first element whose key is 1513 //! "key" according to the given hash and equality functor or end() if 1514 //! that element does not exist. 1515 //! 1516 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1517 //! 1518 //! <b>Throws</b>: If hash_func or equal_func throw. 1519 //! 1520 //! <b>Note</b>: This function is used when constructing a value_type 1521 //! is expensive and the value_type can be compared with a cheaper 1522 //! key type. Usually this key is part of the value_type. 1523 template<class KeyType, class KeyHasher, class KeyValueEqual> find(const KeyType & key,KeyHasher hash_func,KeyValueEqual equal_func)1524 iterator find(const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) 1525 { 1526 size_type bucket_n; 1527 std::size_t hash; 1528 siterator prev; 1529 siterator local_it = this->priv_find(key, hash_func, equal_func, bucket_n, hash, prev); 1530 return iterator(local_it, this); 1531 } 1532 1533 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is 1534 //! "key" or end() if that element does not exist. 1535 //! 1536 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1537 //! 1538 //! <b>Throws</b>: If the internal hasher or the equality functor throws. find(const_reference value) const1539 const_iterator find(const_reference value) const 1540 { return this->find(value, this->priv_hasher(), this->priv_equal()); } 1541 1542 //! <b>Requires</b>: "hash_func" must be a hash function that induces 1543 //! the same hash values as the stored hasher. The difference is that 1544 //! "hash_func" hashes the given key instead of the value_type. 1545 //! 1546 //! "equal_func" must be a equality function that induces 1547 //! the same equality as key_equal. The difference is that 1548 //! "equal_func" compares an arbitrary key with the contained values. 1549 //! 1550 //! <b>Effects</b>: Finds an iterator to the first element whose key is 1551 //! "key" according to the given hasher and equality functor or end() if 1552 //! that element does not exist. 1553 //! 1554 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). 1555 //! 1556 //! <b>Throws</b>: If hash_func or equal_func throw. 1557 //! 1558 //! <b>Note</b>: This function is used when constructing a value_type 1559 //! is expensive and the value_type can be compared with a cheaper 1560 //! key type. Usually this key is part of the value_type. 1561 template<class KeyType, class KeyHasher, class KeyValueEqual> find(const KeyType & key,KeyHasher hash_func,KeyValueEqual equal_func) const1562 const_iterator find 1563 (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) const 1564 { 1565 size_type bucket_n; 1566 std::size_t hash_value; 1567 siterator prev; 1568 siterator sit = this->priv_find(key, hash_func, equal_func, bucket_n, hash_value, prev); 1569 return const_iterator(sit, this); 1570 } 1571 1572 //! <b>Effects</b>: Returns a range containing all elements with values equivalent 1573 //! to value. Returns std::make_pair(this->end(), this->end()) if no such 1574 //! elements exist. 1575 //! 1576 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()). 1577 //! 1578 //! <b>Throws</b>: If the internal hasher or the equality functor throws. equal_range(const_reference value)1579 std::pair<iterator,iterator> equal_range(const_reference value) 1580 { return this->equal_range(value, this->priv_hasher(), this->priv_equal()); } 1581 1582 //! <b>Requires</b>: "hash_func" must be a hash function that induces 1583 //! the same hash values as the stored hasher. The difference is that 1584 //! "hash_func" hashes the given key instead of the value_type. 1585 //! 1586 //! "equal_func" must be a equality function that induces 1587 //! the same equality as key_equal. The difference is that 1588 //! "equal_func" compares an arbitrary key with the contained values. 1589 //! 1590 //! <b>Effects</b>: Returns a range containing all elements with equivalent 1591 //! keys. Returns std::make_pair(this->end(), this->end()) if no such 1592 //! elements exist. 1593 //! 1594 //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)). 1595 //! Worst case O(this->size()). 1596 //! 1597 //! <b>Throws</b>: If hash_func or the equal_func throw. 1598 //! 1599 //! <b>Note</b>: This function is used when constructing a value_type 1600 //! is expensive and the value_type can be compared with a cheaper 1601 //! key type. Usually this key is part of the value_type. 1602 template<class KeyType, class KeyHasher, class KeyValueEqual> equal_range(const KeyType & key,KeyHasher hash_func,KeyValueEqual equal_func)1603 std::pair<iterator,iterator> equal_range 1604 (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) 1605 { 1606 size_type bucket_n1, bucket_n2, count; 1607 std::pair<siterator, siterator> ret = this->priv_equal_range 1608 (key, hash_func, equal_func, bucket_n1, bucket_n2, count); 1609 return std::pair<iterator, iterator> 1610 (iterator(ret.first, this), iterator(ret.second, this)); 1611 } 1612 1613 //! <b>Effects</b>: Returns a range containing all elements with values equivalent 1614 //! to value. Returns std::make_pair(this->end(), this->end()) if no such 1615 //! elements exist. 1616 //! 1617 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()). 1618 //! 1619 //! <b>Throws</b>: If the internal hasher or the equality functor throws. 1620 std::pair<const_iterator, const_iterator> equal_range(const_reference value) const1621 equal_range(const_reference value) const 1622 { return this->equal_range(value, this->priv_hasher(), this->priv_equal()); } 1623 1624 //! <b>Requires</b>: "hash_func" must be a hash function that induces 1625 //! the same hash values as the stored hasher. The difference is that 1626 //! "hash_func" hashes the given key instead of the value_type. 1627 //! 1628 //! "equal_func" must be a equality function that induces 1629 //! the same equality as key_equal. The difference is that 1630 //! "equal_func" compares an arbitrary key with the contained values. 1631 //! 1632 //! <b>Effects</b>: Returns a range containing all elements with equivalent 1633 //! keys. Returns std::make_pair(this->end(), this->end()) if no such 1634 //! elements exist. 1635 //! 1636 //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)). 1637 //! Worst case O(this->size()). 1638 //! 1639 //! <b>Throws</b>: If the hasher or equal_func throw. 1640 //! 1641 //! <b>Note</b>: This function is used when constructing a value_type 1642 //! is expensive and the value_type can be compared with a cheaper 1643 //! key type. Usually this key is part of the value_type. 1644 template<class KeyType, class KeyHasher, class KeyValueEqual> equal_range(const KeyType & key,KeyHasher hash_func,KeyValueEqual equal_func) const1645 std::pair<const_iterator,const_iterator> equal_range 1646 (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) const 1647 { 1648 size_type bucket_n1, bucket_n2, count; 1649 std::pair<siterator, siterator> ret = 1650 this->priv_equal_range(key, hash_func, equal_func, bucket_n1, bucket_n2, count); 1651 return std::pair<const_iterator, const_iterator> 1652 (const_iterator(ret.first, this), const_iterator(ret.second, this)); 1653 } 1654 1655 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of 1656 //! appropriate type. Otherwise the behavior is undefined. 1657 //! 1658 //! <b>Effects</b>: Returns: a valid iterator belonging to the unordered_set 1659 //! that points to the value 1660 //! 1661 //! <b>Complexity</b>: Constant. 1662 //! 1663 //! <b>Throws</b>: If the internal hash function throws. iterator_to(reference value)1664 iterator iterator_to(reference value) 1665 { 1666 return iterator(bucket_type::s_iterator_to(priv_value_to_node(value)), this); 1667 } 1668 1669 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of 1670 //! appropriate type. Otherwise the behavior is undefined. 1671 //! 1672 //! <b>Effects</b>: Returns: a valid const_iterator belonging to the 1673 //! unordered_set that points to the value 1674 //! 1675 //! <b>Complexity</b>: Constant. 1676 //! 1677 //! <b>Throws</b>: If the internal hash function throws. iterator_to(const_reference value) const1678 const_iterator iterator_to(const_reference value) const 1679 { 1680 return const_iterator(bucket_type::s_iterator_to(priv_value_to_node(const_cast<reference>(value))), this); 1681 } 1682 1683 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of 1684 //! appropriate type. Otherwise the behavior is undefined. 1685 //! 1686 //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set 1687 //! that points to the value 1688 //! 1689 //! <b>Complexity</b>: Constant. 1690 //! 1691 //! <b>Throws</b>: Nothing. 1692 //! 1693 //! <b>Note</b>: This static function is available only if the <i>value traits</i> 1694 //! is stateless. s_local_iterator_to(reference value)1695 static local_iterator s_local_iterator_to(reference value) 1696 { 1697 BOOST_STATIC_ASSERT((!stateful_value_traits)); 1698 siterator sit = bucket_type::s_iterator_to(((hashtable_impl*)0)->priv_value_to_node(value)); 1699 return local_iterator(sit, (hashtable_impl*)0); 1700 } 1701 1702 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of 1703 //! appropriate type. Otherwise the behavior is undefined. 1704 //! 1705 //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to 1706 //! the unordered_set that points to the value 1707 //! 1708 //! <b>Complexity</b>: Constant. 1709 //! 1710 //! <b>Throws</b>: Nothing. 1711 //! 1712 //! <b>Note</b>: This static function is available only if the <i>value traits</i> 1713 //! is stateless. s_local_iterator_to(const_reference value)1714 static const_local_iterator s_local_iterator_to(const_reference value) 1715 { 1716 BOOST_STATIC_ASSERT((!stateful_value_traits)); 1717 siterator sit = bucket_type::s_iterator_to(((hashtable_impl*)0)->priv_value_to_node(const_cast<value_type&>(value))); 1718 return const_local_iterator(sit, (hashtable_impl*)0); 1719 } 1720 1721 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of 1722 //! appropriate type. Otherwise the behavior is undefined. 1723 //! 1724 //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set 1725 //! that points to the value 1726 //! 1727 //! <b>Complexity</b>: Constant. 1728 //! 1729 //! <b>Throws</b>: Nothing. local_iterator_to(reference value)1730 local_iterator local_iterator_to(reference value) 1731 { 1732 siterator sit = bucket_type::s_iterator_to(this->priv_value_to_node(value)); 1733 return local_iterator(sit, this); 1734 } 1735 1736 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of 1737 //! appropriate type. Otherwise the behavior is undefined. 1738 //! 1739 //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to 1740 //! the unordered_set that points to the value 1741 //! 1742 //! <b>Complexity</b>: Constant. 1743 //! 1744 //! <b>Throws</b>: Nothing. local_iterator_to(const_reference value) const1745 const_local_iterator local_iterator_to(const_reference value) const 1746 { 1747 siterator sit = bucket_type::s_iterator_to 1748 (const_cast<node &>(this->priv_value_to_node(value))); 1749 return const_local_iterator(sit, this); 1750 } 1751 1752 //! <b>Effects</b>: Returns the number of buckets passed in the constructor 1753 //! or the last rehash function. 1754 //! 1755 //! <b>Complexity</b>: Constant. 1756 //! 1757 //! <b>Throws</b>: Nothing. bucket_count() const1758 size_type bucket_count() const 1759 { return this->priv_buckets_len(); } 1760 1761 //! <b>Requires</b>: n is in the range [0, this->bucket_count()). 1762 //! 1763 //! <b>Effects</b>: Returns the number of elements in the nth bucket. 1764 //! 1765 //! <b>Complexity</b>: Constant. 1766 //! 1767 //! <b>Throws</b>: Nothing. bucket_size(size_type n) const1768 size_type bucket_size(size_type n) const 1769 { return this->priv_buckets()[n].size(); } 1770 1771 //! <b>Effects</b>: Returns the index of the bucket in which elements 1772 //! with keys equivalent to k would be found, if any such element existed. 1773 //! 1774 //! <b>Complexity</b>: Constant. 1775 //! 1776 //! <b>Throws</b>: If the hash functor throws. 1777 //! 1778 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()). bucket(const key_type & k) const1779 size_type bucket(const key_type& k) const 1780 { return this->bucket(k, this->priv_hasher()); } 1781 1782 //! <b>Requires</b>: "hash_func" must be a hash function that induces 1783 //! the same hash values as the stored hasher. The difference is that 1784 //! "hash_func" hashes the given key instead of the value_type. 1785 //! 1786 //! <b>Effects</b>: Returns the index of the bucket in which elements 1787 //! with keys equivalent to k would be found, if any such element existed. 1788 //! 1789 //! <b>Complexity</b>: Constant. 1790 //! 1791 //! <b>Throws</b>: If hash_func throws. 1792 //! 1793 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()). 1794 template<class KeyType, class KeyHasher> bucket(const KeyType & k,const KeyHasher & hash_func) const1795 size_type bucket(const KeyType& k, const KeyHasher &hash_func) const 1796 { return priv_hash_to_bucket(hash_func(k)); } 1797 1798 //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor 1799 //! or the last rehash function. 1800 //! 1801 //! <b>Complexity</b>: Constant. 1802 //! 1803 //! <b>Throws</b>: Nothing. bucket_pointer() const1804 bucket_ptr bucket_pointer() const 1805 { return this->priv_buckets(); } 1806 1807 //! <b>Requires</b>: n is in the range [0, this->bucket_count()). 1808 //! 1809 //! <b>Effects</b>: Returns a local_iterator pointing to the beginning 1810 //! of the sequence stored in the bucket n. 1811 //! 1812 //! <b>Complexity</b>: Constant. 1813 //! 1814 //! <b>Throws</b>: Nothing. 1815 //! 1816 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range 1817 //! containing all of the elements in the nth bucket. begin(size_type n)1818 local_iterator begin(size_type n) 1819 { return local_iterator(this->priv_buckets()[n].begin(), this); } 1820 1821 //! <b>Requires</b>: n is in the range [0, this->bucket_count()). 1822 //! 1823 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning 1824 //! of the sequence stored in the bucket n. 1825 //! 1826 //! <b>Complexity</b>: Constant. 1827 //! 1828 //! <b>Throws</b>: Nothing. 1829 //! 1830 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range 1831 //! containing all of the elements in the nth bucket. begin(size_type n) const1832 const_local_iterator begin(size_type n) const 1833 { return this->cbegin(n); } 1834 1835 //! <b>Requires</b>: n is in the range [0, this->bucket_count()). 1836 //! 1837 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning 1838 //! of the sequence stored in the bucket n. 1839 //! 1840 //! <b>Complexity</b>: Constant. 1841 //! 1842 //! <b>Throws</b>: Nothing. 1843 //! 1844 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range 1845 //! containing all of the elements in the nth bucket. cbegin(size_type n) const1846 const_local_iterator cbegin(size_type n) const 1847 { 1848 siterator sit = const_cast<bucket_type&>(this->priv_buckets()[n]).begin(); 1849 return const_local_iterator(sit, this); 1850 } 1851 1852 //! <b>Requires</b>: n is in the range [0, this->bucket_count()). 1853 //! 1854 //! <b>Effects</b>: Returns a local_iterator pointing to the end 1855 //! of the sequence stored in the bucket n. 1856 //! 1857 //! <b>Complexity</b>: Constant. 1858 //! 1859 //! <b>Throws</b>: Nothing. 1860 //! 1861 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range 1862 //! containing all of the elements in the nth bucket. end(size_type n)1863 local_iterator end(size_type n) 1864 { return local_iterator(this->priv_buckets()[n].end(), this); } 1865 1866 //! <b>Requires</b>: n is in the range [0, this->bucket_count()). 1867 //! 1868 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end 1869 //! of the sequence stored in the bucket n. 1870 //! 1871 //! <b>Complexity</b>: Constant. 1872 //! 1873 //! <b>Throws</b>: Nothing. 1874 //! 1875 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range 1876 //! containing all of the elements in the nth bucket. end(size_type n) const1877 const_local_iterator end(size_type n) const 1878 { return this->cend(n); } 1879 1880 //! <b>Requires</b>: n is in the range [0, this->bucket_count()). 1881 //! 1882 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end 1883 //! of the sequence stored in the bucket n. 1884 //! 1885 //! <b>Complexity</b>: Constant. 1886 //! 1887 //! <b>Throws</b>: Nothing. 1888 //! 1889 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range 1890 //! containing all of the elements in the nth bucket. cend(size_type n) const1891 const_local_iterator cend(size_type n) const 1892 { return const_local_iterator(const_cast<bucket_type&>(this->priv_buckets()[n]).end(), this); } 1893 1894 //! <b>Requires</b>: new_buckets must be a pointer to a new bucket array 1895 //! or the same as the old bucket array. new_size is the length of the 1896 //! the array pointed by new_buckets. If new_buckets == this->bucket_pointer() 1897 //! n can be bigger or smaller than this->bucket_count(). 1898 //! 'new_bucket_traits' copy constructor should not throw. 1899 //! 1900 //! <b>Effects</b>: Updates the internal reference with the new bucket erases 1901 //! the values from the old bucket and inserts then in the new one. 1902 //! Bucket traits hold by *this is assigned from new_bucket_traits. 1903 //! If the container is configured as incremental<>, the split bucket is set 1904 //! to the new bucket_len(). 1905 //! 1906 //! If store_hash option is true, this method does not use the hash function. 1907 //! 1908 //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic. 1909 //! 1910 //! <b>Throws</b>: If the hasher functor throws. Basic guarantee. rehash(const bucket_traits & new_bucket_traits)1911 void rehash(const bucket_traits &new_bucket_traits) 1912 { 1913 bucket_ptr new_buckets = new_bucket_traits.bucket_begin(); 1914 size_type new_buckets_len = new_bucket_traits.bucket_count(); 1915 bucket_ptr old_buckets = this->priv_buckets(); 1916 size_type old_buckets_len = this->priv_buckets_len(); 1917 1918 //Check power of two bucket array if the option is activated 1919 BOOST_INTRUSIVE_INVARIANT_ASSERT 1920 (!power_2_buckets || (0 == (new_buckets_len & (new_buckets_len-1u)))); 1921 1922 size_type n = priv_get_cache_bucket_num(); 1923 const bool same_buffer = old_buckets == new_buckets; 1924 //If the new bucket length is a common factor 1925 //of the old one we can avoid hash calculations. 1926 const bool fast_shrink = (!incremental) && (old_buckets_len > new_buckets_len) && 1927 (power_2_buckets ||(old_buckets_len % new_buckets_len) == 0); 1928 //If we are shrinking the same bucket array and it's 1929 //is a fast shrink, just rehash the last nodes 1930 size_type new_first_bucket_num = new_buckets_len; 1931 if(same_buffer && fast_shrink && (n < new_buckets_len)){ 1932 n = new_buckets_len; 1933 new_first_bucket_num = priv_get_cache_bucket_num(); 1934 } 1935 1936 //Anti-exception stuff: they destroy the elements if something goes wrong. 1937 //If the source and destination buckets are the same, the second rollback function 1938 //is harmless, because all elements have been already unlinked and destroyed 1939 typedef detail::init_disposer<node_algorithms> NodeDisposer; 1940 NodeDisposer node_disp; 1941 detail::exception_array_disposer<bucket_type, NodeDisposer> 1942 rollback1(new_buckets[0], node_disp, new_buckets_len); 1943 detail::exception_array_disposer<bucket_type, NodeDisposer> 1944 rollback2(old_buckets[0], node_disp, old_buckets_len); 1945 1946 //Put size in a safe value for rollback exception 1947 size_type size_backup = this->priv_size_traits().get_size(); 1948 this->priv_size_traits().set_size(0); 1949 //Put cache to safe position 1950 priv_initialize_cache(); 1951 priv_insertion_update_cache(size_type(0u)); 1952 1953 //Iterate through nodes 1954 for(; n < old_buckets_len; ++n){ 1955 bucket_type &old_bucket = old_buckets[n]; 1956 1957 if(!fast_shrink){ 1958 siterator before_i(old_bucket.before_begin()); 1959 siterator end(old_bucket.end()); 1960 siterator i(old_bucket.begin()); 1961 for(;i != end; ++i){ 1962 const value_type &v = priv_value_from_slist_node(i.pointed_node()); 1963 const std::size_t hash_value = this->priv_stored_or_compute_hash(v, store_hash_t()); 1964 const size_type new_n = priv_hash_to_bucket(hash_value, new_buckets_len, new_buckets_len); 1965 if(cache_begin && new_n < new_first_bucket_num) 1966 new_first_bucket_num = new_n; 1967 siterator last = bucket_type::s_iterator_to 1968 (*group_functions_t::priv_get_last_in_group 1969 (dcast_bucket_ptr(i.pointed_node()), optimize_multikey_t())); 1970 if(same_buffer && new_n == n){ 1971 before_i = last; 1972 } 1973 else{ 1974 bucket_type &new_b = new_buckets[new_n]; 1975 new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last); 1976 } 1977 i = before_i; 1978 } 1979 } 1980 else{ 1981 const size_type new_n = priv_hash_to_bucket(n, new_buckets_len, new_buckets_len); 1982 if(cache_begin && new_n < new_first_bucket_num) 1983 new_first_bucket_num = new_n; 1984 bucket_type &new_b = new_buckets[new_n]; 1985 if(!old_bucket.empty()){ 1986 new_b.splice_after( new_b.before_begin() 1987 , old_bucket 1988 , old_bucket.before_begin() 1989 , priv_get_last(old_bucket)); 1990 } 1991 } 1992 } 1993 1994 this->priv_size_traits().set_size(size_backup); 1995 this->priv_split_traits().set_size(new_buckets_len); 1996 this->priv_real_bucket_traits() = new_bucket_traits; 1997 priv_initialize_cache(); 1998 priv_insertion_update_cache(new_first_bucket_num); 1999 rollback1.release(); 2000 rollback2.release(); 2001 } 2002 2003 //! <b>Requires</b>: 2004 //! 2005 //! <b>Effects</b>: 2006 //! 2007 //! <b>Complexity</b>: 2008 //! 2009 //! <b>Throws</b>: 2010 //! 2011 //! <b>Note</b>: this method is only available if incremental<true> option is activated. incremental_rehash(bool grow=true)2012 bool incremental_rehash(bool grow = true) 2013 { 2014 //This function is only available for containers with incremental hashing 2015 BOOST_STATIC_ASSERT(( incremental && power_2_buckets )); 2016 size_type split_idx = priv_split_traits().get_size(); 2017 size_type bucket_len = priv_buckets_len(); 2018 2019 if(grow){ 2020 //Test if the split variable can be changed 2021 if(split_idx >= bucket_len) 2022 return false; 2023 2024 size_type bucket_len = priv_buckets_len(); 2025 size_type bucket_to_rehash = split_idx - bucket_len/2; 2026 bucket_type &old_bucket = this->priv_buckets()[bucket_to_rehash]; 2027 siterator before_i(old_bucket.before_begin()); 2028 siterator end(old_bucket.end()); 2029 siterator i(old_bucket.begin()); 2030 priv_split_traits().increment(); 2031 2032 //Anti-exception stuff: if an exception is thrown while 2033 //moving elements from old_bucket to the target bucket, all moved 2034 //elements are moved back to the original one. 2035 detail::incremental_rehash_rollback<bucket_type, split_traits> rollback 2036 ( this->priv_buckets()[split_idx], old_bucket, priv_split_traits()); 2037 for(;i != end; ++i){ 2038 const value_type &v = priv_value_from_slist_node(i.pointed_node()); 2039 const std::size_t hash_value = this->priv_stored_or_compute_hash(v, store_hash_t()); 2040 const size_type new_n = priv_hash_to_bucket(hash_value); 2041 siterator last = bucket_type::s_iterator_to 2042 (*group_functions_t::priv_get_last_in_group 2043 (dcast_bucket_ptr(i.pointed_node()), optimize_multikey_t())); 2044 if(new_n == bucket_to_rehash){ 2045 before_i = last; 2046 } 2047 else{ 2048 bucket_type &new_b = this->priv_buckets()[new_n]; 2049 new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last); 2050 } 2051 i = before_i; 2052 } 2053 rollback.release(); 2054 priv_erasure_update_cache(); 2055 return true; 2056 } 2057 else{ 2058 //Test if the split variable can be changed 2059 if(split_idx <= bucket_len/2) 2060 return false; 2061 const size_type target_bucket_num = split_idx - 1 - bucket_len/2; 2062 bucket_type &target_bucket = this->priv_buckets()[target_bucket_num]; 2063 bucket_type &source_bucket = this->priv_buckets()[split_idx-1]; 2064 target_bucket.splice_after(target_bucket.cbefore_begin(), source_bucket); 2065 priv_split_traits().decrement(); 2066 priv_insertion_update_cache(target_bucket_num); 2067 return true; 2068 } 2069 } 2070 2071 //! <b>Effects</b>: If new_bucket_traits.bucket_count() is not 2072 //! this->bucket_count()/2 or this->bucket_count()*2, or 2073 //! this->split_bucket() != new_bucket_traits.bucket_count() returns false 2074 //! and does nothing. 2075 //! 2076 //! Otherwise, copy assigns new_bucket_traits to the internal bucket_traits 2077 //! and transfers all the objects from old buckets to the new ones. 2078 //! 2079 //! <b>Complexity</b>: Linear to size(). 2080 //! 2081 //! <b>Throws</b>: Nothing 2082 //! 2083 //! <b>Note</b>: this method is only available if incremental<true> option is activated. incremental_rehash(const bucket_traits & new_bucket_traits)2084 bool incremental_rehash(const bucket_traits &new_bucket_traits) 2085 { 2086 //This function is only available for containers with incremental hashing 2087 BOOST_STATIC_ASSERT(( incremental && power_2_buckets )); 2088 size_type new_bucket_traits_size = new_bucket_traits.bucket_count(); 2089 size_type cur_bucket_traits = this->priv_buckets_len(); 2090 if(new_bucket_traits_size/2 != cur_bucket_traits && new_bucket_traits_size != cur_bucket_traits/2){ 2091 return false; 2092 } 2093 2094 const size_type split_idx = this->split_count(); 2095 2096 if(new_bucket_traits_size/2 == cur_bucket_traits){ 2097 //Test if the split variable can be changed 2098 if(!(split_idx >= cur_bucket_traits)) 2099 return false; 2100 } 2101 else{ 2102 //Test if the split variable can be changed 2103 if(!(split_idx <= cur_bucket_traits/2)) 2104 return false; 2105 } 2106 2107 const size_type ini_n = priv_get_cache_bucket_num(); 2108 const bucket_ptr old_buckets = this->priv_buckets(); 2109 this->priv_real_bucket_traits() = new_bucket_traits; 2110 if(new_bucket_traits.bucket_begin() != old_buckets){ 2111 for(size_type n = ini_n; n < split_idx; ++n){ 2112 bucket_type &new_bucket = new_bucket_traits.bucket_begin()[n]; 2113 bucket_type &old_bucket = old_buckets[n]; 2114 new_bucket.splice_after(new_bucket.cbefore_begin(), old_bucket); 2115 } 2116 //Put cache to safe position 2117 priv_initialize_cache(); 2118 priv_insertion_update_cache(ini_n); 2119 } 2120 return true; 2121 } 2122 2123 //! <b>Requires</b>: 2124 //! 2125 //! <b>Effects</b>: 2126 //! 2127 //! <b>Complexity</b>: 2128 //! 2129 //! <b>Throws</b>: split_count() const2130 size_type split_count() const 2131 { 2132 //This function is only available if incremental hashing is activated 2133 BOOST_STATIC_ASSERT(( incremental && power_2_buckets )); 2134 return this->priv_split_traits().get_size(); 2135 } 2136 2137 //! <b>Effects</b>: Returns the nearest new bucket count optimized for 2138 //! the container that is bigger or equal than n. This suggestion can be 2139 //! used to create bucket arrays with a size that will usually improve 2140 //! container's performance. If such value does not exist, the 2141 //! higher possible value is returned. 2142 //! 2143 //! <b>Complexity</b>: Amortized constant time. 2144 //! 2145 //! <b>Throws</b>: Nothing. suggested_upper_bucket_count(size_type n)2146 static size_type suggested_upper_bucket_count(size_type n) 2147 { 2148 const std::size_t *primes = &detail::prime_list_holder<0>::prime_list[0]; 2149 const std::size_t *primes_end = primes + detail::prime_list_holder<0>::prime_list_size; 2150 size_type const* bound = std::lower_bound(primes, primes_end, n); 2151 if(bound == primes_end) 2152 --bound; 2153 return size_type(*bound); 2154 } 2155 2156 //! <b>Effects</b>: Returns the nearest new bucket count optimized for 2157 //! the container that is smaller or equal than n. This suggestion can be 2158 //! used to create bucket arrays with a size that will usually improve 2159 //! container's performance. If such value does not exist, the 2160 //! lowest possible value is returned. 2161 //! 2162 //! <b>Complexity</b>: Amortized constant time. 2163 //! 2164 //! <b>Throws</b>: Nothing. suggested_lower_bucket_count(size_type n)2165 static size_type suggested_lower_bucket_count(size_type n) 2166 { 2167 const std::size_t *primes = &detail::prime_list_holder<0>::prime_list[0]; 2168 const std::size_t *primes_end = primes + detail::prime_list_holder<0>::prime_list_size; 2169 size_type const* bound = std::upper_bound(primes, primes_end, n); 2170 if(bound != primes) 2171 --bound; 2172 return size_type(*bound); 2173 } 2174 2175 /// @cond 2176 private: 2177 priv_hash_to_bucket(std::size_t hash_value) const2178 std::size_t priv_hash_to_bucket(std::size_t hash_value) const 2179 { return priv_hash_to_bucket(hash_value, this->priv_real_bucket_traits().bucket_count(), priv_split_traits().get_size()); } 2180 priv_hash_to_bucket(std::size_t hash_value,std::size_t bucket_len,std::size_t split) const2181 std::size_t priv_hash_to_bucket(std::size_t hash_value, std::size_t bucket_len, std::size_t split) const 2182 { 2183 std::size_t bucket_number = priv_hash_to_bucket_impl(hash_value, bucket_len, power_2_buckets_t()); 2184 if(incremental) 2185 if(bucket_number >= split) 2186 bucket_number -= bucket_len/2; 2187 return bucket_number; 2188 } 2189 priv_hash_to_bucket_impl(std::size_t hash_value,std::size_t bucket_len,detail::bool_<false>) const2190 std::size_t priv_hash_to_bucket_impl(std::size_t hash_value, std::size_t bucket_len, detail::bool_<false>) const 2191 { return hash_value % bucket_len; } 2192 priv_hash_to_bucket_impl(std::size_t hash_value,std::size_t bucket_len,detail::bool_<true>) const2193 std::size_t priv_hash_to_bucket_impl(std::size_t hash_value, std::size_t bucket_len, detail::bool_<true>) const 2194 { return hash_value & (bucket_len - 1); } 2195 priv_equal() const2196 const key_equal &priv_equal() const 2197 { return static_cast<const key_equal&>(this->data_.internal_.bucket_hash_equal_.get()); } 2198 priv_equal()2199 key_equal &priv_equal() 2200 { return static_cast<key_equal&>(this->data_.internal_.bucket_hash_equal_.get()); } 2201 priv_value_from_slist_node(slist_node_ptr n)2202 value_type &priv_value_from_slist_node(slist_node_ptr n) 2203 { return *this->get_real_value_traits().to_value_ptr(dcast_bucket_ptr(n)); } 2204 priv_value_from_slist_node(slist_node_ptr n) const2205 const value_type &priv_value_from_slist_node(slist_node_ptr n) const 2206 { return *this->get_real_value_traits().to_value_ptr(dcast_bucket_ptr(n)); } 2207 priv_real_bucket_traits(detail::bool_<false>) const2208 const real_bucket_traits &priv_real_bucket_traits(detail::bool_<false>) const 2209 { return this->data_.internal_.bucket_hash_equal_.bucket_hash.bucket_plus_size_.bucket_traits_; } 2210 priv_real_bucket_traits(detail::bool_<true>) const2211 const real_bucket_traits &priv_real_bucket_traits(detail::bool_<true>) const 2212 { return this->data_.internal_.bucket_hash_equal_.bucket_hash.bucket_plus_size_.bucket_traits_.get_bucket_traits(*this); } 2213 priv_real_bucket_traits(detail::bool_<false>)2214 real_bucket_traits &priv_real_bucket_traits(detail::bool_<false>) 2215 { return this->data_.internal_.bucket_hash_equal_.bucket_hash.bucket_plus_size_.bucket_traits_; } 2216 priv_real_bucket_traits(detail::bool_<true>)2217 real_bucket_traits &priv_real_bucket_traits(detail::bool_<true>) 2218 { return this->data_.internal_.bucket_hash_equal_.bucket_hash.bucket_plus_size_.bucket_traits_.get_bucket_traits(*this); } 2219 priv_real_bucket_traits() const2220 const real_bucket_traits &priv_real_bucket_traits() const 2221 { return this->priv_real_bucket_traits(detail::bool_<external_bucket_traits>()); } 2222 priv_real_bucket_traits()2223 real_bucket_traits &priv_real_bucket_traits() 2224 { return this->priv_real_bucket_traits(detail::bool_<external_bucket_traits>()); } 2225 priv_hasher() const2226 const hasher &priv_hasher() const 2227 { return static_cast<const hasher&>(this->data_.internal_.bucket_hash_equal_.bucket_hash.get()); } 2228 priv_hasher()2229 hasher &priv_hasher() 2230 { return static_cast<hasher&>(this->data_.internal_.bucket_hash_equal_.bucket_hash.get()); } 2231 priv_buckets() const2232 bucket_ptr priv_buckets() const 2233 { return this->priv_real_bucket_traits().bucket_begin(); } 2234 priv_buckets_len() const2235 size_type priv_buckets_len() const 2236 { return this->priv_real_bucket_traits().bucket_count(); } 2237 uncast(const_node_ptr ptr)2238 static node_ptr uncast(const_node_ptr ptr) 2239 { return node_ptr(const_cast<node*>(detail::boost_intrusive_get_pointer(ptr))); } 2240 priv_value_to_node(value_type & v)2241 node &priv_value_to_node(value_type &v) 2242 { return *this->get_real_value_traits().to_node_ptr(v); } 2243 priv_value_to_node(const value_type & v) const2244 const node &priv_value_to_node(const value_type &v) const 2245 { return *this->get_real_value_traits().to_node_ptr(v); } 2246 priv_size_traits()2247 size_traits &priv_size_traits() 2248 { return this->data_.internal_.bucket_hash_equal_.bucket_hash.bucket_plus_size_; } 2249 priv_size_traits() const2250 const size_traits &priv_size_traits() const 2251 { return this->data_.internal_.bucket_hash_equal_.bucket_hash.bucket_plus_size_; } 2252 priv_split_traits()2253 split_traits &priv_split_traits() 2254 { return this->data_.internal_; } 2255 priv_split_traits() const2256 const split_traits &priv_split_traits() const 2257 { return this->data_.internal_; } 2258 2259 template<class Disposer> priv_erase_range_impl(size_type bucket_num,siterator before_first_it,siterator end,Disposer disposer,size_type & num_erased)2260 void priv_erase_range_impl 2261 (size_type bucket_num, siterator before_first_it, siterator end, Disposer disposer, size_type &num_erased) 2262 { 2263 const bucket_ptr buckets = priv_buckets(); 2264 bucket_type &b = buckets[bucket_num]; 2265 2266 if(before_first_it == b.before_begin() && end == b.end()){ 2267 priv_erase_range_impl(bucket_num, 1, disposer, num_erased); 2268 } 2269 else{ 2270 num_erased = 0; 2271 siterator to_erase(before_first_it); 2272 ++to_erase; 2273 slist_node_ptr end_ptr = end.pointed_node(); 2274 while(to_erase != end){ 2275 group_functions_t::priv_erase_from_group(end_ptr, dcast_bucket_ptr(to_erase.pointed_node()), optimize_multikey_t()); 2276 to_erase = b.erase_after_and_dispose(before_first_it, make_node_disposer(disposer)); 2277 ++num_erased; 2278 } 2279 this->priv_size_traits().set_size(this->priv_size_traits().get_size()-num_erased); 2280 } 2281 } 2282 2283 template<class Disposer> priv_erase_range_impl(size_type first_bucket_num,size_type num_buckets,Disposer disposer,size_type & num_erased)2284 void priv_erase_range_impl 2285 (size_type first_bucket_num, size_type num_buckets, Disposer disposer, size_type &num_erased) 2286 { 2287 //Now fully clear the intermediate buckets 2288 const bucket_ptr buckets = priv_buckets(); 2289 num_erased = 0; 2290 for(size_type i = first_bucket_num; i < (num_buckets + first_bucket_num); ++i){ 2291 bucket_type &b = buckets[i]; 2292 siterator b_begin(b.before_begin()); 2293 siterator nxt(b_begin); 2294 ++nxt; 2295 siterator end(b.end()); 2296 while(nxt != end){ 2297 priv_init_group(nxt.pointed_node(), optimize_multikey_t()); 2298 nxt = b.erase_after_and_dispose 2299 (b_begin, make_node_disposer(disposer)); 2300 this->priv_size_traits().decrement(); 2301 ++num_erased; 2302 } 2303 } 2304 } 2305 2306 template<class Disposer> priv_erase_range(siterator before_first_it,size_type first_bucket,siterator last_it,size_type last_bucket,Disposer disposer)2307 void priv_erase_range( siterator before_first_it, size_type first_bucket 2308 , siterator last_it, size_type last_bucket 2309 , Disposer disposer) 2310 { 2311 size_type num_erased; 2312 if (first_bucket == last_bucket){ 2313 priv_erase_range_impl(first_bucket, before_first_it, last_it, disposer, num_erased); 2314 } 2315 else { 2316 bucket_type *b = (&this->priv_buckets()[0]); 2317 priv_erase_range_impl(first_bucket, before_first_it, b[first_bucket].end(), disposer, num_erased); 2318 if(size_type n = (last_bucket - first_bucket - 1)) 2319 priv_erase_range_impl(first_bucket + 1, n, disposer, num_erased); 2320 priv_erase_range_impl(last_bucket, b[last_bucket].before_begin(), last_it, disposer, num_erased); 2321 } 2322 } 2323 dcast_bucket_ptr(typename slist_impl::node_ptr p)2324 static node_ptr dcast_bucket_ptr(typename slist_impl::node_ptr p) 2325 { 2326 // This still fails in gcc < 4.4 so forget about it 2327 // using ::boost::static_pointer_cast; 2328 // return static_pointer_cast<node>(p); 2329 return node_ptr(&static_cast<node&>(*p)); 2330 } 2331 priv_stored_or_compute_hash(const value_type & v,detail::true_) const2332 std::size_t priv_stored_or_compute_hash(const value_type &v, detail::true_) const 2333 { return node_traits::get_hash(this->get_real_value_traits().to_node_ptr(v)); } 2334 priv_stored_or_compute_hash(const value_type & v,detail::false_) const2335 std::size_t priv_stored_or_compute_hash(const value_type &v, detail::false_) const 2336 { return priv_hasher()(v); } 2337 priv_stored_hash(slist_node_ptr n,detail::true_) const2338 std::size_t priv_stored_hash(slist_node_ptr n, detail::true_) const 2339 { return node_traits::get_hash(dcast_bucket_ptr(n)); } 2340 priv_stored_hash(slist_node_ptr,detail::false_) const2341 std::size_t priv_stored_hash(slist_node_ptr, detail::false_) const 2342 { 2343 //This code should never be reached! 2344 BOOST_INTRUSIVE_INVARIANT_ASSERT(0); 2345 return 0; 2346 } 2347 priv_store_hash(node_ptr p,std::size_t h,detail::true_)2348 static void priv_store_hash(node_ptr p, std::size_t h, detail::true_) 2349 { return node_traits::set_hash(p, h); } 2350 priv_store_hash(node_ptr,std::size_t,detail::false_)2351 static void priv_store_hash(node_ptr, std::size_t, detail::false_) 2352 {} 2353 priv_clear_group_nodes(bucket_type & b,detail::true_)2354 static void priv_clear_group_nodes(bucket_type &b, detail::true_) 2355 { 2356 siterator it(b.begin()), itend(b.end()); 2357 while(it != itend){ 2358 node_ptr to_erase(dcast_bucket_ptr(it.pointed_node())); 2359 ++it; 2360 group_algorithms::init(to_erase); 2361 } 2362 } 2363 priv_clear_group_nodes(bucket_type &,detail::false_)2364 static void priv_clear_group_nodes(bucket_type &, detail::false_) 2365 {} 2366 priv_get_bucket_num(siterator it)2367 std::size_t priv_get_bucket_num(siterator it) 2368 { return priv_get_bucket_num_hash_dispatch(it, store_hash_t()); } 2369 priv_get_bucket_num_hash_dispatch(siterator it,detail::true_)2370 std::size_t priv_get_bucket_num_hash_dispatch(siterator it, detail::true_) 2371 { 2372 return this->priv_hash_to_bucket 2373 (this->priv_stored_hash(it.pointed_node(), store_hash_t())); 2374 } 2375 priv_get_bucket_num_hash_dispatch(siterator it,detail::false_)2376 std::size_t priv_get_bucket_num_hash_dispatch(siterator it, detail::false_) 2377 { return priv_get_bucket_num_no_hash_store(it, optimize_multikey_t()); } 2378 priv_get_bucket_num_no_hash_store(siterator it,detail::true_)2379 std::size_t priv_get_bucket_num_no_hash_store(siterator it, detail::true_) 2380 { 2381 bucket_ptr f(priv_buckets()), l(f + priv_buckets_len() - 1); 2382 slist_node_ptr bb = group_functions_t::priv_get_bucket_before_begin 2383 ( f->end().pointed_node() 2384 , l->end().pointed_node() 2385 , dcast_bucket_ptr(it.pointed_node())); 2386 //Now get the bucket_impl from the iterator 2387 const bucket_type &b = static_cast<const bucket_type&> 2388 (bucket_type::slist_type::container_from_end_iterator(bucket_type::s_iterator_to(*bb))); 2389 //Now just calculate the index b has in the bucket array 2390 return static_cast<size_type>(&b - &*f); 2391 } 2392 priv_get_bucket_num_no_hash_store(siterator it,detail::false_)2393 std::size_t priv_get_bucket_num_no_hash_store(siterator it, detail::false_) 2394 { 2395 bucket_ptr f(priv_buckets()), l(f + priv_buckets_len() - 1); 2396 slist_node_ptr first_ptr(f->cend().pointed_node()) 2397 , last_ptr(l->cend().pointed_node()); 2398 2399 //The end node is embedded in the singly linked list: 2400 //iterate until we reach it. 2401 while(!(first_ptr <= it.pointed_node() && it.pointed_node() <= last_ptr)){ 2402 ++it; 2403 } 2404 //Now get the bucket_impl from the iterator 2405 const bucket_type &b = static_cast<const bucket_type&> 2406 (bucket_type::container_from_end_iterator(it)); 2407 2408 //Now just calculate the index b has in the bucket array 2409 return static_cast<std::size_t>(&b - &*f); 2410 } 2411 priv_init_group(slist_node_ptr n,detail::true_)2412 void priv_init_group(slist_node_ptr n, detail::true_) 2413 { group_algorithms::init(dcast_bucket_ptr(n)); } 2414 priv_init_group(slist_node_ptr,detail::false_)2415 void priv_init_group(slist_node_ptr, detail::false_) 2416 {} 2417 priv_insert_in_group(node_ptr first_in_group,node_ptr n,detail::true_)2418 void priv_insert_in_group(node_ptr first_in_group, node_ptr n, detail::true_) 2419 { 2420 if(first_in_group){ 2421 if(group_algorithms::unique(first_in_group)) 2422 group_algorithms::link_after(first_in_group, n); 2423 else{ 2424 group_algorithms::link_after(node_traits::get_next(first_in_group), n); 2425 } 2426 } 2427 else{ 2428 group_algorithms::init_header(n); 2429 } 2430 } 2431 priv_insert_in_group(node_ptr,node_ptr,detail::false_)2432 void priv_insert_in_group(node_ptr, node_ptr, detail::false_) 2433 {} 2434 priv_get_previous(bucket_type & b,siterator i)2435 siterator priv_get_previous 2436 (bucket_type &b, siterator i) 2437 { return priv_get_previous(b, i, optimize_multikey_t()); } 2438 priv_get_previous(bucket_type & b,siterator i,detail::true_)2439 siterator priv_get_previous 2440 (bucket_type &b, siterator i, detail::true_) 2441 { 2442 node_ptr elem(dcast_bucket_ptr(i.pointed_node())); 2443 node_ptr prev_in_group(group_traits::get_next(elem)); 2444 bool first_in_group = node_traits::get_next(prev_in_group) != elem; 2445 typename bucket_type::node &n = first_in_group 2446 ? *group_functions_t::priv_get_prev_to_first_in_group(b.end().pointed_node(), elem) 2447 : *group_traits::get_next(elem) 2448 ; 2449 return bucket_type::s_iterator_to(n); 2450 } 2451 priv_get_previous(bucket_type & b,siterator i,detail::false_)2452 siterator priv_get_previous 2453 (bucket_type &b, siterator i, detail::false_) 2454 { return b.previous(i); } 2455 priv_get_last(bucket_type & b)2456 static siterator priv_get_last(bucket_type &b) 2457 { return priv_get_last(b, optimize_multikey_t()); } 2458 priv_get_last(bucket_type & b,detail::true_)2459 static siterator priv_get_last(bucket_type &b, detail::true_) 2460 { 2461 //First find the last node of p's group. 2462 //This requires checking the first node of the next group or 2463 //the bucket node. 2464 slist_node_ptr end_ptr(b.end().pointed_node()); 2465 node_ptr possible_end(node_traits::get_next( dcast_bucket_ptr(end_ptr))); 2466 node_ptr last_node_group(possible_end); 2467 2468 while(end_ptr != possible_end){ 2469 last_node_group = group_traits::get_next(dcast_bucket_ptr(possible_end)); 2470 possible_end = node_traits::get_next(last_node_group); 2471 } 2472 return bucket_type::s_iterator_to(*last_node_group); 2473 } 2474 priv_get_last(bucket_type & b,detail::false_)2475 static siterator priv_get_last(bucket_type &b, detail::false_) 2476 { return b.previous(b.end()); } 2477 priv_get_previous_and_next_in_group(siterator i,node_ptr & nxt_in_group)2478 siterator priv_get_previous_and_next_in_group 2479 (siterator i, node_ptr &nxt_in_group) 2480 { 2481 siterator prev; 2482 node_ptr elem(dcast_bucket_ptr(i.pointed_node())); 2483 bucket_ptr f(priv_buckets()), l(f + priv_buckets_len() - 1); 2484 2485 slist_node_ptr first_end_ptr(f->cend().pointed_node()); 2486 slist_node_ptr last_end_ptr (l->cend().pointed_node()); 2487 2488 node_ptr nxt(node_traits::get_next(elem)); 2489 node_ptr prev_in_group(group_traits::get_next(elem)); 2490 bool last_in_group = (first_end_ptr <= nxt && nxt <= last_end_ptr) || 2491 (group_traits::get_next(nxt) != elem); 2492 bool first_in_group = node_traits::get_next(prev_in_group) != elem; 2493 2494 if(first_in_group){ 2495 node_ptr start_pos; 2496 if(last_in_group){ 2497 start_pos = elem; 2498 nxt_in_group = 0; 2499 } 2500 else{ 2501 start_pos = prev_in_group; 2502 nxt_in_group = node_traits::get_next(elem); 2503 } 2504 slist_node_ptr bucket_node; 2505 if(store_hash){ 2506 bucket_node = this->priv_buckets() 2507 [this->priv_hash_to_bucket 2508 (this->priv_stored_hash(elem, store_hash_t())) 2509 ].before_begin().pointed_node(); 2510 } 2511 else{ 2512 bucket_node = group_functions_t::priv_get_bucket_before_begin 2513 (first_end_ptr, last_end_ptr, start_pos); 2514 } 2515 prev = bucket_type::s_iterator_to 2516 (*group_functions_t::priv_get_prev_to_first_in_group(bucket_node, elem)); 2517 } 2518 else{ 2519 if(last_in_group){ 2520 nxt_in_group = group_functions_t::priv_get_first_in_group_of_last_in_group(elem); 2521 } 2522 else{ 2523 nxt_in_group = node_traits::get_next(elem); 2524 } 2525 prev = bucket_type::s_iterator_to(*group_traits::get_next(elem)); 2526 } 2527 return prev; 2528 } 2529 2530 template<class Disposer> priv_erase(const_iterator i,Disposer disposer,detail::true_)2531 void priv_erase(const_iterator i, Disposer disposer, detail::true_) 2532 { 2533 siterator elem(i.slist_it()); 2534 node_ptr nxt_in_group; 2535 siterator prev = priv_get_previous_and_next_in_group(elem, nxt_in_group); 2536 bucket_type::s_erase_after_and_dispose(prev, make_node_disposer(disposer)); 2537 if(nxt_in_group) 2538 group_algorithms::unlink_after(nxt_in_group); 2539 if(safemode_or_autounlink) 2540 group_algorithms::init(dcast_bucket_ptr(elem.pointed_node())); 2541 } 2542 2543 template <class Disposer> priv_erase(const_iterator i,Disposer disposer,detail::false_)2544 void priv_erase(const_iterator i, Disposer disposer, detail::false_) 2545 { 2546 siterator to_erase(i.slist_it()); 2547 bucket_type &b = this->priv_buckets()[this->priv_get_bucket_num(to_erase)]; 2548 siterator prev(priv_get_previous(b, to_erase)); 2549 b.erase_after_and_dispose(prev, make_node_disposer(disposer)); 2550 } 2551 priv_invalid_bucket() const2552 bucket_ptr priv_invalid_bucket() const 2553 { 2554 const real_bucket_traits &rbt = this->priv_real_bucket_traits(); 2555 return rbt.bucket_begin() + rbt.bucket_count(); 2556 } 2557 priv_invalid_local_it() const2558 siterator priv_invalid_local_it() const 2559 { return priv_invalid_bucket()->end(); } 2560 priv_begin() const2561 siterator priv_begin() const 2562 { return priv_begin(cache_begin_t()); } 2563 priv_begin(detail::bool_<false>) const2564 siterator priv_begin(detail::bool_<false>) const 2565 { 2566 size_type n = 0; 2567 size_type buckets_len = this->priv_buckets_len(); 2568 for (n = 0; n < buckets_len; ++n){ 2569 bucket_type &b = this->priv_buckets()[n]; 2570 if(!b.empty()){ 2571 return b.begin(); 2572 } 2573 } 2574 return priv_invalid_local_it(); 2575 } 2576 priv_begin(detail::bool_<true>) const2577 siterator priv_begin(detail::bool_<true>) const 2578 { 2579 if(this->data_.internal_.bucket_hash_equal_.cached_begin_ == priv_invalid_bucket()){ 2580 return priv_invalid_local_it(); 2581 } 2582 else{ 2583 return this->data_.internal_.bucket_hash_equal_.cached_begin_->begin(); 2584 } 2585 } 2586 priv_initialize_cache()2587 void priv_initialize_cache() 2588 { priv_initialize_cache(cache_begin_t()); } 2589 priv_initialize_cache(detail::bool_<true>)2590 void priv_initialize_cache(detail::bool_<true>) 2591 { this->data_.internal_.bucket_hash_equal_.cached_begin_ = priv_invalid_bucket(); } 2592 priv_initialize_cache(detail::bool_<false>)2593 void priv_initialize_cache(detail::bool_<false>) 2594 {} 2595 priv_insertion_update_cache(size_type insertion_bucket)2596 void priv_insertion_update_cache(size_type insertion_bucket) 2597 { priv_insertion_update_cache(insertion_bucket, cache_begin_t()); } 2598 priv_insertion_update_cache(size_type insertion_bucket,detail::bool_<true>)2599 void priv_insertion_update_cache(size_type insertion_bucket, detail::bool_<true>) 2600 { 2601 bucket_ptr p = priv_buckets() + insertion_bucket; 2602 if(p < this->data_.internal_.bucket_hash_equal_.cached_begin_){ 2603 this->data_.internal_.bucket_hash_equal_.cached_begin_ = p; 2604 } 2605 } 2606 priv_insertion_update_cache(size_type,detail::bool_<false>)2607 void priv_insertion_update_cache(size_type, detail::bool_<false>) 2608 {} 2609 priv_erasure_update_cache(size_type first_bucket,size_type last_bucket)2610 void priv_erasure_update_cache(size_type first_bucket, size_type last_bucket) 2611 { priv_erasure_update_cache(first_bucket, last_bucket, cache_begin_t()); } 2612 priv_erasure_update_cache(size_type first_bucket_num,size_type last_bucket_num,detail::bool_<true>)2613 void priv_erasure_update_cache(size_type first_bucket_num, size_type last_bucket_num, detail::bool_<true>) 2614 { 2615 //If the last bucket is the end, the cache must be updated 2616 //to the last position if all 2617 if(priv_get_cache_bucket_num() == first_bucket_num && 2618 priv_buckets()[first_bucket_num].empty() ){ 2619 priv_set_cache(priv_buckets() + last_bucket_num); 2620 priv_erasure_update_cache(); 2621 } 2622 } 2623 priv_erasure_update_cache(size_type,size_type,detail::bool_<false>)2624 void priv_erasure_update_cache(size_type, size_type, detail::bool_<false>) 2625 {} 2626 priv_erasure_update_cache()2627 void priv_erasure_update_cache() 2628 { priv_erasure_update_cache(cache_begin_t()); } 2629 priv_erasure_update_cache(detail::bool_<true>)2630 void priv_erasure_update_cache(detail::bool_<true>) 2631 { 2632 if(constant_time_size && !size()){ 2633 priv_initialize_cache(); 2634 } 2635 else{ 2636 size_type current_n = this->data_.internal_.bucket_hash_equal_.cached_begin_ - priv_buckets(); 2637 for( const size_type num_buckets = this->priv_buckets_len() 2638 ; current_n < num_buckets 2639 ; ++current_n, ++this->data_.internal_.bucket_hash_equal_.cached_begin_){ 2640 if(!this->data_.internal_.bucket_hash_equal_.cached_begin_->empty()){ 2641 return; 2642 } 2643 } 2644 priv_initialize_cache(); 2645 } 2646 } 2647 priv_erasure_update_cache(detail::bool_<false>)2648 void priv_erasure_update_cache(detail::bool_<false>) 2649 {} 2650 priv_swap_cache(detail::bool_<true>,hashtable_impl & other)2651 void priv_swap_cache(detail::bool_<true>, hashtable_impl &other) 2652 { 2653 std::swap( this->data_.internal_.bucket_hash_equal_.cached_begin_ 2654 , other.data_.internal_.bucket_hash_equal_.cached_begin_); 2655 } 2656 priv_swap_cache(detail::bool_<false>,hashtable_impl &)2657 void priv_swap_cache(detail::bool_<false>, hashtable_impl &) 2658 {} 2659 priv_get_cache()2660 bucket_ptr priv_get_cache() 2661 { return priv_get_cache(cache_begin_t()); } 2662 priv_get_cache(detail::bool_<true>)2663 bucket_ptr priv_get_cache(detail::bool_<true>) 2664 { return this->data_.internal_.bucket_hash_equal_.cached_begin_; } 2665 priv_get_cache(detail::bool_<false>)2666 bucket_ptr priv_get_cache(detail::bool_<false>) 2667 { return this->priv_buckets(); } 2668 priv_set_cache(bucket_ptr p)2669 void priv_set_cache(bucket_ptr p) 2670 { priv_set_cache(p, cache_begin_t()); } 2671 priv_set_cache(bucket_ptr p,detail::bool_<true>)2672 void priv_set_cache(bucket_ptr p, detail::bool_<true>) 2673 { this->data_.internal_.bucket_hash_equal_.cached_begin_ = p; } 2674 priv_set_cache(bucket_ptr,detail::bool_<false>)2675 void priv_set_cache(bucket_ptr, detail::bool_<false>) 2676 {} 2677 priv_get_cache_bucket_num()2678 size_type priv_get_cache_bucket_num() 2679 { return priv_get_cache_bucket_num(cache_begin_t()); } 2680 priv_get_cache_bucket_num(detail::bool_<true>)2681 size_type priv_get_cache_bucket_num(detail::bool_<true>) 2682 { return this->data_.internal_.bucket_hash_equal_.cached_begin_ - this->priv_buckets(); } 2683 priv_get_cache_bucket_num(detail::bool_<false>)2684 size_type priv_get_cache_bucket_num(detail::bool_<false>) 2685 { return 0u; } 2686 priv_clear_buckets()2687 void priv_clear_buckets() 2688 { 2689 this->priv_clear_buckets 2690 ( priv_get_cache() 2691 , this->priv_buckets_len() - (priv_get_cache() - priv_buckets())); 2692 } 2693 priv_initialize_buckets()2694 void priv_initialize_buckets() 2695 { this->priv_clear_buckets(priv_buckets(), this->priv_buckets_len()); } 2696 priv_clear_buckets(bucket_ptr buckets_ptr,size_type buckets_len)2697 void priv_clear_buckets(bucket_ptr buckets_ptr, size_type buckets_len) 2698 { 2699 for(; buckets_len--; ++buckets_ptr){ 2700 if(safemode_or_autounlink){ 2701 priv_clear_group_nodes(*buckets_ptr, optimize_multikey_t()); 2702 buckets_ptr->clear_and_dispose(detail::init_disposer<node_algorithms>()); 2703 } 2704 else{ 2705 buckets_ptr->clear(); 2706 } 2707 } 2708 priv_initialize_cache(); 2709 } 2710 2711 template<class KeyType, class KeyHasher, class KeyValueEqual> priv_find(const KeyType & key,KeyHasher hash_func,KeyValueEqual equal_func,size_type & bucket_number,std::size_t & h,siterator & previt) const2712 siterator priv_find 2713 ( const KeyType &key, KeyHasher hash_func 2714 , KeyValueEqual equal_func, size_type &bucket_number, std::size_t &h, siterator &previt) const 2715 { 2716 h = hash_func(key); 2717 return priv_find_with_hash(key, equal_func, bucket_number, h, previt); 2718 } 2719 2720 template<class KeyType, class KeyValueEqual> priv_find_with_hash(const KeyType & key,KeyValueEqual equal_func,size_type & bucket_number,const std::size_t h,siterator & previt) const2721 siterator priv_find_with_hash 2722 ( const KeyType &key, KeyValueEqual equal_func, size_type &bucket_number, const std::size_t h, siterator &previt) const 2723 { 2724 bucket_number = priv_hash_to_bucket(h); 2725 bucket_type &b = this->priv_buckets()[bucket_number]; 2726 previt = b.before_begin(); 2727 if(constant_time_size && this->empty()){ 2728 return priv_invalid_local_it(); 2729 } 2730 2731 siterator it = previt; 2732 ++it; 2733 2734 while(it != b.end()){ 2735 const value_type &v = priv_value_from_slist_node(it.pointed_node()); 2736 if(compare_hash){ 2737 std::size_t vh = this->priv_stored_or_compute_hash(v, store_hash_t()); 2738 if(h == vh && equal_func(key, v)){ 2739 return it; 2740 } 2741 } 2742 else if(equal_func(key, v)){ 2743 return it; 2744 } 2745 if(optimize_multikey){ 2746 previt = bucket_type::s_iterator_to 2747 (*group_functions_t::priv_get_last_in_group 2748 (dcast_bucket_ptr(it.pointed_node()), optimize_multikey_t())); 2749 it = previt; 2750 } 2751 else{ 2752 previt = it; 2753 } 2754 ++it; 2755 } 2756 previt = b.before_begin(); 2757 return priv_invalid_local_it(); 2758 } 2759 priv_insert_equal_with_hash(reference value,std::size_t hash_value)2760 iterator priv_insert_equal_with_hash(reference value, std::size_t hash_value) 2761 { 2762 size_type bucket_num; 2763 siterator prev; 2764 siterator it = this->priv_find_with_hash 2765 (value, this->priv_equal(), bucket_num, hash_value, prev); 2766 return priv_insert_equal_find(value, bucket_num, hash_value, it); 2767 } 2768 priv_insert_equal_find(reference value,size_type bucket_num,std::size_t hash_value,siterator it)2769 iterator priv_insert_equal_find(reference value, size_type bucket_num, std::size_t hash_value, siterator it) 2770 { 2771 bucket_type &b = this->priv_buckets()[bucket_num]; 2772 bool found_equal = it != priv_invalid_local_it(); 2773 if(!found_equal){ 2774 it = b.before_begin(); 2775 } 2776 //Now store hash if needed 2777 node_ptr n = node_ptr(&priv_value_to_node(value)); 2778 this->priv_store_hash(n, hash_value, store_hash_t()); 2779 //Checks for some modes 2780 if(safemode_or_autounlink) 2781 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n)); 2782 //Shorcut for optimize_multikey cases 2783 if(optimize_multikey){ 2784 node_ptr first_in_group = found_equal ? 2785 dcast_bucket_ptr(it.pointed_node()) : node_ptr(0); 2786 this->priv_insert_in_group(first_in_group, n, optimize_multikey_t()); 2787 } 2788 //Update cache and increment size if needed 2789 priv_insertion_update_cache(bucket_num); 2790 this->priv_size_traits().increment(); 2791 //Insert the element in the bucket after it 2792 return iterator(b.insert_after(it, *n), this); 2793 } 2794 2795 template<class KeyType, class KeyHasher, class KeyValueEqual> priv_equal_range(const KeyType & key,KeyHasher hash_func,KeyValueEqual equal_func,size_type & bucket_number_first,size_type & bucket_number_second,size_type & count) const2796 std::pair<siterator, siterator> priv_equal_range 2797 ( const KeyType &key 2798 , KeyHasher hash_func 2799 , KeyValueEqual equal_func 2800 , size_type &bucket_number_first 2801 , size_type &bucket_number_second 2802 , size_type &count) const 2803 { 2804 std::size_t h; 2805 count = 0; 2806 siterator prev; 2807 //Let's see if the element is present 2808 std::pair<siterator, siterator> to_return 2809 ( priv_find(key, hash_func, equal_func, bucket_number_first, h, prev) 2810 , priv_invalid_local_it()); 2811 if(to_return.first == to_return.second){ 2812 bucket_number_second = bucket_number_first; 2813 return to_return; 2814 } 2815 //If it's present, find the first that it's not equal in 2816 //the same bucket 2817 bucket_type &b = this->priv_buckets()[bucket_number_first]; 2818 siterator it = to_return.first; 2819 if(optimize_multikey){ 2820 to_return.second = bucket_type::s_iterator_to 2821 (*node_traits::get_next(group_functions_t::priv_get_last_in_group 2822 (dcast_bucket_ptr(it.pointed_node()), optimize_multikey_t()))); 2823 count = std::distance(it, to_return.second); 2824 if(to_return.second != b.end()){ 2825 bucket_number_second = bucket_number_first; 2826 return to_return; 2827 } 2828 } 2829 else{ 2830 ++count; 2831 ++it; 2832 while(it != b.end()){ 2833 const value_type &v = priv_value_from_slist_node(it.pointed_node()); 2834 if(compare_hash){ 2835 std::size_t hv = this->priv_stored_or_compute_hash(v, store_hash_t()); 2836 if(hv != h || !equal_func(key, v)){ 2837 to_return.second = it; 2838 bucket_number_second = bucket_number_first; 2839 return to_return; 2840 } 2841 } 2842 else if(!equal_func(key, v)){ 2843 to_return.second = it; 2844 bucket_number_second = bucket_number_first; 2845 return to_return; 2846 } 2847 ++it; 2848 ++count; 2849 } 2850 } 2851 2852 //If we reached the end, find the first, non-empty bucket 2853 for(bucket_number_second = bucket_number_first+1 2854 ; bucket_number_second != this->priv_buckets_len() 2855 ; ++bucket_number_second){ 2856 bucket_type &b = this->priv_buckets()[bucket_number_second]; 2857 if(!b.empty()){ 2858 to_return.second = b.begin(); 2859 return to_return; 2860 } 2861 } 2862 2863 //Otherwise, return the end node 2864 to_return.second = priv_invalid_local_it(); 2865 return to_return; 2866 } 2867 /// @endcond 2868 }; 2869 2870 /// @cond 2871 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2872 template < class T 2873 , bool UniqueKeys 2874 , class O1 = none, class O2 = none 2875 , class O3 = none, class O4 = none 2876 , class O5 = none, class O6 = none 2877 , class O7 = none, class O8 = none 2878 , class O9 = none, class O10= none 2879 > 2880 #else 2881 template <class T, bool UniqueKeys, class ...Options> 2882 #endif 2883 struct make_hashtable_opt 2884 { 2885 typedef typename pack_options 2886 < uset_defaults<T>, 2887 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2888 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10 2889 #else 2890 Options... 2891 #endif 2892 >::type packed_options; 2893 2894 //Real value traits must be calculated from options 2895 typedef typename detail::get_value_traits 2896 <T, typename packed_options::value_traits>::type value_traits; 2897 static const bool external_value_traits = 2898 detail::external_value_traits_is_true<value_traits>::value; 2899 typedef typename detail::eval_if_c 2900 < external_value_traits 2901 , detail::eval_value_traits<value_traits> 2902 , detail::identity<value_traits> 2903 >::type real_value_traits; 2904 typedef typename packed_options::bucket_traits specified_bucket_traits; 2905 2906 //Real bucket traits must be calculated from options and calculated value_traits 2907 typedef typename detail::get_slist_impl 2908 <typename detail::reduced_slist_node_traits 2909 <typename real_value_traits::node_traits>::type 2910 >::type slist_impl; 2911 2912 typedef typename 2913 detail::if_c< detail::is_same 2914 < specified_bucket_traits 2915 , default_bucket_traits 2916 >::value 2917 , detail::bucket_traits_impl<slist_impl> 2918 , specified_bucket_traits 2919 >::type real_bucket_traits; 2920 2921 typedef detail::usetopt 2922 < value_traits 2923 , typename packed_options::hash 2924 , typename packed_options::equal 2925 , typename packed_options::size_type 2926 , real_bucket_traits 2927 , (std::size_t(UniqueKeys)*detail::hash_bool_flags::unique_keys_pos) 2928 | (std::size_t(packed_options::constant_time_size)*detail::hash_bool_flags::constant_time_size_pos) 2929 | (std::size_t(packed_options::power_2_buckets)*detail::hash_bool_flags::power_2_buckets_pos) 2930 | (std::size_t(packed_options::cache_begin)*detail::hash_bool_flags::cache_begin_pos) 2931 | (std::size_t(packed_options::compare_hash)*detail::hash_bool_flags::compare_hash_pos) 2932 | (std::size_t(packed_options::incremental)*detail::hash_bool_flags::incremental_pos) 2933 > type; 2934 }; 2935 /// @endcond 2936 2937 //! Helper metafunction to define a \c hashtable that yields to the same type when the 2938 //! same options (either explicitly or implicitly) are used. 2939 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2940 template<class T, class ...Options> 2941 #else 2942 template<class T, class O1 = none, class O2 = none 2943 , class O3 = none, class O4 = none 2944 , class O5 = none, class O6 = none 2945 , class O7 = none, class O8 = none 2946 , class O9 = none, class O10= none 2947 > 2948 #endif 2949 struct make_hashtable 2950 { 2951 /// @cond 2952 typedef hashtable_impl 2953 < typename make_hashtable_opt 2954 <T, false, 2955 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2956 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10 2957 #else 2958 Options... 2959 #endif 2960 >::type 2961 > implementation_defined; 2962 2963 /// @endcond 2964 typedef implementation_defined type; 2965 }; 2966 2967 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 2968 2969 #if defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2970 template<class T, class ...Options> 2971 #else 2972 template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10> 2973 #endif 2974 class hashtable 2975 : public make_hashtable<T, 2976 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2977 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10 2978 #else 2979 Options... 2980 #endif 2981 >::type 2982 { 2983 typedef typename make_hashtable<T, 2984 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2985 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10 2986 #else 2987 Options... 2988 #endif 2989 >::type Base; 2990 2991 public: 2992 typedef typename Base::value_traits value_traits; 2993 typedef typename Base::real_value_traits real_value_traits; 2994 typedef typename Base::iterator iterator; 2995 typedef typename Base::const_iterator const_iterator; 2996 typedef typename Base::bucket_ptr bucket_ptr; 2997 typedef typename Base::size_type size_type; 2998 typedef typename Base::hasher hasher; 2999 typedef typename Base::bucket_traits bucket_traits; 3000 typedef typename Base::key_equal key_equal; 3001 3002 //Assert if passed value traits are compatible with the type 3003 BOOST_STATIC_ASSERT((detail::is_same<typename real_value_traits::value_type, T>::value)); 3004 hashtable(const bucket_traits & b_traits,const hasher & hash_func=hasher (),const key_equal & equal_func=key_equal (),const value_traits & v_traits=value_traits ())3005 hashtable ( const bucket_traits &b_traits 3006 , const hasher & hash_func = hasher() 3007 , const key_equal &equal_func = key_equal() 3008 , const value_traits &v_traits = value_traits()) 3009 : Base(b_traits, hash_func, equal_func, v_traits) 3010 {} 3011 }; 3012 3013 #endif 3014 3015 } //namespace intrusive 3016 } //namespace boost 3017 3018 #include <boost/intrusive/detail/config_end.hpp> 3019 3020 #endif //BOOST_INTRUSIVE_HASHTABLE_HPP 3021