Index: gcc/libstdc++-v3/include/tr1_impl/hashtable |
diff --git a/gcc/libstdc++-v3/include/tr1_impl/hashtable b/gcc/libstdc++-v3/include/tr1_impl/hashtable |
deleted file mode 100644 |
index 7c90983095f059bca04dde75b3274a59006161f1..0000000000000000000000000000000000000000 |
--- a/gcc/libstdc++-v3/include/tr1_impl/hashtable |
+++ /dev/null |
@@ -1,1266 +0,0 @@ |
-// 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 |
-} |