OSDN Git Service

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