1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2013-2013 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 // 9 // See http://www.boost.org/libs/container for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 13 #ifndef BOOST_CONTAINER_OPTIONS_HPP 14 #define BOOST_CONTAINER_OPTIONS_HPP 15 16 #ifndef BOOST_CONFIG_HPP 17 # include <boost/config.hpp> 18 #endif 19 20 #if defined(BOOST_HAS_PRAGMA_ONCE) 21 # pragma once 22 #endif 23 24 #include <boost/container/detail/config_begin.hpp> 25 #include <boost/container/container_fwd.hpp> 26 #include <boost/intrusive/pack_options.hpp> 27 #include <boost/static_assert.hpp> 28 29 namespace boost { 30 namespace container { 31 32 //////////////////////////////////////////////////////////////// 33 // 34 // 35 // OPTIONS FOR ASSOCIATIVE TREE-BASED CONTAINERS 36 // 37 // 38 //////////////////////////////////////////////////////////////// 39 40 //! Enumeration used to configure ordered associative containers 41 //! with a concrete tree implementation. 42 enum tree_type_enum 43 { 44 red_black_tree, 45 avl_tree, 46 scapegoat_tree, 47 splay_tree 48 }; 49 50 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 51 52 template<tree_type_enum TreeType, bool OptimizeSize> 53 struct tree_opt 54 { 55 static const boost::container::tree_type_enum tree_type = TreeType; 56 static const bool optimize_size = OptimizeSize; 57 }; 58 59 typedef tree_opt<red_black_tree, true> tree_assoc_defaults; 60 61 #endif //!defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 62 63 //!This option setter specifies the underlying tree type 64 //!(red-black, AVL, Scapegoat or Splay) for ordered associative containers 65 BOOST_INTRUSIVE_OPTION_CONSTANT(tree_type, tree_type_enum, TreeType, tree_type) 66 67 //!This option setter specifies if node size is optimized 68 //!storing rebalancing data masked into pointers for ordered associative containers 69 BOOST_INTRUSIVE_OPTION_CONSTANT(optimize_size, bool, Enabled, optimize_size) 70 71 //! Helper metafunction to combine options into a single type to be used 72 //! by \c boost::container::set, \c boost::container::multiset 73 //! \c boost::container::map and \c boost::container::multimap. 74 //! Supported options are: \c boost::container::optimize_size and \c boost::container::tree_type 75 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) || defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 76 template<class ...Options> 77 #else 78 template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> 79 #endif 80 struct tree_assoc_options 81 { 82 /// @cond 83 typedef typename ::boost::intrusive::pack_options 84 < tree_assoc_defaults, 85 #if !defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 86 O1, O2, O3, O4 87 #else 88 Options... 89 #endif 90 >::type packed_options; 91 typedef tree_opt<packed_options::tree_type, packed_options::optimize_size> implementation_defined; 92 /// @endcond 93 typedef implementation_defined type; 94 }; 95 96 #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) 97 98 //! Helper alias metafunction to combine options into a single type to be used 99 //! by tree-based associative containers 100 template<class ...Options> 101 using tree_assoc_options_t = typename boost::container::tree_assoc_options<Options...>::type; 102 103 #endif 104 105 106 //////////////////////////////////////////////////////////////// 107 // 108 // 109 // OPTIONS FOR ASSOCIATIVE HASH-BASED CONTAINERS 110 // 111 // 112 //////////////////////////////////////////////////////////////// 113 114 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 115 116 template<bool StoreHash> 117 struct hash_opt 118 { 119 static const bool store_hash = StoreHash; 120 }; 121 122 typedef hash_opt<false> hash_assoc_defaults; 123 124 #endif //!defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 125 126 //!This option setter specifies if node size is optimized 127 //!storing rebalancing data masked into pointers for ordered associative containers 128 BOOST_INTRUSIVE_OPTION_CONSTANT(store_hash, bool, Enabled, store_hash) 129 130 //! Helper metafunction to combine options into a single type to be used 131 //! by \c boost::container::hash_set, \c boost::container::hash_multiset 132 //! \c boost::container::hash_map and \c boost::container::hash_multimap. 133 //! Supported options are: \c boost::container::store_hash 134 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) || defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 135 template<class ...Options> 136 #else 137 template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> 138 #endif 139 struct hash_assoc_options 140 { 141 /// @cond 142 typedef typename ::boost::intrusive::pack_options 143 < hash_assoc_defaults, 144 #if !defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 145 O1, O2, O3, O4 146 #else 147 Options... 148 #endif 149 >::type packed_options; 150 typedef hash_opt<packed_options::store_hash> implementation_defined; 151 /// @endcond 152 typedef implementation_defined type; 153 }; 154 155 #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) 156 157 //! Helper alias metafunction to combine options into a single type to be used 158 //! by hash-based associative containers 159 template<class ...Options> 160 using hash_assoc_options_t = typename boost::container::hash_assoc_options<Options...>::type; 161 162 #endif 163 164 //////////////////////////////////////////////////////////////// 165 // 166 // 167 // OPTIONS FOR VECTOR-BASED CONTAINERS 168 // 169 // 170 //////////////////////////////////////////////////////////////// 171 172 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 173 174 template<class T, class Default> 175 struct default_if_void 176 { 177 typedef T type; 178 }; 179 180 template<class Default> 181 struct default_if_void<void, Default> 182 { 183 typedef Default type; 184 }; 185 186 #endif 187 188 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 189 190 template<class AllocTraits, class StoredSizeType> 191 struct get_stored_size_type_with_alloctraits 192 { 193 typedef StoredSizeType type; 194 }; 195 196 template<class AllocTraits> 197 struct get_stored_size_type_with_alloctraits<AllocTraits, void> 198 { 199 typedef typename AllocTraits::size_type type; 200 }; 201 202 template<class GrowthType, class StoredSizeType> 203 struct vector_opt 204 { 205 typedef GrowthType growth_factor_type; 206 typedef StoredSizeType stored_size_type; 207 208 template<class AllocTraits> 209 struct get_stored_size_type 210 : get_stored_size_type_with_alloctraits<AllocTraits, StoredSizeType> 211 {}; 212 }; 213 214 class default_next_capacity; 215 216 typedef vector_opt<void, void> vector_null_opt; 217 218 template<class GrowthType, class StoredSizeType> 219 struct devector_opt 220 : vector_opt<GrowthType, StoredSizeType> 221 {}; 222 223 typedef devector_opt<void, void> devector_null_opt; 224 225 #else //!defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 226 227 //!This growth factor argument specifies that the container should increase it's 228 //!capacity a 50% when existing capacity is exhausted. 229 struct growth_factor_50{}; 230 231 //!This growth factor argument specifies that the container should increase it's 232 //!capacity a 60% when existing capacity is exhausted. 233 struct growth_factor_60{}; 234 235 //!This growth factor argument specifies that the container should increase it's 236 //!capacity a 100% (doubling its capacity) when existing capacity is exhausted. 237 struct growth_factor_100{}; 238 239 #endif //!defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 240 241 //!This option setter specifies the growth factor strategy of the underlying vector. 242 //! 243 //!\tparam GrowthFactor A function object that has the following signature:<br/><br/> 244 //!`template<class SizeType>`<br/> 245 //!`SizeType operator()(SizeType cur_cap, SizeType add_min_cap, SizeType max_cap) const;`.<br/><br/> 246 //!`cur_cap` is the current capacity, `add_min_cap` is the minimum additional capacity 247 //!we want to achieve and `max_cap` is the maximum capacity that the allocator or other 248 //!factors allow. The implementation should return a value between `cur_cap` + `add_min_cap` 249 //!and `max_cap`. `cur_cap` + `add_min_cap` is guaranteed not to overflow/wraparound, 250 //! but the implementation should handle wraparound produced by the growth factor. 251 //! 252 //!Predefined growth factors that can be passed as arguments to this option are: 253 //!\c boost::container::growth_factor_50 254 //!\c boost::container::growth_factor_60 255 //!\c boost::container::growth_factor_100 256 //! 257 //!If this option is not specified, a default will be used by the container. 258 BOOST_INTRUSIVE_OPTION_TYPE(growth_factor, GrowthFactor, GrowthFactor, growth_factor_type) 259 260 //!This option specifies the unsigned integer type that a user wants the container 261 //!to use to hold size-related information inside a container (e.g. current size, current capacity). 262 //! 263 //!\tparam StoredSizeType An unsigned integer type. It shall be smaller than than the size 264 //! of the size_type deduced from `allocator_traits<A>::size_type` or the same type. 265 //! 266 //!If the maximum capacity() to be used is limited, a user can try to use 8-bit, 16-bit 267 //!(e.g. in 32-bit machines), or 32-bit size types (e.g. in a 64 bit machine) to see if some 268 //!memory can be saved for empty vectors. This could potentially performance benefits due to better 269 //!cache usage. 270 //! 271 //!Note that alignment requirements can disallow theoretical space savings. Example: 272 //!\c vector holds a pointer and two size types (for size and capacity), in a 32 bit machine 273 //!a 8 bit size type (total size: 4 byte pointer + 2 x 1 byte sizes = 6 bytes) 274 //!will not save space when comparing two 16-bit size types because usually 275 //!a 32 bit alignment is required for vector and the size will be rounded to 8 bytes. In a 64-bit 276 //!machine a 16 bit size type does not usually save memory when comparing to a 32-bit size type. 277 //!Measure the size of the resulting container and do not assume a smaller \c stored_size 278 //!will always lead to a smaller sizeof(container). 279 //! 280 //!If a user tries to insert more elements than representable by \c stored_size, vector 281 //!will throw a length_error. 282 //! 283 //!If this option is not specified, `allocator_traits<A>::size_type` (usually std::size_t) will 284 //!be used to store size-related information inside the container. 285 BOOST_INTRUSIVE_OPTION_TYPE(stored_size, StoredSizeType, StoredSizeType, stored_size_type) 286 287 //! Helper metafunction to combine options into a single type to be used 288 //! by \c boost::container::vector. 289 //! Supported options are: \c boost::container::growth_factor and \c boost::container::stored_size 290 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) || defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 291 template<class ...Options> 292 #else 293 template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> 294 #endif 295 struct vector_options 296 { 297 /// @cond 298 typedef typename ::boost::intrusive::pack_options 299 < vector_null_opt, 300 #if !defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 301 O1, O2, O3, O4 302 #else 303 Options... 304 #endif 305 >::type packed_options; 306 typedef vector_opt< typename packed_options::growth_factor_type 307 , typename packed_options::stored_size_type> implementation_defined; 308 /// @endcond 309 typedef implementation_defined type; 310 }; 311 312 #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) 313 314 //! Helper alias metafunction to combine options into a single type to be used 315 //! by \c boost::container::vector. 316 //! Supported options are: \c boost::container::growth_factor and \c boost::container::stored_size 317 template<class ...Options> 318 using vector_options_t = typename boost::container::vector_options<Options...>::type; 319 320 #endif 321 322 //////////////////////////////////////////////////////////////// 323 // 324 // 325 // OPTIONS FOR SMALL-VECTOR CONTAINER 326 // 327 // 328 //////////////////////////////////////////////////////////////// 329 330 //! This option specifies the desired alignment for the value_type stored 331 //! in the container. 332 //! A value zero represents the natural alignment. 333 //! 334 //!\tparam Alignment An unsigned integer value. Must be power of two. 335 BOOST_INTRUSIVE_OPTION_CONSTANT(inplace_alignment, std::size_t, Alignment, inplace_alignment) 336 337 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 338 339 template<class GrowthType, std::size_t InplaceAlignment> 340 struct small_vector_opt 341 { 342 typedef GrowthType growth_factor_type; 343 static const std::size_t inplace_alignment = InplaceAlignment; 344 }; 345 346 typedef small_vector_opt<void, 0u> small_vector_null_opt; 347 348 #endif //!defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 349 350 //! Helper metafunction to combine options into a single type to be used 351 //! by \c boost::container::small_vector. 352 //! Supported options are: \c boost::container::growth_factor and \c boost::container::inplace_alignment 353 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) || defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 354 template<class ...Options> 355 #else 356 template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> 357 #endif 358 struct small_vector_options 359 { 360 /// @cond 361 typedef typename ::boost::intrusive::pack_options 362 < small_vector_null_opt, 363 #if !defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 364 O1, O2, O3, O4 365 #else 366 Options... 367 #endif 368 >::type packed_options; 369 typedef small_vector_opt< typename packed_options::growth_factor_type 370 , packed_options::inplace_alignment> implementation_defined; 371 /// @endcond 372 typedef implementation_defined type; 373 }; 374 375 #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) 376 377 //! Helper alias metafunction to combine options into a single type to be used 378 //! by \c boost::container::small_vector. 379 //! Supported options are: \c boost::container::growth_factor and \c boost::container::stored_size 380 template<class ...Options> 381 using small_vector_options_t = typename boost::container::small_vector_options<Options...>::type; 382 383 #endif 384 385 386 //////////////////////////////////////////////////////////////// 387 // 388 // 389 // OPTIONS FOR STATIC-VECTOR CONTAINER 390 // 391 // 392 //////////////////////////////////////////////////////////////// 393 394 //!This option specifies if the container will throw if in 395 //!the static capacity is not sufficient to hold the required 396 //!values. If false is specified, insufficient capacity will 397 //!lead to BOOST_ASSERT, and if this assertion returns, to undefined behaviour, 398 //!which potentially can lead to better static_vector performance. 399 //!The default value is true. 400 //! 401 //!\tparam ThrowOnExhaustion A boolean value. True if throw is required. 402 BOOST_INTRUSIVE_OPTION_CONSTANT(throw_on_overflow, bool, ThrowOnOverflow, throw_on_overflow) 403 404 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 405 406 template<bool ThrowOnOverflow, std::size_t InplaceAlignment> 407 struct static_vector_opt 408 { 409 static const bool throw_on_overflow = ThrowOnOverflow; 410 static const std::size_t inplace_alignment = InplaceAlignment; 411 }; 412 413 typedef static_vector_opt<true, 0u> static_vector_null_opt; 414 415 #endif //!defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 416 417 //! Helper metafunction to combine options into a single type to be used 418 //! by \c boost::container::static_vector. 419 //! Supported options are: \c boost::container::throw_on_overflow and \c boost::container::inplace_alignment 420 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) || defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 421 template<class ...Options> 422 #else 423 template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> 424 #endif 425 struct static_vector_options 426 { 427 /// @cond 428 typedef typename ::boost::intrusive::pack_options 429 < static_vector_null_opt, 430 #if !defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 431 O1, O2, O3, O4 432 #else 433 Options... 434 #endif 435 >::type packed_options; 436 typedef static_vector_opt< packed_options::throw_on_overflow 437 , packed_options::inplace_alignment> implementation_defined; 438 /// @endcond 439 typedef implementation_defined type; 440 }; 441 442 #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) 443 444 //! Helper alias metafunction to combine options into a single type to be used 445 //! by \c boost::container::static_vector. 446 //! Supported options are: \c boost::container::growth_factor and \c boost::container::stored_size 447 template<class ...Options> 448 using static_vector_options_t = typename boost::container::static_vector_options<Options...>::type; 449 450 #endif 451 452 //! Helper metafunction to combine options into a single type to be used 453 //! by \c boost::container::devector. 454 //! Supported options are: \c boost::container::growth_factor and \c boost::container::stored_size 455 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) || defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 456 template<class ...Options> 457 #else 458 template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> 459 #endif 460 struct devector_options 461 { 462 /// @cond 463 typedef typename ::boost::intrusive::pack_options 464 < devector_null_opt, 465 #if !defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 466 O1, O2, O3, O4 467 #else 468 Options... 469 #endif 470 >::type packed_options; 471 typedef devector_opt< typename packed_options::growth_factor_type 472 , typename packed_options::stored_size_type> implementation_defined; 473 /// @endcond 474 typedef implementation_defined type; 475 }; 476 477 #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) 478 479 //! Helper alias metafunction to combine options into a single type to be used 480 //! by \c boost::container::devector. 481 //! Supported options are: \c boost::container::growth_factor and \c boost::container::stored_size 482 template<class ...Options> 483 using devector_options_t = typename boost::container::devector_options<Options...>::type; 484 485 #endif 486 487 //////////////////////////////////////////////////////////////// 488 // 489 // 490 // OPTIONS FOR DEQUE-BASED CONTAINERS 491 // 492 // 493 //////////////////////////////////////////////////////////////// 494 495 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 496 497 template<std::size_t BlockBytes, std::size_t BlockSize> 498 struct deque_opt 499 { 500 static const std::size_t block_bytes = BlockBytes; 501 static const std::size_t block_size = BlockSize; 502 BOOST_STATIC_ASSERT_MSG(!(block_bytes && block_size), "block_bytes and block_size can't be specified at the same time"); 503 }; 504 505 typedef deque_opt<0u, 0u> deque_null_opt; 506 507 #endif 508 509 //! Helper metafunction to combine options into a single type to be used 510 //! by \c boost::container::deque. 511 //! Supported options are: \c boost::container::block_bytes 512 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) || defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 513 template<class ...Options> 514 #else 515 template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> 516 #endif 517 struct deque_options 518 { 519 /// @cond 520 typedef typename ::boost::intrusive::pack_options 521 < deque_null_opt, 522 #if !defined(BOOST_CONTAINER_VARIADIC_TEMPLATES) 523 O1, O2, O3, O4 524 #else 525 Options... 526 #endif 527 >::type packed_options; 528 typedef deque_opt< packed_options::block_bytes, packed_options::block_size > implementation_defined; 529 /// @endcond 530 typedef implementation_defined type; 531 }; 532 533 #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) 534 535 //! Helper alias metafunction to combine options into a single type to be used 536 //! by \c boost::container::deque. 537 //! Supported options are: \c boost::container::block_bytes 538 template<class ...Options> 539 using deque_options_t = typename boost::container::deque_options<Options...>::type; 540 541 #endif 542 543 //!This option specifies the maximum size of a block in bytes: this delimites the number of contiguous elements 544 //!that will be allocated by deque as min(1u, BlockBytes/sizeof(value_type)) 545 //!A value zero represents the default value. 546 //! 547 //!\tparam BlockBytes An unsigned integer value. 548 BOOST_INTRUSIVE_OPTION_CONSTANT(block_bytes, std::size_t, BlockBytes, block_bytes) 549 550 //!This option specifies the size of a block, delimites the number of contiguous elements 551 //!that will be allocated by deque as BlockSize. 552 //!A value zero represents the default value. 553 //! 554 //!\tparam BlockBytes An unsigned integer value. 555 BOOST_INTRUSIVE_OPTION_CONSTANT(block_size, std::size_t, BlockSize, block_size) 556 557 } //namespace container { 558 } //namespace boost { 559 560 #include <boost/container/detail/config_end.hpp> 561 562 #endif //#ifndef BOOST_CONTAINER_OPTIONS_HPP 563