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/config.hpp>
  11 #if defined(BOOST_HAS_PRAGMA_ONCE)
  12 #pragma once
  13 #endif
  14
  15 #include <boost/unordered/detail/buckets.hpp>
  16
  17 #if defined(BOOST_MSVC)
  18 #pragma warning(push)
  19 #pragma warning(disable:4127) // conditional expression is constant
  20 #endif
  21
  22 namespace boost { namespace unordered { namespace detail {
  23
  24     ////////////////////////////////////////////////////////////////////////////
  25     // convert double to std::size_t
  26
  27     inline std::size_t double_to_size(double f)
  28     {
  29         return f >= static_cast<double>(
  30             (std::numeric_limits<std::size_t>::max)()) ?
  31             (std::numeric_limits<std::size_t>::max)() :
  32             static_cast<std::size_t>(f);
  33     }
  34
  35     // The space used to store values in a node.
  36
  37     template <typename ValueType>
  38     struct value_base
  39     {
  40         typedef ValueType value_type;
  41
  42         typename boost::aligned_storage<
  43             sizeof(value_type),
  44             boost::alignment_of<value_type>::value>::type data_;
  45
  46         value_base() :
  47             data_()
  48         {}
  49
  50         void* address() {
  51             return this;
  52         }
  53
  54         value_type& value() {
  55             return *(ValueType*) this;
  56         }
  57
  58         value_type* value_ptr() {
  59             return (ValueType*) this;
  60         }
  61
  62     private:
  63
  64         value_base& operator=(value_base const&);
  65     };
  66
  67     template <typename Types>
  68     struct table :
  69         boost::unordered::detail::functions<
  70             typename Types::hasher,
  71             typename Types::key_equal>
  72     {
  73     private:
  74         table(table const&);
  75         table& operator=(table const&);
  76     public:
  77         typedef typename Types::node node;
  78         typedef typename Types::bucket bucket;
  79         typedef typename Types::hasher hasher;
  80         typedef typename Types::key_equal key_equal;
  81         typedef typename Types::key_type key_type;
  82         typedef typename Types::extractor extractor;
  83         typedef typename Types::value_type value_type;
  84         typedef typename Types::table table_impl;
  85         typedef typename Types::link_pointer link_pointer;
  86         typedef typename Types::policy policy;
  87         typedef typename Types::iterator iterator;
  88         typedef typename Types::c_iterator c_iterator;
  89         typedef typename Types::l_iterator l_iterator;
  90         typedef typename Types::cl_iterator cl_iterator;
  91
  92         typedef boost::unordered::detail::functions<
  93             typename Types::hasher,
  94             typename Types::key_equal> functions;
  95         typedef typename functions::set_hash_functions set_hash_functions;
  96
  97         typedef typename Types::allocator allocator;
  98         typedef typename boost::unordered::detail::
  99             rebind_wrap<allocator, node>::type node_allocator;
 100         typedef typename boost::unordered::detail::
 101             rebind_wrap<allocator, bucket>::type bucket_allocator;
 102         typedef boost::unordered::detail::allocator_traits<node_allocator>
 103             node_allocator_traits;
 104         typedef boost::unordered::detail::allocator_traits<bucket_allocator>
 105             bucket_allocator_traits;
 106         typedef typename node_allocator_traits::pointer
 107             node_pointer;
 108         typedef typename node_allocator_traits::const_pointer
 109             const_node_pointer;
 110         typedef typename bucket_allocator_traits::pointer
 111             bucket_pointer;
 112         typedef boost::unordered::detail::node_constructor<node_allocator>
 113             node_constructor;
 114         typedef boost::unordered::detail::node_tmp<node_allocator>
 115             node_tmp;
 116
 117         ////////////////////////////////////////////////////////////////////////
 118         // Members
 119
 120         boost::unordered::detail::compressed<bucket_allocator, node_allocator>
 121             allocators_;
 122         std::size_t bucket_count_;
 123         std::size_t size_;
 124         float mlf_;
 125         std::size_t max_load_;
 126         bucket_pointer buckets_;
 127
 128         ////////////////////////////////////////////////////////////////////////
 129         // Node functions
 130
 131         static inline node_pointer next_node(link_pointer n) {
 132             return static_cast<node_pointer>(n->next_);
 133         }
 134
 135         ////////////////////////////////////////////////////////////////////////
 136         // Data access
 137
 138         bucket_allocator const& bucket_alloc() const
 139         {
 140             return allocators_.first();
 141         }
 142
 143         node_allocator const& node_alloc() const
 144         {
 145             return allocators_.second();
 146         }
 147
 148         bucket_allocator& bucket_alloc()
 149         {
 150             return allocators_.first();
 151         }
 152
 153         node_allocator& node_alloc()
 154         {
 155             return allocators_.second();
 156         }
 157
 158         std::size_t max_bucket_count() const
 159         {
 160             // -1 to account for the start bucket.
 161             return policy::prev_bucket_count(
 162                 bucket_allocator_traits::max_size(bucket_alloc()) - 1);
 163         }
 164
 165         bucket_pointer get_bucket(std::size_t bucket_index) const
 166         {
 167             BOOST_ASSERT(buckets_);
 168             return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
 169         }
 170
 171         link_pointer get_previous_start() const
 172         {
 173             return get_bucket(bucket_count_)->first_from_start();
 174         }
 175
 176         link_pointer get_previous_start(std::size_t bucket_index) const
 177         {
 178             return get_bucket(bucket_index)->next_;
 179         }
 180
 181         node_pointer begin() const
 182         {
 183             return size_ ? next_node(get_previous_start()) : node_pointer();
 184         }
 185
 186         node_pointer begin(std::size_t bucket_index) const
 187         {
 188             if (!size_) return node_pointer();
 189             link_pointer prev = get_previous_start(bucket_index);
 190             return prev ? next_node(prev) : node_pointer();
 191         }
 192
 193         std::size_t hash_to_bucket(std::size_t hash_value) const
 194         {
 195             return policy::to_bucket(bucket_count_, hash_value);
 196         }
 197
 198         float load_factor() const
 199         {
 200             BOOST_ASSERT(bucket_count_ != 0);
 201             return static_cast<float>(size_)
 202                 / static_cast<float>(bucket_count_);
 203         }
 204
 205         std::size_t bucket_size(std::size_t index) const
 206         {
 207             node_pointer n = begin(index);
 208             if (!n) return 0;
 209
 210             std::size_t count = 0;
 211             while(n && hash_to_bucket(n->hash_) == index)
 212             {
 213                 ++count;
 214                 n = next_node(n);
 215             }
 216
 217             return count;
 218         }
 219
 220         ////////////////////////////////////////////////////////////////////////
 221         // Load methods
 222
 223         std::size_t max_size() const
 224         {
 225             using namespace std;
 226
 227             // size < mlf_ * count
 228             return boost::unordered::detail::double_to_size(ceil(
 229                     static_cast<double>(mlf_) *
 230                     static_cast<double>(max_bucket_count())
 231                 )) - 1;
 232         }
 233
 234         void recalculate_max_load()
 235         {
 236             using namespace std;
 237
 238             // From 6.3.1/13:
 239             // Only resize when size >= mlf_ * count
 240             max_load_ = buckets_ ? boost::unordered::detail::double_to_size(ceil(
 241                     static_cast<double>(mlf_) *
 242                     static_cast<double>(bucket_count_)
 243                 )) : 0;
 244
 245         }
 246
 247         void max_load_factor(float z)
 248         {
 249             BOOST_ASSERT(z > 0);
 250             mlf_ = (std::max)(z, minimum_max_load_factor);
 251             recalculate_max_load();
 252         }
 253
 254         std::size_t min_buckets_for_size(std::size_t size) const
 255         {
 256             BOOST_ASSERT(mlf_ >= minimum_max_load_factor);
 257
 258             using namespace std;
 259
 260             // From 6.3.1/13:
 261             // size < mlf_ * count
 262             // => count > size / mlf_
 263             //
 264             // Or from rehash post-condition:
 265             // count > size / mlf_
 266
 267             return policy::new_bucket_count(
 268                 boost::unordered::detail::double_to_size(floor(
 269                     static_cast<double>(size) /
 270                     static_cast<double>(mlf_)) + 1));
 271         }
 272
 273         ////////////////////////////////////////////////////////////////////////
 274         // Constructors
 275
 276         table(std::size_t num_buckets,
 277                 hasher const& hf,
 278                 key_equal const& eq,
 279                 node_allocator const& a) :
 280             functions(hf, eq),
 281             allocators_(a,a),
 282             bucket_count_(policy::new_bucket_count(num_buckets)),
 283             size_(0),
 284             mlf_(1.0f),
 285             max_load_(0),
 286             buckets_()
 287         {}
 288
 289         table(table const& x, node_allocator const& a) :
 290             functions(x),
 291             allocators_(a,a),
 292             bucket_count_(x.min_buckets_for_size(x.size_)),
 293             size_(0),
 294             mlf_(x.mlf_),
 295             max_load_(0),
 296             buckets_()
 297         {}
 298
 299         table(table& x, boost::unordered::detail::move_tag m) :
 300             functions(x, m),
 301             allocators_(x.allocators_, m),
 302             bucket_count_(x.bucket_count_),
 303             size_(x.size_),
 304             mlf_(x.mlf_),
 305             max_load_(x.max_load_),
 306             buckets_(x.buckets_)
 307         {
 308             x.buckets_ = bucket_pointer();
 309             x.size_ = 0;
 310             x.max_load_ = 0;
 311         }
 312
 313         table(table& x, node_allocator const& a,
 314                 boost::unordered::detail::move_tag m) :
 315             functions(x, m),
 316             allocators_(a, a),
 317             bucket_count_(x.bucket_count_),
 318             size_(0),
 319             mlf_(x.mlf_),
 320             max_load_(x.max_load_),
 321             buckets_()
 322         {}
 323
 324         ////////////////////////////////////////////////////////////////////////
 325         // Initialisation.
 326
 327         void init(table const& x)
 328         {
 329             if (x.size_) {
 330                 static_cast<table_impl*>(this)->copy_buckets(x);
 331             }
 332         }
 333
 334         void move_init(table& x)
 335         {
 336             if(node_alloc() == x.node_alloc()) {
 337                 move_buckets_from(x);
 338             }
 339             else if(x.size_) {
 340                 // TODO: Could pick new bucket size?
 341                 static_cast<table_impl*>(this)->move_buckets(x);
 342             }
 343         }
 344
 345         ////////////////////////////////////////////////////////////////////////
 346         // Create buckets
 347
 348         void create_buckets(std::size_t new_count)
 349         {
 350             std::size_t length = new_count + 1;
 351             bucket_pointer new_buckets = bucket_allocator_traits::allocate(
 352                     bucket_alloc(), length);
 353             bucket_pointer constructed = new_buckets;
 354
 355             BOOST_TRY {
 356                 bucket_pointer end = new_buckets
 357                     + static_cast<std::ptrdiff_t>(length);
 358                 for(; constructed != end; ++constructed) {
 359                     new ((void*) boost::addressof(*constructed)) bucket();
 360                 }
 361
 362                 if (buckets_)
 363                 {
 364                     // Copy the nodes to the new buckets, including the dummy
 365                     // node if there is one.
 366                     (new_buckets +
 367                         static_cast<std::ptrdiff_t>(new_count))->next_ =
 368                             (buckets_ + static_cast<std::ptrdiff_t>(
 369                                 bucket_count_))->next_;
 370                     destroy_buckets();
 371                 }
 372                 else if (bucket::extra_node)
 373                 {
 374                     node_constructor a(node_alloc());
 375                     a.create_node();
 376
 377                     (new_buckets +
 378                         static_cast<std::ptrdiff_t>(new_count))->next_ =
 379                             a.release();
 380                 }
 381             }
 382             BOOST_CATCH(...) {
 383                 for(bucket_pointer p = new_buckets; p != constructed; ++p) {
 384                     boost::unordered::detail::func::destroy(
 385                             boost::addressof(*p));
 386                 }
 387
 388                 bucket_allocator_traits::deallocate(bucket_alloc(),
 389                         new_buckets, length);
 390
 391                 BOOST_RETHROW;
 392             }
 393             BOOST_CATCH_END
 394
 395             bucket_count_ = new_count;
 396             buckets_ = new_buckets;
 397             recalculate_max_load();
 398         }
 399
 400         ////////////////////////////////////////////////////////////////////////
 401         // Swap and Move
 402
 403         void swap_allocators(table& other, false_type)
 404         {
 405             boost::unordered::detail::func::ignore_unused_variable_warning(other);
 406
 407             // According to 23.2.1.8, if propagate_on_container_swap is
 408             // false the behaviour is undefined unless the allocators
 409             // are equal.
 410             BOOST_ASSERT(node_alloc() == other.node_alloc());
 411         }
 412
 413         void swap_allocators(table& other, true_type)
 414         {
 415             allocators_.swap(other.allocators_);
 416         }
 417
 418         // Only swaps the allocators if propagate_on_container_swap
 419         void swap(table& x)
 420         {
 421             set_hash_functions op1(*this, x);
 422             set_hash_functions op2(x, *this);
 423
 424             // I think swap can throw if Propagate::value,
 425             // since the allocators' swap can throw. Not sure though.
 426             swap_allocators(x,
 427                 boost::unordered::detail::integral_constant<bool,
 428                     allocator_traits<node_allocator>::
 429                     propagate_on_container_swap::value>());
 430
 431             boost::swap(buckets_, x.buckets_);
 432             boost::swap(bucket_count_, x.bucket_count_);
 433             boost::swap(size_, x.size_);
 434             std::swap(mlf_, x.mlf_);
 435             std::swap(max_load_, x.max_load_);
 436             op1.commit();
 437             op2.commit();
 438         }
 439
 440         // Only call with nodes allocated with the currect allocator, or
 441         // one that is equal to it. (Can't assert because other's
 442         // allocators might have already been moved).
 443         void move_buckets_from(table& other)
 444         {
 445             BOOST_ASSERT(!buckets_);
 446             buckets_ = other.buckets_;
 447             bucket_count_ = other.bucket_count_;
 448             size_ = other.size_;
 449             other.buckets_ = bucket_pointer();
 450             other.size_ = 0;
 451             other.max_load_ = 0;
 452         }
 453
 454         ////////////////////////////////////////////////////////////////////////
 455         // Delete/destruct
 456
 457         ~table()
 458         {
 459             delete_buckets();
 460         }
 461
 462         void delete_node(link_pointer prev)
 463         {
 464             node_pointer n = static_cast<node_pointer>(prev->next_);
 465             prev->next_ = n->next_;
 466
 467             boost::unordered::detail::func::call_destroy(node_alloc(),
 468                 n->value_ptr());
 469             boost::unordered::detail::func::destroy(boost::addressof(*n));
 470             node_allocator_traits::deallocate(node_alloc(), n, 1);
 471             --size_;
 472         }
 473
 474         std::size_t delete_nodes(link_pointer prev, link_pointer end)
 475         {
 476             BOOST_ASSERT(prev->next_ != end);
 477
 478             std::size_t count = 0;
 479
 480             do {
 481                 delete_node(prev);
 482                 ++count;
 483             } while (prev->next_ != end);
 484
 485             return count;
 486         }
 487
 488         void delete_buckets()
 489         {
 490             if(buckets_) {
 491                 if (size_) delete_nodes(get_previous_start(), link_pointer());
 492
 493                 if (bucket::extra_node) {
 494                     node_pointer n = static_cast<node_pointer>(
 495                             get_bucket(bucket_count_)->next_);
 496                     boost::unordered::detail::func::destroy(
 497                             boost::addressof(*n));
 498                     node_allocator_traits::deallocate(node_alloc(), n, 1);
 499                 }
 500
 501                 destroy_buckets();
 502                 buckets_ = bucket_pointer();
 503                 max_load_ = 0;
 504             }
 505
 506             BOOST_ASSERT(!size_);
 507         }
 508
 509         void clear()
 510         {
 511             if (!size_) return;
 512
 513             delete_nodes(get_previous_start(), link_pointer());
 514             clear_buckets();
 515
 516             BOOST_ASSERT(!size_);
 517         }
 518
 519         void clear_buckets()
 520         {
 521             bucket_pointer end = get_bucket(bucket_count_);
 522             for(bucket_pointer it = buckets_; it != end; ++it)
 523             {
 524                 it->next_ = node_pointer();
 525             }
 526         }
 527
 528         void destroy_buckets()
 529         {
 530             bucket_pointer end = get_bucket(bucket_count_ + 1);
 531             for(bucket_pointer it = buckets_; it != end; ++it)
 532             {
 533                 boost::unordered::detail::func::destroy(
 534                     boost::addressof(*it));
 535             }
 536
 537             bucket_allocator_traits::deallocate(bucket_alloc(),
 538                 buckets_, bucket_count_ + 1);
 539         }
 540
 541         ////////////////////////////////////////////////////////////////////////
 542         // Fix buckets after delete
 543         //
 544
 545         std::size_t fix_bucket(std::size_t bucket_index, link_pointer prev)
 546         {
 547             link_pointer end = prev->next_;
 548             std::size_t bucket_index2 = bucket_index;
 549
 550             if (end)
 551             {
 552                 bucket_index2 = hash_to_bucket(
 553                     static_cast<node_pointer>(end)->hash_);
 554
 555                 // If begin and end are in the same bucket, then
 556                 // there's nothing to do.
 557                 if (bucket_index == bucket_index2) return bucket_index2;
 558
 559                 // Update the bucket containing end.
 560                 get_bucket(bucket_index2)->next_ = prev;
 561             }
 562
 563             // Check if this bucket is now empty.
 564             bucket_pointer this_bucket = get_bucket(bucket_index);
 565             if (this_bucket->next_ == prev)
 566                 this_bucket->next_ = link_pointer();
 567
 568             return bucket_index2;
 569         }
 570
 571         ////////////////////////////////////////////////////////////////////////
 572         // Assignment
 573
 574         void assign(table const& x)
 575         {
 576             if (this != boost::addressof(x))
 577             {
 578                 assign(x,
 579                     boost::unordered::detail::integral_constant<bool,
 580                         allocator_traits<node_allocator>::
 581                         propagate_on_container_copy_assignment::value>());
 582             }
 583         }
 584
 585         void assign(table const& x, false_type)
 586         {
 587             // Strong exception safety.
 588             set_hash_functions new_func_this(*this, x);
 589             mlf_ = x.mlf_;
 590             recalculate_max_load();
 591
 592             if (!size_ && !x.size_) {
 593                 new_func_this.commit();
 594                 return;
 595             }
 596
 597             if (x.size_ >= max_load_) {
 598                 create_buckets(min_buckets_for_size(x.size_));
 599             }
 600             else {
 601                 clear_buckets();
 602             }
 603
 604             new_func_this.commit();
 605             static_cast<table_impl*>(this)->assign_buckets(x);
 606         }
 607
 608         void assign(table const& x, true_type)
 609         {
 610             if (node_alloc() == x.node_alloc()) {
 611                 allocators_.assign(x.allocators_);
 612                 assign(x, false_type());
 613             }
 614             else {
 615                 set_hash_functions new_func_this(*this, x);
 616
 617                 // Delete everything with current allocators before assigning
 618                 // the new ones.
 619                 delete_buckets();
 620                 allocators_.assign(x.allocators_);
 621
 622                 // Copy over other data, all no throw.
 623                 new_func_this.commit();
 624                 mlf_ = x.mlf_;
 625                 bucket_count_ = min_buckets_for_size(x.size_);
 626                 max_load_ = 0;
 627
 628                 // Finally copy the elements.
 629                 if (x.size_) {
 630                     static_cast<table_impl*>(this)->copy_buckets(x);
 631                 }
 632             }
 633         }
 634
 635         void move_assign(table& x)
 636         {
 637             if (this != boost::addressof(x))
 638             {
 639                 move_assign(x,
 640                     boost::unordered::detail::integral_constant<bool,
 641                         allocator_traits<node_allocator>::
 642                         propagate_on_container_move_assignment::value>());
 643             }
 644         }
 645
 646         void move_assign(table& x, true_type)
 647         {
 648             delete_buckets();
 649             set_hash_functions new_func_this(*this, x);
 650             allocators_.move_assign(x.allocators_);
 651             // No throw from here.
 652             mlf_ = x.mlf_;
 653             max_load_ = x.max_load_;
 654             move_buckets_from(x);
 655             new_func_this.commit();
 656         }
 657
 658         void move_assign(table& x, false_type)
 659         {
 660             if (node_alloc() == x.node_alloc()) {
 661                 delete_buckets();
 662                 set_hash_functions new_func_this(*this, x);
 663                 // No throw from here.
 664                 mlf_ = x.mlf_;
 665                 max_load_ = x.max_load_;
 666                 move_buckets_from(x);
 667                 new_func_this.commit();
 668             }
 669             else {
 670                 set_hash_functions new_func_this(*this, x);
 671                 mlf_ = x.mlf_;
 672                 recalculate_max_load();
 673
 674                 if (!size_ && !x.size_) {
 675                     new_func_this.commit();
 676                     return;
 677                 }
 678
 679                 if (x.size_ >= max_load_) {
 680                     create_buckets(min_buckets_for_size(x.size_));
 681                 }
 682                 else {
 683                     clear_buckets();
 684                 }
 685
 686                 new_func_this.commit();
 687                 static_cast<table_impl*>(this)->move_assign_buckets(x);
 688             }
 689         }
 690
 691         // Accessors
 692
 693         key_type const& get_key(value_type const& x) const
 694         {
 695             return extractor::extract(x);
 696         }
 697
 698         std::size_t hash(key_type const& k) const
 699         {
 700             return policy::apply_hash(this->hash_function(), k);
 701         }
 702
 703         // Find Node
 704
 705         template <typename Key, typename Hash, typename Pred>
 706         node_pointer generic_find_node(
 707                 Key const& k,
 708                 Hash const& hf,
 709                 Pred const& eq) const
 710         {
 711             return static_cast<table_impl const*>(this)->
 712                 find_node_impl(policy::apply_hash(hf, k), k, eq);
 713         }
 714
 715         node_pointer find_node(
 716                 std::size_t key_hash,
 717                 key_type const& k) const
 718         {
 719             return static_cast<table_impl const*>(this)->
 720                 find_node_impl(key_hash, k, this->key_eq());
 721         }
 722
 723         node_pointer find_node(key_type const& k) const
 724         {
 725             return static_cast<table_impl const*>(this)->
 726                 find_node_impl(hash(k), k, this->key_eq());
 727         }
 728
 729         // Reserve and rehash
 730
 731         void reserve_for_insert(std::size_t);
 732         void rehash(std::size_t);
 733         void reserve(std::size_t);
 734     };
 735
 736     ////////////////////////////////////////////////////////////////////////////
 737     // Reserve & Rehash
 738
 739     // basic exception safety
 740     template <typename Types>
 741     inline void table<Types>::reserve_for_insert(std::size_t size)
 742     {
 743         if (!buckets_) {
 744             create_buckets((std::max)(bucket_count_,
 745                 min_buckets_for_size(size)));
 746         }
 747         // According to the standard this should be 'size >= max_load_',
 748         // but I think this is better, defect report filed.
 749         else if(size > max_load_) {
 750             std::size_t num_buckets
 751                 = min_buckets_for_size((std::max)(size,
 752                     size_ + (size_ >> 1)));
 753
 754             if (num_buckets != bucket_count_)
 755                 static_cast<table_impl*>(this)->rehash_impl(num_buckets);
 756         }
 757     }
 758
 759     // if hash function throws, basic exception safety
 760     // strong otherwise.
 761
 762     template <typename Types>
 763     inline void table<Types>::rehash(std::size_t min_buckets)
 764     {
 765         using namespace std;
 766
 767         if(!size_) {
 768             delete_buckets();
 769             bucket_count_ = policy::new_bucket_count(min_buckets);
 770         }
 771         else {
 772             min_buckets = policy::new_bucket_count((std::max)(min_buckets,
 773                 boost::unordered::detail::double_to_size(floor(
 774                     static_cast<double>(size_) /
 775                     static_cast<double>(mlf_))) + 1));
 776
 777             if(min_buckets != bucket_count_)
 778                 static_cast<table_impl*>(this)->rehash_impl(min_buckets);
 779         }
 780     }
 781
 782     template <typename Types>
 783     inline void table<Types>::reserve(std::size_t num_elements)
 784     {
 785         rehash(static_cast<std::size_t>(
 786             std::ceil(static_cast<double>(num_elements) / mlf_)));
 787     }
 788 }}}
 789
 790 #if defined(BOOST_MSVC)
 791 #pragma warning(pop)
 792 #endif
 793
 794 #endif