hash_table_impl.hpp

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

                    type_wrapper<key_type>*)
            {
                return v;
            }

            static key_type const& extract(value_type const& v,
                    void*)
            {
                return v.first;
            }

#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
            struct no_key {};

            template <typename Arg1, typename... Args>
            static typename boost::enable_if<
                boost::mpl::and_<
                    boost::mpl::not_<boost::is_same<key_type, value_type> >,
                    boost::is_same<Arg1, key_type>
                >,
                key_type>::type const& extract_key(Arg1 const& k, Args const&...)
            {
                return k;
            }

            template <typename First, typename Second>
            static typename boost::enable_if<
                boost::mpl::and_<
                    boost::mpl::not_<boost::is_same<key_type, value_type> >,
                    boost::is_same<key_type,
                        typename boost::remove_const<
                            typename boost::remove_reference<First>::type
                        >::type>
                >,
                key_type>::type const& extract_key(std::pair<First, Second> const& v)
            {
                return v.first;
            }

            template <typename... Args>
            static no_key extract_key(Args const&...)
            {
                return no_key();
            }
#endif

        public:

            // if hash function throws, basic exception safety
            // strong otherwise.
            void rehash(size_type n)
            {
                using namespace std;

                // no throw:
                size_type min_size = min_buckets_for_size(size());
                // basic/strong:
                rehash_impl(min_size > n ? min_size : n);

                BOOST_ASSERT((float) bucket_count() > (float) size() / max_load_factor()
                        && bucket_count() >= n);
            }

        private:

            // if hash function throws, basic exception safety
            // strong otherwise
            void rehash_impl(size_type n)
            {
                n = next_prime(n); // no throw

                if (n == bucket_count())  // no throw
                    return;

                data new_buckets(data_, n); // throws, seperate
                move_buckets(data_, new_buckets, hash_function());
                                                        // basic/no throw
                new_buckets.swap(data_);                // no throw
                calculate_max_load();                   // no throw
            }

            // move_buckets & copy_buckets
            //
            // if the hash function throws, basic excpetion safety
            // no throw otherwise

            static void move_buckets(data& src, data& dst, hasher const& hf)
            {
                BOOST_ASSERT(dst.size_ == 0);
                //BOOST_ASSERT(src.allocators_.node_alloc_ == dst.allocators_.node_alloc_);

                bucket_ptr end = src.buckets_end();

                for(; src.cached_begin_bucket_ != end;
                        ++src.cached_begin_bucket_) {
                    bucket_ptr src_bucket = src.cached_begin_bucket_;
                    while(src_bucket->next_) {
                        // Move the first group of equivalent nodes in
                        // src_bucket to dst.

                        // This next line throws iff the hash function throws.
                        bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
                                hf(extract_key(data::get_value(src_bucket->next_))));

                        link_ptr n = src_bucket->next_;
                        size_type count = src.unlink_group(&src_bucket->next_);
                        dst.link_group(n, dst_bucket, count);
                    }
                }
            }

            // basic excpetion safety. If an exception is thrown this will
            // leave dst partially filled.

            static void copy_buckets(data const& src, data& dst, functions const& f)
            {
                BOOST_ASSERT(dst.size_ == 0);
                // no throw:
                bucket_ptr end = src.buckets_end();
                hasher const& hf = f.hash_function();

                // no throw:
                for(bucket_ptr i = src.cached_begin_bucket_; i != end; ++i) {
                    // no throw:
                    for(link_ptr it = src.begin(i);
                            BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it)) {
                        // hash function can throw.
                        bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
                                hf(extract_key(data::get_value(it))));
                        // throws, strong
                        dst.copy_group(it, dst_bucket);
                    }
                }
            }

        public:

            // Insert functions
            //
            // basic exception safety, if hash function throws
            // strong otherwise.

#if BOOST_UNORDERED_EQUIVALENT_KEYS

#if !(defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL))
            // Insert (equivalent key containers)

            // if hash function throws, basic exception safety
            // strong otherwise
            iterator_base insert(value_type const& v)
            {
                // Create the node before rehashing in case it throws an
                // exception (need strong safety in such a case).
                node_constructor a(data_.allocators_);
                a.construct(v);

                return insert_impl(a);
            }

            // Insert (equivalent key containers)

            // if hash function throws, basic exception safety
            // strong otherwise
            iterator_base insert_hint(iterator_base const& it, value_type const& v)
            {
                // Create the node before rehashing in case it throws an
                // exception (need strong safety in such a case).
                node_constructor a(data_.allocators_);
                a.construct(v);

                return insert_hint_impl(it, a);
            }

#else

            // Insert (equivalent key containers)
            // (I'm using an overloaded insert for both 'insert' and 'emplace')

            // if hash function throws, basic exception safety
            // strong otherwise
            template <class... Args>
            iterator_base insert(Args&&... args)
            {
                // Create the node before rehashing in case it throws an
                // exception (need strong safety in such a case).
                node_constructor a(data_.allocators_);
                a.construct(std::forward<Args>(args)...);

                return insert_impl(a);
            }

            // Insert (equivalent key containers)
            // (I'm using an overloaded insert for both 'insert' and 'emplace')

            // if hash function throws, basic exception safety
            // strong otherwise
            template <class... Args>
            iterator_base insert_hint(iterator_base const& it, Args&&... args)
            {
                // Create the node before rehashing in case it throws an
                // exception (need strong safety in such a case).
                node_constructor a(data_.allocators_);
                a.construct(std::forward<Args>(args)...);

                return insert_hint_impl(it, a);
            }

#endif

            iterator_base insert_impl(node_constructor& a)
            {
                key_type const& k = extract_key(a.get()->value_);
                size_type hash_value = hash_function()(k);
                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
                link_ptr position = find_iterator(bucket, k);

                // reserve has basic exception safety if the hash function
                // throws, strong otherwise.
                if(reserve(size() + 1))
                    bucket = data_.bucket_ptr_from_hash(hash_value);

                // I'm relying on link_ptr not being invalidated by
                // the rehash here.
                return iterator_base(bucket,
                    (BOOST_UNORDERED_BORLAND_BOOL(position)) ?
                    data_.link_node(a, position) :
                    data_.link_node_in_bucket(a, bucket)
                );
            }

            iterator_base insert_hint_impl(iterator_base const& it, node_constructor& a)
            {
                // equal can throw, but with no effects
                if (it == data_.end() || !equal(extract_key(a.get()->value_), *it)) {
                    // Use the standard insert if the iterator doesn't point
                    // to a matching key.
                    return insert_impl(a);
                }
                else {
                    // Find the first node in the group - so that the node
                    // will be inserted at the end of the group.

                    link_ptr start(it.node_);
                    while(data_.prev_in_group(start)->next_ == start)
                        start = data_.prev_in_group(start);

                    // reserve has basic exception safety if the hash function
                    // throws, strong otherwise.
                    bucket_ptr base = reserve(size() + 1) ?
                        get_bucket(extract_key(a.get()->value_)) : it.bucket_;

                    // Nothing after this point can throw

                    return iterator_base(base,
                            data_.link_node(a, start));
                }
            }

            // Insert from iterator range (equivalent key containers)

        private:

            // if hash function throws, or inserting > 1 element, basic exception safety
            // strong otherwise
            template <typename I>
            void insert_for_range(I i, I j, forward_traversal_tag)
            {
                size_type distance = unordered_detail::distance(i, j);
                if(distance == 1) {
                    insert(*i);
                }
                else {
                    // Only require basic exception safety here
                    reserve(size() + distance);
                    node_constructor a(data_.allocators_);

                    for (; i != j; ++i) {
                        a.construct(*i);

                        key_type const& k = extract_key(a.get()->value_);
                        bucket_ptr bucket = get_bucket(k);
                        link_ptr position = find_iterator(bucket, k);

                        if(BOOST_UNORDERED_BORLAND_BOOL(position))
                            data_.link_node(a, position);
                        else
                            data_.link_node_in_bucket(a, bucket);
                    }
                }
            }

            // if hash function throws, or inserting > 1 element, basic exception safety
            // strong otherwise
            template <typename I>
            void insert_for_range(I i, I j,
                    boost::incrementable_traversal_tag)
            {
                // If only inserting 1 element, get the required
                // safety since insert is only called once.
                for (; i != j; ++i) insert(*i);
            }

        public:

            // if hash function throws, or inserting > 1 element, basic exception safety
            // strong otherwise
            template <typename I>
            void insert_range(I i, I j)
            {
                BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
                    iterator_traversal_tag;
                insert_for_range(i, j, iterator_traversal_tag);
            }
#else
            // if hash function throws, basic exception safety
            // strong otherwise
            value_type& operator[](key_type const& k)
            {
                BOOST_STATIC_ASSERT((
                            !boost::is_same<value_type, key_type>::value));
                typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;

                size_type hash_value = hash_function()(k);
                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
                link_ptr pos = find_iterator(bucket, k);

                if (BOOST_UNORDERED_BORLAND_BOOL(pos))
                    return data::get_value(pos);
                else
                {
                    // Side effects only in this block.

                    // Create the node before rehashing in case it throws an
                    // exception (need strong safety in such a case).
                    node_constructor a(data_.allocators_);
                    a.construct(value_type(k, mapped_type()));

                    // reserve has basic exception safety if the hash function
                    // throws, strong otherwise.
                    if(reserve(size() + 1))
                        bucket = data_.bucket_ptr_from_hash(hash_value);

                    // Nothing after this point can throw.

                    return data::get_value(data_.link_node_in_bucket(a, bucket));
                }
            }

#if !(defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL))

            // Insert (unique keys)

            // if hash function throws, basic exception safety
            // strong otherwise
            std::pair<iterator_base, bool> insert(value_type const& v)
            {
                // No side effects in this initial code
                key_type const& k = extract_key(v);
                size_type hash_value = hash_function()(k);
                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
                link_ptr pos = find_iterator(bucket, k);

                if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
                    // Found an existing key, return it (no throw).
                    return std::pair<iterator_base, bool>(
                        iterator_base(bucket, pos), false);

                } else {
                    // Doesn't already exist, add to bucket.
                    // Side effects only in this block.

                    // Create the node before rehashing in case it throws an
                    // except