ceph/src/boost/libs/unordered/include/boost/unordered/detail/unique.hpp

   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
  38         unique_node() :
  39             next_(),
  40             hash_(0)
  41         {}
  42
  43         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
  63         ptr_node() :
  64             bucket_base(),
  65             hash_(0)
  66         {}
  67
  68         void init(node_pointer)
  69         {
  70         }
  71
  72         void* address() { return value_base_.address(); }
  73         value_type& value() { return value_base_.value(); }
  74         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 typename boost::remove_const<T>::type nonconst;
 110
 111         typedef boost::unordered::detail::allocator_traits<
 112             typename boost::unordered::detail::rebind_wrap<A,
 113                 boost::unordered::detail::ptr_node<nonconst> >::type
 114         > tentative_node_traits;
 115
 116         typedef boost::unordered::detail::allocator_traits<
 117             typename boost::unordered::detail::rebind_wrap<A,
 118                 boost::unordered::detail::ptr_bucket >::type
 119         > tentative_bucket_traits;
 120
 121         typedef pick_node2<A, nonconst,
 122             typename tentative_node_traits::pointer,
 123             typename tentative_bucket_traits::pointer> pick;
 124
 125         typedef typename pick::node node;
 126         typedef typename pick::bucket bucket;
 127         typedef typename pick::link_pointer link_pointer;
 128     };
 129
 130     template <typename Types>
 131     struct table_impl : boost::unordered::detail::table<Types>
 132     {
 133         typedef boost::unordered::detail::table<Types> table;
 134         typedef typename table::value_type value_type;
 135         typedef typename table::bucket bucket;
 136         typedef typename table::policy policy;
 137         typedef typename table::node_pointer node_pointer;
 138         typedef typename table::node_allocator node_allocator;
 139         typedef typename table::node_allocator_traits node_allocator_traits;
 140         typedef typename table::bucket_pointer bucket_pointer;
 141         typedef typename table::link_pointer link_pointer;
 142         typedef typename table::hasher hasher;
 143         typedef typename table::key_equal key_equal;
 144         typedef typename table::key_type key_type;
 145         typedef typename table::node_constructor node_constructor;
 146         typedef typename table::node_tmp node_tmp;
 147         typedef typename table::extractor extractor;
 148         typedef typename table::iterator iterator;
 149         typedef typename table::c_iterator c_iterator;
 150
 151         typedef std::pair<iterator, bool> emplace_return;
 152
 153         // Constructors
 154
 155         table_impl(std::size_t n,
 156                 hasher const& hf,
 157                 key_equal const& eq,
 158                 node_allocator const& a)
 159           : table(n, hf, eq, a)
 160         {}
 161
 162         table_impl(table_impl const& x)
 163           : table(x, node_allocator_traits::
 164                 select_on_container_copy_construction(x.node_alloc()))
 165         {
 166             this->init(x);
 167         }
 168
 169         table_impl(table_impl const& x,
 170                 node_allocator const& a)
 171           : table(x, a)
 172         {
 173             this->init(x);
 174         }
 175
 176         table_impl(table_impl& x,
 177                 boost::unordered::detail::move_tag m)
 178           : table(x, m)
 179         {}
 180
 181         table_impl(table_impl& x,
 182                 node_allocator const& a,
 183                 boost::unordered::detail::move_tag m)
 184           : table(x, a, m)
 185         {
 186             this->move_init(x);
 187         }
 188
 189         // Node functions.
 190
 191         static inline node_pointer next_node(link_pointer n) {
 192             return static_cast<node_pointer>(n->next_);
 193         }
 194
 195         // Accessors
 196
 197         template <class Key, class Pred>
 198         node_pointer find_node_impl(
 199                 std::size_t key_hash,
 200                 Key const& k,
 201                 Pred const& eq) const
 202         {
 203             std::size_t bucket_index = this->hash_to_bucket(key_hash);
 204             node_pointer n = this->begin(bucket_index);
 205
 206             for (;;)
 207             {
 208                 if (!n) return n;
 209
 210                 std::size_t node_hash = n->hash_;
 211                 if (key_hash == node_hash)
 212                 {
 213                     if (eq(k, this->get_key(n->value())))
 214                         return n;
 215                 }
 216                 else
 217                 {
 218                     if (this->hash_to_bucket(node_hash) != bucket_index)
 219                         return node_pointer();
 220                 }
 221
 222                 n = next_node(n);
 223             }
 224         }
 225
 226         std::size_t count(key_type const& k) const
 227         {
 228             return this->find_node(k) ? 1 : 0;
 229         }
 230
 231         value_type& at(key_type const& k) const
 232         {
 233             if (this->size_) {
 234                 node_pointer n = this->find_node(k);
 235                 if (n) return n->value();
 236             }
 237
 238             boost::throw_exception(
 239                 std::out_of_range("Unable to find key in unordered_map."));
 240         }
 241
 242         std::pair<iterator, iterator>
 243             equal_range(key_type const& k) const
 244         {
 245             node_pointer n = this->find_node(k);
 246             return std::make_pair(iterator(n), iterator(n ? next_node(n) : n));
 247         }
 248
 249         // equals
 250
 251         bool equals(table_impl const& other) const
 252         {
 253             if(this->size_ != other.size_) return false;
 254
 255             for(node_pointer n1 = this->begin(); n1; n1 = next_node(n1))
 256             {
 257                 node_pointer n2 = other.find_node(other.get_key(n1->value()));
 258
 259                 if (!n2 || n1->value() != n2->value())
 260                     return false;
 261             }
 262
 263             return true;
 264         }
 265
 266         // Emplace/Insert
 267
 268         inline node_pointer add_node(
 269                 node_pointer n,
 270                 std::size_t key_hash)
 271         {
 272             n->hash_ = key_hash;
 273
 274             bucket_pointer b = this->get_bucket(this->hash_to_bucket(key_hash));
 275
 276             if (!b->next_)
 277             {
 278                 link_pointer start_node = this->get_previous_start();
 279
 280                 if (start_node->next_) {
 281                     this->get_bucket(this->hash_to_bucket(
 282                         next_node(start_node)->hash_)
 283                     )->next_ = n;
 284                 }
 285
 286                 b->next_ = start_node;
 287                 n->next_ = start_node->next_;
 288                 start_node->next_ = n;
 289             }
 290             else
 291             {
 292                 n->next_ = b->next_->next_;
 293                 b->next_->next_ = n;
 294             }
 295
 296             ++this->size_;
 297             return n;
 298         }
 299
 300         inline node_pointer resize_and_add_node(node_pointer n, std::size_t key_hash)
 301         {
 302             node_tmp b(n, this->node_alloc());
 303             this->reserve_for_insert(this->size_ + 1);
 304             return this->add_node(b.release(), key_hash);
 305         }
 306
 307         value_type& operator[](key_type const& k)
 308         {
 309             std::size_t key_hash = this->hash(k);
 310             node_pointer pos = this->find_node(key_hash, k);
 311             if (pos) {
 312                 return pos->value();
 313             }
 314             else {
 315                 return this->resize_and_add_node(
 316                     boost::unordered::detail::func::construct_node_pair(this->node_alloc(), k),
 317                     key_hash)->value();
 318             }
 319         }
 320
 321 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 322 #   if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 323         emplace_return emplace(boost::unordered::detail::emplace_args1<
 324                 boost::unordered::detail::please_ignore_this_overload> const&)
 325         {
 326             BOOST_ASSERT(false);
 327             return emplace_return(iterator(), false);
 328         }
 329
 330         iterator emplace_hint(c_iterator,
 331             boost::unordered::detail::emplace_args1<
 332                 boost::unordered::detail::please_ignore_this_overload> const&)
 333         {
 334             BOOST_ASSERT(false);
 335             return iterator();
 336         }
 337 #   else
 338         emplace_return emplace(
 339                 boost::unordered::detail::please_ignore_this_overload const&)
 340         {
 341             BOOST_ASSERT(false);
 342             return emplace_return(iterator(), false);
 343         }
 344
 345         iterator emplace_hint(c_iterator,
 346                 boost::unordered::detail::please_ignore_this_overload const&)
 347         {
 348             BOOST_ASSERT(false);
 349             return iterator();
 350         }
 351 #   endif
 352 #endif
 353
 354         template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
 355         emplace_return emplace(BOOST_UNORDERED_EMPLACE_ARGS)
 356         {
 357 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 358             return emplace_impl(
 359                 extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD),
 360                 BOOST_UNORDERED_EMPLACE_FORWARD);
 361 #else
 362             return emplace_impl(
 363                 extractor::extract(args.a0, args.a1),
 364                 BOOST_UNORDERED_EMPLACE_FORWARD);
 365 #endif
 366         }
 367
 368         template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
 369         iterator emplace_hint(c_iterator hint,
 370             BOOST_UNORDERED_EMPLACE_ARGS)
 371         {
 372 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 373             return emplace_hint_impl(hint,
 374                 extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD),
 375                 BOOST_UNORDERED_EMPLACE_FORWARD);
 376 #else
 377             return emplace_hint_impl(hint,
 378                 extractor::extract(args.a0, args.a1),
 379                 BOOST_UNORDERED_EMPLACE_FORWARD);
 380 #endif
 381         }
 382
 383 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 384         template <typename A0>
 385         emplace_return emplace(
 386                 boost::unordered::detail::emplace_args1<A0> const& args)
 387         {
 388             return emplace_impl(extractor::extract(args.a0), args);
 389         }
 390
 391         template <typename A0>
 392         iterator emplace_hint(c_iterator hint,
 393                 boost::unordered::detail::emplace_args1<A0> const& args)
 394         {
 395             return emplace_hint_impl(hint, extractor::extract(args.a0), args);
 396         }
 397 #endif
 398
 399         template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
 400         iterator emplace_hint_impl(c_iterator hint, key_type const& k,
 401             BOOST_UNORDERED_EMPLACE_ARGS)
 402         {
 403             if (hint.node_ && this->key_eq()(k, this->get_key(*hint))) {
 404                 return iterator(hint.node_);
 405             }
 406             else {
 407                 return emplace_impl(k, BOOST_UNORDERED_EMPLACE_FORWARD).first;
 408             }
 409         }
 410
 411         template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
 412         emplace_return emplace_impl(key_type const& k,
 413             BOOST_UNORDERED_EMPLACE_ARGS)
 414         {
 415             std::size_t key_hash = this->hash(k);
 416             node_pointer pos = this->find_node(key_hash, k);
 417             if (pos) {
 418                 return emplace_return(iterator(pos), false);
 419             }
 420             else {
 421                 return emplace_return(
 422                     iterator(this->resize_and_add_node(
 423                         boost::unordered::detail::func::construct_node_from_args(
 424                             this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
 425                         key_hash)),
 426                     true);
 427             }
 428         }
 429
 430         template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
 431         iterator emplace_hint_impl(c_iterator hint, no_key,
 432             BOOST_UNORDERED_EMPLACE_ARGS)
 433         {
 434             node_tmp b(
 435                 boost::unordered::detail::func::construct_node_from_args(
 436                     this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
 437                 this->node_alloc());
 438             key_type const& k = this->get_key(b.node_->value());
 439             if (hint.node_ && this->key_eq()(k, this->get_key(*hint))) {
 440                 return iterator(hint.node_);
 441             }
 442             std::size_t key_hash = this->hash(k);
 443             node_pointer pos = this->find_node(key_hash, k);
 444             if (pos) {
 445                 return iterator(pos);
 446             }
 447             else {
 448                 return iterator(this->resize_and_add_node(b.release(), key_hash));
 449             }
 450         }
 451
 452         template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
 453         emplace_return emplace_impl(no_key, BOOST_UNORDERED_EMPLACE_ARGS)
 454         {
 455             node_tmp b(
 456                 boost::unordered::detail::func::construct_node_from_args(
 457                     this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
 458                 this->node_alloc());
 459             key_type const& k = this->get_key(b.node_->value());
 460             std::size_t key_hash = this->hash(k);
 461             node_pointer pos = this->find_node(key_hash, k);
 462             if (pos) {
 463                 return emplace_return(iterator(pos), false);
 464             }
 465             else {
 466                 return emplace_return(
 467                     iterator(this->resize_and_add_node(b.release(), key_hash)),
 468                     true);
 469             }
 470         }
 471
 472         ////////////////////////////////////////////////////////////////////////
 473         // Insert range methods
 474         //
 475         // if hash function throws, or inserting > 1 element, basic exception
 476         // safety strong otherwise
 477
 478         template <class InputIt>
 479         void insert_range(InputIt i, InputIt j)
 480         {
 481             if(i != j)
 482                 return insert_range_impl(extractor::extract(*i), i, j);
 483         }
 484
 485         template <class InputIt>
 486         void insert_range_impl(key_type const& k, InputIt i, InputIt j)
 487         {
 488             insert_range_impl2(k, i, j);
 489
 490             while(++i != j) {
 491                 // Note: can't use get_key as '*i' might not be value_type - it
 492                 // could be a pair with first_types as key_type without const or
 493                 // a different second_type.
 494                 //
 495                 // TODO: Might be worth storing the value_type instead of the
 496                 // key here. Could be more efficient if '*i' is expensive. Could
 497                 // be less efficient if copying the full value_type is
 498                 // expensive.
 499                 insert_range_impl2(extractor::extract(*i), i, j);
 500             }
 501         }
 502
 503         template <class InputIt>
 504         void insert_range_impl2(key_type const& k, InputIt i, InputIt j)
 505         {
 506             // No side effects in this initial code
 507             std::size_t key_hash = this->hash(k);
 508             node_pointer pos = this->find_node(key_hash, k);
 509
 510             if (!pos) {
 511                 node_tmp b(
 512                     boost::unordered::detail::func::construct_node(this->node_alloc(), *i),
 513                     this->node_alloc());
 514                 if(this->size_ + 1 > this->max_load_)
 515                     this->reserve_for_insert(this->size_ +
 516                         boost::unordered::detail::insert_size(i, j));
 517                 this->add_node(b.release(), key_hash);
 518             }
 519         }
 520
 521         template <class InputIt>
 522         void insert_range_impl(no_key, InputIt i, InputIt j)
 523         {
 524             node_constructor a(this->node_alloc());
 525
 526             do {
 527                 if (!a.node_) { a.create_node(); }
 528                 boost::unordered::detail::func::call_construct(
 529                     a.alloc_, a.node_->value_ptr(), *i);
 530                 node_tmp b(a.release(), a.alloc_);
 531
 532                 key_type const& k = this->get_key(b.node_->value());
 533                 std::size_t key_hash = this->hash(k);
 534                 node_pointer pos = this->find_node(key_hash, k);
 535
 536                 if (pos) {
 537                     a.reclaim(b.release());
 538                 }
 539                 else {
 540                     // reserve has basic exception safety if the hash function
 541                     // throws, strong otherwise.
 542                     this->reserve_for_insert(this->size_ + 1);
 543                     this->add_node(b.release(), key_hash);
 544                 }
 545             } while(++i != j);
 546         }
 547
 548         ////////////////////////////////////////////////////////////////////////
 549         // Erase
 550         //
 551         // no throw
 552
 553         std::size_t erase_key(key_type const& k)
 554         {
 555             if(!this->size_) return 0;
 556
 557             std::size_t key_hash = this->hash(k);
 558             std::size_t bucket_index = this->hash_to_bucket(key_hash);
 559             link_pointer prev = this->get_previous_start(bucket_index);
 560             if (!prev) return 0;
 561
 562             for (;;)
 563             {
 564                 if (!prev->next_) return 0;
 565                 std::size_t node_hash = next_node(prev)->hash_;
 566                 if (this->hash_to_bucket(node_hash) != bucket_index)
 567                     return 0;
 568                 if (node_hash == key_hash &&
 569                         this->key_eq()(k, this->get_key(
 570                         next_node(prev)->value())))
 571                     break;
 572                 prev = prev->next_;
 573             }
 574
 575             link_pointer end = next_node(prev)->next_;
 576
 577             std::size_t deleted_count = this->delete_nodes(prev, end);
 578             this->fix_bucket(bucket_index, prev);
 579             return deleted_count;
 580         }
 581
 582         iterator erase(c_iterator r)
 583         {
 584             BOOST_ASSERT(r.node_);
 585             node_pointer next = next_node(r.node_);
 586             erase_nodes(r.node_, next);
 587             return iterator(next);
 588         }
 589
 590         iterator erase_range(c_iterator r1, c_iterator r2)
 591         {
 592             if (r1 == r2) return iterator(r2.node_);
 593             erase_nodes(r1.node_, r2.node_);
 594             return iterator(r2.node_);
 595         }
 596
 597         void erase_nodes(node_pointer i, node_pointer j)
 598         {
 599             std::size_t bucket_index = this->hash_to_bucket(i->hash_);
 600
 601             // Find the node before i.
 602             link_pointer prev = this->get_previous_start(bucket_index);
 603             while(prev->next_ != i) prev = prev->next_;
 604
 605             // Delete the nodes.
 606             do {
 607                 this->delete_node(prev);
 608                 bucket_index = this->fix_bucket(bucket_index, prev);
 609             } while (prev->next_ != j);
 610         }
 611
 612         ////////////////////////////////////////////////////////////////////////
 613         // fill_buckets
 614
 615         void copy_buckets(table const& src) {
 616             this->create_buckets(this->bucket_count_);
 617
 618             for(node_pointer n = src.begin(); n; n = next_node(n)) {
 619                 this->add_node(
 620                     boost::unordered::detail::func::construct_node(
 621                      this->node_alloc(), n->value()), n->hash_);
 622             }
 623         }
 624
 625         void move_buckets(table const& src) {
 626             this->create_buckets(this->bucket_count_);
 627
 628             for(node_pointer n = src.begin(); n; n = next_node(n)) {
 629                 this->add_node(
 630                     boost::unordered::detail::func::construct_node(
 631                         this->node_alloc(), boost::move(n->value())), n->hash_);
 632             }
 633         }
 634
 635         void assign_buckets(table const& src)
 636         {
 637             node_holder<node_allocator> holder(*this);
 638             for(node_pointer n = src.begin(); n; n = next_node(n)) {
 639                 this->add_node(holder.copy_of(n->value()), n->hash_);
 640             }
 641         }
 642
 643         void move_assign_buckets(table& src)
 644         {
 645             node_holder<node_allocator> holder(*this);
 646             for(node_pointer n = src.begin(); n; n = next_node(n)) {
 647                 this->add_node(holder.move_copy_of(n->value()), n->hash_);
 648             }
 649         }
 650
 651         // strong otherwise exception safety
 652         void rehash_impl(std::size_t num_buckets)
 653         {
 654             BOOST_ASSERT(this->buckets_);
 655
 656             this->create_buckets(num_buckets);
 657             link_pointer prev = this->get_previous_start();
 658             while (prev->next_)
 659                 prev = place_in_bucket(*this, prev);
 660         }
 661
 662         // Iterate through the nodes placing them in the correct buckets.
 663         // pre: prev->next_ is not null.
 664         static link_pointer place_in_bucket(table& dst, link_pointer prev)
 665         {
 666             node_pointer n = next_node(prev);
 667             bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(n->hash_));
 668
 669             if (!b->next_) {
 670                 b->next_ = prev;
 671                 return n;
 672             }
 673             else {
 674                 prev->next_ = n->next_;
 675                 n->next_ = b->next_->next_;
 676                 b->next_->next_ = n;
 677                 return prev;
 678             }
 679         }
 680     };
 681 }}}
 682
 683 #endif