|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r81438 - in sandbox-branches/geometry/index_dev/boost/geometry/extensions/index: . rtree/linear rtree/quadratic rtree/rstar rtree/visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-20 12:00:42
Author: awulkiew
Date: 2012-11-20 12:00:41 EST (Tue, 20 Nov 2012)
New Revision: 81438
URL: http://svn.boost.org/trac/boost/changeset/81438
Log:
Fixed memleak for CoordinateType/BoundingObject which have throwing copy constructor for R*tree.
Added comments regarding exception-safety.
Text files modified:
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/nonassignable.hpp | 2
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/pushable_array.hpp | 2 +
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp | 16 +++++++-------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 24 ++++++++++----------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp | 44 ++++++++++++++++++++-------------------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 42 ++++++++++++++++++++------------------
6 files changed, 68 insertions(+), 62 deletions(-)
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/nonassignable.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/nonassignable.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/nonassignable.hpp 2012-11-20 12:00:41 EST (Tue, 20 Nov 2012)
@@ -1,6 +1,6 @@
// Boost.Geometry Index
//
-// Spatial query predicates
+// Nonassignable base class.
//
// Copyright (c) 2011-2012 Adam Wulkiewicz, Lodz, Poland.
//
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-20 12:00:41 EST (Tue, 20 Nov 2012)
@@ -133,6 +133,8 @@
m_size = 0;
}
+ // IMPORTANT!
+ // The sequence of elements is NOT preserved
inline void erase(iterator it)
{
BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
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-20 12:00:41 EST (Tue, 20 Nov 2012)
@@ -224,7 +224,7 @@
BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected number of elements");
// copy original elements
- elements_type elements_copy(elements1); // MAY THROW
+ elements_type elements_copy(elements1); // MAY THROW, STRONG (alloc, copy)
// calculate initial seeds
size_t seed1 = 0;
@@ -242,8 +242,8 @@
try
{
// add seeds
- elements1.push_back(elements_copy[seed1]); // MAY THROW
- elements2.push_back(elements_copy[seed2]); // MAY THROW
+ elements1.push_back(elements_copy[seed1]); // MAY THROW, STRONG (copy)
+ elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy)
// calculate boxes
geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
@@ -268,13 +268,13 @@
// just insert them to this node
if ( elements1.size() + remaining <= parameters.get_min_elements() )
{
- elements1.push_back(elem); // MAY THROW
+ elements1.push_back(elem); // MAY THROW, STRONG (copy)
geometry::expand(box1, indexable);
content1 = index::content(box1);
}
else if ( elements2.size() + remaining <= parameters.get_min_elements() )
{
- elements2.push_back(elem); // MAY THROW
+ elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
geometry::expand(box2, indexable);
content2 = index::content(box2);
}
@@ -297,13 +297,13 @@
( content_increase1 == content_increase2 && content1 < content2 ) ||
( content1 == content2 && elements1.size() <= elements2.size() ) )
{
- elements1.push_back(elem); // MAY THROW
+ elements1.push_back(elem); // MAY THROW, STRONG (copy)
box1 = enlarged_box1;
content1 = enlarged_content1;
}
else
{
- elements2.push_back(elem); // MAY THROW
+ elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
box2 = enlarged_box2;
content2 = enlarged_content2;
}
@@ -322,7 +322,7 @@
rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_copy, allocators);
//elements_copy.clear();
- throw; // RETHROW
+ throw; // RETHROW, BASIC
}
}
};
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-20 12:00:41 EST (Tue, 20 Nov 2012)
@@ -109,8 +109,8 @@
BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected elements number");
// copy original elements
- elements_type elements_copy(elements1); // MAY THROW
- elements_type elements_backup(elements1); // MAY THROW
+ elements_type elements_copy(elements1); // MAY THROW, STRONG (alloc, copy)
+ elements_type elements_backup(elements1); // MAY THROW, STRONG (alloc, copy)
// calculate initial seeds
size_t seed1 = 0;
@@ -129,8 +129,8 @@
try
{
// add seeds
- elements1.push_back(elements_copy[seed1]); // MAY THROW
- elements2.push_back(elements_copy[seed2]); // MAY THROW
+ elements1.push_back(elements_copy[seed1]); // MAY THROW, STRONG (copy)
+ elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy)
// calculate boxes
geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
@@ -139,13 +139,13 @@
// remove seeds
if (seed1 < seed2)
{
- elements_copy.erase(elements_copy.begin() + seed2); // MAY THROW
- elements_copy.erase(elements_copy.begin() + seed1); // MAY THROW
+ elements_copy.erase(elements_copy.begin() + seed2); // MAY THROW, BASIC (copy)
+ elements_copy.erase(elements_copy.begin() + seed1); // MAY THROW, BASIC (copy)
}
else
{
- elements_copy.erase(elements_copy.begin() + seed1); // MAY THROW
- elements_copy.erase(elements_copy.begin() + seed2); // MAY THROW
+ elements_copy.erase(elements_copy.begin() + seed1); // MAY THROW, BASIC (copy)
+ elements_copy.erase(elements_copy.begin() + seed2); // MAY THROW, BASIC (copy)
}
// initialize areas
@@ -201,20 +201,20 @@
if ( insert_into_group1 )
{
- elements1.push_back(elem); // MAY THROW
+ elements1.push_back(elem); // MAY THROW, STRONG (copy)
geometry::expand(box1, indexable);
content1 = index::content(box1);
}
else
{
- elements2.push_back(elem); // MAY THROW
+ elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
geometry::expand(box2, indexable);
content2 = index::content(box2);
}
BOOST_GEOMETRY_INDEX_ASSERT(!elements_copy.empty(), "expected more elements");
typename elements_type::iterator el_it_base = el_it.base();
- elements_copy.erase(--el_it_base); // MAY THROW
+ elements_copy.erase(--el_it_base); // MAY THROW, BASIC (copy)
BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
--remaining;
@@ -229,7 +229,7 @@
rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators);
//elements_backup.clear();
- throw; // RETHROW
+ throw; // RETHROW, BASIC
}
}
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-20 12:00:41 EST (Tue, 20 Nov 2012)
@@ -68,11 +68,11 @@
BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == parameters.get_max_elements() + 1, "wrong number of elements");
// copy elements
- Elements elements_copy(elements); // MAY THROW
+ Elements elements_copy(elements); // MAY THROW, STRONG (alloc, copy)
// sort elements
element_axis_corner_less<element_type, Translator, Corner, AxisIndex> elements_less(translator);
- std::sort(elements_copy.begin(), elements_copy.end(), elements_less); // MAY THROW
+ std::sort(elements_copy.begin(), elements_copy.end(), elements_less); // MAY THROW, BASIC (copy)
// init outputs
choosen_index = parameters.get_min_elements();
@@ -135,7 +135,7 @@
choose_split_axis_and_index_for_corner<Parameters, Box, min_corner, AxisIndex>::
apply(elements, index1,
som1, ovl1, con1,
- parameters, translator); // MAY THROW
+ parameters, translator); // MAY THROW, STRONG
size_t index2 = 0;
margin_type som2 = 0;
@@ -145,7 +145,7 @@
choose_split_axis_and_index_for_corner<Parameters, Box, max_corner, AxisIndex>::
apply(elements, index2,
som2, ovl2, con2,
- parameters, translator); // MAY THROW
+ parameters, translator); // MAY THROW, STRONG
sum_of_margins = som1 + som2;
@@ -185,7 +185,7 @@
choose_split_axis_and_index_for_corner<Parameters, Box, min_corner, AxisIndex>::
apply(elements, choosen_index,
sum_of_margins, smallest_overlap, smallest_content,
- parameters, translator); // MAY THROW
+ parameters, translator); // MAY THROW, STRONG
choosen_corner = min_corner;
}
@@ -215,7 +215,7 @@
choose_split_axis_and_index<Parameters, Box, Dimension - 1>::
apply(elements, choosen_axis, choosen_corner, choosen_index,
smallest_sum_of_margins, smallest_overlap, smallest_content,
- parameters, translator); // MAY THROW
+ parameters, translator); // MAY THROW, STRONG
margin_type sum_of_margins = 0;
@@ -230,7 +230,7 @@
Box,
Dimension - 1,
typename index::traits::tag<element_indexable_type>::type
- >::apply(elements, corner, index, sum_of_margins, overlap_val, content_val, parameters, translator); // MAY THROW
+ >::apply(elements, corner, index, sum_of_margins, overlap_val, content_val, parameters, translator); // MAY THROW, STRONG
if ( sum_of_margins < smallest_sum_of_margins )
{
@@ -284,7 +284,7 @@
{
if ( axis < Dimension - 1 )
{
- partial_sort<Corner, Dimension - 1>::apply(elements, axis, index, tr); // MAY THROW
+ partial_sort<Corner, Dimension - 1>::apply(elements, axis, index, tr); // MAY THROW, BASIC (copy)
}
else
{
@@ -292,7 +292,7 @@
typedef typename Elements::value_type element_type;
element_axis_corner_less<element_type, Translator, Corner, Dimension - 1> less(tr);
- std::partial_sort(elements.begin(), elements.begin() + index, elements.end(), less); // MAY THROW
+ std::partial_sort(elements.begin(), elements.begin() + index, elements.end(), less); // MAY THROW, BASIC (copy)
}
}
};
@@ -307,7 +307,7 @@
typedef typename Elements::value_type element_type;
element_axis_corner_less<element_type, Translator, Corner, 0> less(tr);
- std::partial_sort(elements.begin(), elements.begin() + index, elements.end(), less); // MAY THROW
+ std::partial_sort(elements.begin(), elements.begin() + index, elements.end(), less); // MAY THROW, BASIC (copy)
}
};
@@ -356,7 +356,7 @@
>::apply(elements1,
split_axis, split_corner, split_index,
smallest_sum_of_margins, smallest_overlap, smallest_content,
- parameters, translator); // MAY THROW
+ parameters, translator); // MAY THROW, STRONG
// TODO: awulkiew - get rid of following static_casts?
@@ -365,23 +365,24 @@
BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= split_index && split_index <= parameters.get_max_elements() - parameters.get_min_elements() + 1, "unexpected value");
// copy original elements
- elements_type elements_copy(elements1); // MAY THROW
+ elements_type elements_copy(elements1); // MAY THROW, STRONG
+ elements_type elements_backup(elements1); // MAY THROW, STRONG
// TODO: awulkiew - check if std::partial_sort produces the same result as std::sort
if ( split_corner == static_cast<size_t>(min_corner) )
rstar::partial_sort<min_corner, dimension>
- ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW
+ ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW, BASIC (copy)
else
rstar::partial_sort<max_corner, dimension>
- ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW
+ ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW, BASIC (copy)
try
{
// copy elements to nodes
- elements1.resize(split_index); // MIGHT THROW
- std::copy(elements_copy.begin(), elements_copy.begin() + split_index, elements1.begin()); // MAY THROW
- elements2.resize(parameters.get_max_elements() + 1 - split_index); // MAY THROW
- std::copy(elements_copy.begin() + split_index, elements_copy.end(), elements2.begin()); // MAY THROW
+ elements1.resize(split_index); // SHOULDN'T THROW
+ std::copy(elements_copy.begin(), elements_copy.begin() + split_index, elements1.begin()); // MAY THROW, BASIC
+ elements2.resize(parameters.get_max_elements() + 1 - split_index); // MAY THROW, STRONG
+ std::copy(elements_copy.begin() + split_index, elements_copy.end(), elements2.begin()); // MAY THROW, BASIC
// calculate boxes
box1 = rtree::elements_box<Box>(elements1.begin(), elements1.end(), translator);
@@ -389,13 +390,14 @@
}
catch(...)
{
+ //elements_copy.clear();
elements1.clear();
elements2.clear();
- rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_copy, allocators);
- //elements_copy.clear();
+ rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators);
+ //elements_backup.clear();
- throw; // RETHROW
+ throw; // RETHROW, BASIC
}
}
};
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-20 12:00:41 EST (Tue, 20 Nov 2012)
@@ -157,7 +157,7 @@
Box,
Allocators,
typename Options::redistribute_tag
- >::apply(n, n2, n_box, box2, parameters, translator, allocators); // MAY THROW (V: alloc, copy, E: alloc)
+ >::apply(n, n2, n_box, box2, parameters, translator, allocators); // MAY THROW (V, E: alloc, copy, copy)
// check numbers of elements
BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() &&
@@ -168,7 +168,7 @@
"unexpected number of elements");
// return the list of newly created nodes (this algorithm returns one)
- additional_nodes.push_back(std::make_pair(box2, second_node.get())); // MAY THROW
+ additional_nodes.push_back(std::make_pair(box2, second_node.get())); // MAY THROW (alloc, copy)
// release the ptr
second_node.release();
@@ -269,7 +269,7 @@
rtree::element_indexable(m_element, m_translator));
// next traversing step
- traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW (V: alloc, copy, E: alloc, N:alloc)
+ traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW, BASIC (V, E: alloc, copy, 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 (V: alloc, copy, E: alloc, N:alloc)
+ split(n); // MAY THROW, BASIC (V, E: alloc, copy, 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 (V: alloc, copy, E: alloc, N:alloc)
+ rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second); // MAY THROW, BASIC (V, E: alloc, copy, N:alloc)
// restore previous traverse inputs
m_traverse_data = backup_traverse_data;
@@ -314,11 +314,12 @@
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 (V: alloc, copy, E: alloc, N:alloc)
+ split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators); // MAY THROW, BASIC (V, E: alloc, copy, N:alloc)
BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
// TODO add all additional nodes
+ // For kmeans algorithm:
// elements number may be greater than node max elements count
// split and reinsert must take node with some elements count
// and container of additional elements (std::pair<Box, node*>s or Values)
@@ -336,7 +337,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 (V: alloc, copy, E: alloc)
+ m_traverse_data.parent_elements().push_back(additional_nodes[0]); // MAY THROW, STRONG (V, E: alloc, copy)
}
// node is the root - add level
else
@@ -344,15 +345,15 @@
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 (N:alloc)
+ node_auto_ptr new_root(rtree::create_node<Allocators, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc)
try {
- 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)
+ rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(n_box, m_root_node)); // MAY THROW, STRONG (E:alloc, copy)
+ rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]); // MAY THROW, STRONG (E:alloc, copy)
} 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();
- throw; // RETHROW
+ throw; // RETHROW, BASIC
}
m_root_node = new_root.get();
@@ -421,7 +422,7 @@
if ( base::m_traverse_data.current_level < base::m_level )
{
// next traversing step
- base::traverse(*this, n); // MAY THROW (E: alloc, N: alloc)
+ base::traverse(*this, n); // MAY THROW, BASIC (E: alloc, copy, N: alloc)
}
else
{
@@ -430,19 +431,20 @@
try
{
// push new child node
- rtree::elements(n).push_back(base::m_element); // MAY THROW (E: alloc)
+ rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (E: alloc, copy)
}
catch(...)
{
- // if the insert fails here, the element won't be stored in the tree
+ // if the insert fails above, 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
+ throw; // RETHROW, BASIC
}
}
- base::post_traverse(n); // MAY THROW (E: alloc, N: alloc)
+ base::post_traverse(n); // MAY THROW, BASIC (E: alloc, copy, N: alloc)
}
inline void operator()(leaf &)
@@ -481,9 +483,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 (V: alloc, copy, E: alloc, N: alloc)
+ base::traverse(*this, n); // MAY THROW, BASIC (V, E: alloc, copy, N: alloc)
- base::post_traverse(n); // MAY THROW (E: alloc, N: alloc)
+ base::post_traverse(n); // MAY THROW, BASIC (E: alloc, copy, N: alloc)
}
inline void operator()(leaf & n)
@@ -492,9 +494,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 (V: alloc, copy)
+ rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy)
- base::post_traverse(n); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+ base::post_traverse(n); // MAY THROW, BASIC (V: alloc, copy, N: alloc)
}
};
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