1 2 // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. 3 // Copyright (C) 2005-2011 Daniel James 4 // Distributed under the Boost Software License, Version 1.0. (See accompanying 5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 7 #ifndef BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED 8 #define BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED 9 10 #include <boost/config.hpp> 11 #if defined(BOOST_HAS_PRAGMA_ONCE) 12 #pragma once 13 #endif 14 15 #include <boost/unordered/detail/extract_key.hpp> 16 #include <boost/throw_exception.hpp> 17 #include <stdexcept> 18 19 namespace boost { namespace unordered { namespace detail { 20 21 template <typename A, typename T> struct unique_node; 22 template <typename T> struct ptr_node; 23 template <typename Types> struct table_impl; 24 25 template <typename A, typename T> 26 struct unique_node : 27 boost::unordered::detail::value_base<T> 28 { 29 typedef typename ::boost::unordered::detail::rebind_wrap< 30 A, unique_node<A, T> >::type allocator; 31 typedef typename ::boost::unordered::detail:: 32 allocator_traits<allocator>::pointer node_pointer; 33 typedef node_pointer link_pointer; 34 35 link_pointer next_; 36 std::size_t hash_; 37 unique_nodeboost::unordered::detail::unique_node38 unique_node() : 39 next_(), 40 hash_(0) 41 {} 42 initboost::unordered::detail::unique_node43 void init(node_pointer) 44 { 45 } 46 47 private: 48 unique_node& operator=(unique_node const&); 49 }; 50 51 template <typename T> 52 struct ptr_node : 53 boost::unordered::detail::ptr_bucket 54 { 55 typedef T value_type; 56 typedef boost::unordered::detail::ptr_bucket bucket_base; 57 typedef ptr_node<T>* node_pointer; 58 typedef ptr_bucket* link_pointer; 59 60 std::size_t hash_; 61 boost::unordered::detail::value_base<T> value_base_; 62 ptr_nodeboost::unordered::detail::ptr_node63 ptr_node() : 64 bucket_base(), 65 hash_(0) 66 {} 67 initboost::unordered::detail::ptr_node68 void init(node_pointer) 69 { 70 } 71 addressboost::unordered::detail::ptr_node72 void* address() { return value_base_.address(); } valueboost::unordered::detail::ptr_node73 value_type& value() { return value_base_.value(); } value_ptrboost::unordered::detail::ptr_node74 value_type* value_ptr() { return value_base_.value_ptr(); } 75 76 private: 77 ptr_node& operator=(ptr_node const&); 78 }; 79 80 // If the allocator uses raw pointers use ptr_node 81 // Otherwise use node. 82 83 template <typename A, typename T, typename NodePtr, typename BucketPtr> 84 struct pick_node2 85 { 86 typedef boost::unordered::detail::unique_node<A, T> node; 87 88 typedef typename boost::unordered::detail::allocator_traits< 89 typename boost::unordered::detail::rebind_wrap<A, node>::type 90 >::pointer node_pointer; 91 92 typedef boost::unordered::detail::bucket<node_pointer> bucket; 93 typedef node_pointer link_pointer; 94 }; 95 96 template <typename A, typename T> 97 struct pick_node2<A, T, 98 boost::unordered::detail::ptr_node<T>*, 99 boost::unordered::detail::ptr_bucket*> 100 { 101 typedef boost::unordered::detail::ptr_node<T> node; 102 typedef boost::unordered::detail::ptr_bucket bucket; 103 typedef bucket* link_pointer; 104 }; 105 106 template <typename A, typename T> 107 struct pick_node 108 { 109 typedef boost::unordered::detail::allocator_traits< 110 typename boost::unordered::detail::rebind_wrap<A, 111 boost::unordered::detail::ptr_node<T> >::type 112 > tentative_node_traits; 113 114 typedef boost::unordered::detail::allocator_traits< 115 typename boost::unordered::detail::rebind_wrap<A, 116 boost::unordered::detail::ptr_bucket >::type 117 > tentative_bucket_traits; 118 119 typedef pick_node2<A, T, 120 typename tentative_node_traits::pointer, 121 typename tentative_bucket_traits::pointer> pick; 122 123 typedef typename pick::node node; 124 typedef typename pick::bucket bucket; 125 typedef typename pick::link_pointer link_pointer; 126 }; 127 128 template <typename Types> 129 struct table_impl : boost::unordered::detail::table<Types> 130 { 131 typedef boost::unordered::detail::table<Types> table; 132 typedef typename table::value_type value_type; 133 typedef typename table::bucket bucket; 134 typedef typename table::policy policy; 135 typedef typename table::node_pointer node_pointer; 136 typedef typename table::node_allocator node_allocator; 137 typedef typename table::node_allocator_traits node_allocator_traits; 138 typedef typename table::bucket_pointer bucket_pointer; 139 typedef typename table::link_pointer link_pointer; 140 typedef typename table::hasher hasher; 141 typedef typename table::key_equal key_equal; 142 typedef typename table::key_type key_type; 143 typedef typename table::node_constructor node_constructor; 144 typedef typename table::node_tmp node_tmp; 145 typedef typename table::extractor extractor; 146 typedef typename table::iterator iterator; 147 typedef typename table::c_iterator c_iterator; 148 149 typedef std::pair<iterator, bool> emplace_return; 150 151 // Constructors 152 table_implboost::unordered::detail::table_impl153 table_impl(std::size_t n, 154 hasher const& hf, 155 key_equal const& eq, 156 node_allocator const& a) 157 : table(n, hf, eq, a) 158 {} 159 table_implboost::unordered::detail::table_impl160 table_impl(table_impl const& x) 161 : table(x, node_allocator_traits:: 162 select_on_container_copy_construction(x.node_alloc())) 163 { 164 this->init(x); 165 } 166 table_implboost::unordered::detail::table_impl167 table_impl(table_impl const& x, 168 node_allocator const& a) 169 : table(x, a) 170 { 171 this->init(x); 172 } 173 table_implboost::unordered::detail::table_impl174 table_impl(table_impl& x, 175 boost::unordered::detail::move_tag m) 176 : table(x, m) 177 {} 178 table_implboost::unordered::detail::table_impl179 table_impl(table_impl& x, 180 node_allocator const& a, 181 boost::unordered::detail::move_tag m) 182 : table(x, a, m) 183 { 184 this->move_init(x); 185 } 186 187 // Accessors 188 189 template <class Key, class Pred> find_node_implboost::unordered::detail::table_impl190 iterator find_node_impl( 191 std::size_t key_hash, 192 Key const& k, 193 Pred const& eq) const 194 { 195 std::size_t bucket_index = this->hash_to_bucket(key_hash); 196 iterator n = this->begin(bucket_index); 197 198 for (;;) 199 { 200 if (!n.node_) return n; 201 202 std::size_t node_hash = n.node_->hash_; 203 if (key_hash == node_hash) 204 { 205 if (eq(k, this->get_key(*n))) 206 return n; 207 } 208 else 209 { 210 if (this->hash_to_bucket(node_hash) != bucket_index) 211 return iterator(); 212 } 213 214 ++n; 215 } 216 } 217 countboost::unordered::detail::table_impl218 std::size_t count(key_type const& k) const 219 { 220 return this->find_node(k).node_ ? 1 : 0; 221 } 222 atboost::unordered::detail::table_impl223 value_type& at(key_type const& k) const 224 { 225 if (this->size_) { 226 iterator it = this->find_node(k); 227 if (it.node_) return *it; 228 } 229 230 boost::throw_exception( 231 std::out_of_range("Unable to find key in unordered_map.")); 232 } 233 234 std::pair<iterator, iterator> equal_rangeboost::unordered::detail::table_impl235 equal_range(key_type const& k) const 236 { 237 iterator n = this->find_node(k); 238 iterator n2 = n; 239 if (n2.node_) ++n2; 240 return std::make_pair(n, n2); 241 } 242 243 // equals 244 equalsboost::unordered::detail::table_impl245 bool equals(table_impl const& other) const 246 { 247 if(this->size_ != other.size_) return false; 248 249 for(iterator n1 = this->begin(); n1.node_; ++n1) 250 { 251 iterator n2 = other.find_matching_node(n1); 252 253 if (!n2.node_ || *n1 != *n2) 254 return false; 255 } 256 257 return true; 258 } 259 260 // Emplace/Insert 261 add_nodeboost::unordered::detail::table_impl262 inline iterator add_node( 263 node_pointer n, 264 std::size_t key_hash) 265 { 266 n->hash_ = key_hash; 267 268 bucket_pointer b = this->get_bucket(this->hash_to_bucket(key_hash)); 269 270 if (!b->next_) 271 { 272 link_pointer start_node = this->get_previous_start(); 273 274 if (start_node->next_) { 275 this->get_bucket(this->hash_to_bucket( 276 static_cast<node_pointer>(start_node->next_)->hash_) 277 )->next_ = n; 278 } 279 280 b->next_ = start_node; 281 n->next_ = start_node->next_; 282 start_node->next_ = n; 283 } 284 else 285 { 286 n->next_ = b->next_->next_; 287 b->next_->next_ = n; 288 } 289 290 ++this->size_; 291 return iterator(n); 292 } 293 resize_and_add_nodeboost::unordered::detail::table_impl294 inline iterator resize_and_add_node(node_pointer n, std::size_t key_hash) 295 { 296 node_tmp b(n, this->node_alloc()); 297 this->reserve_for_insert(this->size_ + 1); 298 return this->add_node(b.release(), key_hash); 299 } 300 operator []boost::unordered::detail::table_impl301 value_type& operator[](key_type const& k) 302 { 303 std::size_t key_hash = this->hash(k); 304 iterator pos = this->find_node(key_hash, k); 305 if (pos.node_) return *pos; 306 return *this->resize_and_add_node( 307 boost::unordered::detail::func::construct_pair(this->node_alloc(), k), 308 key_hash); 309 } 310 311 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 312 # if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) emplaceboost::unordered::detail::table_impl313 emplace_return emplace(boost::unordered::detail::emplace_args1< 314 boost::unordered::detail::please_ignore_this_overload> const&) 315 { 316 BOOST_ASSERT(false); 317 return emplace_return(this->begin(), false); 318 } 319 # else emplaceboost::unordered::detail::table_impl320 emplace_return emplace( 321 boost::unordered::detail::please_ignore_this_overload const&) 322 { 323 BOOST_ASSERT(false); 324 return emplace_return(this->begin(), false); 325 } 326 # endif 327 #endif 328 329 template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplaceboost::unordered::detail::table_impl330 emplace_return emplace(BOOST_UNORDERED_EMPLACE_ARGS) 331 { 332 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 333 return emplace_impl( 334 extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD), 335 BOOST_UNORDERED_EMPLACE_FORWARD); 336 #else 337 return emplace_impl( 338 extractor::extract(args.a0, args.a1), 339 BOOST_UNORDERED_EMPLACE_FORWARD); 340 #endif 341 } 342 343 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 344 template <typename A0> emplaceboost::unordered::detail::table_impl345 emplace_return emplace( 346 boost::unordered::detail::emplace_args1<A0> const& args) 347 { 348 return emplace_impl(extractor::extract(args.a0), args); 349 } 350 #endif 351 352 template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_implboost::unordered::detail::table_impl353 emplace_return emplace_impl(key_type const& k, 354 BOOST_UNORDERED_EMPLACE_ARGS) 355 { 356 std::size_t key_hash = this->hash(k); 357 iterator pos = this->find_node(key_hash, k); 358 if (pos.node_) { 359 return emplace_return(pos, false); 360 } 361 else { 362 return emplace_return( 363 this->resize_and_add_node( 364 boost::unordered::detail::func::construct_value_generic( 365 this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), 366 key_hash), 367 true); 368 } 369 } 370 371 template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_implboost::unordered::detail::table_impl372 emplace_return emplace_impl(no_key, BOOST_UNORDERED_EMPLACE_ARGS) 373 { 374 // Don't have a key, so construct the node first in order 375 // to be able to lookup the position. 376 node_tmp b( 377 boost::unordered::detail::func::construct_value_generic( 378 this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), 379 this->node_alloc()); 380 key_type const& k = this->get_key(b.node_->value()); 381 std::size_t key_hash = this->hash(k); 382 iterator pos = this->find_node(key_hash, k); 383 if (pos.node_) { 384 return emplace_return(pos, false); 385 } 386 else { 387 return emplace_return( 388 this->resize_and_add_node(b.release(), key_hash), 389 true); 390 } 391 } 392 393 //////////////////////////////////////////////////////////////////////// 394 // Insert range methods 395 // 396 // if hash function throws, or inserting > 1 element, basic exception 397 // safety strong otherwise 398 399 template <class InputIt> insert_rangeboost::unordered::detail::table_impl400 void insert_range(InputIt i, InputIt j) 401 { 402 if(i != j) 403 return insert_range_impl(extractor::extract(*i), i, j); 404 } 405 406 template <class InputIt> insert_range_implboost::unordered::detail::table_impl407 void insert_range_impl(key_type const& k, InputIt i, InputIt j) 408 { 409 insert_range_impl2(k, i, j); 410 411 while(++i != j) { 412 // Note: can't use get_key as '*i' might not be value_type - it 413 // could be a pair with first_types as key_type without const or 414 // a different second_type. 415 // 416 // TODO: Might be worth storing the value_type instead of the 417 // key here. Could be more efficient if '*i' is expensive. Could 418 // be less efficient if copying the full value_type is 419 // expensive. 420 insert_range_impl2(extractor::extract(*i), i, j); 421 } 422 } 423 424 template <class InputIt> insert_range_impl2boost::unordered::detail::table_impl425 void insert_range_impl2(key_type const& k, InputIt i, InputIt j) 426 { 427 // No side effects in this initial code 428 std::size_t key_hash = this->hash(k); 429 iterator pos = this->find_node(key_hash, k); 430 431 if (!pos.node_) { 432 node_tmp b( 433 boost::unordered::detail::func::construct_value(this->node_alloc(), *i), 434 this->node_alloc()); 435 if(this->size_ + 1 > this->max_load_) 436 this->reserve_for_insert(this->size_ + 437 boost::unordered::detail::insert_size(i, j)); 438 this->add_node(b.release(), key_hash); 439 } 440 } 441 442 template <class InputIt> insert_range_implboost::unordered::detail::table_impl443 void insert_range_impl(no_key, InputIt i, InputIt j) 444 { 445 node_constructor a(this->node_alloc()); 446 447 do { 448 if (!a.node_) { a.create_node(); } 449 boost::unordered::detail::func::call_construct( 450 a.alloc_, a.node_->value_ptr(), *i); 451 node_tmp b(a.release(), a.alloc_); 452 453 key_type const& k = this->get_key(b.node_->value()); 454 std::size_t key_hash = this->hash(k); 455 iterator pos = this->find_node(key_hash, k); 456 457 if (pos.node_) { 458 a.reclaim(b.release()); 459 } 460 else { 461 // reserve has basic exception safety if the hash function 462 // throws, strong otherwise. 463 this->reserve_for_insert(this->size_ + 1); 464 this->add_node(b.release(), key_hash); 465 } 466 } while(++i != j); 467 } 468 469 //////////////////////////////////////////////////////////////////////// 470 // Erase 471 // 472 // no throw 473 erase_keyboost::unordered::detail::table_impl474 std::size_t erase_key(key_type const& k) 475 { 476 if(!this->size_) return 0; 477 478 std::size_t key_hash = this->hash(k); 479 std::size_t bucket_index = this->hash_to_bucket(key_hash); 480 link_pointer prev = this->get_previous_start(bucket_index); 481 if (!prev) return 0; 482 483 for (;;) 484 { 485 if (!prev->next_) return 0; 486 std::size_t node_hash = 487 static_cast<node_pointer>(prev->next_)->hash_; 488 if (this->hash_to_bucket(node_hash) != bucket_index) 489 return 0; 490 if (node_hash == key_hash && 491 this->key_eq()(k, this->get_key( 492 static_cast<node_pointer>(prev->next_)->value()))) 493 break; 494 prev = prev->next_; 495 } 496 497 link_pointer end = static_cast<node_pointer>(prev->next_)->next_; 498 499 std::size_t deleted_count = this->delete_nodes(prev, end); 500 this->fix_bucket(bucket_index, prev); 501 return deleted_count; 502 } 503 eraseboost::unordered::detail::table_impl504 iterator erase(c_iterator r) 505 { 506 BOOST_ASSERT(r.node_); 507 iterator next(r.node_); 508 ++next; 509 erase_nodes(r.node_, next.node_); 510 return next; 511 } 512 erase_rangeboost::unordered::detail::table_impl513 iterator erase_range(c_iterator r1, c_iterator r2) 514 { 515 if (r1 == r2) return iterator(r2.node_); 516 erase_nodes(r1.node_, r2.node_); 517 return iterator(r2.node_); 518 } 519 erase_nodesboost::unordered::detail::table_impl520 void erase_nodes(node_pointer i, node_pointer j) 521 { 522 std::size_t bucket_index = this->hash_to_bucket(i->hash_); 523 524 // Find the node before i. 525 link_pointer prev = this->get_previous_start(bucket_index); 526 while(prev->next_ != i) prev = prev->next_; 527 528 // Delete the nodes. 529 do { 530 this->delete_node(prev); 531 bucket_index = this->fix_bucket(bucket_index, prev); 532 } while (prev->next_ != j); 533 } 534 535 //////////////////////////////////////////////////////////////////////// 536 // fill_buckets 537 copy_bucketsboost::unordered::detail::table_impl538 void copy_buckets(table const& src) { 539 this->create_buckets(this->bucket_count_); 540 541 for(iterator n = src.begin(); n.node_; ++n) { 542 this->add_node( 543 boost::unordered::detail::func::construct_value( 544 this->node_alloc(), *n), n.node_->hash_); 545 } 546 } 547 move_bucketsboost::unordered::detail::table_impl548 void move_buckets(table const& src) { 549 this->create_buckets(this->bucket_count_); 550 551 for(iterator n = src.begin(); n.node_; ++n) { 552 this->add_node( 553 boost::unordered::detail::func::construct_value( 554 this->node_alloc(), boost::move(*n)), n.node_->hash_); 555 } 556 } 557 assign_bucketsboost::unordered::detail::table_impl558 void assign_buckets(table const& src) 559 { 560 node_holder<node_allocator> holder(*this); 561 for(iterator n = src.begin(); n.node_; ++n) { 562 this->add_node(holder.copy_of(*n), n.node_->hash_); 563 } 564 } 565 move_assign_bucketsboost::unordered::detail::table_impl566 void move_assign_buckets(table& src) 567 { 568 node_holder<node_allocator> holder(*this); 569 for(iterator n = src.begin(); n.node_; ++n) { 570 this->add_node(holder.move_copy_of(*n), n.node_->hash_); 571 } 572 } 573 574 // strong otherwise exception safety rehash_implboost::unordered::detail::table_impl575 void rehash_impl(std::size_t num_buckets) 576 { 577 BOOST_ASSERT(this->buckets_); 578 579 this->create_buckets(num_buckets); 580 link_pointer prev = this->get_previous_start(); 581 while (prev->next_) 582 prev = place_in_bucket(*this, prev); 583 } 584 585 // Iterate through the nodes placing them in the correct buckets. 586 // pre: prev->next_ is not null. place_in_bucketboost::unordered::detail::table_impl587 static link_pointer place_in_bucket(table& dst, link_pointer prev) 588 { 589 node_pointer n = static_cast<node_pointer>(prev->next_); 590 bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(n->hash_)); 591 592 if (!b->next_) { 593 b->next_ = prev; 594 return n; 595 } 596 else { 597 prev->next_ = n->next_; 598 n->next_ = b->next_->next_; 599 b->next_->next_ = n; 600 return prev; 601 } 602 } 603 }; 604 }}} 605 606 #endif 607