Changeset 44703


Ignore:
Timestamp:
Apr 21, 2008, 7:19:50 PM (10 years ago)
Author:
Daniel James
Message:

Merge latest changes from trunk.

Merged revisions 44616-44702 via svnmerge from
https://svn.boost.org/svn/boost/trunk

........

r44650 | danieljames | 2008-04-20 22:08:57 +0100 (Sun, 20 Apr 2008) | 1 line


Update an include.

........

r44697 | danieljames | 2008-04-21 16:55:40 +0100 (Mon, 21 Apr 2008) | 1 line


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:
branches/unordered/trunk
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/unordered/trunk

  • branches/unordered/trunk/boost/unordered/detail/hash_table.hpp

    r44512 r44703  
    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.
  • branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp

    r44616 r44703  
    438438            allocators allocators_;
    439439            bucket_ptr buckets_;
    440             size_type bucket_count_;
     440            bucket_manager bucket_manager_;
    441441            bucket_ptr cached_begin_bucket_;
    442             size_type size_;
     442            size_type size_;           
    443443
    444444            // Constructors/Deconstructor
     
    446446            BOOST_UNORDERED_TABLE_DATA(size_type n, value_allocator const& a)
    447447              : allocators_(a),
    448                 buckets_(), bucket_count_(next_prime(n)),
     448                buckets_(), bucket_manager_(n),
    449449                cached_begin_bucket_(), size_(0)
    450450            {
     
    455455            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const& x, size_type n)
    456456              : allocators_(x.allocators_),
    457                 buckets_(), bucket_count_(next_prime(n)),
     457                buckets_(), bucket_manager_(n),
    458458                cached_begin_bucket_(), size_(0)
    459459            {
     
    464464            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x, move_tag)
    465465                : allocators_(x.allocators_),
    466                 buckets_(x.buckets_), bucket_count_(x.bucket_count_),
     466                buckets_(x.buckets_), bucket_manager_(x.bucket_manager_),
    467467                cached_begin_bucket_(x.cached_begin_bucket_), size_(x.size_)
    468468            {
     
    472472            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x,
    473473                    value_allocator const& a, size_type n, move_tag)
    474                 : allocators_(a), buckets_(), bucket_count_(),
     474                : allocators_(a), buckets_(), bucket_manager_(),
    475475                cached_begin_bucket_(), size_(0)
    476476            {
    477477                if(allocators_ == x.allocators_) {
    478478                    buckets_ = x.buckets_;
    479                     bucket_count_ = x.bucket_count_;
     479                    bucket_manager_ = x.bucket_manager_;
    480480                    cached_begin_bucket_ = x.cached_begin_bucket_;
    481481                    size_ = x.size_;
     
    484484                else {
    485485                    BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
    486                     bucket_count_ = next_prime(n);
     486                    bucket_manager_ = bucket_manager(n);
    487487                    create_buckets();
    488488                }
     
    496496
    497497            void create_buckets() {
     498                size_type bucket_count = bucket_manager_.bucket_count();
     499           
    498500                // The array constructor will clean up in the event of an
    499501                // exception.
     
    502504
    503505                // Creates an extra bucket to act as a sentinel.
    504                 constructor.construct(bucket(), bucket_count_ + 1);
    505 
    506                 cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count_);
     506                constructor.construct(bucket(), bucket_count + 1);
     507
     508                cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count);
    507509
    508510                // Set up the sentinel.
     
    530532                        allocators_.bucket_alloc_.destroy(begin);
    531533
    532                     allocators_.bucket_alloc_.deallocate(buckets_, bucket_count_ + 1);
     534                    allocators_.bucket_alloc_.deallocate(buckets_,
     535                        bucket_manager_.bucket_count() + 1);
    533536                }
    534537            }
     
    545548            {
    546549                std::swap(buckets_, other.buckets_);
    547                 std::swap(bucket_count_, other.bucket_count_);
     550                std::swap(bucket_manager_, other.bucket_manager_);
    548551                std::swap(cached_begin_bucket_, other.cached_begin_bucket_);
    549552                std::swap(size_, other.size_);
     
    556559                buckets_ = other.buckets_;
    557560                unordered_detail::reset(other.buckets_);
    558                 bucket_count_ = other.bucket_count_;
     561                bucket_manager_ = other.bucket_manager_;
    559562                cached_begin_bucket_ = other.cached_begin_bucket_;
    560563                size_ = other.size_;
    561564            }
    562565
     566            // Return the bucket number for a hashed value.
     567            //
     568            // no throw
     569            size_type bucket_from_hash(size_type hashed) const
     570            {
     571                return bucket_manager_.bucket_from_hash(hashed);
     572            }
     573
    563574            // Return the bucket for a hashed value.
    564575            //
    565576            // no throw
    566             bucket_ptr bucket_from_hash(size_type hashed) const
    567             {
    568                 return buckets_ + static_cast<difference_type>(hashed % bucket_count_);
     577            bucket_ptr bucket_ptr_from_hash(size_type hashed) const
     578            {
     579                return buckets_ + static_cast<difference_type>(
     580                    bucket_manager_.bucket_from_hash(hashed));
    569581            }
    570582
     
    575587            bucket_ptr buckets_end() const
    576588            {
    577                 return buckets_ + static_cast<difference_type>(bucket_count_);
     589                return buckets_ + static_cast<difference_type>(bucket_manager_.bucket_count());
    578590            }
    579591
     
    14081420            {
    14091421                // hash_function can throw:
    1410                 return hash_function()(k) % data_.bucket_count_;
     1422                return data_.bucket_from_hash(hash_function()(k));
    14111423            }
    14121424
     
    14211433            size_type bucket_count() const
    14221434            {
    1423                 return data_.bucket_count_;
     1435                return data_.bucket_manager_.bucket_count();
    14241436            }
    14251437
     
    14571469                // Only resize when size >= mlf_ * count
    14581470                max_load_ = double_to_size_t(ceil(
    1459                         (double) mlf_ * data_.bucket_count_));
     1471                        (double) mlf_ * data_.bucket_manager_.bucket_count()));
    14601472            }
    14611473
     
    15091521            float load_factor() const
    15101522            {
    1511                 BOOST_ASSERT(data_.bucket_count_ != 0);
     1523                BOOST_ASSERT(data_.bucket_manager_.bucket_count() != 0);
    15121524                return static_cast<float>(data_.size_)
    1513                     / static_cast<float>(data_.bucket_count_);
     1525                    / static_cast<float>(data_.bucket_manager_.bucket_count());
    15141526            }
    15151527
     
    15911603
    15921604                        // This next line throws iff the hash function throws.
    1593                         bucket_ptr dst_bucket = dst.bucket_from_hash(
     1605                        bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
    15941606                                hf(extract_key(data::get_value(src_bucket->next_))));
    15951607
     
    16171629                            BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it)) {
    16181630                        // hash function can throw.
    1619                         bucket_ptr dst_bucket = dst.bucket_from_hash(
     1631                        bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
    16201632                                hf(extract_key(data::get_value(it))));
    16211633                        // throws, strong
     
    17011713                key_type const& k = extract_key(a.get()->value_);
    17021714                size_type hash_value = hash_function()(k);
    1703                 bucket_ptr bucket = data_.bucket_from_hash(hash_value);
     1715                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
    17041716                link_ptr position = find_iterator(bucket, k);
    17051717
     
    17071719                // throws, strong otherwise.
    17081720                if(reserve(size() + 1))
    1709                     bucket = data_.bucket_from_hash(hash_value);
     1721                    bucket = data_.bucket_ptr_from_hash(hash_value);
    17101722
    17111723                // I'm relying on link_ptr not being invalidated by
     
    18111823
    18121824                size_type hash_value = hash_function()(k);
    1813                 bucket_ptr bucket = data_.bucket_from_hash(hash_value);
     1825                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
    18141826                link_ptr pos = find_iterator(bucket, k);
    18151827
     
    18281840                    // throws, strong otherwise.
    18291841                    if(reserve(size() + 1))
    1830                         bucket = data_.bucket_from_hash(hash_value);
     1842                        bucket = data_.bucket_ptr_from_hash(hash_value);
    18311843
    18321844                    // Nothing after this point can throw.
     
    18451857                key_type const& k = extract_key(v);
    18461858                size_type hash_value = hash_function()(k);
    1847                 bucket_ptr bucket = data_.bucket_from_hash(hash_value);
     1859                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
    18481860                link_ptr pos = find_iterator(bucket, k);
    18491861
     
    18651877                    // throws, strong otherwise.
    18661878                    if(reserve(size() + 1))
    1867                         bucket = data_.bucket_from_hash(hash_value);
     1879                        bucket = data_.bucket_ptr_from_hash(hash_value);
    18681880
    18691881                    // Nothing after this point can throw.
     
    19091921                key_type const& k = extract_key(a.get()->value_);
    19101922                size_type hash_value = hash_function()(k);
    1911                 bucket_ptr bucket = data_.bucket_from_hash(hash_value);
     1923                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
    19121924                link_ptr pos = find_iterator(bucket, k);
    19131925               
     
    19201932                    // throws, strong otherwise.
    19211933                    if(reserve(size() + 1))
    1922                         bucket = data_.bucket_from_hash(hash_value);
     1934                        bucket = data_.bucket_ptr_from_hash(hash_value);
    19231935
    19241936                    // Nothing after this point can throw.
     
    19741986                    // No side effects in this initial code
    19751987                    size_type hash_value = hash_function()(extract_key(*i));
    1976                     bucket_ptr bucket = data_.bucket_from_hash(hash_value);
     1988                    bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
    19771989                    link_ptr pos = find_iterator(bucket, extract_key(*i));
    19781990
     
    19892001                        if(size() + 1 >= max_load_) {
    19902002                            reserve(size() + insert_size(i, j));
    1991                             bucket = data_.bucket_from_hash(hash_value);
     2003                            bucket = data_.bucket_ptr_from_hash(hash_value);
    19922004                        }
    19932005
     
    22672279#undef BOOST_UNORDERED_LOCAL_ITERATOR
    22682280#undef BOOST_UNORDERED_CONST_LOCAL_ITERATOR
    2269 
  • branches/unordered/trunk/libs/unordered/test/objects/memory.hpp

    r44420 r44703  
    1111#include <boost/mpl/apply.hpp>
    1212#include <boost/assert.hpp>
    13 #include <boost/unordered/detail/allocator.hpp>
     13#include <boost/unordered/detail/allocator_helpers.hpp>
    1414#include <boost/mpl/aux_/config/eti.hpp>
    1515#include "../helpers/test.hpp"
Note: See TracChangeset for help on using the changeset viewer.