Subject: [Boost-commit] svn:boost r85385 - in sandbox/geometry/boost/geometry/index/detail/rtree: . node
From: adam.wulkiewicz_at_[hidden]
Date: 2013-08-17 17:43:21
Author: awulkiew
Date: 2013-08-17 17:43:21 EDT (Sat, 17 Aug 2013)
New Revision: 85385
URL: http://svn.boost.org/trac/boost/changeset/85385
Log:
[sandbox][geometry][index] added some dirty preliminary version of rtree storage manager
Added:
sandbox/geometry/boost/geometry/index/detail/rtree/storage_manager.hpp (contents, props changed)
Text files modified:
sandbox/geometry/boost/geometry/index/detail/rtree/node/node_auto_ptr.hpp | 4
sandbox/geometry/boost/geometry/index/detail/rtree/storage_manager.hpp | 405 ++++++++++++++++++++++++++++++++++++++++
2 files changed, 407 insertions(+), 2 deletions(-)
Modified: sandbox/geometry/boost/geometry/index/detail/rtree/node/node_auto_ptr.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/index/detail/rtree/node/node_auto_ptr.hpp Sat Aug 17 17:05:44 2013 (r85384)
+++ sandbox/geometry/boost/geometry/index/detail/rtree/node/node_auto_ptr.hpp 2013-08-17 17:43:21 EDT (Sat, 17 Aug 2013) (r85385)
@@ -39,7 +39,7 @@
reset();
}
- void reset(pointer ptr = 0)
+ void reset(pointer ptr = pointer(0))
{
if ( m_ptr )
{
@@ -51,7 +51,7 @@
void release()
{
- m_ptr = 0;
+ m_ptr = pointer(0);
}
pointer get() const
Added: sandbox/geometry/boost/geometry/index/detail/rtree/storage_manager.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ sandbox/geometry/boost/geometry/index/detail/rtree/storage_manager.hpp 2013-08-17 17:43:21 EDT (Sat, 17 Aug 2013) (r85385)
@@ -0,0 +1,405 @@
+// Boost.Geometry Index
+//
+// R-tree storage manager
+//
+// Copyright (c) 2011-2013 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_INDEX_DETAIL_RTREE_STORAGE_MANAGER_HPP
+#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_STORAGE_MANAGER_HPP
+
+namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree {
+
+template <typename Val, typename Ptr, typename Id>
+class storage_ptr
+{
+public:
+ typedef Val value_type;
+
+ storage_ptr() {}
+
+ storage_ptr(Ptr p, Id i)
+ : m_ptr(p), m_id(i) {}
+
+ template<typename P>
+ storage_ptr(P p, Id i)
+ : m_ptr(p), m_id(i) {}
+
+ storage_ptr(storage_ptr const& p)
+ : m_ptr(p.m_ptr), m_id(p.m_id) {}
+
+ template <typename V, typename P>
+ storage_ptr(storage_ptr<V, P, Id> const& other)
+ : m_ptr(static_cast<Ptr>(other.m_ptr)), m_id(other.m_id) {}
+
+ //Val & operator*() { BOOST_ASSERT_MSG(m_ptr, "null ptr"); return *m_ptr; }
+ //const Val & operator*() const { BOOST_ASSERT_MSG(m_ptr, "null ptr"); return *m_ptr; }
+ //Val * operator->() { BOOST_ASSERT_MSG(m_ptr, "null ptr"); return boost::addressof(*m_ptr); }
+ //const Val * operator->() const { BOOST_ASSERT_MSG(m_ptr, "null ptr"); return boost::addressof(*m_ptr); }
+
+ Ptr get() const { return m_ptr; }
+ Id id() const { return m_id; }
+
+ friend bool operator< (storage_ptr const& l, storage_ptr const& r) { return l.id() < r.id(); }
+ friend bool operator== (storage_ptr const& l, storage_ptr const& r) { return l.id() == r.id(); }
+
+private:
+ Ptr m_ptr;
+ Id m_id;
+};
+
+// TODO: optimization
+// if node_id is unsigned integer and has the same number of bytes as node_pointer
+// and node_pointer is convertible to node_id
+// use node_pointer as node_id and as storage_node_pointer
+// THIS MAY BE ENCLOSED IN STORAGE_PTR
+// SIGNED TYPES HAS LESS DIGITS THAN UNSIGNED - THIS STRUCT IS WRONG - LEAVE IT FOR NOW, OPTIMIZE LATER
+//template <typename MemId, typename StorageId>
+//struct is_directly_convertible_to_id
+// : boost::mpl::and_<
+// boost::is_integral<StorageId>,
+// boost::mpl::bool_<std::numeric_limits<MemId>::digits == std::numeric_limits<StorageId>::digits>,
+// boost::is_convertible<MemId, StorageId>
+// >
+//{};
+
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Storage>
+class storage_manager
+ : public Allocators
+ , public Storage
+{
+public:
+ typedef typename Allocators::allocator_type allocator_type;
+ typedef typename Allocators::node node;
+ typedef typename Allocators::node_pointer node_pointer;
+ //typedef typename Allocators::size_type size_type;
+
+ typedef typename Storage::node_id node_id;
+ typedef typename Storage::size_type storage_size_type; // different name
+
+ typedef storage_ptr<node, node_pointer, node_id> storage_node_pointer;
+
+ // allocator_type
+ storage_manager(Allocators const& allocators, Storage const& storage)
+ : Allocators(allocators), Storage(storage)
+ , m_current_operation(none)
+ {}
+
+ template <typename Node>
+ storage_node_pointer create()
+ {
+// TODO - not thread safe
+
+ node_pointer n = rtree::create_node<Allocators, Node>(allocators()); // may throw
+
+ node_id id = storage().new_id(static_cast<uintptr_t>(boost::addressof(*n))); // may throw
+
+ storage_node_pointer ptr(n, id);
+
+ create_node<Node>(ptr); // may throw
+
+ return ptr;
+ }
+
+ template <typename Node>
+ void destroy(storage_node_pointer ptr)
+ {
+// TODO - thread safe in the current form (code commented out)
+
+ //destroy_node<Node>(ptr);
+
+ rtree::destroy_node<Allocators, Node>(allocators(), ptr.get()); // shouldn't throw
+
+ destroy_node<Node>(storage_node_pointer(node_pointer(0), ptr.id()));
+ }
+
+ template <typename Node>
+ void modify(storage_node_pointer ptr)
+ {
+ modify_node<Node>(ptr);
+ }
+
+ // for serialization of nodes use wrapers, different than the ones used in whole-tree serialization.
+
+ // header will be stored separately:
+ // tree height
+ // root id
+ // algorithms
+ // other?
+
+ // in unbalanced tree nodes probably the type of the node will be stored
+
+ node & dereference(storage_node_pointer ptr)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(ptr.get(), "node should be acquired before dereference");
+ return *ptr.get();
+ }
+
+// INFO
+// Nodes aren't stored during acquire
+
+ template <typename Node>
+ void acquire(storage_node_pointer & ptr)
+ {
+// TODO - not thread safe
+
+ BOOST_GEOMETRY_INDEX_ASSERT(!ptr.get(), "can't acquire already acquired node");
+
+ node_pointer n = rtree::create_node<Allocators, Node>(allocators()); // may throw
+ storage().load_node(ptr.id(), rtree::get<Node>(*n)); // may throw
+
+ ptr = storage_node_pointer(n, ptr.id());
+ }
+
+// WARNING!
+// Can't destroy node in dismiss if it were modified
+
+// is dismiss really needed since nodes will be unloaded in flush()
+
+ template <typename Node>
+ void dismiss(storage_node_pointer & ptr)
+ {
+// TODO - not thread safe
+
+ BOOST_GEOMETRY_INDEX_ASSERT(ptr.get(), "node should be acquired before dismiss");
+
+ rtree::destroy_node<Allocators, Node>(allocators(), ptr.get()); // shouldn't throw
+ storage().unload_node(ptr.id()); // may throw?
+
+ ptr = storage_node_pointer(node_pointer(0), ptr.id());
+ }
+
+ //enum operation { none, query, insert, remove, copy };
+ // or
+ enum operation { none, nonmodifying, incremental, immediate };
+
+ void operation_begin(operation o) {}
+ //void operation_end(operation o) {} - not needed since flush will be used
+
+ void flush()
+ {
+ typedef typename nodes_map::iterator iter;
+
+ // apply all changes / save all modified, created nodes / delete nodes
+ if ( m_current_operation == incremental )
+ {
+ for ( iter it = m_nodes.begin() ; m_nodes.end() ; ++it )
+ {
+ if ( it->second == modified )
+ storage().save_node(it->first);
+ else if ( it->second == destroyed )
+ storage().destroy_node(it->first);
+
+// TODO
+// Do something with other nodes?
+// call storage().unload(it->first.id()) ?
+ }
+ }
+
+ // TODO - cacheing
+ for ( iter it = m_nodes.begin() ; it != m_nodes.end() ; ++it )
+ {
+ rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators>
+ auto_remover(it->first.get());
+ }
+
+ m_nodes.clear();
+ m_current_operation = none;
+ }
+
+ storage_node_pointer root() { return null(); }
+
+ storage_node_pointer null() { return storage_node_pointer(node_pointer(0), 0); }
+
+private:
+ enum flag { unloaded, loaded, modified, destroyed };
+ typedef std::map<storage_node_pointer, flag> nodes_map;
+
+ template <typename Node>
+ void create_node(storage_node_pointer ptr)
+ {
+ if ( m_current_operation == incremental )
+ {
+ //BOOST_GEOMETRY_INDEX_ASSERT(m_nodes.find(ptr) == m_nodes.end(), "node already created");
+ m_nodes.insert(std::make_pair(ptr, modified)); // may throw
+ }
+ else if ( m_current_operation == immediate )
+ {
+ storage().save_node(ptr.id(), rtree::get<Node>(dereference(ptr))); // may throw
+ }
+ else
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(false, "valid operation wasn't begined");
+ }
+ }
+
+ template <typename Node>
+ void modify_node(storage_node_pointer ptr)
+ {
+ if ( m_current_operation == incremental )
+ {
+ typename nodes_map::iterator it = m_nodes.find(ptr); // shouldn't throw
+ BOOST_GEOMETRY_INDEX_ASSERT(it != m_nodes.end() && it->second < deleted, "node should be stored and not deleted");
+ it->second = modified;
+ }
+ else if ( m_current_operation == immediate )
+ {
+ storage().save_node(ptr.id(), rtree::get<Node>(dereference(ptr))); // may throw
+ }
+ else
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(false, "valid operation wasn't begined");
+ }
+ }
+
+ template <typename Node>
+ void destroy_node(storage_node_pointer ptr)
+ {
+ if ( m_current_operation == incremental )
+ {
+ typename nodes_map::iterator it = m_nodes.find(ptr);
+ BOOST_GEOMETRY_INDEX_ASSERT(it != m_nodes.end() && it->second < deleted, "node should be stored and not deleted");
+ // really? or maybe
+// if ( it == m_nodes.end() )
+// m_nodes.insert(std::make_pair(ptr, deleted)); // may throw if it will be here, otherwise it will be thread safe as it is
+// else
+ it->second = destroyed;
+ }
+ else if ( m_current_operation == immediate )
+ {
+ storage().destroy_node(ptr.id()); // may throw
+ }
+ else
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(false, "valid operation wasn't begined");
+ }
+ }
+
+ Allocators & allocators() { return *this; }
+ Storage & storage() { return *this; }
+
+ nodes_map m_nodes;
+ operation m_current_operation;
+};
+
+// Also the header must be loaded/saved
+
+// rename to serializing_storage
+//template <typename Value>
+//class storage
+//{
+//public:
+// typedef unsigned long long node_id;
+// typedef unsigned long long size_type;
+
+// storage(std::string const& dir)
+// {
+// // try to open header
+// // if ok, load header data and probably root as well
+// }
+
+// node_id null_id() { return 0; }
+
+// // or maybe return header?
+// node_id root_id() { return 0; }
+
+// template <typename T>
+// node_id new_id(T seed) {}
+// void delete_id(node_id id) {}
+
+// template <typename Node> // leaf or internal_node
+// void save_node(node_id id, Node const& n)
+// {
+// // if file isn't created, create it
+// // save node
+//// typedef typename rtree::elements_type<Node>::type elements_type;
+//// typedef typename elements_type::value_type element_type;
+//// BOOST_FOREACH(element_type const& el, rtree::elements(n))
+//// save_element(el);
+
+// // Bedzie problem z elementami movable-only
+// // Bedzie problem z tym, ze second pary w internal node bedzie wskaznikiem+id a nie tylko id
+// // mozna to roznie rozwiazac, np. wrapper<Node> i udostepnienie tego co trzeba
+// // lub ustandaryzowanie wskaznika przechowywanego jako second,
+// // lepiej byloby nie udostepniac wskaznikow
+// }
+
+// template <typename Node> // leaf or internal_node
+// void load_node(node_id id, Node & n) {}
+
+// // Node concept:
+// // elements_type<Node>::type
+// // elements(node)
+// // elements are stored in random access container
+// // internal nodes elements are stored in objects similar to pairs
+// // - this may cause a problem if movable-only pairs will be used in the future
+// // - values and pairs shouldn't be copied?
+
+// // This isn't fully ok
+// // It's possible that those won't be raw nodes but some wrappers
+
+// // Header concept:
+// // ?
+// // root, size, leafs_level
+
+// // a co jesli ktos bedzie chcial sobie np przechowac wskazniki do wezlow, ktore beda mialy byc zapisane w przyszlosci?
+// // bo nie powinien kopiowac wartosci skoro przewidywane jest zrobienie move-only
+// // chyba zeby udostepnic node_pointer do przechowywania
+
+// // lipa bedzie jesli najpierw wezel zostanie zmieniony a potem usuniety
+// // nie, ok poprostu status wszystkich zmienianych wezlow bedzie przechowywany w menedzerze - CREATED, MODIFIED, DELETED
+
+// void save_begin() {}
+// void save_end() {}
+
+//private:
+//// template <typename Element>
+//// void save_element(Element const& el) {}
+//// void save_element(Value const& el) {}
+//};
+
+//struct none {};
+
+//template <typename Allocators>
+//class storage_manager<Allocators, none>
+// : public Allocators
+//{
+//public:
+// typedef typename Allocators::allocator_type allocator_type;
+// typedef typename Allocators::node node;
+// typedef typename Allocators::node_pointer node_pointer;
+// typedef typename Allocators::size_type size_type;
+
+// typedef node_pointer storage_node_pointer;
+// typedef size_type storage_size_type;
+
+// storage_manager(Allocators const& allocators)
+// : Allocators(allocators)
+// {}
+
+// node & dereference(storage_node_pointer ptr) { return *ptr; }
+
+// storage_node_pointer load(storage_node_pointer ptr) { return ptr; }
+// void unload(storage_node_pointer /*ptr*/) {}
+
+// void modified(storage_node_pointer /*ptr*/, size_type /*child_index*/) {}
+// void save() {}
+
+// storage_node_pointer root() { return storage_node_pointer(0); }
+
+//private:
+// Allocators & allocators() { return *this; }
+//};
+
+// allocator storage
+// v v
+// allocators v
+// v v
+// some_nodes_data_manager
+
+}}}}} // namespace boost::geometry::index::detail::rtree
+
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_STORAGE_MANAGER_HPP