blob: e41ccf293eb46d325f923b06dcdbea4c6b0455db [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
Howard Hinnantb64f8b02010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00008//
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
Howard Hinnant66c6f972011-11-29 16:45:27 +000021#include <__undef_min_max>
Saleem Abdulrasoolf1b30c42015-02-13 22:15:32 +000022#include <__undef___deallocate>
Howard Hinnant66c6f972011-11-29 16:45:27 +000023
Eric Fiselierb9536102014-08-10 23:53:08 +000024#include <__debug>
Howard Hinnant8b00e6c2013-08-02 00:26:35 +000025
Howard Hinnant08e17472011-10-17 20:05:10 +000026#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000027#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10 +000028#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000029
30_LIBCPP_BEGIN_NAMESPACE_STD
31
Howard Hinnant83eade62013-03-06 23:30:19 +000032_LIBCPP_FUNC_VIS
Howard Hinnant2b1b2d42011-06-14 19:58:17 +000033size_t __next_prime(size_t __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000034
35template <class _NodePtr>
36struct __hash_node_base
37{
38 typedef __hash_node_base __first_node;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000039
Howard Hinnantdf85e572011-02-27 18:02:02 +000040 _NodePtr __next_;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000041
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000042 _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000043};
44
45template <class _Tp, class _VoidPtr>
46struct __hash_node
47 : public __hash_node_base
48 <
49 typename pointer_traits<_VoidPtr>::template
50#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
51 rebind<__hash_node<_Tp, _VoidPtr> >
52#else
53 rebind<__hash_node<_Tp, _VoidPtr> >::other
54#endif
55 >
56{
57 typedef _Tp value_type;
58
59 size_t __hash_;
60 value_type __value_;
61};
62
Howard Hinnant7a445152012-07-06 17:31:14 +000063inline _LIBCPP_INLINE_VISIBILITY
64bool
Eric Fiselier57947ca2015-02-02 21:31:48 +000065__is_hash_power2(size_t __bc)
Howard Hinnant7a445152012-07-06 17:31:14 +000066{
67 return __bc > 2 && !(__bc & (__bc - 1));
68}
69
70inline _LIBCPP_INLINE_VISIBILITY
71size_t
72__constrain_hash(size_t __h, size_t __bc)
73{
74 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc;
75}
76
77inline _LIBCPP_INLINE_VISIBILITY
78size_t
Eric Fiselier57947ca2015-02-02 21:31:48 +000079__next_hash_pow2(size_t __n)
Howard Hinnant7a445152012-07-06 17:31:14 +000080{
81 return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
82}
83
Howard Hinnant2b1b2d42011-06-14 19:58:17 +000084template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
Howard Hinnant0f678bd2013-08-12 18:38:34 +000085template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
86template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
87template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000088
89template <class _NodePtr>
Howard Hinnant0f678bd2013-08-12 18:38:34 +000090class _LIBCPP_TYPE_VIS_ONLY __hash_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000091{
92 typedef _NodePtr __node_pointer;
93
94 __node_pointer __node_;
95
96public:
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
Howard Hinnant39213642013-07-23 22:01:58 +0000109 _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT
Marshall Clow193ef032013-08-07 21:30:44 +0000110#if _LIBCPP_STD_VER > 11
111 : __node_(nullptr)
112#endif
Howard Hinnant39213642013-07-23 22:01:58 +0000113 {
114#if _LIBCPP_DEBUG_LEVEL >= 2
115 __get_db()->__insert_i(this);
116#endif
117 }
118
119#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000120
Howard Hinnant99acc502010-09-21 17:32:39 +0000121 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000122 __hash_iterator(const __hash_iterator& __i)
123 : __node_(__i.__node_)
124 {
125 __get_db()->__iterator_copy(this, &__i);
126 }
127
Howard Hinnant99acc502010-09-21 17:32:39 +0000128 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000129 ~__hash_iterator()
130 {
131 __get_db()->__erase_i(this);
132 }
133
134 _LIBCPP_INLINE_VISIBILITY
135 __hash_iterator& operator=(const __hash_iterator& __i)
136 {
137 if (this != &__i)
138 {
139 __get_db()->__iterator_copy(this, &__i);
140 __node_ = __i.__node_;
141 }
142 return *this;
143 }
144
145#endif // _LIBCPP_DEBUG_LEVEL >= 2
146
147 _LIBCPP_INLINE_VISIBILITY
148 reference operator*() const
149 {
150#if _LIBCPP_DEBUG_LEVEL >= 2
151 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
152 "Attempted to dereference a non-dereferenceable unordered container iterator");
153#endif
154 return __node_->__value_;
155 }
156 _LIBCPP_INLINE_VISIBILITY
157 pointer operator->() const
158 {
159#if _LIBCPP_DEBUG_LEVEL >= 2
160 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
161 "Attempted to dereference a non-dereferenceable unordered container iterator");
162#endif
163 return pointer_traits<pointer>::pointer_to(__node_->__value_);
164 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000165
Howard Hinnant99acc502010-09-21 17:32:39 +0000166 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000167 __hash_iterator& operator++()
168 {
Howard Hinnant39213642013-07-23 22:01:58 +0000169#if _LIBCPP_DEBUG_LEVEL >= 2
170 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
171 "Attempted to increment non-incrementable unordered container iterator");
172#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000173 __node_ = __node_->__next_;
174 return *this;
175 }
176
Howard Hinnant99acc502010-09-21 17:32:39 +0000177 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000178 __hash_iterator operator++(int)
179 {
180 __hash_iterator __t(*this);
181 ++(*this);
182 return __t;
183 }
184
Howard Hinnant99acc502010-09-21 17:32:39 +0000185 friend _LIBCPP_INLINE_VISIBILITY
186 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
Howard Hinnant39213642013-07-23 22:01:58 +0000187 {
Howard Hinnant39213642013-07-23 22:01:58 +0000188 return __x.__node_ == __y.__node_;
189 }
Howard Hinnant99acc502010-09-21 17:32:39 +0000190 friend _LIBCPP_INLINE_VISIBILITY
191 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
Howard Hinnant39213642013-07-23 22:01:58 +0000192 {return !(__x == __y);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000193
194private:
Howard Hinnant39213642013-07-23 22:01:58 +0000195#if _LIBCPP_DEBUG_LEVEL >= 2
196 _LIBCPP_INLINE_VISIBILITY
197 __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT
198 : __node_(__node)
199 {
200 __get_db()->__insert_ic(this, __c);
201 }
202#else
Howard Hinnant99acc502010-09-21 17:32:39 +0000203 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000204 __hash_iterator(__node_pointer __node) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000205 : __node_(__node)
206 {}
Howard Hinnant39213642013-07-23 22:01:58 +0000207#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000208
209 template <class, class, class, class> friend class __hash_table;
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000210 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
211 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
212 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
213 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000214};
215
216template <class _ConstNodePtr>
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000217class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000218{
219 typedef _ConstNodePtr __node_pointer;
220
221 __node_pointer __node_;
222
223 typedef typename remove_const<
224 typename pointer_traits<__node_pointer>::element_type
225 >::type __node;
226
227public:
228 typedef forward_iterator_tag iterator_category;
229 typedef typename __node::value_type value_type;
230 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
231 typedef const value_type& reference;
232 typedef typename pointer_traits<__node_pointer>::template
233#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
234 rebind<const value_type>
235#else
236 rebind<const value_type>::other
237#endif
238 pointer;
239 typedef typename pointer_traits<__node_pointer>::template
240#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
241 rebind<__node>
242#else
243 rebind<__node>::other
244#endif
245 __non_const_node_pointer;
246 typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator;
247
Howard Hinnant39213642013-07-23 22:01:58 +0000248 _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT
Marshall Clow193ef032013-08-07 21:30:44 +0000249#if _LIBCPP_STD_VER > 11
250 : __node_(nullptr)
251#endif
Howard Hinnant39213642013-07-23 22:01:58 +0000252 {
253#if _LIBCPP_DEBUG_LEVEL >= 2
254 __get_db()->__insert_i(this);
255#endif
256 }
Howard Hinnant99acc502010-09-21 17:32:39 +0000257 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000258 __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000259 : __node_(__x.__node_)
Howard Hinnant39213642013-07-23 22:01:58 +0000260 {
261#if _LIBCPP_DEBUG_LEVEL >= 2
262 __get_db()->__iterator_copy(this, &__x);
263#endif
264 }
265
266#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000267
Howard Hinnant99acc502010-09-21 17:32:39 +0000268 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000269 __hash_const_iterator(const __hash_const_iterator& __i)
270 : __node_(__i.__node_)
271 {
272 __get_db()->__iterator_copy(this, &__i);
273 }
274
Howard Hinnant99acc502010-09-21 17:32:39 +0000275 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000276 ~__hash_const_iterator()
277 {
278 __get_db()->__erase_i(this);
279 }
280
281 _LIBCPP_INLINE_VISIBILITY
282 __hash_const_iterator& operator=(const __hash_const_iterator& __i)
283 {
284 if (this != &__i)
285 {
286 __get_db()->__iterator_copy(this, &__i);
287 __node_ = __i.__node_;
288 }
289 return *this;
290 }
291
292#endif // _LIBCPP_DEBUG_LEVEL >= 2
293
294 _LIBCPP_INLINE_VISIBILITY
295 reference operator*() const
296 {
297#if _LIBCPP_DEBUG_LEVEL >= 2
298 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
299 "Attempted to dereference a non-dereferenceable unordered container const_iterator");
300#endif
301 return __node_->__value_;
302 }
303 _LIBCPP_INLINE_VISIBILITY
304 pointer operator->() const
305 {
306#if _LIBCPP_DEBUG_LEVEL >= 2
307 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
308 "Attempted to dereference a non-dereferenceable unordered container const_iterator");
309#endif
310 return pointer_traits<pointer>::pointer_to(__node_->__value_);
311 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000312
Howard Hinnant99acc502010-09-21 17:32:39 +0000313 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000314 __hash_const_iterator& operator++()
315 {
Howard Hinnant39213642013-07-23 22:01:58 +0000316#if _LIBCPP_DEBUG_LEVEL >= 2
317 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
318 "Attempted to increment non-incrementable unordered container const_iterator");
319#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000320 __node_ = __node_->__next_;
321 return *this;
322 }
323
Howard Hinnant99acc502010-09-21 17:32:39 +0000324 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000325 __hash_const_iterator operator++(int)
326 {
327 __hash_const_iterator __t(*this);
328 ++(*this);
329 return __t;
330 }
331
Howard Hinnant99acc502010-09-21 17:32:39 +0000332 friend _LIBCPP_INLINE_VISIBILITY
333 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
Howard Hinnant39213642013-07-23 22:01:58 +0000334 {
Howard Hinnant39213642013-07-23 22:01:58 +0000335 return __x.__node_ == __y.__node_;
336 }
Howard Hinnant99acc502010-09-21 17:32:39 +0000337 friend _LIBCPP_INLINE_VISIBILITY
338 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
Howard Hinnant39213642013-07-23 22:01:58 +0000339 {return !(__x == __y);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000340
341private:
Howard Hinnant39213642013-07-23 22:01:58 +0000342#if _LIBCPP_DEBUG_LEVEL >= 2
343 _LIBCPP_INLINE_VISIBILITY
344 __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT
345 : __node_(__node)
346 {
347 __get_db()->__insert_ic(this, __c);
348 }
349#else
Howard Hinnant99acc502010-09-21 17:32:39 +0000350 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000351 __hash_const_iterator(__node_pointer __node) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000352 : __node_(__node)
353 {}
Howard Hinnant39213642013-07-23 22:01:58 +0000354#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000355
356 template <class, class, class, class> friend class __hash_table;
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000357 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
358 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
359 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000360};
361
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000362template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000363
364template <class _NodePtr>
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000365class _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000366{
367 typedef _NodePtr __node_pointer;
368
369 __node_pointer __node_;
370 size_t __bucket_;
371 size_t __bucket_count_;
372
373 typedef pointer_traits<__node_pointer> __pointer_traits;
374public:
375 typedef forward_iterator_tag iterator_category;
376 typedef typename __pointer_traits::element_type::value_type value_type;
377 typedef typename __pointer_traits::difference_type difference_type;
378 typedef value_type& reference;
379 typedef typename __pointer_traits::template
380#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
381 rebind<value_type>
382#else
383 rebind<value_type>::other
384#endif
385 pointer;
386
Howard Hinnant39213642013-07-23 22:01:58 +0000387 _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT
388 {
389#if _LIBCPP_DEBUG_LEVEL >= 2
390 __get_db()->__insert_i(this);
391#endif
392 }
393
394#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000395
Howard Hinnant99acc502010-09-21 17:32:39 +0000396 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000397 __hash_local_iterator(const __hash_local_iterator& __i)
398 : __node_(__i.__node_),
399 __bucket_(__i.__bucket_),
400 __bucket_count_(__i.__bucket_count_)
401 {
402 __get_db()->__iterator_copy(this, &__i);
403 }
404
Howard Hinnant99acc502010-09-21 17:32:39 +0000405 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000406 ~__hash_local_iterator()
407 {
408 __get_db()->__erase_i(this);
409 }
410
411 _LIBCPP_INLINE_VISIBILITY
412 __hash_local_iterator& operator=(const __hash_local_iterator& __i)
413 {
414 if (this != &__i)
415 {
416 __get_db()->__iterator_copy(this, &__i);
417 __node_ = __i.__node_;
418 __bucket_ = __i.__bucket_;
419 __bucket_count_ = __i.__bucket_count_;
420 }
421 return *this;
422 }
423
424#endif // _LIBCPP_DEBUG_LEVEL >= 2
425
426 _LIBCPP_INLINE_VISIBILITY
427 reference operator*() const
428 {
429#if _LIBCPP_DEBUG_LEVEL >= 2
430 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
431 "Attempted to dereference a non-dereferenceable unordered container local_iterator");
432#endif
433 return __node_->__value_;
434 }
435 _LIBCPP_INLINE_VISIBILITY
436 pointer operator->() const
437 {
438#if _LIBCPP_DEBUG_LEVEL >= 2
439 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
440 "Attempted to dereference a non-dereferenceable unordered container local_iterator");
441#endif
442 return pointer_traits<pointer>::pointer_to(__node_->__value_);
443 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000444
Howard Hinnant99acc502010-09-21 17:32:39 +0000445 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000446 __hash_local_iterator& operator++()
447 {
Howard Hinnant39213642013-07-23 22:01:58 +0000448#if _LIBCPP_DEBUG_LEVEL >= 2
449 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
450 "Attempted to increment non-incrementable unordered container local_iterator");
451#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000452 __node_ = __node_->__next_;
Howard Hinnant7a445152012-07-06 17:31:14 +0000453 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000454 __node_ = nullptr;
455 return *this;
456 }
457
Howard Hinnant99acc502010-09-21 17:32:39 +0000458 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000459 __hash_local_iterator operator++(int)
460 {
461 __hash_local_iterator __t(*this);
462 ++(*this);
463 return __t;
464 }
465
Howard Hinnant99acc502010-09-21 17:32:39 +0000466 friend _LIBCPP_INLINE_VISIBILITY
467 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
Howard Hinnant39213642013-07-23 22:01:58 +0000468 {
Howard Hinnant39213642013-07-23 22:01:58 +0000469 return __x.__node_ == __y.__node_;
470 }
Howard Hinnant99acc502010-09-21 17:32:39 +0000471 friend _LIBCPP_INLINE_VISIBILITY
472 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
Howard Hinnant39213642013-07-23 22:01:58 +0000473 {return !(__x == __y);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000474
475private:
Howard Hinnant39213642013-07-23 22:01:58 +0000476#if _LIBCPP_DEBUG_LEVEL >= 2
477 _LIBCPP_INLINE_VISIBILITY
478 __hash_local_iterator(__node_pointer __node, size_t __bucket,
479 size_t __bucket_count, const void* __c) _NOEXCEPT
480 : __node_(__node),
481 __bucket_(__bucket),
482 __bucket_count_(__bucket_count)
483 {
484 __get_db()->__insert_ic(this, __c);
485 if (__node_ != nullptr)
486 __node_ = __node_->__next_;
487 }
488#else
Howard Hinnant99acc502010-09-21 17:32:39 +0000489 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000490 __hash_local_iterator(__node_pointer __node, size_t __bucket,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000491 size_t __bucket_count) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000492 : __node_(__node),
493 __bucket_(__bucket),
494 __bucket_count_(__bucket_count)
495 {
496 if (__node_ != nullptr)
497 __node_ = __node_->__next_;
498 }
Howard Hinnant39213642013-07-23 22:01:58 +0000499#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000500 template <class, class, class, class> friend class __hash_table;
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000501 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
502 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000503};
504
505template <class _ConstNodePtr>
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000506class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000507{
508 typedef _ConstNodePtr __node_pointer;
509
510 __node_pointer __node_;
511 size_t __bucket_;
512 size_t __bucket_count_;
513
514 typedef pointer_traits<__node_pointer> __pointer_traits;
515 typedef typename __pointer_traits::element_type __node;
516 typedef typename remove_const<__node>::type __non_const_node;
517 typedef typename pointer_traits<__node_pointer>::template
518#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
519 rebind<__non_const_node>
520#else
521 rebind<__non_const_node>::other
522#endif
523 __non_const_node_pointer;
524 typedef __hash_local_iterator<__non_const_node_pointer>
525 __non_const_iterator;
526public:
527 typedef forward_iterator_tag iterator_category;
528 typedef typename remove_const<
529 typename __pointer_traits::element_type::value_type
530 >::type value_type;
531 typedef typename __pointer_traits::difference_type difference_type;
532 typedef const value_type& reference;
533 typedef typename __pointer_traits::template
534#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
535 rebind<const value_type>
536#else
537 rebind<const value_type>::other
538#endif
539 pointer;
540
Howard Hinnant39213642013-07-23 22:01:58 +0000541 _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT
542 {
543#if _LIBCPP_DEBUG_LEVEL >= 2
544 __get_db()->__insert_i(this);
545#endif
546 }
547
Howard Hinnant99acc502010-09-21 17:32:39 +0000548 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000549 __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000550 : __node_(__x.__node_),
551 __bucket_(__x.__bucket_),
552 __bucket_count_(__x.__bucket_count_)
Howard Hinnant39213642013-07-23 22:01:58 +0000553 {
554#if _LIBCPP_DEBUG_LEVEL >= 2
555 __get_db()->__iterator_copy(this, &__x);
556#endif
557 }
558
559#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000560
Howard Hinnant99acc502010-09-21 17:32:39 +0000561 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000562 __hash_const_local_iterator(const __hash_const_local_iterator& __i)
563 : __node_(__i.__node_),
564 __bucket_(__i.__bucket_),
565 __bucket_count_(__i.__bucket_count_)
566 {
567 __get_db()->__iterator_copy(this, &__i);
568 }
569
Howard Hinnant99acc502010-09-21 17:32:39 +0000570 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000571 ~__hash_const_local_iterator()
572 {
573 __get_db()->__erase_i(this);
574 }
575
576 _LIBCPP_INLINE_VISIBILITY
577 __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i)
578 {
579 if (this != &__i)
580 {
581 __get_db()->__iterator_copy(this, &__i);
582 __node_ = __i.__node_;
583 __bucket_ = __i.__bucket_;
584 __bucket_count_ = __i.__bucket_count_;
585 }
586 return *this;
587 }
588
589#endif // _LIBCPP_DEBUG_LEVEL >= 2
590
591 _LIBCPP_INLINE_VISIBILITY
592 reference operator*() const
593 {
594#if _LIBCPP_DEBUG_LEVEL >= 2
595 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
596 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
597#endif
598 return __node_->__value_;
599 }
600 _LIBCPP_INLINE_VISIBILITY
601 pointer operator->() const
602 {
603#if _LIBCPP_DEBUG_LEVEL >= 2
604 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
605 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
606#endif
607 return pointer_traits<pointer>::pointer_to(__node_->__value_);
608 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000609
Howard Hinnant99acc502010-09-21 17:32:39 +0000610 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000611 __hash_const_local_iterator& operator++()
612 {
Howard Hinnant39213642013-07-23 22:01:58 +0000613#if _LIBCPP_DEBUG_LEVEL >= 2
614 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
615 "Attempted to increment non-incrementable unordered container const_local_iterator");
616#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000617 __node_ = __node_->__next_;
Howard Hinnant7a445152012-07-06 17:31:14 +0000618 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000619 __node_ = nullptr;
620 return *this;
621 }
622
Howard Hinnant99acc502010-09-21 17:32:39 +0000623 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000624 __hash_const_local_iterator operator++(int)
625 {
626 __hash_const_local_iterator __t(*this);
627 ++(*this);
628 return __t;
629 }
630
Howard Hinnant99acc502010-09-21 17:32:39 +0000631 friend _LIBCPP_INLINE_VISIBILITY
632 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
Howard Hinnant39213642013-07-23 22:01:58 +0000633 {
Howard Hinnant39213642013-07-23 22:01:58 +0000634 return __x.__node_ == __y.__node_;
635 }
Howard Hinnant99acc502010-09-21 17:32:39 +0000636 friend _LIBCPP_INLINE_VISIBILITY
637 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
Howard Hinnant39213642013-07-23 22:01:58 +0000638 {return !(__x == __y);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000639
640private:
Howard Hinnant39213642013-07-23 22:01:58 +0000641#if _LIBCPP_DEBUG_LEVEL >= 2
642 _LIBCPP_INLINE_VISIBILITY
643 __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
644 size_t __bucket_count, const void* __c) _NOEXCEPT
645 : __node_(__node),
646 __bucket_(__bucket),
647 __bucket_count_(__bucket_count)
648 {
649 __get_db()->__insert_ic(this, __c);
650 if (__node_ != nullptr)
651 __node_ = __node_->__next_;
652 }
653#else
Howard Hinnant99acc502010-09-21 17:32:39 +0000654 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000655 __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000656 size_t __bucket_count) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000657 : __node_(__node),
658 __bucket_(__bucket),
659 __bucket_count_(__bucket_count)
660 {
661 if (__node_ != nullptr)
662 __node_ = __node_->__next_;
663 }
Howard Hinnant39213642013-07-23 22:01:58 +0000664#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000665 template <class, class, class, class> friend class __hash_table;
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000666 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000667};
668
669template <class _Alloc>
670class __bucket_list_deallocator
671{
672 typedef _Alloc allocator_type;
673 typedef allocator_traits<allocator_type> __alloc_traits;
674 typedef typename __alloc_traits::size_type size_type;
675
676 __compressed_pair<size_type, allocator_type> __data_;
677public:
678 typedef typename __alloc_traits::pointer pointer;
679
Howard Hinnant99acc502010-09-21 17:32:39 +0000680 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000681 __bucket_list_deallocator()
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000682 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000683 : __data_(0) {}
Howard Hinnant99acc502010-09-21 17:32:39 +0000684
685 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000686 __bucket_list_deallocator(const allocator_type& __a, size_type __size)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000687 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000688 : __data_(__size, __a) {}
689
Howard Hinnant73d21a42010-09-04 23:28:19 +0000690#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000691
Howard Hinnant99acc502010-09-21 17:32:39 +0000692 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000693 __bucket_list_deallocator(__bucket_list_deallocator&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000694 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000695 : __data_(_VSTD::move(__x.__data_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000696 {
697 __x.size() = 0;
698 }
699
Howard Hinnant73d21a42010-09-04 23:28:19 +0000700#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000701
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000702 _LIBCPP_INLINE_VISIBILITY
703 size_type& size() _NOEXCEPT {return __data_.first();}
704 _LIBCPP_INLINE_VISIBILITY
705 size_type size() const _NOEXCEPT {return __data_.first();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000706
Howard Hinnant99acc502010-09-21 17:32:39 +0000707 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000708 allocator_type& __alloc() _NOEXCEPT {return __data_.second();}
709 _LIBCPP_INLINE_VISIBILITY
710 const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();}
711
712 _LIBCPP_INLINE_VISIBILITY
713 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000714 {
715 __alloc_traits::deallocate(__alloc(), __p, size());
716 }
717};
718
Howard Hinnant2b1b2d42011-06-14 19:58:17 +0000719template <class _Alloc> class __hash_map_node_destructor;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000720
721template <class _Alloc>
722class __hash_node_destructor
723{
724 typedef _Alloc allocator_type;
725 typedef allocator_traits<allocator_type> __alloc_traits;
726 typedef typename __alloc_traits::value_type::value_type value_type;
727public:
728 typedef typename __alloc_traits::pointer pointer;
729private:
730
731 allocator_type& __na_;
732
733 __hash_node_destructor& operator=(const __hash_node_destructor&);
734
735public:
736 bool __value_constructed;
737
Howard Hinnant99acc502010-09-21 17:32:39 +0000738 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant199d0ae2011-07-31 17:04:30 +0000739 explicit __hash_node_destructor(allocator_type& __na,
740 bool __constructed = false) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000741 : __na_(__na),
Howard Hinnant199d0ae2011-07-31 17:04:30 +0000742 __value_constructed(__constructed)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000743 {}
744
Howard Hinnant99acc502010-09-21 17:32:39 +0000745 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000746 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000747 {
748 if (__value_constructed)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000749 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000750 if (__p)
751 __alloc_traits::deallocate(__na_, __p, 1);
752 }
753
754 template <class> friend class __hash_map_node_destructor;
755};
756
757template <class _Tp, class _Hash, class _Equal, class _Alloc>
758class __hash_table
759{
760public:
761 typedef _Tp value_type;
762 typedef _Hash hasher;
763 typedef _Equal key_equal;
764 typedef _Alloc allocator_type;
765
766private:
767 typedef allocator_traits<allocator_type> __alloc_traits;
768public:
769 typedef value_type& reference;
770 typedef const value_type& const_reference;
771 typedef typename __alloc_traits::pointer pointer;
772 typedef typename __alloc_traits::const_pointer const_pointer;
773 typedef typename __alloc_traits::size_type size_type;
774 typedef typename __alloc_traits::difference_type difference_type;
775public:
776 // Create __node
777 typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node;
Marshall Clow66302c62015-04-07 05:21:38 +0000778 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000779 typedef allocator_traits<__node_allocator> __node_traits;
780 typedef typename __node_traits::pointer __node_pointer;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000781 typedef typename __node_traits::pointer __node_const_pointer;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000782 typedef __hash_node_base<__node_pointer> __first_node;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000783 typedef typename pointer_traits<__node_pointer>::template
784#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
785 rebind<__first_node>
786#else
787 rebind<__first_node>::other
788#endif
789 __node_base_pointer;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000790
791private:
792
Marshall Clow66302c62015-04-07 05:21:38 +0000793 typedef typename __rebind_alloc_helper<__node_traits, __node_pointer>::type __pointer_allocator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000794 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
795 typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list;
796 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;
797 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
798
799 // --- Member data begin ---
800 __bucket_list __bucket_list_;
801 __compressed_pair<__first_node, __node_allocator> __p1_;
802 __compressed_pair<size_type, hasher> __p2_;
803 __compressed_pair<float, key_equal> __p3_;
804 // --- Member data end ---
805
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000806 _LIBCPP_INLINE_VISIBILITY
807 size_type& size() _NOEXCEPT {return __p2_.first();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000808public:
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000809 _LIBCPP_INLINE_VISIBILITY
810 size_type size() const _NOEXCEPT {return __p2_.first();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000811
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000812 _LIBCPP_INLINE_VISIBILITY
813 hasher& hash_function() _NOEXCEPT {return __p2_.second();}
814 _LIBCPP_INLINE_VISIBILITY
815 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000816
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000817 _LIBCPP_INLINE_VISIBILITY
818 float& max_load_factor() _NOEXCEPT {return __p3_.first();}
819 _LIBCPP_INLINE_VISIBILITY
820 float max_load_factor() const _NOEXCEPT {return __p3_.first();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000821
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000822 _LIBCPP_INLINE_VISIBILITY
823 key_equal& key_eq() _NOEXCEPT {return __p3_.second();}
824 _LIBCPP_INLINE_VISIBILITY
825 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000826
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000827 _LIBCPP_INLINE_VISIBILITY
828 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();}
829 _LIBCPP_INLINE_VISIBILITY
830 const __node_allocator& __node_alloc() const _NOEXCEPT
831 {return __p1_.second();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000832
833public:
834 typedef __hash_iterator<__node_pointer> iterator;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000835 typedef __hash_const_iterator<__node_pointer> const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000836 typedef __hash_local_iterator<__node_pointer> local_iterator;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000837 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000838
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000839 __hash_table()
840 _NOEXCEPT_(
841 is_nothrow_default_constructible<__bucket_list>::value &&
842 is_nothrow_default_constructible<__first_node>::value &&
843 is_nothrow_default_constructible<__node_allocator>::value &&
844 is_nothrow_default_constructible<hasher>::value &&
845 is_nothrow_default_constructible<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000846 __hash_table(const hasher& __hf, const key_equal& __eql);
847 __hash_table(const hasher& __hf, const key_equal& __eql,
848 const allocator_type& __a);
849 explicit __hash_table(const allocator_type& __a);
850 __hash_table(const __hash_table& __u);
851 __hash_table(const __hash_table& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000852#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000853 __hash_table(__hash_table&& __u)
854 _NOEXCEPT_(
855 is_nothrow_move_constructible<__bucket_list>::value &&
856 is_nothrow_move_constructible<__first_node>::value &&
857 is_nothrow_move_constructible<__node_allocator>::value &&
858 is_nothrow_move_constructible<hasher>::value &&
859 is_nothrow_move_constructible<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000860 __hash_table(__hash_table&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000861#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000862 ~__hash_table();
863
864 __hash_table& operator=(const __hash_table& __u);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000865#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000866 __hash_table& operator=(__hash_table&& __u)
867 _NOEXCEPT_(
868 __node_traits::propagate_on_container_move_assignment::value &&
869 is_nothrow_move_assignable<__node_allocator>::value &&
870 is_nothrow_move_assignable<hasher>::value &&
871 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000872#endif
873 template <class _InputIterator>
874 void __assign_unique(_InputIterator __first, _InputIterator __last);
875 template <class _InputIterator>
876 void __assign_multi(_InputIterator __first, _InputIterator __last);
877
Howard Hinnant99acc502010-09-21 17:32:39 +0000878 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000879 size_type max_size() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000880 {
881 return allocator_traits<__pointer_allocator>::max_size(
882 __bucket_list_.get_deleter().__alloc());
883 }
884
885 pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
886 iterator __node_insert_multi(__node_pointer __nd);
887 iterator __node_insert_multi(const_iterator __p,
888 __node_pointer __nd);
889
Howard Hinnant73d21a42010-09-04 23:28:19 +0000890#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000891 template <class... _Args>
892 pair<iterator, bool> __emplace_unique(_Args&&... __args);
893 template <class... _Args>
894 iterator __emplace_multi(_Args&&... __args);
895 template <class... _Args>
896 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000897#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000898
899 pair<iterator, bool> __insert_unique(const value_type& __x);
900
Howard Hinnant73d21a42010-09-04 23:28:19 +0000901#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000902 template <class _Pp>
903 pair<iterator, bool> __insert_unique(_Pp&& __x);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000904#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000905
Howard Hinnant73d21a42010-09-04 23:28:19 +0000906#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000907 template <class _Pp>
908 iterator __insert_multi(_Pp&& __x);
909 template <class _Pp>
910 iterator __insert_multi(const_iterator __p, _Pp&& __x);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000911#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000912 iterator __insert_multi(const value_type& __x);
913 iterator __insert_multi(const_iterator __p, const value_type& __x);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000914#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000915
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000916 void clear() _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000917 void rehash(size_type __n);
Howard Hinnant99acc502010-09-21 17:32:39 +0000918 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000919 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
Howard Hinnant99acc502010-09-21 17:32:39 +0000920
921 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000922 size_type bucket_count() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000923 {
924 return __bucket_list_.get_deleter().size();
925 }
926
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000927 iterator begin() _NOEXCEPT;
928 iterator end() _NOEXCEPT;
929 const_iterator begin() const _NOEXCEPT;
930 const_iterator end() const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000931
932 template <class _Key>
Howard Hinnant99acc502010-09-21 17:32:39 +0000933 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000934 size_type bucket(const _Key& __k) const
Howard Hinnant0bb0a7c2013-07-29 19:05:47 +0000935 {
936 _LIBCPP_ASSERT(bucket_count() > 0,
937 "unordered container::bucket(key) called when bucket_count() == 0");
938 return __constrain_hash(hash_function()(__k), bucket_count());
939 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000940
941 template <class _Key>
942 iterator find(const _Key& __x);
943 template <class _Key>
944 const_iterator find(const _Key& __x) const;
945
Howard Hinnant99968442011-11-29 18:15:50 +0000946 typedef __hash_node_destructor<__node_allocator> _Dp;
947 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000948
949 iterator erase(const_iterator __p);
950 iterator erase(const_iterator __first, const_iterator __last);
951 template <class _Key>
952 size_type __erase_unique(const _Key& __k);
953 template <class _Key>
954 size_type __erase_multi(const _Key& __k);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000955 __node_holder remove(const_iterator __p) _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000956
957 template <class _Key>
958 size_type __count_unique(const _Key& __k) const;
959 template <class _Key>
960 size_type __count_multi(const _Key& __k) const;
961
962 template <class _Key>
963 pair<iterator, iterator>
964 __equal_range_unique(const _Key& __k);
965 template <class _Key>
966 pair<const_iterator, const_iterator>
967 __equal_range_unique(const _Key& __k) const;
968
969 template <class _Key>
970 pair<iterator, iterator>
971 __equal_range_multi(const _Key& __k);
972 template <class _Key>
973 pair<const_iterator, const_iterator>
974 __equal_range_multi(const _Key& __k) const;
975
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000976 void swap(__hash_table& __u)
977 _NOEXCEPT_(
978 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
979 __is_nothrow_swappable<__pointer_allocator>::value) &&
980 (!__node_traits::propagate_on_container_swap::value ||
981 __is_nothrow_swappable<__node_allocator>::value) &&
982 __is_nothrow_swappable<hasher>::value &&
983 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000984
Howard Hinnant99acc502010-09-21 17:32:39 +0000985 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000986 size_type max_bucket_count() const _NOEXCEPT
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000987 {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000988 size_type bucket_size(size_type __n) const;
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000989 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000990 {
991 size_type __bc = bucket_count();
992 return __bc != 0 ? (float)size() / __bc : 0.f;
993 }
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000994 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
Howard Hinnant0bb0a7c2013-07-29 19:05:47 +0000995 {
996 _LIBCPP_ASSERT(__mlf > 0,
997 "unordered container::max_load_factor(lf) called with lf <= 0");
998 max_load_factor() = _VSTD::max(__mlf, load_factor());
999 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001000
Howard Hinnant39213642013-07-23 22:01:58 +00001001 _LIBCPP_INLINE_VISIBILITY
1002 local_iterator
1003 begin(size_type __n)
1004 {
Howard Hinnant0bb0a7c2013-07-29 19:05:47 +00001005 _LIBCPP_ASSERT(__n < bucket_count(),
1006 "unordered container::begin(n) called with n >= bucket_count()");
Howard Hinnant39213642013-07-23 22:01:58 +00001007#if _LIBCPP_DEBUG_LEVEL >= 2
1008 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1009#else
1010 return local_iterator(__bucket_list_[__n], __n, bucket_count());
1011#endif
1012 }
1013
1014 _LIBCPP_INLINE_VISIBILITY
1015 local_iterator
1016 end(size_type __n)
1017 {
Howard Hinnant0bb0a7c2013-07-29 19:05:47 +00001018 _LIBCPP_ASSERT(__n < bucket_count(),
1019 "unordered container::end(n) called with n >= bucket_count()");
Howard Hinnant39213642013-07-23 22:01:58 +00001020#if _LIBCPP_DEBUG_LEVEL >= 2
1021 return local_iterator(nullptr, __n, bucket_count(), this);
1022#else
1023 return local_iterator(nullptr, __n, bucket_count());
1024#endif
1025 }
1026
1027 _LIBCPP_INLINE_VISIBILITY
1028 const_local_iterator
1029 cbegin(size_type __n) const
1030 {
Howard Hinnant0bb0a7c2013-07-29 19:05:47 +00001031 _LIBCPP_ASSERT(__n < bucket_count(),
1032 "unordered container::cbegin(n) called with n >= bucket_count()");
Howard Hinnant39213642013-07-23 22:01:58 +00001033#if _LIBCPP_DEBUG_LEVEL >= 2
1034 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1035#else
1036 return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
1037#endif
1038 }
1039
1040 _LIBCPP_INLINE_VISIBILITY
1041 const_local_iterator
1042 cend(size_type __n) const
1043 {
Howard Hinnant0bb0a7c2013-07-29 19:05:47 +00001044 _LIBCPP_ASSERT(__n < bucket_count(),
1045 "unordered container::cend(n) called with n >= bucket_count()");
Howard Hinnant39213642013-07-23 22:01:58 +00001046#if _LIBCPP_DEBUG_LEVEL >= 2
1047 return const_local_iterator(nullptr, __n, bucket_count(), this);
1048#else
1049 return const_local_iterator(nullptr, __n, bucket_count());
1050#endif
1051 }
1052
1053#if _LIBCPP_DEBUG_LEVEL >= 2
1054
1055 bool __dereferenceable(const const_iterator* __i) const;
1056 bool __decrementable(const const_iterator* __i) const;
1057 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1058 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1059
1060#endif // _LIBCPP_DEBUG_LEVEL >= 2
1061
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001062private:
1063 void __rehash(size_type __n);
1064
Howard Hinnant73d21a42010-09-04 23:28:19 +00001065#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1066#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001067 template <class ..._Args>
1068 __node_holder __construct_node(_Args&& ...__args);
Howard Hinnantbfd55302010-09-04 23:46:48 +00001069#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001070 __node_holder __construct_node(value_type&& __v, size_t __hash);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001071#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001072 __node_holder __construct_node(const value_type& __v);
1073#endif
1074 __node_holder __construct_node(const value_type& __v, size_t __hash);
1075
Howard Hinnant99acc502010-09-21 17:32:39 +00001076 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001077 void __copy_assign_alloc(const __hash_table& __u)
1078 {__copy_assign_alloc(__u, integral_constant<bool,
1079 __node_traits::propagate_on_container_copy_assignment::value>());}
1080 void __copy_assign_alloc(const __hash_table& __u, true_type);
Howard Hinnant99acc502010-09-21 17:32:39 +00001081 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantec3773c2011-12-01 20:21:04 +00001082 void __copy_assign_alloc(const __hash_table&, false_type) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001083
1084 void __move_assign(__hash_table& __u, false_type);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001085 void __move_assign(__hash_table& __u, true_type)
1086 _NOEXCEPT_(
1087 is_nothrow_move_assignable<__node_allocator>::value &&
1088 is_nothrow_move_assignable<hasher>::value &&
1089 is_nothrow_move_assignable<key_equal>::value);
1090 _LIBCPP_INLINE_VISIBILITY
1091 void __move_assign_alloc(__hash_table& __u)
1092 _NOEXCEPT_(
1093 !__node_traits::propagate_on_container_move_assignment::value ||
1094 (is_nothrow_move_assignable<__pointer_allocator>::value &&
1095 is_nothrow_move_assignable<__node_allocator>::value))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001096 {__move_assign_alloc(__u, integral_constant<bool,
1097 __node_traits::propagate_on_container_move_assignment::value>());}
Howard Hinnant99acc502010-09-21 17:32:39 +00001098 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001099 void __move_assign_alloc(__hash_table& __u, true_type)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001100 _NOEXCEPT_(
1101 is_nothrow_move_assignable<__pointer_allocator>::value &&
1102 is_nothrow_move_assignable<__node_allocator>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001103 {
1104 __bucket_list_.get_deleter().__alloc() =
Howard Hinnant0949eed2011-06-30 21:18:19 +00001105 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
1106 __node_alloc() = _VSTD::move(__u.__node_alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001107 }
Howard Hinnant99acc502010-09-21 17:32:39 +00001108 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001109 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001110
Howard Hinnant99968442011-11-29 18:15:50 +00001111 template <class _Ap>
Howard Hinnant99acc502010-09-21 17:32:39 +00001112 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001113 static
1114 void
Howard Hinnant99968442011-11-29 18:15:50 +00001115 __swap_alloc(_Ap& __x, _Ap& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001116 _NOEXCEPT_(
Howard Hinnant99968442011-11-29 18:15:50 +00001117 !allocator_traits<_Ap>::propagate_on_container_swap::value ||
1118 __is_nothrow_swappable<_Ap>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001119 {
1120 __swap_alloc(__x, __y,
1121 integral_constant<bool,
Howard Hinnant99968442011-11-29 18:15:50 +00001122 allocator_traits<_Ap>::propagate_on_container_swap::value
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001123 >());
1124 }
1125
Howard Hinnant99968442011-11-29 18:15:50 +00001126 template <class _Ap>
Howard Hinnant99acc502010-09-21 17:32:39 +00001127 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001128 static
1129 void
Howard Hinnant99968442011-11-29 18:15:50 +00001130 __swap_alloc(_Ap& __x, _Ap& __y, true_type)
1131 _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001132 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001133 using _VSTD::swap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001134 swap(__x, __y);
1135 }
1136
Howard Hinnant99968442011-11-29 18:15:50 +00001137 template <class _Ap>
Howard Hinnant99acc502010-09-21 17:32:39 +00001138 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001139 static
1140 void
Howard Hinnantec3773c2011-12-01 20:21:04 +00001141 __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001142
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001143 void __deallocate(__node_pointer __np) _NOEXCEPT;
1144 __node_pointer __detach() _NOEXCEPT;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001145
Howard Hinnant0f678bd2013-08-12 18:38:34 +00001146 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
1147 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001148};
1149
1150template <class _Tp, class _Hash, class _Equal, class _Alloc>
Howard Hinnant99acc502010-09-21 17:32:39 +00001151inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001152__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001153 _NOEXCEPT_(
1154 is_nothrow_default_constructible<__bucket_list>::value &&
1155 is_nothrow_default_constructible<__first_node>::value &&
1156 is_nothrow_default_constructible<hasher>::value &&
1157 is_nothrow_default_constructible<key_equal>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001158 : __p2_(0),
1159 __p3_(1.0f)
1160{
1161}
1162
1163template <class _Tp, class _Hash, class _Equal, class _Alloc>
Howard Hinnant99acc502010-09-21 17:32:39 +00001164inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001165__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1166 const key_equal& __eql)
1167 : __bucket_list_(nullptr, __bucket_list_deleter()),
1168 __p1_(),
1169 __p2_(0, __hf),
1170 __p3_(1.0f, __eql)
1171{
1172}
1173
1174template <class _Tp, class _Hash, class _Equal, class _Alloc>
1175__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1176 const key_equal& __eql,
1177 const allocator_type& __a)
1178 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1179 __p1_(__node_allocator(__a)),
1180 __p2_(0, __hf),
1181 __p3_(1.0f, __eql)
1182{
1183}
1184
1185template <class _Tp, class _Hash, class _Equal, class _Alloc>
1186__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1187 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1188 __p1_(__node_allocator(__a)),
1189 __p2_(0),
1190 __p3_(1.0f)
1191{
1192}
1193
1194template <class _Tp, class _Hash, class _Equal, class _Alloc>
1195__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
1196 : __bucket_list_(nullptr,
1197 __bucket_list_deleter(allocator_traits<__pointer_allocator>::
1198 select_on_container_copy_construction(
1199 __u.__bucket_list_.get_deleter().__alloc()), 0)),
1200 __p1_(allocator_traits<__node_allocator>::
1201 select_on_container_copy_construction(__u.__node_alloc())),
1202 __p2_(0, __u.hash_function()),
1203 __p3_(__u.__p3_)
1204{
1205}
1206
1207template <class _Tp, class _Hash, class _Equal, class _Alloc>
1208__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
1209 const allocator_type& __a)
1210 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1211 __p1_(__node_allocator(__a)),
1212 __p2_(0, __u.hash_function()),
1213 __p3_(__u.__p3_)
1214{
1215}
1216
Howard Hinnant73d21a42010-09-04 23:28:19 +00001217#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001218
1219template <class _Tp, class _Hash, class _Equal, class _Alloc>
1220__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001221 _NOEXCEPT_(
1222 is_nothrow_move_constructible<__bucket_list>::value &&
1223 is_nothrow_move_constructible<__first_node>::value &&
1224 is_nothrow_move_constructible<hasher>::value &&
1225 is_nothrow_move_constructible<key_equal>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001226 : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
1227 __p1_(_VSTD::move(__u.__p1_)),
1228 __p2_(_VSTD::move(__u.__p2_)),
1229 __p3_(_VSTD::move(__u.__p3_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001230{
1231 if (size() > 0)
1232 {
Howard Hinnant7a445152012-07-06 17:31:14 +00001233 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001234 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001235 __u.__p1_.first().__next_ = nullptr;
1236 __u.size() = 0;
1237 }
1238}
1239
1240template <class _Tp, class _Hash, class _Equal, class _Alloc>
1241__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
1242 const allocator_type& __a)
1243 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1244 __p1_(__node_allocator(__a)),
Howard Hinnant0949eed2011-06-30 21:18:19 +00001245 __p2_(0, _VSTD::move(__u.hash_function())),
1246 __p3_(_VSTD::move(__u.__p3_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001247{
1248 if (__a == allocator_type(__u.__node_alloc()))
1249 {
1250 __bucket_list_.reset(__u.__bucket_list_.release());
1251 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1252 __u.__bucket_list_.get_deleter().size() = 0;
1253 if (__u.size() > 0)
1254 {
1255 __p1_.first().__next_ = __u.__p1_.first().__next_;
1256 __u.__p1_.first().__next_ = nullptr;
Howard Hinnant7a445152012-07-06 17:31:14 +00001257 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001258 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001259 size() = __u.size();
1260 __u.size() = 0;
1261 }
1262 }
1263}
1264
Howard Hinnant73d21a42010-09-04 23:28:19 +00001265#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001266
1267template <class _Tp, class _Hash, class _Equal, class _Alloc>
1268__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
1269{
1270 __deallocate(__p1_.first().__next_);
Howard Hinnant39213642013-07-23 22:01:58 +00001271#if _LIBCPP_DEBUG_LEVEL >= 2
1272 __get_db()->__erase_c(this);
1273#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001274}
1275
1276template <class _Tp, class _Hash, class _Equal, class _Alloc>
1277void
1278__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
1279 const __hash_table& __u, true_type)
1280{
1281 if (__node_alloc() != __u.__node_alloc())
1282 {
1283 clear();
1284 __bucket_list_.reset();
1285 __bucket_list_.get_deleter().size() = 0;
1286 }
1287 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1288 __node_alloc() = __u.__node_alloc();
1289}
1290
1291template <class _Tp, class _Hash, class _Equal, class _Alloc>
1292__hash_table<_Tp, _Hash, _Equal, _Alloc>&
1293__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
1294{
1295 if (this != &__u)
1296 {
1297 __copy_assign_alloc(__u);
1298 hash_function() = __u.hash_function();
1299 key_eq() = __u.key_eq();
1300 max_load_factor() = __u.max_load_factor();
1301 __assign_multi(__u.begin(), __u.end());
1302 }
1303 return *this;
1304}
1305
1306template <class _Tp, class _Hash, class _Equal, class _Alloc>
1307void
1308__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001309 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001310{
1311 __node_allocator& __na = __node_alloc();
1312 while (__np != nullptr)
1313 {
1314 __node_pointer __next = __np->__next_;
Howard Hinnant39213642013-07-23 22:01:58 +00001315#if _LIBCPP_DEBUG_LEVEL >= 2
1316 __c_node* __c = __get_db()->__find_c_and_lock(this);
1317 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1318 {
1319 --__p;
1320 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1321 if (__i->__node_ == __np)
1322 {
1323 (*__p)->__c_ = nullptr;
1324 if (--__c->end_ != __p)
1325 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1326 }
1327 }
1328 __get_db()->unlock();
1329#endif
Howard Hinnant0949eed2011-06-30 21:18:19 +00001330 __node_traits::destroy(__na, _VSTD::addressof(__np->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001331 __node_traits::deallocate(__na, __np, 1);
1332 __np = __next;
1333 }
1334}
1335
1336template <class _Tp, class _Hash, class _Equal, class _Alloc>
1337typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001338__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001339{
1340 size_type __bc = bucket_count();
1341 for (size_type __i = 0; __i < __bc; ++__i)
1342 __bucket_list_[__i] = nullptr;
1343 size() = 0;
1344 __node_pointer __cache = __p1_.first().__next_;
1345 __p1_.first().__next_ = nullptr;
1346 return __cache;
1347}
1348
Howard Hinnant73d21a42010-09-04 23:28:19 +00001349#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001350
1351template <class _Tp, class _Hash, class _Equal, class _Alloc>
1352void
1353__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1354 __hash_table& __u, true_type)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001355 _NOEXCEPT_(
1356 is_nothrow_move_assignable<__node_allocator>::value &&
1357 is_nothrow_move_assignable<hasher>::value &&
1358 is_nothrow_move_assignable<key_equal>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001359{
1360 clear();
1361 __bucket_list_.reset(__u.__bucket_list_.release());
1362 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1363 __u.__bucket_list_.get_deleter().size() = 0;
1364 __move_assign_alloc(__u);
1365 size() = __u.size();
Howard Hinnant0949eed2011-06-30 21:18:19 +00001366 hash_function() = _VSTD::move(__u.hash_function());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001367 max_load_factor() = __u.max_load_factor();
Howard Hinnant0949eed2011-06-30 21:18:19 +00001368 key_eq() = _VSTD::move(__u.key_eq());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001369 __p1_.first().__next_ = __u.__p1_.first().__next_;
1370 if (size() > 0)
1371 {
Howard Hinnant7a445152012-07-06 17:31:14 +00001372 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001373 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001374 __u.__p1_.first().__next_ = nullptr;
1375 __u.size() = 0;
1376 }
Howard Hinnant39213642013-07-23 22:01:58 +00001377#if _LIBCPP_DEBUG_LEVEL >= 2
1378 __get_db()->swap(this, &__u);
1379#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001380}
1381
1382template <class _Tp, class _Hash, class _Equal, class _Alloc>
1383void
1384__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1385 __hash_table& __u, false_type)
1386{
1387 if (__node_alloc() == __u.__node_alloc())
1388 __move_assign(__u, true_type());
1389 else
1390 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001391 hash_function() = _VSTD::move(__u.hash_function());
1392 key_eq() = _VSTD::move(__u.key_eq());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001393 max_load_factor() = __u.max_load_factor();
1394 if (bucket_count() != 0)
1395 {
1396 __node_pointer __cache = __detach();
1397#ifndef _LIBCPP_NO_EXCEPTIONS
1398 try
1399 {
Howard Hinnant324bb032010-08-22 00:02:43 +00001400#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001401 const_iterator __i = __u.begin();
1402 while (__cache != nullptr && __u.size() != 0)
1403 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001404 __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001405 __node_pointer __next = __cache->__next_;
1406 __node_insert_multi(__cache);
1407 __cache = __next;
1408 }
1409#ifndef _LIBCPP_NO_EXCEPTIONS
1410 }
1411 catch (...)
1412 {
1413 __deallocate(__cache);
1414 throw;
1415 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001416#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001417 __deallocate(__cache);
1418 }
1419 const_iterator __i = __u.begin();
1420 while (__u.size() != 0)
1421 {
1422 __node_holder __h =
Howard Hinnant0949eed2011-06-30 21:18:19 +00001423 __construct_node(_VSTD::move(__u.remove(__i++)->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001424 __node_insert_multi(__h.get());
1425 __h.release();
1426 }
1427 }
1428}
1429
1430template <class _Tp, class _Hash, class _Equal, class _Alloc>
Howard Hinnant99acc502010-09-21 17:32:39 +00001431inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001432__hash_table<_Tp, _Hash, _Equal, _Alloc>&
1433__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001434 _NOEXCEPT_(
1435 __node_traits::propagate_on_container_move_assignment::value &&
1436 is_nothrow_move_assignable<__node_allocator>::value &&
1437 is_nothrow_move_assignable<hasher>::value &&
1438 is_nothrow_move_assignable<key_equal>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001439{
1440 __move_assign(__u, integral_constant<bool,
1441 __node_traits::propagate_on_container_move_assignment::value>());
1442 return *this;
1443}
1444
Howard Hinnant73d21a42010-09-04 23:28:19 +00001445#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001446
1447template <class _Tp, class _Hash, class _Equal, class _Alloc>
1448template <class _InputIterator>
1449void
1450__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
1451 _InputIterator __last)
1452{
1453 if (bucket_count() != 0)
1454 {
1455 __node_pointer __cache = __detach();
1456#ifndef _LIBCPP_NO_EXCEPTIONS
1457 try
1458 {
Howard Hinnant324bb032010-08-22 00:02:43 +00001459#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001460 for (; __cache != nullptr && __first != __last; ++__first)
1461 {
1462 __cache->__value_ = *__first;
1463 __node_pointer __next = __cache->__next_;
1464 __node_insert_unique(__cache);
1465 __cache = __next;
1466 }
1467#ifndef _LIBCPP_NO_EXCEPTIONS
1468 }
1469 catch (...)
1470 {
1471 __deallocate(__cache);
1472 throw;
1473 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001474#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001475 __deallocate(__cache);
1476 }
1477 for (; __first != __last; ++__first)
1478 __insert_unique(*__first);
1479}
1480
1481template <class _Tp, class _Hash, class _Equal, class _Alloc>
1482template <class _InputIterator>
1483void
1484__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
1485 _InputIterator __last)
1486{
1487 if (bucket_count() != 0)
1488 {
1489 __node_pointer __cache = __detach();
1490#ifndef _LIBCPP_NO_EXCEPTIONS
1491 try
1492 {
Howard Hinnant324bb032010-08-22 00:02:43 +00001493#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001494 for (; __cache != nullptr && __first != __last; ++__first)
1495 {
1496 __cache->__value_ = *__first;
1497 __node_pointer __next = __cache->__next_;
1498 __node_insert_multi(__cache);
1499 __cache = __next;
1500 }
1501#ifndef _LIBCPP_NO_EXCEPTIONS
1502 }
1503 catch (...)
1504 {
1505 __deallocate(__cache);
1506 throw;
1507 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001508#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001509 __deallocate(__cache);
1510 }
1511 for (; __first != __last; ++__first)
1512 __insert_multi(*__first);
1513}
1514
1515template <class _Tp, class _Hash, class _Equal, class _Alloc>
Howard Hinnant99acc502010-09-21 17:32:39 +00001516inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001517typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001518__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001519{
Howard Hinnant39213642013-07-23 22:01:58 +00001520#if _LIBCPP_DEBUG_LEVEL >= 2
1521 return iterator(__p1_.first().__next_, this);
1522#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001523 return iterator(__p1_.first().__next_);
Howard Hinnant39213642013-07-23 22:01:58 +00001524#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001525}
1526
1527template <class _Tp, class _Hash, class _Equal, class _Alloc>
Howard Hinnant99acc502010-09-21 17:32:39 +00001528inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001529typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001530__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001531{
Howard Hinnant39213642013-07-23 22:01:58 +00001532#if _LIBCPP_DEBUG_LEVEL >= 2
1533 return iterator(nullptr, this);
1534#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001535 return iterator(nullptr);
Howard Hinnant39213642013-07-23 22:01:58 +00001536#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001537}
1538
1539template <class _Tp, class _Hash, class _Equal, class _Alloc>
Howard Hinnant99acc502010-09-21 17:32:39 +00001540inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001541typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001542__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001543{
Howard Hinnant39213642013-07-23 22:01:58 +00001544#if _LIBCPP_DEBUG_LEVEL >= 2
1545 return const_iterator(__p1_.first().__next_, this);
1546#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001547 return const_iterator(__p1_.first().__next_);
Howard Hinnant39213642013-07-23 22:01:58 +00001548#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001549}
1550
1551template <class _Tp, class _Hash, class _Equal, class _Alloc>
Howard Hinnant99acc502010-09-21 17:32:39 +00001552inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001553typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001554__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001555{
Howard Hinnant39213642013-07-23 22:01:58 +00001556#if _LIBCPP_DEBUG_LEVEL >= 2
1557 return const_iterator(nullptr, this);
1558#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001559 return const_iterator(nullptr);
Howard Hinnant39213642013-07-23 22:01:58 +00001560#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001561}
1562
1563template <class _Tp, class _Hash, class _Equal, class _Alloc>
1564void
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001565__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001566{
1567 if (size() > 0)
1568 {
1569 __deallocate(__p1_.first().__next_);
1570 __p1_.first().__next_ = nullptr;
1571 size_type __bc = bucket_count();
Howard Hinnant9f66bff2011-07-05 14:14:17 +00001572 for (size_type __i = 0; __i < __bc; ++__i)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001573 __bucket_list_[__i] = nullptr;
1574 size() = 0;
1575 }
1576}
1577
1578template <class _Tp, class _Hash, class _Equal, class _Alloc>
1579pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1580__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
1581{
1582 __nd->__hash_ = hash_function()(__nd->__value_);
1583 size_type __bc = bucket_count();
1584 bool __inserted = false;
1585 __node_pointer __ndptr;
1586 size_t __chash;
1587 if (__bc != 0)
1588 {
Howard Hinnant7a445152012-07-06 17:31:14 +00001589 __chash = __constrain_hash(__nd->__hash_, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001590 __ndptr = __bucket_list_[__chash];
1591 if (__ndptr != nullptr)
1592 {
1593 for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
Howard Hinnant7a445152012-07-06 17:31:14 +00001594 __constrain_hash(__ndptr->__hash_, __bc) == __chash;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001595 __ndptr = __ndptr->__next_)
1596 {
1597 if (key_eq()(__ndptr->__value_, __nd->__value_))
1598 goto __done;
1599 }
1600 }
1601 }
1602 {
1603 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1604 {
Eric Fiselier57947ca2015-02-02 21:31:48 +00001605 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001606 size_type(ceil(float(size() + 1) / max_load_factor()))));
1607 __bc = bucket_count();
Howard Hinnant7a445152012-07-06 17:31:14 +00001608 __chash = __constrain_hash(__nd->__hash_, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001609 }
1610 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1611 __node_pointer __pn = __bucket_list_[__chash];
1612 if (__pn == nullptr)
1613 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001614 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001615 __nd->__next_ = __pn->__next_;
1616 __pn->__next_ = __nd;
1617 // fix up __bucket_list_
1618 __bucket_list_[__chash] = __pn;
1619 if (__nd->__next_ != nullptr)
Howard Hinnant7a445152012-07-06 17:31:14 +00001620 __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001621 }
1622 else
1623 {
1624 __nd->__next_ = __pn->__next_;
1625 __pn->__next_ = __nd;
1626 }
1627 __ndptr = __nd;
1628 // increment size
1629 ++size();
1630 __inserted = true;
1631 }
1632__done:
Howard Hinnant39213642013-07-23 22:01:58 +00001633#if _LIBCPP_DEBUG_LEVEL >= 2
1634 return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
1635#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001636 return pair<iterator, bool>(iterator(__ndptr), __inserted);
Howard Hinnant39213642013-07-23 22:01:58 +00001637#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001638}
1639
1640template <class _Tp, class _Hash, class _Equal, class _Alloc>
1641typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1642__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
1643{
1644 __cp->__hash_ = hash_function()(__cp->__value_);
1645 size_type __bc = bucket_count();
1646 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1647 {
Eric Fiselier57947ca2015-02-02 21:31:48 +00001648 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001649 size_type(ceil(float(size() + 1) / max_load_factor()))));
1650 __bc = bucket_count();
1651 }
Howard Hinnant7a445152012-07-06 17:31:14 +00001652 size_t __chash = __constrain_hash(__cp->__hash_, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001653 __node_pointer __pn = __bucket_list_[__chash];
1654 if (__pn == nullptr)
1655 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001656 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001657 __cp->__next_ = __pn->__next_;
1658 __pn->__next_ = __cp;
1659 // fix up __bucket_list_
1660 __bucket_list_[__chash] = __pn;
1661 if (__cp->__next_ != nullptr)
Howard Hinnant7a445152012-07-06 17:31:14 +00001662 __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001663 }
1664 else
1665 {
1666 for (bool __found = false; __pn->__next_ != nullptr &&
Howard Hinnant7a445152012-07-06 17:31:14 +00001667 __constrain_hash(__pn->__next_->__hash_, __bc) == __chash;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001668 __pn = __pn->__next_)
Howard Hinnant324bb032010-08-22 00:02:43 +00001669 {
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001670 // __found key_eq() action
1671 // false false loop
1672 // true true loop
1673 // false true set __found to true
1674 // true false break
1675 if (__found != (__pn->__next_->__hash_ == __cp->__hash_ &&
1676 key_eq()(__pn->__next_->__value_, __cp->__value_)))
1677 {
1678 if (!__found)
1679 __found = true;
1680 else
1681 break;
1682 }
1683 }
1684 __cp->__next_ = __pn->__next_;
1685 __pn->__next_ = __cp;
1686 if (__cp->__next_ != nullptr)
1687 {
Howard Hinnant7a445152012-07-06 17:31:14 +00001688 size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001689 if (__nhash != __chash)
1690 __bucket_list_[__nhash] = __cp;
1691 }
1692 }
1693 ++size();
Howard Hinnant39213642013-07-23 22:01:58 +00001694#if _LIBCPP_DEBUG_LEVEL >= 2
1695 return iterator(__cp, this);
1696#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001697 return iterator(__cp);
Howard Hinnant39213642013-07-23 22:01:58 +00001698#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001699}
1700
1701template <class _Tp, class _Hash, class _Equal, class _Alloc>
1702typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1703__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
1704 const_iterator __p, __node_pointer __cp)
1705{
Howard Hinnant824c1992013-08-02 17:50:49 +00001706#if _LIBCPP_DEBUG_LEVEL >= 2
1707 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1708 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
1709 " referring to this unordered container");
1710#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001711 if (__p != end() && key_eq()(*__p, __cp->__value_))
1712 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001713 __node_pointer __np = __p.__node_;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001714 __cp->__hash_ = __np->__hash_;
1715 size_type __bc = bucket_count();
1716 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1717 {
Eric Fiselier57947ca2015-02-02 21:31:48 +00001718 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001719 size_type(ceil(float(size() + 1) / max_load_factor()))));
1720 __bc = bucket_count();
1721 }
Howard Hinnant7a445152012-07-06 17:31:14 +00001722 size_t __chash = __constrain_hash(__cp->__hash_, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001723 __node_pointer __pp = __bucket_list_[__chash];
1724 while (__pp->__next_ != __np)
1725 __pp = __pp->__next_;
1726 __cp->__next_ = __np;
1727 __pp->__next_ = __cp;
1728 ++size();
Howard Hinnant39213642013-07-23 22:01:58 +00001729#if _LIBCPP_DEBUG_LEVEL >= 2
1730 return iterator(__cp, this);
1731#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001732 return iterator(__cp);
Howard Hinnant39213642013-07-23 22:01:58 +00001733#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001734 }
1735 return __node_insert_multi(__cp);
1736}
1737
1738template <class _Tp, class _Hash, class _Equal, class _Alloc>
1739pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1740__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x)
1741{
1742 size_t __hash = hash_function()(__x);
1743 size_type __bc = bucket_count();
1744 bool __inserted = false;
1745 __node_pointer __nd;
1746 size_t __chash;
1747 if (__bc != 0)
1748 {
Howard Hinnant7a445152012-07-06 17:31:14 +00001749 __chash = __constrain_hash(__hash, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001750 __nd = __bucket_list_[__chash];
1751 if (__nd != nullptr)
1752 {
1753 for (__nd = __nd->__next_; __nd != nullptr &&
Howard Hinnant7a445152012-07-06 17:31:14 +00001754 __constrain_hash(__nd->__hash_, __bc) == __chash;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001755 __nd = __nd->__next_)
1756 {
1757 if (key_eq()(__nd->__value_, __x))
1758 goto __done;
1759 }
1760 }
1761 }
1762 {
1763 __node_holder __h = __construct_node(__x, __hash);
1764 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1765 {
Eric Fiselier57947ca2015-02-02 21:31:48 +00001766 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001767 size_type(ceil(float(size() + 1) / max_load_factor()))));
1768 __bc = bucket_count();
Howard Hinnant7a445152012-07-06 17:31:14 +00001769 __chash = __constrain_hash(__hash, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001770 }
1771 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1772 __node_pointer __pn = __bucket_list_[__chash];
1773 if (__pn == nullptr)
1774 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001775 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001776 __h->__next_ = __pn->__next_;
1777 __pn->__next_ = __h.get();
1778 // fix up __bucket_list_
1779 __bucket_list_[__chash] = __pn;
1780 if (__h->__next_ != nullptr)
Howard Hinnant7a445152012-07-06 17:31:14 +00001781 __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001782 }
1783 else
1784 {
1785 __h->__next_ = __pn->__next_;
1786 __pn->__next_ = __h.get();
1787 }
1788 __nd = __h.release();
1789 // increment size
1790 ++size();
1791 __inserted = true;
1792 }
1793__done:
Howard Hinnant39213642013-07-23 22:01:58 +00001794#if _LIBCPP_DEBUG_LEVEL >= 2
1795 return pair<iterator, bool>(iterator(__nd, this), __inserted);
1796#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001797 return pair<iterator, bool>(iterator(__nd), __inserted);
Howard Hinnant39213642013-07-23 22:01:58 +00001798#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001799}
1800
Howard Hinnant73d21a42010-09-04 23:28:19 +00001801#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1802#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001803
1804template <class _Tp, class _Hash, class _Equal, class _Alloc>
1805template <class... _Args>
1806pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1807__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args)
1808{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001809 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001810 pair<iterator, bool> __r = __node_insert_unique(__h.get());
1811 if (__r.second)
1812 __h.release();
1813 return __r;
1814}
1815
1816template <class _Tp, class _Hash, class _Equal, class _Alloc>
1817template <class... _Args>
1818typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1819__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
1820{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001821 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001822 iterator __r = __node_insert_multi(__h.get());
1823 __h.release();
1824 return __r;
1825}
1826
1827template <class _Tp, class _Hash, class _Equal, class _Alloc>
1828template <class... _Args>
1829typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1830__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
1831 const_iterator __p, _Args&&... __args)
1832{
Howard Hinnant0bb0a7c2013-07-29 19:05:47 +00001833#if _LIBCPP_DEBUG_LEVEL >= 2
1834 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1835 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
1836 " referring to this unordered container");
1837#endif
Howard Hinnant0949eed2011-06-30 21:18:19 +00001838 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001839 iterator __r = __node_insert_multi(__p, __h.get());
1840 __h.release();
1841 return __r;
1842}
1843
Howard Hinnant73d21a42010-09-04 23:28:19 +00001844#endif // _LIBCPP_HAS_NO_VARIADICS
1845
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001846template <class _Tp, class _Hash, class _Equal, class _Alloc>
Howard Hinnant99968442011-11-29 18:15:50 +00001847template <class _Pp>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001848pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
Howard Hinnant99968442011-11-29 18:15:50 +00001849__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001850{
Howard Hinnant99968442011-11-29 18:15:50 +00001851 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001852 pair<iterator, bool> __r = __node_insert_unique(__h.get());
1853 if (__r.second)
1854 __h.release();
1855 return __r;
1856}
1857
Howard Hinnant73d21a42010-09-04 23:28:19 +00001858#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001859
Howard Hinnant73d21a42010-09-04 23:28:19 +00001860#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001861
1862template <class _Tp, class _Hash, class _Equal, class _Alloc>
Howard Hinnant99968442011-11-29 18:15:50 +00001863template <class _Pp>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001864typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
Howard Hinnant99968442011-11-29 18:15:50 +00001865__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001866{
Howard Hinnant99968442011-11-29 18:15:50 +00001867 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001868 iterator __r = __node_insert_multi(__h.get());
1869 __h.release();
1870 return __r;
1871}
1872
1873template <class _Tp, class _Hash, class _Equal, class _Alloc>
Howard Hinnant99968442011-11-29 18:15:50 +00001874template <class _Pp>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001875typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1876__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
Howard Hinnant99968442011-11-29 18:15:50 +00001877 _Pp&& __x)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001878{
Howard Hinnant0bb0a7c2013-07-29 19:05:47 +00001879#if _LIBCPP_DEBUG_LEVEL >= 2
1880 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1881 "unordered container::insert(const_iterator, rvalue) called with an iterator not"
1882 " referring to this unordered container");
1883#endif
Howard Hinnant99968442011-11-29 18:15:50 +00001884 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001885 iterator __r = __node_insert_multi(__p, __h.get());
1886 __h.release();
1887 return __r;
1888}
1889
Howard Hinnant73d21a42010-09-04 23:28:19 +00001890#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001891
1892template <class _Tp, class _Hash, class _Equal, class _Alloc>
1893typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1894__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x)
1895{
1896 __node_holder __h = __construct_node(__x);
1897 iterator __r = __node_insert_multi(__h.get());
1898 __h.release();
1899 return __r;
1900}
1901
1902template <class _Tp, class _Hash, class _Equal, class _Alloc>
1903typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1904__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
1905 const value_type& __x)
1906{
Howard Hinnant0bb0a7c2013-07-29 19:05:47 +00001907#if _LIBCPP_DEBUG_LEVEL >= 2
1908 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1909 "unordered container::insert(const_iterator, lvalue) called with an iterator not"
1910 " referring to this unordered container");
1911#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001912 __node_holder __h = __construct_node(__x);
1913 iterator __r = __node_insert_multi(__p, __h.get());
1914 __h.release();
1915 return __r;
1916}
1917
Howard Hinnant73d21a42010-09-04 23:28:19 +00001918#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001919
1920template <class _Tp, class _Hash, class _Equal, class _Alloc>
1921void
1922__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
1923{
Howard Hinnant7a445152012-07-06 17:31:14 +00001924 if (__n == 1)
1925 __n = 2;
1926 else if (__n & (__n - 1))
1927 __n = __next_prime(__n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001928 size_type __bc = bucket_count();
1929 if (__n > __bc)
1930 __rehash(__n);
Howard Hinnant7a445152012-07-06 17:31:14 +00001931 else if (__n < __bc)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001932 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001933 __n = _VSTD::max<size_type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001934 (
1935 __n,
Eric Fiselier57947ca2015-02-02 21:31:48 +00001936 __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
1937 __next_prime(size_t(ceil(float(size()) / max_load_factor())))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001938 );
1939 if (__n < __bc)
1940 __rehash(__n);
1941 }
1942}
1943
1944template <class _Tp, class _Hash, class _Equal, class _Alloc>
1945void
1946__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
1947{
Howard Hinnant39213642013-07-23 22:01:58 +00001948#if _LIBCPP_DEBUG_LEVEL >= 2
1949 __get_db()->__invalidate_all(this);
1950#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001951 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
1952 __bucket_list_.reset(__nbc > 0 ?
1953 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
1954 __bucket_list_.get_deleter().size() = __nbc;
1955 if (__nbc > 0)
1956 {
1957 for (size_type __i = 0; __i < __nbc; ++__i)
1958 __bucket_list_[__i] = nullptr;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001959 __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001960 __node_pointer __cp = __pp->__next_;
1961 if (__cp != nullptr)
1962 {
Howard Hinnant7a445152012-07-06 17:31:14 +00001963 size_type __chash = __constrain_hash(__cp->__hash_, __nbc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001964 __bucket_list_[__chash] = __pp;
1965 size_type __phash = __chash;
1966 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr;
1967 __cp = __pp->__next_)
1968 {
Howard Hinnant7a445152012-07-06 17:31:14 +00001969 __chash = __constrain_hash(__cp->__hash_, __nbc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001970 if (__chash == __phash)
1971 __pp = __cp;
1972 else
1973 {
1974 if (__bucket_list_[__chash] == nullptr)
1975 {
1976 __bucket_list_[__chash] = __pp;
1977 __pp = __cp;
1978 __phash = __chash;
1979 }
1980 else
1981 {
1982 __node_pointer __np = __cp;
1983 for (; __np->__next_ != nullptr &&
1984 key_eq()(__cp->__value_, __np->__next_->__value_);
1985 __np = __np->__next_)
1986 ;
1987 __pp->__next_ = __np->__next_;
1988 __np->__next_ = __bucket_list_[__chash]->__next_;
1989 __bucket_list_[__chash]->__next_ = __cp;
Howard Hinnant324bb032010-08-22 00:02:43 +00001990
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001991 }
1992 }
1993 }
1994 }
1995 }
1996}
1997
1998template <class _Tp, class _Hash, class _Equal, class _Alloc>
1999template <class _Key>
2000typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2001__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
2002{
2003 size_t __hash = hash_function()(__k);
2004 size_type __bc = bucket_count();
2005 if (__bc != 0)
2006 {
Howard Hinnant7a445152012-07-06 17:31:14 +00002007 size_t __chash = __constrain_hash(__hash, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002008 __node_pointer __nd = __bucket_list_[__chash];
2009 if (__nd != nullptr)
2010 {
2011 for (__nd = __nd->__next_; __nd != nullptr &&
Howard Hinnant7a445152012-07-06 17:31:14 +00002012 __constrain_hash(__nd->__hash_, __bc) == __chash;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002013 __nd = __nd->__next_)
2014 {
2015 if (key_eq()(__nd->__value_, __k))
Howard Hinnant39213642013-07-23 22:01:58 +00002016#if _LIBCPP_DEBUG_LEVEL >= 2
2017 return iterator(__nd, this);
2018#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002019 return iterator(__nd);
Howard Hinnant39213642013-07-23 22:01:58 +00002020#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002021 }
2022 }
2023 }
2024 return end();
2025}
2026
2027template <class _Tp, class _Hash, class _Equal, class _Alloc>
2028template <class _Key>
2029typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
2030__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
2031{
2032 size_t __hash = hash_function()(__k);
2033 size_type __bc = bucket_count();
2034 if (__bc != 0)
2035 {
Howard Hinnant7a445152012-07-06 17:31:14 +00002036 size_t __chash = __constrain_hash(__hash, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002037 __node_const_pointer __nd = __bucket_list_[__chash];
2038 if (__nd != nullptr)
2039 {
2040 for (__nd = __nd->__next_; __nd != nullptr &&
Howard Hinnant7a445152012-07-06 17:31:14 +00002041 __constrain_hash(__nd->__hash_, __bc) == __chash;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002042 __nd = __nd->__next_)
2043 {
2044 if (key_eq()(__nd->__value_, __k))
Howard Hinnant39213642013-07-23 22:01:58 +00002045#if _LIBCPP_DEBUG_LEVEL >= 2
2046 return const_iterator(__nd, this);
2047#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002048 return const_iterator(__nd);
Howard Hinnant39213642013-07-23 22:01:58 +00002049#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002050 }
2051 }
Howard Hinnant324bb032010-08-22 00:02:43 +00002052
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002053 }
2054 return end();
2055}
2056
Howard Hinnant73d21a42010-09-04 23:28:19 +00002057#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2058#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002059
2060template <class _Tp, class _Hash, class _Equal, class _Alloc>
2061template <class ..._Args>
2062typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2063__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
2064{
2065 __node_allocator& __na = __node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00002066 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00002067 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002068 __h.get_deleter().__value_constructed = true;
2069 __h->__hash_ = hash_function()(__h->__value_);
2070 __h->__next_ = nullptr;
2071 return __h;
2072}
2073
Howard Hinnant73d21a42010-09-04 23:28:19 +00002074#endif // _LIBCPP_HAS_NO_VARIADICS
2075
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002076template <class _Tp, class _Hash, class _Equal, class _Alloc>
2077typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2078__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v,
2079 size_t __hash)
2080{
2081 __node_allocator& __na = __node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00002082 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00002083 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002084 __h.get_deleter().__value_constructed = true;
2085 __h->__hash_ = __hash;
2086 __h->__next_ = nullptr;
Howard Hinnant9a894d92013-08-22 18:29:50 +00002087 return __h;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002088}
2089
Howard Hinnant73d21a42010-09-04 23:28:19 +00002090#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002091
2092template <class _Tp, class _Hash, class _Equal, class _Alloc>
2093typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2094__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v)
2095{
2096 __node_allocator& __na = __node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00002097 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00002098 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002099 __h.get_deleter().__value_constructed = true;
2100 __h->__hash_ = hash_function()(__h->__value_);
2101 __h->__next_ = nullptr;
Howard Hinnant9a894d92013-08-22 18:29:50 +00002102 return _VSTD::move(__h); // explicitly moved for C++03
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002103}
2104
Howard Hinnant73d21a42010-09-04 23:28:19 +00002105#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002106
2107template <class _Tp, class _Hash, class _Equal, class _Alloc>
2108typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2109__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v,
2110 size_t __hash)
2111{
2112 __node_allocator& __na = __node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00002113 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00002114 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002115 __h.get_deleter().__value_constructed = true;
2116 __h->__hash_ = __hash;
2117 __h->__next_ = nullptr;
Howard Hinnant9a894d92013-08-22 18:29:50 +00002118 return _VSTD::move(__h); // explicitly moved for C++03
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002119}
2120
2121template <class _Tp, class _Hash, class _Equal, class _Alloc>
2122typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2123__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
2124{
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00002125 __node_pointer __np = __p.__node_;
Howard Hinnant39213642013-07-23 22:01:58 +00002126#if _LIBCPP_DEBUG_LEVEL >= 2
2127 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2128 "unordered container erase(iterator) called with an iterator not"
2129 " referring to this container");
2130 _LIBCPP_ASSERT(__p != end(),
2131 "unordered container erase(iterator) called with a non-dereferenceable iterator");
2132 iterator __r(__np, this);
2133#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002134 iterator __r(__np);
Howard Hinnant39213642013-07-23 22:01:58 +00002135#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002136 ++__r;
2137 remove(__p);
2138 return __r;
2139}
2140
2141template <class _Tp, class _Hash, class _Equal, class _Alloc>
2142typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2143__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
2144 const_iterator __last)
2145{
Howard Hinnant39213642013-07-23 22:01:58 +00002146#if _LIBCPP_DEBUG_LEVEL >= 2
2147 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
2148 "unodered container::erase(iterator, iterator) called with an iterator not"
2149 " referring to this unodered container");
2150 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
2151 "unodered container::erase(iterator, iterator) called with an iterator not"
2152 " referring to this unodered container");
2153#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002154 for (const_iterator __p = __first; __first != __last; __p = __first)
2155 {
2156 ++__first;
2157 erase(__p);
2158 }
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00002159 __node_pointer __np = __last.__node_;
Howard Hinnant39213642013-07-23 22:01:58 +00002160#if _LIBCPP_DEBUG_LEVEL >= 2
2161 return iterator (__np, this);
2162#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002163 return iterator (__np);
Howard Hinnant39213642013-07-23 22:01:58 +00002164#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002165}
2166
2167template <class _Tp, class _Hash, class _Equal, class _Alloc>
2168template <class _Key>
2169typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2170__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
2171{
2172 iterator __i = find(__k);
2173 if (__i == end())
2174 return 0;
2175 erase(__i);
2176 return 1;
2177}
2178
2179template <class _Tp, class _Hash, class _Equal, class _Alloc>
2180template <class _Key>
2181typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2182__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
2183{
2184 size_type __r = 0;
2185 iterator __i = find(__k);
2186 if (__i != end())
2187 {
2188 iterator __e = end();
2189 do
2190 {
2191 erase(__i++);
2192 ++__r;
2193 } while (__i != __e && key_eq()(*__i, __k));
2194 }
2195 return __r;
2196}
2197
2198template <class _Tp, class _Hash, class _Equal, class _Alloc>
2199typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00002200__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002201{
2202 // current node
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00002203 __node_pointer __cn = __p.__node_;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002204 size_type __bc = bucket_count();
Howard Hinnant7a445152012-07-06 17:31:14 +00002205 size_t __chash = __constrain_hash(__cn->__hash_, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002206 // find previous node
2207 __node_pointer __pn = __bucket_list_[__chash];
2208 for (; __pn->__next_ != __cn; __pn = __pn->__next_)
2209 ;
2210 // Fix up __bucket_list_
2211 // if __pn is not in same bucket (before begin is not in same bucket) &&
2212 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00002213 if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))
2214 || __constrain_hash(__pn->__hash_, __bc) != __chash)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002215 {
Howard Hinnant7a445152012-07-06 17:31:14 +00002216 if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002217 __bucket_list_[__chash] = nullptr;
2218 }
2219 // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
2220 if (__cn->__next_ != nullptr)
2221 {
Howard Hinnant7a445152012-07-06 17:31:14 +00002222 size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002223 if (__nhash != __chash)
2224 __bucket_list_[__nhash] = __pn;
2225 }
2226 // remove __cn
2227 __pn->__next_ = __cn->__next_;
2228 __cn->__next_ = nullptr;
2229 --size();
Howard Hinnant39213642013-07-23 22:01:58 +00002230#if _LIBCPP_DEBUG_LEVEL >= 2
2231 __c_node* __c = __get_db()->__find_c_and_lock(this);
2232 for (__i_node** __p = __c->end_; __p != __c->beg_; )
2233 {
2234 --__p;
2235 iterator* __i = static_cast<iterator*>((*__p)->__i_);
2236 if (__i->__node_ == __cn)
2237 {
2238 (*__p)->__c_ = nullptr;
2239 if (--__c->end_ != __p)
2240 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
2241 }
2242 }
2243 __get_db()->unlock();
2244#endif
Howard Hinnant99968442011-11-29 18:15:50 +00002245 return __node_holder(__cn, _Dp(__node_alloc(), true));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002246}
2247
2248template <class _Tp, class _Hash, class _Equal, class _Alloc>
2249template <class _Key>
Howard Hinnant99acc502010-09-21 17:32:39 +00002250inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002251typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2252__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
2253{
2254 return static_cast<size_type>(find(__k) != end());
2255}
2256
2257template <class _Tp, class _Hash, class _Equal, class _Alloc>
2258template <class _Key>
2259typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2260__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
2261{
2262 size_type __r = 0;
2263 const_iterator __i = find(__k);
2264 if (__i != end())
2265 {
2266 const_iterator __e = end();
2267 do
2268 {
2269 ++__i;
2270 ++__r;
2271 } while (__i != __e && key_eq()(*__i, __k));
2272 }
2273 return __r;
2274}
2275
2276template <class _Tp, class _Hash, class _Equal, class _Alloc>
2277template <class _Key>
2278pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2279 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2280__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2281 const _Key& __k)
2282{
2283 iterator __i = find(__k);
2284 iterator __j = __i;
2285 if (__i != end())
2286 ++__j;
2287 return pair<iterator, iterator>(__i, __j);
2288}
2289
2290template <class _Tp, class _Hash, class _Equal, class _Alloc>
2291template <class _Key>
2292pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2293 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2294__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2295 const _Key& __k) const
2296{
2297 const_iterator __i = find(__k);
2298 const_iterator __j = __i;
2299 if (__i != end())
2300 ++__j;
2301 return pair<const_iterator, const_iterator>(__i, __j);
2302}
2303
2304template <class _Tp, class _Hash, class _Equal, class _Alloc>
2305template <class _Key>
2306pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2307 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2308__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2309 const _Key& __k)
2310{
2311 iterator __i = find(__k);
2312 iterator __j = __i;
2313 if (__i != end())
2314 {
2315 iterator __e = end();
2316 do
2317 {
2318 ++__j;
2319 } while (__j != __e && key_eq()(*__j, __k));
2320 }
2321 return pair<iterator, iterator>(__i, __j);
2322}
2323
2324template <class _Tp, class _Hash, class _Equal, class _Alloc>
2325template <class _Key>
2326pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2327 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2328__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2329 const _Key& __k) const
2330{
2331 const_iterator __i = find(__k);
2332 const_iterator __j = __i;
2333 if (__i != end())
2334 {
2335 const_iterator __e = end();
2336 do
2337 {
2338 ++__j;
2339 } while (__j != __e && key_eq()(*__j, __k));
2340 }
2341 return pair<const_iterator, const_iterator>(__i, __j);
2342}
2343
2344template <class _Tp, class _Hash, class _Equal, class _Alloc>
2345void
2346__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00002347 _NOEXCEPT_(
2348 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
2349 __is_nothrow_swappable<__pointer_allocator>::value) &&
2350 (!__node_traits::propagate_on_container_swap::value ||
2351 __is_nothrow_swappable<__node_allocator>::value) &&
2352 __is_nothrow_swappable<hasher>::value &&
2353 __is_nothrow_swappable<key_equal>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002354{
2355 {
2356 __node_pointer_pointer __npp = __bucket_list_.release();
2357 __bucket_list_.reset(__u.__bucket_list_.release());
2358 __u.__bucket_list_.reset(__npp);
2359 }
Howard Hinnant0949eed2011-06-30 21:18:19 +00002360 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002361 __swap_alloc(__bucket_list_.get_deleter().__alloc(),
2362 __u.__bucket_list_.get_deleter().__alloc());
2363 __swap_alloc(__node_alloc(), __u.__node_alloc());
Howard Hinnant0949eed2011-06-30 21:18:19 +00002364 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002365 __p2_.swap(__u.__p2_);
2366 __p3_.swap(__u.__p3_);
2367 if (size() > 0)
Howard Hinnant7a445152012-07-06 17:31:14 +00002368 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00002369 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002370 if (__u.size() > 0)
Howard Hinnant7a445152012-07-06 17:31:14 +00002371 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] =
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00002372 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first()));
Howard Hinnant39213642013-07-23 22:01:58 +00002373#if _LIBCPP_DEBUG_LEVEL >= 2
2374 __get_db()->swap(this, &__u);
2375#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002376}
2377
2378template <class _Tp, class _Hash, class _Equal, class _Alloc>
2379typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2380__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
2381{
Howard Hinnant0bb0a7c2013-07-29 19:05:47 +00002382 _LIBCPP_ASSERT(__n < bucket_count(),
2383 "unordered container::bucket_size(n) called with n >= bucket_count()");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002384 __node_const_pointer __np = __bucket_list_[__n];
2385 size_type __bc = bucket_count();
2386 size_type __r = 0;
2387 if (__np != nullptr)
2388 {
2389 for (__np = __np->__next_; __np != nullptr &&
Howard Hinnant7a445152012-07-06 17:31:14 +00002390 __constrain_hash(__np->__hash_, __bc) == __n;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002391 __np = __np->__next_, ++__r)
2392 ;
2393 }
2394 return __r;
2395}
2396
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00002397template <class _Tp, class _Hash, class _Equal, class _Alloc>
2398inline _LIBCPP_INLINE_VISIBILITY
2399void
2400swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
2401 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2402 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2403{
2404 __x.swap(__y);
2405}
2406
Howard Hinnant39213642013-07-23 22:01:58 +00002407#if _LIBCPP_DEBUG_LEVEL >= 2
2408
2409template <class _Tp, class _Hash, class _Equal, class _Alloc>
2410bool
2411__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const
2412{
2413 return __i->__node_ != nullptr;
2414}
2415
2416template <class _Tp, class _Hash, class _Equal, class _Alloc>
2417bool
2418__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const
2419{
2420 return false;
2421}
2422
2423template <class _Tp, class _Hash, class _Equal, class _Alloc>
2424bool
2425__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
2426{
2427 return false;
2428}
2429
2430template <class _Tp, class _Hash, class _Equal, class _Alloc>
2431bool
2432__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
2433{
2434 return false;
2435}
2436
2437#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002438_LIBCPP_END_NAMESPACE_STD
2439
2440#endif // _LIBCPP__HASH_TABLE