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, 2012
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /** @file bits/hashtable.h
27  * This is an internal header file, included by other library headers.
28  * Do not attempt to use it directly. @headername{unordered_map, unordered_set}
29  */
30 
31 #ifndef _HASHTABLE_H
32 #define _HASHTABLE_H 1
33 
34 #pragma GCC system_header
35 
36 #include <bits/hashtable_policy.h>
37 
38 namespace std _GLIBCXX_VISIBILITY(default)
39 {
40 _GLIBCXX_BEGIN_NAMESPACE_VERSION
41 
42  // Class template _Hashtable, class definition.
43 
44  // Meaning of class template _Hashtable's template parameters
45 
46  // _Key and _Value: arbitrary CopyConstructible types.
47 
48  // _Allocator: an allocator type ([lib.allocator.requirements]) whose
49  // value type is Value. As a conforming extension, we allow for
50  // value type != Value.
51 
52  // _ExtractKey: function object that takes an object of type Value
53  // and returns a value of type _Key.
54 
55  // _Equal: function object that takes two objects of type k and returns
56  // a bool-like value that is true if the two objects are considered equal.
57 
58  // _H1: the hash function. A unary function object with argument type
59  // Key and result type size_t. Return values should be distributed
60  // over the entire range [0, numeric_limits<size_t>:::max()].
61 
62  // _H2: the range-hashing function (in the terminology of Tavori and
63  // Dreizin). A binary function object whose argument types and result
64  // type are all size_t. Given arguments r and N, the return value is
65  // in the range [0, N).
66 
67  // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
68  // whose argument types are _Key and size_t and whose result type is
69  // size_t. Given arguments k and N, the return value is in the range
70  // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other
71  // than the default, _H1 and _H2 are ignored.
72 
73  // _RehashPolicy: Policy class with three members, all of which govern
74  // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
75  // than n. _M_bkt_for_elements(n) returns a bucket count appropriate
76  // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins)
77  // determines whether, if the current bucket count is n_bkt and the
78  // current element count is n_elt, we need to increase the bucket
79  // count. If so, returns make_pair(true, n), where n is the new
80  // bucket count. If not, returns make_pair(false, <anything>).
81 
82  // __cache_hash_code: bool. true if we store the value of the hash
83  // function along with the value. This is a time-space tradeoff.
84  // Storing it may improve lookup speed by reducing the number of times
85  // we need to call the Equal function.
86 
87  // __constant_iterators: bool. true if iterator and const_iterator are
88  // both constant iterator types. This is true for unordered_set and
89  // unordered_multiset, false for unordered_map and unordered_multimap.
90 
91  // __unique_keys: bool. true if the return value of _Hashtable::count(k)
92  // is always at most one, false if it may be an arbitrary number. This
93  // true for unordered_set and unordered_map, false for unordered_multiset
94  // and unordered_multimap.
95  /**
96  * Here's _Hashtable data structure, each _Hashtable has:
97  * - _Bucket[] _M_buckets
98  * - _Hash_node_base _M_before_begin
99  * - size_type _M_bucket_count
100  * - size_type _M_element_count
101  *
102  * with _Bucket being _Hash_node* and _Hash_node constaining:
103  * - _Hash_node* _M_next
104  * - Tp _M_value
105  * - size_t _M_code if cache_hash_code is true
106  *
107  * In terms of Standard containers the hastable is like the aggregation of:
108  * - std::forward_list<_Node> containing the elements
109  * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
110  *
111  * The non-empty buckets contain the node before the first bucket node. This
112  * design allow to implement something like a std::forward_list::insert_after
113  * on container insertion and std::forward_list::erase_after on container
114  * erase calls. _M_before_begin is equivalent to
115  * std::foward_list::before_begin. Empty buckets are containing nullptr.
116  * Note that one of the non-empty bucket contains &_M_before_begin which is
117  * not a derefenrenceable node so the node pointers in buckets shall never be
118  * derefenrenced, only its next node can be.
119  *
120  * Walk through a bucket nodes require a check on the hash code to see if the
121  * node is still in the bucket. Such a design impose a quite efficient hash
122  * functor and is one of the reasons it is highly advise to set
123  * __cache_hash_code to true.
124  *
125  * The container iterators are simply built from nodes. This way incrementing
126  * the iterator is perfectly efficient independent of how many empty buckets
127  * there are in the container.
128  *
129  * On insert we compute element hash code and thanks to it find the bucket
130  * index. If the element must be inserted on an empty bucket we add it at the
131  * beginning of the singly linked list and make the bucket point to
132  * _M_before_begin. The bucket that used to point to _M_before_begin, if any,
133  * is updated to point to its new before begin node.
134  *
135  * On erase, the simple iterator design impose to use the hash functor to get
136  * the index of the bucket to update. For this reason, when __cache_hash_code
137  * is set to false, there is a static assertion that the hash functor cannot
138  * throw.
139  */
140 
141  template<typename _Key, typename _Value, typename _Allocator,
142  typename _ExtractKey, typename _Equal,
143  typename _H1, typename _H2, typename _Hash,
144  typename _RehashPolicy,
145  bool __cache_hash_code,
146  bool __constant_iterators,
147  bool __unique_keys>
149  : public __detail::_Rehash_base<_RehashPolicy,
150  _Hashtable<_Key, _Value, _Allocator,
151  _ExtractKey,
152  _Equal, _H1, _H2, _Hash,
153  _RehashPolicy,
154  __cache_hash_code,
155  __constant_iterators,
156  __unique_keys> >,
157  public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
158  _H1, _H2, _Hash, __cache_hash_code>,
159  public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
160  _Hashtable<_Key, _Value, _Allocator,
161  _ExtractKey,
162  _Equal, _H1, _H2, _Hash,
163  _RehashPolicy,
164  __cache_hash_code,
165  __constant_iterators,
166  __unique_keys> >,
167  public __detail::_Equality_base<_ExtractKey, __unique_keys,
168  _Hashtable<_Key, _Value, _Allocator,
169  _ExtractKey,
170  _Equal, _H1, _H2, _Hash,
171  _RehashPolicy,
172  __cache_hash_code,
173  __constant_iterators,
174  __unique_keys> >
175  {
176  template<typename _Cond>
177  using __if_hash_code_cached
178  = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
179 
180  template<typename _Cond>
181  using __if_hash_code_not_cached
182  = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
183 
184  // When hash codes are not cached the hash functor shall not throw
185  // because it is used in methods (erase, swap...) that shall not throw.
186  static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key,
187  _H1>>::value,
188  "Cache the hash code or qualify your hash functor with noexcept");
189 
190  // Following two static assertions are necessary to guarantee that
191  // swapping two hashtable instances won't invalidate associated local
192  // iterators.
193 
194  // When hash codes are cached local iterator only uses H2 which must then
195  // be empty.
196  static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
197  "Functor used to map hash code to bucket index must be empty");
198 
199  typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
200  _H1, _H2, _Hash,
201  __cache_hash_code> _HCBase;
202 
203  // When hash codes are not cached local iterator is going to use _HCBase
204  // above to compute node bucket index so it has to be empty.
205  static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value,
206  "Cache the hash code or make functors involved in hash code"
207  " and bucket index computation empty");
208 
209  public:
210  typedef _Allocator allocator_type;
211  typedef _Value value_type;
212  typedef _Key key_type;
213  typedef _Equal key_equal;
214  // mapped_type, if present, comes from _Map_base.
215  // hasher, if present, comes from _Hash_code_base.
216  typedef typename _Allocator::pointer pointer;
217  typedef typename _Allocator::const_pointer const_pointer;
218  typedef typename _Allocator::reference reference;
219  typedef typename _Allocator::const_reference const_reference;
220 
221  typedef std::size_t size_type;
222  typedef std::ptrdiff_t difference_type;
223  typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
224  _H1, _H2, _Hash,
225  __constant_iterators,
226  __cache_hash_code>
227  local_iterator;
228  typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
229  _H1, _H2, _Hash,
230  __constant_iterators,
231  __cache_hash_code>
232  const_local_iterator;
233  typedef __detail::_Node_iterator<value_type, __constant_iterators,
234  __cache_hash_code>
235  iterator;
236  typedef __detail::_Node_const_iterator<value_type,
237  __constant_iterators,
238  __cache_hash_code>
239  const_iterator;
240 
241  template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
242  typename _Hashtable2>
243  friend struct __detail::_Map_base;
244 
245  private:
246  typedef typename _RehashPolicy::_State _RehashPolicyState;
247  typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
248  typedef typename _Allocator::template rebind<_Node>::other
249  _Node_allocator_type;
250  typedef __detail::_Hash_node_base _BaseNode;
251  typedef _BaseNode* _Bucket;
252  typedef typename _Allocator::template rebind<_Bucket>::other
253  _Bucket_allocator_type;
254 
255  typedef typename _Allocator::template rebind<_Value>::other
256  _Value_allocator_type;
257 
258  _Node_allocator_type _M_node_allocator;
259  _Bucket* _M_buckets;
260  size_type _M_bucket_count;
261  _BaseNode _M_before_begin;
262  size_type _M_element_count;
263  _RehashPolicy _M_rehash_policy;
264 
265  template<typename... _Args>
266  _Node*
267  _M_allocate_node(_Args&&... __args);
268 
269  void
270  _M_deallocate_node(_Node* __n);
271 
272  // Deallocate the linked list of nodes pointed to by __n
273  void
274  _M_deallocate_nodes(_Node* __n);
275 
276  _Bucket*
277  _M_allocate_buckets(size_type __n);
278 
279  void
280  _M_deallocate_buckets(_Bucket*, size_type __n);
281 
282  // Gets bucket begin, deals with the fact that non-empty buckets contain
283  // their before begin node.
284  _Node*
285  _M_bucket_begin(size_type __bkt) const;
286 
287  _Node*
288  _M_begin() const
289  { return static_cast<_Node*>(_M_before_begin._M_nxt); }
290 
291  public:
292  // Constructor, destructor, assignment, swap
293  _Hashtable(size_type __bucket_hint,
294  const _H1&, const _H2&, const _Hash&,
295  const _Equal&, const _ExtractKey&,
296  const allocator_type&);
297 
298  template<typename _InputIterator>
299  _Hashtable(_InputIterator __first, _InputIterator __last,
300  size_type __bucket_hint,
301  const _H1&, const _H2&, const _Hash&,
302  const _Equal&, const _ExtractKey&,
303  const allocator_type&);
304 
305  _Hashtable(const _Hashtable&);
306 
308 
309  _Hashtable&
310  operator=(const _Hashtable& __ht)
311  {
312  _Hashtable __tmp(__ht);
313  this->swap(__tmp);
314  return *this;
315  }
316 
317  _Hashtable&
318  operator=(_Hashtable&& __ht)
319  {
320  // NB: DR 1204.
321  // NB: DR 675.
322  this->clear();
323  this->swap(__ht);
324  return *this;
325  }
326 
327  ~_Hashtable() noexcept;
328 
329  void swap(_Hashtable&);
330 
331  // Basic container operations
332  iterator
333  begin() noexcept
334  { return iterator(_M_begin()); }
335 
336  const_iterator
337  begin() const noexcept
338  { return const_iterator(_M_begin()); }
339 
340  iterator
341  end() noexcept
342  { return iterator(nullptr); }
343 
344  const_iterator
345  end() const noexcept
346  { return const_iterator(nullptr); }
347 
348  const_iterator
349  cbegin() const noexcept
350  { return const_iterator(_M_begin()); }
351 
352  const_iterator
353  cend() const noexcept
354  { return const_iterator(nullptr); }
355 
356  size_type
357  size() const noexcept
358  { return _M_element_count; }
359 
360  bool
361  empty() const noexcept
362  { return size() == 0; }
363 
364  allocator_type
365  get_allocator() const noexcept
366  { return allocator_type(_M_node_allocator); }
367 
368  size_type
369  max_size() const noexcept
370  { return _M_node_allocator.max_size(); }
371 
372  // Observers
373  key_equal
374  key_eq() const
375  { return this->_M_eq(); }
376 
377  // hash_function, if present, comes from _Hash_code_base.
378 
379  // Bucket operations
380  size_type
381  bucket_count() const noexcept
382  { return _M_bucket_count; }
383 
384  size_type
385  max_bucket_count() const noexcept
386  { return max_size(); }
387 
388  size_type
389  bucket_size(size_type __n) const
390  { return std::distance(begin(__n), end(__n)); }
391 
392  size_type
393  bucket(const key_type& __k) const
394  { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
395 
396  local_iterator
397  begin(size_type __n)
398  { return local_iterator(_M_bucket_begin(__n), __n,
399  _M_bucket_count); }
400 
401  local_iterator
402  end(size_type __n)
403  { return local_iterator(nullptr, __n, _M_bucket_count); }
404 
405  const_local_iterator
406  begin(size_type __n) const
407  { return const_local_iterator(_M_bucket_begin(__n), __n,
408  _M_bucket_count); }
409 
410  const_local_iterator
411  end(size_type __n) const
412  { return const_local_iterator(nullptr, __n, _M_bucket_count); }
413 
414  // DR 691.
415  const_local_iterator
416  cbegin(size_type __n) const
417  { return const_local_iterator(_M_bucket_begin(__n), __n,
418  _M_bucket_count); }
419 
420  const_local_iterator
421  cend(size_type __n) const
422  { return const_local_iterator(nullptr, __n, _M_bucket_count); }
423 
424  float
425  load_factor() const noexcept
426  {
427  return static_cast<float>(size()) / static_cast<float>(bucket_count());
428  }
429 
430  // max_load_factor, if present, comes from _Rehash_base.
431 
432  // Generalization of max_load_factor. Extension, not found in TR1. Only
433  // useful if _RehashPolicy is something other than the default.
434  const _RehashPolicy&
435  __rehash_policy() const
436  { return _M_rehash_policy; }
437 
438  void
439  __rehash_policy(const _RehashPolicy&);
440 
441  // Lookup.
442  iterator
443  find(const key_type& __k);
444 
445  const_iterator
446  find(const key_type& __k) const;
447 
448  size_type
449  count(const key_type& __k) const;
450 
452  equal_range(const key_type& __k);
453 
455  equal_range(const key_type& __k) const;
456 
457  private:
458  // Bucket index computation helpers.
459  size_type
460  _M_bucket_index(_Node* __n) const
461  { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
462 
463  size_type
464  _M_bucket_index(const key_type& __k,
465  typename _Hashtable::_Hash_code_type __c) const
466  { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
467 
468  // Find and insert helper functions and types
469  // Find the node before the one matching the criteria.
470  _BaseNode*
471  _M_find_before_node(size_type, const key_type&,
472  typename _Hashtable::_Hash_code_type) const;
473 
474  _Node*
475  _M_find_node(size_type __bkt, const key_type& __key,
476  typename _Hashtable::_Hash_code_type __c) const
477  {
478  _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c);
479  if (__before_n)
480  return static_cast<_Node*>(__before_n->_M_nxt);
481  return nullptr;
482  }
483 
484  // Insert a node at the beginning of a bucket.
485  void
486  _M_insert_bucket_begin(size_type, _Node*);
487 
488  // Remove the bucket first node
489  void
490  _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
491  size_type __next_bkt);
492 
493  // Get the node before __n in the bucket __bkt
494  _BaseNode*
495  _M_get_previous_node(size_type __bkt, _BaseNode* __n);
496 
497  template<typename _Arg>
498  iterator
499  _M_insert_bucket(_Arg&&, size_type,
500  typename _Hashtable::_Hash_code_type);
501 
502  typedef typename std::conditional<__unique_keys,
504  iterator>::type
506 
507  typedef typename std::conditional<__unique_keys,
508  std::_Select1st<_Insert_Return_Type>,
509  std::_Identity<_Insert_Return_Type>
510  >::type
512 
513  protected:
514  template<typename... _Args>
516  _M_emplace(std::true_type, _Args&&... __args);
517 
518  template<typename... _Args>
519  iterator
520  _M_emplace(std::false_type, _Args&&... __args);
521 
522  template<typename _Arg>
524  _M_insert(_Arg&&, std::true_type);
525 
526  template<typename _Arg>
527  iterator
528  _M_insert(_Arg&&, std::false_type);
529 
530  public:
531  // Emplace, insert and erase
532  template<typename... _Args>
534  emplace(_Args&&... __args)
535  { return _M_emplace(integral_constant<bool, __unique_keys>(),
536  std::forward<_Args>(__args)...); }
537 
538  template<typename... _Args>
539  iterator
540  emplace_hint(const_iterator, _Args&&... __args)
541  { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }
542 
544  insert(const value_type& __v)
545  { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
546 
547  iterator
548  insert(const_iterator, const value_type& __v)
549  { return _Insert_Conv_Type()(insert(__v)); }
550 
551  template<typename _Pair, typename = typename
553  std::is_constructible<value_type,
554  _Pair&&>>::value>::type>
556  insert(_Pair&& __v)
557  { return _M_insert(std::forward<_Pair>(__v),
559 
560  template<typename _Pair, typename = typename
562  std::is_constructible<value_type,
563  _Pair&&>>::value>::type>
564  iterator
565  insert(const_iterator, _Pair&& __v)
566  { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
567 
568  template<typename _InputIterator>
569  void
570  insert(_InputIterator __first, _InputIterator __last);
571 
572  void
573  insert(initializer_list<value_type> __l)
574  { this->insert(__l.begin(), __l.end()); }
575 
576  iterator
577  erase(const_iterator);
578 
579  // LWG 2059.
580  iterator
581  erase(iterator __it)
582  { return erase(const_iterator(__it)); }
583 
584  size_type
585  erase(const key_type&);
586 
587  iterator
588  erase(const_iterator, const_iterator);
589 
590  void
591  clear() noexcept;
592 
593  // Set number of buckets to be appropriate for container of n element.
594  void rehash(size_type __n);
595 
596  // DR 1189.
597  // reserve, if present, comes from _Rehash_base.
598 
599  private:
600  // Helper rehash method used when keys are unique.
601  void _M_rehash_aux(size_type __n, std::true_type);
602 
603  // Helper rehash method used when keys can be non-unique.
604  void _M_rehash_aux(size_type __n, std::false_type);
605 
606  // Unconditionally change size of bucket array to n, restore hash policy
607  // state to __state on exception.
608  void _M_rehash(size_type __n, const _RehashPolicyState& __state);
609  };
610 
611 
612  // Definitions of class template _Hashtable's out-of-line member functions.
613  template<typename _Key, typename _Value,
614  typename _Allocator, typename _ExtractKey, typename _Equal,
615  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
616  bool __chc, bool __cit, bool __uk>
617  template<typename... _Args>
618  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
619  _H1, _H2, _Hash, _RehashPolicy,
620  __chc, __cit, __uk>::_Node*
621  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
622  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
623  _M_allocate_node(_Args&&... __args)
624  {
625  _Node* __n = _M_node_allocator.allocate(1);
626  __try
627  {
628  _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
629  return __n;
630  }
631  __catch(...)
632  {
633  _M_node_allocator.deallocate(__n, 1);
634  __throw_exception_again;
635  }
636  }
637 
638  template<typename _Key, typename _Value,
639  typename _Allocator, typename _ExtractKey, typename _Equal,
640  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
641  bool __chc, bool __cit, bool __uk>
642  void
643  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
644  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
645  _M_deallocate_node(_Node* __n)
646  {
647  _M_node_allocator.destroy(__n);
648  _M_node_allocator.deallocate(__n, 1);
649  }
650 
651  template<typename _Key, typename _Value,
652  typename _Allocator, typename _ExtractKey, typename _Equal,
653  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
654  bool __chc, bool __cit, bool __uk>
655  void
656  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
657  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
658  _M_deallocate_nodes(_Node* __n)
659  {
660  while (__n)
661  {
662  _Node* __tmp = __n;
663  __n = __n->_M_next();
664  _M_deallocate_node(__tmp);
665  }
666  }
667 
668  template<typename _Key, typename _Value,
669  typename _Allocator, typename _ExtractKey, typename _Equal,
670  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
671  bool __chc, bool __cit, bool __uk>
672  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
673  _H1, _H2, _Hash, _RehashPolicy,
674  __chc, __cit, __uk>::_Bucket*
675  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
676  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
677  _M_allocate_buckets(size_type __n)
678  {
679  _Bucket_allocator_type __alloc(_M_node_allocator);
680 
681  _Bucket* __p = __alloc.allocate(__n);
682  __builtin_memset(__p, 0, __n * sizeof(_Bucket));
683  return __p;
684  }
685 
686  template<typename _Key, typename _Value,
687  typename _Allocator, typename _ExtractKey, typename _Equal,
688  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
689  bool __chc, bool __cit, bool __uk>
690  void
691  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
692  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
693  _M_deallocate_buckets(_Bucket* __p, size_type __n)
694  {
695  _Bucket_allocator_type __alloc(_M_node_allocator);
696  __alloc.deallocate(__p, __n);
697  }
698 
699  template<typename _Key, typename _Value,
700  typename _Allocator, typename _ExtractKey, typename _Equal,
701  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
702  bool __chc, bool __cit, bool __uk>
703  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
704  _Equal, _H1, _H2, _Hash, _RehashPolicy,
705  __chc, __cit, __uk>::_Node*
706  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
707  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
708  _M_bucket_begin(size_type __bkt) const
709  {
710  _BaseNode* __n = _M_buckets[__bkt];
711  return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr;
712  }
713 
714  template<typename _Key, typename _Value,
715  typename _Allocator, typename _ExtractKey, typename _Equal,
716  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
717  bool __chc, bool __cit, bool __uk>
718  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
719  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
720  _Hashtable(size_type __bucket_hint,
721  const _H1& __h1, const _H2& __h2, const _Hash& __h,
722  const _Equal& __eq, const _ExtractKey& __exk,
723  const allocator_type& __a)
724  : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
725  __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
726  _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
727  __eq),
728  __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
729  _M_node_allocator(__a),
730  _M_bucket_count(0),
731  _M_element_count(0),
732  _M_rehash_policy()
733  {
734  _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
735  // We don't want the rehash policy to ask for the hashtable to shrink
736  // on the first insertion so we need to reset its previous resize level.
737  _M_rehash_policy._M_prev_resize = 0;
738  _M_buckets = _M_allocate_buckets(_M_bucket_count);
739  }
740 
741  template<typename _Key, typename _Value,
742  typename _Allocator, typename _ExtractKey, typename _Equal,
743  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
744  bool __chc, bool __cit, bool __uk>
745  template<typename _InputIterator>
746  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
747  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
748  _Hashtable(_InputIterator __f, _InputIterator __l,
749  size_type __bucket_hint,
750  const _H1& __h1, const _H2& __h2, const _Hash& __h,
751  const _Equal& __eq, const _ExtractKey& __exk,
752  const allocator_type& __a)
753  : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
754  __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
755  _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
756  __eq),
757  __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
758  _M_node_allocator(__a),
759  _M_bucket_count(0),
760  _M_element_count(0),
761  _M_rehash_policy()
762  {
763  _M_bucket_count =
764  _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f,
765  __l));
766  if (_M_bucket_count <= __bucket_hint)
767  _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
768 
769  // We don't want the rehash policy to ask for the hashtable to shrink
770  // on the first insertion so we need to reset its previous resize
771  // level.
772  _M_rehash_policy._M_prev_resize = 0;
773  _M_buckets = _M_allocate_buckets(_M_bucket_count);
774  __try
775  {
776  for (; __f != __l; ++__f)
777  this->insert(*__f);
778  }
779  __catch(...)
780  {
781  clear();
782  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
783  __throw_exception_again;
784  }
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  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
792  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
793  _Hashtable(const _Hashtable& __ht)
794  : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
795  __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
796  _H1, _H2, _Hash, __chc>(__ht),
797  __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
798  _M_node_allocator(__ht._M_node_allocator),
799  _M_bucket_count(__ht._M_bucket_count),
800  _M_element_count(__ht._M_element_count),
801  _M_rehash_policy(__ht._M_rehash_policy)
802  {
803  _M_buckets = _M_allocate_buckets(_M_bucket_count);
804  __try
805  {
806  if (!__ht._M_before_begin._M_nxt)
807  return;
808 
809  // First deal with the special first node pointed to by
810  // _M_before_begin.
811  const _Node* __ht_n = __ht._M_begin();
812  _Node* __this_n = _M_allocate_node(__ht_n->_M_v);
813  this->_M_copy_code(__this_n, __ht_n);
814  _M_before_begin._M_nxt = __this_n;
815  _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
816 
817  // Then deal with other nodes.
818  _BaseNode* __prev_n = __this_n;
819  for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
820  {
821  __this_n = _M_allocate_node(__ht_n->_M_v);
822  __prev_n->_M_nxt = __this_n;
823  this->_M_copy_code(__this_n, __ht_n);
824  size_type __bkt = _M_bucket_index(__this_n);
825  if (!_M_buckets[__bkt])
826  _M_buckets[__bkt] = __prev_n;
827  __prev_n = __this_n;
828  }
829  }
830  __catch(...)
831  {
832  clear();
833  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
834  __throw_exception_again;
835  }
836  }
837 
838  template<typename _Key, typename _Value,
839  typename _Allocator, typename _ExtractKey, typename _Equal,
840  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
841  bool __chc, bool __cit, bool __uk>
842  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
843  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
844  _Hashtable(_Hashtable&& __ht)
845  : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
846  __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
847  _H1, _H2, _Hash, __chc>(__ht),
848  __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
849  _M_node_allocator(std::move(__ht._M_node_allocator)),
850  _M_buckets(__ht._M_buckets),
851  _M_bucket_count(__ht._M_bucket_count),
852  _M_before_begin(__ht._M_before_begin._M_nxt),
853  _M_element_count(__ht._M_element_count),
854  _M_rehash_policy(__ht._M_rehash_policy)
855  {
856  // Update, if necessary, bucket pointing to before begin that hasn't move.
857  if (_M_begin())
858  _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
859  __ht._M_rehash_policy = _RehashPolicy();
860  __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
861  __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
862  __ht._M_before_begin._M_nxt = nullptr;
863  __ht._M_element_count = 0;
864  }
865 
866  template<typename _Key, typename _Value,
867  typename _Allocator, typename _ExtractKey, typename _Equal,
868  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
869  bool __chc, bool __cit, bool __uk>
870  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
871  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
872  ~_Hashtable() noexcept
873  {
874  clear();
875  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
876  }
877 
878  template<typename _Key, typename _Value,
879  typename _Allocator, typename _ExtractKey, typename _Equal,
880  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
881  bool __chc, bool __cit, bool __uk>
882  void
883  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
884  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
885  swap(_Hashtable& __x)
886  {
887  // The only base class with member variables is hash_code_base. We
888  // define _Hash_code_base::_M_swap because different specializations
889  // have different members.
890  this->_M_swap(__x);
891 
892  // _GLIBCXX_RESOLVE_LIB_DEFECTS
893  // 431. Swapping containers with unequal allocators.
894  std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
895  __x._M_node_allocator);
896 
897  std::swap(_M_rehash_policy, __x._M_rehash_policy);
898  std::swap(_M_buckets, __x._M_buckets);
899  std::swap(_M_bucket_count, __x._M_bucket_count);
900  std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
901  std::swap(_M_element_count, __x._M_element_count);
902  // Fix buckets containing the _M_before_begin pointers that can't be
903  // swapped.
904  if (_M_begin())
905  _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
906  if (__x._M_begin())
907  __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
908  = &(__x._M_before_begin);
909  }
910 
911  template<typename _Key, typename _Value,
912  typename _Allocator, typename _ExtractKey, typename _Equal,
913  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
914  bool __chc, bool __cit, bool __uk>
915  void
916  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
917  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
918  __rehash_policy(const _RehashPolicy& __pol)
919  {
920  size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
921  if (__n_bkt != _M_bucket_count)
922  _M_rehash(__n_bkt, _M_rehash_policy._M_state());
923  _M_rehash_policy = __pol;
924  }
925 
926  template<typename _Key, typename _Value,
927  typename _Allocator, typename _ExtractKey, typename _Equal,
928  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
929  bool __chc, bool __cit, bool __uk>
930  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
931  _H1, _H2, _Hash, _RehashPolicy,
932  __chc, __cit, __uk>::iterator
933  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
934  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
935  find(const key_type& __k)
936  {
937  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
938  std::size_t __n = _M_bucket_index(__k, __code);
939  _Node* __p = _M_find_node(__n, __k, __code);
940  return __p ? iterator(__p) : this->end();
941  }
942 
943  template<typename _Key, typename _Value,
944  typename _Allocator, typename _ExtractKey, typename _Equal,
945  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
946  bool __chc, bool __cit, bool __uk>
947  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
948  _H1, _H2, _Hash, _RehashPolicy,
949  __chc, __cit, __uk>::const_iterator
950  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
951  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
952  find(const key_type& __k) const
953  {
954  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
955  std::size_t __n = _M_bucket_index(__k, __code);
956  _Node* __p = _M_find_node(__n, __k, __code);
957  return __p ? const_iterator(__p) : this->end();
958  }
959 
960  template<typename _Key, typename _Value,
961  typename _Allocator, typename _ExtractKey, typename _Equal,
962  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
963  bool __chc, bool __cit, bool __uk>
964  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
965  _H1, _H2, _Hash, _RehashPolicy,
966  __chc, __cit, __uk>::size_type
967  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
968  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
969  count(const key_type& __k) const
970  {
971  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
972  std::size_t __n = _M_bucket_index(__k, __code);
973  _Node* __p = _M_bucket_begin(__n);
974  if (!__p)
975  return 0;
976 
977  std::size_t __result = 0;
978  for (;; __p = __p->_M_next())
979  {
980  if (this->_M_equals(__k, __code, __p))
981  ++__result;
982  else if (__result)
983  // All equivalent values are next to each other, if we found a not
984  // equivalent value after an equivalent one it means that we won't
985  // find anymore an equivalent value.
986  break;
987  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
988  break;
989  }
990  return __result;
991  }
992 
993  template<typename _Key, typename _Value,
994  typename _Allocator, typename _ExtractKey, typename _Equal,
995  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
996  bool __chc, bool __cit, bool __uk>
997  std::pair<typename _Hashtable<_Key, _Value, _Allocator,
998  _ExtractKey, _Equal, _H1,
999  _H2, _Hash, _RehashPolicy,
1000  __chc, __cit, __uk>::iterator,
1001  typename _Hashtable<_Key, _Value, _Allocator,
1002  _ExtractKey, _Equal, _H1,
1003  _H2, _Hash, _RehashPolicy,
1004  __chc, __cit, __uk>::iterator>
1005  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1006  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1007  equal_range(const key_type& __k)
1008  {
1009  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1010  std::size_t __n = _M_bucket_index(__k, __code);
1011  _Node* __p = _M_find_node(__n, __k, __code);
1012 
1013  if (__p)
1014  {
1015  _Node* __p1 = __p->_M_next();
1016  while (__p1 && _M_bucket_index(__p1) == __n
1017  && this->_M_equals(__k, __code, __p1))
1018  __p1 = __p1->_M_next();
1019 
1020  return std::make_pair(iterator(__p), iterator(__p1));
1021  }
1022  else
1023  return std::make_pair(this->end(), this->end());
1024  }
1025 
1026  template<typename _Key, typename _Value,
1027  typename _Allocator, typename _ExtractKey, typename _Equal,
1028  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1029  bool __chc, bool __cit, bool __uk>
1030  std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1031  _ExtractKey, _Equal, _H1,
1032  _H2, _Hash, _RehashPolicy,
1033  __chc, __cit, __uk>::const_iterator,
1034  typename _Hashtable<_Key, _Value, _Allocator,
1035  _ExtractKey, _Equal, _H1,
1036  _H2, _Hash, _RehashPolicy,
1037  __chc, __cit, __uk>::const_iterator>
1038  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1039  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1040  equal_range(const key_type& __k) const
1041  {
1042  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1043  std::size_t __n = _M_bucket_index(__k, __code);
1044  _Node* __p = _M_find_node(__n, __k, __code);
1045 
1046  if (__p)
1047  {
1048  _Node* __p1 = __p->_M_next();
1049  while (__p1 && _M_bucket_index(__p1) == __n
1050  && this->_M_equals(__k, __code, __p1))
1051  __p1 = __p1->_M_next();
1052 
1053  return std::make_pair(const_iterator(__p), const_iterator(__p1));
1054  }
1055  else
1056  return std::make_pair(this->end(), this->end());
1057  }
1058 
1059  // Find the node whose key compares equal to k in the bucket n. Return nullptr
1060  // if no node is found.
1061  template<typename _Key, typename _Value,
1062  typename _Allocator, typename _ExtractKey, typename _Equal,
1063  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1064  bool __chc, bool __cit, bool __uk>
1065  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1066  _Equal, _H1, _H2, _Hash, _RehashPolicy,
1067  __chc, __cit, __uk>::_BaseNode*
1068  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1069  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1070  _M_find_before_node(size_type __n, const key_type& __k,
1071  typename _Hashtable::_Hash_code_type __code) const
1072  {
1073  _BaseNode* __prev_p = _M_buckets[__n];
1074  if (!__prev_p)
1075  return nullptr;
1076  _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt);
1077  for (;; __p = __p->_M_next())
1078  {
1079  if (this->_M_equals(__k, __code, __p))
1080  return __prev_p;
1081  if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
1082  break;
1083  __prev_p = __p;
1084  }
1085  return nullptr;
1086  }
1087 
1088  template<typename _Key, typename _Value,
1089  typename _Allocator, typename _ExtractKey, typename _Equal,
1090  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1091  bool __chc, bool __cit, bool __uk>
1092  void
1093  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1094  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1095  _M_insert_bucket_begin(size_type __bkt, _Node* __new_node)
1096  {
1097  if (_M_buckets[__bkt])
1098  {
1099  // Bucket is not empty, we just need to insert the new node after the
1100  // bucket before begin.
1101  __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1102  _M_buckets[__bkt]->_M_nxt = __new_node;
1103  }
1104  else
1105  {
1106  // The bucket is empty, the new node is inserted at the beginning of
1107  // the singly linked list and the bucket will contain _M_before_begin
1108  // pointer.
1109  __new_node->_M_nxt = _M_before_begin._M_nxt;
1110  _M_before_begin._M_nxt = __new_node;
1111  if (__new_node->_M_nxt)
1112  // We must update former begin bucket that is pointing to
1113  // _M_before_begin.
1114  _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node;
1115  _M_buckets[__bkt] = &_M_before_begin;
1116  }
1117  }
1118 
1119  template<typename _Key, typename _Value,
1120  typename _Allocator, typename _ExtractKey, typename _Equal,
1121  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1122  bool __chc, bool __cit, bool __uk>
1123  void
1124  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1125  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1126  _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt)
1127  {
1128  if (!__next || __next_bkt != __bkt)
1129  {
1130  // Bucket is now empty
1131  // First update next bucket if any
1132  if (__next)
1133  _M_buckets[__next_bkt] = _M_buckets[__bkt];
1134  // Second update before begin node if necessary
1135  if (&_M_before_begin == _M_buckets[__bkt])
1136  _M_before_begin._M_nxt = __next;
1137  _M_buckets[__bkt] = nullptr;
1138  }
1139  }
1140 
1141  template<typename _Key, typename _Value,
1142  typename _Allocator, typename _ExtractKey, typename _Equal,
1143  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1144  bool __chc, bool __cit, bool __uk>
1145  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1146  _Equal, _H1, _H2, _Hash, _RehashPolicy,
1147  __chc, __cit, __uk>::_BaseNode*
1148  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1149  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1150  _M_get_previous_node(size_type __bkt, _BaseNode* __n)
1151  {
1152  _BaseNode* __prev_n = _M_buckets[__bkt];
1153  while (__prev_n->_M_nxt != __n)
1154  __prev_n = __prev_n->_M_nxt;
1155  return __prev_n;
1156  }
1157 
1158  template<typename _Key, typename _Value,
1159  typename _Allocator, typename _ExtractKey, typename _Equal,
1160  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1161  bool __chc, bool __cit, bool __uk>
1162  template<typename... _Args>
1163  std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1164  _ExtractKey, _Equal, _H1,
1165  _H2, _Hash, _RehashPolicy,
1166  __chc, __cit, __uk>::iterator, bool>
1167  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1168  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1169  _M_emplace(std::true_type, _Args&&... __args)
1170  {
1171  // First build the node to get access to the hash code
1172  _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1173  __try
1174  {
1175  const key_type& __k = this->_M_extract()(__new_node->_M_v);
1176  typename _Hashtable::_Hash_code_type __code
1177  = this->_M_hash_code(__k);
1178  size_type __bkt = _M_bucket_index(__k, __code);
1179 
1180  if (_Node* __p = _M_find_node(__bkt, __k, __code))
1181  {
1182  // There is already an equivalent node, no insertion
1183  _M_deallocate_node(__new_node);
1184  return std::make_pair(iterator(__p), false);
1185  }
1186 
1187  // We are going to insert this node
1188  this->_M_store_code(__new_node, __code);
1189  const _RehashPolicyState& __saved_state
1190  = _M_rehash_policy._M_state();
1191  std::pair<bool, std::size_t> __do_rehash
1192  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1193  _M_element_count, 1);
1194 
1195  if (__do_rehash.first)
1196  {
1197  _M_rehash(__do_rehash.second, __saved_state);
1198  __bkt = _M_bucket_index(__k, __code);
1199  }
1200 
1201  _M_insert_bucket_begin(__bkt, __new_node);
1202  ++_M_element_count;
1203  return std::make_pair(iterator(__new_node), true);
1204  }
1205  __catch(...)
1206  {
1207  _M_deallocate_node(__new_node);
1208  __throw_exception_again;
1209  }
1210  }
1211 
1212  template<typename _Key, typename _Value,
1213  typename _Allocator, typename _ExtractKey, typename _Equal,
1214  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1215  bool __chc, bool __cit, bool __uk>
1216  template<typename... _Args>
1217  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1218  _H1, _H2, _Hash, _RehashPolicy,
1219  __chc, __cit, __uk>::iterator
1220  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1221  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1222  _M_emplace(std::false_type, _Args&&... __args)
1223  {
1224  const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1225  std::pair<bool, std::size_t> __do_rehash
1226  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1227  _M_element_count, 1);
1228 
1229  // First build the node to get its hash code.
1230  _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1231  __try
1232  {
1233  const key_type& __k = this->_M_extract()(__new_node->_M_v);
1234  typename _Hashtable::_Hash_code_type __code
1235  = this->_M_hash_code(__k);
1236  this->_M_store_code(__new_node, __code);
1237 
1238  // Second, do rehash if necessary.
1239  if (__do_rehash.first)
1240  _M_rehash(__do_rehash.second, __saved_state);
1241 
1242  // Third, find the node before an equivalent one.
1243  size_type __bkt = _M_bucket_index(__k, __code);
1244  _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code);
1245 
1246  if (__prev)
1247  {
1248  // Insert after the node before the equivalent one.
1249  __new_node->_M_nxt = __prev->_M_nxt;
1250  __prev->_M_nxt = __new_node;
1251  }
1252  else
1253  // The inserted node has no equivalent in the hashtable. We must
1254  // insert the new node at the beginning of the bucket to preserve
1255  // equivalent elements relative positions.
1256  _M_insert_bucket_begin(__bkt, __new_node);
1257  ++_M_element_count;
1258  return iterator(__new_node);
1259  }
1260  __catch(...)
1261  {
1262  _M_deallocate_node(__new_node);
1263  __throw_exception_again;
1264  }
1265  }
1266 
1267  // Insert v in bucket n (assumes no element with its key already present).
1268  template<typename _Key, typename _Value,
1269  typename _Allocator, typename _ExtractKey, typename _Equal,
1270  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1271  bool __chc, bool __cit, bool __uk>
1272  template<typename _Arg>
1273  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1274  _H1, _H2, _Hash, _RehashPolicy,
1275  __chc, __cit, __uk>::iterator
1276  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1277  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1278  _M_insert_bucket(_Arg&& __v, size_type __n,
1279  typename _Hashtable::_Hash_code_type __code)
1280  {
1281  const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1282  std::pair<bool, std::size_t> __do_rehash
1283  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1284  _M_element_count, 1);
1285 
1286  if (__do_rehash.first)
1287  {
1288  const key_type& __k = this->_M_extract()(__v);
1289  __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
1290  }
1291 
1292  _Node* __new_node = nullptr;
1293  __try
1294  {
1295  // Allocate the new node before doing the rehash so that we
1296  // don't do a rehash if the allocation throws.
1297  __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1298  this->_M_store_code(__new_node, __code);
1299  if (__do_rehash.first)
1300  _M_rehash(__do_rehash.second, __saved_state);
1301 
1302  _M_insert_bucket_begin(__n, __new_node);
1303  ++_M_element_count;
1304  return iterator(__new_node);
1305  }
1306  __catch(...)
1307  {
1308  if (!__new_node)
1309  _M_rehash_policy._M_reset(__saved_state);
1310  else
1311  _M_deallocate_node(__new_node);
1312  __throw_exception_again;
1313  }
1314  }
1315 
1316  // Insert v if no element with its key is already present.
1317  template<typename _Key, typename _Value,
1318  typename _Allocator, typename _ExtractKey, typename _Equal,
1319  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1320  bool __chc, bool __cit, bool __uk>
1321  template<typename _Arg>
1322  std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1323  _ExtractKey, _Equal, _H1,
1324  _H2, _Hash, _RehashPolicy,
1325  __chc, __cit, __uk>::iterator, bool>
1326  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1327  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1328  _M_insert(_Arg&& __v, std::true_type)
1329  {
1330  const key_type& __k = this->_M_extract()(__v);
1331  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1332  size_type __n = _M_bucket_index(__k, __code);
1333 
1334  if (_Node* __p = _M_find_node(__n, __k, __code))
1335  return std::make_pair(iterator(__p), false);
1336  return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
1337  __n, __code), true);
1338  }
1339 
1340  // Insert v unconditionally.
1341  template<typename _Key, typename _Value,
1342  typename _Allocator, typename _ExtractKey, typename _Equal,
1343  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1344  bool __chc, bool __cit, bool __uk>
1345  template<typename _Arg>
1346  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1347  _H1, _H2, _Hash, _RehashPolicy,
1348  __chc, __cit, __uk>::iterator
1349  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1350  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1351  _M_insert(_Arg&& __v, std::false_type)
1352  {
1353  const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1354  std::pair<bool, std::size_t> __do_rehash
1355  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1356  _M_element_count, 1);
1357 
1358  // First compute the hash code so that we don't do anything if it throws.
1359  typename _Hashtable::_Hash_code_type __code
1360  = this->_M_hash_code(this->_M_extract()(__v));
1361 
1362  _Node* __new_node = nullptr;
1363  __try
1364  {
1365  // Second allocate new node so that we don't rehash if it throws.
1366  __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1367  this->_M_store_code(__new_node, __code);
1368  if (__do_rehash.first)
1369  _M_rehash(__do_rehash.second, __saved_state);
1370 
1371  // Third, find the node before an equivalent one.
1372  size_type __bkt = _M_bucket_index(__new_node);
1373  _BaseNode* __prev
1374  = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v),
1375  __code);
1376  if (__prev)
1377  {
1378  // Insert after the node before the equivalent one.
1379  __new_node->_M_nxt = __prev->_M_nxt;
1380  __prev->_M_nxt = __new_node;
1381  }
1382  else
1383  // The inserted node has no equivalent in the hashtable. We must
1384  // insert the new node at the beginning of the bucket to preserve
1385  // equivalent elements relative positions.
1386  _M_insert_bucket_begin(__bkt, __new_node);
1387  ++_M_element_count;
1388  return iterator(__new_node);
1389  }
1390  __catch(...)
1391  {
1392  if (!__new_node)
1393  _M_rehash_policy._M_reset(__saved_state);
1394  else
1395  _M_deallocate_node(__new_node);
1396  __throw_exception_again;
1397  }
1398  }
1399 
1400  template<typename _Key, typename _Value,
1401  typename _Allocator, typename _ExtractKey, typename _Equal,
1402  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1403  bool __chc, bool __cit, bool __uk>
1404  template<typename _InputIterator>
1405  void
1406  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1407  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1408  insert(_InputIterator __first, _InputIterator __last)
1409  {
1410  size_type __n_elt = __detail::__distance_fw(__first, __last);
1411  const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1412  std::pair<bool, std::size_t> __do_rehash
1413  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1414  _M_element_count, __n_elt);
1415  if (__do_rehash.first)
1416  _M_rehash(__do_rehash.second, __saved_state);
1417 
1418  for (; __first != __last; ++__first)
1419  this->insert(*__first);
1420  }
1421 
1422  template<typename _Key, typename _Value,
1423  typename _Allocator, typename _ExtractKey, typename _Equal,
1424  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1425  bool __chc, bool __cit, bool __uk>
1426  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1427  _H1, _H2, _Hash, _RehashPolicy,
1428  __chc, __cit, __uk>::iterator
1429  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1430  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1431  erase(const_iterator __it)
1432  {
1433  _Node* __n = __it._M_cur;
1434  std::size_t __bkt = _M_bucket_index(__n);
1435 
1436  // Look for previous node to unlink it from the erased one, this is why
1437  // we need buckets to contain the before begin to make this research fast.
1438  _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1439  if (__n == _M_bucket_begin(__bkt))
1440  _M_remove_bucket_begin(__bkt, __n->_M_next(),
1441  __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1442  else if (__n->_M_nxt)
1443  {
1444  size_type __next_bkt = _M_bucket_index(__n->_M_next());
1445  if (__next_bkt != __bkt)
1446  _M_buckets[__next_bkt] = __prev_n;
1447  }
1448 
1449  __prev_n->_M_nxt = __n->_M_nxt;
1450  iterator __result(__n->_M_next());
1451  _M_deallocate_node(__n);
1452  --_M_element_count;
1453 
1454  return __result;
1455  }
1456 
1457  template<typename _Key, typename _Value,
1458  typename _Allocator, typename _ExtractKey, typename _Equal,
1459  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1460  bool __chc, bool __cit, bool __uk>
1461  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1462  _H1, _H2, _Hash, _RehashPolicy,
1463  __chc, __cit, __uk>::size_type
1464  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1465  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1466  erase(const key_type& __k)
1467  {
1468  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1469  std::size_t __bkt = _M_bucket_index(__k, __code);
1470  // Look for the node before the first matching node.
1471  _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code);
1472  if (!__prev_n)
1473  return 0;
1474  _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt);
1475  bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
1476 
1477  // We found a matching node, start deallocation loop from it
1478  std::size_t __next_bkt = __bkt;
1479  _Node* __next_n = __n;
1480  size_type __result = 0;
1481  _Node* __saved_n = nullptr;
1482  do
1483  {
1484  _Node* __p = __next_n;
1485  __next_n = __p->_M_next();
1486  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1487  // 526. Is it undefined if a function in the standard changes
1488  // in parameters?
1489  if (std::__addressof(this->_M_extract()(__p->_M_v))
1490  != std::__addressof(__k))
1491  _M_deallocate_node(__p);
1492  else
1493  __saved_n = __p;
1494  --_M_element_count;
1495  ++__result;
1496  if (!__next_n)
1497  break;
1498  __next_bkt = _M_bucket_index(__next_n);
1499  }
1500  while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
1501 
1502  if (__saved_n)
1503  _M_deallocate_node(__saved_n);
1504  if (__is_bucket_begin)
1505  _M_remove_bucket_begin(__bkt, __next_n, __next_bkt);
1506  else if (__next_n && __next_bkt != __bkt)
1507  _M_buckets[__next_bkt] = __prev_n;
1508  if (__prev_n)
1509  __prev_n->_M_nxt = __next_n;
1510  return __result;
1511  }
1512 
1513  template<typename _Key, typename _Value,
1514  typename _Allocator, typename _ExtractKey, typename _Equal,
1515  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1516  bool __chc, bool __cit, bool __uk>
1517  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1518  _H1, _H2, _Hash, _RehashPolicy,
1519  __chc, __cit, __uk>::iterator
1520  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1521  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1522  erase(const_iterator __first, const_iterator __last)
1523  {
1524  _Node* __n = __first._M_cur;
1525  _Node* __last_n = __last._M_cur;
1526  if (__n == __last_n)
1527  return iterator(__n);
1528 
1529  std::size_t __bkt = _M_bucket_index(__n);
1530 
1531  _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1532  bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1533  std::size_t __n_bkt = __bkt;
1534  for (;;)
1535  {
1536  do
1537  {
1538  _Node* __tmp = __n;
1539  __n = __n->_M_next();
1540  _M_deallocate_node(__tmp);
1541  --_M_element_count;
1542  if (!__n)
1543  break;
1544  __n_bkt = _M_bucket_index(__n);
1545  }
1546  while (__n != __last_n && __n_bkt == __bkt);
1547  if (__is_bucket_begin)
1548  _M_remove_bucket_begin(__bkt, __n, __n_bkt);
1549  if (__n == __last_n)
1550  break;
1551  __is_bucket_begin = true;
1552  __bkt = __n_bkt;
1553  }
1554 
1555  if (__n && (__n_bkt != __bkt || __is_bucket_begin))
1556  _M_buckets[__n_bkt] = __prev_n;
1557  __prev_n->_M_nxt = __n;
1558  return iterator(__n);
1559  }
1560 
1561  template<typename _Key, typename _Value,
1562  typename _Allocator, typename _ExtractKey, typename _Equal,
1563  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1564  bool __chc, bool __cit, bool __uk>
1565  void
1566  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1567  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1568  clear() noexcept
1569  {
1570  _M_deallocate_nodes(_M_begin());
1571  __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket));
1572  _M_element_count = 0;
1573  _M_before_begin._M_nxt = nullptr;
1574  }
1575 
1576  template<typename _Key, typename _Value,
1577  typename _Allocator, typename _ExtractKey, typename _Equal,
1578  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1579  bool __chc, bool __cit, bool __uk>
1580  void
1581  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1582  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1583  rehash(size_type __n)
1584  {
1585  const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1586  std::size_t __buckets
1587  = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1);
1588  if (__buckets <= __n)
1589  __buckets = _M_rehash_policy._M_next_bkt(__n);
1590 
1591  if (__buckets != _M_bucket_count)
1592  {
1593  _M_rehash(__buckets, __saved_state);
1594 
1595  // We don't want the rehash policy to ask for the hashtable to shrink
1596  // on the next insertion so we need to reset its previous resize
1597  // level.
1598  _M_rehash_policy._M_prev_resize = 0;
1599  }
1600  }
1601 
1602  template<typename _Key, typename _Value,
1603  typename _Allocator, typename _ExtractKey, typename _Equal,
1604  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1605  bool __chc, bool __cit, bool __uk>
1606  void
1607  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1608  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1609  _M_rehash(size_type __n, const _RehashPolicyState& __state)
1610  {
1611  __try
1612  {
1613  _M_rehash_aux(__n, integral_constant<bool, __uk>());
1614  }
1615  __catch(...)
1616  {
1617  // A failure here means that buckets allocation failed. We only
1618  // have to restore hash policy previous state.
1619  _M_rehash_policy._M_reset(__state);
1620  __throw_exception_again;
1621  }
1622  }
1623 
1624  // Rehash when there is no equivalent elements.
1625  template<typename _Key, typename _Value,
1626  typename _Allocator, typename _ExtractKey, typename _Equal,
1627  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1628  bool __chc, bool __cit, bool __uk>
1629  void
1630  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1631  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1632  _M_rehash_aux(size_type __n, std::true_type)
1633  {
1634  _Bucket* __new_buckets = _M_allocate_buckets(__n);
1635  _Node* __p = _M_begin();
1636  _M_before_begin._M_nxt = nullptr;
1637  std::size_t __bbegin_bkt;
1638  while (__p)
1639  {
1640  _Node* __next = __p->_M_next();
1641  std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1642  if (!__new_buckets[__bkt])
1643  {
1644  __p->_M_nxt = _M_before_begin._M_nxt;
1645  _M_before_begin._M_nxt = __p;
1646  __new_buckets[__bkt] = &_M_before_begin;
1647  if (__p->_M_nxt)
1648  __new_buckets[__bbegin_bkt] = __p;
1649  __bbegin_bkt = __bkt;
1650  }
1651  else
1652  {
1653  __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1654  __new_buckets[__bkt]->_M_nxt = __p;
1655  }
1656  __p = __next;
1657  }
1658  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1659  _M_bucket_count = __n;
1660  _M_buckets = __new_buckets;
1661  }
1662 
1663  // Rehash when there can be equivalent elements, preserve their relative
1664  // order.
1665  template<typename _Key, typename _Value,
1666  typename _Allocator, typename _ExtractKey, typename _Equal,
1667  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1668  bool __chc, bool __cit, bool __uk>
1669  void
1670  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1671  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1672  _M_rehash_aux(size_type __n, std::false_type)
1673  {
1674  _Bucket* __new_buckets = _M_allocate_buckets(__n);
1675 
1676  _Node* __p = _M_begin();
1677  _M_before_begin._M_nxt = nullptr;
1678  std::size_t __bbegin_bkt;
1679  std::size_t __prev_bkt;
1680  _Node* __prev_p = nullptr;
1681  bool __check_bucket = false;
1682 
1683  while (__p)
1684  {
1685  _Node* __next = __p->_M_next();
1686  std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1687 
1688  if (__prev_p && __prev_bkt == __bkt)
1689  {
1690  // Previous insert was already in this bucket, we insert after
1691  // the previously inserted one to preserve equivalent elements
1692  // relative order.
1693  __p->_M_nxt = __prev_p->_M_nxt;
1694  __prev_p->_M_nxt = __p;
1695 
1696  // Inserting after a node in a bucket require to check that we
1697  // haven't change the bucket last node, in this case next
1698  // bucket containing its before begin node must be updated. We
1699  // schedule a check as soon as we move out of the sequence of
1700  // equivalent nodes to limit the number of checks.
1701  __check_bucket = true;
1702  }
1703  else
1704  {
1705  if (__check_bucket)
1706  {
1707  // Check if we shall update the next bucket because of insertions
1708  // into __prev_bkt bucket.
1709  if (__prev_p->_M_nxt)
1710  {
1711  std::size_t __next_bkt
1712  = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1713  if (__next_bkt != __prev_bkt)
1714  __new_buckets[__next_bkt] = __prev_p;
1715  }
1716  __check_bucket = false;
1717  }
1718  if (!__new_buckets[__bkt])
1719  {
1720  __p->_M_nxt = _M_before_begin._M_nxt;
1721  _M_before_begin._M_nxt = __p;
1722  __new_buckets[__bkt] = &_M_before_begin;
1723  if (__p->_M_nxt)
1724  __new_buckets[__bbegin_bkt] = __p;
1725  __bbegin_bkt = __bkt;
1726  }
1727  else
1728  {
1729  __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1730  __new_buckets[__bkt]->_M_nxt = __p;
1731  }
1732  }
1733 
1734  __prev_p = __p;
1735  __prev_bkt = __bkt;
1736  __p = __next;
1737  }
1738 
1739  if (__check_bucket && __prev_p->_M_nxt)
1740  {
1741  std::size_t __next_bkt
1742  = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1743  if (__next_bkt != __prev_bkt)
1744  __new_buckets[__next_bkt] = __prev_p;
1745  }
1746 
1747  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1748  _M_bucket_count = __n;
1749  _M_buckets = __new_buckets;
1750  }
1751 
1752 _GLIBCXX_END_NAMESPACE_VERSION
1753 } // namespace std
1754 
1755 #endif // _HASHTABLE_H