]>
Commit | Line | Data |
---|---|---|
b82f782b BK |
1 | // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*- |
2 | ||
e133ace8 | 3 | // Copyright (C) 2007 Free Software Foundation, Inc. |
b82f782b BK |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 2, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License along | |
17 | // with this library; see the file COPYING. If not, write to the Free | |
18 | // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, | |
19 | // USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free software | |
22 | // library without restriction. Specifically, if other files instantiate | |
23 | // templates or use macros or inline functions from this file, or you compile | |
24 | // this file and link it with other files to produce an executable, this | |
25 | // file does not by itself cause the resulting executable to be covered by | |
26 | // the GNU General Public License. This exception does not however | |
27 | // invalidate any other reasons why the executable file might be covered by | |
28 | // the GNU General Public License. | |
29 | ||
e133ace8 PC |
30 | /** @file tr1_impl/hashtable_policy.h |
31 | * This is an internal header file, included by other library headers. | |
32 | * You should not attempt to use it directly. | |
b82f782b BK |
33 | */ |
34 | ||
b82f782b BK |
35 | namespace std |
36 | { | |
e133ace8 PC |
37 | _GLIBCXX_BEGIN_NAMESPACE_TR1 |
38 | ||
95cefe5f | 39 | namespace __detail |
b82f782b | 40 | { |
b82f782b BK |
41 | // Helper function: return distance(first, last) for forward |
42 | // iterators, or 0 for input iterators. | |
95cefe5f PC |
43 | template<class _Iterator> |
44 | inline typename std::iterator_traits<_Iterator>::difference_type | |
45 | __distance_fw(_Iterator __first, _Iterator __last, | |
46 | std::input_iterator_tag) | |
b82f782b BK |
47 | { return 0; } |
48 | ||
95cefe5f PC |
49 | template<class _Iterator> |
50 | inline typename std::iterator_traits<_Iterator>::difference_type | |
51 | __distance_fw(_Iterator __first, _Iterator __last, | |
52 | std::forward_iterator_tag) | |
53 | { return std::distance(__first, __last); } | |
b82f782b | 54 | |
95cefe5f PC |
55 | template<class _Iterator> |
56 | inline typename std::iterator_traits<_Iterator>::difference_type | |
57 | __distance_fw(_Iterator __first, _Iterator __last) | |
b82f782b | 58 | { |
95cefe5f PC |
59 | typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; |
60 | return __distance_fw(__first, __last, _Tag()); | |
b82f782b BK |
61 | } |
62 | ||
b82f782b | 63 | |
95cefe5f | 64 | // Auxiliary types used for all instantiations of _Hashtable: nodes |
b82f782b BK |
65 | // and iterators. |
66 | ||
67 | // Nodes, used to wrap elements stored in the hash table. A policy | |
95cefe5f | 68 | // template parameter of class template _Hashtable controls whether |
b82f782b BK |
69 | // nodes also store a hash code. In some cases (e.g. strings) this |
70 | // may be a performance win. | |
95cefe5f PC |
71 | template<typename _Value, bool __cache_hash_code> |
72 | struct _Hash_node; | |
b82f782b | 73 | |
95cefe5f PC |
74 | template<typename _Value> |
75 | struct _Hash_node<_Value, true> | |
b82f782b | 76 | { |
95cefe5f PC |
77 | _Value _M_v; |
78 | std::size_t _M_hash_code; | |
79 | _Hash_node* _M_next; | |
b82f782b BK |
80 | }; |
81 | ||
95cefe5f PC |
82 | template<typename _Value> |
83 | struct _Hash_node<_Value, false> | |
b82f782b | 84 | { |
95cefe5f PC |
85 | _Value _M_v; |
86 | _Hash_node* _M_next; | |
b82f782b BK |
87 | }; |
88 | ||
89 | // Local iterators, used to iterate within a bucket but not between | |
90 | // buckets. | |
95cefe5f PC |
91 | template<typename _Value, bool __cache> |
92 | struct _Node_iterator_base | |
b82f782b | 93 | { |
95cefe5f PC |
94 | _Node_iterator_base(_Hash_node<_Value, __cache>* __p) |
95 | : _M_cur(__p) { } | |
b82f782b BK |
96 | |
97 | void | |
95cefe5f PC |
98 | _M_incr() |
99 | { _M_cur = _M_cur->_M_next; } | |
b82f782b | 100 | |
95cefe5f | 101 | _Hash_node<_Value, __cache>* _M_cur; |
b82f782b BK |
102 | }; |
103 | ||
95cefe5f | 104 | template<typename _Value, bool __cache> |
b82f782b | 105 | inline bool |
95cefe5f PC |
106 | operator==(const _Node_iterator_base<_Value, __cache>& __x, |
107 | const _Node_iterator_base<_Value, __cache>& __y) | |
108 | { return __x._M_cur == __y._M_cur; } | |
b82f782b | 109 | |
95cefe5f | 110 | template<typename _Value, bool __cache> |
b82f782b | 111 | inline bool |
95cefe5f PC |
112 | operator!=(const _Node_iterator_base<_Value, __cache>& __x, |
113 | const _Node_iterator_base<_Value, __cache>& __y) | |
114 | { return __x._M_cur != __y._M_cur; } | |
b82f782b | 115 | |
95cefe5f PC |
116 | template<typename _Value, bool __constant_iterators, bool __cache> |
117 | struct _Node_iterator | |
118 | : public _Node_iterator_base<_Value, __cache> | |
b82f782b | 119 | { |
95cefe5f PC |
120 | typedef _Value value_type; |
121 | typedef typename | |
122 | __gnu_cxx::__conditional_type<__constant_iterators, | |
123 | const _Value*, _Value*>::__type | |
b82f782b | 124 | pointer; |
95cefe5f PC |
125 | typedef typename |
126 | __gnu_cxx::__conditional_type<__constant_iterators, | |
127 | const _Value&, _Value&>::__type | |
b82f782b BK |
128 | reference; |
129 | typedef std::ptrdiff_t difference_type; | |
130 | typedef std::forward_iterator_tag iterator_category; | |
131 | ||
95cefe5f PC |
132 | _Node_iterator() |
133 | : _Node_iterator_base<_Value, __cache>(0) { } | |
b82f782b BK |
134 | |
135 | explicit | |
95cefe5f PC |
136 | _Node_iterator(_Hash_node<_Value, __cache>* __p) |
137 | : _Node_iterator_base<_Value, __cache>(__p) { } | |
b82f782b BK |
138 | |
139 | reference | |
140 | operator*() const | |
95cefe5f | 141 | { return this->_M_cur->_M_v; } |
b82f782b BK |
142 | |
143 | pointer | |
144 | operator->() const | |
95cefe5f | 145 | { return &this->_M_cur->_M_v; } |
b82f782b | 146 | |
95cefe5f | 147 | _Node_iterator& |
b82f782b BK |
148 | operator++() |
149 | { | |
95cefe5f | 150 | this->_M_incr(); |
b82f782b BK |
151 | return *this; |
152 | } | |
153 | ||
95cefe5f | 154 | _Node_iterator |
b82f782b BK |
155 | operator++(int) |
156 | { | |
95cefe5f PC |
157 | _Node_iterator __tmp(*this); |
158 | this->_M_incr(); | |
159 | return __tmp; | |
b82f782b BK |
160 | } |
161 | }; | |
162 | ||
95cefe5f PC |
163 | template<typename _Value, bool __constant_iterators, bool __cache> |
164 | struct _Node_const_iterator | |
165 | : public _Node_iterator_base<_Value, __cache> | |
b82f782b | 166 | { |
95cefe5f PC |
167 | typedef _Value value_type; |
168 | typedef const _Value* pointer; | |
169 | typedef const _Value& reference; | |
b82f782b BK |
170 | typedef std::ptrdiff_t difference_type; |
171 | typedef std::forward_iterator_tag iterator_category; | |
172 | ||
95cefe5f PC |
173 | _Node_const_iterator() |
174 | : _Node_iterator_base<_Value, __cache>(0) { } | |
b82f782b BK |
175 | |
176 | explicit | |
95cefe5f PC |
177 | _Node_const_iterator(_Hash_node<_Value, __cache>* __p) |
178 | : _Node_iterator_base<_Value, __cache>(__p) { } | |
b82f782b | 179 | |
95cefe5f PC |
180 | _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, |
181 | __cache>& __x) | |
182 | : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } | |
b82f782b BK |
183 | |
184 | reference | |
185 | operator*() const | |
95cefe5f | 186 | { return this->_M_cur->_M_v; } |
b82f782b BK |
187 | |
188 | pointer | |
189 | operator->() const | |
95cefe5f | 190 | { return &this->_M_cur->_M_v; } |
b82f782b | 191 | |
95cefe5f | 192 | _Node_const_iterator& |
b82f782b BK |
193 | operator++() |
194 | { | |
95cefe5f | 195 | this->_M_incr(); |
b82f782b BK |
196 | return *this; |
197 | } | |
198 | ||
95cefe5f | 199 | _Node_const_iterator |
b82f782b BK |
200 | operator++(int) |
201 | { | |
95cefe5f PC |
202 | _Node_const_iterator __tmp(*this); |
203 | this->_M_incr(); | |
204 | return __tmp; | |
b82f782b BK |
205 | } |
206 | }; | |
207 | ||
95cefe5f PC |
208 | template<typename _Value, bool __cache> |
209 | struct _Hashtable_iterator_base | |
b82f782b | 210 | { |
95cefe5f PC |
211 | _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node, |
212 | _Hash_node<_Value, __cache>** __bucket) | |
213 | : _M_cur_node(__node), _M_cur_bucket(__bucket) { } | |
b82f782b BK |
214 | |
215 | void | |
95cefe5f | 216 | _M_incr() |
b82f782b | 217 | { |
95cefe5f PC |
218 | _M_cur_node = _M_cur_node->_M_next; |
219 | if (!_M_cur_node) | |
220 | _M_incr_bucket(); | |
b82f782b BK |
221 | } |
222 | ||
223 | void | |
95cefe5f | 224 | _M_incr_bucket(); |
b82f782b | 225 | |
95cefe5f PC |
226 | _Hash_node<_Value, __cache>* _M_cur_node; |
227 | _Hash_node<_Value, __cache>** _M_cur_bucket; | |
b82f782b BK |
228 | }; |
229 | ||
230 | // Global iterators, used for arbitrary iteration within a hash | |
231 | // table. Larger and more expensive than local iterators. | |
95cefe5f | 232 | template<typename _Value, bool __cache> |
b82f782b | 233 | void |
95cefe5f PC |
234 | _Hashtable_iterator_base<_Value, __cache>:: |
235 | _M_incr_bucket() | |
b82f782b | 236 | { |
95cefe5f | 237 | ++_M_cur_bucket; |
b82f782b BK |
238 | |
239 | // This loop requires the bucket array to have a non-null sentinel. | |
95cefe5f PC |
240 | while (!*_M_cur_bucket) |
241 | ++_M_cur_bucket; | |
242 | _M_cur_node = *_M_cur_bucket; | |
b82f782b BK |
243 | } |
244 | ||
95cefe5f | 245 | template<typename _Value, bool __cache> |
b82f782b | 246 | inline bool |
95cefe5f PC |
247 | operator==(const _Hashtable_iterator_base<_Value, __cache>& __x, |
248 | const _Hashtable_iterator_base<_Value, __cache>& __y) | |
249 | { return __x._M_cur_node == __y._M_cur_node; } | |
b82f782b | 250 | |
95cefe5f | 251 | template<typename _Value, bool __cache> |
b82f782b | 252 | inline bool |
95cefe5f PC |
253 | operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x, |
254 | const _Hashtable_iterator_base<_Value, __cache>& __y) | |
255 | { return __x._M_cur_node != __y._M_cur_node; } | |
b82f782b | 256 | |
95cefe5f PC |
257 | template<typename _Value, bool __constant_iterators, bool __cache> |
258 | struct _Hashtable_iterator | |
259 | : public _Hashtable_iterator_base<_Value, __cache> | |
b82f782b | 260 | { |
95cefe5f PC |
261 | typedef _Value value_type; |
262 | typedef typename | |
263 | __gnu_cxx::__conditional_type<__constant_iterators, | |
264 | const _Value*, _Value*>::__type | |
b82f782b | 265 | pointer; |
95cefe5f PC |
266 | typedef typename |
267 | __gnu_cxx::__conditional_type<__constant_iterators, | |
268 | const _Value&, _Value&>::__type | |
b82f782b BK |
269 | reference; |
270 | typedef std::ptrdiff_t difference_type; | |
271 | typedef std::forward_iterator_tag iterator_category; | |
272 | ||
95cefe5f PC |
273 | _Hashtable_iterator() |
274 | : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } | |
b82f782b | 275 | |
95cefe5f PC |
276 | _Hashtable_iterator(_Hash_node<_Value, __cache>* __p, |
277 | _Hash_node<_Value, __cache>** __b) | |
278 | : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } | |
b82f782b BK |
279 | |
280 | explicit | |
95cefe5f PC |
281 | _Hashtable_iterator(_Hash_node<_Value, __cache>** __b) |
282 | : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } | |
b82f782b BK |
283 | |
284 | reference | |
285 | operator*() const | |
95cefe5f | 286 | { return this->_M_cur_node->_M_v; } |
b82f782b BK |
287 | |
288 | pointer | |
289 | operator->() const | |
95cefe5f | 290 | { return &this->_M_cur_node->_M_v; } |
b82f782b | 291 | |
95cefe5f | 292 | _Hashtable_iterator& |
b82f782b BK |
293 | operator++() |
294 | { | |
95cefe5f | 295 | this->_M_incr(); |
b82f782b BK |
296 | return *this; |
297 | } | |
298 | ||
95cefe5f | 299 | _Hashtable_iterator |
b82f782b BK |
300 | operator++(int) |
301 | { | |
95cefe5f PC |
302 | _Hashtable_iterator __tmp(*this); |
303 | this->_M_incr(); | |
304 | return __tmp; | |
b82f782b BK |
305 | } |
306 | }; | |
307 | ||
95cefe5f PC |
308 | template<typename _Value, bool __constant_iterators, bool __cache> |
309 | struct _Hashtable_const_iterator | |
310 | : public _Hashtable_iterator_base<_Value, __cache> | |
b82f782b | 311 | { |
95cefe5f PC |
312 | typedef _Value value_type; |
313 | typedef const _Value* pointer; | |
314 | typedef const _Value& reference; | |
b82f782b BK |
315 | typedef std::ptrdiff_t difference_type; |
316 | typedef std::forward_iterator_tag iterator_category; | |
317 | ||
95cefe5f PC |
318 | _Hashtable_const_iterator() |
319 | : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } | |
b82f782b | 320 | |
95cefe5f PC |
321 | _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p, |
322 | _Hash_node<_Value, __cache>** __b) | |
323 | : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } | |
b82f782b BK |
324 | |
325 | explicit | |
95cefe5f PC |
326 | _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b) |
327 | : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } | |
b82f782b | 328 | |
95cefe5f PC |
329 | _Hashtable_const_iterator(const _Hashtable_iterator<_Value, |
330 | __constant_iterators, __cache>& __x) | |
331 | : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node, | |
332 | __x._M_cur_bucket) { } | |
b82f782b BK |
333 | |
334 | reference | |
335 | operator*() const | |
95cefe5f | 336 | { return this->_M_cur_node->_M_v; } |
b82f782b BK |
337 | |
338 | pointer | |
339 | operator->() const | |
95cefe5f | 340 | { return &this->_M_cur_node->_M_v; } |
b82f782b | 341 | |
95cefe5f | 342 | _Hashtable_const_iterator& |
b82f782b BK |
343 | operator++() |
344 | { | |
95cefe5f | 345 | this->_M_incr(); |
b82f782b BK |
346 | return *this; |
347 | } | |
348 | ||
95cefe5f | 349 | _Hashtable_const_iterator |
b82f782b BK |
350 | operator++(int) |
351 | { | |
95cefe5f PC |
352 | _Hashtable_const_iterator __tmp(*this); |
353 | this->_M_incr(); | |
354 | return __tmp; | |
b82f782b BK |
355 | } |
356 | }; | |
357 | ||
358 | ||
95cefe5f | 359 | // Many of class template _Hashtable's template parameters are policy |
b82f782b BK |
360 | // classes. These are defaults for the policies. |
361 | ||
b82f782b BK |
362 | // Default range hashing function: use division to fold a large number |
363 | // into the range [0, N). | |
95cefe5f | 364 | struct _Mod_range_hashing |
b82f782b BK |
365 | { |
366 | typedef std::size_t first_argument_type; | |
367 | typedef std::size_t second_argument_type; | |
368 | typedef std::size_t result_type; | |
369 | ||
370 | result_type | |
95cefe5f PC |
371 | operator()(first_argument_type __num, second_argument_type __den) const |
372 | { return __num % __den; } | |
b82f782b BK |
373 | }; |
374 | ||
375 | // Default ranged hash function H. In principle it should be a | |
376 | // function object composed from objects of type H1 and H2 such that | |
377 | // h(k, N) = h2(h1(k), N), but that would mean making extra copies of | |
378 | // h1 and h2. So instead we'll just use a tag to tell class template | |
379 | // hashtable to do that composition. | |
95cefe5f | 380 | struct _Default_ranged_hash { }; |
b82f782b BK |
381 | |
382 | // Default value for rehash policy. Bucket size is (usually) the | |
383 | // smallest prime that keeps the load factor small enough. | |
95cefe5f | 384 | struct _Prime_rehash_policy |
b82f782b | 385 | { |
4d007574 PC |
386 | _Prime_rehash_policy(float __z = 1.0) |
387 | : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { } | |
95cefe5f | 388 | |
b82f782b | 389 | float |
4d007574 PC |
390 | max_load_factor() const |
391 | { return _M_max_load_factor; } | |
b82f782b BK |
392 | |
393 | // Return a bucket size no smaller than n. | |
394 | std::size_t | |
95cefe5f | 395 | _M_next_bkt(std::size_t __n) const; |
b82f782b BK |
396 | |
397 | // Return a bucket count appropriate for n elements | |
398 | std::size_t | |
95cefe5f | 399 | _M_bkt_for_elements(std::size_t __n) const; |
b82f782b | 400 | |
95cefe5f PC |
401 | // __n_bkt is current bucket count, __n_elt is current element count, |
402 | // and __n_ins is number of elements to be inserted. Do we need to | |
b82f782b BK |
403 | // increase bucket count? If so, return make_pair(true, n), where n |
404 | // is the new bucket count. If not, return make_pair(false, 0). | |
405 | std::pair<bool, std::size_t> | |
95cefe5f PC |
406 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, |
407 | std::size_t __n_ins) const; | |
b82f782b | 408 | |
95cefe5f PC |
409 | float _M_max_load_factor; |
410 | float _M_growth_factor; | |
411 | mutable std::size_t _M_next_resize; | |
b82f782b BK |
412 | }; |
413 | ||
4d007574 | 414 | extern const unsigned long __prime_list[]; |
b82f782b | 415 | |
4d007574 PC |
416 | // XXX This is a hack. There's no good reason for any of |
417 | // _Prime_rehash_policy's member functions to be inline. | |
b82f782b BK |
418 | |
419 | // Return a prime no smaller than n. | |
420 | inline std::size_t | |
95cefe5f PC |
421 | _Prime_rehash_policy:: |
422 | _M_next_bkt(std::size_t __n) const | |
b82f782b | 423 | { |
4d007574 PC |
424 | const int __n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48; |
425 | const unsigned long* __p = std::lower_bound(__prime_list, __prime_list | |
426 | + __n_primes, __n); | |
95cefe5f PC |
427 | _M_next_resize = static_cast<std::size_t>(std::ceil(*__p |
428 | * _M_max_load_factor)); | |
429 | return *__p; | |
b82f782b BK |
430 | } |
431 | ||
432 | // Return the smallest prime p such that alpha p >= n, where alpha | |
433 | // is the load factor. | |
434 | inline std::size_t | |
95cefe5f PC |
435 | _Prime_rehash_policy:: |
436 | _M_bkt_for_elements(std::size_t __n) const | |
b82f782b | 437 | { |
4d007574 | 438 | const int __n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48; |
95cefe5f | 439 | const float __min_bkts = __n / _M_max_load_factor; |
4d007574 PC |
440 | const unsigned long* __p = std::lower_bound(__prime_list, __prime_list |
441 | + __n_primes, __min_bkts); | |
95cefe5f PC |
442 | _M_next_resize = static_cast<std::size_t>(std::ceil(*__p |
443 | * _M_max_load_factor)); | |
444 | return *__p; | |
b82f782b BK |
445 | } |
446 | ||
95cefe5f PC |
447 | // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. |
448 | // If p > __n_bkt, return make_pair(true, p); otherwise return | |
b82f782b | 449 | // make_pair(false, 0). In principle this isn't very different from |
95cefe5f | 450 | // _M_bkt_for_elements. |
4d007574 | 451 | |
b82f782b BK |
452 | // The only tricky part is that we're caching the element count at |
453 | // which we need to rehash, so we don't have to do a floating-point | |
454 | // multiply for every insertion. | |
4d007574 | 455 | |
b82f782b | 456 | inline std::pair<bool, std::size_t> |
95cefe5f PC |
457 | _Prime_rehash_policy:: |
458 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, | |
459 | std::size_t __n_ins) const | |
b82f782b | 460 | { |
95cefe5f | 461 | if (__n_elt + __n_ins > _M_next_resize) |
b82f782b | 462 | { |
95cefe5f PC |
463 | float __min_bkts = ((float(__n_ins) + float(__n_elt)) |
464 | / _M_max_load_factor); | |
465 | if (__min_bkts > __n_bkt) | |
b82f782b | 466 | { |
95cefe5f | 467 | __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); |
4d007574 PC |
468 | const int __n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48; |
469 | const unsigned long* __p = | |
470 | std::lower_bound(__prime_list, __prime_list + __n_primes, | |
471 | __min_bkts); | |
472 | _M_next_resize = | |
95cefe5f PC |
473 | static_cast<std::size_t>(std::ceil(*__p * _M_max_load_factor)); |
474 | return std::make_pair(true, *__p); | |
b82f782b BK |
475 | } |
476 | else | |
477 | { | |
95cefe5f PC |
478 | _M_next_resize = |
479 | static_cast<std::size_t>(std::ceil(__n_bkt | |
480 | * _M_max_load_factor)); | |
b82f782b BK |
481 | return std::make_pair(false, 0); |
482 | } | |
483 | } | |
484 | else | |
485 | return std::make_pair(false, 0); | |
486 | } | |
487 | ||
95cefe5f | 488 | // Base classes for std::tr1::_Hashtable. We define these base |
b82f782b BK |
489 | // classes because in some cases we want to do different things |
490 | // depending on the value of a policy class. In some cases the | |
491 | // policy class affects which member functions and nested typedefs | |
492 | // are defined; we handle that by specializing base class templates. | |
493 | // Several of the base class templates need to access other members | |
95cefe5f | 494 | // of class template _Hashtable, so we use the "curiously recurring |
b82f782b BK |
495 | // template pattern" for them. |
496 | ||
95cefe5f | 497 | // class template _Map_base. If the hashtable has a value type of the |
b82f782b BK |
498 | // form pair<T1, T2> and a key extraction policy that returns the |
499 | // first part of the pair, the hashtable gets a mapped_type typedef. | |
500 | // If it satisfies those criteria and also has unique keys, then it | |
501 | // also gets an operator[]. | |
95cefe5f PC |
502 | template<typename _Key, typename _Value, typename _Ex, bool __unique, |
503 | typename _Hashtable> | |
504 | struct _Map_base { }; | |
b82f782b | 505 | |
95cefe5f PC |
506 | template<typename _Key, typename _Pair, typename _Hashtable> |
507 | struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> | |
b82f782b | 508 | { |
95cefe5f | 509 | typedef typename _Pair::second_type mapped_type; |
b82f782b BK |
510 | }; |
511 | ||
95cefe5f PC |
512 | template<typename _Key, typename _Pair, typename _Hashtable> |
513 | struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> | |
b82f782b | 514 | { |
95cefe5f | 515 | typedef typename _Pair::second_type mapped_type; |
b82f782b BK |
516 | |
517 | mapped_type& | |
95cefe5f | 518 | operator[](const _Key& __k); |
b82f782b BK |
519 | }; |
520 | ||
95cefe5f PC |
521 | template<typename _Key, typename _Pair, typename _Hashtable> |
522 | typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, | |
523 | true, _Hashtable>::mapped_type& | |
524 | _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: | |
525 | operator[](const _Key& __k) | |
b82f782b | 526 | { |
95cefe5f PC |
527 | _Hashtable* __h = static_cast<_Hashtable*>(this); |
528 | typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); | |
529 | std::size_t __n = __h->_M_bucket_index(__k, __code, | |
530 | __h->_M_bucket_count); | |
531 | ||
532 | typename _Hashtable::_Node* __p = | |
533 | __h->_M_find_node(__h->_M_buckets[__n], __k, __code); | |
534 | if (!__p) | |
535 | return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), | |
536 | __n, __code)->second; | |
537 | return (__p->_M_v).second; | |
b82f782b BK |
538 | } |
539 | ||
95cefe5f PC |
540 | // class template _Rehash_base. Give hashtable the max_load_factor |
541 | // functions iff the rehash policy is _Prime_rehash_policy. | |
542 | template<typename _RehashPolicy, typename _Hashtable> | |
543 | struct _Rehash_base { }; | |
b82f782b | 544 | |
95cefe5f PC |
545 | template<typename _Hashtable> |
546 | struct _Rehash_base<_Prime_rehash_policy, _Hashtable> | |
b82f782b BK |
547 | { |
548 | float | |
549 | max_load_factor() const | |
550 | { | |
95cefe5f PC |
551 | const _Hashtable* __this = static_cast<const _Hashtable*>(this); |
552 | return __this->__rehash_policy().max_load_factor(); | |
b82f782b BK |
553 | } |
554 | ||
555 | void | |
95cefe5f | 556 | max_load_factor(float __z) |
b82f782b | 557 | { |
95cefe5f PC |
558 | _Hashtable* __this = static_cast<_Hashtable*>(this); |
559 | __this->__rehash_policy(_Prime_rehash_policy(__z)); | |
b82f782b BK |
560 | } |
561 | }; | |
562 | ||
95cefe5f | 563 | // Class template _Hash_code_base. Encapsulates two policy issues that |
b82f782b BK |
564 | // aren't quite orthogonal. |
565 | // (1) the difference between using a ranged hash function and using | |
566 | // the combination of a hash function and a range-hashing function. | |
567 | // In the former case we don't have such things as hash codes, so | |
568 | // we have a dummy type as placeholder. | |
569 | // (2) Whether or not we cache hash codes. Caching hash codes is | |
570 | // meaningless if we have a ranged hash function. | |
571 | // We also put the key extraction and equality comparison function | |
572 | // objects here, for convenience. | |
573 | ||
574 | // Primary template: unused except as a hook for specializations. | |
95cefe5f PC |
575 | template<typename _Key, typename _Value, |
576 | typename _ExtractKey, typename _Equal, | |
577 | typename _H1, typename _H2, typename _Hash, | |
578 | bool __cache_hash_code> | |
579 | struct _Hash_code_base; | |
b82f782b BK |
580 | |
581 | // Specialization: ranged hash function, no caching hash codes. H1 | |
582 | // and H2 are provided but ignored. We define a dummy hash code type. | |
95cefe5f PC |
583 | template<typename _Key, typename _Value, |
584 | typename _ExtractKey, typename _Equal, | |
585 | typename _H1, typename _H2, typename _Hash> | |
586 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
587 | _Hash, false> | |
b82f782b BK |
588 | { |
589 | protected: | |
95cefe5f PC |
590 | _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, |
591 | const _H1&, const _H2&, const _Hash& __h) | |
592 | : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { } | |
b82f782b | 593 | |
95cefe5f | 594 | typedef void* _Hash_code_type; |
b82f782b | 595 | |
95cefe5f PC |
596 | _Hash_code_type |
597 | _M_hash_code(const _Key& __key) const | |
b82f782b BK |
598 | { return 0; } |
599 | ||
600 | std::size_t | |
95cefe5f PC |
601 | _M_bucket_index(const _Key& __k, _Hash_code_type, |
602 | std::size_t __n) const | |
603 | { return _M_ranged_hash(__k, __n); } | |
b82f782b BK |
604 | |
605 | std::size_t | |
95cefe5f PC |
606 | _M_bucket_index(const _Hash_node<_Value, false>* __p, |
607 | std::size_t __n) const | |
608 | { return _M_ranged_hash(_M_extract(__p->_M_v), __n); } | |
b82f782b BK |
609 | |
610 | bool | |
95cefe5f PC |
611 | _M_compare(const _Key& __k, _Hash_code_type, |
612 | _Hash_node<_Value, false>* __n) const | |
613 | { return _M_eq(__k, _M_extract(__n->_M_v)); } | |
b82f782b BK |
614 | |
615 | void | |
95cefe5f | 616 | _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const |
b82f782b BK |
617 | { } |
618 | ||
619 | void | |
95cefe5f PC |
620 | _M_copy_code(_Hash_node<_Value, false>*, |
621 | const _Hash_node<_Value, false>*) const | |
b82f782b BK |
622 | { } |
623 | ||
624 | void | |
95cefe5f | 625 | _M_swap(_Hash_code_base& __x) |
b82f782b | 626 | { |
95cefe5f PC |
627 | std::swap(_M_extract, __x._M_extract); |
628 | std::swap(_M_eq, __x._M_eq); | |
629 | std::swap(_M_ranged_hash, __x._M_ranged_hash); | |
b82f782b BK |
630 | } |
631 | ||
632 | protected: | |
95cefe5f PC |
633 | _ExtractKey _M_extract; |
634 | _Equal _M_eq; | |
635 | _Hash _M_ranged_hash; | |
b82f782b BK |
636 | }; |
637 | ||
638 | ||
639 | // No specialization for ranged hash function while caching hash codes. | |
640 | // That combination is meaningless, and trying to do it is an error. | |
641 | ||
642 | ||
643 | // Specialization: ranged hash function, cache hash codes. This | |
644 | // combination is meaningless, so we provide only a declaration | |
645 | // and no definition. | |
95cefe5f PC |
646 | template<typename _Key, typename _Value, |
647 | typename _ExtractKey, typename _Equal, | |
648 | typename _H1, typename _H2, typename _Hash> | |
649 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
650 | _Hash, true>; | |
b82f782b BK |
651 | |
652 | // Specialization: hash function and range-hashing function, no | |
653 | // caching of hash codes. H is provided but ignored. Provides | |
654 | // typedef and accessor required by TR1. | |
95cefe5f PC |
655 | template<typename _Key, typename _Value, |
656 | typename _ExtractKey, typename _Equal, | |
657 | typename _H1, typename _H2> | |
658 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
659 | _Default_ranged_hash, false> | |
b82f782b | 660 | { |
95cefe5f PC |
661 | typedef _H1 hasher; |
662 | ||
b82f782b BK |
663 | hasher |
664 | hash_function() const | |
95cefe5f | 665 | { return _M_h1; } |
b82f782b BK |
666 | |
667 | protected: | |
95cefe5f PC |
668 | _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, |
669 | const _H1& __h1, const _H2& __h2, | |
670 | const _Default_ranged_hash&) | |
671 | : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } | |
b82f782b | 672 | |
95cefe5f PC |
673 | typedef std::size_t _Hash_code_type; |
674 | ||
675 | _Hash_code_type | |
676 | _M_hash_code(const _Key& __k) const | |
677 | { return _M_h1(__k); } | |
b82f782b BK |
678 | |
679 | std::size_t | |
95cefe5f PC |
680 | _M_bucket_index(const _Key&, _Hash_code_type __c, |
681 | std::size_t __n) const | |
682 | { return _M_h2(__c, __n); } | |
b82f782b BK |
683 | |
684 | std::size_t | |
95cefe5f PC |
685 | _M_bucket_index(const _Hash_node<_Value, false>* __p, |
686 | std::size_t __n) const | |
687 | { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); } | |
b82f782b BK |
688 | |
689 | bool | |
95cefe5f PC |
690 | _M_compare(const _Key& __k, _Hash_code_type, |
691 | _Hash_node<_Value, false>* __n) const | |
692 | { return _M_eq(__k, _M_extract(__n->_M_v)); } | |
b82f782b BK |
693 | |
694 | void | |
95cefe5f | 695 | _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const |
b82f782b BK |
696 | { } |
697 | ||
698 | void | |
95cefe5f PC |
699 | _M_copy_code(_Hash_node<_Value, false>*, |
700 | const _Hash_node<_Value, false>*) const | |
b82f782b BK |
701 | { } |
702 | ||
703 | void | |
95cefe5f | 704 | _M_swap(_Hash_code_base& __x) |
b82f782b | 705 | { |
95cefe5f PC |
706 | std::swap(_M_extract, __x._M_extract); |
707 | std::swap(_M_eq, __x._M_eq); | |
708 | std::swap(_M_h1, __x._M_h1); | |
709 | std::swap(_M_h2, __x._M_h2); | |
b82f782b BK |
710 | } |
711 | ||
712 | protected: | |
95cefe5f PC |
713 | _ExtractKey _M_extract; |
714 | _Equal _M_eq; | |
715 | _H1 _M_h1; | |
716 | _H2 _M_h2; | |
b82f782b BK |
717 | }; |
718 | ||
719 | // Specialization: hash function and range-hashing function, | |
720 | // caching hash codes. H is provided but ignored. Provides | |
721 | // typedef and accessor required by TR1. | |
95cefe5f PC |
722 | template<typename _Key, typename _Value, |
723 | typename _ExtractKey, typename _Equal, | |
724 | typename _H1, typename _H2> | |
725 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
726 | _Default_ranged_hash, true> | |
b82f782b | 727 | { |
95cefe5f | 728 | typedef _H1 hasher; |
b82f782b BK |
729 | |
730 | hasher | |
731 | hash_function() const | |
95cefe5f | 732 | { return _M_h1; } |
b82f782b BK |
733 | |
734 | protected: | |
95cefe5f PC |
735 | _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, |
736 | const _H1& __h1, const _H2& __h2, | |
737 | const _Default_ranged_hash&) | |
738 | : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } | |
b82f782b | 739 | |
95cefe5f | 740 | typedef std::size_t _Hash_code_type; |
b82f782b | 741 | |
95cefe5f PC |
742 | _Hash_code_type |
743 | _M_hash_code(const _Key& __k) const | |
744 | { return _M_h1(__k); } | |
b82f782b BK |
745 | |
746 | std::size_t | |
95cefe5f PC |
747 | _M_bucket_index(const _Key&, _Hash_code_type __c, |
748 | std::size_t __n) const | |
749 | { return _M_h2(__c, __n); } | |
b82f782b BK |
750 | |
751 | std::size_t | |
95cefe5f PC |
752 | _M_bucket_index(const _Hash_node<_Value, true>* __p, |
753 | std::size_t __n) const | |
754 | { return _M_h2(__p->_M_hash_code, __n); } | |
b82f782b BK |
755 | |
756 | bool | |
95cefe5f PC |
757 | _M_compare(const _Key& __k, _Hash_code_type __c, |
758 | _Hash_node<_Value, true>* __n) const | |
759 | { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); } | |
b82f782b BK |
760 | |
761 | void | |
95cefe5f PC |
762 | _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const |
763 | { __n->_M_hash_code = __c; } | |
b82f782b BK |
764 | |
765 | void | |
95cefe5f PC |
766 | _M_copy_code(_Hash_node<_Value, true>* __to, |
767 | const _Hash_node<_Value, true>* __from) const | |
768 | { __to->_M_hash_code = __from->_M_hash_code; } | |
b82f782b BK |
769 | |
770 | void | |
95cefe5f | 771 | _M_swap(_Hash_code_base& __x) |
b82f782b | 772 | { |
95cefe5f PC |
773 | std::swap(_M_extract, __x._M_extract); |
774 | std::swap(_M_eq, __x._M_eq); | |
775 | std::swap(_M_h1, __x._M_h1); | |
776 | std::swap(_M_h2, __x._M_h2); | |
b82f782b BK |
777 | } |
778 | ||
779 | protected: | |
95cefe5f PC |
780 | _ExtractKey _M_extract; |
781 | _Equal _M_eq; | |
782 | _H1 _M_h1; | |
783 | _H2 _M_h2; | |
b82f782b | 784 | }; |
95cefe5f | 785 | } // namespace __detail |
b82f782b | 786 | |
e133ace8 PC |
787 | _GLIBCXX_END_NAMESPACE_TR1 |
788 | } |