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

// Profiling unordered_map/unordered_multimap 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_map
 *  This file is a GNU profile extension to the Standard C++ Library.
 */

#ifndef _GLIBCXX_PROFILE_UNORDERED_MAP
#define _GLIBCXX_PROFILE_UNORDERED_MAP 1

#include <profile/base.h>

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

#include <initializer_list>

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

namespace std
{
namespace __profile
{
  /// Class std::unordered_map wrapper with performance instrumentation.
  template<typename _Key, typename _Tp,
	   typename _Hash  = std::hash<_Key>,
	   typename _Pred = std::equal_to<_Key>,
	   typename _Alloc =  std::allocator<_Key> >
    class unordered_map
    : 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::mapped_type      mapped_type;

      typedef typename _Base::iterator iterator;
      typedef typename _Base::const_iterator const_iterator;

      explicit
      unordered_map(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_map(_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_map(const _Base& __x)
      : _Base(__x) 
      { 
        __profcxx_hashtable_construct(this, _Base::bucket_count());
        __profcxx_hashtable_construct2(this);
      }

      unordered_map(unordered_map&& __x)
      : _Base(std::forward<_Base>(__x)) 
      {
        __profcxx_hashtable_construct(this, _Base::bucket_count());
        __profcxx_hashtable_construct2(this);
      }

      unordered_map(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_map&
      operator=(const unordered_map& __x)
      {
	*static_cast<_Base*>(this) = __x;
	return *this;
      }

      unordered_map&
      operator=(unordered_map&& __x)
      {
	// NB: DR 1204.
	// NB: DR 675.
	this->clear();
	this->swap(__x);
	return *this;
      }

      unordered_map&
      operator=(initializer_list<value_type> __l)
      {
	this->clear();
	this->insert(__l);
	return *this;
      }

      ~unordered_map()
      {
        __profcxx_hashtable_destruct(this, _Base::bucket_count(),
				     _Base::size());
        _M_profile_destruct();
      }

      _Base&
      _M_base()       { return *this; }

      const _Base&
      _M_base() const { return *this; }


      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.base(), __last.base());
	  _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()); 
      }
     
      // operator []
      mapped_type&
      operator[](const _Key& _k)
      {
        size_type __old_size =  _Base::bucket_count();
        mapped_type& __res = _M_base()[_k];
        size_type __new_size =  _Base::bucket_count();
        _M_profile_resize(__old_size, _Base::bucket_count()); 
        return __res;
      }   

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

      void rehash(size_type __n)
      {
        size_type __old_size =  _Base::bucket_count();
        _Base::rehash(__n);
        _M_profile_resize(__old_size, _Base::bucket_count()); 
      }

    private:
      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 _Key, typename _Tp, typename _Hash,
	   typename _Pred, typename _Alloc>
    inline void
    swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__y); }

#undef _GLIBCXX_BASE
#undef _GLIBCXX_STD_BASE
#define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE

  /// Class std::unordered_multimap wrapper with performance instrumentation.
  template<typename _Key, typename _Tp,
	   typename _Hash  = std::hash<_Key>,
	   typename _Pred = std::equal_to<_Key>,
	   typename _Alloc =  std::allocator<_Key> >
    class unordered_multimap
    : 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_multimap(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_multimap(_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_multimap(const _Base& __x)
      : _Base(__x)
      {
        __profcxx_hashtable_construct(this, _Base::bucket_count());
      }

      unordered_multimap(unordered_multimap&& __x)
      : _Base(std::forward<_Base>(__x))
      {
        __profcxx_hashtable_construct(this, _Base::bucket_count());
      }

      unordered_multimap(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_multimap&
      operator=(const unordered_multimap& __x)
      {
	*static_cast<_Base*>(this) = __x;
	return *this;
      }

      unordered_multimap&
      operator=(unordered_multimap&& __x)
      {
	// NB: DR 1204.
	// NB: DR 675.
	this->clear();
	this->swap(__x);
	return *this;
      }

      unordered_multimap&
      operator=(initializer_list<value_type> __l)
      {
	this->clear();
	this->insert(__l);
	return *this;
      }

      ~unordered_multimap()
      {
        __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
				     _Base::size());
        _M_profile_destruct();
      }

      _Base&
      _M_base()       { return *this; }

      const _Base&
      _M_base() const { return *this; }


      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.base(), __last.base());
	  _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
      swap(unordered_multimap& __x)
      { _Base::swap(__x); }

      void rehash(size_type __n)
      {
        size_type __old_size =  _Base::bucket_count();
        _Base::rehash(__n);
        _M_profile_resize(__old_size, _Base::bucket_count()); 
      }

    private:
      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 _Key, typename _Tp, typename _Hash,
	   typename _Pred, typename _Alloc>
    inline void
    swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	 unordered_multimap<_Key, _Tp, _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_map/unordered_multimap 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_map
	31	* This file is a GNU profile extension to the Standard C++ Library.
	32	*/
	33
	34	#ifndef _GLIBCXX_PROFILE_UNORDERED_MAP
	35	#define _GLIBCXX_PROFILE_UNORDERED_MAP 1
	36
	37	#include <profile/base.h>
	38
	39	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	40	# include <unordered_map>
	41	#else
	42	# include <c++0x_warning.h>
	43	#endif
	44
	45	#include <initializer_list>
	46
	47	#define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
	48	#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
	49
	50	namespace std
	51	{
	52	namespace __profile
	53	{
9ee6a740	54	/// Class std::unordered_map wrapper with performance instrumentation.
1218d701 SR	55	template<typename _Key, typename _Tp,
	56	typename _Hash = std::hash<_Key>,
	57	typename _Pred = std::equal_to<_Key>,
	58	typename _Alloc = std::allocator<_Key> >
	59	class unordered_map
	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;
	74	typedef typename _Base::mapped_type mapped_type;
1218d701 SR	75
	76	typedef typename _Base::iterator iterator;
	77	typedef typename _Base::const_iterator const_iterator;
	78
	79	explicit
	80	unordered_map(size_type __n = 10,
	81	const hasher& __hf = hasher(),
	82	const key_equal& __eql = key_equal(),
	83	const allocator_type& __a = allocator_type())
	84	: _Base(__n, __hf, __eql, __a)
	85	{
	86	__profcxx_hashtable_construct(this, _Base::bucket_count());
	87	__profcxx_hashtable_construct2(this);
	88	}
	89
	90	template<typename _InputIterator>
	91	unordered_map(_InputIterator __f, _InputIterator __l,
	92	size_type __n = 10,
	93	const hasher& __hf = hasher(),
	94	const key_equal& __eql = key_equal(),
	95	const allocator_type& __a = allocator_type())
	96	: _Base(__f, __l, __n, __hf, __eql, __a)
	97	{
	98	__profcxx_hashtable_construct(this, _Base::bucket_count());
	99	__profcxx_hashtable_construct2(this);
	100	}
	101
	102	unordered_map(const _Base& __x)
	103	: _Base(__x)
	104	{
	105	__profcxx_hashtable_construct(this, _Base::bucket_count());
	106	__profcxx_hashtable_construct2(this);
	107	}
	108
	109	unordered_map(unordered_map&& __x)
	110	: _Base(std::forward<_Base>(__x))
	111	{
	112	__profcxx_hashtable_construct(this, _Base::bucket_count());
	113	__profcxx_hashtable_construct2(this);
	114	}
	115
	116	unordered_map(initializer_list<value_type> __l,
	117	size_type __n = 10,
	118	const hasher& __hf = hasher(),
	119	const key_equal& __eql = key_equal(),
	120	const allocator_type& __a = allocator_type())
	121	: _Base(__l, __n, __hf, __eql, __a) { }
	122
	123	unordered_map&
	124	operator=(const unordered_map& __x)
	125	{
	126	static_cast<_Base>(this) = __x;
	127	return *this;
	128	}
	129
	130	unordered_map&
	131	operator=(unordered_map&& __x)
	132	{
0462fd5e PC	133	// NB: DR 1204.
	134	// NB: DR 675.
	135	this->clear();
	136	this->swap(__x);
1218d701 SR	137	return *this;
	138	}
	139
	140	unordered_map&
	141	operator=(initializer_list<value_type> __l)
	142	{
	143	this->clear();
	144	this->insert(__l);
	145	return *this;
	146	}
	147
	148	~unordered_map()
	149	{
5004040e PC	150	__profcxx_hashtable_destruct(this, _Base::bucket_count(),
5004040e PC	151	_Base::size());
1218d701 SR	152	_M_profile_destruct();
	153	}
	154
	155	_Base&
	156	_M_base() { return *this; }
	157
	158	const _Base&
	159	_M_base() const { return *this; }
	160
	161
	162	void
	163	clear()
	164	{
5004040e PC	165	__profcxx_hashtable_destruct(this, _Base::bucket_count(),
5004040e PC	166	_Base::size());
1218d701 SR	167	_M_profile_destruct();
	168	_Base::clear();
	169	}
	170
	171	void
	172	insert(std::initializer_list<value_type> __l)
	173	{
	174	size_type __old_size = _Base::bucket_count();
	175	_Base::insert(__l);
	176	_M_profile_resize(__old_size, _Base::bucket_count());
	177	}
	178
5004040e	179	std::pair<iterator, bool>
1218d701 SR	180	insert(const value_type& __obj)
	181	{
	182	size_type __old_size = _Base::bucket_count();
5004040e	183	std::pair<iterator, bool> __res = _Base::insert(__obj);
1218d701 SR	184	_M_profile_resize(__old_size, _Base::bucket_count());
	185	return __res;
	186	}
5004040e	187
1218d701	188	iterator
1218d701 SR	189	insert(const_iterator __iter, const value_type& __v)
	190	{
	191	size_type __old_size = _Base::bucket_count();
3b2524b1	192	iterator __res = _Base::insert(__iter, __v);
1218d701	193	_M_profile_resize(__old_size, _Base::bucket_count());
3b2524b1	194	return __res;
1218d701 SR	195	}
	196
	197	template<typename _InputIter>
3b2524b1 PC	198	void
	199	insert(_InputIter __first, _InputIter __last)
	200	{
	201	size_type __old_size = _Base::bucket_count();
	202	_Base::insert(__first.base(), __last.base());
	203	_M_profile_resize(__old_size, _Base::bucket_count());
	204	}
1218d701 SR	205
	206	void
	207	insert(const value_type* __first, const value_type* __last)
	208	{
	209	size_type __old_size = _Base::bucket_count();
	210	_Base::insert(__first, __last);
	211	_M_profile_resize(__old_size, _Base::bucket_count());
	212	}
	213
	214	// operator []
	215	mapped_type&
	216	operator[](const _Key& _k)
	217	{
	218	size_type __old_size = _Base::bucket_count();
	219	mapped_type& __res = _M_base()[_k];
	220	size_type __new_size = _Base::bucket_count();
	221	_M_profile_resize(__old_size, _Base::bucket_count());
	222	return __res;
	223	}
	224
	225	void
	226	swap(unordered_map& __x)
3b2524b1 PC	227	{ _Base::swap(__x); }
3b2524b1 PC	228
1218d701 SR	229	void rehash(size_type __n)
	230	{
	231	size_type __old_size = _Base::bucket_count();
	232	_Base::rehash(__n);
	233	_M_profile_resize(__old_size, _Base::bucket_count());
	234	}
3b2524b1	235
1218d701	236	private:
3b2524b1 PC	237	void
3b2524b1 PC	238	_M_profile_resize(size_type __old_size, size_type __new_size)
1218d701 SR	239	{
1218d701 SR	240	if (__old_size != __new_size)
3b2524b1	241	__profcxx_hashtable_resize(this, __old_size, __new_size);
1218d701	242	}
3b2524b1 PC	243
	244	void
	245	_M_profile_destruct()
1218d701 SR	246	{
1218d701 SR	247	size_type __hops = 0, __lc = 0, __chain = 0;
3b2524b1 PC	248	for (iterator __it = _M_base().begin(); __it != _M_base().end();
	249	++__it)
	250	{
	251	while (__it._M_cur_node->_M_next)
	252	{
	253	++__chain;
	254	++__it;
	255	}
	256	if (__chain)
	257	{
	258	++__chain;
	259	__lc = __lc > __chain ? __lc : __chain;
	260	__hops += __chain * (__chain - 1) / 2;
	261	__chain = 0;
	262	}
	263	}
1218d701 SR	264	__profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
	265	}
	266	};
3b2524b1	267
1218d701	268	template<typename _Key, typename _Tp, typename _Hash,
3b2524b1	269	typename _Pred, typename _Alloc>
1218d701 SR	270	inline void
1218d701 SR	271	swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
3b2524b1	272	unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1218d701 SR	273	{ __x.swap(__y); }
	274
	275	#undef _GLIBCXX_BASE
	276	#undef _GLIBCXX_STD_BASE
	277	#define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
	278	#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
	279
9ee6a740	280	/// Class std::unordered_multimap wrapper with performance instrumentation.
1218d701 SR	281	template<typename _Key, typename _Tp,
	282	typename _Hash = std::hash<_Key>,
	283	typename _Pred = std::equal_to<_Key>,
	284	typename _Alloc = std::allocator<_Key> >
	285	class unordered_multimap
	286	: public _GLIBCXX_STD_BASE
	287	{
	288	typedef typename _GLIBCXX_STD_BASE _Base;
	289
	290	public:
	291	typedef typename _Base::size_type size_type;
	292	typedef typename _Base::hasher hasher;
	293	typedef typename _Base::key_equal key_equal;
	294	typedef typename _Base::allocator_type allocator_type;
	295	typedef typename _Base::key_type key_type;
	296	typedef typename _Base::value_type value_type;
	297	typedef typename _Base::difference_type difference_type;
	298	typedef typename _Base::reference reference;
	299	typedef typename _Base::const_reference const_reference;
1218d701 SR	300
	301	typedef typename _Base::iterator iterator;
	302	typedef typename _Base::const_iterator const_iterator;
	303
	304	explicit
	305	unordered_multimap(size_type __n = 10,
	306	const hasher& __hf = hasher(),
	307	const key_equal& __eql = key_equal(),
	308	const allocator_type& __a = allocator_type())
	309	: _Base(__n, __hf, __eql, __a)
	310	{
	311	__profcxx_hashtable_construct(this, _Base::bucket_count());
	312	}
	313	template<typename _InputIterator>
	314	unordered_multimap(_InputIterator __f, _InputIterator __l,
	315	size_type __n = 10,
	316	const hasher& __hf = hasher(),
	317	const key_equal& __eql = key_equal(),
	318	const allocator_type& __a = allocator_type())
	319	: _Base(__f, __l, __n, __hf, __eql, __a)
	320	{
	321	__profcxx_hashtable_construct(this, _Base::bucket_count());
	322	}
	323
	324	unordered_multimap(const _Base& __x)
	325	: _Base(__x)
	326	{
	327	__profcxx_hashtable_construct(this, _Base::bucket_count());
	328	}
	329
	330	unordered_multimap(unordered_multimap&& __x)
	331	: _Base(std::forward<_Base>(__x))
	332	{
	333	__profcxx_hashtable_construct(this, _Base::bucket_count());
	334	}
	335
	336	unordered_multimap(initializer_list<value_type> __l,
	337	size_type __n = 10,
	338	const hasher& __hf = hasher(),
	339	const key_equal& __eql = key_equal(),
	340	const allocator_type& __a = allocator_type())
	341	: _Base(__l, __n, __hf, __eql, __a) { }
	342
	343	unordered_multimap&
	344	operator=(const unordered_multimap& __x)
	345	{
	346	static_cast<_Base>(this) = __x;
	347	return *this;
	348	}
	349
	350	unordered_multimap&
	351	operator=(unordered_multimap&& __x)
	352	{
0462fd5e PC	353	// NB: DR 1204.
	354	// NB: DR 675.
	355	this->clear();
	356	this->swap(__x);
1218d701 SR	357	return *this;
	358	}
	359
	360	unordered_multimap&
	361	operator=(initializer_list<value_type> __l)
	362	{
	363	this->clear();
	364	this->insert(__l);
	365	return *this;
	366	}
	367
	368	~unordered_multimap()
	369	{
9ee6a740 BK	370	__profcxx_hashtable_destruct(this, _Base::bucket_count(),
9ee6a740 BK	371	_Base::size());
1218d701 SR	372	_M_profile_destruct();
	373	}
	374
	375	_Base&
	376	_M_base() { return *this; }
	377
	378	const _Base&
	379	_M_base() const { return *this; }
	380
	381
	382	void
	383	clear()
	384	{
9ee6a740 BK	385	__profcxx_hashtable_destruct(this, _Base::bucket_count(),
9ee6a740 BK	386	_Base::size());
1218d701 SR	387	_M_profile_destruct();
	388	_Base::clear();
	389	}
	390
	391	void
	392	insert(std::initializer_list<value_type> __l)
	393	{
	394	size_type __old_size = _Base::bucket_count();
	395	_Base::insert(__l);
	396	_M_profile_resize(__old_size, _Base::bucket_count());
	397	}
	398
5004040e	399	iterator
1218d701 SR	400	insert(const value_type& __obj)
	401	{
	402	size_type __old_size = _Base::bucket_count();
5004040e	403	iterator __res = _Base::insert(__obj);
1218d701 SR	404	_M_profile_resize(__old_size, _Base::bucket_count());
	405	return __res;
	406	}
5004040e	407
1218d701	408	iterator
1218d701 SR	409	insert(const_iterator __iter, const value_type& __v)
	410	{
	411	size_type __old_size = _Base::bucket_count();
3b2524b1	412	iterator __res =_Base::insert(__iter, __v);
1218d701	413	_M_profile_resize(__old_size, _Base::bucket_count());
3b2524b1	414	return __res;
1218d701 SR	415	}
	416
	417	template<typename _InputIter>
3b2524b1 PC	418	void
	419	insert(_InputIter __first, _InputIter __last)
	420	{
	421	size_type __old_size = _Base::bucket_count();
	422	_Base::insert(__first.base(), __last.base());
	423	_M_profile_resize(__old_size, _Base::bucket_count());
	424	}
1218d701 SR	425
	426	void
	427	insert(const value_type* __first, const value_type* __last)
	428	{
	429	size_type __old_size = _Base::bucket_count();
	430	_Base::insert(__first, __last);
	431	_M_profile_resize(__old_size, _Base::bucket_count());
	432	}
	433
	434	void
	435	swap(unordered_multimap& __x)
3b2524b1	436	{ _Base::swap(__x); }
1218d701 SR	437
	438	void rehash(size_type __n)
	439	{
	440	size_type __old_size = _Base::bucket_count();
	441	_Base::rehash(__n);
	442	_M_profile_resize(__old_size, _Base::bucket_count());
	443	}
3b2524b1	444
1218d701	445	private:
3b2524b1 PC	446	void
3b2524b1 PC	447	_M_profile_resize(size_type __old_size, size_type __new_size)
1218d701 SR	448	{
1218d701 SR	449	if (__old_size != __new_size)
1218d701	450	__profcxx_hashtable_resize(this, __old_size, __new_size);
1218d701 SR	451	}
1218d701 SR	452
3b2524b1 PC	453	void
3b2524b1 PC	454	_M_profile_destruct()
1218d701 SR	455	{
1218d701 SR	456	size_type __hops = 0, __lc = 0, __chain = 0;
3b2524b1 PC	457	for (iterator __it = _M_base().begin(); __it != _M_base().end();
	458	++__it)
	459	{
	460	while (__it._M_cur_node->_M_next)
	461	{
	462	++__chain;
	463	++__it;
	464	}
	465	if (__chain)
	466	{
	467	++__chain;
	468	__lc = __lc > __chain ? __lc : __chain;
	469	__hops += __chain * (__chain - 1) / 2;
	470	__chain = 0;
	471	}
	472	}
1218d701 SR	473	__profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
	474	}
	475
	476	};
3b2524b1	477
1218d701	478	template<typename _Key, typename _Tp, typename _Hash,
3b2524b1	479	typename _Pred, typename _Alloc>
1218d701 SR	480	inline void
1218d701 SR	481	swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
3b2524b1	482	unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1218d701 SR	483	{ __x.swap(__y); }
	484
	485	} // namespace __profile
	486	} // namespace std
	487
	488	#undef _GLIBCXX_BASE
	489	#undef _GLIBCXX_STD_BASE
	490
	491	#endif