ceph/src/boost/boost/hana/detail/hash_table.hpp

   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