X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=libstdc%2B%2B-v3%2Finclude%2Fbits%2Fhashtable.h;h=f284126e247a663bc91a041a1e10714f9a39f9cc;hp=cd7553d5133795f9ccd910a5de1453db3f6a4836;hb=a484fc356e716397e5545f3c48005268e28b632d;hpb=111d656236a72d52a17fd6cf86cdd50d52b0885b diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index cd7553d5133..f284126e247 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -1,6 +1,6 @@ // hashtable.h header -*- C++ -*- -// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010, 2011 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 @@ -24,7 +24,7 @@ /** @file bits/hashtable.h * This is an internal header file, included by other library headers. - * You should not attempt to use it directly. + * Do not attempt to use it directly. @headername{unordered_map, unordered_set} */ #ifndef _HASHTABLE_H @@ -34,39 +34,41 @@ #include -namespace std +namespace std _GLIBCXX_VISIBILITY(default) { +_GLIBCXX_BEGIN_NAMESPACE_VERSION + // 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:::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 @@ -75,27 +77,27 @@ namespace std // 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, ). - + // ??? 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 > + __unique_keys> >, + public __detail::_Equality_base<_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; @@ -136,75 +146,92 @@ namespace std typedef std::ptrdiff_t difference_type; typedef __detail::_Node_iterator - local_iterator; + local_iterator; typedef __detail::_Node_const_iterator - const_local_iterator; + const_local_iterator; typedef __detail::_Hashtable_iterator - iterator; + iterator; typedef __detail::_Hashtable_const_iterator - const_iterator; + const_iterator; template - friend struct __detail::_Map_base; + 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; + _Node_allocator_type; typedef typename _Allocator::template rebind<_Node*>::other - _Bucket_allocator_type; + _Bucket_allocator_type; typedef typename _Allocator::template rebind<_Value>::other - _Value_allocator_type; + _Value_allocator_type; _Node_allocator_type _M_node_allocator; _Node** _M_buckets; size_type _M_bucket_count; + size_type _M_begin_bucket_index; // First non-empty bucket. size_type _M_element_count; _RehashPolicy _M_rehash_policy; - - _Node* - _M_allocate_node(const value_type& __v); - + + template + _Node* + _M_allocate_node(_Args&&... __args); + 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: + public: // Constructor, destructor, assignment, swap _Hashtable(size_type __bucket_hint, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&); - + template - _Hashtable(_InputIterator __first, _InputIterator __last, + _Hashtable(_InputIterator __first, _InputIterator __last, size_type __bucket_hint, - const _H1&, const _H2&, const _Hash&, + const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&); - + _Hashtable(const _Hashtable&); _Hashtable(_Hashtable&&); - + _Hashtable& - operator=(const _Hashtable&); + operator=(const _Hashtable& __ht) + { + _Hashtable __tmp(__ht); + this->swap(__tmp); + return *this; + } + + _Hashtable& + operator=(_Hashtable&& __ht) + { + // NB: DR 1204. + // NB: DR 675. + this->clear(); + this->swap(__ht); + return *this; + } ~_Hashtable(); @@ -213,21 +240,11 @@ namespace std // Basic container operations iterator begin() - { - iterator __i(_M_buckets); - if (!__i._M_cur_node) - __i._M_incr_bucket(); - return __i; - } + { return iterator(_M_buckets + _M_begin_bucket_index); } const_iterator begin() const - { - const_iterator __i(_M_buckets); - if (!__i._M_cur_node) - __i._M_incr_bucket(); - return __i; - } + { return const_iterator(_M_buckets + _M_begin_bucket_index); } iterator end() @@ -239,12 +256,7 @@ namespace std const_iterator cbegin() const - { - const_iterator __i(_M_buckets); - if (!__i._M_cur_node) - __i._M_incr_bucket(); - return __i; - } + { return const_iterator(_M_buckets + _M_begin_bucket_index); } const_iterator cend() const @@ -253,7 +265,7 @@ namespace std size_type size() const { return _M_element_count; } - + bool empty() const { return size() == 0; } @@ -262,10 +274,6 @@ namespace std 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(); } @@ -281,18 +289,18 @@ namespace std 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()); } @@ -324,7 +332,7 @@ namespace std float load_factor() const - { + { return static_cast(size()) / static_cast(bucket_count()); } @@ -335,8 +343,8 @@ namespace std const _RehashPolicy& __rehash_policy() const { return _M_rehash_policy; } - - void + + void __rehash_policy(const _RehashPolicy&); // Lookup. @@ -355,53 +363,75 @@ namespace std std::pair 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. + private: + // Find and insert helper functions and types + _Node* + _M_find_node(_Node*, const key_type&, + typename _Hashtable::_Hash_code_type) const; + + template + iterator + _M_insert_bucket(_Arg&&, size_type, + typename _Hashtable::_Hash_code_type); + + template + std::pair + _M_insert(_Arg&&, std::true_type); + + template + iterator + _M_insert(_Arg&&, std::false_type); + typedef typename std::conditional<__unique_keys, std::pair, iterator>::type - _Insert_Return_Type; + _Insert_Return_Type; typedef typename std::conditional<__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); + >::type + _Insert_Conv_Type; - std::pair - _M_insert(const value_type&, std::true_type); + public: + // Insert and erase + _Insert_Return_Type + insert(const value_type& __v) + { return _M_insert(__v, std::integral_constant()); } iterator - _M_insert(const value_type&, std::false_type); - - void - _M_erase_node(_Node*, _Node**); + insert(const_iterator, const value_type& __v) + { return _Insert_Conv_Type()(insert(__v)); } - public: - // Insert and erase _Insert_Return_Type - insert(const value_type& __v) - { return _M_insert(__v, std::integral_constant()); } + insert(value_type&& __v) + { return _M_insert(std::move(__v), + std::integral_constant()); } iterator - insert(const_iterator, const value_type& __v) - { return iterator(_Insert_Conv_Type()(this->insert(__v))); } + insert(const_iterator, value_type&& __v) + { return _Insert_Conv_Type()(insert(std::move(__v))); } + + template::value>::type> + _Insert_Return_Type + insert(_Pair&& __v) + { return _M_insert(std::forward<_Pair>(__v), + std::integral_constant()); } + + template::value>::type> + iterator + insert(const_iterator, _Pair&& __v) + { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); } template - void - insert(_InputIterator __first, _InputIterator __last); + void + insert(_InputIterator __first, _InputIterator __last); void insert(initializer_list __l) @@ -432,32 +462,33 @@ namespace std // Definitions of class template _Hashtable's out-of-line member functions. - template - 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 - { - _M_node_allocator.construct(__n, __v); - __n->_M_next = 0; - return __n; - } - __catch(...) - { - _M_node_allocator.deallocate(__n, 1); - __throw_exception_again; - } - } + template + 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(_Args&&... __args) + { + _Node* __n = _M_node_allocator.allocate(1); + __try + { + _M_node_allocator.construct(__n, std::forward<_Args>(__args)...); + __n->_M_next = 0; + return __n; + } + __catch(...) + { + _M_node_allocator.deallocate(__n, 1); + __throw_exception_again; + } + } - template @@ -470,7 +501,7 @@ namespace std _M_node_allocator.deallocate(__n, 1); } - template @@ -492,7 +523,7 @@ namespace std } } - template @@ -513,7 +544,7 @@ namespace std return __p; } - template @@ -526,7 +557,7 @@ namespace std __alloc.deallocate(__p, __n + 1); } - template @@ -548,9 +579,10 @@ namespace std { _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); _M_buckets = _M_allocate_buckets(_M_bucket_count); + _M_begin_bucket_index = _M_bucket_count; } - template @@ -578,6 +610,7 @@ namespace std __distance_fw(__f, __l))); _M_buckets = _M_allocate_buckets(_M_bucket_count); + _M_begin_bucket_index = _M_bucket_count; __try { for (; __f != __l; ++__f) @@ -590,8 +623,8 @@ namespace std __throw_exception_again; } } - - template @@ -604,6 +637,7 @@ namespace std __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), _M_node_allocator(__ht._M_node_allocator), _M_bucket_count(__ht._M_bucket_count), + _M_begin_bucket_index(__ht._M_begin_bucket_index), _M_element_count(__ht._M_element_count), _M_rehash_policy(__ht._M_rehash_policy) { @@ -631,7 +665,7 @@ namespace std } } - template @@ -643,34 +677,21 @@ namespace std _H1, _H2, _Hash, __chc>(__ht), __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), _M_node_allocator(__ht._M_node_allocator), + _M_buckets(__ht._M_buckets), _M_bucket_count(__ht._M_bucket_count), + _M_begin_bucket_index(__ht._M_begin_bucket_index), _M_element_count(__ht._M_element_count), - _M_rehash_policy(__ht._M_rehash_policy), - _M_buckets(__ht._M_buckets) + _M_rehash_policy(__ht._M_rehash_policy) { 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_begin_bucket_index = __ht._M_bucket_count; __ht._M_element_count = 0; __ht._M_rehash_policy = _RehashPolicy(); } - template - _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 @@ -682,7 +703,7 @@ namespace std _M_deallocate_buckets(_M_buckets, _M_bucket_count); } - template @@ -705,10 +726,11 @@ namespace std 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_begin_bucket_index, __x._M_begin_bucket_index); std::swap(_M_element_count, __x._M_element_count); } - template @@ -723,7 +745,7 @@ namespace std _M_rehash(__n_bkt); } - template @@ -740,7 +762,7 @@ namespace std return __p ? iterator(__p, _M_buckets + __n) : this->end(); } - template @@ -757,7 +779,7 @@ namespace std return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); } - template @@ -777,7 +799,7 @@ namespace std return __result; } - template @@ -797,7 +819,7 @@ namespace std 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; @@ -815,7 +837,7 @@ namespace std return std::make_pair(this->end(), this->end()); } - template @@ -855,13 +877,13 @@ namespace std // 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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_Node* + __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, @@ -874,146 +896,128 @@ namespace std } // Insert v in bucket n (assumes no element with its key already present). - template - 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 __do_rehash - = _M_rehash_policy._M_need_rehash(_M_bucket_count, - _M_element_count, 1); + template + 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(_Arg&& __v, size_type __n, + typename _Hashtable::_Hash_code_type __code) + { + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, 1); + + if (__do_rehash.first) + { + const key_type& __k = this->_M_extract(__v); + __n = this->_M_bucket_index(__k, __code, __do_rehash.second); + } - // 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); + // 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(std::forward<_Arg>(__v)); - __try - { - if (__do_rehash.first) - { - const key_type& __k = this->_M_extract(__v); - __n = this->_M_bucket_index(__k, __code, __do_rehash.second); + __try + { + if (__do_rehash.first) _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; - } - } + __new_node->_M_next = _M_buckets[__n]; + this->_M_store_code(__new_node, __code); + _M_buckets[__n] = __new_node; + ++_M_element_count; + if (__n < _M_begin_bucket_index) + _M_begin_bucket_index = __n; + 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 - std::pair::iterator, bool> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_insert(const value_type& __v, std::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); - } + template + std::pair::iterator, bool> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert(_Arg&& __v, std::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(std::forward<_Arg>(__v), + __n, __code), true); + } // Insert v unconditionally. - template - 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::false_type) - { - std::pair __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); + template + 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(_Arg&& __v, std::false_type) + { + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, 1); + if (__do_rehash.first) + _M_rehash(__do_rehash.second); - 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); + 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); - ++_M_element_count; - return iterator(__new_node, _M_buckets + __n); - } + // 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(std::forward<_Arg>(__v)); - // For erase(iterator) and erase(const_iterator). - template - 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; - } + 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; + if (__n < _M_begin_bucket_index) + _M_begin_bucket_index = __n; + } + this->_M_store_code(__new_node, __code); - _M_deallocate_node(__p); - --_M_element_count; - } + ++_M_element_count; + return iterator(__new_node, _M_buckets + __n); + } - template template - void + void _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: insert(_InputIterator __first, _InputIterator __last) @@ -1029,7 +1033,7 @@ namespace std this->insert(*__first); } - template @@ -1042,11 +1046,35 @@ namespace std { iterator __result(__it._M_cur_node, __it._M_cur_bucket); ++__result; - _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); + + _Node* __cur = *__it._M_cur_bucket; + if (__cur == __it._M_cur_node) + { + *__it._M_cur_bucket = __cur->_M_next; + + // If _M_begin_bucket_index no longer indexes the first non-empty + // bucket - its single node is being erased - update it. + if (!_M_buckets[_M_begin_bucket_index]) + _M_begin_bucket_index = __result._M_cur_bucket - _M_buckets; + } + else + { + _Node* __next = __cur->_M_next; + while (__next != __it._M_cur_node) + { + __cur = __next; + __next = __cur->_M_next; + } + __cur->_M_next = __next->_M_next; + } + + _M_deallocate_node(__it._M_cur_node); + --_M_element_count; + return __result; } - template @@ -1060,7 +1088,7 @@ namespace std 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); @@ -1071,10 +1099,11 @@ namespace std // _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) + if (std::__addressof(this->_M_extract((*__slot)->_M_v)) + != std::__addressof(__k)) { - _Node* __p = *__slot; - *__slot = __p->_M_next; + _Node* __p = *__slot; + *__slot = __p->_M_next; _M_deallocate_node(__p); --_M_element_count; ++__result; @@ -1095,13 +1124,27 @@ namespace std ++__result; } + // If the entire bucket indexed by _M_begin_bucket_index has been + // erased look forward for the first non-empty bucket. + if (!_M_buckets[_M_begin_bucket_index]) + { + if (!_M_element_count) + _M_begin_bucket_index = _M_bucket_count; + else + { + ++_M_begin_bucket_index; + while (!_M_buckets[_M_begin_bucket_index]) + ++_M_begin_bucket_index; + } + } + 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 @@ -1112,12 +1155,12 @@ namespace std _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: erase(const_iterator __first, const_iterator __last) { - while (__first != __last) - __first = this->erase(__first); + while (__first != __last) + __first = this->erase(__first); return iterator(__last._M_cur_node, __last._M_cur_bucket); } - template @@ -1128,9 +1171,10 @@ namespace std { _M_deallocate_nodes(_M_buckets, _M_bucket_count); _M_element_count = 0; + _M_begin_bucket_index = _M_bucket_count; } - - template @@ -1144,7 +1188,7 @@ namespace std + 1))); } - template @@ -1156,6 +1200,7 @@ namespace std _Node** __new_array = _M_allocate_buckets(__n); __try { + _M_begin_bucket_index = __n; for (size_type __i = 0; __i < _M_bucket_count; ++__i) while (_Node* __p = _M_buckets[__i]) { @@ -1163,6 +1208,8 @@ namespace std _M_buckets[__i] = __p->_M_next; __p->_M_next = __new_array[__new_index]; __new_array[__new_index] = __p; + if (__new_index < _M_begin_bucket_index) + _M_begin_bucket_index = __new_index; } _M_deallocate_buckets(_M_buckets, _M_bucket_count); _M_bucket_count = __n; @@ -1178,9 +1225,12 @@ namespace std _M_deallocate_buckets(__new_array, __n); _M_deallocate_nodes(_M_buckets, _M_bucket_count); _M_element_count = 0; + _M_begin_bucket_index = _M_bucket_count; __throw_exception_again; } } -} + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std #endif // _HASHTABLE_H