1169691Skan// Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the 7169691Skan// terms of the GNU General Public License as published by the 8169691Skan// Free Software Foundation; either version 2, or (at your option) 9169691Skan// any later version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, 12169691Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169691Skan// GNU General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License along 17169691Skan// with this library; see the file COPYING. If not, write to the Free 18169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19169691Skan// USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free software 22169691Skan// library without restriction. Specifically, if other files instantiate 23169691Skan// templates or use macros or inline functions from this file, or you compile 24169691Skan// this file and link it with other files to produce an executable, this 25169691Skan// file does not by itself cause the resulting executable to be covered by 26169691Skan// the GNU General Public License. This exception does not however 27169691Skan// invalidate any other reasons why the executable file might be covered by 28169691Skan// the GNU General Public License. 29169691Skan 30169691Skan/** @file tr1/hashtable_policy.h 31169691Skan * This is a TR1 C++ Library header. 32169691Skan */ 33169691Skan 34169691Skan#ifndef _TR1_HASHTABLE_POLICY_H 35169691Skan#define _TR1_HASHTABLE_POLICY_H 1 36169691Skan 37169691Skan#include <functional> // _Identity, _Select1st 38169691Skan#include <tr1/utility> 39169691Skan#include <ext/type_traits.h> 40169691Skan 41169691Skannamespace std 42169691Skan{ 43169691Skan_GLIBCXX_BEGIN_NAMESPACE(tr1) 44169691Skannamespace __detail 45169691Skan{ 46169691Skan // Helper function: return distance(first, last) for forward 47169691Skan // iterators, or 0 for input iterators. 48169691Skan template<class _Iterator> 49169691Skan inline typename std::iterator_traits<_Iterator>::difference_type 50169691Skan __distance_fw(_Iterator __first, _Iterator __last, 51169691Skan std::input_iterator_tag) 52169691Skan { return 0; } 53169691Skan 54169691Skan template<class _Iterator> 55169691Skan inline typename std::iterator_traits<_Iterator>::difference_type 56169691Skan __distance_fw(_Iterator __first, _Iterator __last, 57169691Skan std::forward_iterator_tag) 58169691Skan { return std::distance(__first, __last); } 59169691Skan 60169691Skan template<class _Iterator> 61169691Skan inline typename std::iterator_traits<_Iterator>::difference_type 62169691Skan __distance_fw(_Iterator __first, _Iterator __last) 63169691Skan { 64169691Skan typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; 65169691Skan return __distance_fw(__first, __last, _Tag()); 66169691Skan } 67169691Skan 68169691Skan // XXX This is a hack. _Prime_rehash_policy's member functions, and 69169691Skan // certainly the list of primes, should be defined in a .cc file. 70169691Skan // We're temporarily putting them in a header because we don't have a 71169691Skan // place to put TR1 .cc files yet. There's no good reason for any of 72169691Skan // _Prime_rehash_policy's member functions to be inline, and there's 73169691Skan // certainly no good reason for _Primes<> to exist at all. 74169691Skan struct _LessThan 75169691Skan { 76169691Skan template<typename _Tp, typename _Up> 77169691Skan bool 78169691Skan operator()(_Tp __x, _Up __y) 79169691Skan { return __x < __y; } 80169691Skan }; 81169691Skan 82169691Skan template<int __ulongsize = sizeof(unsigned long)> 83169691Skan struct _Primes 84169691Skan { 85169691Skan static const int __n_primes = __ulongsize != 8 ? 256 : 256 + 48; 86169691Skan static const unsigned long __primes[256 + 48 + 1]; 87169691Skan }; 88169691Skan 89169691Skan template<int __ulongsize> 90169691Skan const int _Primes<__ulongsize>::__n_primes; 91169691Skan 92169691Skan template<int __ulongsize> 93169691Skan const unsigned long _Primes<__ulongsize>::__primes[256 + 48 + 1] = 94169691Skan { 95169691Skan 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, 96169691Skan 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, 97169691Skan 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, 98169691Skan 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul, 99169691Skan 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul, 100169691Skan 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul, 101169691Skan 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul, 102169691Skan 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul, 103169691Skan 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul, 104169691Skan 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul, 105169691Skan 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul, 106169691Skan 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul, 107169691Skan 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul, 108169691Skan 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul, 109169691Skan 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul, 110169691Skan 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul, 111169691Skan 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul, 112169691Skan 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul, 113169691Skan 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul, 114169691Skan 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul, 115169691Skan 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul, 116169691Skan 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, 117169691Skan 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, 118169691Skan 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul, 119169691Skan 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul, 120169691Skan 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul, 121169691Skan 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul, 122169691Skan 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul, 123169691Skan 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul, 124169691Skan 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul, 125169691Skan 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul, 126169691Skan 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul, 127169691Skan 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul, 128169691Skan 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul, 129169691Skan 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul, 130169691Skan 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul, 131169691Skan 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, 132169691Skan 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul, 133169691Skan 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul, 134169691Skan 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul, 135169691Skan 4294967291ul, 136169691Skan // Sentinel, so we don't have to test the result of lower_bound, 137169691Skan // or, on 64-bit machines, rest of the table. 138169691Skan __ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull, 139169691Skan (unsigned long)8589934583ull, 140169691Skan (unsigned long)12884901857ull, (unsigned long)17179869143ull, 141169691Skan (unsigned long)25769803693ull, (unsigned long)34359738337ull, 142169691Skan (unsigned long)51539607367ull, (unsigned long)68719476731ull, 143169691Skan (unsigned long)103079215087ull, (unsigned long)137438953447ull, 144169691Skan (unsigned long)206158430123ull, (unsigned long)274877906899ull, 145169691Skan (unsigned long)412316860387ull, (unsigned long)549755813881ull, 146169691Skan (unsigned long)824633720731ull, (unsigned long)1099511627689ull, 147169691Skan (unsigned long)1649267441579ull, (unsigned long)2199023255531ull, 148169691Skan (unsigned long)3298534883309ull, (unsigned long)4398046511093ull, 149169691Skan (unsigned long)6597069766607ull, (unsigned long)8796093022151ull, 150169691Skan (unsigned long)13194139533241ull, (unsigned long)17592186044399ull, 151169691Skan (unsigned long)26388279066581ull, (unsigned long)35184372088777ull, 152169691Skan (unsigned long)52776558133177ull, (unsigned long)70368744177643ull, 153169691Skan (unsigned long)105553116266399ull, (unsigned long)140737488355213ull, 154169691Skan (unsigned long)211106232532861ull, (unsigned long)281474976710597ull, 155169691Skan (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull, 156169691Skan (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull, 157169691Skan (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull, 158169691Skan (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull, 159169691Skan (unsigned long)144115188075855859ull, 160169691Skan (unsigned long)288230376151711717ull, 161169691Skan (unsigned long)576460752303423433ull, 162169691Skan (unsigned long)1152921504606846883ull, 163169691Skan (unsigned long)2305843009213693951ull, 164169691Skan (unsigned long)4611686018427387847ull, 165169691Skan (unsigned long)9223372036854775783ull, 166169691Skan (unsigned long)18446744073709551557ull, 167169691Skan (unsigned long)18446744073709551557ull 168169691Skan }; 169169691Skan 170169691Skan // Auxiliary types used for all instantiations of _Hashtable: nodes 171169691Skan // and iterators. 172169691Skan 173169691Skan // Nodes, used to wrap elements stored in the hash table. A policy 174169691Skan // template parameter of class template _Hashtable controls whether 175169691Skan // nodes also store a hash code. In some cases (e.g. strings) this 176169691Skan // may be a performance win. 177169691Skan template<typename _Value, bool __cache_hash_code> 178169691Skan struct _Hash_node; 179169691Skan 180169691Skan template<typename _Value> 181169691Skan struct _Hash_node<_Value, true> 182169691Skan { 183169691Skan _Value _M_v; 184169691Skan std::size_t _M_hash_code; 185169691Skan _Hash_node* _M_next; 186169691Skan }; 187169691Skan 188169691Skan template<typename _Value> 189169691Skan struct _Hash_node<_Value, false> 190169691Skan { 191169691Skan _Value _M_v; 192169691Skan _Hash_node* _M_next; 193169691Skan }; 194169691Skan 195169691Skan // Local iterators, used to iterate within a bucket but not between 196169691Skan // buckets. 197169691Skan template<typename _Value, bool __cache> 198169691Skan struct _Node_iterator_base 199169691Skan { 200169691Skan _Node_iterator_base(_Hash_node<_Value, __cache>* __p) 201169691Skan : _M_cur(__p) { } 202169691Skan 203169691Skan void 204169691Skan _M_incr() 205169691Skan { _M_cur = _M_cur->_M_next; } 206169691Skan 207169691Skan _Hash_node<_Value, __cache>* _M_cur; 208169691Skan }; 209169691Skan 210169691Skan template<typename _Value, bool __cache> 211169691Skan inline bool 212169691Skan operator==(const _Node_iterator_base<_Value, __cache>& __x, 213169691Skan const _Node_iterator_base<_Value, __cache>& __y) 214169691Skan { return __x._M_cur == __y._M_cur; } 215169691Skan 216169691Skan template<typename _Value, bool __cache> 217169691Skan inline bool 218169691Skan operator!=(const _Node_iterator_base<_Value, __cache>& __x, 219169691Skan const _Node_iterator_base<_Value, __cache>& __y) 220169691Skan { return __x._M_cur != __y._M_cur; } 221169691Skan 222169691Skan template<typename _Value, bool __constant_iterators, bool __cache> 223169691Skan struct _Node_iterator 224169691Skan : public _Node_iterator_base<_Value, __cache> 225169691Skan { 226169691Skan typedef _Value value_type; 227169691Skan typedef typename 228169691Skan __gnu_cxx::__conditional_type<__constant_iterators, 229169691Skan const _Value*, _Value*>::__type 230169691Skan pointer; 231169691Skan typedef typename 232169691Skan __gnu_cxx::__conditional_type<__constant_iterators, 233169691Skan const _Value&, _Value&>::__type 234169691Skan reference; 235169691Skan typedef std::ptrdiff_t difference_type; 236169691Skan typedef std::forward_iterator_tag iterator_category; 237169691Skan 238169691Skan _Node_iterator() 239169691Skan : _Node_iterator_base<_Value, __cache>(0) { } 240169691Skan 241169691Skan explicit 242169691Skan _Node_iterator(_Hash_node<_Value, __cache>* __p) 243169691Skan : _Node_iterator_base<_Value, __cache>(__p) { } 244169691Skan 245169691Skan reference 246169691Skan operator*() const 247169691Skan { return this->_M_cur->_M_v; } 248169691Skan 249169691Skan pointer 250169691Skan operator->() const 251169691Skan { return &this->_M_cur->_M_v; } 252169691Skan 253169691Skan _Node_iterator& 254169691Skan operator++() 255169691Skan { 256169691Skan this->_M_incr(); 257169691Skan return *this; 258169691Skan } 259169691Skan 260169691Skan _Node_iterator 261169691Skan operator++(int) 262169691Skan { 263169691Skan _Node_iterator __tmp(*this); 264169691Skan this->_M_incr(); 265169691Skan return __tmp; 266169691Skan } 267169691Skan }; 268169691Skan 269169691Skan template<typename _Value, bool __constant_iterators, bool __cache> 270169691Skan struct _Node_const_iterator 271169691Skan : public _Node_iterator_base<_Value, __cache> 272169691Skan { 273169691Skan typedef _Value value_type; 274169691Skan typedef const _Value* pointer; 275169691Skan typedef const _Value& reference; 276169691Skan typedef std::ptrdiff_t difference_type; 277169691Skan typedef std::forward_iterator_tag iterator_category; 278169691Skan 279169691Skan _Node_const_iterator() 280169691Skan : _Node_iterator_base<_Value, __cache>(0) { } 281169691Skan 282169691Skan explicit 283169691Skan _Node_const_iterator(_Hash_node<_Value, __cache>* __p) 284169691Skan : _Node_iterator_base<_Value, __cache>(__p) { } 285169691Skan 286169691Skan _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, 287169691Skan __cache>& __x) 288169691Skan : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } 289169691Skan 290169691Skan reference 291169691Skan operator*() const 292169691Skan { return this->_M_cur->_M_v; } 293169691Skan 294169691Skan pointer 295169691Skan operator->() const 296169691Skan { return &this->_M_cur->_M_v; } 297169691Skan 298169691Skan _Node_const_iterator& 299169691Skan operator++() 300169691Skan { 301169691Skan this->_M_incr(); 302169691Skan return *this; 303169691Skan } 304169691Skan 305169691Skan _Node_const_iterator 306169691Skan operator++(int) 307169691Skan { 308169691Skan _Node_const_iterator __tmp(*this); 309169691Skan this->_M_incr(); 310169691Skan return __tmp; 311169691Skan } 312169691Skan }; 313169691Skan 314169691Skan template<typename _Value, bool __cache> 315169691Skan struct _Hashtable_iterator_base 316169691Skan { 317169691Skan _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node, 318169691Skan _Hash_node<_Value, __cache>** __bucket) 319169691Skan : _M_cur_node(__node), _M_cur_bucket(__bucket) { } 320169691Skan 321169691Skan void 322169691Skan _M_incr() 323169691Skan { 324169691Skan _M_cur_node = _M_cur_node->_M_next; 325169691Skan if (!_M_cur_node) 326169691Skan _M_incr_bucket(); 327169691Skan } 328169691Skan 329169691Skan void 330169691Skan _M_incr_bucket(); 331169691Skan 332169691Skan _Hash_node<_Value, __cache>* _M_cur_node; 333169691Skan _Hash_node<_Value, __cache>** _M_cur_bucket; 334169691Skan }; 335169691Skan 336169691Skan // Global iterators, used for arbitrary iteration within a hash 337169691Skan // table. Larger and more expensive than local iterators. 338169691Skan template<typename _Value, bool __cache> 339169691Skan void 340169691Skan _Hashtable_iterator_base<_Value, __cache>:: 341169691Skan _M_incr_bucket() 342169691Skan { 343169691Skan ++_M_cur_bucket; 344169691Skan 345169691Skan // This loop requires the bucket array to have a non-null sentinel. 346169691Skan while (!*_M_cur_bucket) 347169691Skan ++_M_cur_bucket; 348169691Skan _M_cur_node = *_M_cur_bucket; 349169691Skan } 350169691Skan 351169691Skan template<typename _Value, bool __cache> 352169691Skan inline bool 353169691Skan operator==(const _Hashtable_iterator_base<_Value, __cache>& __x, 354169691Skan const _Hashtable_iterator_base<_Value, __cache>& __y) 355169691Skan { return __x._M_cur_node == __y._M_cur_node; } 356169691Skan 357169691Skan template<typename _Value, bool __cache> 358169691Skan inline bool 359169691Skan operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x, 360169691Skan const _Hashtable_iterator_base<_Value, __cache>& __y) 361169691Skan { return __x._M_cur_node != __y._M_cur_node; } 362169691Skan 363169691Skan template<typename _Value, bool __constant_iterators, bool __cache> 364169691Skan struct _Hashtable_iterator 365169691Skan : public _Hashtable_iterator_base<_Value, __cache> 366169691Skan { 367169691Skan typedef _Value value_type; 368169691Skan typedef typename 369169691Skan __gnu_cxx::__conditional_type<__constant_iterators, 370169691Skan const _Value*, _Value*>::__type 371169691Skan pointer; 372169691Skan typedef typename 373169691Skan __gnu_cxx::__conditional_type<__constant_iterators, 374169691Skan const _Value&, _Value&>::__type 375169691Skan reference; 376169691Skan typedef std::ptrdiff_t difference_type; 377169691Skan typedef std::forward_iterator_tag iterator_category; 378169691Skan 379169691Skan _Hashtable_iterator() 380169691Skan : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } 381169691Skan 382169691Skan _Hashtable_iterator(_Hash_node<_Value, __cache>* __p, 383169691Skan _Hash_node<_Value, __cache>** __b) 384169691Skan : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } 385169691Skan 386169691Skan explicit 387169691Skan _Hashtable_iterator(_Hash_node<_Value, __cache>** __b) 388169691Skan : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } 389169691Skan 390169691Skan reference 391169691Skan operator*() const 392169691Skan { return this->_M_cur_node->_M_v; } 393169691Skan 394169691Skan pointer 395169691Skan operator->() const 396169691Skan { return &this->_M_cur_node->_M_v; } 397169691Skan 398169691Skan _Hashtable_iterator& 399169691Skan operator++() 400169691Skan { 401169691Skan this->_M_incr(); 402169691Skan return *this; 403169691Skan } 404169691Skan 405169691Skan _Hashtable_iterator 406169691Skan operator++(int) 407169691Skan { 408169691Skan _Hashtable_iterator __tmp(*this); 409169691Skan this->_M_incr(); 410169691Skan return __tmp; 411169691Skan } 412169691Skan }; 413169691Skan 414169691Skan template<typename _Value, bool __constant_iterators, bool __cache> 415169691Skan struct _Hashtable_const_iterator 416169691Skan : public _Hashtable_iterator_base<_Value, __cache> 417169691Skan { 418169691Skan typedef _Value value_type; 419169691Skan typedef const _Value* pointer; 420169691Skan typedef const _Value& reference; 421169691Skan typedef std::ptrdiff_t difference_type; 422169691Skan typedef std::forward_iterator_tag iterator_category; 423169691Skan 424169691Skan _Hashtable_const_iterator() 425169691Skan : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } 426169691Skan 427169691Skan _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p, 428169691Skan _Hash_node<_Value, __cache>** __b) 429169691Skan : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } 430169691Skan 431169691Skan explicit 432169691Skan _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b) 433169691Skan : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } 434169691Skan 435169691Skan _Hashtable_const_iterator(const _Hashtable_iterator<_Value, 436169691Skan __constant_iterators, __cache>& __x) 437169691Skan : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node, 438169691Skan __x._M_cur_bucket) { } 439169691Skan 440169691Skan reference 441169691Skan operator*() const 442169691Skan { return this->_M_cur_node->_M_v; } 443169691Skan 444169691Skan pointer 445169691Skan operator->() const 446169691Skan { return &this->_M_cur_node->_M_v; } 447169691Skan 448169691Skan _Hashtable_const_iterator& 449169691Skan operator++() 450169691Skan { 451169691Skan this->_M_incr(); 452169691Skan return *this; 453169691Skan } 454169691Skan 455169691Skan _Hashtable_const_iterator 456169691Skan operator++(int) 457169691Skan { 458169691Skan _Hashtable_const_iterator __tmp(*this); 459169691Skan this->_M_incr(); 460169691Skan return __tmp; 461169691Skan } 462169691Skan }; 463169691Skan 464169691Skan 465169691Skan // Many of class template _Hashtable's template parameters are policy 466169691Skan // classes. These are defaults for the policies. 467169691Skan 468169691Skan // Default range hashing function: use division to fold a large number 469169691Skan // into the range [0, N). 470169691Skan struct _Mod_range_hashing 471169691Skan { 472169691Skan typedef std::size_t first_argument_type; 473169691Skan typedef std::size_t second_argument_type; 474169691Skan typedef std::size_t result_type; 475169691Skan 476169691Skan result_type 477169691Skan operator()(first_argument_type __num, second_argument_type __den) const 478169691Skan { return __num % __den; } 479169691Skan }; 480169691Skan 481169691Skan // Default ranged hash function H. In principle it should be a 482169691Skan // function object composed from objects of type H1 and H2 such that 483169691Skan // h(k, N) = h2(h1(k), N), but that would mean making extra copies of 484169691Skan // h1 and h2. So instead we'll just use a tag to tell class template 485169691Skan // hashtable to do that composition. 486169691Skan struct _Default_ranged_hash { }; 487169691Skan 488169691Skan // Default value for rehash policy. Bucket size is (usually) the 489169691Skan // smallest prime that keeps the load factor small enough. 490169691Skan struct _Prime_rehash_policy 491169691Skan { 492169691Skan _Prime_rehash_policy(float __z = 1.0); 493169691Skan 494169691Skan float 495169691Skan max_load_factor() const; 496169691Skan 497169691Skan // Return a bucket size no smaller than n. 498169691Skan std::size_t 499169691Skan _M_next_bkt(std::size_t __n) const; 500169691Skan 501169691Skan // Return a bucket count appropriate for n elements 502169691Skan std::size_t 503169691Skan _M_bkt_for_elements(std::size_t __n) const; 504169691Skan 505169691Skan // __n_bkt is current bucket count, __n_elt is current element count, 506169691Skan // and __n_ins is number of elements to be inserted. Do we need to 507169691Skan // increase bucket count? If so, return make_pair(true, n), where n 508169691Skan // is the new bucket count. If not, return make_pair(false, 0). 509169691Skan std::pair<bool, std::size_t> 510169691Skan _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 511169691Skan std::size_t __n_ins) const; 512169691Skan 513169691Skan float _M_max_load_factor; 514169691Skan float _M_growth_factor; 515169691Skan mutable std::size_t _M_next_resize; 516169691Skan }; 517169691Skan 518169691Skan inline 519169691Skan _Prime_rehash_policy:: 520169691Skan _Prime_rehash_policy(float __z) 521169691Skan : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) 522169691Skan { } 523169691Skan 524169691Skan inline float 525169691Skan _Prime_rehash_policy:: 526169691Skan max_load_factor() const 527169691Skan { return _M_max_load_factor; } 528169691Skan 529169691Skan // Return a prime no smaller than n. 530169691Skan inline std::size_t 531169691Skan _Prime_rehash_policy:: 532169691Skan _M_next_bkt(std::size_t __n) const 533169691Skan { 534169691Skan const unsigned long* const __last = (_Primes<>::__primes 535169691Skan + _Primes<>::__n_primes); 536169691Skan const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last, 537169691Skan __n); 538169691Skan _M_next_resize = static_cast<std::size_t>(std::ceil(*__p 539169691Skan * _M_max_load_factor)); 540169691Skan return *__p; 541169691Skan } 542169691Skan 543169691Skan // Return the smallest prime p such that alpha p >= n, where alpha 544169691Skan // is the load factor. 545169691Skan inline std::size_t 546169691Skan _Prime_rehash_policy:: 547169691Skan _M_bkt_for_elements(std::size_t __n) const 548169691Skan { 549169691Skan const unsigned long* const __last = (_Primes<>::__primes 550169691Skan + _Primes<>::__n_primes); 551169691Skan const float __min_bkts = __n / _M_max_load_factor; 552169691Skan const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last, 553169691Skan __min_bkts, _LessThan()); 554169691Skan _M_next_resize = static_cast<std::size_t>(std::ceil(*__p 555169691Skan * _M_max_load_factor)); 556169691Skan return *__p; 557169691Skan } 558169691Skan 559169691Skan // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. 560169691Skan // If p > __n_bkt, return make_pair(true, p); otherwise return 561169691Skan // make_pair(false, 0). In principle this isn't very different from 562169691Skan // _M_bkt_for_elements. 563169691Skan 564169691Skan // The only tricky part is that we're caching the element count at 565169691Skan // which we need to rehash, so we don't have to do a floating-point 566169691Skan // multiply for every insertion. 567169691Skan 568169691Skan inline std::pair<bool, std::size_t> 569169691Skan _Prime_rehash_policy:: 570169691Skan _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 571169691Skan std::size_t __n_ins) const 572169691Skan { 573169691Skan if (__n_elt + __n_ins > _M_next_resize) 574169691Skan { 575169691Skan float __min_bkts = ((float(__n_ins) + float(__n_elt)) 576169691Skan / _M_max_load_factor); 577169691Skan if (__min_bkts > __n_bkt) 578169691Skan { 579169691Skan __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); 580169691Skan const unsigned long* const __last = (_Primes<>::__primes 581169691Skan + _Primes<>::__n_primes); 582169691Skan const unsigned long* __p = std::lower_bound(_Primes<>::__primes, 583169691Skan __last, __min_bkts, 584169691Skan _LessThan()); 585169691Skan _M_next_resize = 586169691Skan static_cast<std::size_t>(std::ceil(*__p * _M_max_load_factor)); 587169691Skan return std::make_pair(true, *__p); 588169691Skan } 589169691Skan else 590169691Skan { 591169691Skan _M_next_resize = 592169691Skan static_cast<std::size_t>(std::ceil(__n_bkt 593169691Skan * _M_max_load_factor)); 594169691Skan return std::make_pair(false, 0); 595169691Skan } 596169691Skan } 597169691Skan else 598169691Skan return std::make_pair(false, 0); 599169691Skan } 600169691Skan 601169691Skan // Base classes for std::tr1::_Hashtable. We define these base 602169691Skan // classes because in some cases we want to do different things 603169691Skan // depending on the value of a policy class. In some cases the 604169691Skan // policy class affects which member functions and nested typedefs 605169691Skan // are defined; we handle that by specializing base class templates. 606169691Skan // Several of the base class templates need to access other members 607169691Skan // of class template _Hashtable, so we use the "curiously recurring 608169691Skan // template pattern" for them. 609169691Skan 610169691Skan // class template _Map_base. If the hashtable has a value type of the 611169691Skan // form pair<T1, T2> and a key extraction policy that returns the 612169691Skan // first part of the pair, the hashtable gets a mapped_type typedef. 613169691Skan // If it satisfies those criteria and also has unique keys, then it 614169691Skan // also gets an operator[]. 615169691Skan template<typename _Key, typename _Value, typename _Ex, bool __unique, 616169691Skan typename _Hashtable> 617169691Skan struct _Map_base { }; 618169691Skan 619169691Skan template<typename _Key, typename _Pair, typename _Hashtable> 620169691Skan struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> 621169691Skan { 622169691Skan typedef typename _Pair::second_type mapped_type; 623169691Skan }; 624169691Skan 625169691Skan template<typename _Key, typename _Pair, typename _Hashtable> 626169691Skan struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> 627169691Skan { 628169691Skan typedef typename _Pair::second_type mapped_type; 629169691Skan 630169691Skan mapped_type& 631169691Skan operator[](const _Key& __k); 632169691Skan }; 633169691Skan 634169691Skan template<typename _Key, typename _Pair, typename _Hashtable> 635169691Skan typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 636169691Skan true, _Hashtable>::mapped_type& 637169691Skan _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 638169691Skan operator[](const _Key& __k) 639169691Skan { 640169691Skan _Hashtable* __h = static_cast<_Hashtable*>(this); 641169691Skan typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 642169691Skan std::size_t __n = __h->_M_bucket_index(__k, __code, 643169691Skan __h->_M_bucket_count); 644169691Skan 645169691Skan typename _Hashtable::_Node* __p = 646169691Skan __h->_M_find_node(__h->_M_buckets[__n], __k, __code); 647169691Skan if (!__p) 648169691Skan return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), 649169691Skan __n, __code)->second; 650169691Skan return (__p->_M_v).second; 651169691Skan } 652169691Skan 653169691Skan // class template _Rehash_base. Give hashtable the max_load_factor 654169691Skan // functions iff the rehash policy is _Prime_rehash_policy. 655169691Skan template<typename _RehashPolicy, typename _Hashtable> 656169691Skan struct _Rehash_base { }; 657169691Skan 658169691Skan template<typename _Hashtable> 659169691Skan struct _Rehash_base<_Prime_rehash_policy, _Hashtable> 660169691Skan { 661169691Skan float 662169691Skan max_load_factor() const 663169691Skan { 664169691Skan const _Hashtable* __this = static_cast<const _Hashtable*>(this); 665169691Skan return __this->__rehash_policy().max_load_factor(); 666169691Skan } 667169691Skan 668169691Skan void 669169691Skan max_load_factor(float __z) 670169691Skan { 671169691Skan _Hashtable* __this = static_cast<_Hashtable*>(this); 672169691Skan __this->__rehash_policy(_Prime_rehash_policy(__z)); 673169691Skan } 674169691Skan }; 675169691Skan 676169691Skan // Class template _Hash_code_base. Encapsulates two policy issues that 677169691Skan // aren't quite orthogonal. 678169691Skan // (1) the difference between using a ranged hash function and using 679169691Skan // the combination of a hash function and a range-hashing function. 680169691Skan // In the former case we don't have such things as hash codes, so 681169691Skan // we have a dummy type as placeholder. 682169691Skan // (2) Whether or not we cache hash codes. Caching hash codes is 683169691Skan // meaningless if we have a ranged hash function. 684169691Skan // We also put the key extraction and equality comparison function 685169691Skan // objects here, for convenience. 686169691Skan 687169691Skan // Primary template: unused except as a hook for specializations. 688169691Skan template<typename _Key, typename _Value, 689169691Skan typename _ExtractKey, typename _Equal, 690169691Skan typename _H1, typename _H2, typename _Hash, 691169691Skan bool __cache_hash_code> 692169691Skan struct _Hash_code_base; 693169691Skan 694169691Skan // Specialization: ranged hash function, no caching hash codes. H1 695169691Skan // and H2 are provided but ignored. We define a dummy hash code type. 696169691Skan template<typename _Key, typename _Value, 697169691Skan typename _ExtractKey, typename _Equal, 698169691Skan typename _H1, typename _H2, typename _Hash> 699169691Skan struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 700169691Skan _Hash, false> 701169691Skan { 702169691Skan protected: 703169691Skan _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 704169691Skan const _H1&, const _H2&, const _Hash& __h) 705169691Skan : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { } 706169691Skan 707169691Skan typedef void* _Hash_code_type; 708169691Skan 709169691Skan _Hash_code_type 710169691Skan _M_hash_code(const _Key& __key) const 711169691Skan { return 0; } 712169691Skan 713169691Skan std::size_t 714169691Skan _M_bucket_index(const _Key& __k, _Hash_code_type, 715169691Skan std::size_t __n) const 716169691Skan { return _M_ranged_hash(__k, __n); } 717169691Skan 718169691Skan std::size_t 719169691Skan _M_bucket_index(const _Hash_node<_Value, false>* __p, 720169691Skan std::size_t __n) const 721169691Skan { return _M_ranged_hash(_M_extract(__p->_M_v), __n); } 722169691Skan 723169691Skan bool 724169691Skan _M_compare(const _Key& __k, _Hash_code_type, 725169691Skan _Hash_node<_Value, false>* __n) const 726169691Skan { return _M_eq(__k, _M_extract(__n->_M_v)); } 727169691Skan 728169691Skan void 729169691Skan _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 730169691Skan { } 731169691Skan 732169691Skan void 733169691Skan _M_copy_code(_Hash_node<_Value, false>*, 734169691Skan const _Hash_node<_Value, false>*) const 735169691Skan { } 736169691Skan 737169691Skan void 738169691Skan _M_swap(_Hash_code_base& __x) 739169691Skan { 740169691Skan std::swap(_M_extract, __x._M_extract); 741169691Skan std::swap(_M_eq, __x._M_eq); 742169691Skan std::swap(_M_ranged_hash, __x._M_ranged_hash); 743169691Skan } 744169691Skan 745169691Skan protected: 746169691Skan _ExtractKey _M_extract; 747169691Skan _Equal _M_eq; 748169691Skan _Hash _M_ranged_hash; 749169691Skan }; 750169691Skan 751169691Skan 752169691Skan // No specialization for ranged hash function while caching hash codes. 753169691Skan // That combination is meaningless, and trying to do it is an error. 754169691Skan 755169691Skan 756169691Skan // Specialization: ranged hash function, cache hash codes. This 757169691Skan // combination is meaningless, so we provide only a declaration 758169691Skan // and no definition. 759169691Skan template<typename _Key, typename _Value, 760169691Skan typename _ExtractKey, typename _Equal, 761169691Skan typename _H1, typename _H2, typename _Hash> 762169691Skan struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 763169691Skan _Hash, true>; 764169691Skan 765169691Skan // Specialization: hash function and range-hashing function, no 766169691Skan // caching of hash codes. H is provided but ignored. Provides 767169691Skan // typedef and accessor required by TR1. 768169691Skan template<typename _Key, typename _Value, 769169691Skan typename _ExtractKey, typename _Equal, 770169691Skan typename _H1, typename _H2> 771169691Skan struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 772169691Skan _Default_ranged_hash, false> 773169691Skan { 774169691Skan typedef _H1 hasher; 775169691Skan 776169691Skan hasher 777169691Skan hash_function() const 778169691Skan { return _M_h1; } 779169691Skan 780169691Skan protected: 781169691Skan _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 782169691Skan const _H1& __h1, const _H2& __h2, 783169691Skan const _Default_ranged_hash&) 784169691Skan : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } 785169691Skan 786169691Skan typedef std::size_t _Hash_code_type; 787169691Skan 788169691Skan _Hash_code_type 789169691Skan _M_hash_code(const _Key& __k) const 790169691Skan { return _M_h1(__k); } 791169691Skan 792169691Skan std::size_t 793169691Skan _M_bucket_index(const _Key&, _Hash_code_type __c, 794169691Skan std::size_t __n) const 795169691Skan { return _M_h2(__c, __n); } 796169691Skan 797169691Skan std::size_t 798169691Skan _M_bucket_index(const _Hash_node<_Value, false>* __p, 799169691Skan std::size_t __n) const 800169691Skan { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); } 801169691Skan 802169691Skan bool 803169691Skan _M_compare(const _Key& __k, _Hash_code_type, 804169691Skan _Hash_node<_Value, false>* __n) const 805169691Skan { return _M_eq(__k, _M_extract(__n->_M_v)); } 806169691Skan 807169691Skan void 808169691Skan _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 809169691Skan { } 810169691Skan 811169691Skan void 812169691Skan _M_copy_code(_Hash_node<_Value, false>*, 813169691Skan const _Hash_node<_Value, false>*) const 814169691Skan { } 815169691Skan 816169691Skan void 817169691Skan _M_swap(_Hash_code_base& __x) 818169691Skan { 819169691Skan std::swap(_M_extract, __x._M_extract); 820169691Skan std::swap(_M_eq, __x._M_eq); 821169691Skan std::swap(_M_h1, __x._M_h1); 822169691Skan std::swap(_M_h2, __x._M_h2); 823169691Skan } 824169691Skan 825169691Skan protected: 826169691Skan _ExtractKey _M_extract; 827169691Skan _Equal _M_eq; 828169691Skan _H1 _M_h1; 829169691Skan _H2 _M_h2; 830169691Skan }; 831169691Skan 832169691Skan // Specialization: hash function and range-hashing function, 833169691Skan // caching hash codes. H is provided but ignored. Provides 834169691Skan // typedef and accessor required by TR1. 835169691Skan template<typename _Key, typename _Value, 836169691Skan typename _ExtractKey, typename _Equal, 837169691Skan typename _H1, typename _H2> 838169691Skan struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 839169691Skan _Default_ranged_hash, true> 840169691Skan { 841169691Skan typedef _H1 hasher; 842169691Skan 843169691Skan hasher 844169691Skan hash_function() const 845169691Skan { return _M_h1; } 846169691Skan 847169691Skan protected: 848169691Skan _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 849169691Skan const _H1& __h1, const _H2& __h2, 850169691Skan const _Default_ranged_hash&) 851169691Skan : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } 852169691Skan 853169691Skan typedef std::size_t _Hash_code_type; 854169691Skan 855169691Skan _Hash_code_type 856169691Skan _M_hash_code(const _Key& __k) const 857169691Skan { return _M_h1(__k); } 858169691Skan 859169691Skan std::size_t 860169691Skan _M_bucket_index(const _Key&, _Hash_code_type __c, 861169691Skan std::size_t __n) const 862169691Skan { return _M_h2(__c, __n); } 863169691Skan 864169691Skan std::size_t 865169691Skan _M_bucket_index(const _Hash_node<_Value, true>* __p, 866169691Skan std::size_t __n) const 867169691Skan { return _M_h2(__p->_M_hash_code, __n); } 868169691Skan 869169691Skan bool 870169691Skan _M_compare(const _Key& __k, _Hash_code_type __c, 871169691Skan _Hash_node<_Value, true>* __n) const 872169691Skan { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); } 873169691Skan 874169691Skan void 875169691Skan _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const 876169691Skan { __n->_M_hash_code = __c; } 877169691Skan 878169691Skan void 879169691Skan _M_copy_code(_Hash_node<_Value, true>* __to, 880169691Skan const _Hash_node<_Value, true>* __from) const 881169691Skan { __to->_M_hash_code = __from->_M_hash_code; } 882169691Skan 883169691Skan void 884169691Skan _M_swap(_Hash_code_base& __x) 885169691Skan { 886169691Skan std::swap(_M_extract, __x._M_extract); 887169691Skan std::swap(_M_eq, __x._M_eq); 888169691Skan std::swap(_M_h1, __x._M_h1); 889169691Skan std::swap(_M_h2, __x._M_h2); 890169691Skan } 891169691Skan 892169691Skan protected: 893169691Skan _ExtractKey _M_extract; 894169691Skan _Equal _M_eq; 895169691Skan _H1 _M_h1; 896169691Skan _H2 _M_h2; 897169691Skan }; 898169691Skan} // namespace __detail 899169691Skan_GLIBCXX_END_NAMESPACE 900169691Skan} // namespace std::tr1 901169691Skan 902169691Skan#endif // _TR1_HASHTABLE_POLICY_H 903169691Skan 904