111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// TR1 hashtable.h header -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2007-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// terms of the GNU General Public License as published by the 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Free Software Foundation; either version 3, or (at your option) 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// any later version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// but WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// GNU General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** @file tr1/hashtable.h 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This is an internal header file, included by other library headers. 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Do not attempt to use it directly. 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @headername{tr1/unordered_set, tr1/unordered_map} 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _GLIBCXX_TR1_HASHTABLE_H 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _GLIBCXX_TR1_HASHTABLE_H 1 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#pragma GCC system_header 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <tr1/hashtable_policy.h> 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace std _GLIBCXX_VISIBILITY(default) 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace tr1 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_GLIBCXX_BEGIN_NAMESPACE_VERSION 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Class template _Hashtable, class definition. 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Meaning of class template _Hashtable's template parameters 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _Key and _Value: arbitrary CopyConstructible types. 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _Allocator: an allocator type ([lib.allocator.requirements]) whose 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // value type is Value. As a conforming extension, we allow for 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // value type != Value. 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _ExtractKey: function object that takes a object of type Value 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // and returns a value of type _Key. 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _Equal: function object that takes two objects of type k and returns 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // a bool-like value that is true if the two objects are considered equal. 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _H1: the hash function. A unary function object with argument type 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Key and result type size_t. Return values should be distributed 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // over the entire range [0, numeric_limits<size_t>:::max()]. 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _H2: the range-hashing function (in the terminology of Tavori and 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Dreizin). A binary function object whose argument types and result 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // type are all size_t. Given arguments r and N, the return value is 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // in the range [0, N). 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _Hash: the ranged hash function (Tavori and Dreizin). A binary function 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // whose argument types are _Key and size_t and whose result type is 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // size_t. Given arguments k and N, the return value is in the range 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // than the default, _H1 and _H2 are ignored. 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _RehashPolicy: Policy class with three members, all of which govern 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // the bucket count. _M_next_bkt(n) returns a bucket count no smaller 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // than n. _M_bkt_for_elements(n) returns a bucket count appropriate 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // determines whether, if the current bucket count is n_bkt and the 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // current element count is n_elt, we need to increase the bucket 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // count. If so, returns make_pair(true, n), where n is the new 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // bucket count. If not, returns make_pair(false, <anything>). 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // ??? Right now it is hard-wired that the number of buckets never 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // shrinks. Should we allow _RehashPolicy to change that? 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // __cache_hash_code: bool. true if we store the value of the hash 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // function along with the value. This is a time-space tradeoff. 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Storing it may improve lookup speed by reducing the number of times 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // we need to call the Equal function. 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // __constant_iterators: bool. true if iterator and const_iterator are 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // both constant iterator types. This is true for unordered_set and 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // unordered_multiset, false for unordered_map and unordered_multimap. 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // __unique_keys: bool. true if the return value of _Hashtable::count(k) 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // is always at most one, false if it may be an arbitrary number. This 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // true for unordered_set and unordered_map, false for unordered_multiset 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // and unordered_multimap. 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, typename _Allocator, 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _ExtractKey, typename _Equal, 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _RehashPolicy, 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __cache_hash_code, 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __constant_iterators, 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __unique_keys> 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Hashtable 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : public __detail::_Rehash_base<_RehashPolicy, 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ExtractKey, 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Equal, _H1, _H2, _Hash, 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RehashPolicy, 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __cache_hash_code, 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __constant_iterators, 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __unique_keys> >, 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, __cache_hash_code>, 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ExtractKey, 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Equal, _H1, _H2, _Hash, 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RehashPolicy, 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __cache_hash_code, 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __constant_iterators, 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __unique_keys> > 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Allocator allocator_type; 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Value value_type; 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Key key_type; 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Equal key_equal; 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // mapped_type, if present, comes from _Map_base. 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // hasher, if present, comes from _Hash_code_base. 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Allocator::difference_type difference_type; 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Allocator::size_type size_type; 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Allocator::pointer pointer; 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Allocator::const_pointer const_pointer; 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Allocator::reference reference; 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Allocator::const_reference const_reference; 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef __detail::_Node_iterator<value_type, __constant_iterators, 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __cache_hash_code> 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert local_iterator; 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef __detail::_Node_const_iterator<value_type, 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __constant_iterators, 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __cache_hash_code> 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_local_iterator; 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef __detail::_Hashtable_iterator<value_type, __constant_iterators, 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __cache_hash_code> 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator; 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef __detail::_Hashtable_const_iterator<value_type, 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __constant_iterators, 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __cache_hash_code> 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator; 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2, 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable2> 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert friend struct __detail::_Map_base; 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Allocator::template rebind<_Node>::other 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node_allocator_type; 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Allocator::template rebind<_Node*>::other 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Bucket_allocator_type; 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Allocator::template rebind<_Value>::other 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Value_allocator_type; 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node_allocator_type _M_node_allocator; 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node** _M_buckets; 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type _M_bucket_count; 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type _M_element_count; 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RehashPolicy _M_rehash_policy; 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_allocate_node(const value_type& __v); 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_node(_Node* __n); 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_nodes(_Node**, size_type); 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node** 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_allocate_buckets(size_type __n); 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_buckets(_Node**, size_type __n); 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Constructor, destructor, assignment, swap 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable(size_type __bucket_hint, 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _H1&, const _H2&, const _Hash&, 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Equal&, const _ExtractKey&, 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type&); 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _InputIterator> 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable(_InputIterator __first, _InputIterator __last, 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type __bucket_hint, 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _H1&, const _H2&, const _Hash&, 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Equal&, const _ExtractKey&, 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type&); 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable(const _Hashtable&); 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable& 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator=(const _Hashtable&); 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Hashtable(); 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void swap(_Hashtable&); 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Basic container operations 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert begin() 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator __i(_M_buckets); 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__i._M_cur_node) 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __i._M_incr_bucket(); 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __i; 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert begin() const 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator __i(_M_buckets); 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__i._M_cur_node) 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __i._M_incr_bucket(); 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __i; 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert end() 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return iterator(_M_buckets + _M_bucket_count); } 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert end() const 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return const_iterator(_M_buckets + _M_bucket_count); } 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size() const 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_element_count; } 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert empty() const 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return size() == 0; } 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert allocator_type 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_allocator() const 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return allocator_type(_M_node_allocator); } 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Value_allocator_type 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_Value_allocator() const 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _Value_allocator_type(_M_node_allocator); } 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert max_size() const 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_node_allocator.max_size(); } 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Observers 26411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert key_equal 26511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert key_eq() const 26611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return this->_M_eq; } 26711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // hash_function, if present, comes from _Hash_code_base. 26911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Bucket operations 27111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type 27211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bucket_count() const 27311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_bucket_count; } 27411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type 27611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert max_bucket_count() const 27711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return max_size(); } 27811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type 28011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bucket_size(size_type __n) const 28111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return std::distance(begin(__n), end(__n)); } 28211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type 28411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bucket(const key_type& __k) const 28511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 28611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return this->_M_bucket_index(__k, this->_M_hash_code(__k), 28711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bucket_count()); 28811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 28911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert local_iterator 29111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert begin(size_type __n) 29211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return local_iterator(_M_buckets[__n]); } 29311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert local_iterator 29511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert end(size_type) 29611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return local_iterator(0); } 29711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_local_iterator 29911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert begin(size_type __n) const 30011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return const_local_iterator(_M_buckets[__n]); } 30111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_local_iterator 30311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert end(size_type) const 30411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return const_local_iterator(0); } 30511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert float 30711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert load_factor() const 30811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 30911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return static_cast<float>(size()) / static_cast<float>(bucket_count()); 31011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 31111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // max_load_factor, if present, comes from _Rehash_base. 31311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Generalization of max_load_factor. Extension, not found in TR1. Only 31511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // useful if _RehashPolicy is something other than the default. 31611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _RehashPolicy& 31711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __rehash_policy() const 31811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_rehash_policy; } 31911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 32111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __rehash_policy(const _RehashPolicy&); 32211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Lookup. 32411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator 32511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(const key_type& __k); 32611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator 32811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(const key_type& __k) const; 32911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type 33111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert count(const key_type& __k) const; 33211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<iterator, iterator> 33411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert equal_range(const key_type& __k); 33511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<const_iterator, const_iterator> 33711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert equal_range(const key_type& __k) const; 33811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: // Find, insert and erase helper functions 34011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // ??? This dispatching is a workaround for the fact that we don't 34111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // have partial specialization of member templates; it would be 34211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // better to just specialize insert on __unique_keys. There may be a 34311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // cleaner workaround. 34411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename __gnu_cxx::__conditional_type<__unique_keys, 34511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<iterator, bool>, iterator>::__type 34611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Insert_Return_Type; 34711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename __gnu_cxx::__conditional_type<__unique_keys, 34911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::_Select1st<_Insert_Return_Type>, 35011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::_Identity<_Insert_Return_Type> 35111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert >::__type 35211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Insert_Conv_Type; 35311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* 35511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_find_node(_Node*, const key_type&, 35611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type) const; 35711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator 35911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_insert_bucket(const value_type&, size_type, 36011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type); 36111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<iterator, bool> 36311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_insert(const value_type&, std::tr1::true_type); 36411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator 36611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_insert(const value_type&, std::tr1::false_type); 36711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 36911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_erase_node(_Node*, _Node**); 37011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 37211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Insert and erase 37311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Insert_Return_Type 37411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(const value_type& __v) 37511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_insert(__v, std::tr1::integral_constant<bool, 37611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __unique_keys>()); } 37711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator 37911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(iterator, const value_type& __v) 38011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return iterator(_Insert_Conv_Type()(this->insert(__v))); } 38111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator 38311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(const_iterator, const value_type& __v) 38411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); } 38511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _InputIterator> 38711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 38811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(_InputIterator __first, _InputIterator __last); 38911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator 39111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(iterator); 39211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator 39411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(const_iterator); 39511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type 39711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(const key_type&); 39811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator 40011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(iterator, iterator); 40111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator 40311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(const_iterator, const_iterator); 40411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 40611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert clear(); 40711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Set number of buckets to be appropriate for container of n element. 40911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void rehash(size_type __n); 41011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 41211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Unconditionally change size of bucket array to n. 41311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void _M_rehash(size_type __n); 41411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 41511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Definitions of class template _Hashtable's out-of-line member functions. 41811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 41911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 42011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 42111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 42211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 42311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 42411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::_Node* 42511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 42611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 42711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_allocate_node(const value_type& __v) 42811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 42911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __n = _M_node_allocator.allocate(1); 43011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 43111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 43211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_Value_allocator().construct(&__n->_M_v, __v); 43311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __n->_M_next = 0; 43411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __n; 43511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 43611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 43711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 43811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_node_allocator.deallocate(__n, 1); 43911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 44011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 44111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 44211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 44311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 44411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 44511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 44611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 44711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 44811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 44911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 45011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_node(_Node* __n) 45111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 45211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_Value_allocator().destroy(&__n->_M_v); 45311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_node_allocator.deallocate(__n, 1); 45411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 45511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 45611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 45711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 45811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 45911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 46011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 46111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 46211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 46311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_nodes(_Node** __array, size_type __n) 46411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 46511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (size_type __i = 0; __i < __n; ++__i) 46611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 46711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __p = __array[__i]; 46811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__p) 46911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 47011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __tmp = __p; 47111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __p = __p->_M_next; 47211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_node(__tmp); 47311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 47411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __array[__i] = 0; 47511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 47611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 47711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 47811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 47911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 48011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 48111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 48211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 48311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 48411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::_Node** 48511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 48611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 48711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_allocate_buckets(size_type __n) 48811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 48911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Bucket_allocator_type __alloc(_M_node_allocator); 49011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 49111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // We allocate one extra bucket to hold a sentinel, an arbitrary 49211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // non-null pointer. Iterator increment relies on this. 49311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node** __p = __alloc.allocate(__n + 1); 49411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::fill(__p, __p + __n, (_Node*) 0); 49511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __p[__n] = reinterpret_cast<_Node*>(0x1000); 49611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __p; 49711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 49811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 49911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 50011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 50111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 50211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 50311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 50411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 50511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 50611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_buckets(_Node** __p, size_type __n) 50711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 50811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Bucket_allocator_type __alloc(_M_node_allocator); 50911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __alloc.deallocate(__p, __n + 1); 51011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 51111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 51211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 51311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 51411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 51511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 51611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 51711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 51811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable(size_type __bucket_hint, 51911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _H1& __h1, const _H2& __h2, const _Hash& __h, 52011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Equal& __eq, const _ExtractKey& __exk, 52111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type& __a) 52211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 52311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 52411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, __chc>(__exk, __eq, 52511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __h1, __h2, __h), 52611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 52711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_node_allocator(__a), 52811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_bucket_count(0), 52911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_element_count(0), 53011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash_policy() 53111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 53211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 53311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buckets = _M_allocate_buckets(_M_bucket_count); 53411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 53511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 53611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 53711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 53811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 53911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 54011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _InputIterator> 54111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 54211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 54311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable(_InputIterator __f, _InputIterator __l, 54411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type __bucket_hint, 54511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _H1& __h1, const _H2& __h2, const _Hash& __h, 54611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Equal& __eq, const _ExtractKey& __exk, 54711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type& __a) 54811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 54911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 55011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, __chc>(__exk, __eq, 55111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __h1, __h2, __h), 55211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 55311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_node_allocator(__a), 55411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_bucket_count(0), 55511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_element_count(0), 55611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash_policy() 55711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 55811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), 55911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash_policy. 56011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_bkt_for_elements(__detail:: 56111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __distance_fw(__f, 56211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __l))); 56311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buckets = _M_allocate_buckets(_M_bucket_count); 56411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 56511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 56611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __f != __l; ++__f) 56711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->insert(*__f); 56811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 56911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 57011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 57111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert clear(); 57211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_buckets(_M_buckets, _M_bucket_count); 57311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 57411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 57511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 57611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 57711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 57811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 57911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 58011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 58111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 58211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 58311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable(const _Hashtable& __ht) 58411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 58511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 58611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, __chc>(__ht), 58711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 58811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_node_allocator(__ht._M_node_allocator), 58911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_bucket_count(__ht._M_bucket_count), 59011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_element_count(__ht._M_element_count), 59111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash_policy(__ht._M_rehash_policy) 59211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 59311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buckets = _M_allocate_buckets(_M_bucket_count); 59411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 59511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 59611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i) 59711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 59811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __n = __ht._M_buckets[__i]; 59911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node** __tail = _M_buckets + __i; 60011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__n) 60111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 60211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert *__tail = _M_allocate_node(__n->_M_v); 60311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_copy_code(*__tail, __n); 60411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __tail = &((*__tail)->_M_next); 60511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __n = __n->_M_next; 60611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 60711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 60811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 60911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 61011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 61111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert clear(); 61211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_buckets(_M_buckets, _M_bucket_count); 61311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 61411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 61511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 61611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 61711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 61811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 61911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 62011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 62111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 62211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>& 62311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 62411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 62511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator=(const _Hashtable& __ht) 62611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 62711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable __tmp(__ht); 62811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->swap(__tmp); 62911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return *this; 63011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 63111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 63211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 63311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 63411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 63511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 63611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 63711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 63811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Hashtable() 63911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 64011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert clear(); 64111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_buckets(_M_buckets, _M_bucket_count); 64211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 64311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 64411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 64511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 64611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 64711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 64811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 64911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 65011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 65111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert swap(_Hashtable& __x) 65211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 65311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // The only base class with member variables is hash_code_base. We 65411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // define _Hash_code_base::_M_swap because different specializations 65511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // have different members. 65611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 65711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, __chc>::_M_swap(__x); 65811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 65911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _GLIBCXX_RESOLVE_LIB_DEFECTS 66011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // 431. Swapping containers with unequal allocators. 66111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, 66211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_node_allocator); 66311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 66411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::swap(_M_rehash_policy, __x._M_rehash_policy); 66511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::swap(_M_buckets, __x._M_buckets); 66611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::swap(_M_bucket_count, __x._M_bucket_count); 66711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::swap(_M_element_count, __x._M_element_count); 66811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 66911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 67011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 67111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 67211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 67311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 67411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 67511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 67611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 67711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __rehash_policy(const _RehashPolicy& __pol) 67811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 67911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash_policy = __pol; 68011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); 68111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__n_bkt > _M_bucket_count) 68211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash(__n_bkt); 68311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 68411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 68511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 68611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 68711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 68811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 68911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 69011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 69111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::iterator 69211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 69311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 69411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(const key_type& __k) 69511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 69611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 69711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 69811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 69911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __p ? iterator(__p, _M_buckets + __n) : this->end(); 70011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 70111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 70211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 70311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 70411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 70511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 70611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 70711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 70811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::const_iterator 70911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 71011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 71111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(const key_type& __k) const 71211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 71311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 71411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 71511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 71611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); 71711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 71811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 71911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 72011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 72111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 72211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 72311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 72411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 72511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::size_type 72611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 72711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 72811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert count(const key_type& __k) const 72911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 73011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 73111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 73211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t __result = 0; 73311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next) 73411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (this->_M_compare(__k, __code, __p)) 73511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__result; 73611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 73711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 73811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 73911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 74011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 74111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 74211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 74311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<typename _Hashtable<_Key, _Value, _Allocator, 74411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ExtractKey, _Equal, _H1, 74511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H2, _Hash, _RehashPolicy, 74611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::iterator, 74711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, 74811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ExtractKey, _Equal, _H1, 74911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H2, _Hash, _RehashPolicy, 75011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::iterator> 75111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 75211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 75311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert equal_range(const key_type& __k) 75411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 75511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 75611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 75711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node** __head = _M_buckets + __n; 75811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __p = _M_find_node(*__head, __k, __code); 75911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 76011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__p) 76111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 76211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __p1 = __p->_M_next; 76311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __p1; __p1 = __p1->_M_next) 76411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!this->_M_compare(__k, __code, __p1)) 76511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 76611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 76711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator __first(__p, __head); 76811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator __last(__p1, __head); 76911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__p1) 77011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __last._M_incr_bucket(); 77111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(__first, __last); 77211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 77311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 77411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(this->end(), this->end()); 77511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 77611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 77711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 77811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 77911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 78011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 78111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<typename _Hashtable<_Key, _Value, _Allocator, 78211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ExtractKey, _Equal, _H1, 78311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H2, _Hash, _RehashPolicy, 78411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::const_iterator, 78511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, 78611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ExtractKey, _Equal, _H1, 78711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H2, _Hash, _RehashPolicy, 78811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::const_iterator> 78911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 79011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 79111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert equal_range(const key_type& __k) const 79211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 79311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 79411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 79511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node** __head = _M_buckets + __n; 79611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __p = _M_find_node(*__head, __k, __code); 79711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 79811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__p) 79911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 80011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __p1 = __p->_M_next; 80111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __p1; __p1 = __p1->_M_next) 80211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!this->_M_compare(__k, __code, __p1)) 80311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 80411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 80511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator __first(__p, __head); 80611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator __last(__p1, __head); 80711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__p1) 80811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __last._M_incr_bucket(); 80911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(__first, __last); 81011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 81111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 81211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(this->end(), this->end()); 81311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 81411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 81511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Find the node whose key compares equal to k, beginning the search 81611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // at p (usually the head of a bucket). Return zero if no node is found. 81711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 81811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 81911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 82011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 82111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 82211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Equal, _H1, _H2, _Hash, _RehashPolicy, 82311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::_Node* 82411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 82511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 82611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_find_node(_Node* __p, const key_type& __k, 82711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type __code) const 82811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 82911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __p; __p = __p->_M_next) 83011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (this->_M_compare(__k, __code, __p)) 83111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __p; 83211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 0; 83311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 83411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 83511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Insert v in bucket n (assumes no element with its key already present). 83611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 83711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 83811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 83911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 84011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 84111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 84211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::iterator 84311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 84411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 84511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_insert_bucket(const value_type& __v, size_type __n, 84611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type __code) 84711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 84811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<bool, std::size_t> __do_rehash 84911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = _M_rehash_policy._M_need_rehash(_M_bucket_count, 85011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_element_count, 1); 85111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 85211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Allocate the new node before doing the rehash so that we don't 85311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // do a rehash if the allocation throws. 85411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __new_node = _M_allocate_node(__v); 85511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 85611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 85711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 85811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__do_rehash.first) 85911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 86011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const key_type& __k = this->_M_extract(__v); 86111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __n = this->_M_bucket_index(__k, __code, __do_rehash.second); 86211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash(__do_rehash.second); 86311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 86411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 86511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __new_node->_M_next = _M_buckets[__n]; 86611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_store_code(__new_node, __code); 86711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buckets[__n] = __new_node; 86811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++_M_element_count; 86911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return iterator(__new_node, _M_buckets + __n); 87011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 87111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 87211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 87311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_node(__new_node); 87411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 87511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 87611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 87711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 87811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Insert v if no element with its key is already present. 87911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 88011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 88111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 88211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 88311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<typename _Hashtable<_Key, _Value, _Allocator, 88411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ExtractKey, _Equal, _H1, 88511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H2, _Hash, _RehashPolicy, 88611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::iterator, bool> 88711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 88811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 88911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_insert(const value_type& __v, std::tr1::true_type) 89011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 89111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const key_type& __k = this->_M_extract(__v); 89211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 89311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 89411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 89511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code)) 89611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(iterator(__p, _M_buckets + __n), false); 89711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(_M_insert_bucket(__v, __n, __code), true); 89811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 89911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 90011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Insert v unconditionally. 90111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 90211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 90311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 90411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 90511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 90611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 90711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::iterator 90811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 90911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 91011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_insert(const value_type& __v, std::tr1::false_type) 91111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 91211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<bool, std::size_t> __do_rehash 91311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = _M_rehash_policy._M_need_rehash(_M_bucket_count, 91411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_element_count, 1); 91511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__do_rehash.first) 91611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash(__do_rehash.second); 91711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 91811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const key_type& __k = this->_M_extract(__v); 91911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 92011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 92111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 92211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // First find the node, avoid leaking new_node if compare throws. 92311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code); 92411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __new_node = _M_allocate_node(__v); 92511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 92611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__prev) 92711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 92811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __new_node->_M_next = __prev->_M_next; 92911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __prev->_M_next = __new_node; 93011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 93111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 93211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 93311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __new_node->_M_next = _M_buckets[__n]; 93411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buckets[__n] = __new_node; 93511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 93611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_store_code(__new_node, __code); 93711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 93811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++_M_element_count; 93911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return iterator(__new_node, _M_buckets + __n); 94011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 94111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 94211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // For erase(iterator) and erase(const_iterator). 94311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 94411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 94511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 94611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 94711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 94811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 94911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 95011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_erase_node(_Node* __p, _Node** __b) 95111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 95211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __cur = *__b; 95311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__cur == __p) 95411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert *__b = __cur->_M_next; 95511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 95611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 95711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __next = __cur->_M_next; 95811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__next != __p) 95911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 96011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __cur = __next; 96111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __next = __cur->_M_next; 96211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 96311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __cur->_M_next = __next->_M_next; 96411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 96511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 96611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_node(__p); 96711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert --_M_element_count; 96811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 96911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 97011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 97111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 97211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 97311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 97411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _InputIterator> 97511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 97611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 97711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 97811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(_InputIterator __first, _InputIterator __last) 97911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 98011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type __n_elt = __detail::__distance_fw(__first, __last); 98111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<bool, std::size_t> __do_rehash 98211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = _M_rehash_policy._M_need_rehash(_M_bucket_count, 98311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_element_count, __n_elt); 98411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__do_rehash.first) 98511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash(__do_rehash.second); 98611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 98711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __first != __last; ++__first) 98811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->insert(*__first); 98911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 99011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 99111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 99211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 99311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 99411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 99511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 99611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 99711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::iterator 99811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 99911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 100011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(iterator __it) 100111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 100211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator __result = __it; 100311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__result; 100411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); 100511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 100611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 100711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 100811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 100911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 101011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 101111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 101211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 101311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 101411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::const_iterator 101511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 101611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 101711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(const_iterator __it) 101811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 101911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator __result = __it; 102011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__result; 102111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); 102211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 102311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 102411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 102511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 102611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 102711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 102811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 102911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 103011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 103111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::size_type 103211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 103311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 103411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(const key_type& __k) 103511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 103611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 103711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 103811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type __result = 0; 103911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 104011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node** __slot = _M_buckets + __n; 104111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (*__slot && !this->_M_compare(__k, __code, *__slot)) 104211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __slot = &((*__slot)->_M_next); 104311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 104411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node** __saved_slot = 0; 104511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (*__slot && this->_M_compare(__k, __code, *__slot)) 104611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 104711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _GLIBCXX_RESOLVE_LIB_DEFECTS 104811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // 526. Is it undefined if a function in the standard changes 104911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // in parameters? 105011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (&this->_M_extract((*__slot)->_M_v) != &__k) 105111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 105211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __p = *__slot; 105311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert *__slot = __p->_M_next; 105411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_node(__p); 105511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert --_M_element_count; 105611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__result; 105711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 105811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 105911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 106011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __saved_slot = __slot; 106111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __slot = &((*__slot)->_M_next); 106211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 106311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 106411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 106511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__saved_slot) 106611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 106711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node* __p = *__saved_slot; 106811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert *__saved_slot = __p->_M_next; 106911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_node(__p); 107011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert --_M_element_count; 107111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__result; 107211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 107311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 107411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 107511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 107611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 107711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // ??? This could be optimized by taking advantage of the bucket 107811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // structure, but it's not clear that it's worth doing. It probably 107911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // wouldn't even be an optimization unless the load factor is large. 108011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 108111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 108211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 108311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 108411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 108511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 108611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::iterator 108711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 108811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 108911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(iterator __first, iterator __last) 109011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 109111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__first != __last) 109211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __first = this->erase(__first); 109311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __last; 109411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 109511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 109611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 109711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 109811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 109911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 110011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 110111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, 110211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chc, __cit, __uk>::const_iterator 110311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 110411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 110511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(const_iterator __first, const_iterator __last) 110611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 110711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__first != __last) 110811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __first = this->erase(__first); 110911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __last; 111011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 111111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 111211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 111311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 111411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 111511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 111611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 111711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 111811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 111911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert clear() 112011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 112111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_nodes(_M_buckets, _M_bucket_count); 112211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_element_count = 0; 112311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 112411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 112511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 112611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 112711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 112811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 112911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 113011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 113111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 113211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rehash(size_type __n) 113311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 113411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), 113511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash_policy._M_bkt_for_elements(_M_element_count 113611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert + 1))); 113711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 113811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 113911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Key, typename _Value, 114011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Allocator, typename _ExtractKey, typename _Equal, 114111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 114211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __chc, bool __cit, bool __uk> 114311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 114411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 114511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 114611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_rehash(size_type __n) 114711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 114811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Node** __new_array = _M_allocate_buckets(__n); 114911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 115011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 115111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (size_type __i = 0; __i < _M_bucket_count; ++__i) 115211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (_Node* __p = _M_buckets[__i]) 115311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 115411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t __new_index = this->_M_bucket_index(__p, __n); 115511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buckets[__i] = __p->_M_next; 115611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __p->_M_next = __new_array[__new_index]; 115711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __new_array[__new_index] = __p; 115811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 115911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_buckets(_M_buckets, _M_bucket_count); 116011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_bucket_count = __n; 116111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buckets = __new_array; 116211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 116311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 116411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 116511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // A failure here means that a hash function threw an exception. 116611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // We can't restore the previous state without calling the hash 116711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // function again, so the only sensible recovery is to delete 116811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // everything. 116911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_nodes(__new_array, __n); 117011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_buckets(__new_array, __n); 117111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_deallocate_nodes(_M_buckets, _M_bucket_count); 117211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_element_count = 0; 117311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 117411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 117511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 117611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 117711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_GLIBCXX_END_NAMESPACE_VERSION 117811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace tr1 117911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace std 118011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 118111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif // _GLIBCXX_TR1_HASHTABLE_H 1182