From f431d7ca38c9607e6bf90b63b348c8186b984480 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Sat, 10 Dec 2011 14:00:03 +0000 Subject: [PATCH] unordered_set: Minor formatting changes. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2011-12-12 François Dumont * include/profile/unordered_set: Minor formatting changes. (unordered_set<>::_M_profile_destruct, unordered_multiset<>::_M_profile_destruct): Fix implementation to not rely on normal implementation details anymore. (unordered_set<>::_M_profile_resize, unordered_multiset<>::_M_profile_resize): Implement consistently accross all unordered containers. (unordered_set<>::emplace, unordered_set<>::emplace_hint, unordered_multiset<>::emplace, unordered_multset<>::emplace_hint): Add to signal rehash to profiling system. * include/profile/unordered_map: Likewise for unordered_map<> and unordered_multimap<>. From-SVN: r182188 --- libstdc++-v3/ChangeLog | 15 ++ libstdc++-v3/include/profile/unordered_map | 136 ++++++++++------ libstdc++-v3/include/profile/unordered_set | 179 ++++++++++++--------- 3 files changed, 206 insertions(+), 124 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 5ade2a00bd1..9f117b43391 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,18 @@ +2011-12-12 François Dumont + + * include/profile/unordered_set: Minor formatting changes. + (unordered_set<>::_M_profile_destruct, + unordered_multiset<>::_M_profile_destruct): Fix implementation to not + rely on normal implementation details anymore. + (unordered_set<>::_M_profile_resize, + unordered_multiset<>::_M_profile_resize): Implement consistently + accross all unordered containers. + (unordered_set<>::emplace, unordered_set<>::emplace_hint, + unordered_multiset<>::emplace, unordered_multset<>::emplace_hint): Add + to signal rehash to profiling system. + * include/profile/unordered_map: Likewise for unordered_map<> and + unordered_multimap<>. + 2011-12-09 François Dumont * include/bits/hashtable.h (_Hashtable<>::emplace, diff --git a/libstdc++-v3/include/profile/unordered_map b/libstdc++-v3/include/profile/unordered_map index 5d57df53769..3688d549f65 100644 --- a/libstdc++-v3/include/profile/unordered_map +++ b/libstdc++-v3/include/profile/unordered_map @@ -171,6 +171,28 @@ namespace __profile _Base::clear(); } + template + std::pair + emplace(_Args&&... __args) + { + size_type __old_size = _Base::bucket_count(); + std::pair __res + = _Base::emplace(std::forward<_Args>(__args)...); + _M_profile_resize(__old_size); + return __res; + } + + template + iterator + emplace_hint(const_iterator __it, _Args&&... __args) + { + size_type __old_size = _Base::bucket_count(); + iterator __res + = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); + _M_profile_resize(__old_size); + return __res; + } + void insert(std::initializer_list __l) { @@ -182,7 +204,7 @@ namespace __profile std::pair insert(const value_type& __obj) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); std::pair __res = _Base::insert(__obj); _M_profile_resize(__old_size); return __res; @@ -203,7 +225,7 @@ namespace __profile std::pair insert(_Pair&& __obj) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); std::pair __res = _Base::insert(std::forward<_Pair>(__obj)); _M_profile_resize(__old_size); @@ -243,7 +265,7 @@ namespace __profile mapped_type& operator[](const _Key& __k) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); mapped_type& __res = _M_base()[__k]; _M_profile_resize(__old_size); return __res; @@ -252,7 +274,7 @@ namespace __profile mapped_type& operator[](_Key&& __k) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); mapped_type& __res = _M_base()[std::move(__k)]; _M_profile_resize(__old_size); return __res; @@ -264,9 +286,9 @@ namespace __profile void rehash(size_type __n) { - size_type __old_size = _Base::bucket_count(); - _Base::rehash(__n); - _M_profile_resize(__old_size); + size_type __old_size = _Base::bucket_count(); + _Base::rehash(__n); + _M_profile_resize(__old_size); } private: @@ -274,33 +296,33 @@ namespace __profile _M_profile_resize(size_type __old_size) { size_type __new_size = _Base::bucket_count(); - if (__old_size != __new_size) + if (__old_size != __new_size) __profcxx_hashtable_resize(this, __old_size, __new_size); } void _M_profile_destruct() { - size_type __hops = 0, __lc = 0, __chain = 0; - for (iterator __it = _M_base().begin(); __it != _M_base().end(); - ++__it) + size_type __hops = 0, __lc = 0, __chain = 0; + iterator __it = this->begin(); + while (__it != this->end()) { - while (__it._M_cur_node->_M_next) - { - ++__chain; - ++__it; - } + size_type __bkt = this->bucket(__it->first); + for (++__it; __it != this->end() + && this->bucket(__it->first) == __bkt; + ++__it) + ++__chain; if (__chain) { ++__chain; - __lc = __lc > __chain ? __lc : __chain; + __lc = __lc > __chain ? __lc : __chain; __hops += __chain * (__chain - 1) / 2; __chain = 0; } } - __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); + __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); } - }; + }; template @@ -429,12 +451,6 @@ namespace __profile _M_profile_destruct(); } - _Base& - _M_base() noexcept { return *this; } - - const _Base& - _M_base() const noexcept { return *this; } - void clear() noexcept { @@ -444,20 +460,42 @@ namespace __profile _Base::clear(); } + template + iterator + emplace(_Args&&... __args) + { + size_type __old_size = _Base::bucket_count(); + iterator __res + = _Base::emplace(std::forward<_Args>(__args)...); + _M_profile_resize(__old_size); + return __res; + } + + template + iterator + emplace_hint(const_iterator __it, _Args&&... __args) + { + size_type __old_size = _Base::bucket_count(); + iterator __res + = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); + _M_profile_resize(__old_size); + return __res; + } + void insert(std::initializer_list __l) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); _Base::insert(__l); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } iterator insert(const value_type& __obj) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); iterator __res = _Base::insert(__obj); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -466,7 +504,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); iterator __res = _Base::insert(__iter, __v); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -476,9 +514,9 @@ namespace __profile iterator insert(_Pair&& __obj) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); iterator __res = _Base::insert(std::forward<_Pair>(__obj)); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -490,7 +528,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -500,7 +538,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); _Base::insert(__first, __last); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } void @@ -508,7 +546,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); _Base::insert(__first, __last); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } void @@ -517,15 +555,16 @@ namespace __profile void rehash(size_type __n) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); _Base::rehash(__n); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } private: void - _M_profile_resize(size_type __old_size, size_type __new_size) + _M_profile_resize(size_type __old_size) { + size_type __new_size = _Base::bucket_count(); if (__old_size != __new_size) __profcxx_hashtable_resize(this, __old_size, __new_size); } @@ -533,15 +572,15 @@ namespace __profile void _M_profile_destruct() { - size_type __hops = 0, __lc = 0, __chain = 0; - for (iterator __it = _M_base().begin(); __it != _M_base().end(); - ++__it) + size_type __hops = 0, __lc = 0, __chain = 0; + iterator __it = this->begin(); + while (__it != this->end()) { - while (__it._M_cur_node->_M_next) - { - ++__chain; - ++__it; - } + size_type __bkt = this->bucket(__it->first); + for (++__it; __it != this->end() + && this->bucket(__it->first) == __bkt; + ++__it) + ++__chain; if (__chain) { ++__chain; @@ -550,10 +589,9 @@ namespace __profile __chain = 0; } } - __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); + __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); } - - }; + }; template diff --git a/libstdc++-v3/include/profile/unordered_set b/libstdc++-v3/include/profile/unordered_set index 4af778bbf7c..55177b33559 100644 --- a/libstdc++-v3/include/profile/unordered_set +++ b/libstdc++-v3/include/profile/unordered_set @@ -170,12 +170,34 @@ namespace __profile _Base::clear(); } + template + std::pair + emplace(_Args&&... __args) + { + size_type __old_size = _Base::bucket_count(); + std::pair __res + = _Base::emplace(std::forward<_Args>(__args)...); + _M_profile_resize(__old_size); + return __res; + } + + template + iterator + emplace_hint(const_iterator __it, _Args&&... __args) + { + size_type __old_size = _Base::bucket_count(); + iterator __res + = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); + _M_profile_resize(__old_size); + return __res; + } + void insert(std::initializer_list __l) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); _Base::insert(__l); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } std::pair @@ -183,7 +205,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); std::pair __res = _Base::insert(__obj); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -192,7 +214,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); iterator __res = _Base::insert(__iter, __v); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -201,7 +223,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); std::pair __res = _Base::insert(std::move(__obj)); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -210,7 +232,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); iterator __res = _Base::insert(__iter, std::move(__v)); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -220,7 +242,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); _Base::insert(__first, __last); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } void @@ -228,55 +250,48 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); _Base::insert(__first, __last); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } void rehash(size_type __n) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); _Base::rehash(__n); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } private: - _Base& - _M_base() noexcept { return *this; } - - const _Base& - _M_base() const noexcept { return *this; } - void - _M_profile_resize(size_type __old_size, size_type __new_size) + _M_profile_resize(size_type __old_size) { - if (__old_size != __new_size) + size_type __new_size = _Base::bucket_count(); + if (__old_size != __new_size) __profcxx_hashtable_resize(this, __old_size, __new_size); } void _M_profile_destruct() { - size_type __hops = 0, __lc = 0, __chain = 0; - for (iterator __it = _M_base().begin(); __it != _M_base().end(); - ++__it) - { - while (__it._M_cur_node->_M_next) - { + size_type __hops = 0, __lc = 0, __chain = 0; + iterator __it = this->begin(); + while (__it != this->end()) + { + size_type __bkt = this->bucket(*__it); + for (++__it; __it != this->end() && this->bucket(*__it) == __bkt; + ++__it) ++__chain; - ++__it; - } - if (__chain) - { - ++__chain; - __lc = __lc > __chain ? __lc : __chain; - __hops += __chain * (__chain - 1) / 2; - __chain = 0; - } - } - __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); + if (__chain) + { + ++__chain; + __lc = __lc > __chain ? __lc : __chain; + __hops += __chain * (__chain - 1) / 2; + __chain = 0; + } + } + __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); } - - }; + }; template inline void @@ -418,20 +433,41 @@ namespace __profile _Base::clear(); } + template + iterator + emplace(_Args&&... __args) + { + size_type __old_size = _Base::bucket_count(); + iterator __res = _Base::emplace(std::forward<_Args>(__args)...); + _M_profile_resize(__old_size); + return __res; + } + + template + iterator + emplace_hint(const_iterator __it, _Args&&... __args) + { + size_type __old_size = _Base::bucket_count(); + iterator __res + = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); + _M_profile_resize(__old_size); + return __res; + } + void insert(std::initializer_list __l) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); _Base::insert(__l); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } iterator insert(const value_type& __obj) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); iterator __res = _Base::insert(__obj); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -440,16 +476,16 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); iterator __res = _Base::insert(__iter, __v); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } iterator insert(value_type&& __obj) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); iterator __res = _Base::insert(std::move(__obj)); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -458,7 +494,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); iterator __res = _Base::insert(__iter, std::move(__v)); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); return __res; } @@ -468,7 +504,7 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); _Base::insert(__first, __last); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } void @@ -476,26 +512,21 @@ namespace __profile { size_type __old_size = _Base::bucket_count(); _Base::insert(__first, __last); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } void rehash(size_type __n) { - size_type __old_size = _Base::bucket_count(); + size_type __old_size = _Base::bucket_count(); _Base::rehash(__n); - _M_profile_resize(__old_size, _Base::bucket_count()); + _M_profile_resize(__old_size); } private: - _Base& - _M_base() noexcept { return *this; } - - const _Base& - _M_base() const noexcept { return *this; } - void - _M_profile_resize(size_type __old_size, size_type __new_size) + _M_profile_resize(size_type __old_size) { + size_type __new_size = _Base::bucket_count(); if (__old_size != __new_size) __profcxx_hashtable_resize(this, __old_size, __new_size); } @@ -503,27 +534,25 @@ namespace __profile void _M_profile_destruct() { - size_type __hops = 0, __lc = 0, __chain = 0; - for (iterator __it = _M_base().begin(); __it != _M_base().end(); - ++__it) - { - while (__it._M_cur_node->_M_next) - { - ++__chain; - ++__it; - } - - if (__chain) - { + size_type __hops = 0, __lc = 0, __chain = 0; + iterator __it = this->begin(); + while (__it != this->end()) + { + size_type __bkt = this->bucket(*__it); + for (++__it; __it != this->end() && this->bucket(*__it) == __bkt; + ++__it) ++__chain; - __lc = __lc > __chain ? __lc : __chain; - __hops += __chain * (__chain - 1) / 2; - __chain = 0; - } - } - __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); - } + if (__chain) + { + ++__chain; + __lc = __lc > __chain ? __lc : __chain; + __hops += __chain * (__chain - 1) / 2; + __chain = 0; + } + } + __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); + } }; template -- 2.30.2