boost/unordered/detail/table.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_ALL_HPP_INCLUDED
   8 #define BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED
   9
  10 #include <boost/unordered/detail/buckets.hpp>
  11 #include <boost/unordered/detail/util.hpp>
  12 #include <boost/type_traits/aligned_storage.hpp>
  13 #include <boost/type_traits/alignment_of.hpp>
  14 #include <boost/iterator.hpp>
  15 #include <cmath>
  16
  17 namespace boost { namespace unordered { namespace iterator_detail {
  18
  19     ////////////////////////////////////////////////////////////////////////////
  20     // Iterators
  21     //
  22     // all no throw
  23
  24     template <typename NodePointer, typename Value> struct iterator;
  25     template <typename ConstNodePointer, typename NodePointer,
  26         typename Value> struct c_iterator;
  27     template <typename NodePointer, typename Value> struct l_iterator;
  28     template <typename ConstNodePointer, typename NodePointer,
  29         typename Value> struct cl_iterator;
  30
  31     // Local Iterators
  32     //
  33     // all no throw
  34
  35     template <typename NodePointer, typename Value>
  36     struct l_iterator
  37         : public boost::iterator<
  38             std::forward_iterator_tag, Value, std::ptrdiff_t,
  39             NodePointer, Value&>
  40     {
  41 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
  42         template <typename ConstNodePointer, typename NodePointer2,
  43                 typename Value2>
  44         friend struct boost::unordered::iterator_detail::cl_iterator;
  45     private:
  46 #endif
  47         typedef NodePointer node_pointer;
  48         node_pointer ptr_;
  49         std::size_t bucket_;
  50         std::size_t bucket_count_;
  51
  52     public:
  53
  54         l_iterator() : ptr_() {}
  55
  56         l_iterator(node_pointer x, std::size_t b, std::size_t c)
  57             : ptr_(x), bucket_(b), bucket_count_(c) {}
  58
  59         Value& operator*() const {
  60             return ptr_->value();
  61         }
  62
  63         Value* operator->() const {
  64             return ptr_->value_ptr();
  65         }
  66
  67         l_iterator& operator++() {
  68             ptr_ = static_cast<node_pointer>(ptr_->next_);
  69             if (ptr_ && ptr_->hash_ % bucket_count_ != bucket_)
  70                 ptr_ = node_pointer();
  71             return *this;
  72         }
  73
  74         l_iterator operator++(int) {
  75             l_iterator tmp(*this);
  76             ++(*this);
  77             return tmp;
  78         }
  79
  80         bool operator==(l_iterator x) const {
  81             return ptr_ == x.ptr_;
  82         }
  83
  84         bool operator!=(l_iterator x) const {
  85             return ptr_ != x.ptr_;
  86         }
  87     };
  88
  89     template <typename ConstNodePointer, typename NodePointer, typename Value>
  90     struct cl_iterator
  91         : public boost::iterator<
  92             std::forward_iterator_tag, Value, std::ptrdiff_t,
  93             ConstNodePointer, Value const&>
  94     {
  95         friend struct boost::unordered::iterator_detail::l_iterator
  96             <NodePointer, Value>;
  97     private:
  98
  99         typedef NodePointer node_pointer;
 100         node_pointer ptr_;
 101         std::size_t bucket_;
 102         std::size_t bucket_count_;
 103
 104     public:
 105
 106         cl_iterator() : ptr_() {}
 107
 108         cl_iterator(node_pointer x, std::size_t b, std::size_t c) :
 109             ptr_(x), bucket_(b), bucket_count_(c) {}
 110
 111         cl_iterator(boost::unordered::iterator_detail::l_iterator<
 112                 NodePointer, Value> const& x) :
 113             ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_)
 114         {}
 115
 116         Value const&
 117             operator*() const {
 118             return ptr_->value();
 119         }
 120
 121         Value const* operator->() const {
 122             return ptr_->value_ptr();
 123         }
 124
 125         cl_iterator& operator++() {
 126             ptr_ = static_cast<node_pointer>(ptr_->next_);
 127             if (ptr_ && ptr_->hash_ % bucket_count_ != bucket_)
 128                 ptr_ = node_pointer();
 129             return *this;
 130         }
 131
 132         cl_iterator operator++(int) {
 133             cl_iterator tmp(*this);
 134             ++(*this);
 135             return tmp;
 136         }
 137
 138         friend bool operator==(cl_iterator const& x, cl_iterator const& y) {
 139             return x.ptr_ == y.ptr_;
 140         }
 141
 142         friend bool operator!=(cl_iterator const& x, cl_iterator const& y) {
 143             return x.ptr_ != y.ptr_;
 144         }
 145     };
 146
 147     template <typename NodePointer, typename Value>
 148     struct iterator
 149         : public boost::iterator<
 150             std::forward_iterator_tag, Value, std::ptrdiff_t,
 151             NodePointer, Value&>
 152     {
 153 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
 154         template <typename ConstNodePointer, typename NodePointer2,
 155                 typename Value2>
 156         friend struct boost::unordered::iterator_detail::c_iterator;
 157     private:
 158 #endif
 159         typedef NodePointer node_pointer;
 160         node_pointer node_;
 161
 162     public:
 163
 164         iterator() : node_() {}
 165
 166         explicit iterator(node_pointer const& x) : node_(x) {}
 167
 168         Value& operator*() const {
 169             return node_->value();
 170         }
 171
 172         Value* operator->() const {
 173             return &node_->value();
 174         }
 175
 176         iterator& operator++() {
 177             node_ = static_cast<node_pointer>(node_->next_);
 178             return *this;
 179         }
 180
 181         iterator operator++(int) {
 182             iterator tmp(node_);
 183             node_ = static_cast<node_pointer>(node_->next_);
 184             return tmp;
 185         }
 186
 187         bool operator==(iterator const& x) const {
 188             return node_ == x.node_;
 189         }
 190
 191         bool operator!=(iterator const& x) const {
 192             return node_ != x.node_;
 193         }
 194     };
 195
 196     template <typename ConstNodePointer, typename NodePointer, typename Value>
 197     struct c_iterator
 198         : public boost::iterator<
 199             std::forward_iterator_tag, Value, std::ptrdiff_t,
 200             ConstNodePointer, Value const&>
 201     {
 202         friend struct boost::unordered::iterator_detail::iterator<
 203                 NodePointer, Value>;
 204
 205 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
 206         template <typename K, typename T, typename H, typename P, typename A>
 207         friend class boost::unordered::unordered_map;
 208         template <typename K, typename T, typename H, typename P, typename A>
 209         friend class boost::unordered::unordered_multimap;
 210         template <typename T, typename H, typename P, typename A>
 211         friend class boost::unordered::unordered_set;
 212         template <typename T, typename H, typename P, typename A>
 213         friend class boost::unordered::unordered_multiset;
 214
 215     private:
 216 #endif
 217
 218         typedef NodePointer node_pointer;
 219         node_pointer node_;
 220
 221     public:
 222
 223         c_iterator() : node_() {}
 224
 225         explicit c_iterator(node_pointer const& x) : node_(x) {}
 226
 227         c_iterator(boost::unordered::iterator_detail::iterator<
 228                 NodePointer, Value> const& x) : node_(x.node_) {}
 229
 230         Value const& operator*() const {
 231             return node_->value();
 232         }
 233
 234         Value const* operator->() const {
 235             return &node_->value();
 236         }
 237
 238         c_iterator& operator++() {
 239             node_ = static_cast<node_pointer>(node_->next_);
 240             return *this;
 241         }
 242
 243         c_iterator operator++(int) {
 244             c_iterator tmp(node_);
 245             node_ = static_cast<node_pointer>(node_->next_);
 246             return tmp;
 247         }
 248
 249         friend bool operator==(c_iterator const& x, c_iterator const& y) {
 250             return x.node_ == y.node_;
 251         }
 252
 253         friend bool operator!=(c_iterator const& x, c_iterator const& y) {
 254             return x.node_ != y.node_;
 255         }
 256     };
 257 }}}
 258
 259 namespace boost { namespace unordered { namespace detail {
 260
 261     ////////////////////////////////////////////////////////////////////////////
 262     // convert double to std::size_t
 263
 264     inline std::size_t double_to_size(double f)
 265     {
 266         return f >= static_cast<double>(
 267             (std::numeric_limits<std::size_t>::max)()) ?
 268             (std::numeric_limits<std::size_t>::max)() :
 269             static_cast<std::size_t>(f);
 270     }
 271
 272     // The space used to store values in a node.
 273
 274     template <typename ValueType>
 275     struct value_base
 276     {
 277         typedef ValueType value_type;
 278
 279         typename boost::aligned_storage<
 280             sizeof(value_type),
 281             boost::alignment_of<value_type>::value>::type data_;
 282
 283         void* address() {
 284             return this;
 285         }
 286
 287         value_type& value() {
 288             return *(ValueType*) this;
 289         }
 290
 291         value_type* value_ptr() {
 292             return (ValueType*) this;
 293         }
 294
 295     private:
 296
 297         value_base& operator=(value_base const&);
 298     };
 299
 300     template <typename Types>
 301     struct table :
 302         boost::unordered::detail::buckets<
 303             typename Types::allocator,
 304             typename Types::bucket,
 305             typename Types::node>,
 306         boost::unordered::detail::functions<
 307             typename Types::hasher,
 308             typename Types::key_equal>
 309     {
 310     private:
 311         table(table const&);
 312         table& operator=(table const&);
 313     public:
 314         typedef typename Types::hasher hasher;
 315         typedef typename Types::key_equal key_equal;
 316         typedef typename Types::key_type key_type;
 317         typedef typename Types::extractor extractor;
 318         typedef typename Types::value_type value_type;
 319         typedef typename Types::table table_impl;
 320         typedef typename Types::link_pointer link_pointer;
 321
 322         typedef boost::unordered::detail::functions<
 323             typename Types::hasher,
 324             typename Types::key_equal> functions;
 325
 326         typedef boost::unordered::detail::buckets<
 327             typename Types::allocator,
 328             typename Types::bucket,
 329             typename Types::node> buckets;
 330
 331         typedef typename buckets::node_allocator node_allocator;
 332         typedef typename buckets::node_allocator_traits node_allocator_traits;
 333         typedef typename buckets::node_pointer node_pointer;
 334         typedef typename buckets::const_node_pointer const_node_pointer;
 335
 336         typedef boost::unordered::iterator_detail::
 337             iterator<node_pointer, value_type> iterator;
 338         typedef boost::unordered::iterator_detail::
 339             c_iterator<const_node_pointer, node_pointer, value_type> c_iterator;
 340         typedef boost::unordered::iterator_detail::
 341             l_iterator<node_pointer, value_type> l_iterator;
 342         typedef boost::unordered::iterator_detail::
 343             cl_iterator<const_node_pointer, node_pointer, value_type>
 344             cl_iterator;
 345
 346         // Members
 347
 348         float mlf_;
 349         std::size_t max_load_; // Only use if this->buckets_.
 350
 351         ////////////////////////////////////////////////////////////////////////
 352         // Load methods
 353
 354         std::size_t max_size() const
 355         {
 356             using namespace std;
 357
 358             // size < mlf_ * count
 359             return boost::unordered::detail::double_to_size(ceil(
 360                     static_cast<double>(this->mlf_) *
 361                     static_cast<double>(this->max_bucket_count())
 362                 )) - 1;
 363         }
 364
 365         std::size_t calculate_max_load()
 366         {
 367             using namespace std;
 368
 369             // From 6.3.1/13:
 370             // Only resize when size >= mlf_ * count
 371             return boost::unordered::detail::double_to_size(ceil(
 372                     static_cast<double>(this->mlf_) *
 373                     static_cast<double>(this->bucket_count_)
 374                 ));
 375
 376         }
 377         void max_load_factor(float z)
 378         {
 379             BOOST_ASSERT(z > 0);
 380             mlf_ = (std::max)(z, minimum_max_load_factor);
 381             if (this->buckets_)
 382                 this->max_load_ = this->calculate_max_load();
 383         }
 384
 385         std::size_t min_buckets_for_size(std::size_t size) const
 386         {
 387             BOOST_ASSERT(this->mlf_ != 0);
 388
 389             using namespace std;
 390
 391             // From 6.3.1/13:
 392             // size < mlf_ * count
 393             // => count > size / mlf_
 394             //
 395             // Or from rehash post-condition:
 396             // count > size / mlf_
 397
 398             return boost::unordered::detail::next_prime(
 399                 boost::unordered::detail::double_to_size(floor(
 400                     static_cast<double>(size) /
 401                     static_cast<double>(mlf_))) + 1);
 402         }
 403
 404         ////////////////////////////////////////////////////////////////////////
 405         // Constructors
 406
 407         table(std::size_t num_buckets,
 408                 hasher const& hf,
 409                 key_equal const& eq,
 410                 node_allocator const& a) :
 411             buckets(a, boost::unordered::detail::next_prime(num_buckets)),
 412             functions(hf, eq),
 413             mlf_(1.0f),
 414             max_load_(0)
 415         {}
 416
 417         table(table const& x, node_allocator const& a) :
 418             buckets(a, x.min_buckets_for_size(x.size_)),
 419             functions(x),
 420             mlf_(x.mlf_),
 421             max_load_(0)
 422         {
 423             if(x.size_) {
 424                 table_impl::copy_buckets_to(x, *this);
 425                 this->max_load_ = calculate_max_load();
 426             }
 427         }
 428
 429         // TODO: Why calculate_max_load?
 430         table(table& x, boost::unordered::detail::move_tag m) :
 431             buckets(x, m),
 432             functions(x),
 433             mlf_(x.mlf_),
 434             max_load_(calculate_max_load())
 435         {}
 436
 437         // TODO: Why not calculate_max_load?
 438         // TODO: Why do I use x's bucket count?
 439         table(table& x, node_allocator const& a,
 440                 boost::unordered::detail::move_tag m) :
 441             buckets(a, x.bucket_count_),
 442             functions(x),
 443             mlf_(x.mlf_),
 444             max_load_(x.max_load_)
 445         {
 446             if(a == x.node_alloc()) {
 447                 this->buckets::swap(x, false_type());
 448             }
 449             else if(x.size_) {
 450                 // Use a temporary table because move_buckets_to leaves the
 451                 // source container in a complete mess.
 452
 453                 buckets tmp(x, m);
 454                 table_impl::move_buckets_to(tmp, *this);
 455                 this->max_load_ = calculate_max_load();
 456             }
 457         }
 458
 459         // Iterators
 460
 461         node_pointer begin() const {
 462             return !this->buckets_ ?
 463                 node_pointer() : this->get_start();
 464         }
 465
 466         // Assignment
 467
 468         void assign(table const& x)
 469         {
 470             assign(x,
 471                 boost::unordered::detail::integral_constant<bool,
 472                     allocator_traits<node_allocator>::
 473                     propagate_on_container_copy_assignment::value>());
 474         }
 475
 476         void assign(table const& x, false_type)
 477         {
 478             table tmp(x, this->node_alloc());
 479             this->swap(tmp, false_type());
 480         }
 481
 482         void assign(table const& x, true_type)
 483         {
 484             table tmp(x, x.node_alloc());
 485             // Need to delete before setting the allocator so that buckets
 486             // aren't deleted with the wrong allocator.
 487             if(this->buckets_) this->delete_buckets();
 488             // TODO: Can allocator assignment throw?
 489             this->allocators_.assign(x.allocators_);
 490             this->swap(tmp, false_type());
 491         }
 492
 493         void move_assign(table& x)
 494         {
 495             move_assign(x,
 496                 boost::unordered::detail::integral_constant<bool,
 497                     allocator_traits<node_allocator>::
 498                     propagate_on_container_move_assignment::value>());
 499         }
 500
 501         void move_assign(table& x, true_type)
 502         {
 503             if(this->buckets_) this->delete_buckets();
 504             this->allocators_.move_assign(x.allocators_);
 505             move_assign_no_alloc(x);
 506         }
 507
 508         void move_assign(table& x, false_type)
 509         {
 510             if(this->node_alloc() == x.node_alloc()) {
 511                 if(this->buckets_) this->delete_buckets();
 512                 move_assign_no_alloc(x);
 513             }
 514             else {
 515                 boost::unordered::detail::set_hash_functions<hasher, key_equal>
 516                     new_func_this(*this, x);
 517
 518                 if (x.size_) {
 519                     buckets b(this->node_alloc(),
 520                         x.min_buckets_for_size(x.size_));
 521                     buckets tmp(x, move_tag());
 522                     table_impl::move_buckets_to(tmp, b);
 523                     b.swap(*this);
 524                 }
 525                 else {
 526                     this->clear();
 527                 }
 528
 529                 this->mlf_ = x.mlf_;
 530                 if (this->buckets_) this->max_load_ = calculate_max_load();
 531                 new_func_this.commit();
 532             }
 533         }
 534
 535         void move_assign_no_alloc(table& x)
 536         {
 537             boost::unordered::detail::set_hash_functions<hasher, key_equal>
 538                 new_func_this(*this, x);
 539             // No throw from here.
 540             this->move_buckets_from(x);
 541             this->mlf_ = x.mlf_;
 542             this->max_load_ = x.max_load_;
 543             new_func_this.commit();
 544         }
 545
 546         ////////////////////////////////////////////////////////////////////////
 547         // Swap & Move
 548
 549         void swap(table& x)
 550         {
 551             swap(x,
 552                 boost::unordered::detail::integral_constant<bool,
 553                     allocator_traits<node_allocator>::
 554                     propagate_on_container_swap::value>());
 555         }
 556
 557         // Only swaps the allocators if Propagate::value
 558         template <typename Propagate>
 559         void swap(table& x, Propagate p)
 560         {
 561             boost::unordered::detail::set_hash_functions<hasher, key_equal>
 562                 op1(*this, x);
 563             boost::unordered::detail::set_hash_functions<hasher, key_equal>
 564                 op2(x, *this);
 565             // I think swap can throw if Propagate::value,
 566             // since the allocators' swap can throw. Not sure though.
 567             this->buckets::swap(x, p);
 568             std::swap(this->mlf_, x.mlf_);
 569             std::swap(this->max_load_, x.max_load_);
 570             op1.commit();
 571             op2.commit();
 572         }
 573
 574         // Swap everything but the allocators, and the functions objects.
 575         void swap_contents(table& x)
 576         {
 577             this->buckets::swap(x, false_type());
 578             std::swap(this->mlf_, x.mlf_);
 579             std::swap(this->max_load_, x.max_load_);
 580         }
 581
 582         // Accessors
 583
 584         key_type const& get_key(value_type const& x) const
 585         {
 586             return extractor::extract(x);
 587         }
 588
 589         // Find Node
 590
 591         template <typename Key, typename Hash, typename Pred>
 592         node_pointer generic_find_node(
 593                 Key const& k,
 594                 Hash const& hash_function,
 595                 Pred const& eq) const
 596         {
 597             if (!this->size_) return node_pointer();
 598             return static_cast<table_impl const*>(this)->
 599                 find_node_impl(hash_function(k), k, eq);
 600         }
 601
 602         node_pointer find_node(
 603                 std::size_t hash,
 604                 key_type const& k) const
 605         {
 606             if (!this->size_) return node_pointer();
 607             return static_cast<table_impl const*>(this)->
 608                 find_node_impl(hash, k, this->key_eq());
 609         }
 610
 611         node_pointer find_node(key_type const& k) const
 612         {
 613             if (!this->size_) return node_pointer();
 614             return static_cast<table_impl const*>(this)->
 615                 find_node_impl(this->hash_function()(k), k, this->key_eq());
 616         }
 617
 618         node_pointer find_matching_node(node_pointer n) const
 619         {
 620             // TODO: Does this apply to C++11?
 621             //
 622             // For some stupid reason, I decided to support equality comparison
 623             // when different hash functions are used. So I can't use the hash
 624             // value from the node here.
 625
 626             return find_node(get_key(n->value()));
 627         }
 628
 629         // Reserve and rehash
 630
 631         void reserve_for_insert(std::size_t);
 632         void rehash(std::size_t);
 633     };
 634
 635     ////////////////////////////////////////////////////////////////////////////
 636     // Reserve & Rehash
 637
 638     // basic exception safety
 639     template <typename Types>
 640     inline void table<Types>::reserve_for_insert(std::size_t size)
 641     {
 642         if (!this->buckets_) {
 643             this->bucket_count_ = (std::max)(this->bucket_count_,
 644                 this->min_buckets_for_size(size));
 645             this->create_buckets();
 646             this->max_load_ = this->calculate_max_load();
 647         }
 648         else if(size >= max_load_) {
 649             std::size_t num_buckets
 650                 = this->min_buckets_for_size((std::max)(size,
 651                     this->size_ + (this->size_ >> 1)));
 652             if (num_buckets != this->bucket_count_) {
 653                 static_cast<table_impl*>(this)->rehash_impl(num_buckets);
 654                 this->max_load_ = this->calculate_max_load();
 655             }
 656         }
 657     }
 658
 659     // if hash function throws, basic exception safety
 660     // strong otherwise.
 661
 662     template <typename Types>
 663     void table<Types>::rehash(std::size_t min_buckets)
 664     {
 665         using namespace std;
 666
 667         if(!this->size_) {
 668             if(this->buckets_) this->delete_buckets();
 669             this->bucket_count_ = next_prime(min_buckets);
 670         }
 671         else {
 672             min_buckets = next_prime((std::max)(min_buckets,
 673                 boost::unordered::detail::double_to_size(floor(
 674                     static_cast<double>(this->size_) /
 675                     static_cast<double>(mlf_))) + 1));
 676
 677             if(min_buckets != this->bucket_count_) {
 678                 static_cast<table_impl*>(this)->rehash_impl(min_buckets);
 679                 this->max_load_ = this->calculate_max_load();
 680             }
 681         }
 682     }
 683 }}}
 684
 685 #endif