diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/tr1_impl/hashtable')
| -rw-r--r-- | gcc-4.4.3/libstdc++-v3/include/tr1_impl/hashtable | 1266 |
1 files changed, 1266 insertions, 0 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/tr1_impl/hashtable b/gcc-4.4.3/libstdc++-v3/include/tr1_impl/hashtable new file mode 100644 index 000000000..7c9098309 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/tr1_impl/hashtable @@ -0,0 +1,1266 @@ +// Internal header for TR1 unordered_set and unordered_map -*- C++ -*- + +// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file tr1_impl/hashtable + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +// This header file defines std::tr1::hashtable, which is used to +// implement std::tr1::unordered_set, std::tr1::unordered_map, +// std::tr1::unordered_multiset, and std::tr1::unordered_multimap. +// hashtable has many template parameters, partly to accommodate +// the differences between those four classes and partly to +// accommodate policy choices that go beyond TR1 specifications. + +// Class template hashtable attempts to encapsulate all reasonable +// variation among hash tables that use chaining. It does not handle +// open addressing. + +// References: +// M. Austern, "A Proposal to Add Hash Tables to the Standard +// Library (revision 4)," WG21 Document N1456=03-0039, 2003. +// D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching. +// A. Tavori and V. Dreizin, "Policy-Based Data Structures", 2004. +// http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html + +#include <tr1_impl/hashtable_policy.h> + +namespace std +{ +_GLIBCXX_BEGIN_NAMESPACE_TR1 + + // Class template _Hashtable, class definition. + + // Meaning of class template _Hashtable's template parameters + + // _Key and _Value: arbitrary CopyConstructible types. + + // _Allocator: an allocator type ([lib.allocator.requirements]) whose + // value type is Value. As a conforming extension, we allow for + // value type != Value. + + // _ExtractKey: function object that takes a object of type Value + // and returns a value of type _Key. + + // _Equal: function object that takes two objects of type k and returns + // a bool-like value that is true if the two objects are considered equal. + + // _H1: the hash function. A unary function object with argument type + // Key and result type size_t. Return values should be distributed + // over the entire range [0, numeric_limits<size_t>:::max()]. + + // _H2: the range-hashing function (in the terminology of Tavori and + // Dreizin). A binary function object whose argument types and result + // type are all size_t. Given arguments r and N, the return value is + // in the range [0, N). + + // _Hash: the ranged hash function (Tavori and Dreizin). A binary function + // whose argument types are _Key and size_t and whose result type is + // size_t. Given arguments k and N, the return value is in the range + // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other + // than the default, _H1 and _H2 are ignored. + + // _RehashPolicy: Policy class with three members, all of which govern + // the bucket count. _M_next_bkt(n) returns a bucket count no smaller + // than n. _M_bkt_for_elements(n) returns a bucket count appropriate + // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) + // determines whether, if the current bucket count is n_bkt and the + // current element count is n_elt, we need to increase the bucket + // count. If so, returns make_pair(true, n), where n is the new + // bucket count. If not, returns make_pair(false, <anything>). + + // ??? Right now it is hard-wired that the number of buckets never + // shrinks. Should we allow _RehashPolicy to change that? + + // __cache_hash_code: bool. true if we store the value of the hash + // function along with the value. This is a time-space tradeoff. + // Storing it may improve lookup speed by reducing the number of times + // we need to call the Equal function. + + // __constant_iterators: bool. true if iterator and const_iterator are + // both constant iterator types. This is true for unordered_set and + // unordered_multiset, false for unordered_map and unordered_multimap. + + // __unique_keys: bool. true if the return value of _Hashtable::count(k) + // is always at most one, false if it may be an arbitrary number. This + // true for unordered_set and unordered_map, false for unordered_multiset + // and unordered_multimap. + + template<typename _Key, typename _Value, typename _Allocator, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, + bool __cache_hash_code, + bool __constant_iterators, + bool __unique_keys> + class _Hashtable + : public __detail::_Rehash_base<_RehashPolicy, + _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, + __cache_hash_code, + __constant_iterators, + __unique_keys> >, + public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __cache_hash_code>, + public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, + _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, + __cache_hash_code, + __constant_iterators, + __unique_keys> > + { + public: + typedef _Allocator allocator_type; + typedef _Value value_type; + typedef _Key key_type; + typedef _Equal key_equal; + // mapped_type, if present, comes from _Map_base. + // hasher, if present, comes from _Hash_code_base. + typedef typename _Allocator::difference_type difference_type; + typedef typename _Allocator::size_type size_type; + typedef typename _Allocator::pointer pointer; + typedef typename _Allocator::const_pointer const_pointer; + typedef typename _Allocator::reference reference; + typedef typename _Allocator::const_reference const_reference; + + typedef __detail::_Node_iterator<value_type, __constant_iterators, + __cache_hash_code> + local_iterator; + typedef __detail::_Node_const_iterator<value_type, + __constant_iterators, + __cache_hash_code> + const_local_iterator; + + typedef __detail::_Hashtable_iterator<value_type, __constant_iterators, + __cache_hash_code> + iterator; + typedef __detail::_Hashtable_const_iterator<value_type, + __constant_iterators, + __cache_hash_code> + const_iterator; + + template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2, + typename _Hashtable2> + friend struct __detail::_Map_base; + + private: + typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; + typedef typename _Allocator::template rebind<_Node>::other + _Node_allocator_type; + typedef typename _Allocator::template rebind<_Node*>::other + _Bucket_allocator_type; + + typedef typename _Allocator::template rebind<_Value>::other + _Value_allocator_type; + + _Node_allocator_type _M_node_allocator; + _Node** _M_buckets; + size_type _M_bucket_count; + size_type _M_element_count; + _RehashPolicy _M_rehash_policy; + + _Node* + _M_allocate_node(const value_type& __v); + + void + _M_deallocate_node(_Node* __n); + + void + _M_deallocate_nodes(_Node**, size_type); + + _Node** + _M_allocate_buckets(size_type __n); + + void + _M_deallocate_buckets(_Node**, size_type __n); + + public: + // Constructor, destructor, assignment, swap + _Hashtable(size_type __bucket_hint, + const _H1&, const _H2&, const _Hash&, + const _Equal&, const _ExtractKey&, + const allocator_type&); + + template<typename _InputIterator> + _Hashtable(_InputIterator __first, _InputIterator __last, + size_type __bucket_hint, + const _H1&, const _H2&, const _Hash&, + const _Equal&, const _ExtractKey&, + const allocator_type&); + + _Hashtable(const _Hashtable&); + +#ifdef _GLIBCXX_INCLUDE_AS_CXX0X + _Hashtable(_Hashtable&&); +#endif + + _Hashtable& + operator=(const _Hashtable&); + + ~_Hashtable(); + +#ifdef _GLIBCXX_INCLUDE_AS_CXX0X + void swap(_Hashtable&&); +#else + void swap(_Hashtable&); +#endif + + // Basic container operations + iterator + begin() + { + iterator __i(_M_buckets); + if (!__i._M_cur_node) + __i._M_incr_bucket(); + return __i; + } + + const_iterator + begin() const + { + const_iterator __i(_M_buckets); + if (!__i._M_cur_node) + __i._M_incr_bucket(); + return __i; + } + + iterator + end() + { return iterator(_M_buckets + _M_bucket_count); } + + const_iterator + end() const + { return const_iterator(_M_buckets + _M_bucket_count); } + +#ifdef _GLIBCXX_INCLUDE_AS_CXX0X + const_iterator + cbegin() const + { + const_iterator __i(_M_buckets); + if (!__i._M_cur_node) + __i._M_incr_bucket(); + return __i; + } + + const_iterator + cend() const + { return const_iterator(_M_buckets + _M_bucket_count); } +#endif + + size_type + size() const + { return _M_element_count; } + + bool + empty() const + { return size() == 0; } + + allocator_type + get_allocator() const + { return allocator_type(_M_node_allocator); } + + _Value_allocator_type + _M_get_Value_allocator() const + { return _Value_allocator_type(_M_node_allocator); } + + size_type + max_size() const + { return _M_node_allocator.max_size(); } + + // Observers + key_equal + key_eq() const + { return this->_M_eq; } + + // hash_function, if present, comes from _Hash_code_base. + + // Bucket operations + size_type + bucket_count() const + { return _M_bucket_count; } + + size_type + max_bucket_count() const + { return max_size(); } + + size_type + bucket_size(size_type __n) const + { return std::distance(begin(__n), end(__n)); } + + size_type + bucket(const key_type& __k) const + { + return this->_M_bucket_index(__k, this->_M_hash_code(__k), + bucket_count()); + } + + local_iterator + begin(size_type __n) + { return local_iterator(_M_buckets[__n]); } + + local_iterator + end(size_type) + { return local_iterator(0); } + + const_local_iterator + begin(size_type __n) const + { return const_local_iterator(_M_buckets[__n]); } + + const_local_iterator + end(size_type) const + { return const_local_iterator(0); } + +#ifdef _GLIBCXX_INCLUDE_AS_CXX0X + // DR 691. + const_local_iterator + cbegin(size_type __n) const + { return const_local_iterator(_M_buckets[__n]); } + + const_local_iterator + cend(size_type) const + { return const_local_iterator(0); } +#endif + + float + load_factor() const + { + return static_cast<float>(size()) / static_cast<float>(bucket_count()); + } + + // max_load_factor, if present, comes from _Rehash_base. + + // Generalization of max_load_factor. Extension, not found in TR1. Only + // useful if _RehashPolicy is something other than the default. + const _RehashPolicy& + __rehash_policy() const + { return _M_rehash_policy; } + + void + __rehash_policy(const _RehashPolicy&); + + // Lookup. + iterator + find(const key_type& __k); + + const_iterator + find(const key_type& __k) const; + + size_type + count(const key_type& __k) const; + + std::pair<iterator, iterator> + equal_range(const key_type& __k); + + std::pair<const_iterator, const_iterator> + equal_range(const key_type& __k) const; + + private: // Find, insert and erase helper functions + // ??? This dispatching is a workaround for the fact that we don't + // have partial specialization of member templates; it would be + // better to just specialize insert on __unique_keys. There may be a + // cleaner workaround. + typedef typename __gnu_cxx::__conditional_type<__unique_keys, + std::pair<iterator, bool>, iterator>::__type + _Insert_Return_Type; + + typedef typename __gnu_cxx::__conditional_type<__unique_keys, + std::_Select1st<_Insert_Return_Type>, + std::_Identity<_Insert_Return_Type> + >::__type + _Insert_Conv_Type; + + _Node* + _M_find_node(_Node*, const key_type&, + typename _Hashtable::_Hash_code_type) const; + + iterator + _M_insert_bucket(const value_type&, size_type, + typename _Hashtable::_Hash_code_type); + + std::pair<iterator, bool> + _M_insert(const value_type&, std::_GLIBCXX_TR1 true_type); + + iterator + _M_insert(const value_type&, std::_GLIBCXX_TR1 false_type); + + void + _M_erase_node(_Node*, _Node**); + + public: + // Insert and erase + _Insert_Return_Type + insert(const value_type& __v) + { return _M_insert(__v, std::_GLIBCXX_TR1 integral_constant<bool, + __unique_keys>()); } + + iterator + insert(iterator, const value_type& __v) + { return iterator(_Insert_Conv_Type()(this->insert(__v))); } + + const_iterator + insert(const_iterator, const value_type& __v) + { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); } + + template<typename _InputIterator> + void + insert(_InputIterator __first, _InputIterator __last); + +#ifdef _GLIBCXX_INCLUDE_AS_CXX0X + void + insert(initializer_list<value_type> __l) + { this->insert(__l.begin(), __l.end()); } +#endif + + iterator + erase(iterator); + + const_iterator + erase(const_iterator); + + size_type + erase(const key_type&); + + iterator + erase(iterator, iterator); + + const_iterator + erase(const_iterator, const_iterator); + + void + clear(); + + // Set number of buckets to be appropriate for container of n element. + void rehash(size_type __n); + + private: + // Unconditionally change size of bucket array to n. + void _M_rehash(size_type __n); + }; + + + // Definitions of class template _Hashtable's out-of-line member functions. + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::_Node* + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_allocate_node(const value_type& __v) + { + _Node* __n = _M_node_allocator.allocate(1); + __try + { +#ifdef _GLIBCXX_INCLUDE_AS_CXX0X + _M_node_allocator.construct(__n, __v); +#else + _M_get_Value_allocator().construct(&__n->_M_v, __v); +#endif + __n->_M_next = 0; + return __n; + } + __catch(...) + { + _M_node_allocator.deallocate(__n, 1); + __throw_exception_again; + } + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_deallocate_node(_Node* __n) + { +#ifdef _GLIBCXX_INCLUDE_AS_CXX0X + _M_node_allocator.destroy(__n); +#else + _M_get_Value_allocator().destroy(&__n->_M_v); +#endif + _M_node_allocator.deallocate(__n, 1); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_deallocate_nodes(_Node** __array, size_type __n) + { + for (size_type __i = 0; __i < __n; ++__i) + { + _Node* __p = __array[__i]; + while (__p) + { + _Node* __tmp = __p; + __p = __p->_M_next; + _M_deallocate_node(__tmp); + } + __array[__i] = 0; + } + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::_Node** + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_allocate_buckets(size_type __n) + { + _Bucket_allocator_type __alloc(_M_node_allocator); + + // We allocate one extra bucket to hold a sentinel, an arbitrary + // non-null pointer. Iterator increment relies on this. + _Node** __p = __alloc.allocate(__n + 1); + std::fill(__p, __p + __n, (_Node*) 0); + __p[__n] = reinterpret_cast<_Node*>(0x1000); + return __p; + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_deallocate_buckets(_Node** __p, size_type __n) + { + _Bucket_allocator_type __alloc(_M_node_allocator); + __alloc.deallocate(__p, __n + 1); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(size_type __bucket_hint, + const _H1& __h1, const _H2& __h2, const _Hash& __h, + const _Equal& __eq, const _ExtractKey& __exk, + const allocator_type& __a) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__exk, __eq, + __h1, __h2, __h), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), + _M_node_allocator(__a), + _M_bucket_count(0), + _M_element_count(0), + _M_rehash_policy() + { + _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); + _M_buckets = _M_allocate_buckets(_M_bucket_count); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + template<typename _InputIterator> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(_InputIterator __f, _InputIterator __l, + size_type __bucket_hint, + const _H1& __h1, const _H2& __h2, const _Hash& __h, + const _Equal& __eq, const _ExtractKey& __exk, + const allocator_type& __a) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__exk, __eq, + __h1, __h2, __h), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), + _M_node_allocator(__a), + _M_bucket_count(0), + _M_element_count(0), + _M_rehash_policy() + { + _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), + _M_rehash_policy. + _M_bkt_for_elements(__detail:: + __distance_fw(__f, + __l))); + _M_buckets = _M_allocate_buckets(_M_bucket_count); + __try + { + for (; __f != __l; ++__f) + this->insert(*__f); + } + __catch(...) + { + clear(); + _M_deallocate_buckets(_M_buckets, _M_bucket_count); + __throw_exception_again; + } + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(const _Hashtable& __ht) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__ht), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), + _M_node_allocator(__ht._M_node_allocator), + _M_bucket_count(__ht._M_bucket_count), + _M_element_count(__ht._M_element_count), + _M_rehash_policy(__ht._M_rehash_policy) + { + _M_buckets = _M_allocate_buckets(_M_bucket_count); + __try + { + for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i) + { + _Node* __n = __ht._M_buckets[__i]; + _Node** __tail = _M_buckets + __i; + while (__n) + { + *__tail = _M_allocate_node(__n->_M_v); + this->_M_copy_code(*__tail, __n); + __tail = &((*__tail)->_M_next); + __n = __n->_M_next; + } + } + } + __catch(...) + { + clear(); + _M_deallocate_buckets(_M_buckets, _M_bucket_count); + __throw_exception_again; + } + } + +#ifdef _GLIBCXX_INCLUDE_AS_CXX0X + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(_Hashtable&& __ht) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__ht), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), + _M_node_allocator(__ht._M_node_allocator), + _M_bucket_count(__ht._M_bucket_count), + _M_element_count(__ht._M_element_count), + _M_rehash_policy(__ht._M_rehash_policy), + _M_buckets(__ht._M_buckets) + { + size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0); + __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt); + __ht._M_bucket_count = __n_bkt; + __ht._M_element_count = 0; + __ht._M_rehash_policy = _RehashPolicy(); + } +#endif + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>& + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + operator=(const _Hashtable& __ht) + { + _Hashtable __tmp(__ht); + this->swap(__tmp); + return *this; + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + ~_Hashtable() + { + clear(); + _M_deallocate_buckets(_M_buckets, _M_bucket_count); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: +#ifdef _GLIBCXX_INCLUDE_AS_CXX0X + swap(_Hashtable&& __x) +#else + swap(_Hashtable& __x) +#endif + { + // The only base class with member variables is hash_code_base. We + // define _Hash_code_base::_M_swap because different specializations + // have different members. + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>::_M_swap(__x); + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 431. Swapping containers with unequal allocators. + std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, + __x._M_node_allocator); + + std::swap(_M_rehash_policy, __x._M_rehash_policy); + std::swap(_M_buckets, __x._M_buckets); + std::swap(_M_bucket_count, __x._M_bucket_count); + std::swap(_M_element_count, __x._M_element_count); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + __rehash_policy(const _RehashPolicy& __pol) + { + _M_rehash_policy = __pol; + size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); + if (__n_bkt > _M_bucket_count) + _M_rehash(__n_bkt); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + find(const key_type& __k) + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); + return __p ? iterator(__p, _M_buckets + __n) : this->end(); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + find(const key_type& __k) const + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); + return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::size_type + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + count(const key_type& __k) const + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + std::size_t __result = 0; + for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next) + if (this->_M_compare(__k, __code, __p)) + ++__result; + return __result; + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + std::pair<typename _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, _Equal, _H1, + _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator, + typename _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, _Equal, _H1, + _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + equal_range(const key_type& __k) + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node** __head = _M_buckets + __n; + _Node* __p = _M_find_node(*__head, __k, __code); + + if (__p) + { + _Node* __p1 = __p->_M_next; + for (; __p1; __p1 = __p1->_M_next) + if (!this->_M_compare(__k, __code, __p1)) + break; + + iterator __first(__p, __head); + iterator __last(__p1, __head); + if (!__p1) + __last._M_incr_bucket(); + return std::make_pair(__first, __last); + } + else + return std::make_pair(this->end(), this->end()); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + std::pair<typename _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, _Equal, _H1, + _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator, + typename _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, _Equal, _H1, + _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + equal_range(const key_type& __k) const + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node** __head = _M_buckets + __n; + _Node* __p = _M_find_node(*__head, __k, __code); + + if (__p) + { + _Node* __p1 = __p->_M_next; + for (; __p1; __p1 = __p1->_M_next) + if (!this->_M_compare(__k, __code, __p1)) + break; + + const_iterator __first(__p, __head); + const_iterator __last(__p1, __head); + if (!__p1) + __last._M_incr_bucket(); + return std::make_pair(__first, __last); + } + else + return std::make_pair(this->end(), this->end()); + } + + // Find the node whose key compares equal to k, beginning the search + // at p (usually the head of a bucket). Return nil if no node is found. + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, + _Equal, _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::_Node* + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_find_node(_Node* __p, const key_type& __k, + typename _Hashtable::_Hash_code_type __code) const + { + for (; __p; __p = __p->_M_next) + if (this->_M_compare(__k, __code, __p)) + return __p; + return false; + } + + // Insert v in bucket n (assumes no element with its key already present). + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert_bucket(const value_type& __v, size_type __n, + typename _Hashtable::_Hash_code_type __code) + { + std::pair<bool, std::size_t> __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, 1); + + // Allocate the new node before doing the rehash so that we don't + // do a rehash if the allocation throws. + _Node* __new_node = _M_allocate_node(__v); + + __try + { + if (__do_rehash.first) + { + const key_type& __k = this->_M_extract(__v); + __n = this->_M_bucket_index(__k, __code, __do_rehash.second); + _M_rehash(__do_rehash.second); + } + + __new_node->_M_next = _M_buckets[__n]; + this->_M_store_code(__new_node, __code); + _M_buckets[__n] = __new_node; + ++_M_element_count; + return iterator(__new_node, _M_buckets + __n); + } + __catch(...) + { + _M_deallocate_node(__new_node); + __throw_exception_again; + } + } + + // Insert v if no element with its key is already present. + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + std::pair<typename _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, _Equal, _H1, + _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator, bool> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert(const value_type& __v, std::_GLIBCXX_TR1 true_type) + { + const key_type& __k = this->_M_extract(__v); + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + + if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code)) + return std::make_pair(iterator(__p, _M_buckets + __n), false); + return std::make_pair(_M_insert_bucket(__v, __n, __code), true); + } + + // Insert v unconditionally. + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert(const value_type& __v, std::_GLIBCXX_TR1 false_type) + { + std::pair<bool, std::size_t> __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, 1); + if (__do_rehash.first) + _M_rehash(__do_rehash.second); + + const key_type& __k = this->_M_extract(__v); + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + + // First find the node, avoid leaking new_node if compare throws. + _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code); + _Node* __new_node = _M_allocate_node(__v); + + if (__prev) + { + __new_node->_M_next = __prev->_M_next; + __prev->_M_next = __new_node; + } + else + { + __new_node->_M_next = _M_buckets[__n]; + _M_buckets[__n] = __new_node; + } + this->_M_store_code(__new_node, __code); + + ++_M_element_count; + return iterator(__new_node, _M_buckets + __n); + } + + // For erase(iterator) and erase(const_iterator). + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_erase_node(_Node* __p, _Node** __b) + { + _Node* __cur = *__b; + if (__cur == __p) + *__b = __cur->_M_next; + else + { + _Node* __next = __cur->_M_next; + while (__next != __p) + { + __cur = __next; + __next = __cur->_M_next; + } + __cur->_M_next = __next->_M_next; + } + + _M_deallocate_node(__p); + --_M_element_count; + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + template<typename _InputIterator> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + insert(_InputIterator __first, _InputIterator __last) + { + size_type __n_elt = __detail::__distance_fw(__first, __last); + std::pair<bool, std::size_t> __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, __n_elt); + if (__do_rehash.first) + _M_rehash(__do_rehash.second); + + for (; __first != __last; ++__first) + this->insert(*__first); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(iterator __it) + { + iterator __result = __it; + ++__result; + _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); + return __result; + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(const_iterator __it) + { + const_iterator __result = __it; + ++__result; + _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); + return __result; + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::size_type + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(const key_type& __k) + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + size_type __result = 0; + + _Node** __slot = _M_buckets + __n; + while (*__slot && !this->_M_compare(__k, __code, *__slot)) + __slot = &((*__slot)->_M_next); + + _Node** __saved_slot = 0; + while (*__slot && this->_M_compare(__k, __code, *__slot)) + { + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 526. Is it undefined if a function in the standard changes + // in parameters? + if (&this->_M_extract((*__slot)->_M_v) != &__k) + { + _Node* __p = *__slot; + *__slot = __p->_M_next; + _M_deallocate_node(__p); + --_M_element_count; + ++__result; + } + else + { + __saved_slot = __slot; + __slot = &((*__slot)->_M_next); + } + } + + if (__saved_slot) + { + _Node* __p = *__saved_slot; + *__saved_slot = __p->_M_next; + _M_deallocate_node(__p); + --_M_element_count; + ++__result; + } + + return __result; + } + + // ??? This could be optimized by taking advantage of the bucket + // structure, but it's not clear that it's worth doing. It probably + // wouldn't even be an optimization unless the load factor is large. + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(iterator __first, iterator __last) + { + while (__first != __last) + __first = this->erase(__first); + return __last; + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(const_iterator __first, const_iterator __last) + { + while (__first != __last) + __first = this->erase(__first); + return __last; + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + clear() + { + _M_deallocate_nodes(_M_buckets, _M_bucket_count); + _M_element_count = 0; + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + rehash(size_type __n) + { + _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), + _M_rehash_policy._M_bkt_for_elements(_M_element_count + + 1))); + } + + template<typename _Key, typename _Value, + typename _Allocator, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + bool __chc, bool __cit, bool __uk> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_rehash(size_type __n) + { + _Node** __new_array = _M_allocate_buckets(__n); + __try + { + for (size_type __i = 0; __i < _M_bucket_count; ++__i) + while (_Node* __p = _M_buckets[__i]) + { + std::size_t __new_index = this->_M_bucket_index(__p, __n); + _M_buckets[__i] = __p->_M_next; + __p->_M_next = __new_array[__new_index]; + __new_array[__new_index] = __p; + } + _M_deallocate_buckets(_M_buckets, _M_bucket_count); + _M_bucket_count = __n; + _M_buckets = __new_array; + } + __catch(...) + { + // A failure here means that a hash function threw an exception. + // We can't restore the previous state without calling the hash + // function again, so the only sensible recovery is to delete + // everything. + _M_deallocate_nodes(__new_array, __n); + _M_deallocate_buckets(__new_array, __n); + _M_deallocate_nodes(_M_buckets, _M_bucket_count); + _M_element_count = 0; + __throw_exception_again; + } + } + +_GLIBCXX_END_NAMESPACE_TR1 +} |