110 changes: 90 additions & 20 deletions include/boost/intrusive/treap.hpp
View file
Expand Up @@ -80,7 +80,7 @@ class treap_impl
< typename get_prio
< VoidOrPrioComp
, typename bstree_impl
<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, BsTreeAlgorithms, HeaderHolder>::value_type>::type
<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, BsTreeAlgorithms, HeaderHolder>::key_type>::type
>
/// @endcond
{
Expand All @@ -93,7 +93,7 @@ class treap_impl
typedef tree_type implementation_defined;
typedef get_prio
< VoidOrPrioComp
, typename tree_type::value_type> get_prio_type;
, typename tree_type::key_type> get_prio_type;

typedef detail::ebo_functor_holder
<typename get_prio_type::type> prio_base;
Expand Down Expand Up @@ -126,14 +126,11 @@ class treap_impl
static const bool stateful_value_traits = implementation_defined::stateful_value_traits;
static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value;

typedef detail::key_nodeptr_comp<priority_compare, value_traits> value_node_prio_comp_t;
typedef detail::key_nodeptr_comp<priority_compare, value_traits, key_of_value> key_node_prio_comp_t;

template<class KeyPrioComp>
detail::key_nodeptr_comp<KeyPrioComp, value_traits> key_node_prio_comp(KeyPrioComp keypriocomp) const
{ return detail::key_nodeptr_comp<KeyPrioComp, value_traits>(keypriocomp, &this->get_value_traits()); }

value_node_prio_comp_t value_node_prio_comp() const
{ return this->key_node_prio_comp(this->priv_pcomp()); }
detail::key_nodeptr_comp<KeyPrioComp, value_traits, key_of_value> key_node_prio_comp(KeyPrioComp keypriocomp) const
{ return detail::key_nodeptr_comp<KeyPrioComp, value_traits, key_of_value>(keypriocomp, &this->get_value_traits()); }

/// @cond
private:
Expand Down Expand Up @@ -414,7 +411,7 @@ class treap_impl
( this->tree_type::header_ptr()
, to_insert
, this->key_node_comp(this->key_comp())
, this->value_node_prio_comp())
, this->key_node_prio_comp(this->priv_pcomp()))
, this->priv_value_traits_ptr());
this->tree_type::sz_traits().increment();
return ret;
Expand Down Expand Up @@ -444,7 +441,7 @@ class treap_impl
, hint.pointed_node()
, to_insert
, this->key_node_comp(this->key_comp())
, this->value_node_prio_comp())
, this->key_node_prio_comp(this->priv_pcomp()))
, this->priv_value_traits_ptr());
this->tree_type::sz_traits().increment();
return ret;
Expand Down Expand Up @@ -489,8 +486,7 @@ class treap_impl
std::pair<iterator, bool> insert_unique(reference value)
{
insert_commit_data commit_data;
std::pair<iterator, bool> ret = this->insert_unique_check
(value, this->comp(), this->priv_pcomp(), commit_data);
std::pair<iterator, bool> ret = this->insert_unique_check(key_of_value()(value), commit_data);
if(!ret.second)
return ret;
return std::pair<iterator, bool> (this->insert_unique_commit(value, commit_data), true);
Expand All @@ -514,8 +510,7 @@ class treap_impl
iterator insert_unique(const_iterator hint, reference value)
{
insert_commit_data commit_data;
std::pair<iterator, bool> ret = this->insert_unique_check
(hint, value, this->comp(), this->priv_pcomp(), commit_data);
std::pair<iterator, bool> ret = this->insert_unique_check(hint, key_of_value()(value), commit_data);
if(!ret.second)
return ret.first;
return this->insert_unique_commit(value, commit_data);
Expand Down Expand Up @@ -549,6 +544,68 @@ class treap_impl
}
}

//! <b>Effects</b>: Checks if a value can be inserted in the container, using
//! a user provided key instead of the value itself.
//!
//! <b>Returns</b>: If there is an equivalent value
//! returns a pair containing an iterator to the already present value
//! and false. If the value can be inserted returns true in the returned
//! pair boolean and fills "commit_data" that is meant to be used with
//! the "insert_commit" function.
//!
//! <b>Complexity</b>: Average complexity is at most logarithmic.
//!
//! <b>Throws</b>: If the comparison or predicate functions throw. Strong guarantee.
//!
//! <b>Notes</b>: This function is used to improve performance when constructing
//! a value_type is expensive: if there is an equivalent value
//! the constructed object must be discarded. Many times, the part of the
//! node that is used to impose the order is much cheaper to construct
//! than the value_type and this function offers the possibility to use that
//! part to check if the insertion will be successful.
//!
//! If the check is successful, the user can construct the value_type and use
//! "insert_commit" to insert the object in constant-time. This gives a total
//! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
//!
//! "commit_data" remains valid for a subsequent "insert_commit" only if no more
//! objects are inserted or erased from the container.
std::pair<iterator, bool> insert_unique_check
( const key_type &key, insert_commit_data &commit_data)
{ return this->insert_unique_check(key, this->key_comp(), this->priv_pcomp(), commit_data); }

//! <b>Effects</b>: Checks if a value can be inserted in the container, using
//! a user provided key instead of the value itself, using "hint"
//! as a hint to where it will be inserted.
//!
//! <b>Returns</b>: If there is an equivalent value
//! returns a pair containing an iterator to the already present value
//! and false. If the value can be inserted returns true in the returned
//! pair boolean and fills "commit_data" that is meant to be used with
//! the "insert_commit" function.
//!
//! <b>Complexity</b>: Logarithmic in general, but it's amortized
//! constant time if t is inserted immediately before hint.
//!
//! <b>Throws</b>: If the comparison or predicate functions throw. Strong guarantee.
//!
//! <b>Notes</b>: This function is used to improve performance when constructing
//! a value_type is expensive: if there is an equivalent value
//! the constructed object must be discarded. Many times, the part of the
//! constructing that is used to impose the order is much cheaper to construct
//! than the value_type and this function offers the possibility to use that key
//! to check if the insertion will be successful.
//!
//! If the check is successful, the user can construct the value_type and use
//! "insert_commit" to insert the object in constant-time. This can give a total
//! constant-time complexity to the insertion: check(O(1)) + commit(O(1)).
//!
//! "commit_data" remains valid for a subsequent "insert_commit" only if no more
//! objects are inserted or erased from the container.
std::pair<iterator, bool> insert_unique_check
( const_iterator hint, const key_type &key, insert_commit_data &commit_data)
{ return this->insert_unique_check(hint, key, this->key_comp(), this->priv_pcomp(), commit_data); }

//! <b>Requires</b>: comp must be a comparison function that induces
//! the same strict weak ordering as key_compare.
//! key_value_pcomp must be a comparison function that induces
Expand Down Expand Up @@ -583,7 +640,11 @@ class treap_impl
//! "commit_data" remains valid for a subsequent "insert_commit" only if no more
//! objects are inserted or erased from the container.
template<class KeyType, class KeyTypeKeyCompare, class KeyValuePrioCompare>
std::pair<iterator, bool> insert_unique_check
BOOST_INTRUSIVE_DOC1ST(std::pair<iterator BOOST_INTRUSIVE_I bool>
, typename detail::disable_if_convertible
<KeyType BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I
std::pair<iterator BOOST_INTRUSIVE_I bool> >::type)
insert_unique_check
( const KeyType &key, KeyTypeKeyCompare comp
, KeyValuePrioCompare key_value_pcomp, insert_commit_data &commit_data)
{
Expand Down Expand Up @@ -689,7 +750,11 @@ class treap_impl
BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert));
iterator ret
( node_algorithms::insert_before
( this->tree_type::header_ptr(), pos.pointed_node(), to_insert, this->value_node_prio_comp())
( this->tree_type::header_ptr()
, pos.pointed_node()
, to_insert
, this->key_node_prio_comp(this->priv_pcomp())
)
, this->priv_value_traits_ptr());
this->tree_type::sz_traits().increment();
return ret;
Expand All @@ -713,7 +778,8 @@ class treap_impl
{
node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert));
node_algorithms::push_back(this->tree_type::header_ptr(), to_insert, this->value_node_prio_comp());
node_algorithms::push_back
(this->tree_type::header_ptr(), to_insert, this->key_node_prio_comp(this->priv_pcomp()));
this->tree_type::sz_traits().increment();
}

Expand All @@ -735,7 +801,8 @@ class treap_impl
{
node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert));
node_algorithms::push_front(this->tree_type::header_ptr(), to_insert, this->value_node_prio_comp());
node_algorithms::push_front
(this->tree_type::header_ptr(), to_insert, this->key_node_prio_comp(this->priv_pcomp()));
this->tree_type::sz_traits().increment();
}

Expand All @@ -753,7 +820,8 @@ class treap_impl
++ret;
node_ptr to_erase(i.pointed_node());
BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(to_erase));
node_algorithms::erase(this->tree_type::header_ptr(), to_erase, this->value_node_prio_comp());
node_algorithms::erase
(this->tree_type::header_ptr(), to_erase, this->key_node_prio_comp(this->priv_pcomp()));
this->tree_type::sz_traits().decrement();
if(safemode_or_autounlink)
node_algorithms::init(to_erase);
Expand Down Expand Up @@ -933,8 +1001,10 @@ class treap_impl
template <class ExtraChecker>
void check(ExtraChecker extra_checker) const
{
typedef detail::key_nodeptr_comp<priority_compare, value_traits, key_of_value> nodeptr_prio_comp_t;
tree_type::check(detail::treap_node_extra_checker
<ValueTraits, value_node_prio_comp_t, ExtraChecker>(this->value_node_prio_comp(), extra_checker));
<ValueTraits, nodeptr_prio_comp_t, ExtraChecker>
(this->key_node_prio_comp(this->priv_pcomp()), extra_checker));
}

//! @copydoc ::boost::intrusive::bstree::check()const
Expand Down
9 changes: 9 additions & 0 deletions include/boost/intrusive/treap_set.hpp
View file
Expand Up @@ -229,6 +229,15 @@ class treap_set_impl
iterator insert(const_iterator hint, reference value)
{ return tree_type::insert_unique(hint, value); }

//! @copydoc ::boost::intrusive::treap::insert_unique_check(const key_type,insert_commit_data&)
std::pair<iterator, bool> insert_check( const key_type &key, insert_commit_data &commit_data)
{ return tree_type::insert_unique_check(key, commit_data); }

//! @copydoc ::boost::intrusive::treap::insert_unique_check(const_iterator,const key_type&,insert_commit_data&)
std::pair<iterator, bool> insert_check
( const_iterator hint, const key_type &key, insert_commit_data &commit_data)
{ return tree_type::insert_unique_check(hint, key, commit_data); }

//! @copydoc ::boost::intrusive::treap::insert_unique_check(const KeyType&,KeyTypeKeyCompare,KeyValuePrioCompare,insert_commit_data&)
template<class KeyType, class KeyTypeKeyCompare, class KeyValuePrioCompare>
std::pair<iterator, bool> insert_check
Expand Down
4 changes: 4 additions & 0 deletions include/boost/intrusive/unordered_set.hpp
View file
Expand Up @@ -208,6 +208,10 @@ class unordered_set_impl
void insert(Iterator b, Iterator e)
{ table_type::insert_unique(b, e); }

//! @copydoc ::boost::intrusive::hashtable::insert_unique_check(const key_type&,insert_commit_data&)
std::pair<iterator, bool> insert_check(const key_type &key, insert_commit_data &commit_data)
{ return table_type::insert_unique_check(key, commit_data); }

//! @copydoc ::boost::intrusive::hashtable::insert_unique_check(const KeyType&,KeyHasher,KeyEqual,insert_commit_data&)
template<class KeyType, class KeyHasher, class KeyEqual>
std::pair<iterator, bool> insert_check
Expand Down
22 changes: 9 additions & 13 deletions test/generic_set_test.hpp
View file
Expand Up @@ -191,14 +191,6 @@ struct prio_comp
{ return this->priority_compare<int>::operator()(k.int_value(), v.int_value()); }
};

template<class ValueType>
struct prio_comp<ValueType, ValueType>
: priority_compare<ValueType>
{
bool operator()(const ValueType &v1, const ValueType &v2) const
{ return this->priority_compare<ValueType>::operator()(v1, v2); }
};

template<class ValueTraits, class ContainerDefiner>
void test_generic_set<ValueTraits, ContainerDefiner>::test_insert_advanced
(value_cont_type& values, detail::true_type)
Expand All @@ -208,14 +200,16 @@ void test_generic_set<ValueTraits, ContainerDefiner>::test_insert_advanced
typedef typename set_type::key_of_value key_of_value;
typedef typename set_type::key_type key_type;
typedef typename set_type::value_type value_type;
typedef prio_comp<value_type, key_type> prio_comp_t;
typedef priority_compare<key_type> prio_comp_t;
{
set_type testset;
testset.insert(values.begin(), values.begin() + values.size());
value_type v(1);
typename set_type::insert_commit_data data;
BOOST_TEST (!testset.insert_check(key_of_value()(v), testset.key_comp(), prio_comp_t(), data).second);
BOOST_TEST (!testset.insert_check(testset.begin(), key_of_value()(v), testset.key_comp(), prio_comp_t(), data).second);
BOOST_TEST ((!testset.insert_check(key_of_value()(v), testset.key_comp(), prio_comp_t(), data).second));
BOOST_TEST ((!testset.insert_check(testset.begin(), key_of_value()(v), testset.key_comp(), prio_comp_t(), data).second));
BOOST_TEST ((!testset.insert_check(key_of_value()(v), data).second));
BOOST_TEST ((!testset.insert_check(testset.begin(), key_of_value()(v), data).second));
}
}

Expand All @@ -232,8 +226,10 @@ void test_generic_set<ValueTraits, ContainerDefiner>::test_insert_advanced
testset.insert(values.begin(), values.begin() + values.size());
value_type v(1);
typename set_type::insert_commit_data data;
BOOST_TEST (!testset.insert_check(key_of_value()(v), testset.key_comp(), data).second);
BOOST_TEST (!testset.insert_check(testset.begin(), key_of_value()(v), testset.key_comp(), data).second);
BOOST_TEST ((!testset.insert_check(key_of_value()(v), testset.key_comp(), data).second));
BOOST_TEST ((!testset.insert_check(testset.begin(), key_of_value()(v), testset.key_comp(), data).second));
BOOST_TEST ((!testset.insert_check(key_of_value()(v), data).second));
BOOST_TEST ((!testset.insert_check(testset.begin(), key_of_value()(v), data).second));
}
}

Expand Down
11 changes: 8 additions & 3 deletions test/unordered_test.hpp
View file
Expand Up @@ -78,14 +78,14 @@ void test_unordered<ValueTraits, ContainerDefiner>::
test::test_maybe_unique_container(testset, values, select_t());
}
{
value_cont_type values(BucketSize);
value_cont_type vals(BucketSize);
for (int i = 0; i < (int)BucketSize; ++i)
(&values[i])->value_ = i;
(&vals[i])->value_ = i;
typename unordered_type::bucket_type buckets [BucketSize];
unordered_type testset(bucket_traits(
pointer_traits<typename unordered_type::bucket_ptr>::
pointer_to(buckets[0]), BucketSize));
testset.insert(values.begin(), values.end());
testset.insert(vals.begin(), vals.end());
test::test_iterator_forward(testset);
}
test_sort(values);
Expand Down Expand Up @@ -162,13 +162,18 @@ void test_unordered<ValueTraits, ContainerDefiner>
typedef typename ContainerDefiner::template container
<>::type unordered_set_type;
typedef typename unordered_set_type::bucket_traits bucket_traits;
typedef typename unordered_set_type::key_of_value key_of_value;

typename unordered_set_type::bucket_type buckets [BucketSize];
unordered_set_type testset(bucket_traits(
pointer_traits<typename unordered_set_type::bucket_ptr>::
pointer_to(buckets[0]), BucketSize));
testset.insert(&values[0] + 2, &values[0] + 5);

typename unordered_set_type::insert_commit_data commit_data;
BOOST_TEST ((!testset.insert_check(key_of_value()(values[2]), commit_data).second));
BOOST_TEST (( testset.insert_check(key_of_value()(values[0]), commit_data).second));

const unordered_set_type& const_testset = testset;
if(unordered_set_type::incremental)
{
Expand Down