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