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