hash_table_impl.hpp

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

                bool operator==(iterator_base const& x) const
                {
                    return node_ == x.node_;
                }

                bool operator!=(iterator_base const& x) const
                {
                    return node_ != x.node_;
                }

                reference operator*() const
                {
                    return get_value(node_);
                }

                void increment()
                {
                    BOOST_ASSERT(bucket_);
                    node_ = node_->next_;

                    while (!node_) {
                        ++bucket_;
                        node_ = bucket_->next_;
                    }
                }

                void increment_group()
                {
                    node_ = data::next_group(node_);

                    while (!node_) {
                        ++bucket_;
                        node_ = bucket_->next_;
                    }
                }
            };

            // Member Variables

            allocators allocators_;
            bucket_ptr buckets_;
            bucket_manager bucket_manager_;
            bucket_ptr cached_begin_bucket_;
            size_type size_;           

            // Constructors/Deconstructor

            BOOST_UNORDERED_TABLE_DATA(size_type n, value_allocator const& a)
              : allocators_(a),
                buckets_(), bucket_manager_(n),
                cached_begin_bucket_(), size_(0)
            {
                BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
                create_buckets();
            }

            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const& x, size_type n)
              : allocators_(x.allocators_),
                buckets_(), bucket_manager_(n),
                cached_begin_bucket_(), size_(0)
            {
                BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
                create_buckets();
            }

            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x, move_tag)
                : allocators_(x.allocators_),
                buckets_(x.buckets_), bucket_manager_(x.bucket_manager_),
                cached_begin_bucket_(x.cached_begin_bucket_), size_(x.size_)
            {
                unordered_detail::reset(x.buckets_);
            }

            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x,
                    value_allocator const& a, size_type n, move_tag)
                : allocators_(a), buckets_(), bucket_manager_(),
                cached_begin_bucket_(), size_(0)
            {
                if(allocators_ == x.allocators_) {
                    buckets_ = x.buckets_;
                    bucket_manager_ = x.bucket_manager_;
                    cached_begin_bucket_ = x.cached_begin_bucket_;
                    size_ = x.size_;
                    unordered_detail::reset(x.buckets_);
                }
                else {
                    BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
                    bucket_manager_ = bucket_manager(n);
                    create_buckets();
                }
            }

            // no throw
            ~BOOST_UNORDERED_TABLE_DATA()
            {
                delete_buckets();
            }

            void create_buckets() {
                size_type bucket_count = bucket_manager_.bucket_count();
            
                // The array constructor will clean up in the event of an
                // exception.
                allocator_array_constructor<bucket_allocator>
                    constructor(allocators_.bucket_alloc_);

                // Creates an extra bucket to act as a sentinel.
                constructor.construct(bucket(), bucket_count + 1);

                cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count);

                // Set up the sentinel.
                cached_begin_bucket_->next_ = link_ptr(cached_begin_bucket_);

                // Only release the buckets once everything is successfully
                // done.
                buckets_ = constructor.release();
            }

            // no throw
            void delete_buckets()
            {
                if(buckets_) {
                    bucket_ptr begin = cached_begin_bucket_;
                    bucket_ptr end = buckets_end();
                    while(begin != end) {
                        clear_bucket(begin);
                        ++begin;
                    }

                    // Destroy an extra bucket for the sentinels.
                    ++end;
                    for(begin = buckets_; begin != end; ++begin)
                        allocators_.bucket_alloc_.destroy(begin);

                    allocators_.bucket_alloc_.deallocate(buckets_,
                        bucket_manager_.bucket_count() + 1);
                }
            }

        private:

            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const&);
            BOOST_UNORDERED_TABLE_DATA& operator=(BOOST_UNORDERED_TABLE_DATA const&);

        public:

            // no throw
            void swap(BOOST_UNORDERED_TABLE_DATA& other)
            {
                std::swap(buckets_, other.buckets_);
                std::swap(bucket_manager_, other.bucket_manager_);
                std::swap(cached_begin_bucket_, other.cached_begin_bucket_);
                std::swap(size_, other.size_);
            }

            // no throw
            void move(BOOST_UNORDERED_TABLE_DATA& other)
            {
                delete_buckets();
                buckets_ = other.buckets_;
                unordered_detail::reset(other.buckets_);
                bucket_manager_ = other.bucket_manager_;
                cached_begin_bucket_ = other.cached_begin_bucket_;
                size_ = other.size_;
            }

            // Return the bucket number for a hashed value.
            //
            // no throw
            size_type bucket_from_hash(size_type hashed) const
            {
                return bucket_manager_.bucket_from_hash(hashed);
            }

            // Return the bucket for a hashed value.
            //
            // no throw
            bucket_ptr bucket_ptr_from_hash(size_type hashed) const
            {
                return buckets_ + static_cast<difference_type>(
                    bucket_manager_.bucket_from_hash(hashed));
            }

            // Begin & End
            //
            // no throw

            bucket_ptr buckets_end() const
            {
                return buckets_ + static_cast<difference_type>(bucket_manager_.bucket_count());
            }

            iterator_base begin() const
            {
                return size_
                    ? iterator_base(cached_begin_bucket_)
                    : end();
            }

            iterator_base end() const
            {
                return iterator_base(buckets_end());
            }

            link_ptr begin(size_type n) const
            {
                return (buckets_ + static_cast<difference_type>(n))->next_;
            }

            link_ptr end(size_type) const
            {
                return unordered_detail::null_ptr<link_ptr>();
            }

            link_ptr begin(bucket_ptr b) const
            {
                return b->next_;
            }

            // Bucket Size

            // no throw
            static inline size_type node_count(link_ptr it)
            {
                size_type count = 0;
                while(BOOST_UNORDERED_BORLAND_BOOL(it)) {
                    ++count;
                    it = it->next_;
                }
                return count;
            }

            static inline size_type node_count(link_ptr it1, link_ptr it2)
            {
                size_type count = 0;
                while(it1 != it2) {
                    ++count;
                    it1 = it1->next_;
                }
                return count;
            }

            size_type bucket_size(size_type n) const
            {
                return node_count(begin(n));
            }

#if BOOST_UNORDERED_EQUIVALENT_KEYS
            static inline size_type group_count(link_ptr it)
            {
                return node_count(it, next_group(it));
            }
#else
            static inline size_type group_count(link_ptr)
            {
                return 1;
            }
#endif

            // get_for_erase
            //
            // Find the pointer to a node, for use when erasing.
            //
            // no throw

#if BOOST_UNORDERED_EQUIVALENT_KEYS
            static link_ptr* get_for_erase(iterator_base r)
            {
                link_ptr n = r.node_;

                // If the element isn't the first in its group, then
                // the link to it will be found in the previous element
                // in the group.
                link_ptr* it = &prev_in_group(n)->next_;
                if(*it == n) return it;

                // The element is the first in its group, so iterate
                // throught the groups, checking against the first element.
                it = &r.bucket_->next_;
                while(*it != n) it = &BOOST_UNORDERED_TABLE_DATA::next_group(*it);
                return it;
            }
#else
            static link_ptr* get_for_erase(iterator_base r)
            {
                link_ptr n = r.node_;
                link_ptr* it = &r.bucket_->next_;
                while(*it != n) it = &(*it)->next_;
                return it;
            }
#endif

            // Link/Unlink/Move Node
            //
            // For adding nodes to buckets, removing them and moving them to a
            // new bucket.
            //
            // no throw

#if BOOST_UNORDERED_EQUIVALENT_KEYS
            // If n points to the first node in a group, this adds it to the
            // end of that group.
            link_ptr link_node(node_constructor& a, link_ptr pos)
            {
                link_ptr n = a.release();
                node& node_ref = get_node(n);
                node& pos_ref = get_node(pos);
                node_ref.next_ = pos_ref.group_prev_->next_;
                node_ref.group_prev_ = pos_ref.group_prev_;
                pos_ref.group_prev_->next_ = n;
                pos_ref.group_prev_ = n;
                ++size_;
                return n;
            }

            link_ptr link_node_in_bucket(node_constructor& a, bucket_ptr base)
            {
                link_ptr n = a.release();
                node& node_ref = get_node(n);
                node_ref.next_ = base->next_;
                node_ref.group_prev_ = n;
                base->next_ = n;
                ++size_;
                if(base < cached_begin_bucket_) cached_begin_bucket_ = base;
                return n;
            }

            void link_group(link_ptr n, bucket_ptr base, size_type count)
            {
                node& node_ref = get_node(n);
                node& last_ref = get_node(node_ref.group_prev_);
                last_ref.next_ = base->next_;
                base->next_ = n;
                size_ += count;
                if(base < cached_begin_bucket_) cached_begin_bucket_ = base;
            }
#else
            void link_node(link_ptr n, bucket_ptr base)
            {
                n->next_ = base->next_;
                base->next_ = n;
                ++size_;
                if(base < cached_begin_bucket_) cached_begin_bucket_ = base;
            }

            link_ptr link_node_in_bucket(node_constructor& a, bucket_ptr base)
            {
                link_ptr n = a.release();
                link_node(n, base);
                return n;
            }

            void link_group(link_ptr n, bucket_ptr base, size_type)
            {
                link_node(n, base);
            }
#endif

#if BOOST_UNORDERED_EQUIVALENT_KEYS
            void unlink_node(iterator_base it)
            {
                link_ptr* pos = get_for_erase(it);
                node* n = &get_node(it.node_);
                link_ptr next = n->next_;

                if(n->group_prev_ == *pos) {
                    // The deleted node is the sole node in the group, so
                    // no need to unlink it from a group.
                }
                else if(BOOST_UNORDERED_BORLAND_BOOL(next) && prev_in_group(next) == *pos)
                {
                    // The deleted node is not at the end of the group, so
                    // change the link from the next node.
                    prev_in_group(next) = n->group_prev_;