#include <boost/geometry/index/detail/algorithms/bounds.hpp>
#include <boost/geometry/index/detail/algorithms/content.hpp>
+#include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace detail { namespace rtree {
// Default choose_next_node
-template <typename Value, typename Options, typename Box, typename Allocators, typename ChooseNextNodeTag>
+template
+<
+ typename MembersHolder,
+ typename ChooseNextNodeTag = typename MembersHolder::options_type::choose_next_node_tag
+>
class choose_next_node;
-template <typename Value, typename Options, typename Box, typename Allocators>
-class choose_next_node<Value, Options, Box, Allocators, choose_by_content_diff_tag>
+template <typename MembersHolder>
+class choose_next_node<MembersHolder, choose_by_content_diff_tag>
{
public:
- typedef typename Options::parameters_type parameters_type;
+ typedef typename MembersHolder::box_type box_type;
+ typedef typename MembersHolder::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 MembersHolder::node node;
+ typedef typename MembersHolder::internal_node internal_node;
+ typedef typename MembersHolder::leaf leaf;
typedef typename rtree::elements_type<internal_node>::type children_type;
- typedef typename index::detail::default_content_result<Box>::type content_type;
+ typedef typename index::detail::default_content_result<box_type>::type content_type;
template <typename Indexable>
static inline size_t apply(internal_node & n,
child_type const& ch_i = children[i];
// expanded child node's box
- Box box_exp(ch_i.first);
+ box_type box_exp(ch_i.first);
index::detail::expand(box_exp, indexable,
index::detail::get_strategy(parameters));
// ----------------------------------------------------------------------- //
// Not implemented here
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename RedistributeTag>
+template
+<
+ typename MembersHolder,
+ typename RedistributeTag = typename MembersHolder::options_type::redistribute_tag
+>
struct redistribute_elements
{
BOOST_MPL_ASSERT_MSG(
// ----------------------------------------------------------------------- //
// Split algorithm
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename SplitTag>
+template
+<
+ typename MembersHolder,
+ typename SplitTag = typename MembersHolder::options_type::split_tag
+>
class split
{
BOOST_MPL_ASSERT_MSG(
};
// Default split algorithm
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-class split<Value, Options, Translator, Box, Allocators, split_default_tag>
+template <typename MembersHolder>
+class split<MembersHolder, split_default_tag>
{
protected:
- typedef typename Options::parameters_type parameters_type;
+ typedef typename MembersHolder::parameters_type parameters_type;
+ typedef typename MembersHolder::box_type box_type;
+ typedef typename MembersHolder::translator_type translator_type;
+ typedef typename MembersHolder::allocators_type allocators_type;
+ typedef typename MembersHolder::size_type size_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 MembersHolder::node node;
+ typedef typename MembersHolder::internal_node internal_node;
+ typedef typename MembersHolder::leaf leaf;
- typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
+ typedef typename MembersHolder::node_pointer node_pointer;
public:
typedef index::detail::varray<
template <typename Node>
static inline void apply(nodes_container_type & additional_nodes,
Node & n,
- Box & n_box,
+ box_type & n_box,
parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators)
+ translator_type const& translator,
+ allocators_type & allocators)
{
// TODO - consider creating nodes always with sufficient memory allocated
// create additional node, use auto destroyer for automatic destruction on exception
- subtree_destroyer second_node(rtree::create_node<Allocators, Node>::apply(allocators), allocators); // MAY THROW, STRONG (N: alloc)
+ node_pointer n2_ptr = rtree::create_node<allocators_type, Node>::apply(allocators); // MAY THROW, STRONG (N: alloc)
// create reference to the newly created node
- Node & n2 = rtree::get<Node>(*second_node);
-
- // NOTE: thread-safety
- // After throwing an exception by redistribute_elements the original node may be not changed or
- // both nodes may be empty. In both cases the tree won't be valid r-tree.
- // The alternative is to create 2 (or more) additional nodes here and store backup info
- // in the original node, then, if exception was thrown, the node would always have more than max
- // elements.
- // The alternative is to use moving semantics in the implementations of redistribute_elements,
- // it will be possible to throw from boost::move() in the case of e.g. static size nodes.
-
- // redistribute elements
- Box box2;
- redistribute_elements<
- Value,
- Options,
- Translator,
- Box,
- Allocators,
- typename Options::redistribute_tag
- >::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() &&
- rtree::elements(n).size() <= parameters.get_max_elements(),
- "unexpected number of elements");
- BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n2).size() &&
- rtree::elements(n2).size() <= parameters.get_max_elements(),
- "unexpected number of elements");
-
- // return the list of newly created nodes (this algorithm returns one)
- additional_nodes.push_back(rtree::make_ptr_pair(box2, second_node.get())); // MAY THROW, STRONG (alloc, copy)
-
- // release the ptr
- second_node.release();
+ Node & n2 = rtree::get<Node>(*n2_ptr);
+
+ BOOST_TRY
+ {
+ // NOTE: thread-safety
+ // After throwing an exception by redistribute_elements the original node may be not changed or
+ // both nodes may be empty. In both cases the tree won't be valid r-tree.
+ // The alternative is to create 2 (or more) additional nodes here and store backup info
+ // in the original node, then, if exception was thrown, the node would always have more than max
+ // elements.
+ // The alternative is to use moving semantics in the implementations of redistribute_elements,
+ // it will be possible to throw from boost::move() in the case of e.g. static size nodes.
+
+ // redistribute elements
+ box_type box2;
+ redistribute_elements<MembersHolder>
+ ::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() &&
+ rtree::elements(n).size() <= parameters.get_max_elements(),
+ "unexpected number of elements");
+ BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n2).size() &&
+ rtree::elements(n2).size() <= parameters.get_max_elements(),
+ "unexpected number of elements");
+
+ // return the list of newly created nodes (this algorithm returns one)
+ additional_nodes.push_back(rtree::make_ptr_pair(box2, n2_ptr)); // MAY THROW, STRONG (alloc, copy)
+ }
+ BOOST_CATCH(...)
+ {
+ // NOTE: This code is here to prevent leaving the rtree in a state
+ // after an exception is thrown in which pushing new element could
+ // result in assert or putting it outside the memory of node elements.
+ typename rtree::elements_type<Node>::type & elements = rtree::elements(n);
+ size_type const max_size = parameters.get_max_elements();
+ if (elements.size() > max_size)
+ {
+ rtree::destroy_element<MembersHolder>::apply(elements[max_size], allocators);
+ elements.pop_back();
+ }
+
+ rtree::visitors::destroy<MembersHolder>::apply(n2_ptr, allocators);
+
+ BOOST_RETHROW
+ }
+ BOOST_CATCH_END
}
};
};
// Default insert visitor
-template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <typename Element, typename MembersHolder>
class insert
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
+ : MembersHolder::visitor
{
protected:
- typedef typename Options::parameters_type parameters_type;
+ typedef typename MembersHolder::box_type box_type;
+ typedef typename MembersHolder::value_type value_type;
+ typedef typename MembersHolder::parameters_type parameters_type;
+ typedef typename MembersHolder::translator_type translator_type;
+ typedef typename MembersHolder::allocators_type allocators_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 MembersHolder::node node;
+ typedef typename MembersHolder::internal_node internal_node;
+ typedef typename MembersHolder::leaf leaf;
- typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
- typedef typename Allocators::node_pointer node_pointer;
- typedef typename Allocators::size_type size_type;
+ typedef rtree::subtree_destroyer<MembersHolder> subtree_destroyer;
+ typedef typename allocators_type::node_pointer node_pointer;
+ typedef typename allocators_type::size_type size_type;
- //typedef typename Allocators::internal_node_pointer internal_node_pointer;
+ //typedef typename allocators_type::internal_node_pointer internal_node_pointer;
typedef internal_node * internal_node_pointer;
inline insert(node_pointer & root,
size_type & leafs_level,
Element const& element,
parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ translator_type const& translator,
+ allocators_type & allocators,
size_type relative_level = 0
)
: m_element(element)
// It's because Points and Segments are compared WRT machine epsilon
// This ensures that leafs bounds correspond to the stored elements
if (BOOST_GEOMETRY_CONDITION((
- boost::is_same<Element, Value>::value
+ boost::is_same<Element, value_type>::value
&& ! index::detail::is_bounding_geometry
<
- typename indexable_type<Translator>::type
+ typename indexable_type<translator_type>::type
>::value )) )
{
geometry::detail::expand_by_epsilon(m_element_bounds);
inline void traverse(Visitor & visitor, internal_node & n)
{
// choose next node
- size_t choosen_node_index = rtree::choose_next_node<Value, Options, Box, Allocators, typename Options::choose_next_node_tag>::
- apply(n, rtree::element_indexable(m_element, m_translator), m_parameters, m_leafs_level - m_traverse_data.current_level);
+ size_t choosen_node_index = rtree::choose_next_node<MembersHolder>
+ ::apply(n, rtree::element_indexable(m_element, m_translator),
+ m_parameters,
+ m_leafs_level - m_traverse_data.current_level);
// expand the node to contain value
index::detail::expand(
template <typename Node>
inline void split(Node & n) const
{
- typedef rtree::split<Value, Options, Translator, Box, Allocators, typename Options::split_tag> split_algo;
+ typedef rtree::split<MembersHolder> split_algo;
typename split_algo::nodes_container_type additional_nodes;
- Box n_box;
+ box_type n_box;
split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators); // MAY THROW (V, E: alloc, copy, N:alloc)
boost::is_same<Node, leaf>::value
&& ! index::detail::is_bounding_geometry
<
- typename indexable_type<Translator>::type
+ typename indexable_type<translator_type>::type
>::value )))
{
geometry::detail::expand_by_epsilon(n_box);
BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*m_root_node), "node should be the root");
// create new root and add nodes
- subtree_destroyer new_root(rtree::create_node<Allocators, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc)
+ subtree_destroyer new_root(rtree::create_node<allocators_type, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc)
BOOST_TRY
{
// TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation
Element const& m_element;
- Box m_element_bounds;
+ box_type m_element_bounds;
parameters_type const& m_parameters;
- Translator const& m_translator;
+ translator_type const& m_translator;
size_type const m_relative_level;
size_type const m_level;
// traversing input parameters
insert_traverse_data<internal_node, internal_node_pointer, size_type> m_traverse_data;
- Allocators & m_allocators;
+ allocators_type & m_allocators;
};
} // namespace detail
// Insert visitor forward declaration
-template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename InsertTag>
+template
+<
+ typename Element,
+ typename MembersHolder,
+ typename InsertTag = typename MembersHolder::options_type::insert_tag
+>
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>
+template <typename Element, typename MembersHolder>
+class insert<Element, MembersHolder, insert_default_tag>
+ : public detail::insert<Element, MembersHolder>
{
public:
- typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
+ typedef detail::insert<Element, MembersHolder> base;
+
+ typedef typename base::parameters_type parameters_type;
+ typedef typename base::translator_type translator_type;
+ typedef typename base::allocators_type allocators_type;
+
typedef typename base::node node;
typedef typename base::internal_node internal_node;
typedef typename base::leaf leaf;
- typedef typename Options::parameters_type parameters_type;
typedef typename base::node_pointer node_pointer;
typedef typename base::size_type size_type;
size_type & leafs_level,
Element const& element,
parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ translator_type const& translator,
+ allocators_type & allocators,
size_type relative_level = 0
)
: base(root, leafs_level, element, parameters, translator, allocators, relative_level)
{
// 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);
+ rtree::visitors::destroy<MembersHolder>::apply(base::m_element.second, base::m_allocators);
BOOST_RETHROW // RETHROW
}
};
// Default insert visitor specialized for Values elements
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-class insert<Value, Value, Options, Translator, Box, Allocators, insert_default_tag>
- : public detail::insert<Value, Value, Options, Translator, Box, Allocators>
+template <typename MembersHolder>
+class insert<typename MembersHolder::value_type, MembersHolder, insert_default_tag>
+ : public detail::insert<typename MembersHolder::value_type, MembersHolder>
{
public:
- typedef detail::insert<Value, Value, Options, Translator, Box, Allocators> base;
+ typedef detail::insert<typename MembersHolder::value_type, MembersHolder> base;
+
+ typedef typename base::value_type value_type;
+ typedef typename base::parameters_type parameters_type;
+ typedef typename base::translator_type translator_type;
+ typedef typename base::allocators_type allocators_type;
+
typedef typename base::node node;
typedef typename base::internal_node internal_node;
typedef typename base::leaf leaf;
- typedef typename Options::parameters_type parameters_type;
typedef typename base::node_pointer node_pointer;
typedef typename base::size_type size_type;
inline insert(node_pointer & root,
size_type & leafs_level,
- Value const& value,
+ value_type const& value,
parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ translator_type const& translator,
+ allocators_type & allocators,
size_type relative_level = 0
)
: base(root, leafs_level, value, parameters, translator, allocators, relative_level)
projects / ceph.git / blobdiff