1169691Skan// Internal 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 31169691Skan * This is a TR1 C++ Library header. 32169691Skan */ 33169691Skan 34169691Skan// This header file defines std::tr1::hashtable, which is used to 35169691Skan// implement std::tr1::unordered_set, std::tr1::unordered_map, 36169691Skan// std::tr1::unordered_multiset, and std::tr1::unordered_multimap. 37169691Skan// hashtable has many template parameters, partly to accommodate 38169691Skan// the differences between those four classes and partly to 39169691Skan// accommodate policy choices that go beyond what TR1 calls for. 40169691Skan 41169691Skan// Class template hashtable attempts to encapsulate all reasonable 42169691Skan// variation among hash tables that use chaining. It does not handle 43169691Skan// open addressing. 44169691Skan 45169691Skan// References: 46169691Skan// M. Austern, "A Proposal to Add Hash Tables to the Standard 47169691Skan// Library (revision 4)," WG21 Document N1456=03-0039, 2003. 48169691Skan// D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching. 49169691Skan// A. Tavori and V. Dreizin, "Policy-Based Data Structures", 2004. 50169691Skan// http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html 51169691Skan 52169691Skan#ifndef _TR1_HASHTABLE 53169691Skan#define _TR1_HASHTABLE 1 54169691Skan 55169691Skan#include <utility> // For std::pair 56169691Skan#include <memory> 57169691Skan#include <iterator> 58169691Skan#include <cstddef> 59169691Skan#include <cstdlib> 60169691Skan#include <cmath> 61169691Skan#include <bits/functexcept.h> 62169691Skan#include <tr1/type_traits> // For true_type and false_type 63169691Skan#include <tr1/hashtable_policy.h> 64169691Skan 65169691Skannamespace std 66169691Skan{ 67169691Skan_GLIBCXX_BEGIN_NAMESPACE(tr1) 68169691Skan 69169691Skan // Class template _Hashtable, class definition. 70169691Skan 71169691Skan // Meaning of class template _Hashtable's template parameters 72169691Skan 73169691Skan // _Key and _Value: arbitrary CopyConstructible types. 74169691Skan 75169691Skan // _Allocator: an allocator type ([lib.allocator.requirements]) whose 76169691Skan // value type is Value. As a conforming extension, we allow for 77169691Skan // value type != Value. 78169691Skan 79169691Skan // _ExtractKey: function object that takes a object of type Value 80169691Skan // and returns a value of type _Key. 81169691Skan 82169691Skan // _Equal: function object that takes two objects of type k and returns 83169691Skan // a bool-like value that is true if the two objects are considered equal. 84169691Skan 85169691Skan // _H1: the hash function. A unary function object with argument type 86169691Skan // Key and result type size_t. Return values should be distributed 87169691Skan // over the entire range [0, numeric_limits<size_t>:::max()]. 88169691Skan 89169691Skan // _H2: the range-hashing function (in the terminology of Tavori and 90169691Skan // Dreizin). A binary function object whose argument types and result 91169691Skan // type are all size_t. Given arguments r and N, the return value is 92169691Skan // in the range [0, N). 93169691Skan 94169691Skan // _Hash: the ranged hash function (Tavori and Dreizin). A binary function 95169691Skan // whose argument types are _Key and size_t and whose result type is 96169691Skan // size_t. Given arguments k and N, the return value is in the range 97169691Skan // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other 98169691Skan // than the default, _H1 and _H2 are ignored. 99169691Skan 100169691Skan // _RehashPolicy: Policy class with three members, all of which govern 101169691Skan // the bucket count. _M_next_bkt(n) returns a bucket count no smaller 102169691Skan // than n. _M_bkt_for_elements(n) returns a bucket count appropriate 103169691Skan // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) 104169691Skan // determines whether, if the current bucket count is n_bkt and the 105169691Skan // current element count is n_elt, we need to increase the bucket 106169691Skan // count. If so, returns make_pair(true, n), where n is the new 107169691Skan // bucket count. If not, returns make_pair(false, <anything>). 108169691Skan 109169691Skan // ??? Right now it is hard-wired that the number of buckets never 110169691Skan // shrinks. Should we allow _RehashPolicy to change that? 111169691Skan 112169691Skan // __cache_hash_code: bool. true if we store the value of the hash 113169691Skan // function along with the value. This is a time-space tradeoff. 114169691Skan // Storing it may improve lookup speed by reducing the number of times 115169691Skan // we need to call the Equal function. 116169691Skan 117169691Skan // __constant_iterators: bool. true if iterator and const_iterator are 118169691Skan // both constant iterator types. This is true for unordered_set and 119169691Skan // unordered_multiset, false for unordered_map and unordered_multimap. 120169691Skan 121169691Skan // __unique_keys: bool. true if the return value of _Hashtable::count(k) 122169691Skan // is always at most one, false if it may be an arbitrary number. This 123169691Skan // true for unordered_set and unordered_map, false for unordered_multiset 124169691Skan // and unordered_multimap. 125169691Skan 126169691Skan template<typename _Key, typename _Value, typename _Allocator, 127169691Skan typename _ExtractKey, typename _Equal, 128169691Skan typename _H1, typename _H2, typename _Hash, 129169691Skan typename _RehashPolicy, 130169691Skan bool __cache_hash_code, 131169691Skan bool __constant_iterators, 132169691Skan bool __unique_keys> 133169691Skan class _Hashtable 134169691Skan : public __detail::_Rehash_base<_RehashPolicy, 135169691Skan _Hashtable<_Key, _Value, _Allocator, 136169691Skan _ExtractKey, 137169691Skan _Equal, _H1, _H2, _Hash, 138169691Skan _RehashPolicy, 139169691Skan __cache_hash_code, 140169691Skan __constant_iterators, 141169691Skan __unique_keys> >, 142169691Skan public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 143169691Skan _H1, _H2, _Hash, __cache_hash_code>, 144169691Skan public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, 145169691Skan _Hashtable<_Key, _Value, _Allocator, 146169691Skan _ExtractKey, 147169691Skan _Equal, _H1, _H2, _Hash, 148169691Skan _RehashPolicy, 149169691Skan __cache_hash_code, 150169691Skan __constant_iterators, 151169691Skan __unique_keys> > 152169691Skan { 153169691Skan public: 154169691Skan typedef _Allocator allocator_type; 155169691Skan typedef _Value value_type; 156169691Skan typedef _Key key_type; 157169691Skan typedef _Equal key_equal; 158169691Skan // mapped_type, if present, comes from _Map_base. 159169691Skan // hasher, if present, comes from _Hash_code_base. 160169691Skan typedef typename _Allocator::difference_type difference_type; 161169691Skan typedef typename _Allocator::size_type size_type; 162169691Skan typedef typename _Allocator::reference reference; 163169691Skan typedef typename _Allocator::const_reference const_reference; 164169691Skan 165169691Skan typedef __detail::_Node_iterator<value_type, __constant_iterators, 166169691Skan __cache_hash_code> 167169691Skan local_iterator; 168169691Skan typedef __detail::_Node_const_iterator<value_type, 169169691Skan __constant_iterators, 170169691Skan __cache_hash_code> 171169691Skan const_local_iterator; 172169691Skan 173169691Skan typedef __detail::_Hashtable_iterator<value_type, __constant_iterators, 174169691Skan __cache_hash_code> 175169691Skan iterator; 176169691Skan typedef __detail::_Hashtable_const_iterator<value_type, 177169691Skan __constant_iterators, 178169691Skan __cache_hash_code> 179169691Skan const_iterator; 180169691Skan 181169691Skan template<typename _Key2, typename _Pair, typename _Hashtable> 182169691Skan friend struct __detail::_Map_base; 183169691Skan 184169691Skan private: 185169691Skan typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; 186169691Skan typedef typename _Allocator::template rebind<_Node>::other 187169691Skan _Node_allocator_type; 188169691Skan typedef typename _Allocator::template rebind<_Node*>::other 189169691Skan _Bucket_allocator_type; 190169691Skan 191169691Skan typedef typename _Allocator::template rebind<_Value>::other 192169691Skan _Value_allocator_type; 193169691Skan 194169691Skan _Node_allocator_type _M_node_allocator; 195169691Skan _Node** _M_buckets; 196169691Skan size_type _M_bucket_count; 197169691Skan size_type _M_element_count; 198169691Skan _RehashPolicy _M_rehash_policy; 199169691Skan 200169691Skan _Node* 201169691Skan _M_allocate_node(const value_type& __v); 202169691Skan 203169691Skan void 204169691Skan _M_deallocate_node(_Node* __n); 205169691Skan 206169691Skan void 207169691Skan _M_deallocate_nodes(_Node**, size_type); 208169691Skan 209169691Skan _Node** 210169691Skan _M_allocate_buckets(size_type __n); 211169691Skan 212169691Skan void 213169691Skan _M_deallocate_buckets(_Node**, size_type __n); 214169691Skan 215169691Skan public: 216169691Skan // Constructor, destructor, assignment, swap 217169691Skan _Hashtable(size_type __bucket_hint, 218169691Skan const _H1&, const _H2&, const _Hash&, 219169691Skan const _Equal&, const _ExtractKey&, 220169691Skan const allocator_type&); 221169691Skan 222169691Skan template<typename _InputIterator> 223169691Skan _Hashtable(_InputIterator __first, _InputIterator __last, 224169691Skan size_type __bucket_hint, 225169691Skan const _H1&, const _H2&, const _Hash&, 226169691Skan const _Equal&, const _ExtractKey&, 227169691Skan const allocator_type&); 228169691Skan 229169691Skan _Hashtable(const _Hashtable&); 230169691Skan 231169691Skan _Hashtable& 232169691Skan operator=(const _Hashtable&); 233169691Skan 234169691Skan ~_Hashtable(); 235169691Skan 236169691Skan void swap(_Hashtable&); 237169691Skan 238169691Skan // Basic container operations 239169691Skan iterator 240169691Skan begin() 241169691Skan { 242169691Skan iterator __i(_M_buckets); 243169691Skan if (!__i._M_cur_node) 244169691Skan __i._M_incr_bucket(); 245169691Skan return __i; 246169691Skan } 247169691Skan 248169691Skan const_iterator 249169691Skan begin() const 250169691Skan { 251169691Skan const_iterator __i(_M_buckets); 252169691Skan if (!__i._M_cur_node) 253169691Skan __i._M_incr_bucket(); 254169691Skan return __i; 255169691Skan } 256169691Skan 257169691Skan iterator 258169691Skan end() 259169691Skan { return iterator(_M_buckets + _M_bucket_count); } 260169691Skan 261169691Skan const_iterator 262169691Skan end() const 263169691Skan { return const_iterator(_M_buckets + _M_bucket_count); } 264169691Skan 265169691Skan size_type 266169691Skan size() const 267169691Skan { return _M_element_count; } 268169691Skan 269169691Skan bool 270169691Skan empty() const 271169691Skan { return size() == 0; } 272169691Skan 273169691Skan allocator_type 274169691Skan get_allocator() const 275169691Skan { return allocator_type(_M_node_allocator); } 276169691Skan 277169691Skan _Value_allocator_type 278169691Skan _M_get_Value_allocator() const 279169691Skan { return _Value_allocator_type(_M_node_allocator); } 280169691Skan 281169691Skan size_type 282169691Skan max_size() const 283169691Skan { return _M_get_Value_allocator().max_size(); } 284169691Skan 285169691Skan // Observers 286169691Skan key_equal 287169691Skan key_eq() const 288169691Skan { return this->_M_eq; } 289169691Skan 290169691Skan // hash_function, if present, comes from _Hash_code_base. 291169691Skan 292169691Skan // Bucket operations 293169691Skan size_type 294169691Skan bucket_count() const 295169691Skan { return _M_bucket_count; } 296169691Skan 297169691Skan size_type 298169691Skan max_bucket_count() const 299169691Skan { return max_size(); } 300169691Skan 301169691Skan size_type 302169691Skan bucket_size(size_type __n) const 303169691Skan { return std::distance(begin(__n), end(__n)); } 304169691Skan 305169691Skan size_type 306169691Skan bucket(const key_type& __k) const 307169691Skan { 308169691Skan return this->_M_bucket_index(__k, this->_M_hash_code(__k), 309169691Skan bucket_count()); 310169691Skan } 311169691Skan 312169691Skan local_iterator 313169691Skan begin(size_type __n) 314169691Skan { return local_iterator(_M_buckets[__n]); } 315169691Skan 316169691Skan local_iterator 317169691Skan end(size_type) 318169691Skan { return local_iterator(0); } 319169691Skan 320169691Skan const_local_iterator 321169691Skan begin(size_type __n) const 322169691Skan { return const_local_iterator(_M_buckets[__n]); } 323169691Skan 324169691Skan const_local_iterator 325169691Skan end(size_type) const 326169691Skan { return const_local_iterator(0); } 327169691Skan 328169691Skan float 329169691Skan load_factor() const 330169691Skan { 331169691Skan return static_cast<float>(size()) / static_cast<float>(bucket_count()); 332169691Skan } 333169691Skan 334169691Skan // max_load_factor, if present, comes from _Rehash_base. 335169691Skan 336169691Skan // Generalization of max_load_factor. Extension, not found in TR1. Only 337169691Skan // useful if _RehashPolicy is something other than the default. 338169691Skan const _RehashPolicy& 339169691Skan __rehash_policy() const 340169691Skan { return _M_rehash_policy; } 341169691Skan 342169691Skan void 343169691Skan __rehash_policy(const _RehashPolicy&); 344169691Skan 345169691Skan // Lookup. 346169691Skan iterator 347169691Skan find(const key_type& __k); 348169691Skan 349169691Skan const_iterator 350169691Skan find(const key_type& __k) const; 351169691Skan 352169691Skan size_type 353169691Skan count(const key_type& __k) const; 354169691Skan 355169691Skan std::pair<iterator, iterator> 356169691Skan equal_range(const key_type& __k); 357169691Skan 358169691Skan std::pair<const_iterator, const_iterator> 359169691Skan equal_range(const key_type& __k) const; 360169691Skan 361169691Skan private: // Find, insert and erase helper functions 362169691Skan // ??? This dispatching is a workaround for the fact that we don't 363169691Skan // have partial specialization of member templates; it would be 364169691Skan // better to just specialize insert on __unique_keys. There may be a 365169691Skan // cleaner workaround. 366169691Skan typedef typename __gnu_cxx::__conditional_type<__unique_keys, 367169691Skan std::pair<iterator, bool>, iterator>::__type 368169691Skan _Insert_Return_Type; 369169691Skan 370169691Skan typedef typename __gnu_cxx::__conditional_type<__unique_keys, 371169691Skan std::_Select1st<_Insert_Return_Type>, 372169691Skan std::_Identity<_Insert_Return_Type> 373169691Skan >::__type 374169691Skan _Insert_Conv_Type; 375169691Skan 376169691Skan _Node* 377169691Skan _M_find_node(_Node*, const key_type&, 378169691Skan typename _Hashtable::_Hash_code_type) const; 379169691Skan 380169691Skan iterator 381169691Skan _M_insert_bucket(const value_type&, size_type, 382169691Skan typename _Hashtable::_Hash_code_type); 383169691Skan 384169691Skan std::pair<iterator, bool> 385169691Skan _M_insert(const value_type&, std::tr1::true_type); 386169691Skan 387169691Skan iterator 388169691Skan _M_insert(const value_type&, std::tr1::false_type); 389169691Skan 390169691Skan void 391169691Skan _M_erase_node(_Node*, _Node**); 392169691Skan 393169691Skan public: 394169691Skan // Insert and erase 395169691Skan _Insert_Return_Type 396169691Skan insert(const value_type& __v) 397169691Skan { return _M_insert(__v, std::tr1::integral_constant<bool, 398169691Skan __unique_keys>()); } 399169691Skan 400169691Skan iterator 401169691Skan insert(iterator, const value_type& __v) 402169691Skan { return iterator(_Insert_Conv_Type()(this->insert(__v))); } 403169691Skan 404169691Skan const_iterator 405169691Skan insert(const_iterator, const value_type& __v) 406169691Skan { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); } 407169691Skan 408169691Skan template<typename _InputIterator> 409169691Skan void 410169691Skan insert(_InputIterator __first, _InputIterator __last); 411169691Skan 412169691Skan iterator 413169691Skan erase(iterator); 414169691Skan 415169691Skan const_iterator 416169691Skan erase(const_iterator); 417169691Skan 418169691Skan size_type 419169691Skan erase(const key_type&); 420169691Skan 421169691Skan iterator 422169691Skan erase(iterator, iterator); 423169691Skan 424169691Skan const_iterator 425169691Skan erase(const_iterator, const_iterator); 426169691Skan 427169691Skan void 428169691Skan clear(); 429169691Skan 430169691Skan // Set number of buckets to be appropriate for container of n element. 431169691Skan void rehash(size_type __n); 432169691Skan 433169691Skan private: 434169691Skan // Unconditionally change size of bucket array to n. 435169691Skan void _M_rehash(size_type __n); 436169691Skan }; 437169691Skan 438169691Skan 439169691Skan // Definitions of class template _Hashtable's out-of-line member functions. 440169691Skan template<typename _Key, typename _Value, 441169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 442169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 443169691Skan bool __chc, bool __cit, bool __uk> 444169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 445169691Skan _H1, _H2, _Hash, _RehashPolicy, 446169691Skan __chc, __cit, __uk>::_Node* 447169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 448169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 449169691Skan _M_allocate_node(const value_type& __v) 450169691Skan { 451169691Skan _Node* __n = _M_node_allocator.allocate(1); 452169691Skan try 453169691Skan { 454169691Skan _M_get_Value_allocator().construct(&__n->_M_v, __v); 455169691Skan __n->_M_next = 0; 456169691Skan return __n; 457169691Skan } 458169691Skan catch(...) 459169691Skan { 460169691Skan _M_node_allocator.deallocate(__n, 1); 461169691Skan __throw_exception_again; 462169691Skan } 463169691Skan } 464169691Skan 465169691Skan template<typename _Key, typename _Value, 466169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 467169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 468169691Skan bool __chc, bool __cit, bool __uk> 469169691Skan void 470169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 471169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 472169691Skan _M_deallocate_node(_Node* __n) 473169691Skan { 474169691Skan _M_get_Value_allocator().destroy(&__n->_M_v); 475169691Skan _M_node_allocator.deallocate(__n, 1); 476169691Skan } 477169691Skan 478169691Skan template<typename _Key, typename _Value, 479169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 480169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 481169691Skan bool __chc, bool __cit, bool __uk> 482169691Skan void 483169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 484169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 485169691Skan _M_deallocate_nodes(_Node** __array, size_type __n) 486169691Skan { 487169691Skan for (size_type __i = 0; __i < __n; ++__i) 488169691Skan { 489169691Skan _Node* __p = __array[__i]; 490169691Skan while (__p) 491169691Skan { 492169691Skan _Node* __tmp = __p; 493169691Skan __p = __p->_M_next; 494169691Skan _M_deallocate_node(__tmp); 495169691Skan } 496169691Skan __array[__i] = 0; 497169691Skan } 498169691Skan } 499169691Skan 500169691Skan template<typename _Key, typename _Value, 501169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 502169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 503169691Skan bool __chc, bool __cit, bool __uk> 504169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 505169691Skan _H1, _H2, _Hash, _RehashPolicy, 506169691Skan __chc, __cit, __uk>::_Node** 507169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 508169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 509169691Skan _M_allocate_buckets(size_type __n) 510169691Skan { 511169691Skan _Bucket_allocator_type __alloc(_M_node_allocator); 512169691Skan 513169691Skan // We allocate one extra bucket to hold a sentinel, an arbitrary 514169691Skan // non-null pointer. Iterator increment relies on this. 515169691Skan _Node** __p = __alloc.allocate(__n + 1); 516169691Skan std::fill(__p, __p + __n, (_Node*) 0); 517169691Skan __p[__n] = reinterpret_cast<_Node*>(0x1000); 518169691Skan return __p; 519169691Skan } 520169691Skan 521169691Skan template<typename _Key, typename _Value, 522169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 523169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 524169691Skan bool __chc, bool __cit, bool __uk> 525169691Skan void 526169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 527169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 528169691Skan _M_deallocate_buckets(_Node** __p, size_type __n) 529169691Skan { 530169691Skan _Bucket_allocator_type __alloc(_M_node_allocator); 531169691Skan __alloc.deallocate(__p, __n + 1); 532169691Skan } 533169691Skan 534169691Skan template<typename _Key, typename _Value, 535169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 536169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 537169691Skan bool __chc, bool __cit, bool __uk> 538169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 539169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 540169691Skan _Hashtable(size_type __bucket_hint, 541169691Skan const _H1& __h1, const _H2& __h2, const _Hash& __h, 542169691Skan const _Equal& __eq, const _ExtractKey& __exk, 543169691Skan const allocator_type& __a) 544169691Skan : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 545169691Skan __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 546169691Skan _H1, _H2, _Hash, __chc>(__exk, __eq, 547169691Skan __h1, __h2, __h), 548169691Skan __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 549169691Skan _M_node_allocator(__a), 550169691Skan _M_bucket_count(0), 551169691Skan _M_element_count(0), 552169691Skan _M_rehash_policy() 553169691Skan { 554169691Skan _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 555169691Skan _M_buckets = _M_allocate_buckets(_M_bucket_count); 556169691Skan } 557169691Skan 558169691Skan template<typename _Key, typename _Value, 559169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 560169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 561169691Skan bool __chc, bool __cit, bool __uk> 562169691Skan template<typename _InputIterator> 563169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 564169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 565169691Skan _Hashtable(_InputIterator __f, _InputIterator __l, 566169691Skan size_type __bucket_hint, 567169691Skan const _H1& __h1, const _H2& __h2, const _Hash& __h, 568169691Skan const _Equal& __eq, const _ExtractKey& __exk, 569169691Skan const allocator_type& __a) 570169691Skan : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 571169691Skan __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 572169691Skan _H1, _H2, _Hash, __chc>(__exk, __eq, 573169691Skan __h1, __h2, __h), 574169691Skan __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 575169691Skan _M_node_allocator(__a), 576169691Skan _M_bucket_count(0), 577169691Skan _M_element_count(0), 578169691Skan _M_rehash_policy() 579169691Skan { 580169691Skan _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), 581169691Skan _M_rehash_policy. 582169691Skan _M_bkt_for_elements(__detail:: 583169691Skan __distance_fw(__f, 584169691Skan __l))); 585169691Skan _M_buckets = _M_allocate_buckets(_M_bucket_count); 586169691Skan try 587169691Skan { 588169691Skan for (; __f != __l; ++__f) 589169691Skan this->insert(*__f); 590169691Skan } 591169691Skan catch(...) 592169691Skan { 593169691Skan clear(); 594169691Skan _M_deallocate_buckets(_M_buckets, _M_bucket_count); 595169691Skan __throw_exception_again; 596169691Skan } 597169691Skan } 598169691Skan 599169691Skan template<typename _Key, typename _Value, 600169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 601169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 602169691Skan bool __chc, bool __cit, bool __uk> 603169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 604169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 605169691Skan _Hashtable(const _Hashtable& __ht) 606169691Skan : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 607169691Skan __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 608169691Skan _H1, _H2, _Hash, __chc>(__ht), 609169691Skan __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 610169691Skan _M_node_allocator(__ht._M_node_allocator), 611169691Skan _M_bucket_count(__ht._M_bucket_count), 612169691Skan _M_element_count(__ht._M_element_count), 613169691Skan _M_rehash_policy(__ht._M_rehash_policy) 614169691Skan { 615169691Skan _M_buckets = _M_allocate_buckets(_M_bucket_count); 616169691Skan try 617169691Skan { 618169691Skan for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i) 619169691Skan { 620169691Skan _Node* __n = __ht._M_buckets[__i]; 621169691Skan _Node** __tail = _M_buckets + __i; 622169691Skan while (__n) 623169691Skan { 624169691Skan *__tail = _M_allocate_node(__n->_M_v); 625169691Skan this->_M_copy_code(*__tail, __n); 626169691Skan __tail = &((*__tail)->_M_next); 627169691Skan __n = __n->_M_next; 628169691Skan } 629169691Skan } 630169691Skan } 631169691Skan catch(...) 632169691Skan { 633169691Skan clear(); 634169691Skan _M_deallocate_buckets(_M_buckets, _M_bucket_count); 635169691Skan __throw_exception_again; 636169691Skan } 637169691Skan } 638169691Skan 639169691Skan template<typename _Key, typename _Value, 640169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 641169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 642169691Skan bool __chc, bool __cit, bool __uk> 643169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 644169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>& 645169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 646169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 647169691Skan operator=(const _Hashtable& __ht) 648169691Skan { 649169691Skan _Hashtable __tmp(__ht); 650169691Skan this->swap(__tmp); 651169691Skan return *this; 652169691Skan } 653169691Skan 654169691Skan template<typename _Key, typename _Value, 655169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 656169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 657169691Skan bool __chc, bool __cit, bool __uk> 658169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 659169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 660169691Skan ~_Hashtable() 661169691Skan { 662169691Skan clear(); 663169691Skan _M_deallocate_buckets(_M_buckets, _M_bucket_count); 664169691Skan } 665169691Skan 666169691Skan template<typename _Key, typename _Value, 667169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 668169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 669169691Skan bool __chc, bool __cit, bool __uk> 670169691Skan void 671169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 672169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 673169691Skan swap(_Hashtable& __x) 674169691Skan { 675169691Skan // The only base class with member variables is hash_code_base. We 676169691Skan // define _Hash_code_base::_M_swap because different specializations 677169691Skan // have different members. 678169691Skan __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 679169691Skan _H1, _H2, _Hash, __chc>::_M_swap(__x); 680169691Skan 681169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 682169691Skan // 431. Swapping containers with unequal allocators. 683169691Skan std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, 684169691Skan __x._M_node_allocator); 685169691Skan 686169691Skan std::swap(_M_rehash_policy, __x._M_rehash_policy); 687169691Skan std::swap(_M_buckets, __x._M_buckets); 688169691Skan std::swap(_M_bucket_count, __x._M_bucket_count); 689169691Skan std::swap(_M_element_count, __x._M_element_count); 690169691Skan } 691169691Skan 692169691Skan template<typename _Key, typename _Value, 693169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 694169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 695169691Skan bool __chc, bool __cit, bool __uk> 696169691Skan void 697169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 698169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 699169691Skan __rehash_policy(const _RehashPolicy& __pol) 700169691Skan { 701169691Skan _M_rehash_policy = __pol; 702169691Skan size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); 703169691Skan if (__n_bkt > _M_bucket_count) 704169691Skan _M_rehash(__n_bkt); 705169691Skan } 706169691Skan 707169691Skan template<typename _Key, typename _Value, 708169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 709169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 710169691Skan bool __chc, bool __cit, bool __uk> 711169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 712169691Skan _H1, _H2, _Hash, _RehashPolicy, 713169691Skan __chc, __cit, __uk>::iterator 714169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 715169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 716169691Skan find(const key_type& __k) 717169691Skan { 718169691Skan typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 719169691Skan std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 720169691Skan _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 721169691Skan return __p ? iterator(__p, _M_buckets + __n) : this->end(); 722169691Skan } 723169691Skan 724169691Skan template<typename _Key, typename _Value, 725169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 726169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 727169691Skan bool __chc, bool __cit, bool __uk> 728169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 729169691Skan _H1, _H2, _Hash, _RehashPolicy, 730169691Skan __chc, __cit, __uk>::const_iterator 731169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 732169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 733169691Skan find(const key_type& __k) const 734169691Skan { 735169691Skan typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 736169691Skan std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 737169691Skan _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 738169691Skan return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); 739169691Skan } 740169691Skan 741169691Skan template<typename _Key, typename _Value, 742169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 743169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 744169691Skan bool __chc, bool __cit, bool __uk> 745169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 746169691Skan _H1, _H2, _Hash, _RehashPolicy, 747169691Skan __chc, __cit, __uk>::size_type 748169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 749169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 750169691Skan count(const key_type& __k) const 751169691Skan { 752169691Skan typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 753169691Skan std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 754169691Skan std::size_t __result = 0; 755169691Skan for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next) 756169691Skan if (this->_M_compare(__k, __code, __p)) 757169691Skan ++__result; 758169691Skan return __result; 759169691Skan } 760169691Skan 761169691Skan template<typename _Key, typename _Value, 762169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 763169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 764169691Skan bool __chc, bool __cit, bool __uk> 765169691Skan std::pair<typename _Hashtable<_Key, _Value, _Allocator, 766169691Skan _ExtractKey, _Equal, _H1, 767169691Skan _H2, _Hash, _RehashPolicy, 768169691Skan __chc, __cit, __uk>::iterator, 769169691Skan typename _Hashtable<_Key, _Value, _Allocator, 770169691Skan _ExtractKey, _Equal, _H1, 771169691Skan _H2, _Hash, _RehashPolicy, 772169691Skan __chc, __cit, __uk>::iterator> 773169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 774169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 775169691Skan equal_range(const key_type& __k) 776169691Skan { 777169691Skan typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 778169691Skan std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 779169691Skan _Node** __head = _M_buckets + __n; 780169691Skan _Node* __p = _M_find_node(*__head, __k, __code); 781169691Skan 782169691Skan if (__p) 783169691Skan { 784169691Skan _Node* __p1 = __p->_M_next; 785169691Skan for (; __p1; __p1 = __p1->_M_next) 786169691Skan if (!this->_M_compare(__k, __code, __p1)) 787169691Skan break; 788169691Skan 789169691Skan iterator __first(__p, __head); 790169691Skan iterator __last(__p1, __head); 791169691Skan if (!__p1) 792169691Skan __last._M_incr_bucket(); 793169691Skan return std::make_pair(__first, __last); 794169691Skan } 795169691Skan else 796169691Skan return std::make_pair(this->end(), this->end()); 797169691Skan } 798169691Skan 799169691Skan template<typename _Key, typename _Value, 800169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 801169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 802169691Skan bool __chc, bool __cit, bool __uk> 803169691Skan std::pair<typename _Hashtable<_Key, _Value, _Allocator, 804169691Skan _ExtractKey, _Equal, _H1, 805169691Skan _H2, _Hash, _RehashPolicy, 806169691Skan __chc, __cit, __uk>::const_iterator, 807169691Skan typename _Hashtable<_Key, _Value, _Allocator, 808169691Skan _ExtractKey, _Equal, _H1, 809169691Skan _H2, _Hash, _RehashPolicy, 810169691Skan __chc, __cit, __uk>::const_iterator> 811169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 812169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 813169691Skan equal_range(const key_type& __k) const 814169691Skan { 815169691Skan typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 816169691Skan std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 817169691Skan _Node** __head = _M_buckets + __n; 818169691Skan _Node* __p = _M_find_node(*__head, __k, __code); 819169691Skan 820169691Skan if (__p) 821169691Skan { 822169691Skan _Node* __p1 = __p->_M_next; 823169691Skan for (; __p1; __p1 = __p1->_M_next) 824169691Skan if (!this->_M_compare(__k, __code, __p1)) 825169691Skan break; 826169691Skan 827169691Skan const_iterator __first(__p, __head); 828169691Skan const_iterator __last(__p1, __head); 829169691Skan if (!__p1) 830169691Skan __last._M_incr_bucket(); 831169691Skan return std::make_pair(__first, __last); 832169691Skan } 833169691Skan else 834169691Skan return std::make_pair(this->end(), this->end()); 835169691Skan } 836169691Skan 837169691Skan // Find the node whose key compares equal to k, beginning the search 838169691Skan // at p (usually the head of a bucket). Return nil if no node is found. 839169691Skan template<typename _Key, typename _Value, 840169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 841169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 842169691Skan bool __chc, bool __cit, bool __uk> 843169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 844169691Skan _Equal, _H1, _H2, _Hash, _RehashPolicy, 845169691Skan __chc, __cit, __uk>::_Node* 846169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 847169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 848169691Skan _M_find_node(_Node* __p, const key_type& __k, 849169691Skan typename _Hashtable::_Hash_code_type __code) const 850169691Skan { 851169691Skan for (; __p; __p = __p->_M_next) 852169691Skan if (this->_M_compare(__k, __code, __p)) 853169691Skan return __p; 854169691Skan return false; 855169691Skan } 856169691Skan 857169691Skan // Insert v in bucket n (assumes no element with its key already present). 858169691Skan template<typename _Key, typename _Value, 859169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 860169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 861169691Skan bool __chc, bool __cit, bool __uk> 862169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 863169691Skan _H1, _H2, _Hash, _RehashPolicy, 864169691Skan __chc, __cit, __uk>::iterator 865169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 866169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 867169691Skan _M_insert_bucket(const value_type& __v, size_type __n, 868169691Skan typename _Hashtable::_Hash_code_type __code) 869169691Skan { 870169691Skan std::pair<bool, std::size_t> __do_rehash 871169691Skan = _M_rehash_policy._M_need_rehash(_M_bucket_count, 872169691Skan _M_element_count, 1); 873169691Skan 874169691Skan // Allocate the new node before doing the rehash so that we don't 875169691Skan // do a rehash if the allocation throws. 876169691Skan _Node* __new_node = _M_allocate_node(__v); 877169691Skan 878169691Skan try 879169691Skan { 880169691Skan if (__do_rehash.first) 881169691Skan { 882169691Skan const key_type& __k = this->_M_extract(__v); 883169691Skan __n = this->_M_bucket_index(__k, __code, __do_rehash.second); 884169691Skan _M_rehash(__do_rehash.second); 885169691Skan } 886169691Skan 887169691Skan __new_node->_M_next = _M_buckets[__n]; 888169691Skan this->_M_store_code(__new_node, __code); 889169691Skan _M_buckets[__n] = __new_node; 890169691Skan ++_M_element_count; 891169691Skan return iterator(__new_node, _M_buckets + __n); 892169691Skan } 893169691Skan catch(...) 894169691Skan { 895169691Skan _M_deallocate_node(__new_node); 896169691Skan __throw_exception_again; 897169691Skan } 898169691Skan } 899169691Skan 900169691Skan // Insert v if no element with its key is already present. 901169691Skan template<typename _Key, typename _Value, 902169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 903169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 904169691Skan bool __chc, bool __cit, bool __uk> 905169691Skan std::pair<typename _Hashtable<_Key, _Value, _Allocator, 906169691Skan _ExtractKey, _Equal, _H1, 907169691Skan _H2, _Hash, _RehashPolicy, 908169691Skan __chc, __cit, __uk>::iterator, bool> 909169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 910169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 911169691Skan _M_insert(const value_type& __v, std::tr1::true_type) 912169691Skan { 913169691Skan const key_type& __k = this->_M_extract(__v); 914169691Skan typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 915169691Skan size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 916169691Skan 917169691Skan if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code)) 918169691Skan return std::make_pair(iterator(__p, _M_buckets + __n), false); 919169691Skan return std::make_pair(_M_insert_bucket(__v, __n, __code), true); 920169691Skan } 921169691Skan 922169691Skan // Insert v unconditionally. 923169691Skan template<typename _Key, typename _Value, 924169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 925169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 926169691Skan bool __chc, bool __cit, bool __uk> 927169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 928169691Skan _H1, _H2, _Hash, _RehashPolicy, 929169691Skan __chc, __cit, __uk>::iterator 930169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 931169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 932169691Skan _M_insert(const value_type& __v, std::tr1::false_type) 933169691Skan { 934169691Skan std::pair<bool, std::size_t> __do_rehash 935169691Skan = _M_rehash_policy._M_need_rehash(_M_bucket_count, 936169691Skan _M_element_count, 1); 937169691Skan if (__do_rehash.first) 938169691Skan _M_rehash(__do_rehash.second); 939169691Skan 940169691Skan const key_type& __k = this->_M_extract(__v); 941169691Skan typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 942169691Skan size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 943169691Skan 944169691Skan // First find the node, avoid leaking new_node if compare throws. 945169691Skan _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code); 946169691Skan _Node* __new_node = _M_allocate_node(__v); 947169691Skan 948169691Skan if (__prev) 949169691Skan { 950169691Skan __new_node->_M_next = __prev->_M_next; 951169691Skan __prev->_M_next = __new_node; 952169691Skan } 953169691Skan else 954169691Skan { 955169691Skan __new_node->_M_next = _M_buckets[__n]; 956169691Skan _M_buckets[__n] = __new_node; 957169691Skan } 958169691Skan this->_M_store_code(__new_node, __code); 959169691Skan 960169691Skan ++_M_element_count; 961169691Skan return iterator(__new_node, _M_buckets + __n); 962169691Skan } 963169691Skan 964169691Skan // For erase(iterator) and erase(const_iterator). 965169691Skan template<typename _Key, typename _Value, 966169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 967169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 968169691Skan bool __chc, bool __cit, bool __uk> 969169691Skan void 970169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 971169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 972169691Skan _M_erase_node(_Node* __p, _Node** __b) 973169691Skan { 974169691Skan _Node* __cur = *__b; 975169691Skan if (__cur == __p) 976169691Skan *__b = __cur->_M_next; 977169691Skan else 978169691Skan { 979169691Skan _Node* __next = __cur->_M_next; 980169691Skan while (__next != __p) 981169691Skan { 982169691Skan __cur = __next; 983169691Skan __next = __cur->_M_next; 984169691Skan } 985169691Skan __cur->_M_next = __next->_M_next; 986169691Skan } 987169691Skan 988169691Skan _M_deallocate_node(__p); 989169691Skan --_M_element_count; 990169691Skan } 991169691Skan 992169691Skan template<typename _Key, typename _Value, 993169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 994169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 995169691Skan bool __chc, bool __cit, bool __uk> 996169691Skan template<typename _InputIterator> 997169691Skan void 998169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 999169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1000169691Skan insert(_InputIterator __first, _InputIterator __last) 1001169691Skan { 1002169691Skan size_type __n_elt = __detail::__distance_fw(__first, __last); 1003169691Skan std::pair<bool, std::size_t> __do_rehash 1004169691Skan = _M_rehash_policy._M_need_rehash(_M_bucket_count, 1005169691Skan _M_element_count, __n_elt); 1006169691Skan if (__do_rehash.first) 1007169691Skan _M_rehash(__do_rehash.second); 1008169691Skan 1009169691Skan for (; __first != __last; ++__first) 1010169691Skan this->insert(*__first); 1011169691Skan } 1012169691Skan 1013169691Skan template<typename _Key, typename _Value, 1014169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 1015169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1016169691Skan bool __chc, bool __cit, bool __uk> 1017169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1018169691Skan _H1, _H2, _Hash, _RehashPolicy, 1019169691Skan __chc, __cit, __uk>::iterator 1020169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1021169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1022169691Skan erase(iterator __it) 1023169691Skan { 1024169691Skan iterator __result = __it; 1025169691Skan ++__result; 1026169691Skan _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); 1027169691Skan return __result; 1028169691Skan } 1029169691Skan 1030169691Skan template<typename _Key, typename _Value, 1031169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 1032169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1033169691Skan bool __chc, bool __cit, bool __uk> 1034169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1035169691Skan _H1, _H2, _Hash, _RehashPolicy, 1036169691Skan __chc, __cit, __uk>::const_iterator 1037169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1038169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1039169691Skan erase(const_iterator __it) 1040169691Skan { 1041169691Skan const_iterator __result = __it; 1042169691Skan ++__result; 1043169691Skan _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); 1044169691Skan return __result; 1045169691Skan } 1046169691Skan 1047169691Skan template<typename _Key, typename _Value, 1048169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 1049169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1050169691Skan bool __chc, bool __cit, bool __uk> 1051169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1052169691Skan _H1, _H2, _Hash, _RehashPolicy, 1053169691Skan __chc, __cit, __uk>::size_type 1054169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1055169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1056169691Skan erase(const key_type& __k) 1057169691Skan { 1058169691Skan typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 1059169691Skan std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 1060169691Skan size_type __result = 0; 1061169691Skan 1062169691Skan _Node** __slot = _M_buckets + __n; 1063169691Skan while (*__slot && !this->_M_compare(__k, __code, *__slot)) 1064169691Skan __slot = &((*__slot)->_M_next); 1065169691Skan 1066169691Skan while (*__slot && this->_M_compare(__k, __code, *__slot)) 1067169691Skan { 1068169691Skan _Node* __p = *__slot; 1069169691Skan *__slot = __p->_M_next; 1070169691Skan _M_deallocate_node(__p); 1071169691Skan --_M_element_count; 1072169691Skan ++__result; 1073169691Skan } 1074169691Skan 1075169691Skan return __result; 1076169691Skan } 1077169691Skan 1078169691Skan // ??? This could be optimized by taking advantage of the bucket 1079169691Skan // structure, but it's not clear that it's worth doing. It probably 1080169691Skan // wouldn't even be an optimization unless the load factor is large. 1081169691Skan template<typename _Key, typename _Value, 1082169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 1083169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1084169691Skan bool __chc, bool __cit, bool __uk> 1085169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1086169691Skan _H1, _H2, _Hash, _RehashPolicy, 1087169691Skan __chc, __cit, __uk>::iterator 1088169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1089169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1090169691Skan erase(iterator __first, iterator __last) 1091169691Skan { 1092169691Skan while (__first != __last) 1093169691Skan __first = this->erase(__first); 1094169691Skan return __last; 1095169691Skan } 1096169691Skan 1097169691Skan template<typename _Key, typename _Value, 1098169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 1099169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1100169691Skan bool __chc, bool __cit, bool __uk> 1101169691Skan typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1102169691Skan _H1, _H2, _Hash, _RehashPolicy, 1103169691Skan __chc, __cit, __uk>::const_iterator 1104169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1105169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1106169691Skan erase(const_iterator __first, const_iterator __last) 1107169691Skan { 1108169691Skan while (__first != __last) 1109169691Skan __first = this->erase(__first); 1110169691Skan return __last; 1111169691Skan } 1112169691Skan 1113169691Skan template<typename _Key, typename _Value, 1114169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 1115169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1116169691Skan bool __chc, bool __cit, bool __uk> 1117169691Skan void 1118169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1119169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1120169691Skan clear() 1121169691Skan { 1122169691Skan _M_deallocate_nodes(_M_buckets, _M_bucket_count); 1123169691Skan _M_element_count = 0; 1124169691Skan } 1125169691Skan 1126169691Skan template<typename _Key, typename _Value, 1127169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 1128169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1129169691Skan bool __chc, bool __cit, bool __uk> 1130169691Skan void 1131169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1132169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1133169691Skan rehash(size_type __n) 1134169691Skan { 1135169691Skan _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), 1136169691Skan _M_rehash_policy._M_bkt_for_elements(_M_element_count 1137169691Skan + 1))); 1138169691Skan } 1139169691Skan 1140169691Skan template<typename _Key, typename _Value, 1141169691Skan typename _Allocator, typename _ExtractKey, typename _Equal, 1142169691Skan typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1143169691Skan bool __chc, bool __cit, bool __uk> 1144169691Skan void 1145169691Skan _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1146169691Skan _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1147169691Skan _M_rehash(size_type __n) 1148169691Skan { 1149169691Skan _Node** __new_array = _M_allocate_buckets(__n); 1150169691Skan try 1151169691Skan { 1152169691Skan for (size_type __i = 0; __i < _M_bucket_count; ++__i) 1153169691Skan while (_Node* __p = _M_buckets[__i]) 1154169691Skan { 1155169691Skan std::size_t __new_index = this->_M_bucket_index(__p, __n); 1156169691Skan _M_buckets[__i] = __p->_M_next; 1157169691Skan __p->_M_next = __new_array[__new_index]; 1158169691Skan __new_array[__new_index] = __p; 1159169691Skan } 1160169691Skan _M_deallocate_buckets(_M_buckets, _M_bucket_count); 1161169691Skan _M_bucket_count = __n; 1162169691Skan _M_buckets = __new_array; 1163169691Skan } 1164169691Skan catch(...) 1165169691Skan { 1166169691Skan // A failure here means that a hash function threw an exception. 1167169691Skan // We can't restore the previous state without calling the hash 1168169691Skan // function again, so the only sensible recovery is to delete 1169169691Skan // everything. 1170169691Skan _M_deallocate_nodes(__new_array, __n); 1171169691Skan _M_deallocate_buckets(__new_array, __n); 1172169691Skan _M_deallocate_nodes(_M_buckets, _M_bucket_count); 1173169691Skan _M_element_count = 0; 1174169691Skan __throw_exception_again; 1175169691Skan } 1176169691Skan } 1177169691Skan 1178169691Skan_GLIBCXX_END_NAMESPACE 1179169691Skan} // namespace std::tr1 1180169691Skan 1181169691Skan#endif // _TR1_HASHTABLE 1182169691Skan 1183