// Profiling unordered_set/unordered_multiset implementation -*- C++ -*-// Copyright (C) 2009, 2010 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 2, 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.// You should have received a copy of the GNU General Public License along// with this library; see the file COPYING. If not, write to the Free// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,// USA.// As a special exception, you may use this file as part of a free software// library without restriction. Specifically, if other files instantiate// templates or use macros or inline functions from this file, or you compile// this file and link it with other files to produce an executable, this// file does not by itself cause the resulting executable to be covered by// the GNU General Public License. This exception does not however// invalidate any other reasons why the executable file might be covered by// the GNU General Public License./** @file profile/unordered_set* This file is a GNU profile extension to the Standard C++ Library.*/#ifndef _GLIBCXX_PROFILE_UNORDERED_SET#define _GLIBCXX_PROFILE_UNORDERED_SET 1#ifndef __GXX_EXPERIMENTAL_CXX0X__# include <bits/c++0x_warning.h>#else# include <unordered_set>#include <profile/base.h>#define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASEnamespace std{namespace __profile{/** @brief Unordered_set wrapper with performance instrumentation. */template<typename _Key,typename _Hash = std::hash<_Key>,typename _Pred = std::equal_to<_Key>,typename _Alloc = std::allocator<_Key> >class unordered_set: public _GLIBCXX_STD_BASE{typedef typename _GLIBCXX_STD_BASE _Base;public:typedef typename _Base::size_type size_type;typedef typename _Base::hasher hasher;typedef typename _Base::key_equal key_equal;typedef typename _Base::allocator_type allocator_type;typedef typename _Base::key_type key_type;typedef typename _Base::value_type value_type;typedef typename _Base::difference_type difference_type;typedef typename _Base::reference reference;typedef typename _Base::const_reference const_reference;typedef typename _Base::iterator iterator;typedef typename _Base::const_iterator const_iterator;explicitunordered_set(size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__n, __hf, __eql, __a){__profcxx_hashtable_construct(this, _Base::bucket_count());__profcxx_hashtable_construct2(this);}template<typename _InputIterator>unordered_set(_InputIterator __f, _InputIterator __l,size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__f, __l, __n, __hf, __eql, __a){__profcxx_hashtable_construct(this, _Base::bucket_count());__profcxx_hashtable_construct2(this);}unordered_set(const _Base& __x): _Base(__x){__profcxx_hashtable_construct(this, _Base::bucket_count());__profcxx_hashtable_construct2(this);}unordered_set(unordered_set&& __x): _Base(std::forward<_Base>(__x)){__profcxx_hashtable_construct(this, _Base::bucket_count());__profcxx_hashtable_construct2(this);}unordered_set(initializer_list<value_type> __l,size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__l, __n, __hf, __eql, __a) { }unordered_set&operator=(const unordered_set& __x){*static_cast<_Base*>(this) = __x;return *this;}unordered_set&operator=(unordered_set&& __x){// NB: DR 1204.// NB: DR 675.this->clear();this->swap(__x);return *this;}unordered_set&operator=(initializer_list<value_type> __l){this->clear();this->insert(__l);return *this;}~unordered_set(){__profcxx_hashtable_destruct(this, _Base::bucket_count(),_Base::size());_M_profile_destruct();}voidswap(unordered_set& __x){_Base::swap(__x);}voidclear(){__profcxx_hashtable_destruct(this, _Base::bucket_count(),_Base::size());_M_profile_destruct();_Base::clear();}voidinsert(std::initializer_list<value_type> __l){size_type __old_size = _Base::bucket_count();_Base::insert(__l);_M_profile_resize(__old_size, _Base::bucket_count());}std::pair<iterator, bool>insert(const value_type& __obj){size_type __old_size = _Base::bucket_count();std::pair<iterator, bool> __res = _Base::insert(__obj);_M_profile_resize(__old_size, _Base::bucket_count());return __res;}iteratorinsert(const_iterator __iter, const value_type& __v){size_type __old_size = _Base::bucket_count();iterator __res = _Base::insert(__iter, __v);_M_profile_resize(__old_size, _Base::bucket_count());return __res;}template<typename _InputIter>voidinsert(_InputIter __first, _InputIter __last){size_type __old_size = _Base::bucket_count();_Base::insert(__first, __last);_M_profile_resize(__old_size, _Base::bucket_count());}voidinsert(const value_type* __first, const value_type* __last){size_type __old_size = _Base::bucket_count();_Base::insert(__first, __last);_M_profile_resize(__old_size, _Base::bucket_count());}void rehash(size_type __n){size_type __old_size = _Base::bucket_count();_Base::rehash(__n);_M_profile_resize(__old_size, _Base::bucket_count());}private:_Base&_M_base() { return *this; }const _Base&_M_base() const { return *this; }void_M_profile_resize(size_type __old_size, size_type __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){while (__it._M_cur_node->_M_next){++__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);}};template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>inline voidswap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,unordered_set<_Value, _Hash, _Pred, _Alloc>& __y){ __x.swap(__y); }template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>inline booloperator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y){ return __x._M_equal(__y); }template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>inline booloperator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y){ return !(__x == __y); }#undef _GLIBCXX_BASE#undef _GLIBCXX_STD_BASE#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE#define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>/** @brief Unordered_multiset wrapper with performance instrumentation. */template<typename _Value,typename _Hash = std::hash<_Value>,typename _Pred = std::equal_to<_Value>,typename _Alloc = std::allocator<_Value> >class unordered_multiset: public _GLIBCXX_STD_BASE{typedef typename _GLIBCXX_STD_BASE _Base;public:typedef typename _Base::size_type size_type;typedef typename _Base::hasher hasher;typedef typename _Base::key_equal key_equal;typedef typename _Base::allocator_type allocator_type;typedef typename _Base::key_type key_type;typedef typename _Base::value_type value_type;typedef typename _Base::difference_type difference_type;typedef typename _Base::reference reference;typedef typename _Base::const_reference const_reference;typedef typename _Base::iterator iterator;typedef typename _Base::const_iterator const_iterator;explicitunordered_multiset(size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__n, __hf, __eql, __a){__profcxx_hashtable_construct(this, _Base::bucket_count());}template<typename _InputIterator>unordered_multiset(_InputIterator __f, _InputIterator __l,size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__f, __l, __n, __hf, __eql, __a){__profcxx_hashtable_construct(this, _Base::bucket_count());}unordered_multiset(const _Base& __x): _Base(__x){__profcxx_hashtable_construct(this, _Base::bucket_count());}unordered_multiset(unordered_multiset&& __x): _Base(std::forward<_Base>(__x)){__profcxx_hashtable_construct(this, _Base::bucket_count());}unordered_multiset(initializer_list<value_type> __l,size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__l, __n, __hf, __eql, __a) { }unordered_multiset&operator=(const unordered_multiset& __x){*static_cast<_Base*>(this) = __x;return *this;}unordered_multiset&operator=(unordered_multiset&& __x){// NB: DR 1204.// NB: DR 675.this->clear();this->swap(__x);return *this;}unordered_multiset&operator=(initializer_list<value_type> __l){this->clear();this->insert(__l);return *this;}~unordered_multiset(){__profcxx_hashtable_destruct(this, _Base::bucket_count(),_Base::size());_M_profile_destruct();}voidswap(unordered_multiset& __x){_Base::swap(__x);}voidclear(){__profcxx_hashtable_destruct(this, _Base::bucket_count(),_Base::size());_M_profile_destruct();_Base::clear();}voidinsert(std::initializer_list<value_type> __l){size_type __old_size = _Base::bucket_count();_Base::insert(__l);_M_profile_resize(__old_size, _Base::bucket_count());}iteratorinsert(const value_type& __obj){size_type __old_size = _Base::bucket_count();iterator __res = _Base::insert(__obj);_M_profile_resize(__old_size, _Base::bucket_count());return __res;}iteratorinsert(const_iterator __iter, const value_type& __v){size_type __old_size = _Base::bucket_count();iterator __res = _Base::insert(__iter, __v);_M_profile_resize(__old_size, _Base::bucket_count());return __res;}template<typename _InputIter>voidinsert(_InputIter __first, _InputIter __last){size_type __old_size = _Base::bucket_count();_Base::insert(__first, __last);_M_profile_resize(__old_size, _Base::bucket_count());}voidinsert(const value_type* __first, const value_type* __last){size_type __old_size = _Base::bucket_count();_Base::insert(__first, __last);_M_profile_resize(__old_size, _Base::bucket_count());}void rehash(size_type __n){size_type __old_size = _Base::bucket_count();_Base::rehash(__n);_M_profile_resize(__old_size, _Base::bucket_count());}private:_Base&_M_base() { return *this; }const _Base&_M_base() const { return *this; }void_M_profile_resize(size_type __old_size, size_type __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){while (__it._M_cur_node->_M_next){++__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);}};template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>inline voidswap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y){ __x.swap(__y); }template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>inline booloperator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y){ return __x._M_equal(__y); }template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>inline booloperator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y){ return !(__x == __y); }} // namespace __profile} // namespace std#undef _GLIBCXX_BASE#undef _GLIBCXX_STD_BASE#endif // __GXX_EXPERIMENTAL_CXX0X__#endif