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