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