1 // Boost.Geometry Index 2 // 3 // R-tree nodes based on static conversion, storing dynamic-size containers 4 // 5 // Copyright (c) 2011-2018 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_WEAK_DYNAMIC_HPP 12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_WEAK_DYNAMIC_HPP 13 14 namespace boost { namespace geometry { namespace index { 15 16 namespace detail { namespace rtree { 17 18 template <typename Value, typename Parameters, typename Box, typename Allocators, typename Tag> 19 struct weak_internal_node 20 : public weak_node<Value, Parameters, Box, Allocators, Tag> 21 { 22 typedef rtree::ptr_pair<Box, typename Allocators::node_pointer> element_type; 23 typedef typename boost::container::allocator_traits 24 < 25 typename Allocators::internal_node_allocator_type 26 >::template rebind_alloc<element_type> allocator_type; 27 28 typedef boost::container::vector<element_type, allocator_type> elements_type; 29 30 template <typename Al> weak_internal_nodeboost::geometry::index::detail::rtree::weak_internal_node31 inline weak_internal_node(Al const& al) 32 : elements(allocator_type(al)) 33 {} 34 35 elements_type elements; 36 }; 37 38 template <typename Value, typename Parameters, typename Box, typename Allocators, typename Tag> 39 struct weak_leaf 40 : public weak_node<Value, Parameters, Box, Allocators, Tag> 41 { 42 typedef typename boost::container::allocator_traits 43 < 44 typename Allocators::leaf_allocator_type 45 >::template rebind_alloc<Value> allocator_type; 46 47 typedef boost::container::vector<Value, allocator_type> elements_type; 48 49 template <typename Al> weak_leafboost::geometry::index::detail::rtree::weak_leaf50 inline weak_leaf(Al const& al) 51 : elements(allocator_type(al)) 52 {} 53 54 elements_type elements; 55 }; 56 57 // nodes traits 58 59 template <typename Value, typename Parameters, typename Box, typename Allocators> 60 struct node<Value, Parameters, Box, Allocators, node_weak_dynamic_tag> 61 { 62 typedef weak_node<Value, Parameters, Box, Allocators, node_weak_dynamic_tag> type; 63 }; 64 65 template <typename Value, typename Parameters, typename Box, typename Allocators> 66 struct internal_node<Value, Parameters, Box, Allocators, node_weak_dynamic_tag> 67 { 68 typedef weak_internal_node<Value, Parameters, Box, Allocators, node_weak_dynamic_tag> type; 69 }; 70 71 template <typename Value, typename Parameters, typename Box, typename Allocators> 72 struct leaf<Value, Parameters, Box, Allocators, node_weak_dynamic_tag> 73 { 74 typedef weak_leaf<Value, Parameters, Box, Allocators, node_weak_dynamic_tag> type; 75 }; 76 77 // visitor traits 78 79 template <typename Value, typename Parameters, typename Box, typename Allocators, bool IsVisitableConst> 80 struct visitor<Value, Parameters, Box, Allocators, node_weak_dynamic_tag, IsVisitableConst> 81 { 82 typedef weak_visitor<Value, Parameters, Box, Allocators, node_weak_dynamic_tag, IsVisitableConst> type; 83 }; 84 85 // allocators 86 87 template <typename Allocator, typename Value, typename Parameters, typename Box, typename Tag> 88 struct internal_node_alloc 89 { 90 typedef typename internal_nod 91 < 92 Value, Parameters, Box, 93 allocators<Allocator, Value, Parameters, Box, Tag>, 94 Tag 95 >::type node_type; 96 97 typedef typename boost::container::allocator_traits 98 < 99 Allocator 100 >::template rebind_alloc<node_type> type; 101 }; 102 103 template <typename Allocator, typename Value, typename Parameters, typename Box, typename Tag> 104 struct leaf_alloc 105 { 106 typedef typename leaf 107 < 108 Value, Parameters, Box, 109 allocators<Allocator, Value, Parameters, Box, Tag>, 110 Tag 111 >::type node_type; 112 113 typedef typename ::boost::container::allocator_traits 114 < 115 Allocator 116 >::template rebind_alloc<node_type> type; 117 }; 118 119 template <typename Allocator, typename Value, typename Parameters, typename Box> 120 class allocators<Allocator, Value, Parameters, Box, node_weak_dynamic_tag> 121 : public internal_node_alloc<Allocator, Value, Parameters, Box, node_weak_dynamic_tag>::type 122 , public leaf_alloc<Allocator, Value, Parameters, Box, node_weak_dynamic_tag>::type 123 { 124 typedef detail::rtree::internal_node_alloc 125 < 126 Allocator, Value, Parameters, Box, node_weak_dynamic_tag 127 > internal_node_alloc; 128 129 typedef detail::rtree::leaf_alloc 130 < 131 Allocator, Value, Parameters, Box, node_weak_dynamic_tag 132 > leaf_alloc; 133 134 typedef detail::rtree::node_alloc 135 < 136 Allocator, Value, Parameters, Box, node_weak_dynamic_tag 137 > node_alloc; 138 139 public: 140 typedef typename internal_node_alloc::type internal_node_allocator_type; 141 typedef typename leaf_alloc::type leaf_allocator_type; 142 typedef typename node_alloc::traits::pointer node_pointer; 143 144 private: 145 typedef typename boost::container::allocator_traits 146 < 147 leaf_allocator_type // leaf_allocator_type for consistency with weak_leaf 148 >::template rebind_alloc<Value> value_allocator_type; 149 typedef boost::container::allocator_traits<value_allocator_type> value_allocator_traits; 150 151 public: 152 typedef Allocator allocator_type; 153 154 typedef Value value_type; 155 typedef typename value_allocator_traits::reference reference; 156 typedef typename value_allocator_traits::const_reference const_reference; 157 typedef typename value_allocator_traits::size_type size_type; 158 typedef typename value_allocator_traits::difference_type difference_type; 159 typedef typename value_allocator_traits::pointer pointer; 160 typedef typename value_allocator_traits::const_pointer const_pointer; 161 allocators()162 inline allocators() 163 : internal_node_allocator_type() 164 , leaf_allocator_type() 165 {} 166 167 template <typename Alloc> allocators(Alloc const & alloc)168 inline explicit allocators(Alloc const& alloc) 169 : internal_node_allocator_type(alloc) 170 , leaf_allocator_type(alloc) 171 {} 172 allocators(BOOST_FWD_REF (allocators)a)173 inline allocators(BOOST_FWD_REF(allocators) a) 174 : internal_node_allocator_type(boost::move(a.internal_node_allocator())) 175 , leaf_allocator_type(boost::move(a.leaf_allocator())) 176 {} 177 operator =(BOOST_FWD_REF (allocators)a)178 inline allocators & operator=(BOOST_FWD_REF(allocators) a) 179 { 180 internal_node_allocator() = ::boost::move(a.internal_node_allocator()); 181 leaf_allocator() = ::boost::move(a.leaf_allocator()); 182 return *this; 183 } 184 185 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES operator =(allocators const & a)186 inline allocators & operator=(allocators const& a) 187 { 188 internal_node_allocator() = a.internal_node_allocator(); 189 leaf_allocator() = a.leaf_allocator(); 190 return *this; 191 } 192 #endif 193 swap(allocators & a)194 void swap(allocators & a) 195 { 196 boost::swap(internal_node_allocator(), a.internal_node_allocator()); 197 boost::swap(leaf_allocator(), a.leaf_allocator()); 198 } 199 operator ==(allocators const & a) const200 bool operator==(allocators const& a) const { return leaf_allocator() == a.leaf_allocator(); } 201 template <typename Alloc> operator ==(Alloc const & a) const202 bool operator==(Alloc const& a) const { return leaf_allocator() == leaf_allocator_type(a); } 203 allocator() const204 Allocator allocator() const { return Allocator(leaf_allocator()); } 205 internal_node_allocator()206 internal_node_allocator_type & internal_node_allocator() { return *this; } internal_node_allocator() const207 internal_node_allocator_type const& internal_node_allocator() const { return *this; } leaf_allocator()208 leaf_allocator_type & leaf_allocator() { return *this; } leaf_allocator() const209 leaf_allocator_type const& leaf_allocator() const { return *this; } 210 }; 211 212 // create_node_impl 213 214 template <typename BaseNodePtr, typename Node> 215 struct create_weak_node 216 { 217 template <typename AllocNode> applyboost::geometry::index::detail::rtree::create_weak_node218 static inline BaseNodePtr apply(AllocNode & alloc_node) 219 { 220 typedef boost::container::allocator_traits<AllocNode> Al; 221 typedef typename Al::pointer P; 222 223 P p = Al::allocate(alloc_node, 1); 224 225 if ( 0 == p ) 226 throw_runtime_error("boost::geometry::index::rtree node creation failed"); 227 228 scoped_deallocator<AllocNode> deallocator(p, alloc_node); 229 230 Al::construct(alloc_node, boost::to_address(p), alloc_node); 231 232 deallocator.release(); 233 return p; 234 } 235 }; 236 237 // destroy_node_impl 238 239 template <typename Node> 240 struct destroy_weak_node 241 { 242 template <typename AllocNode, typename BaseNodePtr> applyboost::geometry::index::detail::rtree::destroy_weak_node243 static inline void apply(AllocNode & alloc_node, BaseNodePtr n) 244 { 245 typedef boost::container::allocator_traits<AllocNode> Al; 246 typedef typename Al::pointer P; 247 248 P p(&static_cast<Node&>(rtree::get<Node>(*n))); 249 Al::destroy(alloc_node, boost::addressof(*p)); 250 Al::deallocate(alloc_node, p, 1); 251 } 252 }; 253 254 // create_node 255 256 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag> 257 struct create_node< 258 Allocators, 259 weak_internal_node<Value, Parameters, Box, Allocators, Tag> 260 > 261 { 262 static inline typename Allocators::node_pointer applyboost::geometry::index::detail::rtree::create_node263 apply(Allocators & allocators) 264 { 265 return create_weak_node< 266 typename Allocators::node_pointer, 267 weak_internal_node<Value, Parameters, Box, Allocators, Tag> 268 >::apply(allocators.internal_node_allocator()); 269 } 270 }; 271 272 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag> 273 struct create_node< 274 Allocators, 275 weak_leaf<Value, Parameters, Box, Allocators, Tag> 276 > 277 { 278 static inline typename Allocators::node_pointer applyboost::geometry::index::detail::rtree::create_node279 apply(Allocators & allocators) 280 { 281 return create_weak_node< 282 typename Allocators::node_pointer, 283 weak_leaf<Value, Parameters, Box, Allocators, Tag> 284 >::apply(allocators.leaf_allocator()); 285 } 286 }; 287 288 // destroy_node 289 290 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag> 291 struct destroy_node< 292 Allocators, 293 weak_internal_node<Value, Parameters, Box, Allocators, Tag> 294 > 295 { applyboost::geometry::index::detail::rtree::destroy_node296 static inline void apply(Allocators & allocators, typename Allocators::node_pointer n) 297 { 298 destroy_weak_node< 299 weak_internal_node<Value, Parameters, Box, Allocators, Tag> 300 >::apply(allocators.internal_node_allocator(), n); 301 } 302 }; 303 304 template <typename Allocators, typename Value, typename Parameters, typename Box, typename Tag> 305 struct destroy_node< 306 Allocators, 307 weak_leaf<Value, Parameters, Box, Allocators, Tag> 308 > 309 { applyboost::geometry::index::detail::rtree::destroy_node310 static inline void apply(Allocators & allocators, typename Allocators::node_pointer n) 311 { 312 destroy_weak_node< 313 weak_leaf<Value, Parameters, Box, Allocators, Tag> 314 >::apply(allocators.leaf_allocator(), n); 315 } 316 }; 317 318 }} // namespace detail::rtree 319 320 }}} // namespace boost::geometry::index 321 322 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_WEAK_DYNAMIC_HPP 323