9
3

options.hpp 18 KB

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