OSDN Git Service

83cef2d4ca45031df1af72bd0380b9463d3deace
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / hashtable.h
1 // hashtable.h header -*- C++ -*-
2
3 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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 bits/hashtable.h
26  *  This is an internal header file, included by other library headers.
27  *  Do not attempt to use it directly. @headername{unordered_map, unordered_set}
28  */
29
30 #ifndef _HASHTABLE_H
31 #define _HASHTABLE_H 1
32
33 #pragma GCC system_header
34
35 #include <bits/hashtable_policy.h>
36
37 namespace std _GLIBCXX_VISIBILITY(default)
38 {
39 _GLIBCXX_BEGIN_NAMESPACE_VERSION
40
41   // Class template _Hashtable, class definition.
42
43   // Meaning of class template _Hashtable's template parameters
44
45   // _Key and _Value: arbitrary CopyConstructible types.
46
47   // _Allocator: an allocator type ([lib.allocator.requirements]) whose
48   // value type is Value.  As a conforming extension, we allow for
49   // value type != Value.
50
51   // _ExtractKey: function object that takes a object of type Value
52   // and returns a value of type _Key.
53
54   // _Equal: function object that takes two objects of type k and returns
55   // a bool-like value that is true if the two objects are considered equal.
56
57   // _H1: the hash function.  A unary function object with argument type
58   // Key and result type size_t.  Return values should be distributed
59   // over the entire range [0, numeric_limits<size_t>:::max()].
60
61   // _H2: the range-hashing function (in the terminology of Tavori and
62   // Dreizin).  A binary function object whose argument types and result
63   // type are all size_t.  Given arguments r and N, the return value is
64   // in the range [0, N).
65
66   // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
67   // whose argument types are _Key and size_t and whose result type is
68   // size_t.  Given arguments k and N, the return value is in the range
69   // [0, N).  Default: hash(k, N) = h2(h1(k), N).  If _Hash is anything other
70   // than the default, _H1 and _H2 are ignored.
71
72   // _RehashPolicy: Policy class with three members, all of which govern
73   // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
74   // than n.  _M_bkt_for_elements(n) returns a bucket count appropriate
75   // for an element count of n.  _M_need_rehash(n_bkt, n_elt, n_ins)
76   // determines whether, if the current bucket count is n_bkt and the
77   // current element count is n_elt, we need to increase the bucket
78   // count.  If so, returns make_pair(true, n), where n is the new
79   // bucket count.  If not, returns make_pair(false, <anything>).
80
81   // ??? Right now it is hard-wired that the number of buckets never
82   // shrinks.  Should we allow _RehashPolicy to change that?
83
84   // __cache_hash_code: bool.  true if we store the value of the hash
85   // function along with the value.  This is a time-space tradeoff.
86   // Storing it may improve lookup speed by reducing the number of times
87   // we need to call the Equal function.
88
89   // __constant_iterators: bool.  true if iterator and const_iterator are
90   // both constant iterator types.  This is true for unordered_set and
91   // unordered_multiset, false for unordered_map and unordered_multimap.
92
93   // __unique_keys: bool.  true if the return value of _Hashtable::count(k)
94   // is always at most one, false if it may be an arbitrary number.  This
95   // true for unordered_set and unordered_map, false for unordered_multiset
96   // and unordered_multimap.
97
98   template<typename _Key, typename _Value, typename _Allocator,
99            typename _ExtractKey, typename _Equal,
100            typename _H1, typename _H2, typename _Hash,
101            typename _RehashPolicy,
102            bool __cache_hash_code,
103            bool __constant_iterators,
104            bool __unique_keys>
105     class _Hashtable
106     : public __detail::_Rehash_base<_RehashPolicy,
107                                     _Hashtable<_Key, _Value, _Allocator,
108                                                _ExtractKey,
109                                                _Equal, _H1, _H2, _Hash,
110                                                _RehashPolicy,
111                                                __cache_hash_code,
112                                                __constant_iterators,
113                                                __unique_keys> >,
114       public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
115                                        _H1, _H2, _Hash, __cache_hash_code>,
116       public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
117                                  _Hashtable<_Key, _Value, _Allocator,
118                                             _ExtractKey,
119                                             _Equal, _H1, _H2, _Hash,
120                                             _RehashPolicy,
121                                             __cache_hash_code,
122                                             __constant_iterators,
123                                             __unique_keys> >,
124       public __detail::_Equality_base<_ExtractKey, __unique_keys,
125                                       _Hashtable<_Key, _Value, _Allocator,
126                                                  _ExtractKey,
127                                                  _Equal, _H1, _H2, _Hash,
128                                                  _RehashPolicy,
129                                                  __cache_hash_code,
130                                                  __constant_iterators,
131                                                  __unique_keys> >
132     {
133     public:
134       typedef _Allocator                                  allocator_type;
135       typedef _Value                                      value_type;
136       typedef _Key                                        key_type;
137       typedef _Equal                                      key_equal;
138       // mapped_type, if present, comes from _Map_base.
139       // hasher, if present, comes from _Hash_code_base.
140       typedef typename _Allocator::pointer                pointer;
141       typedef typename _Allocator::const_pointer          const_pointer;
142       typedef typename _Allocator::reference              reference;
143       typedef typename _Allocator::const_reference        const_reference;
144
145       typedef std::size_t                                 size_type;
146       typedef std::ptrdiff_t                              difference_type;
147       typedef __detail::_Node_iterator<value_type, __constant_iterators,
148                                        __cache_hash_code>
149                                                           local_iterator;
150       typedef __detail::_Node_const_iterator<value_type,
151                                              __constant_iterators,
152                                              __cache_hash_code>
153                                                           const_local_iterator;
154
155       typedef __detail::_Hashtable_iterator<value_type, __constant_iterators,
156                                             __cache_hash_code>
157                                                           iterator;
158       typedef __detail::_Hashtable_const_iterator<value_type,
159                                                   __constant_iterators,
160                                                   __cache_hash_code>
161                                                           const_iterator;
162
163       template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
164                typename _Hashtable2>
165         friend struct __detail::_Map_base;
166
167     private:
168       typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
169       typedef typename _Allocator::template rebind<_Node>::other
170                                                         _Node_allocator_type;
171       typedef typename _Allocator::template rebind<_Node*>::other
172                                                         _Bucket_allocator_type;
173
174       typedef typename _Allocator::template rebind<_Value>::other
175                                                         _Value_allocator_type;
176
177       _Node_allocator_type   _M_node_allocator;
178       _Node**                _M_buckets;
179       size_type              _M_bucket_count;
180       size_type              _M_begin_bucket_index; // First non-empty bucket.
181       size_type              _M_element_count;
182       _RehashPolicy          _M_rehash_policy;
183
184       template<typename... _Args>
185         _Node*
186         _M_allocate_node(_Args&&... __args);
187
188       void
189       _M_deallocate_node(_Node* __n);
190
191       void
192       _M_deallocate_nodes(_Node**, size_type);
193
194       _Node**
195       _M_allocate_buckets(size_type __n);
196
197       void
198       _M_deallocate_buckets(_Node**, size_type __n);
199
200     public:
201       // Constructor, destructor, assignment, swap
202       _Hashtable(size_type __bucket_hint,
203                  const _H1&, const _H2&, const _Hash&,
204                  const _Equal&, const _ExtractKey&,
205                  const allocator_type&);
206
207       template<typename _InputIterator>
208         _Hashtable(_InputIterator __first, _InputIterator __last,
209                    size_type __bucket_hint,
210                    const _H1&, const _H2&, const _Hash&,
211                    const _Equal&, const _ExtractKey&,
212                    const allocator_type&);
213
214       _Hashtable(const _Hashtable&);
215
216       _Hashtable(_Hashtable&&);
217
218       _Hashtable&
219       operator=(const _Hashtable& __ht)
220       {
221         _Hashtable __tmp(__ht);
222         this->swap(__tmp);
223         return *this;
224       }
225
226       _Hashtable&
227       operator=(_Hashtable&& __ht)
228       {
229         // NB: DR 1204.
230         // NB: DR 675.
231         this->clear();
232         this->swap(__ht);
233         return *this;
234       }
235
236       ~_Hashtable() noexcept;
237
238       void swap(_Hashtable&);
239
240       // Basic container operations
241       iterator
242       begin() noexcept
243       { return iterator(_M_buckets + _M_begin_bucket_index); }
244
245       const_iterator
246       begin() const noexcept
247       { return const_iterator(_M_buckets + _M_begin_bucket_index); }
248
249       iterator
250       end() noexcept
251       { return iterator(_M_buckets + _M_bucket_count); }
252
253       const_iterator
254       end() const noexcept
255       { return const_iterator(_M_buckets + _M_bucket_count); }
256
257       const_iterator
258       cbegin() const noexcept
259       { return const_iterator(_M_buckets + _M_begin_bucket_index); }
260
261       const_iterator
262       cend() const noexcept
263       { return const_iterator(_M_buckets + _M_bucket_count); }
264
265       size_type
266       size() const noexcept
267       { return _M_element_count; }
268
269       bool
270       empty() const noexcept
271       { return size() == 0; }
272
273       allocator_type
274       get_allocator() const noexcept
275       { return allocator_type(_M_node_allocator); }
276
277       size_type
278       max_size() const noexcept
279       { return _M_node_allocator.max_size(); }
280
281       // Observers
282       key_equal
283       key_eq() const
284       { return this->_M_eq; }
285
286       // hash_function, if present, comes from _Hash_code_base.
287
288       // Bucket operations
289       size_type
290       bucket_count() const noexcept
291       { return _M_bucket_count; }
292
293       size_type
294       max_bucket_count() const noexcept
295       { return max_size(); }
296
297       size_type
298       bucket_size(size_type __n) const
299       { return std::distance(begin(__n), end(__n)); }
300
301       size_type
302       bucket(const key_type& __k) const
303       {
304         return this->_M_bucket_index(__k, this->_M_hash_code(__k),
305                                      bucket_count());
306       }
307
308       local_iterator
309       begin(size_type __n)
310       { return local_iterator(_M_buckets[__n]); }
311
312       local_iterator
313       end(size_type)
314       { return local_iterator(0); }
315
316       const_local_iterator
317       begin(size_type __n) const
318       { return const_local_iterator(_M_buckets[__n]); }
319
320       const_local_iterator
321       end(size_type) const
322       { return const_local_iterator(0); }
323
324       // DR 691.
325       const_local_iterator
326       cbegin(size_type __n) const
327       { return const_local_iterator(_M_buckets[__n]); }
328
329       const_local_iterator
330       cend(size_type) const
331       { return const_local_iterator(0); }
332
333       float
334       load_factor() const noexcept
335       {
336         return static_cast<float>(size()) / static_cast<float>(bucket_count());
337       }
338
339       // max_load_factor, if present, comes from _Rehash_base.
340
341       // Generalization of max_load_factor.  Extension, not found in TR1.  Only
342       // useful if _RehashPolicy is something other than the default.
343       const _RehashPolicy&
344       __rehash_policy() const
345       { return _M_rehash_policy; }
346
347       void
348       __rehash_policy(const _RehashPolicy&);
349
350       // Lookup.
351       iterator
352       find(const key_type& __k);
353
354       const_iterator
355       find(const key_type& __k) const;
356
357       size_type
358       count(const key_type& __k) const;
359
360       std::pair<iterator, iterator>
361       equal_range(const key_type& __k);
362
363       std::pair<const_iterator, const_iterator>
364       equal_range(const key_type& __k) const;
365
366     private:
367       // Find and insert helper functions and types
368       _Node*
369       _M_find_node(_Node*, const key_type&,
370                    typename _Hashtable::_Hash_code_type) const;
371
372       template<typename _Arg>
373         iterator
374         _M_insert_bucket(_Arg&&, size_type,
375                          typename _Hashtable::_Hash_code_type);
376
377       typedef typename std::conditional<__unique_keys,
378                                         std::pair<iterator, bool>,
379                                         iterator>::type
380         _Insert_Return_Type;
381
382       typedef typename std::conditional<__unique_keys,
383                                         std::_Select1st<_Insert_Return_Type>,
384                                         std::_Identity<_Insert_Return_Type>
385                                    >::type
386         _Insert_Conv_Type;
387
388     protected:
389       template<typename _Arg>
390         std::pair<iterator, bool>
391         _M_insert(_Arg&&, std::true_type);
392
393       template<typename _Arg>
394         iterator
395         _M_insert(_Arg&&, std::false_type);
396
397     public:
398       // Insert and erase
399       _Insert_Return_Type
400       insert(const value_type& __v)
401       { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
402
403       iterator
404       insert(const_iterator, const value_type& __v)
405       { return _Insert_Conv_Type()(insert(__v)); }
406
407       template<typename _Pair, typename = typename
408         std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
409                               std::is_convertible<_Pair,
410                                                   value_type>>::value>::type>
411         _Insert_Return_Type
412         insert(_Pair&& __v)
413         { return _M_insert(std::forward<_Pair>(__v),
414                            integral_constant<bool, __unique_keys>()); }
415
416       template<typename _Pair, typename = typename
417         std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
418                               std::is_convertible<_Pair,
419                                                   value_type>>::value>::type>
420         iterator
421         insert(const_iterator, _Pair&& __v)
422         { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
423
424       template<typename _InputIterator>
425         void
426         insert(_InputIterator __first, _InputIterator __last);
427
428       void
429       insert(initializer_list<value_type> __l)
430       { this->insert(__l.begin(), __l.end()); }
431
432       iterator
433       erase(const_iterator);
434
435       // LWG 2059.
436       iterator
437       erase(iterator __it)
438       { return erase(const_iterator(__it)); }
439
440       size_type
441       erase(const key_type&);
442
443       iterator
444       erase(const_iterator, const_iterator);
445
446       void
447       clear() noexcept;
448
449       // Set number of buckets to be appropriate for container of n element.
450       void rehash(size_type __n);
451
452       // DR 1189.
453       // reserve, if present, comes from _Rehash_base.
454
455     private:
456       // Unconditionally change size of bucket array to n, restore hash policy
457       // resize value to __next_resize on exception.
458       void _M_rehash(size_type __n, size_type __next_resize);
459     };
460
461
462   // Definitions of class template _Hashtable's out-of-line member functions.
463   template<typename _Key, typename _Value,
464            typename _Allocator, typename _ExtractKey, typename _Equal,
465            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
466            bool __chc, bool __cit, bool __uk>
467     template<typename... _Args>
468       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
469                           _H1, _H2, _Hash, _RehashPolicy,
470                           __chc, __cit, __uk>::_Node*
471       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
472                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
473       _M_allocate_node(_Args&&... __args)
474       {
475         _Node* __n = _M_node_allocator.allocate(1);
476         __try
477           {
478             _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
479             __n->_M_next = 0;
480             return __n;
481           }
482         __catch(...)
483           {
484             _M_node_allocator.deallocate(__n, 1);
485             __throw_exception_again;
486           }
487       }
488
489   template<typename _Key, typename _Value,
490            typename _Allocator, typename _ExtractKey, typename _Equal,
491            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
492            bool __chc, bool __cit, bool __uk>
493     void
494     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
495                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
496     _M_deallocate_node(_Node* __n)
497     {
498       _M_node_allocator.destroy(__n);
499       _M_node_allocator.deallocate(__n, 1);
500     }
501
502   template<typename _Key, typename _Value,
503            typename _Allocator, typename _ExtractKey, typename _Equal,
504            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
505            bool __chc, bool __cit, bool __uk>
506     void
507     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
508                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
509     _M_deallocate_nodes(_Node** __array, size_type __n)
510     {
511       for (size_type __i = 0; __i < __n; ++__i)
512         {
513           _Node* __p = __array[__i];
514           while (__p)
515             {
516               _Node* __tmp = __p;
517               __p = __p->_M_next;
518               _M_deallocate_node(__tmp);
519             }
520           __array[__i] = 0;
521         }
522     }
523
524   template<typename _Key, typename _Value,
525            typename _Allocator, typename _ExtractKey, typename _Equal,
526            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
527            bool __chc, bool __cit, bool __uk>
528     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
529                         _H1, _H2, _Hash, _RehashPolicy,
530                         __chc, __cit, __uk>::_Node**
531     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
532                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
533     _M_allocate_buckets(size_type __n)
534     {
535       _Bucket_allocator_type __alloc(_M_node_allocator);
536
537       // We allocate one extra bucket to hold a sentinel, an arbitrary
538       // non-null pointer.  Iterator increment relies on this.
539       _Node** __p = __alloc.allocate(__n + 1);
540       std::fill(__p, __p + __n, (_Node*) 0);
541       __p[__n] = reinterpret_cast<_Node*>(0x1000);
542       return __p;
543     }
544
545   template<typename _Key, typename _Value,
546            typename _Allocator, typename _ExtractKey, typename _Equal,
547            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
548            bool __chc, bool __cit, bool __uk>
549     void
550     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
551                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
552     _M_deallocate_buckets(_Node** __p, size_type __n)
553     {
554       _Bucket_allocator_type __alloc(_M_node_allocator);
555       __alloc.deallocate(__p, __n + 1);
556     }
557
558   template<typename _Key, typename _Value,
559            typename _Allocator, typename _ExtractKey, typename _Equal,
560            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
561            bool __chc, bool __cit, bool __uk>
562     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
563                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
564     _Hashtable(size_type __bucket_hint,
565                const _H1& __h1, const _H2& __h2, const _Hash& __h,
566                const _Equal& __eq, const _ExtractKey& __exk,
567                const allocator_type& __a)
568     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
569       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
570                                 _H1, _H2, _Hash, __chc>(__exk, __eq,
571                                                         __h1, __h2, __h),
572       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
573       _M_node_allocator(__a),
574       _M_bucket_count(0),
575       _M_element_count(0),
576       _M_rehash_policy()
577     {
578       _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
579       _M_buckets = _M_allocate_buckets(_M_bucket_count);
580       _M_begin_bucket_index = _M_bucket_count;
581     }
582
583   template<typename _Key, typename _Value,
584            typename _Allocator, typename _ExtractKey, typename _Equal,
585            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
586            bool __chc, bool __cit, bool __uk>
587     template<typename _InputIterator>
588       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
589                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
590       _Hashtable(_InputIterator __f, _InputIterator __l,
591                  size_type __bucket_hint,
592                  const _H1& __h1, const _H2& __h2, const _Hash& __h,
593                  const _Equal& __eq, const _ExtractKey& __exk,
594                  const allocator_type& __a)
595       : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
596         __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
597                                   _H1, _H2, _Hash, __chc>(__exk, __eq,
598                                                           __h1, __h2, __h),
599         __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
600         _M_node_allocator(__a),
601         _M_bucket_count(0),
602         _M_element_count(0),
603         _M_rehash_policy()
604       {
605         _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
606                                    _M_rehash_policy.
607                                    _M_bkt_for_elements(__detail::
608                                                        __distance_fw(__f,
609                                                                      __l)));
610         _M_buckets = _M_allocate_buckets(_M_bucket_count);
611         _M_begin_bucket_index = _M_bucket_count;
612         __try
613           {
614             for (; __f != __l; ++__f)
615               this->insert(*__f);
616           }
617         __catch(...)
618           {
619             clear();
620             _M_deallocate_buckets(_M_buckets, _M_bucket_count);
621             __throw_exception_again;
622           }
623       }
624
625   template<typename _Key, typename _Value,
626            typename _Allocator, typename _ExtractKey, typename _Equal,
627            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
628            bool __chc, bool __cit, bool __uk>
629     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
630                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
631     _Hashtable(const _Hashtable& __ht)
632     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
633       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
634                                 _H1, _H2, _Hash, __chc>(__ht),
635       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
636       _M_node_allocator(__ht._M_node_allocator),
637       _M_bucket_count(__ht._M_bucket_count),
638       _M_begin_bucket_index(__ht._M_begin_bucket_index),
639       _M_element_count(__ht._M_element_count),
640       _M_rehash_policy(__ht._M_rehash_policy)
641     {
642       _M_buckets = _M_allocate_buckets(_M_bucket_count);
643       __try
644         {
645           for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
646             {
647               _Node* __n = __ht._M_buckets[__i];
648               _Node** __tail = _M_buckets + __i;
649               while (__n)
650                 {
651                   *__tail = _M_allocate_node(__n->_M_v);
652                   this->_M_copy_code(*__tail, __n);
653                   __tail = &((*__tail)->_M_next);
654                   __n = __n->_M_next;
655                 }
656             }
657         }
658       __catch(...)
659         {
660           clear();
661           _M_deallocate_buckets(_M_buckets, _M_bucket_count);
662           __throw_exception_again;
663         }
664     }
665
666   template<typename _Key, typename _Value,
667            typename _Allocator, typename _ExtractKey, typename _Equal,
668            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
669            bool __chc, bool __cit, bool __uk>
670     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
671                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
672     _Hashtable(_Hashtable&& __ht)
673     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
674       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
675                                 _H1, _H2, _Hash, __chc>(__ht),
676       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
677       _M_node_allocator(std::move(__ht._M_node_allocator)),
678       _M_buckets(__ht._M_buckets),
679       _M_bucket_count(__ht._M_bucket_count),
680       _M_begin_bucket_index(__ht._M_begin_bucket_index),
681       _M_element_count(__ht._M_element_count),
682       _M_rehash_policy(__ht._M_rehash_policy)
683     {
684       __ht._M_rehash_policy = _RehashPolicy();
685       __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
686       __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
687       __ht._M_begin_bucket_index = __ht._M_bucket_count;
688       __ht._M_element_count = 0;
689     }
690
691   template<typename _Key, typename _Value,
692            typename _Allocator, typename _ExtractKey, typename _Equal,
693            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
694            bool __chc, bool __cit, bool __uk>
695     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
696                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
697     ~_Hashtable() noexcept
698     {
699       clear();
700       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
701     }
702
703   template<typename _Key, typename _Value,
704            typename _Allocator, typename _ExtractKey, typename _Equal,
705            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
706            bool __chc, bool __cit, bool __uk>
707     void
708     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
709                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
710     swap(_Hashtable& __x)
711     {
712       // The only base class with member variables is hash_code_base.  We
713       // define _Hash_code_base::_M_swap because different specializations
714       // have different members.
715       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
716         _H1, _H2, _Hash, __chc>::_M_swap(__x);
717
718       // _GLIBCXX_RESOLVE_LIB_DEFECTS
719       // 431. Swapping containers with unequal allocators.
720       std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
721                                                         __x._M_node_allocator);
722
723       std::swap(_M_rehash_policy, __x._M_rehash_policy);
724       std::swap(_M_buckets, __x._M_buckets);
725       std::swap(_M_bucket_count, __x._M_bucket_count);
726       std::swap(_M_begin_bucket_index, __x._M_begin_bucket_index);
727       std::swap(_M_element_count, __x._M_element_count);
728     }
729
730   template<typename _Key, typename _Value,
731            typename _Allocator, typename _ExtractKey, typename _Equal,
732            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
733            bool __chc, bool __cit, bool __uk>
734     void
735     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
736                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
737     __rehash_policy(const _RehashPolicy& __pol)
738     {
739       size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
740       if (__n_bkt > _M_bucket_count)
741         _M_rehash(__n_bkt, _M_rehash_policy._M_next_resize);
742       _M_rehash_policy = __pol;
743     }
744
745   template<typename _Key, typename _Value,
746            typename _Allocator, typename _ExtractKey, typename _Equal,
747            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
748            bool __chc, bool __cit, bool __uk>
749     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
750                         _H1, _H2, _Hash, _RehashPolicy,
751                         __chc, __cit, __uk>::iterator
752     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
753                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
754     find(const key_type& __k)
755     {
756       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
757       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
758       _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
759       return __p ? iterator(__p, _M_buckets + __n) : this->end();
760     }
761
762   template<typename _Key, typename _Value,
763            typename _Allocator, typename _ExtractKey, typename _Equal,
764            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
765            bool __chc, bool __cit, bool __uk>
766     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
767                         _H1, _H2, _Hash, _RehashPolicy,
768                         __chc, __cit, __uk>::const_iterator
769     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
770                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
771     find(const key_type& __k) const
772     {
773       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
774       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
775       _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
776       return __p ? const_iterator(__p, _M_buckets + __n) : this->end();
777     }
778
779   template<typename _Key, typename _Value,
780            typename _Allocator, typename _ExtractKey, typename _Equal,
781            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
782            bool __chc, bool __cit, bool __uk>
783     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
784                         _H1, _H2, _Hash, _RehashPolicy,
785                         __chc, __cit, __uk>::size_type
786     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
787                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
788     count(const key_type& __k) const
789     {
790       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
791       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
792       std::size_t __result = 0;
793       for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)
794         if (this->_M_compare(__k, __code, __p))
795           ++__result;
796       return __result;
797     }
798
799   template<typename _Key, typename _Value,
800            typename _Allocator, typename _ExtractKey, typename _Equal,
801            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
802            bool __chc, bool __cit, bool __uk>
803     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
804                                   _ExtractKey, _Equal, _H1,
805                                   _H2, _Hash, _RehashPolicy,
806                                   __chc, __cit, __uk>::iterator,
807               typename _Hashtable<_Key, _Value, _Allocator,
808                                   _ExtractKey, _Equal, _H1,
809                                   _H2, _Hash, _RehashPolicy,
810                                   __chc, __cit, __uk>::iterator>
811     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
812                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
813     equal_range(const key_type& __k)
814     {
815       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
816       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
817       _Node** __head = _M_buckets + __n;
818       _Node* __p = _M_find_node(*__head, __k, __code);
819
820       if (__p)
821         {
822           _Node* __p1 = __p->_M_next;
823           for (; __p1; __p1 = __p1->_M_next)
824             if (!this->_M_compare(__k, __code, __p1))
825               break;
826
827           iterator __first(__p, __head);
828           iterator __last(__p1, __head);
829           if (!__p1)
830             __last._M_incr_bucket();
831           return std::make_pair(__first, __last);
832         }
833       else
834         return std::make_pair(this->end(), this->end());
835     }
836
837   template<typename _Key, typename _Value,
838            typename _Allocator, typename _ExtractKey, typename _Equal,
839            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
840            bool __chc, bool __cit, bool __uk>
841     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
842                                   _ExtractKey, _Equal, _H1,
843                                   _H2, _Hash, _RehashPolicy,
844                                   __chc, __cit, __uk>::const_iterator,
845               typename _Hashtable<_Key, _Value, _Allocator,
846                                   _ExtractKey, _Equal, _H1,
847                                   _H2, _Hash, _RehashPolicy,
848                                   __chc, __cit, __uk>::const_iterator>
849     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
850                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
851     equal_range(const key_type& __k) const
852     {
853       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
854       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
855       _Node** __head = _M_buckets + __n;
856       _Node* __p = _M_find_node(*__head, __k, __code);
857
858       if (__p)
859         {
860           _Node* __p1 = __p->_M_next;
861           for (; __p1; __p1 = __p1->_M_next)
862             if (!this->_M_compare(__k, __code, __p1))
863               break;
864
865           const_iterator __first(__p, __head);
866           const_iterator __last(__p1, __head);
867           if (!__p1)
868             __last._M_incr_bucket();
869           return std::make_pair(__first, __last);
870         }
871       else
872         return std::make_pair(this->end(), this->end());
873     }
874
875   // Find the node whose key compares equal to k, beginning the search
876   // at p (usually the head of a bucket).  Return nullptr if no node is found.
877   template<typename _Key, typename _Value,
878            typename _Allocator, typename _ExtractKey, typename _Equal,
879            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
880            bool __chc, bool __cit, bool __uk>
881     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
882                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
883                         __chc, __cit, __uk>::_Node*
884     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
885                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
886     _M_find_node(_Node* __p, const key_type& __k,
887                 typename _Hashtable::_Hash_code_type __code) const
888     {
889       for (; __p; __p = __p->_M_next)
890         if (this->_M_compare(__k, __code, __p))
891           return __p;
892       return nullptr;
893     }
894
895   // Insert v in bucket n (assumes no element with its key already present).
896   template<typename _Key, typename _Value,
897            typename _Allocator, typename _ExtractKey, typename _Equal,
898            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
899            bool __chc, bool __cit, bool __uk>
900     template<typename _Arg>
901       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
902                           _H1, _H2, _Hash, _RehashPolicy,
903                           __chc, __cit, __uk>::iterator
904       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
905                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
906       _M_insert_bucket(_Arg&& __v, size_type __n,
907                        typename _Hashtable::_Hash_code_type __code)
908       {
909         const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
910         std::pair<bool, std::size_t> __do_rehash
911           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
912                                             _M_element_count, 1);
913
914         if (__do_rehash.first)
915           {
916             const key_type& __k = this->_M_extract(__v);
917             __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
918           }
919
920         _Node* __new_node = 0;
921         __try
922           {
923             // Allocate the new node before doing the rehash so that we
924             // don't do a rehash if the allocation throws.
925             __new_node = _M_allocate_node(std::forward<_Arg>(__v));
926             if (__do_rehash.first)
927               _M_rehash(__do_rehash.second, __saved_next_resize);
928
929             __new_node->_M_next = _M_buckets[__n];
930             this->_M_store_code(__new_node, __code);
931             _M_buckets[__n] = __new_node;
932             ++_M_element_count;
933             if (__n < _M_begin_bucket_index)
934               _M_begin_bucket_index = __n;
935             return iterator(__new_node, _M_buckets + __n);
936           }
937         __catch(...)
938           {
939             if (!__new_node)
940               _M_rehash_policy._M_next_resize = __saved_next_resize;
941             else
942               _M_deallocate_node(__new_node);
943             __throw_exception_again;
944           }
945       }
946
947   // Insert v if no element with its key is already present.
948   template<typename _Key, typename _Value,
949            typename _Allocator, typename _ExtractKey, typename _Equal,
950            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
951            bool __chc, bool __cit, bool __uk>
952     template<typename _Arg>
953       std::pair<typename _Hashtable<_Key, _Value, _Allocator,
954                                     _ExtractKey, _Equal, _H1,
955                                     _H2, _Hash, _RehashPolicy,
956                                     __chc, __cit, __uk>::iterator, bool>
957       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
958                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
959       _M_insert(_Arg&& __v, std::true_type)
960       {
961         const key_type& __k = this->_M_extract(__v);
962         typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
963         size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
964
965         if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
966           return std::make_pair(iterator(__p, _M_buckets + __n), false);
967         return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
968                               __n, __code), true);
969       }
970
971   // Insert v unconditionally.
972   template<typename _Key, typename _Value,
973            typename _Allocator, typename _ExtractKey, typename _Equal,
974            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
975            bool __chc, bool __cit, bool __uk>
976     template<typename _Arg>
977       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
978                           _H1, _H2, _Hash, _RehashPolicy,
979                           __chc, __cit, __uk>::iterator
980       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
981                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
982       _M_insert(_Arg&& __v, std::false_type)
983       {
984         const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
985         std::pair<bool, std::size_t> __do_rehash
986           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
987                                             _M_element_count, 1);
988         if (__do_rehash.first)
989           _M_rehash(__do_rehash.second, __saved_next_resize);
990
991         const key_type& __k = this->_M_extract(__v);
992         typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
993         size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
994
995         // First find the node, avoid leaking new_node if compare throws.
996         _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
997         _Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v));
998
999         if (__prev)
1000           {
1001             __new_node->_M_next = __prev->_M_next;
1002             __prev->_M_next = __new_node;
1003           }
1004         else
1005           {
1006             __new_node->_M_next = _M_buckets[__n];
1007             _M_buckets[__n] = __new_node;
1008             if (__n < _M_begin_bucket_index)
1009               _M_begin_bucket_index = __n;
1010           }
1011         this->_M_store_code(__new_node, __code);
1012
1013         ++_M_element_count;
1014         return iterator(__new_node, _M_buckets + __n);
1015       }
1016
1017   template<typename _Key, typename _Value,
1018            typename _Allocator, typename _ExtractKey, typename _Equal,
1019            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1020            bool __chc, bool __cit, bool __uk>
1021     template<typename _InputIterator>
1022       void
1023       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1024                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1025       insert(_InputIterator __first, _InputIterator __last)
1026       {
1027         size_type __n_elt = __detail::__distance_fw(__first, __last);
1028         const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
1029         std::pair<bool, std::size_t> __do_rehash
1030           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1031                                             _M_element_count, __n_elt);
1032         if (__do_rehash.first)
1033           _M_rehash(__do_rehash.second, __saved_next_resize);
1034
1035         for (; __first != __last; ++__first)
1036           this->insert(*__first);
1037       }
1038
1039   template<typename _Key, typename _Value,
1040            typename _Allocator, typename _ExtractKey, typename _Equal,
1041            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1042            bool __chc, bool __cit, bool __uk>
1043     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1044                         _H1, _H2, _Hash, _RehashPolicy,
1045                         __chc, __cit, __uk>::iterator
1046     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1047                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1048     erase(const_iterator __it)
1049     {
1050       iterator __result(__it._M_cur_node, __it._M_cur_bucket);
1051       ++__result;
1052
1053       _Node* __cur = *__it._M_cur_bucket;
1054       if (__cur == __it._M_cur_node)
1055         {
1056           *__it._M_cur_bucket = __cur->_M_next;
1057
1058           // If _M_begin_bucket_index no longer indexes the first non-empty
1059           // bucket - its single node is being erased - update it.
1060           if (!_M_buckets[_M_begin_bucket_index])
1061             _M_begin_bucket_index = __result._M_cur_bucket - _M_buckets;
1062         }
1063       else
1064         {
1065           _Node* __next = __cur->_M_next;
1066           while (__next != __it._M_cur_node)
1067             {
1068               __cur = __next;
1069               __next = __cur->_M_next;
1070             }
1071           __cur->_M_next = __next->_M_next;
1072         }
1073
1074       _M_deallocate_node(__it._M_cur_node);
1075       --_M_element_count;
1076
1077       return __result;
1078     }
1079
1080   template<typename _Key, typename _Value,
1081            typename _Allocator, typename _ExtractKey, typename _Equal,
1082            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1083            bool __chc, bool __cit, bool __uk>
1084     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1085                         _H1, _H2, _Hash, _RehashPolicy,
1086                         __chc, __cit, __uk>::size_type
1087     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1088                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1089     erase(const key_type& __k)
1090     {
1091       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1092       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
1093       size_type __result = 0;
1094
1095       _Node** __slot = _M_buckets + __n;
1096       while (*__slot && !this->_M_compare(__k, __code, *__slot))
1097         __slot = &((*__slot)->_M_next);
1098
1099       _Node** __saved_slot = 0;
1100       while (*__slot && this->_M_compare(__k, __code, *__slot))
1101         {
1102           // _GLIBCXX_RESOLVE_LIB_DEFECTS
1103           // 526. Is it undefined if a function in the standard changes
1104           // in parameters?
1105           if (std::__addressof(this->_M_extract((*__slot)->_M_v))
1106               != std::__addressof(__k))
1107             {
1108               _Node* __p = *__slot;
1109               *__slot = __p->_M_next;
1110               _M_deallocate_node(__p);
1111               --_M_element_count;
1112               ++__result;
1113             }
1114           else
1115             {
1116               __saved_slot = __slot;
1117               __slot = &((*__slot)->_M_next);
1118             }
1119         }
1120
1121       if (__saved_slot)
1122         {
1123           _Node* __p = *__saved_slot;
1124           *__saved_slot = __p->_M_next;
1125           _M_deallocate_node(__p);
1126           --_M_element_count;
1127           ++__result;
1128         }
1129
1130       // If the entire bucket indexed by _M_begin_bucket_index has been
1131       // erased look forward for the first non-empty bucket.
1132       if (!_M_buckets[_M_begin_bucket_index])
1133         {
1134           if (!_M_element_count)
1135             _M_begin_bucket_index = _M_bucket_count;
1136           else
1137             {
1138               ++_M_begin_bucket_index;
1139               while (!_M_buckets[_M_begin_bucket_index])
1140                 ++_M_begin_bucket_index;
1141             }
1142         }
1143
1144       return __result;
1145     }
1146
1147   // ??? This could be optimized by taking advantage of the bucket
1148   // structure, but it's not clear that it's worth doing.  It probably
1149   // wouldn't even be an optimization unless the load factor is large.
1150   template<typename _Key, typename _Value,
1151            typename _Allocator, typename _ExtractKey, typename _Equal,
1152            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1153            bool __chc, bool __cit, bool __uk>
1154     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1155                         _H1, _H2, _Hash, _RehashPolicy,
1156                         __chc, __cit, __uk>::iterator
1157     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1158                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1159     erase(const_iterator __first, const_iterator __last)
1160     {
1161        while (__first != __last)
1162          __first = this->erase(__first);
1163       return iterator(__last._M_cur_node, __last._M_cur_bucket);
1164     }
1165
1166   template<typename _Key, typename _Value,
1167            typename _Allocator, typename _ExtractKey, typename _Equal,
1168            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1169            bool __chc, bool __cit, bool __uk>
1170     void
1171     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1172                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1173     clear() noexcept
1174     {
1175       _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1176       _M_element_count = 0;
1177       _M_begin_bucket_index = _M_bucket_count;
1178     }
1179
1180   template<typename _Key, typename _Value,
1181            typename _Allocator, typename _ExtractKey, typename _Equal,
1182            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1183            bool __chc, bool __cit, bool __uk>
1184     void
1185     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1186                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1187     rehash(size_type __n)
1188     {
1189       const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
1190       _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1191                          _M_rehash_policy._M_bkt_for_elements(_M_element_count
1192                                                               + 1)),
1193                 __saved_next_resize);
1194     }
1195
1196   template<typename _Key, typename _Value,
1197            typename _Allocator, typename _ExtractKey, typename _Equal,
1198            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1199            bool __chc, bool __cit, bool __uk>
1200     void
1201     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1202                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1203     _M_rehash(size_type __n, size_type __next_resize)
1204     {
1205       _Node** __new_array = 0;
1206       __try
1207         {
1208           __new_array = _M_allocate_buckets(__n);
1209           _M_begin_bucket_index = __n;
1210           for (size_type __i = 0; __i < _M_bucket_count; ++__i)
1211             while (_Node* __p = _M_buckets[__i])
1212               {
1213                 std::size_t __new_index = this->_M_bucket_index(__p, __n);
1214                 _M_buckets[__i] = __p->_M_next;
1215                 __p->_M_next = __new_array[__new_index];
1216                 __new_array[__new_index] = __p;
1217                 if (__new_index < _M_begin_bucket_index)
1218                   _M_begin_bucket_index = __new_index;
1219               }
1220           _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1221           _M_bucket_count = __n;
1222           _M_buckets = __new_array;
1223         }
1224       __catch(...)
1225         {
1226           if (__new_array)
1227             {
1228               // A failure here means that a hash function threw an exception.
1229               // We can't restore the previous state without calling the hash
1230               // function again, so the only sensible recovery is to delete
1231               // everything.
1232               _M_deallocate_nodes(__new_array, __n);
1233               _M_deallocate_buckets(__new_array, __n);
1234               _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1235               _M_element_count = 0;
1236               _M_begin_bucket_index = _M_bucket_count;
1237               _M_rehash_policy._M_next_resize = 0;
1238             }
1239           else
1240             // A failure here means that buckets allocation failed.  We only
1241             // have to restore hash policy previous state.
1242             _M_rehash_policy._M_next_resize = __next_resize;
1243           __throw_exception_again;
1244         }
1245     }
1246
1247 _GLIBCXX_END_NAMESPACE_VERSION
1248 } // namespace std
1249
1250 #endif // _HASHTABLE_H