1/*!
2@file
3Defines `boost::hana::detail::hash_table`.
4
5Copyright Louis Dionne 2016
6Copyright Jason Rice 2016
7Distributed 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
30namespace boost { namespace hana { 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} }} // end namespace boost::hana
144
145#endif // !BOOST_HANA_DETAIL_HASH_TABLE_HPP
146

source code of boost/libs/hana/include/boost/hana/detail/hash_table.hpp