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
//
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 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

    
34
inline std::size_t calculate_hash_value(int i)
35
{
36
  return static_cast<std::size_t>(i);
37
}
38

    
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__)
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.
68
  hash_map()
69
    : size_(0),
70
      buckets_(0),
71
      num_buckets_(0)
72
  {
73
  }
74

    
75
  // Destructor.
76
  ~hash_map()
77
  {
78
    delete[] buckets_;
79
  }
80

    
81
  // Get an iterator for the beginning of the map.
82
  iterator begin()
83
  {
84
    return values_.begin();
85
  }
86

    
87
  // Get an iterator for the beginning of the map.
88
  const_iterator begin() const
89
  {
90
    return values_.begin();
91
  }
92

    
93
  // Get an iterator for the end of the map.
94
  iterator end()
95
  {
96
    return values_.end();
97
  }
98

    
99
  // Get an iterator for the end of the map.
100
  const_iterator end() const
101
  {
102
    return values_.end();
103
  }
104

    
105
  // Check whether the map is empty.
106
  bool empty() const
107
  {
108
    return values_.empty();
109
  }
110

    
111
  // Find an entry in the map.
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.
133
  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.
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.
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.
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.
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.
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.
243
  void rehash(std::size_t num_buckets)
244
  {
245
    if (num_buckets == num_buckets_)
246
      return;
247
    num_buckets_ = num_buckets;
248
    BOOST_ASIO_ASSERT(num_buckets_ != 0);
249

    
250
    iterator end_iter = values_.end();
251

    
252
    // Update number of buckets and initialise all buckets to empty.
253
    bucket_type* tmp = new bucket_type[num_buckets_];
254
    delete[] buckets_;
255
    buckets_ = tmp;
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.
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.
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