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