diff options
Diffstat (limited to 'boost/unordered/detail/equivalent.hpp')
| -rw-r--r-- | boost/unordered/detail/equivalent.hpp | 322 |
1 files changed, 197 insertions, 125 deletions
diff --git a/boost/unordered/detail/equivalent.hpp b/boost/unordered/detail/equivalent.hpp index 6e7e4190da..5cbf6a7cea 100644 --- a/boost/unordered/detail/equivalent.hpp +++ b/boost/unordered/detail/equivalent.hpp @@ -12,7 +12,6 @@ #endif #include <boost/unordered/detail/table.hpp> -#include <boost/unordered/detail/emplace_args.hpp> #include <boost/unordered/detail/extract_key.hpp> namespace boost { namespace unordered { namespace detail { @@ -23,25 +22,52 @@ namespace boost { namespace unordered { namespace detail { template <typename A, typename T> struct grouped_node : + boost::unordered::detail::node_base< + typename ::boost::unordered::detail::rebind_wrap< + A, grouped_node<A, T> >::type::pointer + >, boost::unordered::detail::value_base<T> { typedef typename ::boost::unordered::detail::rebind_wrap< A, grouped_node<A, T> >::type::pointer link_pointer; + typedef boost::unordered::detail::node_base<link_pointer> node_base; - link_pointer next_; link_pointer group_prev_; std::size_t hash_; +#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + explicit grouped_node(BOOST_UNORDERED_EMPLACE_ARGS) : + node_base(), + group_prev_(), + hash_(0) + { + boost::unordered::detail::construct_impl( + this->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); + } + + ~grouped_node() { + boost::unordered::detail::destroy(this->value_ptr()); + } + + grouped_node(grouped_node const&) { + assert(false); + } +#else grouped_node() : - next_(), + node_base(), group_prev_(), hash_(0) {} +#endif void init(link_pointer self) { group_prev_ = self; } + + private: + grouped_node& operator=(grouped_node const&); }; template <typename T> @@ -50,21 +76,45 @@ namespace boost { namespace unordered { namespace detail { boost::unordered::detail::ptr_bucket { typedef boost::unordered::detail::ptr_bucket bucket_base; + typedef bucket_base node_base; typedef ptr_bucket* link_pointer; link_pointer group_prev_; std::size_t hash_; +#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + explicit grouped_ptr_node(BOOST_UNORDERED_EMPLACE_ARGS) : + bucket_base(), + group_prev_(0), + hash_(0) + { + boost::unordered::detail::construct_impl( + this->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); + } + + ~grouped_ptr_node() { + boost::unordered::detail::destroy(this->value_ptr()); + } + + grouped_ptr_node(grouped_ptr_node const&) { + assert(false); + } +#else grouped_ptr_node() : bucket_base(), group_prev_(0), hash_(0) {} +#endif void init(link_pointer self) { group_prev_ = self; } + + private: + grouped_ptr_node& operator=(grouped_ptr_node const&); }; // If the allocator uses raw pointers use grouped_ptr_node @@ -136,6 +186,8 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::grouped_table_impl<types> table; typedef boost::unordered::detail::set_extractor<value_type> extractor; + + typedef boost::unordered::detail::pick_policy::type policy; }; template <typename A, typename K, typename M, typename H, typename P> @@ -160,6 +212,8 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::grouped_table_impl<types> table; typedef boost::unordered::detail::map_extractor<key_type, value_type> extractor; + + typedef boost::unordered::detail::pick_policy::type policy; }; template <typename Types> @@ -169,6 +223,7 @@ namespace boost { namespace unordered { namespace detail { typedef typename table::value_type value_type; typedef typename table::bucket bucket; typedef typename table::buckets buckets; + typedef typename table::policy policy; typedef typename table::node_pointer node_pointer; typedef typename table::node_allocator node_allocator; typedef typename table::node_allocator_traits node_allocator_traits; @@ -181,6 +236,7 @@ namespace boost { namespace unordered { namespace detail { typedef typename table::node_constructor node_constructor; typedef typename table::extractor extractor; typedef typename table::iterator iterator; + typedef typename table::c_iterator c_iterator; // Constructors @@ -214,59 +270,61 @@ namespace boost { namespace unordered { namespace detail { // Accessors template <class Key, class Pred> - node_pointer find_node_impl( - std::size_t hash, + iterator find_node_impl( + std::size_t key_hash, Key const& k, Pred const& eq) const { - std::size_t bucket_index = hash % this->bucket_count_; - node_pointer n = this->get_start(bucket_index); + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, key_hash); + iterator n = this->get_start(bucket_index); for (;;) { - if (!n) return n; + if (!n.node_) return n; - std::size_t node_hash = n->hash_; - if (hash == node_hash) + std::size_t node_hash = n.node_->hash_; + if (key_hash == node_hash) { - if (eq(k, this->get_key(n->value()))) + if (eq(k, this->get_key(*n))) return n; } else { - if (node_hash % this->bucket_count_ != bucket_index) - return node_pointer(); + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) + return iterator(); } - n = static_cast<node_pointer>( - static_cast<node_pointer>(n->group_prev_)->next_); + n = iterator(static_cast<node_pointer>( + static_cast<node_pointer>(n.node_->group_prev_)->next_)); } } std::size_t count(key_type const& k) const { - node_pointer n = this->find_node(k); - if (!n) return 0; + iterator n = this->find_node(k); + if (!n.node_) return 0; - std::size_t count = 0; - node_pointer it = n; + std::size_t x = 0; + node_pointer it = n.node_; do { it = static_cast<node_pointer>(it->group_prev_); - ++count; - } while(it != n); + ++x; + } while(it != n.node_); - return count; + return x; } std::pair<iterator, iterator> equal_range(key_type const& k) const { - node_pointer n = this->find_node(k); + iterator n = this->find_node(k); return std::make_pair( - iterator(n), iterator(n ? + n, n.node_ ? iterator( static_cast<node_pointer>( - static_cast<node_pointer>(n->group_prev_)->next_) : - n)); + static_cast<node_pointer>(n.node_->group_prev_)->next_ + )) : n); } // Equality @@ -276,14 +334,14 @@ namespace boost { namespace unordered { namespace detail { if(this->size_ != other.size_) return false; if(!this->size_) return true; - for(node_pointer n1 = this->get_start(); n1;) + for(iterator n1 = this->get_start(); n1.node_;) { - node_pointer n2 = other.find_matching_node(n1); - if (!n2) return false; - node_pointer end1 = static_cast<node_pointer>( - static_cast<node_pointer>(n1->group_prev_)->next_); - node_pointer end2 = static_cast<node_pointer>( - static_cast<node_pointer>(n2->group_prev_)->next_); + iterator n2 = other.find_matching_node(n1); + if (!n2.node_) return false; + iterator end1(static_cast<node_pointer>( + static_cast<node_pointer>(n1.node_->group_prev_)->next_)); + iterator end2(static_cast<node_pointer>( + static_cast<node_pointer>(n2.node_->group_prev_)->next_)); if (!group_equals(n1, end1, n2, end2)) return false; n1 = end1; } @@ -293,25 +351,24 @@ namespace boost { namespace unordered { namespace detail { #if !defined(BOOST_UNORDERED_DEPRECATED_EQUALITY) - static bool group_equals(node_pointer n1, node_pointer end1, - node_pointer n2, node_pointer end2) + static bool group_equals(iterator n1, iterator end1, + iterator n2, iterator end2) { for(;;) { - if (n1->value() != n2->value()) - break; + if (*n1 != *n2) break; - n1 = static_cast<node_pointer>(n1->next_); - n2 = static_cast<node_pointer>(n2->next_); + ++n1; + ++n2; if (n1 == end1) return n2 == end2; if (n2 == end2) return false; } - for(node_pointer n1a = n1, n2a = n2;;) + for(iterator n1a = n1, n2a = n2;;) { - n1a = static_cast<node_pointer>(n1a->next_); - n2a = static_cast<node_pointer>(n2a->next_); + ++n1a; + ++n2a; if (n1a == end1) { @@ -322,50 +379,50 @@ namespace boost { namespace unordered { namespace detail { if (n2a == end2) return false; } - node_pointer start = n1; - for(;n1 != end2; n1 = static_cast<node_pointer>(n1->next_)) + iterator start = n1; + for(;n1 != end1; ++n1) { - value_type const& v = n1->value(); + value_type const& v = *n1; if (find(start, n1, v)) continue; std::size_t matches = count_equal(n2, end2, v); - if (!matches || matches != 1 + count_equal( - static_cast<node_pointer>(n1->next_), end1, v)) - return false; + if (!matches) return false; + iterator next = n1; + ++next; + if (matches != 1 + count_equal(next, end1, v)) return false; } return true; } - static bool find(node_pointer n, node_pointer end, value_type const& v) + static bool find(iterator n, iterator end, value_type const& v) { - for(;n != end; n = static_cast<node_pointer>(n->next_)) - if (n->value() == v) + for(;n != end; ++n) + if (*n == v) return true; return false; } - static std::size_t count_equal(node_pointer n, node_pointer end, + static std::size_t count_equal(iterator n, iterator end, value_type const& v) { std::size_t count = 0; - for(;n != end; n = static_cast<node_pointer>(n->next_)) - if (n->value() == v) ++count; + for(;n != end; ++n) + if (*n == v) ++count; return count; } #else - static bool group_equals(node_pointer n1, node_pointer end1, - node_pointer n2, node_pointer end2) + static bool group_equals(iterator n1, iterator end1, + iterator n2, iterator end2) { for(;;) { - if(!extractor::compare_mapped( - n1->value(), n2->value())) + if(!extractor::compare_mapped(*n1, *n2)) return false; - n1 = static_cast<node_pointer>(n1->next_); - n2 = static_cast<node_pointer>(n2->next_); + ++n1; + ++n2; if (n1 == end1) return n2 == end2; if (n2 == end2) return false; @@ -387,35 +444,37 @@ namespace boost { namespace unordered { namespace detail { pos->group_prev_ = static_cast<link_pointer>(n); } - inline node_pointer add_node( + inline iterator add_node( node_constructor& a, - std::size_t hash, - node_pointer pos) + std::size_t key_hash, + iterator pos) { node_pointer n = a.release(); - n->hash_ = hash; - if(pos) { - this->add_after_node(n, pos); + n->hash_ = key_hash; + if (pos.node_) { + this->add_after_node(n, pos.node_); if (n->next_) { - std::size_t next_bucket = - static_cast<node_pointer>(n->next_)->hash_ % - this->bucket_count_; - if (next_bucket != hash % this->bucket_count_) { + std::size_t next_bucket = policy::to_bucket( + this->bucket_count_, + static_cast<node_pointer>(n->next_)->hash_); + if (next_bucket != + policy::to_bucket(this->bucket_count_, key_hash)) { this->get_bucket(next_bucket)->next_ = n; } } } else { - bucket_pointer b = this->get_bucket(hash % this->bucket_count_); + bucket_pointer b = this->get_bucket( + policy::to_bucket(this->bucket_count_, key_hash)); if (!b->next_) { previous_pointer start_node = this->get_previous_start(); if (start_node->next_) { - this->get_bucket( + this->get_bucket(policy::to_bucket(this->bucket_count_, static_cast<node_pointer>(start_node->next_)->hash_ - % this->bucket_count_)->next_ = n; + ))->next_ = n; } b->next_ = start_node; @@ -429,36 +488,44 @@ namespace boost { namespace unordered { namespace detail { } } ++this->size_; - return n; + return iterator(n); } - node_pointer emplace_impl(node_constructor& a) + iterator emplace_impl(node_constructor& a) { key_type const& k = this->get_key(a.value()); - std::size_t hash = this->hash_function()(k); - node_pointer position = this->find_node(hash, k); + std::size_t key_hash = this->hash(k); + iterator position = this->find_node(key_hash, k); // reserve has basic exception safety if the hash function // throws, strong otherwise. this->reserve_for_insert(this->size_ + 1); - return this->add_node(a, hash, position); + return this->add_node(a, key_hash, position); } void emplace_impl_no_rehash(node_constructor& a) { key_type const& k = this->get_key(a.value()); - std::size_t hash = this->hash_function()(k); - this->add_node(a, hash, - this->find_node(hash, k)); + std::size_t key_hash = this->hash(k); + this->add_node(a, key_hash, this->find_node(key_hash, k)); } #if defined(BOOST_NO_RVALUE_REFERENCES) +# if defined(BOOST_NO_VARIADIC_TEMPLATES) iterator emplace(boost::unordered::detail::emplace_args1< boost::unordered::detail::please_ignore_this_overload> const&) { BOOST_ASSERT(false); return iterator(); } +# else + iterator emplace( + boost::unordered::detail::please_ignore_this_overload const&) + { + BOOST_ASSERT(false); + return iterator(); + } +# endif #endif template <BOOST_UNORDERED_EMPLACE_TEMPLATE> @@ -523,11 +590,12 @@ namespace boost { namespace unordered { namespace detail { { if(!this->size_) return 0; - std::size_t hash = this->hash_function()(k); - std::size_t bucket_index = hash % this->bucket_count_; - bucket_pointer bucket = this->get_bucket(bucket_index); + std::size_t key_hash = this->hash(k); + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, key_hash); + bucket_pointer this_bucket = this->get_bucket(bucket_index); - previous_pointer prev = bucket->next_; + previous_pointer prev = this_bucket->next_; if (!prev) return 0; for (;;) @@ -535,9 +603,10 @@ namespace boost { namespace unordered { namespace detail { if (!prev->next_) return 0; std::size_t node_hash = static_cast<node_pointer>(prev->next_)->hash_; - if (node_hash % this->bucket_count_ != bucket_index) + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) return 0; - if (node_hash == hash && + if (node_hash == key_hash && this->key_eq()(k, this->get_key( static_cast<node_pointer>(prev->next_)->value()))) break; @@ -550,37 +619,39 @@ namespace boost { namespace unordered { namespace detail { static_cast<node_pointer>(pos->group_prev_)->next_; node_pointer end = static_cast<node_pointer>(end1); prev->next_ = end1; - this->fix_buckets(bucket, prev, end); - return this->delete_nodes(pos, end); + this->fix_buckets(this_bucket, prev, end); + return this->delete_nodes(c_iterator(pos), c_iterator(end)); } - node_pointer erase(node_pointer r) + iterator erase(c_iterator r) { - BOOST_ASSERT(r); - node_pointer next = static_cast<node_pointer>(r->next_); + BOOST_ASSERT(r.node_); + iterator next(r.node_); + ++next; - bucket_pointer bucket = this->get_bucket( - r->hash_ % this->bucket_count_); - previous_pointer prev = unlink_node(*bucket, r); + bucket_pointer this_bucket = this->get_bucket( + policy::to_bucket(this->bucket_count_, r.node_->hash_)); + previous_pointer prev = unlink_node(*this_bucket, r.node_); - this->fix_buckets(bucket, prev, next); + this->fix_buckets(this_bucket, prev, next.node_); this->delete_node(r); return next; } - node_pointer erase_range(node_pointer r1, node_pointer r2) + iterator erase_range(c_iterator r1, c_iterator r2) { - if (r1 == r2) return r2; + if (r1 == r2) return iterator(r2.node_); - std::size_t bucket_index = r1->hash_ % this->bucket_count_; + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, r1.node_->hash_); previous_pointer prev = unlink_nodes( - *this->get_bucket(bucket_index), r1, r2); - this->fix_buckets_range(bucket_index, prev, r1, r2); + *this->get_bucket(bucket_index), r1.node_, r2.node_); + this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_); this->delete_nodes(r1, r2); - return r2; + return iterator(r2.node_); } static previous_pointer unlink_node(bucket& b, node_pointer n) @@ -697,31 +768,31 @@ namespace boost { namespace unordered { namespace detail { node_constructor a(dst.node_alloc()); - node_pointer n = src.get_start(); + iterator n = src.get_start(); previous_pointer prev = dst.get_previous_start(); - while(n) { - std::size_t hash = n->hash_; - node_pointer group_end = + while (n.node_) { + std::size_t key_hash = n.node_->hash_; + iterator group_end( static_cast<node_pointer>( - static_cast<node_pointer>(n->group_prev_)->next_); + static_cast<node_pointer>(n.node_->group_prev_)->next_ + )); a.construct_node(); - a.construct_value2(n->value()); + a.construct_value2(*n); node_pointer first_node = a.release(); node_pointer end = first_node; - first_node->hash_ = hash; + first_node->hash_ = key_hash; prev->next_ = static_cast<link_pointer>(first_node); ++dst.size_; - for(n = static_cast<node_pointer>(n->next_); n != group_end; - n = static_cast<node_pointer>(n->next_)) + for (++n; n != group_end; ++n) { a.construct_node(); - a.construct_value2(n->value()); + a.construct_value2(*n); end = a.release(); - end->hash_ = hash; + end->hash_ = key_hash; add_after_node(end, first_node); ++dst.size_; } @@ -744,31 +815,31 @@ namespace boost { namespace unordered { namespace detail { node_constructor a(dst.node_alloc()); - node_pointer n = src.get_start(); + iterator n = src.get_start(); previous_pointer prev = dst.get_previous_start(); - while(n) { - std::size_t hash = n->hash_; - node_pointer group_end = + while (n.node_) { + std::size_t key_hash = n.node_->hash_; + iterator group_end( static_cast<node_pointer>( - static_cast<node_pointer>(n->group_prev_)->next_); + static_cast<node_pointer>(n.node_->group_prev_)->next_ + )); a.construct_node(); - a.construct_value2(boost::move(n->value())); + a.construct_value2(boost::move(*n)); node_pointer first_node = a.release(); node_pointer end = first_node; - first_node->hash_ = hash; + first_node->hash_ = key_hash; prev->next_ = static_cast<link_pointer>(first_node); ++dst.size_; - for(n = static_cast<node_pointer>(n->next_); n != group_end; - n = static_cast<node_pointer>(n->next_)) + for(++n; n != group_end; ++n) { a.construct_node(); - a.construct_value2(boost::move(n->value())); + a.construct_value2(boost::move(*n)); end = a.release(); - end->hash_ = hash; + end->hash_ = key_hash; add_after_node(end, first_node); ++dst.size_; } @@ -809,7 +880,8 @@ namespace boost { namespace unordered { namespace detail { static previous_pointer place_in_bucket(buckets& dst, previous_pointer prev, node_pointer end) { - bucket_pointer b = dst.get_bucket(end->hash_ % dst.bucket_count_); + bucket_pointer b = dst.get_bucket(policy::to_bucket( + dst.bucket_count_, end->hash_)); if (!b->next_) { b->next_ = static_cast<node_pointer>(prev); |