← Back to branch summary

~ubuntu-branches/ubuntu/maverick/libtorrent-rasterbar/maverick

« back to all changes in this revision

Viewing changes to include/libtorrent/asio/detail/hash_map.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Christophe Sauthier
  • Date: 2010-08-10 12:59:37 UTC
  • mfrom: (1.3.7 upstream)
  • Revision ID: james.westby@ubuntu.com-20100810125937-jbcmmf17y8yo9hgz
Tags: 0.15.0-0ubuntu1
* New upstream version.
* debian/patches/100_fix_html_docs.patch: refreshed.
* debian/control: bump up standards-version to 3.9.1 (no changes).

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/libtorrent/asio/detail/hash_map.hpp
1
 
//
2
 
// hash_map.hpp
3
 
// ~~~~~~~~~~~~
4
 
//
5
 
// Copyright (c) 2003-2008 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
 
#if defined(_MSC_VER) && (_MSC_VER >= 1200)
15
 
# pragma once
16
 
#endif // defined(_MSC_VER) && (_MSC_VER >= 1200)
17
 
 
18
 
#include "asio/detail/push_options.hpp"
19
 
 
20
 
#include "asio/detail/push_options.hpp"
21
 
#include <cassert>
22
 
#include <list>
23
 
#include <utility>
24
 
#include <boost/functional/hash.hpp>
25
 
#include "asio/detail/pop_options.hpp"
26
 
 
27
 
#include "asio/detail/noncopyable.hpp"
28
 
#include "asio/detail/socket_types.hpp"
29
 
 
30
 
namespace asio {
31
 
namespace detail {
32
 
 
33
 
template <typename T>
34
 
inline std::size_t calculate_hash_value(const T& t)
35
 
{
36
 
  return boost::hash_value(t);
37
 
}
38
 
 
39
 
#if defined(_WIN64)
40
 
inline std::size_t calculate_hash_value(SOCKET s)
41
 
{
42
 
  return static_cast<std::size_t>(s);
43
 
}
44
 
#endif // defined(_WIN64)
45
 
 
46
 
// Note: assumes K and V are POD types.
47
 
template <typename K, typename V>
48
 
class hash_map
49
 
  : private noncopyable
50
 
{
51
 
public:
52
 
  // The type of a value in the map.
53
 
  typedef std::pair<K, V> value_type;
54
 
 
55
 
  // The type of a non-const iterator over the hash map.
56
 
  typedef typename std::list<value_type>::iterator iterator;
57
 
 
58
 
  // The type of a const iterator over the hash map.
59
 
  typedef typename std::list<value_type>::const_iterator const_iterator;
60
 
 
61
 
  // Constructor.
62
 
  hash_map()
63
 
  {
64
 
    // Initialise all buckets to empty.
65
 
    for (size_t i = 0; i < num_buckets; ++i)
66
 
      buckets_[i].first = buckets_[i].last = values_.end();
67
 
  }
68
 
 
69
 
  // Get an iterator for the beginning of the map.
70
 
  iterator begin()
71
 
  {
72
 
    return values_.begin();
73
 
  }
74
 
 
75
 
  // Get an iterator for the beginning of the map.
76
 
  const_iterator begin() const
77
 
  {
78
 
    return values_.begin();
79
 
  }
80
 
 
81
 
  // Get an iterator for the end of the map.
82
 
  iterator end()
83
 
  {
84
 
    return values_.end();
85
 
  }
86
 
 
87
 
  // Get an iterator for the end of the map.
88
 
  const_iterator end() const
89
 
  {
90
 
    return values_.end();
91
 
  }
92
 
 
93
 
  // Check whether the map is empty.
94
 
  bool empty() const
95
 
  {
96
 
    return values_.empty();
97
 
  }
98
 
 
99
 
  // Find an entry in the map.
100
 
  iterator find(const K& k)
101
 
  {
102
 
    size_t bucket = calculate_hash_value(k) % num_buckets;
103
 
    iterator it = buckets_[bucket].first;
104
 
    if (it == values_.end())
105
 
      return values_.end();
106
 
    iterator end = buckets_[bucket].last;
107
 
    ++end;
108
 
    while (it != end)
109
 
    {
110
 
      if (it->first == k)
111
 
        return it;
112
 
      ++it;
113
 
    }
114
 
    return values_.end();
115
 
  }
116
 
 
117
 
  // Find an entry in the map.
118
 
  const_iterator find(const K& k) const
119
 
  {
120
 
    size_t bucket = calculate_hash_value(k) % num_buckets;
121
 
    const_iterator it = buckets_[bucket].first;
122
 
    if (it == values_.end())
123
 
      return it;
124
 
    const_iterator end = buckets_[bucket].last;
125
 
    ++end;
126
 
    while (it != end)
127
 
    {
128
 
      if (it->first == k)
129
 
        return it;
130
 
      ++it;
131
 
    }
132
 
    return values_.end();
133
 
  }
134
 
 
135
 
  // Insert a new entry into the map.
136
 
  std::pair<iterator, bool> insert(const value_type& v)
137
 
  {
138
 
    size_t bucket = calculate_hash_value(v.first) % num_buckets;
139
 
    iterator it = buckets_[bucket].first;
140
 
    if (it == values_.end())
141
 
    {
142
 
      buckets_[bucket].first = buckets_[bucket].last =
143
 
        values_insert(values_.end(), v);
144
 
      return std::pair<iterator, bool>(buckets_[bucket].last, true);
145
 
    }
146
 
    iterator end = buckets_[bucket].last;
147
 
    ++end;
148
 
    while (it != end)
149
 
    {
150
 
      if (it->first == v.first)
151
 
        return std::pair<iterator, bool>(it, false);
152
 
      ++it;
153
 
    }
154
 
    buckets_[bucket].last = values_insert(end, v);
155
 
    return std::pair<iterator, bool>(buckets_[bucket].last, true);
156
 
  }
157
 
 
158
 
  // Erase an entry from the map.
159
 
  void erase(iterator it)
160
 
  {
161
 
    assert(it != values_.end());
162
 
 
163
 
    size_t bucket = calculate_hash_value(it->first) % num_buckets;
164
 
    bool is_first = (it == buckets_[bucket].first);
165
 
    bool is_last = (it == buckets_[bucket].last);
166
 
    if (is_first && is_last)
167
 
      buckets_[bucket].first = buckets_[bucket].last = values_.end();
168
 
    else if (is_first)
169
 
      ++buckets_[bucket].first;
170
 
    else if (is_last)
171
 
      --buckets_[bucket].last;
172
 
 
173
 
    values_erase(it);
174
 
  }
175
 
 
176
 
  // Remove all entries from the map.
177
 
  void clear()
178
 
  {
179
 
    // Clear the values.
180
 
    values_.clear();
181
 
 
182
 
    // Initialise all buckets to empty.
183
 
    for (size_t i = 0; i < num_buckets; ++i)
184
 
      buckets_[i].first = buckets_[i].last = values_.end();
185
 
  }
186
 
 
187
 
private:
188
 
  // Insert an element into the values list by splicing from the spares list,
189
 
  // if a spare is available, and otherwise by inserting a new element.
190
 
  iterator values_insert(iterator it, const value_type& v)
191
 
  {
192
 
    if (spares_.empty())
193
 
    {
194
 
      return values_.insert(it, v);
195
 
    }
196
 
    else
197
 
    {
198
 
      spares_.front() = v;
199
 
      values_.splice(it, spares_, spares_.begin());
200
 
      return --it;
201
 
    }
202
 
  }
203
 
 
204
 
  // Erase an element from the values list by splicing it to the spares list.
205
 
  void values_erase(iterator it)
206
 
  {
207
 
    *it = value_type();
208
 
    spares_.splice(spares_.begin(), values_, it);
209
 
  }
210
 
 
211
 
  // The list of all values in the hash map.
212
 
  std::list<value_type> values_;
213
 
 
214
 
  // The list of spare nodes waiting to be recycled. Assumes that POD types only
215
 
  // are stored in the hash map.
216
 
  std::list<value_type> spares_;
217
 
 
218
 
  // The type for a bucket in the hash table.
219
 
  struct bucket_type
220
 
  {
221
 
    iterator first;
222
 
    iterator last;
223
 
  };
224
 
 
225
 
  // The number of buckets in the hash.
226
 
  enum { num_buckets = 1021 };
227
 
 
228
 
  // The buckets in the hash.
229
 
  bucket_type buckets_[num_buckets];
230
 
};
231
 
 
232
 
} // namespace detail
233
 
} // namespace asio
234
 
 
235
 
#include "asio/detail/pop_options.hpp"
236
 
 
237
 
#endif // ASIO_DETAIL_HASH_MAP_HPP