diff options
Diffstat (limited to 'boost/intrusive/hashtable.hpp')
| -rw-r--r-- | boost/intrusive/hashtable.hpp | 2320 |
1 files changed, 1255 insertions, 1065 deletions
diff --git a/boost/intrusive/hashtable.hpp b/boost/intrusive/hashtable.hpp index 1d4f3d3f0c..125330ff6e 100644 --- a/boost/intrusive/hashtable.hpp +++ b/boost/intrusive/hashtable.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2013 +// (C) Copyright Ion Gaztanaga 2006-2015 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -26,6 +26,7 @@ #include <boost/intrusive/detail/node_cloner_disposer.hpp> #include <boost/intrusive/detail/simple_disposers.hpp> #include <boost/intrusive/detail/size_holder.hpp> +#include <boost/intrusive/detail/iterator.hpp> //Implementation utilities #include <boost/intrusive/unordered_set_hook.hpp> @@ -55,6 +56,62 @@ namespace intrusive { /// @cond +template<class InputIt, class T> +InputIt priv_algo_find(InputIt first, InputIt last, const T& value) +{ + for (; first != last; ++first) { + if (*first == value) { + return first; + } + } + return last; +} + +template<class InputIt, class T> +typename boost::intrusive::iterator_traits<InputIt>::difference_type + priv_algo_count(InputIt first, InputIt last, const T& value) +{ + typename boost::intrusive::iterator_traits<InputIt>::difference_type ret = 0; + for (; first != last; ++first) { + if (*first == value) { + ret++; + } + } + return ret; +} + +template <class ForwardIterator1, class ForwardIterator2> +bool priv_algo_is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2) +{ + typedef typename + boost::intrusive::iterator_traits<ForwardIterator2>::difference_type + distance_type; + //Efficiently compare identical prefixes: O(N) if sequences + //have the same elements in the same order. + for ( ; first1 != last1; ++first1, ++first2){ + if (! (*first1 == *first2)) + break; + } + if (first1 == last1){ + return true; + } + + //Establish last2 assuming equal ranges by iterating over the + //rest of the list. + ForwardIterator2 last2 = first2; + boost::intrusive::iterator_advance(last2, boost::intrusive::iterator_distance(first1, last1)); + for(ForwardIterator1 scan = first1; scan != last1; ++scan){ + if (scan != (priv_algo_find)(first1, scan, *scan)){ + continue; //We've seen this one before. + } + distance_type matches = (priv_algo_count)(first2, last2, *scan); + if (0 == matches || (priv_algo_count)(scan, last1, *scan != matches)){ + return false; + } + } + return true; +} + template<int Dummy = 0> struct prime_list_holder { @@ -169,35 +226,23 @@ struct unordered_bucket_ptr_impl }; template <class T> -struct store_hash_bool +struct store_hash_is_true { template<bool Add> - struct two_or_three {one _[2 + Add];}; - template <class U> static one test(...); + struct two_or_three {yes_type _[2 + Add];}; + template <class U> static yes_type test(...); template <class U> static two_or_three<U::store_hash> test (int); - static const std::size_t value = sizeof(test<T>(0)); + static const bool value = sizeof(test<T>(0)) > sizeof(yes_type)*2; }; template <class T> -struct store_hash_is_true -{ - static const bool value = store_hash_bool<T>::value > sizeof(one)*2; -}; - -template <class T> -struct optimize_multikey_bool +struct optimize_multikey_is_true { template<bool Add> - struct two_or_three {one _[2 + Add];}; - template <class U> static one test(...); + struct two_or_three {yes_type _[2 + Add];}; + template <class U> static yes_type test(...); template <class U> static two_or_three<U::optimize_multikey> test (int); - static const std::size_t value = sizeof(test<T>(0)); -}; - -template <class T> -struct optimize_multikey_is_true -{ - static const bool value = optimize_multikey_bool<T>::value > sizeof(one)*2; + static const bool value = sizeof(test<T>(0)) > sizeof(yes_type)*2; }; struct insert_commit_data_impl @@ -216,6 +261,23 @@ inline typename pointer_traits<SlistNodePtr>::template rebind_pointer<Node>::typ template<class NodeTraits> struct group_functions { + // A group is reverse-linked + // + // A is "first in group" + // C is "last in group" + // __________________ + // | _____ _____ | + // | | | | | | <- Group links + // ^ V ^ V ^ V + // _ _ _ _ + // A|_| B|_| C|_| D|_| + // + // ^ | ^ | ^ | ^ V <- Bucket links + // _ _____| |_____| |______| |____| | + // |B| | + // ^________________________________| + // + typedef NodeTraits node_traits; typedef unordered_group_adapter<node_traits> group_traits; typedef typename node_traits::node_ptr node_ptr; @@ -225,6 +287,7 @@ struct group_functions typedef typename reduced_node_traits::node_ptr slist_node_ptr; typedef typename reduced_node_traits::node slist_node; typedef circular_slist_algorithms<group_traits> group_algorithms; + typedef circular_slist_algorithms<node_traits> node_algorithms; static slist_node_ptr get_bucket_before_begin (const slist_node_ptr &bucket_beg, const slist_node_ptr &bucket_end, const node_ptr &p) @@ -260,53 +323,20 @@ struct group_functions static node_ptr get_prev_to_first_in_group(const slist_node_ptr &bucket_node, const node_ptr &first_in_group) { - //Just iterate using group links and obtain the node - //before "first_in_group)" - node_ptr prev_node = detail::dcast_bucket_ptr<node>(bucket_node); - node_ptr nxt(node_traits::get_next(prev_node)); - while(nxt != first_in_group){ - prev_node = group_traits::get_next(nxt); - nxt = node_traits::get_next(prev_node); + node_ptr nb = detail::dcast_bucket_ptr<node>(bucket_node); + node_ptr n; + while((n = node_traits::get_next(nb)) != first_in_group){ + nb = group_traits::get_next(n); //go to last in group } - return prev_node; - } - - static node_ptr get_first_in_group_of_last_in_group(const node_ptr &last_in_group) - { - //Just iterate using group links and obtain the node - //before "last_in_group" - node_ptr possible_first = group_traits::get_next(last_in_group); - node_ptr possible_first_prev = group_traits::get_next(possible_first); - // The deleted node is at the end of the group, so the - // node in the group pointing to it is at the beginning - // of the group. Find that to change its pointer. - while(possible_first_prev != last_in_group){ - possible_first = possible_first_prev; - possible_first_prev = group_traits::get_next(possible_first); - } - return possible_first; + return nb; } static void erase_from_group(const slist_node_ptr &end_ptr, const node_ptr &to_erase_ptr, detail::true_) { - node_ptr nxt_ptr(node_traits::get_next(to_erase_ptr)); - node_ptr prev_in_group_ptr(group_traits::get_next(to_erase_ptr)); - bool last_in_group = (end_ptr == nxt_ptr) || - (group_traits::get_next(nxt_ptr) != to_erase_ptr); - bool is_first_in_group = node_traits::get_next(prev_in_group_ptr) != to_erase_ptr; - - if(is_first_in_group && last_in_group){ - group_algorithms::init(to_erase_ptr); - } - else if(is_first_in_group){ - group_algorithms::unlink_after(nxt_ptr); - } - else if(last_in_group){ - node_ptr first_in_group = - get_first_in_group_of_last_in_group(to_erase_ptr); - group_algorithms::unlink_after(first_in_group); - } - else{ + node_ptr const nxt_ptr(node_traits::get_next(to_erase_ptr)); + //Check if the next node is in the group (not end node) and reverse linked to + //'to_erase_ptr'. Erase if that's the case. + if(nxt_ptr != end_ptr && to_erase_ptr == group_traits::get_next(nxt_ptr)){ group_algorithms::unlink_after(nxt_ptr); } } @@ -317,81 +347,42 @@ struct group_functions static node_ptr get_last_in_group(const node_ptr &first_in_group, detail::true_) { return group_traits::get_next(first_in_group); } - static node_ptr get_last_in_group(const node_ptr &n, detail::false_) + static node_ptr get_last_in_group(node_ptr n, detail::false_) { return n; } - static void init_group(const node_ptr &n, true_) - { group_algorithms::init(n); } - - static void init_group(const node_ptr &, false_) - {} - - static void insert_in_group(const node_ptr &first_in_group, const node_ptr &n, true_) + static node_ptr get_first_in_group(node_ptr n, detail::true_) { - if(first_in_group){ - if(group_algorithms::unique(first_in_group)) - group_algorithms::link_after(first_in_group, n); - else{ - group_algorithms::link_after(node_traits::get_next(first_in_group), n); - } - } - else{ - group_algorithms::init_header(n); + node_ptr ng; + while(n == node_traits::get_next((ng = group_traits::get_next(n)))){ + n = ng; } + return n; } - static slist_node_ptr get_previous_and_next_in_group - ( const slist_node_ptr &i, node_ptr &nxt_in_group - //If first_end_ptr == last_end_ptr, then first_end_ptr is the bucket of i - //Otherwise first_end_ptr is the first bucket and last_end_ptr the last one. - , const slist_node_ptr &first_end_ptr, const slist_node_ptr &last_end_ptr) - { - slist_node_ptr prev; - node_ptr elem(detail::dcast_bucket_ptr<node>(i)); - - //It's the last in group if the next_node is a bucket - slist_node_ptr nxt(node_traits::get_next(elem)); - bool last_in_group = (first_end_ptr <= nxt && nxt <= last_end_ptr) || - (group_traits::get_next(detail::dcast_bucket_ptr<node>(nxt)) != elem); - //It's the first in group if group_previous's next_node is not - //itself, as group list does not link bucket - node_ptr prev_in_group(group_traits::get_next(elem)); - bool first_in_group = node_traits::get_next(prev_in_group) != elem; - - if(first_in_group){ - node_ptr start_pos; - if(last_in_group){ - start_pos = elem; - nxt_in_group = node_ptr(); - } - else{ - start_pos = prev_in_group; - nxt_in_group = node_traits::get_next(elem); - } - slist_node_ptr bucket_node; - if(first_end_ptr != last_end_ptr){ - bucket_node = group_functions::get_bucket_before_begin - (first_end_ptr, last_end_ptr, start_pos); - } - else{ - bucket_node = first_end_ptr; - } - prev = group_functions::get_prev_to_first_in_group(bucket_node, elem); - } - else{ - if(last_in_group){ - nxt_in_group = group_functions::get_first_in_group_of_last_in_group(elem); - } - else{ - nxt_in_group = node_traits::get_next(elem); - } - prev = group_traits::get_next(elem); - } - return prev; + static node_ptr next_group_if_first_in_group(node_ptr ptr) + { + return node_traits::get_next(group_traits::get_next(ptr)); } + static node_ptr get_first_in_group(const node_ptr &n, detail::false_) + { return n; } + + static void insert_in_group(const node_ptr &first_in_group, const node_ptr &n, true_) + { group_algorithms::link_after(first_in_group, n); } + static void insert_in_group(const node_ptr&, const node_ptr&, false_) {} + + static node_ptr split_group(node_ptr const new_first_in_group) + { + node_ptr const first((get_first_in_group)(new_first_in_group, detail::true_())); + if(first != new_first_in_group){ + node_ptr const last = group_traits::get_next(first); + group_traits::set_next(first, group_traits::get_next(new_first_in_group)); + group_traits::set_next(new_first_in_group, last); + } + return first; + } }; template<class BucketType, class SplitTraits> @@ -453,8 +444,7 @@ inline std::size_t hash_to_bucket_split(std::size_t hash_value, std::size_t buck { std::size_t bucket_number = detail::hash_to_bucket(hash_value, bucket_cnt, detail::bool_<Power2Buckets>()); if(Incremental) - if(bucket_number >= split) - bucket_number -= bucket_cnt/2; + bucket_number -= static_cast<std::size_t>(bucket_number >= split)*(bucket_cnt/2); return bucket_number; } @@ -513,6 +503,7 @@ struct hashtable_defaults { typedef default_hashtable_hook_applier proto_value_traits; typedef std::size_t size_type; + typedef void key_of_value; typedef void equal; typedef void hash; typedef default_bucket_traits bucket_traits; @@ -576,17 +567,11 @@ struct node_cast_adaptor } }; -static const std::size_t hashtable_data_bool_flags_mask = - ( hash_bool_flags::cache_begin_pos - | hash_bool_flags::constant_time_size_pos - | hash_bool_flags::incremental_pos - ); - //bucket_plus_vtraits stores ValueTraits + BucketTraits //this data is needed by iterators to obtain the //value from the iterator and detect the bucket template<class ValueTraits, class BucketTraits> -struct bucket_plus_vtraits : public ValueTraits +struct bucket_plus_vtraits { typedef BucketTraits bucket_traits; typedef ValueTraits value_traits; @@ -607,6 +592,11 @@ struct bucket_plus_vtraits : public ValueTraits typedef typename node_traits::node_ptr node_ptr; typedef typename node_traits::node node; typedef typename value_traits::value_type value_type; + typedef typename value_traits::pointer pointer; + typedef typename value_traits::const_pointer const_pointer; + typedef typename pointer_traits<pointer>::reference reference; + typedef typename pointer_traits + <const_pointer>::reference const_reference; typedef circular_slist_algorithms<group_traits> group_algorithms; typedef typename pointer_traits <typename value_traits::pointer>:: @@ -618,16 +608,14 @@ struct bucket_plus_vtraits : public ValueTraits <const bucket_plus_vtraits>::type const_bucket_value_traits_ptr; typedef typename detail::unordered_bucket_ptr_impl <value_traits>::type bucket_ptr; - typedef detail::bool_<detail::optimize_multikey_is_true - <node_traits>::value> optimize_multikey_t; template<class BucketTraitsType> bucket_plus_vtraits(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits) - : ValueTraits(val_traits), bucket_traits_(::boost::forward<BucketTraitsType>(b_traits)) + : data(val_traits, ::boost::forward<BucketTraitsType>(b_traits)) {} bucket_plus_vtraits & operator =(const bucket_plus_vtraits &x) - { bucket_traits_ = x.bucket_traits_; return *this; } + { data.bucket_traits_ = x.data.bucket_traits_; return *this; } const_value_traits_ptr priv_value_traits_ptr() const { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); } @@ -646,18 +634,18 @@ struct bucket_plus_vtraits : public ValueTraits //value traits // const value_traits &priv_value_traits() const - { return *this; } + { return this->data; } value_traits &priv_value_traits() - { return *this; } + { return this->data; } //bucket_traits // const bucket_traits &priv_bucket_traits() const - { return this->bucket_traits_; } + { return this->data.bucket_traits_; } bucket_traits &priv_bucket_traits() - { return this->bucket_traits_; } + { return this->data.bucket_traits_; } //bucket operations bucket_ptr priv_bucket_pointer() const @@ -674,6 +662,119 @@ struct bucket_plus_vtraits : public ValueTraits siterator priv_invalid_local_it() const { return this->priv_bucket_traits().bucket_begin()->before_begin(); } + template<class NodeDisposer> + static size_type priv_erase_from_single_bucket(bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::true_) //optimize multikey + { + size_type n = 0; + siterator const sfirst(++siterator(sbefore_first)); + if(sfirst != slast){ + node_ptr const nf = detail::dcast_bucket_ptr<node>(sfirst.pointed_node()); + node_ptr const nl = detail::dcast_bucket_ptr<node>(slast.pointed_node()); + node_ptr const ne = detail::dcast_bucket_ptr<node>(b.end().pointed_node()); + + if(group_functions_t::next_group_if_first_in_group(nf) != nf) { + // The node is at the beginning of a group. + if(nl != ne){ + group_functions_t::split_group(nl); + } + } + else { + node_ptr const group1 = group_functions_t::split_group(nf); + if(nl != ne) { + node_ptr const group2 = group_functions_t::split_group(ne); + if(nf == group2) { //Both first and last in the same group + //so join group1 and group2 + node_ptr const end1 = group_traits::get_next(group1); + node_ptr const end2 = group_traits::get_next(group2); + group_traits::set_next(group1, end2); + group_traits::set_next(group2, end1); + } + } + } + + siterator it(++siterator(sbefore_first)); + while(it != slast){ + node_disposer((it++).pointed_node()); + ++n; + } + b.erase_after(sbefore_first, slast); + } + return n; + } + + template<class NodeDisposer> + static size_type priv_erase_from_single_bucket(bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::false_) //optimize multikey + { + size_type n = 0; + siterator it(++siterator(sbefore_first)); + while(it != slast){ + node_disposer((it++).pointed_node()); + ++n; + } + b.erase_after(sbefore_first, slast); + return n; + } + + template<class NodeDisposer> + static void priv_erase_node(bucket_type &b, siterator i, NodeDisposer node_disposer, detail::true_) //optimize multikey + { + node_ptr const ne(detail::dcast_bucket_ptr<node>(b.end().pointed_node())); + node_ptr n(detail::dcast_bucket_ptr<node>(i.pointed_node())); + node_ptr pos = node_traits::get_next(group_traits::get_next(n)); + node_ptr bn; + node_ptr nn(node_traits::get_next(n)); + + if(pos != n) { + //Node is the first of the group + bn = group_functions_t::get_prev_to_first_in_group(ne, n); + + //Unlink the rest of the group if it's not the last node of its group + if(nn != ne && group_traits::get_next(nn) == n){ + group_algorithms::unlink_after(nn); + } + } + else if(nn != ne && group_traits::get_next(nn) == n){ + //Node is not the end of the group + bn = group_traits::get_next(n); + group_algorithms::unlink_after(nn); + } + else{ + //Node is the end of the group + bn = group_traits::get_next(n); + node_ptr const x(group_algorithms::get_previous_node(n)); + group_algorithms::unlink_after(x); + } + b.erase_after_and_dispose(bucket_type::s_iterator_to(*bn), node_disposer); + } + + template<class NodeDisposer> + static void priv_erase_node(bucket_type &b, siterator i, NodeDisposer node_disposer, detail::false_) //optimize multikey + { b.erase_after_and_dispose(b.previous(i), node_disposer); } + + template<class NodeDisposer, bool OptimizeMultikey> + size_type priv_erase_node_range( siterator const &before_first_it, size_type const first_bucket + , siterator const &last_it, size_type const last_bucket + , NodeDisposer node_disposer, detail::bool_<OptimizeMultikey> optimize_multikey_tag) + { + size_type num_erased(0); + siterator last_step_before_it; + if(first_bucket != last_bucket){ + bucket_type *b = (&this->priv_bucket_pointer()[0]); + num_erased += this->priv_erase_from_single_bucket + (b[first_bucket], before_first_it, b[first_bucket].end(), node_disposer, optimize_multikey_tag); + for(size_type i = 0, n = (last_bucket - first_bucket - 1); i != n; ++i){ + num_erased += this->priv_erase_whole_bucket(b[first_bucket+i+1], node_disposer); + } + last_step_before_it = b[last_bucket].before_begin(); + } + else{ + last_step_before_it = before_first_it; + } + num_erased += this->priv_erase_from_single_bucket + (this->priv_bucket_pointer()[last_bucket], last_step_before_it, last_it, node_disposer, optimize_multikey_tag); + return num_erased; + } + static siterator priv_get_last(bucket_type &b, detail::true_) //optimize multikey { //First find the last node of p's group. @@ -690,14 +791,30 @@ struct bucket_plus_vtraits : public ValueTraits return bucket_type::s_iterator_to(*last_node_group); } + template<class NodeDisposer> + size_type priv_erase_whole_bucket(bucket_type &b, NodeDisposer node_disposer) + { + size_type num_erased = 0; + siterator b_begin(b.before_begin()); + siterator nxt(b_begin); + ++nxt; + siterator const end_sit(b.end()); + while(nxt != end_sit){ + //No need to init group links as we'll delete all bucket nodes + nxt = bucket_type::s_erase_after_and_dispose(b_begin, node_disposer); + ++num_erased; + } + return num_erased; + } + static siterator priv_get_last(bucket_type &b, detail::false_) //NOT optimize multikey { return b.previous(b.end()); } static siterator priv_get_previous(bucket_type &b, siterator i, detail::true_) //optimize multikey { - node_ptr elem(detail::dcast_bucket_ptr<node>(i.pointed_node())); - node_ptr prev_in_group(group_traits::get_next(elem)); - bool first_in_group = node_traits::get_next(prev_in_group) != elem; + node_ptr const elem(detail::dcast_bucket_ptr<node>(i.pointed_node())); + node_ptr const prev_in_group(group_traits::get_next(elem)); + bool const first_in_group = node_traits::get_next(prev_in_group) != elem; typename bucket_type::node &n = first_in_group ? *group_functions_t::get_prev_to_first_in_group(b.end().pointed_node(), elem) : *group_traits::get_next(elem) @@ -708,19 +825,6 @@ struct bucket_plus_vtraits : public ValueTraits static siterator priv_get_previous(bucket_type &b, siterator i, detail::false_) //NOT optimize multikey { return b.previous(i); } - static void priv_clear_group_nodes(bucket_type &b, detail::true_) //optimize multikey - { - siterator it(b.begin()), itend(b.end()); - while(it != itend){ - node_ptr to_erase(detail::dcast_bucket_ptr<node>(it.pointed_node())); - ++it; - group_algorithms::init(to_erase); - } - } - - static void priv_clear_group_nodes(bucket_type &, detail::false_) //NOT optimize multikey - {} - std::size_t priv_get_bucket_num_no_hash_store(siterator it, detail::true_) //optimize multikey { const bucket_ptr f(this->priv_bucket_pointer()), l(f + this->priv_bucket_count() - 1); @@ -757,19 +861,19 @@ struct bucket_plus_vtraits : public ValueTraits static std::size_t priv_stored_hash(slist_node_ptr n, detail::true_) //store_hash { return node_traits::get_hash(detail::dcast_bucket_ptr<node>(n)); } - static std::size_t priv_stored_hash(slist_node_ptr, detail::false_) //NO store_hash (This should never be called) - { BOOST_INTRUSIVE_INVARIANT_ASSERT(0); return 0; } + static std::size_t priv_stored_hash(slist_node_ptr, detail::false_) //NO store_hash + { return std::size_t(-1); } - node &priv_value_to_node(value_type &v) + node &priv_value_to_node(reference v) { return *this->priv_value_traits().to_node_ptr(v); } - const node &priv_value_to_node(const value_type &v) const + const node &priv_value_to_node(const_reference v) const { return *this->priv_value_traits().to_node_ptr(v); } - value_type &priv_value_from_slist_node(slist_node_ptr n) + reference priv_value_from_slist_node(slist_node_ptr n) { return *this->priv_value_traits().to_value_ptr(detail::dcast_bucket_ptr<node>(n)); } - const value_type &priv_value_from_slist_node(slist_node_ptr n) const + const_reference priv_value_from_slist_node(slist_node_ptr n) const { return *this->priv_value_traits().to_value_ptr(detail::dcast_bucket_ptr<node>(n)); } void priv_clear_buckets(const bucket_ptr buckets_ptr, const size_type bucket_cnt) @@ -777,7 +881,6 @@ struct bucket_plus_vtraits : public ValueTraits bucket_ptr buckets_it = buckets_ptr; for(size_type bucket_i = 0; bucket_i != bucket_cnt; ++buckets_it, ++bucket_i){ if(safemode_or_autounlink){ - bucket_plus_vtraits::priv_clear_group_nodes(*buckets_it, optimize_multikey_t()); buckets_it->clear_and_dispose(detail::init_disposer<node_algorithms>()); } else{ @@ -786,10 +889,51 @@ struct bucket_plus_vtraits : public ValueTraits } } - bucket_traits bucket_traits_; + std::size_t priv_stored_or_compute_hash(const value_type &v, detail::true_) const //For store_hash == true + { return node_traits::get_hash(this->priv_value_traits().to_node_ptr(v)); } + + typedef hashtable_iterator<bucket_plus_vtraits, false> iterator; + typedef hashtable_iterator<bucket_plus_vtraits, true> const_iterator; + + iterator end() + { return iterator(this->priv_invalid_local_it(), 0); } + + const_iterator end() const + { return this->cend(); } + + const_iterator cend() const + { return const_iterator(this->priv_invalid_local_it(), 0); } + + static size_type suggested_upper_bucket_count(size_type n) + { + const std::size_t *primes = &prime_list_holder<0>::prime_list[0]; + const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size; + std::size_t const* bound = std::lower_bound(primes, primes_end, n); + bound -= (bound == primes_end); + return size_type(*bound); + } + + static size_type suggested_lower_bucket_count(size_type n) + { + const std::size_t *primes = &prime_list_holder<0>::prime_list[0]; + const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size; + size_type const* bound = std::upper_bound(primes, primes_end, n); + bound -= (bound != primes); + return size_type(*bound); + } + + //Public functions: + struct data_type : public ValueTraits + { + template<class BucketTraitsType> + data_type(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits) + : ValueTraits(val_traits), bucket_traits_(::boost::forward<BucketTraitsType>(b_traits)) + {} + bucket_traits bucket_traits_; + } data; }; -template<class Hash, class T> +template<class Hash, class> struct get_hash { typedef Hash type; @@ -801,76 +945,124 @@ struct get_hash<void, T> typedef ::boost::hash<T> type; }; +template<class EqualTo, class> +struct get_equal_to +{ + typedef EqualTo type; +}; + +template<class T> +struct get_equal_to<void, T> +{ + typedef std::equal_to<T> type; +}; + +template<class KeyOfValue, class T> +struct get_hash_key_of_value +{ + typedef KeyOfValue type; +}; + +template<class T> +struct get_hash_key_of_value<void, T> +{ + typedef ::boost::intrusive::detail::identity<T> type; +}; + +template<class T, class VoidOrKeyOfValue> +struct hash_key_types_base +{ + typedef typename get_hash_key_of_value + < VoidOrKeyOfValue, T>::type key_of_value; + typedef typename key_of_value::type key_type; +}; + +template<class T, class VoidOrKeyOfValue, class VoidOrKeyHash> +struct hash_key_hash + : get_hash + < VoidOrKeyHash + , typename hash_key_types_base<T, VoidOrKeyOfValue>::key_type + > +{}; + +template<class T, class VoidOrKeyOfValue, class VoidOrKeyEqual> +struct hash_key_equal + : get_equal_to + < VoidOrKeyEqual + , typename hash_key_types_base<T, VoidOrKeyOfValue>::key_type + > + +{}; + //bucket_hash_t //Stores bucket_plus_vtraits plust the hash function -template<class VoidOrKeyHash, class ValueTraits, class BucketTraits> +template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class BucketTraits> struct bucket_hash_t //Use public inheritance to avoid MSVC bugs with closures : public detail::ebo_functor_holder - <typename get_hash< VoidOrKeyHash - , typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits::value_type - >::type - > + <typename hash_key_hash < typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits::value_type + , VoidOrKeyOfValue + , VoidOrKeyHash + >::type + > + , bucket_plus_vtraits<ValueTraits, BucketTraits> //4 { typedef typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits value_traits; typedef typename value_traits::value_type value_type; typedef typename value_traits::node_traits node_traits; - typedef typename get_hash< VoidOrKeyHash, value_type>::type hasher; + typedef hash_key_hash + < value_type, VoidOrKeyOfValue, VoidOrKeyHash> hash_key_hash_t; + typedef typename hash_key_hash_t::type hasher; + typedef typename hash_key_types_base<value_type, VoidOrKeyOfValue>::key_of_value key_of_value; + typedef BucketTraits bucket_traits; typedef bucket_plus_vtraits<ValueTraits, BucketTraits> bucket_plus_vtraits_t; + typedef detail::ebo_functor_holder<hasher> base_t; template<class BucketTraitsType> bucket_hash_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h) - : detail::ebo_functor_holder<hasher>(h), internal(val_traits, ::boost::forward<BucketTraitsType>(b_traits)) + : detail::ebo_functor_holder<hasher>(h), bucket_plus_vtraits_t(val_traits, ::boost::forward<BucketTraitsType>(b_traits)) {} const hasher &priv_hasher() const - { return this->detail::ebo_functor_holder<hasher>::get(); } + { return this->base_t::get(); } hasher &priv_hasher() - { return this->detail::ebo_functor_holder<hasher>::get(); } + { return this->base_t::get(); } - std::size_t priv_stored_or_compute_hash(const value_type &v, detail::true_) const //For store_hash == true - { return node_traits::get_hash(this->internal.priv_value_traits().to_node_ptr(v)); } + using bucket_plus_vtraits_t::priv_stored_or_compute_hash; //For store_hash == true std::size_t priv_stored_or_compute_hash(const value_type &v, detail::false_) const //For store_hash == false - { return this->priv_hasher()(v); } - - bucket_plus_vtraits_t internal; //4 + { return this->priv_hasher()(key_of_value()(v)); } }; - -template<class EqualTo, class T> -struct get_equal_to +template<class ValueTraits, class BucketTraits, class VoidOrKeyOfValue, class VoidOrKeyEqual> +struct hashtable_equal_holder { - typedef EqualTo type; -}; - -template<class T> -struct get_equal_to<void, T> -{ - typedef ::std::equal_to<T> type; + typedef detail::ebo_functor_holder + < typename hash_key_equal < typename bucket_plus_vtraits<ValueTraits, BucketTraits>::value_traits::value_type + , VoidOrKeyOfValue + , VoidOrKeyEqual + >::type + > type; }; //bucket_hash_equal_t //Stores bucket_hash_t and the equality function when the first //non-empty bucket shall not be cached. -template<class VoidOrKeyHash, class VoidOrKeyEqual, class ValueTraits, class BucketTraits, bool> +template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, bool> struct bucket_hash_equal_t //Use public inheritance to avoid MSVC bugs with closures - : public detail::ebo_functor_holder //equal - <typename get_equal_to< VoidOrKeyEqual - , typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits::value_type - >::type - > + : public bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> //3 + , public hashtable_equal_holder<ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type //equal { - typedef bucket_hash_t<VoidOrKeyHash, ValueTraits, BucketTraits> bucket_hash_type; + typedef typename hashtable_equal_holder + <ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type equal_holder_t; + typedef bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> bucket_hash_type; typedef bucket_plus_vtraits<ValueTraits,BucketTraits> bucket_plus_vtraits_t; - typedef typename bucket_plus_vtraits_t::value_traits value_traits; - typedef typename get_equal_to< VoidOrKeyEqual - , typename value_traits::value_type - >::type value_equal; + typedef ValueTraits value_traits; + typedef typename equal_holder_t::functor_type key_equal; typedef typename bucket_hash_type::hasher hasher; typedef BucketTraits bucket_traits; typedef typename bucket_plus_vtraits_t::slist_impl slist_impl; @@ -880,13 +1072,13 @@ struct bucket_hash_equal_t typedef typename detail::unordered_bucket_ptr_impl<value_traits>::type bucket_ptr; template<class BucketTraitsType> - bucket_hash_equal_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h, const value_equal &e) - : detail::ebo_functor_holder<value_equal>(e) - , internal(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h) + bucket_hash_equal_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h, const key_equal &e) + : bucket_hash_type(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h) + , equal_holder_t(e) {} bucket_ptr priv_get_cache() - { return this->internal.internal.priv_bucket_pointer(); } + { return this->bucket_hash_type::priv_bucket_pointer(); } void priv_set_cache(const bucket_ptr &) {} @@ -903,14 +1095,14 @@ struct bucket_hash_equal_t siterator priv_begin() const { size_type n = 0; - size_type bucket_cnt = this->internal.internal.priv_bucket_count(); + size_type bucket_cnt = this->bucket_hash_type::priv_bucket_count(); for (n = 0; n < bucket_cnt; ++n){ - bucket_type &b = this->internal.internal.priv_bucket_pointer()[n]; + bucket_type &b = this->bucket_hash_type::priv_bucket_pointer()[n]; if(!b.empty()){ return b.begin(); } } - return this->internal.internal.priv_invalid_local_it(); + return this->bucket_hash_type::priv_invalid_local_it(); } void priv_insertion_update_cache(size_type) @@ -922,43 +1114,38 @@ struct bucket_hash_equal_t void priv_erasure_update_cache() {} - const value_equal &priv_equal() const - { return this->detail::ebo_functor_holder<value_equal>::get(); } + const key_equal &priv_equal() const + { return this->equal_holder_t::get(); } - value_equal &priv_equal() - { return this->detail::ebo_functor_holder<value_equal>::get(); } - - bucket_hash_t<VoidOrKeyHash, ValueTraits, BucketTraits> internal; //3 + key_equal &priv_equal() + { return this->equal_holder_t::get(); } }; //bucket_hash_equal_t //Stores bucket_hash_t and the equality function when the first //non-empty bucket shall be cached. -template<class VoidOrKeyHash, class VoidOrKeyEqual, class ValueTraits, class BucketTraits> //cache_begin == true version -struct bucket_hash_equal_t<VoidOrKeyHash, VoidOrKeyEqual, ValueTraits, BucketTraits, true> +template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits> //cache_begin == true version +struct bucket_hash_equal_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, true> //Use public inheritance to avoid MSVC bugs with closures - : public detail::ebo_functor_holder //equal - <typename get_equal_to< VoidOrKeyEqual - , typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits::value_type - >::type - > + : bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> //2 + , hashtable_equal_holder<ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type { - typedef bucket_plus_vtraits<ValueTraits, BucketTraits> bucket_plus_vtraits_t; - typedef bucket_hash_t<VoidOrKeyHash, ValueTraits, BucketTraits> bucket_hash_type; - typedef typename bucket_plus_vtraits - <ValueTraits,BucketTraits>::value_traits value_traits; - typedef typename get_equal_to - < VoidOrKeyEqual - , typename value_traits::value_type>::type value_equal; + typedef typename hashtable_equal_holder + <ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type equal_holder_t; + + typedef bucket_plus_vtraits<ValueTraits,BucketTraits> bucket_plus_vtraits_t; + typedef ValueTraits value_traits; + typedef typename equal_holder_t::functor_type key_equal; + typedef bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> bucket_hash_type; typedef typename bucket_hash_type::hasher hasher; typedef BucketTraits bucket_traits; typedef typename bucket_plus_vtraits_t::slist_impl::size_type size_type; typedef typename bucket_plus_vtraits_t::slist_impl::iterator siterator; template<class BucketTraitsType> - bucket_hash_equal_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h, const value_equal &e) - : detail::ebo_functor_holder<value_equal>(e) - , internal(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h) + bucket_hash_equal_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h, const key_equal &e) + : bucket_hash_type(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h) + , equal_holder_t(e) {} typedef typename detail::unordered_bucket_ptr_impl @@ -974,10 +1161,10 @@ struct bucket_hash_equal_t<VoidOrKeyHash, VoidOrKeyEqual, ValueTraits, BucketTra { cached_begin_ = p; } std::size_t priv_get_cache_bucket_num() - { return this->cached_begin_ - this->internal.internal.priv_bucket_pointer(); } + { return this->cached_begin_ - this->bucket_hash_type::priv_bucket_pointer(); } void priv_initialize_cache() - { this->cached_begin_ = this->internal.internal.priv_invalid_bucket(); } + { this->cached_begin_ = this->bucket_hash_type::priv_invalid_bucket(); } void priv_swap_cache(bucket_hash_equal_t &other) { @@ -986,8 +1173,8 @@ struct bucket_hash_equal_t<VoidOrKeyHash, VoidOrKeyEqual, ValueTraits, BucketTra siterator priv_begin() const { - if(this->cached_begin_ == this->internal.internal.priv_invalid_bucket()){ - return this->internal.internal.priv_invalid_local_it(); + if(this->cached_begin_ == this->bucket_hash_type::priv_invalid_bucket()){ + return this->bucket_hash_type::priv_invalid_local_it(); } else{ return this->cached_begin_->begin(); @@ -996,34 +1183,34 @@ struct bucket_hash_equal_t<VoidOrKeyHash, VoidOrKeyEqual, ValueTraits, BucketTra void priv_insertion_update_cache(size_type insertion_bucket) { - bucket_ptr p = this->internal.internal.priv_bucket_pointer() + insertion_bucket; + bucket_ptr p = this->bucket_hash_type::priv_bucket_pointer() + insertion_bucket; if(p < this->cached_begin_){ this->cached_begin_ = p; } } - const value_equal &priv_equal() const - { return this->detail::ebo_functor_holder<value_equal>::get(); } + const key_equal &priv_equal() const + { return this->equal_holder_t::get(); } - value_equal &priv_equal() - { return this->detail::ebo_functor_holder<value_equal>::get(); } + key_equal &priv_equal() + { return this->equal_holder_t::get(); } void priv_erasure_update_cache_range(size_type first_bucket_num, size_type last_bucket_num) { //If the last bucket is the end, the cache must be updated //to the last position if all if(this->priv_get_cache_bucket_num() == first_bucket_num && - this->internal.internal.priv_bucket_pointer()[first_bucket_num].empty() ){ - this->priv_set_cache(this->internal.internal.priv_bucket_pointer() + last_bucket_num); + this->bucket_hash_type::priv_bucket_pointer()[first_bucket_num].empty() ){ + this->priv_set_cache(this->bucket_hash_type::priv_bucket_pointer() + last_bucket_num); this->priv_erasure_update_cache(); } } void priv_erasure_update_cache() { - if(this->cached_begin_ != this->internal.internal.priv_invalid_bucket()){ - size_type current_n = this->priv_get_cache() - this->internal.internal.priv_bucket_pointer(); - for( const size_type num_buckets = this->internal.internal.priv_bucket_count() + if(this->cached_begin_ != this->bucket_hash_type::priv_invalid_bucket()){ + size_type current_n = this->priv_get_cache() - this->bucket_hash_type::priv_bucket_pointer(); + for( const size_type num_buckets = this->bucket_hash_type::priv_bucket_count() ; current_n < num_buckets ; ++current_n, ++this->priv_get_cache()){ if(!this->priv_get_cache()->empty()){ @@ -1035,103 +1222,291 @@ struct bucket_hash_equal_t<VoidOrKeyHash, VoidOrKeyEqual, ValueTraits, BucketTra } bucket_ptr cached_begin_; - bucket_hash_t<VoidOrKeyHash, ValueTraits, BucketTraits> internal; //2 }; +//This wrapper around size_traits is used +//to maintain minimal container size with compilers like MSVC +//that have problems with EBO and multiple empty base classes +template<class DeriveFrom, class SizeType, bool> +struct hashtable_size_traits_wrapper + : public DeriveFrom +{ + template<class Base, class Arg0, class Arg1, class Arg2> + hashtable_size_traits_wrapper( BOOST_FWD_REF(Base) base, BOOST_FWD_REF(Arg0) arg0 + , BOOST_FWD_REF(Arg1) arg1, BOOST_FWD_REF(Arg2) arg2) + : DeriveFrom(::boost::forward<Base>(base) + , ::boost::forward<Arg0>(arg0) + , ::boost::forward<Arg1>(arg1) + , ::boost::forward<Arg2>(arg2)) + {} + typedef detail::size_holder < true, SizeType> size_traits;//size_traits + + size_traits size_traits_; + + const size_traits &priv_size_traits() const + { return size_traits_; } + + size_traits &priv_size_traits() + { return size_traits_; } +}; + +template<class DeriveFrom, class SizeType> +struct hashtable_size_traits_wrapper<DeriveFrom, SizeType, false> + : public DeriveFrom +{ + template<class Base, class Arg0, class Arg1, class Arg2> + hashtable_size_traits_wrapper( BOOST_FWD_REF(Base) base, BOOST_FWD_REF(Arg0) arg0 + , BOOST_FWD_REF(Arg1) arg1, BOOST_FWD_REF(Arg2) arg2) + : DeriveFrom(::boost::forward<Base>(base) + , ::boost::forward<Arg0>(arg0) + , ::boost::forward<Arg1>(arg1) + , ::boost::forward<Arg2>(arg2)) + {} + + typedef detail::size_holder< false, SizeType> size_traits; + + const size_traits &priv_size_traits() const + { return size_traits_; } + + size_traits &priv_size_traits() + { return size_traits_; } + + static size_traits size_traits_; +}; + +template<class DeriveFrom, class SizeType> +detail::size_holder< false, SizeType > hashtable_size_traits_wrapper<DeriveFrom, SizeType, false>::size_traits_; + //hashdata_internal //Stores bucket_hash_equal_t and split_traits -template<class SizeType, std::size_t BoolFlags, class VoidOrKeyHash, class VoidOrKeyEqual, class ValueTraits, class BucketTraits> +template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, class SizeType, std::size_t BoolFlags> struct hashdata_internal - : public detail::size_holder< 0 != (BoolFlags & hash_bool_flags::incremental_pos), SizeType, int> //split_traits + : public hashtable_size_traits_wrapper + < bucket_hash_equal_t + < ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual + , BucketTraits + , 0 != (BoolFlags & hash_bool_flags::cache_begin_pos) + > //2 + , SizeType + , (BoolFlags & hash_bool_flags::incremental_pos) != 0 + > { - typedef bucket_hash_equal_t - < VoidOrKeyHash, VoidOrKeyEqual - , ValueTraits, BucketTraits - , 0 != (BoolFlags & hash_bool_flags::cache_begin_pos) + typedef hashtable_size_traits_wrapper + < bucket_hash_equal_t + < ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual + , BucketTraits + , 0 != (BoolFlags & hash_bool_flags::cache_begin_pos) + > //2 + , SizeType + , (BoolFlags & hash_bool_flags::incremental_pos) != 0 > internal_type; - typedef typename internal_type::value_equal value_equal; + typedef typename internal_type::key_equal key_equal; typedef typename internal_type::hasher hasher; typedef bucket_plus_vtraits<ValueTraits,BucketTraits> bucket_plus_vtraits_t; typedef typename bucket_plus_vtraits_t::size_type size_type; + typedef typename internal_type::size_traits split_traits; typedef typename bucket_plus_vtraits_t::bucket_ptr bucket_ptr; - typedef detail::size_holder - <0 != (BoolFlags & hash_bool_flags::incremental_pos) - , SizeType, int> split_traits; - typedef typename bucket_plus_vtraits_t:: - value_traits::node_traits node_traits; - typedef detail::bool_<detail::optimize_multikey_is_true - <node_traits>::value> optimize_multikey_t; + typedef typename bucket_plus_vtraits_t::const_value_traits_ptr const_value_traits_ptr; + typedef typename bucket_plus_vtraits_t::siterator siterator; + typedef typename bucket_plus_vtraits_t::bucket_traits bucket_traits; + typedef typename bucket_plus_vtraits_t::value_traits value_traits; + typedef typename bucket_plus_vtraits_t::bucket_type bucket_type; + typedef typename value_traits::value_type value_type; + typedef typename value_traits::pointer pointer; + typedef typename value_traits::const_pointer const_pointer; + typedef typename pointer_traits<pointer>::reference reference; + typedef typename pointer_traits + <const_pointer>::reference const_reference; + typedef typename value_traits::node_traits node_traits; + typedef typename node_traits::node node; + typedef typename node_traits::node_ptr node_ptr; + typedef typename node_traits::const_node_ptr const_node_ptr; + typedef detail::node_functions<node_traits> node_functions_t; + typedef typename detail::get_slist_impl + <typename detail::reduced_slist_node_traits + <typename value_traits::node_traits>::type + >::type slist_impl; + typedef typename slist_impl::node_algorithms node_algorithms; + typedef typename slist_impl::node_ptr slist_node_ptr; + + typedef hash_key_types_base + < typename ValueTraits::value_type + , VoidOrKeyOfValue + > hash_types_base; + typedef typename hash_types_base::key_of_value key_of_value; + + static const bool store_hash = detail::store_hash_is_true<node_traits>::value; + static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; + static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; + + typedef detail::bool_<store_hash> store_hash_t; + + typedef detail::transform_iterator + < typename slist_impl::iterator + , downcast_node_to_value_t + < value_traits + , false> > local_iterator; + + typedef detail::transform_iterator + < typename slist_impl::iterator + , downcast_node_to_value_t + < value_traits + , true> > const_local_iterator; + // template<class BucketTraitsType> hashdata_internal( const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits - , const hasher & h, const value_equal &e) - : internal(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h, e) + , const hasher & h, const key_equal &e) + : internal_type(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h, e) {} split_traits &priv_split_traits() - { return *this; } + { return this->priv_size_traits(); } const split_traits &priv_split_traits() const - { return *this; } + { return this->priv_size_traits(); } ~hashdata_internal() { this->priv_clear_buckets(); } void priv_clear_buckets() { - this->internal.internal.internal.priv_clear_buckets - ( this->internal.priv_get_cache() - , this->internal.internal.internal.priv_bucket_count() - - (this->internal.priv_get_cache() - - this->internal.internal.internal.priv_bucket_pointer())); + this->internal_type::priv_clear_buckets + ( this->priv_get_cache() + , this->internal_type::priv_bucket_count() + - (this->priv_get_cache() + - this->internal_type::priv_bucket_pointer())); } void priv_clear_buckets_and_cache() { this->priv_clear_buckets(); - this->internal.priv_initialize_cache(); + this->priv_initialize_cache(); } void priv_initialize_buckets_and_cache() { - this->internal.internal.internal.priv_clear_buckets - ( this->internal.internal.internal.priv_bucket_pointer() - , this->internal.internal.internal.priv_bucket_count()); - this->internal.priv_initialize_cache(); + this->internal_type::priv_clear_buckets + ( this->internal_type::priv_bucket_pointer() + , this->internal_type::priv_bucket_count()); + this->priv_initialize_cache(); } - internal_type internal; //2 -}; + typedef hashtable_iterator<bucket_plus_vtraits_t, false> iterator; + typedef hashtable_iterator<bucket_plus_vtraits_t, true> const_iterator; -//hashtable_data_t -//Stores hashdata_internal and size_traits -template<class SizeType, std::size_t BoolFlags, class VoidOrKeyHash, class VoidOrKeyEqual, class ValueTraits, class BucketTraits> -struct hashtable_data_t - : public detail::size_holder - < 0 != (BoolFlags & hash_bool_flags::constant_time_size_pos), SizeType> //size_traits -{ - typedef detail::size_holder - < 0 != (BoolFlags & hash_bool_flags::constant_time_size_pos) - , SizeType> size_traits; - typedef hashdata_internal - < SizeType - , BoolFlags & (hash_bool_flags::incremental_pos | hash_bool_flags::cache_begin_pos) - , VoidOrKeyHash, VoidOrKeyEqual - , ValueTraits, BucketTraits> internal_type; - typedef ValueTraits value_traits; - typedef typename internal_type::value_equal value_equal; - typedef typename internal_type::hasher hasher; - typedef BucketTraits bucket_traits; - typedef bucket_plus_vtraits - <ValueTraits,BucketTraits> bucket_plus_vtraits_t; + static std::size_t priv_stored_hash(slist_node_ptr n, detail::true_ true_value) + { return bucket_plus_vtraits<ValueTraits, BucketTraits>::priv_stored_hash(n, true_value); } - template<class BucketTraitsType> - hashtable_data_t( BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h - , const value_equal &e, const value_traits &val_traits) - : internal(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h, e) - {} + static std::size_t priv_stored_hash(slist_node_ptr n, detail::false_ false_value) + { return bucket_plus_vtraits<ValueTraits, BucketTraits>::priv_stored_hash(n, false_value); } + + //public functions + SizeType split_count() const + { + return this->priv_split_traits().get_size(); + } + + iterator iterator_to(reference value) + { + return iterator(bucket_type::s_iterator_to + (this->priv_value_to_node(value)), &this->get_bucket_value_traits()); + } + + const_iterator iterator_to(const_reference value) const + { + siterator const sit = bucket_type::s_iterator_to + ( *pointer_traits<node_ptr>::const_cast_from + (pointer_traits<const_node_ptr>::pointer_to(this->priv_value_to_node(value))) + ); + return const_iterator(sit, &this->get_bucket_value_traits()); + } + + static local_iterator s_local_iterator_to(reference value) + { + BOOST_STATIC_ASSERT((!stateful_value_traits)); + siterator sit = bucket_type::s_iterator_to(*value_traits::to_node_ptr(value)); + return local_iterator(sit, const_value_traits_ptr()); + } + + static const_local_iterator s_local_iterator_to(const_reference value) + { + BOOST_STATIC_ASSERT((!stateful_value_traits)); + siterator const sit = bucket_type::s_iterator_to + ( *pointer_traits<node_ptr>::const_cast_from + (value_traits::to_node_ptr(value)) + ); + return const_local_iterator(sit, const_value_traits_ptr()); + } + + local_iterator local_iterator_to(reference value) + { + siterator sit = bucket_type::s_iterator_to(this->priv_value_to_node(value)); + return local_iterator(sit, this->priv_value_traits_ptr()); + } + + const_local_iterator local_iterator_to(const_reference value) const + { + siterator sit = bucket_type::s_iterator_to + ( *pointer_traits<node_ptr>::const_cast_from + (pointer_traits<const_node_ptr>::pointer_to(this->priv_value_to_node(value))) + ); + return const_local_iterator(sit, this->priv_value_traits_ptr()); + } + + size_type bucket_count() const + { return this->priv_bucket_count(); } - internal_type internal; //1 + size_type bucket_size(size_type n) const + { return this->priv_bucket_pointer()[n].size(); } + + bucket_ptr bucket_pointer() const + { return this->priv_bucket_pointer(); } + + local_iterator begin(size_type n) + { return local_iterator(this->priv_bucket_pointer()[n].begin(), this->priv_value_traits_ptr()); } + + const_local_iterator begin(size_type n) const + { return this->cbegin(n); } + + const_local_iterator cbegin(size_type n) const + { + return const_local_iterator + ( pointer_traits<bucket_ptr>::const_cast_from(this->priv_bucket_pointer())[n].begin() + , this->priv_value_traits_ptr()); + } + + using internal_type::end; + using internal_type::cend; + local_iterator end(size_type n) + { return local_iterator(this->priv_bucket_pointer()[n].end(), this->priv_value_traits_ptr()); } + + const_local_iterator end(size_type n) const + { return this->cend(n); } + + const_local_iterator cend(size_type n) const + { + return const_local_iterator + ( pointer_traits<bucket_ptr>::const_cast_from(this->priv_bucket_pointer())[n].end() + , this->priv_value_traits_ptr()); + } + + //Public functions for hashtable_impl + + iterator begin() + { return iterator(this->priv_begin(), &this->get_bucket_value_traits()); } + + const_iterator begin() const + { return this->cbegin(); } + + const_iterator cbegin() const + { return const_iterator(this->priv_begin(), &this->get_bucket_value_traits()); } + + hasher hash_function() const + { return this->priv_hasher(); } + + key_equal key_eq() const + { return this->priv_equal(); } }; /// @endcond @@ -1175,61 +1550,82 @@ struct hashtable_data_t #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class ValueTraits, class VoidOrKeyHash, class VoidOrKeyEqual, class SizeType, class BucketTraits, std::size_t BoolFlags> +template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, class SizeType, std::size_t BoolFlags> #endif class hashtable_impl - : private hashtable_data_t - < SizeType - , BoolFlags & hashtable_data_bool_flags_mask - , VoidOrKeyHash, VoidOrKeyEqual, ValueTraits, BucketTraits> + : private hashtable_size_traits_wrapper + < hashdata_internal + < ValueTraits + , VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual + , BucketTraits, SizeType + , BoolFlags & (hash_bool_flags::incremental_pos | hash_bool_flags::cache_begin_pos) //1 + > + , SizeType + , (BoolFlags & hash_bool_flags::constant_time_size_pos) != 0 + > { - typedef hashtable_data_t - < SizeType - , BoolFlags & hashtable_data_bool_flags_mask - , VoidOrKeyHash, VoidOrKeyEqual, ValueTraits, BucketTraits> data_type; - + typedef hashtable_size_traits_wrapper + < hashdata_internal + < ValueTraits + , VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual + , BucketTraits, SizeType + , BoolFlags & (hash_bool_flags::incremental_pos | hash_bool_flags::cache_begin_pos) //1 + > + , SizeType + , (BoolFlags & hash_bool_flags::constant_time_size_pos) != 0 + > internal_type; + typedef typename internal_type::size_traits size_traits; + typedef hash_key_types_base + < typename ValueTraits::value_type + , VoidOrKeyOfValue + > hash_types_base; public: typedef ValueTraits value_traits; /// @cond typedef BucketTraits bucket_traits; - typedef typename detail::get_slist_impl - <typename detail::reduced_slist_node_traits - <typename value_traits::node_traits>::type - >::type slist_impl; + typedef typename internal_type::slist_impl slist_impl; typedef bucket_plus_vtraits<ValueTraits, BucketTraits> bucket_plus_vtraits_t; typedef typename bucket_plus_vtraits_t::const_value_traits_ptr const_value_traits_ptr; + using internal_type::begin; + using internal_type::cbegin; + using internal_type::end; + using internal_type::cend; + using internal_type::hash_function; + using internal_type::key_eq; + using internal_type::bucket_size; + using internal_type::bucket_count; + using internal_type::local_iterator_to; + using internal_type::s_local_iterator_to; + using internal_type::iterator_to; + using internal_type::bucket_pointer; + using internal_type::suggested_upper_bucket_count; + using internal_type::suggested_lower_bucket_count; + using internal_type::split_count; /// @endcond typedef typename value_traits::pointer pointer; typedef typename value_traits::const_pointer const_pointer; typedef typename value_traits::value_type value_type; + typedef typename hash_types_base::key_type key_type; + typedef typename hash_types_base::key_of_value key_of_value; typedef typename pointer_traits<pointer>::reference reference; typedef typename pointer_traits<const_pointer>::reference const_reference; typedef typename pointer_traits<pointer>::difference_type difference_type; typedef SizeType size_type; - typedef value_type key_type; - typedef typename data_type::value_equal key_equal; - typedef typename data_type::value_equal value_equal; - typedef typename data_type::hasher hasher; + typedef typename internal_type::key_equal key_equal; + typedef typename internal_type::hasher hasher; typedef detail::bucket_impl<slist_impl> bucket_type; - typedef typename pointer_traits - <pointer>::template rebind_pointer - < bucket_type >::type bucket_ptr; - typedef typename pointer_traits - <pointer>::template rebind_pointer - < const bucket_type >::type const_bucket_ptr; - typedef typename pointer_traits - <bucket_ptr>::reference bucket_reference; - typedef typename pointer_traits - <bucket_ptr>::reference const_bucket_reference; + typedef typename internal_type::bucket_ptr bucket_ptr; typedef typename slist_impl::iterator siterator; typedef typename slist_impl::const_iterator const_siterator; - typedef hashtable_iterator<bucket_plus_vtraits_t, false> iterator; - typedef hashtable_iterator<bucket_plus_vtraits_t, true> const_iterator; + typedef typename internal_type::iterator iterator; + typedef typename internal_type::const_iterator const_iterator; + typedef typename internal_type::local_iterator local_iterator; + typedef typename internal_type::const_local_iterator const_local_iterator; typedef typename value_traits::node_traits node_traits; typedef typename node_traits::node node; typedef typename pointer_traits @@ -1244,8 +1640,8 @@ class hashtable_impl <const_node_ptr>::reference const_node_reference; typedef typename slist_impl::node_algorithms node_algorithms; - static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; - static const bool store_hash = detail::store_hash_is_true<node_traits>::value; + static const bool stateful_value_traits = internal_type::stateful_value_traits; + static const bool store_hash = internal_type::store_hash; static const bool unique_keys = 0 != (BoolFlags & hash_bool_flags::unique_keys_pos); static const bool constant_time_size = 0 != (BoolFlags & hash_bool_flags::constant_time_size_pos); @@ -1258,6 +1654,7 @@ class hashtable_impl = detail::optimize_multikey_is_true<node_traits>::value && !unique_keys; /// @cond + static const bool is_multikey = !unique_keys; private: //Configuration error: compare_hash<> can't be specified without store_hash<> @@ -1272,12 +1669,11 @@ class hashtable_impl //optimize_multikey is not true typedef unordered_group_adapter<node_traits> group_traits; typedef circular_slist_algorithms<group_traits> group_algorithms; - typedef detail::bool_<store_hash> store_hash_t; + typedef typename internal_type::store_hash_t store_hash_t; typedef detail::bool_<optimize_multikey> optimize_multikey_t; typedef detail::bool_<cache_begin> cache_begin_t; typedef detail::bool_<power_2_buckets> power_2_buckets_t; - typedef detail::size_holder<constant_time_size, size_type> size_traits; - typedef detail::size_holder<incremental, size_type, int> split_traits; + typedef typename internal_type::split_traits split_traits; typedef detail::group_functions<node_traits> group_functions_t; typedef detail::node_functions<node_traits> node_functions_t; @@ -1285,7 +1681,7 @@ class hashtable_impl //noncopyable, movable BOOST_MOVABLE_BUT_NOT_COPYABLE(hashtable_impl) - static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; + static const bool safemode_or_autounlink = internal_type::safemode_or_autounlink; //Constant-time size is incompatible with auto-unlink hooks! BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink))); @@ -1293,14 +1689,19 @@ class hashtable_impl BOOST_STATIC_ASSERT(!(cache_begin && ((int)value_traits::link_mode == (int)auto_unlink))); template<class Disposer> - node_cast_adaptor< detail::node_disposer<Disposer, value_traits, CircularSListAlgorithms> - , slist_node_ptr, node_ptr > + struct typeof_node_disposer + { + typedef node_cast_adaptor + < detail::node_disposer< Disposer, value_traits, CircularSListAlgorithms> + , slist_node_ptr, node_ptr > type; + }; + + template<class Disposer> + typename typeof_node_disposer<Disposer>::type make_node_disposer(const Disposer &disposer) const { - return node_cast_adaptor - < detail::node_disposer<Disposer, value_traits, CircularSListAlgorithms> - , slist_node_ptr, node_ptr > - (disposer, &this->priv_value_traits()); + typedef typename typeof_node_disposer<Disposer>::type return_t; + return return_t(disposer, &this->priv_value_traits()); } /// @endcond @@ -1308,17 +1709,6 @@ class hashtable_impl public: typedef detail::insert_commit_data_impl insert_commit_data; - typedef detail::transform_iterator - < typename slist_impl::iterator - , downcast_node_to_value_t - < value_traits - , false> > local_iterator; - - typedef detail::transform_iterator - < typename slist_impl::iterator - , downcast_node_to_value_t - < value_traits - , true> > const_local_iterator; public: @@ -1339,9 +1729,42 @@ class hashtable_impl , const hasher & hash_func = hasher() , const key_equal &equal_func = key_equal() , const value_traits &v_traits = value_traits()) - : data_type(b_traits, hash_func, equal_func, v_traits) + : internal_type(v_traits, b_traits, hash_func, equal_func) { - this->data_type::internal.priv_initialize_buckets_and_cache(); + this->priv_initialize_buckets_and_cache(); + this->priv_size_traits().set_size(size_type(0)); + size_type bucket_sz = this->priv_bucket_count(); + BOOST_INTRUSIVE_INVARIANT_ASSERT(bucket_sz != 0); + //Check power of two bucket array if the option is activated + BOOST_INTRUSIVE_INVARIANT_ASSERT + (!power_2_buckets || (0 == (bucket_sz & (bucket_sz-1)))); + this->priv_split_traits().set_size(bucket_sz>>1); + } + + //! <b>Requires</b>: buckets must not be being used by any other resource + //! and dereferencing iterator must yield an lvalue of type value_type. + //! + //! <b>Effects</b>: Constructs an empty container and inserts elements from + //! [b, e). + //! + //! <b>Complexity</b>: If N is distance(b, e): Average case is O(N) + //! (with a good hash function and with buckets_len >= N),worst case O(N^2). + //! + //! <b>Throws</b>: If value_traits::node_traits::node + //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) + //! or the copy constructor or invocation of hasher or key_equal throws. + //! + //! <b>Notes</b>: buckets array must be disposed only after + //! *this is disposed. + template<class Iterator> + hashtable_impl ( bool unique, Iterator b, Iterator e + , const bucket_traits &b_traits + , const hasher & hash_func = hasher() + , const key_equal &equal_func = key_equal() + , const value_traits &v_traits = value_traits()) + : internal_type(v_traits, b_traits, hash_func, equal_func) + { + this->priv_initialize_buckets_and_cache(); this->priv_size_traits().set_size(size_type(0)); size_type bucket_sz = this->priv_bucket_count(); BOOST_INTRUSIVE_INVARIANT_ASSERT(bucket_sz != 0); @@ -1349,16 +1772,21 @@ class hashtable_impl BOOST_INTRUSIVE_INVARIANT_ASSERT (!power_2_buckets || (0 == (bucket_sz & (bucket_sz-1)))); this->priv_split_traits().set_size(bucket_sz>>1); + //Now insert + if(unique) + this->insert_unique(b, e); + else + this->insert_equal(b, e); } //! <b>Effects</b>: to-do //! hashtable_impl(BOOST_RV_REF(hashtable_impl) x) - : data_type( ::boost::move(x.priv_bucket_traits()) - , ::boost::move(x.priv_hasher()) - , ::boost::move(x.priv_equal()) - , ::boost::move(x.priv_value_traits()) - ) + : internal_type( ::boost::move(x.priv_value_traits()) + , ::boost::move(x.priv_bucket_traits()) + , ::boost::move(x.priv_hasher()) + , ::boost::move(x.priv_equal()) + ) { this->priv_swap_cache(x); x.priv_initialize_cache(); @@ -1387,7 +1815,6 @@ class hashtable_impl //! //! <b>Throws</b>: Nothing. ~hashtable_impl(); - #endif //! <b>Effects</b>: Returns an iterator pointing to the beginning of the unordered_set. //! @@ -1395,8 +1822,7 @@ class hashtable_impl //! Worst case (empty unordered_set): O(this->bucket_count()) //! //! <b>Throws</b>: Nothing. - iterator begin() - { return iterator(this->priv_begin(), &this->get_bucket_value_traits()); } + iterator begin(); //! <b>Effects</b>: Returns a const_iterator pointing to the beginning //! of the unordered_set. @@ -1405,8 +1831,7 @@ class hashtable_impl //! Worst case (empty unordered_set): O(this->bucket_count()) //! //! <b>Throws</b>: Nothing. - const_iterator begin() const - { return this->cbegin(); } + const_iterator begin() const; //! <b>Effects</b>: Returns a const_iterator pointing to the beginning //! of the unordered_set. @@ -1415,48 +1840,44 @@ class hashtable_impl //! Worst case (empty unordered_set): O(this->bucket_count()) //! //! <b>Throws</b>: Nothing. - const_iterator cbegin() const - { return const_iterator(this->priv_begin(), &this->get_bucket_value_traits()); } + const_iterator cbegin() const; //! <b>Effects</b>: Returns an iterator pointing to the end of the unordered_set. //! //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - iterator end() - { return iterator(this->priv_invalid_local_it(), 0); } + iterator end(); //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set. //! //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - const_iterator end() const - { return this->cend(); } + const_iterator end() const; //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set. //! //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - const_iterator cend() const - { return const_iterator(this->priv_invalid_local_it(), 0); } + const_iterator cend() const; //! <b>Effects</b>: Returns the hasher object used by the unordered_set. //! //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: If hasher copy-constructor throws. - hasher hash_function() const - { return this->priv_hasher(); } + hasher hash_function() const; //! <b>Effects</b>: Returns the key_equal object used by the unordered_set. //! //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: If key_equal copy-constructor throws. - key_equal key_eq() const - { return this->priv_equal(); } + key_equal key_eq() const; + + #endif //! <b>Effects</b>: Returns true if the container is empty. //! @@ -1525,16 +1946,8 @@ class hashtable_impl ::boost::adl_move_swap(this->priv_bucket_traits(), other.priv_bucket_traits()); ::boost::adl_move_swap(this->priv_value_traits(), other.priv_value_traits()); this->priv_swap_cache(other); - if(constant_time_size){ - size_type backup = this->priv_size_traits().get_size(); - this->priv_size_traits().set_size(other.priv_size_traits().get_size()); - other.priv_size_traits().set_size(backup); - } - if(incremental){ - size_type backup = this->priv_split_traits().get_size(); - this->priv_split_traits().set_size(other.priv_split_traits().get_size()); - other.priv_split_traits().set_size(backup); - } + ::boost::adl_move_swap(this->priv_size_traits(), other.priv_size_traits()); + ::boost::adl_move_swap(this->priv_split_traits(), other.priv_split_traits()); } //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw @@ -1558,87 +1971,30 @@ class hashtable_impl //! throws. Basic guarantee. template <class Cloner, class Disposer> void clone_from(const hashtable_impl &src, Cloner cloner, Disposer disposer) - { - this->clear_and_dispose(disposer); - if(!constant_time_size || !src.empty()){ - const size_type src_bucket_count = src.bucket_count(); - const size_type dst_bucket_count = this->bucket_count(); - //Check power of two bucket array if the option is activated - BOOST_INTRUSIVE_INVARIANT_ASSERT - (!power_2_buckets || (0 == (src_bucket_count & (src_bucket_count-1)))); - BOOST_INTRUSIVE_INVARIANT_ASSERT - (!power_2_buckets || (0 == (dst_bucket_count & (dst_bucket_count-1)))); + { this->priv_clone_from(src, cloner, disposer); } - //If src bucket count is bigger or equal, structural copy is possible - if(!incremental && (src_bucket_count >= dst_bucket_count)){ - //First clone the first ones - const bucket_ptr src_buckets = src.priv_bucket_pointer(); - const bucket_ptr dst_buckets = this->priv_bucket_pointer(); - size_type constructed; - - typedef node_cast_adaptor< detail::node_disposer<Disposer, value_traits, CircularSListAlgorithms> - , slist_node_ptr, node_ptr > NodeDisposer; - typedef node_cast_adaptor< detail::node_cloner <Cloner, value_traits, CircularSListAlgorithms> - , slist_node_ptr, node_ptr > NodeCloner; - NodeDisposer node_disp(disposer, &this->priv_value_traits()); - - detail::exception_array_disposer<bucket_type, NodeDisposer, size_type> - rollback(dst_buckets[0], node_disp, constructed); - for( constructed = 0 - ; constructed < dst_bucket_count - ; ++constructed){ - dst_buckets[constructed].clone_from - ( src_buckets[constructed] - , NodeCloner(cloner, &this->priv_value_traits()), node_disp); - } - if(src_bucket_count != dst_bucket_count){ - //Now insert the remaining ones using the modulo trick - for(//"constructed" comes from the previous loop - ; constructed < src_bucket_count - ; ++constructed){ - bucket_type &dst_b = - dst_buckets[detail::hash_to_bucket_split<power_2_buckets, incremental>(constructed, dst_bucket_count, dst_bucket_count)]; - bucket_type &src_b = src_buckets[constructed]; - for( siterator b(src_b.begin()), e(src_b.end()) - ; b != e - ; ++b){ - dst_b.push_front(*(NodeCloner(cloner, &this->priv_value_traits())(*b.pointed_node()))); - } - } - } - this->priv_hasher() = src.priv_hasher(); - this->priv_equal() = src.priv_equal(); - rollback.release(); - this->priv_size_traits().set_size(src.priv_size_traits().get_size()); - this->priv_split_traits().set_size(dst_bucket_count); - this->priv_insertion_update_cache(0u); - this->priv_erasure_update_cache(); - } - else if(store_hash){ - //Unlike previous cloning algorithm, this can throw - //if cloner, hasher or comparison functor throw - const_iterator b(src.cbegin()), e(src.cend()); - detail::exception_disposer<hashtable_impl, Disposer> - rollback(*this, disposer); - for(; b != e; ++b){ - std::size_t hash_value = this->priv_stored_or_compute_hash(*b, store_hash_t());; - this->priv_insert_equal_with_hash(*cloner(*b), hash_value); - } - rollback.release(); - } - else{ - //Unlike previous cloning algorithm, this can throw - //if cloner, hasher or comparison functor throw - const_iterator b(src.cbegin()), e(src.cend()); - detail::exception_disposer<hashtable_impl, Disposer> - rollback(*this, disposer); - for(; b != e; ++b){ - this->insert_equal(*cloner(*b)); - } - rollback.release(); - } - } - } + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw + //! Cloner should yield to nodes that compare equal and produce the same + //! hash than the original node. + //! + //! <b>Effects</b>: Erases all the elements from *this + //! calling Disposer::operator()(pointer), clones all the + //! elements from src calling Cloner::operator()(reference) + //! and inserts them on *this. The hash function and the equality + //! predicate are copied from the source. + //! + //! If store_hash option is true, this method does not use the hash function. + //! + //! If any operation throws, all cloned elements are unlinked and disposed + //! calling Disposer::operator()(pointer). + //! + //! <b>Complexity</b>: Linear to erased plus inserted elements. + //! + //! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying + //! throws. Basic guarantee. + template <class Cloner, class Disposer> + void clone_from(BOOST_RV_REF(hashtable_impl) src, Cloner cloner, Disposer disposer) + { this->priv_clone_from(static_cast<hashtable_impl&>(src), cloner, disposer); } //! <b>Requires</b>: value must be an lvalue //! @@ -1657,9 +2013,10 @@ class hashtable_impl size_type bucket_num; std::size_t hash_value; siterator prev; - siterator it = this->priv_find - (value, this->priv_hasher(), this->priv_equal(), bucket_num, hash_value, prev); - return this->priv_insert_equal_find(value, bucket_num, hash_value, it); + siterator const it = this->priv_find + (key_of_value()(value), this->priv_hasher(), this->priv_equal(), bucket_num, hash_value, prev); + bool const next_is_in_group = optimize_multikey && it != this->priv_invalid_local_it(); + return this->priv_insert_equal_after_find(value, bucket_num, hash_value, prev, next_is_in_group); } //! <b>Requires</b>: Dereferencing iterator must yield an lvalue @@ -1701,11 +2058,11 @@ class hashtable_impl { insert_commit_data commit_data; std::pair<iterator, bool> ret = this->insert_unique_check - (value, this->priv_hasher(), this->priv_equal(), commit_data); - if(!ret.second) - return ret; - return std::pair<iterator, bool> - (this->insert_unique_commit(value, commit_data), true); + (key_of_value()(value), this->priv_hasher(), this->priv_equal(), commit_data); + if(ret.second){ + ret.first = this->insert_unique_commit(value, commit_data); + } + return ret; } //! <b>Requires</b>: Dereferencing iterator must yield an lvalue @@ -1762,22 +2119,19 @@ class hashtable_impl //! objects are inserted or erased from the unordered_set. //! //! After a successful rehashing insert_commit_data remains valid. - template<class KeyType, class KeyHasher, class KeyValueEqual> + template<class KeyType, class KeyHasher, class KeyEqual> std::pair<iterator, bool> insert_unique_check ( const KeyType &key , KeyHasher hash_func - , KeyValueEqual equal_func + , KeyEqual equal_func , insert_commit_data &commit_data) { size_type bucket_num; siterator prev; - siterator prev_pos = - this->priv_find(key, hash_func, equal_func, bucket_num, commit_data.hash, prev); - bool success = prev_pos == this->priv_invalid_local_it(); - if(success){ - prev_pos = prev; - } - return std::pair<iterator, bool>(iterator(prev_pos, &this->get_bucket_value_traits()),success); + siterator const pos = this->priv_find(key, hash_func, equal_func, bucket_num, commit_data.hash, prev); + return std::pair<iterator, bool> + ( iterator(pos, &this->get_bucket_value_traits()) + , pos == this->priv_invalid_local_it()); } //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data @@ -1804,12 +2158,11 @@ class hashtable_impl size_type bucket_num = this->priv_hash_to_bucket(commit_data.hash); bucket_type &b = this->priv_bucket_pointer()[bucket_num]; this->priv_size_traits().increment(); - node_ptr n = pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(value)); + node_ptr const n = pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(value)); + BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(n)); node_functions_t::store_hash(n, commit_data.hash, store_hash_t()); - if(safemode_or_autounlink) - BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n)); this->priv_insertion_update_cache(bucket_num); - group_functions_t::insert_in_group(node_ptr(), n, optimize_multikey_t()); + group_functions_t::insert_in_group(n, n, optimize_multikey_t()); return iterator(b.insert_after(b.before_begin(), *n), &this->get_bucket_value_traits()); } @@ -1848,8 +2201,8 @@ class hashtable_impl //! //! <b>Note</b>: Invalidates the iterators (but not the references) //! to the erased elements. No destructors are called. - size_type erase(const_reference value) - { return this->erase(value, this->priv_hasher(), this->priv_equal()); } + size_type erase(const key_type &key) + { return this->erase(key, this->priv_hasher(), this->priv_equal()); } //! <b>Requires</b>: "hash_func" must be a hash function that induces //! the same hash values as the stored hasher. The difference is that @@ -1871,8 +2224,8 @@ class hashtable_impl //! //! <b>Note</b>: Invalidates the iterators (but not the references) //! to the erased elements. No destructors are called. - template<class KeyType, class KeyHasher, class KeyValueEqual> - size_type erase(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) + template<class KeyType, class KeyHasher, class KeyEqual> + size_type erase(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func) { return this->erase_and_dispose(key, hash_func, equal_func, detail::null_disposer()); } //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. @@ -1887,15 +2240,16 @@ class hashtable_impl //! <b>Note</b>: Invalidates the iterators //! to the erased elements. template<class Disposer> - void erase_and_dispose(const_iterator i, Disposer disposer - /// @cond - , typename detail::enable_if_c<!detail::is_convertible<Disposer, const_iterator>::value >::type * = 0 - /// @endcond - ) - { - this->priv_erase(i, disposer, optimize_multikey_t()); + BOOST_INTRUSIVE_DOC1ST(void + , typename detail::disable_if_convertible<Disposer BOOST_INTRUSIVE_I const_iterator>::type) + erase_and_dispose(const_iterator i, Disposer disposer) + { + //Get the bucket number and local iterator for both iterators + siterator const first_local_it(i.slist_it()); + size_type const first_bucket_num = this->priv_get_bucket_num(first_local_it); + this->priv_erase_node(this->priv_bucket_pointer()[first_bucket_num], first_local_it, make_node_disposer(disposer), optimize_multikey_t()); this->priv_size_traits().decrement(); - this->priv_erasure_update_cache(); + this->priv_erasure_update_cache_range(first_bucket_num, first_bucket_num); } //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. @@ -1934,7 +2288,10 @@ class hashtable_impl last_local_it = e.slist_it(); last_bucket_num = this->priv_get_bucket_num(last_local_it); } - this->priv_erase_range(before_first_local_it, first_bucket_num, last_local_it, last_bucket_num, disposer); + size_type const num_erased = this->priv_erase_node_range + ( before_first_local_it, first_bucket_num, last_local_it, last_bucket_num + , make_node_disposer(disposer), optimize_multikey_t()); + this->priv_size_traits().set_size(this->priv_size_traits().get_size()-num_erased); this->priv_erasure_update_cache_range(first_bucket_num, last_bucket_num); } } @@ -1955,8 +2312,8 @@ class hashtable_impl //! <b>Note</b>: Invalidates the iterators (but not the references) //! to the erased elements. No destructors are called. template<class Disposer> - size_type erase_and_dispose(const_reference value, Disposer disposer) - { return this->erase_and_dispose(value, this->priv_hasher(), this->priv_equal(), disposer); } + size_type erase_and_dispose(const key_type &key, Disposer disposer) + { return this->erase_and_dispose(key, this->priv_hasher(), this->priv_equal(), disposer); } //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. //! @@ -1973,45 +2330,37 @@ class hashtable_impl //! //! <b>Note</b>: Invalidates the iterators //! to the erased elements. - template<class KeyType, class KeyHasher, class KeyValueEqual, class Disposer> + template<class KeyType, class KeyHasher, class KeyEqual, class Disposer> size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func - ,KeyValueEqual equal_func, Disposer disposer) + ,KeyEqual equal_func, Disposer disposer) { size_type bucket_num; std::size_t h; siterator prev; siterator it = this->priv_find(key, hash_func, equal_func, bucket_num, h, prev); - bool success = it != this->priv_invalid_local_it(); + bool const success = it != this->priv_invalid_local_it(); + size_type cnt(0); - if(!success){ - return 0; - } - else if(optimize_multikey){ - siterator last = bucket_type::s_iterator_to - (*node_traits::get_next(group_functions_t::get_last_in_group - (detail::dcast_bucket_ptr<node>(it.pointed_node()), optimize_multikey_t()))); - this->priv_erase_range_impl(bucket_num, prev, last, disposer, cnt); - } - else{ - //If found erase all equal values - bucket_type &b = this->priv_bucket_pointer()[bucket_num]; - for(siterator end_sit = b.end(); it != end_sit; ++cnt, ++it){ - slist_node_ptr n(it.pointed_node()); - const value_type &v = this->priv_value_from_slist_node(n); - if(compare_hash){ - std::size_t vh = this->priv_stored_or_compute_hash(v, store_hash_t()); - if(h != vh || !equal_func(key, v)){ - break; - } - } - else if(!equal_func(key, v)){ - break; - } - this->priv_size_traits().decrement(); + if(success){ + if(optimize_multikey){ + cnt = this->priv_erase_from_single_bucket + (this->priv_bucket_pointer()[bucket_num], prev, ++(priv_last_in_group)(it), make_node_disposer(disposer), optimize_multikey_t()); } - b.erase_after_and_dispose(prev, it, make_node_disposer(disposer)); + else{ + bucket_type &b = this->priv_bucket_pointer()[bucket_num]; + siterator const end_sit = b.end(); + do{ + ++cnt; + ++it; + }while(it != end_sit && + this->priv_is_value_equal_to_key + (this->priv_value_from_slist_node(it.pointed_node()), h, key, equal_func)); + bucket_type::s_erase_after_and_dispose(prev, it, make_node_disposer(disposer)); + } + this->priv_size_traits().set_size(this->priv_size_traits().get_size()-cnt); + this->priv_erasure_update_cache(); } - this->priv_erasure_update_cache(); + return cnt; } @@ -2026,7 +2375,7 @@ class hashtable_impl //! to the erased elements. No destructors are called. void clear() { - this->data_type::internal.priv_clear_buckets_and_cache(); + this->priv_clear_buckets_and_cache(); this->priv_size_traits().set_size(size_type(0)); } @@ -2047,8 +2396,9 @@ class hashtable_impl if(!constant_time_size || !this->empty()){ size_type num_buckets = this->bucket_count(); bucket_ptr b = this->priv_bucket_pointer(); + typename typeof_node_disposer<Disposer>::type d(disposer, &this->priv_value_traits()); for(; num_buckets--; ++b){ - b->clear_and_dispose(make_node_disposer(disposer)); + b->clear_and_dispose(d); } this->priv_size_traits().set_size(size_type(0)); } @@ -2060,8 +2410,8 @@ class hashtable_impl //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). //! //! <b>Throws</b>: If the internal hasher or the equality functor throws. - size_type count(const_reference value) const - { return this->count(value, this->priv_hasher(), this->priv_equal()); } + size_type count(const key_type &key) const + { return this->count(key, this->priv_hasher(), this->priv_equal()); } //! <b>Requires</b>: "hash_func" must be a hash function that induces //! the same hash values as the stored hasher. The difference is that @@ -2076,11 +2426,12 @@ class hashtable_impl //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). //! //! <b>Throws</b>: If hash_func or equal throw. - template<class KeyType, class KeyHasher, class KeyValueEqual> - size_type count(const KeyType &key, const KeyHasher &hash_func, const KeyValueEqual &equal_func) const + template<class KeyType, class KeyHasher, class KeyEqual> + size_type count(const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const { - size_type bucket_n1, bucket_n2, cnt; - this->priv_equal_range(key, hash_func, equal_func, bucket_n1, bucket_n2, cnt); + size_type cnt; + size_type n_bucket; + this->priv_local_equal_range(key, hash_func, equal_func, n_bucket, cnt); return cnt; } @@ -2090,8 +2441,8 @@ class hashtable_impl //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). //! //! <b>Throws</b>: If the internal hasher or the equality functor throws. - iterator find(const_reference value) - { return this->find(value, this->priv_hasher(), this->priv_equal()); } + iterator find(const key_type &key) + { return this->find(key, this->priv_hasher(), this->priv_equal()); } //! <b>Requires</b>: "hash_func" must be a hash function that induces //! the same hash values as the stored hasher. The difference is that @@ -2112,14 +2463,14 @@ class hashtable_impl //! <b>Note</b>: This function is used when constructing a value_type //! is expensive and the value_type can be compared with a cheaper //! key type. Usually this key is part of the value_type. - template<class KeyType, class KeyHasher, class KeyValueEqual> - iterator find(const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) + template<class KeyType, class KeyHasher, class KeyEqual> + iterator find(const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) { size_type bucket_n; std::size_t hash; siterator prev; - siterator local_it = this->priv_find(key, hash_func, equal_func, bucket_n, hash, prev); - return iterator(local_it, &this->get_bucket_value_traits()); + return iterator( this->priv_find(key, hash_func, equal_func, bucket_n, hash, prev) + , &this->get_bucket_value_traits()); } //! <b>Effects</b>: Finds a const_iterator to the first element whose key is @@ -2128,8 +2479,8 @@ class hashtable_impl //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). //! //! <b>Throws</b>: If the internal hasher or the equality functor throws. - const_iterator find(const_reference value) const - { return this->find(value, this->priv_hasher(), this->priv_equal()); } + const_iterator find(const key_type &key) const + { return this->find(key, this->priv_hasher(), this->priv_equal()); } //! <b>Requires</b>: "hash_func" must be a hash function that induces //! the same hash values as the stored hasher. The difference is that @@ -2150,15 +2501,15 @@ class hashtable_impl //! <b>Note</b>: This function is used when constructing a value_type //! is expensive and the value_type can be compared with a cheaper //! key type. Usually this key is part of the value_type. - template<class KeyType, class KeyHasher, class KeyValueEqual> + template<class KeyType, class KeyHasher, class KeyEqual> const_iterator find - (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) const + (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const { size_type bucket_n; std::size_t hash_value; siterator prev; - siterator sit = this->priv_find(key, hash_func, equal_func, bucket_n, hash_value, prev); - return const_iterator(sit, &this->get_bucket_value_traits()); + return const_iterator( this->priv_find(key, hash_func, equal_func, bucket_n, hash_value, prev) + , &this->get_bucket_value_traits()); } //! <b>Effects</b>: Returns a range containing all elements with values equivalent @@ -2168,8 +2519,8 @@ class hashtable_impl //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()). //! //! <b>Throws</b>: If the internal hasher or the equality functor throws. - std::pair<iterator,iterator> equal_range(const_reference value) - { return this->equal_range(value, this->priv_hasher(), this->priv_equal()); } + std::pair<iterator,iterator> equal_range(const key_type &key) + { return this->equal_range(key, this->priv_hasher(), this->priv_equal()); } //! <b>Requires</b>: "hash_func" must be a hash function that induces //! the same hash values as the stored hasher. The difference is that @@ -2191,15 +2542,15 @@ class hashtable_impl //! <b>Note</b>: This function is used when constructing a value_type //! is expensive and the value_type can be compared with a cheaper //! key type. Usually this key is part of the value_type. - template<class KeyType, class KeyHasher, class KeyValueEqual> + template<class KeyType, class KeyHasher, class KeyEqual> std::pair<iterator,iterator> equal_range - (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) + (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) { - size_type bucket_n1, bucket_n2, cnt; - std::pair<siterator, siterator> ret = this->priv_equal_range - (key, hash_func, equal_func, bucket_n1, bucket_n2, cnt); + std::pair<siterator, siterator> ret = + this->priv_equal_range(key, hash_func, equal_func); return std::pair<iterator, iterator> - (iterator(ret.first, &this->get_bucket_value_traits()), iterator(ret.second, &this->get_bucket_value_traits())); + ( iterator(ret.first, &this->get_bucket_value_traits()) + , iterator(ret.second, &this->get_bucket_value_traits())); } //! <b>Effects</b>: Returns a range containing all elements with values equivalent @@ -2210,8 +2561,8 @@ class hashtable_impl //! //! <b>Throws</b>: If the internal hasher or the equality functor throws. std::pair<const_iterator, const_iterator> - equal_range(const_reference value) const - { return this->equal_range(value, this->priv_hasher(), this->priv_equal()); } + equal_range(const key_type &key) const + { return this->equal_range(key, this->priv_hasher(), this->priv_equal()); } //! <b>Requires</b>: "hash_func" must be a hash function that induces //! the same hash values as the stored hasher. The difference is that @@ -2233,18 +2584,19 @@ class hashtable_impl //! <b>Note</b>: This function is used when constructing a value_type //! is expensive and the value_type can be compared with a cheaper //! key type. Usually this key is part of the value_type. - template<class KeyType, class KeyHasher, class KeyValueEqual> + template<class KeyType, class KeyHasher, class KeyEqual> std::pair<const_iterator,const_iterator> equal_range - (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) const + (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const { - size_type bucket_n1, bucket_n2, cnt; std::pair<siterator, siterator> ret = - this->priv_equal_range(key, hash_func, equal_func, bucket_n1, bucket_n2, cnt); + this->priv_equal_range(key, hash_func, equal_func); return std::pair<const_iterator, const_iterator> ( const_iterator(ret.first, &this->get_bucket_value_traits()) , const_iterator(ret.second, &this->get_bucket_value_traits())); } + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of //! appropriate type. Otherwise the behavior is undefined. //! @@ -2254,11 +2606,7 @@ class hashtable_impl //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: If the internal hash function throws. - iterator iterator_to(reference value) - { - return iterator(bucket_type::s_iterator_to - (this->priv_value_to_node(value)), &this->get_bucket_value_traits()); - } + iterator iterator_to(reference value); //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of //! appropriate type. Otherwise the behavior is undefined. @@ -2269,13 +2617,7 @@ class hashtable_impl //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: If the internal hash function throws. - const_iterator iterator_to(const_reference value) const - { - node_reference r = *pointer_traits<node_ptr>::const_cast_from - (pointer_traits<const_node_ptr>::pointer_to(this->priv_value_to_node(value))); - siterator sit = bucket_type::s_iterator_to(r); - return const_iterator(sit, &this->get_bucket_value_traits()); - } + const_iterator iterator_to(const_reference value) const; //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of //! appropriate type. Otherwise the behavior is undefined. @@ -2289,12 +2631,7 @@ class hashtable_impl //! //! <b>Note</b>: This static function is available only if the <i>value traits</i> //! is stateless. - static local_iterator s_local_iterator_to(reference value) - { - BOOST_STATIC_ASSERT((!stateful_value_traits)); - siterator sit = bucket_type::s_iterator_to(*value_traits::to_node_ptr(value)); - return local_iterator(sit, const_value_traits_ptr()); - } + static local_iterator s_local_iterator_to(reference value); //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of //! appropriate type. Otherwise the behavior is undefined. @@ -2308,14 +2645,7 @@ class hashtable_impl //! //! <b>Note</b>: This static function is available only if the <i>value traits</i> //! is stateless. - static const_local_iterator s_local_iterator_to(const_reference value) - { - BOOST_STATIC_ASSERT((!stateful_value_traits)); - node_reference r = *pointer_traits<node_ptr>::const_cast_from - (value_traits::to_node_ptr(value)); - siterator sit = bucket_type::s_iterator_to(r); - return const_local_iterator(sit, const_value_traits_ptr()); - } + static const_local_iterator s_local_iterator_to(const_reference value); //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of //! appropriate type. Otherwise the behavior is undefined. @@ -2326,11 +2656,7 @@ class hashtable_impl //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - local_iterator local_iterator_to(reference value) - { - siterator sit = bucket_type::s_iterator_to(this->priv_value_to_node(value)); - return local_iterator(sit, this->priv_value_traits_ptr()); - } + local_iterator local_iterator_to(reference value); //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of //! appropriate type. Otherwise the behavior is undefined. @@ -2341,13 +2667,7 @@ class hashtable_impl //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - const_local_iterator local_iterator_to(const_reference value) const - { - node_reference r = *pointer_traits<node_ptr>::const_cast_from - (pointer_traits<const_node_ptr>::pointer_to(this->priv_value_to_node(value))); - siterator sit = bucket_type::s_iterator_to(r); - return const_local_iterator(sit, this->priv_value_traits_ptr()); - } + const_local_iterator local_iterator_to(const_reference value) const; //! <b>Effects</b>: Returns the number of buckets passed in the constructor //! or the last rehash function. @@ -2355,8 +2675,7 @@ class hashtable_impl //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - size_type bucket_count() const - { return this->priv_bucket_count(); } + size_type bucket_count() const; //! <b>Requires</b>: n is in the range [0, this->bucket_count()). //! @@ -2365,8 +2684,8 @@ class hashtable_impl //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - size_type bucket_size(size_type n) const - { return this->priv_bucket_pointer()[n].size(); } + size_type bucket_size(size_type n) const; + #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) //! <b>Effects</b>: Returns the index of the bucket in which elements //! with keys equivalent to k would be found, if any such element existed. @@ -2392,17 +2711,17 @@ class hashtable_impl //! //! <b>Note</b>: the return value is in the range [0, this->bucket_count()). template<class KeyType, class KeyHasher> - size_type bucket(const KeyType& k, const KeyHasher &hash_func) const + size_type bucket(const KeyType& k, KeyHasher hash_func) const { return this->priv_hash_to_bucket(hash_func(k)); } + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor //! or the last rehash function. //! //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - bucket_ptr bucket_pointer() const - { return this->priv_bucket_pointer(); } + bucket_ptr bucket_pointer() const; //! <b>Requires</b>: n is in the range [0, this->bucket_count()). //! @@ -2415,8 +2734,7 @@ class hashtable_impl //! //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range //! containing all of the elements in the nth bucket. - local_iterator begin(size_type n) - { return local_iterator(this->priv_bucket_pointer()[n].begin(), this->priv_value_traits_ptr()); } + local_iterator begin(size_type n); //! <b>Requires</b>: n is in the range [0, this->bucket_count()). //! @@ -2429,8 +2747,7 @@ class hashtable_impl //! //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range //! containing all of the elements in the nth bucket. - const_local_iterator begin(size_type n) const - { return this->cbegin(n); } + const_local_iterator begin(size_type n) const; //! <b>Requires</b>: n is in the range [0, this->bucket_count()). //! @@ -2443,11 +2760,7 @@ class hashtable_impl //! //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range //! containing all of the elements in the nth bucket. - const_local_iterator cbegin(size_type n) const - { - bucket_reference br = pointer_traits<bucket_ptr>::const_cast_from(this->priv_bucket_pointer())[n]; - return const_local_iterator(br.begin(), this->priv_value_traits_ptr()); - } + const_local_iterator cbegin(size_type n) const; //! <b>Requires</b>: n is in the range [0, this->bucket_count()). //! @@ -2460,8 +2773,7 @@ class hashtable_impl //! //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range //! containing all of the elements in the nth bucket. - local_iterator end(size_type n) - { return local_iterator(this->priv_bucket_pointer()[n].end(), this->priv_value_traits_ptr()); } + local_iterator end(size_type n); //! <b>Requires</b>: n is in the range [0, this->bucket_count()). //! @@ -2474,8 +2786,7 @@ class hashtable_impl //! //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range //! containing all of the elements in the nth bucket. - const_local_iterator end(size_type n) const - { return this->cend(n); } + const_local_iterator end(size_type n) const; //! <b>Requires</b>: n is in the range [0, this->bucket_count()). //! @@ -2488,11 +2799,8 @@ class hashtable_impl //! //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range //! containing all of the elements in the nth bucket. - const_local_iterator cend(size_type n) const - { - bucket_reference br = pointer_traits<bucket_ptr>::const_cast_from(this->priv_bucket_pointer())[n]; - return const_local_iterator ( br.end(), this->priv_value_traits_ptr()); - } + const_local_iterator cend(size_type n) const; + #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) //! <b>Requires</b>: new_bucket_traits can hold a pointer to a new bucket array //! or the same as the old bucket array with a different length. new_size is the length of the @@ -2520,36 +2828,33 @@ class hashtable_impl //Check power of two bucket array if the option is activated BOOST_INTRUSIVE_INVARIANT_ASSERT - (!power_2_buckets || (0 == (new_bucket_count & (new_bucket_count-1u)))); + (!power_2_buckets || (0 == (new_bucket_count & (new_bucket_count-1u)))); size_type n = this->priv_get_cache_bucket_num(); const bool same_buffer = old_buckets == new_buckets; //If the new bucket length is a common factor //of the old one we can avoid hash calculations. - const bool fast_shrink = (!incremental) && (old_bucket_count > new_bucket_count) && - (power_2_buckets ||(old_bucket_count % new_bucket_count) == 0); + const bool fast_shrink = (!incremental) && (old_bucket_count >= new_bucket_count) && + (power_2_buckets || (old_bucket_count % new_bucket_count) == 0); //If we are shrinking the same bucket array and it's //is a fast shrink, just rehash the last nodes size_type new_first_bucket_num = new_bucket_count; if(same_buffer && fast_shrink && (n < new_bucket_count)){ + new_first_bucket_num = n; n = new_bucket_count; - new_first_bucket_num = this->priv_get_cache_bucket_num(); } //Anti-exception stuff: they destroy the elements if something goes wrong. //If the source and destination buckets are the same, the second rollback function //is harmless, because all elements have been already unlinked and destroyed typedef detail::init_disposer<node_algorithms> NodeDisposer; + typedef detail::exception_array_disposer<bucket_type, NodeDisposer, size_type> ArrayDisposer; NodeDisposer node_disp; - bucket_type & newbuck = new_buckets[0]; - bucket_type & oldbuck = old_buckets[0]; - detail::exception_array_disposer<bucket_type, NodeDisposer, size_type> - rollback1(newbuck, node_disp, new_bucket_count); - detail::exception_array_disposer<bucket_type, NodeDisposer, size_type> - rollback2(oldbuck, node_disp, old_bucket_count); + ArrayDisposer rollback1(new_buckets[0], node_disp, new_bucket_count); + ArrayDisposer rollback2(old_buckets[0], node_disp, old_bucket_count); //Put size in a safe value for rollback exception - size_type size_backup = this->priv_size_traits().get_size(); + size_type const size_backup = this->priv_size_traits().get_size(); this->priv_size_traits().set_size(0); //Put cache to safe position this->priv_initialize_cache(); @@ -2558,20 +2863,17 @@ class hashtable_impl //Iterate through nodes for(; n < old_bucket_count; ++n){ bucket_type &old_bucket = old_buckets[n]; - if(!fast_shrink){ - siterator before_i(old_bucket.before_begin()); - siterator end_sit(old_bucket.end()); - siterator i(old_bucket.begin()); - for(;i != end_sit; ++i){ + for( siterator before_i(old_bucket.before_begin()), i(old_bucket.begin()), end_sit(old_bucket.end()) + ; i != end_sit + ; i = before_i, ++i){ const value_type &v = this->priv_value_from_slist_node(i.pointed_node()); const std::size_t hash_value = this->priv_stored_or_compute_hash(v, store_hash_t()); - const size_type new_n = detail::hash_to_bucket_split<power_2_buckets, incremental>(hash_value, new_bucket_count, new_bucket_count); + const size_type new_n = detail::hash_to_bucket_split<power_2_buckets, incremental> + (hash_value, new_bucket_count, new_bucket_count); if(cache_begin && new_n < new_first_bucket_num) new_first_bucket_num = new_n; - siterator last = bucket_type::s_iterator_to - (*group_functions_t::get_last_in_group - (detail::dcast_bucket_ptr<node>(i.pointed_node()), optimize_multikey_t())); + siterator const last = (priv_last_in_group)(i); if(same_buffer && new_n == n){ before_i = last; } @@ -2579,7 +2881,6 @@ class hashtable_impl bucket_type &new_b = new_buckets[new_n]; new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last); } - i = before_i; } } else{ @@ -2587,12 +2888,10 @@ class hashtable_impl if(cache_begin && new_n < new_first_bucket_num) new_first_bucket_num = new_n; bucket_type &new_b = new_buckets[new_n]; - if(!old_bucket.empty()){ - new_b.splice_after( new_b.before_begin() - , old_bucket - , old_bucket.before_begin() - , hashtable_impl::priv_get_last(old_bucket)); - } + new_b.splice_after( new_b.before_begin() + , old_bucket + , old_bucket.before_begin() + , bucket_plus_vtraits_t::priv_get_last(old_bucket, optimize_multikey_t())); } } @@ -2621,56 +2920,47 @@ class hashtable_impl const size_type split_idx = this->priv_split_traits().get_size(); const size_type bucket_cnt = this->priv_bucket_count(); const bucket_ptr buck_ptr = this->priv_bucket_pointer(); + bool ret = false; if(grow){ //Test if the split variable can be changed - if(split_idx >= bucket_cnt) - return false; - - const size_type bucket_to_rehash = split_idx - bucket_cnt/2; - bucket_type &old_bucket = buck_ptr[bucket_to_rehash]; - siterator before_i(old_bucket.before_begin()); - const siterator end_sit(old_bucket.end()); - siterator i(old_bucket.begin()); - this->priv_split_traits().increment(); - - //Anti-exception stuff: if an exception is thrown while - //moving elements from old_bucket to the target bucket, all moved - //elements are moved back to the original one. - detail::incremental_rehash_rollback<bucket_type, split_traits> rollback - ( buck_ptr[split_idx], old_bucket, this->priv_split_traits()); - for(;i != end_sit; ++i){ - const value_type &v = this->priv_value_from_slist_node(i.pointed_node()); - const std::size_t hash_value = this->priv_stored_or_compute_hash(v, store_hash_t()); - const size_type new_n = this->priv_hash_to_bucket(hash_value); - siterator last = bucket_type::s_iterator_to - (*group_functions_t::get_last_in_group - (detail::dcast_bucket_ptr<node>(i.pointed_node()), optimize_multikey_t())); - if(new_n == bucket_to_rehash){ - before_i = last; - } - else{ - bucket_type &new_b = buck_ptr[new_n]; - new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last); + if((ret = split_idx < bucket_cnt)){ + const size_type bucket_to_rehash = split_idx - bucket_cnt/2; + bucket_type &old_bucket = buck_ptr[bucket_to_rehash]; + this->priv_split_traits().increment(); + + //Anti-exception stuff: if an exception is thrown while + //moving elements from old_bucket to the target bucket, all moved + //elements are moved back to the original one. + detail::incremental_rehash_rollback<bucket_type, split_traits> rollback + ( buck_ptr[split_idx], old_bucket, this->priv_split_traits()); + for( siterator before_i(old_bucket.before_begin()), i(old_bucket.begin()), end_sit(old_bucket.end()) + ; i != end_sit; i = before_i, ++i){ + const value_type &v = this->priv_value_from_slist_node(i.pointed_node()); + const std::size_t hash_value = this->priv_stored_or_compute_hash(v, store_hash_t()); + const size_type new_n = this->priv_hash_to_bucket(hash_value); + siterator const last = (priv_last_in_group)(i); + if(new_n == bucket_to_rehash){ + before_i = last; + } + else{ + bucket_type &new_b = buck_ptr[new_n]; + new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last); + } } - i = before_i; + rollback.release(); + this->priv_erasure_update_cache(); } - rollback.release(); - this->priv_erasure_update_cache(); - return true; } - else{ - //Test if the split variable can be changed - if(split_idx <= bucket_cnt/2) - return false; + else if((ret = split_idx > bucket_cnt/2)){ //!grow const size_type target_bucket_num = split_idx - 1 - bucket_cnt/2; bucket_type &target_bucket = buck_ptr[target_bucket_num]; bucket_type &source_bucket = buck_ptr[split_idx-1]; target_bucket.splice_after(target_bucket.cbefore_begin(), source_bucket); this->priv_split_traits().decrement(); this->priv_insertion_update_cache(target_bucket_num); - return true; } + return ret; } //! <b>Effects</b>: If new_bucket_traits.bucket_count() is not @@ -2690,24 +2980,22 @@ class hashtable_impl { //This function is only available for containers with incremental hashing BOOST_STATIC_ASSERT(( incremental && power_2_buckets )); - size_type new_bucket_traits_size = new_bucket_traits.bucket_count(); - size_type cur_bucket_traits = this->priv_bucket_count(); - if(new_bucket_traits_size/2 != cur_bucket_traits && new_bucket_traits_size != cur_bucket_traits/2){ - return false; - } - + size_type const new_bucket_traits_size = new_bucket_traits.bucket_count(); + size_type const cur_bucket_traits = this->priv_bucket_count(); const size_type split_idx = this->split_count(); + //Test new bucket size is consistent with internal bucket size and split count if(new_bucket_traits_size/2 == cur_bucket_traits){ - //Test if the split variable can be changed if(!(split_idx >= cur_bucket_traits)) return false; } - else{ - //Test if the split variable can be changed - if(!(split_idx <= cur_bucket_traits/2)) + else if(new_bucket_traits_size == cur_bucket_traits/2){ + if(!(split_idx <= new_bucket_traits_size)) return false; } + else{ + return false; + } const size_type ini_n = this->priv_get_cache_bucket_num(); const bucket_ptr old_buckets = this->priv_bucket_pointer(); @@ -2725,19 +3013,16 @@ class hashtable_impl return true; } - //! <b>Requires</b>: + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + + //! <b>Requires</b>: incremental<> option must be set //! - //! <b>Effects</b>: + //! <b>Effects</b>: returns the current split count //! - //! <b>Complexity</b>: + //! <b>Complexity</b>: Constant //! - //! <b>Throws</b>: - size_type split_count() const - { - //This function is only available if incremental hashing is activated - BOOST_STATIC_ASSERT(( incremental && power_2_buckets )); - return this->priv_split_traits().get_size(); - } + //! <b>Throws</b>: Nothing + size_type split_count() const; //! <b>Effects</b>: Returns the nearest new bucket count optimized for //! the container that is bigger or equal than n. This suggestion can be @@ -2748,14 +3033,7 @@ class hashtable_impl //! <b>Complexity</b>: Amortized constant time. //! //! <b>Throws</b>: Nothing. - static size_type suggested_upper_bucket_count(size_type n) - { - const std::size_t *primes = &prime_list_holder<0>::prime_list[0]; - const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size; - std::size_t const* bound = std::lower_bound(primes, primes_end, n); - bound -= (bound == primes_end); - return size_type(*bound); - } + static size_type suggested_upper_bucket_count(size_type n); //! <b>Effects</b>: Returns the nearest new bucket count optimized for //! the container that is smaller or equal than n. This suggestion can be @@ -2766,403 +3044,306 @@ class hashtable_impl //! <b>Complexity</b>: Amortized constant time. //! //! <b>Throws</b>: Nothing. - static size_type suggested_lower_bucket_count(size_type n) - { - const std::size_t *primes = &prime_list_holder<0>::prime_list[0]; - const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size; - size_type const* bound = std::upper_bound(primes, primes_end, n); - bound -= (bound != primes); - return size_type(*bound); - } - /// @cond - void check() const {} - private: - size_traits &priv_size_traits() - { return static_cast<size_traits&>(static_cast<data_type&>(*this)); } - - const size_traits &priv_size_traits() const - { return static_cast<const size_traits&>(static_cast<const data_type&>(*this)); } - - bucket_ptr priv_bucket_pointer() const - { return this->data_type::internal.internal.internal.internal.priv_bucket_pointer(); } - - SizeType priv_bucket_count() const - { return this->data_type::internal.internal.internal.internal.priv_bucket_count(); } - - const bucket_plus_vtraits<ValueTraits, BucketTraits> &get_bucket_value_traits() const - { return this->data_type::internal.internal.internal.internal.get_bucket_value_traits(); } - - bucket_plus_vtraits<ValueTraits, BucketTraits> &get_bucket_value_traits() - { return this->data_type::internal.internal.internal.internal.get_bucket_value_traits(); } - - bucket_traits &priv_bucket_traits() - { return this->data_type::internal.internal.internal.internal.priv_bucket_traits(); } + static size_type suggested_lower_bucket_count(size_type n); + #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) - const bucket_traits &priv_bucket_traits() const - { return this->data_type::internal.internal.internal.internal.priv_bucket_traits(); } - - value_traits &priv_value_traits() - { return this->data_type::internal.internal.internal.internal.priv_value_traits(); } - - const value_traits &priv_value_traits() const - { return this->data_type::internal.internal.internal.internal.priv_value_traits(); } - - const_value_traits_ptr priv_value_traits_ptr() const - { return this->data_type::internal.internal.internal.internal.priv_value_traits_ptr(); } - - siterator priv_invalid_local_it() const - { return this->data_type::internal.internal.internal.internal.priv_invalid_local_it(); } - - split_traits &priv_split_traits() - { return this->data_type::internal.priv_split_traits(); } - - const split_traits &priv_split_traits() const - { return this->data_type::internal.priv_split_traits(); } - bucket_ptr priv_get_cache() - { return this->data_type::internal.internal.priv_get_cache(); } - - void priv_initialize_cache() - { return this->data_type::internal.internal.priv_initialize_cache(); } - - siterator priv_begin() const - { return this->data_type::internal.internal.priv_begin(); } - - const value_equal &priv_equal() const - { return this->data_type::internal.internal.priv_equal(); } - - value_equal &priv_equal() - { return this->data_type::internal.internal.priv_equal(); } - - const hasher &priv_hasher() const - { return this->data_type::internal.internal.internal.priv_hasher(); } - - hasher &priv_hasher() - { return this->data_type::internal.internal.internal.priv_hasher(); } - - void priv_swap_cache(hashtable_impl &h) - { this->data_type::internal.internal.priv_swap_cache(h.data_type::internal.internal); } - - node &priv_value_to_node(value_type &v) - { return this->data_type::internal.internal.internal.internal.priv_value_to_node(v); } - - const node &priv_value_to_node(const value_type &v) const - { return this->data_type::internal.internal.internal.internal.priv_value_to_node(v); } - - SizeType priv_get_cache_bucket_num() - { return this->data_type::internal.internal.priv_get_cache_bucket_num(); } - - void priv_insertion_update_cache(SizeType n) - { return this->data_type::internal.internal.priv_insertion_update_cache(n); } - - template<bool Boolean> - std::size_t priv_stored_or_compute_hash(const value_type &v, detail::bool_<Boolean> b) const - { return this->data_type::internal.internal.internal.priv_stored_or_compute_hash(v, b); } - - value_type &priv_value_from_slist_node(slist_node_ptr n) - { return this->data_type::internal.internal.internal.internal.priv_value_from_slist_node(n); } + friend bool operator==(const hashtable_impl &x, const hashtable_impl &y) + { + //Taken from N3068 + if(constant_time_size && x.size() != y.size()){ + return false; + } + for (const_iterator ix = x.cbegin(), ex = x.cend(); ix != ex; ++ix){ + std::pair<const_iterator, const_iterator> eqx(x.equal_range(key_of_value()(*ix))), + eqy(y.equal_range(key_of_value()(*ix))); + if (boost::intrusive::iterator_distance(eqx.first, eqx.second) != + boost::intrusive::iterator_distance(eqy.first, eqy.second) || + !(priv_algo_is_permutation)(eqx.first, eqx.second, eqy.first) ){ + return false; + } + ix = eqx.second; + } + return true; + } - const value_type &priv_value_from_slist_node(slist_node_ptr n) const - { return this->data_type::internal.internal.internal.internal.priv_value_from_slist_node(n); } + friend bool operator!=(const hashtable_impl &x, const hashtable_impl &y) + { return !(x == y); } - void priv_erasure_update_cache_range(SizeType first_bucket_num, SizeType last_bucket_num) - { return this->data_type::internal.internal.priv_erasure_update_cache_range(first_bucket_num, last_bucket_num); } + friend bool operator<(const hashtable_impl &x, const hashtable_impl &y) + { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } - void priv_erasure_update_cache() - { return this->data_type::internal.internal.priv_erasure_update_cache(); } + friend bool operator>(const hashtable_impl &x, const hashtable_impl &y) + { return y < x; } - static std::size_t priv_stored_hash(slist_node_ptr n, detail::true_ true_value) - { return bucket_plus_vtraits<ValueTraits, BucketTraits>::priv_stored_hash(n, true_value); } + friend bool operator<=(const hashtable_impl &x, const hashtable_impl &y) + { return !(y < x); } - static std::size_t priv_stored_hash(slist_node_ptr n, detail::false_ false_value) - { return bucket_plus_vtraits<ValueTraits, BucketTraits>::priv_stored_hash(n, false_value); } + friend bool operator>=(const hashtable_impl &x, const hashtable_impl &y) + { return !(x < y); } - std::size_t priv_hash_to_bucket(std::size_t hash_value) const - { - return detail::hash_to_bucket_split<power_2_buckets, incremental> - (hash_value, this->priv_bucket_traits().bucket_count(), this->priv_split_traits().get_size()); - } + /// @cond + void check() const {} + private: - template<class Disposer> - void priv_erase_range_impl - (size_type bucket_num, siterator before_first_it, siterator end_sit, Disposer disposer, size_type &num_erased) + template <class MaybeConstHashtableImpl, class Cloner, class Disposer> + void priv_clone_from(MaybeConstHashtableImpl &src, Cloner cloner, Disposer disposer) { - const bucket_ptr buckets = this->priv_bucket_pointer(); - bucket_type &b = buckets[bucket_num]; - - if(before_first_it == b.before_begin() && end_sit == b.end()){ - this->priv_erase_range_impl(bucket_num, 1, disposer, num_erased); - } - else{ - num_erased = 0; - siterator to_erase(before_first_it); - ++to_erase; - slist_node_ptr end_ptr = end_sit.pointed_node(); - while(to_erase != end_sit){ - group_functions_t::erase_from_group(end_ptr, detail::dcast_bucket_ptr<node>(to_erase.pointed_node()), optimize_multikey_t()); - to_erase = b.erase_after_and_dispose(before_first_it, make_node_disposer(disposer)); - ++num_erased; + this->clear_and_dispose(disposer); + if(!constant_time_size || !src.empty()){ + const size_type src_bucket_count = src.bucket_count(); + const size_type dst_bucket_count = this->bucket_count(); + //Check power of two bucket array if the option is activated + BOOST_INTRUSIVE_INVARIANT_ASSERT + (!power_2_buckets || (0 == (src_bucket_count & (src_bucket_count-1)))); + BOOST_INTRUSIVE_INVARIANT_ASSERT + (!power_2_buckets || (0 == (dst_bucket_count & (dst_bucket_count-1)))); + //If src bucket count is bigger or equal, structural copy is possible + const bool structural_copy = (!incremental) && (src_bucket_count >= dst_bucket_count) && + (power_2_buckets || (src_bucket_count % dst_bucket_count) == 0); + if(structural_copy){ + this->priv_structural_clone_from(src, cloner, disposer); + } + else{ + //Unlike previous cloning algorithm, this can throw + //if cloner, hasher or comparison functor throw + typedef typename detail::if_c< detail::is_const<MaybeConstHashtableImpl>::value + , typename MaybeConstHashtableImpl::const_iterator + , typename MaybeConstHashtableImpl::iterator + >::type clone_iterator; + clone_iterator b(src.begin()), e(src.end()); + detail::exception_disposer<hashtable_impl, Disposer> rollback(*this, disposer); + for(; b != e; ++b){ + //No need to check for duplicates and insert it in the first position + //as this is an unordered container. So use minimal insertion code + std::size_t const hash_to_store = this->priv_stored_or_compute_hash(*b, store_hash_t());; + size_type const bucket_number = this->priv_hash_to_bucket(hash_to_store); + typedef typename detail::if_c + <detail::is_const<MaybeConstHashtableImpl>::value, const_reference, reference>::type reference_type; + reference_type r = *b; + this->priv_clone_front_in_bucket<reference_type>(bucket_number, r, hash_to_store, cloner); + } + rollback.release(); } - this->priv_size_traits().set_size(this->priv_size_traits().get_size()-num_erased); } } - template<class Disposer> - void priv_erase_range_impl - (size_type first_bucket_num, size_type num_buckets, Disposer disposer, size_type &num_erased) - { - //Now fully clear the intermediate buckets - const bucket_ptr buckets = this->priv_bucket_pointer(); - num_erased = 0; - for(size_type i = first_bucket_num; i < (num_buckets + first_bucket_num); ++i){ - bucket_type &b = buckets[i]; - siterator b_begin(b.before_begin()); - siterator nxt(b_begin); - ++nxt; - siterator end_sit(b.end()); - while(nxt != end_sit){ - group_functions_t::init_group(detail::dcast_bucket_ptr<node>(nxt.pointed_node()), optimize_multikey_t()); - nxt = b.erase_after_and_dispose - (b_begin, make_node_disposer(disposer)); - this->priv_size_traits().decrement(); - ++num_erased; + template<class ValueReference, class Cloner> + void priv_clone_front_in_bucket( size_type const bucket_number + , typename detail::identity<ValueReference>::type src_ref + , std::size_t const hash_to_store, Cloner cloner) + { + //No need to check for duplicates and insert it in the first position + //as this is an unordered container. So use minimal insertion code + //std::size_t const hash_value = this->priv_stored_or_compute_hash(src_ref, store_hash_t());; + //size_type const bucket_number = this->priv_hash_to_bucket(hash_value); + bucket_type &cur_bucket = this->priv_bucket_pointer()[bucket_number]; + siterator const prev(cur_bucket.before_begin()); + //Just check if the cloned node is equal to the first inserted value in the new bucket + //as equal src values were contiguous and they should be already inserted in the + //destination bucket. + bool const next_is_in_group = optimize_multikey && !cur_bucket.empty() && + this->priv_equal()( key_of_value()(src_ref) + , key_of_value()(this->priv_value_from_slist_node((++siterator(prev)).pointed_node()))); + this->priv_insert_equal_after_find(*cloner(src_ref), bucket_number, hash_to_store, prev, next_is_in_group); + } + + template <class MaybeConstHashtableImpl, class Cloner, class Disposer> + void priv_structural_clone_from(MaybeConstHashtableImpl &src, Cloner cloner, Disposer disposer) + { + //First clone the first ones + const size_type src_bucket_count = src.bucket_count(); + const size_type dst_bucket_count = this->bucket_count(); + const bucket_ptr src_buckets = src.priv_bucket_pointer(); + const bucket_ptr dst_buckets = this->priv_bucket_pointer(); + size_type constructed = 0; + typedef node_cast_adaptor< detail::node_disposer<Disposer, value_traits, CircularSListAlgorithms> + , slist_node_ptr, node_ptr > NodeDisposer; + NodeDisposer node_disp(disposer, &this->priv_value_traits()); + + detail::exception_array_disposer<bucket_type, NodeDisposer, size_type> + rollback(dst_buckets[0], node_disp, constructed); + //Now insert the remaining ones using the modulo trick + for( //"constructed" already initialized + ; constructed < src_bucket_count + ; ++constructed){ + //Since incremental hashing can't be structurally copied, avoid hash_to_bucket_split + const std::size_t new_n = detail::hash_to_bucket(constructed, dst_bucket_count, detail::bool_<power_2_buckets>()); + bucket_type &src_b = src_buckets[constructed]; + for( siterator b(src_b.begin()), e(src_b.end()); b != e; ++b){ + slist_node_ptr const n(b.pointed_node()); + typedef typename detail::if_c + <detail::is_const<MaybeConstHashtableImpl>::value, const_reference, reference>::type reference_type; + reference_type r = this->priv_value_from_slist_node(n); + this->priv_clone_front_in_bucket<reference_type> + (new_n, r, this->priv_stored_hash(n, store_hash_t()), cloner); } } + this->priv_hasher() = src.priv_hasher(); + this->priv_equal() = src.priv_equal(); + rollback.release(); + this->priv_size_traits().set_size(src.priv_size_traits().get_size()); + this->priv_split_traits().set_size(dst_bucket_count); + this->priv_insertion_update_cache(0u); + this->priv_erasure_update_cache(); } - template<class Disposer> - void priv_erase_range( siterator before_first_it, size_type first_bucket - , siterator last_it, size_type last_bucket - , Disposer disposer) + std::size_t priv_hash_to_bucket(std::size_t hash_value) const { - size_type num_erased; - if (first_bucket == last_bucket){ - this->priv_erase_range_impl(first_bucket, before_first_it, last_it, disposer, num_erased); - } - else { - bucket_type *b = (&this->priv_bucket_pointer()[0]); - this->priv_erase_range_impl(first_bucket, before_first_it, b[first_bucket].end(), disposer, num_erased); - if(size_type n = (last_bucket - first_bucket - 1)) - this->priv_erase_range_impl(first_bucket + 1, n, disposer, num_erased); - this->priv_erase_range_impl(last_bucket, b[last_bucket].before_begin(), last_it, disposer, num_erased); - } + return detail::hash_to_bucket_split<power_2_buckets, incremental> + (hash_value, this->priv_bucket_traits().bucket_count(), this->priv_split_traits().get_size()); } - std::size_t priv_get_bucket_num(siterator it) - { return this->priv_get_bucket_num_hash_dispatch(it, store_hash_t()); } - - std::size_t priv_get_bucket_num_hash_dispatch(siterator it, detail::true_) //store_hash + iterator priv_insert_equal_after_find(reference value, size_type bucket_num, std::size_t hash_value, siterator prev, bool const next_is_in_group) { - return this->priv_hash_to_bucket - (this->priv_stored_hash(it.pointed_node(), store_hash_t())); + //Now store hash if needed + node_ptr n = pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(value)); + node_functions_t::store_hash(n, hash_value, store_hash_t()); + //Checks for some modes + BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(n)); + //Shortcut to optimize_multikey cases + group_functions_t::insert_in_group + ( next_is_in_group ? detail::dcast_bucket_ptr<node>((++siterator(prev)).pointed_node()) : n + , n, optimize_multikey_t()); + //Update cache and increment size if needed + this->priv_insertion_update_cache(bucket_num); + this->priv_size_traits().increment(); + //Insert the element in the bucket after it + return iterator(bucket_type::s_insert_after(prev, *n), &this->get_bucket_value_traits()); } - std::size_t priv_get_bucket_num_hash_dispatch(siterator it, detail::false_) //NO store_hash - { return this->data_type::internal.internal.internal.internal.priv_get_bucket_num_no_hash_store(it, optimize_multikey_t()); } - - static siterator priv_get_previous(bucket_type &b, siterator i) - { return bucket_plus_vtraits_t::priv_get_previous(b, i, optimize_multikey_t()); } - - static siterator priv_get_last(bucket_type &b) - { return bucket_plus_vtraits_t::priv_get_last(b, optimize_multikey_t()); } - - template<class Disposer> - void priv_erase(const_iterator i, Disposer disposer, detail::true_) - { - slist_node_ptr elem(i.slist_it().pointed_node()); - slist_node_ptr f_bucket_end, l_bucket_end; - if(store_hash){ - f_bucket_end = l_bucket_end = - (this->priv_bucket_pointer() - [this->priv_hash_to_bucket - (this->priv_stored_hash(elem, store_hash_t())) - ]).before_begin().pointed_node(); - } - else{ - f_bucket_end = this->priv_bucket_pointer()->cend().pointed_node(); - l_bucket_end = f_bucket_end + this->priv_bucket_count() - 1; - } - node_ptr nxt_in_group; - siterator prev = bucket_type::s_iterator_to - (*group_functions_t::get_previous_and_next_in_group - ( elem, nxt_in_group, f_bucket_end, l_bucket_end) - ); - bucket_type::s_erase_after_and_dispose(prev, make_node_disposer(disposer)); - if(nxt_in_group) - group_algorithms::unlink_after(nxt_in_group); - if(safemode_or_autounlink) - group_algorithms::init(detail::dcast_bucket_ptr<node>(elem)); + template<class KeyType, class KeyHasher, class KeyEqual> + siterator priv_find //In case it is not found previt is bucket.before_begin() + ( const KeyType &key, KeyHasher hash_func + , KeyEqual equal_func, size_type &bucket_number, std::size_t &h, siterator &previt) const + { + h = hash_func(key); + return this->priv_find_with_hash(key, equal_func, bucket_number, h, previt); } - template <class Disposer> - void priv_erase(const_iterator i, Disposer disposer, detail::false_) + template<class KeyType, class KeyEqual> + bool priv_is_value_equal_to_key(const value_type &v, const std::size_t h, const KeyType &key, KeyEqual equal_func) const { - siterator to_erase(i.slist_it()); - bucket_type &b = this->priv_bucket_pointer()[this->priv_get_bucket_num(to_erase)]; - siterator prev(this->priv_get_previous(b, to_erase)); - b.erase_after_and_dispose(prev, make_node_disposer(disposer)); + (void)h; + return (!compare_hash || this->priv_stored_or_compute_hash(v, store_hash_t()) == h) && equal_func(key, key_of_value()(v)); } - template<class KeyType, class KeyHasher, class KeyValueEqual> - siterator priv_find - ( const KeyType &key, KeyHasher hash_func - , KeyValueEqual equal_func, size_type &bucket_number, std::size_t &h, siterator &previt) const + //return previous iterator to the next equal range group in case + static siterator priv_last_in_group(const siterator &it_first_in_group) { - h = hash_func(key); - return this->priv_find_with_hash(key, equal_func, bucket_number, h, previt); + return bucket_type::s_iterator_to + (*group_functions_t::get_last_in_group + (detail::dcast_bucket_ptr<node>(it_first_in_group.pointed_node()), optimize_multikey_t())); } - template<class KeyType, class KeyValueEqual> - siterator priv_find_with_hash - ( const KeyType &key, KeyValueEqual equal_func, size_type &bucket_number, const std::size_t h, siterator &previt) const + template<class KeyType, class KeyEqual> + siterator priv_find_with_hash //In case it is not found previt is bucket.before_begin() + ( const KeyType &key, KeyEqual equal_func, size_type &bucket_number, const std::size_t h, siterator &previt) const { bucket_number = this->priv_hash_to_bucket(h); bucket_type &b = this->priv_bucket_pointer()[bucket_number]; previt = b.before_begin(); - if(constant_time_size && this->empty()){ - return this->priv_invalid_local_it(); - } - siterator it = previt; - ++it; - - while(it != b.end()){ - const value_type &v = this->priv_value_from_slist_node(it.pointed_node()); - if(compare_hash){ - std::size_t vh = this->priv_stored_or_compute_hash(v, store_hash_t()); - if(h == vh && equal_func(key, v)){ - return it; - } - } - else if(equal_func(key, v)){ + siterator const endit = b.end(); + + while(++it != endit){ + if(this->priv_is_value_equal_to_key(this->priv_value_from_slist_node(it.pointed_node()), h, key, equal_func)){ return it; } - if(optimize_multikey){ - previt = bucket_type::s_iterator_to - (*group_functions_t::get_last_in_group - (detail::dcast_bucket_ptr<node>(it.pointed_node()), optimize_multikey_t())); - it = previt; - } - else{ - previt = it; - } - ++it; + previt = it = (priv_last_in_group)(it); } previt = b.before_begin(); return this->priv_invalid_local_it(); } - iterator priv_insert_equal_with_hash(reference value, std::size_t hash_value) - { - size_type bucket_num; - siterator prev; - siterator it = this->priv_find_with_hash - (value, this->priv_equal(), bucket_num, hash_value, prev); - return this->priv_insert_equal_find(value, bucket_num, hash_value, it); - } - - iterator priv_insert_equal_find(reference value, size_type bucket_num, std::size_t hash_value, siterator it) - { - bucket_type &b = this->priv_bucket_pointer()[bucket_num]; - bool found_equal = it != this->priv_invalid_local_it(); - if(!found_equal){ - it = b.before_begin(); - } - //Now store hash if needed - node_ptr n = pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(value)); - node_functions_t::store_hash(n, hash_value, store_hash_t()); - //Checks for some modes - if(safemode_or_autounlink) - BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n)); - //Shortcut for optimize_multikey cases - if(optimize_multikey){ - node_ptr first_in_group = found_equal ? - detail::dcast_bucket_ptr<node>(it.pointed_node()) : node_ptr(); - group_functions_t::insert_in_group(first_in_group, n, optimize_multikey_t()); - } - //Update cache and increment size if needed - this->priv_insertion_update_cache(bucket_num); - this->priv_size_traits().increment(); - //Insert the element in the bucket after it - return iterator(b.insert_after(it, *n), &this->get_bucket_value_traits()); - } - - template<class KeyType, class KeyHasher, class KeyValueEqual> - std::pair<siterator, siterator> priv_equal_range + template<class KeyType, class KeyHasher, class KeyEqual> + std::pair<siterator, siterator> priv_local_equal_range ( const KeyType &key , KeyHasher hash_func - , KeyValueEqual equal_func - , size_type &bucket_number_first - , size_type &bucket_number_second + , KeyEqual equal_func + , size_type &found_bucket , size_type &cnt) const { - std::size_t h; cnt = 0; - siterator prev; //Let's see if the element is present + + siterator prev; + size_type n_bucket; + std::size_t h; std::pair<siterator, siterator> to_return - ( this->priv_find(key, hash_func, equal_func, bucket_number_first, h, prev) + ( this->priv_find(key, hash_func, equal_func, n_bucket, h, prev) , this->priv_invalid_local_it()); - if(to_return.first == to_return.second){ - bucket_number_second = bucket_number_first; - return to_return; - } - { + + if(to_return.first != to_return.second){ + found_bucket = n_bucket; //If it's present, find the first that it's not equal in //the same bucket - bucket_type &b = this->priv_bucket_pointer()[bucket_number_first]; + bucket_type &b = this->priv_bucket_pointer()[n_bucket]; siterator it = to_return.first; + ++cnt; //At least one is found if(optimize_multikey){ - to_return.second = bucket_type::s_iterator_to - (*node_traits::get_next(group_functions_t::get_last_in_group - (detail::dcast_bucket_ptr<node>(it.pointed_node()), optimize_multikey_t()))); - - cnt = 0; - for(; it != to_return.second; ++it){ ++cnt; } - if(to_return.second != b.end()){ - bucket_number_second = bucket_number_first; - return to_return; - } + to_return.second = ++(priv_last_in_group)(it); + cnt += boost::intrusive::iterator_distance(++it, to_return.second); } else{ - ++cnt; - ++it; - while(it != b.end()){ - const value_type &v = this->priv_value_from_slist_node(it.pointed_node()); - if(compare_hash){ - std::size_t hv = this->priv_stored_or_compute_hash(v, store_hash_t()); - if(hv != h || !equal_func(key, v)){ - to_return.second = it; - bucket_number_second = bucket_number_first; - return to_return; - } - } - else if(!equal_func(key, v)){ - to_return.second = it; - bucket_number_second = bucket_number_first; - return to_return; - } - ++it; + siterator const bend = b.end(); + while(++it != bend && + this->priv_is_value_equal_to_key(this->priv_value_from_slist_node(it.pointed_node()), h, key, equal_func)){ ++cnt; } + to_return.second = it; } } + return to_return; + } - //If we reached the end, find the first, non-empty bucket - for(bucket_number_second = bucket_number_first+1 - ; bucket_number_second != this->priv_bucket_count() - ; ++bucket_number_second){ - bucket_type &b = this->priv_bucket_pointer()[bucket_number_second]; - if(!b.empty()){ - to_return.second = b.begin(); - return to_return; + template<class KeyType, class KeyHasher, class KeyEqual> + std::pair<siterator, siterator> priv_equal_range + ( const KeyType &key + , KeyHasher hash_func + , KeyEqual equal_func) const + { + size_type n_bucket; + size_type cnt; + + //Let's see if the element is present + std::pair<siterator, siterator> to_return + (this->priv_local_equal_range(key, hash_func, equal_func, n_bucket, cnt)); + //If not, find the next element as ".second" if ".second" local iterator + //is not pointing to an element. + bucket_ptr const bp = this->priv_bucket_pointer(); + if(to_return.first != to_return.second && + to_return.second == bp[n_bucket].end()){ + to_return.second = this->priv_invalid_local_it(); + ++n_bucket; + for( const size_type max_bucket = this->priv_bucket_count() + ; n_bucket != max_bucket + ; ++n_bucket){ + bucket_type &b = bp[n_bucket]; + if(!b.empty()){ + to_return.second = b.begin(); + break; + } } } - - //Otherwise, return the end node - to_return.second = this->priv_invalid_local_it(); return to_return; } + + std::size_t priv_get_bucket_num(siterator it) + { return this->priv_get_bucket_num_hash_dispatch(it, store_hash_t()); } + + std::size_t priv_get_bucket_num_hash_dispatch(siterator it, detail::true_) //store_hash + { + return this->priv_hash_to_bucket + (this->priv_stored_hash(it.pointed_node(), store_hash_t())); + } + + std::size_t priv_get_bucket_num_hash_dispatch(siterator it, detail::false_) //NO store_hash + { return this->priv_get_bucket_num_no_hash_store(it, optimize_multikey_t()); } + + static siterator priv_get_previous(bucket_type &b, siterator i) + { return bucket_plus_vtraits_t::priv_get_previous(b, i, optimize_multikey_t()); } + /// @endcond }; @@ -3232,16 +3413,17 @@ struct make_hashtable typedef hashtable_impl < value_traits + , typename packed_options::key_of_value , typename packed_options::hash , typename packed_options::equal - , typename packed_options::size_type , bucket_traits + , typename packed_options::size_type , (std::size_t(false)*hash_bool_flags::unique_keys_pos) - | (std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos) - | (std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos) - | (std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos) - | (std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos) - | (std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos) + |(std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos) + |(std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos) + |(std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos) + |(std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos) + |(std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos) > implementation_defined; /// @endcond @@ -3299,6 +3481,14 @@ class hashtable hashtable& operator=(BOOST_RV_REF(hashtable) x) { return static_cast<hashtable&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } + + template <class Cloner, class Disposer> + void clone_from(const hashtable &src, Cloner cloner, Disposer disposer) + { Base::clone_from(src, cloner, disposer); } + + template <class Cloner, class Disposer> + void clone_from(BOOST_RV_REF(hashtable) src, Cloner cloner, Disposer disposer) + { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } }; #endif |