Line data Source code
1 : // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*-
2 :
3 : // Copyright (C) 2010-2013 Free Software Foundation, Inc.
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 : namespace tr1
34 : {
35 : namespace __detail
36 : {
37 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
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 13713 : : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
211 :
212 : void
213 : _M_incr()
214 : {
215 39 : _M_cur_node = _M_cur_node->_M_next;
216 39 : 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 133 : ++_M_cur_bucket;
235 :
236 : // This loop requires the bucket array to have a non-null sentinel.
237 263 : while (!*_M_cur_bucket)
238 130 : ++_M_cur_bucket;
239 0 : _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 0 : { 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 0 : { 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 35609 : : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
276 :
277 : explicit
278 : _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
279 8108 : : _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 4349 : { return std::__addressof(this->_M_cur_node->_M_v); }
288 :
289 : _Hashtable_iterator&
290 : operator++()
291 : {
292 39 : 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 0 : : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
317 :
318 : _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
319 : _Hash_node<_Value, __cache>** __b)
320 13308 : : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
321 :
322 : explicit
323 : _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
324 22588 : : _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 13308 : { return std::__addressof(this->_M_cur_node->_M_v); }
338 :
339 : _Hashtable_const_iterator&
340 : operator++()
341 : {
342 0 : 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 157701 : { 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 5120 : : _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 5120 : _Prime_rehash_policy::
421 : _M_next_bkt(std::size_t __n) const
422 : {
423 : const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
424 5120 : + _S_n_primes, __n);
425 : _M_next_resize =
426 5120 : static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
427 5120 : return *__p;
428 : }
429 :
430 : // Return the smallest prime p such that alpha p >= n, where alpha
431 : // is the load factor.
432 : inline std::size_t
433 : _Prime_rehash_policy::
434 : _M_bkt_for_elements(std::size_t __n) const
435 : {
436 : const float __min_bkts = __n / _M_max_load_factor;
437 : const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
438 : + _S_n_primes, __min_bkts);
439 : _M_next_resize =
440 : static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
441 : return *__p;
442 : }
443 :
444 : // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
445 : // If p > __n_bkt, return make_pair(true, p); otherwise return
446 : // make_pair(false, 0). In principle this isn't very different from
447 : // _M_bkt_for_elements.
448 :
449 : // The only tricky part is that we're caching the element count at
450 : // which we need to rehash, so we don't have to do a floating-point
451 : // multiply for every insertion.
452 :
453 : inline std::pair<bool, std::size_t>
454 35261 : _Prime_rehash_policy::
455 : _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
456 : std::size_t __n_ins) const
457 : {
458 35261 : if (__n_elt + __n_ins > _M_next_resize)
459 : {
460 1603 : float __min_bkts = ((float(__n_ins) + float(__n_elt))
461 1603 : / _M_max_load_factor);
462 1603 : if (__min_bkts > __n_bkt)
463 : {
464 3206 : __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
465 : const unsigned long* __p =
466 : std::lower_bound(__prime_list, __prime_list + _S_n_primes,
467 1603 : __min_bkts);
468 : _M_next_resize = static_cast<std::size_t>
469 1603 : (__builtin_ceil(*__p * _M_max_load_factor));
470 1603 : return std::make_pair(true, *__p);
471 : }
472 : else
473 : {
474 : _M_next_resize = static_cast<std::size_t>
475 0 : (__builtin_ceil(__n_bkt * _M_max_load_factor));
476 0 : return std::make_pair(false, 0);
477 : }
478 : }
479 : else
480 33658 : return std::make_pair(false, 0);
481 : }
482 :
483 : // Base classes for std::tr1::_Hashtable. We define these base
484 : // classes because in some cases we want to do different things
485 : // depending on the value of a policy class. In some cases the
486 : // policy class affects which member functions and nested typedefs
487 : // are defined; we handle that by specializing base class templates.
488 : // Several of the base class templates need to access other members
489 : // of class template _Hashtable, so we use the "curiously recurring
490 : // template pattern" for them.
491 :
492 : // class template _Map_base. If the hashtable has a value type of the
493 : // form pair<T1, T2> and a key extraction policy that returns the
494 : // first part of the pair, the hashtable gets a mapped_type typedef.
495 : // If it satisfies those criteria and also has unique keys, then it
496 : // also gets an operator[].
497 : template<typename _Key, typename _Value, typename _Ex, bool __unique,
498 : typename _Hashtable>
499 : struct _Map_base { };
500 :
501 : template<typename _Key, typename _Pair, typename _Hashtable>
502 : struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
503 : {
504 : typedef typename _Pair::second_type mapped_type;
505 : };
506 :
507 : template<typename _Key, typename _Pair, typename _Hashtable>
508 : struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
509 : {
510 : typedef typename _Pair::second_type mapped_type;
511 :
512 : mapped_type&
513 : operator[](const _Key& __k);
514 : };
515 :
516 : template<typename _Key, typename _Pair, typename _Hashtable>
517 : typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
518 : true, _Hashtable>::mapped_type&
519 5901 : _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
520 2304 : operator[](const _Key& __k)
521 : {
522 5901 : _Hashtable* __h = static_cast<_Hashtable*>(this);
523 14106 : typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
524 : std::size_t __n = __h->_M_bucket_index(__k, __code,
525 11802 : __h->_M_bucket_count);
526 :
527 : typename _Hashtable::_Node* __p =
528 11802 : __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
529 5901 : if (!__p)
530 571 : return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
531 22305 : __n, __code)->second;
532 1898 : return (__p->_M_v).second;
533 : }
534 :
535 : // class template _Rehash_base. Give hashtable the max_load_factor
536 : // functions iff the rehash policy is _Prime_rehash_policy.
537 : template<typename _RehashPolicy, typename _Hashtable>
538 : struct _Rehash_base { };
539 :
540 : template<typename _Hashtable>
541 : struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
542 : {
543 : float
544 : max_load_factor() const
545 : {
546 : const _Hashtable* __this = static_cast<const _Hashtable*>(this);
547 : return __this->__rehash_policy().max_load_factor();
548 : }
549 :
550 : void
551 : max_load_factor(float __z)
552 : {
553 : _Hashtable* __this = static_cast<_Hashtable*>(this);
554 : __this->__rehash_policy(_Prime_rehash_policy(__z));
555 : }
556 : };
557 :
558 : // Class template _Hash_code_base. Encapsulates two policy issues that
559 : // aren't quite orthogonal.
560 : // (1) the difference between using a ranged hash function and using
561 : // the combination of a hash function and a range-hashing function.
562 : // In the former case we don't have such things as hash codes, so
563 : // we have a dummy type as placeholder.
564 : // (2) Whether or not we cache hash codes. Caching hash codes is
565 : // meaningless if we have a ranged hash function.
566 : // We also put the key extraction and equality comparison function
567 : // objects here, for convenience.
568 :
569 : // Primary template: unused except as a hook for specializations.
570 : template<typename _Key, typename _Value,
571 : typename _ExtractKey, typename _Equal,
572 : typename _H1, typename _H2, typename _Hash,
573 : bool __cache_hash_code>
574 : struct _Hash_code_base;
575 :
576 : // Specialization: ranged hash function, no caching hash codes. H1
577 : // and H2 are provided but ignored. We define a dummy hash code type.
578 : template<typename _Key, typename _Value,
579 : typename _ExtractKey, typename _Equal,
580 : typename _H1, typename _H2, typename _Hash>
581 : struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
582 : _Hash, false>
583 : {
584 : protected:
585 : _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
586 : const _H1&, const _H2&, const _Hash& __h)
587 : : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
588 :
589 : typedef void* _Hash_code_type;
590 :
591 : _Hash_code_type
592 : _M_hash_code(const _Key& __key) const
593 : { return 0; }
594 :
595 : std::size_t
596 : _M_bucket_index(const _Key& __k, _Hash_code_type,
597 : std::size_t __n) const
598 : { return _M_ranged_hash(__k, __n); }
599 :
600 : std::size_t
601 : _M_bucket_index(const _Hash_node<_Value, false>* __p,
602 : std::size_t __n) const
603 : { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
604 :
605 : bool
606 : _M_compare(const _Key& __k, _Hash_code_type,
607 : _Hash_node<_Value, false>* __n) const
608 : { return _M_eq(__k, _M_extract(__n->_M_v)); }
609 :
610 : void
611 : _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
612 : { }
613 :
614 : void
615 : _M_copy_code(_Hash_node<_Value, false>*,
616 : const _Hash_node<_Value, false>*) const
617 : { }
618 :
619 : void
620 : _M_swap(_Hash_code_base& __x)
621 : {
622 : std::swap(_M_extract, __x._M_extract);
623 : std::swap(_M_eq, __x._M_eq);
624 : std::swap(_M_ranged_hash, __x._M_ranged_hash);
625 : }
626 :
627 : protected:
628 : _ExtractKey _M_extract;
629 : _Equal _M_eq;
630 : _Hash _M_ranged_hash;
631 : };
632 :
633 :
634 : // No specialization for ranged hash function while caching hash codes.
635 : // That combination is meaningless, and trying to do it is an error.
636 :
637 :
638 : // Specialization: ranged hash function, cache hash codes. This
639 : // combination is meaningless, so we provide only a declaration
640 : // and no definition.
641 : template<typename _Key, typename _Value,
642 : typename _ExtractKey, typename _Equal,
643 : typename _H1, typename _H2, typename _Hash>
644 : struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
645 : _Hash, true>;
646 :
647 : // Specialization: hash function and range-hashing function, no
648 : // caching of hash codes. H is provided but ignored. Provides
649 : // typedef and accessor required by TR1.
650 : template<typename _Key, typename _Value,
651 : typename _ExtractKey, typename _Equal,
652 : typename _H1, typename _H2>
653 : struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
654 : _Default_ranged_hash, false>
655 : {
656 : typedef _H1 hasher;
657 :
658 : hasher
659 : hash_function() const
660 : { return _M_h1; }
661 :
662 : protected:
663 : _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
664 : const _H1& __h1, const _H2& __h2,
665 : const _Default_ranged_hash&)
666 : : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
667 :
668 : typedef std::size_t _Hash_code_type;
669 :
670 : _Hash_code_type
671 10978 : _M_hash_code(const _Key& __k) const
672 124792 : { return _M_h1(__k); }
673 :
674 : std::size_t
675 : _M_bucket_index(const _Key&, _Hash_code_type __c,
676 : std::size_t __n) const
677 115417 : { return _M_h2(__c, __n); }
678 :
679 : std::size_t
680 : _M_bucket_index(const _Hash_node<_Value, false>* __p,
681 : std::size_t __n) const
682 84568 : { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
683 :
684 : bool
685 : _M_compare(const _Key& __k, _Hash_code_type,
686 : _Hash_node<_Value, false>* __n) const
687 94506 : { return _M_eq(__k, _M_extract(__n->_M_v)); }
688 :
689 : void
690 : _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
691 : { }
692 :
693 : void
694 : _M_copy_code(_Hash_node<_Value, false>*,
695 : const _Hash_node<_Value, false>*) const
696 : { }
697 :
698 : void
699 : _M_swap(_Hash_code_base& __x)
700 : {
701 : std::swap(_M_extract, __x._M_extract);
702 : std::swap(_M_eq, __x._M_eq);
703 : std::swap(_M_h1, __x._M_h1);
704 : std::swap(_M_h2, __x._M_h2);
705 : }
706 :
707 : protected:
708 : _ExtractKey _M_extract;
709 : _Equal _M_eq;
710 : _H1 _M_h1;
711 : _H2 _M_h2;
712 : };
713 :
714 : // Specialization: hash function and range-hashing function,
715 : // caching hash codes. H is provided but ignored. Provides
716 : // typedef and accessor required by TR1.
717 : template<typename _Key, typename _Value,
718 : typename _ExtractKey, typename _Equal,
719 : typename _H1, typename _H2>
720 : struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
721 : _Default_ranged_hash, true>
722 : {
723 : typedef _H1 hasher;
724 :
725 : hasher
726 : hash_function() const
727 : { return _M_h1; }
728 :
729 : protected:
730 : _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
731 : const _H1& __h1, const _H2& __h2,
732 : const _Default_ranged_hash&)
733 : : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
734 :
735 : typedef std::size_t _Hash_code_type;
736 :
737 : _Hash_code_type
738 : _M_hash_code(const _Key& __k) const
739 : { return _M_h1(__k); }
740 :
741 : std::size_t
742 : _M_bucket_index(const _Key&, _Hash_code_type __c,
743 : std::size_t __n) const
744 : { return _M_h2(__c, __n); }
745 :
746 : std::size_t
747 : _M_bucket_index(const _Hash_node<_Value, true>* __p,
748 : std::size_t __n) const
749 : { return _M_h2(__p->_M_hash_code, __n); }
750 :
751 : bool
752 : _M_compare(const _Key& __k, _Hash_code_type __c,
753 : _Hash_node<_Value, true>* __n) const
754 : { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
755 :
756 : void
757 : _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
758 : { __n->_M_hash_code = __c; }
759 :
760 : void
761 : _M_copy_code(_Hash_node<_Value, true>* __to,
762 : const _Hash_node<_Value, true>* __from) const
763 : { __to->_M_hash_code = __from->_M_hash_code; }
764 :
765 : void
766 : _M_swap(_Hash_code_base& __x)
767 : {
768 : std::swap(_M_extract, __x._M_extract);
769 : std::swap(_M_eq, __x._M_eq);
770 : std::swap(_M_h1, __x._M_h1);
771 : std::swap(_M_h2, __x._M_h2);
772 : }
773 :
774 : protected:
775 : _ExtractKey _M_extract;
776 : _Equal _M_eq;
777 : _H1 _M_h1;
778 : _H2 _M_h2;
779 : };
780 : _GLIBCXX_END_NAMESPACE_VERSION
781 : } // namespace __detail
782 : }
783 : }
|
