diff options
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail/util.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/util.hpp | 331 |
1 files changed, 331 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/util.hpp b/3rdParty/Boost/src/boost/unordered/detail/util.hpp new file mode 100644 index 0000000..5540965 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/util.hpp @@ -0,0 +1,331 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2009 Daniel James +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED + +#include <cstddef> +#include <utility> +#include <algorithm> +#include <boost/limits.hpp> +#include <boost/iterator/iterator_categories.hpp> +#include <boost/preprocessor/seq/size.hpp> +#include <boost/preprocessor/seq/enum.hpp> +#include <boost/unordered/detail/fwd.hpp> + +namespace boost { namespace unordered_detail { + + //////////////////////////////////////////////////////////////////////////// + // convert double to std::size_t + + inline std::size_t double_to_size_t(double f) + { + return f >= static_cast<double>( + (std::numeric_limits<std::size_t>::max)()) ? + (std::numeric_limits<std::size_t>::max)() : + static_cast<std::size_t>(f); + } + + //////////////////////////////////////////////////////////////////////////// + // primes + +#define BOOST_UNORDERED_PRIMES \ + (5ul)(11ul)(17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \ + (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \ + (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \ + (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \ + (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \ + (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \ + (1610612741ul)(3221225473ul)(4294967291ul) + + template<class T> struct prime_list_template + { + static std::size_t const value[]; + +#if !defined(SUNPRO_CC) + static std::ptrdiff_t const length; +#else + static std::ptrdiff_t const length + = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); +#endif + }; + + template<class T> + std::size_t const prime_list_template<T>::value[] = { + BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES) + }; + +#if !defined(SUNPRO_CC) + template<class T> + std::ptrdiff_t const prime_list_template<T>::length + = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); +#endif + +#undef BOOST_UNORDERED_PRIMES + + typedef prime_list_template<std::size_t> prime_list; + + // no throw + inline std::size_t next_prime(std::size_t num) { + std::size_t const* const prime_list_begin = prime_list::value; + std::size_t const* const prime_list_end = prime_list_begin + + prime_list::length; + std::size_t const* bound = + std::lower_bound(prime_list_begin, prime_list_end, num); + if(bound == prime_list_end) + bound--; + return *bound; + } + + // no throw + inline std::size_t prev_prime(std::size_t num) { + std::size_t const* const prime_list_begin = prime_list::value; + std::size_t const* const prime_list_end = prime_list_begin + + prime_list::length; + std::size_t const* bound = + std::upper_bound(prime_list_begin,prime_list_end, num); + if(bound != prime_list_begin) + bound--; + return *bound; + } + + //////////////////////////////////////////////////////////////////////////// + // pair_cast - because some libraries don't have the full pair constructors. + + template <class Dst1, class Dst2, class Src1, class Src2> + inline std::pair<Dst1, Dst2> pair_cast(std::pair<Src1, Src2> const& x) + { + return std::pair<Dst1, Dst2>(Dst1(x.first), Dst2(x.second)); + } + + //////////////////////////////////////////////////////////////////////////// + // insert_size/initial_size + +#if !defined(BOOST_NO_STD_DISTANCE) + using ::std::distance; +#else + template <class ForwardIterator> + inline std::size_t distance(ForwardIterator i, ForwardIterator j) { + std::size_t x; + std::distance(i, j, x); + return x; + } +#endif + + template <class I> + inline std::size_t insert_size(I i, I j, boost::forward_traversal_tag) + { + return std::distance(i, j); + } + + template <class I> + inline std::size_t insert_size(I, I, boost::incrementable_traversal_tag) + { + return 1; + } + + template <class I> + inline std::size_t insert_size(I i, I j) + { + BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type + iterator_traversal_tag; + return insert_size(i, j, iterator_traversal_tag); + } + + template <class I> + inline std::size_t initial_size(I i, I j, + std::size_t num_buckets = boost::unordered_detail::default_bucket_count) + { + return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1, + num_buckets); + } + + //////////////////////////////////////////////////////////////////////////// + // Node Constructors + +#if defined(BOOST_UNORDERED_STD_FORWARD) + + template <class T, class... Args> + inline void construct_impl(T*, void* address, Args&&... args) + { + new(address) T(std::forward<Args>(args)...); + } + +#if defined(BOOST_UNORDERED_CPP0X_PAIR) + template <class First, class Second, class Key, class Arg0, class... Args> + inline void construct_impl(std::pair<First, Second>*, void* address, + Key&& k, Arg0&& arg0, Args&&... args) + ) + { + new(address) std::pair<First, Second>(k, + Second(arg0, std::forward<Args>(args)...); + } +#endif + +#else + +#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \ + template < \ + class T, \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + > \ + inline void construct_impl( \ + T*, void* address, \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ + ) \ + { \ + new(address) T( \ + BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ + } \ + \ + template <class First, class Second, class Key, \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + > \ + inline void construct_impl( \ + std::pair<First, Second>*, void* address, \ + Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ + { \ + new(address) std::pair<First, Second>(k, \ + Second(BOOST_UNORDERED_CALL_PARAMS(z, num_params))); \ + } + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_CONSTRUCT_IMPL, _) + +#undef BOOST_UNORDERED_CONSTRUCT_IMPL +#endif + + // hash_node_constructor + // + // Used to construct nodes in an exception safe manner. + + template <class Alloc, class Grouped> + class hash_node_constructor + { + typedef hash_buckets<Alloc, Grouped> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type; + + buckets& buckets_; + real_node_ptr node_; + bool node_constructed_; + bool value_constructed_; + + public: + + hash_node_constructor(buckets& m) : + buckets_(m), + node_(), + node_constructed_(false), + value_constructed_(false) + { + } + + ~hash_node_constructor(); + void construct_preamble(); + +#if defined(BOOST_UNORDERED_STD_FORWARD) + template <class... Args> + void construct(Args&&... args) + { + construct_preamble(); + construct_impl((value_type*) 0, node_->address(), + std::forward<Args>(args)...); + value_constructed_ = true; + } +#else + +#define BOOST_UNORDERED_CONSTRUCT(z, num_params, _) \ + template < \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + > \ + void construct( \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ + ) \ + { \ + construct_preamble(); \ + construct_impl( \ + (value_type*) 0, node_->address(), \ + BOOST_UNORDERED_CALL_PARAMS(z, num_params) \ + ); \ + value_constructed_ = true; \ + } + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_CONSTRUCT, _) + +#undef BOOST_UNORDERED_CONSTRUCT + +#endif + template <class K, class M> + void construct_pair(K const& k, M*) + { + construct_preamble(); + new(node_->address()) value_type(k, M()); + value_constructed_ = true; + } + + value_type& value() const + { + BOOST_ASSERT(node_); + return node_->value(); + } + + // no throw + BOOST_DEDUCED_TYPENAME buckets::node_ptr release() + { + real_node_ptr p = node_; + node_ = real_node_ptr(); + // node_ptr cast + return buckets_.bucket_alloc().address(*p); + } + + private: + hash_node_constructor(hash_node_constructor const&); + hash_node_constructor& operator=(hash_node_constructor const&); + }; + + // hash_node_constructor + + template <class Alloc, class Grouped> + inline hash_node_constructor<Alloc, Grouped>::~hash_node_constructor() + { + if (node_) { + if (value_constructed_) { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { hash_node<Alloc, Grouped> x; }; +#endif + boost::unordered_detail::destroy(&node_->value()); + } + + if (node_constructed_) + buckets_.node_alloc().destroy(node_); + + buckets_.node_alloc().deallocate(node_, 1); + } + } + + template <class Alloc, class Grouped> + inline void hash_node_constructor<Alloc, Grouped>::construct_preamble() + { + if(!node_) { + node_constructed_ = false; + value_constructed_ = false; + + node_ = buckets_.node_alloc().allocate(1); + buckets_.node_alloc().construct(node_, node()); + node_constructed_ = true; + } + else { + BOOST_ASSERT(node_constructed_ && value_constructed_); + boost::unordered_detail::destroy(&node_->value()); + value_constructed_ = false; + } + } +}} + +#endif |