1132720Skan// Hashtable implementation used by containers -*- C++ -*- 2132720Skan 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 5132720Skan// 6132720Skan// This file is part of the GNU ISO C++ Library. This library is free 7132720Skan// software; you can redistribute it and/or modify it under the 8132720Skan// terms of the GNU General Public License as published by the 9132720Skan// Free Software Foundation; either version 2, or (at your option) 10132720Skan// any later version. 11132720Skan 12132720Skan// This library is distributed in the hope that it will be useful, 13132720Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 14132720Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15132720Skan// GNU General Public License for more details. 16132720Skan 17132720Skan// You should have received a copy of the GNU General Public License along 18132720Skan// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20132720Skan// USA. 21132720Skan 22132720Skan// As a special exception, you may use this file as part of a free software 23132720Skan// library without restriction. Specifically, if other files instantiate 24132720Skan// templates or use macros or inline functions from this file, or you compile 25132720Skan// this file and link it with other files to produce an executable, this 26132720Skan// file does not by itself cause the resulting executable to be covered by 27132720Skan// the GNU General Public License. This exception does not however 28132720Skan// invalidate any other reasons why the executable file might be covered by 29132720Skan// the GNU General Public License. 30132720Skan 31132720Skan/* 32132720Skan * Copyright (c) 1996,1997 33132720Skan * Silicon Graphics Computer Systems, Inc. 34132720Skan * 35132720Skan * Permission to use, copy, modify, distribute and sell this software 36132720Skan * and its documentation for any purpose is hereby granted without fee, 37132720Skan * provided that the above copyright notice appear in all copies and 38132720Skan * that both that copyright notice and this permission notice appear 39132720Skan * in supporting documentation. Silicon Graphics makes no 40132720Skan * representations about the suitability of this software for any 41132720Skan * purpose. It is provided "as is" without express or implied warranty. 42132720Skan * 43132720Skan * 44132720Skan * Copyright (c) 1994 45132720Skan * Hewlett-Packard Company 46132720Skan * 47132720Skan * Permission to use, copy, modify, distribute and sell this software 48132720Skan * and its documentation for any purpose is hereby granted without fee, 49132720Skan * provided that the above copyright notice appear in all copies and 50132720Skan * that both that copyright notice and this permission notice appear 51132720Skan * in supporting documentation. Hewlett-Packard Company makes no 52132720Skan * representations about the suitability of this software for any 53132720Skan * purpose. It is provided "as is" without express or implied warranty. 54132720Skan * 55132720Skan */ 56132720Skan 57132720Skan/** @file ext/hashtable.h 58132720Skan * This file is a GNU extension to the Standard C++ Library (possibly 59169691Skan * containing extensions from the HP/SGI STL subset). 60132720Skan */ 61132720Skan 62132720Skan#ifndef _HASHTABLE_H 63132720Skan#define _HASHTABLE_H 1 64132720Skan 65132720Skan// Hashtable class, used to implement the hashed associative containers 66132720Skan// hash_set, hash_map, hash_multiset, and hash_multimap. 67132720Skan 68132720Skan#include <vector> 69132720Skan#include <iterator> 70132720Skan#include <bits/stl_algo.h> 71132720Skan#include <bits/stl_function.h> 72132720Skan#include <ext/hash_fun.h> 73132720Skan 74169691Skan_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 75132720Skan 76169691Skan using std::size_t; 77169691Skan using std::ptrdiff_t; 78169691Skan using std::forward_iterator_tag; 79169691Skan using std::input_iterator_tag; 80169691Skan using std::_Construct; 81169691Skan using std::_Destroy; 82169691Skan using std::distance; 83169691Skan using std::vector; 84169691Skan using std::pair; 85169691Skan using std::__iterator_category; 86132720Skan 87169691Skan template<class _Val> 88169691Skan struct _Hashtable_node 89169691Skan { 90169691Skan _Hashtable_node* _M_next; 91169691Skan _Val _M_val; 92169691Skan }; 93132720Skan 94169691Skan template<class _Val, class _Key, class _HashFcn, class _ExtractKey, 95169691Skan class _EqualKey, class _Alloc = std::allocator<_Val> > 96169691Skan class hashtable; 97132720Skan 98169691Skan template<class _Val, class _Key, class _HashFcn, 99169691Skan class _ExtractKey, class _EqualKey, class _Alloc> 100169691Skan struct _Hashtable_iterator; 101132720Skan 102169691Skan template<class _Val, class _Key, class _HashFcn, 103169691Skan class _ExtractKey, class _EqualKey, class _Alloc> 104169691Skan struct _Hashtable_const_iterator; 105132720Skan 106169691Skan template<class _Val, class _Key, class _HashFcn, 107169691Skan class _ExtractKey, class _EqualKey, class _Alloc> 108169691Skan struct _Hashtable_iterator 109169691Skan { 110169691Skan typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> 111169691Skan _Hashtable; 112169691Skan typedef _Hashtable_iterator<_Val, _Key, _HashFcn, 113169691Skan _ExtractKey, _EqualKey, _Alloc> 114169691Skan iterator; 115169691Skan typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 116169691Skan _ExtractKey, _EqualKey, _Alloc> 117169691Skan const_iterator; 118169691Skan typedef _Hashtable_node<_Val> _Node; 119169691Skan typedef forward_iterator_tag iterator_category; 120169691Skan typedef _Val value_type; 121169691Skan typedef ptrdiff_t difference_type; 122169691Skan typedef size_t size_type; 123169691Skan typedef _Val& reference; 124169691Skan typedef _Val* pointer; 125169691Skan 126169691Skan _Node* _M_cur; 127169691Skan _Hashtable* _M_ht; 128132720Skan 129169691Skan _Hashtable_iterator(_Node* __n, _Hashtable* __tab) 130169691Skan : _M_cur(__n), _M_ht(__tab) { } 131132720Skan 132169691Skan _Hashtable_iterator() { } 133132720Skan 134169691Skan reference 135169691Skan operator*() const 136169691Skan { return _M_cur->_M_val; } 137132720Skan 138169691Skan pointer 139169691Skan operator->() const 140169691Skan { return &(operator*()); } 141132720Skan 142169691Skan iterator& 143169691Skan operator++(); 144132720Skan 145169691Skan iterator 146169691Skan operator++(int); 147132720Skan 148169691Skan bool 149169691Skan operator==(const iterator& __it) const 150169691Skan { return _M_cur == __it._M_cur; } 151132720Skan 152169691Skan bool 153169691Skan operator!=(const iterator& __it) const 154169691Skan { return _M_cur != __it._M_cur; } 155169691Skan }; 156132720Skan 157169691Skan template<class _Val, class _Key, class _HashFcn, 158169691Skan class _ExtractKey, class _EqualKey, class _Alloc> 159169691Skan struct _Hashtable_const_iterator 160169691Skan { 161169691Skan typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> 162169691Skan _Hashtable; 163169691Skan typedef _Hashtable_iterator<_Val,_Key,_HashFcn, 164169691Skan _ExtractKey,_EqualKey,_Alloc> 165169691Skan iterator; 166169691Skan typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 167169691Skan _ExtractKey, _EqualKey, _Alloc> 168169691Skan const_iterator; 169169691Skan typedef _Hashtable_node<_Val> _Node; 170132720Skan 171169691Skan typedef forward_iterator_tag iterator_category; 172169691Skan typedef _Val value_type; 173169691Skan typedef ptrdiff_t difference_type; 174169691Skan typedef size_t size_type; 175169691Skan typedef const _Val& reference; 176169691Skan typedef const _Val* pointer; 177169691Skan 178169691Skan const _Node* _M_cur; 179169691Skan const _Hashtable* _M_ht; 180132720Skan 181169691Skan _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab) 182169691Skan : _M_cur(__n), _M_ht(__tab) { } 183132720Skan 184169691Skan _Hashtable_const_iterator() { } 185132720Skan 186169691Skan _Hashtable_const_iterator(const iterator& __it) 187169691Skan : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { } 188132720Skan 189169691Skan reference 190169691Skan operator*() const 191169691Skan { return _M_cur->_M_val; } 192132720Skan 193169691Skan pointer 194169691Skan operator->() const 195169691Skan { return &(operator*()); } 196132720Skan 197169691Skan const_iterator& 198169691Skan operator++(); 199132720Skan 200169691Skan const_iterator 201169691Skan operator++(int); 202132720Skan 203169691Skan bool 204169691Skan operator==(const const_iterator& __it) const 205169691Skan { return _M_cur == __it._M_cur; } 206132720Skan 207169691Skan bool 208169691Skan operator!=(const const_iterator& __it) const 209169691Skan { return _M_cur != __it._M_cur; } 210169691Skan }; 211132720Skan 212169691Skan // Note: assumes long is at least 32 bits. 213169691Skan enum { _S_num_primes = 28 }; 214132720Skan 215169691Skan static const unsigned long __stl_prime_list[_S_num_primes] = 216169691Skan { 217169691Skan 53ul, 97ul, 193ul, 389ul, 769ul, 218169691Skan 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 219169691Skan 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 220169691Skan 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 221169691Skan 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 222169691Skan 1610612741ul, 3221225473ul, 4294967291ul 223169691Skan }; 224132720Skan 225169691Skan inline unsigned long 226169691Skan __stl_next_prime(unsigned long __n) 227169691Skan { 228169691Skan const unsigned long* __first = __stl_prime_list; 229169691Skan const unsigned long* __last = __stl_prime_list + (int)_S_num_primes; 230169691Skan const unsigned long* pos = std::lower_bound(__first, __last, __n); 231169691Skan return pos == __last ? *(__last - 1) : *pos; 232169691Skan } 233132720Skan 234169691Skan // Forward declaration of operator==. 235169691Skan template<class _Val, class _Key, class _HF, class _Ex, 236169691Skan class _Eq, class _All> 237169691Skan class hashtable; 238132720Skan 239169691Skan template<class _Val, class _Key, class _HF, class _Ex, 240169691Skan class _Eq, class _All> 241169691Skan bool 242169691Skan operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 243169691Skan const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2); 244132720Skan 245169691Skan // Hashtables handle allocators a bit differently than other 246169691Skan // containers do. If we're using standard-conforming allocators, then 247169691Skan // a hashtable unconditionally has a member variable to hold its 248169691Skan // allocator, even if it so happens that all instances of the 249169691Skan // allocator type are identical. This is because, for hashtables, 250169691Skan // this extra storage is negligible. Additionally, a base class 251169691Skan // wouldn't serve any other purposes; it wouldn't, for example, 252169691Skan // simplify the exception-handling code. 253169691Skan template<class _Val, class _Key, class _HashFcn, 254169691Skan class _ExtractKey, class _EqualKey, class _Alloc> 255169691Skan class hashtable 256169691Skan { 257169691Skan public: 258169691Skan typedef _Key key_type; 259169691Skan typedef _Val value_type; 260169691Skan typedef _HashFcn hasher; 261169691Skan typedef _EqualKey key_equal; 262132720Skan 263169691Skan typedef size_t size_type; 264169691Skan typedef ptrdiff_t difference_type; 265169691Skan typedef value_type* pointer; 266169691Skan typedef const value_type* const_pointer; 267169691Skan typedef value_type& reference; 268169691Skan typedef const value_type& const_reference; 269132720Skan 270169691Skan hasher 271169691Skan hash_funct() const 272169691Skan { return _M_hash; } 273132720Skan 274169691Skan key_equal 275169691Skan key_eq() const 276169691Skan { return _M_equals; } 277132720Skan 278169691Skan private: 279169691Skan typedef _Hashtable_node<_Val> _Node; 280132720Skan 281169691Skan public: 282169691Skan typedef typename _Alloc::template rebind<value_type>::other allocator_type; 283169691Skan allocator_type 284169691Skan get_allocator() const 285169691Skan { return _M_node_allocator; } 286132720Skan 287169691Skan private: 288169691Skan typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc; 289169691Skan typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc; 290169691Skan typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type; 291132720Skan 292169691Skan _Node_Alloc _M_node_allocator; 293132720Skan 294169691Skan _Node* 295169691Skan _M_get_node() 296169691Skan { return _M_node_allocator.allocate(1); } 297132720Skan 298169691Skan void 299169691Skan _M_put_node(_Node* __p) 300169691Skan { _M_node_allocator.deallocate(__p, 1); } 301132720Skan 302169691Skan private: 303169691Skan hasher _M_hash; 304169691Skan key_equal _M_equals; 305169691Skan _ExtractKey _M_get_key; 306169691Skan _Vector_type _M_buckets; 307169691Skan size_type _M_num_elements; 308169691Skan 309169691Skan public: 310169691Skan typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, 311169691Skan _EqualKey, _Alloc> 312169691Skan iterator; 313169691Skan typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 314169691Skan _EqualKey, _Alloc> 315169691Skan const_iterator; 316132720Skan 317169691Skan friend struct 318169691Skan _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>; 319132720Skan 320169691Skan friend struct 321169691Skan _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 322169691Skan _EqualKey, _Alloc>; 323132720Skan 324169691Skan public: 325169691Skan hashtable(size_type __n, const _HashFcn& __hf, 326169691Skan const _EqualKey& __eql, const _ExtractKey& __ext, 327169691Skan const allocator_type& __a = allocator_type()) 328169691Skan : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 329169691Skan _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0) 330169691Skan { _M_initialize_buckets(__n); } 331132720Skan 332169691Skan hashtable(size_type __n, const _HashFcn& __hf, 333169691Skan const _EqualKey& __eql, 334169691Skan const allocator_type& __a = allocator_type()) 335169691Skan : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 336169691Skan _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0) 337169691Skan { _M_initialize_buckets(__n); } 338132720Skan 339169691Skan hashtable(const hashtable& __ht) 340169691Skan : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash), 341169691Skan _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key), 342169691Skan _M_buckets(__ht.get_allocator()), _M_num_elements(0) 343169691Skan { _M_copy_from(__ht); } 344132720Skan 345169691Skan hashtable& 346169691Skan operator= (const hashtable& __ht) 347169691Skan { 348169691Skan if (&__ht != this) 349169691Skan { 350169691Skan clear(); 351169691Skan _M_hash = __ht._M_hash; 352169691Skan _M_equals = __ht._M_equals; 353169691Skan _M_get_key = __ht._M_get_key; 354169691Skan _M_copy_from(__ht); 355169691Skan } 356169691Skan return *this; 357169691Skan } 358132720Skan 359169691Skan ~hashtable() 360169691Skan { clear(); } 361132720Skan 362169691Skan size_type 363169691Skan size() const 364169691Skan { return _M_num_elements; } 365132720Skan 366169691Skan size_type 367169691Skan max_size() const 368169691Skan { return size_type(-1); } 369132720Skan 370169691Skan bool 371169691Skan empty() const 372169691Skan { return size() == 0; } 373132720Skan 374169691Skan void 375169691Skan swap(hashtable& __ht) 376169691Skan { 377169691Skan std::swap(_M_hash, __ht._M_hash); 378169691Skan std::swap(_M_equals, __ht._M_equals); 379169691Skan std::swap(_M_get_key, __ht._M_get_key); 380169691Skan _M_buckets.swap(__ht._M_buckets); 381169691Skan std::swap(_M_num_elements, __ht._M_num_elements); 382169691Skan } 383132720Skan 384169691Skan iterator 385169691Skan begin() 386169691Skan { 387169691Skan for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 388169691Skan if (_M_buckets[__n]) 389169691Skan return iterator(_M_buckets[__n], this); 390169691Skan return end(); 391169691Skan } 392132720Skan 393169691Skan iterator 394169691Skan end() 395169691Skan { return iterator(0, this); } 396132720Skan 397169691Skan const_iterator 398169691Skan begin() const 399169691Skan { 400169691Skan for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 401169691Skan if (_M_buckets[__n]) 402169691Skan return const_iterator(_M_buckets[__n], this); 403169691Skan return end(); 404169691Skan } 405132720Skan 406169691Skan const_iterator 407169691Skan end() const 408169691Skan { return const_iterator(0, this); } 409132720Skan 410169691Skan template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, 411169691Skan class _Al> 412169691Skan friend bool 413169691Skan operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, 414169691Skan const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); 415132720Skan 416169691Skan public: 417169691Skan size_type 418169691Skan bucket_count() const 419169691Skan { return _M_buckets.size(); } 420132720Skan 421169691Skan size_type 422169691Skan max_bucket_count() const 423169691Skan { return __stl_prime_list[(int)_S_num_primes - 1]; } 424132720Skan 425169691Skan size_type 426169691Skan elems_in_bucket(size_type __bucket) const 427169691Skan { 428169691Skan size_type __result = 0; 429169691Skan for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next) 430169691Skan __result += 1; 431169691Skan return __result; 432169691Skan } 433132720Skan 434169691Skan pair<iterator, bool> 435169691Skan insert_unique(const value_type& __obj) 436169691Skan { 437169691Skan resize(_M_num_elements + 1); 438169691Skan return insert_unique_noresize(__obj); 439169691Skan } 440132720Skan 441169691Skan iterator 442169691Skan insert_equal(const value_type& __obj) 443169691Skan { 444169691Skan resize(_M_num_elements + 1); 445169691Skan return insert_equal_noresize(__obj); 446169691Skan } 447132720Skan 448169691Skan pair<iterator, bool> 449169691Skan insert_unique_noresize(const value_type& __obj); 450132720Skan 451169691Skan iterator 452169691Skan insert_equal_noresize(const value_type& __obj); 453132720Skan 454169691Skan template<class _InputIterator> 455169691Skan void 456169691Skan insert_unique(_InputIterator __f, _InputIterator __l) 457169691Skan { insert_unique(__f, __l, __iterator_category(__f)); } 458132720Skan 459169691Skan template<class _InputIterator> 460169691Skan void 461169691Skan insert_equal(_InputIterator __f, _InputIterator __l) 462169691Skan { insert_equal(__f, __l, __iterator_category(__f)); } 463132720Skan 464169691Skan template<class _InputIterator> 465169691Skan void 466169691Skan insert_unique(_InputIterator __f, _InputIterator __l, 467169691Skan input_iterator_tag) 468169691Skan { 469169691Skan for ( ; __f != __l; ++__f) 470169691Skan insert_unique(*__f); 471169691Skan } 472132720Skan 473169691Skan template<class _InputIterator> 474169691Skan void 475169691Skan insert_equal(_InputIterator __f, _InputIterator __l, 476169691Skan input_iterator_tag) 477169691Skan { 478169691Skan for ( ; __f != __l; ++__f) 479169691Skan insert_equal(*__f); 480169691Skan } 481132720Skan 482169691Skan template<class _ForwardIterator> 483169691Skan void 484169691Skan insert_unique(_ForwardIterator __f, _ForwardIterator __l, 485169691Skan forward_iterator_tag) 486169691Skan { 487169691Skan size_type __n = distance(__f, __l); 488169691Skan resize(_M_num_elements + __n); 489169691Skan for ( ; __n > 0; --__n, ++__f) 490169691Skan insert_unique_noresize(*__f); 491169691Skan } 492132720Skan 493169691Skan template<class _ForwardIterator> 494169691Skan void 495169691Skan insert_equal(_ForwardIterator __f, _ForwardIterator __l, 496169691Skan forward_iterator_tag) 497169691Skan { 498169691Skan size_type __n = distance(__f, __l); 499169691Skan resize(_M_num_elements + __n); 500169691Skan for ( ; __n > 0; --__n, ++__f) 501169691Skan insert_equal_noresize(*__f); 502169691Skan } 503132720Skan 504169691Skan reference 505169691Skan find_or_insert(const value_type& __obj); 506169691Skan 507169691Skan iterator 508169691Skan find(const key_type& __key) 509132720Skan { 510169691Skan size_type __n = _M_bkt_num_key(__key); 511169691Skan _Node* __first; 512169691Skan for (__first = _M_buckets[__n]; 513169691Skan __first && !_M_equals(_M_get_key(__first->_M_val), __key); 514169691Skan __first = __first->_M_next) 515169691Skan { } 516169691Skan return iterator(__first, this); 517132720Skan } 518132720Skan 519169691Skan const_iterator 520169691Skan find(const key_type& __key) const 521169691Skan { 522169691Skan size_type __n = _M_bkt_num_key(__key); 523169691Skan const _Node* __first; 524169691Skan for (__first = _M_buckets[__n]; 525169691Skan __first && !_M_equals(_M_get_key(__first->_M_val), __key); 526169691Skan __first = __first->_M_next) 527169691Skan { } 528169691Skan return const_iterator(__first, this); 529169691Skan } 530132720Skan 531169691Skan size_type 532169691Skan count(const key_type& __key) const 533169691Skan { 534169691Skan const size_type __n = _M_bkt_num_key(__key); 535169691Skan size_type __result = 0; 536169691Skan 537169691Skan for (const _Node* __cur = _M_buckets[__n]; __cur; 538169691Skan __cur = __cur->_M_next) 539169691Skan if (_M_equals(_M_get_key(__cur->_M_val), __key)) 540169691Skan ++__result; 541169691Skan return __result; 542169691Skan } 543132720Skan 544169691Skan pair<iterator, iterator> 545169691Skan equal_range(const key_type& __key); 546132720Skan 547169691Skan pair<const_iterator, const_iterator> 548169691Skan equal_range(const key_type& __key) const; 549132720Skan 550169691Skan size_type 551169691Skan erase(const key_type& __key); 552169691Skan 553169691Skan void 554169691Skan erase(const iterator& __it); 555132720Skan 556169691Skan void 557169691Skan erase(iterator __first, iterator __last); 558132720Skan 559169691Skan void 560169691Skan erase(const const_iterator& __it); 561132720Skan 562169691Skan void 563169691Skan erase(const_iterator __first, const_iterator __last); 564132720Skan 565169691Skan void 566169691Skan resize(size_type __num_elements_hint); 567169691Skan 568169691Skan void 569169691Skan clear(); 570169691Skan 571169691Skan private: 572169691Skan size_type 573169691Skan _M_next_size(size_type __n) const 574169691Skan { return __stl_next_prime(__n); } 575169691Skan 576169691Skan void 577169691Skan _M_initialize_buckets(size_type __n) 578132720Skan { 579169691Skan const size_type __n_buckets = _M_next_size(__n); 580169691Skan _M_buckets.reserve(__n_buckets); 581169691Skan _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); 582169691Skan _M_num_elements = 0; 583132720Skan } 584132720Skan 585169691Skan size_type 586169691Skan _M_bkt_num_key(const key_type& __key) const 587169691Skan { return _M_bkt_num_key(__key, _M_buckets.size()); } 588132720Skan 589169691Skan size_type 590169691Skan _M_bkt_num(const value_type& __obj) const 591169691Skan { return _M_bkt_num_key(_M_get_key(__obj)); } 592132720Skan 593169691Skan size_type 594169691Skan _M_bkt_num_key(const key_type& __key, size_t __n) const 595169691Skan { return _M_hash(__key) % __n; } 596132720Skan 597169691Skan size_type 598169691Skan _M_bkt_num(const value_type& __obj, size_t __n) const 599169691Skan { return _M_bkt_num_key(_M_get_key(__obj), __n); } 600132720Skan 601169691Skan _Node* 602169691Skan _M_new_node(const value_type& __obj) 603169691Skan { 604169691Skan _Node* __n = _M_get_node(); 605169691Skan __n->_M_next = 0; 606169691Skan try 607169691Skan { 608169691Skan this->get_allocator().construct(&__n->_M_val, __obj); 609169691Skan return __n; 610169691Skan } 611169691Skan catch(...) 612169691Skan { 613169691Skan _M_put_node(__n); 614169691Skan __throw_exception_again; 615169691Skan } 616169691Skan } 617132720Skan 618169691Skan void 619169691Skan _M_delete_node(_Node* __n) 620169691Skan { 621169691Skan this->get_allocator().destroy(&__n->_M_val); 622169691Skan _M_put_node(__n); 623169691Skan } 624169691Skan 625169691Skan void 626169691Skan _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); 627132720Skan 628169691Skan void 629169691Skan _M_erase_bucket(const size_type __n, _Node* __last); 630132720Skan 631169691Skan void 632169691Skan _M_copy_from(const hashtable& __ht); 633169691Skan }; 634169691Skan 635169691Skan template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 636169691Skan class _All> 637169691Skan _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 638169691Skan _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 639169691Skan operator++() 640169691Skan { 641169691Skan const _Node* __old = _M_cur; 642169691Skan _M_cur = _M_cur->_M_next; 643169691Skan if (!_M_cur) 644169691Skan { 645169691Skan size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 646169691Skan while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 647169691Skan _M_cur = _M_ht->_M_buckets[__bucket]; 648169691Skan } 649169691Skan return *this; 650132720Skan } 651132720Skan 652169691Skan template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 653169691Skan class _All> 654169691Skan inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 655169691Skan _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 656169691Skan operator++(int) 657169691Skan { 658169691Skan iterator __tmp = *this; 659169691Skan ++*this; 660169691Skan return __tmp; 661169691Skan } 662132720Skan 663169691Skan template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 664169691Skan class _All> 665169691Skan _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 666169691Skan _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 667169691Skan operator++() 668169691Skan { 669169691Skan const _Node* __old = _M_cur; 670169691Skan _M_cur = _M_cur->_M_next; 671169691Skan if (!_M_cur) 672169691Skan { 673169691Skan size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 674169691Skan while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 675169691Skan _M_cur = _M_ht->_M_buckets[__bucket]; 676169691Skan } 677169691Skan return *this; 678169691Skan } 679132720Skan 680169691Skan template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 681169691Skan class _All> 682169691Skan inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 683169691Skan _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 684169691Skan operator++(int) 685169691Skan { 686169691Skan const_iterator __tmp = *this; 687169691Skan ++*this; 688169691Skan return __tmp; 689169691Skan } 690132720Skan 691169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 692169691Skan bool 693169691Skan operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 694169691Skan const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 695169691Skan { 696169691Skan typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node; 697132720Skan 698169691Skan if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) 699169691Skan return false; 700132720Skan 701169691Skan for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) 702169691Skan { 703169691Skan _Node* __cur1 = __ht1._M_buckets[__n]; 704169691Skan _Node* __cur2 = __ht2._M_buckets[__n]; 705169691Skan // Check same length of lists 706169691Skan for (; __cur1 && __cur2; 707169691Skan __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) 708169691Skan { } 709169691Skan if (__cur1 || __cur2) 710169691Skan return false; 711169691Skan // Now check one's elements are in the other 712169691Skan for (__cur1 = __ht1._M_buckets[__n] ; __cur1; 713169691Skan __cur1 = __cur1->_M_next) 714169691Skan { 715169691Skan bool _found__cur1 = false; 716169691Skan for (__cur2 = __ht2._M_buckets[__n]; 717169691Skan __cur2; __cur2 = __cur2->_M_next) 718169691Skan { 719169691Skan if (__cur1->_M_val == __cur2->_M_val) 720169691Skan { 721169691Skan _found__cur1 = true; 722169691Skan break; 723169691Skan } 724169691Skan } 725169691Skan if (!_found__cur1) 726169691Skan return false; 727169691Skan } 728169691Skan } 729169691Skan return true; 730169691Skan } 731132720Skan 732169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 733169691Skan inline bool 734169691Skan operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 735169691Skan const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 736169691Skan { return !(__ht1 == __ht2); } 737169691Skan 738169691Skan template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, 739169691Skan class _All> 740169691Skan inline void 741169691Skan swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, 742169691Skan hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) 743169691Skan { __ht1.swap(__ht2); } 744169691Skan 745169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 746169691Skan pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool> 747169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 748169691Skan insert_unique_noresize(const value_type& __obj) 749169691Skan { 750169691Skan const size_type __n = _M_bkt_num(__obj); 751169691Skan _Node* __first = _M_buckets[__n]; 752169691Skan 753169691Skan for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 754169691Skan if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 755169691Skan return pair<iterator, bool>(iterator(__cur, this), false); 756169691Skan 757169691Skan _Node* __tmp = _M_new_node(__obj); 758169691Skan __tmp->_M_next = __first; 759169691Skan _M_buckets[__n] = __tmp; 760169691Skan ++_M_num_elements; 761169691Skan return pair<iterator, bool>(iterator(__tmp, this), true); 762132720Skan } 763132720Skan 764169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 765169691Skan typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator 766169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 767169691Skan insert_equal_noresize(const value_type& __obj) 768169691Skan { 769169691Skan const size_type __n = _M_bkt_num(__obj); 770169691Skan _Node* __first = _M_buckets[__n]; 771169691Skan 772169691Skan for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 773169691Skan if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 774169691Skan { 775169691Skan _Node* __tmp = _M_new_node(__obj); 776169691Skan __tmp->_M_next = __cur->_M_next; 777169691Skan __cur->_M_next = __tmp; 778169691Skan ++_M_num_elements; 779169691Skan return iterator(__tmp, this); 780169691Skan } 781132720Skan 782169691Skan _Node* __tmp = _M_new_node(__obj); 783169691Skan __tmp->_M_next = __first; 784169691Skan _M_buckets[__n] = __tmp; 785169691Skan ++_M_num_elements; 786169691Skan return iterator(__tmp, this); 787132720Skan } 788132720Skan 789169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 790169691Skan typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference 791169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 792169691Skan find_or_insert(const value_type& __obj) 793169691Skan { 794169691Skan resize(_M_num_elements + 1); 795132720Skan 796169691Skan size_type __n = _M_bkt_num(__obj); 797169691Skan _Node* __first = _M_buckets[__n]; 798169691Skan 799169691Skan for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 800169691Skan if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 801169691Skan return __cur->_M_val; 802169691Skan 803169691Skan _Node* __tmp = _M_new_node(__obj); 804169691Skan __tmp->_M_next = __first; 805169691Skan _M_buckets[__n] = __tmp; 806169691Skan ++_M_num_elements; 807169691Skan return __tmp->_M_val; 808132720Skan } 809169691Skan 810169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 811169691Skan pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, 812169691Skan typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator> 813169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 814169691Skan equal_range(const key_type& __key) 815169691Skan { 816169691Skan typedef pair<iterator, iterator> _Pii; 817169691Skan const size_type __n = _M_bkt_num_key(__key); 818169691Skan 819169691Skan for (_Node* __first = _M_buckets[__n]; __first; 820169691Skan __first = __first->_M_next) 821169691Skan if (_M_equals(_M_get_key(__first->_M_val), __key)) 822169691Skan { 823169691Skan for (_Node* __cur = __first->_M_next; __cur; 824169691Skan __cur = __cur->_M_next) 825169691Skan if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 826169691Skan return _Pii(iterator(__first, this), iterator(__cur, this)); 827169691Skan for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 828169691Skan if (_M_buckets[__m]) 829169691Skan return _Pii(iterator(__first, this), 830169691Skan iterator(_M_buckets[__m], this)); 831169691Skan return _Pii(iterator(__first, this), end()); 832169691Skan } 833169691Skan return _Pii(end(), end()); 834132720Skan } 835132720Skan 836169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 837169691Skan pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator, 838169691Skan typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator> 839169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 840169691Skan equal_range(const key_type& __key) const 841169691Skan { 842169691Skan typedef pair<const_iterator, const_iterator> _Pii; 843169691Skan const size_type __n = _M_bkt_num_key(__key); 844132720Skan 845169691Skan for (const _Node* __first = _M_buckets[__n]; __first; 846169691Skan __first = __first->_M_next) 847169691Skan { 848169691Skan if (_M_equals(_M_get_key(__first->_M_val), __key)) 849169691Skan { 850169691Skan for (const _Node* __cur = __first->_M_next; __cur; 851169691Skan __cur = __cur->_M_next) 852169691Skan if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 853169691Skan return _Pii(const_iterator(__first, this), 854169691Skan const_iterator(__cur, this)); 855169691Skan for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 856169691Skan if (_M_buckets[__m]) 857169691Skan return _Pii(const_iterator(__first, this), 858169691Skan const_iterator(_M_buckets[__m], this)); 859169691Skan return _Pii(const_iterator(__first, this), end()); 860169691Skan } 861169691Skan } 862169691Skan return _Pii(end(), end()); 863132720Skan } 864169691Skan 865169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 866169691Skan typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type 867169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 868169691Skan erase(const key_type& __key) 869169691Skan { 870169691Skan const size_type __n = _M_bkt_num_key(__key); 871169691Skan _Node* __first = _M_buckets[__n]; 872169691Skan size_type __erased = 0; 873169691Skan 874169691Skan if (__first) 875169691Skan { 876169691Skan _Node* __cur = __first; 877169691Skan _Node* __next = __cur->_M_next; 878169691Skan while (__next) 879169691Skan { 880169691Skan if (_M_equals(_M_get_key(__next->_M_val), __key)) 881169691Skan { 882169691Skan __cur->_M_next = __next->_M_next; 883169691Skan _M_delete_node(__next); 884169691Skan __next = __cur->_M_next; 885169691Skan ++__erased; 886169691Skan --_M_num_elements; 887169691Skan } 888169691Skan else 889169691Skan { 890169691Skan __cur = __next; 891169691Skan __next = __cur->_M_next; 892169691Skan } 893169691Skan } 894169691Skan if (_M_equals(_M_get_key(__first->_M_val), __key)) 895169691Skan { 896169691Skan _M_buckets[__n] = __first->_M_next; 897169691Skan _M_delete_node(__first); 898169691Skan ++__erased; 899169691Skan --_M_num_elements; 900169691Skan } 901169691Skan } 902169691Skan return __erased; 903132720Skan } 904132720Skan 905169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 906169691Skan void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 907169691Skan erase(const iterator& __it) 908169691Skan { 909169691Skan _Node* __p = __it._M_cur; 910169691Skan if (__p) 911169691Skan { 912169691Skan const size_type __n = _M_bkt_num(__p->_M_val); 913169691Skan _Node* __cur = _M_buckets[__n]; 914169691Skan 915169691Skan if (__cur == __p) 916169691Skan { 917169691Skan _M_buckets[__n] = __cur->_M_next; 918169691Skan _M_delete_node(__cur); 919169691Skan --_M_num_elements; 920169691Skan } 921169691Skan else 922169691Skan { 923169691Skan _Node* __next = __cur->_M_next; 924169691Skan while (__next) 925169691Skan { 926169691Skan if (__next == __p) 927169691Skan { 928169691Skan __cur->_M_next = __next->_M_next; 929169691Skan _M_delete_node(__next); 930169691Skan --_M_num_elements; 931169691Skan break; 932169691Skan } 933169691Skan else 934169691Skan { 935169691Skan __cur = __next; 936169691Skan __next = __cur->_M_next; 937169691Skan } 938169691Skan } 939169691Skan } 940169691Skan } 941169691Skan } 942132720Skan 943169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 944169691Skan void 945169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 946169691Skan erase(iterator __first, iterator __last) 947169691Skan { 948169691Skan size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) 949169691Skan : _M_buckets.size(); 950132720Skan 951169691Skan size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) 952169691Skan : _M_buckets.size(); 953132720Skan 954169691Skan if (__first._M_cur == __last._M_cur) 955169691Skan return; 956169691Skan else if (__f_bucket == __l_bucket) 957169691Skan _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); 958169691Skan else 959169691Skan { 960169691Skan _M_erase_bucket(__f_bucket, __first._M_cur, 0); 961169691Skan for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) 962169691Skan _M_erase_bucket(__n, 0); 963169691Skan if (__l_bucket != _M_buckets.size()) 964169691Skan _M_erase_bucket(__l_bucket, __last._M_cur); 965169691Skan } 966132720Skan } 967132720Skan 968169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 969169691Skan inline void 970169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 971169691Skan erase(const_iterator __first, const_iterator __last) 972169691Skan { 973169691Skan erase(iterator(const_cast<_Node*>(__first._M_cur), 974169691Skan const_cast<hashtable*>(__first._M_ht)), 975169691Skan iterator(const_cast<_Node*>(__last._M_cur), 976169691Skan const_cast<hashtable*>(__last._M_ht))); 977132720Skan } 978132720Skan 979169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 980169691Skan inline void 981169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 982169691Skan erase(const const_iterator& __it) 983169691Skan { erase(iterator(const_cast<_Node*>(__it._M_cur), 984169691Skan const_cast<hashtable*>(__it._M_ht))); } 985132720Skan 986169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 987169691Skan void 988169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 989169691Skan resize(size_type __num_elements_hint) 990169691Skan { 991169691Skan const size_type __old_n = _M_buckets.size(); 992169691Skan if (__num_elements_hint > __old_n) 993169691Skan { 994169691Skan const size_type __n = _M_next_size(__num_elements_hint); 995169691Skan if (__n > __old_n) 996169691Skan { 997169691Skan _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator()); 998169691Skan try 999169691Skan { 1000169691Skan for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) 1001169691Skan { 1002169691Skan _Node* __first = _M_buckets[__bucket]; 1003169691Skan while (__first) 1004169691Skan { 1005169691Skan size_type __new_bucket = _M_bkt_num(__first->_M_val, 1006169691Skan __n); 1007169691Skan _M_buckets[__bucket] = __first->_M_next; 1008169691Skan __first->_M_next = __tmp[__new_bucket]; 1009169691Skan __tmp[__new_bucket] = __first; 1010169691Skan __first = _M_buckets[__bucket]; 1011169691Skan } 1012169691Skan } 1013169691Skan _M_buckets.swap(__tmp); 1014169691Skan } 1015169691Skan catch(...) 1016169691Skan { 1017169691Skan for (size_type __bucket = 0; __bucket < __tmp.size(); 1018169691Skan ++__bucket) 1019169691Skan { 1020169691Skan while (__tmp[__bucket]) 1021169691Skan { 1022169691Skan _Node* __next = __tmp[__bucket]->_M_next; 1023169691Skan _M_delete_node(__tmp[__bucket]); 1024169691Skan __tmp[__bucket] = __next; 1025169691Skan } 1026169691Skan } 1027169691Skan __throw_exception_again; 1028169691Skan } 1029169691Skan } 1030169691Skan } 1031132720Skan } 1032132720Skan 1033169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1034169691Skan void 1035169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1036169691Skan _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) 1037169691Skan { 1038169691Skan _Node* __cur = _M_buckets[__n]; 1039169691Skan if (__cur == __first) 1040169691Skan _M_erase_bucket(__n, __last); 1041169691Skan else 1042169691Skan { 1043169691Skan _Node* __next; 1044169691Skan for (__next = __cur->_M_next; 1045169691Skan __next != __first; 1046169691Skan __cur = __next, __next = __cur->_M_next) 1047169691Skan ; 1048169691Skan while (__next != __last) 1049169691Skan { 1050169691Skan __cur->_M_next = __next->_M_next; 1051169691Skan _M_delete_node(__next); 1052169691Skan __next = __cur->_M_next; 1053169691Skan --_M_num_elements; 1054169691Skan } 1055169691Skan } 1056169691Skan } 1057132720Skan 1058169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1059169691Skan void 1060169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1061169691Skan _M_erase_bucket(const size_type __n, _Node* __last) 1062169691Skan { 1063169691Skan _Node* __cur = _M_buckets[__n]; 1064169691Skan while (__cur != __last) 1065169691Skan { 1066169691Skan _Node* __next = __cur->_M_next; 1067169691Skan _M_delete_node(__cur); 1068169691Skan __cur = __next; 1069169691Skan _M_buckets[__n] = __cur; 1070169691Skan --_M_num_elements; 1071169691Skan } 1072169691Skan } 1073132720Skan 1074169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1075169691Skan void 1076169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1077169691Skan clear() 1078169691Skan { 1079169691Skan for (size_type __i = 0; __i < _M_buckets.size(); ++__i) 1080169691Skan { 1081169691Skan _Node* __cur = _M_buckets[__i]; 1082169691Skan while (__cur != 0) 1083169691Skan { 1084169691Skan _Node* __next = __cur->_M_next; 1085169691Skan _M_delete_node(__cur); 1086169691Skan __cur = __next; 1087169691Skan } 1088169691Skan _M_buckets[__i] = 0; 1089169691Skan } 1090169691Skan _M_num_elements = 0; 1091132720Skan } 1092169691Skan 1093169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1094169691Skan void 1095169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1096169691Skan _M_copy_from(const hashtable& __ht) 1097132720Skan { 1098169691Skan _M_buckets.clear(); 1099169691Skan _M_buckets.reserve(__ht._M_buckets.size()); 1100169691Skan _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); 1101169691Skan try 1102169691Skan { 1103169691Skan for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { 1104169691Skan const _Node* __cur = __ht._M_buckets[__i]; 1105169691Skan if (__cur) 1106169691Skan { 1107169691Skan _Node* __local_copy = _M_new_node(__cur->_M_val); 1108169691Skan _M_buckets[__i] = __local_copy; 1109169691Skan 1110169691Skan for (_Node* __next = __cur->_M_next; 1111169691Skan __next; 1112169691Skan __cur = __next, __next = __cur->_M_next) 1113169691Skan { 1114169691Skan __local_copy->_M_next = _M_new_node(__next->_M_val); 1115169691Skan __local_copy = __local_copy->_M_next; 1116169691Skan } 1117169691Skan } 1118169691Skan } 1119169691Skan _M_num_elements = __ht._M_num_elements; 1120169691Skan } 1121169691Skan catch(...) 1122169691Skan { 1123169691Skan clear(); 1124169691Skan __throw_exception_again; 1125169691Skan } 1126132720Skan } 1127132720Skan 1128169691Skan_GLIBCXX_END_NAMESPACE 1129169691Skan 1130132720Skan#endif 1131