Statistics
| Revision:

root / tmp / org.txm.statsengine.r.core.win32 / res / win32 / library / BH / include / boost / asio / detail / hash_map.hpp @ 2486

History | View | Annotate | Download (8.1 kB)

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