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. 213259405Spfg enum { _S_num_primes = 29 }; 214132720Skan 215169691Skan static const unsigned long __stl_prime_list[_S_num_primes] = 216169691Skan { 217259405Spfg 5ul, // 5ul mini size is a Google addition 218169691Skan 53ul, 97ul, 193ul, 389ul, 769ul, 219169691Skan 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 220169691Skan 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 221169691Skan 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 222169691Skan 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 223169691Skan 1610612741ul, 3221225473ul, 4294967291ul 224169691Skan }; 225132720Skan 226169691Skan inline unsigned long 227169691Skan __stl_next_prime(unsigned long __n) 228169691Skan { 229169691Skan const unsigned long* __first = __stl_prime_list; 230169691Skan const unsigned long* __last = __stl_prime_list + (int)_S_num_primes; 231169691Skan const unsigned long* pos = std::lower_bound(__first, __last, __n); 232169691Skan return pos == __last ? *(__last - 1) : *pos; 233169691Skan } 234132720Skan 235169691Skan // Forward declaration of operator==. 236169691Skan template<class _Val, class _Key, class _HF, class _Ex, 237169691Skan class _Eq, class _All> 238169691Skan class hashtable; 239132720Skan 240169691Skan template<class _Val, class _Key, class _HF, class _Ex, 241169691Skan class _Eq, class _All> 242169691Skan bool 243169691Skan operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 244169691Skan const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2); 245132720Skan 246169691Skan // Hashtables handle allocators a bit differently than other 247169691Skan // containers do. If we're using standard-conforming allocators, then 248169691Skan // a hashtable unconditionally has a member variable to hold its 249169691Skan // allocator, even if it so happens that all instances of the 250169691Skan // allocator type are identical. This is because, for hashtables, 251169691Skan // this extra storage is negligible. Additionally, a base class 252169691Skan // wouldn't serve any other purposes; it wouldn't, for example, 253169691Skan // simplify the exception-handling code. 254169691Skan template<class _Val, class _Key, class _HashFcn, 255169691Skan class _ExtractKey, class _EqualKey, class _Alloc> 256169691Skan class hashtable 257169691Skan { 258169691Skan public: 259169691Skan typedef _Key key_type; 260169691Skan typedef _Val value_type; 261169691Skan typedef _HashFcn hasher; 262169691Skan typedef _EqualKey key_equal; 263132720Skan 264169691Skan typedef size_t size_type; 265169691Skan typedef ptrdiff_t difference_type; 266169691Skan typedef value_type* pointer; 267169691Skan typedef const value_type* const_pointer; 268169691Skan typedef value_type& reference; 269169691Skan typedef const value_type& const_reference; 270132720Skan 271169691Skan hasher 272169691Skan hash_funct() const 273169691Skan { return _M_hash; } 274132720Skan 275169691Skan key_equal 276169691Skan key_eq() const 277169691Skan { return _M_equals; } 278132720Skan 279169691Skan private: 280169691Skan typedef _Hashtable_node<_Val> _Node; 281132720Skan 282169691Skan public: 283169691Skan typedef typename _Alloc::template rebind<value_type>::other allocator_type; 284169691Skan allocator_type 285169691Skan get_allocator() const 286169691Skan { return _M_node_allocator; } 287132720Skan 288169691Skan private: 289169691Skan typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc; 290169691Skan typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc; 291169691Skan typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type; 292132720Skan 293169691Skan _Node_Alloc _M_node_allocator; 294132720Skan 295169691Skan _Node* 296169691Skan _M_get_node() 297169691Skan { return _M_node_allocator.allocate(1); } 298132720Skan 299169691Skan void 300169691Skan _M_put_node(_Node* __p) 301169691Skan { _M_node_allocator.deallocate(__p, 1); } 302132720Skan 303169691Skan private: 304169691Skan hasher _M_hash; 305169691Skan key_equal _M_equals; 306169691Skan _ExtractKey _M_get_key; 307169691Skan _Vector_type _M_buckets; 308169691Skan size_type _M_num_elements; 309169691Skan 310169691Skan public: 311169691Skan typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, 312169691Skan _EqualKey, _Alloc> 313169691Skan iterator; 314169691Skan typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 315169691Skan _EqualKey, _Alloc> 316169691Skan const_iterator; 317132720Skan 318169691Skan friend struct 319169691Skan _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>; 320132720Skan 321169691Skan friend struct 322169691Skan _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 323169691Skan _EqualKey, _Alloc>; 324132720Skan 325169691Skan public: 326169691Skan hashtable(size_type __n, const _HashFcn& __hf, 327169691Skan const _EqualKey& __eql, const _ExtractKey& __ext, 328169691Skan const allocator_type& __a = allocator_type()) 329169691Skan : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 330169691Skan _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0) 331169691Skan { _M_initialize_buckets(__n); } 332132720Skan 333169691Skan hashtable(size_type __n, const _HashFcn& __hf, 334169691Skan const _EqualKey& __eql, 335169691Skan const allocator_type& __a = allocator_type()) 336169691Skan : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 337169691Skan _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0) 338169691Skan { _M_initialize_buckets(__n); } 339132720Skan 340169691Skan hashtable(const hashtable& __ht) 341169691Skan : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash), 342169691Skan _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key), 343169691Skan _M_buckets(__ht.get_allocator()), _M_num_elements(0) 344169691Skan { _M_copy_from(__ht); } 345132720Skan 346169691Skan hashtable& 347169691Skan operator= (const hashtable& __ht) 348169691Skan { 349169691Skan if (&__ht != this) 350169691Skan { 351169691Skan clear(); 352169691Skan _M_hash = __ht._M_hash; 353169691Skan _M_equals = __ht._M_equals; 354169691Skan _M_get_key = __ht._M_get_key; 355169691Skan _M_copy_from(__ht); 356169691Skan } 357169691Skan return *this; 358169691Skan } 359132720Skan 360169691Skan ~hashtable() 361169691Skan { clear(); } 362132720Skan 363169691Skan size_type 364169691Skan size() const 365169691Skan { return _M_num_elements; } 366132720Skan 367169691Skan size_type 368169691Skan max_size() const 369169691Skan { return size_type(-1); } 370132720Skan 371169691Skan bool 372169691Skan empty() const 373169691Skan { return size() == 0; } 374132720Skan 375169691Skan void 376169691Skan swap(hashtable& __ht) 377169691Skan { 378169691Skan std::swap(_M_hash, __ht._M_hash); 379169691Skan std::swap(_M_equals, __ht._M_equals); 380169691Skan std::swap(_M_get_key, __ht._M_get_key); 381169691Skan _M_buckets.swap(__ht._M_buckets); 382169691Skan std::swap(_M_num_elements, __ht._M_num_elements); 383169691Skan } 384132720Skan 385169691Skan iterator 386169691Skan begin() 387169691Skan { 388169691Skan for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 389169691Skan if (_M_buckets[__n]) 390169691Skan return iterator(_M_buckets[__n], this); 391169691Skan return end(); 392169691Skan } 393132720Skan 394169691Skan iterator 395169691Skan end() 396169691Skan { return iterator(0, this); } 397132720Skan 398169691Skan const_iterator 399169691Skan begin() const 400169691Skan { 401169691Skan for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 402169691Skan if (_M_buckets[__n]) 403169691Skan return const_iterator(_M_buckets[__n], this); 404169691Skan return end(); 405169691Skan } 406132720Skan 407169691Skan const_iterator 408169691Skan end() const 409169691Skan { return const_iterator(0, this); } 410132720Skan 411169691Skan template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, 412169691Skan class _Al> 413169691Skan friend bool 414169691Skan operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, 415169691Skan const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); 416132720Skan 417169691Skan public: 418169691Skan size_type 419169691Skan bucket_count() const 420169691Skan { return _M_buckets.size(); } 421132720Skan 422169691Skan size_type 423169691Skan max_bucket_count() const 424169691Skan { return __stl_prime_list[(int)_S_num_primes - 1]; } 425132720Skan 426169691Skan size_type 427169691Skan elems_in_bucket(size_type __bucket) const 428169691Skan { 429169691Skan size_type __result = 0; 430169691Skan for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next) 431169691Skan __result += 1; 432169691Skan return __result; 433169691Skan } 434132720Skan 435169691Skan pair<iterator, bool> 436169691Skan insert_unique(const value_type& __obj) 437169691Skan { 438169691Skan resize(_M_num_elements + 1); 439169691Skan return insert_unique_noresize(__obj); 440169691Skan } 441132720Skan 442169691Skan iterator 443169691Skan insert_equal(const value_type& __obj) 444169691Skan { 445169691Skan resize(_M_num_elements + 1); 446169691Skan return insert_equal_noresize(__obj); 447169691Skan } 448132720Skan 449169691Skan pair<iterator, bool> 450169691Skan insert_unique_noresize(const value_type& __obj); 451132720Skan 452169691Skan iterator 453169691Skan insert_equal_noresize(const value_type& __obj); 454132720Skan 455169691Skan template<class _InputIterator> 456169691Skan void 457169691Skan insert_unique(_InputIterator __f, _InputIterator __l) 458169691Skan { insert_unique(__f, __l, __iterator_category(__f)); } 459132720Skan 460169691Skan template<class _InputIterator> 461169691Skan void 462169691Skan insert_equal(_InputIterator __f, _InputIterator __l) 463169691Skan { insert_equal(__f, __l, __iterator_category(__f)); } 464132720Skan 465169691Skan template<class _InputIterator> 466169691Skan void 467169691Skan insert_unique(_InputIterator __f, _InputIterator __l, 468169691Skan input_iterator_tag) 469169691Skan { 470169691Skan for ( ; __f != __l; ++__f) 471169691Skan insert_unique(*__f); 472169691Skan } 473132720Skan 474169691Skan template<class _InputIterator> 475169691Skan void 476169691Skan insert_equal(_InputIterator __f, _InputIterator __l, 477169691Skan input_iterator_tag) 478169691Skan { 479169691Skan for ( ; __f != __l; ++__f) 480169691Skan insert_equal(*__f); 481169691Skan } 482132720Skan 483169691Skan template<class _ForwardIterator> 484169691Skan void 485169691Skan insert_unique(_ForwardIterator __f, _ForwardIterator __l, 486169691Skan forward_iterator_tag) 487169691Skan { 488169691Skan size_type __n = distance(__f, __l); 489169691Skan resize(_M_num_elements + __n); 490169691Skan for ( ; __n > 0; --__n, ++__f) 491169691Skan insert_unique_noresize(*__f); 492169691Skan } 493132720Skan 494169691Skan template<class _ForwardIterator> 495169691Skan void 496169691Skan insert_equal(_ForwardIterator __f, _ForwardIterator __l, 497169691Skan forward_iterator_tag) 498169691Skan { 499169691Skan size_type __n = distance(__f, __l); 500169691Skan resize(_M_num_elements + __n); 501169691Skan for ( ; __n > 0; --__n, ++__f) 502169691Skan insert_equal_noresize(*__f); 503169691Skan } 504132720Skan 505169691Skan reference 506169691Skan find_or_insert(const value_type& __obj); 507169691Skan 508169691Skan iterator 509169691Skan find(const key_type& __key) 510132720Skan { 511169691Skan size_type __n = _M_bkt_num_key(__key); 512169691Skan _Node* __first; 513169691Skan for (__first = _M_buckets[__n]; 514169691Skan __first && !_M_equals(_M_get_key(__first->_M_val), __key); 515169691Skan __first = __first->_M_next) 516169691Skan { } 517169691Skan return iterator(__first, this); 518132720Skan } 519132720Skan 520169691Skan const_iterator 521169691Skan find(const key_type& __key) const 522169691Skan { 523169691Skan size_type __n = _M_bkt_num_key(__key); 524169691Skan const _Node* __first; 525169691Skan for (__first = _M_buckets[__n]; 526169691Skan __first && !_M_equals(_M_get_key(__first->_M_val), __key); 527169691Skan __first = __first->_M_next) 528169691Skan { } 529169691Skan return const_iterator(__first, this); 530169691Skan } 531132720Skan 532169691Skan size_type 533169691Skan count(const key_type& __key) const 534169691Skan { 535169691Skan const size_type __n = _M_bkt_num_key(__key); 536169691Skan size_type __result = 0; 537169691Skan 538169691Skan for (const _Node* __cur = _M_buckets[__n]; __cur; 539169691Skan __cur = __cur->_M_next) 540169691Skan if (_M_equals(_M_get_key(__cur->_M_val), __key)) 541169691Skan ++__result; 542169691Skan return __result; 543169691Skan } 544132720Skan 545169691Skan pair<iterator, iterator> 546169691Skan equal_range(const key_type& __key); 547132720Skan 548169691Skan pair<const_iterator, const_iterator> 549169691Skan equal_range(const key_type& __key) const; 550132720Skan 551169691Skan size_type 552169691Skan erase(const key_type& __key); 553169691Skan 554169691Skan void 555169691Skan erase(const iterator& __it); 556132720Skan 557169691Skan void 558169691Skan erase(iterator __first, iterator __last); 559132720Skan 560169691Skan void 561169691Skan erase(const const_iterator& __it); 562132720Skan 563169691Skan void 564169691Skan erase(const_iterator __first, const_iterator __last); 565132720Skan 566169691Skan void 567169691Skan resize(size_type __num_elements_hint); 568169691Skan 569169691Skan void 570169691Skan clear(); 571169691Skan 572169691Skan private: 573169691Skan size_type 574169691Skan _M_next_size(size_type __n) const 575169691Skan { return __stl_next_prime(__n); } 576169691Skan 577169691Skan void 578169691Skan _M_initialize_buckets(size_type __n) 579132720Skan { 580169691Skan const size_type __n_buckets = _M_next_size(__n); 581169691Skan _M_buckets.reserve(__n_buckets); 582169691Skan _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); 583169691Skan _M_num_elements = 0; 584132720Skan } 585132720Skan 586169691Skan size_type 587169691Skan _M_bkt_num_key(const key_type& __key) const 588169691Skan { return _M_bkt_num_key(__key, _M_buckets.size()); } 589132720Skan 590169691Skan size_type 591169691Skan _M_bkt_num(const value_type& __obj) const 592169691Skan { return _M_bkt_num_key(_M_get_key(__obj)); } 593132720Skan 594169691Skan size_type 595169691Skan _M_bkt_num_key(const key_type& __key, size_t __n) const 596169691Skan { return _M_hash(__key) % __n; } 597132720Skan 598169691Skan size_type 599169691Skan _M_bkt_num(const value_type& __obj, size_t __n) const 600169691Skan { return _M_bkt_num_key(_M_get_key(__obj), __n); } 601132720Skan 602169691Skan _Node* 603169691Skan _M_new_node(const value_type& __obj) 604169691Skan { 605169691Skan _Node* __n = _M_get_node(); 606169691Skan __n->_M_next = 0; 607169691Skan try 608169691Skan { 609169691Skan this->get_allocator().construct(&__n->_M_val, __obj); 610169691Skan return __n; 611169691Skan } 612169691Skan catch(...) 613169691Skan { 614169691Skan _M_put_node(__n); 615169691Skan __throw_exception_again; 616169691Skan } 617169691Skan } 618132720Skan 619169691Skan void 620169691Skan _M_delete_node(_Node* __n) 621169691Skan { 622169691Skan this->get_allocator().destroy(&__n->_M_val); 623169691Skan _M_put_node(__n); 624169691Skan } 625169691Skan 626169691Skan void 627169691Skan _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); 628132720Skan 629169691Skan void 630169691Skan _M_erase_bucket(const size_type __n, _Node* __last); 631132720Skan 632169691Skan void 633169691Skan _M_copy_from(const hashtable& __ht); 634169691Skan }; 635169691Skan 636169691Skan template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 637169691Skan class _All> 638169691Skan _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 639169691Skan _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 640169691Skan operator++() 641169691Skan { 642169691Skan const _Node* __old = _M_cur; 643169691Skan _M_cur = _M_cur->_M_next; 644169691Skan if (!_M_cur) 645169691Skan { 646169691Skan size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 647169691Skan while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 648169691Skan _M_cur = _M_ht->_M_buckets[__bucket]; 649169691Skan } 650169691Skan return *this; 651132720Skan } 652132720Skan 653169691Skan template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 654169691Skan class _All> 655169691Skan inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 656169691Skan _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 657169691Skan operator++(int) 658169691Skan { 659169691Skan iterator __tmp = *this; 660169691Skan ++*this; 661169691Skan return __tmp; 662169691Skan } 663132720Skan 664169691Skan template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 665169691Skan class _All> 666169691Skan _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 667169691Skan _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 668169691Skan operator++() 669169691Skan { 670169691Skan const _Node* __old = _M_cur; 671169691Skan _M_cur = _M_cur->_M_next; 672169691Skan if (!_M_cur) 673169691Skan { 674169691Skan size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 675169691Skan while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 676169691Skan _M_cur = _M_ht->_M_buckets[__bucket]; 677169691Skan } 678169691Skan return *this; 679169691Skan } 680132720Skan 681169691Skan template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 682169691Skan class _All> 683169691Skan inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 684169691Skan _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 685169691Skan operator++(int) 686169691Skan { 687169691Skan const_iterator __tmp = *this; 688169691Skan ++*this; 689169691Skan return __tmp; 690169691Skan } 691132720Skan 692169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 693169691Skan bool 694169691Skan operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 695169691Skan const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 696169691Skan { 697169691Skan typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node; 698132720Skan 699169691Skan if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) 700169691Skan return false; 701132720Skan 702169691Skan for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) 703169691Skan { 704169691Skan _Node* __cur1 = __ht1._M_buckets[__n]; 705169691Skan _Node* __cur2 = __ht2._M_buckets[__n]; 706169691Skan // Check same length of lists 707169691Skan for (; __cur1 && __cur2; 708169691Skan __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) 709169691Skan { } 710169691Skan if (__cur1 || __cur2) 711169691Skan return false; 712169691Skan // Now check one's elements are in the other 713169691Skan for (__cur1 = __ht1._M_buckets[__n] ; __cur1; 714169691Skan __cur1 = __cur1->_M_next) 715169691Skan { 716169691Skan bool _found__cur1 = false; 717169691Skan for (__cur2 = __ht2._M_buckets[__n]; 718169691Skan __cur2; __cur2 = __cur2->_M_next) 719169691Skan { 720169691Skan if (__cur1->_M_val == __cur2->_M_val) 721169691Skan { 722169691Skan _found__cur1 = true; 723169691Skan break; 724169691Skan } 725169691Skan } 726169691Skan if (!_found__cur1) 727169691Skan return false; 728169691Skan } 729169691Skan } 730169691Skan return true; 731169691Skan } 732132720Skan 733169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 734169691Skan inline bool 735169691Skan operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 736169691Skan const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 737169691Skan { return !(__ht1 == __ht2); } 738169691Skan 739169691Skan template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, 740169691Skan class _All> 741169691Skan inline void 742169691Skan swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, 743169691Skan hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) 744169691Skan { __ht1.swap(__ht2); } 745169691Skan 746169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 747169691Skan pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool> 748169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 749169691Skan insert_unique_noresize(const value_type& __obj) 750169691Skan { 751169691Skan const size_type __n = _M_bkt_num(__obj); 752169691Skan _Node* __first = _M_buckets[__n]; 753169691Skan 754169691Skan for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 755169691Skan if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 756169691Skan return pair<iterator, bool>(iterator(__cur, this), false); 757169691Skan 758169691Skan _Node* __tmp = _M_new_node(__obj); 759169691Skan __tmp->_M_next = __first; 760169691Skan _M_buckets[__n] = __tmp; 761169691Skan ++_M_num_elements; 762169691Skan return pair<iterator, bool>(iterator(__tmp, this), true); 763132720Skan } 764132720Skan 765169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 766169691Skan typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator 767169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 768169691Skan insert_equal_noresize(const value_type& __obj) 769169691Skan { 770169691Skan const size_type __n = _M_bkt_num(__obj); 771169691Skan _Node* __first = _M_buckets[__n]; 772169691Skan 773169691Skan for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 774169691Skan if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 775169691Skan { 776169691Skan _Node* __tmp = _M_new_node(__obj); 777169691Skan __tmp->_M_next = __cur->_M_next; 778169691Skan __cur->_M_next = __tmp; 779169691Skan ++_M_num_elements; 780169691Skan return iterator(__tmp, this); 781169691Skan } 782132720Skan 783169691Skan _Node* __tmp = _M_new_node(__obj); 784169691Skan __tmp->_M_next = __first; 785169691Skan _M_buckets[__n] = __tmp; 786169691Skan ++_M_num_elements; 787169691Skan return iterator(__tmp, this); 788132720Skan } 789132720Skan 790169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 791169691Skan typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference 792169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 793169691Skan find_or_insert(const value_type& __obj) 794169691Skan { 795169691Skan resize(_M_num_elements + 1); 796132720Skan 797169691Skan size_type __n = _M_bkt_num(__obj); 798169691Skan _Node* __first = _M_buckets[__n]; 799169691Skan 800169691Skan for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 801169691Skan if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 802169691Skan return __cur->_M_val; 803169691Skan 804169691Skan _Node* __tmp = _M_new_node(__obj); 805169691Skan __tmp->_M_next = __first; 806169691Skan _M_buckets[__n] = __tmp; 807169691Skan ++_M_num_elements; 808169691Skan return __tmp->_M_val; 809132720Skan } 810169691Skan 811169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 812169691Skan pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, 813169691Skan typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator> 814169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 815169691Skan equal_range(const key_type& __key) 816169691Skan { 817169691Skan typedef pair<iterator, iterator> _Pii; 818169691Skan const size_type __n = _M_bkt_num_key(__key); 819169691Skan 820169691Skan for (_Node* __first = _M_buckets[__n]; __first; 821169691Skan __first = __first->_M_next) 822169691Skan if (_M_equals(_M_get_key(__first->_M_val), __key)) 823169691Skan { 824169691Skan for (_Node* __cur = __first->_M_next; __cur; 825169691Skan __cur = __cur->_M_next) 826169691Skan if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 827169691Skan return _Pii(iterator(__first, this), iterator(__cur, this)); 828169691Skan for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 829169691Skan if (_M_buckets[__m]) 830169691Skan return _Pii(iterator(__first, this), 831169691Skan iterator(_M_buckets[__m], this)); 832169691Skan return _Pii(iterator(__first, this), end()); 833169691Skan } 834169691Skan return _Pii(end(), end()); 835132720Skan } 836132720Skan 837169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 838169691Skan pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator, 839169691Skan typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator> 840169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 841169691Skan equal_range(const key_type& __key) const 842169691Skan { 843169691Skan typedef pair<const_iterator, const_iterator> _Pii; 844169691Skan const size_type __n = _M_bkt_num_key(__key); 845132720Skan 846169691Skan for (const _Node* __first = _M_buckets[__n]; __first; 847169691Skan __first = __first->_M_next) 848169691Skan { 849169691Skan if (_M_equals(_M_get_key(__first->_M_val), __key)) 850169691Skan { 851169691Skan for (const _Node* __cur = __first->_M_next; __cur; 852169691Skan __cur = __cur->_M_next) 853169691Skan if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 854169691Skan return _Pii(const_iterator(__first, this), 855169691Skan const_iterator(__cur, this)); 856169691Skan for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 857169691Skan if (_M_buckets[__m]) 858169691Skan return _Pii(const_iterator(__first, this), 859169691Skan const_iterator(_M_buckets[__m], this)); 860169691Skan return _Pii(const_iterator(__first, this), end()); 861169691Skan } 862169691Skan } 863169691Skan return _Pii(end(), end()); 864132720Skan } 865169691Skan 866169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 867169691Skan typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type 868169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 869169691Skan erase(const key_type& __key) 870169691Skan { 871169691Skan const size_type __n = _M_bkt_num_key(__key); 872169691Skan _Node* __first = _M_buckets[__n]; 873169691Skan size_type __erased = 0; 874169691Skan 875169691Skan if (__first) 876169691Skan { 877169691Skan _Node* __cur = __first; 878169691Skan _Node* __next = __cur->_M_next; 879169691Skan while (__next) 880169691Skan { 881169691Skan if (_M_equals(_M_get_key(__next->_M_val), __key)) 882169691Skan { 883169691Skan __cur->_M_next = __next->_M_next; 884169691Skan _M_delete_node(__next); 885169691Skan __next = __cur->_M_next; 886169691Skan ++__erased; 887169691Skan --_M_num_elements; 888169691Skan } 889169691Skan else 890169691Skan { 891169691Skan __cur = __next; 892169691Skan __next = __cur->_M_next; 893169691Skan } 894169691Skan } 895169691Skan if (_M_equals(_M_get_key(__first->_M_val), __key)) 896169691Skan { 897169691Skan _M_buckets[__n] = __first->_M_next; 898169691Skan _M_delete_node(__first); 899169691Skan ++__erased; 900169691Skan --_M_num_elements; 901169691Skan } 902169691Skan } 903169691Skan return __erased; 904132720Skan } 905132720Skan 906169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 907169691Skan void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 908169691Skan erase(const iterator& __it) 909169691Skan { 910169691Skan _Node* __p = __it._M_cur; 911169691Skan if (__p) 912169691Skan { 913169691Skan const size_type __n = _M_bkt_num(__p->_M_val); 914169691Skan _Node* __cur = _M_buckets[__n]; 915169691Skan 916169691Skan if (__cur == __p) 917169691Skan { 918169691Skan _M_buckets[__n] = __cur->_M_next; 919169691Skan _M_delete_node(__cur); 920169691Skan --_M_num_elements; 921169691Skan } 922169691Skan else 923169691Skan { 924169691Skan _Node* __next = __cur->_M_next; 925169691Skan while (__next) 926169691Skan { 927169691Skan if (__next == __p) 928169691Skan { 929169691Skan __cur->_M_next = __next->_M_next; 930169691Skan _M_delete_node(__next); 931169691Skan --_M_num_elements; 932169691Skan break; 933169691Skan } 934169691Skan else 935169691Skan { 936169691Skan __cur = __next; 937169691Skan __next = __cur->_M_next; 938169691Skan } 939169691Skan } 940169691Skan } 941169691Skan } 942169691Skan } 943132720Skan 944169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 945169691Skan void 946169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 947169691Skan erase(iterator __first, iterator __last) 948169691Skan { 949169691Skan size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) 950169691Skan : _M_buckets.size(); 951132720Skan 952169691Skan size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) 953169691Skan : _M_buckets.size(); 954132720Skan 955169691Skan if (__first._M_cur == __last._M_cur) 956169691Skan return; 957169691Skan else if (__f_bucket == __l_bucket) 958169691Skan _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); 959169691Skan else 960169691Skan { 961169691Skan _M_erase_bucket(__f_bucket, __first._M_cur, 0); 962169691Skan for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) 963169691Skan _M_erase_bucket(__n, 0); 964169691Skan if (__l_bucket != _M_buckets.size()) 965169691Skan _M_erase_bucket(__l_bucket, __last._M_cur); 966169691Skan } 967132720Skan } 968132720Skan 969169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 970169691Skan inline void 971169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 972169691Skan erase(const_iterator __first, const_iterator __last) 973169691Skan { 974169691Skan erase(iterator(const_cast<_Node*>(__first._M_cur), 975169691Skan const_cast<hashtable*>(__first._M_ht)), 976169691Skan iterator(const_cast<_Node*>(__last._M_cur), 977169691Skan const_cast<hashtable*>(__last._M_ht))); 978132720Skan } 979132720Skan 980169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 981169691Skan inline void 982169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 983169691Skan erase(const const_iterator& __it) 984169691Skan { erase(iterator(const_cast<_Node*>(__it._M_cur), 985169691Skan const_cast<hashtable*>(__it._M_ht))); } 986132720Skan 987169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 988169691Skan void 989169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 990169691Skan resize(size_type __num_elements_hint) 991169691Skan { 992169691Skan const size_type __old_n = _M_buckets.size(); 993169691Skan if (__num_elements_hint > __old_n) 994169691Skan { 995169691Skan const size_type __n = _M_next_size(__num_elements_hint); 996169691Skan if (__n > __old_n) 997169691Skan { 998169691Skan _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator()); 999169691Skan try 1000169691Skan { 1001169691Skan for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) 1002169691Skan { 1003169691Skan _Node* __first = _M_buckets[__bucket]; 1004169691Skan while (__first) 1005169691Skan { 1006169691Skan size_type __new_bucket = _M_bkt_num(__first->_M_val, 1007169691Skan __n); 1008169691Skan _M_buckets[__bucket] = __first->_M_next; 1009169691Skan __first->_M_next = __tmp[__new_bucket]; 1010169691Skan __tmp[__new_bucket] = __first; 1011169691Skan __first = _M_buckets[__bucket]; 1012169691Skan } 1013169691Skan } 1014169691Skan _M_buckets.swap(__tmp); 1015169691Skan } 1016169691Skan catch(...) 1017169691Skan { 1018169691Skan for (size_type __bucket = 0; __bucket < __tmp.size(); 1019169691Skan ++__bucket) 1020169691Skan { 1021169691Skan while (__tmp[__bucket]) 1022169691Skan { 1023169691Skan _Node* __next = __tmp[__bucket]->_M_next; 1024169691Skan _M_delete_node(__tmp[__bucket]); 1025169691Skan __tmp[__bucket] = __next; 1026169691Skan } 1027169691Skan } 1028169691Skan __throw_exception_again; 1029169691Skan } 1030169691Skan } 1031169691Skan } 1032132720Skan } 1033132720Skan 1034169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1035169691Skan void 1036169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1037169691Skan _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) 1038169691Skan { 1039169691Skan _Node* __cur = _M_buckets[__n]; 1040169691Skan if (__cur == __first) 1041169691Skan _M_erase_bucket(__n, __last); 1042169691Skan else 1043169691Skan { 1044169691Skan _Node* __next; 1045169691Skan for (__next = __cur->_M_next; 1046169691Skan __next != __first; 1047169691Skan __cur = __next, __next = __cur->_M_next) 1048169691Skan ; 1049169691Skan while (__next != __last) 1050169691Skan { 1051169691Skan __cur->_M_next = __next->_M_next; 1052169691Skan _M_delete_node(__next); 1053169691Skan __next = __cur->_M_next; 1054169691Skan --_M_num_elements; 1055169691Skan } 1056169691Skan } 1057169691Skan } 1058132720Skan 1059169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1060169691Skan void 1061169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1062169691Skan _M_erase_bucket(const size_type __n, _Node* __last) 1063169691Skan { 1064169691Skan _Node* __cur = _M_buckets[__n]; 1065169691Skan while (__cur != __last) 1066169691Skan { 1067169691Skan _Node* __next = __cur->_M_next; 1068169691Skan _M_delete_node(__cur); 1069169691Skan __cur = __next; 1070169691Skan _M_buckets[__n] = __cur; 1071169691Skan --_M_num_elements; 1072169691Skan } 1073169691Skan } 1074132720Skan 1075169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1076169691Skan void 1077169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1078169691Skan clear() 1079169691Skan { 1080259405Spfg // Google addition: do not iterate over buckets when empty 1081259405Spfg if (_M_num_elements == 0) 1082259405Spfg return; 1083259405Spfg 1084169691Skan for (size_type __i = 0; __i < _M_buckets.size(); ++__i) 1085169691Skan { 1086169691Skan _Node* __cur = _M_buckets[__i]; 1087169691Skan while (__cur != 0) 1088169691Skan { 1089169691Skan _Node* __next = __cur->_M_next; 1090169691Skan _M_delete_node(__cur); 1091169691Skan __cur = __next; 1092169691Skan } 1093169691Skan _M_buckets[__i] = 0; 1094169691Skan } 1095169691Skan _M_num_elements = 0; 1096132720Skan } 1097169691Skan 1098169691Skan template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1099169691Skan void 1100169691Skan hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1101169691Skan _M_copy_from(const hashtable& __ht) 1102132720Skan { 1103169691Skan _M_buckets.clear(); 1104169691Skan _M_buckets.reserve(__ht._M_buckets.size()); 1105169691Skan _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); 1106169691Skan try 1107169691Skan { 1108169691Skan for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { 1109169691Skan const _Node* __cur = __ht._M_buckets[__i]; 1110169691Skan if (__cur) 1111169691Skan { 1112169691Skan _Node* __local_copy = _M_new_node(__cur->_M_val); 1113169691Skan _M_buckets[__i] = __local_copy; 1114169691Skan 1115169691Skan for (_Node* __next = __cur->_M_next; 1116169691Skan __next; 1117169691Skan __cur = __next, __next = __cur->_M_next) 1118169691Skan { 1119169691Skan __local_copy->_M_next = _M_new_node(__next->_M_val); 1120169691Skan __local_copy = __local_copy->_M_next; 1121169691Skan } 1122169691Skan } 1123169691Skan } 1124169691Skan _M_num_elements = __ht._M_num_elements; 1125169691Skan } 1126169691Skan catch(...) 1127169691Skan { 1128169691Skan clear(); 1129169691Skan __throw_exception_again; 1130169691Skan } 1131132720Skan } 1132132720Skan 1133169691Skan_GLIBCXX_END_NAMESPACE 1134169691Skan 1135132720Skan#endif 1136