1 // Boost.Geometry Index 2 // 3 // R-tree nodes storing static-size containers 4 // test version throwing exceptions on creation 5 // 6 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. 7 // 8 // Use, modification and distribution is subject to the Boost Software License, 9 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 10 // http://www.boost.org/LICENSE_1_0.txt) 11 12 #ifndef BOOST_GEOMETRY_INDEX_TEST_RTREE_THROWING_NODE_HPP 13 #define BOOST_GEOMETRY_INDEX_TEST_RTREE_THROWING_NODE_HPP 14 15 #include <rtree/exceptions/test_throwing.hpp> 16 17 struct throwing_nodes_stats 18 { reset_countersthrowing_nodes_stats19 static void reset_counters() { get_internal_nodes_counter_ref() = 0; get_leafs_counter_ref() = 0; } internal_nodes_countthrowing_nodes_stats20 static size_t internal_nodes_count() { return get_internal_nodes_counter_ref(); } leafs_countthrowing_nodes_stats21 static size_t leafs_count() { return get_leafs_counter_ref(); } 22 get_internal_nodes_counter_refthrowing_nodes_stats23 static size_t & get_internal_nodes_counter_ref() { static size_t cc = 0; return cc; } get_leafs_counter_refthrowing_nodes_stats24 static size_t & get_leafs_counter_ref() { static size_t cc = 0; return cc; } 25 }; 26 27 namespace boost { namespace geometry { namespace index { 28 29 template <size_t MaxElements, size_t MinElements> 30 struct linear_throwing : public linear<MaxElements, MinElements> {}; 31 32 template <size_t MaxElements, size_t MinElements> 33 struct quadratic_throwing : public quadratic<MaxElements, MinElements> {}; 34 35 template <size_t MaxElements, size_t MinElements, size_t OverlapCostThreshold = 0, size_t ReinsertedElements = detail::default_rstar_reinserted_elements_s<MaxElements>::value> 36 struct rstar_throwing : public rstar<MaxElements, MinElements, OverlapCostThreshold, ReinsertedElements> {}; 37 38 namespace detail { namespace rtree { 39 40 // options implementation (from options.hpp) 41 42 struct node_throwing_static_tag {}; 43 44 template <size_t MaxElements, size_t MinElements> 45 struct options_type< linear_throwing<MaxElements, MinElements> > 46 { 47 typedef options< 48 linear_throwing<MaxElements, MinElements>, 49 insert_default_tag, choose_by_content_diff_tag, split_default_tag, linear_tag, 50 node_throwing_static_tag 51 > type; 52 }; 53 54 template <size_t MaxElements, size_t MinElements> 55 struct options_type< quadratic_throwing<MaxElements, MinElements> > 56 { 57 typedef options< 58 quadratic_throwing<MaxElements, MinElements>, 59 insert_default_tag, choose_by_content_diff_tag, split_default_tag, quadratic_tag, 60 node_throwing_static_tag 61 > type; 62 }; 63 64 template <size_t MaxElements, size_t MinElements, size_t OverlapCostThreshold, size_t ReinsertedElements> 65 struct options_type< rstar_throwing<MaxElements, MinElements, OverlapCostThreshold, ReinsertedElements> > 66 { 67 typedef options< 68 rstar_throwing<MaxElements, MinElements, OverlapCostThreshold, ReinsertedElements>, 69 insert_reinsert_tag, choose_by_overlap_diff_tag, split_default_tag, rstar_tag, 70 node_throwing_static_tag 71 > type; 72 }; 73 74 }} // namespace detail::rtree 75 76 // node implementation 77 78 namespace detail { namespace rtree { 79 80 template <typename Value, typename Parameters, typename Box, typename Allocators> 81 struct variant_internal_node<Value, Parameters, Box, Allocators, node_throwing_static_tag> 82 { 83 typedef throwing_varray< 84 rtree::ptr_pair<Box, typename Allocators::node_pointer>, 85 Parameters::max_elements + 1 86 > elements_type; 87 88 template <typename Alloc> variant_internal_nodeboost::geometry::index::detail::rtree::variant_internal_node89 inline variant_internal_node(Alloc const&) { throwing_nodes_stats::get_internal_nodes_counter_ref()++; } ~variant_internal_nodeboost::geometry::index::detail::rtree::variant_internal_node90 inline ~variant_internal_node() { throwing_nodes_stats::get_internal_nodes_counter_ref()--; } 91 92 // required because variants are initialized using node object 93 // temporary must be taken into account variant_internal_nodeboost::geometry::index::detail::rtree::variant_internal_node94 inline variant_internal_node(variant_internal_node const& n) 95 : elements(n.elements) 96 { 97 throwing_nodes_stats::get_internal_nodes_counter_ref()++; 98 } 99 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES variant_internal_nodeboost::geometry::index::detail::rtree::variant_internal_node100 inline variant_internal_node(variant_internal_node && n) 101 : elements(boost::move(n.elements)) 102 { 103 throwing_nodes_stats::get_internal_nodes_counter_ref()++; 104 } 105 #endif 106 107 elements_type elements; 108 109 private: 110 variant_internal_node & operator=(variant_internal_node const& n); 111 }; 112 113 template <typename Value, typename Parameters, typename Box, typename Allocators> 114 struct variant_leaf<Value, Parameters, Box, Allocators, node_throwing_static_tag> 115 { 116 typedef throwing_varray<Value, Parameters::max_elements + 1> elements_type; 117 118 template <typename Alloc> variant_leafboost::geometry::index::detail::rtree::variant_leaf119 inline variant_leaf(Alloc const&) { throwing_nodes_stats::get_leafs_counter_ref()++; } ~variant_leafboost::geometry::index::detail::rtree::variant_leaf120 inline ~variant_leaf() { throwing_nodes_stats::get_leafs_counter_ref()--; } 121 122 // required because variants are initialized using node object 123 // temporary must be taken into account variant_leafboost::geometry::index::detail::rtree::variant_leaf124 inline variant_leaf(variant_leaf const& n) 125 : elements(n.elements) 126 { 127 throwing_nodes_stats::get_leafs_counter_ref()++; 128 } 129 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES variant_leafboost::geometry::index::detail::rtree::variant_leaf130 inline variant_leaf(variant_leaf && n) 131 : elements(boost::move(n.elements)) 132 { 133 throwing_nodes_stats::get_leafs_counter_ref()++; 134 } 135 #endif 136 137 elements_type elements; 138 139 private: 140 variant_leaf & operator=(variant_leaf const& n); 141 }; 142 143 // nodes traits 144 145 template <typename Value, typename Parameters, typename Box, typename Allocators> 146 struct node<Value, Parameters, Box, Allocators, node_throwing_static_tag> 147 { 148 typedef boost::variant< 149 variant_leaf<Value, Parameters, Box, Allocators, node_throwing_static_tag>, 150 variant_internal_node<Value, Parameters, Box, Allocators, node_throwing_static_tag> 151 > type; 152 }; 153 154 template <typename Value, typename Parameters, typename Box, typename Allocators> 155 struct internal_node<Value, Parameters, Box, Allocators, node_throwing_static_tag> 156 { 157 typedef variant_internal_node<Value, Parameters, Box, Allocators, node_throwing_static_tag> type; 158 }; 159 160 template <typename Value, typename Parameters, typename Box, typename Allocators> 161 struct leaf<Value, Parameters, Box, Allocators, node_throwing_static_tag> 162 { 163 typedef variant_leaf<Value, Parameters, Box, Allocators, node_throwing_static_tag> type; 164 }; 165 166 // visitor traits 167 168 template <typename Value, typename Parameters, typename Box, typename Allocators, bool IsVisitableConst> 169 struct visitor<Value, Parameters, Box, Allocators, node_throwing_static_tag, IsVisitableConst> 170 { 171 typedef static_visitor<> type; 172 }; 173 174 // allocators 175 176 template <typename Allocator, typename Value, typename Parameters, typename Box> 177 class allocators<Allocator, Value, Parameters, Box, node_throwing_static_tag> 178 : public Allocator::template rebind< 179 typename node< 180 Value, Parameters, Box, 181 allocators<Allocator, Value, Parameters, Box, node_throwing_static_tag>, 182 node_throwing_static_tag 183 >::type 184 >::other 185 { 186 typedef typename Allocator::template rebind< 187 Value 188 >::other value_allocator_type; 189 190 public: 191 typedef Allocator allocator_type; 192 193 typedef Value value_type; 194 typedef value_type & reference; 195 typedef const value_type & const_reference; 196 typedef typename value_allocator_type::size_type size_type; 197 typedef typename value_allocator_type::difference_type difference_type; 198 typedef typename value_allocator_type::pointer pointer; 199 typedef typename value_allocator_type::const_pointer const_pointer; 200 201 typedef typename Allocator::template rebind< 202 typename node<Value, Parameters, Box, allocators, node_throwing_static_tag>::type 203 >::other::pointer node_pointer; 204 205 // typedef typename Allocator::template rebind< 206 // typename internal_node<Value, Parameters, Box, allocators, node_throwing_static_tag>::type 207 // >::other::pointer internal_node_pointer; 208 209 typedef typename Allocator::template rebind< 210 typename node<Value, Parameters, Box, allocators, node_throwing_static_tag>::type 211 >::other node_allocator_type; 212 allocators()213 inline allocators() 214 : node_allocator_type() 215 {} 216 217 template <typename Alloc> allocators(Alloc const & alloc)218 inline explicit allocators(Alloc const& alloc) 219 : node_allocator_type(alloc) 220 {} 221 allocators(BOOST_FWD_REF (allocators)a)222 inline allocators(BOOST_FWD_REF(allocators) a) 223 : node_allocator_type(boost::move(a.node_allocator())) 224 {} 225 operator =(BOOST_FWD_REF (allocators)a)226 inline allocators & operator=(BOOST_FWD_REF(allocators) a) 227 { 228 node_allocator() = boost::move(a.node_allocator()); 229 return *this; 230 } 231 232 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES operator =(allocators const & a)233 inline allocators & operator=(allocators const& a) 234 { 235 node_allocator() = a.node_allocator(); 236 return *this; 237 } 238 #endif 239 swap(allocators & a)240 void swap(allocators & a) 241 { 242 boost::swap(node_allocator(), a.node_allocator()); 243 } 244 operator ==(allocators const & a) const245 bool operator==(allocators const& a) const { return node_allocator() == a.node_allocator(); } 246 template <typename Alloc> operator ==(Alloc const & a) const247 bool operator==(Alloc const& a) const { return node_allocator() == node_allocator_type(a); } 248 allocator() const249 Allocator allocator() const { return Allocator(node_allocator()); } 250 node_allocator()251 node_allocator_type & node_allocator() { return *this; } node_allocator() const252 node_allocator_type const& node_allocator() const { return *this; } 253 }; 254 255 struct node_bad_alloc : public std::exception 256 { whatboost::geometry::index::detail::rtree::node_bad_alloc257 const char * what() const throw() { return "internal node creation failed."; } 258 }; 259 260 struct throwing_node_settings 261 { throw_if_requiredboost::geometry::index::detail::rtree::throwing_node_settings262 static void throw_if_required() 263 { 264 // throw if counter meets max count 265 if ( get_max_calls_ref() <= get_calls_counter_ref() ) 266 throw node_bad_alloc(); 267 else 268 ++get_calls_counter_ref(); 269 } 270 reset_calls_counterboost::geometry::index::detail::rtree::throwing_node_settings271 static void reset_calls_counter() { get_calls_counter_ref() = 0; } set_max_callsboost::geometry::index::detail::rtree::throwing_node_settings272 static void set_max_calls(size_t mc) { get_max_calls_ref() = mc; } 273 get_calls_counter_refboost::geometry::index::detail::rtree::throwing_node_settings274 static size_t & get_calls_counter_ref() { static size_t cc = 0; return cc; } get_max_calls_refboost::geometry::index::detail::rtree::throwing_node_settings275 static size_t & get_max_calls_ref() { static size_t mc = (std::numeric_limits<size_t>::max)(); return mc; } 276 }; 277 278 // create_node 279 280 template <typename Allocators, typename Value, typename Parameters, typename Box> 281 struct create_node< 282 Allocators, 283 variant_internal_node<Value, Parameters, Box, Allocators, node_throwing_static_tag> 284 > 285 { 286 static inline typename Allocators::node_pointer applyboost::geometry::index::detail::rtree::create_node287 apply(Allocators & allocators) 288 { 289 // throw if counter meets max count 290 throwing_node_settings::throw_if_required(); 291 292 return create_variant_node< 293 typename Allocators::node_pointer, 294 variant_internal_node<Value, Parameters, Box, Allocators, node_throwing_static_tag> 295 >::apply(allocators.node_allocator()); 296 } 297 }; 298 299 template <typename Allocators, typename Value, typename Parameters, typename Box> 300 struct create_node< 301 Allocators, 302 variant_leaf<Value, Parameters, Box, Allocators, node_throwing_static_tag> 303 > 304 { 305 static inline typename Allocators::node_pointer applyboost::geometry::index::detail::rtree::create_node306 apply(Allocators & allocators) 307 { 308 // throw if counter meets max count 309 throwing_node_settings::throw_if_required(); 310 311 return create_variant_node< 312 typename Allocators::node_pointer, 313 variant_leaf<Value, Parameters, Box, Allocators, node_throwing_static_tag> 314 >::apply(allocators.node_allocator()); 315 } 316 }; 317 318 }} // namespace detail::rtree 319 320 }}} // namespace boost::geometry::index 321 322 #endif // BOOST_GEOMETRY_INDEX_TEST_RTREE_THROWING_NODE_HPP 323