|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r81340 - in sandbox-branches/geometry/index_dev: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/node boost/geometry/extensions/index/rtree/visitors test/rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-14 09:37:10
Author: awulkiew
Date: 2012-11-14 09:37:09 EST (Wed, 14 Nov 2012)
New Revision: 81340
URL: http://svn.boost.org/trac/boost/changeset/81340
Log:
mem leaks related exceptions in rtree copying fixed
Text files modified:
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp | 38 ++++++
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp | 231 ++++++++++++++++++++++++---------------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/copy.hpp | 20 ++-
sandbox-branches/geometry/index_dev/test/rtree/rtree_exceptions.cpp | 31 +++++
4 files changed, 225 insertions(+), 95 deletions(-)
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp 2012-11-14 09:37:09 EST (Wed, 14 Nov 2012)
@@ -31,6 +31,8 @@
#include <boost/geometry/algorithms/expand.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace detail { namespace rtree {
@@ -113,6 +115,42 @@
{}
};
+// clears node, deletes all subtrees stored in node
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+struct clear_node
+{
+ typedef typename Options::parameters_type parameters_type;
+
+ typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+
+ inline static void apply(node & node, Allocators & allocators)
+ {
+ rtree::visitors::is_leaf<Value, Options, Box, Allocators> ilv;
+ rtree::apply_visitor(ilv, node);
+ if ( ilv.result )
+ {
+ apply(rtree::get<leaf>(node), allocators);
+ }
+ else
+ {
+ apply(rtree::get<internal_node>(node), allocators);
+ }
+ }
+
+ inline static void apply(internal_node & internal_node, Allocators & allocators)
+ {
+ destroy_elements<Value, Options, Translator, Box, Allocators>::apply(rtree::elements(internal_node), allocators);
+ rtree::elements(internal_node).clear();
+ }
+
+ inline static void apply(leaf & leaf, Allocators &)
+ {
+ rtree::elements(leaf).clear();
+ }
+};
+
}} // namespace detail::rtree
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp 2012-11-14 09:37:09 EST (Wed, 14 Nov 2012)
@@ -96,6 +96,8 @@
/*!
The constructor.
+ \note Exception-safety: strong
+
\param parameters The parameters object.
\param translator The translator object.
\param allocator The allocator object.
@@ -114,6 +116,8 @@
/*!
The constructor.
+ \note Exception-safety: strong
+
\param first The beginning of the range of Values.
\param last The end of the range of Values.
\param parameters The parameters object.
@@ -130,60 +134,64 @@
, m_allocators(allocator)
{
this->create();
- this->insert(first, last);
+
+ try
+ {
+ this->insert(first, last);
+ }
+ catch(...)
+ {
+ this->destroy(*this);
+ throw;
+ }
}
/*!
The destructor.
+
+ \note Exception-safety: strong
*/
inline ~rtree()
{
+// TODO: after moving assignment, rvalue will have root == 0
if ( m_root )
this->destroy(*this);
}
/*!
The copy constructor.
+
+ \note Exception-safety: strong
*/
inline rtree(rtree const& src)
- : m_parameters(src.m_parameters)
+ : m_root(0)
+ , m_parameters(src.m_parameters)
, m_translator(src.m_translator)
, m_allocators(src.m_allocators)
{
//TODO use Boost.Container allocator_traits_type::select_on_container_copy_construction()
- try
- {
- this->copy(src, *this);
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ this->copy(src, *this, m_allocators);
}
/*!
The copy constructor.
+
+ \note Exception-safety: strong
*/
inline rtree(rtree const& src, Allocator const& allocator)
- : m_parameters(src.m_parameters)
+ : m_root(0)
+ , m_parameters(src.m_parameters)
, m_translator(src.m_translator)
, m_allocators(allocator)
{
- try
- {
- this->copy(src, *this);
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ this->copy(src, *this, m_allocators);
}
/*!
The moving constructor.
+
+ \note Exception-safety: strong
*/
inline rtree(BOOST_RV_REF(rtree) src)
: m_values_count(src.m_values_count)
@@ -196,73 +204,60 @@
src.m_values_count = 0;
src.m_root = 0;
src.m_leafs_level = 0;
+// TODO: after moving, rvalue will have root == 0
+// This would leave the tree unusable
+// Write the test
}
/*!
The assignment operator.
+
+ \note Exception-safety: strong
*/
inline rtree & operator=(BOOST_COPY_ASSIGN_REF(rtree) src)
{
if ( this == &src )
return *this;
- if ( !this->empty() )
- this->destroy(*this);
-
- m_parameters = src.m_parameters;
- m_translator = src.m_translator;
//TODO use Boost.Container allocator_traits_type::propagate_on_container_move_assignment
- //m_allocators = src.m_allocators;
- try
- {
- this->copy(src, *this);
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ this->copy(src, *this, m_allocators);
return *this;
}
/*!
The moving assignment.
+
+ \note Exception-safety: strong
*/
inline rtree & operator=(BOOST_RV_REF(rtree) src)
{
if ( this == &src )
return *this;
- if ( !this->empty() )
- this->destroy(*this);
-
- m_parameters = src.m_parameters;
- m_translator = src.m_translator;
//TODO use Boost.Container allocator_traits_type::propagate_on_container_move_assignment
- //m_allocators = src.m_allocators;
if ( m_allocators.allocator == src.m_allocators.allocator )
{
+ m_parameters = src.m_parameters;
+ m_translator = src.m_translator;
+ //m_allocators = src.m_allocators;
+
m_values_count = src.m_values_count;
src.m_values_count = 0;
m_root = src.m_root;
src.m_root = 0;
m_leafs_level = src.m_leafs_level;
src.m_leafs_level = 0;
+
+// TODO: after moving, rvalue will have root == 0
+// This would leave the tree unusable
+// Write the test
}
else
{
- try
- {
- this->copy(src, *this);
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ this->copy(src, *this, m_allocators);
}
return *this;
@@ -271,6 +266,8 @@
/*!
Insert a value to the index.
+ \note Exception-safety: basic
+
\param value The value which will be stored in the container.
*/
inline void insert(value_type const& value)
@@ -279,23 +276,26 @@
detail::rtree::visitors::insert<
value_type,
- value_type,
- options_type,
- translator_type,
- box_type,
- allocators_type,
+ value_type, options_type, translator_type, box_type, allocators_type,
typename options_type::insert_tag
> insert_v(m_root, m_leafs_level, value, m_parameters, m_translator, m_allocators);
detail::rtree::apply_visitor(insert_v, *m_root);
- // If exception is thrown, m_values_count is invalid
+// TODO
+// Think about this: If exception is thrown, may the root be removed?
+// Or it is just cleared?
+
+// TODO
+// If exception is thrown, m_values_count may be invalid
++m_values_count;
}
/*!
Insert a range of values to the index.
+ \note Exception-safety: basic
+
\param first The beginning of the range of values.
\param last The end of the range of values.
*/
@@ -309,6 +309,8 @@
/*!
Remove the value from the container.
+ \note Exception-safety: basic
+
\param value The value which will be removed from the container.
*/
inline void remove(value_type const& value)
@@ -317,30 +319,26 @@
BOOST_GEOMETRY_INDEX_ASSERT(0 < m_values_count, "can't remove, there are no elements in the rtree");
- try
- {
- detail::rtree::visitors::remove<
- value_type,
- options_type,
- translator_type,
- box_type,
- allocators_type
- > remove_v(m_root, m_leafs_level, value, m_parameters, m_translator, m_allocators);
-
- detail::rtree::apply_visitor(remove_v, *m_root);
-
- --m_values_count;
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ detail::rtree::visitors::remove<
+ value_type, options_type, translator_type, box_type, allocators_type
+ > remove_v(m_root, m_leafs_level, value, m_parameters, m_translator, m_allocators);
+
+ detail::rtree::apply_visitor(remove_v, *m_root);
+
+// TODO
+// Think about this: If exception is thrown, may the root be removed?
+// Or it is just cleared?
+
+// TODO
+// If exception is thrown, m_values_count may be invalid
+ --m_values_count;
}
/*!
Remove the range of values from the container.
+ \note Exception-safety: basic
+
\param first The beginning of the range of values.
\param last The end of the range of values.
*/
@@ -354,6 +352,8 @@
/*!
Find values meeting spatial predicates, e.g. intersecting some box.
+ \note Exception-safety: strong
+
\param pred The spatial predicates. May be a Geometry (in this case default
predicate - intersects is used) or generated by bgi::covered_by(geometry),
bgi::disjoint(geometry), bgi::intersects(geometry), bgi::overlaps(geometry),
@@ -381,6 +381,8 @@
/*!
Find one value meeting distances predicates, e.g. nearest to some point.
+ \note Exception-safety: strong
+
\param dpred The distances predicates. May be a Point. This is default case where Value which
nearest point is closest to Point is returned. May be a PointRelation which define
how distance to Value is calculated. This may be generated by bgi::to_nearest(Point),
@@ -405,6 +407,8 @@
Find one value meeting distances predicates and spatial predicates,
e.g. nearest to some point and intersecting some box.
+ \note Exception-safety: strong
+
\param dpred The distances predicates. May be a Point. This is default case where Value which
nearest point is closest to Point is returned. May be a PointRelation which define
how distance to Value is calculated. This may be generated by bgi::to_nearest(Point),
@@ -434,6 +438,8 @@
/*!
Find k values meeting distances predicates, e.g. k nearest values to some point.
+ \note Exception-safety: strong
+
\param dpred The distances predicates. May be a Point. This is default case where Value which
nearest point is closest to Point is returned. May be a PointRelation which define
how distance to Value is calculated. This may be generated by bgi::to_nearest(Point),
@@ -458,6 +464,8 @@
Find k values meeting distances predicates and spatial predicates,
e.g. k nearest values to some point and intersecting some box.
+ \note Exception-safety: strong
+
\param dpred The distances predicates. May be a Point. This is default case where Value which
nearest point is closest to Point is returned. May be a PointRelation which define
how distance to Value is calculated. This may be generated by bgi::to_nearest(Point),
@@ -488,6 +496,8 @@
/*!
Returns the number of stored values.
+ \note Exception-safety: nothrow
+
\return The number of stored values.
*/
inline size_type size() const
@@ -498,6 +508,8 @@
/*!
Query if the container is empty.
+ \note Exception-safety: nothrow
+
\return true if the container is empty.
*/
inline bool empty() const
@@ -507,17 +519,20 @@
/*!
Removes all values stored in the container.
+
+ \note Exception-safety: nothrow.
*/
inline void clear()
{
- this->destroy(*this);
- this->create();
+ this->destroy(*this, false);
}
/*!
Returns the box containing all values stored in the container.
If the container is empty the result of geometry::assign_inverse() is returned.
+ \note Exception-safety: nothrow.
+
\return The box containing all values stored in the container or an invalid box if
there are no values in the container.
*/
@@ -541,6 +556,8 @@
/*!
Returns allocator used by the rtree.
+ \note Exception-safety: nothrow if allocator copy can't throw.
+
\return The allocator.
*/
allocator_type get_allocator() const
@@ -553,6 +570,8 @@
This function is not a part of the 'official' interface. However it makes
possible to e.g. draw the tree structure.
+ \note Exception-safety: the same as visitor.
+
\param visitor The visitor object.
*/
template <typename Visitor>
@@ -565,6 +584,8 @@
Returns the translator object.
This function is not a part of the 'official' interface.
+ \note Exception-safety: nothrow.
+
\return The translator object.
*/
inline translator_type const& translator() const
@@ -574,7 +595,9 @@
/*!
Returns the number of stored objects. Same as size()
- This function is not a part of the 'official' interface.
+ This function is not a part of the 'official' interface.
+
+ \note Exception-safety: nothrow.
\return The number of stored objects.
*/
@@ -585,7 +608,9 @@
/*!
Returns the depth of the R-tree.
- This function is not a part of the 'official' interface.
+ This function is not a part of the 'official' interface.
+
+ \note Exception-safety: nothrow.
\return The depth of the R-tree.
*/
@@ -597,12 +622,14 @@
private:
/*!
Create an empty R-tree i.e. new empty root node and clear other attributes.
+
+ \note Exception-safety: strong.
*/
inline void create()
{
- assert(0 == m_root);
+ BOOST_GEOMETRY_INDEX_ASSERT(0 == m_root, "the tree is already created");
- m_root = detail::rtree::create_node<allocators_type, leaf>::apply(m_allocators);
+ m_root = detail::rtree::create_node<allocators_type, leaf>::apply(m_allocators); // MAY THROW (N: alloc)
m_values_count = 0;
m_leafs_level = 0;
}
@@ -610,12 +637,23 @@
/*!
Destroy the R-tree i.e. all nodes and clear attributes.
+ \note Exception-safety: nothrow.
+
\param t The container which is going to be destroyed.
*/
- inline void destroy(rtree & t)
+ inline void destroy(rtree & t, bool destroy_root = true)
{
- detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type> del_v(t.m_root, t.m_allocators);
- detail::rtree::apply_visitor(del_v, *t.m_root);
+ BOOST_GEOMETRY_INDEX_ASSERT(t.m_root, "can't destroy empty tree");
+
+ if ( destroy_root )
+ {
+ detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type> del_v(t.m_root, t.m_allocators);
+ detail::rtree::apply_visitor(del_v, *t.m_root);
+ }
+ else
+ {
+ detail::rtree::clear_node<value_type, options_type, translator_type, box_type, allocators_type>::apply(*t.m_root, t.m_allocators);
+ }
t.m_root = 0;
t.m_values_count = 0;
@@ -625,13 +663,26 @@
/*!
Copy the R-tree i.e. whole nodes structure, values and other attributes.
+ \note Exception-safety: strong.
+
\param src The source R-tree.
\param dst The destination R-tree.
*/
- inline void copy(rtree const& src, rtree & dst) const
+ inline void copy(rtree const& src, rtree & dst, allocators_type & allocators) const
{
- detail::rtree::visitors::copy<value_type, options_type, translator_type, box_type, allocators_type> copy_v(dst.m_allocators);
- detail::rtree::apply_visitor(copy_v, *src.m_root);
+ detail::rtree::visitors::copy<value_type, options_type, translator_type, box_type, allocators_type> copy_v(allocators);
+ detail::rtree::apply_visitor(copy_v, *src.m_root); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+
+ if ( dst.m_root )
+ {
+ detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type> del_v(dst.m_root, dst.m_allocators);
+ detail::rtree::apply_visitor(del_v, *dst.m_root);
+ dst.m_root = 0;
+ }
+
+ dst.m_parameters = src.m_parameters;
+ dst.m_translator = src.m_translator;
+ dst.m_allocators = allocators;
dst.m_root = copy_v.result;
dst.m_values_count = src.m_values_count;
@@ -640,6 +691,8 @@
/*!
Find one value meeting distances and spatial predicates.
+
+ \note Exception-safety: strong.
*/
template <typename DistancesPredicates, typename Predicates>
inline size_type nearest_one(DistancesPredicates const& dpred, Predicates const& pred, value_type & v) const
@@ -673,6 +726,8 @@
/*!
Find k values meeting distances and spatial predicates.
+
+ \note Exception-safety: strong.
*/
template <typename DistancesPredicates, typename Predicates, typename OutIter>
inline size_type nearest_k(DistancesPredicates const& dpred, size_t k, Predicates const& pred, OutIter out_it) const
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/copy.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/copy.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/copy.hpp 2012-11-14 09:37:09 EST (Wed, 14 Nov 2012)
@@ -27,6 +27,8 @@
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+ typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+
explicit inline copy(Allocators & allocators)
: result(0)
, m_allocators(allocators)
@@ -34,7 +36,8 @@
inline void operator()(internal_node & n)
{
- node * new_node = rtree::create_node<Allocators, internal_node>::apply(m_allocators);
+ node * raw_new_node = rtree::create_node<Allocators, internal_node>::apply(m_allocators); // MAY THROW (N: alloc)
+ node_auto_ptr new_node(raw_new_node, m_allocators);
typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type & elements = rtree::elements(n);
@@ -46,16 +49,18 @@
{
rtree::apply_visitor(*this, *it->second);
- elements_dst.push_back( std::make_pair(it->first, result) );
+ elements_dst.push_back( std::make_pair(it->first, result) ); // MAY THROW (E: alloc)
}
- result = new_node;
+ result = new_node.get();
+ new_node.release();
}
inline void operator()(leaf & l)
{
- node * new_node = rtree::create_node<Allocators, leaf>::apply(m_allocators);
-
+ node * raw_new_node = rtree::create_node<Allocators, leaf>::apply(m_allocators); // MAY THROW (N: alloc)
+ node_auto_ptr new_node(raw_new_node, m_allocators);
+
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type & elements = rtree::elements(l);
@@ -64,10 +69,11 @@
for (typename elements_type::iterator it = elements.begin();
it != elements.end(); ++it)
{
- elements_dst.push_back(*it);
+ elements_dst.push_back(*it); // MAY THROW (V: alloc, copy)
}
- result = new_node;
+ result = new_node.get();
+ new_node.release();
}
node * result;
Modified: sandbox-branches/geometry/index_dev/test/rtree/rtree_exceptions.cpp
==============================================================================
--- sandbox-branches/geometry/index_dev/test/rtree/rtree_exceptions.cpp (original)
+++ sandbox-branches/geometry/index_dev/test/rtree/rtree_exceptions.cpp 2012-11-14 09:37:09 EST (Wed, 14 Nov 2012)
@@ -54,6 +54,37 @@
BOOST_CHECK_THROW( tree.remove(input.begin(), input.end()), throwing_value_copy_exception );
}
+
+ for ( size_t i = 0 ; i < 20 ; i += 2 )
+ {
+ throwing_value::reset_calls_counter();
+ throwing_value::set_max_calls(10000);
+
+ Tree tree(parameters);
+
+ tree.insert(input.begin(), input.end());
+
+ throwing_value::reset_calls_counter();
+ throwing_value::set_max_calls(i);
+
+ BOOST_CHECK_THROW( Tree tree2(tree), throwing_value_copy_exception );
+ }
+
+ for ( size_t i = 0 ; i < 20 ; i += 2 )
+ {
+ throwing_value::reset_calls_counter();
+ throwing_value::set_max_calls(10000);
+
+ Tree tree(parameters);
+ Tree tree2(parameters);
+
+ tree.insert(input.begin(), input.end());
+
+ throwing_value::reset_calls_counter();
+ throwing_value::set_max_calls(i);
+
+ BOOST_CHECK_THROW(tree2 = tree, throwing_value_copy_exception );
+ }
}
int test_main(int, char* [])
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk