__hash_table 99 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806
  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-exception
  7. //
  8. //===----------------------------------------------------------------------===//
  9. #ifndef _LIBCPP__HASH_TABLE
  10. #define _LIBCPP__HASH_TABLE
  11. #include <__bits> // __libcpp_clz
  12. #include <__config>
  13. #include <__debug>
  14. #include <algorithm>
  15. #include <cmath>
  16. #include <initializer_list>
  17. #include <iterator>
  18. #include <memory>
  19. #include <type_traits>
  20. #include <utility>
  21. #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  22. #pragma GCC system_header
  23. #endif
  24. _LIBCPP_PUSH_MACROS
  25. #include <__undef_macros>
  26. _LIBCPP_BEGIN_NAMESPACE_STD
  27. template <class _Key, class _Tp>
  28. struct __hash_value_type;
  29. template <class _Tp>
  30. struct __is_hash_value_type_imp : false_type {};
  31. template <class _Key, class _Value>
  32. struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value> > : true_type {};
  33. template <class ..._Args>
  34. struct __is_hash_value_type : false_type {};
  35. template <class _One>
  36. struct __is_hash_value_type<_One> : __is_hash_value_type_imp<typename __uncvref<_One>::type> {};
  37. _LIBCPP_FUNC_VIS
  38. size_t __next_prime(size_t __n);
  39. template <class _NodePtr>
  40. struct __hash_node_base
  41. {
  42. typedef typename pointer_traits<_NodePtr>::element_type __node_type;
  43. typedef __hash_node_base __first_node;
  44. typedef typename __rebind_pointer<_NodePtr, __first_node>::type __node_base_pointer;
  45. typedef _NodePtr __node_pointer;
  46. #if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB)
  47. typedef __node_base_pointer __next_pointer;
  48. #else
  49. typedef typename conditional<
  50. is_pointer<__node_pointer>::value,
  51. __node_base_pointer,
  52. __node_pointer>::type __next_pointer;
  53. #endif
  54. __next_pointer __next_;
  55. _LIBCPP_INLINE_VISIBILITY
  56. __next_pointer __ptr() _NOEXCEPT {
  57. return static_cast<__next_pointer>(
  58. pointer_traits<__node_base_pointer>::pointer_to(*this));
  59. }
  60. _LIBCPP_INLINE_VISIBILITY
  61. __node_pointer __upcast() _NOEXCEPT {
  62. return static_cast<__node_pointer>(
  63. pointer_traits<__node_base_pointer>::pointer_to(*this));
  64. }
  65. _LIBCPP_INLINE_VISIBILITY
  66. size_t __hash() const _NOEXCEPT {
  67. return static_cast<__node_type const&>(*this).__hash_;
  68. }
  69. _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
  70. };
  71. #ifdef _LIBCPP_COMPILER_MSVC
  72. #pragma warning( push )
  73. #pragma warning( disable: 4624 )
  74. #endif // _LIBCPP_COMPILER_MSVC
  75. template <class _Tp, class _VoidPtr>
  76. struct _LIBCPP_STANDALONE_DEBUG __hash_node
  77. : public __hash_node_base
  78. <
  79. typename __rebind_pointer<_VoidPtr, __hash_node<_Tp, _VoidPtr> >::type
  80. >
  81. {
  82. typedef _Tp __node_value_type;
  83. size_t __hash_;
  84. __node_value_type __value_;
  85. };
  86. #ifdef _LIBCPP_COMPILER_MSVC
  87. #pragma warning( pop )
  88. #endif // _LIBCPP_COMPILER_MSVC
  89. inline _LIBCPP_INLINE_VISIBILITY
  90. bool
  91. __is_hash_power2(size_t __bc)
  92. {
  93. return __bc > 2 && !(__bc & (__bc - 1));
  94. }
  95. inline _LIBCPP_INLINE_VISIBILITY
  96. size_t
  97. __constrain_hash(size_t __h, size_t __bc)
  98. {
  99. return !(__bc & (__bc - 1)) ? __h & (__bc - 1) :
  100. (__h < __bc ? __h : __h % __bc);
  101. }
  102. inline _LIBCPP_INLINE_VISIBILITY
  103. size_t
  104. __next_hash_pow2(size_t __n)
  105. {
  106. return __n < 2 ? __n : (size_t(1) << (numeric_limits<size_t>::digits - __libcpp_clz(__n-1)));
  107. }
  108. template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
  109. template <class _NodePtr> class _LIBCPP_TEMPLATE_VIS __hash_iterator;
  110. template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
  111. template <class _NodePtr> class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
  112. template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
  113. template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
  114. template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
  115. template <class _Tp>
  116. struct __hash_key_value_types {
  117. static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
  118. typedef _Tp key_type;
  119. typedef _Tp __node_value_type;
  120. typedef _Tp __container_value_type;
  121. static const bool __is_map = false;
  122. _LIBCPP_INLINE_VISIBILITY
  123. static key_type const& __get_key(_Tp const& __v) {
  124. return __v;
  125. }
  126. _LIBCPP_INLINE_VISIBILITY
  127. static __container_value_type const& __get_value(__node_value_type const& __v) {
  128. return __v;
  129. }
  130. _LIBCPP_INLINE_VISIBILITY
  131. static __container_value_type* __get_ptr(__node_value_type& __n) {
  132. return _VSTD::addressof(__n);
  133. }
  134. _LIBCPP_INLINE_VISIBILITY
  135. static __container_value_type&& __move(__node_value_type& __v) {
  136. return _VSTD::move(__v);
  137. }
  138. };
  139. template <class _Key, class _Tp>
  140. struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
  141. typedef _Key key_type;
  142. typedef _Tp mapped_type;
  143. typedef __hash_value_type<_Key, _Tp> __node_value_type;
  144. typedef pair<const _Key, _Tp> __container_value_type;
  145. typedef __container_value_type __map_value_type;
  146. static const bool __is_map = true;
  147. _LIBCPP_INLINE_VISIBILITY
  148. static key_type const& __get_key(__container_value_type const& __v) {
  149. return __v.first;
  150. }
  151. template <class _Up>
  152. _LIBCPP_INLINE_VISIBILITY
  153. static typename enable_if<__is_same_uncvref<_Up, __node_value_type>::value,
  154. __container_value_type const&>::type
  155. __get_value(_Up& __t) {
  156. return __t.__get_value();
  157. }
  158. template <class _Up>
  159. _LIBCPP_INLINE_VISIBILITY
  160. static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,
  161. __container_value_type const&>::type
  162. __get_value(_Up& __t) {
  163. return __t;
  164. }
  165. _LIBCPP_INLINE_VISIBILITY
  166. static __container_value_type* __get_ptr(__node_value_type& __n) {
  167. return _VSTD::addressof(__n.__get_value());
  168. }
  169. _LIBCPP_INLINE_VISIBILITY
  170. static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) {
  171. return __v.__move();
  172. }
  173. };
  174. template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>,
  175. bool = _KVTypes::__is_map>
  176. struct __hash_map_pointer_types {};
  177. template <class _Tp, class _AllocPtr, class _KVTypes>
  178. struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
  179. typedef typename _KVTypes::__map_value_type _Mv;
  180. typedef typename __rebind_pointer<_AllocPtr, _Mv>::type
  181. __map_value_type_pointer;
  182. typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type
  183. __const_map_value_type_pointer;
  184. };
  185. template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
  186. struct __hash_node_types;
  187. template <class _NodePtr, class _Tp, class _VoidPtr>
  188. struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
  189. : public __hash_key_value_types<_Tp>, __hash_map_pointer_types<_Tp, _VoidPtr>
  190. {
  191. typedef __hash_key_value_types<_Tp> __base;
  192. public:
  193. typedef ptrdiff_t difference_type;
  194. typedef size_t size_type;
  195. typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer;
  196. typedef typename pointer_traits<_NodePtr>::element_type __node_type;
  197. typedef _NodePtr __node_pointer;
  198. typedef __hash_node_base<__node_pointer> __node_base_type;
  199. typedef typename __rebind_pointer<_NodePtr, __node_base_type>::type
  200. __node_base_pointer;
  201. typedef typename __node_base_type::__next_pointer __next_pointer;
  202. typedef _Tp __node_value_type;
  203. typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type
  204. __node_value_type_pointer;
  205. typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type
  206. __const_node_value_type_pointer;
  207. private:
  208. static_assert(!is_const<__node_type>::value,
  209. "_NodePtr should never be a pointer to const");
  210. static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),
  211. "_VoidPtr does not point to unqualified void type");
  212. static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type,
  213. _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");
  214. };
  215. template <class _HashIterator>
  216. struct __hash_node_types_from_iterator;
  217. template <class _NodePtr>
  218. struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
  219. template <class _NodePtr>
  220. struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
  221. template <class _NodePtr>
  222. struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
  223. template <class _NodePtr>
  224. struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
  225. template <class _NodeValueTp, class _VoidPtr>
  226. struct __make_hash_node_types {
  227. typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
  228. typedef typename __rebind_pointer<_VoidPtr, _NodeTp>::type _NodePtr;
  229. typedef __hash_node_types<_NodePtr> type;
  230. };
  231. template <class _NodePtr>
  232. class _LIBCPP_TEMPLATE_VIS __hash_iterator
  233. {
  234. typedef __hash_node_types<_NodePtr> _NodeTypes;
  235. typedef _NodePtr __node_pointer;
  236. typedef typename _NodeTypes::__next_pointer __next_pointer;
  237. __next_pointer __node_;
  238. public:
  239. typedef forward_iterator_tag iterator_category;
  240. typedef typename _NodeTypes::__node_value_type value_type;
  241. typedef typename _NodeTypes::difference_type difference_type;
  242. typedef value_type& reference;
  243. typedef typename _NodeTypes::__node_value_type_pointer pointer;
  244. _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT : __node_(nullptr) {
  245. _VSTD::__debug_db_insert_i(this);
  246. }
  247. #if _LIBCPP_DEBUG_LEVEL == 2
  248. _LIBCPP_INLINE_VISIBILITY
  249. __hash_iterator(const __hash_iterator& __i)
  250. : __node_(__i.__node_)
  251. {
  252. __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
  253. }
  254. _LIBCPP_INLINE_VISIBILITY
  255. ~__hash_iterator()
  256. {
  257. __get_db()->__erase_i(this);
  258. }
  259. _LIBCPP_INLINE_VISIBILITY
  260. __hash_iterator& operator=(const __hash_iterator& __i)
  261. {
  262. if (this != _VSTD::addressof(__i))
  263. {
  264. __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
  265. __node_ = __i.__node_;
  266. }
  267. return *this;
  268. }
  269. #endif // _LIBCPP_DEBUG_LEVEL == 2
  270. _LIBCPP_INLINE_VISIBILITY
  271. reference operator*() const {
  272. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  273. "Attempted to dereference a non-dereferenceable unordered container iterator");
  274. return __node_->__upcast()->__value_;
  275. }
  276. _LIBCPP_INLINE_VISIBILITY
  277. pointer operator->() const {
  278. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  279. "Attempted to dereference a non-dereferenceable unordered container iterator");
  280. return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
  281. }
  282. _LIBCPP_INLINE_VISIBILITY
  283. __hash_iterator& operator++() {
  284. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  285. "Attempted to increment a non-incrementable unordered container iterator");
  286. __node_ = __node_->__next_;
  287. return *this;
  288. }
  289. _LIBCPP_INLINE_VISIBILITY
  290. __hash_iterator operator++(int)
  291. {
  292. __hash_iterator __t(*this);
  293. ++(*this);
  294. return __t;
  295. }
  296. friend _LIBCPP_INLINE_VISIBILITY
  297. bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
  298. {
  299. return __x.__node_ == __y.__node_;
  300. }
  301. friend _LIBCPP_INLINE_VISIBILITY
  302. bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
  303. {return !(__x == __y);}
  304. private:
  305. #if _LIBCPP_DEBUG_LEVEL == 2
  306. _LIBCPP_INLINE_VISIBILITY
  307. __hash_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
  308. : __node_(__node)
  309. {
  310. __get_db()->__insert_ic(this, __c);
  311. }
  312. #else
  313. _LIBCPP_INLINE_VISIBILITY
  314. __hash_iterator(__next_pointer __node) _NOEXCEPT
  315. : __node_(__node)
  316. {}
  317. #endif
  318. template <class, class, class, class> friend class __hash_table;
  319. template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
  320. template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
  321. template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
  322. template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
  323. };
  324. template <class _NodePtr>
  325. class _LIBCPP_TEMPLATE_VIS __hash_const_iterator
  326. {
  327. static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
  328. typedef __hash_node_types<_NodePtr> _NodeTypes;
  329. typedef _NodePtr __node_pointer;
  330. typedef typename _NodeTypes::__next_pointer __next_pointer;
  331. __next_pointer __node_;
  332. public:
  333. typedef __hash_iterator<_NodePtr> __non_const_iterator;
  334. typedef forward_iterator_tag iterator_category;
  335. typedef typename _NodeTypes::__node_value_type value_type;
  336. typedef typename _NodeTypes::difference_type difference_type;
  337. typedef const value_type& reference;
  338. typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
  339. _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {
  340. _VSTD::__debug_db_insert_i(this);
  341. }
  342. _LIBCPP_INLINE_VISIBILITY
  343. __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
  344. : __node_(__x.__node_)
  345. {
  346. #if _LIBCPP_DEBUG_LEVEL == 2
  347. __get_db()->__iterator_copy(this, _VSTD::addressof(__x));
  348. #endif
  349. }
  350. #if _LIBCPP_DEBUG_LEVEL == 2
  351. _LIBCPP_INLINE_VISIBILITY
  352. __hash_const_iterator(const __hash_const_iterator& __i)
  353. : __node_(__i.__node_)
  354. {
  355. __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
  356. }
  357. _LIBCPP_INLINE_VISIBILITY
  358. ~__hash_const_iterator()
  359. {
  360. __get_db()->__erase_i(this);
  361. }
  362. _LIBCPP_INLINE_VISIBILITY
  363. __hash_const_iterator& operator=(const __hash_const_iterator& __i)
  364. {
  365. if (this != _VSTD::addressof(__i))
  366. {
  367. __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
  368. __node_ = __i.__node_;
  369. }
  370. return *this;
  371. }
  372. #endif // _LIBCPP_DEBUG_LEVEL == 2
  373. _LIBCPP_INLINE_VISIBILITY
  374. reference operator*() const {
  375. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  376. "Attempted to dereference a non-dereferenceable unordered container const_iterator");
  377. return __node_->__upcast()->__value_;
  378. }
  379. _LIBCPP_INLINE_VISIBILITY
  380. pointer operator->() const {
  381. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  382. "Attempted to dereference a non-dereferenceable unordered container const_iterator");
  383. return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
  384. }
  385. _LIBCPP_INLINE_VISIBILITY
  386. __hash_const_iterator& operator++() {
  387. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  388. "Attempted to increment a non-incrementable unordered container const_iterator");
  389. __node_ = __node_->__next_;
  390. return *this;
  391. }
  392. _LIBCPP_INLINE_VISIBILITY
  393. __hash_const_iterator operator++(int)
  394. {
  395. __hash_const_iterator __t(*this);
  396. ++(*this);
  397. return __t;
  398. }
  399. friend _LIBCPP_INLINE_VISIBILITY
  400. bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
  401. {
  402. return __x.__node_ == __y.__node_;
  403. }
  404. friend _LIBCPP_INLINE_VISIBILITY
  405. bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
  406. {return !(__x == __y);}
  407. private:
  408. #if _LIBCPP_DEBUG_LEVEL == 2
  409. _LIBCPP_INLINE_VISIBILITY
  410. __hash_const_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
  411. : __node_(__node)
  412. {
  413. __get_db()->__insert_ic(this, __c);
  414. }
  415. #else
  416. _LIBCPP_INLINE_VISIBILITY
  417. __hash_const_iterator(__next_pointer __node) _NOEXCEPT
  418. : __node_(__node)
  419. {}
  420. #endif
  421. template <class, class, class, class> friend class __hash_table;
  422. template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
  423. template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
  424. template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
  425. };
  426. template <class _NodePtr>
  427. class _LIBCPP_TEMPLATE_VIS __hash_local_iterator
  428. {
  429. typedef __hash_node_types<_NodePtr> _NodeTypes;
  430. typedef _NodePtr __node_pointer;
  431. typedef typename _NodeTypes::__next_pointer __next_pointer;
  432. __next_pointer __node_;
  433. size_t __bucket_;
  434. size_t __bucket_count_;
  435. public:
  436. typedef forward_iterator_tag iterator_category;
  437. typedef typename _NodeTypes::__node_value_type value_type;
  438. typedef typename _NodeTypes::difference_type difference_type;
  439. typedef value_type& reference;
  440. typedef typename _NodeTypes::__node_value_type_pointer pointer;
  441. _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {
  442. _VSTD::__debug_db_insert_i(this);
  443. }
  444. #if _LIBCPP_DEBUG_LEVEL == 2
  445. _LIBCPP_INLINE_VISIBILITY
  446. __hash_local_iterator(const __hash_local_iterator& __i)
  447. : __node_(__i.__node_),
  448. __bucket_(__i.__bucket_),
  449. __bucket_count_(__i.__bucket_count_)
  450. {
  451. __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
  452. }
  453. _LIBCPP_INLINE_VISIBILITY
  454. ~__hash_local_iterator()
  455. {
  456. __get_db()->__erase_i(this);
  457. }
  458. _LIBCPP_INLINE_VISIBILITY
  459. __hash_local_iterator& operator=(const __hash_local_iterator& __i)
  460. {
  461. if (this != _VSTD::addressof(__i))
  462. {
  463. __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
  464. __node_ = __i.__node_;
  465. __bucket_ = __i.__bucket_;
  466. __bucket_count_ = __i.__bucket_count_;
  467. }
  468. return *this;
  469. }
  470. #endif // _LIBCPP_DEBUG_LEVEL == 2
  471. _LIBCPP_INLINE_VISIBILITY
  472. reference operator*() const {
  473. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  474. "Attempted to dereference a non-dereferenceable unordered container local_iterator");
  475. return __node_->__upcast()->__value_;
  476. }
  477. _LIBCPP_INLINE_VISIBILITY
  478. pointer operator->() const {
  479. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  480. "Attempted to dereference a non-dereferenceable unordered container local_iterator");
  481. return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
  482. }
  483. _LIBCPP_INLINE_VISIBILITY
  484. __hash_local_iterator& operator++() {
  485. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  486. "Attempted to increment a non-incrementable unordered container local_iterator");
  487. __node_ = __node_->__next_;
  488. if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
  489. __node_ = nullptr;
  490. return *this;
  491. }
  492. _LIBCPP_INLINE_VISIBILITY
  493. __hash_local_iterator operator++(int)
  494. {
  495. __hash_local_iterator __t(*this);
  496. ++(*this);
  497. return __t;
  498. }
  499. friend _LIBCPP_INLINE_VISIBILITY
  500. bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
  501. {
  502. return __x.__node_ == __y.__node_;
  503. }
  504. friend _LIBCPP_INLINE_VISIBILITY
  505. bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
  506. {return !(__x == __y);}
  507. private:
  508. #if _LIBCPP_DEBUG_LEVEL == 2
  509. _LIBCPP_INLINE_VISIBILITY
  510. __hash_local_iterator(__next_pointer __node, size_t __bucket,
  511. size_t __bucket_count, const void* __c) _NOEXCEPT
  512. : __node_(__node),
  513. __bucket_(__bucket),
  514. __bucket_count_(__bucket_count)
  515. {
  516. __get_db()->__insert_ic(this, __c);
  517. if (__node_ != nullptr)
  518. __node_ = __node_->__next_;
  519. }
  520. #else
  521. _LIBCPP_INLINE_VISIBILITY
  522. __hash_local_iterator(__next_pointer __node, size_t __bucket,
  523. size_t __bucket_count) _NOEXCEPT
  524. : __node_(__node),
  525. __bucket_(__bucket),
  526. __bucket_count_(__bucket_count)
  527. {
  528. if (__node_ != nullptr)
  529. __node_ = __node_->__next_;
  530. }
  531. #endif
  532. template <class, class, class, class> friend class __hash_table;
  533. template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
  534. template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
  535. };
  536. template <class _ConstNodePtr>
  537. class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator
  538. {
  539. typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
  540. typedef _ConstNodePtr __node_pointer;
  541. typedef typename _NodeTypes::__next_pointer __next_pointer;
  542. __next_pointer __node_;
  543. size_t __bucket_;
  544. size_t __bucket_count_;
  545. typedef pointer_traits<__node_pointer> __pointer_traits;
  546. typedef typename __pointer_traits::element_type __node;
  547. typedef typename remove_const<__node>::type __non_const_node;
  548. typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type
  549. __non_const_node_pointer;
  550. public:
  551. typedef __hash_local_iterator<__non_const_node_pointer>
  552. __non_const_iterator;
  553. typedef forward_iterator_tag iterator_category;
  554. typedef typename _NodeTypes::__node_value_type value_type;
  555. typedef typename _NodeTypes::difference_type difference_type;
  556. typedef const value_type& reference;
  557. typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
  558. _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {
  559. _VSTD::__debug_db_insert_i(this);
  560. }
  561. _LIBCPP_INLINE_VISIBILITY
  562. __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
  563. : __node_(__x.__node_),
  564. __bucket_(__x.__bucket_),
  565. __bucket_count_(__x.__bucket_count_)
  566. {
  567. #if _LIBCPP_DEBUG_LEVEL == 2
  568. __get_db()->__iterator_copy(this, _VSTD::addressof(__x));
  569. #endif
  570. }
  571. #if _LIBCPP_DEBUG_LEVEL == 2
  572. _LIBCPP_INLINE_VISIBILITY
  573. __hash_const_local_iterator(const __hash_const_local_iterator& __i)
  574. : __node_(__i.__node_),
  575. __bucket_(__i.__bucket_),
  576. __bucket_count_(__i.__bucket_count_)
  577. {
  578. __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
  579. }
  580. _LIBCPP_INLINE_VISIBILITY
  581. ~__hash_const_local_iterator()
  582. {
  583. __get_db()->__erase_i(this);
  584. }
  585. _LIBCPP_INLINE_VISIBILITY
  586. __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i)
  587. {
  588. if (this != _VSTD::addressof(__i))
  589. {
  590. __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
  591. __node_ = __i.__node_;
  592. __bucket_ = __i.__bucket_;
  593. __bucket_count_ = __i.__bucket_count_;
  594. }
  595. return *this;
  596. }
  597. #endif // _LIBCPP_DEBUG_LEVEL == 2
  598. _LIBCPP_INLINE_VISIBILITY
  599. reference operator*() const {
  600. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  601. "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
  602. return __node_->__upcast()->__value_;
  603. }
  604. _LIBCPP_INLINE_VISIBILITY
  605. pointer operator->() const {
  606. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  607. "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
  608. return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
  609. }
  610. _LIBCPP_INLINE_VISIBILITY
  611. __hash_const_local_iterator& operator++() {
  612. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
  613. "Attempted to increment a non-incrementable unordered container const_local_iterator");
  614. __node_ = __node_->__next_;
  615. if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
  616. __node_ = nullptr;
  617. return *this;
  618. }
  619. _LIBCPP_INLINE_VISIBILITY
  620. __hash_const_local_iterator operator++(int)
  621. {
  622. __hash_const_local_iterator __t(*this);
  623. ++(*this);
  624. return __t;
  625. }
  626. friend _LIBCPP_INLINE_VISIBILITY
  627. bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
  628. {
  629. return __x.__node_ == __y.__node_;
  630. }
  631. friend _LIBCPP_INLINE_VISIBILITY
  632. bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
  633. {return !(__x == __y);}
  634. private:
  635. #if _LIBCPP_DEBUG_LEVEL == 2
  636. _LIBCPP_INLINE_VISIBILITY
  637. __hash_const_local_iterator(__next_pointer __node_ptr, size_t __bucket,
  638. size_t __bucket_count, const void* __c) _NOEXCEPT
  639. : __node_(__node_ptr),
  640. __bucket_(__bucket),
  641. __bucket_count_(__bucket_count)
  642. {
  643. __get_db()->__insert_ic(this, __c);
  644. if (__node_ != nullptr)
  645. __node_ = __node_->__next_;
  646. }
  647. #else
  648. _LIBCPP_INLINE_VISIBILITY
  649. __hash_const_local_iterator(__next_pointer __node_ptr, size_t __bucket,
  650. size_t __bucket_count) _NOEXCEPT
  651. : __node_(__node_ptr),
  652. __bucket_(__bucket),
  653. __bucket_count_(__bucket_count)
  654. {
  655. if (__node_ != nullptr)
  656. __node_ = __node_->__next_;
  657. }
  658. #endif
  659. template <class, class, class, class> friend class __hash_table;
  660. template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
  661. };
  662. template <class _Alloc>
  663. class __bucket_list_deallocator
  664. {
  665. typedef _Alloc allocator_type;
  666. typedef allocator_traits<allocator_type> __alloc_traits;
  667. typedef typename __alloc_traits::size_type size_type;
  668. __compressed_pair<size_type, allocator_type> __data_;
  669. public:
  670. typedef typename __alloc_traits::pointer pointer;
  671. _LIBCPP_INLINE_VISIBILITY
  672. __bucket_list_deallocator()
  673. _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
  674. : __data_(0, __default_init_tag()) {}
  675. _LIBCPP_INLINE_VISIBILITY
  676. __bucket_list_deallocator(const allocator_type& __a, size_type __size)
  677. _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
  678. : __data_(__size, __a) {}
  679. _LIBCPP_INLINE_VISIBILITY
  680. __bucket_list_deallocator(__bucket_list_deallocator&& __x)
  681. _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
  682. : __data_(_VSTD::move(__x.__data_))
  683. {
  684. __x.size() = 0;
  685. }
  686. _LIBCPP_INLINE_VISIBILITY
  687. size_type& size() _NOEXCEPT {return __data_.first();}
  688. _LIBCPP_INLINE_VISIBILITY
  689. size_type size() const _NOEXCEPT {return __data_.first();}
  690. _LIBCPP_INLINE_VISIBILITY
  691. allocator_type& __alloc() _NOEXCEPT {return __data_.second();}
  692. _LIBCPP_INLINE_VISIBILITY
  693. const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();}
  694. _LIBCPP_INLINE_VISIBILITY
  695. void operator()(pointer __p) _NOEXCEPT
  696. {
  697. __alloc_traits::deallocate(__alloc(), __p, size());
  698. }
  699. };
  700. template <class _Alloc> class __hash_map_node_destructor;
  701. template <class _Alloc>
  702. class __hash_node_destructor
  703. {
  704. typedef _Alloc allocator_type;
  705. typedef allocator_traits<allocator_type> __alloc_traits;
  706. public:
  707. typedef typename __alloc_traits::pointer pointer;
  708. private:
  709. typedef __hash_node_types<pointer> _NodeTypes;
  710. allocator_type& __na_;
  711. public:
  712. bool __value_constructed;
  713. __hash_node_destructor(__hash_node_destructor const&) = default;
  714. __hash_node_destructor& operator=(const __hash_node_destructor&) = delete;
  715. _LIBCPP_INLINE_VISIBILITY
  716. explicit __hash_node_destructor(allocator_type& __na,
  717. bool __constructed = false) _NOEXCEPT
  718. : __na_(__na),
  719. __value_constructed(__constructed)
  720. {}
  721. _LIBCPP_INLINE_VISIBILITY
  722. void operator()(pointer __p) _NOEXCEPT
  723. {
  724. if (__value_constructed)
  725. __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
  726. if (__p)
  727. __alloc_traits::deallocate(__na_, __p, 1);
  728. }
  729. template <class> friend class __hash_map_node_destructor;
  730. };
  731. #if _LIBCPP_STD_VER > 14
  732. template <class _NodeType, class _Alloc>
  733. struct __generic_container_node_destructor;
  734. template <class _Tp, class _VoidPtr, class _Alloc>
  735. struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc>
  736. : __hash_node_destructor<_Alloc>
  737. {
  738. using __hash_node_destructor<_Alloc>::__hash_node_destructor;
  739. };
  740. #endif
  741. template <class _Key, class _Hash, class _Equal>
  742. struct __enforce_unordered_container_requirements {
  743. #ifndef _LIBCPP_CXX03_LANG
  744. static_assert(__check_hash_requirements<_Key, _Hash>::value,
  745. "the specified hash does not meet the Hash requirements");
  746. static_assert(is_copy_constructible<_Equal>::value,
  747. "the specified comparator is required to be copy constructible");
  748. #endif
  749. typedef int type;
  750. };
  751. template <class _Key, class _Hash, class _Equal>
  752. #ifndef _LIBCPP_CXX03_LANG
  753. _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value,
  754. "the specified comparator type does not provide a viable const call operator")
  755. _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value,
  756. "the specified hash functor does not provide a viable const call operator")
  757. #endif
  758. typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type
  759. __diagnose_unordered_container_requirements(int);
  760. // This dummy overload is used so that the compiler won't emit a spurious
  761. // "no matching function for call to __diagnose_unordered_xxx" diagnostic
  762. // when the overload above causes a hard error.
  763. template <class _Key, class _Hash, class _Equal>
  764. int __diagnose_unordered_container_requirements(void*);
  765. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  766. class __hash_table
  767. {
  768. public:
  769. typedef _Tp value_type;
  770. typedef _Hash hasher;
  771. typedef _Equal key_equal;
  772. typedef _Alloc allocator_type;
  773. private:
  774. typedef allocator_traits<allocator_type> __alloc_traits;
  775. typedef typename
  776. __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type
  777. _NodeTypes;
  778. public:
  779. typedef typename _NodeTypes::__node_value_type __node_value_type;
  780. typedef typename _NodeTypes::__container_value_type __container_value_type;
  781. typedef typename _NodeTypes::key_type key_type;
  782. typedef value_type& reference;
  783. typedef const value_type& const_reference;
  784. typedef typename __alloc_traits::pointer pointer;
  785. typedef typename __alloc_traits::const_pointer const_pointer;
  786. #ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
  787. typedef typename __alloc_traits::size_type size_type;
  788. #else
  789. typedef typename _NodeTypes::size_type size_type;
  790. #endif
  791. typedef typename _NodeTypes::difference_type difference_type;
  792. public:
  793. // Create __node
  794. typedef typename _NodeTypes::__node_type __node;
  795. typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
  796. typedef allocator_traits<__node_allocator> __node_traits;
  797. typedef typename _NodeTypes::__void_pointer __void_pointer;
  798. typedef typename _NodeTypes::__node_pointer __node_pointer;
  799. typedef typename _NodeTypes::__node_pointer __node_const_pointer;
  800. typedef typename _NodeTypes::__node_base_type __first_node;
  801. typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
  802. typedef typename _NodeTypes::__next_pointer __next_pointer;
  803. private:
  804. // check for sane allocator pointer rebinding semantics. Rebinding the
  805. // allocator for a new pointer type should be exactly the same as rebinding
  806. // the pointer using 'pointer_traits'.
  807. static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value),
  808. "Allocator does not rebind pointers in a sane manner.");
  809. typedef typename __rebind_alloc_helper<__node_traits, __first_node>::type
  810. __node_base_allocator;
  811. typedef allocator_traits<__node_base_allocator> __node_base_traits;
  812. static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value),
  813. "Allocator does not rebind pointers in a sane manner.");
  814. private:
  815. typedef typename __rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator;
  816. typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
  817. typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
  818. typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;
  819. typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
  820. // --- Member data begin ---
  821. __bucket_list __bucket_list_;
  822. __compressed_pair<__first_node, __node_allocator> __p1_;
  823. __compressed_pair<size_type, hasher> __p2_;
  824. __compressed_pair<float, key_equal> __p3_;
  825. // --- Member data end ---
  826. _LIBCPP_INLINE_VISIBILITY
  827. size_type& size() _NOEXCEPT {return __p2_.first();}
  828. public:
  829. _LIBCPP_INLINE_VISIBILITY
  830. size_type size() const _NOEXCEPT {return __p2_.first();}
  831. _LIBCPP_INLINE_VISIBILITY
  832. hasher& hash_function() _NOEXCEPT {return __p2_.second();}
  833. _LIBCPP_INLINE_VISIBILITY
  834. const hasher& hash_function() const _NOEXCEPT {return __p2_.second();}
  835. _LIBCPP_INLINE_VISIBILITY
  836. float& max_load_factor() _NOEXCEPT {return __p3_.first();}
  837. _LIBCPP_INLINE_VISIBILITY
  838. float max_load_factor() const _NOEXCEPT {return __p3_.first();}
  839. _LIBCPP_INLINE_VISIBILITY
  840. key_equal& key_eq() _NOEXCEPT {return __p3_.second();}
  841. _LIBCPP_INLINE_VISIBILITY
  842. const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();}
  843. _LIBCPP_INLINE_VISIBILITY
  844. __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();}
  845. _LIBCPP_INLINE_VISIBILITY
  846. const __node_allocator& __node_alloc() const _NOEXCEPT
  847. {return __p1_.second();}
  848. public:
  849. typedef __hash_iterator<__node_pointer> iterator;
  850. typedef __hash_const_iterator<__node_pointer> const_iterator;
  851. typedef __hash_local_iterator<__node_pointer> local_iterator;
  852. typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
  853. _LIBCPP_INLINE_VISIBILITY
  854. __hash_table()
  855. _NOEXCEPT_(
  856. is_nothrow_default_constructible<__bucket_list>::value &&
  857. is_nothrow_default_constructible<__first_node>::value &&
  858. is_nothrow_default_constructible<__node_allocator>::value &&
  859. is_nothrow_default_constructible<hasher>::value &&
  860. is_nothrow_default_constructible<key_equal>::value);
  861. _LIBCPP_INLINE_VISIBILITY
  862. __hash_table(const hasher& __hf, const key_equal& __eql);
  863. __hash_table(const hasher& __hf, const key_equal& __eql,
  864. const allocator_type& __a);
  865. explicit __hash_table(const allocator_type& __a);
  866. __hash_table(const __hash_table& __u);
  867. __hash_table(const __hash_table& __u, const allocator_type& __a);
  868. __hash_table(__hash_table&& __u)
  869. _NOEXCEPT_(
  870. is_nothrow_move_constructible<__bucket_list>::value &&
  871. is_nothrow_move_constructible<__first_node>::value &&
  872. is_nothrow_move_constructible<__node_allocator>::value &&
  873. is_nothrow_move_constructible<hasher>::value &&
  874. is_nothrow_move_constructible<key_equal>::value);
  875. __hash_table(__hash_table&& __u, const allocator_type& __a);
  876. ~__hash_table();
  877. __hash_table& operator=(const __hash_table& __u);
  878. _LIBCPP_INLINE_VISIBILITY
  879. __hash_table& operator=(__hash_table&& __u)
  880. _NOEXCEPT_(
  881. __node_traits::propagate_on_container_move_assignment::value &&
  882. is_nothrow_move_assignable<__node_allocator>::value &&
  883. is_nothrow_move_assignable<hasher>::value &&
  884. is_nothrow_move_assignable<key_equal>::value);
  885. template <class _InputIterator>
  886. void __assign_unique(_InputIterator __first, _InputIterator __last);
  887. template <class _InputIterator>
  888. void __assign_multi(_InputIterator __first, _InputIterator __last);
  889. _LIBCPP_INLINE_VISIBILITY
  890. size_type max_size() const _NOEXCEPT
  891. {
  892. return _VSTD::min<size_type>(
  893. __node_traits::max_size(__node_alloc()),
  894. numeric_limits<difference_type >::max()
  895. );
  896. }
  897. private:
  898. _LIBCPP_INLINE_VISIBILITY
  899. __next_pointer __node_insert_multi_prepare(size_t __cp_hash,
  900. value_type& __cp_val);
  901. _LIBCPP_INLINE_VISIBILITY
  902. void __node_insert_multi_perform(__node_pointer __cp,
  903. __next_pointer __pn) _NOEXCEPT;
  904. _LIBCPP_INLINE_VISIBILITY
  905. __next_pointer __node_insert_unique_prepare(size_t __nd_hash,
  906. value_type& __nd_val);
  907. _LIBCPP_INLINE_VISIBILITY
  908. void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
  909. public:
  910. _LIBCPP_INLINE_VISIBILITY
  911. pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
  912. _LIBCPP_INLINE_VISIBILITY
  913. iterator __node_insert_multi(__node_pointer __nd);
  914. _LIBCPP_INLINE_VISIBILITY
  915. iterator __node_insert_multi(const_iterator __p,
  916. __node_pointer __nd);
  917. template <class _Key, class ..._Args>
  918. _LIBCPP_INLINE_VISIBILITY
  919. pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
  920. template <class... _Args>
  921. _LIBCPP_INLINE_VISIBILITY
  922. pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
  923. template <class _Pp>
  924. _LIBCPP_INLINE_VISIBILITY
  925. pair<iterator, bool> __emplace_unique(_Pp&& __x) {
  926. return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
  927. __can_extract_key<_Pp, key_type>());
  928. }
  929. template <class _First, class _Second>
  930. _LIBCPP_INLINE_VISIBILITY
  931. typename enable_if<
  932. __can_extract_map_key<_First, key_type, __container_value_type>::value,
  933. pair<iterator, bool>
  934. >::type __emplace_unique(_First&& __f, _Second&& __s) {
  935. return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f),
  936. _VSTD::forward<_Second>(__s));
  937. }
  938. template <class... _Args>
  939. _LIBCPP_INLINE_VISIBILITY
  940. pair<iterator, bool> __emplace_unique(_Args&&... __args) {
  941. return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
  942. }
  943. template <class _Pp>
  944. _LIBCPP_INLINE_VISIBILITY
  945. pair<iterator, bool>
  946. __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
  947. return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
  948. }
  949. template <class _Pp>
  950. _LIBCPP_INLINE_VISIBILITY
  951. pair<iterator, bool>
  952. __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
  953. return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
  954. }
  955. template <class _Pp>
  956. _LIBCPP_INLINE_VISIBILITY
  957. pair<iterator, bool>
  958. __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
  959. return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
  960. }
  961. template <class... _Args>
  962. _LIBCPP_INLINE_VISIBILITY
  963. iterator __emplace_multi(_Args&&... __args);
  964. template <class... _Args>
  965. _LIBCPP_INLINE_VISIBILITY
  966. iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
  967. _LIBCPP_INLINE_VISIBILITY
  968. pair<iterator, bool>
  969. __insert_unique(__container_value_type&& __x) {
  970. return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x));
  971. }
  972. template <class _Pp, class = typename enable_if<
  973. !__is_same_uncvref<_Pp, __container_value_type>::value
  974. >::type>
  975. _LIBCPP_INLINE_VISIBILITY
  976. pair<iterator, bool> __insert_unique(_Pp&& __x) {
  977. return __emplace_unique(_VSTD::forward<_Pp>(__x));
  978. }
  979. template <class _Pp>
  980. _LIBCPP_INLINE_VISIBILITY
  981. iterator __insert_multi(_Pp&& __x) {
  982. return __emplace_multi(_VSTD::forward<_Pp>(__x));
  983. }
  984. template <class _Pp>
  985. _LIBCPP_INLINE_VISIBILITY
  986. iterator __insert_multi(const_iterator __p, _Pp&& __x) {
  987. return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x));
  988. }
  989. _LIBCPP_INLINE_VISIBILITY
  990. pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
  991. return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
  992. }
  993. #if _LIBCPP_STD_VER > 14
  994. template <class _NodeHandle, class _InsertReturnType>
  995. _LIBCPP_INLINE_VISIBILITY
  996. _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
  997. template <class _NodeHandle>
  998. _LIBCPP_INLINE_VISIBILITY
  999. iterator __node_handle_insert_unique(const_iterator __hint,
  1000. _NodeHandle&& __nh);
  1001. template <class _Table>
  1002. _LIBCPP_INLINE_VISIBILITY
  1003. void __node_handle_merge_unique(_Table& __source);
  1004. template <class _NodeHandle>
  1005. _LIBCPP_INLINE_VISIBILITY
  1006. iterator __node_handle_insert_multi(_NodeHandle&& __nh);
  1007. template <class _NodeHandle>
  1008. _LIBCPP_INLINE_VISIBILITY
  1009. iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
  1010. template <class _Table>
  1011. _LIBCPP_INLINE_VISIBILITY
  1012. void __node_handle_merge_multi(_Table& __source);
  1013. template <class _NodeHandle>
  1014. _LIBCPP_INLINE_VISIBILITY
  1015. _NodeHandle __node_handle_extract(key_type const& __key);
  1016. template <class _NodeHandle>
  1017. _LIBCPP_INLINE_VISIBILITY
  1018. _NodeHandle __node_handle_extract(const_iterator __it);
  1019. #endif
  1020. void clear() _NOEXCEPT;
  1021. void rehash(size_type __n);
  1022. _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
  1023. {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
  1024. _LIBCPP_INLINE_VISIBILITY
  1025. size_type bucket_count() const _NOEXCEPT
  1026. {
  1027. return __bucket_list_.get_deleter().size();
  1028. }
  1029. _LIBCPP_INLINE_VISIBILITY
  1030. iterator begin() _NOEXCEPT;
  1031. _LIBCPP_INLINE_VISIBILITY
  1032. iterator end() _NOEXCEPT;
  1033. _LIBCPP_INLINE_VISIBILITY
  1034. const_iterator begin() const _NOEXCEPT;
  1035. _LIBCPP_INLINE_VISIBILITY
  1036. const_iterator end() const _NOEXCEPT;
  1037. template <class _Key>
  1038. _LIBCPP_INLINE_VISIBILITY
  1039. size_type bucket(const _Key& __k) const
  1040. {
  1041. _LIBCPP_ASSERT(bucket_count() > 0,
  1042. "unordered container::bucket(key) called when bucket_count() == 0");
  1043. return __constrain_hash(hash_function()(__k), bucket_count());
  1044. }
  1045. template <class _Key>
  1046. iterator find(const _Key& __x);
  1047. template <class _Key>
  1048. const_iterator find(const _Key& __x) const;
  1049. typedef __hash_node_destructor<__node_allocator> _Dp;
  1050. typedef unique_ptr<__node, _Dp> __node_holder;
  1051. iterator erase(const_iterator __p);
  1052. iterator erase(const_iterator __first, const_iterator __last);
  1053. template <class _Key>
  1054. size_type __erase_unique(const _Key& __k);
  1055. template <class _Key>
  1056. size_type __erase_multi(const _Key& __k);
  1057. __node_holder remove(const_iterator __p) _NOEXCEPT;
  1058. template <class _Key>
  1059. _LIBCPP_INLINE_VISIBILITY
  1060. size_type __count_unique(const _Key& __k) const;
  1061. template <class _Key>
  1062. size_type __count_multi(const _Key& __k) const;
  1063. template <class _Key>
  1064. pair<iterator, iterator>
  1065. __equal_range_unique(const _Key& __k);
  1066. template <class _Key>
  1067. pair<const_iterator, const_iterator>
  1068. __equal_range_unique(const _Key& __k) const;
  1069. template <class _Key>
  1070. pair<iterator, iterator>
  1071. __equal_range_multi(const _Key& __k);
  1072. template <class _Key>
  1073. pair<const_iterator, const_iterator>
  1074. __equal_range_multi(const _Key& __k) const;
  1075. void swap(__hash_table& __u)
  1076. #if _LIBCPP_STD_VER <= 11
  1077. _NOEXCEPT_(
  1078. __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
  1079. && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
  1080. || __is_nothrow_swappable<__pointer_allocator>::value)
  1081. && (!__node_traits::propagate_on_container_swap::value
  1082. || __is_nothrow_swappable<__node_allocator>::value)
  1083. );
  1084. #else
  1085. _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value);
  1086. #endif
  1087. _LIBCPP_INLINE_VISIBILITY
  1088. size_type max_bucket_count() const _NOEXCEPT
  1089. {return max_size(); }
  1090. size_type bucket_size(size_type __n) const;
  1091. _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
  1092. {
  1093. size_type __bc = bucket_count();
  1094. return __bc != 0 ? (float)size() / __bc : 0.f;
  1095. }
  1096. _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
  1097. {
  1098. _LIBCPP_ASSERT(__mlf > 0,
  1099. "unordered container::max_load_factor(lf) called with lf <= 0");
  1100. max_load_factor() = _VSTD::max(__mlf, load_factor());
  1101. }
  1102. _LIBCPP_INLINE_VISIBILITY
  1103. local_iterator
  1104. begin(size_type __n)
  1105. {
  1106. _LIBCPP_ASSERT(__n < bucket_count(),
  1107. "unordered container::begin(n) called with n >= bucket_count()");
  1108. #if _LIBCPP_DEBUG_LEVEL == 2
  1109. return local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
  1110. #else
  1111. return local_iterator(__bucket_list_[__n], __n, bucket_count());
  1112. #endif
  1113. }
  1114. _LIBCPP_INLINE_VISIBILITY
  1115. local_iterator
  1116. end(size_type __n)
  1117. {
  1118. _LIBCPP_ASSERT(__n < bucket_count(),
  1119. "unordered container::end(n) called with n >= bucket_count()");
  1120. #if _LIBCPP_DEBUG_LEVEL == 2
  1121. return local_iterator(nullptr, __n, bucket_count(), this);
  1122. #else
  1123. return local_iterator(nullptr, __n, bucket_count());
  1124. #endif
  1125. }
  1126. _LIBCPP_INLINE_VISIBILITY
  1127. const_local_iterator
  1128. cbegin(size_type __n) const
  1129. {
  1130. _LIBCPP_ASSERT(__n < bucket_count(),
  1131. "unordered container::cbegin(n) called with n >= bucket_count()");
  1132. #if _LIBCPP_DEBUG_LEVEL == 2
  1133. return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
  1134. #else
  1135. return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
  1136. #endif
  1137. }
  1138. _LIBCPP_INLINE_VISIBILITY
  1139. const_local_iterator
  1140. cend(size_type __n) const
  1141. {
  1142. _LIBCPP_ASSERT(__n < bucket_count(),
  1143. "unordered container::cend(n) called with n >= bucket_count()");
  1144. #if _LIBCPP_DEBUG_LEVEL == 2
  1145. return const_local_iterator(nullptr, __n, bucket_count(), this);
  1146. #else
  1147. return const_local_iterator(nullptr, __n, bucket_count());
  1148. #endif
  1149. }
  1150. #if _LIBCPP_DEBUG_LEVEL == 2
  1151. bool __dereferenceable(const const_iterator* __i) const;
  1152. bool __decrementable(const const_iterator* __i) const;
  1153. bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
  1154. bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
  1155. #endif // _LIBCPP_DEBUG_LEVEL == 2
  1156. private:
  1157. void __rehash(size_type __n);
  1158. template <class ..._Args>
  1159. __node_holder __construct_node(_Args&& ...__args);
  1160. template <class _First, class ..._Rest>
  1161. __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
  1162. _LIBCPP_INLINE_VISIBILITY
  1163. void __copy_assign_alloc(const __hash_table& __u)
  1164. {__copy_assign_alloc(__u, integral_constant<bool,
  1165. __node_traits::propagate_on_container_copy_assignment::value>());}
  1166. void __copy_assign_alloc(const __hash_table& __u, true_type);
  1167. _LIBCPP_INLINE_VISIBILITY
  1168. void __copy_assign_alloc(const __hash_table&, false_type) {}
  1169. void __move_assign(__hash_table& __u, false_type);
  1170. void __move_assign(__hash_table& __u, true_type)
  1171. _NOEXCEPT_(
  1172. is_nothrow_move_assignable<__node_allocator>::value &&
  1173. is_nothrow_move_assignable<hasher>::value &&
  1174. is_nothrow_move_assignable<key_equal>::value);
  1175. _LIBCPP_INLINE_VISIBILITY
  1176. void __move_assign_alloc(__hash_table& __u)
  1177. _NOEXCEPT_(
  1178. !__node_traits::propagate_on_container_move_assignment::value ||
  1179. (is_nothrow_move_assignable<__pointer_allocator>::value &&
  1180. is_nothrow_move_assignable<__node_allocator>::value))
  1181. {__move_assign_alloc(__u, integral_constant<bool,
  1182. __node_traits::propagate_on_container_move_assignment::value>());}
  1183. _LIBCPP_INLINE_VISIBILITY
  1184. void __move_assign_alloc(__hash_table& __u, true_type)
  1185. _NOEXCEPT_(
  1186. is_nothrow_move_assignable<__pointer_allocator>::value &&
  1187. is_nothrow_move_assignable<__node_allocator>::value)
  1188. {
  1189. __bucket_list_.get_deleter().__alloc() =
  1190. _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
  1191. __node_alloc() = _VSTD::move(__u.__node_alloc());
  1192. }
  1193. _LIBCPP_INLINE_VISIBILITY
  1194. void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
  1195. void __deallocate_node(__next_pointer __np) _NOEXCEPT;
  1196. __next_pointer __detach() _NOEXCEPT;
  1197. template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
  1198. template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
  1199. };
  1200. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1201. inline
  1202. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
  1203. _NOEXCEPT_(
  1204. is_nothrow_default_constructible<__bucket_list>::value &&
  1205. is_nothrow_default_constructible<__first_node>::value &&
  1206. is_nothrow_default_constructible<__node_allocator>::value &&
  1207. is_nothrow_default_constructible<hasher>::value &&
  1208. is_nothrow_default_constructible<key_equal>::value)
  1209. : __p2_(0, __default_init_tag()),
  1210. __p3_(1.0f, __default_init_tag())
  1211. {
  1212. }
  1213. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1214. inline
  1215. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
  1216. const key_equal& __eql)
  1217. : __bucket_list_(nullptr, __bucket_list_deleter()),
  1218. __p1_(),
  1219. __p2_(0, __hf),
  1220. __p3_(1.0f, __eql)
  1221. {
  1222. }
  1223. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1224. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
  1225. const key_equal& __eql,
  1226. const allocator_type& __a)
  1227. : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
  1228. __p1_(__default_init_tag(), __node_allocator(__a)),
  1229. __p2_(0, __hf),
  1230. __p3_(1.0f, __eql)
  1231. {
  1232. }
  1233. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1234. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
  1235. : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
  1236. __p1_(__default_init_tag(), __node_allocator(__a)),
  1237. __p2_(0, __default_init_tag()),
  1238. __p3_(1.0f, __default_init_tag())
  1239. {
  1240. }
  1241. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1242. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
  1243. : __bucket_list_(nullptr,
  1244. __bucket_list_deleter(allocator_traits<__pointer_allocator>::
  1245. select_on_container_copy_construction(
  1246. __u.__bucket_list_.get_deleter().__alloc()), 0)),
  1247. __p1_(__default_init_tag(), allocator_traits<__node_allocator>::
  1248. select_on_container_copy_construction(__u.__node_alloc())),
  1249. __p2_(0, __u.hash_function()),
  1250. __p3_(__u.__p3_)
  1251. {
  1252. }
  1253. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1254. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
  1255. const allocator_type& __a)
  1256. : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
  1257. __p1_(__default_init_tag(), __node_allocator(__a)),
  1258. __p2_(0, __u.hash_function()),
  1259. __p3_(__u.__p3_)
  1260. {
  1261. }
  1262. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1263. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
  1264. _NOEXCEPT_(
  1265. is_nothrow_move_constructible<__bucket_list>::value &&
  1266. is_nothrow_move_constructible<__first_node>::value &&
  1267. is_nothrow_move_constructible<__node_allocator>::value &&
  1268. is_nothrow_move_constructible<hasher>::value &&
  1269. is_nothrow_move_constructible<key_equal>::value)
  1270. : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
  1271. __p1_(_VSTD::move(__u.__p1_)),
  1272. __p2_(_VSTD::move(__u.__p2_)),
  1273. __p3_(_VSTD::move(__u.__p3_))
  1274. {
  1275. if (size() > 0)
  1276. {
  1277. __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
  1278. __p1_.first().__ptr();
  1279. __u.__p1_.first().__next_ = nullptr;
  1280. __u.size() = 0;
  1281. }
  1282. }
  1283. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1284. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
  1285. const allocator_type& __a)
  1286. : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
  1287. __p1_(__default_init_tag(), __node_allocator(__a)),
  1288. __p2_(0, _VSTD::move(__u.hash_function())),
  1289. __p3_(_VSTD::move(__u.__p3_))
  1290. {
  1291. if (__a == allocator_type(__u.__node_alloc()))
  1292. {
  1293. __bucket_list_.reset(__u.__bucket_list_.release());
  1294. __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
  1295. __u.__bucket_list_.get_deleter().size() = 0;
  1296. if (__u.size() > 0)
  1297. {
  1298. __p1_.first().__next_ = __u.__p1_.first().__next_;
  1299. __u.__p1_.first().__next_ = nullptr;
  1300. __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
  1301. __p1_.first().__ptr();
  1302. size() = __u.size();
  1303. __u.size() = 0;
  1304. }
  1305. }
  1306. }
  1307. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1308. __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
  1309. {
  1310. #if defined(_LIBCPP_CXX03_LANG)
  1311. static_assert((is_copy_constructible<key_equal>::value),
  1312. "Predicate must be copy-constructible.");
  1313. static_assert((is_copy_constructible<hasher>::value),
  1314. "Hasher must be copy-constructible.");
  1315. #endif
  1316. __deallocate_node(__p1_.first().__next_);
  1317. #if _LIBCPP_DEBUG_LEVEL == 2
  1318. __get_db()->__erase_c(this);
  1319. #endif
  1320. }
  1321. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1322. void
  1323. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
  1324. const __hash_table& __u, true_type)
  1325. {
  1326. if (__node_alloc() != __u.__node_alloc())
  1327. {
  1328. clear();
  1329. __bucket_list_.reset();
  1330. __bucket_list_.get_deleter().size() = 0;
  1331. }
  1332. __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
  1333. __node_alloc() = __u.__node_alloc();
  1334. }
  1335. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1336. __hash_table<_Tp, _Hash, _Equal, _Alloc>&
  1337. __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
  1338. {
  1339. if (this != _VSTD::addressof(__u))
  1340. {
  1341. __copy_assign_alloc(__u);
  1342. hash_function() = __u.hash_function();
  1343. key_eq() = __u.key_eq();
  1344. max_load_factor() = __u.max_load_factor();
  1345. __assign_multi(__u.begin(), __u.end());
  1346. }
  1347. return *this;
  1348. }
  1349. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1350. void
  1351. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np)
  1352. _NOEXCEPT
  1353. {
  1354. __node_allocator& __na = __node_alloc();
  1355. while (__np != nullptr)
  1356. {
  1357. __next_pointer __next = __np->__next_;
  1358. #if _LIBCPP_DEBUG_LEVEL == 2
  1359. __c_node* __c = __get_db()->__find_c_and_lock(this);
  1360. for (__i_node** __p = __c->end_; __p != __c->beg_; )
  1361. {
  1362. --__p;
  1363. iterator* __i = static_cast<iterator*>((*__p)->__i_);
  1364. if (__i->__node_ == __np)
  1365. {
  1366. (*__p)->__c_ = nullptr;
  1367. if (--__c->end_ != __p)
  1368. _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
  1369. }
  1370. }
  1371. __get_db()->unlock();
  1372. #endif
  1373. __node_pointer __real_np = __np->__upcast();
  1374. __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__value_));
  1375. __node_traits::deallocate(__na, __real_np, 1);
  1376. __np = __next;
  1377. }
  1378. }
  1379. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1380. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
  1381. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
  1382. {
  1383. size_type __bc = bucket_count();
  1384. for (size_type __i = 0; __i < __bc; ++__i)
  1385. __bucket_list_[__i] = nullptr;
  1386. size() = 0;
  1387. __next_pointer __cache = __p1_.first().__next_;
  1388. __p1_.first().__next_ = nullptr;
  1389. return __cache;
  1390. }
  1391. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1392. void
  1393. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
  1394. __hash_table& __u, true_type)
  1395. _NOEXCEPT_(
  1396. is_nothrow_move_assignable<__node_allocator>::value &&
  1397. is_nothrow_move_assignable<hasher>::value &&
  1398. is_nothrow_move_assignable<key_equal>::value)
  1399. {
  1400. clear();
  1401. __bucket_list_.reset(__u.__bucket_list_.release());
  1402. __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
  1403. __u.__bucket_list_.get_deleter().size() = 0;
  1404. __move_assign_alloc(__u);
  1405. size() = __u.size();
  1406. hash_function() = _VSTD::move(__u.hash_function());
  1407. max_load_factor() = __u.max_load_factor();
  1408. key_eq() = _VSTD::move(__u.key_eq());
  1409. __p1_.first().__next_ = __u.__p1_.first().__next_;
  1410. if (size() > 0)
  1411. {
  1412. __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
  1413. __p1_.first().__ptr();
  1414. __u.__p1_.first().__next_ = nullptr;
  1415. __u.size() = 0;
  1416. }
  1417. #if _LIBCPP_DEBUG_LEVEL == 2
  1418. __get_db()->swap(this, _VSTD::addressof(__u));
  1419. #endif
  1420. }
  1421. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1422. void
  1423. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
  1424. __hash_table& __u, false_type)
  1425. {
  1426. if (__node_alloc() == __u.__node_alloc())
  1427. __move_assign(__u, true_type());
  1428. else
  1429. {
  1430. hash_function() = _VSTD::move(__u.hash_function());
  1431. key_eq() = _VSTD::move(__u.key_eq());
  1432. max_load_factor() = __u.max_load_factor();
  1433. if (bucket_count() != 0)
  1434. {
  1435. __next_pointer __cache = __detach();
  1436. #ifndef _LIBCPP_NO_EXCEPTIONS
  1437. try
  1438. {
  1439. #endif // _LIBCPP_NO_EXCEPTIONS
  1440. const_iterator __i = __u.begin();
  1441. while (__cache != nullptr && __u.size() != 0)
  1442. {
  1443. __cache->__upcast()->__value_ =
  1444. _VSTD::move(__u.remove(__i++)->__value_);
  1445. __next_pointer __next = __cache->__next_;
  1446. __node_insert_multi(__cache->__upcast());
  1447. __cache = __next;
  1448. }
  1449. #ifndef _LIBCPP_NO_EXCEPTIONS
  1450. }
  1451. catch (...)
  1452. {
  1453. __deallocate_node(__cache);
  1454. throw;
  1455. }
  1456. #endif // _LIBCPP_NO_EXCEPTIONS
  1457. __deallocate_node(__cache);
  1458. }
  1459. const_iterator __i = __u.begin();
  1460. while (__u.size() != 0)
  1461. {
  1462. __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__value_));
  1463. __node_insert_multi(__h.get());
  1464. __h.release();
  1465. }
  1466. }
  1467. }
  1468. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1469. inline
  1470. __hash_table<_Tp, _Hash, _Equal, _Alloc>&
  1471. __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
  1472. _NOEXCEPT_(
  1473. __node_traits::propagate_on_container_move_assignment::value &&
  1474. is_nothrow_move_assignable<__node_allocator>::value &&
  1475. is_nothrow_move_assignable<hasher>::value &&
  1476. is_nothrow_move_assignable<key_equal>::value)
  1477. {
  1478. __move_assign(__u, integral_constant<bool,
  1479. __node_traits::propagate_on_container_move_assignment::value>());
  1480. return *this;
  1481. }
  1482. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1483. template <class _InputIterator>
  1484. void
  1485. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
  1486. _InputIterator __last)
  1487. {
  1488. typedef iterator_traits<_InputIterator> _ITraits;
  1489. typedef typename _ITraits::value_type _ItValueType;
  1490. static_assert((is_same<_ItValueType, __container_value_type>::value),
  1491. "__assign_unique may only be called with the containers value type");
  1492. if (bucket_count() != 0)
  1493. {
  1494. __next_pointer __cache = __detach();
  1495. #ifndef _LIBCPP_NO_EXCEPTIONS
  1496. try
  1497. {
  1498. #endif // _LIBCPP_NO_EXCEPTIONS
  1499. for (; __cache != nullptr && __first != __last; ++__first)
  1500. {
  1501. __cache->__upcast()->__value_ = *__first;
  1502. __next_pointer __next = __cache->__next_;
  1503. __node_insert_unique(__cache->__upcast());
  1504. __cache = __next;
  1505. }
  1506. #ifndef _LIBCPP_NO_EXCEPTIONS
  1507. }
  1508. catch (...)
  1509. {
  1510. __deallocate_node(__cache);
  1511. throw;
  1512. }
  1513. #endif // _LIBCPP_NO_EXCEPTIONS
  1514. __deallocate_node(__cache);
  1515. }
  1516. for (; __first != __last; ++__first)
  1517. __insert_unique(*__first);
  1518. }
  1519. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1520. template <class _InputIterator>
  1521. void
  1522. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
  1523. _InputIterator __last)
  1524. {
  1525. typedef iterator_traits<_InputIterator> _ITraits;
  1526. typedef typename _ITraits::value_type _ItValueType;
  1527. static_assert((is_same<_ItValueType, __container_value_type>::value ||
  1528. is_same<_ItValueType, __node_value_type>::value),
  1529. "__assign_multi may only be called with the containers value type"
  1530. " or the nodes value type");
  1531. if (bucket_count() != 0)
  1532. {
  1533. __next_pointer __cache = __detach();
  1534. #ifndef _LIBCPP_NO_EXCEPTIONS
  1535. try
  1536. {
  1537. #endif // _LIBCPP_NO_EXCEPTIONS
  1538. for (; __cache != nullptr && __first != __last; ++__first)
  1539. {
  1540. __cache->__upcast()->__value_ = *__first;
  1541. __next_pointer __next = __cache->__next_;
  1542. __node_insert_multi(__cache->__upcast());
  1543. __cache = __next;
  1544. }
  1545. #ifndef _LIBCPP_NO_EXCEPTIONS
  1546. }
  1547. catch (...)
  1548. {
  1549. __deallocate_node(__cache);
  1550. throw;
  1551. }
  1552. #endif // _LIBCPP_NO_EXCEPTIONS
  1553. __deallocate_node(__cache);
  1554. }
  1555. for (; __first != __last; ++__first)
  1556. __insert_multi(_NodeTypes::__get_value(*__first));
  1557. }
  1558. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1559. inline
  1560. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  1561. __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
  1562. {
  1563. #if _LIBCPP_DEBUG_LEVEL == 2
  1564. return iterator(__p1_.first().__next_, this);
  1565. #else
  1566. return iterator(__p1_.first().__next_);
  1567. #endif
  1568. }
  1569. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1570. inline
  1571. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  1572. __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
  1573. {
  1574. #if _LIBCPP_DEBUG_LEVEL == 2
  1575. return iterator(nullptr, this);
  1576. #else
  1577. return iterator(nullptr);
  1578. #endif
  1579. }
  1580. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1581. inline
  1582. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
  1583. __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
  1584. {
  1585. #if _LIBCPP_DEBUG_LEVEL == 2
  1586. return const_iterator(__p1_.first().__next_, this);
  1587. #else
  1588. return const_iterator(__p1_.first().__next_);
  1589. #endif
  1590. }
  1591. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1592. inline
  1593. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
  1594. __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
  1595. {
  1596. #if _LIBCPP_DEBUG_LEVEL == 2
  1597. return const_iterator(nullptr, this);
  1598. #else
  1599. return const_iterator(nullptr);
  1600. #endif
  1601. }
  1602. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1603. void
  1604. __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
  1605. {
  1606. if (size() > 0)
  1607. {
  1608. __deallocate_node(__p1_.first().__next_);
  1609. __p1_.first().__next_ = nullptr;
  1610. size_type __bc = bucket_count();
  1611. for (size_type __i = 0; __i < __bc; ++__i)
  1612. __bucket_list_[__i] = nullptr;
  1613. size() = 0;
  1614. }
  1615. }
  1616. // Prepare the container for an insertion of the value __value with the hash
  1617. // __hash. This does a lookup into the container to see if __value is already
  1618. // present, and performs a rehash if necessary. Returns a pointer to the
  1619. // existing element if it exists, otherwise nullptr.
  1620. //
  1621. // Note that this function does forward exceptions if key_eq() throws, and never
  1622. // mutates __value or actually inserts into the map.
  1623. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1624. _LIBCPP_INLINE_VISIBILITY
  1625. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
  1626. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(
  1627. size_t __hash, value_type& __value)
  1628. {
  1629. size_type __bc = bucket_count();
  1630. if (__bc != 0)
  1631. {
  1632. size_t __chash = __constrain_hash(__hash, __bc);
  1633. __next_pointer __ndptr = __bucket_list_[__chash];
  1634. if (__ndptr != nullptr)
  1635. {
  1636. for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
  1637. __constrain_hash(__ndptr->__hash(), __bc) == __chash;
  1638. __ndptr = __ndptr->__next_)
  1639. {
  1640. if (key_eq()(__ndptr->__upcast()->__value_, __value))
  1641. return __ndptr;
  1642. }
  1643. }
  1644. }
  1645. if (size()+1 > __bc * max_load_factor() || __bc == 0)
  1646. {
  1647. rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
  1648. size_type(ceil(float(size() + 1) / max_load_factor()))));
  1649. }
  1650. return nullptr;
  1651. }
  1652. // Insert the node __nd into the container by pushing it into the right bucket,
  1653. // and updating size(). Assumes that __nd->__hash is up-to-date, and that
  1654. // rehashing has already occurred and that no element with the same key exists
  1655. // in the map.
  1656. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1657. _LIBCPP_INLINE_VISIBILITY
  1658. void
  1659. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(
  1660. __node_pointer __nd) _NOEXCEPT
  1661. {
  1662. size_type __bc = bucket_count();
  1663. size_t __chash = __constrain_hash(__nd->__hash(), __bc);
  1664. // insert_after __bucket_list_[__chash], or __first_node if bucket is null
  1665. __next_pointer __pn = __bucket_list_[__chash];
  1666. if (__pn == nullptr)
  1667. {
  1668. __pn =__p1_.first().__ptr();
  1669. __nd->__next_ = __pn->__next_;
  1670. __pn->__next_ = __nd->__ptr();
  1671. // fix up __bucket_list_
  1672. __bucket_list_[__chash] = __pn;
  1673. if (__nd->__next_ != nullptr)
  1674. __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
  1675. }
  1676. else
  1677. {
  1678. __nd->__next_ = __pn->__next_;
  1679. __pn->__next_ = __nd->__ptr();
  1680. }
  1681. ++size();
  1682. }
  1683. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1684. pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
  1685. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
  1686. {
  1687. __nd->__hash_ = hash_function()(__nd->__value_);
  1688. __next_pointer __existing_node =
  1689. __node_insert_unique_prepare(__nd->__hash(), __nd->__value_);
  1690. // Insert the node, unless it already exists in the container.
  1691. bool __inserted = false;
  1692. if (__existing_node == nullptr)
  1693. {
  1694. __node_insert_unique_perform(__nd);
  1695. __existing_node = __nd->__ptr();
  1696. __inserted = true;
  1697. }
  1698. #if _LIBCPP_DEBUG_LEVEL == 2
  1699. return pair<iterator, bool>(iterator(__existing_node, this), __inserted);
  1700. #else
  1701. return pair<iterator, bool>(iterator(__existing_node), __inserted);
  1702. #endif
  1703. }
  1704. // Prepare the container for an insertion of the value __cp_val with the hash
  1705. // __cp_hash. This does a lookup into the container to see if __cp_value is
  1706. // already present, and performs a rehash if necessary. Returns a pointer to the
  1707. // last occurrence of __cp_val in the map.
  1708. //
  1709. // Note that this function does forward exceptions if key_eq() throws, and never
  1710. // mutates __value or actually inserts into the map.
  1711. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1712. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
  1713. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(
  1714. size_t __cp_hash, value_type& __cp_val)
  1715. {
  1716. size_type __bc = bucket_count();
  1717. if (size()+1 > __bc * max_load_factor() || __bc == 0)
  1718. {
  1719. rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
  1720. size_type(ceil(float(size() + 1) / max_load_factor()))));
  1721. __bc = bucket_count();
  1722. }
  1723. size_t __chash = __constrain_hash(__cp_hash, __bc);
  1724. __next_pointer __pn = __bucket_list_[__chash];
  1725. if (__pn != nullptr)
  1726. {
  1727. for (bool __found = false; __pn->__next_ != nullptr &&
  1728. __constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
  1729. __pn = __pn->__next_)
  1730. {
  1731. // __found key_eq() action
  1732. // false false loop
  1733. // true true loop
  1734. // false true set __found to true
  1735. // true false break
  1736. if (__found != (__pn->__next_->__hash() == __cp_hash &&
  1737. key_eq()(__pn->__next_->__upcast()->__value_, __cp_val)))
  1738. {
  1739. if (!__found)
  1740. __found = true;
  1741. else
  1742. break;
  1743. }
  1744. }
  1745. }
  1746. return __pn;
  1747. }
  1748. // Insert the node __cp into the container after __pn (which is the last node in
  1749. // the bucket that compares equal to __cp). Rehashing, and checking for
  1750. // uniqueness has already been performed (in __node_insert_multi_prepare), so
  1751. // all we need to do is update the bucket and size(). Assumes that __cp->__hash
  1752. // is up-to-date.
  1753. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1754. void
  1755. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
  1756. __node_pointer __cp, __next_pointer __pn) _NOEXCEPT
  1757. {
  1758. size_type __bc = bucket_count();
  1759. size_t __chash = __constrain_hash(__cp->__hash_, __bc);
  1760. if (__pn == nullptr)
  1761. {
  1762. __pn =__p1_.first().__ptr();
  1763. __cp->__next_ = __pn->__next_;
  1764. __pn->__next_ = __cp->__ptr();
  1765. // fix up __bucket_list_
  1766. __bucket_list_[__chash] = __pn;
  1767. if (__cp->__next_ != nullptr)
  1768. __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
  1769. = __cp->__ptr();
  1770. }
  1771. else
  1772. {
  1773. __cp->__next_ = __pn->__next_;
  1774. __pn->__next_ = __cp->__ptr();
  1775. if (__cp->__next_ != nullptr)
  1776. {
  1777. size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc);
  1778. if (__nhash != __chash)
  1779. __bucket_list_[__nhash] = __cp->__ptr();
  1780. }
  1781. }
  1782. ++size();
  1783. }
  1784. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1785. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  1786. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
  1787. {
  1788. __cp->__hash_ = hash_function()(__cp->__value_);
  1789. __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_);
  1790. __node_insert_multi_perform(__cp, __pn);
  1791. #if _LIBCPP_DEBUG_LEVEL == 2
  1792. return iterator(__cp->__ptr(), this);
  1793. #else
  1794. return iterator(__cp->__ptr());
  1795. #endif
  1796. }
  1797. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1798. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  1799. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
  1800. const_iterator __p, __node_pointer __cp)
  1801. {
  1802. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
  1803. "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
  1804. " referring to this unordered container");
  1805. if (__p != end() && key_eq()(*__p, __cp->__value_))
  1806. {
  1807. __next_pointer __np = __p.__node_;
  1808. __cp->__hash_ = __np->__hash();
  1809. size_type __bc = bucket_count();
  1810. if (size()+1 > __bc * max_load_factor() || __bc == 0)
  1811. {
  1812. rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
  1813. size_type(ceil(float(size() + 1) / max_load_factor()))));
  1814. __bc = bucket_count();
  1815. }
  1816. size_t __chash = __constrain_hash(__cp->__hash_, __bc);
  1817. __next_pointer __pp = __bucket_list_[__chash];
  1818. while (__pp->__next_ != __np)
  1819. __pp = __pp->__next_;
  1820. __cp->__next_ = __np;
  1821. __pp->__next_ = static_cast<__next_pointer>(__cp);
  1822. ++size();
  1823. #if _LIBCPP_DEBUG_LEVEL == 2
  1824. return iterator(static_cast<__next_pointer>(__cp), this);
  1825. #else
  1826. return iterator(static_cast<__next_pointer>(__cp));
  1827. #endif
  1828. }
  1829. return __node_insert_multi(__cp);
  1830. }
  1831. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1832. template <class _Key, class ..._Args>
  1833. pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
  1834. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
  1835. {
  1836. size_t __hash = hash_function()(__k);
  1837. size_type __bc = bucket_count();
  1838. bool __inserted = false;
  1839. __next_pointer __nd;
  1840. size_t __chash;
  1841. if (__bc != 0)
  1842. {
  1843. __chash = __constrain_hash(__hash, __bc);
  1844. __nd = __bucket_list_[__chash];
  1845. if (__nd != nullptr)
  1846. {
  1847. for (__nd = __nd->__next_; __nd != nullptr &&
  1848. (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash);
  1849. __nd = __nd->__next_)
  1850. {
  1851. if (key_eq()(__nd->__upcast()->__value_, __k))
  1852. goto __done;
  1853. }
  1854. }
  1855. }
  1856. {
  1857. __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
  1858. if (size()+1 > __bc * max_load_factor() || __bc == 0)
  1859. {
  1860. rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
  1861. size_type(ceil(float(size() + 1) / max_load_factor()))));
  1862. __bc = bucket_count();
  1863. __chash = __constrain_hash(__hash, __bc);
  1864. }
  1865. // insert_after __bucket_list_[__chash], or __first_node if bucket is null
  1866. __next_pointer __pn = __bucket_list_[__chash];
  1867. if (__pn == nullptr)
  1868. {
  1869. __pn = __p1_.first().__ptr();
  1870. __h->__next_ = __pn->__next_;
  1871. __pn->__next_ = __h.get()->__ptr();
  1872. // fix up __bucket_list_
  1873. __bucket_list_[__chash] = __pn;
  1874. if (__h->__next_ != nullptr)
  1875. __bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)]
  1876. = __h.get()->__ptr();
  1877. }
  1878. else
  1879. {
  1880. __h->__next_ = __pn->__next_;
  1881. __pn->__next_ = static_cast<__next_pointer>(__h.get());
  1882. }
  1883. __nd = static_cast<__next_pointer>(__h.release());
  1884. // increment size
  1885. ++size();
  1886. __inserted = true;
  1887. }
  1888. __done:
  1889. #if _LIBCPP_DEBUG_LEVEL == 2
  1890. return pair<iterator, bool>(iterator(__nd, this), __inserted);
  1891. #else
  1892. return pair<iterator, bool>(iterator(__nd), __inserted);
  1893. #endif
  1894. }
  1895. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1896. template <class... _Args>
  1897. pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
  1898. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args)
  1899. {
  1900. __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
  1901. pair<iterator, bool> __r = __node_insert_unique(__h.get());
  1902. if (__r.second)
  1903. __h.release();
  1904. return __r;
  1905. }
  1906. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1907. template <class... _Args>
  1908. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  1909. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
  1910. {
  1911. __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
  1912. iterator __r = __node_insert_multi(__h.get());
  1913. __h.release();
  1914. return __r;
  1915. }
  1916. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1917. template <class... _Args>
  1918. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  1919. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
  1920. const_iterator __p, _Args&&... __args)
  1921. {
  1922. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
  1923. "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
  1924. " referring to this unordered container");
  1925. __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
  1926. iterator __r = __node_insert_multi(__p, __h.get());
  1927. __h.release();
  1928. return __r;
  1929. }
  1930. #if _LIBCPP_STD_VER > 14
  1931. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1932. template <class _NodeHandle, class _InsertReturnType>
  1933. _LIBCPP_INLINE_VISIBILITY
  1934. _InsertReturnType
  1935. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
  1936. _NodeHandle&& __nh)
  1937. {
  1938. if (__nh.empty())
  1939. return _InsertReturnType{end(), false, _NodeHandle()};
  1940. pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
  1941. if (__result.second)
  1942. __nh.__release_ptr();
  1943. return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)};
  1944. }
  1945. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1946. template <class _NodeHandle>
  1947. _LIBCPP_INLINE_VISIBILITY
  1948. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  1949. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
  1950. const_iterator, _NodeHandle&& __nh)
  1951. {
  1952. if (__nh.empty())
  1953. return end();
  1954. pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
  1955. if (__result.second)
  1956. __nh.__release_ptr();
  1957. return __result.first;
  1958. }
  1959. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1960. template <class _NodeHandle>
  1961. _LIBCPP_INLINE_VISIBILITY
  1962. _NodeHandle
  1963. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
  1964. key_type const& __key)
  1965. {
  1966. iterator __i = find(__key);
  1967. if (__i == end())
  1968. return _NodeHandle();
  1969. return __node_handle_extract<_NodeHandle>(__i);
  1970. }
  1971. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1972. template <class _NodeHandle>
  1973. _LIBCPP_INLINE_VISIBILITY
  1974. _NodeHandle
  1975. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
  1976. const_iterator __p)
  1977. {
  1978. allocator_type __alloc(__node_alloc());
  1979. return _NodeHandle(remove(__p).release(), __alloc);
  1980. }
  1981. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  1982. template <class _Table>
  1983. _LIBCPP_INLINE_VISIBILITY
  1984. void
  1985. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(
  1986. _Table& __source)
  1987. {
  1988. static_assert(is_same<__node, typename _Table::__node>::value, "");
  1989. for (typename _Table::iterator __it = __source.begin();
  1990. __it != __source.end();)
  1991. {
  1992. __node_pointer __src_ptr = __it.__node_->__upcast();
  1993. size_t __hash = hash_function()(__src_ptr->__value_);
  1994. __next_pointer __existing_node =
  1995. __node_insert_unique_prepare(__hash, __src_ptr->__value_);
  1996. auto __prev_iter = __it++;
  1997. if (__existing_node == nullptr)
  1998. {
  1999. (void)__source.remove(__prev_iter).release();
  2000. __src_ptr->__hash_ = __hash;
  2001. __node_insert_unique_perform(__src_ptr);
  2002. }
  2003. }
  2004. }
  2005. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2006. template <class _NodeHandle>
  2007. _LIBCPP_INLINE_VISIBILITY
  2008. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  2009. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
  2010. _NodeHandle&& __nh)
  2011. {
  2012. if (__nh.empty())
  2013. return end();
  2014. iterator __result = __node_insert_multi(__nh.__ptr_);
  2015. __nh.__release_ptr();
  2016. return __result;
  2017. }
  2018. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2019. template <class _NodeHandle>
  2020. _LIBCPP_INLINE_VISIBILITY
  2021. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  2022. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
  2023. const_iterator __hint, _NodeHandle&& __nh)
  2024. {
  2025. if (__nh.empty())
  2026. return end();
  2027. iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
  2028. __nh.__release_ptr();
  2029. return __result;
  2030. }
  2031. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2032. template <class _Table>
  2033. _LIBCPP_INLINE_VISIBILITY
  2034. void
  2035. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(
  2036. _Table& __source)
  2037. {
  2038. static_assert(is_same<typename _Table::__node, __node>::value, "");
  2039. for (typename _Table::iterator __it = __source.begin();
  2040. __it != __source.end();)
  2041. {
  2042. __node_pointer __src_ptr = __it.__node_->__upcast();
  2043. size_t __src_hash = hash_function()(__src_ptr->__value_);
  2044. __next_pointer __pn =
  2045. __node_insert_multi_prepare(__src_hash, __src_ptr->__value_);
  2046. (void)__source.remove(__it++).release();
  2047. __src_ptr->__hash_ = __src_hash;
  2048. __node_insert_multi_perform(__src_ptr, __pn);
  2049. }
  2050. }
  2051. #endif // _LIBCPP_STD_VER > 14
  2052. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2053. void
  2054. __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
  2055. _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
  2056. {
  2057. if (__n == 1)
  2058. __n = 2;
  2059. else if (__n & (__n - 1))
  2060. __n = __next_prime(__n);
  2061. size_type __bc = bucket_count();
  2062. if (__n > __bc)
  2063. __rehash(__n);
  2064. else if (__n < __bc)
  2065. {
  2066. __n = _VSTD::max<size_type>
  2067. (
  2068. __n,
  2069. __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
  2070. __next_prime(size_t(ceil(float(size()) / max_load_factor())))
  2071. );
  2072. if (__n < __bc)
  2073. __rehash(__n);
  2074. }
  2075. }
  2076. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2077. void
  2078. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
  2079. {
  2080. #if _LIBCPP_DEBUG_LEVEL == 2
  2081. __get_db()->__invalidate_all(this);
  2082. #endif
  2083. __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
  2084. __bucket_list_.reset(__nbc > 0 ?
  2085. __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
  2086. __bucket_list_.get_deleter().size() = __nbc;
  2087. if (__nbc > 0)
  2088. {
  2089. for (size_type __i = 0; __i < __nbc; ++__i)
  2090. __bucket_list_[__i] = nullptr;
  2091. __next_pointer __pp = __p1_.first().__ptr();
  2092. __next_pointer __cp = __pp->__next_;
  2093. if (__cp != nullptr)
  2094. {
  2095. size_type __chash = __constrain_hash(__cp->__hash(), __nbc);
  2096. __bucket_list_[__chash] = __pp;
  2097. size_type __phash = __chash;
  2098. for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr;
  2099. __cp = __pp->__next_)
  2100. {
  2101. __chash = __constrain_hash(__cp->__hash(), __nbc);
  2102. if (__chash == __phash)
  2103. __pp = __cp;
  2104. else
  2105. {
  2106. if (__bucket_list_[__chash] == nullptr)
  2107. {
  2108. __bucket_list_[__chash] = __pp;
  2109. __pp = __cp;
  2110. __phash = __chash;
  2111. }
  2112. else
  2113. {
  2114. __next_pointer __np = __cp;
  2115. for (; __np->__next_ != nullptr &&
  2116. key_eq()(__cp->__upcast()->__value_,
  2117. __np->__next_->__upcast()->__value_);
  2118. __np = __np->__next_)
  2119. ;
  2120. __pp->__next_ = __np->__next_;
  2121. __np->__next_ = __bucket_list_[__chash]->__next_;
  2122. __bucket_list_[__chash]->__next_ = __cp;
  2123. }
  2124. }
  2125. }
  2126. }
  2127. }
  2128. }
  2129. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2130. template <class _Key>
  2131. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  2132. __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
  2133. {
  2134. size_t __hash = hash_function()(__k);
  2135. size_type __bc = bucket_count();
  2136. if (__bc != 0)
  2137. {
  2138. size_t __chash = __constrain_hash(__hash, __bc);
  2139. __next_pointer __nd = __bucket_list_[__chash];
  2140. if (__nd != nullptr)
  2141. {
  2142. for (__nd = __nd->__next_; __nd != nullptr &&
  2143. (__nd->__hash() == __hash
  2144. || __constrain_hash(__nd->__hash(), __bc) == __chash);
  2145. __nd = __nd->__next_)
  2146. {
  2147. if ((__nd->__hash() == __hash)
  2148. && key_eq()(__nd->__upcast()->__value_, __k))
  2149. #if _LIBCPP_DEBUG_LEVEL == 2
  2150. return iterator(__nd, this);
  2151. #else
  2152. return iterator(__nd);
  2153. #endif
  2154. }
  2155. }
  2156. }
  2157. return end();
  2158. }
  2159. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2160. template <class _Key>
  2161. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
  2162. __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
  2163. {
  2164. size_t __hash = hash_function()(__k);
  2165. size_type __bc = bucket_count();
  2166. if (__bc != 0)
  2167. {
  2168. size_t __chash = __constrain_hash(__hash, __bc);
  2169. __next_pointer __nd = __bucket_list_[__chash];
  2170. if (__nd != nullptr)
  2171. {
  2172. for (__nd = __nd->__next_; __nd != nullptr &&
  2173. (__hash == __nd->__hash()
  2174. || __constrain_hash(__nd->__hash(), __bc) == __chash);
  2175. __nd = __nd->__next_)
  2176. {
  2177. if ((__nd->__hash() == __hash)
  2178. && key_eq()(__nd->__upcast()->__value_, __k))
  2179. #if _LIBCPP_DEBUG_LEVEL == 2
  2180. return const_iterator(__nd, this);
  2181. #else
  2182. return const_iterator(__nd);
  2183. #endif
  2184. }
  2185. }
  2186. }
  2187. return end();
  2188. }
  2189. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2190. template <class ..._Args>
  2191. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
  2192. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
  2193. {
  2194. static_assert(!__is_hash_value_type<_Args...>::value,
  2195. "Construct cannot be called with a hash value type");
  2196. __node_allocator& __na = __node_alloc();
  2197. __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
  2198. __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
  2199. __h.get_deleter().__value_constructed = true;
  2200. __h->__hash_ = hash_function()(__h->__value_);
  2201. __h->__next_ = nullptr;
  2202. return __h;
  2203. }
  2204. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2205. template <class _First, class ..._Rest>
  2206. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
  2207. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(
  2208. size_t __hash, _First&& __f, _Rest&& ...__rest)
  2209. {
  2210. static_assert(!__is_hash_value_type<_First, _Rest...>::value,
  2211. "Construct cannot be called with a hash value type");
  2212. __node_allocator& __na = __node_alloc();
  2213. __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
  2214. __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_),
  2215. _VSTD::forward<_First>(__f),
  2216. _VSTD::forward<_Rest>(__rest)...);
  2217. __h.get_deleter().__value_constructed = true;
  2218. __h->__hash_ = __hash;
  2219. __h->__next_ = nullptr;
  2220. return __h;
  2221. }
  2222. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2223. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  2224. __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
  2225. {
  2226. __next_pointer __np = __p.__node_;
  2227. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
  2228. "unordered container erase(iterator) called with an iterator not"
  2229. " referring to this container");
  2230. _LIBCPP_DEBUG_ASSERT(__p != end(),
  2231. "unordered container erase(iterator) called with a non-dereferenceable iterator");
  2232. #if _LIBCPP_DEBUG_LEVEL == 2
  2233. iterator __r(__np, this);
  2234. #else
  2235. iterator __r(__np);
  2236. #endif
  2237. ++__r;
  2238. remove(__p);
  2239. return __r;
  2240. }
  2241. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2242. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
  2243. __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
  2244. const_iterator __last)
  2245. {
  2246. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__first)) == this,
  2247. "unordered container::erase(iterator, iterator) called with an iterator not"
  2248. " referring to this container");
  2249. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__last)) == this,
  2250. "unordered container::erase(iterator, iterator) called with an iterator not"
  2251. " referring to this container");
  2252. for (const_iterator __p = __first; __first != __last; __p = __first)
  2253. {
  2254. ++__first;
  2255. erase(__p);
  2256. }
  2257. __next_pointer __np = __last.__node_;
  2258. #if _LIBCPP_DEBUG_LEVEL == 2
  2259. return iterator (__np, this);
  2260. #else
  2261. return iterator (__np);
  2262. #endif
  2263. }
  2264. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2265. template <class _Key>
  2266. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
  2267. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
  2268. {
  2269. iterator __i = find(__k);
  2270. if (__i == end())
  2271. return 0;
  2272. erase(__i);
  2273. return 1;
  2274. }
  2275. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2276. template <class _Key>
  2277. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
  2278. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
  2279. {
  2280. size_type __r = 0;
  2281. iterator __i = find(__k);
  2282. if (__i != end())
  2283. {
  2284. iterator __e = end();
  2285. do
  2286. {
  2287. erase(__i++);
  2288. ++__r;
  2289. } while (__i != __e && key_eq()(*__i, __k));
  2290. }
  2291. return __r;
  2292. }
  2293. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2294. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
  2295. __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
  2296. {
  2297. // current node
  2298. __next_pointer __cn = __p.__node_;
  2299. size_type __bc = bucket_count();
  2300. size_t __chash = __constrain_hash(__cn->__hash(), __bc);
  2301. // find previous node
  2302. __next_pointer __pn = __bucket_list_[__chash];
  2303. for (; __pn->__next_ != __cn; __pn = __pn->__next_)
  2304. ;
  2305. // Fix up __bucket_list_
  2306. // if __pn is not in same bucket (before begin is not in same bucket) &&
  2307. // if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
  2308. if (__pn == __p1_.first().__ptr()
  2309. || __constrain_hash(__pn->__hash(), __bc) != __chash)
  2310. {
  2311. if (__cn->__next_ == nullptr
  2312. || __constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
  2313. __bucket_list_[__chash] = nullptr;
  2314. }
  2315. // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
  2316. if (__cn->__next_ != nullptr)
  2317. {
  2318. size_t __nhash = __constrain_hash(__cn->__next_->__hash(), __bc);
  2319. if (__nhash != __chash)
  2320. __bucket_list_[__nhash] = __pn;
  2321. }
  2322. // remove __cn
  2323. __pn->__next_ = __cn->__next_;
  2324. __cn->__next_ = nullptr;
  2325. --size();
  2326. #if _LIBCPP_DEBUG_LEVEL == 2
  2327. __c_node* __c = __get_db()->__find_c_and_lock(this);
  2328. for (__i_node** __dp = __c->end_; __dp != __c->beg_; )
  2329. {
  2330. --__dp;
  2331. iterator* __i = static_cast<iterator*>((*__dp)->__i_);
  2332. if (__i->__node_ == __cn)
  2333. {
  2334. (*__dp)->__c_ = nullptr;
  2335. if (--__c->end_ != __dp)
  2336. _VSTD::memmove(__dp, __dp+1, (__c->end_ - __dp)*sizeof(__i_node*));
  2337. }
  2338. }
  2339. __get_db()->unlock();
  2340. #endif
  2341. return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
  2342. }
  2343. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2344. template <class _Key>
  2345. inline
  2346. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
  2347. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
  2348. {
  2349. return static_cast<size_type>(find(__k) != end());
  2350. }
  2351. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2352. template <class _Key>
  2353. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
  2354. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
  2355. {
  2356. size_type __r = 0;
  2357. const_iterator __i = find(__k);
  2358. if (__i != end())
  2359. {
  2360. const_iterator __e = end();
  2361. do
  2362. {
  2363. ++__i;
  2364. ++__r;
  2365. } while (__i != __e && key_eq()(*__i, __k));
  2366. }
  2367. return __r;
  2368. }
  2369. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2370. template <class _Key>
  2371. pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
  2372. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
  2373. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
  2374. const _Key& __k)
  2375. {
  2376. iterator __i = find(__k);
  2377. iterator __j = __i;
  2378. if (__i != end())
  2379. ++__j;
  2380. return pair<iterator, iterator>(__i, __j);
  2381. }
  2382. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2383. template <class _Key>
  2384. pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
  2385. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
  2386. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
  2387. const _Key& __k) const
  2388. {
  2389. const_iterator __i = find(__k);
  2390. const_iterator __j = __i;
  2391. if (__i != end())
  2392. ++__j;
  2393. return pair<const_iterator, const_iterator>(__i, __j);
  2394. }
  2395. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2396. template <class _Key>
  2397. pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
  2398. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
  2399. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
  2400. const _Key& __k)
  2401. {
  2402. iterator __i = find(__k);
  2403. iterator __j = __i;
  2404. if (__i != end())
  2405. {
  2406. iterator __e = end();
  2407. do
  2408. {
  2409. ++__j;
  2410. } while (__j != __e && key_eq()(*__j, __k));
  2411. }
  2412. return pair<iterator, iterator>(__i, __j);
  2413. }
  2414. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2415. template <class _Key>
  2416. pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
  2417. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
  2418. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
  2419. const _Key& __k) const
  2420. {
  2421. const_iterator __i = find(__k);
  2422. const_iterator __j = __i;
  2423. if (__i != end())
  2424. {
  2425. const_iterator __e = end();
  2426. do
  2427. {
  2428. ++__j;
  2429. } while (__j != __e && key_eq()(*__j, __k));
  2430. }
  2431. return pair<const_iterator, const_iterator>(__i, __j);
  2432. }
  2433. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2434. void
  2435. __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
  2436. #if _LIBCPP_STD_VER <= 11
  2437. _NOEXCEPT_(
  2438. __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
  2439. && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
  2440. || __is_nothrow_swappable<__pointer_allocator>::value)
  2441. && (!__node_traits::propagate_on_container_swap::value
  2442. || __is_nothrow_swappable<__node_allocator>::value)
  2443. )
  2444. #else
  2445. _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value)
  2446. #endif
  2447. {
  2448. _LIBCPP_ASSERT(__node_traits::propagate_on_container_swap::value ||
  2449. this->__node_alloc() == __u.__node_alloc(),
  2450. "list::swap: Either propagate_on_container_swap must be true"
  2451. " or the allocators must compare equal");
  2452. {
  2453. __node_pointer_pointer __npp = __bucket_list_.release();
  2454. __bucket_list_.reset(__u.__bucket_list_.release());
  2455. __u.__bucket_list_.reset(__npp);
  2456. }
  2457. _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
  2458. _VSTD::__swap_allocator(__bucket_list_.get_deleter().__alloc(),
  2459. __u.__bucket_list_.get_deleter().__alloc());
  2460. _VSTD::__swap_allocator(__node_alloc(), __u.__node_alloc());
  2461. _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
  2462. __p2_.swap(__u.__p2_);
  2463. __p3_.swap(__u.__p3_);
  2464. if (size() > 0)
  2465. __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
  2466. __p1_.first().__ptr();
  2467. if (__u.size() > 0)
  2468. __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] =
  2469. __u.__p1_.first().__ptr();
  2470. #if _LIBCPP_DEBUG_LEVEL == 2
  2471. __get_db()->swap(this, _VSTD::addressof(__u));
  2472. #endif
  2473. }
  2474. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2475. typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
  2476. __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
  2477. {
  2478. _LIBCPP_ASSERT(__n < bucket_count(),
  2479. "unordered container::bucket_size(n) called with n >= bucket_count()");
  2480. __next_pointer __np = __bucket_list_[__n];
  2481. size_type __bc = bucket_count();
  2482. size_type __r = 0;
  2483. if (__np != nullptr)
  2484. {
  2485. for (__np = __np->__next_; __np != nullptr &&
  2486. __constrain_hash(__np->__hash(), __bc) == __n;
  2487. __np = __np->__next_, (void) ++__r)
  2488. ;
  2489. }
  2490. return __r;
  2491. }
  2492. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2493. inline _LIBCPP_INLINE_VISIBILITY
  2494. void
  2495. swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
  2496. __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
  2497. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  2498. {
  2499. __x.swap(__y);
  2500. }
  2501. #if _LIBCPP_DEBUG_LEVEL == 2
  2502. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2503. bool
  2504. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const
  2505. {
  2506. return __i->__node_ != nullptr;
  2507. }
  2508. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2509. bool
  2510. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const
  2511. {
  2512. return false;
  2513. }
  2514. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2515. bool
  2516. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
  2517. {
  2518. return false;
  2519. }
  2520. template <class _Tp, class _Hash, class _Equal, class _Alloc>
  2521. bool
  2522. __hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
  2523. {
  2524. return false;
  2525. }
  2526. #endif // _LIBCPP_DEBUG_LEVEL == 2
  2527. _LIBCPP_END_NAMESPACE_STD
  2528. _LIBCPP_POP_MACROS
  2529. #endif // _LIBCPP__HASH_TABLE