1 /*! 2 @file 3 Defines `boost::hana::detail::hash_table`. 4 5 @copyright Louis Dionne 2016 6 @copyright Jason Rice 2016 7 Distributed under the Boost Software License, Version 1.0. 8 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) 9 */ 10 11 #ifndef BOOST_HANA_DETAIL_HASH_TABLE_HPP 12 #define BOOST_HANA_DETAIL_HASH_TABLE_HPP 13 14 #include <boost/hana/equal.hpp> 15 #include <boost/hana/ext/std/integer_sequence.hpp> 16 #include <boost/hana/ext/std/integral_constant.hpp> 17 #include <boost/hana/find_if.hpp> 18 #include <boost/hana/fold_left.hpp> 19 #include <boost/hana/hash.hpp> 20 #include <boost/hana/optional.hpp> 21 #include <boost/hana/range.hpp> 22 #include <boost/hana/type.hpp> 23 #include <boost/hana/value.hpp> 24 25 #include <cstddef> 26 #include <type_traits> 27 #include <utility> 28 29 30 BOOST_HANA_NAMESPACE_BEGIN namespace detail { 31 template <typename Hash, std::size_t ...i> 32 struct bucket { }; 33 34 template <typename ...Buckets> 35 struct hash_table 36 : Buckets... 37 { }; 38 39 // find_indices: 40 // Returns an `index_sequence` containing possible indices for the given 41 // `Key` in the `Map`. 42 template <typename Hash, std::size_t ...i> 43 std::index_sequence<i...> find_indices_impl(bucket<Hash, i...> const&); 44 45 template <typename Hash> 46 std::index_sequence<> find_indices_impl(...); 47 48 template <typename Map, typename Key> 49 struct find_indices { 50 using Hash = typename decltype(hana::hash(std::declval<Key>()))::type; 51 using type = decltype(detail::find_indices_impl<Hash>(std::declval<Map>())); 52 }; 53 // end find_indices 54 55 // find_index: 56 // Returns the actual index of a `Key` in the `Map`. The type of the key 57 // associated to any given index must be retrievable with the `KeyAtIndex` 58 // alias. 59 template <template <std::size_t> class KeyAtIndex, typename Key> 60 struct find_pred { 61 template <typename Index> 62 auto operator()(Index const&) const -> decltype( 63 hana::equal(std::declval<KeyAtIndex<Index::value>>(), 64 std::declval<Key>()) 65 ); 66 }; 67 68 template <typename Indices, typename Key, template <std::size_t> class KeyAtIndex> 69 struct find_index_impl { 70 using type = decltype(hana::find_if(Indices{}, find_pred<KeyAtIndex, Key>{})); 71 }; 72 73 // This is a peephole optimization for buckets that have a single entry. 74 // It provides a nice speedup in the at_key.number_of_lookups benchmark. 75 // It is perhaps possible to make this part of `find_if` itself, but we 76 // should make sure that we retain that speedup. 77 template <std::size_t i, typename Key, template <std::size_t> class KeyAtIndex> 78 struct find_index_impl<std::index_sequence<i>, Key, KeyAtIndex> { 79 using Equal = decltype( 80 hana::equal(std::declval<KeyAtIndex<i>>(), 81 std::declval<Key>()) 82 ); 83 using type = typename std::conditional<Equal::value, 84 hana::optional<std::integral_constant<std::size_t, i>>, 85 hana::optional<> 86 >::type; 87 }; 88 89 template <typename Map, typename Key, template <std::size_t> class KeyAtIndex> 90 struct find_index { 91 using Indices = typename find_indices<Map, Key>::type; 92 using type = typename find_index_impl<Indices, Key, KeyAtIndex>::type; 93 }; 94 // end find_index 95 96 // bucket_insert: 97 // Inserts the given `Index` into the bucket of the `Map` in which `Key` falls. 98 template <typename Bucket, typename Hash, std::size_t Index> 99 struct update_bucket { 100 using type = Bucket; 101 }; 102 103 template <std::size_t ...i, typename Hash, std::size_t Index> 104 struct update_bucket<bucket<Hash, i...>, Hash, Index> { 105 using type = bucket<Hash, i..., Index>; 106 }; 107 108 template <typename Map, typename Key, std::size_t Index, bool = 109 (find_indices<Map, Key>::type::size() > 0) 110 > 111 struct bucket_insert; 112 113 template <typename ...Buckets, typename Key, std::size_t Index> 114 struct bucket_insert<hash_table<Buckets...>, Key, Index, true> { 115 // There is a bucket for that Hash; append the new index to it. 116 using Hash = typename decltype(hana::hash(std::declval<Key>()))::type; 117 using type = hash_table<typename update_bucket<Buckets, Hash, Index>::type...>; 118 }; 119 120 template <typename ...Buckets, typename Key, std::size_t Index> 121 struct bucket_insert<hash_table<Buckets...>, Key, Index, false> { 122 // There is no bucket for that Hash; insert a new bucket. 123 using Hash = typename decltype(hana::hash(std::declval<Key>()))::type; 124 using type = hash_table<Buckets..., bucket<Hash, Index>>; 125 }; 126 // end bucket_insert 127 128 // make_hash_table: 129 // Creates a `hash_table` type able of holding the given number of 130 // elements. The type of the key associated to any given index must 131 // be retrievable using the `KeyAtIndex` alias. All the keys must 132 // be distinct and have different hashes too. 133 template <template <std::size_t> class KeyAtIndex, std::size_t N, 134 typename Indices = std::make_index_sequence<N>> 135 struct make_hash_table; 136 137 template <template <std::size_t> class KeyAtIndex, std::size_t N, std::size_t ...i> 138 struct make_hash_table<KeyAtIndex, N, std::index_sequence<i...>> { 139 using type = hash_table< 140 bucket<typename decltype(hana::hash(std::declval<KeyAtIndex<i>>()))::type, i>... 141 >; 142 }; 143 } BOOST_HANA_NAMESPACE_END 144 145 #endif // !BOOST_HANA_DETAIL_HASH_TABLE_HPP 146