Subject: [Boost-commit] svn:boost r81325 - in sandbox-branches/geometry/index_dev: boost/geometry/extensions/index boost/geometry/extensions/index/rtree/node boost/geometry/extensions/index/rtree/quadratic boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors test/rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-13 17:13:18
Author: awulkiew
Date: 2012-11-13 17:13:17 EST (Tue, 13 Nov 2012)
New Revision: 81325
URL: http://svn.boost.org/trac/boost/changeset/81325
Log:
mem leaks related to exceptions in remove fixed
Text files modified:
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/pushable_array.hpp | 8
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp | 19 +
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 16
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 409 ++++++++++++++++++++-------------------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 52 +++-
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 126 +++++++----
sandbox-branches/geometry/index_dev/test/rtree/rtree_exceptions.cpp | 24 ++
sandbox-branches/geometry/index_dev/test/rtree/test_rtree_exceptions.hpp | 5
8 files changed, 385 insertions(+), 274 deletions(-)
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/pushable_array.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/pushable_array.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/pushable_array.hpp 2012-11-13 17:13:17 EST (Tue, 13 Nov 2012)
@@ -138,7 +138,13 @@
BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
BOOST_GEOMETRY_INDEX_ASSERT(begin() <= it && it < end(), "iterator points on the element outside the container");
//std::copy(it + 1, end(), it);
- *it = back();
+ // TODO: leave this code or use copy?
+ // code below may work differently than one might think about erase()
+ if ( it != (begin() + (m_size - 1)) )
+ {
+ // NOTE: without this condition assignment may call memcpy with the same 2 addresses
+ *it = back();
+ }
--m_size;
}
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-13 17:13:17 EST (Tue, 13 Nov 2012)
@@ -93,7 +93,24 @@
}
}
- inline static void apply(typename leaf::elements_type &, Allocators &) {}
+ inline static void apply(typename leaf::elements_type &, Allocators &)
+ {}
+
+ inline static void apply(typename internal_node::elements_type::iterator first,
+ typename internal_node::elements_type::iterator last,
+ Allocators & allocators)
+ {
+ for ( ; first != last ; ++first )
+ {
+ node_auto_ptr dummy(first->second, allocators);
+ first->second = 0;
+ }
+ }
+
+ inline static void apply(typename leaf::elements_type::iterator first,
+ typename leaf::elements_type::iterator last,
+ Allocators &)
+ {}
};
}} // namespace detail::rtree
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-13 17:13:17 EST (Tue, 13 Nov 2012)
@@ -90,11 +90,11 @@
template <typename Node>
static inline void apply(Node & n,
- Node & second_node,
- Box & box1,
- Box & box2,
+ Node & second_node,
+ 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;
@@ -102,11 +102,11 @@
typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
- elements_type & elements1 = rtree::elements(n);
- elements_type & elements2 = rtree::elements(second_node);
- const size_t elements1_count = parameters.get_max_elements() + 1;
+ elements_type & elements1 = rtree::elements(n);
+ elements_type & elements2 = rtree::elements(second_node);
+ const size_t elements1_count = parameters.get_max_elements() + 1;
- BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected elements number");
+ BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected elements number");
// copy original elements
elements_type elements_copy(elements1); // MAY THROW
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2012-11-13 17:13:17 EST (Tue, 13 Nov 2012)
@@ -29,15 +29,15 @@
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 typename Options::parameters_type parameters_type;
+ typedef typename Options::parameters_type parameters_type;
template <typename Node>
static inline void apply(typename rtree::elements_type<Node>::type & result_elements,
- Node & n,
- internal_node *parent,
- size_t current_child_index,
+ Node & n,
+ internal_node *parent,
+ size_t current_child_index,
parameters_type const& parameters,
- Translator const& translator,
+ Translator const& translator,
Allocators & allocators)
{
typedef typename rtree::elements_type<Node>::type elements_type;
@@ -46,13 +46,13 @@
// TODO: awulkiew - change second point_type to the point type of the Indexable?
typedef typename geometry::default_distance_result<point_type>::type distance_type;
- elements_type & elements = rtree::elements(n);
+ elements_type & elements = rtree::elements(n);
- const size_t elements_count = parameters.get_max_elements() + 1;
- const size_t reinserted_elements_count = parameters.get_reinserted_elements();
+ const size_t elements_count = parameters.get_max_elements() + 1;
+ const size_t reinserted_elements_count = parameters.get_reinserted_elements();
- BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
- BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number");
+ BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
+ BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number");
BOOST_GEOMETRY_INDEX_ASSERT(0 < reinserted_elements_count, "wrong value of elements to reinsert");
// calculate current node's center
@@ -63,14 +63,14 @@
typename index::detail::rtree::container_from_elements_type<
elements_type,
std::pair<distance_type, element_type>
- >::type sorted_elements(elements_count); // MAY THROW
+ >::type sorted_elements(elements_count); // MAY THROW (V: alloc, copy, E: alloc)
- for ( size_t i = 0 ; i < elements_count ; ++i )
+ for ( size_t i = 0 ; i < elements_count ; ++i )
{
point_type element_center;
geometry::centroid( rtree::element_indexable(elements[i], translator), element_center);
sorted_elements[i].first = geometry::comparable_distance(node_center, element_center);
- sorted_elements[i].second = elements[i]; // MAY THROW
+ sorted_elements[i].second = elements[i]; // MAY THROW (V: copy)
}
// sort elements by distances from center
@@ -78,20 +78,20 @@
sorted_elements.begin(),
sorted_elements.begin() + reinserted_elements_count,
sorted_elements.end(),
- distances_dsc<distance_type, element_type>); // MAY THROW
+ distances_dsc<distance_type, element_type>); // MAY THROW (V: copy)
// copy elements which will be reinserted
- result_elements.resize(reinserted_elements_count); // MAY THROW
+ result_elements.resize(reinserted_elements_count); // MAY THROW (V: alloc, copy?, E: alloc)
for ( size_t i = 0 ; i < reinserted_elements_count ; ++i )
- result_elements[i] = sorted_elements[i].second; // MAY THROW
+ result_elements[i] = sorted_elements[i].second; // MAY THROW (V: copy)
try
{
// copy remaining elements to the current node
size_t elements_new_count = elements_count - reinserted_elements_count;
- elements.resize(elements_new_count); // MIGHT THROW
+ elements.resize(elements_new_count); // SHOULDN'T THROW (new_size <= old size)
for ( size_t i = 0 ; i < elements_new_count ; ++i )
- elements[i] = sorted_elements[i + reinserted_elements_count].second; // MAY THROW
+ elements[i] = sorted_elements[i + reinserted_elements_count].second; // MAY THROW (V: copy)
}
catch(...)
{
@@ -100,7 +100,7 @@
for ( size_t i = 0 ; i < elements_count ; ++i )
destroy_element<Value, Options, Translator, Box, Allocators>::apply(sorted_elements[i].second, allocators);
- throw; // RETHROW
+ throw; // RETHROW
}
}
@@ -125,101 +125,101 @@
template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Box, typename Allocators>
struct level_insert_elements_type
{
- typedef typename rtree::elements_type<
- typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
- >::type type;
+ typedef typename rtree::elements_type<
+ typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
+ >::type type;
};
template <typename Value, typename Options, typename Box, typename Allocators>
struct level_insert_elements_type<0, Value, Value, Options, Box, Allocators>
{
- typedef typename rtree::elements_type<
- typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
- >::type type;
+ typedef typename rtree::elements_type<
+ typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
+ >::type type;
};
template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
struct level_insert_base
- : public detail::insert<Element, Value, Options, Translator, Box, Allocators>
+ : public detail::insert<Element, Value, Options, Translator, Box, Allocators>
{
- typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
- typedef typename base::node node;
- typedef typename base::internal_node internal_node;
- typedef typename base::leaf leaf;
-
- typedef typename level_insert_elements_type<InsertIndex, Element, Value, Options, Box, Allocators>::type elements_type;
- typedef typename Options::parameters_type parameters_type;
-
- inline level_insert_base(node* & root,
- size_t & leafs_level,
- Element const& element,
+ typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
+ typedef typename base::node node;
+ typedef typename base::internal_node internal_node;
+ typedef typename base::leaf leaf;
+
+ typedef typename level_insert_elements_type<InsertIndex, Element, Value, Options, Box, Allocators>::type elements_type;
+ typedef typename Options::parameters_type parameters_type;
+
+ inline level_insert_base(node* & root,
+ size_t & leafs_level,
+ Element const& element,
parameters_type const& parameters,
- Translator const& translator,
+ Translator const& translator,
Allocators & allocators,
- size_t relative_level)
- : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
- , result_relative_level(0)
- {}
-
- template <typename Node>
- inline void handle_possible_reinsert_or_split_of_root(Node &n)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
-
- result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
-
- // overflow
- if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
- {
- // node isn't root node
- if ( !base::m_traverse_data.current_is_root() )
- {
+ size_t relative_level)
+ : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
+ , result_relative_level(0)
+ {}
+
+ template <typename Node>
+ inline void handle_possible_reinsert_or_split_of_root(Node &n)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
+
+ result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
+
+ // overflow
+ if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
+ {
+ // node isn't root node
+ if ( !base::m_traverse_data.current_is_root() )
+ {
// NOTE: exception-safety
// After an exception result_elements may contain garbage
- rstar::remove_elements_to_reinsert<Value, Options, Translator, Box, Allocators>::apply(
- result_elements, n,
- base::m_traverse_data.parent, base::m_traverse_data.current_child_index,
- base::m_parameters, base::m_translator, base::m_allocators); // MAY THROW
- }
- // node is root node
- else
- {
- BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<Node>(base::m_root_node), "node should be the root node");
- base::split(n); // MAY THROW
- }
- }
- }
-
- template <typename Node>
- inline void handle_possible_split(Node &n) const
- {
- // overflow
- if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
- {
- base::split(n); // MAY THROW
- }
- }
-
- template <typename Node>
- inline void recalculate_aabb_if_necessary(Node &n) const
- {
- if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
- {
- // calulate node's new box
- base::m_traverse_data.current_element().first =
- elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator);
- }
- }
+ rstar::remove_elements_to_reinsert<Value, Options, Translator, Box, Allocators>::apply(
+ result_elements, n,
+ base::m_traverse_data.parent, base::m_traverse_data.current_child_index,
+ base::m_parameters, base::m_translator, base::m_allocators); // MAY THROW (V: alloc, copy, E: alloc)
+ }
+ // node is root node
+ else
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<Node>(base::m_root_node), "node should be the root node");
+ base::split(n); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+ }
+ }
+ }
+
+ template <typename Node>
+ inline void handle_possible_split(Node &n) const
+ {
+ // overflow
+ if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
+ {
+ base::split(n); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+ }
+ }
+
+ template <typename Node>
+ inline void recalculate_aabb_if_necessary(Node &n) const
+ {
+ if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
+ {
+ // calulate node's new box
+ base::m_traverse_data.current_element().first =
+ elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator);
+ }
+ }
- size_t result_relative_level;
- elements_type result_elements;
+ size_t result_relative_level;
+ elements_type result_elements;
};
template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
struct level_insert
: public level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators>
{
- typedef level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators> base;
+ typedef level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators> base;
typedef typename base::node node;
typedef typename base::internal_node internal_node;
typedef typename base::leaf leaf;
@@ -238,12 +238,12 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
if ( base::m_traverse_data.current_level < base::m_level )
{
// next traversing step
- base::traverse(*this, n); // MAY THROW
+ base::traverse(*this, n); // MAY THROW (E: alloc, N: alloc)
// further insert
if ( 0 < InsertIndex )
@@ -252,26 +252,40 @@
if ( base::m_traverse_data.current_level == base::m_level - 1 )
{
- base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, N: alloc)
}
}
}
else
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
-
- // push new child node
- rtree::elements(n).push_back(base::m_element); // MAY THROW
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
// first insert
if ( 0 == InsertIndex )
{
- base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW
+ try
+ {
+ // push new child node
+ rtree::elements(n).push_back(base::m_element); // MAY THROW (E: alloc)
+ }
+ catch(...)
+ {
+ // if the first insert fails here, the element won't be stored in the tree
+ rtree::visitors::destroy<Value, Options, Translator, Box, Allocators> del_v(base::m_element.second, base::m_allocators);
+ rtree::apply_visitor(del_v, *base::m_element.second);
+
+ throw; // RETHROW
+ }
+
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, N: alloc)
}
// not the first insert
else
{
- base::handle_possible_split(n); // MAY THROW
+ // push new child node
+ rtree::elements(n).push_back(base::m_element); // MAY THROW (E: alloc)
+
+ base::handle_possible_split(n); // MAY THROW (E: alloc, N: alloc)
}
}
@@ -307,17 +321,17 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
// next traversing step
- base::traverse(*this, n); // MAY THROW
+ base::traverse(*this, n); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
- BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
if ( base::m_traverse_data.current_level == base::m_level - 1 )
{
- base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, N: alloc)
}
base::recalculate_aabb_if_necessary(n);
@@ -325,15 +339,15 @@
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
- "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
- base::m_level == (std::numeric_limits<size_t>::max)(),
- "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
+ base::m_level == (std::numeric_limits<size_t>::max)(),
+ "unexpected level");
- rtree::elements(n).push_back(base::m_element); // MAY THROW
+ rtree::elements(n).push_back(base::m_element); // MAY THROW (V: alloc, copy)
- base::handle_possible_split(n); // MAY THROW
+ base::handle_possible_split(n); // MAY THROW (V: alloc, copy, N: alloc)
}
};
@@ -360,28 +374,28 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
- "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
- "unexpected level");
-
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
+ "unexpected level");
+
// next traversing step
- base::traverse(*this, n); // MAY THROW
+ base::traverse(*this, n); // MAY THROW (V: alloc, copy, N: alloc)
base::recalculate_aabb_if_necessary(n);
}
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
- "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
- base::m_level == (std::numeric_limits<size_t>::max)(),
- "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
+ base::m_level == (std::numeric_limits<size_t>::max)(),
+ "unexpected level");
- rtree::elements(n).push_back(base::m_element); // MAY THROW
+ rtree::elements(n).push_back(base::m_element); // MAY THROW (V: alloc, copy)
- base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (V: alloc, copy, N: alloc)
base::recalculate_aabb_if_necessary(n);
}
@@ -392,91 +406,94 @@
} // namespace detail
// R*-tree insert visitor
+// After passing the Element to insert visitor the Element is managed by the tree
+// I.e. one should not delete the node passed to the insert visitor after exception is thrown
+// because this visitor may delete it
template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
class insert<Element, Value, Options, Translator, Box, Allocators, insert_reinsert_tag>
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
- , index::nonassignable
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
+ , index::nonassignable
{
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;
+ 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;
public:
- inline insert(node* & root,
- size_t & leafs_level,
- Element const& element,
+ inline insert(node* & root,
+ size_t & leafs_level,
+ Element const& element,
parameters_type const& parameters,
- Translator const& translator,
+ Translator const& translator,
Allocators & allocators,
- size_t relative_level = 0)
- : m_root(root), m_leafs_level(leafs_level), m_element(element)
- , m_parameters(parameters), m_translator(translator)
+ size_t relative_level = 0)
+ : m_root(root), m_leafs_level(leafs_level), m_element(element)
+ , m_parameters(parameters), m_translator(translator)
, m_relative_level(relative_level), m_allocators(allocators)
- {}
+ {}
+
+ inline void operator()(internal_node & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(n))
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root), "current node should be the root");
+
+ detail::rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
+ m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
+
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+
+ if ( !lins_v.result_elements.empty() )
+ {
+ recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+ }
+ }
+
+ inline void operator()(leaf & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(n))
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<leaf>(m_root), "current node should be the root");
- inline void operator()(internal_node & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(n))
- {
- BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root), "current node should be the root");
-
- detail::rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
- m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
-
- rtree::apply_visitor(lins_v, *m_root); // MAY THROW
-
- if ( !lins_v.result_elements.empty() )
- {
- recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW
- }
- }
-
- inline void operator()(leaf & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(n))
- {
- BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<leaf>(m_root), "current node should be the root");
-
- detail::rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
- m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
-
- rtree::apply_visitor(lins_v, *m_root); // MAY THROW
-
- // we're in the root, so root should be split and there should be no elements to reinsert
- assert(lins_v.result_elements.empty());
- }
+ detail::rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
+ m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
+
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+
+ // we're in the root, so root should be split and there should be no elements to reinsert
+ assert(lins_v.result_elements.empty());
+ }
private:
- template <typename Elements>
- inline void recursive_reinsert(Elements const& elements, size_t relative_level)
- {
- typedef typename Elements::value_type element_type;
-
- // reinsert children starting from the minimum distance
- for ( typename Elements::const_reverse_iterator it = elements.rbegin();
- it != elements.rend(); ++it)
- {
- detail::rstar::level_insert<1, element_type, Value, Options, Translator, Box, Allocators> lins_v(
- m_root, m_leafs_level, *it, m_parameters, m_translator, m_allocators, relative_level);
-
- rtree::apply_visitor(lins_v, *m_root); // MAY THROW
-
- assert(relative_level + 1 == lins_v.result_relative_level);
-
- // non-root relative level
- if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty())
- {
- recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW
- }
- }
- }
-
- node* & m_root;
- size_t & m_leafs_level;
- Element const& m_element;
+ template <typename Elements>
+ inline void recursive_reinsert(Elements const& elements, size_t relative_level)
+ {
+ typedef typename Elements::value_type element_type;
+
+ // reinsert children starting from the minimum distance
+ for ( typename Elements::const_reverse_iterator it = elements.rbegin();
+ it != elements.rend(); ++it)
+ {
+ detail::rstar::level_insert<1, element_type, Value, Options, Translator, Box, Allocators> lins_v(
+ m_root, m_leafs_level, *it, m_parameters, m_translator, m_allocators, relative_level);
+
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+
+ assert(relative_level + 1 == lins_v.result_relative_level);
+
+ // non-root relative level
+ if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty())
+ {
+ recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+ }
+ }
+ }
+
+ node* & m_root;
+ size_t & m_leafs_level;
+ Element const& m_element;
parameters_type const& m_parameters;
- Translator const& m_translator;
+ Translator const& m_translator;
- size_t m_relative_level;
+ size_t m_relative_level;
Allocators m_allocators;
};
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-13 17:13:17 EST (Tue, 13 Nov 2012)
@@ -135,7 +135,7 @@
// TODO - consider creating nodes always with sufficient memory allocated
// create additional node, use auto ptr for automatic destruction on exception
- node_auto_ptr second_node(rtree::create_node<Allocators, Node>::apply(allocators), allocators); // MAY THROW
+ node_auto_ptr second_node(rtree::create_node<Allocators, Node>::apply(allocators), allocators); // MAY THROW (N: alloc)
// create reference to the newly created node
Node & n2 = rtree::get<Node>(*second_node);
@@ -157,7 +157,7 @@
Box,
Allocators,
typename Options::redistribute_tag
- >::apply(n, n2, n_box, box2, parameters, translator, allocators); // MAY THROW
+ >::apply(n, n2, n_box, box2, parameters, translator, allocators); // MAY THROW (V: alloc, copy, E: alloc)
// check numbers of elements
BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() &&
@@ -269,7 +269,7 @@
rtree::element_indexable(m_element, m_translator));
// next traversing step
- traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW
+ traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW (V: alloc, copy, E: alloc, N:alloc)
}
// TODO: awulkiew - change post_traverse name to handle_overflow or overflow_treatment?
@@ -284,7 +284,7 @@
// handle overflow
if ( m_parameters.get_max_elements() < rtree::elements(n).size() )
{
- split(n); // MAY THROW
+ split(n); // MAY THROW (V: alloc, copy, E: alloc, N:alloc)
}
}
@@ -298,7 +298,7 @@
m_traverse_data.move_to_next_level(&n, choosen_node_index);
// next traversing step
- rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second); // MAY THROW
+ rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V: alloc, copy, E: alloc, N:alloc)
// restore previous traverse inputs
m_traverse_data = backup_traverse_data;
@@ -314,7 +314,7 @@
typename split_algo::nodes_container_type additional_nodes;
Box n_box;
- split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators); // MAY THROW
+ split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators); // MAY THROW (V: alloc, copy, E: alloc, N:alloc)
BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
@@ -336,7 +336,7 @@
// update old node's box
m_traverse_data.current_element().first = n_box;
// add new node to parent's children
- m_traverse_data.parent_elements().push_back(additional_nodes[0]); // MAY THROW
+ m_traverse_data.parent_elements().push_back(additional_nodes[0]); // MAY THROW (V: alloc, copy, E: alloc)
}
// node is the root - add level
else
@@ -344,11 +344,11 @@
BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<Node>(m_root_node), "node should be the root");
// create new root and add nodes
- node_auto_ptr new_root(rtree::create_node<Allocators, internal_node>::apply(m_allocators), m_allocators); // MAY THROW
+ node_auto_ptr new_root(rtree::create_node<Allocators, internal_node>::apply(m_allocators), m_allocators); // MAY THROW (N:alloc)
try {
- rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(n_box, m_root_node)); // MAY THROW
- rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]); // MAY THROW
+ rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(n_box, m_root_node)); // MAY THROW (E:alloc)
+ rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]); // MAY THROW (E:alloc)
} catch (...) {
// clear new root to not delete in the ~node_auto_ptr() potentially stored old root node
rtree::elements(rtree::get<internal_node>(*new_root)).clear();
@@ -388,6 +388,9 @@
class insert;
// Default insert visitor used for nodes elements
+// After passing the Element to insert visitor the Element is managed by the tree
+// I.e. one should not delete the node passed to the insert visitor after exception is thrown
+// because this visitor may delete it
template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
class insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag>
: public detail::insert<Element, Value, Options, Translator, Box, Allocators>
@@ -402,7 +405,7 @@
inline insert(node* & root,
size_t & leafs_level,
- Element const& element,
+ Element & element,
parameters_type const& parameters,
Translator const& translator,
Allocators & allocators,
@@ -418,17 +421,28 @@
if ( base::m_traverse_data.current_level < base::m_level )
{
// next traversing step
- base::traverse(*this, n); // MAY THROW
+ base::traverse(*this, n); // MAY THROW (E: alloc, N: alloc)
}
else
{
BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
- // push new child node
- rtree::elements(n).push_back(base::m_element);
+ try
+ {
+ // push new child node
+ rtree::elements(n).push_back(base::m_element); // MAY THROW (E: alloc)
+ }
+ catch(...)
+ {
+ // if the insert fails here, the element won't be stored in the tree
+ rtree::visitors::destroy<Value, Options, Translator, Box, Allocators> del_v(base::m_element.second, base::m_allocators);
+ rtree::apply_visitor(del_v, *base::m_element.second);
+
+ throw; // RETHROW
+ }
}
- base::post_traverse(n); // MAY THROW
+ base::post_traverse(n); // MAY THROW (E: alloc, N: alloc)
}
inline void operator()(leaf &)
@@ -467,9 +481,9 @@
BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
// next traversing step
- base::traverse(*this, n); // MAY THROW
+ base::traverse(*this, n); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
- base::post_traverse(n); // MAY THROW
+ base::post_traverse(n); // MAY THROW (E: alloc, N: alloc)
}
inline void operator()(leaf & n)
@@ -478,9 +492,9 @@
BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
- rtree::elements(n).push_back(base::m_element); // MAY THROW
+ rtree::elements(n).push_back(base::m_element); // MAY THROW (V: alloc, copy)
- base::post_traverse(n); // MAY THROW
+ base::post_traverse(n); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
}
};
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/remove.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/remove.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/remove.hpp 2012-11-13 17:13:17 EST (Tue, 13 Nov 2012)
@@ -33,6 +33,8 @@
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;
+
public:
inline remove(node* & root,
size_t & leafs_level,
@@ -68,7 +70,7 @@
if ( geometry::covered_by(m_translator(m_value), children[child_node_index].first) )
{
// next traversing step
- traverse_apply_visitor(n, child_node_index);
+ traverse_apply_visitor(n, child_node_index); // MAY THROW
if ( m_is_value_removed )
break;
@@ -88,8 +90,9 @@
element_iterator underfl_el_it = elements.begin() + child_node_index;
// move node to the container - store node's relative level as well
- m_underflowed_nodes.push_back(std::make_pair(m_leafs_level - m_current_level, underfl_el_it->second));
- elements.erase(underfl_el_it);
+ m_underflowed_nodes.push_back(std::make_pair(m_leafs_level - m_current_level, underfl_el_it->second)); // MAY THROW (alloc)
+
+ elements.erase(underfl_el_it); // SHOULDN'T THROW
// calc underflow
m_is_underflow = elements.size() < m_parameters.get_min_elements();
@@ -112,26 +115,8 @@
BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root_node), "node must be the root");
BOOST_GEOMETRY_INDEX_ASSERT(m_is_value_removed, "value not found");
- // reinsert elements from removed nodes
- // begin with levels closer to the root
- for ( typename std::vector< std::pair<size_t, node*> >::reverse_iterator it = m_underflowed_nodes.rbegin();
- it != m_underflowed_nodes.rend() ; ++it )
- {
- is_leaf<Value, Options, Box, Allocators> ilv;
- rtree::apply_visitor(ilv, *it->second);
- if ( ilv.result )
- {
- reinsert_elements(rtree::get<leaf>(*it->second), it->first);
-
- rtree::destroy_node<Allocators, leaf>::apply(m_allocators, it->second);
- }
- else
- {
- reinsert_elements(rtree::get<internal_node>(*it->second), it->first);
-
- rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, it->second);
- }
- }
+ // reinsert elements from removed nodes (underflows)
+ reinsert_removed_nodes_elements(); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
// shorten the tree
if ( rtree::elements(n).size() == 1 )
@@ -156,7 +141,7 @@
{
if ( m_translator.equals(*it, m_value) )
{
- elements.erase(it);
+ elements.erase(it); // MAY THROW (V: copy)
m_is_value_removed = true;
break;
}
@@ -178,6 +163,9 @@
}
private:
+
+ typedef std::vector< std::pair<size_t, node*> > UnderflowNodes;
+
inline void traverse_apply_visitor(internal_node &n, size_t choosen_node_index)
{
// save previous traverse inputs and set new ones
@@ -190,7 +178,7 @@
++m_current_level;
// next traversing step
- rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second);
+ rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
// restore previous traverse inputs
m_parent = parent_bckup;
@@ -198,32 +186,78 @@
m_current_level = current_level_bckup;
}
+ void reinsert_removed_nodes_elements()
+ {
+ typename UnderflowNodes::reverse_iterator it = m_underflowed_nodes.rbegin();
+
+ try
+ {
+ // reinsert elements from removed nodes
+ // begin with levels closer to the root
+ for ( ; it != m_underflowed_nodes.rend() ; ++it )
+ {
+ is_leaf<Value, Options, Box, Allocators> ilv;
+ rtree::apply_visitor(ilv, *it->second);
+ if ( ilv.result )
+ {
+ reinsert_node_elements(rtree::get<leaf>(*it->second), it->first); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+
+ rtree::destroy_node<Allocators, leaf>::apply(m_allocators, it->second);
+ }
+ else
+ {
+ reinsert_node_elements(rtree::get<internal_node>(*it->second), it->first); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+
+ rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, it->second);
+ }
+ }
+
+ //m_underflowed_nodes.clear();
+ }
+ catch(...)
+ {
+ // destroy current and remaining nodes
+ for ( ; it != m_underflowed_nodes.rend() ; ++it )
+ {
+ node_auto_ptr dummy(it->second, m_allocators);
+ }
+
+ //m_underflowed_nodes.clear();
+
+ throw; // RETHROW
+ }
+ }
+
template <typename Node>
- void reinsert_elements(Node &n, size_t node_relative_level)
+ void reinsert_node_elements(Node &n, size_t node_relative_level)
{
typedef typename rtree::elements_type<Node>::type elements_type;
elements_type & elements = rtree::elements(n);
- for ( typename elements_type::iterator it = elements.begin();
- it != elements.end() ; ++it )
+
+ typename elements_type::iterator it = elements.begin();
+ try
{
- visitors::insert<
- typename elements_type::value_type,
- Value,
- Options,
- Translator,
- Box,
- Allocators,
- typename Options::insert_tag
- > insert_v(
- m_root_node,
- m_leafs_level,
- *it,
- m_parameters,
- m_translator,
- m_allocators,
- node_relative_level - 1);
+ for ( ; it != elements.end() ; ++it )
+ {
+ visitors::insert<
+ typename elements_type::value_type,
+ Value, Options, Translator, Box, Allocators,
+ typename Options::insert_tag
+ > insert_v(
+ m_root_node, m_leafs_level, *it,
+ m_parameters, m_translator, m_allocators,
+ node_relative_level - 1);
- rtree::apply_visitor(insert_v, *m_root_node);
+ rtree::apply_visitor(insert_v, *m_root_node); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+ }
+ }
+ catch(...)
+ {
+ ++it;
+ rtree::destroy_elements<Value, Options, Translator, Box, Allocators>
+ ::apply(it, elements.end(), m_allocators);
+ elements.clear();
+ throw; // RETHROW
}
}
@@ -235,7 +269,7 @@
node* & m_root_node;
size_t & m_leafs_level;
bool m_is_value_removed;
- std::vector< std::pair<size_t, node*> > m_underflowed_nodes;
+ UnderflowNodes m_underflowed_nodes;
// traversing input parameters
internal_node *m_parent;
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-13 17:13:17 EST (Tue, 13 Nov 2012)
@@ -27,15 +27,33 @@
B qbox;
generate_input<2>::apply(input, qbox);
- for ( size_t i = 10 ; i < 100 ; i += 5 )
+ for ( size_t i = 0 ; i < 100 ; i += 5 )
{
throwing_value::reset_calls_counter();
- throwing_value::set_max_calls(i);
+ throwing_value::set_max_calls(10000);
Tree tree(parameters);
-
+
+ throwing_value::reset_calls_counter();
+ throwing_value::set_max_calls(i);
+
BOOST_CHECK_THROW( tree.insert(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.remove(input.begin(), input.end()), throwing_value_copy_exception );
+ }
}
int test_main(int, char* [])
Modified: sandbox-branches/geometry/index_dev/test/rtree/test_rtree_exceptions.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/test/rtree/test_rtree_exceptions.hpp (original)
+++ sandbox-branches/geometry/index_dev/test/rtree/test_rtree_exceptions.hpp 2012-11-13 17:13:17 EST (Tue, 13 Nov 2012)
@@ -244,6 +244,11 @@
: value(v)
{}
+ bool operator==(throwing_value const& v) const
+ {
+ return value == v.value;
+ }
+
throwing_value(throwing_value const& v)
{
throw_if_required();