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