1 //
2 // detail/hash_map.hpp
3 // ~~~~~~~~~~~~~~~~~~~
4 //
5 // Copyright (c) 2003-2021 Christopher M. Kohlhoff (chris at kohlhoff dot com)
6 //
7 // Distributed under the Boost Software License, Version 1.0. (See accompanying
8 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
9 //
10
11 #ifndef BOOST_ASIO_DETAIL_HASH_MAP_HPP
12 #define BOOST_ASIO_DETAIL_HASH_MAP_HPP
13
14 #if defined(_MSC_VER) && (_MSC_VER >= 1200)
15 # pragma once
16 #endif // defined(_MSC_VER) && (_MSC_VER >= 1200)
17
18 #include <boost/asio/detail/config.hpp>
19 #include <list>
20 #include <utility>
21 #include <boost/asio/detail/assert.hpp>
22 #include <boost/asio/detail/noncopyable.hpp>
23
24 #if defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
25 # include <boost/asio/detail/socket_types.hpp>
26 #endif // defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
27
28 #include <boost/asio/detail/push_options.hpp>
29
30 namespace boost {
31 namespace asio {
32 namespace detail {
33
calculate_hash_value(int i)34 inline std::size_t calculate_hash_value(int i)
35 {
36 return static_cast<std::size_t>(i);
37 }
38
calculate_hash_value(void * p)39 inline std::size_t calculate_hash_value(void* p)
40 {
41 return reinterpret_cast<std::size_t>(p)
42 + (reinterpret_cast<std::size_t>(p) >> 3);
43 }
44
45 #if defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
calculate_hash_value(SOCKET s)46 inline std::size_t calculate_hash_value(SOCKET s)
47 {
48 return static_cast<std::size_t>(s);
49 }
50 #endif // defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
51
52 // Note: assumes K and V are POD types.
53 template <typename K, typename V>
54 class hash_map
55 : private noncopyable
56 {
57 public:
58 // The type of a value in the map.
59 typedef std::pair<K, V> value_type;
60
61 // The type of a non-const iterator over the hash map.
62 typedef typename std::list<value_type>::iterator iterator;
63
64 // The type of a const iterator over the hash map.
65 typedef typename std::list<value_type>::const_iterator const_iterator;
66
67 // Constructor.
hash_map()68 hash_map()
69 : size_(0),
70 buckets_(0),
71 num_buckets_(0)
72 {
73 }
74
75 // Destructor.
~hash_map()76 ~hash_map()
77 {
78 delete[] buckets_;
79 }
80
81 // Get an iterator for the beginning of the map.
begin()82 iterator begin()
83 {
84 return values_.begin();
85 }
86
87 // Get an iterator for the beginning of the map.
begin() const88 const_iterator begin() const
89 {
90 return values_.begin();
91 }
92
93 // Get an iterator for the end of the map.
end()94 iterator end()
95 {
96 return values_.end();
97 }
98
99 // Get an iterator for the end of the map.
end() const100 const_iterator end() const
101 {
102 return values_.end();
103 }
104
105 // Check whether the map is empty.
empty() const106 bool empty() const
107 {
108 return values_.empty();
109 }
110
111 // Find an entry in the map.
find(const K & k)112 iterator find(const K& k)
113 {
114 if (num_buckets_)
115 {
116 size_t bucket = calculate_hash_value(k) % num_buckets_;
117 iterator it = buckets_[bucket].first;
118 if (it == values_.end())
119 return values_.end();
120 iterator end_it = buckets_[bucket].last;
121 ++end_it;
122 while (it != end_it)
123 {
124 if (it->first == k)
125 return it;
126 ++it;
127 }
128 }
129 return values_.end();
130 }
131
132 // Find an entry in the map.
find(const K & k) const133 const_iterator find(const K& k) const
134 {
135 if (num_buckets_)
136 {
137 size_t bucket = calculate_hash_value(k) % num_buckets_;
138 const_iterator it = buckets_[bucket].first;
139 if (it == values_.end())
140 return it;
141 const_iterator end_it = buckets_[bucket].last;
142 ++end_it;
143 while (it != end_it)
144 {
145 if (it->first == k)
146 return it;
147 ++it;
148 }
149 }
150 return values_.end();
151 }
152
153 // Insert a new entry into the map.
insert(const value_type & v)154 std::pair<iterator, bool> insert(const value_type& v)
155 {
156 if (size_ + 1 >= num_buckets_)
157 rehash(hash_size(size_ + 1));
158 size_t bucket = calculate_hash_value(v.first) % num_buckets_;
159 iterator it = buckets_[bucket].first;
160 if (it == values_.end())
161 {
162 buckets_[bucket].first = buckets_[bucket].last =
163 values_insert(values_.end(), v);
164 ++size_;
165 return std::pair<iterator, bool>(buckets_[bucket].last, true);
166 }
167 iterator end_it = buckets_[bucket].last;
168 ++end_it;
169 while (it != end_it)
170 {
171 if (it->first == v.first)
172 return std::pair<iterator, bool>(it, false);
173 ++it;
174 }
175 buckets_[bucket].last = values_insert(end_it, v);
176 ++size_;
177 return std::pair<iterator, bool>(buckets_[bucket].last, true);
178 }
179
180 // Erase an entry from the map.
erase(iterator it)181 void erase(iterator it)
182 {
183 BOOST_ASIO_ASSERT(it != values_.end());
184 BOOST_ASIO_ASSERT(num_buckets_ != 0);
185
186 size_t bucket = calculate_hash_value(it->first) % num_buckets_;
187 bool is_first = (it == buckets_[bucket].first);
188 bool is_last = (it == buckets_[bucket].last);
189 if (is_first && is_last)
190 buckets_[bucket].first = buckets_[bucket].last = values_.end();
191 else if (is_first)
192 ++buckets_[bucket].first;
193 else if (is_last)
194 --buckets_[bucket].last;
195
196 values_erase(it);
197 --size_;
198 }
199
200 // Erase a key from the map.
erase(const K & k)201 void erase(const K& k)
202 {
203 iterator it = find(k);
204 if (it != values_.end())
205 erase(it);
206 }
207
208 // Remove all entries from the map.
clear()209 void clear()
210 {
211 // Clear the values.
212 values_.clear();
213 size_ = 0;
214
215 // Initialise all buckets to empty.
216 iterator end_it = values_.end();
217 for (size_t i = 0; i < num_buckets_; ++i)
218 buckets_[i].first = buckets_[i].last = end_it;
219 }
220
221 private:
222 // Calculate the hash size for the specified number of elements.
hash_size(std::size_t num_elems)223 static std::size_t hash_size(std::size_t num_elems)
224 {
225 static std::size_t sizes[] =
226 {
227 #if defined(BOOST_ASIO_HASH_MAP_BUCKETS)
228 BOOST_ASIO_HASH_MAP_BUCKETS
229 #else // BOOST_ASIO_HASH_MAP_BUCKETS
230 3, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
231 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
232 12582917, 25165843
233 #endif // BOOST_ASIO_HASH_MAP_BUCKETS
234 };
235 const std::size_t nth_size = sizeof(sizes) / sizeof(std::size_t) - 1;
236 for (std::size_t i = 0; i < nth_size; ++i)
237 if (num_elems < sizes[i])
238 return sizes[i];
239 return sizes[nth_size];
240 }
241
242 // Re-initialise the hash from the values already contained in the list.
rehash(std::size_t num_buckets)243 void rehash(std::size_t num_buckets)
244 {
245 if (num_buckets == num_buckets_)
246 return;
247 BOOST_ASIO_ASSERT(num_buckets != 0);
248
249 iterator end_iter = values_.end();
250
251 // Update number of buckets and initialise all buckets to empty.
252 bucket_type* tmp = new bucket_type[num_buckets];
253 delete[] buckets_;
254 buckets_ = tmp;
255 num_buckets_ = num_buckets;
256 for (std::size_t i = 0; i < num_buckets_; ++i)
257 buckets_[i].first = buckets_[i].last = end_iter;
258
259 // Put all values back into the hash.
260 iterator iter = values_.begin();
261 while (iter != end_iter)
262 {
263 std::size_t bucket = calculate_hash_value(iter->first) % num_buckets_;
264 if (buckets_[bucket].last == end_iter)
265 {
266 buckets_[bucket].first = buckets_[bucket].last = iter++;
267 }
268 else if (++buckets_[bucket].last == iter)
269 {
270 ++iter;
271 }
272 else
273 {
274 values_.splice(buckets_[bucket].last, values_, iter++);
275 --buckets_[bucket].last;
276 }
277 }
278 }
279
280 // Insert an element into the values list by splicing from the spares list,
281 // if a spare is available, and otherwise by inserting a new element.
values_insert(iterator it,const value_type & v)282 iterator values_insert(iterator it, const value_type& v)
283 {
284 if (spares_.empty())
285 {
286 return values_.insert(it, v);
287 }
288 else
289 {
290 spares_.front() = v;
291 values_.splice(it, spares_, spares_.begin());
292 return --it;
293 }
294 }
295
296 // Erase an element from the values list by splicing it to the spares list.
values_erase(iterator it)297 void values_erase(iterator it)
298 {
299 *it = value_type();
300 spares_.splice(spares_.begin(), values_, it);
301 }
302
303 // The number of elements in the hash.
304 std::size_t size_;
305
306 // The list of all values in the hash map.
307 std::list<value_type> values_;
308
309 // The list of spare nodes waiting to be recycled. Assumes that POD types only
310 // are stored in the hash map.
311 std::list<value_type> spares_;
312
313 // The type for a bucket in the hash table.
314 struct bucket_type
315 {
316 iterator first;
317 iterator last;
318 };
319
320 // The buckets in the hash.
321 bucket_type* buckets_;
322
323 // The number of buckets in the hash.
324 std::size_t num_buckets_;
325 };
326
327 } // namespace detail
328 } // namespace asio
329 } // namespace boost
330
331 #include <boost/asio/detail/pop_options.hpp>
332
333 #endif // BOOST_ASIO_DETAIL_HASH_MAP_HPP
334