Changeset 44697


Ignore:
Timestamp:
Apr 21, 2008, 3:55:40 PM (10 years ago)
Author:
Daniel James
Message:

Factor out the code for choosing the bucket count, and which bucket that hash values map to make it easier to experiment with alternative policies.

Location:
trunk/boost/unordered/detail
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/boost/unordered/detail/hash_table.hpp

    r44614 r44697  
    5151        static const std::size_t default_initial_bucket_count = 50;
    5252        static const float minimum_max_load_factor = 1e-3f;
    53         inline std::size_t next_prime(std::size_t n);
    5453
    5554        template <class T>
     
    102101            return *bound;
    103102        }
     103       
     104        // Controls how many buckets are allocated and which buckets hash
     105        // values map to. Does not contain the buckets themselves, or ever
     106        // deal with them directly.
     107
     108        struct bucket_manager {
     109            std::size_t bucket_count_;
     110           
     111            bucket_manager()
     112                : bucket_count_(0) {}
     113           
     114            explicit bucket_manager(std::size_t n)
     115                : bucket_count_(next_prime(n)) {}
     116           
     117            std::size_t bucket_count() const {
     118                return bucket_count_;
     119            }
     120           
     121            std::size_t bucket_from_hash(std::size_t hashed) const {
     122                return hashed % bucket_count_;
     123            }
     124           
     125            std::size_t max_bucket_count(std::size_t max_size) const {
     126                return prev_prime(max_size);
     127            }
     128        };
    104129
    105130        // pair_cast - used to convert between pair types.
  • trunk/boost/unordered/detail/hash_table_impl.hpp

    r44614 r44697  
    313313            allocators allocators_;
    314314            bucket_ptr buckets_;
    315             size_type bucket_count_;
     315            bucket_manager bucket_manager_;
    316316            bucket_ptr cached_begin_bucket_;
    317             size_type size_;
     317            size_type size_;           
    318318
    319319            // Constructors/Deconstructor
     
    321321            BOOST_UNORDERED_TABLE_DATA(size_type n, value_allocator const& a)
    322322              : allocators_(a),
    323                 buckets_(), bucket_count_(next_prime(n)),
     323                buckets_(), bucket_manager_(n),
    324324                cached_begin_bucket_(), size_(0)
    325325            {
     
    330330            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const& x, size_type n)
    331331              : allocators_(x.allocators_),
    332                 buckets_(), bucket_count_(next_prime(n)),
     332                buckets_(), bucket_manager_(n),
    333333                cached_begin_bucket_(), size_(0)
    334334            {
     
    339339            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x, move_tag)
    340340                : allocators_(x.allocators_),
    341                 buckets_(x.buckets_), bucket_count_(x.bucket_count_),
     341                buckets_(x.buckets_), bucket_manager_(x.bucket_manager_),
    342342                cached_begin_bucket_(x.cached_begin_bucket_), size_(x.size_)
    343343            {
     
    347347            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x,
    348348                    value_allocator const& a, size_type n, move_tag)
    349                 : allocators_(a), buckets_(), bucket_count_(),
     349                : allocators_(a), buckets_(), bucket_manager_(),
    350350                cached_begin_bucket_(), size_(0)
    351351            {
    352352                if(allocators_ == x.allocators_) {
    353353                    buckets_ = x.buckets_;
    354                     bucket_count_ = x.bucket_count_;
     354                    bucket_manager_ = x.bucket_manager_;
    355355                    cached_begin_bucket_ = x.cached_begin_bucket_;
    356356                    size_ = x.size_;
     
    359359                else {
    360360                    BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
    361                     bucket_count_ = next_prime(n);
     361                    bucket_manager_ = bucket_manager(n);
    362362                    create_buckets();
    363363                }
     
    371371
    372372            void create_buckets() {
     373                size_type bucket_count = bucket_manager_.bucket_count();
     374           
    373375                // The array constructor will clean up in the event of an
    374376                // exception.
     
    377379
    378380                // Creates an extra bucket to act as a sentinel.
    379                 constructor.construct(bucket(), bucket_count_ + 1);
    380 
    381                 cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count_);
     381                constructor.construct(bucket(), bucket_count + 1);
     382
     383                cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count);
    382384
    383385                // Set up the sentinel.
     
    405407                        allocators_.bucket_alloc_.destroy(begin);
    406408
    407                     allocators_.bucket_alloc_.deallocate(buckets_, bucket_count_ + 1);
     409                    allocators_.bucket_alloc_.deallocate(buckets_,
     410                        bucket_manager_.bucket_count() + 1);
    408411                }
    409412            }
     
    420423            {
    421424                std::swap(buckets_, other.buckets_);
    422                 std::swap(bucket_count_, other.bucket_count_);
     425                std::swap(bucket_manager_, other.bucket_manager_);
    423426                std::swap(cached_begin_bucket_, other.cached_begin_bucket_);
    424427                std::swap(size_, other.size_);
     
    431434                buckets_ = other.buckets_;
    432435                unordered_detail::reset(other.buckets_);
    433                 bucket_count_ = other.bucket_count_;
     436                bucket_manager_ = other.bucket_manager_;
    434437                cached_begin_bucket_ = other.cached_begin_bucket_;
    435438                size_ = other.size_;
    436439            }
    437440
     441            // Return the bucket number for a hashed value.
     442            //
     443            // no throw
     444            size_type bucket_from_hash(size_type hashed) const
     445            {
     446                return bucket_manager_.bucket_from_hash(hashed);
     447            }
     448
    438449            // Return the bucket for a hashed value.
    439450            //
    440451            // no throw
    441             bucket_ptr bucket_from_hash(size_type hashed) const
    442             {
    443                 return buckets_ + static_cast<difference_type>(hashed % bucket_count_);
     452            bucket_ptr bucket_ptr_from_hash(size_type hashed) const
     453            {
     454                return buckets_ + static_cast<difference_type>(
     455                    bucket_manager_.bucket_from_hash(hashed));
    444456            }
    445457
     
    450462            bucket_ptr buckets_end() const
    451463            {
    452                 return buckets_ + static_cast<difference_type>(bucket_count_);
     464                return buckets_ + static_cast<difference_type>(bucket_manager_.bucket_count());
    453465            }
    454466
     
    12831295            {
    12841296                // hash_function can throw:
    1285                 return hash_function()(k) % data_.bucket_count_;
     1297                return data_.bucket_from_hash(hash_function()(k));
    12861298            }
    12871299
     
    12961308            size_type bucket_count() const
    12971309            {
    1298                 return data_.bucket_count_;
     1310                return data_.bucket_manager_.bucket_count();
    12991311            }
    13001312
     
    13321344                // Only resize when size >= mlf_ * count
    13331345                max_load_ = double_to_size_t(ceil(
    1334                         (double) mlf_ * data_.bucket_count_));
     1346                        (double) mlf_ * data_.bucket_manager_.bucket_count()));
    13351347            }
    13361348
     
    13841396            float load_factor() const
    13851397            {
    1386                 BOOST_ASSERT(data_.bucket_count_ != 0);
     1398                BOOST_ASSERT(data_.bucket_manager_.bucket_count() != 0);
    13871399                return static_cast<float>(data_.size_)
    1388                     / static_cast<float>(data_.bucket_count_);
     1400                    / static_cast<float>(data_.bucket_manager_.bucket_count());
    13891401            }
    13901402
     
    14661478
    14671479                        // This next line throws iff the hash function throws.
    1468                         bucket_ptr dst_bucket = dst.bucket_from_hash(
     1480                        bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
    14691481                                hf(extract_key(data::get_value(src_bucket->next_))));
    14701482
     
    14921504                            BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it)) {
    14931505                        // hash function can throw.
    1494                         bucket_ptr dst_bucket = dst.bucket_from_hash(
     1506                        bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
    14951507                                hf(extract_key(data::get_value(it))));
    14961508                        // throws, strong
     
    15171529                key_type const& k = extract_key(v);
    15181530                size_type hash_value = hash_function()(k);
    1519                 bucket_ptr bucket = data_.bucket_from_hash(hash_value);
     1531                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
    15201532                link_ptr position = find_iterator(bucket, k);
    15211533
     
    15281540                // throws, strong otherwise.
    15291541                if(reserve(size() + 1))
    1530                     bucket = data_.bucket_from_hash(hash_value);
     1542                    bucket = data_.bucket_ptr_from_hash(hash_value);
    15311543
    15321544                // I'm relying on link_ptr not being invalidated by
     
    16411653
    16421654                size_type hash_value = hash_function()(k);
    1643                 bucket_ptr bucket = data_.bucket_from_hash(hash_value);
     1655                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
    16441656                link_ptr pos = find_iterator(bucket, k);
    16451657
     
    16581670                    // throws, strong otherwise.
    16591671                    if(reserve(size() + 1))
    1660                         bucket = data_.bucket_from_hash(hash_value);
     1672                        bucket = data_.bucket_ptr_from_hash(hash_value);
    16611673
    16621674                    // Nothing after this point can throw.
     
    16751687                key_type const& k = extract_key(v);
    16761688                size_type hash_value = hash_function()(k);
    1677                 bucket_ptr bucket = data_.bucket_from_hash(hash_value);
     1689                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
    16781690                link_ptr pos = find_iterator(bucket, k);
    16791691
     
    16951707                    // throws, strong otherwise.
    16961708                    if(reserve(size() + 1))
    1697                         bucket = data_.bucket_from_hash(hash_value);
     1709                        bucket = data_.bucket_ptr_from_hash(hash_value);
    16981710
    16991711                    // Nothing after this point can throw.
     
    17501762                    // No side effects in this initial code
    17511763                    size_type hash_value = hash_function()(extract_key(*i));
    1752                     bucket_ptr bucket = data_.bucket_from_hash(hash_value);
     1764                    bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
    17531765                    link_ptr pos = find_iterator(bucket, extract_key(*i));
    17541766
     
    17651777                        if(size() + 1 >= max_load_) {
    17661778                            reserve(size() + insert_size(i, j));
    1767                             bucket = data_.bucket_from_hash(hash_value);
     1779                            bucket = data_.bucket_ptr_from_hash(hash_value);
    17681780                        }
    17691781
     
    20432055#undef BOOST_UNORDERED_LOCAL_ITERATOR
    20442056#undef BOOST_UNORDERED_CONST_LOCAL_ITERATOR
    2045 
Note: See TracChangeset for help on using the changeset viewer.