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> ignore_unused_variable_warning(T const &)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 next_prime(std::size_t num)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 prev_prime(std::size_t num)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> insert_size(I i,I j,typename boost::unordered::detail::enable_if_forward<I,void * >::type=0)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 std::distance(i, j); 132 } 133 134 template <class I> insert_size(I,I,typename boost::unordered::detail::disable_if_forward<I,void * >::type=0)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> initial_size(I i,I j,std::size_t num_buckets=boost::unordered::detail::default_bucket_count)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 { compressed_baseboost::unordered::detail::compressed_base158 compressed_base(T const& x) : T(x) {} compressed_baseboost::unordered::detail::compressed_base159 compressed_base(T& x, move_tag) : T(boost::move(x)) {} 160 getboost::unordered::detail::compressed_base161 T& get() { return *this; } getboost::unordered::detail::compressed_base162 T const& get() const { return *this; } 163 }; 164 165 template <typename T, int Index> 166 struct uncompressed_base 167 { uncompressed_baseboost::unordered::detail::uncompressed_base168 uncompressed_base(T const& x) : value_(x) {} uncompressed_baseboost::unordered::detail::uncompressed_base169 uncompressed_base(T& x, move_tag) : value_(boost::move(x)) {} 170 getboost::unordered::detail::uncompressed_base171 T& get() { return value_; } getboost::unordered::detail::uncompressed_base172 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 firstboost::unordered::detail::compressed198 first_type& first() { 199 return static_cast<base1*>(this)->get(); 200 } 201 firstboost::unordered::detail::compressed202 first_type const& first() const { 203 return static_cast<base1 const*>(this)->get(); 204 } 205 secondboost::unordered::detail::compressed206 second_type& second() { 207 return static_cast<base2*>(this)->get(); 208 } 209 secondboost::unordered::detail::compressed210 second_type const& second() const { 211 return static_cast<base2 const*>(this)->get(); 212 } 213 214 template <typename First, typename Second> compressedboost::unordered::detail::compressed215 compressed(First const& x1, Second const& x2) 216 : base1(x1), base2(x2) {} 217 compressedboost::unordered::detail::compressed218 compressed(compressed const& x) 219 : base1(x.first()), base2(x.second()) {} 220 compressedboost::unordered::detail::compressed221 compressed(compressed& x, move_tag m) 222 : base1(x.first(), m), base2(x.second(), m) {} 223 assignboost::unordered::detail::compressed224 void assign(compressed const& x) 225 { 226 first() = x.first(); 227 second() = x.second(); 228 } 229 move_assignboost::unordered::detail::compressed230 void move_assign(compressed& x) 231 { 232 first() = boost::move(x.first()); 233 second() = boost::move(x.second()); 234 } 235 swapboost::unordered::detail::compressed236 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 250