1 // Internal policy header for unordered_set and unordered_map -*- C++ -*- 2 3 // Copyright (C) 2010, 2011, 2012 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 34 namespace std _GLIBCXX_VISIBILITY(default) 35 { 36 namespace __detail 37 { 38 _GLIBCXX_BEGIN_NAMESPACE_VERSION 39 40 // Helper function: return distance(first, last) for forward 41 // iterators, or 0 for input iterators. 42 template<class _Iterator> 43 inline typename std::iterator_traits<_Iterator>::difference_type 44 __distance_fw(_Iterator __first, _Iterator __last, 45 std::input_iterator_tag) 46 { return 0; } 47 48 template<class _Iterator> 49 inline typename std::iterator_traits<_Iterator>::difference_type 50 __distance_fw(_Iterator __first, _Iterator __last, 51 std::forward_iterator_tag) 52 { return std::distance(__first, __last); } 53 54 template<class _Iterator> 55 inline typename std::iterator_traits<_Iterator>::difference_type 56 __distance_fw(_Iterator __first, _Iterator __last) 57 { 58 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; 59 return __distance_fw(__first, __last, _Tag()); 60 } 61 62 // Helper type used to detect whether the hash functor is noexcept. 63 template <typename _Key, typename _Hash> 64 struct __is_noexcept_hash : std::integral_constant<bool, 65 noexcept(declval<const _Hash&>()(declval<const _Key&>()))> 66 {}; 67 68 // Auxiliary types used for all instantiations of _Hashtable: nodes 69 // and iterators. 70 71 // Nodes, used to wrap elements stored in the hash table. A policy 72 // template parameter of class template _Hashtable controls whether 73 // nodes also store a hash code. In some cases (e.g. strings) this 74 // may be a performance win. 75 struct _Hash_node_base 76 { 77 _Hash_node_base* _M_nxt; 78 79 _Hash_node_base() 80 : _M_nxt() { } 81 _Hash_node_base(_Hash_node_base* __next) 82 : _M_nxt(__next) { } 83 }; 84 85 template<typename _Value, bool __cache_hash_code> 86 struct _Hash_node; 87 88 template<typename _Value> 89 struct _Hash_node<_Value, true> : _Hash_node_base 90 { 91 _Value _M_v; 92 std::size_t _M_hash_code; 93 94 template<typename... _Args> 95 _Hash_node(_Args&&... __args) 96 : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { } 97 98 _Hash_node* _M_next() const 99 { return static_cast<_Hash_node*>(_M_nxt); } 100 }; 101 102 template<typename _Value> 103 struct _Hash_node<_Value, false> : _Hash_node_base 104 { 105 _Value _M_v; 106 107 template<typename... _Args> 108 _Hash_node(_Args&&... __args) 109 : _M_v(std::forward<_Args>(__args)...) { } 110 111 _Hash_node* _M_next() const 112 { return static_cast<_Hash_node*>(_M_nxt); } 113 }; 114 115 // Node iterators, used to iterate through all the hashtable. 116 template<typename _Value, bool __cache> 117 struct _Node_iterator_base 118 { 119 _Node_iterator_base(_Hash_node<_Value, __cache>* __p) 120 : _M_cur(__p) { } 121 122 void 123 _M_incr() 124 { _M_cur = _M_cur->_M_next(); } 125 126 _Hash_node<_Value, __cache>* _M_cur; 127 }; 128 129 template<typename _Value, bool __cache> 130 inline bool 131 operator==(const _Node_iterator_base<_Value, __cache>& __x, 132 const _Node_iterator_base<_Value, __cache>& __y) 133 { return __x._M_cur == __y._M_cur; } 134 135 template<typename _Value, bool __cache> 136 inline bool 137 operator!=(const _Node_iterator_base<_Value, __cache>& __x, 138 const _Node_iterator_base<_Value, __cache>& __y) 139 { return __x._M_cur != __y._M_cur; } 140 141 template<typename _Value, bool __constant_iterators, bool __cache> 142 struct _Node_iterator 143 : public _Node_iterator_base<_Value, __cache> 144 { 145 typedef _Value value_type; 146 typedef typename std::conditional<__constant_iterators, 147 const _Value*, _Value*>::type 148 pointer; 149 typedef typename std::conditional<__constant_iterators, 150 const _Value&, _Value&>::type 151 reference; 152 typedef std::ptrdiff_t difference_type; 153 typedef std::forward_iterator_tag iterator_category; 154 155 _Node_iterator() 156 : _Node_iterator_base<_Value, __cache>(0) { } 157 158 explicit 159 _Node_iterator(_Hash_node<_Value, __cache>* __p) 160 : _Node_iterator_base<_Value, __cache>(__p) { } 161 162 reference 163 operator*() const 164 { return this->_M_cur->_M_v; } 165 166 pointer 167 operator->() const 168 { return std::__addressof(this->_M_cur->_M_v); } 169 170 _Node_iterator& 171 operator++() 172 { 173 this->_M_incr(); 174 return *this; 175 } 176 177 _Node_iterator 178 operator++(int) 179 { 180 _Node_iterator __tmp(*this); 181 this->_M_incr(); 182 return __tmp; 183 } 184 }; 185 186 template<typename _Value, bool __constant_iterators, bool __cache> 187 struct _Node_const_iterator 188 : public _Node_iterator_base<_Value, __cache> 189 { 190 typedef _Value value_type; 191 typedef const _Value* pointer; 192 typedef const _Value& reference; 193 typedef std::ptrdiff_t difference_type; 194 typedef std::forward_iterator_tag iterator_category; 195 196 _Node_const_iterator() 197 : _Node_iterator_base<_Value, __cache>(0) { } 198 199 explicit 200 _Node_const_iterator(_Hash_node<_Value, __cache>* __p) 201 : _Node_iterator_base<_Value, __cache>(__p) { } 202 203 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, 204 __cache>& __x) 205 : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } 206 207 reference 208 operator*() const 209 { return this->_M_cur->_M_v; } 210 211 pointer 212 operator->() const 213 { return std::__addressof(this->_M_cur->_M_v); } 214 215 _Node_const_iterator& 216 operator++() 217 { 218 this->_M_incr(); 219 return *this; 220 } 221 222 _Node_const_iterator 223 operator++(int) 224 { 225 _Node_const_iterator __tmp(*this); 226 this->_M_incr(); 227 return __tmp; 228 } 229 }; 230 231 // Many of class template _Hashtable's template parameters are policy 232 // classes. These are defaults for the policies. 233 234 // Default range hashing function: use division to fold a large number 235 // into the range [0, N). 236 struct _Mod_range_hashing 237 { 238 typedef std::size_t first_argument_type; 239 typedef std::size_t second_argument_type; 240 typedef std::size_t result_type; 241 242 result_type 243 operator()(first_argument_type __num, second_argument_type __den) const 244 { return __num % __den; } 245 }; 246 247 // Default ranged hash function H. In principle it should be a 248 // function object composed from objects of type H1 and H2 such that 249 // h(k, N) = h2(h1(k), N), but that would mean making extra copies of 250 // h1 and h2. So instead we'll just use a tag to tell class template 251 // hashtable to do that composition. 252 struct _Default_ranged_hash { }; 253 254 // Default value for rehash policy. Bucket size is (usually) the 255 // smallest prime that keeps the load factor small enough. 256 struct _Prime_rehash_policy 257 { 258 _Prime_rehash_policy(float __z = 1.0) 259 : _M_max_load_factor(__z), _M_prev_resize(0), _M_next_resize(0) { } 260 261 float 262 max_load_factor() const noexcept 263 { return _M_max_load_factor; } 264 265 // Return a bucket size no smaller than n. 266 std::size_t 267 _M_next_bkt(std::size_t __n) const; 268 269 // Return a bucket count appropriate for n elements 270 std::size_t 271 _M_bkt_for_elements(std::size_t __n) const; 272 273 // __n_bkt is current bucket count, __n_elt is current element count, 274 // and __n_ins is number of elements to be inserted. Do we need to 275 // increase bucket count? If so, return make_pair(true, n), where n 276 // is the new bucket count. If not, return make_pair(false, 0). 277 std::pair<bool, std::size_t> 278 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 279 std::size_t __n_ins) const; 280 281 typedef std::pair<std::size_t, std::size_t> _State; 282 283 _State 284 _M_state() const 285 { return std::make_pair(_M_prev_resize, _M_next_resize); } 286 287 void 288 _M_reset(const _State& __state) 289 { 290 _M_prev_resize = __state.first; 291 _M_next_resize = __state.second; 292 } 293 294 enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; 295 296 static const std::size_t _S_growth_factor = 2; 297 298 float _M_max_load_factor; 299 mutable std::size_t _M_prev_resize; 300 mutable std::size_t _M_next_resize; 301 }; 302 303 extern const unsigned long __prime_list[]; 304 305 // XXX This is a hack. There's no good reason for any of 306 // _Prime_rehash_policy's member functions to be inline. 307 308 // Return a prime no smaller than n. 309 inline std::size_t 310 _Prime_rehash_policy:: 311 _M_next_bkt(std::size_t __n) const 312 { 313 // Optimize lookups involving the first elements of __prime_list. 314 // (useful to speed-up, eg, constructors) 315 static const unsigned char __fast_bkt[12] 316 = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; 317 318 const std::size_t __grown_n = __n * _S_growth_factor; 319 if (__grown_n <= 11) 320 { 321 _M_prev_resize = 0; 322 _M_next_resize 323 = __builtin_ceil(__fast_bkt[__grown_n] 324 * (long double)_M_max_load_factor); 325 return __fast_bkt[__grown_n]; 326 } 327 328 const unsigned long* __next_bkt 329 = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, 330 __grown_n); 331 const unsigned long* __prev_bkt 332 = std::lower_bound(__prime_list + 1, __next_bkt, __n / _S_growth_factor); 333 334 _M_prev_resize 335 = __builtin_floor(*(__prev_bkt - 1) * (long double)_M_max_load_factor); 336 _M_next_resize 337 = __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor); 338 return *__next_bkt; 339 } 340 341 // Return the smallest prime p such that alpha p >= n, where alpha 342 // is the load factor. 343 inline std::size_t 344 _Prime_rehash_policy:: 345 _M_bkt_for_elements(std::size_t __n) const 346 { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); } 347 348 // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. 349 // If p > __n_bkt, return make_pair(true, p); otherwise return 350 // make_pair(false, 0). In principle this isn't very different from 351 // _M_bkt_for_elements. 352 353 // The only tricky part is that we're caching the element count at 354 // which we need to rehash, so we don't have to do a floating-point 355 // multiply for every insertion. 356 357 inline std::pair<bool, std::size_t> 358 _Prime_rehash_policy:: 359 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 360 std::size_t __n_ins) const 361 { 362 if (__n_elt + __n_ins >= _M_next_resize) 363 { 364 long double __min_bkts = (__n_elt + __n_ins) 365 / (long double)_M_max_load_factor; 366 if (__min_bkts >= __n_bkt) 367 return std::make_pair(true, 368 _M_next_bkt(__builtin_floor(__min_bkts) + 1)); 369 else 370 { 371 _M_next_resize 372 = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); 373 return std::make_pair(false, 0); 374 } 375 } 376 else if (__n_elt + __n_ins < _M_prev_resize) 377 { 378 long double __min_bkts = (__n_elt + __n_ins) 379 / (long double)_M_max_load_factor; 380 return std::make_pair(true, 381 _M_next_bkt(__builtin_floor(__min_bkts) + 1)); 382 } 383 else 384 return std::make_pair(false, 0); 385 } 386 387 // Base classes for std::_Hashtable. We define these base classes 388 // because in some cases we want to do different things depending 389 // on the value of a policy class. In some cases the policy class 390 // affects which member functions and nested typedefs are defined; 391 // we handle that by specializing base class templates. Several of 392 // the base class templates need to access other members of class 393 // template _Hashtable, so we use the "curiously recurring template 394 // pattern" for them. 395 396 // class template _Map_base. If the hashtable has a value type of 397 // the form pair<T1, T2> and a key extraction policy that returns the 398 // first part of the pair, the hashtable gets a mapped_type typedef. 399 // If it satisfies those criteria and also has unique keys, then it 400 // also gets an operator[]. 401 template<typename _Key, typename _Value, typename _Ex, bool __unique, 402 typename _Hashtable> 403 struct _Map_base { }; 404 405 template<typename _Key, typename _Pair, typename _Hashtable> 406 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> 407 { 408 typedef typename _Pair::second_type mapped_type; 409 }; 410 411 template<typename _Key, typename _Pair, typename _Hashtable> 412 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> 413 { 414 typedef typename _Pair::second_type mapped_type; 415 416 mapped_type& 417 operator[](const _Key& __k); 418 419 mapped_type& 420 operator[](_Key&& __k); 421 422 // _GLIBCXX_RESOLVE_LIB_DEFECTS 423 // DR 761. unordered_map needs an at() member function. 424 mapped_type& 425 at(const _Key& __k); 426 427 const mapped_type& 428 at(const _Key& __k) const; 429 }; 430 431 template<typename _Key, typename _Pair, typename _Hashtable> 432 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 433 true, _Hashtable>::mapped_type& 434 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 435 operator[](const _Key& __k) 436 { 437 _Hashtable* __h = static_cast<_Hashtable*>(this); 438 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 439 std::size_t __n = __h->_M_bucket_index(__k, __code); 440 441 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 442 if (!__p) 443 return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), 444 __n, __code)->second; 445 return (__p->_M_v).second; 446 } 447 448 template<typename _Key, typename _Pair, typename _Hashtable> 449 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 450 true, _Hashtable>::mapped_type& 451 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 452 operator[](_Key&& __k) 453 { 454 _Hashtable* __h = static_cast<_Hashtable*>(this); 455 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 456 std::size_t __n = __h->_M_bucket_index(__k, __code); 457 458 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 459 if (!__p) 460 return __h->_M_insert_bucket(std::make_pair(std::move(__k), 461 mapped_type()), 462 __n, __code)->second; 463 return (__p->_M_v).second; 464 } 465 466 template<typename _Key, typename _Pair, typename _Hashtable> 467 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 468 true, _Hashtable>::mapped_type& 469 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 470 at(const _Key& __k) 471 { 472 _Hashtable* __h = static_cast<_Hashtable*>(this); 473 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 474 std::size_t __n = __h->_M_bucket_index(__k, __code); 475 476 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 477 if (!__p) 478 __throw_out_of_range(__N("_Map_base::at")); 479 return (__p->_M_v).second; 480 } 481 482 template<typename _Key, typename _Pair, typename _Hashtable> 483 const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 484 true, _Hashtable>::mapped_type& 485 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 486 at(const _Key& __k) const 487 { 488 const _Hashtable* __h = static_cast<const _Hashtable*>(this); 489 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 490 std::size_t __n = __h->_M_bucket_index(__k, __code); 491 492 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 493 if (!__p) 494 __throw_out_of_range(__N("_Map_base::at")); 495 return (__p->_M_v).second; 496 } 497 498 // class template _Rehash_base. Give hashtable the max_load_factor 499 // functions and reserve iff the rehash policy is _Prime_rehash_policy. 500 template<typename _RehashPolicy, typename _Hashtable> 501 struct _Rehash_base { }; 502 503 template<typename _Hashtable> 504 struct _Rehash_base<_Prime_rehash_policy, _Hashtable> 505 { 506 float 507 max_load_factor() const noexcept 508 { 509 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 510 return __this->__rehash_policy().max_load_factor(); 511 } 512 513 void 514 max_load_factor(float __z) 515 { 516 _Hashtable* __this = static_cast<_Hashtable*>(this); 517 __this->__rehash_policy(_Prime_rehash_policy(__z)); 518 } 519 520 void 521 reserve(std::size_t __n) 522 { 523 _Hashtable* __this = static_cast<_Hashtable*>(this); 524 __this->rehash(__builtin_ceil(__n / max_load_factor())); 525 } 526 }; 527 528 // Helper class using EBO when it is not forbidden, type is not final, 529 // and when it worth it, type is empty. 530 template<int _Nm, typename _Tp, 531 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> 532 struct _Hashtable_ebo_helper; 533 534 // Specialization using EBO. 535 template<int _Nm, typename _Tp> 536 struct _Hashtable_ebo_helper<_Nm, _Tp, true> 537 // See PR53067. 538 : public _Tp 539 { 540 _Hashtable_ebo_helper() = default; 541 _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp) 542 { } 543 544 static const _Tp& 545 _S_cget(const _Hashtable_ebo_helper& __eboh) 546 { return static_cast<const _Tp&>(__eboh); } 547 548 static _Tp& 549 _S_get(_Hashtable_ebo_helper& __eboh) 550 { return static_cast<_Tp&>(__eboh); } 551 }; 552 553 // Specialization not using EBO. 554 template<int _Nm, typename _Tp> 555 struct _Hashtable_ebo_helper<_Nm, _Tp, false> 556 { 557 _Hashtable_ebo_helper() = default; 558 _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp) 559 { } 560 561 static const _Tp& 562 _S_cget(const _Hashtable_ebo_helper& __eboh) 563 { return __eboh._M_tp; } 564 565 static _Tp& 566 _S_get(_Hashtable_ebo_helper& __eboh) 567 { return __eboh._M_tp; } 568 569 private: 570 _Tp _M_tp; 571 }; 572 573 // Class template _Hash_code_base. Encapsulates two policy issues that 574 // aren't quite orthogonal. 575 // (1) the difference between using a ranged hash function and using 576 // the combination of a hash function and a range-hashing function. 577 // In the former case we don't have such things as hash codes, so 578 // we have a dummy type as placeholder. 579 // (2) Whether or not we cache hash codes. Caching hash codes is 580 // meaningless if we have a ranged hash function. 581 // We also put the key extraction objects here, for convenience. 582 // 583 // Each specialization derives from one or more of the template parameters to 584 // benefit from Ebo. This is important as this type is inherited in some cases 585 // by the _Local_iterator_base type used to implement local_iterator and 586 // const_local_iterator. As with any iterator type we prefer to make it as 587 // small as possible. 588 589 // Primary template: unused except as a hook for specializations. 590 template<typename _Key, typename _Value, typename _ExtractKey, 591 typename _H1, typename _H2, typename _Hash, 592 bool __cache_hash_code> 593 struct _Hash_code_base; 594 595 // Specialization: ranged hash function, no caching hash codes. H1 596 // and H2 are provided but ignored. We define a dummy hash code type. 597 template<typename _Key, typename _Value, typename _ExtractKey, 598 typename _H1, typename _H2, typename _Hash> 599 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> 600 // See PR53067. 601 : public _Hashtable_ebo_helper<0, _ExtractKey>, 602 public _Hashtable_ebo_helper<1, _Hash> 603 { 604 private: 605 typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 606 typedef _Hashtable_ebo_helper<1, _Hash> _EboHash; 607 608 protected: 609 // We need the default constructor for the local iterators. 610 _Hash_code_base() = default; 611 _Hash_code_base(const _ExtractKey& __ex, 612 const _H1&, const _H2&, const _Hash& __h) 613 : _EboExtractKey(__ex), _EboHash(__h) { } 614 615 typedef void* _Hash_code_type; 616 617 _Hash_code_type 618 _M_hash_code(const _Key& __key) const 619 { return 0; } 620 621 std::size_t 622 _M_bucket_index(const _Key& __k, _Hash_code_type, 623 std::size_t __n) const 624 { return _M_ranged_hash()(__k, __n); } 625 626 std::size_t 627 _M_bucket_index(const _Hash_node<_Value, false>* __p, 628 std::size_t __n) const 629 { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); } 630 631 void 632 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 633 { } 634 635 void 636 _M_copy_code(_Hash_node<_Value, false>*, 637 const _Hash_node<_Value, false>*) const 638 { } 639 640 void 641 _M_swap(_Hash_code_base& __x) 642 { 643 std::swap(_M_extract(), __x._M_extract()); 644 std::swap(_M_ranged_hash(), __x._M_ranged_hash()); 645 } 646 647 protected: 648 const _ExtractKey& 649 _M_extract() const { return _EboExtractKey::_S_cget(*this); } 650 _ExtractKey& 651 _M_extract() { return _EboExtractKey::_S_get(*this); } 652 const _Hash& 653 _M_ranged_hash() const { return _EboHash::_S_cget(*this); } 654 _Hash& 655 _M_ranged_hash() { return _EboHash::_S_get(*this); } 656 }; 657 658 // No specialization for ranged hash function while caching hash codes. 659 // That combination is meaningless, and trying to do it is an error. 660 661 // Specialization: ranged hash function, cache hash codes. This 662 // combination is meaningless, so we provide only a declaration 663 // and no definition. 664 template<typename _Key, typename _Value, typename _ExtractKey, 665 typename _H1, typename _H2, typename _Hash> 666 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; 667 668 // Specialization: hash function and range-hashing function, no 669 // caching of hash codes. 670 // Provides typedef and accessor required by TR1. 671 template<typename _Key, typename _Value, typename _ExtractKey, 672 typename _H1, typename _H2> 673 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 674 _Default_ranged_hash, false> 675 // See PR53067. 676 : public _Hashtable_ebo_helper<0, _ExtractKey>, 677 public _Hashtable_ebo_helper<1, _H1>, 678 public _Hashtable_ebo_helper<2, _H2> 679 { 680 private: 681 typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 682 typedef _Hashtable_ebo_helper<1, _H1> _EboH1; 683 typedef _Hashtable_ebo_helper<2, _H2> _EboH2; 684 685 public: 686 typedef _H1 hasher; 687 688 hasher 689 hash_function() const 690 { return _M_h1(); } 691 692 protected: 693 // We need the default constructor for the local iterators. 694 _Hash_code_base() = default; 695 _Hash_code_base(const _ExtractKey& __ex, 696 const _H1& __h1, const _H2& __h2, 697 const _Default_ranged_hash&) 698 : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } 699 700 typedef std::size_t _Hash_code_type; 701 702 _Hash_code_type 703 _M_hash_code(const _Key& __k) const 704 { return _M_h1()(__k); } 705 706 std::size_t 707 _M_bucket_index(const _Key&, _Hash_code_type __c, 708 std::size_t __n) const 709 { return _M_h2()(__c, __n); } 710 711 std::size_t 712 _M_bucket_index(const _Hash_node<_Value, false>* __p, 713 std::size_t __n) const 714 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); } 715 716 void 717 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 718 { } 719 720 void 721 _M_copy_code(_Hash_node<_Value, false>*, 722 const _Hash_node<_Value, false>*) const 723 { } 724 725 void 726 _M_swap(_Hash_code_base& __x) 727 { 728 std::swap(_M_extract(), __x._M_extract()); 729 std::swap(_M_h1(), __x._M_h1()); 730 std::swap(_M_h2(), __x._M_h2()); 731 } 732 733 protected: 734 const _ExtractKey& 735 _M_extract() const { return _EboExtractKey::_S_cget(*this); } 736 _ExtractKey& 737 _M_extract() { return _EboExtractKey::_S_get(*this); } 738 const _H1& 739 _M_h1() const { return _EboH1::_S_cget(*this); } 740 _H1& 741 _M_h1() { return _EboH1::_S_get(*this); } 742 const _H2& 743 _M_h2() const { return _EboH2::_S_cget(*this); } 744 _H2& 745 _M_h2() { return _EboH2::_S_get(*this); } 746 }; 747 748 // Specialization: hash function and range-hashing function, 749 // caching hash codes. H is provided but ignored. Provides 750 // typedef and accessor required by TR1. 751 template<typename _Key, typename _Value, typename _ExtractKey, 752 typename _H1, typename _H2> 753 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 754 _Default_ranged_hash, true> 755 // See PR53067. 756 : public _Hashtable_ebo_helper<0, _ExtractKey>, 757 public _Hashtable_ebo_helper<1, _H1>, 758 public _Hashtable_ebo_helper<2, _H2> 759 { 760 private: 761 typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 762 typedef _Hashtable_ebo_helper<1, _H1> _EboH1; 763 typedef _Hashtable_ebo_helper<2, _H2> _EboH2; 764 765 public: 766 typedef _H1 hasher; 767 768 hasher 769 hash_function() const 770 { return _M_h1(); } 771 772 protected: 773 _Hash_code_base(const _ExtractKey& __ex, 774 const _H1& __h1, const _H2& __h2, 775 const _Default_ranged_hash&) 776 : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } 777 778 typedef std::size_t _Hash_code_type; 779 780 _Hash_code_type 781 _M_hash_code(const _Key& __k) const 782 { return _M_h1()(__k); } 783 784 std::size_t 785 _M_bucket_index(const _Key&, _Hash_code_type __c, 786 std::size_t __n) const 787 { return _M_h2()(__c, __n); } 788 789 std::size_t 790 _M_bucket_index(const _Hash_node<_Value, true>* __p, 791 std::size_t __n) const 792 { return _M_h2()(__p->_M_hash_code, __n); } 793 794 void 795 _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const 796 { __n->_M_hash_code = __c; } 797 798 void 799 _M_copy_code(_Hash_node<_Value, true>* __to, 800 const _Hash_node<_Value, true>* __from) const 801 { __to->_M_hash_code = __from->_M_hash_code; } 802 803 void 804 _M_swap(_Hash_code_base& __x) 805 { 806 std::swap(_M_extract(), __x._M_extract()); 807 std::swap(_M_h1(), __x._M_h1()); 808 std::swap(_M_h2(), __x._M_h2()); 809 } 810 811 protected: 812 const _ExtractKey& 813 _M_extract() const { return _EboExtractKey::_S_cget(*this); } 814 _ExtractKey& 815 _M_extract() { return _EboExtractKey::_S_get(*this); } 816 const _H1& 817 _M_h1() const { return _EboH1::_S_cget(*this); } 818 _H1& 819 _M_h1() { return _EboH1::_S_get(*this); } 820 const _H2& 821 _M_h2() const { return _EboH2::_S_cget(*this); } 822 _H2& 823 _M_h2() { return _EboH2::_S_get(*this); } 824 }; 825 826 template <typename _Key, typename _Value, typename _ExtractKey, 827 typename _Equal, typename _HashCodeType, 828 bool __cache_hash_code> 829 struct _Equal_helper; 830 831 template<typename _Key, typename _Value, typename _ExtractKey, 832 typename _Equal, typename _HashCodeType> 833 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> 834 { 835 static bool 836 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 837 const _Key& __k, _HashCodeType __c, 838 _Hash_node<_Value, true>* __n) 839 { return __c == __n->_M_hash_code 840 && __eq(__k, __extract(__n->_M_v)); } 841 }; 842 843 template<typename _Key, typename _Value, typename _ExtractKey, 844 typename _Equal, typename _HashCodeType> 845 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> 846 { 847 static bool 848 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 849 const _Key& __k, _HashCodeType, 850 _Hash_node<_Value, false>* __n) 851 { return __eq(__k, __extract(__n->_M_v)); } 852 }; 853 854 // Helper class adding management of _Equal functor to _Hash_code_base 855 // type. 856 template<typename _Key, typename _Value, 857 typename _ExtractKey, typename _Equal, 858 typename _H1, typename _H2, typename _Hash, 859 bool __cache_hash_code> 860 struct _Hashtable_base 861 // See PR53067. 862 : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 863 __cache_hash_code>, 864 public _Hashtable_ebo_helper<0, _Equal> 865 { 866 private: 867 typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual; 868 869 protected: 870 typedef _Hash_code_base<_Key, _Value, _ExtractKey, 871 _H1, _H2, _Hash, __cache_hash_code> _HCBase; 872 typedef typename _HCBase::_Hash_code_type _Hash_code_type; 873 874 _Hashtable_base(const _ExtractKey& __ex, 875 const _H1& __h1, const _H2& __h2, 876 const _Hash& __hash, const _Equal& __eq) 877 : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { } 878 879 bool 880 _M_equals(const _Key& __k, _Hash_code_type __c, 881 _Hash_node<_Value, __cache_hash_code>* __n) const 882 { 883 typedef _Equal_helper<_Key, _Value, _ExtractKey, 884 _Equal, _Hash_code_type, 885 __cache_hash_code> _EqualHelper; 886 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), 887 __k, __c, __n); 888 } 889 890 void 891 _M_swap(_Hashtable_base& __x) 892 { 893 _HCBase::_M_swap(__x); 894 std::swap(_M_eq(), __x._M_eq()); 895 } 896 897 protected: 898 const _Equal& 899 _M_eq() const { return _EboEqual::_S_cget(*this); } 900 _Equal& 901 _M_eq() { return _EboEqual::_S_get(*this); } 902 }; 903 904 // Local iterators, used to iterate within a bucket but not between 905 // buckets. 906 template<typename _Key, typename _Value, typename _ExtractKey, 907 typename _H1, typename _H2, typename _Hash, 908 bool __cache_hash_code> 909 struct _Local_iterator_base; 910 911 template<typename _Key, typename _Value, typename _ExtractKey, 912 typename _H1, typename _H2, typename _Hash> 913 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 914 _H1, _H2, _Hash, true> 915 // See PR53067. 916 : public _H2 917 { 918 _Local_iterator_base() = default; 919 _Local_iterator_base(_Hash_node<_Value, true>* __p, 920 std::size_t __bkt, std::size_t __bkt_count) 921 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 922 923 void 924 _M_incr() 925 { 926 _M_cur = _M_cur->_M_next(); 927 if (_M_cur) 928 { 929 std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count); 930 if (__bkt != _M_bucket) 931 _M_cur = nullptr; 932 } 933 } 934 935 const _H2& _M_h2() const 936 { return *this; } 937 938 _Hash_node<_Value, true>* _M_cur; 939 std::size_t _M_bucket; 940 std::size_t _M_bucket_count; 941 }; 942 943 template<typename _Key, typename _Value, typename _ExtractKey, 944 typename _H1, typename _H2, typename _Hash> 945 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 946 _H1, _H2, _Hash, false> 947 // See PR53067. 948 : public _Hash_code_base<_Key, _Value, _ExtractKey, 949 _H1, _H2, _Hash, false> 950 { 951 _Local_iterator_base() = default; 952 _Local_iterator_base(_Hash_node<_Value, false>* __p, 953 std::size_t __bkt, std::size_t __bkt_count) 954 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 955 956 void 957 _M_incr() 958 { 959 _M_cur = _M_cur->_M_next(); 960 if (_M_cur) 961 { 962 std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count); 963 if (__bkt != _M_bucket) 964 _M_cur = nullptr; 965 } 966 } 967 968 _Hash_node<_Value, false>* _M_cur; 969 std::size_t _M_bucket; 970 std::size_t _M_bucket_count; 971 }; 972 973 template<typename _Key, typename _Value, typename _ExtractKey, 974 typename _H1, typename _H2, typename _Hash, bool __cache> 975 inline bool 976 operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey, 977 _H1, _H2, _Hash, __cache>& __x, 978 const _Local_iterator_base<_Key, _Value, _ExtractKey, 979 _H1, _H2, _Hash, __cache>& __y) 980 { return __x._M_cur == __y._M_cur; } 981 982 template<typename _Key, typename _Value, typename _ExtractKey, 983 typename _H1, typename _H2, typename _Hash, bool __cache> 984 inline bool 985 operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey, 986 _H1, _H2, _Hash, __cache>& __x, 987 const _Local_iterator_base<_Key, _Value, _ExtractKey, 988 _H1, _H2, _Hash, __cache>& __y) 989 { return __x._M_cur != __y._M_cur; } 990 991 template<typename _Key, typename _Value, typename _ExtractKey, 992 typename _H1, typename _H2, typename _Hash, 993 bool __constant_iterators, bool __cache> 994 struct _Local_iterator 995 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 996 _H1, _H2, _Hash, __cache> 997 { 998 typedef _Value value_type; 999 typedef typename std::conditional<__constant_iterators, 1000 const _Value*, _Value*>::type 1001 pointer; 1002 typedef typename std::conditional<__constant_iterators, 1003 const _Value&, _Value&>::type 1004 reference; 1005 typedef std::ptrdiff_t difference_type; 1006 typedef std::forward_iterator_tag iterator_category; 1007 1008 _Local_iterator() = default; 1009 1010 explicit 1011 _Local_iterator(_Hash_node<_Value, __cache>* __p, 1012 std::size_t __bkt, std::size_t __bkt_count) 1013 : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 1014 __cache>(__p, __bkt, __bkt_count) 1015 { } 1016 1017 reference 1018 operator*() const 1019 { return this->_M_cur->_M_v; } 1020 1021 pointer 1022 operator->() const 1023 { return std::__addressof(this->_M_cur->_M_v); } 1024 1025 _Local_iterator& 1026 operator++() 1027 { 1028 this->_M_incr(); 1029 return *this; 1030 } 1031 1032 _Local_iterator 1033 operator++(int) 1034 { 1035 _Local_iterator __tmp(*this); 1036 this->_M_incr(); 1037 return __tmp; 1038 } 1039 }; 1040 1041 template<typename _Key, typename _Value, typename _ExtractKey, 1042 typename _H1, typename _H2, typename _Hash, 1043 bool __constant_iterators, bool __cache> 1044 struct _Local_const_iterator 1045 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 1046 _H1, _H2, _Hash, __cache> 1047 { 1048 typedef _Value value_type; 1049 typedef const _Value* pointer; 1050 typedef const _Value& reference; 1051 typedef std::ptrdiff_t difference_type; 1052 typedef std::forward_iterator_tag iterator_category; 1053 1054 _Local_const_iterator() = default; 1055 1056 explicit 1057 _Local_const_iterator(_Hash_node<_Value, __cache>* __p, 1058 std::size_t __bkt, std::size_t __bkt_count) 1059 : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 1060 __cache>(__p, __bkt, __bkt_count) 1061 { } 1062 1063 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, 1064 _H1, _H2, _Hash, 1065 __constant_iterators, 1066 __cache>& __x) 1067 : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 1068 __cache>(__x._M_cur, __x._M_bucket, 1069 __x._M_bucket_count) 1070 { } 1071 1072 reference 1073 operator*() const 1074 { return this->_M_cur->_M_v; } 1075 1076 pointer 1077 operator->() const 1078 { return std::__addressof(this->_M_cur->_M_v); } 1079 1080 _Local_const_iterator& 1081 operator++() 1082 { 1083 this->_M_incr(); 1084 return *this; 1085 } 1086 1087 _Local_const_iterator 1088 operator++(int) 1089 { 1090 _Local_const_iterator __tmp(*this); 1091 this->_M_incr(); 1092 return __tmp; 1093 } 1094 }; 1095 1096 1097 // Class template _Equality_base. This is for implementing equality 1098 // comparison for unordered containers, per N3068, by John Lakos and 1099 // Pablo Halpern. Algorithmically, we follow closely the reference 1100 // implementations therein. 1101 template<typename _ExtractKey, bool __unique_keys, 1102 typename _Hashtable> 1103 struct _Equality_base; 1104 1105 template<typename _ExtractKey, typename _Hashtable> 1106 struct _Equality_base<_ExtractKey, true, _Hashtable> 1107 { 1108 bool _M_equal(const _Hashtable&) const; 1109 }; 1110 1111 template<typename _ExtractKey, typename _Hashtable> 1112 bool 1113 _Equality_base<_ExtractKey, true, _Hashtable>:: 1114 _M_equal(const _Hashtable& __other) const 1115 { 1116 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 1117 1118 if (__this->size() != __other.size()) 1119 return false; 1120 1121 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) 1122 { 1123 const auto __ity = __other.find(_ExtractKey()(*__itx)); 1124 if (__ity == __other.end() || !bool(*__ity == *__itx)) 1125 return false; 1126 } 1127 return true; 1128 } 1129 1130 template<typename _ExtractKey, typename _Hashtable> 1131 struct _Equality_base<_ExtractKey, false, _Hashtable> 1132 { 1133 bool _M_equal(const _Hashtable&) const; 1134 1135 private: 1136 template<typename _Uiterator> 1137 static bool 1138 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); 1139 }; 1140 1141 // See std::is_permutation in N3068. 1142 template<typename _ExtractKey, typename _Hashtable> 1143 template<typename _Uiterator> 1144 bool 1145 _Equality_base<_ExtractKey, false, _Hashtable>:: 1146 _S_is_permutation(_Uiterator __first1, _Uiterator __last1, 1147 _Uiterator __first2) 1148 { 1149 for (; __first1 != __last1; ++__first1, ++__first2) 1150 if (!(*__first1 == *__first2)) 1151 break; 1152 1153 if (__first1 == __last1) 1154 return true; 1155 1156 _Uiterator __last2 = __first2; 1157 std::advance(__last2, std::distance(__first1, __last1)); 1158 1159 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) 1160 { 1161 _Uiterator __tmp = __first1; 1162 while (__tmp != __it1 && !bool(*__tmp == *__it1)) 1163 ++__tmp; 1164 1165 // We've seen this one before. 1166 if (__tmp != __it1) 1167 continue; 1168 1169 std::ptrdiff_t __n2 = 0; 1170 for (__tmp = __first2; __tmp != __last2; ++__tmp) 1171 if (*__tmp == *__it1) 1172 ++__n2; 1173 1174 if (!__n2) 1175 return false; 1176 1177 std::ptrdiff_t __n1 = 0; 1178 for (__tmp = __it1; __tmp != __last1; ++__tmp) 1179 if (*__tmp == *__it1) 1180 ++__n1; 1181 1182 if (__n1 != __n2) 1183 return false; 1184 } 1185 return true; 1186 } 1187 1188 template<typename _ExtractKey, typename _Hashtable> 1189 bool 1190 _Equality_base<_ExtractKey, false, _Hashtable>:: 1191 _M_equal(const _Hashtable& __other) const 1192 { 1193 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 1194 1195 if (__this->size() != __other.size()) 1196 return false; 1197 1198 for (auto __itx = __this->begin(); __itx != __this->end();) 1199 { 1200 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); 1201 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); 1202 1203 if (std::distance(__xrange.first, __xrange.second) 1204 != std::distance(__yrange.first, __yrange.second)) 1205 return false; 1206 1207 if (!_S_is_permutation(__xrange.first, 1208 __xrange.second, 1209 __yrange.first)) 1210 return false; 1211 1212 __itx = __xrange.second; 1213 } 1214 return true; 1215 } 1216 1217 _GLIBCXX_END_NAMESPACE_VERSION 1218 } // namespace __detail 1219 } // namespace std 1220 1221 #endif // _HASHTABLE_POLICY_H 1222