[thirdparty/gcc.git] / libstdc++-v3 / include / profile / unordered_set

// 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

#include <profile/base.h>

#ifdef __GXX_EXPERIMENTAL_CXX0X__
# include <unordered_set>
#else
# include <c++0x_warning.h>
#endif

#include <initializer_list>

#define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE

namespace 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;

      explicit
      unordered_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();
      }

      void
      swap(unordered_set& __x)
      {
        _Base::swap(__x);
      }

      void
      clear()
      {
        __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
                                     _Base::size());
        _M_profile_destruct();
        _Base::clear();
      }

      void
      insert(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;
      }

      iterator
      insert(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>
        void
        insert(_InputIter __first, _InputIter __last)
        {
	  size_type __old_size = _Base::bucket_count(); 
	  _Base::insert(__first, __last);
	  _M_profile_resize(__old_size,  _Base::bucket_count()); 
	}

      void
      insert(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 void
    swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
	 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__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;

      explicit
      unordered_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();
      }

      void
      swap(unordered_multiset& __x)
      {
        _Base::swap(__x);
      }

      void
      clear()
      {
        __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
                                     _Base::size());
        _M_profile_destruct();
        _Base::clear();
      }

      void
      insert(std::initializer_list<value_type> __l)
      { 
        size_type __old_size =  _Base::bucket_count();
        _Base::insert(__l); 
        _M_profile_resize(__old_size,  _Base::bucket_count()); 
      }

      iterator
      insert(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;
      }

      iterator
      insert(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>
        void
        insert(_InputIter __first, _InputIter __last)
        {
	  size_type __old_size = _Base::bucket_count(); 
	  _Base::insert(__first, __last);
	  _M_profile_resize(__old_size,  _Base::bucket_count()); 
	}

      void
      insert(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 void
    swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
	 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__y); }

} // namespace __profile
} // namespace std

#undef _GLIBCXX_BASE
#undef _GLIBCXX_STD_BASE

#endif
Commit	Line	Data
1218d701 SR	1	// Profiling unordered_set/unordered_multiset implementation -- C++ --
1218d701 SR	2
5004040e	3	// Copyright (C) 2009, 2010 Free Software Foundation, Inc.
1218d701 SR	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the
	7	// terms of the GNU General Public License as published by the
	8	// Free Software Foundation; either version 2, or (at your option)
	9	// any later version.
	10
	11	// This library is distributed in the hope that it will be useful,
	12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	// GNU General Public License for more details.
	15
	16	// You should have received a copy of the GNU General Public License along
	17	// with this library; see the file COPYING. If not, write to the Free
	18	// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
	19	// USA.
	20
	21	// As a special exception, you may use this file as part of a free software
	22	// library without restriction. Specifically, if other files instantiate
	23	// templates or use macros or inline functions from this file, or you compile
	24	// this file and link it with other files to produce an executable, this
	25	// file does not by itself cause the resulting executable to be covered by
	26	// the GNU General Public License. This exception does not however
	27	// invalidate any other reasons why the executable file might be covered by
	28	// the GNU General Public License.
	29
	30	/** @file profile/unordered_set
	31	* This file is a GNU profile extension to the Standard C++ Library.
	32	*/
	33
	34	#ifndef _GLIBCXX_PROFILE_UNORDERED_SET
	35	#define _GLIBCXX_PROFILE_UNORDERED_SET 1
	36
	37	#include <profile/base.h>
	38
	39	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	40	# include <unordered_set>
	41	#else
	42	# include <c++0x_warning.h>
	43	#endif
	44
	45	#include <initializer_list>
	46
	47	#define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
	48	#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
	49
	50	namespace std
	51	{
	52	namespace __profile
	53	{
	54	/** @brief Unordered_set wrapper with performance instrumentation. */
	55	template<typename _Key,
	56	typename _Hash = std::hash<_Key>,
	57	typename _Pred = std::equal_to<_Key>,
	58	typename _Alloc = std::allocator<_Key> >
	59	class unordered_set
	60	: public _GLIBCXX_STD_BASE
	61	{
	62	typedef typename _GLIBCXX_STD_BASE _Base;
	63
	64	public:
	65	typedef typename _Base::size_type size_type;
	66	typedef typename _Base::hasher hasher;
	67	typedef typename _Base::key_equal key_equal;
68	typedef typename _Base::allocator_type allocator_type;
69	typedef typename _Base::key_type key_type;
70	typedef typename _Base::value_type value_type;
71	typedef typename _Base::difference_type difference_type;
72	typedef typename _Base::reference reference;
73	typedef typename _Base::const_reference const_reference;
1218d701 SR	74
	75	typedef typename _Base::iterator iterator;
	76	typedef typename _Base::const_iterator const_iterator;
	77
	78	explicit
	79	unordered_set(size_type __n = 10,
	80	const hasher& __hf = hasher(),
	81	const key_equal& __eql = key_equal(),
	82	const allocator_type& __a = allocator_type())
	83	: _Base(__n, __hf, __eql, __a)
	84	{
	85	__profcxx_hashtable_construct(this, _Base::bucket_count());
	86	__profcxx_hashtable_construct2(this);
	87	}
	88
	89	template<typename _InputIterator>
	90	unordered_set(_InputIterator __f, _InputIterator __l,
	91	size_type __n = 10,
	92	const hasher& __hf = hasher(),
	93	const key_equal& __eql = key_equal(),
	94	const allocator_type& __a = allocator_type())
	95	: _Base(__f, __l, __n, __hf, __eql, __a)
	96	{
	97	__profcxx_hashtable_construct(this, _Base::bucket_count());
	98	__profcxx_hashtable_construct2(this);
	99	}
	100
	101	unordered_set(const _Base& __x)
	102	: _Base(__x)
	103	{
	104	__profcxx_hashtable_construct(this, _Base::bucket_count());
	105	__profcxx_hashtable_construct2(this);
	106	}
	107
	108	unordered_set(unordered_set&& __x)
	109	: _Base(std::forward<_Base>(__x))
	110	{
	111	__profcxx_hashtable_construct(this, _Base::bucket_count());
	112	__profcxx_hashtable_construct2(this);
	113	}
	114
	115	unordered_set(initializer_list<value_type> __l,
	116	size_type __n = 10,
	117	const hasher& __hf = hasher(),
	118	const key_equal& __eql = key_equal(),
	119	const allocator_type& __a = allocator_type())
	120	: _Base(__l, __n, __hf, __eql, __a) { }
	121
	122	unordered_set&
	123	operator=(const unordered_set& __x)
	124	{
	125	static_cast<_Base>(this) = __x;
	126	return *this;
	127	}
	128
	129	unordered_set&
	130	operator=(unordered_set&& __x)
	131	{
0462fd5e PC	132	// NB: DR 1204.
	133	// NB: DR 675.
	134	this->clear();
	135	this->swap(__x);
1218d701 SR	136	return *this;
	137	}
	138
	139	unordered_set&
	140	operator=(initializer_list<value_type> __l)
	141	{
	142	this->clear();
	143	this->insert(__l);
	144	return *this;
	145	}
	146
	147	~unordered_set()
	148	{
	149	__profcxx_hashtable_destruct(this, _Base::bucket_count(),
	150	_Base::size());
	151	_M_profile_destruct();
	152	}
	153
	154	void
	155	swap(unordered_set& __x)
	156	{
	157	_Base::swap(__x);
	158	}
	159
	160	void
	161	clear()
	162	{
	163	__profcxx_hashtable_destruct(this, _Base::bucket_count(),
	164	_Base::size());
	165	_M_profile_destruct();
	166	_Base::clear();
	167	}
5004040e	168
1218d701 SR	169	void
	170	insert(std::initializer_list<value_type> __l)
	171	{
	172	size_type __old_size = _Base::bucket_count();
	173	_Base::insert(__l);
	174	_M_profile_resize(__old_size, _Base::bucket_count());
	175	}
5004040e PC	176
	177	std::pair<iterator, bool>
	178	insert(const value_type& __obj)
1218d701 SR	179	{
1218d701 SR	180	size_type __old_size = _Base::bucket_count();
5004040e	181	std::pair<iterator, bool> __res = _Base::insert(__obj);
1218d701 SR	182	_M_profile_resize(__old_size, _Base::bucket_count());
	183	return __res;
	184	}
5004040e	185
1218d701	186	iterator
1218d701 SR	187	insert(const_iterator __iter, const value_type& __v)
	188	{
	189	size_type __old_size = _Base::bucket_count();
3b2524b1 PC	190	iterator __res = _Base::insert(__iter, __v);
	191	_M_profile_resize(__old_size, _Base::bucket_count());
	192	return __res;
1218d701 SR	193	}
	194
	195	template<typename _InputIter>
3b2524b1 PC	196	void
	197	insert(_InputIter __first, _InputIter __last)
	198	{
	199	size_type __old_size = _Base::bucket_count();
	200	_Base::insert(__first, __last);
	201	_M_profile_resize(__old_size, _Base::bucket_count());
	202	}
1218d701 SR	203
	204	void
	205	insert(const value_type* __first, const value_type* __last)
	206	{
	207	size_type __old_size = _Base::bucket_count();
	208	_Base::insert(__first, __last);
	209	_M_profile_resize(__old_size, _Base::bucket_count());
	210	}
	211
	212	void rehash(size_type __n)
	213	{
	214	size_type __old_size = _Base::bucket_count();
	215	_Base::rehash(__n);
	216	_M_profile_resize(__old_size, _Base::bucket_count());
	217	}
5004040e	218
1218d701 SR	219	private:
	220	_Base&
	221	_M_base() { return *this; }
	222
	223	const _Base&
	224	_M_base() const { return *this; }
	225
3b2524b1 PC	226	void
3b2524b1 PC	227	_M_profile_resize(size_type __old_size, size_type __new_size)
1218d701 SR	228	{
1218d701 SR	229	if (__old_size != __new_size)
3b2524b1	230	__profcxx_hashtable_resize(this, __old_size, __new_size);
1218d701	231	}
3b2524b1 PC	232
	233	void
	234	_M_profile_destruct()
1218d701 SR	235	{
1218d701 SR	236	size_type __hops = 0, __lc = 0, __chain = 0;
3b2524b1 PC	237	for (iterator __it = _M_base().begin(); __it != _M_base().end();
3b2524b1 PC	238	++__it)
1218d701	239	{
3b2524b1 PC	240	while (__it._M_cur_node->_M_next)
	241	{
	242	++__chain;
	243	++__it;
	244	}
	245
	246	if (__chain)
	247	{
	248	++__chain;
	249	__lc = __lc > __chain ? __lc : __chain;
	250	__hops += __chain * (__chain - 1) / 2;
	251	__chain = 0;
	252	}
1218d701 SR	253	}
	254	__profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
	255	}
	256
	257	};
3b2524b1	258
1218d701 SR	259	template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
	260	inline void
	261	swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
3b2524b1	262	unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1218d701 SR	263	{ __x.swap(__y); }
	264
	265	#undef _GLIBCXX_BASE
	266	#undef _GLIBCXX_STD_BASE
	267	#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
	268	#define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
	269
	270	/** @brief Unordered_multiset wrapper with performance instrumentation. */
	271	template<typename _Value,
	272	typename _Hash = std::hash<_Value>,
	273	typename _Pred = std::equal_to<_Value>,
	274	typename _Alloc = std::allocator<_Value> >
	275	class unordered_multiset
	276	: public _GLIBCXX_STD_BASE
	277	{
	278	typedef typename _GLIBCXX_STD_BASE _Base;
	279
	280	public:
	281	typedef typename _Base::size_type size_type;
	282	typedef typename _Base::hasher hasher;
	283	typedef typename _Base::key_equal key_equal;
	284	typedef typename _Base::allocator_type allocator_type;
	285	typedef typename _Base::key_type key_type;
	286	typedef typename _Base::value_type value_type;
	287	typedef typename _Base::difference_type difference_type;
	288	typedef typename _Base::reference reference;
	289	typedef typename _Base::const_reference const_reference;
1218d701 SR	290
	291	typedef typename _Base::iterator iterator;
	292	typedef typename _Base::const_iterator const_iterator;
	293
	294	explicit
	295	unordered_multiset(size_type __n = 10,
	296	const hasher& __hf = hasher(),
	297	const key_equal& __eql = key_equal(),
	298	const allocator_type& __a = allocator_type())
	299	: _Base(__n, __hf, __eql, __a)
	300	{
	301	__profcxx_hashtable_construct(this, _Base::bucket_count());
	302	}
	303
	304	template<typename _InputIterator>
	305	unordered_multiset(_InputIterator __f, _InputIterator __l,
	306	size_type __n = 10,
	307	const hasher& __hf = hasher(),
	308	const key_equal& __eql = key_equal(),
	309	const allocator_type& __a = allocator_type())
	310	: _Base(__f, __l, __n, __hf, __eql, __a)
	311	{
	312	__profcxx_hashtable_construct(this, _Base::bucket_count());
	313	}
	314
	315	unordered_multiset(const _Base& __x)
	316	: _Base(__x)
	317	{
	318	__profcxx_hashtable_construct(this, _Base::bucket_count());
	319	}
	320
	321	unordered_multiset(unordered_multiset&& __x)
	322	: _Base(std::forward<_Base>(__x))
	323	{
	324	__profcxx_hashtable_construct(this, _Base::bucket_count());
	325	}
	326
	327	unordered_multiset(initializer_list<value_type> __l,
	328	size_type __n = 10,
	329	const hasher& __hf = hasher(),
	330	const key_equal& __eql = key_equal(),
	331	const allocator_type& __a = allocator_type())
	332	: _Base(__l, __n, __hf, __eql, __a) { }
	333
	334	unordered_multiset&
	335	operator=(const unordered_multiset& __x)
	336	{
	337	static_cast<_Base>(this) = __x;
	338	return *this;
	339	}
	340
	341	unordered_multiset&
	342	operator=(unordered_multiset&& __x)
	343	{
0462fd5e PC	344	// NB: DR 1204.
	345	// NB: DR 675.
	346	this->clear();
	347	this->swap(__x);
1218d701 SR	348	return *this;
	349	}
	350
	351	unordered_multiset&
	352	operator=(initializer_list<value_type> __l)
	353	{
	354	this->clear();
	355	this->insert(__l);
	356	return *this;
	357	}
	358
	359	~unordered_multiset()
	360	{
	361	__profcxx_hashtable_destruct(this, _Base::bucket_count(),
	362	_Base::size());
	363	_M_profile_destruct();
	364	}
	365
	366	void
	367	swap(unordered_multiset& __x)
	368	{
	369	_Base::swap(__x);
	370	}
	371
	372	void
	373	clear()
	374	{
	375	__profcxx_hashtable_destruct(this, _Base::bucket_count(),
	376	_Base::size());
	377	_M_profile_destruct();
	378	_Base::clear();
	379	}
5004040e	380
1218d701 SR	381	void
	382	insert(std::initializer_list<value_type> __l)
	383	{
	384	size_type __old_size = _Base::bucket_count();
	385	_Base::insert(__l);
	386	_M_profile_resize(__old_size, _Base::bucket_count());
	387	}
5004040e PC	388
	389	iterator
	390	insert(const value_type& __obj)
1218d701 SR	391	{
1218d701 SR	392	size_type __old_size = _Base::bucket_count();
5004040e	393	iterator __res = _Base::insert(__obj);
1218d701 SR	394	_M_profile_resize(__old_size, _Base::bucket_count());
	395	return __res;
	396	}
5004040e	397
1218d701	398	iterator
1218d701 SR	399	insert(const_iterator __iter, const value_type& __v)
	400	{
	401	size_type __old_size = _Base::bucket_count();
3b2524b1 PC	402	iterator __res = _Base::insert(__iter, __v);
	403	_M_profile_resize(__old_size, _Base::bucket_count());
	404	return __res;
1218d701 SR	405	}
	406
	407	template<typename _InputIter>
3b2524b1 PC	408	void
	409	insert(_InputIter __first, _InputIter __last)
	410	{
	411	size_type __old_size = _Base::bucket_count();
	412	_Base::insert(__first, __last);
	413	_M_profile_resize(__old_size, _Base::bucket_count());
	414	}
1218d701 SR	415
	416	void
	417	insert(const value_type* __first, const value_type* __last)
	418	{
	419	size_type __old_size = _Base::bucket_count();
	420	_Base::insert(__first, __last);
	421	_M_profile_resize(__old_size, _Base::bucket_count());
	422	}
	423
	424	void rehash(size_type __n)
	425	{
	426	size_type __old_size = _Base::bucket_count();
	427	_Base::rehash(__n);
	428	_M_profile_resize(__old_size, _Base::bucket_count());
	429	}
5004040e	430
1218d701 SR	431	private:
	432	_Base&
	433	_M_base() { return *this; }
	434
	435	const _Base&
	436	_M_base() const { return *this; }
	437
3b2524b1 PC	438	void
3b2524b1 PC	439	_M_profile_resize(size_type __old_size, size_type __new_size)
1218d701 SR	440	{
1218d701 SR	441	if (__old_size != __new_size)
1218d701	442	__profcxx_hashtable_resize(this, __old_size, __new_size);
1218d701 SR	443	}
1218d701 SR	444
3b2524b1 PC	445	void
3b2524b1 PC	446	_M_profile_destruct()
1218d701 SR	447	{
1218d701 SR	448	size_type __hops = 0, __lc = 0, __chain = 0;
3b2524b1 PC	449	for (iterator __it = _M_base().begin(); __it != _M_base().end();
3b2524b1 PC	450	++__it)
1218d701	451	{
3b2524b1 PC	452	while (__it._M_cur_node->_M_next)
	453	{
	454	++__chain;
	455	++__it;
	456	}
	457
	458	if (__chain)
	459	{
	460	++__chain;
	461	__lc = __lc > __chain ? __lc : __chain;
	462	__hops += __chain * (__chain - 1) / 2;
	463	__chain = 0;
	464	}
1218d701 SR	465	}
	466	__profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
	467	}
	468
	469	};
3b2524b1	470
1218d701 SR	471	template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
	472	inline void
	473	swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
3b2524b1	474	unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1218d701 SR	475	{ __x.swap(__y); }
	476
	477	} // namespace __profile
	478	} // namespace std
	479
	480	#undef _GLIBCXX_BASE
	481	#undef _GLIBCXX_STD_BASE
	482
	483	#endif