summaryrefslogtreecommitdiff
path: root/boost/intrusive/hashtable.hpp
diff options
context:
space:
mode:
authorDongHun Kwak <dh0128.kwak@samsung.com>2016-10-06 10:30:07 +0900
committerDongHun Kwak <dh0128.kwak@samsung.com>2016-10-06 10:32:57 +0900
commit71d216b90256936a9638f325af9bc69d720e75de (patch)
tree9c5f682d341c7c88ad0c8e3d4b262e00b6fb691a /boost/intrusive/hashtable.hpp
parent733b5d5ae2c5d625211e2985ac25728ac3f54883 (diff)
downloadboost-71d216b90256936a9638f325af9bc69d720e75de.tar.gz
boost-71d216b90256936a9638f325af9bc69d720e75de.tar.bz2
boost-71d216b90256936a9638f325af9bc69d720e75de.zip
Imported Upstream version 1.59.0
Change-Id: I2dde00f4eca71df3eea9d251dcaecde18a6c90a5 Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/intrusive/hashtable.hpp')
-rw-r--r--boost/intrusive/hashtable.hpp2320
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