]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |