OSDN Git Service

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