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

// Profiling unordered_map/unordered_multimap implementation -*- C++ -*-

// Copyright (C) 2009 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
{
  /** @brief 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 std::pair<typename _Base::iterator, bool> pair_type;
      typedef typename _Base::insert_return_type insert_return_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 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()); 
      }

       insert_return_type
      insert(const value_type& __obj)
      {
        size_type __old_size =  _Base::bucket_count();
        insert_return_type __res = _Base::insert(__obj);
        _M_profile_resize(__old_size, _Base::bucket_count()); 
        return __res;
      }
      iterator
      insert(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;
      }

      const_iterator
      insert(const_iterator __iter, const value_type& __v)
      { 
        size_type __old_size = _Base::bucket_count(); 
        const_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

  /** @brief 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 std::pair<typename _Base::iterator, bool> pair_type;
      typedef typename _Base::insert_return_type insert_return_type;

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

      insert_return_type
      insert(const value_type& __obj)
      {
        size_type __old_size =  _Base::bucket_count();
        insert_return_type __res = _Base::insert(__obj);
        _M_profile_resize(__old_size, _Base::bucket_count()); 
        return __res;
      }
      iterator
      insert(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;
      }

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