| |
| // 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 |