hash_table_impl.hpp

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

// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
// Copyright (C) 2005-2008 Daniel James
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#if BOOST_UNORDERED_EQUIVALENT_KEYS
#define BOOST_UNORDERED_TABLE hash_table_equivalent_keys
#define BOOST_UNORDERED_TABLE_DATA hash_table_data_equivalent_keys
#define BOOST_UNORDERED_ITERATOR hash_iterator_equivalent_keys
#define BOOST_UNORDERED_CONST_ITERATOR hash_const_iterator_equivalent_keys
#define BOOST_UNORDERED_LOCAL_ITERATOR hash_local_iterator_equivalent_keys
#define BOOST_UNORDERED_CONST_LOCAL_ITERATOR hash_const_local_iterator_equivalent_keys
#else
#define BOOST_UNORDERED_TABLE hash_table_unique_keys
#define BOOST_UNORDERED_TABLE_DATA hash_table_data_unique_keys
#define BOOST_UNORDERED_ITERATOR hash_iterator_unique_keys
#define BOOST_UNORDERED_CONST_ITERATOR hash_const_iterator_unique_keys
#define BOOST_UNORDERED_LOCAL_ITERATOR hash_local_iterator_unique_keys
#define BOOST_UNORDERED_CONST_LOCAL_ITERATOR hash_const_local_iterator_unique_keys
#endif

namespace boost {
    namespace unordered_detail {

        //
        // Hash Table Data
        //
        // Responsible for managing the hash buckets.

        template <typename Alloc>
        class BOOST_UNORDERED_TABLE_DATA
        {
        public:
            typedef BOOST_UNORDERED_TABLE_DATA data;

            struct node_base;
            struct node;
            struct bucket;
            typedef std::size_t size_type;
            typedef std::ptrdiff_t difference_type;

            typedef Alloc value_allocator;

            typedef BOOST_DEDUCED_TYPENAME
                boost::unordered_detail::rebind_wrap<Alloc, node>::type
                node_allocator;
            typedef BOOST_DEDUCED_TYPENAME
                boost::unordered_detail::rebind_wrap<Alloc, node_base>::type
                node_base_allocator;
            typedef BOOST_DEDUCED_TYPENAME
                boost::unordered_detail::rebind_wrap<Alloc, bucket>::type
                bucket_allocator;

            typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
            typedef BOOST_DEDUCED_TYPENAME allocator_pointer<node_allocator>::type node_ptr;
            typedef BOOST_DEDUCED_TYPENAME allocator_pointer<bucket_allocator>::type bucket_ptr;
            typedef BOOST_DEDUCED_TYPENAME allocator_reference<value_allocator>::type reference;
            typedef BOOST_DEDUCED_TYPENAME allocator_reference<bucket_allocator>::type bucket_reference;

            typedef bucket_ptr link_ptr;

            // Hash Bucket
            //
            // all no throw

            struct bucket
            {
            private:
                bucket& operator=(bucket const&);
            public:
                link_ptr next_;

                bucket() : next_()
                {
                    BOOST_UNORDERED_MSVC_RESET_PTR(next_);
                }

                bucket(bucket const& x) : next_(x.next_)
                {
                    // Only copy construct when allocating.
                    BOOST_ASSERT(!x.next_);
                }

                bool empty() const
                {
                    return !this->next_;
                }
            };

            // Hash Node
            //
            // all no throw

            struct node_base : bucket
            {
#if BOOST_UNORDERED_EQUIVALENT_KEYS
            public:
                node_base() : group_prev_()
                {
                    BOOST_UNORDERED_MSVC_RESET_PTR(group_prev_);
                }

                link_ptr group_prev_;
#endif
            };

            struct node : node_base
            {
            public:
#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
                template <typename... Args>
                node(Args&&... args)
                    : node_base(), value_(std::forward<Args>(args)...) {}
#else
                node(value_type const& v) : node_base(), value_(v) {}
#endif

                value_type value_;
            };

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

            // allocators
            //
            // Stores all the allocators that we're going to need.

            struct allocators
            {
                node_allocator node_alloc_;
                bucket_allocator bucket_alloc_;

                allocators(value_allocator const& a)
                    : node_alloc_(a), bucket_alloc_(a)
                {}

                void destroy(link_ptr ptr)
                {
                    node_ptr n(node_alloc_.address(*static_cast<node*>(&*ptr)));
                    node_alloc_.destroy(n);
                    node_alloc_.deallocate(n, 1);
                }

                void swap(allocators& x)
                {
                    unordered_detail::hash_swap(node_alloc_, x.node_alloc_);
                    unordered_detail::hash_swap(bucket_alloc_, x.bucket_alloc_);
                }

                bool operator==(allocators const& x)
                {
                    return node_alloc_ == x.node_alloc_;
                }
            };

            // node_constructor
            //
            // Used to construct nodes in an exception safe manner.

            class node_constructor
            {
                allocators& allocators_;

                node_ptr node_;
                bool node_constructed_;

            public:

                node_constructor(allocators& a)
                    : allocators_(a),
                    node_(), node_constructed_(false)
                {
                }

                ~node_constructor()
                {
                    if (node_) {
                        if (node_constructed_)
                            allocators_.node_alloc_.destroy(node_);
                        allocators_.node_alloc_.deallocate(node_, 1);
                    }
                }

                template <typename... Args>
                void construct(Args&&... args)
                {
                    BOOST_ASSERT(!node_);
                    node_constructed_ = false;

                    node_ = allocators_.node_alloc_.allocate(1);
                    allocators_.node_alloc_.construct(node_, std::forward<Args>(args)...);
                    node_constructed_ = true;
                }

                node_ptr get() const
                {
                    BOOST_ASSERT(node_);
                    return node_;
                }

                // no throw
                link_ptr release()
                {
                    node_ptr p = node_;
                    unordered_detail::reset(node_);
                    return link_ptr(allocators_.bucket_alloc_.address(*p));
                }

            private:
                node_constructor(node_constructor const&);
                node_constructor& operator=(node_constructor const&);
            };
#else

            // allocators
            //
            // Stores all the allocators that we're going to need.

            struct allocators
            {
                node_allocator node_alloc_;
                bucket_allocator bucket_alloc_;
                value_allocator value_alloc_;
                node_base_allocator node_base_alloc_;

                allocators(value_allocator const& a)
                    : node_alloc_(a), bucket_alloc_(a),
                    value_alloc_(a), node_base_alloc_(a)
                {}

                void destroy(link_ptr ptr)
                {
                    node_ptr n(node_alloc_.address(*static_cast<node*>(&*ptr)));
                    value_alloc_.destroy(value_alloc_.address(n->value_));
                    node_base_alloc_.destroy(node_base_alloc_.address(*n));
                    node_alloc_.deallocate(n, 1);
                }

                void swap(allocators& x)
                {
                    unordered_detail::hash_swap(node_alloc_, x.node_alloc_);
                    unordered_detail::hash_swap(bucket_alloc_, x.bucket_alloc_);
                    unordered_detail::hash_swap(value_alloc_, x.value_alloc_);
                    unordered_detail::hash_swap(node_base_alloc_, x.node_base_alloc_);
                }

                bool operator==(allocators const& x)
                {
                    return value_alloc_ == x.value_alloc_;
                }
            };

            // node_constructor
            //
            // Used to construct nodes in an exception safe manner.

            class node_constructor
            {
                allocators& allocators_;

                node_ptr node_;
                bool value_constructed_;
                bool node_base_constructed_;

            public:

                node_constructor(allocators& a)
                    : allocators_(a),
                    node_(), value_constructed_(false), node_base_constructed_(false)
                {
                    BOOST_UNORDERED_MSVC_RESET_PTR(node_);
                }

                ~node_constructor()
                {
                    if (node_) {
                        if (value_constructed_)
                            allocators_.value_alloc_.destroy(
                                allocators_.value_alloc_.address(node_->value_));
                        if (node_base_constructed_)
                            allocators_.node_base_alloc_.destroy(
                                allocators_.node_base_alloc_.address(*node_));

                        allocators_.node_alloc_.deallocate(node_, 1);
                    }
                }

                template <typename V>
                void construct(V const& v)
                {
                    BOOST_ASSERT(!node_);
                    value_constructed_ = false;
                    node_base_constructed_ = false;

                    node_ = allocators_.node_alloc_.allocate(1);

                    allocators_.node_base_alloc_.construct(
                            allocators_.node_base_alloc_.address(*node_),
                            node_base());
                    node_base_constructed_ = true;

                    allocators_.value_alloc_.construct(
                            allocators_.value_alloc_.address(node_->value_), v);
                    value_constructed_ = true;
                }

                node_ptr get() const
                {
                    BOOST_ASSERT(node_);
                    return node_;
                }

                // no throw
                link_ptr release()
                {
                    node_ptr p = node_;
                    unordered_detail::reset(node_);
                    return link_ptr(allocators_.bucket_alloc_.address(*p));
                }

            private:
                node_constructor(node_constructor const&);
                node_constructor& operator=(node_constructor const&);
            };
#endif

            // Methods for navigating groups of elements with equal keys.

#if BOOST_UNORDERED_EQUIVALENT_KEYS
            static inline link_ptr& prev_in_group(link_ptr n) {
                return static_cast<node*>(&*n)->group_prev_;
            }

            // pre: Must be pointing to the first node in a group.
            static inline link_ptr& next_group(link_ptr n) {
                BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
                return prev_in_group(n)->next_;
            }
#else
            static inline link_ptr& next_group(link_ptr n) {
                BOOST_ASSERT(n);
                return n->next_;
            }
#endif

            // pre: Must be pointing to a node
            static inline node& get_node(link_ptr p) {
                BOOST_ASSERT(p);
                return *static_cast<node*>(&*p);
            }

            // pre: Must be pointing to a node
            static inline reference get_value(link_ptr p) {
                BOOST_ASSERT(p);
                return static_cast<node*>(&*p)->value_;
            }

            class iterator_base
            {
                typedef BOOST_UNORDERED_TABLE_DATA<Alloc> data;
            public:
                bucket_ptr bucket_;
                link_ptr node_;

                iterator_base()
                    : bucket_(), node_()
                {
                    BOOST_UNORDERED_MSVC_RESET_PTR(bucket_);
                    BOOST_UNORDERED_MSVC_RESET_PTR(node_);
                }

                explicit iterator_base(bucket_ptr b)
                    : bucket_(b), node_(b->next_) {}

                iterator_base(bucket_ptr b, link_ptr n)
                    : bucket_(b), node_(n) {}