blob: 6d6a6a1aa3379f04ff377b895308d4768dff3f20 [file] [log] [blame]
Howard Hinnant3e519522010-05-11 19:42:16 +00001// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
Howard Hinnant5b08a8a2010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnant3e519522010-05-11 19:42:16 +00005//
Howard Hinnant412dbeb2010-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 Hinnant3e519522010-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>
Eric Fiselier75d0dcf2016-02-10 20:46:23 +000020#include <utility>
Eric Fiselier04333f92017-01-13 22:42:53 +000021#include <type_traits>
Howard Hinnant3e519522010-05-11 19:42:16 +000022
Howard Hinnantab4f4382011-11-29 16:45:27 +000023#include <__undef_min_max>
24
Eric Fiselierc1bd9192014-08-10 23:53:08 +000025#include <__debug>
Howard Hinnant42a30462013-08-02 00:26:35 +000026
Howard Hinnant073458b2011-10-17 20:05:10 +000027#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnant3e519522010-05-11 19:42:16 +000028#pragma GCC system_header
Howard Hinnant073458b2011-10-17 20:05:10 +000029#endif
Howard Hinnant3e519522010-05-11 19:42:16 +000030
31_LIBCPP_BEGIN_NAMESPACE_STD
32
Eric Fiselierfcd02212016-02-11 11:59:44 +000033
34#ifndef _LIBCPP_CXX03_LANG
35template <class _Key, class _Tp>
36union __hash_value_type;
37#else
38template <class _Key, class _Tp>
39struct __hash_value_type;
40#endif
41
Eric Fiselier04333f92017-01-13 22:42:53 +000042template <class _Key, class _Cp, class _Hash,
43 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
44class __unordered_map_hasher;
45
46template <class _Key, class _Cp, class _Pred,
47 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value
48 >
49class __unordered_map_equal;
50
Eric Fiselierfcd02212016-02-11 11:59:44 +000051#ifndef _LIBCPP_CXX03_LANG
52template <class _Tp>
53struct __is_hash_value_type_imp : false_type {};
54
55template <class _Key, class _Value>
56struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value>> : true_type {};
57
58template <class ..._Args>
59struct __is_hash_value_type : false_type {};
60
61template <class _One>
62struct __is_hash_value_type<_One> : __is_hash_value_type_imp<typename __uncvref<_One>::type> {};
63#endif
64
Howard Hinnant6e412562013-03-06 23:30:19 +000065_LIBCPP_FUNC_VIS
Howard Hinnantce534202011-06-14 19:58:17 +000066size_t __next_prime(size_t __n);
Howard Hinnant3e519522010-05-11 19:42:16 +000067
68template <class _NodePtr>
69struct __hash_node_base
70{
Eric Fiselier40492ba2016-07-23 20:36:55 +000071 typedef typename pointer_traits<_NodePtr>::element_type __node_type;
Howard Hinnant3e519522010-05-11 19:42:16 +000072 typedef __hash_node_base __first_node;
Eric Fiselier40492ba2016-07-23 20:36:55 +000073 typedef typename __rebind_pointer<_NodePtr, __first_node>::type __node_base_pointer;
74 typedef _NodePtr __node_pointer;
Howard Hinnant3e519522010-05-11 19:42:16 +000075
Eric Fiselier40492ba2016-07-23 20:36:55 +000076#if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB)
77 typedef __node_base_pointer __next_pointer;
78#else
79 typedef typename conditional<
80 is_pointer<__node_pointer>::value,
81 __node_base_pointer,
82 __node_pointer>::type __next_pointer;
83#endif
84
85 __next_pointer __next_;
86
87 _LIBCPP_INLINE_VISIBILITY
88 __next_pointer __ptr() _NOEXCEPT {
89 return static_cast<__next_pointer>(
90 pointer_traits<__node_base_pointer>::pointer_to(*this));
91 }
92
93 _LIBCPP_INLINE_VISIBILITY
94 __node_pointer __upcast() _NOEXCEPT {
95 return static_cast<__node_pointer>(
96 pointer_traits<__node_base_pointer>::pointer_to(*this));
97 }
98
99 _LIBCPP_INLINE_VISIBILITY
100 size_t __hash() const _NOEXCEPT {
101 return static_cast<__node_type const&>(*this).__hash_;
102 }
Howard Hinnant3e519522010-05-11 19:42:16 +0000103
Howard Hinnant37141072011-06-04 18:54:24 +0000104 _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
Howard Hinnant3e519522010-05-11 19:42:16 +0000105};
106
107template <class _Tp, class _VoidPtr>
108struct __hash_node
109 : public __hash_node_base
110 <
Eric Fiselier934b0922015-12-30 21:52:00 +0000111 typename __rebind_pointer<_VoidPtr, __hash_node<_Tp, _VoidPtr> >::type
Howard Hinnant3e519522010-05-11 19:42:16 +0000112 >
113{
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000114 typedef _Tp __node_value_type;
Howard Hinnant3e519522010-05-11 19:42:16 +0000115
Eric Fiselier40492ba2016-07-23 20:36:55 +0000116 size_t __hash_;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000117 __node_value_type __value_;
Howard Hinnant3e519522010-05-11 19:42:16 +0000118};
119
Howard Hinnant4cb38a82012-07-06 17:31:14 +0000120inline _LIBCPP_INLINE_VISIBILITY
121bool
Eric Fiselier9ba5c112015-02-02 21:31:48 +0000122__is_hash_power2(size_t __bc)
Howard Hinnant4cb38a82012-07-06 17:31:14 +0000123{
124 return __bc > 2 && !(__bc & (__bc - 1));
125}
126
127inline _LIBCPP_INLINE_VISIBILITY
128size_t
129__constrain_hash(size_t __h, size_t __bc)
130{
Eric Fiselier118cb412016-07-11 22:02:02 +0000131 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) :
132 (__h < __bc ? __h : __h % __bc);
Howard Hinnant4cb38a82012-07-06 17:31:14 +0000133}
134
135inline _LIBCPP_INLINE_VISIBILITY
136size_t
Eric Fiselier9ba5c112015-02-02 21:31:48 +0000137__next_hash_pow2(size_t __n)
Howard Hinnant4cb38a82012-07-06 17:31:14 +0000138{
139 return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
140}
141
Duncan P. N. Exon Smithfde79b42016-03-17 20:45:20 +0000142
Howard Hinnantce534202011-06-14 19:58:17 +0000143template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000144
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000145template <class _NodePtr> class _LIBCPP_TEMPLATE_VIS __hash_iterator;
146template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
147template <class _NodePtr> class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
148template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
149template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
150template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
Howard Hinnant3e519522010-05-11 19:42:16 +0000151
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000152template <class _Tp>
Eric Fiselier43b121d2016-02-20 07:59:16 +0000153struct __hash_key_value_types {
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000154 static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
155 typedef _Tp key_type;
156 typedef _Tp __node_value_type;
157 typedef _Tp __container_value_type;
158 static const bool __is_map = false;
Eric Fiselierfcd02212016-02-11 11:59:44 +0000159
160 _LIBCPP_INLINE_VISIBILITY
161 static key_type const& __get_key(_Tp const& __v) {
162 return __v;
163 }
164 _LIBCPP_INLINE_VISIBILITY
165 static __container_value_type const& __get_value(__node_value_type const& __v) {
166 return __v;
167 }
168 _LIBCPP_INLINE_VISIBILITY
169 static __container_value_type* __get_ptr(__node_value_type& __n) {
170 return _VSTD::addressof(__n);
171 }
172#ifndef _LIBCPP_CXX03_LANG
173 _LIBCPP_INLINE_VISIBILITY
174 static __container_value_type&& __move(__node_value_type& __v) {
175 return _VSTD::move(__v);
176 }
177#endif
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000178};
179
180template <class _Key, class _Tp>
Eric Fiselier43b121d2016-02-20 07:59:16 +0000181struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000182 typedef _Key key_type;
183 typedef _Tp mapped_type;
184 typedef __hash_value_type<_Key, _Tp> __node_value_type;
185 typedef pair<const _Key, _Tp> __container_value_type;
Eric Fiselierfcd02212016-02-11 11:59:44 +0000186 typedef pair<_Key, _Tp> __nc_value_type;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000187 typedef __container_value_type __map_value_type;
188 static const bool __is_map = true;
Eric Fiselierfcd02212016-02-11 11:59:44 +0000189
190 _LIBCPP_INLINE_VISIBILITY
191 static key_type const& __get_key(__container_value_type const& __v) {
192 return __v.first;
193 }
194
195 template <class _Up>
196 _LIBCPP_INLINE_VISIBILITY
197 static typename enable_if<__is_same_uncvref<_Up, __node_value_type>::value,
198 __container_value_type const&>::type
199 __get_value(_Up& __t) {
200 return __t.__cc;
201 }
202
203 template <class _Up>
204 _LIBCPP_INLINE_VISIBILITY
205 static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,
206 __container_value_type const&>::type
207 __get_value(_Up& __t) {
208 return __t;
209 }
210
211 _LIBCPP_INLINE_VISIBILITY
212 static __container_value_type* __get_ptr(__node_value_type& __n) {
213 return _VSTD::addressof(__n.__cc);
214 }
215#ifndef _LIBCPP_CXX03_LANG
216 _LIBCPP_INLINE_VISIBILITY
217 static __nc_value_type&& __move(__node_value_type& __v) {
218 return _VSTD::move(__v.__nc);
219 }
220#endif
221
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000222};
223
Eric Fiselier43b121d2016-02-20 07:59:16 +0000224template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>,
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000225 bool = _KVTypes::__is_map>
Eric Fiselier43b121d2016-02-20 07:59:16 +0000226struct __hash_map_pointer_types {};
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000227
228template <class _Tp, class _AllocPtr, class _KVTypes>
Eric Fiselier43b121d2016-02-20 07:59:16 +0000229struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000230 typedef typename _KVTypes::__map_value_type _Mv;
231 typedef typename __rebind_pointer<_AllocPtr, _Mv>::type
232 __map_value_type_pointer;
233 typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type
234 __const_map_value_type_pointer;
235};
236
237template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
238struct __hash_node_types;
239
240template <class _NodePtr, class _Tp, class _VoidPtr>
241struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
Eric Fiselier43b121d2016-02-20 07:59:16 +0000242 : public __hash_key_value_types<_Tp>, __hash_map_pointer_types<_Tp, _VoidPtr>
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000243
244{
Eric Fiselier43b121d2016-02-20 07:59:16 +0000245 typedef __hash_key_value_types<_Tp> __base;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000246
247public:
248 typedef ptrdiff_t difference_type;
249 typedef size_t size_type;
250
251 typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer;
252
253 typedef typename pointer_traits<_NodePtr>::element_type __node_type;
254 typedef _NodePtr __node_pointer;
255
256 typedef __hash_node_base<__node_pointer> __node_base_type;
257 typedef typename __rebind_pointer<_NodePtr, __node_base_type>::type
258 __node_base_pointer;
259
Eric Fiselier40492ba2016-07-23 20:36:55 +0000260 typedef typename __node_base_type::__next_pointer __next_pointer;
261
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000262 typedef _Tp __node_value_type;
263 typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type
264 __node_value_type_pointer;
265 typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type
266 __const_node_value_type_pointer;
Eric Fiselier40492ba2016-07-23 20:36:55 +0000267
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000268private:
269 static_assert(!is_const<__node_type>::value,
270 "_NodePtr should never be a pointer to const");
271 static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),
272 "_VoidPtr does not point to unqualified void type");
273 static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type,
274 _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");
275};
276
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000277template <class _HashIterator>
278struct __hash_node_types_from_iterator;
279template <class _NodePtr>
280struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
281template <class _NodePtr>
282struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
283template <class _NodePtr>
284struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
285template <class _NodePtr>
286struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
287
288
289template <class _NodeValueTp, class _VoidPtr>
290struct __make_hash_node_types {
291 typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
292 typedef typename __rebind_pointer<_VoidPtr, _NodeTp>::type _NodePtr;
293 typedef __hash_node_types<_NodePtr> type;
294};
295
Howard Hinnant3e519522010-05-11 19:42:16 +0000296template <class _NodePtr>
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000297class _LIBCPP_TEMPLATE_VIS __hash_iterator
Howard Hinnant3e519522010-05-11 19:42:16 +0000298{
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000299 typedef __hash_node_types<_NodePtr> _NodeTypes;
Eric Fiselier40492ba2016-07-23 20:36:55 +0000300 typedef _NodePtr __node_pointer;
301 typedef typename _NodeTypes::__next_pointer __next_pointer;
Howard Hinnant3e519522010-05-11 19:42:16 +0000302
Eric Fiselier40492ba2016-07-23 20:36:55 +0000303 __next_pointer __node_;
Howard Hinnant3e519522010-05-11 19:42:16 +0000304
305public:
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000306 typedef forward_iterator_tag iterator_category;
307 typedef typename _NodeTypes::__node_value_type value_type;
308 typedef typename _NodeTypes::difference_type difference_type;
309 typedef value_type& reference;
310 typedef typename _NodeTypes::__node_value_type_pointer pointer;
Howard Hinnant3e519522010-05-11 19:42:16 +0000311
Eric Fiselier40492ba2016-07-23 20:36:55 +0000312 _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT : __node_(nullptr) {
313 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
Howard Hinnantb24c8022013-07-23 22:01:58 +0000314 }
315
316#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant43d99232010-09-21 17:32:39 +0000317 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb24c8022013-07-23 22:01:58 +0000318 __hash_iterator(const __hash_iterator& __i)
319 : __node_(__i.__node_)
320 {
321 __get_db()->__iterator_copy(this, &__i);
322 }
323
Howard Hinnant43d99232010-09-21 17:32:39 +0000324 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb24c8022013-07-23 22:01:58 +0000325 ~__hash_iterator()
326 {
327 __get_db()->__erase_i(this);
328 }
329
330 _LIBCPP_INLINE_VISIBILITY
331 __hash_iterator& operator=(const __hash_iterator& __i)
332 {
333 if (this != &__i)
334 {
335 __get_db()->__iterator_copy(this, &__i);
336 __node_ = __i.__node_;
337 }
338 return *this;
339 }
Howard Hinnantb24c8022013-07-23 22:01:58 +0000340#endif // _LIBCPP_DEBUG_LEVEL >= 2
341
342 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000343 reference operator*() const {
344 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
345 "Attempted to dereference a non-dereferenceable unordered container iterator");
346 return __node_->__upcast()->__value_;
347 }
Howard Hinnant3e519522010-05-11 19:42:16 +0000348
Howard Hinnant43d99232010-09-21 17:32:39 +0000349 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000350 pointer operator->() const {
351 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
352 "Attempted to dereference a non-dereferenceable unordered container iterator");
353 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
354 }
355
356 _LIBCPP_INLINE_VISIBILITY
357 __hash_iterator& operator++() {
358 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
Howard Hinnantb24c8022013-07-23 22:01:58 +0000359 "Attempted to increment non-incrementable unordered container iterator");
Howard Hinnant3e519522010-05-11 19:42:16 +0000360 __node_ = __node_->__next_;
361 return *this;
362 }
363
Howard Hinnant43d99232010-09-21 17:32:39 +0000364 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000365 __hash_iterator operator++(int)
366 {
367 __hash_iterator __t(*this);
368 ++(*this);
369 return __t;
370 }
371
Howard Hinnant43d99232010-09-21 17:32:39 +0000372 friend _LIBCPP_INLINE_VISIBILITY
373 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000374 {
Howard Hinnantb24c8022013-07-23 22:01:58 +0000375 return __x.__node_ == __y.__node_;
376 }
Howard Hinnant43d99232010-09-21 17:32:39 +0000377 friend _LIBCPP_INLINE_VISIBILITY
378 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000379 {return !(__x == __y);}
Howard Hinnant3e519522010-05-11 19:42:16 +0000380
381private:
Howard Hinnantb24c8022013-07-23 22:01:58 +0000382#if _LIBCPP_DEBUG_LEVEL >= 2
383 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000384 __hash_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
Howard Hinnantb24c8022013-07-23 22:01:58 +0000385 : __node_(__node)
386 {
387 __get_db()->__insert_ic(this, __c);
388 }
389#else
Howard Hinnant43d99232010-09-21 17:32:39 +0000390 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000391 __hash_iterator(__next_pointer __node) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000392 : __node_(__node)
393 {}
Howard Hinnantb24c8022013-07-23 22:01:58 +0000394#endif
Howard Hinnant3e519522010-05-11 19:42:16 +0000395 template <class, class, class, class> friend class __hash_table;
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000396 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
397 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
398 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
399 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
Howard Hinnant3e519522010-05-11 19:42:16 +0000400};
401
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000402template <class _NodePtr>
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000403class _LIBCPP_TEMPLATE_VIS __hash_const_iterator
Howard Hinnant3e519522010-05-11 19:42:16 +0000404{
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000405 static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
406 typedef __hash_node_types<_NodePtr> _NodeTypes;
Eric Fiselier40492ba2016-07-23 20:36:55 +0000407 typedef _NodePtr __node_pointer;
408 typedef typename _NodeTypes::__next_pointer __next_pointer;
Eric Fiselier757373e2016-02-18 00:20:34 +0000409
Eric Fiselier40492ba2016-07-23 20:36:55 +0000410 __next_pointer __node_;
Howard Hinnant3e519522010-05-11 19:42:16 +0000411
412public:
Eric Fiselier757373e2016-02-18 00:20:34 +0000413 typedef __hash_iterator<_NodePtr> __non_const_iterator;
414
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000415 typedef forward_iterator_tag iterator_category;
416 typedef typename _NodeTypes::__node_value_type value_type;
417 typedef typename _NodeTypes::difference_type difference_type;
418 typedef const value_type& reference;
419 typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
420
Howard Hinnant3e519522010-05-11 19:42:16 +0000421
Eric Fiselier40492ba2016-07-23 20:36:55 +0000422 _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {
423 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
Howard Hinnantb24c8022013-07-23 22:01:58 +0000424 }
Eric Fiselier40492ba2016-07-23 20:36:55 +0000425
Howard Hinnant43d99232010-09-21 17:32:39 +0000426 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000427 __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000428 : __node_(__x.__node_)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000429 {
Eric Fiselier40492ba2016-07-23 20:36:55 +0000430 _LIBCPP_DEBUG_MODE(__get_db()->__iterator_copy(this, &__x));
Howard Hinnantb24c8022013-07-23 22:01:58 +0000431 }
432
433#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant43d99232010-09-21 17:32:39 +0000434 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb24c8022013-07-23 22:01:58 +0000435 __hash_const_iterator(const __hash_const_iterator& __i)
436 : __node_(__i.__node_)
437 {
438 __get_db()->__iterator_copy(this, &__i);
439 }
440
Howard Hinnant43d99232010-09-21 17:32:39 +0000441 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb24c8022013-07-23 22:01:58 +0000442 ~__hash_const_iterator()
443 {
444 __get_db()->__erase_i(this);
445 }
446
447 _LIBCPP_INLINE_VISIBILITY
448 __hash_const_iterator& operator=(const __hash_const_iterator& __i)
449 {
450 if (this != &__i)
451 {
452 __get_db()->__iterator_copy(this, &__i);
453 __node_ = __i.__node_;
454 }
455 return *this;
456 }
Howard Hinnantb24c8022013-07-23 22:01:58 +0000457#endif // _LIBCPP_DEBUG_LEVEL >= 2
458
459 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000460 reference operator*() const {
461 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
Howard Hinnantb24c8022013-07-23 22:01:58 +0000462 "Attempted to dereference a non-dereferenceable unordered container const_iterator");
Eric Fiselier40492ba2016-07-23 20:36:55 +0000463 return __node_->__upcast()->__value_;
464 }
Howard Hinnantb24c8022013-07-23 22:01:58 +0000465 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000466 pointer operator->() const {
467 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
Howard Hinnantb24c8022013-07-23 22:01:58 +0000468 "Attempted to dereference a non-dereferenceable unordered container const_iterator");
Eric Fiselier40492ba2016-07-23 20:36:55 +0000469 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
470 }
Howard Hinnant3e519522010-05-11 19:42:16 +0000471
Howard Hinnant43d99232010-09-21 17:32:39 +0000472 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000473 __hash_const_iterator& operator++() {
474 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
475 "Attempted to increment non-incrementable unordered container const_iterator");
Howard Hinnant3e519522010-05-11 19:42:16 +0000476 __node_ = __node_->__next_;
477 return *this;
478 }
479
Howard Hinnant43d99232010-09-21 17:32:39 +0000480 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000481 __hash_const_iterator operator++(int)
482 {
483 __hash_const_iterator __t(*this);
484 ++(*this);
485 return __t;
486 }
487
Howard Hinnant43d99232010-09-21 17:32:39 +0000488 friend _LIBCPP_INLINE_VISIBILITY
489 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000490 {
Howard Hinnantb24c8022013-07-23 22:01:58 +0000491 return __x.__node_ == __y.__node_;
492 }
Howard Hinnant43d99232010-09-21 17:32:39 +0000493 friend _LIBCPP_INLINE_VISIBILITY
494 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000495 {return !(__x == __y);}
Howard Hinnant3e519522010-05-11 19:42:16 +0000496
497private:
Howard Hinnantb24c8022013-07-23 22:01:58 +0000498#if _LIBCPP_DEBUG_LEVEL >= 2
499 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000500 __hash_const_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
Howard Hinnantb24c8022013-07-23 22:01:58 +0000501 : __node_(__node)
502 {
503 __get_db()->__insert_ic(this, __c);
504 }
505#else
Howard Hinnant43d99232010-09-21 17:32:39 +0000506 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000507 __hash_const_iterator(__next_pointer __node) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000508 : __node_(__node)
509 {}
Howard Hinnantb24c8022013-07-23 22:01:58 +0000510#endif
Howard Hinnant3e519522010-05-11 19:42:16 +0000511 template <class, class, class, class> friend class __hash_table;
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000512 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
513 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
514 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
Howard Hinnant3e519522010-05-11 19:42:16 +0000515};
516
Howard Hinnant3e519522010-05-11 19:42:16 +0000517template <class _NodePtr>
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000518class _LIBCPP_TEMPLATE_VIS __hash_local_iterator
Howard Hinnant3e519522010-05-11 19:42:16 +0000519{
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000520 typedef __hash_node_types<_NodePtr> _NodeTypes;
Eric Fiselier40492ba2016-07-23 20:36:55 +0000521 typedef _NodePtr __node_pointer;
522 typedef typename _NodeTypes::__next_pointer __next_pointer;
Howard Hinnant3e519522010-05-11 19:42:16 +0000523
Eric Fiselier40492ba2016-07-23 20:36:55 +0000524 __next_pointer __node_;
Howard Hinnant3e519522010-05-11 19:42:16 +0000525 size_t __bucket_;
526 size_t __bucket_count_;
527
Howard Hinnant3e519522010-05-11 19:42:16 +0000528public:
529 typedef forward_iterator_tag iterator_category;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000530 typedef typename _NodeTypes::__node_value_type value_type;
531 typedef typename _NodeTypes::difference_type difference_type;
Howard Hinnant3e519522010-05-11 19:42:16 +0000532 typedef value_type& reference;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000533 typedef typename _NodeTypes::__node_value_type_pointer pointer;
Howard Hinnant3e519522010-05-11 19:42:16 +0000534
Eric Fiselier40492ba2016-07-23 20:36:55 +0000535 _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {
536 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
Howard Hinnantb24c8022013-07-23 22:01:58 +0000537 }
538
539#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant43d99232010-09-21 17:32:39 +0000540 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb24c8022013-07-23 22:01:58 +0000541 __hash_local_iterator(const __hash_local_iterator& __i)
542 : __node_(__i.__node_),
543 __bucket_(__i.__bucket_),
544 __bucket_count_(__i.__bucket_count_)
545 {
546 __get_db()->__iterator_copy(this, &__i);
547 }
548
Howard Hinnant43d99232010-09-21 17:32:39 +0000549 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb24c8022013-07-23 22:01:58 +0000550 ~__hash_local_iterator()
551 {
552 __get_db()->__erase_i(this);
553 }
554
555 _LIBCPP_INLINE_VISIBILITY
556 __hash_local_iterator& operator=(const __hash_local_iterator& __i)
557 {
558 if (this != &__i)
559 {
560 __get_db()->__iterator_copy(this, &__i);
561 __node_ = __i.__node_;
562 __bucket_ = __i.__bucket_;
563 __bucket_count_ = __i.__bucket_count_;
564 }
565 return *this;
566 }
Howard Hinnantb24c8022013-07-23 22:01:58 +0000567#endif // _LIBCPP_DEBUG_LEVEL >= 2
568
569 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000570 reference operator*() const {
571 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
Howard Hinnantb24c8022013-07-23 22:01:58 +0000572 "Attempted to dereference a non-dereferenceable unordered container local_iterator");
Eric Fiselier40492ba2016-07-23 20:36:55 +0000573 return __node_->__upcast()->__value_;
574 }
Howard Hinnant3e519522010-05-11 19:42:16 +0000575
Howard Hinnant43d99232010-09-21 17:32:39 +0000576 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000577 pointer operator->() const {
578 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
579 "Attempted to dereference a non-dereferenceable unordered container local_iterator");
580 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
581 }
582
583 _LIBCPP_INLINE_VISIBILITY
584 __hash_local_iterator& operator++() {
585 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
Howard Hinnantb24c8022013-07-23 22:01:58 +0000586 "Attempted to increment non-incrementable unordered container local_iterator");
Howard Hinnant3e519522010-05-11 19:42:16 +0000587 __node_ = __node_->__next_;
Eric Fiselier40492ba2016-07-23 20:36:55 +0000588 if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
Howard Hinnant3e519522010-05-11 19:42:16 +0000589 __node_ = nullptr;
590 return *this;
591 }
592
Howard Hinnant43d99232010-09-21 17:32:39 +0000593 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000594 __hash_local_iterator operator++(int)
595 {
596 __hash_local_iterator __t(*this);
597 ++(*this);
598 return __t;
599 }
600
Howard Hinnant43d99232010-09-21 17:32:39 +0000601 friend _LIBCPP_INLINE_VISIBILITY
602 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000603 {
Howard Hinnantb24c8022013-07-23 22:01:58 +0000604 return __x.__node_ == __y.__node_;
605 }
Howard Hinnant43d99232010-09-21 17:32:39 +0000606 friend _LIBCPP_INLINE_VISIBILITY
607 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000608 {return !(__x == __y);}
Howard Hinnant3e519522010-05-11 19:42:16 +0000609
610private:
Howard Hinnantb24c8022013-07-23 22:01:58 +0000611#if _LIBCPP_DEBUG_LEVEL >= 2
612 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000613 __hash_local_iterator(__next_pointer __node, size_t __bucket,
Howard Hinnantb24c8022013-07-23 22:01:58 +0000614 size_t __bucket_count, const void* __c) _NOEXCEPT
615 : __node_(__node),
616 __bucket_(__bucket),
617 __bucket_count_(__bucket_count)
618 {
619 __get_db()->__insert_ic(this, __c);
620 if (__node_ != nullptr)
621 __node_ = __node_->__next_;
622 }
623#else
Howard Hinnant43d99232010-09-21 17:32:39 +0000624 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000625 __hash_local_iterator(__next_pointer __node, size_t __bucket,
Howard Hinnant37141072011-06-04 18:54:24 +0000626 size_t __bucket_count) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000627 : __node_(__node),
628 __bucket_(__bucket),
629 __bucket_count_(__bucket_count)
630 {
631 if (__node_ != nullptr)
632 __node_ = __node_->__next_;
633 }
Howard Hinnantb24c8022013-07-23 22:01:58 +0000634#endif
Howard Hinnant3e519522010-05-11 19:42:16 +0000635 template <class, class, class, class> friend class __hash_table;
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000636 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
637 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
Howard Hinnant3e519522010-05-11 19:42:16 +0000638};
639
640template <class _ConstNodePtr>
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000641class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator
Howard Hinnant3e519522010-05-11 19:42:16 +0000642{
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000643 typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
Eric Fiselier40492ba2016-07-23 20:36:55 +0000644 typedef _ConstNodePtr __node_pointer;
645 typedef typename _NodeTypes::__next_pointer __next_pointer;
Howard Hinnant3e519522010-05-11 19:42:16 +0000646
Eric Fiselier40492ba2016-07-23 20:36:55 +0000647 __next_pointer __node_;
Howard Hinnant3e519522010-05-11 19:42:16 +0000648 size_t __bucket_;
649 size_t __bucket_count_;
650
651 typedef pointer_traits<__node_pointer> __pointer_traits;
652 typedef typename __pointer_traits::element_type __node;
653 typedef typename remove_const<__node>::type __non_const_node;
Eric Fiselier934b0922015-12-30 21:52:00 +0000654 typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type
655 __non_const_node_pointer;
Eric Fiselier757373e2016-02-18 00:20:34 +0000656public:
Howard Hinnant3e519522010-05-11 19:42:16 +0000657 typedef __hash_local_iterator<__non_const_node_pointer>
658 __non_const_iterator;
Eric Fiselier757373e2016-02-18 00:20:34 +0000659
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000660 typedef forward_iterator_tag iterator_category;
661 typedef typename _NodeTypes::__node_value_type value_type;
662 typedef typename _NodeTypes::difference_type difference_type;
663 typedef const value_type& reference;
664 typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
Eric Fiselier934b0922015-12-30 21:52:00 +0000665
Howard Hinnant3e519522010-05-11 19:42:16 +0000666
Eric Fiselier40492ba2016-07-23 20:36:55 +0000667 _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {
668 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
Howard Hinnantb24c8022013-07-23 22:01:58 +0000669 }
670
Howard Hinnant43d99232010-09-21 17:32:39 +0000671 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000672 __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000673 : __node_(__x.__node_),
674 __bucket_(__x.__bucket_),
675 __bucket_count_(__x.__bucket_count_)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000676 {
Eric Fiselier40492ba2016-07-23 20:36:55 +0000677 _LIBCPP_DEBUG_MODE(__get_db()->__iterator_copy(this, &__x));
Howard Hinnantb24c8022013-07-23 22:01:58 +0000678 }
679
680#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant43d99232010-09-21 17:32:39 +0000681 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb24c8022013-07-23 22:01:58 +0000682 __hash_const_local_iterator(const __hash_const_local_iterator& __i)
683 : __node_(__i.__node_),
684 __bucket_(__i.__bucket_),
685 __bucket_count_(__i.__bucket_count_)
686 {
687 __get_db()->__iterator_copy(this, &__i);
688 }
689
Howard Hinnant43d99232010-09-21 17:32:39 +0000690 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb24c8022013-07-23 22:01:58 +0000691 ~__hash_const_local_iterator()
692 {
693 __get_db()->__erase_i(this);
694 }
695
696 _LIBCPP_INLINE_VISIBILITY
697 __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i)
698 {
699 if (this != &__i)
700 {
701 __get_db()->__iterator_copy(this, &__i);
702 __node_ = __i.__node_;
703 __bucket_ = __i.__bucket_;
704 __bucket_count_ = __i.__bucket_count_;
705 }
706 return *this;
707 }
Howard Hinnantb24c8022013-07-23 22:01:58 +0000708#endif // _LIBCPP_DEBUG_LEVEL >= 2
709
710 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000711 reference operator*() const {
712 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
Howard Hinnantb24c8022013-07-23 22:01:58 +0000713 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
Eric Fiselier40492ba2016-07-23 20:36:55 +0000714 return __node_->__upcast()->__value_;
715 }
Howard Hinnant3e519522010-05-11 19:42:16 +0000716
Howard Hinnant43d99232010-09-21 17:32:39 +0000717 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000718 pointer operator->() const {
719 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
720 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
721 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
722 }
723
724 _LIBCPP_INLINE_VISIBILITY
725 __hash_const_local_iterator& operator++() {
726 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
Howard Hinnantb24c8022013-07-23 22:01:58 +0000727 "Attempted to increment non-incrementable unordered container const_local_iterator");
Howard Hinnant3e519522010-05-11 19:42:16 +0000728 __node_ = __node_->__next_;
Eric Fiselier40492ba2016-07-23 20:36:55 +0000729 if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
Howard Hinnant3e519522010-05-11 19:42:16 +0000730 __node_ = nullptr;
731 return *this;
732 }
733
Howard Hinnant43d99232010-09-21 17:32:39 +0000734 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000735 __hash_const_local_iterator operator++(int)
736 {
737 __hash_const_local_iterator __t(*this);
738 ++(*this);
739 return __t;
740 }
741
Howard Hinnant43d99232010-09-21 17:32:39 +0000742 friend _LIBCPP_INLINE_VISIBILITY
743 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000744 {
Howard Hinnantb24c8022013-07-23 22:01:58 +0000745 return __x.__node_ == __y.__node_;
746 }
Howard Hinnant43d99232010-09-21 17:32:39 +0000747 friend _LIBCPP_INLINE_VISIBILITY
748 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000749 {return !(__x == __y);}
Howard Hinnant3e519522010-05-11 19:42:16 +0000750
751private:
Howard Hinnantb24c8022013-07-23 22:01:58 +0000752#if _LIBCPP_DEBUG_LEVEL >= 2
753 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000754 __hash_const_local_iterator(__next_pointer __node, size_t __bucket,
Howard Hinnantb24c8022013-07-23 22:01:58 +0000755 size_t __bucket_count, const void* __c) _NOEXCEPT
756 : __node_(__node),
757 __bucket_(__bucket),
758 __bucket_count_(__bucket_count)
759 {
760 __get_db()->__insert_ic(this, __c);
761 if (__node_ != nullptr)
762 __node_ = __node_->__next_;
763 }
764#else
Howard Hinnant43d99232010-09-21 17:32:39 +0000765 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier40492ba2016-07-23 20:36:55 +0000766 __hash_const_local_iterator(__next_pointer __node, size_t __bucket,
Howard Hinnant37141072011-06-04 18:54:24 +0000767 size_t __bucket_count) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000768 : __node_(__node),
769 __bucket_(__bucket),
770 __bucket_count_(__bucket_count)
771 {
772 if (__node_ != nullptr)
773 __node_ = __node_->__next_;
774 }
Howard Hinnantb24c8022013-07-23 22:01:58 +0000775#endif
Howard Hinnant3e519522010-05-11 19:42:16 +0000776 template <class, class, class, class> friend class __hash_table;
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000777 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
Howard Hinnant3e519522010-05-11 19:42:16 +0000778};
779
780template <class _Alloc>
781class __bucket_list_deallocator
782{
783 typedef _Alloc allocator_type;
784 typedef allocator_traits<allocator_type> __alloc_traits;
785 typedef typename __alloc_traits::size_type size_type;
786
787 __compressed_pair<size_type, allocator_type> __data_;
788public:
789 typedef typename __alloc_traits::pointer pointer;
790
Howard Hinnant43d99232010-09-21 17:32:39 +0000791 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000792 __bucket_list_deallocator()
Howard Hinnant37141072011-06-04 18:54:24 +0000793 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnant3e519522010-05-11 19:42:16 +0000794 : __data_(0) {}
Howard Hinnant43d99232010-09-21 17:32:39 +0000795
796 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000797 __bucket_list_deallocator(const allocator_type& __a, size_type __size)
Howard Hinnant37141072011-06-04 18:54:24 +0000798 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
Howard Hinnant3e519522010-05-11 19:42:16 +0000799 : __data_(__size, __a) {}
800
Howard Hinnant7609c9b2010-09-04 23:28:19 +0000801#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +0000802
Howard Hinnant43d99232010-09-21 17:32:39 +0000803 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000804 __bucket_list_deallocator(__bucket_list_deallocator&& __x)
Howard Hinnant37141072011-06-04 18:54:24 +0000805 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Howard Hinnantce48a112011-06-30 21:18:19 +0000806 : __data_(_VSTD::move(__x.__data_))
Howard Hinnant3e519522010-05-11 19:42:16 +0000807 {
808 __x.size() = 0;
809 }
810
Howard Hinnant7609c9b2010-09-04 23:28:19 +0000811#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +0000812
Howard Hinnant37141072011-06-04 18:54:24 +0000813 _LIBCPP_INLINE_VISIBILITY
814 size_type& size() _NOEXCEPT {return __data_.first();}
815 _LIBCPP_INLINE_VISIBILITY
816 size_type size() const _NOEXCEPT {return __data_.first();}
Howard Hinnant3e519522010-05-11 19:42:16 +0000817
Howard Hinnant43d99232010-09-21 17:32:39 +0000818 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000819 allocator_type& __alloc() _NOEXCEPT {return __data_.second();}
820 _LIBCPP_INLINE_VISIBILITY
821 const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();}
822
823 _LIBCPP_INLINE_VISIBILITY
824 void operator()(pointer __p) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000825 {
826 __alloc_traits::deallocate(__alloc(), __p, size());
827 }
828};
829
Howard Hinnantce534202011-06-14 19:58:17 +0000830template <class _Alloc> class __hash_map_node_destructor;
Howard Hinnant3e519522010-05-11 19:42:16 +0000831
832template <class _Alloc>
833class __hash_node_destructor
834{
835 typedef _Alloc allocator_type;
836 typedef allocator_traits<allocator_type> __alloc_traits;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000837
Howard Hinnant3e519522010-05-11 19:42:16 +0000838public:
839 typedef typename __alloc_traits::pointer pointer;
840private:
Eric Fiselierfcd02212016-02-11 11:59:44 +0000841 typedef __hash_node_types<pointer> _NodeTypes;
Howard Hinnant3e519522010-05-11 19:42:16 +0000842
843 allocator_type& __na_;
844
845 __hash_node_destructor& operator=(const __hash_node_destructor&);
846
847public:
848 bool __value_constructed;
849
Howard Hinnant43d99232010-09-21 17:32:39 +0000850 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf622b582011-07-31 17:04:30 +0000851 explicit __hash_node_destructor(allocator_type& __na,
852 bool __constructed = false) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000853 : __na_(__na),
Howard Hinnantf622b582011-07-31 17:04:30 +0000854 __value_constructed(__constructed)
Howard Hinnant3e519522010-05-11 19:42:16 +0000855 {}
856
Howard Hinnant43d99232010-09-21 17:32:39 +0000857 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000858 void operator()(pointer __p) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000859 {
860 if (__value_constructed)
Eric Fiselierfcd02212016-02-11 11:59:44 +0000861 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
Howard Hinnant3e519522010-05-11 19:42:16 +0000862 if (__p)
863 __alloc_traits::deallocate(__na_, __p, 1);
864 }
865
866 template <class> friend class __hash_map_node_destructor;
867};
868
Eric Fiselier04333f92017-01-13 22:42:53 +0000869
870#ifndef _LIBCPP_CXX03_LANG
871template <class _Key, class _Hash, class _Equal, class _Alloc>
872struct __diagnose_hash_table_helper {
873 static constexpr bool __trigger_diagnostics()
874 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value,
875 "the specified hash functor does not provide a const call operator")
876 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value,
877 "the specified comparator type does not provide a const call operator")
878 { return true; }
879};
880
881template <class _Key, class _Value, class _Hash, class _Equal, class _Alloc>
882struct __diagnose_hash_table_helper<
883 __hash_value_type<_Key, _Value>,
884 __unordered_map_hasher<_Key, __hash_value_type<_Key, _Value>, _Hash>,
885 __unordered_map_equal<_Key, __hash_value_type<_Key, _Value>, _Equal>,
886 _Alloc>
887: __diagnose_hash_table_helper<_Key, _Hash, _Equal, _Alloc>
888{
889};
890#endif // _LIBCPP_CXX03_LANG
891
Howard Hinnant3e519522010-05-11 19:42:16 +0000892template <class _Tp, class _Hash, class _Equal, class _Alloc>
893class __hash_table
894{
895public:
896 typedef _Tp value_type;
897 typedef _Hash hasher;
898 typedef _Equal key_equal;
899 typedef _Alloc allocator_type;
900
901private:
902 typedef allocator_traits<allocator_type> __alloc_traits;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000903 typedef typename
904 __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type
905 _NodeTypes;
Howard Hinnant3e519522010-05-11 19:42:16 +0000906public:
Eric Fiselierfcd02212016-02-11 11:59:44 +0000907
908 typedef typename _NodeTypes::__node_value_type __node_value_type;
909 typedef typename _NodeTypes::__container_value_type __container_value_type;
Duncan P. N. Exon Smithfde79b42016-03-17 20:45:20 +0000910 typedef typename _NodeTypes::key_type key_type;
Howard Hinnant3e519522010-05-11 19:42:16 +0000911 typedef value_type& reference;
912 typedef const value_type& const_reference;
913 typedef typename __alloc_traits::pointer pointer;
914 typedef typename __alloc_traits::const_pointer const_pointer;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000915#ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
Howard Hinnant3e519522010-05-11 19:42:16 +0000916 typedef typename __alloc_traits::size_type size_type;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000917#else
918 typedef typename _NodeTypes::size_type size_type;
919#endif
920 typedef typename _NodeTypes::difference_type difference_type;
Howard Hinnant3e519522010-05-11 19:42:16 +0000921public:
922 // Create __node
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000923
924 typedef typename _NodeTypes::__node_type __node;
Marshall Clow1f508012015-04-07 05:21:38 +0000925 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
Howard Hinnant3e519522010-05-11 19:42:16 +0000926 typedef allocator_traits<__node_allocator> __node_traits;
Eric Fiselier8e397682016-02-11 15:22:37 +0000927 typedef typename _NodeTypes::__void_pointer __void_pointer;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000928 typedef typename _NodeTypes::__node_pointer __node_pointer;
929 typedef typename _NodeTypes::__node_pointer __node_const_pointer;
930 typedef typename _NodeTypes::__node_base_type __first_node;
931 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
Eric Fiselier40492ba2016-07-23 20:36:55 +0000932 typedef typename _NodeTypes::__next_pointer __next_pointer;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000933
934private:
935 // check for sane allocator pointer rebinding semantics. Rebinding the
936 // allocator for a new pointer type should be exactly the same as rebinding
937 // the pointer using 'pointer_traits'.
938 static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value),
939 "Allocator does not rebind pointers in a sane manner.");
940 typedef typename __rebind_alloc_helper<__node_traits, __first_node>::type
941 __node_base_allocator;
942 typedef allocator_traits<__node_base_allocator> __node_base_traits;
943 static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value),
944 "Allocator does not rebind pointers in a sane manner.");
Howard Hinnant3e519522010-05-11 19:42:16 +0000945
946private:
947
Eric Fiselier40492ba2016-07-23 20:36:55 +0000948 typedef typename __rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator;
Howard Hinnant3e519522010-05-11 19:42:16 +0000949 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
Eric Fiselier40492ba2016-07-23 20:36:55 +0000950 typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
Howard Hinnant3e519522010-05-11 19:42:16 +0000951 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;
Eric Fiselier40492ba2016-07-23 20:36:55 +0000952 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
Howard Hinnant3e519522010-05-11 19:42:16 +0000953
954 // --- Member data begin ---
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000955 __bucket_list __bucket_list_;
956 __compressed_pair<__first_node, __node_allocator> __p1_;
957 __compressed_pair<size_type, hasher> __p2_;
958 __compressed_pair<float, key_equal> __p3_;
Howard Hinnant3e519522010-05-11 19:42:16 +0000959 // --- Member data end ---
960
Howard Hinnant37141072011-06-04 18:54:24 +0000961 _LIBCPP_INLINE_VISIBILITY
962 size_type& size() _NOEXCEPT {return __p2_.first();}
Howard Hinnant3e519522010-05-11 19:42:16 +0000963public:
Howard Hinnant37141072011-06-04 18:54:24 +0000964 _LIBCPP_INLINE_VISIBILITY
965 size_type size() const _NOEXCEPT {return __p2_.first();}
Howard Hinnant3e519522010-05-11 19:42:16 +0000966
Howard Hinnant37141072011-06-04 18:54:24 +0000967 _LIBCPP_INLINE_VISIBILITY
968 hasher& hash_function() _NOEXCEPT {return __p2_.second();}
969 _LIBCPP_INLINE_VISIBILITY
970 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();}
Howard Hinnant3e519522010-05-11 19:42:16 +0000971
Howard Hinnant37141072011-06-04 18:54:24 +0000972 _LIBCPP_INLINE_VISIBILITY
973 float& max_load_factor() _NOEXCEPT {return __p3_.first();}
974 _LIBCPP_INLINE_VISIBILITY
975 float max_load_factor() const _NOEXCEPT {return __p3_.first();}
Howard Hinnant3e519522010-05-11 19:42:16 +0000976
Howard Hinnant37141072011-06-04 18:54:24 +0000977 _LIBCPP_INLINE_VISIBILITY
978 key_equal& key_eq() _NOEXCEPT {return __p3_.second();}
979 _LIBCPP_INLINE_VISIBILITY
980 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();}
Howard Hinnant3e519522010-05-11 19:42:16 +0000981
Howard Hinnant37141072011-06-04 18:54:24 +0000982 _LIBCPP_INLINE_VISIBILITY
983 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();}
984 _LIBCPP_INLINE_VISIBILITY
985 const __node_allocator& __node_alloc() const _NOEXCEPT
986 {return __p1_.second();}
Howard Hinnant3e519522010-05-11 19:42:16 +0000987
988public:
989 typedef __hash_iterator<__node_pointer> iterator;
Howard Hinnant307f8142013-06-22 15:21:29 +0000990 typedef __hash_const_iterator<__node_pointer> const_iterator;
Howard Hinnant3e519522010-05-11 19:42:16 +0000991 typedef __hash_local_iterator<__node_pointer> local_iterator;
Howard Hinnant307f8142013-06-22 15:21:29 +0000992 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
Howard Hinnant3e519522010-05-11 19:42:16 +0000993
Evgeniy Stepanov906c8722015-11-07 01:22:13 +0000994 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000995 __hash_table()
996 _NOEXCEPT_(
997 is_nothrow_default_constructible<__bucket_list>::value &&
998 is_nothrow_default_constructible<__first_node>::value &&
999 is_nothrow_default_constructible<__node_allocator>::value &&
1000 is_nothrow_default_constructible<hasher>::value &&
1001 is_nothrow_default_constructible<key_equal>::value);
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001002 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001003 __hash_table(const hasher& __hf, const key_equal& __eql);
1004 __hash_table(const hasher& __hf, const key_equal& __eql,
1005 const allocator_type& __a);
1006 explicit __hash_table(const allocator_type& __a);
1007 __hash_table(const __hash_table& __u);
1008 __hash_table(const __hash_table& __u, const allocator_type& __a);
Eric Fiselierfcd02212016-02-11 11:59:44 +00001009#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant37141072011-06-04 18:54:24 +00001010 __hash_table(__hash_table&& __u)
1011 _NOEXCEPT_(
1012 is_nothrow_move_constructible<__bucket_list>::value &&
1013 is_nothrow_move_constructible<__first_node>::value &&
1014 is_nothrow_move_constructible<__node_allocator>::value &&
1015 is_nothrow_move_constructible<hasher>::value &&
1016 is_nothrow_move_constructible<key_equal>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +00001017 __hash_table(__hash_table&& __u, const allocator_type& __a);
Eric Fiselierfcd02212016-02-11 11:59:44 +00001018#endif // _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001019 ~__hash_table();
1020
1021 __hash_table& operator=(const __hash_table& __u);
Eric Fiselierfcd02212016-02-11 11:59:44 +00001022#ifndef _LIBCPP_CXX03_LANG
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001023 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001024 __hash_table& operator=(__hash_table&& __u)
1025 _NOEXCEPT_(
1026 __node_traits::propagate_on_container_move_assignment::value &&
1027 is_nothrow_move_assignable<__node_allocator>::value &&
1028 is_nothrow_move_assignable<hasher>::value &&
1029 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +00001030#endif
1031 template <class _InputIterator>
1032 void __assign_unique(_InputIterator __first, _InputIterator __last);
1033 template <class _InputIterator>
1034 void __assign_multi(_InputIterator __first, _InputIterator __last);
1035
Howard Hinnant43d99232010-09-21 17:32:39 +00001036 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001037 size_type max_size() const _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001038 {
Eric Fiselier55b31b4e2016-11-23 01:18:56 +00001039 return std::min<size_type>(
Eric Fiselier341c9dd2016-11-23 09:16:12 +00001040 __node_traits::max_size(__node_alloc()),
Eric Fiselier55b31b4e2016-11-23 01:18:56 +00001041 numeric_limits<difference_type >::max()
1042 );
Howard Hinnant3e519522010-05-11 19:42:16 +00001043 }
1044
1045 pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
1046 iterator __node_insert_multi(__node_pointer __nd);
1047 iterator __node_insert_multi(const_iterator __p,
1048 __node_pointer __nd);
1049
Eric Fiselierfcd02212016-02-11 11:59:44 +00001050#ifndef _LIBCPP_CXX03_LANG
1051 template <class _Key, class ..._Args>
Duncan P. N. Exon Smithfde79b42016-03-17 20:45:20 +00001052 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierfcd02212016-02-11 11:59:44 +00001053 pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
Howard Hinnant3e519522010-05-11 19:42:16 +00001054
Eric Fiselierfcd02212016-02-11 11:59:44 +00001055 template <class... _Args>
Duncan P. N. Exon Smithfde79b42016-03-17 20:45:20 +00001056 _LIBCPP_INLINE_VISIBILITY
1057 pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
1058
1059 template <class _Pp>
1060 _LIBCPP_INLINE_VISIBILITY
1061 pair<iterator, bool> __emplace_unique(_Pp&& __x) {
1062 return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
1063 __can_extract_key<_Pp, key_type>());
1064 }
Eric Fiselier50088682016-04-16 00:23:12 +00001065
1066 template <class _First, class _Second>
1067 _LIBCPP_INLINE_VISIBILITY
1068 typename enable_if<
1069 __can_extract_map_key<_First, key_type, __container_value_type>::value,
1070 pair<iterator, bool>
1071 >::type __emplace_unique(_First&& __f, _Second&& __s) {
1072 return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f),
1073 _VSTD::forward<_Second>(__s));
1074 }
1075
Eric Fiselierfcd02212016-02-11 11:59:44 +00001076 template <class... _Args>
Duncan P. N. Exon Smithfde79b42016-03-17 20:45:20 +00001077 _LIBCPP_INLINE_VISIBILITY
1078 pair<iterator, bool> __emplace_unique(_Args&&... __args) {
1079 return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
1080 }
1081
1082 template <class _Pp>
1083 _LIBCPP_INLINE_VISIBILITY
1084 pair<iterator, bool>
1085 __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
1086 return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
1087 }
1088 template <class _Pp>
1089 _LIBCPP_INLINE_VISIBILITY
1090 pair<iterator, bool>
1091 __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
1092 return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
1093 }
1094 template <class _Pp>
1095 _LIBCPP_INLINE_VISIBILITY
1096 pair<iterator, bool>
1097 __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
1098 return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
1099 }
1100
1101 template <class... _Args>
1102 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierfcd02212016-02-11 11:59:44 +00001103 iterator __emplace_multi(_Args&&... __args);
1104 template <class... _Args>
Duncan P. N. Exon Smithfde79b42016-03-17 20:45:20 +00001105 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierfcd02212016-02-11 11:59:44 +00001106 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
1107
1108
Eric Fiselierde3f2b32015-06-13 07:18:32 +00001109 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierfcd02212016-02-11 11:59:44 +00001110 pair<iterator, bool>
1111 __insert_unique(__container_value_type&& __x) {
1112 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x));
1113 }
1114
1115 template <class _Pp, class = typename enable_if<
1116 !__is_same_uncvref<_Pp, __container_value_type>::value
1117 >::type>
Eric Fiselierde3f2b32015-06-13 07:18:32 +00001118 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierfcd02212016-02-11 11:59:44 +00001119 pair<iterator, bool> __insert_unique(_Pp&& __x) {
1120 return __emplace_unique(_VSTD::forward<_Pp>(__x));
1121 }
1122
1123 template <class _Pp>
1124 _LIBCPP_INLINE_VISIBILITY
1125 iterator __insert_multi(_Pp&& __x) {
1126 return __emplace_multi(_VSTD::forward<_Pp>(__x));
1127 }
1128
1129 template <class _Pp>
1130 _LIBCPP_INLINE_VISIBILITY
1131 iterator __insert_multi(const_iterator __p, _Pp&& __x) {
1132 return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x));
1133 }
1134
1135#else // !defined(_LIBCPP_CXX03_LANG)
1136 template <class _Key, class _Args>
Eric Fiselier4271d012016-09-25 04:05:46 +00001137 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierfcd02212016-02-11 11:59:44 +00001138 pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args);
1139
1140 iterator __insert_multi(const __container_value_type& __x);
1141 iterator __insert_multi(const_iterator __p, const __container_value_type& __x);
Eric Fiselierde3f2b32015-06-13 07:18:32 +00001142#endif
1143
Eric Fiselierfcd02212016-02-11 11:59:44 +00001144 _LIBCPP_INLINE_VISIBILITY
1145 pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
1146 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
1147 }
Howard Hinnant3e519522010-05-11 19:42:16 +00001148
Howard Hinnant37141072011-06-04 18:54:24 +00001149 void clear() _NOEXCEPT;
Howard Hinnant3e519522010-05-11 19:42:16 +00001150 void rehash(size_type __n);
Howard Hinnant43d99232010-09-21 17:32:39 +00001151 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
Howard Hinnant3e519522010-05-11 19:42:16 +00001152 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
Howard Hinnant43d99232010-09-21 17:32:39 +00001153
1154 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001155 size_type bucket_count() const _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001156 {
1157 return __bucket_list_.get_deleter().size();
1158 }
1159
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001160 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001161 iterator begin() _NOEXCEPT;
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001162 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001163 iterator end() _NOEXCEPT;
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001164 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001165 const_iterator begin() const _NOEXCEPT;
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001166 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001167 const_iterator end() const _NOEXCEPT;
Howard Hinnant3e519522010-05-11 19:42:16 +00001168
1169 template <class _Key>
Howard Hinnant43d99232010-09-21 17:32:39 +00001170 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001171 size_type bucket(const _Key& __k) const
Howard Hinnante5c13de2013-07-29 19:05:47 +00001172 {
1173 _LIBCPP_ASSERT(bucket_count() > 0,
1174 "unordered container::bucket(key) called when bucket_count() == 0");
1175 return __constrain_hash(hash_function()(__k), bucket_count());
1176 }
Howard Hinnant3e519522010-05-11 19:42:16 +00001177
1178 template <class _Key>
1179 iterator find(const _Key& __x);
1180 template <class _Key>
1181 const_iterator find(const _Key& __x) const;
1182
Howard Hinnantc003db12011-11-29 18:15:50 +00001183 typedef __hash_node_destructor<__node_allocator> _Dp;
1184 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnant3e519522010-05-11 19:42:16 +00001185
1186 iterator erase(const_iterator __p);
1187 iterator erase(const_iterator __first, const_iterator __last);
1188 template <class _Key>
1189 size_type __erase_unique(const _Key& __k);
1190 template <class _Key>
1191 size_type __erase_multi(const _Key& __k);
Howard Hinnant37141072011-06-04 18:54:24 +00001192 __node_holder remove(const_iterator __p) _NOEXCEPT;
Howard Hinnant3e519522010-05-11 19:42:16 +00001193
1194 template <class _Key>
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001195 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001196 size_type __count_unique(const _Key& __k) const;
1197 template <class _Key>
1198 size_type __count_multi(const _Key& __k) const;
1199
1200 template <class _Key>
1201 pair<iterator, iterator>
1202 __equal_range_unique(const _Key& __k);
1203 template <class _Key>
1204 pair<const_iterator, const_iterator>
1205 __equal_range_unique(const _Key& __k) const;
1206
1207 template <class _Key>
1208 pair<iterator, iterator>
1209 __equal_range_multi(const _Key& __k);
1210 template <class _Key>
1211 pair<const_iterator, const_iterator>
1212 __equal_range_multi(const _Key& __k) const;
1213
Howard Hinnant37141072011-06-04 18:54:24 +00001214 void swap(__hash_table& __u)
Eric Fiselier87a82492015-07-18 20:40:46 +00001215#if _LIBCPP_STD_VER <= 11
Eric Fiselier780b51d2016-12-28 05:53:01 +00001216 _NOEXCEPT_DEBUG_(
Marshall Clowe3fbe142015-07-13 20:04:56 +00001217 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
Marshall Clowe3fbe142015-07-13 20:04:56 +00001218 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
1219 || __is_nothrow_swappable<__pointer_allocator>::value)
1220 && (!__node_traits::propagate_on_container_swap::value
1221 || __is_nothrow_swappable<__node_allocator>::value)
Marshall Clowe3fbe142015-07-13 20:04:56 +00001222 );
Eric Fiselier87a82492015-07-18 20:40:46 +00001223#else
Eric Fiselier780b51d2016-12-28 05:53:01 +00001224 _NOEXCEPT_DEBUG_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value);
Eric Fiselier87a82492015-07-18 20:40:46 +00001225#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001226
Howard Hinnant43d99232010-09-21 17:32:39 +00001227 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001228 size_type max_bucket_count() const _NOEXCEPT
Eric Fiselier55b31b4e2016-11-23 01:18:56 +00001229 {return max_size(); }
Howard Hinnant3e519522010-05-11 19:42:16 +00001230 size_type bucket_size(size_type __n) const;
Howard Hinnant37141072011-06-04 18:54:24 +00001231 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001232 {
1233 size_type __bc = bucket_count();
1234 return __bc != 0 ? (float)size() / __bc : 0.f;
1235 }
Howard Hinnant37141072011-06-04 18:54:24 +00001236 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
Howard Hinnante5c13de2013-07-29 19:05:47 +00001237 {
1238 _LIBCPP_ASSERT(__mlf > 0,
1239 "unordered container::max_load_factor(lf) called with lf <= 0");
1240 max_load_factor() = _VSTD::max(__mlf, load_factor());
1241 }
Howard Hinnant3e519522010-05-11 19:42:16 +00001242
Howard Hinnantb24c8022013-07-23 22:01:58 +00001243 _LIBCPP_INLINE_VISIBILITY
1244 local_iterator
1245 begin(size_type __n)
1246 {
Howard Hinnante5c13de2013-07-29 19:05:47 +00001247 _LIBCPP_ASSERT(__n < bucket_count(),
1248 "unordered container::begin(n) called with n >= bucket_count()");
Howard Hinnantb24c8022013-07-23 22:01:58 +00001249#if _LIBCPP_DEBUG_LEVEL >= 2
1250 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1251#else
1252 return local_iterator(__bucket_list_[__n], __n, bucket_count());
1253#endif
1254 }
1255
1256 _LIBCPP_INLINE_VISIBILITY
1257 local_iterator
1258 end(size_type __n)
1259 {
Howard Hinnante5c13de2013-07-29 19:05:47 +00001260 _LIBCPP_ASSERT(__n < bucket_count(),
1261 "unordered container::end(n) called with n >= bucket_count()");
Howard Hinnantb24c8022013-07-23 22:01:58 +00001262#if _LIBCPP_DEBUG_LEVEL >= 2
1263 return local_iterator(nullptr, __n, bucket_count(), this);
1264#else
1265 return local_iterator(nullptr, __n, bucket_count());
1266#endif
1267 }
1268
1269 _LIBCPP_INLINE_VISIBILITY
1270 const_local_iterator
1271 cbegin(size_type __n) const
1272 {
Howard Hinnante5c13de2013-07-29 19:05:47 +00001273 _LIBCPP_ASSERT(__n < bucket_count(),
1274 "unordered container::cbegin(n) called with n >= bucket_count()");
Howard Hinnantb24c8022013-07-23 22:01:58 +00001275#if _LIBCPP_DEBUG_LEVEL >= 2
1276 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1277#else
1278 return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
1279#endif
1280 }
1281
1282 _LIBCPP_INLINE_VISIBILITY
1283 const_local_iterator
1284 cend(size_type __n) const
1285 {
Howard Hinnante5c13de2013-07-29 19:05:47 +00001286 _LIBCPP_ASSERT(__n < bucket_count(),
1287 "unordered container::cend(n) called with n >= bucket_count()");
Howard Hinnantb24c8022013-07-23 22:01:58 +00001288#if _LIBCPP_DEBUG_LEVEL >= 2
1289 return const_local_iterator(nullptr, __n, bucket_count(), this);
1290#else
1291 return const_local_iterator(nullptr, __n, bucket_count());
1292#endif
1293 }
1294
1295#if _LIBCPP_DEBUG_LEVEL >= 2
1296
1297 bool __dereferenceable(const const_iterator* __i) const;
1298 bool __decrementable(const const_iterator* __i) const;
1299 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1300 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1301
1302#endif // _LIBCPP_DEBUG_LEVEL >= 2
1303
Howard Hinnant3e519522010-05-11 19:42:16 +00001304private:
1305 void __rehash(size_type __n);
1306
Eric Fiselierfcd02212016-02-11 11:59:44 +00001307#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001308 template <class ..._Args>
Eric Fiselierfcd02212016-02-11 11:59:44 +00001309 __node_holder __construct_node(_Args&& ...__args);
1310
1311 template <class _First, class ..._Rest>
1312 __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
1313#else // _LIBCPP_CXX03_LANG
1314 __node_holder __construct_node(const __container_value_type& __v);
1315 __node_holder __construct_node_hash(size_t __hash, const __container_value_type& __v);
Howard Hinnant3e519522010-05-11 19:42:16 +00001316#endif
Eric Fiselierfcd02212016-02-11 11:59:44 +00001317
Howard Hinnant3e519522010-05-11 19:42:16 +00001318
Howard Hinnant43d99232010-09-21 17:32:39 +00001319 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001320 void __copy_assign_alloc(const __hash_table& __u)
1321 {__copy_assign_alloc(__u, integral_constant<bool,
1322 __node_traits::propagate_on_container_copy_assignment::value>());}
1323 void __copy_assign_alloc(const __hash_table& __u, true_type);
Howard Hinnant43d99232010-09-21 17:32:39 +00001324 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc2063662011-12-01 20:21:04 +00001325 void __copy_assign_alloc(const __hash_table&, false_type) {}
Howard Hinnant3e519522010-05-11 19:42:16 +00001326
Eric Fiselierfcd02212016-02-11 11:59:44 +00001327#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001328 void __move_assign(__hash_table& __u, false_type);
Howard Hinnant37141072011-06-04 18:54:24 +00001329 void __move_assign(__hash_table& __u, true_type)
1330 _NOEXCEPT_(
1331 is_nothrow_move_assignable<__node_allocator>::value &&
1332 is_nothrow_move_assignable<hasher>::value &&
1333 is_nothrow_move_assignable<key_equal>::value);
1334 _LIBCPP_INLINE_VISIBILITY
1335 void __move_assign_alloc(__hash_table& __u)
1336 _NOEXCEPT_(
1337 !__node_traits::propagate_on_container_move_assignment::value ||
1338 (is_nothrow_move_assignable<__pointer_allocator>::value &&
1339 is_nothrow_move_assignable<__node_allocator>::value))
Howard Hinnant3e519522010-05-11 19:42:16 +00001340 {__move_assign_alloc(__u, integral_constant<bool,
1341 __node_traits::propagate_on_container_move_assignment::value>());}
Howard Hinnant43d99232010-09-21 17:32:39 +00001342 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001343 void __move_assign_alloc(__hash_table& __u, true_type)
Howard Hinnant37141072011-06-04 18:54:24 +00001344 _NOEXCEPT_(
1345 is_nothrow_move_assignable<__pointer_allocator>::value &&
1346 is_nothrow_move_assignable<__node_allocator>::value)
Howard Hinnant3e519522010-05-11 19:42:16 +00001347 {
1348 __bucket_list_.get_deleter().__alloc() =
Howard Hinnantce48a112011-06-30 21:18:19 +00001349 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
1350 __node_alloc() = _VSTD::move(__u.__node_alloc());
Howard Hinnant3e519522010-05-11 19:42:16 +00001351 }
Howard Hinnant43d99232010-09-21 17:32:39 +00001352 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001353 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
Eric Fiselierfcd02212016-02-11 11:59:44 +00001354#endif // _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001355
Eric Fiseliercd71f442017-01-07 03:01:24 +00001356 void __deallocate_node(__next_pointer __np) _NOEXCEPT;
Eric Fiselier40492ba2016-07-23 20:36:55 +00001357 __next_pointer __detach() _NOEXCEPT;
Howard Hinnant307f8142013-06-22 15:21:29 +00001358
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +00001359 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1360 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
Howard Hinnant3e519522010-05-11 19:42:16 +00001361};
1362
1363template <class _Tp, class _Hash, class _Equal, class _Alloc>
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001364inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001365__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
Howard Hinnant37141072011-06-04 18:54:24 +00001366 _NOEXCEPT_(
1367 is_nothrow_default_constructible<__bucket_list>::value &&
1368 is_nothrow_default_constructible<__first_node>::value &&
Eric Fiseliere2e332a2015-12-16 00:53:04 +00001369 is_nothrow_default_constructible<__node_allocator>::value &&
Howard Hinnant37141072011-06-04 18:54:24 +00001370 is_nothrow_default_constructible<hasher>::value &&
1371 is_nothrow_default_constructible<key_equal>::value)
Howard Hinnant3e519522010-05-11 19:42:16 +00001372 : __p2_(0),
1373 __p3_(1.0f)
1374{
1375}
1376
1377template <class _Tp, class _Hash, class _Equal, class _Alloc>
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001378inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001379__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1380 const key_equal& __eql)
1381 : __bucket_list_(nullptr, __bucket_list_deleter()),
1382 __p1_(),
1383 __p2_(0, __hf),
1384 __p3_(1.0f, __eql)
1385{
1386}
1387
1388template <class _Tp, class _Hash, class _Equal, class _Alloc>
1389__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1390 const key_equal& __eql,
1391 const allocator_type& __a)
1392 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1393 __p1_(__node_allocator(__a)),
1394 __p2_(0, __hf),
1395 __p3_(1.0f, __eql)
1396{
1397}
1398
1399template <class _Tp, class _Hash, class _Equal, class _Alloc>
1400__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1401 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1402 __p1_(__node_allocator(__a)),
1403 __p2_(0),
1404 __p3_(1.0f)
1405{
1406}
1407
1408template <class _Tp, class _Hash, class _Equal, class _Alloc>
1409__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
1410 : __bucket_list_(nullptr,
1411 __bucket_list_deleter(allocator_traits<__pointer_allocator>::
1412 select_on_container_copy_construction(
1413 __u.__bucket_list_.get_deleter().__alloc()), 0)),
1414 __p1_(allocator_traits<__node_allocator>::
1415 select_on_container_copy_construction(__u.__node_alloc())),
1416 __p2_(0, __u.hash_function()),
1417 __p3_(__u.__p3_)
1418{
1419}
1420
1421template <class _Tp, class _Hash, class _Equal, class _Alloc>
1422__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
1423 const allocator_type& __a)
1424 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1425 __p1_(__node_allocator(__a)),
1426 __p2_(0, __u.hash_function()),
1427 __p3_(__u.__p3_)
1428{
1429}
1430
Eric Fiselierfcd02212016-02-11 11:59:44 +00001431#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001432
1433template <class _Tp, class _Hash, class _Equal, class _Alloc>
1434__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
Howard Hinnant37141072011-06-04 18:54:24 +00001435 _NOEXCEPT_(
1436 is_nothrow_move_constructible<__bucket_list>::value &&
1437 is_nothrow_move_constructible<__first_node>::value &&
Eric Fiseliere2e332a2015-12-16 00:53:04 +00001438 is_nothrow_move_constructible<__node_allocator>::value &&
Howard Hinnant37141072011-06-04 18:54:24 +00001439 is_nothrow_move_constructible<hasher>::value &&
1440 is_nothrow_move_constructible<key_equal>::value)
Howard Hinnantce48a112011-06-30 21:18:19 +00001441 : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
1442 __p1_(_VSTD::move(__u.__p1_)),
1443 __p2_(_VSTD::move(__u.__p2_)),
1444 __p3_(_VSTD::move(__u.__p3_))
Howard Hinnant3e519522010-05-11 19:42:16 +00001445{
1446 if (size() > 0)
1447 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001448 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1449 __p1_.first().__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001450 __u.__p1_.first().__next_ = nullptr;
1451 __u.size() = 0;
1452 }
1453}
1454
1455template <class _Tp, class _Hash, class _Equal, class _Alloc>
1456__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
1457 const allocator_type& __a)
1458 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1459 __p1_(__node_allocator(__a)),
Howard Hinnantce48a112011-06-30 21:18:19 +00001460 __p2_(0, _VSTD::move(__u.hash_function())),
1461 __p3_(_VSTD::move(__u.__p3_))
Howard Hinnant3e519522010-05-11 19:42:16 +00001462{
1463 if (__a == allocator_type(__u.__node_alloc()))
1464 {
1465 __bucket_list_.reset(__u.__bucket_list_.release());
1466 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1467 __u.__bucket_list_.get_deleter().size() = 0;
1468 if (__u.size() > 0)
1469 {
1470 __p1_.first().__next_ = __u.__p1_.first().__next_;
1471 __u.__p1_.first().__next_ = nullptr;
Eric Fiselier40492ba2016-07-23 20:36:55 +00001472 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1473 __p1_.first().__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001474 size() = __u.size();
1475 __u.size() = 0;
1476 }
1477 }
1478}
1479
Eric Fiselierfcd02212016-02-11 11:59:44 +00001480#endif // _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001481
1482template <class _Tp, class _Hash, class _Equal, class _Alloc>
1483__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
1484{
Marshall Clow3b8669e2016-06-30 22:05:45 +00001485 static_assert((is_copy_constructible<key_equal>::value),
1486 "Predicate must be copy-constructible.");
1487 static_assert((is_copy_constructible<hasher>::value),
1488 "Hasher must be copy-constructible.");
Eric Fiselier04333f92017-01-13 22:42:53 +00001489#ifndef _LIBCPP_CXX03_LANG
1490 static_assert(__diagnose_hash_table_helper<_Tp, _Hash, _Equal, _Alloc>::__trigger_diagnostics(), "");
1491#endif
Eric Fiseliercd71f442017-01-07 03:01:24 +00001492 __deallocate_node(__p1_.first().__next_);
Howard Hinnantb24c8022013-07-23 22:01:58 +00001493#if _LIBCPP_DEBUG_LEVEL >= 2
1494 __get_db()->__erase_c(this);
1495#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001496}
1497
1498template <class _Tp, class _Hash, class _Equal, class _Alloc>
1499void
1500__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
1501 const __hash_table& __u, true_type)
1502{
1503 if (__node_alloc() != __u.__node_alloc())
1504 {
1505 clear();
1506 __bucket_list_.reset();
1507 __bucket_list_.get_deleter().size() = 0;
1508 }
1509 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1510 __node_alloc() = __u.__node_alloc();
1511}
1512
1513template <class _Tp, class _Hash, class _Equal, class _Alloc>
1514__hash_table<_Tp, _Hash, _Equal, _Alloc>&
1515__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
1516{
1517 if (this != &__u)
1518 {
1519 __copy_assign_alloc(__u);
1520 hash_function() = __u.hash_function();
1521 key_eq() = __u.key_eq();
1522 max_load_factor() = __u.max_load_factor();
1523 __assign_multi(__u.begin(), __u.end());
1524 }
1525 return *this;
1526}
1527
1528template <class _Tp, class _Hash, class _Equal, class _Alloc>
1529void
Eric Fiseliercd71f442017-01-07 03:01:24 +00001530__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np)
Howard Hinnant37141072011-06-04 18:54:24 +00001531 _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001532{
1533 __node_allocator& __na = __node_alloc();
1534 while (__np != nullptr)
1535 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001536 __next_pointer __next = __np->__next_;
Howard Hinnantb24c8022013-07-23 22:01:58 +00001537#if _LIBCPP_DEBUG_LEVEL >= 2
1538 __c_node* __c = __get_db()->__find_c_and_lock(this);
1539 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1540 {
1541 --__p;
1542 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1543 if (__i->__node_ == __np)
1544 {
1545 (*__p)->__c_ = nullptr;
1546 if (--__c->end_ != __p)
1547 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1548 }
1549 }
1550 __get_db()->unlock();
1551#endif
Eric Fiselier40492ba2016-07-23 20:36:55 +00001552 __node_pointer __real_np = __np->__upcast();
1553 __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__value_));
1554 __node_traits::deallocate(__na, __real_np, 1);
Howard Hinnant3e519522010-05-11 19:42:16 +00001555 __np = __next;
1556 }
1557}
1558
1559template <class _Tp, class _Hash, class _Equal, class _Alloc>
Eric Fiselier40492ba2016-07-23 20:36:55 +00001560typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
Howard Hinnant37141072011-06-04 18:54:24 +00001561__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001562{
1563 size_type __bc = bucket_count();
1564 for (size_type __i = 0; __i < __bc; ++__i)
1565 __bucket_list_[__i] = nullptr;
1566 size() = 0;
Eric Fiselier40492ba2016-07-23 20:36:55 +00001567 __next_pointer __cache = __p1_.first().__next_;
Howard Hinnant3e519522010-05-11 19:42:16 +00001568 __p1_.first().__next_ = nullptr;
1569 return __cache;
1570}
1571
Eric Fiselierfcd02212016-02-11 11:59:44 +00001572#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001573
1574template <class _Tp, class _Hash, class _Equal, class _Alloc>
1575void
1576__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1577 __hash_table& __u, true_type)
Howard Hinnant37141072011-06-04 18:54:24 +00001578 _NOEXCEPT_(
1579 is_nothrow_move_assignable<__node_allocator>::value &&
1580 is_nothrow_move_assignable<hasher>::value &&
1581 is_nothrow_move_assignable<key_equal>::value)
Howard Hinnant3e519522010-05-11 19:42:16 +00001582{
1583 clear();
1584 __bucket_list_.reset(__u.__bucket_list_.release());
1585 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1586 __u.__bucket_list_.get_deleter().size() = 0;
1587 __move_assign_alloc(__u);
1588 size() = __u.size();
Howard Hinnantce48a112011-06-30 21:18:19 +00001589 hash_function() = _VSTD::move(__u.hash_function());
Howard Hinnant3e519522010-05-11 19:42:16 +00001590 max_load_factor() = __u.max_load_factor();
Howard Hinnantce48a112011-06-30 21:18:19 +00001591 key_eq() = _VSTD::move(__u.key_eq());
Howard Hinnant3e519522010-05-11 19:42:16 +00001592 __p1_.first().__next_ = __u.__p1_.first().__next_;
1593 if (size() > 0)
1594 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001595 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1596 __p1_.first().__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001597 __u.__p1_.first().__next_ = nullptr;
1598 __u.size() = 0;
1599 }
Howard Hinnantb24c8022013-07-23 22:01:58 +00001600#if _LIBCPP_DEBUG_LEVEL >= 2
1601 __get_db()->swap(this, &__u);
1602#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001603}
1604
1605template <class _Tp, class _Hash, class _Equal, class _Alloc>
1606void
1607__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1608 __hash_table& __u, false_type)
1609{
1610 if (__node_alloc() == __u.__node_alloc())
1611 __move_assign(__u, true_type());
1612 else
1613 {
Howard Hinnantce48a112011-06-30 21:18:19 +00001614 hash_function() = _VSTD::move(__u.hash_function());
1615 key_eq() = _VSTD::move(__u.key_eq());
Howard Hinnant3e519522010-05-11 19:42:16 +00001616 max_load_factor() = __u.max_load_factor();
1617 if (bucket_count() != 0)
1618 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001619 __next_pointer __cache = __detach();
Howard Hinnant3e519522010-05-11 19:42:16 +00001620#ifndef _LIBCPP_NO_EXCEPTIONS
1621 try
1622 {
Howard Hinnantb3371f62010-08-22 00:02:43 +00001623#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant3e519522010-05-11 19:42:16 +00001624 const_iterator __i = __u.begin();
1625 while (__cache != nullptr && __u.size() != 0)
1626 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001627 __cache->__upcast()->__value_ =
1628 _VSTD::move(__u.remove(__i++)->__value_);
1629 __next_pointer __next = __cache->__next_;
1630 __node_insert_multi(__cache->__upcast());
Howard Hinnant3e519522010-05-11 19:42:16 +00001631 __cache = __next;
1632 }
1633#ifndef _LIBCPP_NO_EXCEPTIONS
1634 }
1635 catch (...)
1636 {
Eric Fiseliercd71f442017-01-07 03:01:24 +00001637 __deallocate_node(__cache);
Howard Hinnant3e519522010-05-11 19:42:16 +00001638 throw;
1639 }
Howard Hinnantb3371f62010-08-22 00:02:43 +00001640#endif // _LIBCPP_NO_EXCEPTIONS
Eric Fiseliercd71f442017-01-07 03:01:24 +00001641 __deallocate_node(__cache);
Howard Hinnant3e519522010-05-11 19:42:16 +00001642 }
1643 const_iterator __i = __u.begin();
1644 while (__u.size() != 0)
1645 {
Eric Fiselierfcd02212016-02-11 11:59:44 +00001646 __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__value_));
Howard Hinnant3e519522010-05-11 19:42:16 +00001647 __node_insert_multi(__h.get());
1648 __h.release();
1649 }
1650 }
1651}
1652
1653template <class _Tp, class _Hash, class _Equal, class _Alloc>
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001654inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001655__hash_table<_Tp, _Hash, _Equal, _Alloc>&
1656__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
Howard Hinnant37141072011-06-04 18:54:24 +00001657 _NOEXCEPT_(
1658 __node_traits::propagate_on_container_move_assignment::value &&
1659 is_nothrow_move_assignable<__node_allocator>::value &&
1660 is_nothrow_move_assignable<hasher>::value &&
1661 is_nothrow_move_assignable<key_equal>::value)
Howard Hinnant3e519522010-05-11 19:42:16 +00001662{
1663 __move_assign(__u, integral_constant<bool,
1664 __node_traits::propagate_on_container_move_assignment::value>());
1665 return *this;
1666}
1667
Eric Fiselierfcd02212016-02-11 11:59:44 +00001668#endif // _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001669
1670template <class _Tp, class _Hash, class _Equal, class _Alloc>
1671template <class _InputIterator>
1672void
1673__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
1674 _InputIterator __last)
1675{
Eric Fiselierfcd02212016-02-11 11:59:44 +00001676 typedef iterator_traits<_InputIterator> _ITraits;
1677 typedef typename _ITraits::value_type _ItValueType;
1678 static_assert((is_same<_ItValueType, __container_value_type>::value),
1679 "__assign_unique may only be called with the containers value type");
1680
Howard Hinnant3e519522010-05-11 19:42:16 +00001681 if (bucket_count() != 0)
1682 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001683 __next_pointer __cache = __detach();
Howard Hinnant3e519522010-05-11 19:42:16 +00001684#ifndef _LIBCPP_NO_EXCEPTIONS
1685 try
1686 {
Howard Hinnantb3371f62010-08-22 00:02:43 +00001687#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant3e519522010-05-11 19:42:16 +00001688 for (; __cache != nullptr && __first != __last; ++__first)
1689 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001690 __cache->__upcast()->__value_ = *__first;
1691 __next_pointer __next = __cache->__next_;
1692 __node_insert_unique(__cache->__upcast());
Howard Hinnant3e519522010-05-11 19:42:16 +00001693 __cache = __next;
1694 }
1695#ifndef _LIBCPP_NO_EXCEPTIONS
1696 }
1697 catch (...)
1698 {
Eric Fiseliercd71f442017-01-07 03:01:24 +00001699 __deallocate_node(__cache);
Howard Hinnant3e519522010-05-11 19:42:16 +00001700 throw;
1701 }
Howard Hinnantb3371f62010-08-22 00:02:43 +00001702#endif // _LIBCPP_NO_EXCEPTIONS
Eric Fiseliercd71f442017-01-07 03:01:24 +00001703 __deallocate_node(__cache);
Howard Hinnant3e519522010-05-11 19:42:16 +00001704 }
1705 for (; __first != __last; ++__first)
1706 __insert_unique(*__first);
1707}
1708
1709template <class _Tp, class _Hash, class _Equal, class _Alloc>
1710template <class _InputIterator>
1711void
1712__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
1713 _InputIterator __last)
1714{
Eric Fiselierfcd02212016-02-11 11:59:44 +00001715 typedef iterator_traits<_InputIterator> _ITraits;
1716 typedef typename _ITraits::value_type _ItValueType;
1717 static_assert((is_same<_ItValueType, __container_value_type>::value ||
1718 is_same<_ItValueType, __node_value_type>::value),
1719 "__assign_multi may only be called with the containers value type"
1720 " or the nodes value type");
Howard Hinnant3e519522010-05-11 19:42:16 +00001721 if (bucket_count() != 0)
1722 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001723 __next_pointer __cache = __detach();
Howard Hinnant3e519522010-05-11 19:42:16 +00001724#ifndef _LIBCPP_NO_EXCEPTIONS
1725 try
1726 {
Howard Hinnantb3371f62010-08-22 00:02:43 +00001727#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant3e519522010-05-11 19:42:16 +00001728 for (; __cache != nullptr && __first != __last; ++__first)
1729 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001730 __cache->__upcast()->__value_ = *__first;
1731 __next_pointer __next = __cache->__next_;
1732 __node_insert_multi(__cache->__upcast());
Howard Hinnant3e519522010-05-11 19:42:16 +00001733 __cache = __next;
1734 }
1735#ifndef _LIBCPP_NO_EXCEPTIONS
1736 }
1737 catch (...)
1738 {
Eric Fiseliercd71f442017-01-07 03:01:24 +00001739 __deallocate_node(__cache);
Howard Hinnant3e519522010-05-11 19:42:16 +00001740 throw;
1741 }
Howard Hinnantb3371f62010-08-22 00:02:43 +00001742#endif // _LIBCPP_NO_EXCEPTIONS
Eric Fiseliercd71f442017-01-07 03:01:24 +00001743 __deallocate_node(__cache);
Howard Hinnant3e519522010-05-11 19:42:16 +00001744 }
1745 for (; __first != __last; ++__first)
Eric Fiselierfcd02212016-02-11 11:59:44 +00001746 __insert_multi(_NodeTypes::__get_value(*__first));
Howard Hinnant3e519522010-05-11 19:42:16 +00001747}
1748
1749template <class _Tp, class _Hash, class _Equal, class _Alloc>
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001750inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001751typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
Howard Hinnant37141072011-06-04 18:54:24 +00001752__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001753{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001754#if _LIBCPP_DEBUG_LEVEL >= 2
1755 return iterator(__p1_.first().__next_, this);
1756#else
Howard Hinnant3e519522010-05-11 19:42:16 +00001757 return iterator(__p1_.first().__next_);
Howard Hinnantb24c8022013-07-23 22:01:58 +00001758#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001759}
1760
1761template <class _Tp, class _Hash, class _Equal, class _Alloc>
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001762inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001763typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
Howard Hinnant37141072011-06-04 18:54:24 +00001764__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001765{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001766#if _LIBCPP_DEBUG_LEVEL >= 2
1767 return iterator(nullptr, this);
1768#else
Howard Hinnant3e519522010-05-11 19:42:16 +00001769 return iterator(nullptr);
Howard Hinnantb24c8022013-07-23 22:01:58 +00001770#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001771}
1772
1773template <class _Tp, class _Hash, class _Equal, class _Alloc>
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001774inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001775typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
Howard Hinnant37141072011-06-04 18:54:24 +00001776__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001777{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001778#if _LIBCPP_DEBUG_LEVEL >= 2
1779 return const_iterator(__p1_.first().__next_, this);
1780#else
Howard Hinnant3e519522010-05-11 19:42:16 +00001781 return const_iterator(__p1_.first().__next_);
Howard Hinnantb24c8022013-07-23 22:01:58 +00001782#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001783}
1784
1785template <class _Tp, class _Hash, class _Equal, class _Alloc>
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00001786inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001787typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
Howard Hinnant37141072011-06-04 18:54:24 +00001788__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001789{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001790#if _LIBCPP_DEBUG_LEVEL >= 2
1791 return const_iterator(nullptr, this);
1792#else
Howard Hinnant3e519522010-05-11 19:42:16 +00001793 return const_iterator(nullptr);
Howard Hinnantb24c8022013-07-23 22:01:58 +00001794#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001795}
1796
1797template <class _Tp, class _Hash, class _Equal, class _Alloc>
1798void
Howard Hinnant37141072011-06-04 18:54:24 +00001799__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001800{
1801 if (size() > 0)
1802 {
Eric Fiseliercd71f442017-01-07 03:01:24 +00001803 __deallocate_node(__p1_.first().__next_);
Howard Hinnant3e519522010-05-11 19:42:16 +00001804 __p1_.first().__next_ = nullptr;
1805 size_type __bc = bucket_count();
Howard Hinnant1f8da842011-07-05 14:14:17 +00001806 for (size_type __i = 0; __i < __bc; ++__i)
Howard Hinnant3e519522010-05-11 19:42:16 +00001807 __bucket_list_[__i] = nullptr;
1808 size() = 0;
1809 }
1810}
1811
1812template <class _Tp, class _Hash, class _Equal, class _Alloc>
1813pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1814__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
1815{
1816 __nd->__hash_ = hash_function()(__nd->__value_);
1817 size_type __bc = bucket_count();
1818 bool __inserted = false;
Eric Fiselier40492ba2016-07-23 20:36:55 +00001819 __next_pointer __ndptr;
Howard Hinnant3e519522010-05-11 19:42:16 +00001820 size_t __chash;
1821 if (__bc != 0)
1822 {
Howard Hinnant4cb38a82012-07-06 17:31:14 +00001823 __chash = __constrain_hash(__nd->__hash_, __bc);
Howard Hinnant3e519522010-05-11 19:42:16 +00001824 __ndptr = __bucket_list_[__chash];
1825 if (__ndptr != nullptr)
1826 {
1827 for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
Eric Fiselier40492ba2016-07-23 20:36:55 +00001828 __constrain_hash(__ndptr->__hash(), __bc) == __chash;
Howard Hinnant3e519522010-05-11 19:42:16 +00001829 __ndptr = __ndptr->__next_)
1830 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001831 if (key_eq()(__ndptr->__upcast()->__value_, __nd->__value_))
Howard Hinnant3e519522010-05-11 19:42:16 +00001832 goto __done;
1833 }
1834 }
1835 }
1836 {
1837 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1838 {
Eric Fiselier9ba5c112015-02-02 21:31:48 +00001839 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
Howard Hinnant3e519522010-05-11 19:42:16 +00001840 size_type(ceil(float(size() + 1) / max_load_factor()))));
1841 __bc = bucket_count();
Howard Hinnant4cb38a82012-07-06 17:31:14 +00001842 __chash = __constrain_hash(__nd->__hash_, __bc);
Howard Hinnant3e519522010-05-11 19:42:16 +00001843 }
1844 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
Eric Fiselier40492ba2016-07-23 20:36:55 +00001845 __next_pointer __pn = __bucket_list_[__chash];
Howard Hinnant3e519522010-05-11 19:42:16 +00001846 if (__pn == nullptr)
1847 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001848 __pn =__p1_.first().__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001849 __nd->__next_ = __pn->__next_;
Eric Fiselier40492ba2016-07-23 20:36:55 +00001850 __pn->__next_ = __nd->__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001851 // fix up __bucket_list_
1852 __bucket_list_[__chash] = __pn;
1853 if (__nd->__next_ != nullptr)
Eric Fiselier40492ba2016-07-23 20:36:55 +00001854 __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001855 }
1856 else
1857 {
1858 __nd->__next_ = __pn->__next_;
Eric Fiselier40492ba2016-07-23 20:36:55 +00001859 __pn->__next_ = __nd->__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001860 }
Eric Fiselier40492ba2016-07-23 20:36:55 +00001861 __ndptr = __nd->__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001862 // increment size
1863 ++size();
1864 __inserted = true;
1865 }
1866__done:
Howard Hinnantb24c8022013-07-23 22:01:58 +00001867#if _LIBCPP_DEBUG_LEVEL >= 2
1868 return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
1869#else
Howard Hinnant3e519522010-05-11 19:42:16 +00001870 return pair<iterator, bool>(iterator(__ndptr), __inserted);
Howard Hinnantb24c8022013-07-23 22:01:58 +00001871#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001872}
1873
1874template <class _Tp, class _Hash, class _Equal, class _Alloc>
1875typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1876__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
1877{
1878 __cp->__hash_ = hash_function()(__cp->__value_);
1879 size_type __bc = bucket_count();
1880 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1881 {
Eric Fiselier9ba5c112015-02-02 21:31:48 +00001882 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
Howard Hinnant3e519522010-05-11 19:42:16 +00001883 size_type(ceil(float(size() + 1) / max_load_factor()))));
1884 __bc = bucket_count();
1885 }
Howard Hinnant4cb38a82012-07-06 17:31:14 +00001886 size_t __chash = __constrain_hash(__cp->__hash_, __bc);
Eric Fiselier40492ba2016-07-23 20:36:55 +00001887 __next_pointer __pn = __bucket_list_[__chash];
Howard Hinnant3e519522010-05-11 19:42:16 +00001888 if (__pn == nullptr)
1889 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001890 __pn =__p1_.first().__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001891 __cp->__next_ = __pn->__next_;
Eric Fiselier40492ba2016-07-23 20:36:55 +00001892 __pn->__next_ = __cp->__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001893 // fix up __bucket_list_
1894 __bucket_list_[__chash] = __pn;
1895 if (__cp->__next_ != nullptr)
Eric Fiselier40492ba2016-07-23 20:36:55 +00001896 __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
1897 = __cp->__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001898 }
1899 else
1900 {
1901 for (bool __found = false; __pn->__next_ != nullptr &&
Eric Fiselier40492ba2016-07-23 20:36:55 +00001902 __constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
Howard Hinnant3e519522010-05-11 19:42:16 +00001903 __pn = __pn->__next_)
Howard Hinnantb3371f62010-08-22 00:02:43 +00001904 {
Howard Hinnant3e519522010-05-11 19:42:16 +00001905 // __found key_eq() action
1906 // false false loop
1907 // true true loop
1908 // false true set __found to true
1909 // true false break
Eric Fiselier40492ba2016-07-23 20:36:55 +00001910 if (__found != (__pn->__next_->__hash() == __cp->__hash_ &&
1911 key_eq()(__pn->__next_->__upcast()->__value_, __cp->__value_)))
Howard Hinnant3e519522010-05-11 19:42:16 +00001912 {
1913 if (!__found)
1914 __found = true;
1915 else
1916 break;
1917 }
1918 }
1919 __cp->__next_ = __pn->__next_;
Eric Fiselier40492ba2016-07-23 20:36:55 +00001920 __pn->__next_ = __cp->__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001921 if (__cp->__next_ != nullptr)
1922 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001923 size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc);
Howard Hinnant3e519522010-05-11 19:42:16 +00001924 if (__nhash != __chash)
Eric Fiselier40492ba2016-07-23 20:36:55 +00001925 __bucket_list_[__nhash] = __cp->__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00001926 }
1927 }
1928 ++size();
Howard Hinnantb24c8022013-07-23 22:01:58 +00001929#if _LIBCPP_DEBUG_LEVEL >= 2
Eric Fiselier40492ba2016-07-23 20:36:55 +00001930 return iterator(__cp->__ptr(), this);
Howard Hinnantb24c8022013-07-23 22:01:58 +00001931#else
Eric Fiselier40492ba2016-07-23 20:36:55 +00001932 return iterator(__cp->__ptr());
Howard Hinnantb24c8022013-07-23 22:01:58 +00001933#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001934}
1935
1936template <class _Tp, class _Hash, class _Equal, class _Alloc>
1937typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1938__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
1939 const_iterator __p, __node_pointer __cp)
1940{
Howard Hinnant2f51de52013-08-02 17:50:49 +00001941#if _LIBCPP_DEBUG_LEVEL >= 2
1942 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1943 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
1944 " referring to this unordered container");
1945#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001946 if (__p != end() && key_eq()(*__p, __cp->__value_))
1947 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00001948 __next_pointer __np = __p.__node_;
1949 __cp->__hash_ = __np->__hash();
Howard Hinnant3e519522010-05-11 19:42:16 +00001950 size_type __bc = bucket_count();
1951 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1952 {
Eric Fiselier9ba5c112015-02-02 21:31:48 +00001953 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
Howard Hinnant3e519522010-05-11 19:42:16 +00001954 size_type(ceil(float(size() + 1) / max_load_factor()))));
1955 __bc = bucket_count();
1956 }
Howard Hinnant4cb38a82012-07-06 17:31:14 +00001957 size_t __chash = __constrain_hash(__cp->__hash_, __bc);
Eric Fiselier40492ba2016-07-23 20:36:55 +00001958 __next_pointer __pp = __bucket_list_[__chash];
Howard Hinnant3e519522010-05-11 19:42:16 +00001959 while (__pp->__next_ != __np)
1960 __pp = __pp->__next_;
1961 __cp->__next_ = __np;
Eric Fiselier40492ba2016-07-23 20:36:55 +00001962 __pp->__next_ = static_cast<__next_pointer>(__cp);
Howard Hinnant3e519522010-05-11 19:42:16 +00001963 ++size();
Howard Hinnantb24c8022013-07-23 22:01:58 +00001964#if _LIBCPP_DEBUG_LEVEL >= 2
Eric Fiselier40492ba2016-07-23 20:36:55 +00001965 return iterator(static_cast<__next_pointer>(__cp), this);
Howard Hinnantb24c8022013-07-23 22:01:58 +00001966#else
Eric Fiselier40492ba2016-07-23 20:36:55 +00001967 return iterator(static_cast<__next_pointer>(__cp));
Howard Hinnantb24c8022013-07-23 22:01:58 +00001968#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001969 }
1970 return __node_insert_multi(__cp);
1971}
1972
Eric Fiselierde3f2b32015-06-13 07:18:32 +00001973
1974
Eric Fiselierfcd02212016-02-11 11:59:44 +00001975#ifndef _LIBCPP_CXX03_LANG
Eric Fiselierde3f2b32015-06-13 07:18:32 +00001976template <class _Tp, class _Hash, class _Equal, class _Alloc>
Eric Fiselierfcd02212016-02-11 11:59:44 +00001977template <class _Key, class ..._Args>
Eric Fiselierde3f2b32015-06-13 07:18:32 +00001978pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
Eric Fiselierfcd02212016-02-11 11:59:44 +00001979__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
Eric Fiselierde3f2b32015-06-13 07:18:32 +00001980#else
1981template <class _Tp, class _Hash, class _Equal, class _Alloc>
Eric Fiselierfcd02212016-02-11 11:59:44 +00001982template <class _Key, class _Args>
Eric Fiselierde3f2b32015-06-13 07:18:32 +00001983pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
Eric Fiselierfcd02212016-02-11 11:59:44 +00001984__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args& __args)
Eric Fiselierde3f2b32015-06-13 07:18:32 +00001985#endif
1986{
Eric Fiselierfcd02212016-02-11 11:59:44 +00001987
1988 size_t __hash = hash_function()(__k);
Howard Hinnant3e519522010-05-11 19:42:16 +00001989 size_type __bc = bucket_count();
1990 bool __inserted = false;
Eric Fiselier40492ba2016-07-23 20:36:55 +00001991 __next_pointer __nd;
Howard Hinnant3e519522010-05-11 19:42:16 +00001992 size_t __chash;
1993 if (__bc != 0)
1994 {
Howard Hinnant4cb38a82012-07-06 17:31:14 +00001995 __chash = __constrain_hash(__hash, __bc);
Howard Hinnant3e519522010-05-11 19:42:16 +00001996 __nd = __bucket_list_[__chash];
1997 if (__nd != nullptr)
1998 {
1999 for (__nd = __nd->__next_; __nd != nullptr &&
Eric Fiselier1a06fe52016-07-24 06:22:25 +00002000 (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash);
Howard Hinnant3e519522010-05-11 19:42:16 +00002001 __nd = __nd->__next_)
2002 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00002003 if (key_eq()(__nd->__upcast()->__value_, __k))
Howard Hinnant3e519522010-05-11 19:42:16 +00002004 goto __done;
2005 }
2006 }
2007 }
2008 {
Eric Fiselierfcd02212016-02-11 11:59:44 +00002009#ifndef _LIBCPP_CXX03_LANG
2010 __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
2011#else
2012 __node_holder __h = __construct_node_hash(__hash, __args);
2013#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00002014 if (size()+1 > __bc * max_load_factor() || __bc == 0)
2015 {
Eric Fiselier9ba5c112015-02-02 21:31:48 +00002016 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
Howard Hinnant3e519522010-05-11 19:42:16 +00002017 size_type(ceil(float(size() + 1) / max_load_factor()))));
2018 __bc = bucket_count();
Howard Hinnant4cb38a82012-07-06 17:31:14 +00002019 __chash = __constrain_hash(__hash, __bc);
Howard Hinnant3e519522010-05-11 19:42:16 +00002020 }
2021 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
Eric Fiselier40492ba2016-07-23 20:36:55 +00002022 __next_pointer __pn = __bucket_list_[__chash];
Howard Hinnant3e519522010-05-11 19:42:16 +00002023 if (__pn == nullptr)
2024 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00002025 __pn = __p1_.first().__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00002026 __h->__next_ = __pn->__next_;
Eric Fiselier40492ba2016-07-23 20:36:55 +00002027 __pn->__next_ = __h.get()->__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00002028 // fix up __bucket_list_
2029 __bucket_list_[__chash] = __pn;
2030 if (__h->__next_ != nullptr)
Eric Fiselier40492ba2016-07-23 20:36:55 +00002031 __bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)]
2032 = __h.get()->__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00002033 }
2034 else
2035 {
2036 __h->__next_ = __pn->__next_;
Eric Fiselier40492ba2016-07-23 20:36:55 +00002037 __pn->__next_ = static_cast<__next_pointer>(__h.get());
Howard Hinnant3e519522010-05-11 19:42:16 +00002038 }
Eric Fiselier40492ba2016-07-23 20:36:55 +00002039 __nd = static_cast<__next_pointer>(__h.release());
Howard Hinnant3e519522010-05-11 19:42:16 +00002040 // increment size
2041 ++size();
2042 __inserted = true;
2043 }
2044__done:
Howard Hinnantb24c8022013-07-23 22:01:58 +00002045#if _LIBCPP_DEBUG_LEVEL >= 2
2046 return pair<iterator, bool>(iterator(__nd, this), __inserted);
2047#else
Howard Hinnant3e519522010-05-11 19:42:16 +00002048 return pair<iterator, bool>(iterator(__nd), __inserted);
Howard Hinnantb24c8022013-07-23 22:01:58 +00002049#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00002050}
2051
Eric Fiselierfcd02212016-02-11 11:59:44 +00002052#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00002053
2054template <class _Tp, class _Hash, class _Equal, class _Alloc>
2055template <class... _Args>
2056pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
Duncan P. N. Exon Smithfde79b42016-03-17 20:45:20 +00002057__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args)
Howard Hinnant3e519522010-05-11 19:42:16 +00002058{
Howard Hinnantce48a112011-06-30 21:18:19 +00002059 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnant3e519522010-05-11 19:42:16 +00002060 pair<iterator, bool> __r = __node_insert_unique(__h.get());
2061 if (__r.second)
2062 __h.release();
2063 return __r;
2064}
2065
2066template <class _Tp, class _Hash, class _Equal, class _Alloc>
2067template <class... _Args>
2068typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2069__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
2070{
Howard Hinnantce48a112011-06-30 21:18:19 +00002071 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnant3e519522010-05-11 19:42:16 +00002072 iterator __r = __node_insert_multi(__h.get());
2073 __h.release();
2074 return __r;
2075}
2076
2077template <class _Tp, class _Hash, class _Equal, class _Alloc>
2078template <class... _Args>
2079typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2080__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
2081 const_iterator __p, _Args&&... __args)
2082{
Howard Hinnante5c13de2013-07-29 19:05:47 +00002083#if _LIBCPP_DEBUG_LEVEL >= 2
2084 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2085 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
2086 " referring to this unordered container");
2087#endif
Howard Hinnantce48a112011-06-30 21:18:19 +00002088 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnant3e519522010-05-11 19:42:16 +00002089 iterator __r = __node_insert_multi(__p, __h.get());
2090 __h.release();
2091 return __r;
2092}
2093
Eric Fiselierfcd02212016-02-11 11:59:44 +00002094#else // _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00002095
2096template <class _Tp, class _Hash, class _Equal, class _Alloc>
2097typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
Eric Fiselierfcd02212016-02-11 11:59:44 +00002098__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const __container_value_type& __x)
Howard Hinnant3e519522010-05-11 19:42:16 +00002099{
2100 __node_holder __h = __construct_node(__x);
2101 iterator __r = __node_insert_multi(__h.get());
2102 __h.release();
2103 return __r;
2104}
2105
2106template <class _Tp, class _Hash, class _Equal, class _Alloc>
2107typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2108__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
Eric Fiselierfcd02212016-02-11 11:59:44 +00002109 const __container_value_type& __x)
Howard Hinnant3e519522010-05-11 19:42:16 +00002110{
Howard Hinnante5c13de2013-07-29 19:05:47 +00002111#if _LIBCPP_DEBUG_LEVEL >= 2
2112 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2113 "unordered container::insert(const_iterator, lvalue) called with an iterator not"
2114 " referring to this unordered container");
2115#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00002116 __node_holder __h = __construct_node(__x);
2117 iterator __r = __node_insert_multi(__p, __h.get());
2118 __h.release();
2119 return __r;
2120}
2121
Eric Fiselierfcd02212016-02-11 11:59:44 +00002122#endif // _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00002123
2124template <class _Tp, class _Hash, class _Equal, class _Alloc>
2125void
2126__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
2127{
Howard Hinnant4cb38a82012-07-06 17:31:14 +00002128 if (__n == 1)
2129 __n = 2;
2130 else if (__n & (__n - 1))
2131 __n = __next_prime(__n);
Howard Hinnant3e519522010-05-11 19:42:16 +00002132 size_type __bc = bucket_count();
2133 if (__n > __bc)
2134 __rehash(__n);
Howard Hinnant4cb38a82012-07-06 17:31:14 +00002135 else if (__n < __bc)
Howard Hinnant3e519522010-05-11 19:42:16 +00002136 {
Howard Hinnantce48a112011-06-30 21:18:19 +00002137 __n = _VSTD::max<size_type>
Howard Hinnant3e519522010-05-11 19:42:16 +00002138 (
2139 __n,
Eric Fiselier9ba5c112015-02-02 21:31:48 +00002140 __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
2141 __next_prime(size_t(ceil(float(size()) / max_load_factor())))
Howard Hinnant3e519522010-05-11 19:42:16 +00002142 );
2143 if (__n < __bc)
2144 __rehash(__n);
2145 }
2146}
2147
2148template <class _Tp, class _Hash, class _Equal, class _Alloc>
2149void
2150__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
2151{
Howard Hinnantb24c8022013-07-23 22:01:58 +00002152#if _LIBCPP_DEBUG_LEVEL >= 2
2153 __get_db()->__invalidate_all(this);
2154#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant3e519522010-05-11 19:42:16 +00002155 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
2156 __bucket_list_.reset(__nbc > 0 ?
2157 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
2158 __bucket_list_.get_deleter().size() = __nbc;
2159 if (__nbc > 0)
2160 {
2161 for (size_type __i = 0; __i < __nbc; ++__i)
2162 __bucket_list_[__i] = nullptr;
Eric Fiselier40492ba2016-07-23 20:36:55 +00002163 __next_pointer __pp = __p1_.first().__ptr();
2164 __next_pointer __cp = __pp->__next_;
Howard Hinnant3e519522010-05-11 19:42:16 +00002165 if (__cp != nullptr)
2166 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00002167 size_type __chash = __constrain_hash(__cp->__hash(), __nbc);
Howard Hinnant3e519522010-05-11 19:42:16 +00002168 __bucket_list_[__chash] = __pp;
2169 size_type __phash = __chash;
2170 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr;
2171 __cp = __pp->__next_)
2172 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00002173 __chash = __constrain_hash(__cp->__hash(), __nbc);
Howard Hinnant3e519522010-05-11 19:42:16 +00002174 if (__chash == __phash)
2175 __pp = __cp;
2176 else
2177 {
2178 if (__bucket_list_[__chash] == nullptr)
2179 {
2180 __bucket_list_[__chash] = __pp;
2181 __pp = __cp;
2182 __phash = __chash;
2183 }
2184 else
2185 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00002186 __next_pointer __np = __cp;
Howard Hinnant3e519522010-05-11 19:42:16 +00002187 for (; __np->__next_ != nullptr &&
Eric Fiselier40492ba2016-07-23 20:36:55 +00002188 key_eq()(__cp->__upcast()->__value_,
2189 __np->__next_->__upcast()->__value_);
Howard Hinnant3e519522010-05-11 19:42:16 +00002190 __np = __np->__next_)
2191 ;
2192 __pp->__next_ = __np->__next_;
2193 __np->__next_ = __bucket_list_[__chash]->__next_;
2194 __bucket_list_[__chash]->__next_ = __cp;
Howard Hinnantb3371f62010-08-22 00:02:43 +00002195
Howard Hinnant3e519522010-05-11 19:42:16 +00002196 }
2197 }
2198 }
2199 }
2200 }
2201}
2202
2203template <class _Tp, class _Hash, class _Equal, class _Alloc>
2204template <class _Key>
2205typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2206__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
2207{
2208 size_t __hash = hash_function()(__k);
2209 size_type __bc = bucket_count();
2210 if (__bc != 0)
2211 {
Howard Hinnant4cb38a82012-07-06 17:31:14 +00002212 size_t __chash = __constrain_hash(__hash, __bc);
Eric Fiselier40492ba2016-07-23 20:36:55 +00002213 __next_pointer __nd = __bucket_list_[__chash];
Howard Hinnant3e519522010-05-11 19:42:16 +00002214 if (__nd != nullptr)
2215 {
2216 for (__nd = __nd->__next_; __nd != nullptr &&
Eric Fiselier40492ba2016-07-23 20:36:55 +00002217 (__nd->__hash() == __hash
2218 || __constrain_hash(__nd->__hash(), __bc) == __chash);
Howard Hinnant3e519522010-05-11 19:42:16 +00002219 __nd = __nd->__next_)
2220 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00002221 if ((__nd->__hash() == __hash)
2222 && key_eq()(__nd->__upcast()->__value_, __k))
Howard Hinnantb24c8022013-07-23 22:01:58 +00002223#if _LIBCPP_DEBUG_LEVEL >= 2
2224 return iterator(__nd, this);
2225#else
Howard Hinnant3e519522010-05-11 19:42:16 +00002226 return iterator(__nd);
Howard Hinnantb24c8022013-07-23 22:01:58 +00002227#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00002228 }
2229 }
2230 }
2231 return end();
2232}
2233
2234template <class _Tp, class _Hash, class _Equal, class _Alloc>
2235template <class _Key>
2236typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
2237__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
2238{
2239 size_t __hash = hash_function()(__k);
2240 size_type __bc = bucket_count();
2241 if (__bc != 0)
2242 {
Howard Hinnant4cb38a82012-07-06 17:31:14 +00002243 size_t __chash = __constrain_hash(__hash, __bc);
Eric Fiselier40492ba2016-07-23 20:36:55 +00002244 __next_pointer __nd = __bucket_list_[__chash];
Howard Hinnant3e519522010-05-11 19:42:16 +00002245 if (__nd != nullptr)
2246 {
2247 for (__nd = __nd->__next_; __nd != nullptr &&
Eric Fiselier40492ba2016-07-23 20:36:55 +00002248 (__hash == __nd->__hash()
2249 || __constrain_hash(__nd->__hash(), __bc) == __chash);
Howard Hinnant3e519522010-05-11 19:42:16 +00002250 __nd = __nd->__next_)
2251 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00002252 if ((__nd->__hash() == __hash)
2253 && key_eq()(__nd->__upcast()->__value_, __k))
Howard Hinnantb24c8022013-07-23 22:01:58 +00002254#if _LIBCPP_DEBUG_LEVEL >= 2
2255 return const_iterator(__nd, this);
2256#else
Howard Hinnant3e519522010-05-11 19:42:16 +00002257 return const_iterator(__nd);
Howard Hinnantb24c8022013-07-23 22:01:58 +00002258#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00002259 }
2260 }
Howard Hinnantb3371f62010-08-22 00:02:43 +00002261
Howard Hinnant3e519522010-05-11 19:42:16 +00002262 }
2263 return end();
2264}
2265
Eric Fiselierfcd02212016-02-11 11:59:44 +00002266#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00002267
2268template <class _Tp, class _Hash, class _Equal, class _Alloc>
2269template <class ..._Args>
2270typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2271__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
2272{
Eric Fiselierfcd02212016-02-11 11:59:44 +00002273 static_assert(!__is_hash_value_type<_Args...>::value,
2274 "Construct cannot be called with a hash value type");
Howard Hinnant3e519522010-05-11 19:42:16 +00002275 __node_allocator& __na = __node_alloc();
Howard Hinnantc003db12011-11-29 18:15:50 +00002276 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Eric Fiselierfcd02212016-02-11 11:59:44 +00002277 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
Howard Hinnant3e519522010-05-11 19:42:16 +00002278 __h.get_deleter().__value_constructed = true;
2279 __h->__hash_ = hash_function()(__h->__value_);
2280 __h->__next_ = nullptr;
2281 return __h;
2282}
2283
2284template <class _Tp, class _Hash, class _Equal, class _Alloc>
Eric Fiselierfcd02212016-02-11 11:59:44 +00002285template <class _First, class ..._Rest>
Howard Hinnant3e519522010-05-11 19:42:16 +00002286typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
Eric Fiselierfcd02212016-02-11 11:59:44 +00002287__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(
2288 size_t __hash, _First&& __f, _Rest&& ...__rest)
Howard Hinnant3e519522010-05-11 19:42:16 +00002289{
Eric Fiselierfcd02212016-02-11 11:59:44 +00002290 static_assert(!__is_hash_value_type<_First, _Rest...>::value,
2291 "Construct cannot be called with a hash value type");
Howard Hinnant3e519522010-05-11 19:42:16 +00002292 __node_allocator& __na = __node_alloc();
Howard Hinnantc003db12011-11-29 18:15:50 +00002293 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Eric Fiselierfcd02212016-02-11 11:59:44 +00002294 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_),
2295 _VSTD::forward<_First>(__f),
2296 _VSTD::forward<_Rest>(__rest)...);
Howard Hinnant3e519522010-05-11 19:42:16 +00002297 __h.get_deleter().__value_constructed = true;
2298 __h->__hash_ = __hash;
2299 __h->__next_ = nullptr;
Howard Hinnant179b1f82013-08-22 18:29:50 +00002300 return __h;
Howard Hinnant3e519522010-05-11 19:42:16 +00002301}
2302
Eric Fiselierfcd02212016-02-11 11:59:44 +00002303#else // _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00002304
2305template <class _Tp, class _Hash, class _Equal, class _Alloc>
2306typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
Eric Fiselierfcd02212016-02-11 11:59:44 +00002307__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const __container_value_type& __v)
Howard Hinnant3e519522010-05-11 19:42:16 +00002308{
2309 __node_allocator& __na = __node_alloc();
Howard Hinnantc003db12011-11-29 18:15:50 +00002310 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Eric Fiselierfcd02212016-02-11 11:59:44 +00002311 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v);
Howard Hinnant3e519522010-05-11 19:42:16 +00002312 __h.get_deleter().__value_constructed = true;
2313 __h->__hash_ = hash_function()(__h->__value_);
2314 __h->__next_ = nullptr;
Dimitry Andric251c6292015-08-19 06:43:33 +00002315 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
Howard Hinnant3e519522010-05-11 19:42:16 +00002316}
2317
Howard Hinnant3e519522010-05-11 19:42:16 +00002318template <class _Tp, class _Hash, class _Equal, class _Alloc>
2319typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
Eric Fiselierfcd02212016-02-11 11:59:44 +00002320__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash,
2321 const __container_value_type& __v)
Howard Hinnant3e519522010-05-11 19:42:16 +00002322{
2323 __node_allocator& __na = __node_alloc();
Howard Hinnantc003db12011-11-29 18:15:50 +00002324 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Eric Fiselierfcd02212016-02-11 11:59:44 +00002325 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v);
Howard Hinnant3e519522010-05-11 19:42:16 +00002326 __h.get_deleter().__value_constructed = true;
2327 __h->__hash_ = __hash;
2328 __h->__next_ = nullptr;
Dimitry Andric251c6292015-08-19 06:43:33 +00002329 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
Howard Hinnant3e519522010-05-11 19:42:16 +00002330}
2331
Eric Fiselierfcd02212016-02-11 11:59:44 +00002332#endif // _LIBCPP_CXX03_LANG
2333
Howard Hinnant3e519522010-05-11 19:42:16 +00002334template <class _Tp, class _Hash, class _Equal, class _Alloc>
2335typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2336__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
2337{
Eric Fiselier40492ba2016-07-23 20:36:55 +00002338 __next_pointer __np = __p.__node_;
Howard Hinnantb24c8022013-07-23 22:01:58 +00002339#if _LIBCPP_DEBUG_LEVEL >= 2
2340 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2341 "unordered container erase(iterator) called with an iterator not"
2342 " referring to this container");
2343 _LIBCPP_ASSERT(__p != end(),
2344 "unordered container erase(iterator) called with a non-dereferenceable iterator");
2345 iterator __r(__np, this);
2346#else
Howard Hinnant3e519522010-05-11 19:42:16 +00002347 iterator __r(__np);
Howard Hinnantb24c8022013-07-23 22:01:58 +00002348#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00002349 ++__r;
2350 remove(__p);
2351 return __r;
2352}
2353
2354template <class _Tp, class _Hash, class _Equal, class _Alloc>
2355typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2356__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
2357 const_iterator __last)
2358{
Howard Hinnantb24c8022013-07-23 22:01:58 +00002359#if _LIBCPP_DEBUG_LEVEL >= 2
2360 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
2361 "unodered container::erase(iterator, iterator) called with an iterator not"
2362 " referring to this unodered container");
2363 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
2364 "unodered container::erase(iterator, iterator) called with an iterator not"
2365 " referring to this unodered container");
2366#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00002367 for (const_iterator __p = __first; __first != __last; __p = __first)
2368 {
2369 ++__first;
2370 erase(__p);
2371 }
Eric Fiselier40492ba2016-07-23 20:36:55 +00002372 __next_pointer __np = __last.__node_;
Howard Hinnantb24c8022013-07-23 22:01:58 +00002373#if _LIBCPP_DEBUG_LEVEL >= 2
2374 return iterator (__np, this);
2375#else
Howard Hinnant3e519522010-05-11 19:42:16 +00002376 return iterator (__np);
Howard Hinnantb24c8022013-07-23 22:01:58 +00002377#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00002378}
2379
2380template <class _Tp, class _Hash, class _Equal, class _Alloc>
2381template <class _Key>
2382typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2383__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
2384{
2385 iterator __i = find(__k);
2386 if (__i == end())
2387 return 0;
2388 erase(__i);
2389 return 1;
2390}
2391
2392template <class _Tp, class _Hash, class _Equal, class _Alloc>
2393template <class _Key>
2394typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2395__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
2396{
2397 size_type __r = 0;
2398 iterator __i = find(__k);
2399 if (__i != end())
2400 {
2401 iterator __e = end();
2402 do
2403 {
2404 erase(__i++);
2405 ++__r;
2406 } while (__i != __e && key_eq()(*__i, __k));
2407 }
2408 return __r;
2409}
2410
2411template <class _Tp, class _Hash, class _Equal, class _Alloc>
2412typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
Howard Hinnant37141072011-06-04 18:54:24 +00002413__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00002414{
2415 // current node
Eric Fiselier40492ba2016-07-23 20:36:55 +00002416 __next_pointer __cn = __p.__node_;
Howard Hinnant3e519522010-05-11 19:42:16 +00002417 size_type __bc = bucket_count();
Eric Fiselier40492ba2016-07-23 20:36:55 +00002418 size_t __chash = __constrain_hash(__cn->__hash(), __bc);
Howard Hinnant3e519522010-05-11 19:42:16 +00002419 // find previous node
Eric Fiselier40492ba2016-07-23 20:36:55 +00002420 __next_pointer __pn = __bucket_list_[__chash];
Howard Hinnant3e519522010-05-11 19:42:16 +00002421 for (; __pn->__next_ != __cn; __pn = __pn->__next_)
2422 ;
2423 // Fix up __bucket_list_
2424 // if __pn is not in same bucket (before begin is not in same bucket) &&
2425 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
Eric Fiselier40492ba2016-07-23 20:36:55 +00002426 if (__pn == __p1_.first().__ptr()
2427 || __constrain_hash(__pn->__hash(), __bc) != __chash)
Howard Hinnant3e519522010-05-11 19:42:16 +00002428 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00002429 if (__cn->__next_ == nullptr
2430 || __constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
Howard Hinnant3e519522010-05-11 19:42:16 +00002431 __bucket_list_[__chash] = nullptr;
2432 }
2433 // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
2434 if (__cn->__next_ != nullptr)
2435 {
Eric Fiselier40492ba2016-07-23 20:36:55 +00002436 size_t __nhash = __constrain_hash(__cn->__next_->__hash(), __bc);
Howard Hinnant3e519522010-05-11 19:42:16 +00002437 if (__nhash != __chash)
2438 __bucket_list_[__nhash] = __pn;
2439 }
2440 // remove __cn
2441 __pn->__next_ = __cn->__next_;
2442 __cn->__next_ = nullptr;
2443 --size();
Howard Hinnantb24c8022013-07-23 22:01:58 +00002444#if _LIBCPP_DEBUG_LEVEL >= 2
2445 __c_node* __c = __get_db()->__find_c_and_lock(this);
Eric Fiselier780b51d2016-12-28 05:53:01 +00002446 for (__i_node** __dp = __c->end_; __dp != __c->beg_; )
Howard Hinnantb24c8022013-07-23 22:01:58 +00002447 {
Eric Fiselier780b51d2016-12-28 05:53:01 +00002448 --__dp;
2449 iterator* __i = static_cast<iterator*>((*__dp)->__i_);
Howard Hinnantb24c8022013-07-23 22:01:58 +00002450 if (__i->__node_ == __cn)
2451 {
Eric Fiselier780b51d2016-12-28 05:53:01 +00002452 (*__dp)->__c_ = nullptr;
2453 if (--__c->end_ != __dp)
2454 memmove(__dp, __dp+1, (__c->end_ - __dp)*sizeof(__i_node*));
Howard Hinnantb24c8022013-07-23 22:01:58 +00002455 }
2456 }
2457 __get_db()->unlock();
2458#endif
Eric Fiselier40492ba2016-07-23 20:36:55 +00002459 return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
Howard Hinnant3e519522010-05-11 19:42:16 +00002460}
2461
2462template <class _Tp, class _Hash, class _Equal, class _Alloc>
2463template <class _Key>
Evgeniy Stepanov906c8722015-11-07 01:22:13 +00002464inline
Howard Hinnant3e519522010-05-11 19:42:16 +00002465typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2466__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
2467{
2468 return static_cast<size_type>(find(__k) != end());
2469}
2470
2471template <class _Tp, class _Hash, class _Equal, class _Alloc>
2472template <class _Key>
2473typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2474__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
2475{
2476 size_type __r = 0;
2477 const_iterator __i = find(__k);
2478 if (__i != end())
2479 {
2480 const_iterator __e = end();
2481 do
2482 {
2483 ++__i;
2484 ++__r;
2485 } while (__i != __e && key_eq()(*__i, __k));
2486 }
2487 return __r;
2488}
2489
2490template <class _Tp, class _Hash, class _Equal, class _Alloc>
2491template <class _Key>
2492pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2493 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2494__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2495 const _Key& __k)
2496{
2497 iterator __i = find(__k);
2498 iterator __j = __i;
2499 if (__i != end())
2500 ++__j;
2501 return pair<iterator, iterator>(__i, __j);
2502}
2503
2504template <class _Tp, class _Hash, class _Equal, class _Alloc>
2505template <class _Key>
2506pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2507 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2508__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2509 const _Key& __k) const
2510{
2511 const_iterator __i = find(__k);
2512 const_iterator __j = __i;
2513 if (__i != end())
2514 ++__j;
2515 return pair<const_iterator, const_iterator>(__i, __j);
2516}
2517
2518template <class _Tp, class _Hash, class _Equal, class _Alloc>
2519template <class _Key>
2520pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2521 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2522__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2523 const _Key& __k)
2524{
2525 iterator __i = find(__k);
2526 iterator __j = __i;
2527 if (__i != end())
2528 {
2529 iterator __e = end();
2530 do
2531 {
2532 ++__j;
2533 } while (__j != __e && key_eq()(*__j, __k));
2534 }
2535 return pair<iterator, iterator>(__i, __j);
2536}
2537
2538template <class _Tp, class _Hash, class _Equal, class _Alloc>
2539template <class _Key>
2540pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2541 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2542__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2543 const _Key& __k) const
2544{
2545 const_iterator __i = find(__k);
2546 const_iterator __j = __i;
2547 if (__i != end())
2548 {
2549 const_iterator __e = end();
2550 do
2551 {
2552 ++__j;
2553 } while (__j != __e && key_eq()(*__j, __k));
2554 }
2555 return pair<const_iterator, const_iterator>(__i, __j);
2556}
2557
2558template <class _Tp, class _Hash, class _Equal, class _Alloc>
2559void
2560__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
Eric Fiselier87a82492015-07-18 20:40:46 +00002561#if _LIBCPP_STD_VER <= 11
Eric Fiselier780b51d2016-12-28 05:53:01 +00002562 _NOEXCEPT_DEBUG_(
Marshall Clowe3fbe142015-07-13 20:04:56 +00002563 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
Marshall Clowe3fbe142015-07-13 20:04:56 +00002564 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
2565 || __is_nothrow_swappable<__pointer_allocator>::value)
2566 && (!__node_traits::propagate_on_container_swap::value
2567 || __is_nothrow_swappable<__node_allocator>::value)
Marshall Clowe3fbe142015-07-13 20:04:56 +00002568 )
Eric Fiselier87a82492015-07-18 20:40:46 +00002569#else
Eric Fiselier780b51d2016-12-28 05:53:01 +00002570 _NOEXCEPT_DEBUG_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value)
Eric Fiselier87a82492015-07-18 20:40:46 +00002571#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00002572{
Eric Fiselier780b51d2016-12-28 05:53:01 +00002573 _LIBCPP_ASSERT(__node_traits::propagate_on_container_swap::value ||
2574 this->__node_alloc() == __u.__node_alloc(),
2575 "list::swap: Either propagate_on_container_swap must be true"
2576 " or the allocators must compare equal");
Howard Hinnant3e519522010-05-11 19:42:16 +00002577 {
2578 __node_pointer_pointer __npp = __bucket_list_.release();
2579 __bucket_list_.reset(__u.__bucket_list_.release());
2580 __u.__bucket_list_.reset(__npp);
2581 }
Howard Hinnantce48a112011-06-30 21:18:19 +00002582 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
Marshall Clowe3fbe142015-07-13 20:04:56 +00002583 __swap_allocator(__bucket_list_.get_deleter().__alloc(),
Howard Hinnant3e519522010-05-11 19:42:16 +00002584 __u.__bucket_list_.get_deleter().__alloc());
Marshall Clowe3fbe142015-07-13 20:04:56 +00002585 __swap_allocator(__node_alloc(), __u.__node_alloc());
Howard Hinnantce48a112011-06-30 21:18:19 +00002586 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
Howard Hinnant3e519522010-05-11 19:42:16 +00002587 __p2_.swap(__u.__p2_);
2588 __p3_.swap(__u.__p3_);
2589 if (size() > 0)
Eric Fiselier40492ba2016-07-23 20:36:55 +00002590 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
2591 __p1_.first().__ptr();
Howard Hinnant3e519522010-05-11 19:42:16 +00002592 if (__u.size() > 0)
Eric Fiselier40492ba2016-07-23 20:36:55 +00002593 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] =
2594 __u.__p1_.first().__ptr();
Howard Hinnantb24c8022013-07-23 22:01:58 +00002595#if _LIBCPP_DEBUG_LEVEL >= 2
2596 __get_db()->swap(this, &__u);
2597#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00002598}
2599
2600template <class _Tp, class _Hash, class _Equal, class _Alloc>
2601typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2602__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
2603{
Howard Hinnante5c13de2013-07-29 19:05:47 +00002604 _LIBCPP_ASSERT(__n < bucket_count(),
2605 "unordered container::bucket_size(n) called with n >= bucket_count()");
Eric Fiselier40492ba2016-07-23 20:36:55 +00002606 __next_pointer __np = __bucket_list_[__n];
Howard Hinnant3e519522010-05-11 19:42:16 +00002607 size_type __bc = bucket_count();
2608 size_type __r = 0;
2609 if (__np != nullptr)
2610 {
2611 for (__np = __np->__next_; __np != nullptr &&
Eric Fiselier40492ba2016-07-23 20:36:55 +00002612 __constrain_hash(__np->__hash(), __bc) == __n;
Howard Hinnant3e519522010-05-11 19:42:16 +00002613 __np = __np->__next_, ++__r)
2614 ;
2615 }
2616 return __r;
2617}
2618
Howard Hinnant37141072011-06-04 18:54:24 +00002619template <class _Tp, class _Hash, class _Equal, class _Alloc>
2620inline _LIBCPP_INLINE_VISIBILITY
2621void
2622swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
2623 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2624 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2625{
2626 __x.swap(__y);
2627}
2628
Howard Hinnantb24c8022013-07-23 22:01:58 +00002629#if _LIBCPP_DEBUG_LEVEL >= 2
2630
2631template <class _Tp, class _Hash, class _Equal, class _Alloc>
2632bool
2633__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const
2634{
2635 return __i->__node_ != nullptr;
2636}
2637
2638template <class _Tp, class _Hash, class _Equal, class _Alloc>
2639bool
2640__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const
2641{
2642 return false;
2643}
2644
2645template <class _Tp, class _Hash, class _Equal, class _Alloc>
2646bool
2647__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
2648{
2649 return false;
2650}
2651
2652template <class _Tp, class _Hash, class _Equal, class _Alloc>
2653bool
2654__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
2655{
2656 return false;
2657}
2658
2659#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant3e519522010-05-11 19:42:16 +00002660_LIBCPP_END_NAMESPACE_STD
2661
2662#endif // _LIBCPP__HASH_TABLE