hash_table_impl.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

            BOOST_UNORDERED_TABLE(size_type n,
                    hasher const& hf, key_equal const& eq,
                    value_allocator const& a)
                : functions_(hf, eq), // throws, cleans itself up
                mlf_(1.0f),           // no throw
                data_(n, a)           // throws, cleans itself up
            {
                calculate_max_load(); // no throw
            }

            // Construct from iterators

            // initial_size
            //
            // A helper function for the copy constructor to calculate how many
            // nodes will be created if the iterator's support it. Might get it
            // totally wrong for containers with unique keys.
            //
            // no throw

            template <typename I>
            size_type initial_size(I i, I j, size_type n,
                    boost::forward_traversal_tag)
            {
                // max load factor isn't set yet, but when it is, it'll be 1.0.
                return (std::max)(static_cast<size_type>(unordered_detail::distance(i, j)) + 1, n);
            }

            template <typename I>
            size_type initial_size(I, I, size_type n,
                    boost::incrementable_traversal_tag)
            {
                return n;
            }

            template <typename I>
            size_type initial_size(I i, I j, size_type n)
            {
                BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
                    iterator_traversal_tag;
                return initial_size(i, j, n, iterator_traversal_tag);
            }

            template <typename I>
            BOOST_UNORDERED_TABLE(I i, I j, size_type n,
                    hasher const& hf, key_equal const& eq,
                    value_allocator const& a)
                : functions_(hf, eq),              // throws, cleans itself up
                  mlf_(1.0f),                      // no throw
                  data_(initial_size(i, j, n), a)  // throws, cleans itself up
            {
                calculate_max_load(); // no throw

                // This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean up.
                insert_range(i, j);
            }

            // Copy Construct

            BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE const& x)
                : functions_(x.functions_), // throws
                  mlf_(x.mlf_),             // no throw
                  data_(x.data_, x.min_buckets_for_size(x.size()))  // throws
            {
                calculate_max_load(); // no throw

                // This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean
                // up.
                copy_buckets(x.data_, data_, functions_.current());
            }

            // Copy Construct with allocator

            BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE const& x,
                    value_allocator const& a)
                : functions_(x.functions_), // throws
                mlf_(x.mlf_),               // no throw
                data_(x.min_buckets_for_size(x.size()), a)
            {
                calculate_max_load(); // no throw

                // This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean
                // up.
                copy_buckets(x.data_, data_, functions_.current());
            }

            // Move Construct

            BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE& x, move_tag m)
                : functions_(x.functions_), // throws
                  mlf_(x.mlf_),             // no throw
                  data_(x.data_, m)         // throws
            {
                calculate_max_load(); // no throw
            }

            BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE& x,
                    value_allocator const& a, move_tag m)
                : functions_(x.functions_), // throws
                  mlf_(x.mlf_),             // no throw
                  data_(x.data_, a,
                        x.min_buckets_for_size(x.size()), m)  // throws
            {
                calculate_max_load(); // no throw

                if(x.data_.buckets_) {
                    // This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean
                    // up.
                    copy_buckets(x.data_, data_, functions_.current());
                }
            }

            // Assign
            //
            // basic exception safety, if buffered_functions::buffer or reserver throws
            // the container is left in a sane, empty state. If copy_buckets
            // throws the container is left with whatever was successfully
            // copied.

            BOOST_UNORDERED_TABLE& operator=(BOOST_UNORDERED_TABLE const& x)
            {
                if(this != &x)
                {
                    data_.clear();                        // no throw
                    functions_.set(functions_.buffer(x.functions_));
                                                          // throws, strong
                    mlf_ = x.mlf_;                        // no throw
                    calculate_max_load();                 // no throw
                    reserve(x.size());                    // throws
                    copy_buckets(x.data_, data_, functions_.current()); // throws
                }

                return *this;
            }

            // Swap
            //
            // Swap's behaviour when allocators aren't equal is in dispute, for
            // details see:
            //
            // http://unordered.nfshost.com/doc/html/unordered/rationale.html#swapping_containers_with_unequal_allocators
            //
            // ----------------------------------------------------------------
            //
            // Strong exception safety (might change unused function objects)
            //
            // Can throw if hash or predicate object's copy constructor throws
            // or if allocators are unequal.

            void swap(BOOST_UNORDERED_TABLE& x)
            {
                // The swap code can work when swapping a container with itself
                // but it triggers an assertion in buffered_functions.
                // At the moment, I'd rather leave that assertion in and add a
                // check here, rather than remove the assertion. I might change
                // this at a later date.
                if(this == &x) return;

                // These can throw, but they only affect the function objects
                // that aren't in use so it is strongly exception safe, via.
                // double buffering.
                functions_ptr new_func_this = functions_.buffer(x.functions_);
                functions_ptr new_func_that = x.functions_.buffer(functions_);

                if(data_.allocators_ == x.data_.allocators_) {
                    data_.swap(x.data_); // no throw
                }
                else {
                    // Create new buckets in separate HASH_TABLE_DATA objects
                    // which will clean up if anything throws an exception.
                    // (all can throw, but with no effect as these are new objects).
                    data new_this(data_, x.min_buckets_for_size(x.data_.size_));
                    copy_buckets(x.data_, new_this, functions_.*new_func_this);

                    data new_that(x.data_, min_buckets_for_size(data_.size_));
                    x.copy_buckets(data_, new_that, x.functions_.*new_func_that);

                    // Start updating the data here, no throw from now on.
                    data_.swap(new_this);
                    x.data_.swap(new_that);
                }

                // We've made it, the rest is no throw.
                std::swap(mlf_, x.mlf_);

                functions_.set(new_func_this);
                x.functions_.set(new_func_that);

                calculate_max_load();
                x.calculate_max_load();
            }

            // Move
            //
            // ----------------------------------------------------------------
            //
            // Strong exception safety (might change unused function objects)
            //
            // Can throw if hash or predicate object's copy constructor throws
            // or if allocators are unequal.

            void move(BOOST_UNORDERED_TABLE& x)
            {
                // This can throw, but it only affects the function objects
                // that aren't in use so it is strongly exception safe, via.
                // double buffering.
                functions_ptr new_func_this = functions_.buffer(x.functions_);

                if(data_.allocators_ == x.data_.allocators_) {
                    data_.move(x.data_); // no throw
                }
                else {
                    // Create new buckets in separate HASH_TABLE_DATA objects
                    // which will clean up if anything throws an exception.
                    // (all can throw, but with no effect as these are new objects).
                    data new_this(data_, x.min_buckets_for_size(x.data_.size_));
                    copy_buckets(x.data_, new_this, functions_.*new_func_this);

                    // Start updating the data here, no throw from now on.
                    data_.move(new_this);
                }

                // We've made it, the rest is no throw.
                mlf_ = x.mlf_;
                functions_.set(new_func_this);
                calculate_max_load();
            }

            // accessors

            // no throw
#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
            node_allocator get_allocator() const
            {
                return data_.allocators_.node_alloc_;
            }
#else
            value_allocator get_allocator() const
            {
                return data_.allocators_.value_alloc_;
            }
#endif

            // no throw
            hasher const& hash_function() const
            {
                return functions_.current().hash_function();
            }

            // no throw
            key_equal const& key_eq() const
            {
                return functions_.current().key_eq();
            }

            // no throw
            size_type size() const
            {
                return data_.size_;
            }

            // no throw
            bool empty() const
            {
                return data_.size_ == 0;
            }

            // no throw
            size_type max_size() const
            {
                using namespace std;

                // size < mlf_ * count
                return double_to_size_t(ceil(
                        (double) mlf_ * max_bucket_count())) - 1;
            }

            // strong safety
            size_type bucket(key_type const& k) const
            {
                // hash_function can throw:
                return data_.bucket_from_hash(hash_function()(k));
            }


            // strong safety
            bucket_ptr get_bucket(key_type const& k) const
            {
                return data_.buckets_ + static_cast<difference_type>(bucket(k));
            }

            // no throw
            size_type bucket_count() const
            {
                return data_.bucket_manager_.bucket_count();
            }

            // no throw
            size_type max_bucket_count() const
            {
                // -1 to account for the end marker.
                return prev_prime(data_.allocators_.bucket_alloc_.max_size() - 1);
            }

        private:

            // no throw
            size_type min_buckets_for_size(size_type n) const
            {
                BOOST_ASSERT(mlf_ != 0);

                using namespace std;

                // From 6.3.1/13:
                // size < mlf_ * count
                // => count > size / mlf_
                //
                // Or from rehash post-condition:
                // count > size / mlf_
                return double_to_size_t(floor(n / (double) mlf_)) + 1;
            }

            // no throw
            void calculate_max_load()
            {
                using namespace std;

                // From 6.3.1/13:
                // Only resize when size >= mlf_ * count
                max_load_ = double_to_size_t(ceil(
                        (double) mlf_ * data_.bucket_manager_.bucket_count()));
            }

            // basic exception safety
            bool reserve(size_type n)
            {
                bool need_to_reserve = n >= max_load_;
                // throws - basic:
                if (need_to_reserve) rehash_impl(min_buckets_for_size(n));
                BOOST_ASSERT(n < max_load_ || n > max_size());
                return need_to_reserve;
            }

        public:

            // no throw
            float max_load_factor() const
            {
                return mlf_;
            }

            // no throw
            void max_load_factor(float z)
            {
                BOOST_ASSERT(z > 0);
                mlf_ = (std::max)(z, minimum_max_load_factor);
                calculate_max_load();
            }

            // no throw
            float load_factor() const
            {
                BOOST_ASSERT(data_.bucket_manager_.bucket_count() != 0);
                return static_cast<float>(data_.size_)
                    / static_cast<float>(data_.bucket_manager_.bucket_count());
            }

            // key extractors

            // no throw
            static key_type const& extract_key(value_type const& v)
            {
                return extract(v, (type_wrapper<value_type>*)0);
            }

            static key_type const& extract(value_type const& v,