__hash_table revision 253146 
1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP__HASH_TABLE
12#define _LIBCPP__HASH_TABLE
13
14#include <__config>
15#include <initializer_list>
16#include <memory>
17#include <iterator>
18#include <algorithm>
19#include <cmath>
20
21#include <__undef_min_max>
22
23#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
24#pragma GCC system_header
25#endif
26
27_LIBCPP_BEGIN_NAMESPACE_STD
28
29_LIBCPP_FUNC_VIS
30size_t __next_prime(size_t __n);
31
32template <class _NodePtr>
33struct __hash_node_base
34{
35    typedef __hash_node_base __first_node;
36
37    _NodePtr    __next_;
38
39    _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
40};
41
42template <class _Tp, class _VoidPtr>
43struct __hash_node
44    : public __hash_node_base
45             <
46                 typename pointer_traits<_VoidPtr>::template
47#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
48                     rebind<__hash_node<_Tp, _VoidPtr> >
49#else
50                     rebind<__hash_node<_Tp, _VoidPtr> >::other
51#endif
52             >
53{
54    typedef _Tp value_type;
55
56    size_t     __hash_;
57    value_type __value_;
58};
59
60inline _LIBCPP_INLINE_VISIBILITY
61bool
62__is_power2(size_t __bc)
63{
64    return __bc > 2 && !(__bc & (__bc - 1));
65}
66
67inline _LIBCPP_INLINE_VISIBILITY
68size_t
69__constrain_hash(size_t __h, size_t __bc)
70{
71    return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc;
72}
73
74inline _LIBCPP_INLINE_VISIBILITY
75size_t
76__next_pow2(size_t __n)
77{
78    return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
79}
80
81template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
82template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS __hash_const_iterator;
83template <class _HashIterator> class _LIBCPP_TYPE_VIS __hash_map_iterator;
84template <class _HashIterator> class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
85template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
86    class _LIBCPP_TYPE_VIS unordered_map;
87
88template <class _NodePtr>
89class _LIBCPP_TYPE_VIS __hash_iterator
90{
91    typedef _NodePtr __node_pointer;
92
93    __node_pointer            __node_;
94
95public:
96    typedef forward_iterator_tag                         iterator_category;
97    typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type;
98    typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
99    typedef value_type&                                  reference;
100    typedef typename pointer_traits<__node_pointer>::template
101#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
102                     rebind<value_type>
103#else
104                     rebind<value_type>::other
105#endif
106                                                         pointer;
107
108    _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT {}
109
110    _LIBCPP_INLINE_VISIBILITY
111        reference operator*() const {return __node_->__value_;}
112    _LIBCPP_INLINE_VISIBILITY
113        pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
114
115    _LIBCPP_INLINE_VISIBILITY
116    __hash_iterator& operator++()
117    {
118        __node_ = __node_->__next_;
119        return *this;
120    }
121
122    _LIBCPP_INLINE_VISIBILITY
123    __hash_iterator operator++(int)
124    {
125        __hash_iterator __t(*this);
126        ++(*this);
127        return __t;
128    }
129
130    friend _LIBCPP_INLINE_VISIBILITY
131    bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
132        {return __x.__node_ == __y.__node_;}
133    friend _LIBCPP_INLINE_VISIBILITY
134    bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
135        {return __x.__node_ != __y.__node_;}
136
137private:
138    _LIBCPP_INLINE_VISIBILITY
139    __hash_iterator(__node_pointer __node) _NOEXCEPT
140        : __node_(__node)
141        {}
142
143    template <class, class, class, class> friend class __hash_table;
144    template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
145    template <class> friend class _LIBCPP_TYPE_VIS __hash_map_iterator;
146    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
147    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
148};
149
150template <class _ConstNodePtr>
151class _LIBCPP_TYPE_VIS __hash_const_iterator
152{
153    typedef _ConstNodePtr __node_pointer;
154
155    __node_pointer         __node_;
156
157    typedef typename remove_const<
158        typename pointer_traits<__node_pointer>::element_type
159                                 >::type __node;
160
161public:
162    typedef forward_iterator_tag                       iterator_category;
163    typedef typename __node::value_type                value_type;
164    typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
165    typedef const value_type&                          reference;
166    typedef typename pointer_traits<__node_pointer>::template
167#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
168            rebind<const value_type>
169#else
170            rebind<const value_type>::other
171#endif
172                                                       pointer;
173    typedef typename pointer_traits<__node_pointer>::template
174#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
175            rebind<__node>
176#else
177            rebind<__node>::other
178#endif
179                                                      __non_const_node_pointer;
180    typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator;
181
182    _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT {}
183    _LIBCPP_INLINE_VISIBILITY 
184    __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
185        : __node_(__x.__node_)
186        {}
187
188    _LIBCPP_INLINE_VISIBILITY
189        reference operator*() const {return __node_->__value_;}
190    _LIBCPP_INLINE_VISIBILITY
191        pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
192
193    _LIBCPP_INLINE_VISIBILITY
194    __hash_const_iterator& operator++()
195    {
196        __node_ = __node_->__next_;
197        return *this;
198    }
199
200    _LIBCPP_INLINE_VISIBILITY
201    __hash_const_iterator operator++(int)
202    {
203        __hash_const_iterator __t(*this);
204        ++(*this);
205        return __t;
206    }
207
208    friend _LIBCPP_INLINE_VISIBILITY
209    bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
210        {return __x.__node_ == __y.__node_;}
211    friend _LIBCPP_INLINE_VISIBILITY
212    bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
213        {return __x.__node_ != __y.__node_;}
214
215private:
216    _LIBCPP_INLINE_VISIBILITY
217    __hash_const_iterator(__node_pointer __node) _NOEXCEPT
218        : __node_(__node)
219        {}
220
221    template <class, class, class, class> friend class __hash_table;
222    template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
223    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
224    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
225};
226
227template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
228
229template <class _NodePtr>
230class _LIBCPP_TYPE_VIS __hash_local_iterator
231{
232    typedef _NodePtr __node_pointer;
233
234    __node_pointer         __node_;
235    size_t                 __bucket_;
236    size_t                 __bucket_count_;
237
238    typedef pointer_traits<__node_pointer>          __pointer_traits;
239public:
240    typedef forward_iterator_tag                                iterator_category;
241    typedef typename __pointer_traits::element_type::value_type value_type;
242    typedef typename __pointer_traits::difference_type          difference_type;
243    typedef value_type&                                         reference;
244    typedef typename __pointer_traits::template
245#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
246            rebind<value_type>
247#else
248            rebind<value_type>::other
249#endif
250                                                                pointer;
251
252    _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT {}
253
254    _LIBCPP_INLINE_VISIBILITY
255        reference operator*() const {return __node_->__value_;}
256    _LIBCPP_INLINE_VISIBILITY
257        pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
258
259    _LIBCPP_INLINE_VISIBILITY
260    __hash_local_iterator& operator++()
261    {
262        __node_ = __node_->__next_;
263        if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
264            __node_ = nullptr;
265        return *this;
266    }
267
268    _LIBCPP_INLINE_VISIBILITY
269    __hash_local_iterator operator++(int)
270    {
271        __hash_local_iterator __t(*this);
272        ++(*this);
273        return __t;
274    }
275
276    friend _LIBCPP_INLINE_VISIBILITY
277    bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
278        {return __x.__node_ == __y.__node_;}
279    friend _LIBCPP_INLINE_VISIBILITY
280    bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
281        {return __x.__node_ != __y.__node_;}
282
283private:
284    _LIBCPP_INLINE_VISIBILITY
285    __hash_local_iterator(__node_pointer __node, size_t __bucket,
286                          size_t __bucket_count) _NOEXCEPT
287        : __node_(__node),
288          __bucket_(__bucket),
289          __bucket_count_(__bucket_count)
290        {
291            if (__node_ != nullptr)
292                __node_ = __node_->__next_;
293        }
294
295    template <class, class, class, class> friend class __hash_table;
296    template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
297    template <class> friend class _LIBCPP_TYPE_VIS __hash_map_iterator;
298};
299
300template <class _ConstNodePtr>
301class _LIBCPP_TYPE_VIS __hash_const_local_iterator
302{
303    typedef _ConstNodePtr __node_pointer;
304
305    __node_pointer         __node_;
306    size_t                 __bucket_;
307    size_t                 __bucket_count_;
308
309    typedef pointer_traits<__node_pointer>          __pointer_traits;
310    typedef typename __pointer_traits::element_type __node;
311    typedef typename remove_const<__node>::type     __non_const_node;
312    typedef typename pointer_traits<__node_pointer>::template
313#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
314            rebind<__non_const_node>
315#else
316            rebind<__non_const_node>::other
317#endif
318                                                    __non_const_node_pointer;
319    typedef __hash_local_iterator<__non_const_node_pointer>
320                                                    __non_const_iterator;
321public:
322    typedef forward_iterator_tag                       iterator_category;
323    typedef typename remove_const<
324                        typename __pointer_traits::element_type::value_type
325                     >::type                           value_type;
326    typedef typename __pointer_traits::difference_type difference_type;
327    typedef const value_type&                          reference;
328    typedef typename __pointer_traits::template
329#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
330            rebind<const value_type>
331#else
332            rebind<const value_type>::other
333#endif
334                                                       pointer;
335
336    _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT {}
337    _LIBCPP_INLINE_VISIBILITY
338    __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
339        : __node_(__x.__node_),
340          __bucket_(__x.__bucket_),
341          __bucket_count_(__x.__bucket_count_)
342        {}
343
344    _LIBCPP_INLINE_VISIBILITY
345        reference operator*() const {return __node_->__value_;}
346    _LIBCPP_INLINE_VISIBILITY
347        pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
348
349    _LIBCPP_INLINE_VISIBILITY
350    __hash_const_local_iterator& operator++()
351    {
352        __node_ = __node_->__next_;
353        if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
354            __node_ = nullptr;
355        return *this;
356    }
357
358    _LIBCPP_INLINE_VISIBILITY
359    __hash_const_local_iterator operator++(int)
360    {
361        __hash_const_local_iterator __t(*this);
362        ++(*this);
363        return __t;
364    }
365
366    friend _LIBCPP_INLINE_VISIBILITY
367    bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
368        {return __x.__node_ == __y.__node_;}
369    friend _LIBCPP_INLINE_VISIBILITY
370    bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
371        {return __x.__node_ != __y.__node_;}
372
373private:
374    _LIBCPP_INLINE_VISIBILITY
375    __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
376                                size_t __bucket_count) _NOEXCEPT
377        : __node_(__node),
378          __bucket_(__bucket),
379          __bucket_count_(__bucket_count)
380        {
381            if (__node_ != nullptr)
382                __node_ = __node_->__next_;
383        }
384
385    template <class, class, class, class> friend class __hash_table;
386    template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
387};
388
389template <class _Alloc>
390class __bucket_list_deallocator
391{
392    typedef _Alloc                                          allocator_type;
393    typedef allocator_traits<allocator_type>                __alloc_traits;
394    typedef typename __alloc_traits::size_type              size_type;
395
396    __compressed_pair<size_type, allocator_type> __data_;
397public:
398    typedef typename __alloc_traits::pointer pointer;
399
400    _LIBCPP_INLINE_VISIBILITY
401    __bucket_list_deallocator()
402        _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
403        : __data_(0) {}
404
405    _LIBCPP_INLINE_VISIBILITY
406    __bucket_list_deallocator(const allocator_type& __a, size_type __size)
407        _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
408        : __data_(__size, __a) {}
409
410#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
411
412    _LIBCPP_INLINE_VISIBILITY
413    __bucket_list_deallocator(__bucket_list_deallocator&& __x)
414        _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
415        : __data_(_VSTD::move(__x.__data_))
416    {
417        __x.size() = 0;
418    }
419
420#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
421
422    _LIBCPP_INLINE_VISIBILITY
423    size_type& size() _NOEXCEPT {return __data_.first();}
424    _LIBCPP_INLINE_VISIBILITY
425    size_type  size() const _NOEXCEPT {return __data_.first();}
426
427    _LIBCPP_INLINE_VISIBILITY
428    allocator_type& __alloc() _NOEXCEPT {return __data_.second();}
429    _LIBCPP_INLINE_VISIBILITY
430    const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();}
431
432    _LIBCPP_INLINE_VISIBILITY
433    void operator()(pointer __p) _NOEXCEPT
434    {
435        __alloc_traits::deallocate(__alloc(), __p, size());
436    }
437};
438
439template <class _Alloc> class __hash_map_node_destructor;
440
441template <class _Alloc>
442class __hash_node_destructor
443{
444    typedef _Alloc                                          allocator_type;
445    typedef allocator_traits<allocator_type>                __alloc_traits;
446    typedef typename __alloc_traits::value_type::value_type value_type;
447public:
448    typedef typename __alloc_traits::pointer                pointer;
449private:
450
451    allocator_type& __na_;
452
453    __hash_node_destructor& operator=(const __hash_node_destructor&);
454
455public:
456    bool __value_constructed;
457
458    _LIBCPP_INLINE_VISIBILITY
459    explicit __hash_node_destructor(allocator_type& __na,
460                                    bool __constructed = false) _NOEXCEPT
461        : __na_(__na),
462          __value_constructed(__constructed)
463        {}
464
465    _LIBCPP_INLINE_VISIBILITY
466    void operator()(pointer __p) _NOEXCEPT
467    {
468        if (__value_constructed)
469            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_));
470        if (__p)
471            __alloc_traits::deallocate(__na_, __p, 1);
472    }
473
474    template <class> friend class __hash_map_node_destructor;
475};
476
477template <class _Tp, class _Hash, class _Equal, class _Alloc>
478class __hash_table
479{
480public:
481    typedef _Tp    value_type;
482    typedef _Hash  hasher;
483    typedef _Equal key_equal;
484    typedef _Alloc allocator_type;
485
486private:
487    typedef allocator_traits<allocator_type> __alloc_traits;
488public:
489    typedef value_type&                              reference;
490    typedef const value_type&                        const_reference;
491    typedef typename __alloc_traits::pointer         pointer;
492    typedef typename __alloc_traits::const_pointer   const_pointer;
493    typedef typename __alloc_traits::size_type       size_type;
494    typedef typename __alloc_traits::difference_type difference_type;
495public:
496    // Create __node
497    typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node;
498    typedef typename __alloc_traits::template
499#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
500            rebind_alloc<__node>
501#else
502            rebind_alloc<__node>::other
503#endif
504                                                     __node_allocator;
505    typedef allocator_traits<__node_allocator>       __node_traits;
506    typedef typename __node_traits::pointer          __node_pointer;
507    typedef typename __node_traits::pointer          __node_const_pointer;
508    typedef __hash_node_base<__node_pointer>         __first_node;
509    typedef typename pointer_traits<__node_pointer>::template
510#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
511            rebind<__first_node>
512#else
513            rebind<__first_node>::other
514#endif
515                                                     __node_base_pointer;
516
517private:
518
519    typedef typename __node_traits::template
520#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
521            rebind_alloc<__node_pointer>
522#else
523            rebind_alloc<__node_pointer>::other
524#endif
525                                                            __pointer_allocator;
526    typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
527    typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list;
528    typedef allocator_traits<__pointer_allocator>          __pointer_alloc_traits;
529    typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
530
531    // --- Member data begin ---
532    __bucket_list                                     __bucket_list_;
533    __compressed_pair<__first_node, __node_allocator> __p1_;
534    __compressed_pair<size_type, hasher>              __p2_;
535    __compressed_pair<float, key_equal>               __p3_;
536    // --- Member data end ---
537
538    _LIBCPP_INLINE_VISIBILITY
539    size_type& size() _NOEXCEPT {return __p2_.first();}
540public:
541    _LIBCPP_INLINE_VISIBILITY
542    size_type  size() const _NOEXCEPT {return __p2_.first();}
543
544    _LIBCPP_INLINE_VISIBILITY
545    hasher& hash_function() _NOEXCEPT {return __p2_.second();}
546    _LIBCPP_INLINE_VISIBILITY
547    const hasher& hash_function() const _NOEXCEPT {return __p2_.second();}
548
549    _LIBCPP_INLINE_VISIBILITY
550    float& max_load_factor() _NOEXCEPT {return __p3_.first();}
551    _LIBCPP_INLINE_VISIBILITY
552    float  max_load_factor() const _NOEXCEPT {return __p3_.first();}
553
554    _LIBCPP_INLINE_VISIBILITY
555    key_equal& key_eq() _NOEXCEPT {return __p3_.second();}
556    _LIBCPP_INLINE_VISIBILITY
557    const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();}
558
559    _LIBCPP_INLINE_VISIBILITY
560    __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();}
561    _LIBCPP_INLINE_VISIBILITY
562    const __node_allocator& __node_alloc() const _NOEXCEPT
563        {return __p1_.second();}
564
565public:
566    typedef __hash_iterator<__node_pointer>                   iterator;
567    typedef __hash_const_iterator<__node_pointer>             const_iterator;
568    typedef __hash_local_iterator<__node_pointer>             local_iterator;
569    typedef __hash_const_local_iterator<__node_pointer>       const_local_iterator;
570
571    __hash_table()
572        _NOEXCEPT_(
573            is_nothrow_default_constructible<__bucket_list>::value &&
574            is_nothrow_default_constructible<__first_node>::value &&
575            is_nothrow_default_constructible<__node_allocator>::value &&
576            is_nothrow_default_constructible<hasher>::value &&
577            is_nothrow_default_constructible<key_equal>::value);
578    __hash_table(const hasher& __hf, const key_equal& __eql);
579    __hash_table(const hasher& __hf, const key_equal& __eql,
580                 const allocator_type& __a);
581    explicit __hash_table(const allocator_type& __a);
582    __hash_table(const __hash_table& __u);
583    __hash_table(const __hash_table& __u, const allocator_type& __a);
584#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
585    __hash_table(__hash_table&& __u)
586        _NOEXCEPT_(
587            is_nothrow_move_constructible<__bucket_list>::value &&
588            is_nothrow_move_constructible<__first_node>::value &&
589            is_nothrow_move_constructible<__node_allocator>::value &&
590            is_nothrow_move_constructible<hasher>::value &&
591            is_nothrow_move_constructible<key_equal>::value);
592    __hash_table(__hash_table&& __u, const allocator_type& __a);
593#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
594    ~__hash_table();
595
596    __hash_table& operator=(const __hash_table& __u);
597#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
598    __hash_table& operator=(__hash_table&& __u)
599        _NOEXCEPT_(
600            __node_traits::propagate_on_container_move_assignment::value &&
601            is_nothrow_move_assignable<__node_allocator>::value &&
602            is_nothrow_move_assignable<hasher>::value &&
603            is_nothrow_move_assignable<key_equal>::value);
604#endif
605    template <class _InputIterator>
606        void __assign_unique(_InputIterator __first, _InputIterator __last);
607    template <class _InputIterator>
608        void __assign_multi(_InputIterator __first, _InputIterator __last);
609
610    _LIBCPP_INLINE_VISIBILITY
611    size_type max_size() const _NOEXCEPT
612    {
613        return allocator_traits<__pointer_allocator>::max_size(
614            __bucket_list_.get_deleter().__alloc());
615    }
616
617    pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
618    iterator             __node_insert_multi(__node_pointer __nd);
619    iterator             __node_insert_multi(const_iterator __p,
620                                             __node_pointer __nd);
621
622#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
623    template <class... _Args>
624        pair<iterator, bool> __emplace_unique(_Args&&... __args);
625    template <class... _Args>
626        iterator __emplace_multi(_Args&&... __args);
627    template <class... _Args>
628        iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
629#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
630
631    pair<iterator, bool> __insert_unique(const value_type& __x);
632
633#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
634    template <class _Pp>
635        pair<iterator, bool> __insert_unique(_Pp&& __x);
636#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
637
638#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
639    template <class _Pp>
640        iterator __insert_multi(_Pp&& __x);
641    template <class _Pp>
642        iterator __insert_multi(const_iterator __p, _Pp&& __x);
643#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
644    iterator __insert_multi(const value_type& __x);
645    iterator __insert_multi(const_iterator __p, const value_type& __x);
646#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
647
648    void clear() _NOEXCEPT;
649    void rehash(size_type __n);
650    _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
651        {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
652
653    _LIBCPP_INLINE_VISIBILITY
654    size_type bucket_count() const _NOEXCEPT
655    {
656        return __bucket_list_.get_deleter().size();
657    }
658
659    iterator       begin() _NOEXCEPT;
660    iterator       end() _NOEXCEPT;
661    const_iterator begin() const _NOEXCEPT;
662    const_iterator end() const _NOEXCEPT;
663
664    template <class _Key>
665        _LIBCPP_INLINE_VISIBILITY
666        size_type bucket(const _Key& __k) const
667            {return __constrain_hash(hash_function()(__k), bucket_count());}
668
669    template <class _Key>
670        iterator       find(const _Key& __x);
671    template <class _Key>
672        const_iterator find(const _Key& __x) const;
673
674    typedef __hash_node_destructor<__node_allocator> _Dp;
675    typedef unique_ptr<__node, _Dp> __node_holder;
676
677    iterator erase(const_iterator __p);
678    iterator erase(const_iterator __first, const_iterator __last);
679    template <class _Key>
680        size_type __erase_unique(const _Key& __k);
681    template <class _Key>
682        size_type __erase_multi(const _Key& __k);
683    __node_holder remove(const_iterator __p) _NOEXCEPT;
684
685    template <class _Key>
686        size_type __count_unique(const _Key& __k) const;
687    template <class _Key>
688        size_type __count_multi(const _Key& __k) const;
689
690    template <class _Key>
691        pair<iterator, iterator>
692        __equal_range_unique(const _Key& __k);
693    template <class _Key>
694        pair<const_iterator, const_iterator>
695        __equal_range_unique(const _Key& __k) const;
696
697    template <class _Key>
698        pair<iterator, iterator>
699        __equal_range_multi(const _Key& __k);
700    template <class _Key>
701        pair<const_iterator, const_iterator>
702        __equal_range_multi(const _Key& __k) const;
703
704    void swap(__hash_table& __u)
705        _NOEXCEPT_(
706            (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
707             __is_nothrow_swappable<__pointer_allocator>::value) &&
708            (!__node_traits::propagate_on_container_swap::value ||
709             __is_nothrow_swappable<__node_allocator>::value) &&
710            __is_nothrow_swappable<hasher>::value &&
711            __is_nothrow_swappable<key_equal>::value);
712
713    _LIBCPP_INLINE_VISIBILITY
714    size_type max_bucket_count() const _NOEXCEPT
715        {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());}
716    size_type bucket_size(size_type __n) const;
717    _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
718    {
719        size_type __bc = bucket_count();
720        return __bc != 0 ? (float)size() / __bc : 0.f;
721    }
722    _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
723        {max_load_factor() = _VSTD::max(__mlf, load_factor());}
724
725    _LIBCPP_INLINE_VISIBILITY local_iterator       begin(size_type __n)
726        {return local_iterator(__bucket_list_[__n], __n, bucket_count());}
727    _LIBCPP_INLINE_VISIBILITY local_iterator       end(size_type __n)
728        {return local_iterator(nullptr, __n, bucket_count());}
729    _LIBCPP_INLINE_VISIBILITY const_local_iterator cbegin(size_type __n) const
730        {return const_local_iterator(__bucket_list_[__n], __n, bucket_count());}
731    _LIBCPP_INLINE_VISIBILITY const_local_iterator cend(size_type __n) const
732        {return const_local_iterator(nullptr, __n, bucket_count());}
733private:
734    void __rehash(size_type __n);
735
736#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
737#ifndef _LIBCPP_HAS_NO_VARIADICS
738    template <class ..._Args>
739        __node_holder __construct_node(_Args&& ...__args);
740#endif  // _LIBCPP_HAS_NO_VARIADICS
741    __node_holder __construct_node(value_type&& __v, size_t __hash);
742#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
743    __node_holder __construct_node(const value_type& __v);
744#endif
745    __node_holder __construct_node(const value_type& __v, size_t __hash);
746
747    _LIBCPP_INLINE_VISIBILITY
748    void __copy_assign_alloc(const __hash_table& __u)
749        {__copy_assign_alloc(__u, integral_constant<bool,
750             __node_traits::propagate_on_container_copy_assignment::value>());}
751    void __copy_assign_alloc(const __hash_table& __u, true_type);
752    _LIBCPP_INLINE_VISIBILITY
753        void __copy_assign_alloc(const __hash_table&, false_type) {}
754
755    void __move_assign(__hash_table& __u, false_type);
756    void __move_assign(__hash_table& __u, true_type)
757        _NOEXCEPT_(
758            is_nothrow_move_assignable<__node_allocator>::value &&
759            is_nothrow_move_assignable<hasher>::value &&
760            is_nothrow_move_assignable<key_equal>::value);
761    _LIBCPP_INLINE_VISIBILITY
762    void __move_assign_alloc(__hash_table& __u)
763        _NOEXCEPT_(
764            !__node_traits::propagate_on_container_move_assignment::value ||
765            (is_nothrow_move_assignable<__pointer_allocator>::value &&
766             is_nothrow_move_assignable<__node_allocator>::value))
767        {__move_assign_alloc(__u, integral_constant<bool,
768             __node_traits::propagate_on_container_move_assignment::value>());}
769    _LIBCPP_INLINE_VISIBILITY
770    void __move_assign_alloc(__hash_table& __u, true_type)
771        _NOEXCEPT_(
772            is_nothrow_move_assignable<__pointer_allocator>::value &&
773            is_nothrow_move_assignable<__node_allocator>::value)
774    {
775        __bucket_list_.get_deleter().__alloc() =
776                _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
777        __node_alloc() = _VSTD::move(__u.__node_alloc());
778    }
779    _LIBCPP_INLINE_VISIBILITY
780        void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
781
782    template <class _Ap>
783    _LIBCPP_INLINE_VISIBILITY
784    static
785    void
786    __swap_alloc(_Ap& __x, _Ap& __y)
787        _NOEXCEPT_(
788            !allocator_traits<_Ap>::propagate_on_container_swap::value ||
789            __is_nothrow_swappable<_Ap>::value)
790    {
791        __swap_alloc(__x, __y,
792                     integral_constant<bool,
793                        allocator_traits<_Ap>::propagate_on_container_swap::value
794                                      >());
795    }
796
797    template <class _Ap>
798    _LIBCPP_INLINE_VISIBILITY
799    static
800    void
801    __swap_alloc(_Ap& __x, _Ap& __y, true_type)
802        _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value)
803    {
804        using _VSTD::swap;
805        swap(__x, __y);
806    }
807
808    template <class _Ap>
809    _LIBCPP_INLINE_VISIBILITY
810    static
811    void
812    __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {}
813
814    void __deallocate(__node_pointer __np) _NOEXCEPT;
815    __node_pointer __detach() _NOEXCEPT;
816
817    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
818    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
819};
820
821template <class _Tp, class _Hash, class _Equal, class _Alloc>
822inline _LIBCPP_INLINE_VISIBILITY
823__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
824    _NOEXCEPT_(
825        is_nothrow_default_constructible<__bucket_list>::value &&
826        is_nothrow_default_constructible<__first_node>::value &&
827        is_nothrow_default_constructible<hasher>::value &&
828        is_nothrow_default_constructible<key_equal>::value)
829    : __p2_(0),
830      __p3_(1.0f)
831{
832}
833
834template <class _Tp, class _Hash, class _Equal, class _Alloc>
835inline _LIBCPP_INLINE_VISIBILITY
836__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
837                                                       const key_equal& __eql)
838    : __bucket_list_(nullptr, __bucket_list_deleter()),
839      __p1_(),
840      __p2_(0, __hf),
841      __p3_(1.0f, __eql)
842{
843}
844
845template <class _Tp, class _Hash, class _Equal, class _Alloc>
846__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
847                                                       const key_equal& __eql,
848                                                       const allocator_type& __a)
849    : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
850      __p1_(__node_allocator(__a)),
851      __p2_(0, __hf),
852      __p3_(1.0f, __eql)
853{
854}
855
856template <class _Tp, class _Hash, class _Equal, class _Alloc>
857__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
858    : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
859      __p1_(__node_allocator(__a)),
860      __p2_(0),
861      __p3_(1.0f)
862{
863}
864
865template <class _Tp, class _Hash, class _Equal, class _Alloc>
866__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
867    : __bucket_list_(nullptr,
868          __bucket_list_deleter(allocator_traits<__pointer_allocator>::
869              select_on_container_copy_construction(
870                  __u.__bucket_list_.get_deleter().__alloc()), 0)),
871      __p1_(allocator_traits<__node_allocator>::
872          select_on_container_copy_construction(__u.__node_alloc())),
873      __p2_(0, __u.hash_function()),
874      __p3_(__u.__p3_)
875{
876}
877
878template <class _Tp, class _Hash, class _Equal, class _Alloc>
879__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
880                                                       const allocator_type& __a)
881    : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
882      __p1_(__node_allocator(__a)),
883      __p2_(0, __u.hash_function()),
884      __p3_(__u.__p3_)
885{
886}
887
888#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
889
890template <class _Tp, class _Hash, class _Equal, class _Alloc>
891__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
892        _NOEXCEPT_(
893            is_nothrow_move_constructible<__bucket_list>::value &&
894            is_nothrow_move_constructible<__first_node>::value &&
895            is_nothrow_move_constructible<hasher>::value &&
896            is_nothrow_move_constructible<key_equal>::value)
897    : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
898      __p1_(_VSTD::move(__u.__p1_)),
899      __p2_(_VSTD::move(__u.__p2_)),
900      __p3_(_VSTD::move(__u.__p3_))
901{
902    if (size() > 0)
903    {
904        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
905            static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
906        __u.__p1_.first().__next_ = nullptr;
907        __u.size() = 0;
908    }
909}
910
911template <class _Tp, class _Hash, class _Equal, class _Alloc>
912__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
913                                                       const allocator_type& __a)
914    : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
915      __p1_(__node_allocator(__a)),
916      __p2_(0, _VSTD::move(__u.hash_function())),
917      __p3_(_VSTD::move(__u.__p3_))
918{
919    if (__a == allocator_type(__u.__node_alloc()))
920    {
921        __bucket_list_.reset(__u.__bucket_list_.release());
922        __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
923        __u.__bucket_list_.get_deleter().size() = 0;
924        if (__u.size() > 0)
925        {
926            __p1_.first().__next_ = __u.__p1_.first().__next_;
927            __u.__p1_.first().__next_ = nullptr;
928            __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
929                static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
930            size() = __u.size();
931            __u.size() = 0;
932        }
933    }
934}
935
936#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
937
938template <class _Tp, class _Hash, class _Equal, class _Alloc>
939__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
940{
941    __deallocate(__p1_.first().__next_);
942}
943
944template <class _Tp, class _Hash, class _Equal, class _Alloc>
945void
946__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
947        const __hash_table& __u, true_type)
948{
949    if (__node_alloc() != __u.__node_alloc())
950    {
951        clear();
952        __bucket_list_.reset();
953        __bucket_list_.get_deleter().size() = 0;
954    }
955    __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
956    __node_alloc() = __u.__node_alloc();
957}
958
959template <class _Tp, class _Hash, class _Equal, class _Alloc>
960__hash_table<_Tp, _Hash, _Equal, _Alloc>&
961__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
962{
963    if (this != &__u)
964    {
965        __copy_assign_alloc(__u);
966        hash_function() = __u.hash_function();
967        key_eq() = __u.key_eq();
968        max_load_factor() = __u.max_load_factor();
969        __assign_multi(__u.begin(), __u.end());
970    }
971    return *this;
972}
973
974template <class _Tp, class _Hash, class _Equal, class _Alloc>
975void
976__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np)
977    _NOEXCEPT
978{
979    __node_allocator& __na = __node_alloc();
980    while (__np != nullptr)
981    {
982        __node_pointer __next = __np->__next_;
983        __node_traits::destroy(__na, _VSTD::addressof(__np->__value_));
984        __node_traits::deallocate(__na, __np, 1);
985        __np = __next;
986    }
987}
988
989template <class _Tp, class _Hash, class _Equal, class _Alloc>
990typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer
991__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
992{
993    size_type __bc = bucket_count();
994    for (size_type __i = 0; __i < __bc; ++__i)
995        __bucket_list_[__i] = nullptr;
996    size() = 0;
997    __node_pointer __cache = __p1_.first().__next_;
998    __p1_.first().__next_ = nullptr;
999    return __cache;
1000}
1001
1002#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1003
1004template <class _Tp, class _Hash, class _Equal, class _Alloc>
1005void
1006__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1007        __hash_table& __u, true_type)
1008    _NOEXCEPT_(
1009        is_nothrow_move_assignable<__node_allocator>::value &&
1010        is_nothrow_move_assignable<hasher>::value &&
1011        is_nothrow_move_assignable<key_equal>::value)
1012{
1013    clear();
1014    __bucket_list_.reset(__u.__bucket_list_.release());
1015    __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1016    __u.__bucket_list_.get_deleter().size() = 0;
1017    __move_assign_alloc(__u);
1018    size() = __u.size();
1019    hash_function() = _VSTD::move(__u.hash_function());
1020    max_load_factor() = __u.max_load_factor();
1021    key_eq() = _VSTD::move(__u.key_eq());
1022    __p1_.first().__next_ = __u.__p1_.first().__next_;
1023    if (size() > 0)
1024    {
1025        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
1026            static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1027        __u.__p1_.first().__next_ = nullptr;
1028        __u.size() = 0;
1029    }
1030}
1031
1032template <class _Tp, class _Hash, class _Equal, class _Alloc>
1033void
1034__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1035        __hash_table& __u, false_type)
1036{
1037    if (__node_alloc() == __u.__node_alloc())
1038        __move_assign(__u, true_type());
1039    else
1040    {
1041        hash_function() = _VSTD::move(__u.hash_function());
1042        key_eq() = _VSTD::move(__u.key_eq());
1043        max_load_factor() = __u.max_load_factor();
1044        if (bucket_count() != 0)
1045        {
1046            __node_pointer __cache = __detach();
1047#ifndef _LIBCPP_NO_EXCEPTIONS
1048            try
1049            {
1050#endif  // _LIBCPP_NO_EXCEPTIONS
1051                const_iterator __i = __u.begin();
1052                while (__cache != nullptr && __u.size() != 0)
1053                {
1054                    __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_);
1055                    __node_pointer __next = __cache->__next_;
1056                    __node_insert_multi(__cache);
1057                    __cache = __next;
1058                }
1059#ifndef _LIBCPP_NO_EXCEPTIONS
1060            }
1061            catch (...)
1062            {
1063                __deallocate(__cache);
1064                throw;
1065            }
1066#endif  // _LIBCPP_NO_EXCEPTIONS
1067            __deallocate(__cache);
1068        }
1069        const_iterator __i = __u.begin();
1070        while (__u.size() != 0)
1071        {
1072            __node_holder __h =
1073                    __construct_node(_VSTD::move(__u.remove(__i++)->__value_));
1074            __node_insert_multi(__h.get());
1075            __h.release();
1076        }
1077    }
1078}
1079
1080template <class _Tp, class _Hash, class _Equal, class _Alloc>
1081inline _LIBCPP_INLINE_VISIBILITY
1082__hash_table<_Tp, _Hash, _Equal, _Alloc>&
1083__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
1084    _NOEXCEPT_(
1085        __node_traits::propagate_on_container_move_assignment::value &&
1086        is_nothrow_move_assignable<__node_allocator>::value &&
1087        is_nothrow_move_assignable<hasher>::value &&
1088        is_nothrow_move_assignable<key_equal>::value)
1089{
1090    __move_assign(__u, integral_constant<bool,
1091                  __node_traits::propagate_on_container_move_assignment::value>());
1092    return *this;
1093}
1094
1095#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1096
1097template <class _Tp, class _Hash, class _Equal, class _Alloc>
1098template <class _InputIterator>
1099void
1100__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
1101                                                          _InputIterator __last)
1102{
1103    if (bucket_count() != 0)
1104    {
1105        __node_pointer __cache = __detach();
1106#ifndef _LIBCPP_NO_EXCEPTIONS
1107        try
1108        {
1109#endif  // _LIBCPP_NO_EXCEPTIONS
1110            for (; __cache != nullptr && __first != __last; ++__first)
1111            {
1112                __cache->__value_ = *__first;
1113                __node_pointer __next = __cache->__next_;
1114                __node_insert_unique(__cache);
1115                __cache = __next;
1116            }
1117#ifndef _LIBCPP_NO_EXCEPTIONS
1118        }
1119        catch (...)
1120        {
1121            __deallocate(__cache);
1122            throw;
1123        }
1124#endif  // _LIBCPP_NO_EXCEPTIONS
1125        __deallocate(__cache);
1126    }
1127    for (; __first != __last; ++__first)
1128        __insert_unique(*__first);
1129}
1130
1131template <class _Tp, class _Hash, class _Equal, class _Alloc>
1132template <class _InputIterator>
1133void
1134__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
1135                                                         _InputIterator __last)
1136{
1137    if (bucket_count() != 0)
1138    {
1139        __node_pointer __cache = __detach();
1140#ifndef _LIBCPP_NO_EXCEPTIONS
1141        try
1142        {
1143#endif  // _LIBCPP_NO_EXCEPTIONS
1144            for (; __cache != nullptr && __first != __last; ++__first)
1145            {
1146                __cache->__value_ = *__first;
1147                __node_pointer __next = __cache->__next_;
1148                __node_insert_multi(__cache);
1149                __cache = __next;
1150            }
1151#ifndef _LIBCPP_NO_EXCEPTIONS
1152        }
1153        catch (...)
1154        {
1155            __deallocate(__cache);
1156            throw;
1157        }
1158#endif  // _LIBCPP_NO_EXCEPTIONS
1159        __deallocate(__cache);
1160    }
1161    for (; __first != __last; ++__first)
1162        __insert_multi(*__first);
1163}
1164
1165template <class _Tp, class _Hash, class _Equal, class _Alloc>
1166inline _LIBCPP_INLINE_VISIBILITY
1167typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1168__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
1169{
1170    return iterator(__p1_.first().__next_);
1171}
1172
1173template <class _Tp, class _Hash, class _Equal, class _Alloc>
1174inline _LIBCPP_INLINE_VISIBILITY
1175typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1176__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
1177{
1178    return iterator(nullptr);
1179}
1180
1181template <class _Tp, class _Hash, class _Equal, class _Alloc>
1182inline _LIBCPP_INLINE_VISIBILITY
1183typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1184__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
1185{
1186    return const_iterator(__p1_.first().__next_);
1187}
1188
1189template <class _Tp, class _Hash, class _Equal, class _Alloc>
1190inline _LIBCPP_INLINE_VISIBILITY
1191typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1192__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
1193{
1194    return const_iterator(nullptr);
1195}
1196
1197template <class _Tp, class _Hash, class _Equal, class _Alloc>
1198void
1199__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
1200{
1201    if (size() > 0)
1202    {
1203        __deallocate(__p1_.first().__next_);
1204        __p1_.first().__next_ = nullptr;
1205        size_type __bc = bucket_count();
1206        for (size_type __i = 0; __i < __bc; ++__i)
1207            __bucket_list_[__i] = nullptr;
1208        size() = 0;
1209    }
1210}
1211
1212template <class _Tp, class _Hash, class _Equal, class _Alloc>
1213pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1214__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
1215{
1216    __nd->__hash_ = hash_function()(__nd->__value_);
1217    size_type __bc = bucket_count();
1218    bool __inserted = false;
1219    __node_pointer __ndptr;
1220    size_t __chash;
1221    if (__bc != 0)
1222    {
1223        __chash = __constrain_hash(__nd->__hash_, __bc);
1224        __ndptr = __bucket_list_[__chash];
1225        if (__ndptr != nullptr)
1226        {
1227            for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
1228                                             __constrain_hash(__ndptr->__hash_, __bc) == __chash;
1229                                                     __ndptr = __ndptr->__next_)
1230            {
1231                if (key_eq()(__ndptr->__value_, __nd->__value_))
1232                    goto __done;
1233            }
1234        }
1235    }
1236    {
1237        if (size()+1 > __bc * max_load_factor() || __bc == 0)
1238        {
1239            rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1240                           size_type(ceil(float(size() + 1) / max_load_factor()))));
1241            __bc = bucket_count();
1242            __chash = __constrain_hash(__nd->__hash_, __bc);
1243        }
1244        // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1245        __node_pointer __pn = __bucket_list_[__chash];
1246        if (__pn == nullptr)
1247        {
1248            __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1249            __nd->__next_ = __pn->__next_;
1250            __pn->__next_ = __nd;
1251            // fix up __bucket_list_
1252            __bucket_list_[__chash] = __pn;
1253            if (__nd->__next_ != nullptr)
1254                __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd;
1255        }
1256        else
1257        {
1258            __nd->__next_ = __pn->__next_;
1259            __pn->__next_ = __nd;
1260        }
1261        __ndptr = __nd;
1262        // increment size
1263        ++size();
1264        __inserted = true;
1265    }
1266__done:
1267    return pair<iterator, bool>(iterator(__ndptr), __inserted);
1268}
1269
1270template <class _Tp, class _Hash, class _Equal, class _Alloc>
1271typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1272__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
1273{
1274    __cp->__hash_ = hash_function()(__cp->__value_);
1275    size_type __bc = bucket_count();
1276    if (size()+1 > __bc * max_load_factor() || __bc == 0)
1277    {
1278        rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1279                       size_type(ceil(float(size() + 1) / max_load_factor()))));
1280        __bc = bucket_count();
1281    }
1282    size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1283    __node_pointer __pn = __bucket_list_[__chash];
1284    if (__pn == nullptr)
1285    {
1286        __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1287        __cp->__next_ = __pn->__next_;
1288        __pn->__next_ = __cp;
1289        // fix up __bucket_list_
1290        __bucket_list_[__chash] = __pn;
1291        if (__cp->__next_ != nullptr)
1292            __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp;
1293    }
1294    else
1295    {
1296        for (bool __found = false; __pn->__next_ != nullptr &&
1297                                   __constrain_hash(__pn->__next_->__hash_, __bc) == __chash;
1298                                                           __pn = __pn->__next_)
1299        {
1300            //      __found    key_eq()     action
1301            //      false       false       loop
1302            //      true        true        loop
1303            //      false       true        set __found to true
1304            //      true        false       break
1305            if (__found != (__pn->__next_->__hash_ == __cp->__hash_ &&
1306                            key_eq()(__pn->__next_->__value_, __cp->__value_)))
1307            {
1308                if (!__found)
1309                    __found = true;
1310                else
1311                    break;
1312            }
1313        }
1314        __cp->__next_ = __pn->__next_;
1315        __pn->__next_ = __cp;
1316        if (__cp->__next_ != nullptr)
1317        {
1318            size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc);
1319            if (__nhash != __chash)
1320                __bucket_list_[__nhash] = __cp;
1321        }
1322    }
1323    ++size();
1324    return iterator(__cp);
1325}
1326
1327template <class _Tp, class _Hash, class _Equal, class _Alloc>
1328typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1329__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
1330        const_iterator __p, __node_pointer __cp)
1331{
1332    if (__p != end() && key_eq()(*__p, __cp->__value_))
1333    {
1334        __node_pointer __np = __p.__node_;
1335        __cp->__hash_ = __np->__hash_;
1336        size_type __bc = bucket_count();
1337        if (size()+1 > __bc * max_load_factor() || __bc == 0)
1338        {
1339            rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1340                           size_type(ceil(float(size() + 1) / max_load_factor()))));
1341            __bc = bucket_count();
1342        }
1343        size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1344        __node_pointer __pp = __bucket_list_[__chash];
1345        while (__pp->__next_ != __np)
1346            __pp = __pp->__next_;
1347        __cp->__next_ = __np;
1348        __pp->__next_ = __cp;
1349        ++size();
1350        return iterator(__cp);
1351    }
1352    return __node_insert_multi(__cp);
1353}
1354
1355template <class _Tp, class _Hash, class _Equal, class _Alloc>
1356pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1357__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x)
1358{
1359    size_t __hash = hash_function()(__x);
1360    size_type __bc = bucket_count();
1361    bool __inserted = false;
1362    __node_pointer __nd;
1363    size_t __chash;
1364    if (__bc != 0)
1365    {
1366        __chash = __constrain_hash(__hash, __bc);
1367        __nd = __bucket_list_[__chash];
1368        if (__nd != nullptr)
1369        {
1370            for (__nd = __nd->__next_; __nd != nullptr &&
1371                                       __constrain_hash(__nd->__hash_, __bc) == __chash;
1372                                                           __nd = __nd->__next_)
1373            {
1374                if (key_eq()(__nd->__value_, __x))
1375                    goto __done;
1376            }
1377        }
1378    }
1379    {
1380        __node_holder __h = __construct_node(__x, __hash);
1381        if (size()+1 > __bc * max_load_factor() || __bc == 0)
1382        {
1383            rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1384                           size_type(ceil(float(size() + 1) / max_load_factor()))));
1385            __bc = bucket_count();
1386            __chash = __constrain_hash(__hash, __bc);
1387        }
1388        // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1389        __node_pointer __pn = __bucket_list_[__chash];
1390        if (__pn == nullptr)
1391        {
1392            __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1393            __h->__next_ = __pn->__next_;
1394            __pn->__next_ = __h.get();
1395            // fix up __bucket_list_
1396            __bucket_list_[__chash] = __pn;
1397            if (__h->__next_ != nullptr)
1398                __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get();
1399        }
1400        else
1401        {
1402            __h->__next_ = __pn->__next_;
1403            __pn->__next_ = __h.get();
1404        }
1405        __nd = __h.release();
1406        // increment size
1407        ++size();
1408        __inserted = true;
1409    }
1410__done:
1411    return pair<iterator, bool>(iterator(__nd), __inserted);
1412}
1413
1414#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1415#ifndef _LIBCPP_HAS_NO_VARIADICS
1416
1417template <class _Tp, class _Hash, class _Equal, class _Alloc>
1418template <class... _Args>
1419pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1420__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args)
1421{
1422    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1423    pair<iterator, bool> __r = __node_insert_unique(__h.get());
1424    if (__r.second)
1425        __h.release();
1426    return __r;
1427}
1428
1429template <class _Tp, class _Hash, class _Equal, class _Alloc>
1430template <class... _Args>
1431typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1432__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
1433{
1434    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1435    iterator __r = __node_insert_multi(__h.get());
1436    __h.release();
1437    return __r;
1438}
1439
1440template <class _Tp, class _Hash, class _Equal, class _Alloc>
1441template <class... _Args>
1442typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1443__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
1444        const_iterator __p, _Args&&... __args)
1445{
1446    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1447    iterator __r = __node_insert_multi(__p, __h.get());
1448    __h.release();
1449    return __r;
1450}
1451
1452#endif  // _LIBCPP_HAS_NO_VARIADICS
1453
1454template <class _Tp, class _Hash, class _Equal, class _Alloc>
1455template <class _Pp>
1456pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1457__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x)
1458{
1459    __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
1460    pair<iterator, bool> __r = __node_insert_unique(__h.get());
1461    if (__r.second)
1462        __h.release();
1463    return __r;
1464}
1465
1466#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1467
1468#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1469
1470template <class _Tp, class _Hash, class _Equal, class _Alloc>
1471template <class _Pp>
1472typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1473__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x)
1474{
1475    __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
1476    iterator __r = __node_insert_multi(__h.get());
1477    __h.release();
1478    return __r;
1479}
1480
1481template <class _Tp, class _Hash, class _Equal, class _Alloc>
1482template <class _Pp>
1483typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1484__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
1485                                                         _Pp&& __x)
1486{
1487    __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
1488    iterator __r = __node_insert_multi(__p, __h.get());
1489    __h.release();
1490    return __r;
1491}
1492
1493#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1494
1495template <class _Tp, class _Hash, class _Equal, class _Alloc>
1496typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1497__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x)
1498{
1499    __node_holder __h = __construct_node(__x);
1500    iterator __r = __node_insert_multi(__h.get());
1501    __h.release();
1502    return __r;
1503}
1504
1505template <class _Tp, class _Hash, class _Equal, class _Alloc>
1506typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1507__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
1508                                                         const value_type& __x)
1509{
1510    __node_holder __h = __construct_node(__x);
1511    iterator __r = __node_insert_multi(__p, __h.get());
1512    __h.release();
1513    return __r;
1514}
1515
1516#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1517
1518template <class _Tp, class _Hash, class _Equal, class _Alloc>
1519void
1520__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
1521{
1522    if (__n == 1)
1523        __n = 2;
1524    else if (__n & (__n - 1))
1525        __n = __next_prime(__n);
1526    size_type __bc = bucket_count();
1527    if (__n > __bc)
1528        __rehash(__n);
1529    else if (__n < __bc)
1530    {
1531        __n = _VSTD::max<size_type>
1532              (
1533                  __n,
1534                  __is_power2(__bc) ? __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
1535                                      __next_prime(size_t(ceil(float(size()) / max_load_factor())))
1536              );
1537        if (__n < __bc)
1538            __rehash(__n);
1539    }
1540}
1541
1542template <class _Tp, class _Hash, class _Equal, class _Alloc>
1543void
1544__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
1545{
1546    __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
1547    __bucket_list_.reset(__nbc > 0 ?
1548                      __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
1549    __bucket_list_.get_deleter().size() = __nbc;
1550    if (__nbc > 0)
1551    {
1552        for (size_type __i = 0; __i < __nbc; ++__i)
1553            __bucket_list_[__i] = nullptr;
1554        __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())));
1555        __node_pointer __cp = __pp->__next_;
1556        if (__cp != nullptr)
1557        {
1558            size_type __chash = __constrain_hash(__cp->__hash_, __nbc);
1559            __bucket_list_[__chash] = __pp;
1560            size_type __phash = __chash;
1561            for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr;
1562                                                           __cp = __pp->__next_)
1563            {
1564                __chash = __constrain_hash(__cp->__hash_, __nbc);
1565                if (__chash == __phash)
1566                    __pp = __cp;
1567                else
1568                {
1569                    if (__bucket_list_[__chash] == nullptr)
1570                    {
1571                        __bucket_list_[__chash] = __pp;
1572                        __pp = __cp;
1573                        __phash = __chash;
1574                    }
1575                    else
1576                    {
1577                        __node_pointer __np = __cp;
1578                        for (; __np->__next_ != nullptr &&
1579                               key_eq()(__cp->__value_, __np->__next_->__value_);
1580                                                           __np = __np->__next_)
1581                            ;
1582                        __pp->__next_ = __np->__next_;
1583                        __np->__next_ = __bucket_list_[__chash]->__next_;
1584                        __bucket_list_[__chash]->__next_ = __cp;
1585
1586                    }
1587                }
1588            }
1589        }
1590    }
1591}
1592
1593template <class _Tp, class _Hash, class _Equal, class _Alloc>
1594template <class _Key>
1595typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1596__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
1597{
1598    size_t __hash = hash_function()(__k);
1599    size_type __bc = bucket_count();
1600    if (__bc != 0)
1601    {
1602        size_t __chash = __constrain_hash(__hash, __bc);
1603        __node_pointer __nd = __bucket_list_[__chash];
1604        if (__nd != nullptr)
1605        {
1606            for (__nd = __nd->__next_; __nd != nullptr &&
1607                                       __constrain_hash(__nd->__hash_, __bc) == __chash;
1608                                                           __nd = __nd->__next_)
1609            {
1610                if (key_eq()(__nd->__value_, __k))
1611                    return iterator(__nd);
1612            }
1613        }
1614    }
1615    return end();
1616}
1617
1618template <class _Tp, class _Hash, class _Equal, class _Alloc>
1619template <class _Key>
1620typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1621__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
1622{
1623    size_t __hash = hash_function()(__k);
1624    size_type __bc = bucket_count();
1625    if (__bc != 0)
1626    {
1627        size_t __chash = __constrain_hash(__hash, __bc);
1628        __node_const_pointer __nd = __bucket_list_[__chash];
1629        if (__nd != nullptr)
1630        {
1631            for (__nd = __nd->__next_; __nd != nullptr &&
1632                                           __constrain_hash(__nd->__hash_, __bc) == __chash;
1633                                                           __nd = __nd->__next_)
1634            {
1635                if (key_eq()(__nd->__value_, __k))
1636                    return const_iterator(__nd);
1637            }
1638        }
1639
1640    }
1641    return end();
1642}
1643
1644#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1645#ifndef _LIBCPP_HAS_NO_VARIADICS
1646
1647template <class _Tp, class _Hash, class _Equal, class _Alloc>
1648template <class ..._Args>
1649typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1650__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
1651{
1652    __node_allocator& __na = __node_alloc();
1653    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1654    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...);
1655    __h.get_deleter().__value_constructed = true;
1656    __h->__hash_ = hash_function()(__h->__value_);
1657    __h->__next_ = nullptr;
1658    return __h;
1659}
1660
1661#endif  // _LIBCPP_HAS_NO_VARIADICS
1662
1663template <class _Tp, class _Hash, class _Equal, class _Alloc>
1664typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1665__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v,
1666                                                           size_t __hash)
1667{
1668    __node_allocator& __na = __node_alloc();
1669    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1670    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1671    __h.get_deleter().__value_constructed = true;
1672    __h->__hash_ = __hash;
1673    __h->__next_ = nullptr;
1674    return _VSTD::move(__h);
1675}
1676
1677#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1678
1679template <class _Tp, class _Hash, class _Equal, class _Alloc>
1680typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1681__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v)
1682{
1683    __node_allocator& __na = __node_alloc();
1684    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1685    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
1686    __h.get_deleter().__value_constructed = true;
1687    __h->__hash_ = hash_function()(__h->__value_);
1688    __h->__next_ = nullptr;
1689    return _VSTD::move(__h);
1690}
1691
1692#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1693
1694template <class _Tp, class _Hash, class _Equal, class _Alloc>
1695typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1696__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v,
1697                                                           size_t __hash)
1698{
1699    __node_allocator& __na = __node_alloc();
1700    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1701    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
1702    __h.get_deleter().__value_constructed = true;
1703    __h->__hash_ = __hash;
1704    __h->__next_ = nullptr;
1705    return _VSTD::move(__h);
1706}
1707
1708template <class _Tp, class _Hash, class _Equal, class _Alloc>
1709typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1710__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
1711{
1712    __node_pointer __np = __p.__node_;
1713    iterator __r(__np);
1714    ++__r;
1715    remove(__p);
1716    return __r;
1717}
1718
1719template <class _Tp, class _Hash, class _Equal, class _Alloc>
1720typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1721__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
1722                                                const_iterator __last)
1723{
1724    for (const_iterator __p = __first; __first != __last; __p = __first)
1725    {
1726        ++__first;
1727        erase(__p);
1728    }
1729    __node_pointer __np = __last.__node_;
1730    return iterator (__np);
1731}
1732
1733template <class _Tp, class _Hash, class _Equal, class _Alloc>
1734template <class _Key>
1735typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1736__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
1737{
1738    iterator __i = find(__k);
1739    if (__i == end())
1740        return 0;
1741    erase(__i);
1742    return 1;
1743}
1744
1745template <class _Tp, class _Hash, class _Equal, class _Alloc>
1746template <class _Key>
1747typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1748__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
1749{
1750    size_type __r = 0;
1751    iterator __i = find(__k);
1752    if (__i != end())
1753    {
1754        iterator __e = end();
1755        do
1756        {
1757            erase(__i++);
1758            ++__r;
1759        } while (__i != __e && key_eq()(*__i, __k));
1760    }
1761    return __r;
1762}
1763
1764template <class _Tp, class _Hash, class _Equal, class _Alloc>
1765typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1766__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
1767{
1768    // current node
1769    __node_pointer __cn = __p.__node_;
1770    size_type __bc = bucket_count();
1771    size_t __chash = __constrain_hash(__cn->__hash_, __bc);
1772    // find previous node
1773    __node_pointer __pn = __bucket_list_[__chash];
1774    for (; __pn->__next_ != __cn; __pn = __pn->__next_)
1775        ;
1776    // Fix up __bucket_list_
1777        // if __pn is not in same bucket (before begin is not in same bucket) &&
1778        //    if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
1779    if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))
1780                            || __constrain_hash(__pn->__hash_, __bc) != __chash)
1781    {
1782        if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash)
1783            __bucket_list_[__chash] = nullptr;
1784    }
1785        // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
1786    if (__cn->__next_ != nullptr)
1787    {
1788        size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc);
1789        if (__nhash != __chash)
1790            __bucket_list_[__nhash] = __pn;
1791    }
1792    // remove __cn
1793    __pn->__next_ = __cn->__next_;
1794    __cn->__next_ = nullptr;
1795    --size();
1796    return __node_holder(__cn, _Dp(__node_alloc(), true));
1797}
1798
1799template <class _Tp, class _Hash, class _Equal, class _Alloc>
1800template <class _Key>
1801inline _LIBCPP_INLINE_VISIBILITY
1802typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1803__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
1804{
1805    return static_cast<size_type>(find(__k) != end());
1806}
1807
1808template <class _Tp, class _Hash, class _Equal, class _Alloc>
1809template <class _Key>
1810typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1811__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
1812{
1813    size_type __r = 0;
1814    const_iterator __i = find(__k);
1815    if (__i != end())
1816    {
1817        const_iterator __e = end();
1818        do
1819        {
1820            ++__i;
1821            ++__r;
1822        } while (__i != __e && key_eq()(*__i, __k));
1823    }
1824    return __r;
1825}
1826
1827template <class _Tp, class _Hash, class _Equal, class _Alloc>
1828template <class _Key>
1829pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
1830     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
1831__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
1832        const _Key& __k)
1833{
1834    iterator __i = find(__k);
1835    iterator __j = __i;
1836    if (__i != end())
1837        ++__j;
1838    return pair<iterator, iterator>(__i, __j);
1839}
1840
1841template <class _Tp, class _Hash, class _Equal, class _Alloc>
1842template <class _Key>
1843pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
1844     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
1845__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
1846        const _Key& __k) const
1847{
1848    const_iterator __i = find(__k);
1849    const_iterator __j = __i;
1850    if (__i != end())
1851        ++__j;
1852    return pair<const_iterator, const_iterator>(__i, __j);
1853}
1854
1855template <class _Tp, class _Hash, class _Equal, class _Alloc>
1856template <class _Key>
1857pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
1858     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
1859__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
1860        const _Key& __k)
1861{
1862    iterator __i = find(__k);
1863    iterator __j = __i;
1864    if (__i != end())
1865    {
1866        iterator __e = end();
1867        do
1868        {
1869            ++__j;
1870        } while (__j != __e && key_eq()(*__j, __k));
1871    }
1872    return pair<iterator, iterator>(__i, __j);
1873}
1874
1875template <class _Tp, class _Hash, class _Equal, class _Alloc>
1876template <class _Key>
1877pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
1878     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
1879__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
1880        const _Key& __k) const
1881{
1882    const_iterator __i = find(__k);
1883    const_iterator __j = __i;
1884    if (__i != end())
1885    {
1886        const_iterator __e = end();
1887        do
1888        {
1889            ++__j;
1890        } while (__j != __e && key_eq()(*__j, __k));
1891    }
1892    return pair<const_iterator, const_iterator>(__i, __j);
1893}
1894
1895template <class _Tp, class _Hash, class _Equal, class _Alloc>
1896void
1897__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
1898    _NOEXCEPT_(
1899        (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
1900         __is_nothrow_swappable<__pointer_allocator>::value) &&
1901        (!__node_traits::propagate_on_container_swap::value ||
1902         __is_nothrow_swappable<__node_allocator>::value) &&
1903        __is_nothrow_swappable<hasher>::value &&
1904        __is_nothrow_swappable<key_equal>::value)
1905{
1906    {
1907    __node_pointer_pointer __npp = __bucket_list_.release();
1908    __bucket_list_.reset(__u.__bucket_list_.release());
1909    __u.__bucket_list_.reset(__npp);
1910    }
1911    _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
1912    __swap_alloc(__bucket_list_.get_deleter().__alloc(),
1913             __u.__bucket_list_.get_deleter().__alloc());
1914    __swap_alloc(__node_alloc(), __u.__node_alloc());
1915    _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
1916    __p2_.swap(__u.__p2_);
1917    __p3_.swap(__u.__p3_);
1918    if (size() > 0)
1919        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
1920            static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1921    if (__u.size() > 0)
1922        __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] =
1923            static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first()));
1924}
1925
1926template <class _Tp, class _Hash, class _Equal, class _Alloc>
1927typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1928__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
1929{
1930    __node_const_pointer __np = __bucket_list_[__n];
1931    size_type __bc = bucket_count();
1932    size_type __r = 0;
1933    if (__np != nullptr)
1934    {
1935        for (__np = __np->__next_; __np != nullptr &&
1936                                   __constrain_hash(__np->__hash_, __bc) == __n;
1937                                                    __np = __np->__next_, ++__r)
1938            ;
1939    }
1940    return __r;
1941}
1942
1943template <class _Tp, class _Hash, class _Equal, class _Alloc>
1944inline _LIBCPP_INLINE_VISIBILITY
1945void
1946swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
1947     __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
1948    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1949{
1950    __x.swap(__y);
1951}
1952
1953_LIBCPP_END_NAMESPACE_STD
1954
1955#endif  // _LIBCPP__HASH_TABLE
1956