Line data Source code
1 : // Author(s): Maurice Laveaux
2 : // Copyright: see the accompanying file COPYING or copy at
3 : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4 : //
5 : // Distributed under the Boost Software License, Version 1.0.
6 : // (See accompanying file LICENSE_1_0.txt or copy at
7 : // http://www.boost.org/LICENSE_1_0.txt)
8 :
9 : #ifndef MCRL2_UTILITIES_UNORDERED_MAP_H
10 : #define MCRL2_UTILITIES_UNORDERED_MAP_H
11 :
12 : #include <utility>
13 : #include <functional>
14 : #include "mcrl2/utilities/unordered_set.h"
15 :
16 :
17 : namespace mcrl2::utilities
18 : {
19 :
20 : /// \brief A class for a map of keys to values in T based using the simple hash table set implementation.
21 : template<typename Key,
22 : typename T,
23 : typename Hash,
24 : typename KeyEqual,
25 : typename Allocator,
26 : bool ThreadSafe,
27 : bool Resize>
28 : class unordered_map
29 : {
30 : public:
31 : using key_type = Key;
32 : using mapped_type = T;
33 : using value_type = std::pair<const Key, T>;
34 : typedef value_type node_type;
35 : using size_type = std::size_t;
36 : using difference_type = std::ptrdiff_t;
37 :
38 : using hasher = Hash;
39 : using key_equal = KeyEqual;
40 : using allocator_type = typename std::allocator_traits<Allocator>::template rebind_alloc<value_type>;
41 :
42 : using reference = value_type&;
43 : using const_reference = const value_type&;
44 : using pointer = typename std::allocator_traits<Allocator>::pointer;
45 : using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
46 :
47 : private:
48 : /// \brief True iff the hash and equals functions allow transparent lookup,
49 : static constexpr bool allow_transparent = detail::is_transparent<Hash>() && detail::is_transparent<KeyEqual>();
50 :
51 : // Hashes only the keys of each pair.
52 : struct PairHash
53 : {
54 : using is_transparent = void;
55 :
56 : PairHash() = default;
57 :
58 22515 : explicit PairHash(const hasher& hash)
59 : : hash(hash)
60 22515 : {}
61 :
62 : hasher hash;
63 :
64 19605 : std::size_t operator()(const value_type& pair) const
65 : {
66 19605 : return hash(pair.first);
67 : }
68 :
69 : template<typename U, typename ...V, typename = std::enable_if_t<!std::is_same_v<U, std::pair<Key, T>>>>
70 858105 : std::size_t operator()(const U& key, const V&... /* args */) const
71 : {
72 858105 : return hash(key);
73 : }
74 : };
75 :
76 : // Compares only the keys of each pair.
77 : struct PairEquals
78 : {
79 : using is_transparent = void;
80 :
81 : PairEquals() = default;
82 :
83 22515 : explicit PairEquals(const key_equal& equals)
84 : : equals(equals)
85 22515 : {}
86 :
87 : key_equal equals;
88 :
89 10805 : bool operator()(const value_type& first, const value_type& second) const
90 : {
91 10805 : return equals(first.first, second.first);
92 : }
93 :
94 : template <typename U, typename...V, typename = std::enable_if_t<!std::is_same_v<U, std::pair<Key, T>>>>
95 585245 : bool operator()(const value_type& first, const U& key, const V&... /* args */) const
96 : {
97 585245 : return equals(first.first, key);
98 : }
99 : };
100 :
101 : using Set = unordered_set<value_type, PairHash, PairEquals, allocator_type, ThreadSafe, Resize>;
102 : using bucket_type = typename Set::bucket_type;
103 :
104 : Set m_set; ///< The underlying set storing <key, value> pairs.
105 :
106 : public:
107 : using iterator = typename Set::template unordered_set_iterator<bucket_type, false>;
108 : using const_iterator = typename Set::const_iterator;
109 : using local_iterator = typename bucket_type::iterator;
110 : using const_local_iterator = typename Set::const_local_iterator;
111 : typedef typename std::pair<unordered_map::iterator, bool> insert_return_type;
112 :
113 22514 : unordered_map()
114 22514 : : m_set(0, PairHash(hasher()), PairEquals(key_equal()))
115 22514 : {}
116 :
117 : /// \brief Constructs an unordered_map that can store initial_size number of elements before resizing.
118 1 : unordered_map(std::size_t initial_size,
119 : const hasher& hash = hasher(),
120 : const key_equal& equals = key_equal())
121 1 : : m_set(initial_size, PairHash(hash), PairEquals(equals))
122 1 : {}
123 :
124 : /// \returns A reference to the local node allocator.
125 : const allocator_type& get_allocator() const noexcept { return m_set.get_allocator(); }
126 : allocator_type& get_allocator() noexcept { return m_set.get_allocator(); }
127 :
128 364 : iterator begin() { return m_set.begin(); }
129 1459170 : iterator end() { return m_set.end(); }
130 :
131 285 : const_iterator begin() const { return m_set.begin(); }
132 25630 : const_iterator end() const { return m_set.end(); }
133 :
134 : const_iterator cbegin() const { return m_set.begin(); }
135 : const_iterator cend() const { return m_set.end(); }
136 :
137 : /// \returns True iff the set is empty.
138 88648 : bool empty() const noexcept { return m_set.empty(); }
139 :
140 : /// \returns The number of elements.
141 106149 : size_type size() const { return m_set.size(); }
142 : size_type max_size() const noexcept { return m_set.max_size(); }
143 :
144 : /// \brief Clears the content.
145 : void clear() { m_set.clear(); }
146 :
147 : /// \brief Inserts elements.
148 4271 : std::pair<iterator, bool> insert(const value_type& pair) { auto[x, y] = m_set.emplace(pair); return std::make_pair(iterator(x), y); }
149 :
150 : std::pair<iterator, bool> insert(const_iterator hint, const value_type& pair) { return insert(hint, pair); }
151 :
152 : template<typename ...Args>
153 101296 : std::pair<iterator, bool> emplace(Args&&... args) { auto[x, y] = m_set.emplace(std::forward<Args>(args)...); return std::make_pair(iterator(x), y); }
154 :
155 : template<typename ...Args>
156 : iterator emplace_hint(const_iterator /*hint*/, Args&&... args) { return emplace(std::forward<Args>(args)...); }
157 :
158 : template<typename ...Args>
159 : std::pair<iterator, bool> try_emplace(const key_type& key, Args&&... args);
160 :
161 : template< class... Args >
162 : iterator try_emplace(const_iterator /*hint*/, const Key& k, Args&&... args) { return try_emplace(k, std::forward<Args>(args)...); }
163 :
164 : template< class... Args >
165 : iterator try_emplace(const_iterator /*hint*/, Key&& k, Args&&... args) { return try_emplace(std::forward<Key>(k), std::forward<Args>(args)...); }
166 :
167 : template <typename M>
168 : std::pair<iterator, bool> insert_or_assign(Key&& k, M&& obj)
169 : {
170 : auto it = find(k);
171 : if (it != end())
172 : {
173 : *it = obj;
174 : return std::make_pair(it, true);
175 : }
176 : else
177 : {
178 : return emplace(std::forward<Key>(obj), std::forward<M>(obj));
179 : }
180 : }
181 :
182 : template <typename M>
183 : std::pair<iterator, bool> insert_or_assign(const Key& k, M&& obj) { return insert_or_emplace(k, std::forward<M>(obj)); }
184 :
185 : template <typename M>
186 : std::pair<iterator, bool> insert_or_assign(const_iterator /* hint */, const Key& k, M&& obj) { return insert_or_emplace(k, std::forward<M>(obj)); }
187 :
188 : template <typename M>
189 : std::pair<iterator, bool> insert_or_assign(const_iterator /* hint */, Key&& k, M&& obj) { return insert_or_emplace(k, std::forward<M>(obj)); }
190 :
191 : /// \brief Erases elements.
192 : void erase(const key_type& key) { const_iterator it = m_set.find(key); m_set.erase(it); }
193 172646 : iterator erase(const_iterator it) { return m_set.erase(it); }
194 :
195 : /// \brief Provides access to the value associated with the given key.
196 : const T& at(const key_type& key) const;
197 :
198 : /// \brief Provides access to the value associated with the given key, constructs a default
199 : /// value whenever the key was undefined.
200 : mapped_type& operator[](const key_type& key);
201 :
202 : /// \returns The number of elements matching the specified key.
203 : size_type count(const key_type& key) const { return m_set.count(key); }
204 :
205 : /// \returns Element with the specified key.
206 : template<typename ...Args>
207 1458802 : iterator find(const Args&... args) { return m_set.find(args...); }
208 :
209 : template<typename ...Args>
210 25345 : const_iterator find(const Args&... args) const { return m_set.find(args...); }
211 :
212 : /// \returns An iterator to the elements in the given bucket with index n.
213 : local_iterator begin(size_type n) { return m_set.begin(n); }
214 : local_iterator end(size_type n) { return m_set.end(n); }
215 :
216 : const_local_iterator begin(size_type n) const { return m_set.begin(n); }
217 : const_local_iterator end(size_type n) const { return m_set.end(n); }
218 :
219 : const_local_iterator cbegin(size_type n) const { return m_set.begin(n); }
220 : const_local_iterator cend(size_type n) const { return m_set.end(n); }
221 :
222 : /// \returns The number of buckets.
223 207016 : size_type bucket_count() const noexcept { return m_set.bucket_count(); }
224 : size_type max_bucket_count() const noexcept { return m_set.max_bucket_count(); }
225 :
226 : size_type bucket_size(size_type n) const noexcept { return m_set.bucket_size(n); }
227 : size_type bucket(const key_type& key) const noexcept { return m_set.bucket(key); }
228 :
229 103508 : float load_factor() const { return static_cast<float>(size()) / bucket_count(); }
230 103508 : float max_load_factor() const { return m_set.max_load_factor(); }
231 : void max_load_factor(float factor) { m_set.max_load_factor(factor); }
232 :
233 : /// \brief Resize the number buckets to at least number_of_buckets.
234 547 : void rehash(size_type number_of_buckets)
235 : {
236 547 : m_set.rehash(number_of_buckets);
237 547 : }
238 :
239 : /// \brief Resizes the set to the given number of elements.
240 : void reserve(size_type count) { rehash(std::ceil(static_cast<float>(count) / max_load_factor())); }
241 :
242 : hasher hash_function() const { return m_set.hash_function(); }
243 : key_equal key_eq() const { return m_set.key_eq(); }
244 :
245 : /// \brief Number of elements that can be stored before rehash.
246 : /// \details Nonstandard.
247 1 : size_type capacity() { return m_set.capacity(); }
248 : };
249 :
250 : /// \brief A specialization for large unordered maps that uses the block_allocator internally by default.
251 : template<typename Key,
252 : typename T,
253 : typename Hash = std::hash<Key>,
254 : typename Equals = std::equal_to<Key>,
255 : typename Allocator = mcrl2::utilities::block_allocator<Key>,
256 : bool ThreadSafe = false,
257 : bool Resize = true>
258 : using unordered_map_large = unordered_map<Key, T, Hash, Equals, Allocator, ThreadSafe, Resize>;
259 :
260 : } // namespace mcrl2::utilities
261 :
262 : #include "mcrl2/utilities/detail/unordered_map_implementation.h"
263 :
264 : #endif // MCRL2_UTILITIES_UNORDERED_MAP_H
|
