1 // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*-
3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
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)
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.
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,
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.
30 /** @file tr1/hashtable_policy.h
31 * This is a TR1 C++ Library header.
34 #ifndef _TR1_HASHTABLE_POLICY_H
35 #define _TR1_HASHTABLE_POLICY_H 1
37 #include <functional> // _Identity, _Select1st
38 #include <tr1/utility>
39 #include <ext/type_traits.h>
43 _GLIBCXX_BEGIN_NAMESPACE(tr1)
46 // Helper function: return distance(first, last) for forward
47 // iterators, or 0 for input iterators.
48 template<class _Iterator>
49 inline typename std::iterator_traits<_Iterator>::difference_type
50 __distance_fw(_Iterator __first, _Iterator __last,
51 std::input_iterator_tag)
54 template<class _Iterator>
55 inline typename std::iterator_traits<_Iterator>::difference_type
56 __distance_fw(_Iterator __first, _Iterator __last,
57 std::forward_iterator_tag)
58 { return std::distance(__first, __last); }
60 template<class _Iterator>
61 inline typename std::iterator_traits<_Iterator>::difference_type
62 __distance_fw(_Iterator __first, _Iterator __last)
64 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
65 return __distance_fw(__first, __last, _Tag());
68 // XXX This is a hack. _Prime_rehash_policy's member functions, and
69 // certainly the list of primes, should be defined in a .cc file.
70 // We're temporarily putting them in a header because we don't have a
71 // place to put TR1 .cc files yet. There's no good reason for any of
72 // _Prime_rehash_policy's member functions to be inline, and there's
73 // certainly no good reason for _Primes<> to exist at all.
76 template<typename _Tp, typename _Up>
78 operator()(_Tp __x, _Up __y)
82 template<int __ulongsize = sizeof(unsigned long)>
85 static const int __n_primes = __ulongsize != 8 ? 256 : 256 + 48;
86 static const unsigned long __primes[256 + 48 + 1];
89 template<int __ulongsize>
90 const int _Primes<__ulongsize>::__n_primes;
92 template<int __ulongsize>
93 const unsigned long _Primes<__ulongsize>::__primes[256 + 48 + 1] =
95 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
96 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
97 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
98 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
99 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
100 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
101 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
102 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
103 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
104 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
105 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
106 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
107 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
108 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
109 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
110 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
111 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
112 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
113 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
114 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
115 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
116 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
117 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
118 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
119 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
120 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
121 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
122 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
123 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
124 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
125 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
126 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
127 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
128 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
129 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
130 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
131 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,
132 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,
133 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,
134 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
136 // Sentinel, so we don't have to test the result of lower_bound,
137 // or, on 64-bit machines, rest of the table.
138 __ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull,
139 (unsigned long)8589934583ull,
140 (unsigned long)12884901857ull, (unsigned long)17179869143ull,
141 (unsigned long)25769803693ull, (unsigned long)34359738337ull,
142 (unsigned long)51539607367ull, (unsigned long)68719476731ull,
143 (unsigned long)103079215087ull, (unsigned long)137438953447ull,
144 (unsigned long)206158430123ull, (unsigned long)274877906899ull,
145 (unsigned long)412316860387ull, (unsigned long)549755813881ull,
146 (unsigned long)824633720731ull, (unsigned long)1099511627689ull,
147 (unsigned long)1649267441579ull, (unsigned long)2199023255531ull,
148 (unsigned long)3298534883309ull, (unsigned long)4398046511093ull,
149 (unsigned long)6597069766607ull, (unsigned long)8796093022151ull,
150 (unsigned long)13194139533241ull, (unsigned long)17592186044399ull,
151 (unsigned long)26388279066581ull, (unsigned long)35184372088777ull,
152 (unsigned long)52776558133177ull, (unsigned long)70368744177643ull,
153 (unsigned long)105553116266399ull, (unsigned long)140737488355213ull,
154 (unsigned long)211106232532861ull, (unsigned long)281474976710597ull,
155 (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull,
156 (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull,
157 (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull,
158 (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull,
159 (unsigned long)144115188075855859ull,
160 (unsigned long)288230376151711717ull,
161 (unsigned long)576460752303423433ull,
162 (unsigned long)1152921504606846883ull,
163 (unsigned long)2305843009213693951ull,
164 (unsigned long)4611686018427387847ull,
165 (unsigned long)9223372036854775783ull,
166 (unsigned long)18446744073709551557ull,
167 (unsigned long)18446744073709551557ull
170 // Auxiliary types used for all instantiations of _Hashtable: nodes
173 // Nodes, used to wrap elements stored in the hash table. A policy
174 // template parameter of class template _Hashtable controls whether
175 // nodes also store a hash code. In some cases (e.g. strings) this
176 // may be a performance win.
177 template<typename _Value, bool __cache_hash_code>
180 template<typename _Value>
181 struct _Hash_node<_Value, true>
184 std::size_t _M_hash_code;
188 template<typename _Value>
189 struct _Hash_node<_Value, false>
195 // Local iterators, used to iterate within a bucket but not between
197 template<typename _Value, bool __cache>
198 struct _Node_iterator_base
200 _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
205 { _M_cur = _M_cur->_M_next; }
207 _Hash_node<_Value, __cache>* _M_cur;
210 template<typename _Value, bool __cache>
212 operator==(const _Node_iterator_base<_Value, __cache>& __x,
213 const _Node_iterator_base<_Value, __cache>& __y)
214 { return __x._M_cur == __y._M_cur; }
216 template<typename _Value, bool __cache>
218 operator!=(const _Node_iterator_base<_Value, __cache>& __x,
219 const _Node_iterator_base<_Value, __cache>& __y)
220 { return __x._M_cur != __y._M_cur; }
222 template<typename _Value, bool __constant_iterators, bool __cache>
223 struct _Node_iterator
224 : public _Node_iterator_base<_Value, __cache>
226 typedef _Value value_type;
228 __gnu_cxx::__conditional_type<__constant_iterators,
229 const _Value*, _Value*>::__type
232 __gnu_cxx::__conditional_type<__constant_iterators,
233 const _Value&, _Value&>::__type
235 typedef std::ptrdiff_t difference_type;
236 typedef std::forward_iterator_tag iterator_category;
239 : _Node_iterator_base<_Value, __cache>(0) { }
242 _Node_iterator(_Hash_node<_Value, __cache>* __p)
243 : _Node_iterator_base<_Value, __cache>(__p) { }
247 { return this->_M_cur->_M_v; }
251 { return &this->_M_cur->_M_v; }
263 _Node_iterator __tmp(*this);
269 template<typename _Value, bool __constant_iterators, bool __cache>
270 struct _Node_const_iterator
271 : public _Node_iterator_base<_Value, __cache>
273 typedef _Value value_type;
274 typedef const _Value* pointer;
275 typedef const _Value& reference;
276 typedef std::ptrdiff_t difference_type;
277 typedef std::forward_iterator_tag iterator_category;
279 _Node_const_iterator()
280 : _Node_iterator_base<_Value, __cache>(0) { }
283 _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
284 : _Node_iterator_base<_Value, __cache>(__p) { }
286 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
288 : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
292 { return this->_M_cur->_M_v; }
296 { return &this->_M_cur->_M_v; }
298 _Node_const_iterator&
308 _Node_const_iterator __tmp(*this);
314 template<typename _Value, bool __cache>
315 struct _Hashtable_iterator_base
317 _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node,
318 _Hash_node<_Value, __cache>** __bucket)
319 : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
324 _M_cur_node = _M_cur_node->_M_next;
332 _Hash_node<_Value, __cache>* _M_cur_node;
333 _Hash_node<_Value, __cache>** _M_cur_bucket;
336 // Global iterators, used for arbitrary iteration within a hash
337 // table. Larger and more expensive than local iterators.
338 template<typename _Value, bool __cache>
340 _Hashtable_iterator_base<_Value, __cache>::
345 // This loop requires the bucket array to have a non-null sentinel.
346 while (!*_M_cur_bucket)
348 _M_cur_node = *_M_cur_bucket;
351 template<typename _Value, bool __cache>
353 operator==(const _Hashtable_iterator_base<_Value, __cache>& __x,
354 const _Hashtable_iterator_base<_Value, __cache>& __y)
355 { return __x._M_cur_node == __y._M_cur_node; }
357 template<typename _Value, bool __cache>
359 operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x,
360 const _Hashtable_iterator_base<_Value, __cache>& __y)
361 { return __x._M_cur_node != __y._M_cur_node; }
363 template<typename _Value, bool __constant_iterators, bool __cache>
364 struct _Hashtable_iterator
365 : public _Hashtable_iterator_base<_Value, __cache>
367 typedef _Value value_type;
369 __gnu_cxx::__conditional_type<__constant_iterators,
370 const _Value*, _Value*>::__type
373 __gnu_cxx::__conditional_type<__constant_iterators,
374 const _Value&, _Value&>::__type
376 typedef std::ptrdiff_t difference_type;
377 typedef std::forward_iterator_tag iterator_category;
379 _Hashtable_iterator()
380 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
382 _Hashtable_iterator(_Hash_node<_Value, __cache>* __p,
383 _Hash_node<_Value, __cache>** __b)
384 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
387 _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
388 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
392 { return this->_M_cur_node->_M_v; }
396 { return &this->_M_cur_node->_M_v; }
408 _Hashtable_iterator __tmp(*this);
414 template<typename _Value, bool __constant_iterators, bool __cache>
415 struct _Hashtable_const_iterator
416 : public _Hashtable_iterator_base<_Value, __cache>
418 typedef _Value value_type;
419 typedef const _Value* pointer;
420 typedef const _Value& reference;
421 typedef std::ptrdiff_t difference_type;
422 typedef std::forward_iterator_tag iterator_category;
424 _Hashtable_const_iterator()
425 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
427 _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
428 _Hash_node<_Value, __cache>** __b)
429 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
432 _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
433 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
435 _Hashtable_const_iterator(const _Hashtable_iterator<_Value,
436 __constant_iterators, __cache>& __x)
437 : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node,
438 __x._M_cur_bucket) { }
442 { return this->_M_cur_node->_M_v; }
446 { return &this->_M_cur_node->_M_v; }
448 _Hashtable_const_iterator&
455 _Hashtable_const_iterator
458 _Hashtable_const_iterator __tmp(*this);
465 // Many of class template _Hashtable's template parameters are policy
466 // classes. These are defaults for the policies.
468 // Default range hashing function: use division to fold a large number
469 // into the range [0, N).
470 struct _Mod_range_hashing
472 typedef std::size_t first_argument_type;
473 typedef std::size_t second_argument_type;
474 typedef std::size_t result_type;
477 operator()(first_argument_type __num, second_argument_type __den) const
478 { return __num % __den; }
481 // Default ranged hash function H. In principle it should be a
482 // function object composed from objects of type H1 and H2 such that
483 // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
484 // h1 and h2. So instead we'll just use a tag to tell class template
485 // hashtable to do that composition.
486 struct _Default_ranged_hash { };
488 // Default value for rehash policy. Bucket size is (usually) the
489 // smallest prime that keeps the load factor small enough.
490 struct _Prime_rehash_policy
492 _Prime_rehash_policy(float __z = 1.0);
495 max_load_factor() const;
497 // Return a bucket size no smaller than n.
499 _M_next_bkt(std::size_t __n) const;
501 // Return a bucket count appropriate for n elements
503 _M_bkt_for_elements(std::size_t __n) const;
505 // __n_bkt is current bucket count, __n_elt is current element count,
506 // and __n_ins is number of elements to be inserted. Do we need to
507 // increase bucket count? If so, return make_pair(true, n), where n
508 // is the new bucket count. If not, return make_pair(false, 0).
509 std::pair<bool, std::size_t>
510 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
511 std::size_t __n_ins) const;
513 float _M_max_load_factor;
514 float _M_growth_factor;
515 mutable std::size_t _M_next_resize;
519 _Prime_rehash_policy::
520 _Prime_rehash_policy(float __z)
521 : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0)
525 _Prime_rehash_policy::
526 max_load_factor() const
527 { return _M_max_load_factor; }
529 // Return a prime no smaller than n.
531 _Prime_rehash_policy::
532 _M_next_bkt(std::size_t __n) const
534 const unsigned long* const __last = (_Primes<>::__primes
535 + _Primes<>::__n_primes);
536 const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last,
538 _M_next_resize = static_cast<std::size_t>(std::ceil(*__p
539 * _M_max_load_factor));
543 // Return the smallest prime p such that alpha p >= n, where alpha
544 // is the load factor.
546 _Prime_rehash_policy::
547 _M_bkt_for_elements(std::size_t __n) const
549 const unsigned long* const __last = (_Primes<>::__primes
550 + _Primes<>::__n_primes);
551 const float __min_bkts = __n / _M_max_load_factor;
552 const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last,
553 __min_bkts, _LessThan());
554 _M_next_resize = static_cast<std::size_t>(std::ceil(*__p
555 * _M_max_load_factor));
559 // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
560 // If p > __n_bkt, return make_pair(true, p); otherwise return
561 // make_pair(false, 0). In principle this isn't very different from
562 // _M_bkt_for_elements.
564 // The only tricky part is that we're caching the element count at
565 // which we need to rehash, so we don't have to do a floating-point
566 // multiply for every insertion.
568 inline std::pair<bool, std::size_t>
569 _Prime_rehash_policy::
570 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
571 std::size_t __n_ins) const
573 if (__n_elt + __n_ins > _M_next_resize)
575 float __min_bkts = ((float(__n_ins) + float(__n_elt))
576 / _M_max_load_factor);
577 if (__min_bkts > __n_bkt)
579 __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
580 const unsigned long* const __last = (_Primes<>::__primes
581 + _Primes<>::__n_primes);
582 const unsigned long* __p = std::lower_bound(_Primes<>::__primes,
586 static_cast<std::size_t>(std::ceil(*__p * _M_max_load_factor));
587 return std::make_pair(true, *__p);
592 static_cast<std::size_t>(std::ceil(__n_bkt
593 * _M_max_load_factor));
594 return std::make_pair(false, 0);
598 return std::make_pair(false, 0);
601 // Base classes for std::tr1::_Hashtable. We define these base
602 // classes because in some cases we want to do different things
603 // depending on the value of a policy class. In some cases the
604 // policy class affects which member functions and nested typedefs
605 // are defined; we handle that by specializing base class templates.
606 // Several of the base class templates need to access other members
607 // of class template _Hashtable, so we use the "curiously recurring
608 // template pattern" for them.
610 // class template _Map_base. If the hashtable has a value type of the
611 // form pair<T1, T2> and a key extraction policy that returns the
612 // first part of the pair, the hashtable gets a mapped_type typedef.
613 // If it satisfies those criteria and also has unique keys, then it
614 // also gets an operator[].
615 template<typename _Key, typename _Value, typename _Ex, bool __unique,
617 struct _Map_base { };
619 template<typename _Key, typename _Pair, typename _Hashtable>
620 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
622 typedef typename _Pair::second_type mapped_type;
625 template<typename _Key, typename _Pair, typename _Hashtable>
626 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
628 typedef typename _Pair::second_type mapped_type;
631 operator[](const _Key& __k);
634 template<typename _Key, typename _Pair, typename _Hashtable>
635 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
636 true, _Hashtable>::mapped_type&
637 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
638 operator[](const _Key& __k)
640 _Hashtable* __h = static_cast<_Hashtable*>(this);
641 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
642 std::size_t __n = __h->_M_bucket_index(__k, __code,
643 __h->_M_bucket_count);
645 typename _Hashtable::_Node* __p =
646 __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
648 return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
649 __n, __code)->second;
650 return (__p->_M_v).second;
653 // class template _Rehash_base. Give hashtable the max_load_factor
654 // functions iff the rehash policy is _Prime_rehash_policy.
655 template<typename _RehashPolicy, typename _Hashtable>
656 struct _Rehash_base { };
658 template<typename _Hashtable>
659 struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
662 max_load_factor() const
664 const _Hashtable* __this = static_cast<const _Hashtable*>(this);
665 return __this->__rehash_policy().max_load_factor();
669 max_load_factor(float __z)
671 _Hashtable* __this = static_cast<_Hashtable*>(this);
672 __this->__rehash_policy(_Prime_rehash_policy(__z));
676 // Class template _Hash_code_base. Encapsulates two policy issues that
677 // aren't quite orthogonal.
678 // (1) the difference between using a ranged hash function and using
679 // the combination of a hash function and a range-hashing function.
680 // In the former case we don't have such things as hash codes, so
681 // we have a dummy type as placeholder.
682 // (2) Whether or not we cache hash codes. Caching hash codes is
683 // meaningless if we have a ranged hash function.
684 // We also put the key extraction and equality comparison function
685 // objects here, for convenience.
687 // Primary template: unused except as a hook for specializations.
688 template<typename _Key, typename _Value,
689 typename _ExtractKey, typename _Equal,
690 typename _H1, typename _H2, typename _Hash,
691 bool __cache_hash_code>
692 struct _Hash_code_base;
694 // Specialization: ranged hash function, no caching hash codes. H1
695 // and H2 are provided but ignored. We define a dummy hash code type.
696 template<typename _Key, typename _Value,
697 typename _ExtractKey, typename _Equal,
698 typename _H1, typename _H2, typename _Hash>
699 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
703 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
704 const _H1&, const _H2&, const _Hash& __h)
705 : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
707 typedef void* _Hash_code_type;
710 _M_hash_code(const _Key& __key) const
714 _M_bucket_index(const _Key& __k, _Hash_code_type,
715 std::size_t __n) const
716 { return _M_ranged_hash(__k, __n); }
719 _M_bucket_index(const _Hash_node<_Value, false>* __p,
720 std::size_t __n) const
721 { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
724 _M_compare(const _Key& __k, _Hash_code_type,
725 _Hash_node<_Value, false>* __n) const
726 { return _M_eq(__k, _M_extract(__n->_M_v)); }
729 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
733 _M_copy_code(_Hash_node<_Value, false>*,
734 const _Hash_node<_Value, false>*) const
738 _M_swap(_Hash_code_base& __x)
740 std::swap(_M_extract, __x._M_extract);
741 std::swap(_M_eq, __x._M_eq);
742 std::swap(_M_ranged_hash, __x._M_ranged_hash);
746 _ExtractKey _M_extract;
748 _Hash _M_ranged_hash;
752 // No specialization for ranged hash function while caching hash codes.
753 // That combination is meaningless, and trying to do it is an error.
756 // Specialization: ranged hash function, cache hash codes. This
757 // combination is meaningless, so we provide only a declaration
758 // and no definition.
759 template<typename _Key, typename _Value,
760 typename _ExtractKey, typename _Equal,
761 typename _H1, typename _H2, typename _Hash>
762 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
765 // Specialization: hash function and range-hashing function, no
766 // caching of hash codes. H is provided but ignored. Provides
767 // typedef and accessor required by TR1.
768 template<typename _Key, typename _Value,
769 typename _ExtractKey, typename _Equal,
770 typename _H1, typename _H2>
771 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
772 _Default_ranged_hash, false>
777 hash_function() const
781 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
782 const _H1& __h1, const _H2& __h2,
783 const _Default_ranged_hash&)
784 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
786 typedef std::size_t _Hash_code_type;
789 _M_hash_code(const _Key& __k) const
790 { return _M_h1(__k); }
793 _M_bucket_index(const _Key&, _Hash_code_type __c,
794 std::size_t __n) const
795 { return _M_h2(__c, __n); }
798 _M_bucket_index(const _Hash_node<_Value, false>* __p,
799 std::size_t __n) const
800 { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
803 _M_compare(const _Key& __k, _Hash_code_type,
804 _Hash_node<_Value, false>* __n) const
805 { return _M_eq(__k, _M_extract(__n->_M_v)); }
808 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
812 _M_copy_code(_Hash_node<_Value, false>*,
813 const _Hash_node<_Value, false>*) const
817 _M_swap(_Hash_code_base& __x)
819 std::swap(_M_extract, __x._M_extract);
820 std::swap(_M_eq, __x._M_eq);
821 std::swap(_M_h1, __x._M_h1);
822 std::swap(_M_h2, __x._M_h2);
826 _ExtractKey _M_extract;
832 // Specialization: hash function and range-hashing function,
833 // caching hash codes. H is provided but ignored. Provides
834 // typedef and accessor required by TR1.
835 template<typename _Key, typename _Value,
836 typename _ExtractKey, typename _Equal,
837 typename _H1, typename _H2>
838 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
839 _Default_ranged_hash, true>
844 hash_function() const
848 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
849 const _H1& __h1, const _H2& __h2,
850 const _Default_ranged_hash&)
851 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
853 typedef std::size_t _Hash_code_type;
856 _M_hash_code(const _Key& __k) const
857 { return _M_h1(__k); }
860 _M_bucket_index(const _Key&, _Hash_code_type __c,
861 std::size_t __n) const
862 { return _M_h2(__c, __n); }
865 _M_bucket_index(const _Hash_node<_Value, true>* __p,
866 std::size_t __n) const
867 { return _M_h2(__p->_M_hash_code, __n); }
870 _M_compare(const _Key& __k, _Hash_code_type __c,
871 _Hash_node<_Value, true>* __n) const
872 { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
875 _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
876 { __n->_M_hash_code = __c; }
879 _M_copy_code(_Hash_node<_Value, true>* __to,
880 const _Hash_node<_Value, true>* __from) const
881 { __to->_M_hash_code = __from->_M_hash_code; }
884 _M_swap(_Hash_code_base& __x)
886 std::swap(_M_extract, __x._M_extract);
887 std::swap(_M_eq, __x._M_eq);
888 std::swap(_M_h1, __x._M_h1);
889 std::swap(_M_h2, __x._M_h2);
893 _ExtractKey _M_extract;
898 } // namespace __detail
899 _GLIBCXX_END_NAMESPACE
900 } // namespace std::tr1
902 #endif // _TR1_HASHTABLE_POLICY_H