1 // Boost.Geometry Index
2 //
3 // R-tree nodes based on Boost.Variant, storing dynamic-size containers
4 //
5 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
6 //
7 // Use, modification and distribution is subject to the Boost Software License,
8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 
11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_VARIANT_DYNAMIC_HPP
12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_VARIANT_DYNAMIC_HPP
13 
14 #include <boost/core/pointer_traits.hpp>
15 
16 namespace boost { namespace geometry { namespace index {
17 
18 namespace detail { namespace rtree {
19 
20 // nodes default types
21 
22 template <typename Value, typename Parameters, typename Box, typename Allocators, typename Tag>
23 struct variant_internal_node
24 {
25     typedef boost::container::vector
26         <
27             rtree::ptr_pair<Box, typename Allocators::node_pointer>,
28             typename Allocators::node_allocator_type::template rebind
29                 <
30                     rtree::ptr_pair<Box, typename Allocators::node_pointer>
31                 >::other
32         > elements_type;
33 
34     template <typename Al>
variant_internal_nodeboost::geometry::index::detail::rtree::variant_internal_node35     inline variant_internal_node(Al const& al)
36         : elements(al)
37     {}
38 
39     elements_type elements;
40 };
41 
42 template <typename Value, typename Parameters, typename Box, typename Allocators, typename Tag>
43 struct variant_leaf
44 {
45     typedef boost::container::vector
46         <
47             Value,
48             typename Allocators::node_allocator_type::template rebind
49                 <
50                     Value
51                 >::other
52         > elements_type;
53 
54      template <typename Al>
variant_leafboost::geometry::index::detail::rtree::variant_leaf55     inline variant_leaf(Al const& al)
56         : elements(al)
57     {}
58 
59     elements_type elements;
60 };
61 
62 // nodes traits
63 
64 template <typename Value, typename Parameters, typename Box, typename Allocators>
65 struct node<Value, Parameters, Box, Allocators, node_variant_dynamic_tag>
66 {
67     typedef boost::variant<
68         variant_leaf<Value, Parameters, Box, Allocators, node_variant_dynamic_tag>,
69         variant_internal_node<Value, Parameters, Box, Allocators, node_variant_dynamic_tag>
70     > type;
71 };
72 
73 template <typename Value, typename Parameters, typename Box, typename Allocators>
74 struct internal_node<Value, Parameters, Box, Allocators, node_variant_dynamic_tag>
75 {
76     typedef variant_internal_node<Value, Parameters, Box, Allocators, node_variant_dynamic_tag> type;
77 };
78 
79 template <typename Value, typename Parameters, typename Box, typename Allocators>
80 struct leaf<Value, Parameters, Box, Allocators, node_variant_dynamic_tag>
81 {
82     typedef variant_leaf<Value, Parameters, Box, Allocators, node_variant_dynamic_tag> type;
83 };
84 
85 // visitor traits
86 
87 template <typename Value, typename Parameters, typename Box, typename Allocators, bool IsVisitableConst>
88 struct visitor<Value, Parameters, Box, Allocators, node_variant_dynamic_tag, IsVisitableConst>
89 {
90     typedef static_visitor<> type;
91 };
92 
93 // allocators
94 
95 template <typename Allocator, typename Value, typename Parameters, typename Box>
96 class allocators<Allocator, Value, Parameters, Box, node_variant_dynamic_tag>
97     : public Allocator::template rebind<
98         typename node<
99             Value, Parameters, Box,
100             allocators<Allocator, Value, Parameters, Box, node_variant_dynamic_tag>,
101             node_variant_dynamic_tag
102         >::type
103     >::other
104 {
105     typedef typename Allocator::template rebind<
106         Value
107     >::other value_allocator_type;
108 
109 public:
110     typedef Allocator allocator_type;
111 
112     typedef Value value_type;
113     typedef typename value_allocator_type::reference reference;
114     typedef typename value_allocator_type::const_reference const_reference;
115     typedef typename value_allocator_type::size_type size_type;
116     typedef typename value_allocator_type::difference_type difference_type;
117     typedef typename value_allocator_type::pointer pointer;
118     typedef typename value_allocator_type::const_pointer const_pointer;
119 
120     typedef typename Allocator::template rebind<
121         typename node<Value, Parameters, Box, allocators, node_variant_dynamic_tag>::type
122     >::other::pointer node_pointer;
123 
124     typedef typename Allocator::template rebind<
125         typename node<Value, Parameters, Box, allocators, node_variant_dynamic_tag>::type
126     >::other node_allocator_type;
127 
allocators()128     inline allocators()
129         : node_allocator_type()
130     {}
131 
132     template <typename Alloc>
allocators(Alloc const & alloc)133     inline explicit allocators(Alloc const& alloc)
134         : node_allocator_type(alloc)
135     {}
136 
allocators(BOOST_FWD_REF (allocators)a)137     inline allocators(BOOST_FWD_REF(allocators) a)
138         : node_allocator_type(boost::move(a.node_allocator()))
139     {}
140 
operator =(BOOST_FWD_REF (allocators)a)141     inline allocators & operator=(BOOST_FWD_REF(allocators) a)
142     {
143         node_allocator() = boost::move(a.node_allocator());
144         return *this;
145     }
146 
147 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
operator =(allocators const & a)148     inline allocators & operator=(allocators const& a)
149     {
150         node_allocator() = a.node_allocator();
151         return *this;
152     }
153 #endif
154 
swap(allocators & a)155     void swap(allocators & a)
156     {
157         boost::swap(node_allocator(), a.node_allocator());
158     }
159 
operator ==(allocators const & a) const160     bool operator==(allocators const& a) const { return node_allocator() == a.node_allocator(); }
161     template <typename Alloc>
operator ==(Alloc const & a) const162     bool operator==(Alloc const& a) const { return node_allocator() == node_allocator_type(a); }
163 
allocator() const164     Allocator allocator() const { return Allocator(node_allocator()); }
165 
node_allocator()166     node_allocator_type & node_allocator() { return *this; }
node_allocator() const167     node_allocator_type const& node_allocator() const { return *this; }
168 };
169 
170 // create_node_variant
171 
172 template <typename VariantPtr, typename Node>
173 struct create_variant_node
174 {
175     template <typename AllocNode>
applyboost::geometry::index::detail::rtree::create_variant_node176     static inline VariantPtr apply(AllocNode & alloc_node)
177     {
178         typedef boost::container::allocator_traits<AllocNode> Al;
179         typedef typename Al::pointer P;
180 
181         P p = Al::allocate(alloc_node, 1);
182 
183         if ( 0 == p )
184             throw_runtime_error("boost::geometry::index::rtree node creation failed");
185 
186         scoped_deallocator<AllocNode> deallocator(p, alloc_node);
187 
188         Al::construct(alloc_node, boost::pointer_traits<P>::to_address(p), Node(alloc_node)); // implicit cast to Variant
189 
190         deallocator.release();
191         return p;
192     }
193 };
194 
195 // destroy_node_variant
196 
197 template <typename Node>
198 struct destroy_variant_node
199 {
200     template <typename AllocNode, typename VariantPtr>
applyboost::geometry::index::detail::rtree::destroy_variant_node201     static inline void apply(AllocNode & alloc_node, VariantPtr n)
202     {
203         typedef boost::container::allocator_traits<AllocNode> Al;
204 
205         Al::destroy(alloc_node, boost::addressof(*n));
206         Al::deallocate(alloc_node, n, 1);
207     }
208 };
209 
210 // create_node
211 
212 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag>
213 struct create_node<
214     Allocators,
215     variant_internal_node<Value, Parameters, Box, Allocators, Tag>
216 >
217 {
218     static inline typename Allocators::node_pointer
applyboost::geometry::index::detail::rtree::create_node219     apply(Allocators & allocators)
220     {
221         return create_variant_node<
222             typename Allocators::node_pointer,
223             variant_internal_node<Value, Parameters, Box, Allocators, Tag>
224         >::apply(allocators.node_allocator());
225     }
226 };
227 
228 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag>
229 struct create_node<
230     Allocators,
231     variant_leaf<Value, Parameters, Box, Allocators, Tag>
232 >
233 {
234     static inline typename Allocators::node_pointer
applyboost::geometry::index::detail::rtree::create_node235     apply(Allocators & allocators)
236     {
237         return create_variant_node<
238             typename Allocators::node_pointer,
239             variant_leaf<Value, Parameters, Box, Allocators, Tag>
240         >::apply(allocators.node_allocator());
241     }
242 };
243 
244 // destroy_node
245 
246 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag>
247 struct destroy_node<
248     Allocators,
249     variant_internal_node<Value, Parameters, Box, Allocators, Tag>
250 >
251 {
applyboost::geometry::index::detail::rtree::destroy_node252     static inline void apply(Allocators & allocators, typename Allocators::node_pointer n)
253     {
254         destroy_variant_node<
255             variant_internal_node<Value, Parameters, Box, Allocators, Tag>
256         >::apply(allocators.node_allocator(), n);
257     }
258 };
259 
260 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag>
261 struct destroy_node<
262     Allocators,
263     variant_leaf<Value, Parameters, Box, Allocators, Tag>
264 >
265 {
applyboost::geometry::index::detail::rtree::destroy_node266     static inline void apply(Allocators & allocators, typename Allocators::node_pointer n)
267     {
268         destroy_variant_node<
269             variant_leaf<Value, Parameters, Box, Allocators, Tag>
270         >::apply(allocators.node_allocator(), n);
271     }
272 };
273 
274 }} // namespace detail::rtree
275 
276 }}} // namespace boost::geometry::index
277 
278 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_VARIANT_DYNAMIC_HPP
279