[Boost-commit] svn:boost r81280 - in sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree: node visitors

Subject: [Boost-commit] svn:boost r81280 - in sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree: node visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-10 05:25:57

Author: awulkiew
Date: 2012-11-10 05:25:56 EST (Sat, 10 Nov 2012)
New Revision: 81280
URL: http://svn.boost.org/trac/boost/changeset/81280

Log:
Exception-safety of the default insert and split algorithms improved.
Added:
   sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node_auto_ptr.hpp   (contents, props changed)
Text files modified: 
   sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp       |    10 ++++++                                  
   sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp |    66 +++++++++++++++++++++++++++++---------- 
   2 files changed, 58 insertions(+), 18 deletions(-)

Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp	(original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp	2012-11-10 05:25:56 EST (Sat, 10 Nov 2012)
@@ -13,12 +13,22 @@
 
 #include <boost/geometry/extensions/index/rtree/node/concept.hpp>
 
+// WARNING!
+// The Node elements containing pointers to nodes, i.e. pair<Box, node*> MUST NOT throw an exception
+// in the copy constructor. Otherwise copying may be broken in push_back() of internal vectors.
+// The result may be two copies of the same pointer in the vector. This may cause the attempt to destroy
+// the same object two times.
+// This means for example that Value's CoordinateType copy constructor MUST NOT throw an exception
+// because Value's CoordinateType is used in Box type.
+
 #include <boost/geometry/extensions/index/rtree/node/node_d_mem_dynamic.hpp>
 #include <boost/geometry/extensions/index/rtree/node/node_d_mem_static.hpp>
 
 #include <boost/geometry/extensions/index/rtree/node/node_s_mem_dynamic.hpp>
 #include <boost/geometry/extensions/index/rtree/node/node_s_mem_static.hpp>
 
+#include <boost/geometry/extensions/index/rtree/node/node_auto_ptr.hpp>
+
 #include <boost/geometry/algorithms/expand.hpp>
 
 namespace boost { namespace geometry { namespace index {

Added: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node_auto_ptr.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node_auto_ptr.hpp	2012-11-10 05:25:56 EST (Sat, 10 Nov 2012)
@@ -0,0 +1,78 @@
+// Boost.Geometry Index
+//
+// R-tree node auto ptr
+//
+// 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_RTREE_NODE_NODE_AUTO_PTR_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_AUTO_PTR_HPP
+
+#include <boost/noncopyable.hpp>
+
+#include <boost/geometry/extensions/index/rtree/visitors/destroy.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree {
+
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+class node_auto_ptr
+    : boost::noncopyable
+{
+    typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
+
+public:
+    node_auto_ptr(node * ptr, Allocators & allocators)
+        : m_ptr(ptr)
+        , m_allocators(allocators)
+    {}
+
+    ~node_auto_ptr()
+    {
+        reset();
+    }
+
+    void reset(node * ptr = 0)
+    {
+        if ( m_ptr )
+        {
+            detail::rtree::visitors::destroy<Value, Options, Translator, Box, Allocators> del_v(m_ptr, m_allocators);
+            detail::rtree::apply_visitor(del_v, *m_ptr);
+        }
+        m_ptr = ptr;
+    }
+
+    void release()
+    {
+        m_ptr = 0;
+    }
+
+    node * get() const
+    {
+        return m_ptr;
+    }
+
+    node & operator*() const
+    {
+        return *m_ptr;
+    }
+
+    node * operator->() const
+    {
+        return m_ptr;
+    }
+
+private:
+    node * m_ptr;
+    Allocators & m_allocators;
+};
+
+}} // namespace detail::rtree
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_AUTO_PTR_HPP

Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp	(original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp	2012-11-10 05:25:56 EST (Sat, 10 Nov 2012)
@@ -119,6 +119,8 @@
     typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
     typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
 
+    typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+
 public:
     typedef index::pushable_array<std::pair<Box, node*>, 1> nodes_container_type;
 
@@ -130,14 +132,23 @@
                              Translator const& translator,
                              Allocators & allocators)
     {
-        // create additional node
-        node * second_node = rtree::create_node<Allocators, Node>::apply(allocators);
+        // 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
+        // create reference to the newly created node
         Node & n2 = rtree::get<Node>(*second_node);
 
         // redistribute elements
         Box box2;
-        redistribute_elements<Value, Options, Translator, Box, Allocators, typename Options::redistribute_tag>::
-            apply(n, n2, n_box, box2, parameters, translator);
+        redistribute_elements<
+            Value,
+            Options,
+            Translator,
+            Box,
+            Allocators,
+            typename Options::redistribute_tag
+        >::apply(n, n2, n_box, box2, parameters, translator);                                               // MAY THROW
 
         // check numbers of elements
         BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() &&
@@ -147,7 +158,11 @@
             rtree::elements(n2).size() <= parameters.get_max_elements(),
             "unexpected number of elements");
 
-        additional_nodes.push_back(std::make_pair(box2, second_node));
+        // return the list of newly created nodes (this algorithm returns one)
+        additional_nodes.push_back(std::make_pair(box2, second_node.get()));                                // MAY THROW
+
+        // release the ptr
+        second_node.release();
     }
 };
 
@@ -205,6 +220,8 @@
     typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
     typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
 
+    typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+
     inline insert(node* & root,
                   size_t & leafs_level,
                   Element const& element,
@@ -258,7 +275,7 @@
         // handle overflow
         if ( m_parameters.get_max_elements() < rtree::elements(n).size() )
         {
-            split(n);
+            split(n);                                                                                               // MAY THROW
         }
     }
 
@@ -288,7 +305,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);
+        split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators);                    // MAY THROW
 
         BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
 
@@ -298,16 +315,19 @@
         // and container of additional elements (std::pair<Box, node*>s or Values)
         // and translator + allocators
         // where node_elements_count + additional_elements > node_max_elements_count
-        // What with elements other than std::pair<Box, node*> ???
+        // What with elements other than std::pair<Box, node*> ?
         // Implement template <node_tag> struct node_element_type or something like that
 
+        // for exception safety
+        node_auto_ptr additional_node_ptr(additional_nodes[0].second, m_allocators);
+
         // node is not the root - just add the new node
         if ( !m_traverse_data.current_is_root() )
         {
             // update old node's box
             m_traverse_data.current_element().first = n_box;
-            // add new node to the parent's children
-            m_traverse_data.parent_elements().push_back(additional_nodes[0]);
+            // add new node to parent's children
+            m_traverse_data.parent_elements().push_back(additional_nodes[0]);                                         // MAY THROW
         }
         // node is the root - add level
         else
@@ -315,14 +335,24 @@
             BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<Node>(m_root_node), "node should be the root");
 
             // create new root and add nodes
-            node * new_root = rtree::create_node<Allocators, internal_node>::apply(m_allocators);
+            node_auto_ptr new_root(rtree::create_node<Allocators, internal_node>::apply(m_allocators), m_allocators); // MAY THROW
 
-            rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(n_box, m_root_node));
-            rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]);
+            try {
+                rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(n_box, m_root_node));  // MAY THROW
+                rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]);                 // MAY THROW
+            } 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
+            }
 
-            m_root_node = new_root;
+            m_root_node = new_root.get();
             ++m_leafs_level;
+
+            new_root.release();
         }
+
+        additional_node_ptr.release();
     }
 
     // TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation
@@ -389,7 +419,7 @@
             rtree::elements(n).push_back(base::m_element);
         }
 
-        base::post_traverse(n);
+        base::post_traverse(n);                                                                                         // MAY THROW
     }
 
     inline void operator()(leaf &)
@@ -430,7 +460,7 @@
         // next traversing step
         base::traverse(*this, n);
 
-        base::post_traverse(n);
+        base::post_traverse(n);                                                                                         // MAY THROW
     }
 
     inline void operator()(leaf & n)
@@ -439,9 +469,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);
+        rtree::elements(n).push_back(base::m_element);                                                                  // MAY THROW
 
-        base::post_traverse(n);
+        base::post_traverse(n);                                                                                         // MAY THROW
     }
 };