|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r81284 - in sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree: linear node quadratic rstar visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-10 08:29:08
Author: awulkiew
Date: 2012-11-10 08:29:07 EST (Sat, 10 Nov 2012)
New Revision: 81284
URL: http://svn.boost.org/trac/boost/changeset/81284
Log:
mem leaks related to exceptions fixed in linear redistribute_elements.
Text files modified:
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp | 137 +++++++++++++++++++++------------------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp | 23 ++++++
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 3
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp | 3
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 8 ++
5 files changed, 109 insertions(+), 65 deletions(-)
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp 2012-11-10 08:29:07 EST (Sat, 10 Nov 2012)
@@ -208,7 +208,8 @@
Box & box1,
Box & box2,
parameters_type const& parameters,
- Translator const& translator)
+ Translator const& translator,
+ Allocators & allocators)
{
typedef typename rtree::elements_type<Node>::type elements_type;
typedef typename elements_type::value_type element_type;
@@ -223,7 +224,7 @@
BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected number of elements");
// copy original elements
- elements_type elements_copy(elements1);
+ elements_type elements_copy(elements1); // MAY THROW
// calculate initial seeds
size_t seed1 = 0;
@@ -234,78 +235,90 @@
elements1.clear();
BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "unexpected container state");
- // add seeds
- elements1.push_back(elements_copy[seed1]);
- elements2.push_back(elements_copy[seed2]);
-
- // calculate boxes
- geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
- geometry::convert(rtree::element_indexable(elements_copy[seed2], translator), box2);
-
- // initialize areas
- content_type content1 = index::content(box1);
- content_type content2 = index::content(box2);
+ try
+ {
+ // add seeds
+ elements1.push_back(elements_copy[seed1]); // MAY THROW
+ elements2.push_back(elements_copy[seed2]); // MAY THROW
+
+ // calculate boxes
+ geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
+ geometry::convert(rtree::element_indexable(elements_copy[seed2], translator), box2);
+
+ // initialize areas
+ content_type content1 = index::content(box1);
+ content_type content2 = index::content(box2);
- BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements1_count, "unexpected elements number");
- size_t remaining = elements1_count - 2;
+ BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements1_count, "unexpected elements number");
+ size_t remaining = elements1_count - 2;
- // redistribute the rest of the elements
- for ( size_t i = 0 ; i < elements1_count ; ++i )
- {
- if (i != seed1 && i != seed2)
+ // redistribute the rest of the elements
+ for ( size_t i = 0 ; i < elements1_count ; ++i )
{
- element_type const& elem = elements_copy[i];
- indexable_type const& indexable = rtree::element_indexable(elem, translator);
-
- // if there is small number of elements left and the number of elements in node is lesser than min_elems
- // just insert them to this node
- if ( elements1.size() + remaining <= parameters.get_min_elements() )
- {
- elements1.push_back(elem);
- geometry::expand(box1, indexable);
- content1 = index::content(box1);
- }
- else if ( elements2.size() + remaining <= parameters.get_min_elements() )
- {
- elements2.push_back(elem);
- geometry::expand(box2, indexable);
- content2 = index::content(box2);
- }
- // choose better node and insert element
- else
+ if (i != seed1 && i != seed2)
{
- // calculate enlarged boxes and areas
- Box enlarged_box1(box1);
- Box enlarged_box2(box2);
- geometry::expand(enlarged_box1, indexable);
- geometry::expand(enlarged_box2, indexable);
- content_type enlarged_content1 = index::content(enlarged_box1);
- content_type enlarged_content2 = index::content(enlarged_box2);
-
- content_type content_increase1 = enlarged_content1 - content1;
- content_type content_increase2 = enlarged_content2 - content2;
-
- // choose group which box content have to be enlarged least or has smaller content or has fewer elements
- if ( content_increase1 < content_increase2 ||
- ( content_increase1 == content_increase2 && content1 < content2 ) ||
- ( content1 == content2 && elements1.size() <= elements2.size() ) )
+ element_type const& elem = elements_copy[i];
+ indexable_type const& indexable = rtree::element_indexable(elem, translator);
+
+ // if there is small number of elements left and the number of elements in node is lesser than min_elems
+ // just insert them to this node
+ if ( elements1.size() + remaining <= parameters.get_min_elements() )
{
- elements1.push_back(elem);
- box1 = enlarged_box1;
- content1 = enlarged_content1;
+ elements1.push_back(elem); // MAY THROW
+ geometry::expand(box1, indexable);
+ content1 = index::content(box1);
}
+ else if ( elements2.size() + remaining <= parameters.get_min_elements() )
+ {
+ elements2.push_back(elem); // MAY THROW
+ geometry::expand(box2, indexable);
+ content2 = index::content(box2);
+ }
+ // choose better node and insert element
else
{
- elements2.push_back(elem);
- box2 = enlarged_box2;
- content2 = enlarged_content2;
+ // calculate enlarged boxes and areas
+ Box enlarged_box1(box1);
+ Box enlarged_box2(box2);
+ geometry::expand(enlarged_box1, indexable);
+ geometry::expand(enlarged_box2, indexable);
+ content_type enlarged_content1 = index::content(enlarged_box1);
+ content_type enlarged_content2 = index::content(enlarged_box2);
+
+ content_type content_increase1 = enlarged_content1 - content1;
+ content_type content_increase2 = enlarged_content2 - content2;
+
+ // choose group which box content have to be enlarged least or has smaller content or has fewer elements
+ if ( content_increase1 < content_increase2 ||
+ ( content_increase1 == content_increase2 && content1 < content2 ) ||
+ ( content1 == content2 && elements1.size() <= elements2.size() ) )
+ {
+ elements1.push_back(elem); // MAY THROW
+ box1 = enlarged_box1;
+ content1 = enlarged_content1;
+ }
+ else
+ {
+ elements2.push_back(elem); // MAY THROW
+ box2 = enlarged_box2;
+ content2 = enlarged_content2;
+ }
}
- }
- assert(0 < remaining);
- --remaining;
+ assert(0 < remaining);
+ --remaining;
+ }
}
}
+ catch (...)
+ {
+ elements1.clear();
+ elements2.clear();
+
+ rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_copy, allocators);
+
+ throw; // RETHROW
+ }
}
};
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-10 08:29:07 EST (Sat, 10 Nov 2012)
@@ -53,6 +53,29 @@
return result;
}
+// destroys stored subtrees if internal node's elements are passed
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+struct destroy_elements
+{
+ typedef typename Options::parameters_type parameters_type;
+
+ 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;
+
+ typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+
+ inline static void apply(typename internal_node::elements_type & elements, Allocators & allocators)
+ {
+ for ( size_t i = 0 ; i < elements.size() ; ++i )
+ {
+ node_auto_ptr dummy(elements[i].second, allocators);
+ elements[i].second = 0;
+ }
+ }
+
+ inline static void apply(typename leaf::elements_type &, Allocators &) {}
+};
+
}} // namespace detail::rtree
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp 2012-11-10 08:29:07 EST (Sat, 10 Nov 2012)
@@ -94,7 +94,8 @@
Box & box1,
Box & box2,
parameters_type const& parameters,
- Translator const& translator)
+ Translator const& translator,
+ Allocators & allocators)
{
typedef typename rtree::elements_type<Node>::type elements_type;
typedef typename elements_type::value_type element_type;
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp 2012-11-10 08:29:07 EST (Sat, 10 Nov 2012)
@@ -334,7 +334,8 @@
Box & box1,
Box & box2,
parameters_type const& parameters,
- Translator const& translator)
+ Translator const& translator,
+ Allocators & allocators)
{
typedef typename rtree::elements_type<Node>::type elements_type;
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2012-11-10 08:29:07 EST (Sat, 10 Nov 2012)
@@ -139,6 +139,12 @@
// create reference to the newly created node
Node & n2 = rtree::get<Node>(*second_node);
+ // After throwing an exception by redistribute_elements both nodes may be empty.
+ // The tree won't be valid r-tree.
+ // The alternative is to create 2 (or more) additional nodes here and store backup info
+ // in the original node, but then, if exception was thrown, the node would have more than max
+ // elements which also is not allowed in the r-tree.
+
// redistribute elements
Box box2;
redistribute_elements<
@@ -148,7 +154,7 @@
Box,
Allocators,
typename Options::redistribute_tag
- >::apply(n, n2, n_box, box2, parameters, translator); // MAY THROW
+ >::apply(n, n2, n_box, box2, parameters, translator, allocators); // MAY THROW
// check numbers of elements
BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() &&
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