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