Chris@16: 
Chris@16: // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
Chris@16: // Copyright (C) 2005-2011 Daniel James
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See accompanying
Chris@16: // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
Chris@16: #define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
Chris@16: 
Chris@101: #include <boost/config.hpp>
Chris@101: #if defined(BOOST_HAS_PRAGMA_ONCE)
Chris@101: #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/type_traits/is_convertible.hpp>
Chris@16: #include <boost/type_traits/is_empty.hpp>
Chris@16: #include <boost/iterator/iterator_categories.hpp>
Chris@16: #include <boost/utility/enable_if.hpp>
Chris@16: #include <boost/detail/select_type.hpp>
Chris@16: #include <boost/move/move.hpp>
Chris@16: #include <boost/preprocessor/seq/size.hpp>
Chris@16: #include <boost/preprocessor/seq/enum.hpp>
Chris@16: #include <boost/swap.hpp>
Chris@16: 
Chris@16: namespace boost { namespace unordered { namespace detail {
Chris@16: 
Chris@16:     static const float minimum_max_load_factor = 1e-3f;
Chris@16:     static const std::size_t default_bucket_count = 11;
Chris@16:     struct move_tag {};
Chris@16:     struct empty_emplace {};
Chris@16: 
Chris@16:     namespace func {
Chris@16:         template <class T>
Chris@16:         inline void ignore_unused_variable_warning(T const&) {}
Chris@16:     }
Chris@16: 
Chris@16:     ////////////////////////////////////////////////////////////////////////////
Chris@16:     // iterator SFINAE
Chris@16: 
Chris@16:     template <typename I>
Chris@16:     struct is_forward :
Chris@16:         boost::is_convertible<
Chris@16:             typename boost::iterator_traversal<I>::type,
Chris@16:             boost::forward_traversal_tag>
Chris@16:     {};
Chris@16: 
Chris@16:     template <typename I, typename ReturnType>
Chris@16:     struct enable_if_forward :
Chris@16:         boost::enable_if_c<
Chris@16:             boost::unordered::detail::is_forward<I>::value,
Chris@16:             ReturnType>
Chris@16:     {};
Chris@16: 
Chris@16:     template <typename I, typename ReturnType>
Chris@16:     struct disable_if_forward :
Chris@16:         boost::disable_if_c<
Chris@16:             boost::unordered::detail::is_forward<I>::value,
Chris@16:             ReturnType>
Chris@16:     {};
Chris@16: 
Chris@16:     ////////////////////////////////////////////////////////////////////////////
Chris@16:     // primes
Chris@16: 
Chris@16: #define BOOST_UNORDERED_PRIMES \
Chris@16:     (17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \
Chris@16:     (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \
Chris@16:     (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \
Chris@16:     (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \
Chris@16:     (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \
Chris@16:     (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \
Chris@16:     (1610612741ul)(3221225473ul)(4294967291ul)
Chris@16: 
Chris@16:     template<class T> struct prime_list_template
Chris@16:     {
Chris@16:         static std::size_t const value[];
Chris@16: 
Chris@16: #if !defined(SUNPRO_CC)
Chris@16:         static std::ptrdiff_t const length;
Chris@16: #else
Chris@16:         static std::ptrdiff_t const length
Chris@16:             = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
Chris@16: #endif
Chris@16:     };
Chris@16: 
Chris@16:     template<class T>
Chris@16:     std::size_t const prime_list_template<T>::value[] = {
Chris@16:         BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)
Chris@16:     };
Chris@16: 
Chris@16: #if !defined(SUNPRO_CC)
Chris@16:     template<class T>
Chris@16:     std::ptrdiff_t const prime_list_template<T>::length
Chris@16:         = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
Chris@16: #endif
Chris@16: 
Chris@16: #undef BOOST_UNORDERED_PRIMES
Chris@16: 
Chris@16:     typedef prime_list_template<std::size_t> prime_list;
Chris@16: 
Chris@16:     // no throw
Chris@16:     inline std::size_t next_prime(std::size_t num) {
Chris@16:         std::size_t const* const prime_list_begin = prime_list::value;
Chris@16:         std::size_t const* const prime_list_end = prime_list_begin +
Chris@16:             prime_list::length;
Chris@16:         std::size_t const* bound =
Chris@16:             std::lower_bound(prime_list_begin, prime_list_end, num);
Chris@16:         if(bound == prime_list_end)
Chris@16:             bound--;
Chris@16:         return *bound;
Chris@16:     }
Chris@16: 
Chris@16:     // no throw
Chris@16:     inline std::size_t prev_prime(std::size_t num) {
Chris@16:         std::size_t const* const prime_list_begin = prime_list::value;
Chris@16:         std::size_t const* const prime_list_end = prime_list_begin +
Chris@16:             prime_list::length;
Chris@16:         std::size_t const* bound =
Chris@16:             std::upper_bound(prime_list_begin,prime_list_end, num);
Chris@16:         if(bound != prime_list_begin)
Chris@16:             bound--;
Chris@16:         return *bound;
Chris@16:     }
Chris@16: 
Chris@16:     ////////////////////////////////////////////////////////////////////////////
Chris@16:     // insert_size/initial_size
Chris@16: 
Chris@16: #if !defined(BOOST_NO_STD_DISTANCE)
Chris@16: 
Chris@16:     using ::std::distance;
Chris@16: 
Chris@16: #else
Chris@16: 
Chris@16:     template <class ForwardIterator>
Chris@16:     inline std::size_t distance(ForwardIterator i, ForwardIterator j) {
Chris@16:         std::size_t x;
Chris@16:         std::distance(i, j, x);
Chris@16:         return x;
Chris@16:     }
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16:     template <class I>
Chris@16:     inline typename
Chris@16:         boost::unordered::detail::enable_if_forward<I, std::size_t>::type
Chris@16:         insert_size(I i, I j)
Chris@16:     {
Chris@16:         return std::distance(i, j);
Chris@16:     }
Chris@16: 
Chris@16:     template <class I>
Chris@16:     inline typename
Chris@16:         boost::unordered::detail::disable_if_forward<I, std::size_t>::type
Chris@16:         insert_size(I, I)
Chris@16:     {
Chris@16:         return 1;
Chris@16:     }
Chris@16: 
Chris@16:     template <class I>
Chris@16:     inline std::size_t initial_size(I i, I j,
Chris@16:         std::size_t num_buckets =
Chris@16:             boost::unordered::detail::default_bucket_count)
Chris@16:     {
Chris@16:         // TODO: Why +1?
Chris@16:         return (std::max)(
Chris@16:             boost::unordered::detail::insert_size(i, j) + 1,
Chris@16:             num_buckets);
Chris@16:     }
Chris@16: 
Chris@16:     ////////////////////////////////////////////////////////////////////////////
Chris@16:     // compressed
Chris@16: 
Chris@16:     template <typename T, int Index>
Chris@16:     struct compressed_base : private T
Chris@16:     {
Chris@16:         compressed_base(T const& x) : T(x) {}
Chris@16:         compressed_base(T& x, move_tag) : T(boost::move(x)) {}
Chris@16: 
Chris@16:         T& get() { return *this; }
Chris@16:         T const& get() const { return *this; }
Chris@16:     };
Chris@16:     
Chris@16:     template <typename T, int Index>
Chris@16:     struct uncompressed_base
Chris@16:     {
Chris@16:         uncompressed_base(T const& x) : value_(x) {}
Chris@16:         uncompressed_base(T& x, move_tag) : value_(boost::move(x)) {}
Chris@16: 
Chris@16:         T& get() { return value_; }
Chris@16:         T const& get() const { return value_; }
Chris@16:     private:
Chris@16:         T value_;
Chris@16:     };
Chris@16:     
Chris@16:     template <typename T, int Index>
Chris@16:     struct generate_base
Chris@16:       : boost::detail::if_true<
Chris@16:             boost::is_empty<T>::value
Chris@16:         >:: BOOST_NESTED_TEMPLATE then<
Chris@16:             boost::unordered::detail::compressed_base<T, Index>,
Chris@16:             boost::unordered::detail::uncompressed_base<T, Index>
Chris@16:         >
Chris@16:     {};
Chris@16:     
Chris@16:     template <typename T1, typename T2>
Chris@16:     struct compressed
Chris@16:       : private boost::unordered::detail::generate_base<T1, 1>::type,
Chris@16:         private boost::unordered::detail::generate_base<T2, 2>::type
Chris@16:     {
Chris@16:         typedef typename generate_base<T1, 1>::type base1;
Chris@16:         typedef typename generate_base<T2, 2>::type base2;
Chris@16: 
Chris@16:         typedef T1 first_type;
Chris@16:         typedef T2 second_type;
Chris@16:         
Chris@16:         first_type& first() {
Chris@16:             return static_cast<base1*>(this)->get();
Chris@16:         }
Chris@16: 
Chris@16:         first_type const& first() const {
Chris@16:             return static_cast<base1 const*>(this)->get();
Chris@16:         }
Chris@16: 
Chris@16:         second_type& second() {
Chris@16:             return static_cast<base2*>(this)->get();
Chris@16:         }
Chris@16: 
Chris@16:         second_type const& second() const {
Chris@16:             return static_cast<base2 const*>(this)->get();
Chris@16:         }
Chris@16: 
Chris@16:         template <typename First, typename Second>
Chris@16:         compressed(First const& x1, Second const& x2)
Chris@16:             : base1(x1), base2(x2) {}
Chris@16: 
Chris@16:         compressed(compressed const& x)
Chris@16:             : base1(x.first()), base2(x.second()) {}
Chris@16: 
Chris@16:         compressed(compressed& x, move_tag m)
Chris@16:             : base1(x.first(), m), base2(x.second(), m) {}
Chris@16: 
Chris@16:         void assign(compressed const& x)
Chris@16:         {
Chris@16:             first() = x.first();
Chris@16:             second() = x.second();
Chris@16:         }
Chris@16: 
Chris@16:         void move_assign(compressed& x)
Chris@16:         {
Chris@16:             first() = boost::move(x.first());
Chris@16:             second() = boost::move(x.second());
Chris@16:         }
Chris@16:         
Chris@16:         void swap(compressed& x)
Chris@16:         {
Chris@16:             boost::swap(first(), x.first());
Chris@16:             boost::swap(second(), x.second());
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         // Prevent assignment just to make use of assign or
Chris@16:         // move_assign explicit.
Chris@16:         compressed& operator=(compressed const&);
Chris@16:     };
Chris@16: }}}
Chris@16: 
Chris@16: #endif