1// Internal policy header for unordered_set and unordered_map -*- C++ -*- 2 3// Copyright (C) 2010-2013 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/** @file bits/hashtable_policy.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. 28 * @headername{unordered_map,unordered_set} 29 */ 30 31#ifndef _HASHTABLE_POLICY_H 32#define _HASHTABLE_POLICY_H 1 33 34namespace std _GLIBCXX_VISIBILITY(default) 35{ 36_GLIBCXX_BEGIN_NAMESPACE_VERSION 37 38 template<typename _Key, typename _Value, typename _Alloc, 39 typename _ExtractKey, typename _Equal, 40 typename _H1, typename _H2, typename _Hash, 41 typename _RehashPolicy, typename _Traits> 42 class _Hashtable; 43 44_GLIBCXX_END_NAMESPACE_VERSION 45 46namespace __detail 47{ 48_GLIBCXX_BEGIN_NAMESPACE_VERSION 49 50 /** 51 * @defgroup hashtable-detail Base and Implementation Classes 52 * @ingroup unordered_associative_containers 53 * @{ 54 */ 55 template<typename _Key, typename _Value, 56 typename _ExtractKey, typename _Equal, 57 typename _H1, typename _H2, typename _Hash, typename _Traits> 58 struct _Hashtable_base; 59 60 // Helper function: return distance(first, last) for forward 61 // iterators, or 0 for input iterators. 62 template<class _Iterator> 63 inline typename std::iterator_traits<_Iterator>::difference_type 64 __distance_fw(_Iterator __first, _Iterator __last, 65 std::input_iterator_tag) 66 { return 0; } 67 68 template<class _Iterator> 69 inline typename std::iterator_traits<_Iterator>::difference_type 70 __distance_fw(_Iterator __first, _Iterator __last, 71 std::forward_iterator_tag) 72 { return std::distance(__first, __last); } 73 74 template<class _Iterator> 75 inline typename std::iterator_traits<_Iterator>::difference_type 76 __distance_fw(_Iterator __first, _Iterator __last) 77 { 78 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; 79 return __distance_fw(__first, __last, _Tag()); 80 } 81 82 // Helper type used to detect whether the hash functor is noexcept. 83 template <typename _Key, typename _Hash> 84 struct __is_noexcept_hash : std::integral_constant<bool, 85 noexcept(declval<const _Hash&>()(declval<const _Key&>()))> 86 { }; 87 88 struct _Identity 89 { 90 template<typename _Tp> 91 _Tp&& 92 operator()(_Tp&& __x) const 93 { return std::forward<_Tp>(__x); } 94 }; 95 96 struct _Select1st 97 { 98 template<typename _Tp> 99 auto 100 operator()(_Tp&& __x) const 101 -> decltype(std::get<0>(std::forward<_Tp>(__x))) 102 { return std::get<0>(std::forward<_Tp>(__x)); } 103 }; 104 105 // Auxiliary types used for all instantiations of _Hashtable nodes 106 // and iterators. 107 108 /** 109 * struct _Hashtable_traits 110 * 111 * Important traits for hash tables. 112 * 113 * @tparam _Cache_hash_code Boolean value. True if the value of 114 * the hash function is stored along with the value. This is a 115 * time-space tradeoff. Storing it may improve lookup speed by 116 * reducing the number of times we need to call the _Equal 117 * function. 118 * 119 * @tparam _Constant_iterators Boolean value. True if iterator and 120 * const_iterator are both constant iterator types. This is true 121 * for unordered_set and unordered_multiset, false for 122 * unordered_map and unordered_multimap. 123 * 124 * @tparam _Unique_keys Boolean value. True if the return value 125 * of _Hashtable::count(k) is always at most one, false if it may 126 * be an arbitrary number. This is true for unordered_set and 127 * unordered_map, false for unordered_multiset and 128 * unordered_multimap. 129 */ 130 template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys> 131 struct _Hashtable_traits 132 { 133 template<bool _Cond> 134 using __bool_constant = integral_constant<bool, _Cond>; 135 136 using __hash_cached = __bool_constant<_Cache_hash_code>; 137 using __constant_iterators = __bool_constant<_Constant_iterators>; 138 using __unique_keys = __bool_constant<_Unique_keys>; 139 }; 140 141 /** 142 * struct _Hash_node_base 143 * 144 * Nodes, used to wrap elements stored in the hash table. A policy 145 * template parameter of class template _Hashtable controls whether 146 * nodes also store a hash code. In some cases (e.g. strings) this 147 * may be a performance win. 148 */ 149 struct _Hash_node_base 150 { 151 _Hash_node_base* _M_nxt; 152 153 _Hash_node_base() : _M_nxt() { } 154 155 _Hash_node_base(_Hash_node_base* __next) : _M_nxt(__next) { } 156 }; 157 158 /** 159 * Primary template struct _Hash_node. 160 */ 161 template<typename _Value, bool _Cache_hash_code> 162 struct _Hash_node; 163 164 /** 165 * Specialization for nodes with caches, struct _Hash_node. 166 * 167 * Base class is __detail::_Hash_node_base. 168 */ 169 template<typename _Value> 170 struct _Hash_node<_Value, true> : _Hash_node_base 171 { 172 _Value _M_v; 173 std::size_t _M_hash_code; 174 175 template<typename... _Args> 176 _Hash_node(_Args&&... __args) 177 : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { } 178 179 _Hash_node* 180 _M_next() const { return static_cast<_Hash_node*>(_M_nxt); } 181 }; 182 183 /** 184 * Specialization for nodes without caches, struct _Hash_node. 185 * 186 * Base class is __detail::_Hash_node_base. 187 */ 188 template<typename _Value> 189 struct _Hash_node<_Value, false> : _Hash_node_base 190 { 191 _Value _M_v; 192 193 template<typename... _Args> 194 _Hash_node(_Args&&... __args) 195 : _M_v(std::forward<_Args>(__args)...) { } 196 197 _Hash_node* 198 _M_next() const { return static_cast<_Hash_node*>(_M_nxt); } 199 }; 200 201 /// Base class for node iterators. 202 template<typename _Value, bool _Cache_hash_code> 203 struct _Node_iterator_base 204 { 205 using __node_type = _Hash_node<_Value, _Cache_hash_code>; 206 207 __node_type* _M_cur; 208 209 _Node_iterator_base(__node_type* __p) 210 : _M_cur(__p) { } 211 212 void 213 _M_incr() 214 { _M_cur = _M_cur->_M_next(); } 215 }; 216 217 template<typename _Value, bool _Cache_hash_code> 218 inline bool 219 operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, 220 const _Node_iterator_base<_Value, _Cache_hash_code >& __y) 221 { return __x._M_cur == __y._M_cur; } 222 223 template<typename _Value, bool _Cache_hash_code> 224 inline bool 225 operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, 226 const _Node_iterator_base<_Value, _Cache_hash_code>& __y) 227 { return __x._M_cur != __y._M_cur; } 228 229 /// Node iterators, used to iterate through all the hashtable. 230 template<typename _Value, bool __constant_iterators, bool __cache> 231 struct _Node_iterator 232 : public _Node_iterator_base<_Value, __cache> 233 { 234 private: 235 using __base_type = _Node_iterator_base<_Value, __cache>; 236 using __node_type = typename __base_type::__node_type; 237 238 public: 239 typedef _Value value_type; 240 typedef std::ptrdiff_t difference_type; 241 typedef std::forward_iterator_tag iterator_category; 242 243 using pointer = typename std::conditional<__constant_iterators, 244 const _Value*, _Value*>::type; 245 246 using reference = typename std::conditional<__constant_iterators, 247 const _Value&, _Value&>::type; 248 249 _Node_iterator() 250 : __base_type(0) { } 251 252 explicit 253 _Node_iterator(__node_type* __p) 254 : __base_type(__p) { } 255 256 reference 257 operator*() const 258 { return this->_M_cur->_M_v; } 259 260 pointer 261 operator->() const 262 { return std::__addressof(this->_M_cur->_M_v); } 263 264 _Node_iterator& 265 operator++() 266 { 267 this->_M_incr(); 268 return *this; 269 } 270 271 _Node_iterator 272 operator++(int) 273 { 274 _Node_iterator __tmp(*this); 275 this->_M_incr(); 276 return __tmp; 277 } 278 }; 279 280 /// Node const_iterators, used to iterate through all the hashtable. 281 template<typename _Value, bool __constant_iterators, bool __cache> 282 struct _Node_const_iterator 283 : public _Node_iterator_base<_Value, __cache> 284 { 285 private: 286 using __base_type = _Node_iterator_base<_Value, __cache>; 287 using __node_type = typename __base_type::__node_type; 288 289 public: 290 typedef _Value value_type; 291 typedef std::ptrdiff_t difference_type; 292 typedef std::forward_iterator_tag iterator_category; 293 294 typedef const _Value* pointer; 295 typedef const _Value& reference; 296 297 _Node_const_iterator() 298 : __base_type(0) { } 299 300 explicit 301 _Node_const_iterator(__node_type* __p) 302 : __base_type(__p) { } 303 304 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, 305 __cache>& __x) 306 : __base_type(__x._M_cur) { } 307 308 reference 309 operator*() const 310 { return this->_M_cur->_M_v; } 311 312 pointer 313 operator->() const 314 { return std::__addressof(this->_M_cur->_M_v); } 315 316 _Node_const_iterator& 317 operator++() 318 { 319 this->_M_incr(); 320 return *this; 321 } 322 323 _Node_const_iterator 324 operator++(int) 325 { 326 _Node_const_iterator __tmp(*this); 327 this->_M_incr(); 328 return __tmp; 329 } 330 }; 331 332 // Many of class template _Hashtable's template parameters are policy 333 // classes. These are defaults for the policies. 334 335 /// Default range hashing function: use division to fold a large number 336 /// into the range [0, N). 337 struct _Mod_range_hashing 338 { 339 typedef std::size_t first_argument_type; 340 typedef std::size_t second_argument_type; 341 typedef std::size_t result_type; 342 343 result_type 344 operator()(first_argument_type __num, second_argument_type __den) const 345 { return __num % __den; } 346 }; 347 348 /// Default ranged hash function H. In principle it should be a 349 /// function object composed from objects of type H1 and H2 such that 350 /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of 351 /// h1 and h2. So instead we'll just use a tag to tell class template 352 /// hashtable to do that composition. 353 struct _Default_ranged_hash { }; 354 355 /// Default value for rehash policy. Bucket size is (usually) the 356 /// smallest prime that keeps the load factor small enough. 357 struct _Prime_rehash_policy 358 { 359 _Prime_rehash_policy(float __z = 1.0) 360 : _M_max_load_factor(__z), _M_next_resize(0) { } 361 362 float 363 max_load_factor() const noexcept 364 { return _M_max_load_factor; } 365 366 // Return a bucket size no smaller than n. 367 std::size_t 368 _M_next_bkt(std::size_t __n) const; 369 370 // Return a bucket count appropriate for n elements 371 std::size_t 372 _M_bkt_for_elements(std::size_t __n) const 373 { return __builtin_ceil(__n / (long double)_M_max_load_factor); } 374 375 // __n_bkt is current bucket count, __n_elt is current element count, 376 // and __n_ins is number of elements to be inserted. Do we need to 377 // increase bucket count? If so, return make_pair(true, n), where n 378 // is the new bucket count. If not, return make_pair(false, 0). 379 std::pair<bool, std::size_t> 380 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 381 std::size_t __n_ins) const; 382 383 typedef std::size_t _State; 384 385 _State 386 _M_state() const 387 { return _M_next_resize; } 388 389 void 390 _M_reset(_State __state) 391 { _M_next_resize = __state; } 392 393 enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; 394 395 static const std::size_t _S_growth_factor = 2; 396 397 float _M_max_load_factor; 398 mutable std::size_t _M_next_resize; 399 }; 400 401 // Base classes for std::_Hashtable. We define these base classes 402 // because in some cases we want to do different things depending on 403 // the value of a policy class. In some cases the policy class 404 // affects which member functions and nested typedefs are defined; 405 // we handle that by specializing base class templates. Several of 406 // the base class templates need to access other members of class 407 // template _Hashtable, so we use a variant of the "Curiously 408 // Recurring Template Pattern" (CRTP) technique. 409 410 /** 411 * Primary class template _Map_base. 412 * 413 * If the hashtable has a value type of the form pair<T1, T2> and a 414 * key extraction policy (_ExtractKey) that returns the first part 415 * of the pair, the hashtable gets a mapped_type typedef. If it 416 * satisfies those criteria and also has unique keys, then it also 417 * gets an operator[]. 418 */ 419 template<typename _Key, typename _Value, typename _Alloc, 420 typename _ExtractKey, typename _Equal, 421 typename _H1, typename _H2, typename _Hash, 422 typename _RehashPolicy, typename _Traits, 423 bool _Unique_keys = _Traits::__unique_keys::value> 424 struct _Map_base { }; 425 426 /// Partial specialization, __unique_keys set to false. 427 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 428 typename _H1, typename _H2, typename _Hash, 429 typename _RehashPolicy, typename _Traits> 430 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 431 _H1, _H2, _Hash, _RehashPolicy, _Traits, false> 432 { 433 using mapped_type = typename std::tuple_element<1, _Pair>::type; 434 }; 435 436 /// Partial specialization, __unique_keys set to true. 437 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 438 typename _H1, typename _H2, typename _Hash, 439 typename _RehashPolicy, typename _Traits> 440 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 441 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 442 { 443 private: 444 using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair, 445 _Select1st, 446 _Equal, _H1, _H2, _Hash, 447 _Traits>; 448 449 using __hashtable = _Hashtable<_Key, _Pair, _Alloc, 450 _Select1st, _Equal, 451 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 452 453 using __hash_code = typename __hashtable_base::__hash_code; 454 using __node_type = typename __hashtable_base::__node_type; 455 456 public: 457 using key_type = typename __hashtable_base::key_type; 458 using iterator = typename __hashtable_base::iterator; 459 using mapped_type = typename std::tuple_element<1, _Pair>::type; 460 461 mapped_type& 462 operator[](const key_type& __k); 463 464 mapped_type& 465 operator[](key_type&& __k); 466 467 // _GLIBCXX_RESOLVE_LIB_DEFECTS 468 // DR 761. unordered_map needs an at() member function. 469 mapped_type& 470 at(const key_type& __k); 471 472 const mapped_type& 473 at(const key_type& __k) const; 474 }; 475 476 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 477 typename _H1, typename _H2, typename _Hash, 478 typename _RehashPolicy, typename _Traits> 479 typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 480 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 481 ::mapped_type& 482 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 483 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 484 operator[](const key_type& __k) 485 { 486 __hashtable* __h = static_cast<__hashtable*>(this); 487 __hash_code __code = __h->_M_hash_code(__k); 488 std::size_t __n = __h->_M_bucket_index(__k, __code); 489 __node_type* __p = __h->_M_find_node(__n, __k, __code); 490 491 if (!__p) 492 { 493 __p = __h->_M_allocate_node(std::piecewise_construct, 494 std::tuple<const key_type&>(__k), 495 std::tuple<>()); 496 return __h->_M_insert_unique_node(__n, __code, __p)->second; 497 } 498 499 return (__p->_M_v).second; 500 } 501 502 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 503 typename _H1, typename _H2, typename _Hash, 504 typename _RehashPolicy, typename _Traits> 505 typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 506 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 507 ::mapped_type& 508 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 509 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 510 operator[](key_type&& __k) 511 { 512 __hashtable* __h = static_cast<__hashtable*>(this); 513 __hash_code __code = __h->_M_hash_code(__k); 514 std::size_t __n = __h->_M_bucket_index(__k, __code); 515 __node_type* __p = __h->_M_find_node(__n, __k, __code); 516 517 if (!__p) 518 { 519 __p = __h->_M_allocate_node(std::piecewise_construct, 520 std::forward_as_tuple(std::move(__k)), 521 std::tuple<>()); 522 return __h->_M_insert_unique_node(__n, __code, __p)->second; 523 } 524 525 return (__p->_M_v).second; 526 } 527 528 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 529 typename _H1, typename _H2, typename _Hash, 530 typename _RehashPolicy, typename _Traits> 531 typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 532 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 533 ::mapped_type& 534 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 535 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 536 at(const key_type& __k) 537 { 538 __hashtable* __h = static_cast<__hashtable*>(this); 539 __hash_code __code = __h->_M_hash_code(__k); 540 std::size_t __n = __h->_M_bucket_index(__k, __code); 541 __node_type* __p = __h->_M_find_node(__n, __k, __code); 542 543 if (!__p) 544 __throw_out_of_range(__N("_Map_base::at")); 545 return (__p->_M_v).second; 546 } 547 548 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 549 typename _H1, typename _H2, typename _Hash, 550 typename _RehashPolicy, typename _Traits> 551 const typename _Map_base<_Key, _Pair, _Alloc, _Select1st, 552 _Equal, _H1, _H2, _Hash, _RehashPolicy, 553 _Traits, true>::mapped_type& 554 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 555 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 556 at(const key_type& __k) const 557 { 558 const __hashtable* __h = static_cast<const __hashtable*>(this); 559 __hash_code __code = __h->_M_hash_code(__k); 560 std::size_t __n = __h->_M_bucket_index(__k, __code); 561 __node_type* __p = __h->_M_find_node(__n, __k, __code); 562 563 if (!__p) 564 __throw_out_of_range(__N("_Map_base::at")); 565 return (__p->_M_v).second; 566 } 567 568 /** 569 * Primary class template _Insert_base. 570 * 571 * insert member functions appropriate to all _Hashtables. 572 */ 573 template<typename _Key, typename _Value, typename _Alloc, 574 typename _ExtractKey, typename _Equal, 575 typename _H1, typename _H2, typename _Hash, 576 typename _RehashPolicy, typename _Traits> 577 struct _Insert_base 578 { 579 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 580 _Equal, _H1, _H2, _Hash, 581 _RehashPolicy, _Traits>; 582 583 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, 584 _Equal, _H1, _H2, _Hash, 585 _Traits>; 586 587 using value_type = typename __hashtable_base::value_type; 588 using iterator = typename __hashtable_base::iterator; 589 using const_iterator = typename __hashtable_base::const_iterator; 590 using size_type = typename __hashtable_base::size_type; 591 592 using __unique_keys = typename __hashtable_base::__unique_keys; 593 using __ireturn_type = typename __hashtable_base::__ireturn_type; 594 using __iconv_type = typename __hashtable_base::__iconv_type; 595 596 __hashtable& 597 _M_conjure_hashtable() 598 { return *(static_cast<__hashtable*>(this)); } 599 600 __ireturn_type 601 insert(const value_type& __v) 602 { 603 __hashtable& __h = _M_conjure_hashtable(); 604 return __h._M_insert(__v, __unique_keys()); 605 } 606 607 iterator 608 insert(const_iterator, const value_type& __v) 609 { return __iconv_type()(insert(__v)); } 610 611 void 612 insert(initializer_list<value_type> __l) 613 { this->insert(__l.begin(), __l.end()); } 614 615 template<typename _InputIterator> 616 void 617 insert(_InputIterator __first, _InputIterator __last); 618 }; 619 620 template<typename _Key, typename _Value, typename _Alloc, 621 typename _ExtractKey, typename _Equal, 622 typename _H1, typename _H2, typename _Hash, 623 typename _RehashPolicy, typename _Traits> 624 template<typename _InputIterator> 625 void 626 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 627 _RehashPolicy, _Traits>:: 628 insert(_InputIterator __first, _InputIterator __last) 629 { 630 using __rehash_type = typename __hashtable::__rehash_type; 631 using __rehash_state = typename __hashtable::__rehash_state; 632 using pair_type = std::pair<bool, std::size_t>; 633 634 size_type __n_elt = __detail::__distance_fw(__first, __last); 635 636 __hashtable& __h = _M_conjure_hashtable(); 637 __rehash_type& __rehash = __h._M_rehash_policy; 638 const __rehash_state& __saved_state = __rehash._M_state(); 639 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count, 640 __h._M_element_count, 641 __n_elt); 642 643 if (__do_rehash.first) 644 __h._M_rehash(__do_rehash.second, __saved_state); 645 646 for (; __first != __last; ++__first) 647 __h._M_insert(*__first, __unique_keys()); 648 } 649 650 /** 651 * Primary class template _Insert. 652 * 653 * Select insert member functions appropriate to _Hashtable policy choices. 654 */ 655 template<typename _Key, typename _Value, typename _Alloc, 656 typename _ExtractKey, typename _Equal, 657 typename _H1, typename _H2, typename _Hash, 658 typename _RehashPolicy, typename _Traits, 659 bool _Constant_iterators = _Traits::__constant_iterators::value, 660 bool _Unique_keys = _Traits::__unique_keys::value> 661 struct _Insert; 662 663 /// Specialization. 664 template<typename _Key, typename _Value, typename _Alloc, 665 typename _ExtractKey, typename _Equal, 666 typename _H1, typename _H2, typename _Hash, 667 typename _RehashPolicy, typename _Traits> 668 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 669 _RehashPolicy, _Traits, true, true> 670 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 671 _H1, _H2, _Hash, _RehashPolicy, _Traits> 672 { 673 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, 674 _Equal, _H1, _H2, _Hash, 675 _RehashPolicy, _Traits>; 676 using value_type = typename __base_type::value_type; 677 using iterator = typename __base_type::iterator; 678 using const_iterator = typename __base_type::const_iterator; 679 680 using __unique_keys = typename __base_type::__unique_keys; 681 using __hashtable = typename __base_type::__hashtable; 682 683 using __base_type::insert; 684 685 std::pair<iterator, bool> 686 insert(value_type&& __v) 687 { 688 __hashtable& __h = this->_M_conjure_hashtable(); 689 return __h._M_insert(std::move(__v), __unique_keys()); 690 } 691 692 iterator 693 insert(const_iterator, value_type&& __v) 694 { return insert(std::move(__v)).first; } 695 }; 696 697 /// Specialization. 698 template<typename _Key, typename _Value, typename _Alloc, 699 typename _ExtractKey, typename _Equal, 700 typename _H1, typename _H2, typename _Hash, 701 typename _RehashPolicy, typename _Traits> 702 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 703 _RehashPolicy, _Traits, true, false> 704 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 705 _H1, _H2, _Hash, _RehashPolicy, _Traits> 706 { 707 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, 708 _Equal, _H1, _H2, _Hash, 709 _RehashPolicy, _Traits>; 710 using value_type = typename __base_type::value_type; 711 using iterator = typename __base_type::iterator; 712 using const_iterator = typename __base_type::const_iterator; 713 714 using __unique_keys = typename __base_type::__unique_keys; 715 using __hashtable = typename __base_type::__hashtable; 716 717 using __base_type::insert; 718 719 iterator 720 insert(value_type&& __v) 721 { 722 __hashtable& __h = this->_M_conjure_hashtable(); 723 return __h._M_insert(std::move(__v), __unique_keys()); 724 } 725 726 iterator 727 insert(const_iterator, value_type&& __v) 728 { return insert(std::move(__v)); } 729 }; 730 731 /// Specialization. 732 template<typename _Key, typename _Value, typename _Alloc, 733 typename _ExtractKey, typename _Equal, 734 typename _H1, typename _H2, typename _Hash, 735 typename _RehashPolicy, typename _Traits, bool _Unique_keys> 736 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 737 _RehashPolicy, _Traits, false, _Unique_keys> 738 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 739 _H1, _H2, _Hash, _RehashPolicy, _Traits> 740 { 741 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, 742 _Equal, _H1, _H2, _Hash, 743 _RehashPolicy, _Traits>; 744 using value_type = typename __base_type::value_type; 745 using iterator = typename __base_type::iterator; 746 using const_iterator = typename __base_type::const_iterator; 747 748 using __unique_keys = typename __base_type::__unique_keys; 749 using __hashtable = typename __base_type::__hashtable; 750 using __ireturn_type = typename __base_type::__ireturn_type; 751 using __iconv_type = typename __base_type::__iconv_type; 752 753 using __base_type::insert; 754 755 template<typename _Pair> 756 using __is_cons = std::is_constructible<value_type, _Pair&&>; 757 758 template<typename _Pair> 759 using _IFcons = std::enable_if<__is_cons<_Pair>::value>; 760 761 template<typename _Pair> 762 using _IFconsp = typename _IFcons<_Pair>::type; 763 764 template<typename _Pair, typename = _IFconsp<_Pair>> 765 __ireturn_type 766 insert(_Pair&& __v) 767 { 768 __hashtable& __h = this->_M_conjure_hashtable(); 769 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v)); 770 } 771 772 template<typename _Pair, typename = _IFconsp<_Pair>> 773 iterator 774 insert(const_iterator, _Pair&& __v) 775 { return __iconv_type()(insert(std::forward<_Pair>(__v))); } 776 }; 777 778 /** 779 * Primary class template _Rehash_base. 780 * 781 * Give hashtable the max_load_factor functions and reserve iff the 782 * rehash policy is _Prime_rehash_policy. 783 */ 784 template<typename _Key, typename _Value, typename _Alloc, 785 typename _ExtractKey, typename _Equal, 786 typename _H1, typename _H2, typename _Hash, 787 typename _RehashPolicy, typename _Traits> 788 struct _Rehash_base; 789 790 /// Specialization. 791 template<typename _Key, typename _Value, typename _Alloc, 792 typename _ExtractKey, typename _Equal, 793 typename _H1, typename _H2, typename _Hash, typename _Traits> 794 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 795 _H1, _H2, _Hash, _Prime_rehash_policy, _Traits> 796 { 797 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 798 _Equal, _H1, _H2, _Hash, 799 _Prime_rehash_policy, _Traits>; 800 801 float 802 max_load_factor() const noexcept 803 { 804 const __hashtable* __this = static_cast<const __hashtable*>(this); 805 return __this->__rehash_policy().max_load_factor(); 806 } 807 808 void 809 max_load_factor(float __z) 810 { 811 __hashtable* __this = static_cast<__hashtable*>(this); 812 __this->__rehash_policy(_Prime_rehash_policy(__z)); 813 } 814 815 void 816 reserve(std::size_t __n) 817 { 818 __hashtable* __this = static_cast<__hashtable*>(this); 819 __this->rehash(__builtin_ceil(__n / max_load_factor())); 820 } 821 }; 822 823 /** 824 * Primary class template _Hashtable_ebo_helper. 825 * 826 * Helper class using EBO when it is not forbidden, type is not 827 * final, and when it worth it, type is empty. 828 */ 829 template<int _Nm, typename _Tp, 830 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> 831 struct _Hashtable_ebo_helper; 832 833 /// Specialization using EBO. 834 template<int _Nm, typename _Tp> 835 struct _Hashtable_ebo_helper<_Nm, _Tp, true> 836 : private _Tp 837 { 838 _Hashtable_ebo_helper() = default; 839 840 _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp) 841 { } 842 843 static const _Tp& 844 _S_cget(const _Hashtable_ebo_helper& __eboh) 845 { return static_cast<const _Tp&>(__eboh); } 846 847 static _Tp& 848 _S_get(_Hashtable_ebo_helper& __eboh) 849 { return static_cast<_Tp&>(__eboh); } 850 }; 851 852 /// Specialization not using EBO. 853 template<int _Nm, typename _Tp> 854 struct _Hashtable_ebo_helper<_Nm, _Tp, false> 855 { 856 _Hashtable_ebo_helper() = default; 857 858 _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp) 859 { } 860 861 static const _Tp& 862 _S_cget(const _Hashtable_ebo_helper& __eboh) 863 { return __eboh._M_tp; } 864 865 static _Tp& 866 _S_get(_Hashtable_ebo_helper& __eboh) 867 { return __eboh._M_tp; } 868 869 private: 870 _Tp _M_tp; 871 }; 872 873 /** 874 * Primary class template _Local_iterator_base. 875 * 876 * Base class for local iterators, used to iterate within a bucket 877 * but not between buckets. 878 */ 879 template<typename _Key, typename _Value, typename _ExtractKey, 880 typename _H1, typename _H2, typename _Hash, 881 bool __cache_hash_code> 882 struct _Local_iterator_base; 883 884 /** 885 * Primary class template _Hash_code_base. 886 * 887 * Encapsulates two policy issues that aren't quite orthogonal. 888 * (1) the difference between using a ranged hash function and using 889 * the combination of a hash function and a range-hashing function. 890 * In the former case we don't have such things as hash codes, so 891 * we have a dummy type as placeholder. 892 * (2) Whether or not we cache hash codes. Caching hash codes is 893 * meaningless if we have a ranged hash function. 894 * 895 * We also put the key extraction objects here, for convenience. 896 * Each specialization derives from one or more of the template 897 * parameters to benefit from Ebo. This is important as this type 898 * is inherited in some cases by the _Local_iterator_base type used 899 * to implement local_iterator and const_local_iterator. As with 900 * any iterator type we prefer to make it as small as possible. 901 * 902 * Primary template is unused except as a hook for specializations. 903 */ 904 template<typename _Key, typename _Value, typename _ExtractKey, 905 typename _H1, typename _H2, typename _Hash, 906 bool __cache_hash_code> 907 struct _Hash_code_base; 908 909 /// Specialization: ranged hash function, no caching hash codes. H1 910 /// and H2 are provided but ignored. We define a dummy hash code type. 911 template<typename _Key, typename _Value, typename _ExtractKey, 912 typename _H1, typename _H2, typename _Hash> 913 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> 914 : private _Hashtable_ebo_helper<0, _ExtractKey>, 915 private _Hashtable_ebo_helper<1, _Hash> 916 { 917 private: 918 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 919 using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>; 920 921 protected: 922 typedef void* __hash_code; 923 typedef _Hash_node<_Value, false> __node_type; 924 925 // We need the default constructor for the local iterators. 926 _Hash_code_base() = default; 927 928 _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&, 929 const _Hash& __h) 930 : __ebo_extract_key(__ex), __ebo_hash(__h) { } 931 932 __hash_code 933 _M_hash_code(const _Key& __key) const 934 { return 0; } 935 936 std::size_t 937 _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const 938 { return _M_ranged_hash()(__k, __n); } 939 940 std::size_t 941 _M_bucket_index(const __node_type* __p, std::size_t __n) const 942 { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); } 943 944 void 945 _M_store_code(__node_type*, __hash_code) const 946 { } 947 948 void 949 _M_copy_code(__node_type*, const __node_type*) const 950 { } 951 952 void 953 _M_swap(_Hash_code_base& __x) 954 { 955 std::swap(_M_extract(), __x._M_extract()); 956 std::swap(_M_ranged_hash(), __x._M_ranged_hash()); 957 } 958 959 const _ExtractKey& 960 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 961 962 _ExtractKey& 963 _M_extract() { return __ebo_extract_key::_S_get(*this); } 964 965 const _Hash& 966 _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); } 967 968 _Hash& 969 _M_ranged_hash() { return __ebo_hash::_S_get(*this); } 970 }; 971 972 // No specialization for ranged hash function while caching hash codes. 973 // That combination is meaningless, and trying to do it is an error. 974 975 /// Specialization: ranged hash function, cache hash codes. This 976 /// combination is meaningless, so we provide only a declaration 977 /// and no definition. 978 template<typename _Key, typename _Value, typename _ExtractKey, 979 typename _H1, typename _H2, typename _Hash> 980 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; 981 982 /// Specialization: hash function and range-hashing function, no 983 /// caching of hash codes. 984 /// Provides typedef and accessor required by C++ 11. 985 template<typename _Key, typename _Value, typename _ExtractKey, 986 typename _H1, typename _H2> 987 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 988 _Default_ranged_hash, false> 989 : private _Hashtable_ebo_helper<0, _ExtractKey>, 990 private _Hashtable_ebo_helper<1, _H1>, 991 private _Hashtable_ebo_helper<2, _H2> 992 { 993 private: 994 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 995 using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; 996 using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; 997 998 public: 999 typedef _H1 hasher; 1000 1001 hasher 1002 hash_function() const 1003 { return _M_h1(); } 1004 1005 protected: 1006 typedef std::size_t __hash_code; 1007 typedef _Hash_node<_Value, false> __node_type; 1008 1009 // We need the default constructor for the local iterators. 1010 _Hash_code_base() = default; 1011 1012 _Hash_code_base(const _ExtractKey& __ex, 1013 const _H1& __h1, const _H2& __h2, 1014 const _Default_ranged_hash&) 1015 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } 1016 1017 __hash_code 1018 _M_hash_code(const _Key& __k) const 1019 { return _M_h1()(__k); } 1020 1021 std::size_t 1022 _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const 1023 { return _M_h2()(__c, __n); } 1024 1025 std::size_t 1026 _M_bucket_index(const __node_type* __p, 1027 std::size_t __n) const 1028 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); } 1029 1030 void 1031 _M_store_code(__node_type*, __hash_code) const 1032 { } 1033 1034 void 1035 _M_copy_code(__node_type*, const __node_type*) const 1036 { } 1037 1038 void 1039 _M_swap(_Hash_code_base& __x) 1040 { 1041 std::swap(_M_extract(), __x._M_extract()); 1042 std::swap(_M_h1(), __x._M_h1()); 1043 std::swap(_M_h2(), __x._M_h2()); 1044 } 1045 1046 const _ExtractKey& 1047 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 1048 1049 _ExtractKey& 1050 _M_extract() { return __ebo_extract_key::_S_get(*this); } 1051 1052 const _H1& 1053 _M_h1() const { return __ebo_h1::_S_cget(*this); } 1054 1055 _H1& 1056 _M_h1() { return __ebo_h1::_S_get(*this); } 1057 1058 const _H2& 1059 _M_h2() const { return __ebo_h2::_S_cget(*this); } 1060 1061 _H2& 1062 _M_h2() { return __ebo_h2::_S_get(*this); } 1063 }; 1064 1065 /// Specialization: hash function and range-hashing function, 1066 /// caching hash codes. H is provided but ignored. Provides 1067 /// typedef and accessor required by C++ 11. 1068 template<typename _Key, typename _Value, typename _ExtractKey, 1069 typename _H1, typename _H2> 1070 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 1071 _Default_ranged_hash, true> 1072 : private _Hashtable_ebo_helper<0, _ExtractKey>, 1073 private _Hashtable_ebo_helper<1, _H1>, 1074 private _Hashtable_ebo_helper<2, _H2> 1075 { 1076 private: 1077 // Gives access to _M_h2() to the local iterator implementation. 1078 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, 1079 _Default_ranged_hash, true>; 1080 1081 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 1082 using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; 1083 using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; 1084 1085 public: 1086 typedef _H1 hasher; 1087 1088 hasher 1089 hash_function() const 1090 { return _M_h1(); } 1091 1092 protected: 1093 typedef std::size_t __hash_code; 1094 typedef _Hash_node<_Value, true> __node_type; 1095 1096 _Hash_code_base(const _ExtractKey& __ex, 1097 const _H1& __h1, const _H2& __h2, 1098 const _Default_ranged_hash&) 1099 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } 1100 1101 __hash_code 1102 _M_hash_code(const _Key& __k) const 1103 { return _M_h1()(__k); } 1104 1105 std::size_t 1106 _M_bucket_index(const _Key&, __hash_code __c, 1107 std::size_t __n) const 1108 { return _M_h2()(__c, __n); } 1109 1110 std::size_t 1111 _M_bucket_index(const __node_type* __p, std::size_t __n) const 1112 { return _M_h2()(__p->_M_hash_code, __n); } 1113 1114 void 1115 _M_store_code(__node_type* __n, __hash_code __c) const 1116 { __n->_M_hash_code = __c; } 1117 1118 void 1119 _M_copy_code(__node_type* __to, const __node_type* __from) const 1120 { __to->_M_hash_code = __from->_M_hash_code; } 1121 1122 void 1123 _M_swap(_Hash_code_base& __x) 1124 { 1125 std::swap(_M_extract(), __x._M_extract()); 1126 std::swap(_M_h1(), __x._M_h1()); 1127 std::swap(_M_h2(), __x._M_h2()); 1128 } 1129 1130 const _ExtractKey& 1131 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 1132 1133 _ExtractKey& 1134 _M_extract() { return __ebo_extract_key::_S_get(*this); } 1135 1136 const _H1& 1137 _M_h1() const { return __ebo_h1::_S_cget(*this); } 1138 1139 _H1& 1140 _M_h1() { return __ebo_h1::_S_get(*this); } 1141 1142 const _H2& 1143 _M_h2() const { return __ebo_h2::_S_cget(*this); } 1144 1145 _H2& 1146 _M_h2() { return __ebo_h2::_S_get(*this); } 1147 }; 1148 1149 /** 1150 * Primary class template _Equal_helper. 1151 * 1152 */ 1153 template <typename _Key, typename _Value, typename _ExtractKey, 1154 typename _Equal, typename _HashCodeType, 1155 bool __cache_hash_code> 1156 struct _Equal_helper; 1157 1158 /// Specialization. 1159 template<typename _Key, typename _Value, typename _ExtractKey, 1160 typename _Equal, typename _HashCodeType> 1161 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> 1162 { 1163 static bool 1164 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 1165 const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n) 1166 { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v)); } 1167 }; 1168 1169 /// Specialization. 1170 template<typename _Key, typename _Value, typename _ExtractKey, 1171 typename _Equal, typename _HashCodeType> 1172 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> 1173 { 1174 static bool 1175 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 1176 const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n) 1177 { return __eq(__k, __extract(__n->_M_v)); } 1178 }; 1179 1180 1181 /// Specialization. 1182 template<typename _Key, typename _Value, typename _ExtractKey, 1183 typename _H1, typename _H2, typename _Hash> 1184 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 1185 _H1, _H2, _Hash, true> 1186 : private _Hashtable_ebo_helper<0, _H2> 1187 { 1188 protected: 1189 using __base_type = _Hashtable_ebo_helper<0, _H2>; 1190 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 1191 _H1, _H2, _Hash, true>; 1192 1193 public: 1194 _Local_iterator_base() = default; 1195 _Local_iterator_base(const __hash_code_base& __base, 1196 _Hash_node<_Value, true>* __p, 1197 std::size_t __bkt, std::size_t __bkt_count) 1198 : __base_type(__base._M_h2()), 1199 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 1200 1201 void 1202 _M_incr() 1203 { 1204 _M_cur = _M_cur->_M_next(); 1205 if (_M_cur) 1206 { 1207 std::size_t __bkt 1208 = __base_type::_S_get(*this)(_M_cur->_M_hash_code, 1209 _M_bucket_count); 1210 if (__bkt != _M_bucket) 1211 _M_cur = nullptr; 1212 } 1213 } 1214 1215 _Hash_node<_Value, true>* _M_cur; 1216 std::size_t _M_bucket; 1217 std::size_t _M_bucket_count; 1218 }; 1219 1220 /// Specialization. 1221 template<typename _Key, typename _Value, typename _ExtractKey, 1222 typename _H1, typename _H2, typename _Hash> 1223 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 1224 _H1, _H2, _Hash, false> 1225 : private _Hash_code_base<_Key, _Value, _ExtractKey, 1226 _H1, _H2, _Hash, false> 1227 { 1228 protected: 1229 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 1230 _H1, _H2, _Hash, false>; 1231 1232 public: 1233 _Local_iterator_base() = default; 1234 _Local_iterator_base(const __hash_code_base& __base, 1235 _Hash_node<_Value, false>* __p, 1236 std::size_t __bkt, std::size_t __bkt_count) 1237 : __hash_code_base(__base), 1238 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 1239 1240 void 1241 _M_incr() 1242 { 1243 _M_cur = _M_cur->_M_next(); 1244 if (_M_cur) 1245 { 1246 std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count); 1247 if (__bkt != _M_bucket) 1248 _M_cur = nullptr; 1249 } 1250 } 1251 1252 _Hash_node<_Value, false>* _M_cur; 1253 std::size_t _M_bucket; 1254 std::size_t _M_bucket_count; 1255 }; 1256 1257 template<typename _Key, typename _Value, typename _ExtractKey, 1258 typename _H1, typename _H2, typename _Hash, bool __cache> 1259 inline bool 1260 operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey, 1261 _H1, _H2, _Hash, __cache>& __x, 1262 const _Local_iterator_base<_Key, _Value, _ExtractKey, 1263 _H1, _H2, _Hash, __cache>& __y) 1264 { return __x._M_cur == __y._M_cur; } 1265 1266 template<typename _Key, typename _Value, typename _ExtractKey, 1267 typename _H1, typename _H2, typename _Hash, bool __cache> 1268 inline bool 1269 operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey, 1270 _H1, _H2, _Hash, __cache>& __x, 1271 const _Local_iterator_base<_Key, _Value, _ExtractKey, 1272 _H1, _H2, _Hash, __cache>& __y) 1273 { return __x._M_cur != __y._M_cur; } 1274 1275 /// local iterators 1276 template<typename _Key, typename _Value, typename _ExtractKey, 1277 typename _H1, typename _H2, typename _Hash, 1278 bool __constant_iterators, bool __cache> 1279 struct _Local_iterator 1280 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 1281 _H1, _H2, _Hash, __cache> 1282 { 1283 private: 1284 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, 1285 _H1, _H2, _Hash, __cache>; 1286 using __hash_code_base = typename __base_type::__hash_code_base; 1287 public: 1288 typedef _Value value_type; 1289 typedef typename std::conditional<__constant_iterators, 1290 const _Value*, _Value*>::type 1291 pointer; 1292 typedef typename std::conditional<__constant_iterators, 1293 const _Value&, _Value&>::type 1294 reference; 1295 typedef std::ptrdiff_t difference_type; 1296 typedef std::forward_iterator_tag iterator_category; 1297 1298 _Local_iterator() = default; 1299 1300 _Local_iterator(const __hash_code_base& __base, 1301 _Hash_node<_Value, __cache>* __p, 1302 std::size_t __bkt, std::size_t __bkt_count) 1303 : __base_type(__base, __p, __bkt, __bkt_count) 1304 { } 1305 1306 reference 1307 operator*() const 1308 { return this->_M_cur->_M_v; } 1309 1310 pointer 1311 operator->() const 1312 { return std::__addressof(this->_M_cur->_M_v); } 1313 1314 _Local_iterator& 1315 operator++() 1316 { 1317 this->_M_incr(); 1318 return *this; 1319 } 1320 1321 _Local_iterator 1322 operator++(int) 1323 { 1324 _Local_iterator __tmp(*this); 1325 this->_M_incr(); 1326 return __tmp; 1327 } 1328 }; 1329 1330 /// local const_iterators 1331 template<typename _Key, typename _Value, typename _ExtractKey, 1332 typename _H1, typename _H2, typename _Hash, 1333 bool __constant_iterators, bool __cache> 1334 struct _Local_const_iterator 1335 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 1336 _H1, _H2, _Hash, __cache> 1337 { 1338 private: 1339 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, 1340 _H1, _H2, _Hash, __cache>; 1341 using __hash_code_base = typename __base_type::__hash_code_base; 1342 1343 public: 1344 typedef _Value value_type; 1345 typedef const _Value* pointer; 1346 typedef const _Value& reference; 1347 typedef std::ptrdiff_t difference_type; 1348 typedef std::forward_iterator_tag iterator_category; 1349 1350 _Local_const_iterator() = default; 1351 1352 _Local_const_iterator(const __hash_code_base& __base, 1353 _Hash_node<_Value, __cache>* __p, 1354 std::size_t __bkt, std::size_t __bkt_count) 1355 : __base_type(__base, __p, __bkt, __bkt_count) 1356 { } 1357 1358 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, 1359 _H1, _H2, _Hash, 1360 __constant_iterators, 1361 __cache>& __x) 1362 : __base_type(__x) 1363 { } 1364 1365 reference 1366 operator*() const 1367 { return this->_M_cur->_M_v; } 1368 1369 pointer 1370 operator->() const 1371 { return std::__addressof(this->_M_cur->_M_v); } 1372 1373 _Local_const_iterator& 1374 operator++() 1375 { 1376 this->_M_incr(); 1377 return *this; 1378 } 1379 1380 _Local_const_iterator 1381 operator++(int) 1382 { 1383 _Local_const_iterator __tmp(*this); 1384 this->_M_incr(); 1385 return __tmp; 1386 } 1387 }; 1388 1389 /** 1390 * Primary class template _Hashtable_base. 1391 * 1392 * Helper class adding management of _Equal functor to 1393 * _Hash_code_base type. 1394 * 1395 * Base class templates are: 1396 * - __detail::_Hash_code_base 1397 * - __detail::_Hashtable_ebo_helper 1398 */ 1399 template<typename _Key, typename _Value, 1400 typename _ExtractKey, typename _Equal, 1401 typename _H1, typename _H2, typename _Hash, typename _Traits> 1402 struct _Hashtable_base 1403 : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 1404 _Traits::__hash_cached::value>, 1405 private _Hashtable_ebo_helper<0, _Equal> 1406 { 1407 public: 1408 typedef _Key key_type; 1409 typedef _Value value_type; 1410 typedef _Equal key_equal; 1411 typedef std::size_t size_type; 1412 typedef std::ptrdiff_t difference_type; 1413 1414 using __traits_type = _Traits; 1415 using __hash_cached = typename __traits_type::__hash_cached; 1416 using __constant_iterators = typename __traits_type::__constant_iterators; 1417 using __unique_keys = typename __traits_type::__unique_keys; 1418 1419 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 1420 _H1, _H2, _Hash, 1421 __hash_cached::value>; 1422 1423 using __hash_code = typename __hash_code_base::__hash_code; 1424 using __node_type = typename __hash_code_base::__node_type; 1425 1426 using iterator = __detail::_Node_iterator<value_type, 1427 __constant_iterators::value, 1428 __hash_cached::value>; 1429 1430 using const_iterator = __detail::_Node_const_iterator<value_type, 1431 __constant_iterators::value, 1432 __hash_cached::value>; 1433 1434 using local_iterator = __detail::_Local_iterator<key_type, value_type, 1435 _ExtractKey, _H1, _H2, _Hash, 1436 __constant_iterators::value, 1437 __hash_cached::value>; 1438 1439 using const_local_iterator = __detail::_Local_const_iterator<key_type, 1440 value_type, 1441 _ExtractKey, _H1, _H2, _Hash, 1442 __constant_iterators::value, 1443 __hash_cached::value>; 1444 1445 using __ireturn_type = typename std::conditional<__unique_keys::value, 1446 std::pair<iterator, bool>, 1447 iterator>::type; 1448 1449 using __iconv_type = typename std::conditional<__unique_keys::value, 1450 _Select1st, _Identity 1451 >::type; 1452 private: 1453 using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; 1454 using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal, 1455 __hash_code, __hash_cached::value>; 1456 1457 protected: 1458 using __node_base = __detail::_Hash_node_base; 1459 using __bucket_type = __node_base*; 1460 1461 _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, 1462 const _Hash& __hash, const _Equal& __eq) 1463 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq) 1464 { } 1465 1466 bool 1467 _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const 1468 { 1469 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), 1470 __k, __c, __n); 1471 } 1472 1473 void 1474 _M_swap(_Hashtable_base& __x) 1475 { 1476 __hash_code_base::_M_swap(__x); 1477 std::swap(_M_eq(), __x._M_eq()); 1478 } 1479 1480 const _Equal& 1481 _M_eq() const { return _EqualEBO::_S_cget(*this); } 1482 1483 _Equal& 1484 _M_eq() { return _EqualEBO::_S_get(*this); } 1485 }; 1486 1487 /** 1488 * struct _Equality_base. 1489 * 1490 * Common types and functions for class _Equality. 1491 */ 1492 struct _Equality_base 1493 { 1494 protected: 1495 template<typename _Uiterator> 1496 static bool 1497 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); 1498 }; 1499 1500 // See std::is_permutation in N3068. 1501 template<typename _Uiterator> 1502 bool 1503 _Equality_base:: 1504 _S_is_permutation(_Uiterator __first1, _Uiterator __last1, 1505 _Uiterator __first2) 1506 { 1507 for (; __first1 != __last1; ++__first1, ++__first2) 1508 if (!(*__first1 == *__first2)) 1509 break; 1510 1511 if (__first1 == __last1) 1512 return true; 1513 1514 _Uiterator __last2 = __first2; 1515 std::advance(__last2, std::distance(__first1, __last1)); 1516 1517 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) 1518 { 1519 _Uiterator __tmp = __first1; 1520 while (__tmp != __it1 && !bool(*__tmp == *__it1)) 1521 ++__tmp; 1522 1523 // We've seen this one before. 1524 if (__tmp != __it1) 1525 continue; 1526 1527 std::ptrdiff_t __n2 = 0; 1528 for (__tmp = __first2; __tmp != __last2; ++__tmp) 1529 if (*__tmp == *__it1) 1530 ++__n2; 1531 1532 if (!__n2) 1533 return false; 1534 1535 std::ptrdiff_t __n1 = 0; 1536 for (__tmp = __it1; __tmp != __last1; ++__tmp) 1537 if (*__tmp == *__it1) 1538 ++__n1; 1539 1540 if (__n1 != __n2) 1541 return false; 1542 } 1543 return true; 1544 } 1545 1546 /** 1547 * Primary class template _Equality. 1548 * 1549 * This is for implementing equality comparison for unordered 1550 * containers, per N3068, by John Lakos and Pablo Halpern. 1551 * Algorithmically, we follow closely the reference implementations 1552 * therein. 1553 */ 1554 template<typename _Key, typename _Value, typename _Alloc, 1555 typename _ExtractKey, typename _Equal, 1556 typename _H1, typename _H2, typename _Hash, 1557 typename _RehashPolicy, typename _Traits, 1558 bool _Unique_keys = _Traits::__unique_keys::value> 1559 struct _Equality; 1560 1561 /// Specialization. 1562 template<typename _Key, typename _Value, typename _Alloc, 1563 typename _ExtractKey, typename _Equal, 1564 typename _H1, typename _H2, typename _Hash, 1565 typename _RehashPolicy, typename _Traits> 1566 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1567 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 1568 { 1569 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1570 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 1571 1572 bool 1573 _M_equal(const __hashtable&) const; 1574 }; 1575 1576 template<typename _Key, typename _Value, typename _Alloc, 1577 typename _ExtractKey, typename _Equal, 1578 typename _H1, typename _H2, typename _Hash, 1579 typename _RehashPolicy, typename _Traits> 1580 bool 1581 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1582 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 1583 _M_equal(const __hashtable& __other) const 1584 { 1585 const __hashtable* __this = static_cast<const __hashtable*>(this); 1586 1587 if (__this->size() != __other.size()) 1588 return false; 1589 1590 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) 1591 { 1592 const auto __ity = __other.find(_ExtractKey()(*__itx)); 1593 if (__ity == __other.end() || !bool(*__ity == *__itx)) 1594 return false; 1595 } 1596 return true; 1597 } 1598 1599 /// Specialization. 1600 template<typename _Key, typename _Value, typename _Alloc, 1601 typename _ExtractKey, typename _Equal, 1602 typename _H1, typename _H2, typename _Hash, 1603 typename _RehashPolicy, typename _Traits> 1604 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1605 _H1, _H2, _Hash, _RehashPolicy, _Traits, false> 1606 : public _Equality_base 1607 { 1608 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1609 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 1610 1611 bool 1612 _M_equal(const __hashtable&) const; 1613 }; 1614 1615 template<typename _Key, typename _Value, typename _Alloc, 1616 typename _ExtractKey, typename _Equal, 1617 typename _H1, typename _H2, typename _Hash, 1618 typename _RehashPolicy, typename _Traits> 1619 bool 1620 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1621 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: 1622 _M_equal(const __hashtable& __other) const 1623 { 1624 const __hashtable* __this = static_cast<const __hashtable*>(this); 1625 1626 if (__this->size() != __other.size()) 1627 return false; 1628 1629 for (auto __itx = __this->begin(); __itx != __this->end();) 1630 { 1631 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); 1632 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); 1633 1634 if (std::distance(__xrange.first, __xrange.second) 1635 != std::distance(__yrange.first, __yrange.second)) 1636 return false; 1637 1638 if (!_S_is_permutation(__xrange.first, __xrange.second, 1639 __yrange.first)) 1640 return false; 1641 1642 __itx = __xrange.second; 1643 } 1644 return true; 1645 } 1646 1647 /** 1648 * This type is to combine a _Hash_node_base instance with an allocator 1649 * instance through inheritance to benefit from EBO when possible. 1650 */ 1651 template<typename _NodeAlloc> 1652 struct _Before_begin : public _NodeAlloc 1653 { 1654 _Hash_node_base _M_node; 1655 1656 _Before_begin(const _Before_begin&) = default; 1657 _Before_begin(_Before_begin&&) = default; 1658 1659 template<typename _Alloc> 1660 _Before_begin(_Alloc&& __a) 1661 : _NodeAlloc(std::forward<_Alloc>(__a)) 1662 { } 1663 }; 1664 1665 //@} hashtable-detail 1666_GLIBCXX_END_NAMESPACE_VERSION 1667} // namespace __detail 1668} // namespace std 1669 1670#endif // _HASHTABLE_POLICY_H 1671