hana/detail/hash_table.hpp

0001 /*!
0002 @file
0003 Defines `boost::hana::detail::hash_table`.
0004
0005 Copyright Louis Dionne 2016
0006 Copyright Jason Rice 2016
0007 Distributed under the Boost Software License, Version 1.0.
0008 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
0009  */
0010
0011 #ifndef BOOST_HANA_DETAIL_HASH_TABLE_HPP
0012 #define BOOST_HANA_DETAIL_HASH_TABLE_HPP
0013
0014 #include <boost/hana/equal.hpp>
0015 #include <boost/hana/ext/std/integer_sequence.hpp>
0016 #include <boost/hana/ext/std/integral_constant.hpp>
0017 #include <boost/hana/find_if.hpp>
0018 #include <boost/hana/fold_left.hpp>
0019 #include <boost/hana/hash.hpp>
0020 #include <boost/hana/optional.hpp>
0021 #include <boost/hana/range.hpp>
0022 #include <boost/hana/type.hpp>
0023 #include <boost/hana/value.hpp>
0024
0025 #include <cstddef>
0026 #include <type_traits>
0027 #include <utility>
0028
0029
0030 namespace boost { namespace hana { namespace detail {
0031     template <typename Hash, std::size_t ...i>
0032     struct bucket { };
0033
0034     template <typename ...Buckets>
0035     struct hash_table
0036         : Buckets...
0037     { };
0038
0039     // find_indices:
0040     //  Returns an `index_sequence` containing possible indices for the given
0041     //  `Key` in the `Map`.
0042     template <typename Hash, std::size_t ...i>
0043     std::index_sequence<i...> find_indices_impl(bucket<Hash, i...> const&);
0044
0045     template <typename Hash>
0046     std::index_sequence<> find_indices_impl(...);
0047
0048     template <typename Map, typename Key>
0049     struct find_indices {
0050         using Hash = typename decltype(hana::hash(std::declval<Key>()))::type;
0051         using type = decltype(detail::find_indices_impl<Hash>(std::declval<Map>()));
0052     };
0053     // end find_indices
0054
0055     // find_index:
0056     //  Returns the actual index of a `Key` in the `Map`. The type of the key
0057     //  associated to any given index must be retrievable with the `KeyAtIndex`
0058     //  alias.
0059     template <template <std::size_t> class KeyAtIndex, typename Key>
0060     struct find_pred {
0061         template <typename Index>
0062         auto operator()(Index const&) const -> decltype(
0063             hana::equal(std::declval<KeyAtIndex<Index::value>>(),
0064                         std::declval<Key>())
0065         );
0066     };
0067
0068     template <typename Indices, typename Key, template <std::size_t> class KeyAtIndex>
0069     struct find_index_impl {
0070         using type = decltype(hana::find_if(Indices{}, find_pred<KeyAtIndex, Key>{}));
0071     };
0072
0073     // This is a peephole optimization for buckets that have a single entry.
0074     // It provides a nice speedup in the at_key.number_of_lookups benchmark.
0075     // It is perhaps possible to make this part of `find_if` itself, but we
0076     // should make sure that we retain that speedup.
0077     template <std::size_t i, typename Key, template <std::size_t> class KeyAtIndex>
0078     struct find_index_impl<std::index_sequence<i>, Key, KeyAtIndex> {
0079         using Equal = decltype(
0080             hana::equal(std::declval<KeyAtIndex<i>>(),
0081                         std::declval<Key>())
0082         );
0083         using type = typename std::conditional<Equal::value,
0084             hana::optional<std::integral_constant<std::size_t, i>>,
0085             hana::optional<>
0086         >::type;
0087     };
0088
0089     template <typename Map, typename Key, template <std::size_t> class KeyAtIndex>
0090     struct find_index {
0091         using Indices = typename find_indices<Map, Key>::type;
0092         using type = typename find_index_impl<Indices, Key, KeyAtIndex>::type;
0093     };
0094     // end find_index
0095
0096     // bucket_insert:
0097     //  Inserts the given `Index` into the bucket of the `Map` in which `Key` falls.
0098     template <typename Bucket, typename Hash, std::size_t Index>
0099     struct update_bucket {
0100         using type = Bucket;
0101     };
0102
0103     template <std::size_t ...i, typename Hash, std::size_t Index>
0104     struct update_bucket<bucket<Hash, i...>, Hash, Index> {
0105         using type = bucket<Hash, i..., Index>;
0106     };
0107
0108     template <typename Map, typename Key, std::size_t Index, bool =
0109         (find_indices<Map, Key>::type::size() > 0)
0110     >
0111     struct bucket_insert;
0112
0113     template <typename ...Buckets, typename Key, std::size_t Index>
0114     struct bucket_insert<hash_table<Buckets...>, Key, Index, true> {
0115         // There is a bucket for that Hash; append the new index to it.
0116         using Hash = typename decltype(hana::hash(std::declval<Key>()))::type;
0117         using type = hash_table<typename update_bucket<Buckets, Hash, Index>::type...>;
0118     };
0119
0120     template <typename ...Buckets, typename Key, std::size_t Index>
0121     struct bucket_insert<hash_table<Buckets...>, Key, Index, false> {
0122         // There is no bucket for that Hash; insert a new bucket.
0123         using Hash = typename decltype(hana::hash(std::declval<Key>()))::type;
0124         using type = hash_table<Buckets..., bucket<Hash, Index>>;
0125     };
0126     // end bucket_insert
0127
0128     // make_hash_table:
0129     //  Creates a `hash_table` type able of holding the given number of
0130     //  elements. The type of the key associated to any given index must
0131     //  be retrievable using the `KeyAtIndex` alias. All the keys must
0132     //  be distinct and have different hashes too.
0133     template <template <std::size_t> class KeyAtIndex, std::size_t N,
0134               typename Indices = std::make_index_sequence<N>>
0135     struct make_hash_table;
0136
0137     template <template <std::size_t> class KeyAtIndex, std::size_t N, std::size_t ...i>
0138     struct make_hash_table<KeyAtIndex, N, std::index_sequence<i...>> {
0139         using type = hash_table<
0140             bucket<typename decltype(hana::hash(std::declval<KeyAtIndex<i>>()))::type, i>...
0141         >;
0142     };
0143 } }} // end namespace boost::hana
0144
0145 #endif // !BOOST_HANA_DETAIL_HASH_TABLE_HPP