1*404b540aSrobert // Hashtable implementation used by containers -*- C++ -*- 2*404b540aSrobert 3*404b540aSrobert // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4*404b540aSrobert // Free Software Foundation, Inc. 5*404b540aSrobert // 6*404b540aSrobert // This file is part of the GNU ISO C++ Library. This library is free 7*404b540aSrobert // software; you can redistribute it and/or modify it under the 8*404b540aSrobert // terms of the GNU General Public License as published by the 9*404b540aSrobert // Free Software Foundation; either version 2, or (at your option) 10*404b540aSrobert // any later version. 11*404b540aSrobert 12*404b540aSrobert // This library is distributed in the hope that it will be useful, 13*404b540aSrobert // but WITHOUT ANY WARRANTY; without even the implied warranty of 14*404b540aSrobert // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15*404b540aSrobert // GNU General Public License for more details. 16*404b540aSrobert 17*404b540aSrobert // You should have received a copy of the GNU General Public License along 18*404b540aSrobert // with this library; see the file COPYING. If not, write to the Free 19*404b540aSrobert // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20*404b540aSrobert // USA. 21*404b540aSrobert 22*404b540aSrobert // As a special exception, you may use this file as part of a free software 23*404b540aSrobert // library without restriction. Specifically, if other files instantiate 24*404b540aSrobert // templates or use macros or inline functions from this file, or you compile 25*404b540aSrobert // this file and link it with other files to produce an executable, this 26*404b540aSrobert // file does not by itself cause the resulting executable to be covered by 27*404b540aSrobert // the GNU General Public License. This exception does not however 28*404b540aSrobert // invalidate any other reasons why the executable file might be covered by 29*404b540aSrobert // the GNU General Public License. 30*404b540aSrobert 31*404b540aSrobert /* 32*404b540aSrobert * Copyright (c) 1996,1997 33*404b540aSrobert * Silicon Graphics Computer Systems, Inc. 34*404b540aSrobert * 35*404b540aSrobert * Permission to use, copy, modify, distribute and sell this software 36*404b540aSrobert * and its documentation for any purpose is hereby granted without fee, 37*404b540aSrobert * provided that the above copyright notice appear in all copies and 38*404b540aSrobert * that both that copyright notice and this permission notice appear 39*404b540aSrobert * in supporting documentation. Silicon Graphics makes no 40*404b540aSrobert * representations about the suitability of this software for any 41*404b540aSrobert * purpose. It is provided "as is" without express or implied warranty. 42*404b540aSrobert * 43*404b540aSrobert * 44*404b540aSrobert * Copyright (c) 1994 45*404b540aSrobert * Hewlett-Packard Company 46*404b540aSrobert * 47*404b540aSrobert * Permission to use, copy, modify, distribute and sell this software 48*404b540aSrobert * and its documentation for any purpose is hereby granted without fee, 49*404b540aSrobert * provided that the above copyright notice appear in all copies and 50*404b540aSrobert * that both that copyright notice and this permission notice appear 51*404b540aSrobert * in supporting documentation. Hewlett-Packard Company makes no 52*404b540aSrobert * representations about the suitability of this software for any 53*404b540aSrobert * purpose. It is provided "as is" without express or implied warranty. 54*404b540aSrobert * 55*404b540aSrobert */ 56*404b540aSrobert 57*404b540aSrobert /** @file ext/hashtable.h 58*404b540aSrobert * This file is a GNU extension to the Standard C++ Library (possibly 59*404b540aSrobert * containing extensions from the HP/SGI STL subset). 60*404b540aSrobert */ 61*404b540aSrobert 62*404b540aSrobert #ifndef _HASHTABLE_H 63*404b540aSrobert #define _HASHTABLE_H 1 64*404b540aSrobert 65*404b540aSrobert // Hashtable class, used to implement the hashed associative containers 66*404b540aSrobert // hash_set, hash_map, hash_multiset, and hash_multimap. 67*404b540aSrobert 68*404b540aSrobert #include <vector> 69*404b540aSrobert #include <iterator> 70*404b540aSrobert #include <bits/stl_algo.h> 71*404b540aSrobert #include <bits/stl_function.h> 72*404b540aSrobert #include <ext/hash_fun.h> 73*404b540aSrobert 74*404b540aSrobert _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 75*404b540aSrobert 76*404b540aSrobert using std::size_t; 77*404b540aSrobert using std::ptrdiff_t; 78*404b540aSrobert using std::forward_iterator_tag; 79*404b540aSrobert using std::input_iterator_tag; 80*404b540aSrobert using std::_Construct; 81*404b540aSrobert using std::_Destroy; 82*404b540aSrobert using std::distance; 83*404b540aSrobert using std::vector; 84*404b540aSrobert using std::pair; 85*404b540aSrobert using std::__iterator_category; 86*404b540aSrobert 87*404b540aSrobert template<class _Val> 88*404b540aSrobert struct _Hashtable_node 89*404b540aSrobert { 90*404b540aSrobert _Hashtable_node* _M_next; 91*404b540aSrobert _Val _M_val; 92*404b540aSrobert }; 93*404b540aSrobert 94*404b540aSrobert template<class _Val, class _Key, class _HashFcn, class _ExtractKey, 95*404b540aSrobert class _EqualKey, class _Alloc = std::allocator<_Val> > 96*404b540aSrobert class hashtable; 97*404b540aSrobert 98*404b540aSrobert template<class _Val, class _Key, class _HashFcn, 99*404b540aSrobert class _ExtractKey, class _EqualKey, class _Alloc> 100*404b540aSrobert struct _Hashtable_iterator; 101*404b540aSrobert 102*404b540aSrobert template<class _Val, class _Key, class _HashFcn, 103*404b540aSrobert class _ExtractKey, class _EqualKey, class _Alloc> 104*404b540aSrobert struct _Hashtable_const_iterator; 105*404b540aSrobert 106*404b540aSrobert template<class _Val, class _Key, class _HashFcn, 107*404b540aSrobert class _ExtractKey, class _EqualKey, class _Alloc> 108*404b540aSrobert struct _Hashtable_iterator 109*404b540aSrobert { 110*404b540aSrobert typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> 111*404b540aSrobert _Hashtable; 112*404b540aSrobert typedef _Hashtable_iterator<_Val, _Key, _HashFcn, 113*404b540aSrobert _ExtractKey, _EqualKey, _Alloc> 114*404b540aSrobert iterator; 115*404b540aSrobert typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 116*404b540aSrobert _ExtractKey, _EqualKey, _Alloc> 117*404b540aSrobert const_iterator; 118*404b540aSrobert typedef _Hashtable_node<_Val> _Node; 119*404b540aSrobert typedef forward_iterator_tag iterator_category; 120*404b540aSrobert typedef _Val value_type; 121*404b540aSrobert typedef ptrdiff_t difference_type; 122*404b540aSrobert typedef size_t size_type; 123*404b540aSrobert typedef _Val& reference; 124*404b540aSrobert typedef _Val* pointer; 125*404b540aSrobert 126*404b540aSrobert _Node* _M_cur; 127*404b540aSrobert _Hashtable* _M_ht; 128*404b540aSrobert _Hashtable_iterator_Hashtable_iterator129*404b540aSrobert _Hashtable_iterator(_Node* __n, _Hashtable* __tab) 130*404b540aSrobert : _M_cur(__n), _M_ht(__tab) { } 131*404b540aSrobert _Hashtable_iterator_Hashtable_iterator132*404b540aSrobert _Hashtable_iterator() { } 133*404b540aSrobert 134*404b540aSrobert reference 135*404b540aSrobert operator*() const 136*404b540aSrobert { return _M_cur->_M_val; } 137*404b540aSrobert 138*404b540aSrobert pointer 139*404b540aSrobert operator->() const 140*404b540aSrobert { return &(operator*()); } 141*404b540aSrobert 142*404b540aSrobert iterator& 143*404b540aSrobert operator++(); 144*404b540aSrobert 145*404b540aSrobert iterator 146*404b540aSrobert operator++(int); 147*404b540aSrobert 148*404b540aSrobert bool 149*404b540aSrobert operator==(const iterator& __it) const 150*404b540aSrobert { return _M_cur == __it._M_cur; } 151*404b540aSrobert 152*404b540aSrobert bool 153*404b540aSrobert operator!=(const iterator& __it) const 154*404b540aSrobert { return _M_cur != __it._M_cur; } 155*404b540aSrobert }; 156*404b540aSrobert 157*404b540aSrobert template<class _Val, class _Key, class _HashFcn, 158*404b540aSrobert class _ExtractKey, class _EqualKey, class _Alloc> 159*404b540aSrobert struct _Hashtable_const_iterator 160*404b540aSrobert { 161*404b540aSrobert typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> 162*404b540aSrobert _Hashtable; 163*404b540aSrobert typedef _Hashtable_iterator<_Val,_Key,_HashFcn, 164*404b540aSrobert _ExtractKey,_EqualKey,_Alloc> 165*404b540aSrobert iterator; 166*404b540aSrobert typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 167*404b540aSrobert _ExtractKey, _EqualKey, _Alloc> 168*404b540aSrobert const_iterator; 169*404b540aSrobert typedef _Hashtable_node<_Val> _Node; 170*404b540aSrobert 171*404b540aSrobert typedef forward_iterator_tag iterator_category; 172*404b540aSrobert typedef _Val value_type; 173*404b540aSrobert typedef ptrdiff_t difference_type; 174*404b540aSrobert typedef size_t size_type; 175*404b540aSrobert typedef const _Val& reference; 176*404b540aSrobert typedef const _Val* pointer; 177*404b540aSrobert 178*404b540aSrobert const _Node* _M_cur; 179*404b540aSrobert const _Hashtable* _M_ht; 180*404b540aSrobert _Hashtable_const_iterator_Hashtable_const_iterator181*404b540aSrobert _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab) 182*404b540aSrobert : _M_cur(__n), _M_ht(__tab) { } 183*404b540aSrobert _Hashtable_const_iterator_Hashtable_const_iterator184*404b540aSrobert _Hashtable_const_iterator() { } 185*404b540aSrobert _Hashtable_const_iterator_Hashtable_const_iterator186*404b540aSrobert _Hashtable_const_iterator(const iterator& __it) 187*404b540aSrobert : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { } 188*404b540aSrobert 189*404b540aSrobert reference 190*404b540aSrobert operator*() const 191*404b540aSrobert { return _M_cur->_M_val; } 192*404b540aSrobert 193*404b540aSrobert pointer 194*404b540aSrobert operator->() const 195*404b540aSrobert { return &(operator*()); } 196*404b540aSrobert 197*404b540aSrobert const_iterator& 198*404b540aSrobert operator++(); 199*404b540aSrobert 200*404b540aSrobert const_iterator 201*404b540aSrobert operator++(int); 202*404b540aSrobert 203*404b540aSrobert bool 204*404b540aSrobert operator==(const const_iterator& __it) const 205*404b540aSrobert { return _M_cur == __it._M_cur; } 206*404b540aSrobert 207*404b540aSrobert bool 208*404b540aSrobert operator!=(const const_iterator& __it) const 209*404b540aSrobert { return _M_cur != __it._M_cur; } 210*404b540aSrobert }; 211*404b540aSrobert 212*404b540aSrobert // Note: assumes long is at least 32 bits. 213*404b540aSrobert enum { _S_num_primes = 28 }; 214*404b540aSrobert 215*404b540aSrobert static const unsigned long __stl_prime_list[_S_num_primes] = 216*404b540aSrobert { 217*404b540aSrobert 53ul, 97ul, 193ul, 389ul, 769ul, 218*404b540aSrobert 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 219*404b540aSrobert 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 220*404b540aSrobert 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 221*404b540aSrobert 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 222*404b540aSrobert 1610612741ul, 3221225473ul, 4294967291ul 223*404b540aSrobert }; 224*404b540aSrobert 225*404b540aSrobert inline unsigned long __stl_next_prime(unsigned long __n)226*404b540aSrobert __stl_next_prime(unsigned long __n) 227*404b540aSrobert { 228*404b540aSrobert const unsigned long* __first = __stl_prime_list; 229*404b540aSrobert const unsigned long* __last = __stl_prime_list + (int)_S_num_primes; 230*404b540aSrobert const unsigned long* pos = std::lower_bound(__first, __last, __n); 231*404b540aSrobert return pos == __last ? *(__last - 1) : *pos; 232*404b540aSrobert } 233*404b540aSrobert 234*404b540aSrobert // Forward declaration of operator==. 235*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, 236*404b540aSrobert class _Eq, class _All> 237*404b540aSrobert class hashtable; 238*404b540aSrobert 239*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, 240*404b540aSrobert class _Eq, class _All> 241*404b540aSrobert bool 242*404b540aSrobert operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 243*404b540aSrobert const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2); 244*404b540aSrobert 245*404b540aSrobert // Hashtables handle allocators a bit differently than other 246*404b540aSrobert // containers do. If we're using standard-conforming allocators, then 247*404b540aSrobert // a hashtable unconditionally has a member variable to hold its 248*404b540aSrobert // allocator, even if it so happens that all instances of the 249*404b540aSrobert // allocator type are identical. This is because, for hashtables, 250*404b540aSrobert // this extra storage is negligible. Additionally, a base class 251*404b540aSrobert // wouldn't serve any other purposes; it wouldn't, for example, 252*404b540aSrobert // simplify the exception-handling code. 253*404b540aSrobert template<class _Val, class _Key, class _HashFcn, 254*404b540aSrobert class _ExtractKey, class _EqualKey, class _Alloc> 255*404b540aSrobert class hashtable 256*404b540aSrobert { 257*404b540aSrobert public: 258*404b540aSrobert typedef _Key key_type; 259*404b540aSrobert typedef _Val value_type; 260*404b540aSrobert typedef _HashFcn hasher; 261*404b540aSrobert typedef _EqualKey key_equal; 262*404b540aSrobert 263*404b540aSrobert typedef size_t size_type; 264*404b540aSrobert typedef ptrdiff_t difference_type; 265*404b540aSrobert typedef value_type* pointer; 266*404b540aSrobert typedef const value_type* const_pointer; 267*404b540aSrobert typedef value_type& reference; 268*404b540aSrobert typedef const value_type& const_reference; 269*404b540aSrobert 270*404b540aSrobert hasher hash_funct()271*404b540aSrobert hash_funct() const 272*404b540aSrobert { return _M_hash; } 273*404b540aSrobert 274*404b540aSrobert key_equal key_eq()275*404b540aSrobert key_eq() const 276*404b540aSrobert { return _M_equals; } 277*404b540aSrobert 278*404b540aSrobert private: 279*404b540aSrobert typedef _Hashtable_node<_Val> _Node; 280*404b540aSrobert 281*404b540aSrobert public: 282*404b540aSrobert typedef typename _Alloc::template rebind<value_type>::other allocator_type; 283*404b540aSrobert allocator_type get_allocator()284*404b540aSrobert get_allocator() const 285*404b540aSrobert { return _M_node_allocator; } 286*404b540aSrobert 287*404b540aSrobert private: 288*404b540aSrobert typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc; 289*404b540aSrobert typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc; 290*404b540aSrobert typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type; 291*404b540aSrobert 292*404b540aSrobert _Node_Alloc _M_node_allocator; 293*404b540aSrobert 294*404b540aSrobert _Node* _M_get_node()295*404b540aSrobert _M_get_node() 296*404b540aSrobert { return _M_node_allocator.allocate(1); } 297*404b540aSrobert 298*404b540aSrobert void _M_put_node(_Node * __p)299*404b540aSrobert _M_put_node(_Node* __p) 300*404b540aSrobert { _M_node_allocator.deallocate(__p, 1); } 301*404b540aSrobert 302*404b540aSrobert private: 303*404b540aSrobert hasher _M_hash; 304*404b540aSrobert key_equal _M_equals; 305*404b540aSrobert _ExtractKey _M_get_key; 306*404b540aSrobert _Vector_type _M_buckets; 307*404b540aSrobert size_type _M_num_elements; 308*404b540aSrobert 309*404b540aSrobert public: 310*404b540aSrobert typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, 311*404b540aSrobert _EqualKey, _Alloc> 312*404b540aSrobert iterator; 313*404b540aSrobert typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 314*404b540aSrobert _EqualKey, _Alloc> 315*404b540aSrobert const_iterator; 316*404b540aSrobert 317*404b540aSrobert friend struct 318*404b540aSrobert _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>; 319*404b540aSrobert 320*404b540aSrobert friend struct 321*404b540aSrobert _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 322*404b540aSrobert _EqualKey, _Alloc>; 323*404b540aSrobert 324*404b540aSrobert public: 325*404b540aSrobert hashtable(size_type __n, const _HashFcn& __hf, 326*404b540aSrobert const _EqualKey& __eql, const _ExtractKey& __ext, 327*404b540aSrobert const allocator_type& __a = allocator_type()) 328*404b540aSrobert : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 329*404b540aSrobert _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0) 330*404b540aSrobert { _M_initialize_buckets(__n); } 331*404b540aSrobert 332*404b540aSrobert hashtable(size_type __n, const _HashFcn& __hf, 333*404b540aSrobert const _EqualKey& __eql, 334*404b540aSrobert const allocator_type& __a = allocator_type()) 335*404b540aSrobert : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 336*404b540aSrobert _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0) 337*404b540aSrobert { _M_initialize_buckets(__n); } 338*404b540aSrobert 339*404b540aSrobert hashtable(const hashtable& __ht) 340*404b540aSrobert : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash), 341*404b540aSrobert _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key), 342*404b540aSrobert _M_buckets(__ht.get_allocator()), _M_num_elements(0) 343*404b540aSrobert { _M_copy_from(__ht); } 344*404b540aSrobert 345*404b540aSrobert hashtable& 346*404b540aSrobert operator= (const hashtable& __ht) 347*404b540aSrobert { 348*404b540aSrobert if (&__ht != this) 349*404b540aSrobert { 350*404b540aSrobert clear(); 351*404b540aSrobert _M_hash = __ht._M_hash; 352*404b540aSrobert _M_equals = __ht._M_equals; 353*404b540aSrobert _M_get_key = __ht._M_get_key; 354*404b540aSrobert _M_copy_from(__ht); 355*404b540aSrobert } 356*404b540aSrobert return *this; 357*404b540aSrobert } 358*404b540aSrobert 359*404b540aSrobert ~hashtable() 360*404b540aSrobert { clear(); } 361*404b540aSrobert 362*404b540aSrobert size_type 363*404b540aSrobert size() const 364*404b540aSrobert { return _M_num_elements; } 365*404b540aSrobert 366*404b540aSrobert size_type 367*404b540aSrobert max_size() const 368*404b540aSrobert { return size_type(-1); } 369*404b540aSrobert 370*404b540aSrobert bool 371*404b540aSrobert empty() const 372*404b540aSrobert { return size() == 0; } 373*404b540aSrobert 374*404b540aSrobert void 375*404b540aSrobert swap(hashtable& __ht) 376*404b540aSrobert { 377*404b540aSrobert std::swap(_M_hash, __ht._M_hash); 378*404b540aSrobert std::swap(_M_equals, __ht._M_equals); 379*404b540aSrobert std::swap(_M_get_key, __ht._M_get_key); 380*404b540aSrobert _M_buckets.swap(__ht._M_buckets); 381*404b540aSrobert std::swap(_M_num_elements, __ht._M_num_elements); 382*404b540aSrobert } 383*404b540aSrobert 384*404b540aSrobert iterator 385*404b540aSrobert begin() 386*404b540aSrobert { 387*404b540aSrobert for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 388*404b540aSrobert if (_M_buckets[__n]) 389*404b540aSrobert return iterator(_M_buckets[__n], this); 390*404b540aSrobert return end(); 391*404b540aSrobert } 392*404b540aSrobert 393*404b540aSrobert iterator 394*404b540aSrobert end() 395*404b540aSrobert { return iterator(0, this); } 396*404b540aSrobert 397*404b540aSrobert const_iterator 398*404b540aSrobert begin() const 399*404b540aSrobert { 400*404b540aSrobert for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 401*404b540aSrobert if (_M_buckets[__n]) 402*404b540aSrobert return const_iterator(_M_buckets[__n], this); 403*404b540aSrobert return end(); 404*404b540aSrobert } 405*404b540aSrobert 406*404b540aSrobert const_iterator 407*404b540aSrobert end() const 408*404b540aSrobert { return const_iterator(0, this); } 409*404b540aSrobert 410*404b540aSrobert template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, 411*404b540aSrobert class _Al> 412*404b540aSrobert friend bool 413*404b540aSrobert operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, 414*404b540aSrobert const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); 415*404b540aSrobert 416*404b540aSrobert public: 417*404b540aSrobert size_type 418*404b540aSrobert bucket_count() const 419*404b540aSrobert { return _M_buckets.size(); } 420*404b540aSrobert 421*404b540aSrobert size_type 422*404b540aSrobert max_bucket_count() const 423*404b540aSrobert { return __stl_prime_list[(int)_S_num_primes - 1]; } 424*404b540aSrobert 425*404b540aSrobert size_type 426*404b540aSrobert elems_in_bucket(size_type __bucket) const 427*404b540aSrobert { 428*404b540aSrobert size_type __result = 0; 429*404b540aSrobert for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next) 430*404b540aSrobert __result += 1; 431*404b540aSrobert return __result; 432*404b540aSrobert } 433*404b540aSrobert 434*404b540aSrobert pair<iterator, bool> 435*404b540aSrobert insert_unique(const value_type& __obj) 436*404b540aSrobert { 437*404b540aSrobert resize(_M_num_elements + 1); 438*404b540aSrobert return insert_unique_noresize(__obj); 439*404b540aSrobert } 440*404b540aSrobert 441*404b540aSrobert iterator 442*404b540aSrobert insert_equal(const value_type& __obj) 443*404b540aSrobert { 444*404b540aSrobert resize(_M_num_elements + 1); 445*404b540aSrobert return insert_equal_noresize(__obj); 446*404b540aSrobert } 447*404b540aSrobert 448*404b540aSrobert pair<iterator, bool> 449*404b540aSrobert insert_unique_noresize(const value_type& __obj); 450*404b540aSrobert 451*404b540aSrobert iterator 452*404b540aSrobert insert_equal_noresize(const value_type& __obj); 453*404b540aSrobert 454*404b540aSrobert template<class _InputIterator> 455*404b540aSrobert void 456*404b540aSrobert insert_unique(_InputIterator __f, _InputIterator __l) 457*404b540aSrobert { insert_unique(__f, __l, __iterator_category(__f)); } 458*404b540aSrobert 459*404b540aSrobert template<class _InputIterator> 460*404b540aSrobert void 461*404b540aSrobert insert_equal(_InputIterator __f, _InputIterator __l) 462*404b540aSrobert { insert_equal(__f, __l, __iterator_category(__f)); } 463*404b540aSrobert 464*404b540aSrobert template<class _InputIterator> 465*404b540aSrobert void 466*404b540aSrobert insert_unique(_InputIterator __f, _InputIterator __l, 467*404b540aSrobert input_iterator_tag) 468*404b540aSrobert { 469*404b540aSrobert for ( ; __f != __l; ++__f) 470*404b540aSrobert insert_unique(*__f); 471*404b540aSrobert } 472*404b540aSrobert 473*404b540aSrobert template<class _InputIterator> 474*404b540aSrobert void 475*404b540aSrobert insert_equal(_InputIterator __f, _InputIterator __l, 476*404b540aSrobert input_iterator_tag) 477*404b540aSrobert { 478*404b540aSrobert for ( ; __f != __l; ++__f) 479*404b540aSrobert insert_equal(*__f); 480*404b540aSrobert } 481*404b540aSrobert 482*404b540aSrobert template<class _ForwardIterator> 483*404b540aSrobert void 484*404b540aSrobert insert_unique(_ForwardIterator __f, _ForwardIterator __l, 485*404b540aSrobert forward_iterator_tag) 486*404b540aSrobert { 487*404b540aSrobert size_type __n = distance(__f, __l); 488*404b540aSrobert resize(_M_num_elements + __n); 489*404b540aSrobert for ( ; __n > 0; --__n, ++__f) 490*404b540aSrobert insert_unique_noresize(*__f); 491*404b540aSrobert } 492*404b540aSrobert 493*404b540aSrobert template<class _ForwardIterator> 494*404b540aSrobert void 495*404b540aSrobert insert_equal(_ForwardIterator __f, _ForwardIterator __l, 496*404b540aSrobert forward_iterator_tag) 497*404b540aSrobert { 498*404b540aSrobert size_type __n = distance(__f, __l); 499*404b540aSrobert resize(_M_num_elements + __n); 500*404b540aSrobert for ( ; __n > 0; --__n, ++__f) 501*404b540aSrobert insert_equal_noresize(*__f); 502*404b540aSrobert } 503*404b540aSrobert 504*404b540aSrobert reference 505*404b540aSrobert find_or_insert(const value_type& __obj); 506*404b540aSrobert 507*404b540aSrobert iterator 508*404b540aSrobert find(const key_type& __key) 509*404b540aSrobert { 510*404b540aSrobert size_type __n = _M_bkt_num_key(__key); 511*404b540aSrobert _Node* __first; 512*404b540aSrobert for (__first = _M_buckets[__n]; 513*404b540aSrobert __first && !_M_equals(_M_get_key(__first->_M_val), __key); 514*404b540aSrobert __first = __first->_M_next) 515*404b540aSrobert { } 516*404b540aSrobert return iterator(__first, this); 517*404b540aSrobert } 518*404b540aSrobert 519*404b540aSrobert const_iterator 520*404b540aSrobert find(const key_type& __key) const 521*404b540aSrobert { 522*404b540aSrobert size_type __n = _M_bkt_num_key(__key); 523*404b540aSrobert const _Node* __first; 524*404b540aSrobert for (__first = _M_buckets[__n]; 525*404b540aSrobert __first && !_M_equals(_M_get_key(__first->_M_val), __key); 526*404b540aSrobert __first = __first->_M_next) 527*404b540aSrobert { } 528*404b540aSrobert return const_iterator(__first, this); 529*404b540aSrobert } 530*404b540aSrobert 531*404b540aSrobert size_type 532*404b540aSrobert count(const key_type& __key) const 533*404b540aSrobert { 534*404b540aSrobert const size_type __n = _M_bkt_num_key(__key); 535*404b540aSrobert size_type __result = 0; 536*404b540aSrobert 537*404b540aSrobert for (const _Node* __cur = _M_buckets[__n]; __cur; 538*404b540aSrobert __cur = __cur->_M_next) 539*404b540aSrobert if (_M_equals(_M_get_key(__cur->_M_val), __key)) 540*404b540aSrobert ++__result; 541*404b540aSrobert return __result; 542*404b540aSrobert } 543*404b540aSrobert 544*404b540aSrobert pair<iterator, iterator> 545*404b540aSrobert equal_range(const key_type& __key); 546*404b540aSrobert 547*404b540aSrobert pair<const_iterator, const_iterator> 548*404b540aSrobert equal_range(const key_type& __key) const; 549*404b540aSrobert 550*404b540aSrobert size_type 551*404b540aSrobert erase(const key_type& __key); 552*404b540aSrobert 553*404b540aSrobert void 554*404b540aSrobert erase(const iterator& __it); 555*404b540aSrobert 556*404b540aSrobert void 557*404b540aSrobert erase(iterator __first, iterator __last); 558*404b540aSrobert 559*404b540aSrobert void 560*404b540aSrobert erase(const const_iterator& __it); 561*404b540aSrobert 562*404b540aSrobert void 563*404b540aSrobert erase(const_iterator __first, const_iterator __last); 564*404b540aSrobert 565*404b540aSrobert void 566*404b540aSrobert resize(size_type __num_elements_hint); 567*404b540aSrobert 568*404b540aSrobert void 569*404b540aSrobert clear(); 570*404b540aSrobert 571*404b540aSrobert private: 572*404b540aSrobert size_type 573*404b540aSrobert _M_next_size(size_type __n) const 574*404b540aSrobert { return __stl_next_prime(__n); } 575*404b540aSrobert 576*404b540aSrobert void 577*404b540aSrobert _M_initialize_buckets(size_type __n) 578*404b540aSrobert { 579*404b540aSrobert const size_type __n_buckets = _M_next_size(__n); 580*404b540aSrobert _M_buckets.reserve(__n_buckets); 581*404b540aSrobert _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); 582*404b540aSrobert _M_num_elements = 0; 583*404b540aSrobert } 584*404b540aSrobert 585*404b540aSrobert size_type 586*404b540aSrobert _M_bkt_num_key(const key_type& __key) const 587*404b540aSrobert { return _M_bkt_num_key(__key, _M_buckets.size()); } 588*404b540aSrobert 589*404b540aSrobert size_type 590*404b540aSrobert _M_bkt_num(const value_type& __obj) const 591*404b540aSrobert { return _M_bkt_num_key(_M_get_key(__obj)); } 592*404b540aSrobert 593*404b540aSrobert size_type 594*404b540aSrobert _M_bkt_num_key(const key_type& __key, size_t __n) const 595*404b540aSrobert { return _M_hash(__key) % __n; } 596*404b540aSrobert 597*404b540aSrobert size_type 598*404b540aSrobert _M_bkt_num(const value_type& __obj, size_t __n) const 599*404b540aSrobert { return _M_bkt_num_key(_M_get_key(__obj), __n); } 600*404b540aSrobert 601*404b540aSrobert _Node* 602*404b540aSrobert _M_new_node(const value_type& __obj) 603*404b540aSrobert { 604*404b540aSrobert _Node* __n = _M_get_node(); 605*404b540aSrobert __n->_M_next = 0; 606*404b540aSrobert try 607*404b540aSrobert { 608*404b540aSrobert this->get_allocator().construct(&__n->_M_val, __obj); 609*404b540aSrobert return __n; 610*404b540aSrobert } 611*404b540aSrobert catch(...) 612*404b540aSrobert { 613*404b540aSrobert _M_put_node(__n); 614*404b540aSrobert __throw_exception_again; 615*404b540aSrobert } 616*404b540aSrobert } 617*404b540aSrobert 618*404b540aSrobert void 619*404b540aSrobert _M_delete_node(_Node* __n) 620*404b540aSrobert { 621*404b540aSrobert this->get_allocator().destroy(&__n->_M_val); 622*404b540aSrobert _M_put_node(__n); 623*404b540aSrobert } 624*404b540aSrobert 625*404b540aSrobert void 626*404b540aSrobert _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); 627*404b540aSrobert 628*404b540aSrobert void 629*404b540aSrobert _M_erase_bucket(const size_type __n, _Node* __last); 630*404b540aSrobert 631*404b540aSrobert void 632*404b540aSrobert _M_copy_from(const hashtable& __ht); 633*404b540aSrobert }; 634*404b540aSrobert 635*404b540aSrobert template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 636*404b540aSrobert class _All> 637*404b540aSrobert _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 638*404b540aSrobert _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 639*404b540aSrobert operator++() 640*404b540aSrobert { 641*404b540aSrobert const _Node* __old = _M_cur; 642*404b540aSrobert _M_cur = _M_cur->_M_next; 643*404b540aSrobert if (!_M_cur) 644*404b540aSrobert { 645*404b540aSrobert size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 646*404b540aSrobert while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 647*404b540aSrobert _M_cur = _M_ht->_M_buckets[__bucket]; 648*404b540aSrobert } 649*404b540aSrobert return *this; 650*404b540aSrobert } 651*404b540aSrobert 652*404b540aSrobert template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 653*404b540aSrobert class _All> 654*404b540aSrobert inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 655*404b540aSrobert _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 656*404b540aSrobert operator++(int) 657*404b540aSrobert { 658*404b540aSrobert iterator __tmp = *this; 659*404b540aSrobert ++*this; 660*404b540aSrobert return __tmp; 661*404b540aSrobert } 662*404b540aSrobert 663*404b540aSrobert template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 664*404b540aSrobert class _All> 665*404b540aSrobert _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 666*404b540aSrobert _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 667*404b540aSrobert operator++() 668*404b540aSrobert { 669*404b540aSrobert const _Node* __old = _M_cur; 670*404b540aSrobert _M_cur = _M_cur->_M_next; 671*404b540aSrobert if (!_M_cur) 672*404b540aSrobert { 673*404b540aSrobert size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 674*404b540aSrobert while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 675*404b540aSrobert _M_cur = _M_ht->_M_buckets[__bucket]; 676*404b540aSrobert } 677*404b540aSrobert return *this; 678*404b540aSrobert } 679*404b540aSrobert 680*404b540aSrobert template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 681*404b540aSrobert class _All> 682*404b540aSrobert inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 683*404b540aSrobert _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 684*404b540aSrobert operator++(int) 685*404b540aSrobert { 686*404b540aSrobert const_iterator __tmp = *this; 687*404b540aSrobert ++*this; 688*404b540aSrobert return __tmp; 689*404b540aSrobert } 690*404b540aSrobert 691*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 692*404b540aSrobert bool 693*404b540aSrobert operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 694*404b540aSrobert const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 695*404b540aSrobert { 696*404b540aSrobert typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node; 697*404b540aSrobert 698*404b540aSrobert if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) 699*404b540aSrobert return false; 700*404b540aSrobert 701*404b540aSrobert for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) 702*404b540aSrobert { 703*404b540aSrobert _Node* __cur1 = __ht1._M_buckets[__n]; 704*404b540aSrobert _Node* __cur2 = __ht2._M_buckets[__n]; 705*404b540aSrobert // Check same length of lists 706*404b540aSrobert for (; __cur1 && __cur2; 707*404b540aSrobert __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) 708*404b540aSrobert { } 709*404b540aSrobert if (__cur1 || __cur2) 710*404b540aSrobert return false; 711*404b540aSrobert // Now check one's elements are in the other 712*404b540aSrobert for (__cur1 = __ht1._M_buckets[__n] ; __cur1; 713*404b540aSrobert __cur1 = __cur1->_M_next) 714*404b540aSrobert { 715*404b540aSrobert bool _found__cur1 = false; 716*404b540aSrobert for (__cur2 = __ht2._M_buckets[__n]; 717*404b540aSrobert __cur2; __cur2 = __cur2->_M_next) 718*404b540aSrobert { 719*404b540aSrobert if (__cur1->_M_val == __cur2->_M_val) 720*404b540aSrobert { 721*404b540aSrobert _found__cur1 = true; 722*404b540aSrobert break; 723*404b540aSrobert } 724*404b540aSrobert } 725*404b540aSrobert if (!_found__cur1) 726*404b540aSrobert return false; 727*404b540aSrobert } 728*404b540aSrobert } 729*404b540aSrobert return true; 730*404b540aSrobert } 731*404b540aSrobert 732*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 733*404b540aSrobert inline bool 734*404b540aSrobert operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 735*404b540aSrobert const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 736*404b540aSrobert { return !(__ht1 == __ht2); } 737*404b540aSrobert 738*404b540aSrobert template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, 739*404b540aSrobert class _All> 740*404b540aSrobert inline void 741*404b540aSrobert swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, 742*404b540aSrobert hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) 743*404b540aSrobert { __ht1.swap(__ht2); } 744*404b540aSrobert 745*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 746*404b540aSrobert pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool> 747*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 748*404b540aSrobert insert_unique_noresize(const value_type& __obj) 749*404b540aSrobert { 750*404b540aSrobert const size_type __n = _M_bkt_num(__obj); 751*404b540aSrobert _Node* __first = _M_buckets[__n]; 752*404b540aSrobert 753*404b540aSrobert for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 754*404b540aSrobert if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 755*404b540aSrobert return pair<iterator, bool>(iterator(__cur, this), false); 756*404b540aSrobert 757*404b540aSrobert _Node* __tmp = _M_new_node(__obj); 758*404b540aSrobert __tmp->_M_next = __first; 759*404b540aSrobert _M_buckets[__n] = __tmp; 760*404b540aSrobert ++_M_num_elements; 761*404b540aSrobert return pair<iterator, bool>(iterator(__tmp, this), true); 762*404b540aSrobert } 763*404b540aSrobert 764*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 765*404b540aSrobert typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator 766*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 767*404b540aSrobert insert_equal_noresize(const value_type& __obj) 768*404b540aSrobert { 769*404b540aSrobert const size_type __n = _M_bkt_num(__obj); 770*404b540aSrobert _Node* __first = _M_buckets[__n]; 771*404b540aSrobert 772*404b540aSrobert for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 773*404b540aSrobert if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 774*404b540aSrobert { 775*404b540aSrobert _Node* __tmp = _M_new_node(__obj); 776*404b540aSrobert __tmp->_M_next = __cur->_M_next; 777*404b540aSrobert __cur->_M_next = __tmp; 778*404b540aSrobert ++_M_num_elements; 779*404b540aSrobert return iterator(__tmp, this); 780*404b540aSrobert } 781*404b540aSrobert 782*404b540aSrobert _Node* __tmp = _M_new_node(__obj); 783*404b540aSrobert __tmp->_M_next = __first; 784*404b540aSrobert _M_buckets[__n] = __tmp; 785*404b540aSrobert ++_M_num_elements; 786*404b540aSrobert return iterator(__tmp, this); 787*404b540aSrobert } 788*404b540aSrobert 789*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 790*404b540aSrobert typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference 791*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 792*404b540aSrobert find_or_insert(const value_type& __obj) 793*404b540aSrobert { 794*404b540aSrobert resize(_M_num_elements + 1); 795*404b540aSrobert 796*404b540aSrobert size_type __n = _M_bkt_num(__obj); 797*404b540aSrobert _Node* __first = _M_buckets[__n]; 798*404b540aSrobert 799*404b540aSrobert for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 800*404b540aSrobert if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 801*404b540aSrobert return __cur->_M_val; 802*404b540aSrobert 803*404b540aSrobert _Node* __tmp = _M_new_node(__obj); 804*404b540aSrobert __tmp->_M_next = __first; 805*404b540aSrobert _M_buckets[__n] = __tmp; 806*404b540aSrobert ++_M_num_elements; 807*404b540aSrobert return __tmp->_M_val; 808*404b540aSrobert } 809*404b540aSrobert 810*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 811*404b540aSrobert pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, 812*404b540aSrobert typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator> 813*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 814*404b540aSrobert equal_range(const key_type& __key) 815*404b540aSrobert { 816*404b540aSrobert typedef pair<iterator, iterator> _Pii; 817*404b540aSrobert const size_type __n = _M_bkt_num_key(__key); 818*404b540aSrobert 819*404b540aSrobert for (_Node* __first = _M_buckets[__n]; __first; 820*404b540aSrobert __first = __first->_M_next) 821*404b540aSrobert if (_M_equals(_M_get_key(__first->_M_val), __key)) 822*404b540aSrobert { 823*404b540aSrobert for (_Node* __cur = __first->_M_next; __cur; 824*404b540aSrobert __cur = __cur->_M_next) 825*404b540aSrobert if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 826*404b540aSrobert return _Pii(iterator(__first, this), iterator(__cur, this)); 827*404b540aSrobert for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 828*404b540aSrobert if (_M_buckets[__m]) 829*404b540aSrobert return _Pii(iterator(__first, this), 830*404b540aSrobert iterator(_M_buckets[__m], this)); 831*404b540aSrobert return _Pii(iterator(__first, this), end()); 832*404b540aSrobert } 833*404b540aSrobert return _Pii(end(), end()); 834*404b540aSrobert } 835*404b540aSrobert 836*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 837*404b540aSrobert pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator, 838*404b540aSrobert typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator> 839*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 840*404b540aSrobert equal_range(const key_type& __key) const 841*404b540aSrobert { 842*404b540aSrobert typedef pair<const_iterator, const_iterator> _Pii; 843*404b540aSrobert const size_type __n = _M_bkt_num_key(__key); 844*404b540aSrobert 845*404b540aSrobert for (const _Node* __first = _M_buckets[__n]; __first; 846*404b540aSrobert __first = __first->_M_next) 847*404b540aSrobert { 848*404b540aSrobert if (_M_equals(_M_get_key(__first->_M_val), __key)) 849*404b540aSrobert { 850*404b540aSrobert for (const _Node* __cur = __first->_M_next; __cur; 851*404b540aSrobert __cur = __cur->_M_next) 852*404b540aSrobert if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 853*404b540aSrobert return _Pii(const_iterator(__first, this), 854*404b540aSrobert const_iterator(__cur, this)); 855*404b540aSrobert for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 856*404b540aSrobert if (_M_buckets[__m]) 857*404b540aSrobert return _Pii(const_iterator(__first, this), 858*404b540aSrobert const_iterator(_M_buckets[__m], this)); 859*404b540aSrobert return _Pii(const_iterator(__first, this), end()); 860*404b540aSrobert } 861*404b540aSrobert } 862*404b540aSrobert return _Pii(end(), end()); 863*404b540aSrobert } 864*404b540aSrobert 865*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 866*404b540aSrobert typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type 867*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 868*404b540aSrobert erase(const key_type& __key) 869*404b540aSrobert { 870*404b540aSrobert const size_type __n = _M_bkt_num_key(__key); 871*404b540aSrobert _Node* __first = _M_buckets[__n]; 872*404b540aSrobert size_type __erased = 0; 873*404b540aSrobert 874*404b540aSrobert if (__first) 875*404b540aSrobert { 876*404b540aSrobert _Node* __cur = __first; 877*404b540aSrobert _Node* __next = __cur->_M_next; 878*404b540aSrobert while (__next) 879*404b540aSrobert { 880*404b540aSrobert if (_M_equals(_M_get_key(__next->_M_val), __key)) 881*404b540aSrobert { 882*404b540aSrobert __cur->_M_next = __next->_M_next; 883*404b540aSrobert _M_delete_node(__next); 884*404b540aSrobert __next = __cur->_M_next; 885*404b540aSrobert ++__erased; 886*404b540aSrobert --_M_num_elements; 887*404b540aSrobert } 888*404b540aSrobert else 889*404b540aSrobert { 890*404b540aSrobert __cur = __next; 891*404b540aSrobert __next = __cur->_M_next; 892*404b540aSrobert } 893*404b540aSrobert } 894*404b540aSrobert if (_M_equals(_M_get_key(__first->_M_val), __key)) 895*404b540aSrobert { 896*404b540aSrobert _M_buckets[__n] = __first->_M_next; 897*404b540aSrobert _M_delete_node(__first); 898*404b540aSrobert ++__erased; 899*404b540aSrobert --_M_num_elements; 900*404b540aSrobert } 901*404b540aSrobert } 902*404b540aSrobert return __erased; 903*404b540aSrobert } 904*404b540aSrobert 905*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 906*404b540aSrobert void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 907*404b540aSrobert erase(const iterator& __it) 908*404b540aSrobert { 909*404b540aSrobert _Node* __p = __it._M_cur; 910*404b540aSrobert if (__p) 911*404b540aSrobert { 912*404b540aSrobert const size_type __n = _M_bkt_num(__p->_M_val); 913*404b540aSrobert _Node* __cur = _M_buckets[__n]; 914*404b540aSrobert 915*404b540aSrobert if (__cur == __p) 916*404b540aSrobert { 917*404b540aSrobert _M_buckets[__n] = __cur->_M_next; 918*404b540aSrobert _M_delete_node(__cur); 919*404b540aSrobert --_M_num_elements; 920*404b540aSrobert } 921*404b540aSrobert else 922*404b540aSrobert { 923*404b540aSrobert _Node* __next = __cur->_M_next; 924*404b540aSrobert while (__next) 925*404b540aSrobert { 926*404b540aSrobert if (__next == __p) 927*404b540aSrobert { 928*404b540aSrobert __cur->_M_next = __next->_M_next; 929*404b540aSrobert _M_delete_node(__next); 930*404b540aSrobert --_M_num_elements; 931*404b540aSrobert break; 932*404b540aSrobert } 933*404b540aSrobert else 934*404b540aSrobert { 935*404b540aSrobert __cur = __next; 936*404b540aSrobert __next = __cur->_M_next; 937*404b540aSrobert } 938*404b540aSrobert } 939*404b540aSrobert } 940*404b540aSrobert } 941*404b540aSrobert } 942*404b540aSrobert 943*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 944*404b540aSrobert void 945*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 946*404b540aSrobert erase(iterator __first, iterator __last) 947*404b540aSrobert { 948*404b540aSrobert size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) 949*404b540aSrobert : _M_buckets.size(); 950*404b540aSrobert 951*404b540aSrobert size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) 952*404b540aSrobert : _M_buckets.size(); 953*404b540aSrobert 954*404b540aSrobert if (__first._M_cur == __last._M_cur) 955*404b540aSrobert return; 956*404b540aSrobert else if (__f_bucket == __l_bucket) 957*404b540aSrobert _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); 958*404b540aSrobert else 959*404b540aSrobert { 960*404b540aSrobert _M_erase_bucket(__f_bucket, __first._M_cur, 0); 961*404b540aSrobert for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) 962*404b540aSrobert _M_erase_bucket(__n, 0); 963*404b540aSrobert if (__l_bucket != _M_buckets.size()) 964*404b540aSrobert _M_erase_bucket(__l_bucket, __last._M_cur); 965*404b540aSrobert } 966*404b540aSrobert } 967*404b540aSrobert 968*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 969*404b540aSrobert inline void 970*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 971*404b540aSrobert erase(const_iterator __first, const_iterator __last) 972*404b540aSrobert { 973*404b540aSrobert erase(iterator(const_cast<_Node*>(__first._M_cur), 974*404b540aSrobert const_cast<hashtable*>(__first._M_ht)), 975*404b540aSrobert iterator(const_cast<_Node*>(__last._M_cur), 976*404b540aSrobert const_cast<hashtable*>(__last._M_ht))); 977*404b540aSrobert } 978*404b540aSrobert 979*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 980*404b540aSrobert inline void 981*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 982*404b540aSrobert erase(const const_iterator& __it) 983*404b540aSrobert { erase(iterator(const_cast<_Node*>(__it._M_cur), 984*404b540aSrobert const_cast<hashtable*>(__it._M_ht))); } 985*404b540aSrobert 986*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 987*404b540aSrobert void 988*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 989*404b540aSrobert resize(size_type __num_elements_hint) 990*404b540aSrobert { 991*404b540aSrobert const size_type __old_n = _M_buckets.size(); 992*404b540aSrobert if (__num_elements_hint > __old_n) 993*404b540aSrobert { 994*404b540aSrobert const size_type __n = _M_next_size(__num_elements_hint); 995*404b540aSrobert if (__n > __old_n) 996*404b540aSrobert { 997*404b540aSrobert _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator()); 998*404b540aSrobert try 999*404b540aSrobert { 1000*404b540aSrobert for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) 1001*404b540aSrobert { 1002*404b540aSrobert _Node* __first = _M_buckets[__bucket]; 1003*404b540aSrobert while (__first) 1004*404b540aSrobert { 1005*404b540aSrobert size_type __new_bucket = _M_bkt_num(__first->_M_val, 1006*404b540aSrobert __n); 1007*404b540aSrobert _M_buckets[__bucket] = __first->_M_next; 1008*404b540aSrobert __first->_M_next = __tmp[__new_bucket]; 1009*404b540aSrobert __tmp[__new_bucket] = __first; 1010*404b540aSrobert __first = _M_buckets[__bucket]; 1011*404b540aSrobert } 1012*404b540aSrobert } 1013*404b540aSrobert _M_buckets.swap(__tmp); 1014*404b540aSrobert } 1015*404b540aSrobert catch(...) 1016*404b540aSrobert { 1017*404b540aSrobert for (size_type __bucket = 0; __bucket < __tmp.size(); 1018*404b540aSrobert ++__bucket) 1019*404b540aSrobert { 1020*404b540aSrobert while (__tmp[__bucket]) 1021*404b540aSrobert { 1022*404b540aSrobert _Node* __next = __tmp[__bucket]->_M_next; 1023*404b540aSrobert _M_delete_node(__tmp[__bucket]); 1024*404b540aSrobert __tmp[__bucket] = __next; 1025*404b540aSrobert } 1026*404b540aSrobert } 1027*404b540aSrobert __throw_exception_again; 1028*404b540aSrobert } 1029*404b540aSrobert } 1030*404b540aSrobert } 1031*404b540aSrobert } 1032*404b540aSrobert 1033*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1034*404b540aSrobert void 1035*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1036*404b540aSrobert _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) 1037*404b540aSrobert { 1038*404b540aSrobert _Node* __cur = _M_buckets[__n]; 1039*404b540aSrobert if (__cur == __first) 1040*404b540aSrobert _M_erase_bucket(__n, __last); 1041*404b540aSrobert else 1042*404b540aSrobert { 1043*404b540aSrobert _Node* __next; 1044*404b540aSrobert for (__next = __cur->_M_next; 1045*404b540aSrobert __next != __first; 1046*404b540aSrobert __cur = __next, __next = __cur->_M_next) 1047*404b540aSrobert ; 1048*404b540aSrobert while (__next != __last) 1049*404b540aSrobert { 1050*404b540aSrobert __cur->_M_next = __next->_M_next; 1051*404b540aSrobert _M_delete_node(__next); 1052*404b540aSrobert __next = __cur->_M_next; 1053*404b540aSrobert --_M_num_elements; 1054*404b540aSrobert } 1055*404b540aSrobert } 1056*404b540aSrobert } 1057*404b540aSrobert 1058*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1059*404b540aSrobert void 1060*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1061*404b540aSrobert _M_erase_bucket(const size_type __n, _Node* __last) 1062*404b540aSrobert { 1063*404b540aSrobert _Node* __cur = _M_buckets[__n]; 1064*404b540aSrobert while (__cur != __last) 1065*404b540aSrobert { 1066*404b540aSrobert _Node* __next = __cur->_M_next; 1067*404b540aSrobert _M_delete_node(__cur); 1068*404b540aSrobert __cur = __next; 1069*404b540aSrobert _M_buckets[__n] = __cur; 1070*404b540aSrobert --_M_num_elements; 1071*404b540aSrobert } 1072*404b540aSrobert } 1073*404b540aSrobert 1074*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1075*404b540aSrobert void 1076*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1077*404b540aSrobert clear() 1078*404b540aSrobert { 1079*404b540aSrobert for (size_type __i = 0; __i < _M_buckets.size(); ++__i) 1080*404b540aSrobert { 1081*404b540aSrobert _Node* __cur = _M_buckets[__i]; 1082*404b540aSrobert while (__cur != 0) 1083*404b540aSrobert { 1084*404b540aSrobert _Node* __next = __cur->_M_next; 1085*404b540aSrobert _M_delete_node(__cur); 1086*404b540aSrobert __cur = __next; 1087*404b540aSrobert } 1088*404b540aSrobert _M_buckets[__i] = 0; 1089*404b540aSrobert } 1090*404b540aSrobert _M_num_elements = 0; 1091*404b540aSrobert } 1092*404b540aSrobert 1093*404b540aSrobert template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1094*404b540aSrobert void 1095*404b540aSrobert hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1096*404b540aSrobert _M_copy_from(const hashtable& __ht) 1097*404b540aSrobert { 1098*404b540aSrobert _M_buckets.clear(); 1099*404b540aSrobert _M_buckets.reserve(__ht._M_buckets.size()); 1100*404b540aSrobert _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); 1101*404b540aSrobert try 1102*404b540aSrobert { 1103*404b540aSrobert for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { 1104*404b540aSrobert const _Node* __cur = __ht._M_buckets[__i]; 1105*404b540aSrobert if (__cur) 1106*404b540aSrobert { 1107*404b540aSrobert _Node* __local_copy = _M_new_node(__cur->_M_val); 1108*404b540aSrobert _M_buckets[__i] = __local_copy; 1109*404b540aSrobert 1110*404b540aSrobert for (_Node* __next = __cur->_M_next; 1111*404b540aSrobert __next; 1112*404b540aSrobert __cur = __next, __next = __cur->_M_next) 1113*404b540aSrobert { 1114*404b540aSrobert __local_copy->_M_next = _M_new_node(__next->_M_val); 1115*404b540aSrobert __local_copy = __local_copy->_M_next; 1116*404b540aSrobert } 1117*404b540aSrobert } 1118*404b540aSrobert } 1119*404b540aSrobert _M_num_elements = __ht._M_num_elements; 1120*404b540aSrobert } 1121*404b540aSrobert catch(...) 1122*404b540aSrobert { 1123*404b540aSrobert clear(); 1124*404b540aSrobert __throw_exception_again; 1125*404b540aSrobert } 1126*404b540aSrobert } 1127*404b540aSrobert 1128*404b540aSrobert _GLIBCXX_END_NAMESPACE 1129*404b540aSrobert 1130*404b540aSrobert #endif 1131