rtree/node/variant_dynamic.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree nodes based on Boost.Variant, storing dynamic-size containers
0004 //
0005 // Copyright (c) 2011-2023 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2021-2023.
0008 // Modifications copyright (c) 2021-2023 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_VARIANT_DYNAMIC_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_VARIANT_DYNAMIC_HPP
0018
0019 #include <utility>
0020 #include <boost/container/allocator_traits.hpp>
0021 #include <boost/container/vector.hpp>
0022 #include <boost/core/invoke_swap.hpp>
0023 #include <boost/core/pointer_traits.hpp>
0024 #include <boost/variant/static_visitor.hpp>
0025 #include <boost/variant/variant.hpp>
0026
0027 #include <boost/geometry/index/detail/rtree/options.hpp>
0028 #include <boost/geometry/index/detail/rtree/node/concept.hpp>
0029 #include <boost/geometry/index/detail/rtree/node/pairs.hpp>
0030 #include <boost/geometry/index/detail/rtree/node/scoped_deallocator.hpp>
0031
0032 namespace boost { namespace geometry { namespace index {
0033
0034 namespace detail { namespace rtree {
0035
0036 // nodes default types
0037
0038 template <typename Value, typename Parameters, typename Box, typename Allocators, typename Tag>
0039 struct variant_internal_node
0040 {
0041     typedef rtree::ptr_pair<Box, typename Allocators::node_pointer> element_type;
0042     typedef typename boost::container::allocator_traits
0043         <
0044             typename Allocators::node_allocator_type
0045         >::template rebind_alloc<element_type> allocator_type;
0046
0047     typedef boost::container::vector<element_type, allocator_type> elements_type;
0048
0049     template <typename Al>
0050     inline variant_internal_node(Al const& al)
0051         : elements(allocator_type(al))
0052     {}
0053
0054     elements_type elements;
0055 };
0056
0057 template <typename Value, typename Parameters, typename Box, typename Allocators, typename Tag>
0058 struct variant_leaf
0059 {
0060     typedef typename boost::container::allocator_traits
0061         <
0062             typename Allocators::node_allocator_type
0063         >::template rebind_alloc<Value> allocator_type;
0064
0065     typedef boost::container::vector<Value, allocator_type> elements_type;
0066
0067     template <typename Al>
0068     inline variant_leaf(Al const& al)
0069         : elements(allocator_type(al))
0070     {}
0071
0072     elements_type elements;
0073 };
0074
0075 // nodes traits
0076
0077 template <typename Value, typename Parameters, typename Box, typename Allocators>
0078 struct node<Value, Parameters, Box, Allocators, node_variant_dynamic_tag>
0079 {
0080     typedef boost::variant<
0081         variant_leaf<Value, Parameters, Box, Allocators, node_variant_dynamic_tag>,
0082         variant_internal_node<Value, Parameters, Box, Allocators, node_variant_dynamic_tag>
0083     > type;
0084 };
0085
0086 template <typename Value, typename Parameters, typename Box, typename Allocators>
0087 struct internal_node<Value, Parameters, Box, Allocators, node_variant_dynamic_tag>
0088 {
0089     typedef variant_internal_node<Value, Parameters, Box, Allocators, node_variant_dynamic_tag> type;
0090 };
0091
0092 template <typename Value, typename Parameters, typename Box, typename Allocators>
0093 struct leaf<Value, Parameters, Box, Allocators, node_variant_dynamic_tag>
0094 {
0095     typedef variant_leaf<Value, Parameters, Box, Allocators, node_variant_dynamic_tag> type;
0096 };
0097
0098 // visitor traits
0099
0100 template <typename Value, typename Parameters, typename Box, typename Allocators, bool IsVisitableConst>
0101 struct visitor<Value, Parameters, Box, Allocators, node_variant_dynamic_tag, IsVisitableConst>
0102 {
0103     typedef static_visitor<> type;
0104 };
0105
0106 // allocators
0107
0108 template <typename Allocator, typename Value, typename Parameters, typename Box, typename Tag>
0109 struct node_alloc
0110 {
0111     typedef typename node
0112         <
0113             Value, Parameters, Box,
0114             allocators<Allocator, Value, Parameters, Box, Tag>,
0115             Tag
0116         >::type node_type;
0117
0118     typedef typename boost::container::allocator_traits
0119         <
0120             Allocator
0121         >::template rebind_alloc<node_type> type;
0122
0123     typedef boost::container::allocator_traits<type> traits;
0124 };
0125
0126
0127 template <typename Allocator, typename Value, typename Parameters, typename Box>
0128 class allocators<Allocator, Value, Parameters, Box, node_variant_dynamic_tag>
0129     : public detail::rtree::node_alloc
0130         <
0131             Allocator, Value, Parameters, Box, node_variant_dynamic_tag
0132         >::type
0133 {
0134     typedef detail::rtree::node_alloc
0135         <
0136             Allocator, Value, Parameters, Box, node_variant_dynamic_tag
0137         > node_alloc;
0138
0139 public:
0140     typedef typename node_alloc::type node_allocator_type;
0141     typedef typename node_alloc::traits::pointer node_pointer;
0142
0143 private:
0144     typedef typename boost::container::allocator_traits
0145         <
0146             node_allocator_type // node_allocator_type for consistency with variant_leaf
0147         >::template rebind_alloc<Value> value_allocator_type;
0148     typedef boost::container::allocator_traits<value_allocator_type> value_allocator_traits;
0149
0150
0151 public:
0152     typedef Allocator allocator_type;
0153
0154     typedef Value value_type;
0155     typedef typename value_allocator_traits::reference reference;
0156     typedef typename value_allocator_traits::const_reference const_reference;
0157     typedef typename value_allocator_traits::size_type size_type;
0158     typedef typename value_allocator_traits::difference_type difference_type;
0159     typedef typename value_allocator_traits::pointer pointer;
0160     typedef typename value_allocator_traits::const_pointer const_pointer;
0161
0162     inline allocators()
0163         : node_allocator_type()
0164     {}
0165
0166     template <typename Alloc>
0167     inline explicit allocators(Alloc const& alloc)
0168         : node_allocator_type(alloc)
0169     {}
0170
0171     inline allocators(allocators&& a)
0172         : node_allocator_type(std::move(a.node_allocator()))
0173     {}
0174
0175     inline allocators & operator=(allocators&& a)
0176     {
0177         node_allocator() = std::move(a.node_allocator());
0178         return *this;
0179     }
0180
0181     inline allocators & operator=(allocators const& a)
0182     {
0183         node_allocator() = a.node_allocator();
0184         return *this;
0185     }
0186
0187     void swap(allocators & a)
0188     {
0189         boost::core::invoke_swap(node_allocator(), a.node_allocator());
0190     }
0191
0192     bool operator==(allocators const& a) const { return node_allocator() == a.node_allocator(); }
0193     template <typename Alloc>
0194     bool operator==(Alloc const& a) const { return node_allocator() == node_allocator_type(a); }
0195
0196     Allocator allocator() const { return Allocator(node_allocator()); }
0197
0198     node_allocator_type & node_allocator() { return *this; }
0199     node_allocator_type const& node_allocator() const { return *this; }
0200 };
0201
0202 // create_node_variant
0203
0204 template <typename VariantPtr, typename Node>
0205 struct create_variant_node
0206 {
0207     template <typename AllocNode>
0208     static inline VariantPtr apply(AllocNode & alloc_node)
0209     {
0210         typedef boost::container::allocator_traits<AllocNode> Al;
0211         typedef typename Al::pointer P;
0212
0213         P p = Al::allocate(alloc_node, 1);
0214
0215         if ( 0 == p )
0216             throw_runtime_error("boost::geometry::index::rtree node creation failed");
0217
0218         scoped_deallocator<AllocNode> deallocator(p, alloc_node);
0219
0220         Al::construct(alloc_node, boost::to_address(p), Node(alloc_node)); // implicit cast to Variant
0221
0222         deallocator.release();
0223         return p;
0224     }
0225 };
0226
0227 // destroy_node_variant
0228
0229 template <typename Node>
0230 struct destroy_variant_node
0231 {
0232     template <typename AllocNode, typename VariantPtr>
0233     static inline void apply(AllocNode & alloc_node, VariantPtr n)
0234     {
0235         typedef boost::container::allocator_traits<AllocNode> Al;
0236
0237         Al::destroy(alloc_node, boost::addressof(*n));
0238         Al::deallocate(alloc_node, n, 1);
0239     }
0240 };
0241
0242 // create_node
0243
0244 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag>
0245 struct create_node<
0246     Allocators,
0247     variant_internal_node<Value, Parameters, Box, Allocators, Tag>
0248 >
0249 {
0250     static inline typename Allocators::node_pointer
0251     apply(Allocators & allocators)
0252     {
0253         return create_variant_node<
0254             typename Allocators::node_pointer,
0255             variant_internal_node<Value, Parameters, Box, Allocators, Tag>
0256         >::apply(allocators.node_allocator());
0257     }
0258 };
0259
0260 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag>
0261 struct create_node<
0262     Allocators,
0263     variant_leaf<Value, Parameters, Box, Allocators, Tag>
0264 >
0265 {
0266     static inline typename Allocators::node_pointer
0267     apply(Allocators & allocators)
0268     {
0269         return create_variant_node<
0270             typename Allocators::node_pointer,
0271             variant_leaf<Value, Parameters, Box, Allocators, Tag>
0272         >::apply(allocators.node_allocator());
0273     }
0274 };
0275
0276 // destroy_node
0277
0278 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag>
0279 struct destroy_node<
0280     Allocators,
0281     variant_internal_node<Value, Parameters, Box, Allocators, Tag>
0282 >
0283 {
0284     static inline void apply(Allocators & allocators, typename Allocators::node_pointer n)
0285     {
0286         destroy_variant_node<
0287             variant_internal_node<Value, Parameters, Box, Allocators, Tag>
0288         >::apply(allocators.node_allocator(), n);
0289     }
0290 };
0291
0292 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag>
0293 struct destroy_node<
0294     Allocators,
0295     variant_leaf<Value, Parameters, Box, Allocators, Tag>
0296 >
0297 {
0298     static inline void apply(Allocators & allocators, typename Allocators::node_pointer n)
0299     {
0300         destroy_variant_node<
0301             variant_leaf<Value, Parameters, Box, Allocators, Tag>
0302         >::apply(allocators.node_allocator(), n);
0303     }
0304 };
0305
0306 }} // namespace detail::rtree
0307
0308 }}} // namespace boost::geometry::index
0309
0310 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_VARIANT_DYNAMIC_HPP