|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r81445 - 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 doc/html doc/html/geometry_index doc/html/geometry_index/r_tree doc/rtree test/rtree tests
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-20 17:49:17
Author: awulkiew
Date: 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
New Revision: 81445
URL: http://svn.boost.org/trac/boost/changeset/81445
Log:
Improved exception safety of the r-tree.
Requirement 'nonthrowing copy constructor of the BoundingObject/CoordinateType' changed to 'exception-safe copy constructor of the BoundingObject/CoordinateType'.
>From now the r-tree do not use erase() method of the elements containers. It uses copy_from_back() and pop_back() instead.
erase() removed from pushable_array.
Added various memory leaks fixes taking throwing by Element's copy constructor into account.
Tests added.
Docs modified.
Added:
sandbox-branches/geometry/index_dev/test/rtree/test_throwing.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/pushable_array.hpp | 17 -----
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp | 12 +++
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 15 +++-
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 97 ++++++++++++++++--------------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/copy.hpp | 15 +++-
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 26 ++++----
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 50 +++++++++++----
sandbox-branches/geometry/index_dev/doc/html/geometry_index/introduction.html | 2
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html | 2
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html | 6
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html | 24 ++++---
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html | 2
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html | 2
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/rtree_quickstart.html | 4
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/spatial_queries.html | 2
sandbox-branches/geometry/index_dev/doc/html/index.html | 4
sandbox-branches/geometry/index_dev/doc/rtree/exception_safety.qbk | 3
sandbox-branches/geometry/index_dev/test/rtree/rtree_exceptions.cpp | 83 +++++++++++++++++++++++++
sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp | 18 +++--
sandbox-branches/geometry/index_dev/test/rtree/test_rtree_exceptions.hpp | 125 ++++++++++-----------------------------
sandbox-branches/geometry/index_dev/tests/additional_speed.cpp | 4
21 files changed, 287 insertions(+), 226 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-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -133,23 +133,6 @@
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");
- BOOST_GEOMETRY_INDEX_ASSERT(begin() <= it && it < end(), "iterator points on the element outside the container");
- //std::copy(it + 1, end(), it);
- // 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;
- }
-
inline void push_back(Element const& v)
{
BOOST_GEOMETRY_INDEX_ASSERT(m_size < Capacity, "can't further increase the size of the container");
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-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -151,6 +151,18 @@
}
};
+template <typename Container, typename Iterator>
+void copy_from_back(Container & container, Iterator it)
+{
+ BOOST_GEOMETRY_INDEX_ASSERT(!container.empty(), "cannot copy from empty container");
+ Iterator back_it = container.end();
+ --back_it;
+ if ( it != back_it )
+ {
+ *it = *back_it; // MAY THROW (copy)
+ }
+}
+
}} // 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-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -139,13 +139,17 @@
// remove seeds
if (seed1 < seed2)
{
- elements_copy.erase(elements_copy.begin() + seed2); // MAY THROW, BASIC (copy)
- elements_copy.erase(elements_copy.begin() + seed1); // MAY THROW, BASIC (copy)
+ rtree::copy_from_back(elements_copy, elements_copy.begin() + seed2); // MAY THROW, STRONG (copy)
+ elements_copy.pop_back();
+ rtree::copy_from_back(elements_copy, elements_copy.begin() + seed1); // MAY THROW, STRONG (copy)
+ elements_copy.pop_back();
}
else
{
- elements_copy.erase(elements_copy.begin() + seed1); // MAY THROW, BASIC (copy)
- elements_copy.erase(elements_copy.begin() + seed2); // MAY THROW, BASIC (copy)
+ rtree::copy_from_back(elements_copy, elements_copy.begin() + seed1); // MAY THROW, STRONG (copy)
+ elements_copy.pop_back();
+ rtree::copy_from_back(elements_copy, elements_copy.begin() + seed2); // MAY THROW, STRONG (copy)
+ elements_copy.pop_back();
}
// initialize areas
@@ -214,7 +218,8 @@
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, BASIC (copy)
+ rtree::copy_from_back(elements_copy, --el_it_base); // MAY THROW, STRONG (copy)
+ elements_copy.pop_back();
BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
--remaining;
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-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -65,14 +65,14 @@
std::pair<distance_type, element_type>
>::type sorted_elements;
// If constructor is used instead of resize() MS implementation leaks here
- sorted_elements.resize(elements_count); // MAY THROW (V: alloc, copy, E: alloc)
+ sorted_elements.resize(elements_count); // MAY THROW, STRONG (V, E: alloc, copy)
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 (V: copy)
+ sorted_elements[i].second = elements[i]; // MAY THROW (V, E: copy)
}
// sort elements by distances from center
@@ -80,12 +80,12 @@
sorted_elements.begin(),
sorted_elements.begin() + reinserted_elements_count,
sorted_elements.end(),
- distances_dsc<distance_type, element_type>); // MAY THROW (V: copy)
+ distances_dsc<distance_type, element_type>); // MAY THROW, BASIC (V, E: copy)
// copy elements which will be reinserted
- result_elements.resize(reinserted_elements_count); // MAY THROW (V: alloc, copy?, E: alloc)
+ result_elements.resize(reinserted_elements_count); // MAY THROW, STRONG (V, E: alloc, copy)
for ( size_t i = 0 ; i < reinserted_elements_count ; ++i )
- result_elements[i] = sorted_elements[i].second; // MAY THROW (V: copy)
+ result_elements[i] = sorted_elements[i].second; // MAY THROW (V, E: copy)
try
{
@@ -93,7 +93,7 @@
size_t elements_new_count = elements_count - reinserted_elements_count;
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 (V: copy)
+ elements[i] = sorted_elements[i + reinserted_elements_count].second; // MAY THROW (V, E: copy)
}
catch(...)
{
@@ -177,17 +177,17 @@
if ( !base::m_traverse_data.current_is_root() )
{
// NOTE: exception-safety
- // After an exception result_elements may contain garbage
+ // After an exception result_elements may contain garbage, don't use it
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)
+ base::m_parameters, base::m_translator, base::m_allocators); // MAY THROW, BASIC (V, E: alloc, copy)
}
// 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)
+ base::split(n); // MAY THROW (V, E: alloc, copy, N: alloc)
}
}
}
@@ -198,7 +198,7 @@
// overflow
if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
{
- base::split(n); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+ base::split(n); // MAY THROW (V, E: alloc, copy, N: alloc)
}
}
@@ -245,7 +245,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 (E: alloc, copy, N: alloc)
// further insert
if ( 0 < InsertIndex )
@@ -254,7 +254,7 @@
if ( base::m_traverse_data.current_level == base::m_level - 1 )
{
- base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, N: alloc)
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc)
}
}
}
@@ -262,31 +262,30 @@
{
BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
- // first insert
- if ( 0 == InsertIndex )
+ try
{
- 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);
+ // push new child node
+ rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (E: alloc, copy)
+ }
+ catch(...)
+ {
+ // NOTE: exception-safety
+ // if the insert fails above, the element won't be stored in the tree, so delete it
- throw; // RETHROW
- }
+ 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);
- base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, N: alloc)
+ throw; // RETHROW
+ }
+
+ // first insert
+ if ( 0 == InsertIndex )
+ {
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc)
}
// not the first insert
else
{
- // 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)
}
}
@@ -327,13 +326,13 @@
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 (V, E: alloc, copy, N: alloc)
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 (E: alloc, N: alloc)
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc)
}
base::recalculate_aabb_if_necessary(n);
@@ -347,7 +346,7 @@
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::handle_possible_split(n); // MAY THROW (V: alloc, copy, N: alloc)
}
@@ -395,7 +394,7 @@
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::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (V: alloc, copy, N: alloc)
@@ -442,11 +441,11 @@
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)
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, 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)
+ recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V, E: alloc, copy, N: alloc)
}
}
@@ -457,33 +456,43 @@
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)
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, 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());
+ BOOST_GEOMETRY_INDEX_ASSERT(lins_v.result_elements.empty(), "unexpected state");
}
private:
template <typename Elements>
- inline void recursive_reinsert(Elements const& elements, size_t relative_level)
+ inline void recursive_reinsert(Elements & 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)
+ typename Elements::reverse_iterator it = elements.rbegin();
+ for ( ; 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)
+ try
+ {
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
+ }
+ catch(...)
+ {
+ ++it;
+ for ( ; it != elements.rend() ; ++it)
+ rtree::destroy_element<Value, Options, Translator, Box, Allocators>::apply(*it, m_allocators);
+ throw; // RETHROW
+ }
- assert(relative_level + 1 == lins_v.result_relative_level);
+ BOOST_GEOMETRY_INDEX_ASSERT(relative_level + 1 == lins_v.result_relative_level, "unexpected 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)
+ recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V, E: alloc, copy, N: alloc)
}
}
}
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-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -36,7 +36,7 @@
inline void operator()(internal_node & n)
{
- node * raw_new_node = rtree::create_node<Allocators, internal_node>::apply(m_allocators); // MAY THROW (N: alloc)
+ node * raw_new_node = rtree::create_node<Allocators, internal_node>::apply(m_allocators); // MAY THROW, STRONG (N: alloc)
node_auto_ptr new_node(raw_new_node, m_allocators);
typedef typename rtree::elements_type<internal_node>::type elements_type;
@@ -47,9 +47,14 @@
for (typename elements_type::iterator it = elements.begin();
it != elements.end(); ++it)
{
- rtree::apply_visitor(*this, *it->second);
+ rtree::apply_visitor(*this, *it->second); // MAY THROW (V, E: alloc, copy, N: alloc)
- elements_dst.push_back( std::make_pair(it->first, result) ); // MAY THROW (E: alloc)
+ // for exception safety
+ node_auto_ptr auto_result(result, m_allocators);
+
+ elements_dst.push_back( std::make_pair(it->first, result) ); // MAY THROW, STRONG (E: alloc, copy)
+
+ auto_result.release();
}
result = new_node.get();
@@ -58,7 +63,7 @@
inline void operator()(leaf & l)
{
- node * raw_new_node = rtree::create_node<Allocators, leaf>::apply(m_allocators); // MAY THROW (N: alloc)
+ node * raw_new_node = rtree::create_node<Allocators, leaf>::apply(m_allocators); // MAY THROW, STRONG (N: alloc)
node_auto_ptr new_node(raw_new_node, m_allocators);
typedef typename rtree::elements_type<leaf>::type elements_type;
@@ -69,7 +74,7 @@
for (typename elements_type::iterator it = elements.begin();
it != elements.end(); ++it)
{
- elements_dst.push_back(*it); // MAY THROW (V: alloc, copy)
+ elements_dst.push_back(*it); // MAY THROW, STRONG (V: alloc, copy)
}
result = new_node.get();
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 17:49:14 EST (Tue, 20 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 (N: alloc)
+ node_auto_ptr second_node(rtree::create_node<Allocators, Node>::apply(allocators), allocators); // MAY THROW, STRONG (N: alloc)
// create reference to the newly created node
Node & n2 = rtree::get<Node>(*second_node);
@@ -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 (alloc, copy)
+ additional_nodes.push_back(std::make_pair(box2, second_node.get())); // MAY THROW, STRONG (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, BASIC (V, E: alloc, copy, N:alloc)
+ traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW (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, BASIC (V, E: alloc, copy, N:alloc)
+ split(n); // MAY THROW (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, BASIC (V, E: alloc, copy, N:alloc)
+ rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V, E: alloc, copy, 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, BASIC (V, E: alloc, copy, N:alloc)
+ split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators); // MAY THROW (V, E: alloc, copy, N:alloc)
BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
@@ -353,7 +353,7 @@
} 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, BASIC
+ throw; // RETHROW
}
m_root_node = new_root.get();
@@ -422,7 +422,7 @@
if ( base::m_traverse_data.current_level < base::m_level )
{
// next traversing step
- base::traverse(*this, n); // MAY THROW, BASIC (E: alloc, copy, N: alloc)
+ base::traverse(*this, n); // MAY THROW (E: alloc, copy, N: alloc)
}
else
{
@@ -440,11 +440,11 @@
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, BASIC
+ throw; // RETHROW
}
}
- base::post_traverse(n); // MAY THROW, BASIC (E: alloc, copy, N: alloc)
+ base::post_traverse(n); // MAY THROW (E: alloc, copy, N: alloc)
}
inline void operator()(leaf &)
@@ -483,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, BASIC (V, E: alloc, copy, N: alloc)
+ base::traverse(*this, n); // MAY THROW (V, E: alloc, copy, N: alloc)
- base::post_traverse(n); // MAY THROW, BASIC (E: alloc, copy, N: alloc)
+ base::post_traverse(n); // MAY THROW (E: alloc, copy, N: alloc)
}
inline void operator()(leaf & n)
@@ -496,7 +496,7 @@
rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy)
- base::post_traverse(n); // MAY THROW, BASIC (V: alloc, copy, N: alloc)
+ base::post_traverse(n); // MAY THROW (V: alloc, copy, 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-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -70,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); // MAY THROW
+ traverse_apply_visitor(n, child_node_index); // MAY THROW
if ( m_is_value_removed )
break;
@@ -88,14 +88,10 @@
if ( m_is_underflow )
{
element_iterator underfl_el_it = elements.begin() + child_node_index;
+ size_t relative_level = m_leafs_level - m_current_level;
- // 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)); // MAY THROW (alloc)
-
- elements.erase(underfl_el_it); // SHOULDN'T THROW
-
- // calc underflow
- m_is_underflow = elements.size() < m_parameters.get_min_elements();
+ // move node to the container - store node's relative level as well and return new underflow state
+ m_is_underflow = store_underflowed_node(elements, underfl_el_it, relative_level); // MAY THROW (E: alloc, copy)
}
// n is not root - adjust aabb
@@ -116,7 +112,7 @@
BOOST_GEOMETRY_INDEX_ASSERT(m_is_value_removed, "value not found");
// reinsert elements from removed nodes (underflows)
- reinsert_removed_nodes_elements(); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+ reinsert_removed_nodes_elements(); // MAY THROW (V, E: alloc, copy, N: alloc)
// shorten the tree
if ( rtree::elements(n).size() == 1 )
@@ -141,7 +137,8 @@
{
if ( m_translator.equals(*it, m_value) )
{
- elements.erase(it); // MAY THROW (V: copy)
+ rtree::copy_from_back(elements, it); // MAY THROW (V: copy)
+ elements.pop_back();
m_is_value_removed = true;
break;
}
@@ -166,7 +163,7 @@
typedef std::vector< std::pair<size_t, node*> > UnderflowNodes;
- inline void traverse_apply_visitor(internal_node &n, size_t choosen_node_index)
+ void traverse_apply_visitor(internal_node &n, size_t choosen_node_index)
{
// save previous traverse inputs and set new ones
internal_node * parent_bckup = m_parent;
@@ -178,7 +175,7 @@
++m_current_level;
// next traversing step
- rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+ rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V, E: alloc, copy, N: alloc)
// restore previous traverse inputs
m_parent = parent_bckup;
@@ -186,6 +183,29 @@
m_current_level = current_level_bckup;
}
+ bool store_underflowed_node(
+ typename rtree::elements_type<internal_node>::type & elements,
+ typename rtree::elements_type<internal_node>::type::iterator underfl_el_it,
+ size_t relative_level)
+ {
+ // move node to the container - store node's relative level as well
+ m_underflowed_nodes.push_back(std::make_pair(relative_level, underfl_el_it->second)); // MAY THROW (E: alloc, copy)
+
+ try
+ {
+ rtree::copy_from_back(elements, underfl_el_it); // MAY THROW (E: copy)
+ elements.pop_back();
+ }
+ catch(...)
+ {
+ m_underflowed_nodes.pop_back();
+ throw; // RETHROW
+ }
+
+ // calc underflow
+ return elements.size() < m_parameters.get_min_elements();
+ }
+
void reinsert_removed_nodes_elements()
{
typename UnderflowNodes::reverse_iterator it = m_underflowed_nodes.rbegin();
@@ -200,13 +220,13 @@
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)
+ reinsert_node_elements(rtree::get<leaf>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, 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)
+ reinsert_node_elements(rtree::get<internal_node>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, N: alloc)
rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, it->second);
}
@@ -248,7 +268,7 @@
m_parameters, m_translator, m_allocators,
node_relative_level - 1);
- rtree::apply_visitor(insert_v, *m_root_node); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+ rtree::apply_visitor(insert_v, *m_root_node); // MAY THROW (V, E: alloc, copy, N: alloc)
}
}
catch(...)
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/introduction.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/introduction.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/introduction.html 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Introduction</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../index.html" title="Chapter 1. Geometry Index">
<link rel="prev" href="../index.html" title="Chapter 1. Geometry Index">
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>R-tree</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../index.html" title="Chapter 1. Geometry Index">
<link rel="prev" href="introduction.html" title="Introduction">
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Creation and modification</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="rtree_quickstart.html" title="Quick Start">
@@ -51,7 +51,7 @@
</p>
<pre class="programlisting"><span class="identifier">rtree</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Parameters</span><span class="special">,</span> <span class="identifier">Translator</span><span class="special">,</span> <span class="identifier">Allocator</span><span class="special">></span>
</pre>
-<div class="itemizedlist"><ul class="itemizedlist" type="disc">
+<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
<code class="computeroutput">Value</code> - type of object which will be stored in the container.
</li>
@@ -89,7 +89,7 @@
<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><...></span></code>,
pointer, iterator or smart pointer.
</p>
-<div class="itemizedlist"><ul class="itemizedlist" type="disc">
+<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
<code class="computeroutput">Indexable <span class="special">=</span> Point
<span class="special">|</span> Box</code>
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/rtree_quickstart.html
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/spatial_queries.html
Modified: sandbox-branches/geometry/index_dev/doc/html/index.html
Modified: sandbox-branches/geometry/index_dev/doc/rtree/exception_safety.qbk
Modified: sandbox-branches/geometry/index_dev/test/rtree/rtree_exceptions.cpp
Modified: sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp
Modified: sandbox-branches/geometry/index_dev/test/rtree/test_rtree_exceptions.hpp
Added: sandbox-branches/geometry/index_dev/test/rtree/test_throwing.hpp
Modified: sandbox-branches/geometry/index_dev/tests/additional_speed.cpp
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
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Exception safety</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="nearest_neighbours_queries.html" title="Nearest neighbours queries">
@@ -28,13 +28,15 @@
<p>
In order to be exception-safe the R-tree requires:
</p>
-<div class="itemizedlist"><ul class="itemizedlist" type="disc">
+<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
- Nonthrowing copy constructor of the <code class="computeroutput"><span class="identifier">CoordinateType</span></code>
- used in the <code class="computeroutput">Indexable</code>,
+ Nonthrowing destructor of the <code class="computeroutput">Value</code>.
</li>
<li class="listitem">
- Nonthrowing destructor of the <code class="computeroutput">Value</code>.
+ Exception-safe copy constructor of the <code class="computeroutput">Value</code>.
+ </li>
+<li class="listitem">
+ Exception-safe copy constructor of the <code class="computeroutput"><span class="identifier">CoordinateType</span></code>.
</li>
</ul></div>
<div class="informaltable"><table class="table">
@@ -64,7 +66,7 @@
<td>
<p>
<span class="emphasis"><em>nothrow (default)</em></span> or <span class="bold"><strong>strong</strong></span>
- <sup>[<a name="geometry_index.r_tree.exception_safety.f0" href="#ftn.geometry_index.r_tree.exception_safety.f0" class="footnote">a</a>]</sup>
+ [a]</sup></a>
</p>
</td>
</tr>
@@ -138,7 +140,7 @@
<td>
<p>
<span class="emphasis"><em>nothrow (default)</em></span> or <span class="bold"><strong>strong</strong></span>
- <sup>[<a name="geometry_index.r_tree.exception_safety.f1" href="#ftn.geometry_index.r_tree.exception_safety.f1" class="footnote">b</a>]</sup>
+ [b]</sup></a>
</p>
</td>
</tr>
@@ -151,7 +153,7 @@
<td>
<p>
<span class="emphasis"><em>nothrow</em></span> or <span class="bold"><strong>strong</strong></span>
- <sup>[<a name="geometry_index.r_tree.exception_safety.f2" href="#ftn.geometry_index.r_tree.exception_safety.f2" class="footnote">c</a>]</sup>
+ [c]</sup></a>
</p>
</td>
</tr>
@@ -333,19 +335,19 @@
</tr>
</tbody>
<tbody class="footnotes"><tr><td colspan="2">
-<div class="footnote"><p><sup>[<a id="ftn.geometry_index.r_tree.exception_safety.f0" href="#geometry_index.r_tree.exception_safety.f0" class="para">a</a>] </sup>
+<div id="ftn.geometry_index.r_tree.exception_safety.f0" class="footnote"><p>[a]
<span class="emphasis"><em>nothrow</em></span> - if <code class="computeroutput"><span class="identifier">Translator</span></code>
has nonthrowing copy constructor (default), <span class="bold"><strong>strong</strong></span>
- if <code class="computeroutput"><span class="identifier">Translator</span></code>
has throwing copy constructor
</p></div>
-<div class="footnote"><p><sup>[<a id="ftn.geometry_index.r_tree.exception_safety.f1" href="#geometry_index.r_tree.exception_safety.f1" class="para">b</a>] </sup>
+<div id="ftn.geometry_index.r_tree.exception_safety.f1" class="footnote"><p>[b]
<span class="emphasis"><em>nothrow</em></span> - if <code class="computeroutput"><span class="identifier">Translator</span></code>
has nonthrowing copy constructor (default), <span class="bold"><strong>strong</strong></span>
- if <code class="computeroutput"><span class="identifier">Translator</span></code>
has throwing copy constructor
</p></div>
-<div class="footnote"><p><sup>[<a id="ftn.geometry_index.r_tree.exception_safety.f2" href="#geometry_index.r_tree.exception_safety.f2" class="para">c</a>] </sup>
+<div id="ftn.geometry_index.r_tree.exception_safety.f2" class="footnote"><p>[c]
<span class="emphasis"><em>nothrow</em></span> - if allocators are equal and <code class="computeroutput"><span class="identifier">Translator</span></code> has nonthrowing
copy constructor (default), <span class="bold"><strong>strong</strong></span>
- if allocators aren't equal or <code class="computeroutput"><span class="identifier">Translator</span></code>
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Introduction</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="../r_tree.html" title="R-tree">
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Nearest neighbours queries</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="spatial_queries.html" title="Spatial queries">
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/rtree_quickstart.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/rtree_quickstart.html 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Quick Start</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="introduction.html" title="Introduction">
@@ -109,7 +109,7 @@
</p>
<h4>
<a name="geometry_index.r_tree.rtree_quickstart.h0"></a>
- <span><a name="geometry_index.r_tree.rtree_quickstart.more"></a></span><a class="link" href="rtree_quickstart.html#geometry_index.r_tree.rtree_quickstart.more">More</a>
+ <span class="phrase"><a name="geometry_index.r_tree.rtree_quickstart.more"></a></span><a class="link" href="rtree_quickstart.html#geometry_index.r_tree.rtree_quickstart.more">More</a>
</h4>
<p>
More information about the R-tree implementation, other algorithms and queries
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/spatial_queries.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/spatial_queries.html 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Spatial queries</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="creation_and_modification.html" title="Creation and modification">
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/index.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/index.html 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Chapter 1. Geometry Index</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="index.html" title="Chapter 1. Geometry Index">
<link rel="next" href="geometry_index/introduction.html" title="Introduction">
</head>
@@ -56,7 +56,7 @@
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left"><p><small>Last revised: November 16, 2012 at 12:39:01 GMT</small></p></td>
+<td align="left"><p><small>Last revised: November 20, 2012 at 22:42:04 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/rtree/exception_safety.qbk (original)
+++ sandbox-branches/geometry/index_dev/doc/rtree/exception_safety.qbk 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -12,8 +12,9 @@
In order to be exception-safe the __rtree__ requires:
-* Nonthrowing copy constructor of the `CoordinateType` used in the `__indexable__`,
* Nonthrowing destructor of the `__value__`.
+* Exception-safe copy constructor of the `__value__`.
+* Exception-safe copy constructor of the `CoordinateType`.
[table
[[Operation] [exception-safety]]
==============================================================================
--- sandbox-branches/geometry/index_dev/test/rtree/rtree_exceptions.cpp (original)
+++ sandbox-branches/geometry/index_dev/test/rtree/rtree_exceptions.cpp 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -87,14 +87,93 @@
}
}
+// test value exceptions
+template <typename Parameters>
+void test_rtree_elements_exceptions(Parameters const& parameters = Parameters())
+{
+ typedef std::pair<bg::model::point<float, 2, bg::cs::cartesian>, throwing_value> Value;
+ typedef bgi::rtree<Value, Parameters> Tree;
+ typedef typename Tree::box_type B;
+
+ throwing_value::reset_calls_counter();
+ throwing_value::set_max_calls((std::numeric_limits<size_t>::max)());
+
+ std::vector<Value> input;
+ B qbox;
+ generate_input<2>::apply(input, qbox, 2);
+
+ for ( size_t i = 0 ; i < 100 ; i += 2 )
+ {
+ throwing_pushable_array_settings::reset_calls_counter();
+ throwing_pushable_array_settings::set_max_calls(10000);
+
+ Tree tree(parameters);
+
+ throwing_pushable_array_settings::reset_calls_counter();
+ throwing_pushable_array_settings::set_max_calls(i);
+
+ BOOST_CHECK_THROW( tree.insert(input.begin(), input.end()), throwing_pushable_array_exception );
+ }
+
+ for ( size_t i = 0 ; i < 50 ; i += 2 )
+ {
+ throwing_pushable_array_settings::reset_calls_counter();
+ throwing_pushable_array_settings::set_max_calls(10000);
+
+ Tree tree(parameters);
+
+ tree.insert(input.begin(), input.end());
+
+ throwing_pushable_array_settings::reset_calls_counter();
+ throwing_pushable_array_settings::set_max_calls(i);
+
+ BOOST_CHECK_THROW( tree.remove(input.begin(), input.end()), throwing_pushable_array_exception );
+ }
+
+ for ( size_t i = 0 ; i < 50 ; i += 2 )
+ {
+ throwing_pushable_array_settings::reset_calls_counter();
+ throwing_pushable_array_settings::set_max_calls(10000);
+
+ Tree tree(parameters);
+
+ tree.insert(input.begin(), input.end());
+
+ throwing_pushable_array_settings::reset_calls_counter();
+ throwing_pushable_array_settings::set_max_calls(i);
+
+ BOOST_CHECK_THROW( Tree tree2(tree), throwing_pushable_array_exception );
+ }
+
+ for ( size_t i = 0 ; i < 50 ; i += 2 )
+ {
+ throwing_pushable_array_settings::reset_calls_counter();
+ throwing_pushable_array_settings::set_max_calls(10000);
+
+ Tree tree(parameters);
+ Tree tree2(parameters);
+
+ tree.insert(input.begin(), input.end());
+
+ throwing_pushable_array_settings::reset_calls_counter();
+ throwing_pushable_array_settings::set_max_calls(i);
+
+ BOOST_CHECK_THROW(tree2 = tree, throwing_pushable_array_exception );
+ }
+}
+
int test_main(int, char* [])
{
test_rtree_value_exceptions< bgi::linear<4, 2> >();
test_rtree_value_exceptions(bgi::runtime::linear(4, 2));
test_rtree_value_exceptions< bgi::quadratic<4, 2> >();
test_rtree_value_exceptions(bgi::runtime::quadratic(4, 2));
- test_rtree_value_exceptions< bgi::rstar<4, 2> >();
- test_rtree_value_exceptions(bgi::runtime::rstar(4, 2));
+ test_rtree_value_exceptions< bgi::rstar<4, 2, 0, 2> >();
+ test_rtree_value_exceptions(bgi::runtime::rstar(4, 2, 0, 2));
+
+ test_rtree_elements_exceptions< bgi::linear_throwing<4, 2> >();
+ test_rtree_elements_exceptions< bgi::quadratic_throwing<4, 2> >();
+ test_rtree_elements_exceptions< bgi::rstar_throwing<4, 2, 0, 2> >();
return 0;
}
==============================================================================
--- sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp (original)
+++ sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -149,11 +149,13 @@
struct generate_input<2>
{
template <typename Value, typename Box>
- static void apply(std::vector<Value> & input, Box & qbox)
+ static void apply(std::vector<Value> & input, Box & qbox, int size = 1)
{
- for ( int i = 0 ; i < 12 ; i += 3 )
+ assert(0 < size);
+
+ for ( int i = 0 ; i < 12 * size ; i += 3 )
{
- for ( int j = 1 ; j < 25 ; j += 4 )
+ for ( int j = 1 ; j < 25 * size ; j += 4 )
{
input.push_back( generate_value<Value>::apply(i, j) );
}
@@ -169,13 +171,15 @@
struct generate_input<3>
{
template <typename Value, typename Box>
- static void apply(std::vector<Value> & input, Box & qbox)
+ static void apply(std::vector<Value> & input, Box & qbox, unsigned size = 1)
{
- for ( int i = 0 ; i < 12 ; i += 3 )
+ assert(0 < size);
+
+ for ( int i = 0 ; i < 12 * size ; i += 3 )
{
- for ( int j = 1 ; j < 25 ; j += 4 )
+ for ( int j = 1 ; j < 25 * size ; j += 4 )
{
- for ( int k = 2 ; k < 12 ; k += 5 )
+ for ( int k = 2 ; k < 12 * size ; k += 5 )
{
input.push_back( generate_value<Value>::apply(i, j, k) );
}
==============================================================================
--- 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-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -15,7 +15,8 @@
#include <rtree/test_rtree.hpp>
#include <boost/geometry/extensions/index/rtree/node/dynamic_visitor.hpp>
-#include <boost/geometry/extensions/index/pushable_array.hpp>
+
+#include <rtree/test_throwing.hpp>
namespace boost { namespace geometry { namespace index {
@@ -74,10 +75,10 @@
struct dynamic_internal_node<Value, Parameters, Box, Allocators, node_throwing_d_mem_static_tag>
: public dynamic_node<Value, Parameters, Box, Allocators, node_throwing_d_mem_static_tag>
{
- typedef index::pushable_array<
+ typedef throwing_pushable_array<
std::pair<
Box,
- dynamic_node<Value, Parameters, Box, Allocators, node_d_mem_static_tag> *
+ dynamic_node<Value, Parameters, Box, Allocators, node_throwing_d_mem_static_tag> *
>,
Parameters::max_elements + 1
> elements_type;
@@ -95,7 +96,7 @@
struct dynamic_leaf<Value, Parameters, Box, Allocators, node_throwing_d_mem_static_tag>
: public dynamic_node<Value, Parameters, Box, Allocators, node_throwing_d_mem_static_tag>
{
- typedef index::pushable_array<Value, Parameters::max_elements + 1> elements_type;
+ typedef throwing_pushable_array<Value, Parameters::max_elements + 1> elements_type;
template <typename Dummy>
inline dynamic_leaf(Dummy) {}
@@ -106,6 +107,13 @@
elements_type elements;
};
+// elements derived type
+template <typename OldValue, size_t N, typename NewValue>
+struct container_from_elements_type<throwing_pushable_array<OldValue, N>, NewValue>
+{
+ typedef throwing_pushable_array<NewValue, N> type;
+};
+
// nodes traits
template <typename Value, typename Parameters, typename Box, typename Allocators>
@@ -159,11 +167,29 @@
leaf_allocator_type leaf_allocator;
};
-struct internal_node_bad_alloc : public std::exception
+struct node_bad_alloc : public std::exception
{
const char * what() const throw() { return "internal node creation failed."; }
};
+struct throwing_node_settings
+{
+ static void throw_if_required()
+ {
+ // throw if counter meets max count
+ if ( get_max_calls_ref() <= get_calls_counter_ref() )
+ throw node_bad_alloc();
+ else
+ ++get_calls_counter_ref();
+ }
+
+ static void reset_calls_counter() { get_calls_counter_ref() = 0; }
+ static void set_max_calls(size_t mc) { get_max_calls_ref() = mc; }
+
+ static size_t & get_calls_counter_ref() { static size_t cc = 0; return cc; }
+ static size_t & get_max_calls_ref() { static size_t mc = (std::numeric_limits<size_t>::max)(); return mc; }
+};
+
// create_node
template <typename Allocators, typename Value, typename Parameters, typename Box>
@@ -176,27 +202,13 @@
apply(Allocators & allocators)
{
// throw if counter meets max count
- if ( get_max_calls_ref() <= get_calls_counter_ref() )
- throw internal_node_bad_alloc();
- else
- ++get_calls_counter_ref();
+ throwing_node_settings::throw_if_required();
return create_dynamic_node<
dynamic_node<Value, Parameters, Box, Allocators, node_throwing_d_mem_static_tag>,
dynamic_internal_node<Value, Parameters, Box, Allocators, node_throwing_d_mem_static_tag>
>::template apply(allocators.internal_node_allocator, allocators.internal_node_allocator);
}
-
- static void reset_calls_counter() { get_calls_counter_ref() = 0; }
- static void set_max_calls(size_t mc) { get_max_calls_ref() = mc; }
-
- static size_t & get_calls_counter_ref() { static size_t cc = 0; return cc; }
- static size_t & get_max_calls_ref() { static size_t mc = 0; return mc; }
-};
-
-struct leaf_bad_alloc : public std::exception
-{
- const char * what() const throw() { return "leaf node creation failed."; }
};
template <typename Allocators, typename Value, typename Parameters, typename Box>
@@ -209,88 +221,17 @@
apply(Allocators & allocators)
{
// throw if counter meets max count
- if ( get_max_calls_ref() <= get_calls_counter_ref() )
- throw leaf_bad_alloc();
- else
- ++get_calls_counter_ref();
+ throwing_node_settings::throw_if_required();
return create_dynamic_node<
dynamic_node<Value, Parameters, Box, Allocators, node_throwing_d_mem_static_tag>,
dynamic_leaf<Value, Parameters, Box, Allocators, node_throwing_d_mem_static_tag>
>::template apply(allocators.leaf_allocator, allocators.leaf_allocator);
}
-
- static void reset_calls_counter() { get_calls_counter_ref() = 0; }
- static void set_max_calls(size_t mc) { get_max_calls_ref() = mc; }
-
- static size_t & get_calls_counter_ref() { static size_t cc = 0; return cc; }
- static size_t & get_max_calls_ref() { static size_t mc = 0; return mc; }
};
}} // namespace detail::rtree
}}} // namespace boost::geometry::index
-// value implementation
-
-struct throwing_value_copy_exception : public std::exception
-{
- const char * what() const throw() { return "value copy failed."; }
-};
-
-struct throwing_value
-{
- explicit throwing_value(int v = 0)
- : value(v)
- {}
-
- bool operator==(throwing_value const& v) const
- {
- return value == v.value;
- }
-
- throwing_value(throwing_value const& v)
- {
- throw_if_required();
-
- value = v.value;
- }
-
- throwing_value & operator=(throwing_value const& v)
- {
- throw_if_required();
-
- value = v.value;
- return *this;
- }
-
- void throw_if_required()
- {
- // throw if counter meets max count
- if ( get_max_calls_ref() <= get_calls_counter_ref() )
- throw throwing_value_copy_exception();
- else
- ++get_calls_counter_ref();
- }
-
- static void reset_calls_counter() { get_calls_counter_ref() = 0; }
- static void set_max_calls(size_t mc) { get_max_calls_ref() = mc; }
-
- static size_t & get_calls_counter_ref() { static size_t cc = 0; return cc; }
- static size_t & get_max_calls_ref() { static size_t mc = 0; return mc; }
-
- int value;
-};
-
-template <typename T, typename C>
-struct generate_value< std::pair<bg::model::point<T, 2, C>, throwing_value> >
-{
- typedef bg::model::point<T, 2, C> P;
- typedef std::pair<P, throwing_value> R;
- static R apply(int x, int y)
- {
- return std::make_pair(P(x, y), throwing_value(x + y * 100));
- }
-};
-
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_TEST_RTREE_EXCEPTIONS_HPP
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_dev/test/rtree/test_throwing.hpp 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -0,0 +1,322 @@
+// Boost.Geometry Index
+//
+// Throwing objects implementation
+//
+// Copyright (c) 2011-2012 Adam Wulkiewicz, Lodz, Poland.
+//
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_TEST_THROWING_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_TEST_THROWING_HPP
+
+// value
+
+struct throwing_value_copy_exception : public std::exception
+{
+ const char * what() const throw() { return "value copy failed."; }
+};
+
+struct throwing_value
+{
+ explicit throwing_value(int v = 0)
+ : value(v)
+ {}
+
+ bool operator==(throwing_value const& v) const
+ {
+ return value == v.value;
+ }
+
+ throwing_value(throwing_value const& v)
+ {
+ throw_if_required();
+
+ value = v.value;
+ }
+
+ throwing_value & operator=(throwing_value const& v)
+ {
+ throw_if_required();
+
+ value = v.value;
+ return *this;
+ }
+
+ void throw_if_required()
+ {
+ // throw if counter meets max count
+ if ( get_max_calls_ref() <= get_calls_counter_ref() )
+ throw throwing_value_copy_exception();
+ else
+ ++get_calls_counter_ref();
+ }
+
+ static void reset_calls_counter() { get_calls_counter_ref() = 0; }
+ static void set_max_calls(size_t mc) { get_max_calls_ref() = mc; }
+
+ static size_t & get_calls_counter_ref() { static size_t cc = 0; return cc; }
+ static size_t & get_max_calls_ref() { static size_t mc = (std::numeric_limits<size_t>::max)(); return mc; }
+
+ int value;
+};
+
+template <typename T, typename C>
+struct generate_value< std::pair<bg::model::point<T, 2, C>, throwing_value> >
+{
+ typedef bg::model::point<T, 2, C> P;
+ typedef std::pair<P, throwing_value> R;
+ static R apply(int x, int y)
+ {
+ return std::make_pair(P(x, y), throwing_value(x + y * 100));
+ }
+};
+
+// box
+//
+//#include <boost/geometry/geometries/register/box.hpp>
+//
+//struct throwing_box_copy_exception : public std::exception
+//{
+// const char * what() const throw() { return "box copy failed."; }
+//};
+//
+//template <typename Point>
+//struct throwing_box
+//{
+// throwing_box(){}
+//
+// throwing_box(Point const& m, Point const& mm)
+// : min_p(m), max_p(mm)
+// {}
+//
+// throwing_box(throwing_box const& o)
+// {
+// throw_if_required();
+//
+// min_p = o.min_p;
+// max_p = o.max_p;
+// }
+//
+// throwing_box & operator=(throwing_box const& o)
+// {
+// throw_if_required();
+//
+// min_p = o.min_p;
+// max_p = o.max_p;
+// return *this;
+// }
+//
+// void throw_if_required()
+// {
+// // throw if counter meets max count
+// if ( get_max_calls_ref() <= get_calls_counter_ref() )
+// throw throwing_box_copy_exception();
+// else
+// ++get_calls_counter_ref();
+// }
+//
+// static void reset_calls_counter() { get_calls_counter_ref() = 0; }
+// static void set_max_calls(size_t mc) { get_max_calls_ref() = mc; }
+//
+// static size_t & get_calls_counter_ref() { static size_t cc = 0; return cc; }
+// static size_t & get_max_calls_ref() { static size_t mc = (std::numeric_limits<size_t>::max)(); return mc; }
+//
+// Point min_p;
+// Point max_p;
+//};
+//
+//BOOST_GEOMETRY_REGISTER_BOX_TEMPLATED(throwing_box, min_p, max_p)
+//
+//namespace boost { namespace geometry { namespace index {
+//
+//template <typename CT, size_t D, typename CS>
+//struct default_box_type< bg::model::point<CT, D, CS> >
+//{
+// typedef throwing_box<
+// bg::model::point<CT, D, CS>
+// > type;
+//};
+//
+//}}} // namespace boost::geometry::index
+
+#include <boost/geometry/extensions/index/pushable_array.hpp>
+
+struct throwing_pushable_array_exception : public std::exception
+{
+ const char * what() const throw() { return "pushable array exception."; }
+};
+
+struct throwing_pushable_array_settings
+{
+ static void throw_if_required()
+ {
+ // throw if counter meets max count
+ if ( get_max_calls_ref() <= get_calls_counter_ref() )
+ throw throwing_pushable_array_exception();
+ else
+ ++get_calls_counter_ref();
+ }
+
+ static void reset_calls_counter() { get_calls_counter_ref() = 0; }
+ static void set_max_calls(size_t mc) { get_max_calls_ref() = mc; }
+
+ static size_t & get_calls_counter_ref() { static size_t cc = 0; return cc; }
+ static size_t & get_max_calls_ref() { static size_t mc = (std::numeric_limits<size_t>::max)(); return mc; }
+};
+
+template <typename Element, size_t Capacity>
+class throwing_pushable_array
+{
+ typedef typename boost::array<Element, Capacity> array_type;
+
+public:
+ typedef typename array_type::value_type value_type;
+ typedef typename array_type::size_type size_type;
+ typedef typename array_type::iterator iterator;
+ typedef typename array_type::const_iterator const_iterator;
+ typedef typename array_type::reverse_iterator reverse_iterator;
+ typedef typename array_type::const_reverse_iterator const_reverse_iterator;
+ typedef typename array_type::reference reference;
+ typedef typename array_type::const_reference const_reference;
+
+ inline throwing_pushable_array()
+ : m_size(0)
+ {}
+
+ //inline explicit throwing_pushable_array(size_type s)
+ // : m_size(s)
+ //{
+ // BOOST_GEOMETRY_INDEX_ASSERT(s <= Capacity, "size too big");
+ //}
+
+ inline void resize(size_type s)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(s <= Capacity, "size too big");
+ throwing_pushable_array_settings::throw_if_required();
+ m_size = s;
+ }
+
+ inline void reserve(size_type /*s*/)
+ {
+ //BOOST_GEOMETRY_INDEX_ASSERT(s <= Capacity, "size too big");
+ // do nothing
+ }
+
+ inline Element & operator[](size_type i)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(i < m_size, "index of the element outside the container");
+ return m_array[i];
+ }
+
+ inline Element const& operator[](size_type i) const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(i < m_size, "index of the element outside the container");
+ return m_array[i];
+ }
+
+ inline Element const& front() const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return m_array.front();
+ }
+
+ inline Element & front()
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return m_array.front();
+ }
+
+ inline Element const& back() const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return *(begin() + (m_size - 1));
+ }
+
+ inline Element & back()
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return *(begin() + (m_size - 1));
+ }
+
+ inline iterator begin()
+ {
+ return m_array.begin();
+ }
+
+ inline iterator end()
+ {
+ return m_array.begin() + m_size;
+ }
+
+ inline const_iterator begin() const
+ {
+ return m_array.begin();
+ }
+
+ inline const_iterator end() const
+ {
+ return m_array.begin() + m_size;
+ }
+
+ inline reverse_iterator rbegin()
+ {
+ return reverse_iterator(end());
+ }
+
+ inline reverse_iterator rend()
+ {
+ return reverse_iterator(begin());
+ }
+
+ inline const_reverse_iterator rbegin() const
+ {
+ return const_reverse_iterator(end());
+ }
+
+ inline const_reverse_iterator rend() const
+ {
+ return const_reverse_iterator(begin());
+ }
+
+ inline void clear()
+ {
+ m_size = 0;
+ }
+
+ void push_back(Element const& v)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(m_size < Capacity, "can't further increase the size of the container");
+ throwing_pushable_array_settings::throw_if_required();
+ m_array[m_size] = v;
+ ++m_size;
+ }
+
+ inline void pop_back()
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ --m_size;
+ }
+
+ inline bool empty() const
+ {
+ return m_size == 0;
+ }
+
+ inline size_t size() const
+ {
+ return m_size;
+ }
+
+ inline size_t capacity() const
+ {
+ return Capacity;
+ }
+
+private:
+ boost::array<Element, Capacity> m_array;
+ size_type m_size;
+};
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_TEST_THROWING_HPP
==============================================================================
--- sandbox-branches/geometry/index_dev/tests/additional_speed.cpp (original)
+++ sandbox-branches/geometry/index_dev/tests/additional_speed.cpp 2012-11-20 17:49:14 EST (Tue, 20 Nov 2012)
@@ -48,9 +48,9 @@
typedef bg::model::box<P> B;
//typedef bgi::rtree<B, bgi::linear<32, 8> > RT;
//typedef bgi::rtree<B, bgi::runtime::linear > RT;
- typedef bgi::rtree<B, bgi::quadratic<32, 8> > RT;
+ //typedef bgi::rtree<B, bgi::quadratic<32, 8> > RT;
// typedef bgi::rtree<B, bgi::runtime::quadratic > RT;
- //typedef bgi::rtree<B, bgi::rstar<32, 8> > RT;
+ typedef bgi::rtree<B, bgi::rstar<32, 8> > RT;
//typedef bgi::rtree<B, bgi::runtime::rstar > RT;
for ( ;; )