boost/unordered/detail/util.hpp

   1
   2 // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
   3 // Copyright (C) 2005-2011 Daniel James
   4 // Distributed under the Boost Software License, Version 1.0. (See accompanying
   5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
   8 #define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
   9
  10 #include <boost/config.hpp>
  11 #if defined(BOOST_HAS_PRAGMA_ONCE)
  12 #pragma once
  13 #endif
  14
  15 #include <boost/type_traits/is_convertible.hpp>
  16 #include <boost/type_traits/is_empty.hpp>
  17 #include <boost/iterator/iterator_categories.hpp>
  18 #include <boost/utility/enable_if.hpp>
  19 #include <boost/detail/select_type.hpp>
  20 #include <boost/move/move.hpp>
  21 #include <boost/preprocessor/seq/size.hpp>
  22 #include <boost/preprocessor/seq/enum.hpp>
  23 #include <boost/swap.hpp>
  24
  25 namespace boost { namespace unordered { namespace detail {
  26
  27     static const float minimum_max_load_factor = 1e-3f;
  28     static const std::size_t default_bucket_count = 11;
  29     struct move_tag {};
  30     struct empty_emplace {};
  31
  32     namespace func {
  33         template <class T>
  34         inline void ignore_unused_variable_warning(T const&) {}
  35     }
  36
  37     ////////////////////////////////////////////////////////////////////////////
  38     // iterator SFINAE
  39
  40     template <typename I>
  41     struct is_forward :
  42         boost::is_convertible<
  43             typename boost::iterator_traversal<I>::type,
  44             boost::forward_traversal_tag>
  45     {};
  46
  47     template <typename I, typename ReturnType>
  48     struct enable_if_forward :
  49         boost::enable_if_c<
  50             boost::unordered::detail::is_forward<I>::value,
  51             ReturnType>
  52     {};
  53
  54     template <typename I, typename ReturnType>
  55     struct disable_if_forward :
  56         boost::disable_if_c<
  57             boost::unordered::detail::is_forward<I>::value,
  58             ReturnType>
  59     {};
  60
  61     ////////////////////////////////////////////////////////////////////////////
  62     // primes
  63
  64 #define BOOST_UNORDERED_PRIMES \
  65     (17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \
  66     (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \
  67     (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \
  68     (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \
  69     (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \
  70     (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \
  71     (1610612741ul)(3221225473ul)(4294967291ul)
  72
  73     template<class T> struct prime_list_template
  74     {
  75         static std::size_t const value[];
  76
  77 #if !defined(SUNPRO_CC)
  78         static std::ptrdiff_t const length;
  79 #else
  80         static std::ptrdiff_t const length
  81             = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
  82 #endif
  83     };
  84
  85     template<class T>
  86     std::size_t const prime_list_template<T>::value[] = {
  87         BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)
  88     };
  89
  90 #if !defined(SUNPRO_CC)
  91     template<class T>
  92     std::ptrdiff_t const prime_list_template<T>::length
  93         = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
  94 #endif
  95
  96 #undef BOOST_UNORDERED_PRIMES
  97
  98     typedef prime_list_template<std::size_t> prime_list;
  99
 100     // no throw
 101     inline std::size_t next_prime(std::size_t num) {
 102         std::size_t const* const prime_list_begin = prime_list::value;
 103         std::size_t const* const prime_list_end = prime_list_begin +
 104             prime_list::length;
 105         std::size_t const* bound =
 106             std::lower_bound(prime_list_begin, prime_list_end, num);
 107         if(bound == prime_list_end)
 108             bound--;
 109         return *bound;
 110     }
 111
 112     // no throw
 113     inline std::size_t prev_prime(std::size_t num) {
 114         std::size_t const* const prime_list_begin = prime_list::value;
 115         std::size_t const* const prime_list_end = prime_list_begin +
 116             prime_list::length;
 117         std::size_t const* bound =
 118             std::upper_bound(prime_list_begin,prime_list_end, num);
 119         if(bound != prime_list_begin)
 120             bound--;
 121         return *bound;
 122     }
 123
 124     ////////////////////////////////////////////////////////////////////////////
 125     // insert_size/initial_size
 126
 127     template <class I>
 128     inline std::size_t insert_size(I i, I j, typename
 129         boost::unordered::detail::enable_if_forward<I, void*>::type = 0)
 130     {
 131         return static_cast<std::size_t>(std::distance(i, j));
 132     }
 133
 134     template <class I>
 135     inline std::size_t insert_size(I, I, typename
 136         boost::unordered::detail::disable_if_forward<I, void*>::type = 0)
 137     {
 138         return 1;
 139     }
 140
 141     template <class I>
 142     inline std::size_t initial_size(I i, I j,
 143         std::size_t num_buckets =
 144             boost::unordered::detail::default_bucket_count)
 145     {
 146         // TODO: Why +1?
 147         return (std::max)(
 148             boost::unordered::detail::insert_size(i, j) + 1,
 149             num_buckets);
 150     }
 151
 152     ////////////////////////////////////////////////////////////////////////////
 153     // compressed
 154
 155     template <typename T, int Index>
 156     struct compressed_base : private T
 157     {
 158         compressed_base(T const& x) : T(x) {}
 159         compressed_base(T& x, move_tag) : T(boost::move(x)) {}
 160
 161         T& get() { return *this; }
 162         T const& get() const { return *this; }
 163     };
 164
 165     template <typename T, int Index>
 166     struct uncompressed_base
 167     {
 168         uncompressed_base(T const& x) : value_(x) {}
 169         uncompressed_base(T& x, move_tag) : value_(boost::move(x)) {}
 170
 171         T& get() { return value_; }
 172         T const& get() const { return value_; }
 173     private:
 174         T value_;
 175     };
 176
 177     template <typename T, int Index>
 178     struct generate_base
 179       : boost::detail::if_true<
 180             boost::is_empty<T>::value
 181         >:: BOOST_NESTED_TEMPLATE then<
 182             boost::unordered::detail::compressed_base<T, Index>,
 183             boost::unordered::detail::uncompressed_base<T, Index>
 184         >
 185     {};
 186
 187     template <typename T1, typename T2>
 188     struct compressed
 189       : private boost::unordered::detail::generate_base<T1, 1>::type,
 190         private boost::unordered::detail::generate_base<T2, 2>::type
 191     {
 192         typedef typename generate_base<T1, 1>::type base1;
 193         typedef typename generate_base<T2, 2>::type base2;
 194
 195         typedef T1 first_type;
 196         typedef T2 second_type;
 197
 198         first_type& first() {
 199             return static_cast<base1*>(this)->get();
 200         }
 201
 202         first_type const& first() const {
 203             return static_cast<base1 const*>(this)->get();
 204         }
 205
 206         second_type& second() {
 207             return static_cast<base2*>(this)->get();
 208         }
 209
 210         second_type const& second() const {
 211             return static_cast<base2 const*>(this)->get();
 212         }
 213
 214         template <typename First, typename Second>
 215         compressed(First const& x1, Second const& x2)
 216             : base1(x1), base2(x2) {}
 217
 218         compressed(compressed const& x)
 219             : base1(x.first()), base2(x.second()) {}
 220
 221         compressed(compressed& x, move_tag m)
 222             : base1(x.first(), m), base2(x.second(), m) {}
 223
 224         void assign(compressed const& x)
 225         {
 226             first() = x.first();
 227             second() = x.second();
 228         }
 229
 230         void move_assign(compressed& x)
 231         {
 232             first() = boost::move(x.first());
 233             second() = boost::move(x.second());
 234         }
 235
 236         void swap(compressed& x)
 237         {
 238             boost::swap(first(), x.first());
 239             boost::swap(second(), x.second());
 240         }
 241
 242     private:
 243         // Prevent assignment just to make use of assign or
 244         // move_assign explicit.
 245         compressed& operator=(compressed const&);
 246     };
 247 }}}
 248
 249 #endif