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_EQUIVALENT_HPP_INCLUDED 8 #define BOOST_UNORDERED_DETAIL_EQUIVALENT_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/table.hpp> 16 #include <boost/unordered/detail/extract_key.hpp> 17 18 namespace boost { namespace unordered { namespace detail { 19 20 template <typename A, typename T> struct grouped_node; 21 template <typename T> struct grouped_ptr_node; 22 template <typename Types> struct grouped_table_impl; 23 24 template <typename A, typename T> 25 struct grouped_node : 26 boost::unordered::detail::value_base<T> 27 { 28 typedef typename ::boost::unordered::detail::rebind_wrap< 29 A, grouped_node<A, T> >::type allocator; 30 typedef typename ::boost::unordered::detail:: 31 allocator_traits<allocator>::pointer node_pointer; 32 typedef node_pointer link_pointer; 33 34 link_pointer next_; 35 node_pointer group_prev_; 36 std::size_t hash_; 37 grouped_nodeboost::unordered::detail::grouped_node38 grouped_node() : 39 next_(), 40 group_prev_(), 41 hash_(0) 42 {} 43 initboost::unordered::detail::grouped_node44 void init(node_pointer self) 45 { 46 group_prev_ = self; 47 } 48 49 private: 50 grouped_node& operator=(grouped_node const&); 51 }; 52 53 template <typename T> 54 struct grouped_ptr_node : 55 boost::unordered::detail::ptr_bucket 56 { 57 typedef T value_type; 58 typedef boost::unordered::detail::ptr_bucket bucket_base; 59 typedef grouped_ptr_node<T>* node_pointer; 60 typedef ptr_bucket* link_pointer; 61 62 node_pointer group_prev_; 63 std::size_t hash_; 64 boost::unordered::detail::value_base<T> value_base_; 65 grouped_ptr_nodeboost::unordered::detail::grouped_ptr_node66 grouped_ptr_node() : 67 bucket_base(), 68 group_prev_(0), 69 hash_(0) 70 {} 71 initboost::unordered::detail::grouped_ptr_node72 void init(node_pointer self) 73 { 74 group_prev_ = self; 75 } 76 addressboost::unordered::detail::grouped_ptr_node77 void* address() { return value_base_.address(); } valueboost::unordered::detail::grouped_ptr_node78 value_type& value() { return value_base_.value(); } value_ptrboost::unordered::detail::grouped_ptr_node79 value_type* value_ptr() { return value_base_.value_ptr(); } 80 81 private: 82 grouped_ptr_node& operator=(grouped_ptr_node const&); 83 }; 84 85 // If the allocator uses raw pointers use grouped_ptr_node 86 // Otherwise use grouped_node. 87 88 template <typename A, typename T, typename NodePtr, typename BucketPtr> 89 struct pick_grouped_node2 90 { 91 typedef boost::unordered::detail::grouped_node<A, T> node; 92 93 typedef typename boost::unordered::detail::allocator_traits< 94 typename boost::unordered::detail::rebind_wrap<A, node>::type 95 >::pointer node_pointer; 96 97 typedef boost::unordered::detail::bucket<node_pointer> bucket; 98 typedef node_pointer link_pointer; 99 }; 100 101 template <typename A, typename T> 102 struct pick_grouped_node2<A, T, 103 boost::unordered::detail::grouped_ptr_node<T>*, 104 boost::unordered::detail::ptr_bucket*> 105 { 106 typedef boost::unordered::detail::grouped_ptr_node<T> node; 107 typedef boost::unordered::detail::ptr_bucket bucket; 108 typedef bucket* link_pointer; 109 }; 110 111 template <typename A, typename T> 112 struct pick_grouped_node 113 { 114 typedef boost::unordered::detail::allocator_traits< 115 typename boost::unordered::detail::rebind_wrap<A, 116 boost::unordered::detail::grouped_ptr_node<T> >::type 117 > tentative_node_traits; 118 119 typedef boost::unordered::detail::allocator_traits< 120 typename boost::unordered::detail::rebind_wrap<A, 121 boost::unordered::detail::ptr_bucket >::type 122 > tentative_bucket_traits; 123 124 typedef pick_grouped_node2<A, T, 125 typename tentative_node_traits::pointer, 126 typename tentative_bucket_traits::pointer> pick; 127 128 typedef typename pick::node node; 129 typedef typename pick::bucket bucket; 130 typedef typename pick::link_pointer link_pointer; 131 }; 132 133 template <typename A, typename T, typename H, typename P> 134 struct multiset 135 { 136 typedef boost::unordered::detail::multiset<A, T, H, P> types; 137 138 typedef A allocator; 139 typedef T value_type; 140 typedef H hasher; 141 typedef P key_equal; 142 typedef T key_type; 143 144 typedef boost::unordered::detail::allocator_traits<allocator> traits; 145 typedef boost::unordered::detail::pick_grouped_node<allocator, 146 value_type> pick; 147 typedef typename pick::node node; 148 typedef typename pick::bucket bucket; 149 typedef typename pick::link_pointer link_pointer; 150 151 typedef boost::unordered::detail::grouped_table_impl<types> table; 152 typedef boost::unordered::detail::set_extractor<value_type> extractor; 153 154 typedef typename boost::unordered::detail::pick_policy<T>::type policy; 155 }; 156 157 template <typename A, typename K, typename M, typename H, typename P> 158 struct multimap 159 { 160 typedef boost::unordered::detail::multimap<A, K, M, H, P> types; 161 162 typedef A allocator; 163 typedef std::pair<K const, M> value_type; 164 typedef H hasher; 165 typedef P key_equal; 166 typedef K key_type; 167 168 typedef boost::unordered::detail::allocator_traits<allocator> traits; 169 typedef boost::unordered::detail::pick_grouped_node<allocator, 170 value_type> pick; 171 typedef typename pick::node node; 172 typedef typename pick::bucket bucket; 173 typedef typename pick::link_pointer link_pointer; 174 175 typedef boost::unordered::detail::grouped_table_impl<types> table; 176 typedef boost::unordered::detail::map_extractor<key_type, value_type> 177 extractor; 178 179 typedef typename boost::unordered::detail::pick_policy<K>::type policy; 180 }; 181 182 template <typename Types> 183 struct grouped_table_impl : boost::unordered::detail::table<Types> 184 { 185 typedef boost::unordered::detail::table<Types> table; 186 typedef typename table::value_type value_type; 187 typedef typename table::bucket bucket; 188 typedef typename table::policy policy; 189 typedef typename table::node_pointer node_pointer; 190 typedef typename table::node_allocator node_allocator; 191 typedef typename table::node_allocator_traits node_allocator_traits; 192 typedef typename table::bucket_pointer bucket_pointer; 193 typedef typename table::link_pointer link_pointer; 194 typedef typename table::hasher hasher; 195 typedef typename table::key_equal key_equal; 196 typedef typename table::key_type key_type; 197 typedef typename table::node_constructor node_constructor; 198 typedef typename table::extractor extractor; 199 typedef typename table::iterator iterator; 200 typedef typename table::c_iterator c_iterator; 201 202 // Constructors 203 grouped_table_implboost::unordered::detail::grouped_table_impl204 grouped_table_impl(std::size_t n, 205 hasher const& hf, 206 key_equal const& eq, 207 node_allocator const& a) 208 : table(n, hf, eq, a) 209 {} 210 grouped_table_implboost::unordered::detail::grouped_table_impl211 grouped_table_impl(grouped_table_impl const& x) 212 : table(x, node_allocator_traits:: 213 select_on_container_copy_construction(x.node_alloc())) 214 { 215 this->init(x); 216 } 217 grouped_table_implboost::unordered::detail::grouped_table_impl218 grouped_table_impl(grouped_table_impl const& x, 219 node_allocator const& a) 220 : table(x, a) 221 { 222 this->init(x); 223 } 224 grouped_table_implboost::unordered::detail::grouped_table_impl225 grouped_table_impl(grouped_table_impl& x, 226 boost::unordered::detail::move_tag m) 227 : table(x, m) 228 {} 229 grouped_table_implboost::unordered::detail::grouped_table_impl230 grouped_table_impl(grouped_table_impl& x, 231 node_allocator const& a, 232 boost::unordered::detail::move_tag m) 233 : table(x, a, m) 234 { 235 this->move_init(x); 236 } 237 238 // Accessors 239 240 template <class Key, class Pred> find_node_implboost::unordered::detail::grouped_table_impl241 iterator find_node_impl( 242 std::size_t key_hash, 243 Key const& k, 244 Pred const& eq) const 245 { 246 std::size_t bucket_index = this->hash_to_bucket(key_hash); 247 iterator n = this->begin(bucket_index); 248 249 for (;;) 250 { 251 if (!n.node_) return n; 252 253 std::size_t node_hash = n.node_->hash_; 254 if (key_hash == node_hash) 255 { 256 if (eq(k, this->get_key(*n))) 257 return n; 258 } 259 else 260 { 261 if (this->hash_to_bucket(node_hash) != bucket_index) 262 return iterator(); 263 } 264 265 n = iterator(n.node_->group_prev_->next_); 266 } 267 } 268 countboost::unordered::detail::grouped_table_impl269 std::size_t count(key_type const& k) const 270 { 271 iterator n = this->find_node(k); 272 if (!n.node_) return 0; 273 274 std::size_t x = 0; 275 node_pointer it = n.node_; 276 do { 277 it = it->group_prev_; 278 ++x; 279 } while(it != n.node_); 280 281 return x; 282 } 283 284 std::pair<iterator, iterator> equal_rangeboost::unordered::detail::grouped_table_impl285 equal_range(key_type const& k) const 286 { 287 iterator n = this->find_node(k); 288 return std::make_pair( 289 n, n.node_ ? iterator(n.node_->group_prev_->next_) : n); 290 } 291 292 // Equality 293 equalsboost::unordered::detail::grouped_table_impl294 bool equals(grouped_table_impl const& other) const 295 { 296 if(this->size_ != other.size_) return false; 297 298 for(iterator n1 = this->begin(); n1.node_;) 299 { 300 iterator n2 = other.find_matching_node(n1); 301 if (!n2.node_) return false; 302 iterator end1(n1.node_->group_prev_->next_); 303 iterator end2(n2.node_->group_prev_->next_); 304 if (!group_equals(n1, end1, n2, end2)) return false; 305 n1 = end1; 306 } 307 308 return true; 309 } 310 group_equalsboost::unordered::detail::grouped_table_impl311 static bool group_equals(iterator n1, iterator end1, 312 iterator n2, iterator end2) 313 { 314 for(;;) 315 { 316 if (*n1 != *n2) break; 317 318 ++n1; 319 ++n2; 320 321 if (n1 == end1) return n2 == end2; 322 if (n2 == end2) return false; 323 } 324 325 for(iterator n1a = n1, n2a = n2;;) 326 { 327 ++n1a; 328 ++n2a; 329 330 if (n1a == end1) 331 { 332 if (n2a == end2) break; 333 else return false; 334 } 335 336 if (n2a == end2) return false; 337 } 338 339 iterator start = n1; 340 for(;n1 != end1; ++n1) 341 { 342 value_type const& v = *n1; 343 if (find(start, n1, v)) continue; 344 std::size_t matches = count_equal(n2, end2, v); 345 if (!matches) return false; 346 iterator next = n1; 347 ++next; 348 if (matches != 1 + count_equal(next, end1, v)) return false; 349 } 350 351 return true; 352 } 353 findboost::unordered::detail::grouped_table_impl354 static bool find(iterator n, iterator end, value_type const& v) 355 { 356 for(;n != end; ++n) 357 if (*n == v) 358 return true; 359 return false; 360 } 361 count_equalboost::unordered::detail::grouped_table_impl362 static std::size_t count_equal(iterator n, iterator end, 363 value_type const& v) 364 { 365 std::size_t count = 0; 366 for(;n != end; ++n) 367 if (*n == v) ++count; 368 return count; 369 } 370 371 // Emplace/Insert 372 add_after_nodeboost::unordered::detail::grouped_table_impl373 static inline void add_after_node( 374 node_pointer n, 375 node_pointer pos) 376 { 377 n->next_ = pos->group_prev_->next_; 378 n->group_prev_ = pos->group_prev_; 379 pos->group_prev_->next_ = n; 380 pos->group_prev_ = n; 381 } 382 add_nodeboost::unordered::detail::grouped_table_impl383 inline iterator add_node( 384 node_constructor& a, 385 std::size_t key_hash, 386 iterator pos) 387 { 388 node_pointer n = a.release(); 389 n->hash_ = key_hash; 390 if (pos.node_) { 391 this->add_after_node(n, pos.node_); 392 if (n->next_) { 393 std::size_t next_bucket = this->hash_to_bucket( 394 static_cast<node_pointer>(n->next_)->hash_); 395 if (next_bucket != this->hash_to_bucket(key_hash)) { 396 this->get_bucket(next_bucket)->next_ = n; 397 } 398 } 399 } 400 else { 401 bucket_pointer b = this->get_bucket( 402 this->hash_to_bucket(key_hash)); 403 404 if (!b->next_) 405 { 406 link_pointer start_node = this->get_previous_start(); 407 408 if (start_node->next_) { 409 this->get_bucket(this->hash_to_bucket( 410 static_cast<node_pointer>(start_node->next_)->hash_ 411 ))->next_ = n; 412 } 413 414 b->next_ = start_node; 415 n->next_ = start_node->next_; 416 start_node->next_ = n; 417 } 418 else 419 { 420 n->next_ = b->next_->next_; 421 b->next_->next_ = n; 422 } 423 } 424 ++this->size_; 425 return iterator(n); 426 } 427 emplace_implboost::unordered::detail::grouped_table_impl428 iterator emplace_impl(node_constructor& a) 429 { 430 key_type const& k = this->get_key(a.value()); 431 std::size_t key_hash = this->hash(k); 432 iterator position = this->find_node(key_hash, k); 433 434 // reserve has basic exception safety if the hash function 435 // throws, strong otherwise. 436 this->reserve_for_insert(this->size_ + 1); 437 return this->add_node(a, key_hash, position); 438 } 439 emplace_impl_no_rehashboost::unordered::detail::grouped_table_impl440 void emplace_impl_no_rehash(node_constructor& a) 441 { 442 key_type const& k = this->get_key(a.value()); 443 std::size_t key_hash = this->hash(k); 444 this->add_node(a, key_hash, this->find_node(key_hash, k)); 445 } 446 447 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 448 # if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) emplaceboost::unordered::detail::grouped_table_impl449 iterator emplace(boost::unordered::detail::emplace_args1< 450 boost::unordered::detail::please_ignore_this_overload> const&) 451 { 452 BOOST_ASSERT(false); 453 return iterator(); 454 } 455 # else emplaceboost::unordered::detail::grouped_table_impl456 iterator emplace( 457 boost::unordered::detail::please_ignore_this_overload const&) 458 { 459 BOOST_ASSERT(false); 460 return iterator(); 461 } 462 # endif 463 #endif 464 465 template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplaceboost::unordered::detail::grouped_table_impl466 iterator emplace(BOOST_UNORDERED_EMPLACE_ARGS) 467 { 468 node_constructor a(this->node_alloc()); 469 a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD); 470 471 return iterator(emplace_impl(a)); 472 } 473 474 //////////////////////////////////////////////////////////////////////// 475 // Insert range methods 476 477 // if hash function throws, or inserting > 1 element, basic exception 478 // safety. Strong otherwise 479 template <class I> 480 typename boost::unordered::detail::enable_if_forward<I, void>::type insert_rangeboost::unordered::detail::grouped_table_impl481 insert_range(I i, I j) 482 { 483 if(i == j) return; 484 485 std::size_t distance = boost::unordered::detail::distance(i, j); 486 if(distance == 1) { 487 node_constructor a(this->node_alloc()); 488 a.construct_with_value2(*i); 489 emplace_impl(a); 490 } 491 else { 492 // Only require basic exception safety here 493 this->reserve_for_insert(this->size_ + distance); 494 495 node_constructor a(this->node_alloc()); 496 for (; i != j; ++i) { 497 a.construct_with_value2(*i); 498 emplace_impl_no_rehash(a); 499 } 500 } 501 } 502 503 template <class I> 504 typename boost::unordered::detail::disable_if_forward<I, void>::type insert_rangeboost::unordered::detail::grouped_table_impl505 insert_range(I i, I j) 506 { 507 node_constructor a(this->node_alloc()); 508 for (; i != j; ++i) { 509 a.construct_with_value2(*i); 510 emplace_impl(a); 511 } 512 } 513 514 //////////////////////////////////////////////////////////////////////// 515 // Erase 516 // 517 // no throw 518 erase_keyboost::unordered::detail::grouped_table_impl519 std::size_t erase_key(key_type const& k) 520 { 521 if(!this->size_) return 0; 522 523 std::size_t key_hash = this->hash(k); 524 std::size_t bucket_index = this->hash_to_bucket(key_hash); 525 link_pointer prev = this->get_previous_start(bucket_index); 526 if (!prev) return 0; 527 528 for (;;) 529 { 530 if (!prev->next_) return 0; 531 std::size_t node_hash = 532 static_cast<node_pointer>(prev->next_)->hash_; 533 if (this->hash_to_bucket(node_hash) != bucket_index) 534 return 0; 535 if (node_hash == key_hash && 536 this->key_eq()(k, this->get_key( 537 static_cast<node_pointer>(prev->next_)->value()))) 538 break; 539 prev = static_cast<node_pointer>(prev->next_)->group_prev_; 540 } 541 542 node_pointer first_node = static_cast<node_pointer>(prev->next_); 543 link_pointer end = first_node->group_prev_->next_; 544 545 std::size_t deleted_count = this->delete_nodes(prev, end); 546 this->fix_bucket(bucket_index, prev); 547 return deleted_count; 548 } 549 eraseboost::unordered::detail::grouped_table_impl550 iterator erase(c_iterator r) 551 { 552 BOOST_ASSERT(r.node_); 553 iterator next(r.node_); 554 ++next; 555 erase_nodes(r.node_, next.node_); 556 return next; 557 } 558 erase_rangeboost::unordered::detail::grouped_table_impl559 iterator erase_range(c_iterator r1, c_iterator r2) 560 { 561 if (r1 == r2) return iterator(r2.node_); 562 erase_nodes(r1.node_, r2.node_); 563 return iterator(r2.node_); 564 } 565 erase_nodesboost::unordered::detail::grouped_table_impl566 link_pointer erase_nodes(node_pointer i, node_pointer j) 567 { 568 std::size_t bucket_index = this->hash_to_bucket(i->hash_); 569 570 // Split the groups containing 'i' and 'j'. 571 // And get the pointer to the node before i while 572 // we're at it. 573 link_pointer prev = split_groups(i, j); 574 575 // If we don't have a 'prev' it means that i is at the 576 // beginning of a block, so search through the blocks in the 577 // same bucket. 578 if (!prev) { 579 prev = this->get_previous_start(bucket_index); 580 while (prev->next_ != i) 581 prev = static_cast<node_pointer>(prev->next_)->group_prev_; 582 } 583 584 // Delete the nodes. 585 do { 586 link_pointer group_end = 587 static_cast<node_pointer>(prev->next_)->group_prev_->next_; 588 this->delete_nodes(prev, group_end); 589 bucket_index = this->fix_bucket(bucket_index, prev); 590 } while(prev->next_ != j); 591 592 return prev; 593 } 594 split_groupsboost::unordered::detail::grouped_table_impl595 static link_pointer split_groups(node_pointer i, node_pointer j) 596 { 597 node_pointer prev = i->group_prev_; 598 if (prev->next_ != i) prev = node_pointer(); 599 600 if (j) { 601 node_pointer first = j; 602 while (first != i && first->group_prev_->next_ == first) { 603 first = first->group_prev_; 604 } 605 606 boost::swap(first->group_prev_, j->group_prev_); 607 if (first == i) return prev; 608 } 609 610 if (prev) { 611 node_pointer first = prev; 612 while (first->group_prev_->next_ == first) { 613 first = first->group_prev_; 614 } 615 boost::swap(first->group_prev_, i->group_prev_); 616 } 617 618 return prev; 619 } 620 621 //////////////////////////////////////////////////////////////////////// 622 // fill_buckets 623 624 template <class NodeCreator> fill_bucketsboost::unordered::detail::grouped_table_impl625 static void fill_buckets(iterator n, table& dst, 626 NodeCreator& creator) 627 { 628 link_pointer prev = dst.get_previous_start(); 629 630 while (n.node_) { 631 std::size_t key_hash = n.node_->hash_; 632 iterator group_end(n.node_->group_prev_->next_); 633 634 node_pointer first_node = creator.create(*n); 635 node_pointer end = first_node; 636 first_node->hash_ = key_hash; 637 prev->next_ = first_node; 638 ++dst.size_; 639 640 for (++n; n != group_end; ++n) 641 { 642 end = creator.create(*n); 643 end->hash_ = key_hash; 644 add_after_node(end, first_node); 645 ++dst.size_; 646 } 647 648 prev = place_in_bucket(dst, prev, end); 649 } 650 } 651 652 // strong otherwise exception safety rehash_implboost::unordered::detail::grouped_table_impl653 void rehash_impl(std::size_t num_buckets) 654 { 655 BOOST_ASSERT(this->buckets_); 656 657 this->create_buckets(num_buckets); 658 link_pointer prev = this->get_previous_start(); 659 while (prev->next_) 660 prev = place_in_bucket(*this, prev, 661 static_cast<node_pointer>(prev->next_)->group_prev_); 662 } 663 664 // Iterate through the nodes placing them in the correct buckets. 665 // pre: prev->next_ is not null. place_in_bucketboost::unordered::detail::grouped_table_impl666 static link_pointer place_in_bucket(table& dst, 667 link_pointer prev, node_pointer end) 668 { 669 bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(end->hash_)); 670 671 if (!b->next_) { 672 b->next_ = prev; 673 return end; 674 } 675 else { 676 link_pointer next = end->next_; 677 end->next_ = b->next_->next_; 678 b->next_->next_ = prev->next_; 679 prev->next_ = next; 680 return prev; 681 } 682 } 683 }; 684 }}} 685 686 #endif 687