← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to system/include/libcxx/__hash_table

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

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