codekingpro/portable-devtools
114k
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCUDACXX__HASH_TABLE11#define _LIBCUDACXX__HASH_TABLE12 13#include <__config>14#include <initializer_list>15#include <memory>16#include <iterator>17#include <algorithm>18#include <cmath>19#include <utility>20#include <type_traits>21 22#include "__assert" // all public C++ headers provide the assertion handler23#include "__debug"24 25#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)26# pragma GCC system_header27#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)28# pragma clang system_header29#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)30# pragma system_header31#endif // no system header32 33_LIBCUDACXX_PUSH_MACROS34#include <__undef_macros>35 36 37_LIBCUDACXX_BEGIN_NAMESPACE_STD38 39template <class _Key, class _Tp>40struct __hash_value_type;41 42template <class _Tp>43struct __is_hash_value_type_imp : false_type {};44 45template <class _Key, class _Value>46struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value>> : true_type {};47 48template <class ..._Args>49struct __is_hash_value_type : false_type {};50 51template <class _One>52struct __is_hash_value_type<_One> : __is_hash_value_type_imp<__remove_cvref_t<_One>> {};53 54_LIBCUDACXX_FUNC_VIS55size_t __next_prime(size_t __n);56 57template <class _NodePtr>58struct __hash_node_base59{60 typedef typename pointer_traits<_NodePtr>::element_type __node_type;61 typedef __hash_node_base __first_node;62 typedef typename __rebind_pointer<_NodePtr, __first_node>::type __node_base_pointer;63 typedef _NodePtr __node_pointer;64 65#if defined(_LIBCUDACXX_ABI_FIX_UNORDERED_NODE_POINTER_UB)66 typedef __node_base_pointer __next_pointer;67#else68 typedef typename conditional<69 is_pointer<__node_pointer>::value,70 __node_base_pointer,71 __node_pointer>::type __next_pointer;72#endif73 74 __next_pointer __next_;75 76 _LIBCUDACXX_INLINE_VISIBILITY77 __next_pointer __ptr() noexcept {78 return static_cast<__next_pointer>(79 pointer_traits<__node_base_pointer>::pointer_to(*this));80 }81 82 _LIBCUDACXX_INLINE_VISIBILITY83 __node_pointer __upcast() noexcept {84 return static_cast<__node_pointer>(85 pointer_traits<__node_base_pointer>::pointer_to(*this));86 }87 88 _LIBCUDACXX_INLINE_VISIBILITY89 size_t __hash() const noexcept {90 return static_cast<__node_type const&>(*this).__hash_;91 }92 93 _LIBCUDACXX_INLINE_VISIBILITY __hash_node_base() noexcept : __next_(nullptr) {}94};95 96template <class _Tp, class _VoidPtr>97struct __hash_node98 : public __hash_node_base99 <100 typename __rebind_pointer<_VoidPtr, __hash_node<_Tp, _VoidPtr> >::type101 >102{103 typedef _Tp __node_value_type;104 105 size_t __hash_;106 __node_value_type __value_;107};108 109inline _LIBCUDACXX_INLINE_VISIBILITY110bool111__is_hash_power2(size_t __bc)112{113 return __bc > 2 && !(__bc & (__bc - 1));114}115 116inline _LIBCUDACXX_INLINE_VISIBILITY117size_t118__constrain_hash(size_t __h, size_t __bc)119{120 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) :121 (__h < __bc ? __h : __h % __bc);122}123 124inline _LIBCUDACXX_INLINE_VISIBILITY125size_t126__next_hash_pow2(size_t __n)127{128 return __n < 2 ? __n : (size_t(1) << (std::numeric_limits<size_t>::digits - __libcpp_clz(__n-1)));129}130 131 132template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;133 134template <class _NodePtr> class _LIBCUDACXX_TEMPLATE_VIS __hash_iterator;135template <class _ConstNodePtr> class _LIBCUDACXX_TEMPLATE_VIS __hash_const_iterator;136template <class _NodePtr> class _LIBCUDACXX_TEMPLATE_VIS __hash_local_iterator;137template <class _ConstNodePtr> class _LIBCUDACXX_TEMPLATE_VIS __hash_const_local_iterator;138template <class _HashIterator> class _LIBCUDACXX_TEMPLATE_VIS __hash_map_iterator;139template <class _HashIterator> class _LIBCUDACXX_TEMPLATE_VIS __hash_map_const_iterator;140 141template <class _Tp>142struct __hash_key_value_types {143 static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");144 typedef _Tp key_type;145 typedef _Tp __node_value_type;146 typedef _Tp __container_value_type;147 static const bool __is_map = false;148 149 _LIBCUDACXX_INLINE_VISIBILITY150 static key_type const& __get_key(_Tp const& __v) {151 return __v;152 }153 _LIBCUDACXX_INLINE_VISIBILITY154 static __container_value_type const& __get_value(__node_value_type const& __v) {155 return __v;156 }157 _LIBCUDACXX_INLINE_VISIBILITY158 static __container_value_type* __get_ptr(__node_value_type& __n) {159 return _CUDA_VSTD::addressof(__n);160 }161 _LIBCUDACXX_INLINE_VISIBILITY162 static __container_value_type&& __move(__node_value_type& __v) {163 return _CUDA_VSTD::move(__v);164 }165};166 167template <class _Key, class _Tp>168struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {169 typedef _Key key_type;170 typedef _Tp mapped_type;171 typedef __hash_value_type<_Key, _Tp> __node_value_type;172 typedef pair<const _Key, _Tp> __container_value_type;173 typedef __container_value_type __map_value_type;174 static const bool __is_map = true;175 176 _LIBCUDACXX_INLINE_VISIBILITY177 static key_type const& __get_key(__container_value_type const& __v) {178 return __v.first;179 }180 181 template <class _Up>182 _LIBCUDACXX_INLINE_VISIBILITY183 static typename enable_if<__is_same_uncvref<_Up, __node_value_type>::value,184 __container_value_type const&>::type185 __get_value(_Up& __t) {186 return __t.__get_value();187 }188 189 template <class _Up>190 _LIBCUDACXX_INLINE_VISIBILITY191 static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,192 __container_value_type const&>::type193 __get_value(_Up& __t) {194 return __t;195 }196 197 _LIBCUDACXX_INLINE_VISIBILITY198 static __container_value_type* __get_ptr(__node_value_type& __n) {199 return _CUDA_VSTD::addressof(__n.__get_value());200 }201 _LIBCUDACXX_INLINE_VISIBILITY202 static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) {203 return __v.__move();204 }205};206 207template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>,208 bool = _KVTypes::__is_map>209struct __hash_map_pointer_types {};210 211template <class _Tp, class _AllocPtr, class _KVTypes>212struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {213 typedef typename _KVTypes::__map_value_type _Mv;214 typedef typename __rebind_pointer<_AllocPtr, _Mv>::type215 __map_value_type_pointer;216 typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type217 __const_map_value_type_pointer;218};219 220template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>221struct __hash_node_types;222 223template <class _NodePtr, class _Tp, class _VoidPtr>224struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >225 : public __hash_key_value_types<_Tp>, __hash_map_pointer_types<_Tp, _VoidPtr>226 227{228 typedef __hash_key_value_types<_Tp> __base;229 230public:231 typedef ptrdiff_t difference_type;232 typedef size_t size_type;233 234 typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer;235 236 typedef typename pointer_traits<_NodePtr>::element_type __node_type;237 typedef _NodePtr __node_pointer;238 239 typedef __hash_node_base<__node_pointer> __node_base_type;240 typedef typename __rebind_pointer<_NodePtr, __node_base_type>::type241 __node_base_pointer;242 243 typedef typename __node_base_type::__next_pointer __next_pointer;244 245 typedef _Tp __node_value_type;246 typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type247 __node_value_type_pointer;248 typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type249 __const_node_value_type_pointer;250 251private:252 static_assert(!is_const<__node_type>::value,253 "_NodePtr should never be a pointer to const");254 static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),255 "_VoidPtr does not point to unqualified void type");256 static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type,257 _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");258};259 260template <class _HashIterator>261struct __hash_node_types_from_iterator;262template <class _NodePtr>263struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};264template <class _NodePtr>265struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};266template <class _NodePtr>267struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};268template <class _NodePtr>269struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};270 271 272template <class _NodeValueTp, class _VoidPtr>273struct __make_hash_node_types {274 typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;275 typedef typename __rebind_pointer<_VoidPtr, _NodeTp>::type _NodePtr;276 typedef __hash_node_types<_NodePtr> type;277};278 279template <class _NodePtr>280class _LIBCUDACXX_TEMPLATE_VIS __hash_iterator281{282 typedef __hash_node_types<_NodePtr> _NodeTypes;283 typedef _NodePtr __node_pointer;284 typedef typename _NodeTypes::__next_pointer __next_pointer;285 286 __next_pointer __node_;287 288public:289 typedef forward_iterator_tag iterator_category;290 typedef typename _NodeTypes::__node_value_type value_type;291 typedef typename _NodeTypes::difference_type difference_type;292 typedef value_type& reference;293 typedef typename _NodeTypes::__node_value_type_pointer pointer;294 295 _LIBCUDACXX_INLINE_VISIBILITY __hash_iterator() noexcept : __node_(nullptr) {296#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE297 _LIBCUDACXX_DEBUG_MODE(__get_db()->__insert_i(this));298#endif299 }300 301#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE302 _LIBCUDACXX_INLINE_VISIBILITY303 __hash_iterator(const __hash_iterator& __i)304 : __node_(__i.__node_)305 {306 __get_db()->__iterator_copy(this, &__i);307 }308 309 _LIBCUDACXX_INLINE_VISIBILITY310 ~__hash_iterator()311 {312 __get_db()->__erase_i(this);313 }314 315 _LIBCUDACXX_INLINE_VISIBILITY316 __hash_iterator& operator=(const __hash_iterator& __i)317 {318 if (this != &__i)319 {320 __get_db()->__iterator_copy(this, &__i);321 __node_ = __i.__node_;322 }323 return *this;324 }325#endif // _LIBCUDACXX_ENABLE_DEBUG_MODE326 327 _LIBCUDACXX_INLINE_VISIBILITY328 reference operator*() const {329 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),330 "Attempted to dereference a non-dereferenceable unordered container iterator");331 return __node_->__upcast()->__value_;332 }333 334 _LIBCUDACXX_INLINE_VISIBILITY335 pointer operator->() const {336 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),337 "Attempted to dereference a non-dereferenceable unordered container iterator");338 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);339 }340 341 _LIBCUDACXX_INLINE_VISIBILITY342 __hash_iterator& operator++() {343 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),344 "Attempted to increment non-incrementable unordered container iterator");345 __node_ = __node_->__next_;346 return *this;347 }348 349 _LIBCUDACXX_INLINE_VISIBILITY350 __hash_iterator operator++(int)351 {352 __hash_iterator __t(*this);353 ++(*this);354 return __t;355 }356 357 friend _LIBCUDACXX_INLINE_VISIBILITY358 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)359 {360 return __x.__node_ == __y.__node_;361 }362 friend _LIBCUDACXX_INLINE_VISIBILITY363 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)364 {return !(__x == __y);}365 366private:367#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE368 _LIBCUDACXX_INLINE_VISIBILITY369 __hash_iterator(__next_pointer __node, const void* __c) noexcept370 : __node_(__node)371 {372 __get_db()->__insert_ic(this, __c);373 }374#else375 _LIBCUDACXX_INLINE_VISIBILITY376 __hash_iterator(__next_pointer __node) noexcept377 : __node_(__node)378 {}379#endif380 template <class, class, class, class> friend class __hash_table;381 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_const_iterator;382 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_map_iterator;383 template <class, class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS unordered_map;384 template <class, class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS unordered_multimap;385};386 387template <class _NodePtr>388class _LIBCUDACXX_TEMPLATE_VIS __hash_const_iterator389{390 static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");391 typedef __hash_node_types<_NodePtr> _NodeTypes;392 typedef _NodePtr __node_pointer;393 typedef typename _NodeTypes::__next_pointer __next_pointer;394 395 __next_pointer __node_;396 397public:398 typedef __hash_iterator<_NodePtr> __non_const_iterator;399 400 typedef forward_iterator_tag iterator_category;401 typedef typename _NodeTypes::__node_value_type value_type;402 typedef typename _NodeTypes::difference_type difference_type;403 typedef const value_type& reference;404 typedef typename _NodeTypes::__const_node_value_type_pointer pointer;405 406 407 _LIBCUDACXX_INLINE_VISIBILITY __hash_const_iterator() noexcept : __node_(nullptr) {408#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE409 _LIBCUDACXX_DEBUG_MODE(__get_db()->__insert_i(this));410#endif411 }412 413 _LIBCUDACXX_INLINE_VISIBILITY414 __hash_const_iterator(const __non_const_iterator& __x) noexcept415 : __node_(__x.__node_)416 {417#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE418 _LIBCUDACXX_DEBUG_MODE(__get_db()->__iterator_copy(this, &__x));419#endif420 }421 422#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE423 _LIBCUDACXX_INLINE_VISIBILITY424 __hash_const_iterator(const __hash_const_iterator& __i)425 : __node_(__i.__node_)426 {427 __get_db()->__iterator_copy(this, &__i);428 }429 430 _LIBCUDACXX_INLINE_VISIBILITY431 ~__hash_const_iterator()432 {433 __get_db()->__erase_i(this);434 }435 436 _LIBCUDACXX_INLINE_VISIBILITY437 __hash_const_iterator& operator=(const __hash_const_iterator& __i)438 {439 if (this != &__i)440 {441 __get_db()->__iterator_copy(this, &__i);442 __node_ = __i.__node_;443 }444 return *this;445 }446#endif // _LIBCUDACXX_ENABLE_DEBUG_MODE447 448 _LIBCUDACXX_INLINE_VISIBILITY449 reference operator*() const {450 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),451 "Attempted to dereference a non-dereferenceable unordered container const_iterator");452 return __node_->__upcast()->__value_;453 }454 _LIBCUDACXX_INLINE_VISIBILITY455 pointer operator->() const {456 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),457 "Attempted to dereference a non-dereferenceable unordered container const_iterator");458 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);459 }460 461 _LIBCUDACXX_INLINE_VISIBILITY462 __hash_const_iterator& operator++() {463 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),464 "Attempted to increment non-incrementable unordered container const_iterator");465 __node_ = __node_->__next_;466 return *this;467 }468 469 _LIBCUDACXX_INLINE_VISIBILITY470 __hash_const_iterator operator++(int)471 {472 __hash_const_iterator __t(*this);473 ++(*this);474 return __t;475 }476 477 friend _LIBCUDACXX_INLINE_VISIBILITY478 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)479 {480 return __x.__node_ == __y.__node_;481 }482 friend _LIBCUDACXX_INLINE_VISIBILITY483 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)484 {return !(__x == __y);}485 486private:487#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE488 _LIBCUDACXX_INLINE_VISIBILITY489 __hash_const_iterator(__next_pointer __node, const void* __c) noexcept490 : __node_(__node)491 {492 __get_db()->__insert_ic(this, __c);493 }494#else495 _LIBCUDACXX_INLINE_VISIBILITY496 __hash_const_iterator(__next_pointer __node) noexcept497 : __node_(__node)498 {}499#endif500 template <class, class, class, class> friend class __hash_table;501 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_map_const_iterator;502 template <class, class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS unordered_map;503 template <class, class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS unordered_multimap;504};505 506template <class _NodePtr>507class _LIBCUDACXX_TEMPLATE_VIS __hash_local_iterator508{509 typedef __hash_node_types<_NodePtr> _NodeTypes;510 typedef _NodePtr __node_pointer;511 typedef typename _NodeTypes::__next_pointer __next_pointer;512 513 __next_pointer __node_;514 size_t __bucket_;515 size_t __bucket_count_;516 517public:518 typedef forward_iterator_tag iterator_category;519 typedef typename _NodeTypes::__node_value_type value_type;520 typedef typename _NodeTypes::difference_type difference_type;521 typedef value_type& reference;522 typedef typename _NodeTypes::__node_value_type_pointer pointer;523 524 _LIBCUDACXX_INLINE_VISIBILITY __hash_local_iterator() noexcept : __node_(nullptr) {525#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE526 _LIBCUDACXX_DEBUG_MODE(__get_db()->__insert_i(this));527#endif528 }529 530#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE531 _LIBCUDACXX_INLINE_VISIBILITY532 __hash_local_iterator(const __hash_local_iterator& __i)533 : __node_(__i.__node_),534 __bucket_(__i.__bucket_),535 __bucket_count_(__i.__bucket_count_)536 {537 __get_db()->__iterator_copy(this, &__i);538 }539 540 _LIBCUDACXX_INLINE_VISIBILITY541 ~__hash_local_iterator()542 {543 __get_db()->__erase_i(this);544 }545 546 _LIBCUDACXX_INLINE_VISIBILITY547 __hash_local_iterator& operator=(const __hash_local_iterator& __i)548 {549 if (this != &__i)550 {551 __get_db()->__iterator_copy(this, &__i);552 __node_ = __i.__node_;553 __bucket_ = __i.__bucket_;554 __bucket_count_ = __i.__bucket_count_;555 }556 return *this;557 }558#endif // _LIBCUDACXX_ENABLE_DEBUG_MODE559 560 _LIBCUDACXX_INLINE_VISIBILITY561 reference operator*() const {562 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),563 "Attempted to dereference a non-dereferenceable unordered container local_iterator");564 return __node_->__upcast()->__value_;565 }566 567 _LIBCUDACXX_INLINE_VISIBILITY568 pointer operator->() const {569 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),570 "Attempted to dereference a non-dereferenceable unordered container local_iterator");571 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);572 }573 574 _LIBCUDACXX_INLINE_VISIBILITY575 __hash_local_iterator& operator++() {576 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),577 "Attempted to increment non-incrementable unordered container local_iterator");578 __node_ = __node_->__next_;579 if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)580 __node_ = nullptr;581 return *this;582 }583 584 _LIBCUDACXX_INLINE_VISIBILITY585 __hash_local_iterator operator++(int)586 {587 __hash_local_iterator __t(*this);588 ++(*this);589 return __t;590 }591 592 friend _LIBCUDACXX_INLINE_VISIBILITY593 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)594 {595 return __x.__node_ == __y.__node_;596 }597 friend _LIBCUDACXX_INLINE_VISIBILITY598 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)599 {return !(__x == __y);}600 601private:602#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE603 _LIBCUDACXX_INLINE_VISIBILITY604 __hash_local_iterator(__next_pointer __node, size_t __bucket,605 size_t __bucket_count, const void* __c) noexcept606 : __node_(__node),607 __bucket_(__bucket),608 __bucket_count_(__bucket_count)609 {610 __get_db()->__insert_ic(this, __c);611 if (__node_ != nullptr)612 __node_ = __node_->__next_;613 }614#else615 _LIBCUDACXX_INLINE_VISIBILITY616 __hash_local_iterator(__next_pointer __node, size_t __bucket,617 size_t __bucket_count) noexcept618 : __node_(__node),619 __bucket_(__bucket),620 __bucket_count_(__bucket_count)621 {622 if (__node_ != nullptr)623 __node_ = __node_->__next_;624 }625#endif626 template <class, class, class, class> friend class __hash_table;627 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_const_local_iterator;628 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_map_iterator;629};630 631template <class _ConstNodePtr>632class _LIBCUDACXX_TEMPLATE_VIS __hash_const_local_iterator633{634 typedef __hash_node_types<_ConstNodePtr> _NodeTypes;635 typedef _ConstNodePtr __node_pointer;636 typedef typename _NodeTypes::__next_pointer __next_pointer;637 638 __next_pointer __node_;639 size_t __bucket_;640 size_t __bucket_count_;641 642 typedef pointer_traits<__node_pointer> __pointer_traits;643 typedef typename __pointer_traits::element_type __node;644 typedef __remove_const_t<__node> __non_const_node;645 typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type646 __non_const_node_pointer;647public:648 typedef __hash_local_iterator<__non_const_node_pointer>649 __non_const_iterator;650 651 typedef forward_iterator_tag iterator_category;652 typedef typename _NodeTypes::__node_value_type value_type;653 typedef typename _NodeTypes::difference_type difference_type;654 typedef const value_type& reference;655 typedef typename _NodeTypes::__const_node_value_type_pointer pointer;656 657 658 _LIBCUDACXX_INLINE_VISIBILITY __hash_const_local_iterator() noexcept : __node_(nullptr) {659#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE660 _LIBCUDACXX_DEBUG_MODE(__get_db()->__insert_i(this));661#endif662 }663 664 _LIBCUDACXX_INLINE_VISIBILITY665 __hash_const_local_iterator(const __non_const_iterator& __x) noexcept666 : __node_(__x.__node_),667 __bucket_(__x.__bucket_),668 __bucket_count_(__x.__bucket_count_)669 {670#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE671 _LIBCUDACXX_DEBUG_MODE(__get_db()->__iterator_copy(this, &__x));672#endif673 }674 675#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE676 _LIBCUDACXX_INLINE_VISIBILITY677 __hash_const_local_iterator(const __hash_const_local_iterator& __i)678 : __node_(__i.__node_),679 __bucket_(__i.__bucket_),680 __bucket_count_(__i.__bucket_count_)681 {682 __get_db()->__iterator_copy(this, &__i);683 }684 685 _LIBCUDACXX_INLINE_VISIBILITY686 ~__hash_const_local_iterator()687 {688 __get_db()->__erase_i(this);689 }690 691 _LIBCUDACXX_INLINE_VISIBILITY692 __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i)693 {694 if (this != &__i)695 {696 __get_db()->__iterator_copy(this, &__i);697 __node_ = __i.__node_;698 __bucket_ = __i.__bucket_;699 __bucket_count_ = __i.__bucket_count_;700 }701 return *this;702 }703#endif // _LIBCUDACXX_ENABLE_DEBUG_MODE704 705 _LIBCUDACXX_INLINE_VISIBILITY706 reference operator*() const {707 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),708 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");709 return __node_->__upcast()->__value_;710 }711 712 _LIBCUDACXX_INLINE_VISIBILITY713 pointer operator->() const {714 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),715 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");716 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);717 }718 719 _LIBCUDACXX_INLINE_VISIBILITY720 __hash_const_local_iterator& operator++() {721 _LIBCUDACXX_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),722 "Attempted to increment non-incrementable unordered container const_local_iterator");723 __node_ = __node_->__next_;724 if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)725 __node_ = nullptr;726 return *this;727 }728 729 _LIBCUDACXX_INLINE_VISIBILITY730 __hash_const_local_iterator operator++(int)731 {732 __hash_const_local_iterator __t(*this);733 ++(*this);734 return __t;735 }736 737 friend _LIBCUDACXX_INLINE_VISIBILITY738 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)739 {740 return __x.__node_ == __y.__node_;741 }742 friend _LIBCUDACXX_INLINE_VISIBILITY743 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)744 {return !(__x == __y);}745 746private:747#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE748 _LIBCUDACXX_INLINE_VISIBILITY749 __hash_const_local_iterator(__next_pointer __node, size_t __bucket,750 size_t __bucket_count, const void* __c) noexcept751 : __node_(__node),752 __bucket_(__bucket),753 __bucket_count_(__bucket_count)754 {755 __get_db()->__insert_ic(this, __c);756 if (__node_ != nullptr)757 __node_ = __node_->__next_;758 }759#else760 _LIBCUDACXX_INLINE_VISIBILITY761 __hash_const_local_iterator(__next_pointer __node, size_t __bucket,762 size_t __bucket_count) noexcept763 : __node_(__node),764 __bucket_(__bucket),765 __bucket_count_(__bucket_count)766 {767 if (__node_ != nullptr)768 __node_ = __node_->__next_;769 }770#endif771 template <class, class, class, class> friend class __hash_table;772 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_map_const_iterator;773};774 775template <class _Alloc>776class __bucket_list_deallocator777{778 typedef _Alloc allocator_type;779 typedef allocator_traits<allocator_type> __alloc_traits;780 typedef typename __alloc_traits::size_type size_type;781 782 __compressed_pair<size_type, allocator_type> __data_;783public:784 typedef typename __alloc_traits::pointer pointer;785 786 _LIBCUDACXX_INLINE_VISIBILITY787 __bucket_list_deallocator()788 noexcept(is_nothrow_default_constructible<allocator_type>::value)789 : __data_(0) {}790 791 _LIBCUDACXX_INLINE_VISIBILITY792 __bucket_list_deallocator(const allocator_type& __a, size_type __size)793 noexcept(is_nothrow_copy_constructible<allocator_type>::value)794 : __data_(__size, __a) {}795 796 _LIBCUDACXX_INLINE_VISIBILITY797 __bucket_list_deallocator(__bucket_list_deallocator&& __x)798 noexcept(is_nothrow_move_constructible<allocator_type>::value)799 : __data_(_CUDA_VSTD::move(__x.__data_))800 {801 __x.size() = 0;802 }803 804 _LIBCUDACXX_INLINE_VISIBILITY805 size_type& size() noexcept {return __data_.first();}806 _LIBCUDACXX_INLINE_VISIBILITY807 size_type size() const noexcept {return __data_.first();}808 809 _LIBCUDACXX_INLINE_VISIBILITY810 allocator_type& __alloc() noexcept {return __data_.second();}811 _LIBCUDACXX_INLINE_VISIBILITY812 const allocator_type& __alloc() const noexcept {return __data_.second();}813 814 _LIBCUDACXX_INLINE_VISIBILITY815 void operator()(pointer __p) noexcept816 {817 __alloc_traits::deallocate(__alloc(), __p, size());818 }819};820 821template <class _Alloc> class __hash_map_node_destructor;822 823template <class _Alloc>824class __hash_node_destructor825{826 typedef _Alloc allocator_type;827 typedef allocator_traits<allocator_type> __alloc_traits;828 829public:830 typedef typename __alloc_traits::pointer pointer;831private:832 typedef __hash_node_types<pointer> _NodeTypes;833 834 allocator_type& __na_;835 836public:837 bool __value_constructed;838 839 __hash_node_destructor(__hash_node_destructor const&) = default;840 __hash_node_destructor& operator=(const __hash_node_destructor&) = delete;841 842 _LIBCUDACXX_INLINE_VISIBILITY843 explicit __hash_node_destructor(allocator_type& __na,844 bool __constructed = false) noexcept845 : __na_(__na),846 __value_constructed(__constructed)847 {}848 849 _LIBCUDACXX_INLINE_VISIBILITY850 void operator()(pointer __p) noexcept851 {852 if (__value_constructed)853 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));854 if (__p)855 __alloc_traits::deallocate(__na_, __p, 1);856 }857 858 template <class> friend class __hash_map_node_destructor;859};860 861#if _LIBCUDACXX_STD_VER > 14862template <class _NodeType, class _Alloc>863struct __generic_container_node_destructor;864 865template <class _Tp, class _VoidPtr, class _Alloc>866struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc>867 : __hash_node_destructor<_Alloc>868{869 using __hash_node_destructor<_Alloc>::__hash_node_destructor;870};871#endif872 873template <class _Key, class _Hash, class _Equal>874struct __enforce_unordered_container_requirements {875 static_assert(__check_hash_requirements<_Key, _Hash>::value,876 "the specified hash does not meet the Hash requirements");877 static_assert(is_copy_constructible<_Equal>::value,878 "the specified comparator is required to be copy constructible");879 typedef int type;880};881 882template <class _Key, class _Hash, class _Equal>883 _LIBCUDACXX_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value,884 "the specified comparator type does not provide a viable const call operator")885 _LIBCUDACXX_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value,886 "the specified hash functor does not provide a viable const call operator")887typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type888__diagnose_unordered_container_requirements(int);889 890// This dummy overload is used so that the compiler won't emit a spurious891// "no matching function for call to __diagnose_unordered_xxx" diagnostic892// when the overload above causes a hard error.893template <class _Key, class _Hash, class _Equal>894int __diagnose_unordered_container_requirements(void*);895 896template <class _Tp, class _Hash, class _Equal, class _Alloc>897class __hash_table898{899public:900 typedef _Tp value_type;901 typedef _Hash hasher;902 typedef _Equal key_equal;903 typedef _Alloc allocator_type;904 905private:906 typedef allocator_traits<allocator_type> __alloc_traits;907 typedef typename908 __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type909 _NodeTypes;910public:911 912 typedef typename _NodeTypes::__node_value_type __node_value_type;913 typedef typename _NodeTypes::__container_value_type __container_value_type;914 typedef typename _NodeTypes::key_type key_type;915 typedef value_type& reference;916 typedef const value_type& const_reference;917 typedef typename __alloc_traits::pointer pointer;918 typedef typename __alloc_traits::const_pointer const_pointer;919#ifndef _LIBCUDACXX_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE920 typedef typename __alloc_traits::size_type size_type;921#else922 typedef typename _NodeTypes::size_type size_type;923#endif924 typedef typename _NodeTypes::difference_type difference_type;925public:926 // Create __node927 928 typedef typename _NodeTypes::__node_type __node;929 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;930 typedef allocator_traits<__node_allocator> __node_traits;931 typedef typename _NodeTypes::__void_pointer __void_pointer;932 typedef typename _NodeTypes::__node_pointer __node_pointer;933 typedef typename _NodeTypes::__node_pointer __node_const_pointer;934 typedef typename _NodeTypes::__node_base_type __first_node;935 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;936 typedef typename _NodeTypes::__next_pointer __next_pointer;937 938private:939 // check for sane allocator pointer rebinding semantics. Rebinding the940 // allocator for a new pointer type should be exactly the same as rebinding941 // the pointer using 'pointer_traits'.942 static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value),943 "Allocator does not rebind pointers in a sane manner.");944 typedef typename __rebind_alloc_helper<__node_traits, __first_node>::type945 __node_base_allocator;946 typedef allocator_traits<__node_base_allocator> __node_base_traits;947 static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value),948 "Allocator does not rebind pointers in a sane manner.");949 950private:951 952 typedef typename __rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator;953 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;954 typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;955 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;956 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;957 958 // --- Member data begin ---959 __bucket_list __bucket_list_;960 __compressed_pair<__first_node, __node_allocator> __p1_;961 __compressed_pair<size_type, hasher> __p2_;962 __compressed_pair<float, key_equal> __p3_;963 // --- Member data end ---964 965 _LIBCUDACXX_INLINE_VISIBILITY966 size_type& size() noexcept {return __p2_.first();}967public:968 _LIBCUDACXX_INLINE_VISIBILITY969 size_type size() const noexcept {return __p2_.first();}970 971 _LIBCUDACXX_INLINE_VISIBILITY972 hasher& hash_function() noexcept {return __p2_.second();}973 _LIBCUDACXX_INLINE_VISIBILITY974 const hasher& hash_function() const noexcept {return __p2_.second();}975 976 _LIBCUDACXX_INLINE_VISIBILITY977 float& max_load_factor() noexcept {return __p3_.first();}978 _LIBCUDACXX_INLINE_VISIBILITY979 float max_load_factor() const noexcept {return __p3_.first();}980 981 _LIBCUDACXX_INLINE_VISIBILITY982 key_equal& key_eq() noexcept {return __p3_.second();}983 _LIBCUDACXX_INLINE_VISIBILITY984 const key_equal& key_eq() const noexcept {return __p3_.second();}985 986 _LIBCUDACXX_INLINE_VISIBILITY987 __node_allocator& __node_alloc() noexcept {return __p1_.second();}988 _LIBCUDACXX_INLINE_VISIBILITY989 const __node_allocator& __node_alloc() const noexcept990 {return __p1_.second();}991 992public:993 typedef __hash_iterator<__node_pointer> iterator;994 typedef __hash_const_iterator<__node_pointer> const_iterator;995 typedef __hash_local_iterator<__node_pointer> local_iterator;996 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;997 998 _LIBCUDACXX_INLINE_VISIBILITY999 __hash_table()1000 noexcept(1001 is_nothrow_default_constructible<__bucket_list>::value &&1002 is_nothrow_default_constructible<__first_node>::value &&1003 is_nothrow_default_constructible<__node_allocator>::value &&1004 is_nothrow_default_constructible<hasher>::value &&1005 is_nothrow_default_constructible<key_equal>::value);1006 _LIBCUDACXX_INLINE_VISIBILITY1007 __hash_table(const hasher& __hf, const key_equal& __eql);1008 __hash_table(const hasher& __hf, const key_equal& __eql,1009 const allocator_type& __a);1010 explicit __hash_table(const allocator_type& __a);1011 __hash_table(const __hash_table& __u);1012 __hash_table(const __hash_table& __u, const allocator_type& __a);1013 __hash_table(__hash_table&& __u)1014 noexcept(1015 is_nothrow_move_constructible<__bucket_list>::value &&1016 is_nothrow_move_constructible<__first_node>::value &&1017 is_nothrow_move_constructible<__node_allocator>::value &&1018 is_nothrow_move_constructible<hasher>::value &&1019 is_nothrow_move_constructible<key_equal>::value);1020 __hash_table(__hash_table&& __u, const allocator_type& __a);1021 ~__hash_table();1022 1023 __hash_table& operator=(const __hash_table& __u);1024 _LIBCUDACXX_INLINE_VISIBILITY1025 __hash_table& operator=(__hash_table&& __u)1026 noexcept(1027 __node_traits::propagate_on_container_move_assignment::value &&1028 is_nothrow_move_assignable<__node_allocator>::value &&1029 is_nothrow_move_assignable<hasher>::value &&1030 is_nothrow_move_assignable<key_equal>::value);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 1036 _LIBCUDACXX_INLINE_VISIBILITY1037 size_type max_size() const noexcept1038 {1039 return std::min<size_type>(1040 __node_traits::max_size(__node_alloc()),1041 numeric_limits<difference_type >::max()1042 );1043 }1044 1045private:1046 _LIBCUDACXX_INLINE_VISIBILITY1047 __next_pointer __node_insert_multi_prepare(size_t __cp_hash,1048 value_type& __cp_val);1049 _LIBCUDACXX_INLINE_VISIBILITY1050 void __node_insert_multi_perform(__node_pointer __cp,1051 __next_pointer __pn) noexcept;1052 1053 _LIBCUDACXX_INLINE_VISIBILITY1054 __next_pointer __node_insert_unique_prepare(size_t __nd_hash,1055 value_type& __nd_val);1056 _LIBCUDACXX_INLINE_VISIBILITY1057 void __node_insert_unique_perform(__node_pointer __ptr) noexcept;1058 1059public:1060 _LIBCUDACXX_INLINE_VISIBILITY1061 pair<iterator, bool> __node_insert_unique(__node_pointer __nd);1062 _LIBCUDACXX_INLINE_VISIBILITY1063 iterator __node_insert_multi(__node_pointer __nd);1064 _LIBCUDACXX_INLINE_VISIBILITY1065 iterator __node_insert_multi(const_iterator __p,1066 __node_pointer __nd);1067 1068 template <class _Key, class ..._Args>1069 _LIBCUDACXX_INLINE_VISIBILITY1070 pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);1071 1072 template <class... _Args>1073 _LIBCUDACXX_INLINE_VISIBILITY1074 pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);1075 1076 template <class _Pp>1077 _LIBCUDACXX_INLINE_VISIBILITY1078 pair<iterator, bool> __emplace_unique(_Pp&& __x) {1079 return __emplace_unique_extract_key(_CUDA_VSTD::forward<_Pp>(__x),1080 __can_extract_key<_Pp, key_type>());1081 }1082 1083 template <class _First, class _Second>1084 _LIBCUDACXX_INLINE_VISIBILITY1085 typename enable_if<1086 __can_extract_map_key<_First, key_type, __container_value_type>::value,1087 pair<iterator, bool>1088 >::type __emplace_unique(_First&& __f, _Second&& __s) {1089 return __emplace_unique_key_args(__f, _CUDA_VSTD::forward<_First>(__f),1090 _CUDA_VSTD::forward<_Second>(__s));1091 }1092 1093 template <class... _Args>1094 _LIBCUDACXX_INLINE_VISIBILITY1095 pair<iterator, bool> __emplace_unique(_Args&&... __args) {1096 return __emplace_unique_impl(_CUDA_VSTD::forward<_Args>(__args)...);1097 }1098 1099 template <class _Pp>1100 _LIBCUDACXX_INLINE_VISIBILITY1101 pair<iterator, bool>1102 __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {1103 return __emplace_unique_impl(_CUDA_VSTD::forward<_Pp>(__x));1104 }1105 template <class _Pp>1106 _LIBCUDACXX_INLINE_VISIBILITY1107 pair<iterator, bool>1108 __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {1109 return __emplace_unique_key_args(__x, _CUDA_VSTD::forward<_Pp>(__x));1110 }1111 template <class _Pp>1112 _LIBCUDACXX_INLINE_VISIBILITY1113 pair<iterator, bool>1114 __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {1115 return __emplace_unique_key_args(__x.first, _CUDA_VSTD::forward<_Pp>(__x));1116 }1117 1118 template <class... _Args>1119 _LIBCUDACXX_INLINE_VISIBILITY1120 iterator __emplace_multi(_Args&&... __args);1121 template <class... _Args>1122 _LIBCUDACXX_INLINE_VISIBILITY1123 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);1124 1125 1126 _LIBCUDACXX_INLINE_VISIBILITY1127 pair<iterator, bool>1128 __insert_unique(__container_value_type&& __x) {1129 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _CUDA_VSTD::move(__x));1130 }1131 1132 template <class _Pp, class = typename enable_if<1133 !__is_same_uncvref<_Pp, __container_value_type>::value1134 >::type>1135 _LIBCUDACXX_INLINE_VISIBILITY1136 pair<iterator, bool> __insert_unique(_Pp&& __x) {1137 return __emplace_unique(_CUDA_VSTD::forward<_Pp>(__x));1138 }1139 1140 template <class _Pp>1141 _LIBCUDACXX_INLINE_VISIBILITY1142 iterator __insert_multi(_Pp&& __x) {1143 return __emplace_multi(_CUDA_VSTD::forward<_Pp>(__x));1144 }1145 1146 template <class _Pp>1147 _LIBCUDACXX_INLINE_VISIBILITY1148 iterator __insert_multi(const_iterator __p, _Pp&& __x) {1149 return __emplace_hint_multi(__p, _CUDA_VSTD::forward<_Pp>(__x));1150 }1151 1152 _LIBCUDACXX_INLINE_VISIBILITY1153 pair<iterator, bool> __insert_unique(const __container_value_type& __x) {1154 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);1155 }1156 1157#if _LIBCUDACXX_STD_VER > 141158 template <class _NodeHandle, class _InsertReturnType>1159 _LIBCUDACXX_INLINE_VISIBILITY1160 _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);1161 template <class _NodeHandle>1162 _LIBCUDACXX_INLINE_VISIBILITY1163 iterator __node_handle_insert_unique(const_iterator __hint,1164 _NodeHandle&& __nh);1165 template <class _Table>1166 _LIBCUDACXX_INLINE_VISIBILITY1167 void __node_handle_merge_unique(_Table& __source);1168 1169 template <class _NodeHandle>1170 _LIBCUDACXX_INLINE_VISIBILITY1171 iterator __node_handle_insert_multi(_NodeHandle&& __nh);1172 template <class _NodeHandle>1173 _LIBCUDACXX_INLINE_VISIBILITY1174 iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);1175 template <class _Table>1176 _LIBCUDACXX_INLINE_VISIBILITY1177 void __node_handle_merge_multi(_Table& __source);1178 1179 template <class _NodeHandle>1180 _LIBCUDACXX_INLINE_VISIBILITY1181 _NodeHandle __node_handle_extract(key_type const& __key);1182 template <class _NodeHandle>1183 _LIBCUDACXX_INLINE_VISIBILITY1184 _NodeHandle __node_handle_extract(const_iterator __it);1185#endif1186 1187 void clear() noexcept;1188 void rehash(size_type __n);1189 _LIBCUDACXX_INLINE_VISIBILITY void reserve(size_type __n)1190 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}1191 1192 _LIBCUDACXX_INLINE_VISIBILITY1193 size_type bucket_count() const noexcept1194 {1195 return __bucket_list_.get_deleter().size();1196 }1197 1198 _LIBCUDACXX_INLINE_VISIBILITY1199 iterator begin() noexcept;1200 _LIBCUDACXX_INLINE_VISIBILITY