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