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

// Profiling unordered containers implementation details -*- C++ -*-

// Copyright (C) 2013-2019 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 3, 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.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING3.  If not see
// <http://www.gnu.org/licenses/>.

/** @file profile/unordered_base.h
 *  This file is a GNU profile extension to the Standard C++ Library.
 */

#ifndef _GLIBCXX_PROFILE_UNORDERED
#define _GLIBCXX_PROFILE_UNORDERED 1

namespace std _GLIBCXX_VISIBILITY(default)
{
namespace __profile
{
  template<typename _UnorderedCont,
	   typename _Value, bool _Cache_hash_code>
    struct _Bucket_index_helper;

  template<typename _UnorderedCont, typename _Value>
    struct _Bucket_index_helper<_UnorderedCont, _Value, true>
    {
      static std::size_t
      bucket(const _UnorderedCont& __uc,
	     const __detail::_Hash_node<_Value, true>* __node)
      { return __node->_M_hash_code % __uc.bucket_count(); }
    };

  template<typename _UnorderedCont, typename _Value>
    struct _Bucket_index_helper<_UnorderedCont, _Value, false>
    {
      static std::size_t
      bucket(const _UnorderedCont& __uc,
	     const __detail::_Hash_node<_Value, false>* __node)
      { return __uc.bucket(__node->_M_v()); }
    };

  template<typename _UnorderedCont, typename _Key, typename _Mapped>
    struct _Bucket_index_helper<_UnorderedCont,
				std::pair<const _Key, _Mapped>, false>
    {
      typedef std::pair<const _Key, _Mapped> _Value;

      static std::size_t
      bucket(const _UnorderedCont& __uc,
	     const __detail::_Hash_node<_Value, false>* __node)
      { return __uc.bucket(__node->_M_v().first); }
    };

  template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
    std::size_t
    __get_bucket_index(const _UnorderedCont& __uc,
		       const __detail::_Hash_node<_Value, _Cache_hash_code>* __node)
    {
      using __bucket_index_helper
	= _Bucket_index_helper<_UnorderedCont, _Value, _Cache_hash_code>;
      return __bucket_index_helper::bucket(__uc, __node);
    }

  template<typename _UnorderedCont,
	   typename _Value, bool _Cache_hash_code>
    struct _Equal_helper;

  template<typename _UnorderedCont, typename _Value>
    struct _Equal_helper<_UnorderedCont, _Value, true>
    {
      static std::size_t
      are_equal(const _UnorderedCont& __uc,
		const __detail::_Hash_node<_Value, true>* __lhs,
		const __detail::_Hash_node<_Value, true>* __rhs)
      {
	return __lhs->_M_hash_code == __rhs->_M_hash_code
	  && __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v());
      }
    };

  template<typename _UnorderedCont,
	   typename _Value>
    struct _Equal_helper<_UnorderedCont, _Value, false>
    {
      static std::size_t
      are_equal(const _UnorderedCont& __uc,
		const __detail::_Hash_node<_Value, false>* __lhs,
		const __detail::_Hash_node<_Value, false>* __rhs)
      { return __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v()); }
    };

  template<typename _UnorderedCont,
	   typename _Key, typename _Mapped>
    struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, true>
    {
      typedef std::pair<const _Key, _Mapped> _Value;

      static std::size_t
      are_equal(const _UnorderedCont& __uc,
		const __detail::_Hash_node<_Value, true>* __lhs,
		const __detail::_Hash_node<_Value, true>* __rhs)
      {
	return __lhs->_M_hash_code == __rhs->_M_hash_code
	  && __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first);
      }
    };

  template<typename _UnorderedCont,
	   typename _Key, typename _Mapped>
    struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, false>
    {
      typedef std::pair<const _Key, _Mapped> _Value;

      static std::size_t
      are_equal(const _UnorderedCont& __uc,
		const __detail::_Hash_node<_Value, false>* __lhs,
		const __detail::_Hash_node<_Value, false>* __rhs)
      { return __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first); }
    };

  template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
    bool
    __are_equal(const _UnorderedCont& __uc,
		const __detail::_Hash_node<_Value, _Cache_hash_code>* __lhs,
		const __detail::_Hash_node<_Value, _Cache_hash_code>* __rhs)
  {
    using __equal_helper
      = _Equal_helper<_UnorderedCont, _Value, _Cache_hash_code>;
    return __equal_helper::are_equal(__uc, __lhs, __rhs);
  }

  template<typename _UnorderedCont, bool _Unique_keys>
    class _Unordered_profile
    {
      _UnorderedCont&
      _M_conjure()
      { return *(static_cast<_UnorderedCont*>(this)); }

      using __unique_keys = std::integral_constant<bool, _Unique_keys>;

    protected:
      _Unordered_profile() noexcept
      { _M_profile_construct(); }

      _Unordered_profile(const _Unordered_profile&) noexcept
	: _Unordered_profile() { }

      _Unordered_profile(_Unordered_profile&& __other) noexcept
	: _Unordered_profile()
      { _M_swap(__other); }

      ~_Unordered_profile()
      { _M_profile_destruct(); }

      _Unordered_profile&
      operator=(const _Unordered_profile&) noexcept
      {
	// Assignment just reset profiling.
	_M_profile_destruct();
	_M_profile_construct();
      }

      _Unordered_profile&
      operator=(_Unordered_profile&& __other) noexcept
      {
	// Take profiling of the moved instance...
	_M_swap(__other);

	// ...and then reset other instance profiling.
	__other._M_profile_destruct();
	__other._M_profile_construct();
      }

      void
      _M_profile_construct() noexcept
      {
	auto& __uc = _M_conjure();
	_M_size_info = __profcxx_hashtable_size_construct(__uc.bucket_count());
	_M_hashfunc_info = __profcxx_hash_func_construct();
      }

      void
      _M_profile_destruct() noexcept
      {
	auto& __uc = _M_conjure();
	__profcxx_hashtable_size_destruct(_M_size_info,
					  __uc.bucket_count(), __uc.size());
	_M_size_info = 0;

	if (!_M_hashfunc_info)
	  return;

	_M_profile_destruct(__unique_keys());
	_M_hashfunc_info = 0;
      }

      void
      _M_swap(_Unordered_profile& __other) noexcept
      {
	std::swap(_M_size_info, __other._M_size_info);
	std::swap(_M_hashfunc_info, __other._M_hashfunc_info);
      }

      void
      _M_profile_resize(std::size_t __old_size)
      {
	auto __new_size = _M_conjure().bucket_count();
	if (__old_size != __new_size)
	  __profcxx_hashtable_size_resize(_M_size_info, __old_size, __new_size);
      }

      __gnu_profile::__container_size_info* _M_size_info;
      __gnu_profile::__hashfunc_info* _M_hashfunc_info;

    private:
      void
      _M_profile_destruct(std::true_type);

      void
      _M_profile_destruct(std::false_type);
    };

  template<typename _UnorderedCont, bool _Unique_keys>
    void
    _Unordered_profile<_UnorderedCont, _Unique_keys>::
    _M_profile_destruct(std::true_type)
    {
      auto& __uc = _M_conjure();
      std::size_t __hops = 0, __lc = 0, __chain = 0;
      auto __it = __uc.begin();
      while (__it != __uc.end())
	{
	  auto __bkt = __get_bucket_index(__uc, __it._M_cur);
	  auto __lit = __uc.begin(__bkt);
	  auto __lend = __uc.end(__bkt);
	  for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
	    ++__chain;

	  if (__chain)
	    {
	      ++__chain;
	      __lc = __lc > __chain ? __lc : __chain;
	      __hops += __chain * (__chain - 1) / 2;
	      __chain = 0;
	    }
	}

      __profcxx_hash_func_destruct(_M_hashfunc_info,
				   __lc, __uc.size(), __hops);
    }

  template<typename _UnorderedCont, bool _Unique_keys>
    void
    _Unordered_profile<_UnorderedCont, _Unique_keys>::
    _M_profile_destruct(std::false_type)
    {
      auto& __uc = _M_conjure();
      std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0;
      auto __it = __uc.begin();
      while (__it != __uc.end())
	{
	  auto __bkt = __get_bucket_index(__uc, __it._M_cur);
	  auto __lit = __uc.begin(__bkt);
	  auto __lend = __uc.end(__bkt);
	  auto __pit = __it;
	  ++__unique_size;
	  for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
	    {
	      if (!__are_equal(__uc, __pit._M_cur, __it._M_cur))
		{
		  ++__chain;
		  ++__unique_size;
		  __pit = __it;
		}
	    }

	  if (__chain)
	    {
	      ++__chain;
	      __lc = __lc > __chain ? __lc : __chain;
	      __hops += __chain * (__chain - 1) / 2;
	      __chain = 0;
	    }
	}

      __profcxx_hash_func_destruct(_M_hashfunc_info,
				   __lc, __unique_size, __hops);
    }

} // namespace __profile
} // namespace std

#endif
Commit	Line	Data
c50ff294	1	// Profiling unordered containers implementation details -- C++ --
c50ff294	2
fbd26352	3	// Copyright (C) 2013-2019 Free Software Foundation, Inc.
c50ff294	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 3, 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	// Under Section 7 of GPL version 3, you are granted additional
	17	// permissions described in the GCC Runtime Library Exception, version
	18	// 3.1, as published by the Free Software Foundation.
	19
	20	// You should have received a copy of the GNU General Public License along
	21	// with this library; see the file COPYING3. If not see
	22	// <http://www.gnu.org/licenses/>.
	23
	24	/** @file profile/unordered_base.h
	25	* This file is a GNU profile extension to the Standard C++ Library.
	26	*/
	27
	28	#ifndef _GLIBCXX_PROFILE_UNORDERED
	29	#define _GLIBCXX_PROFILE_UNORDERED 1
	30
	31	namespace std _GLIBCXX_VISIBILITY(default)
	32	{
	33	namespace __profile
	34	{
	35	template<typename _UnorderedCont,
	36	typename _Value, bool _Cache_hash_code>
	37	struct _Bucket_index_helper;
	38
	39	template<typename _UnorderedCont, typename _Value>
	40	struct _Bucket_index_helper<_UnorderedCont, _Value, true>
	41	{
	42	static std::size_t
	43	bucket(const _UnorderedCont& __uc,
	44	const __detail::_Hash_node<_Value, true>* __node)
	45	{ return __node->_M_hash_code % __uc.bucket_count(); }
	46	};
	47
	48	template<typename _UnorderedCont, typename _Value>
	49	struct _Bucket_index_helper<_UnorderedCont, _Value, false>
	50	{
	51	static std::size_t
	52	bucket(const _UnorderedCont& __uc,
	53	const __detail::_Hash_node<_Value, false>* __node)
	54	{ return __uc.bucket(__node->_M_v()); }
	55	};
	56
	57	template<typename _UnorderedCont, typename _Key, typename _Mapped>
	58	struct _Bucket_index_helper<_UnorderedCont,
	59	std::pair<const _Key, _Mapped>, false>
	60	{
	61	typedef std::pair<const _Key, _Mapped> _Value;
	62
	63	static std::size_t
	64	bucket(const _UnorderedCont& __uc,
	65	const __detail::_Hash_node<_Value, false>* __node)
	66	{ return __uc.bucket(__node->_M_v().first); }
	67	};
68
69	template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
70	std::size_t
71	__get_bucket_index(const _UnorderedCont& __uc,
72	const __detail::_Hash_node<_Value, _Cache_hash_code>* __node)
73	{
74	using __bucket_index_helper
75	= _Bucket_index_helper<_UnorderedCont, _Value, _Cache_hash_code>;
76	return __bucket_index_helper::bucket(__uc, __node);
77	}
78
79	template<typename _UnorderedCont,
80	typename _Value, bool _Cache_hash_code>
81	struct _Equal_helper;
82
83	template<typename _UnorderedCont, typename _Value>
84	struct _Equal_helper<_UnorderedCont, _Value, true>
85	{
86	static std::size_t
87	are_equal(const _UnorderedCont& __uc,
88	const __detail::_Hash_node<_Value, true>* __lhs,
89	const __detail::_Hash_node<_Value, true>* __rhs)
90	{
91	return __lhs->_M_hash_code == __rhs->_M_hash_code
92	&& __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v());
93	}
94	};
95
96	template<typename _UnorderedCont,
97	typename _Value>
98	struct _Equal_helper<_UnorderedCont, _Value, false>
99	{
100	static std::size_t
101	are_equal(const _UnorderedCont& __uc,
102	const __detail::_Hash_node<_Value, false>* __lhs,
103	const __detail::_Hash_node<_Value, false>* __rhs)
104	{ return __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v()); }
105	};
106
107	template<typename _UnorderedCont,
108	typename _Key, typename _Mapped>
109	struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, true>
110	{
111	typedef std::pair<const _Key, _Mapped> _Value;
112
113	static std::size_t
114	are_equal(const _UnorderedCont& __uc,
115	const __detail::_Hash_node<_Value, true>* __lhs,
116	const __detail::_Hash_node<_Value, true>* __rhs)
117	{
118	return __lhs->_M_hash_code == __rhs->_M_hash_code
119	&& __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first);
120	}
121	};
122
123	template<typename _UnorderedCont,
124	typename _Key, typename _Mapped>
125	struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, false>
126	{
127	typedef std::pair<const _Key, _Mapped> _Value;
128
129	static std::size_t
130	are_equal(const _UnorderedCont& __uc,
131	const __detail::_Hash_node<_Value, false>* __lhs,
132	const __detail::_Hash_node<_Value, false>* __rhs)
133	{ return __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first); }
134	};
135
136	template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
137	bool
138	__are_equal(const _UnorderedCont& __uc,
139	const __detail::_Hash_node<_Value, _Cache_hash_code>* __lhs,
140	const __detail::_Hash_node<_Value, _Cache_hash_code>* __rhs)
141	{
142	using __equal_helper
143	= _Equal_helper<_UnorderedCont, _Value, _Cache_hash_code>;
144	return __equal_helper::are_equal(__uc, __lhs, __rhs);
145	}
146
147	template<typename _UnorderedCont, bool _Unique_keys>
148	class _Unordered_profile
149	{
150	_UnorderedCont&
151	_M_conjure()
152	{ return (static_cast<_UnorderedCont>(this)); }
153
154	using __unique_keys = std::integral_constant<bool, _Unique_keys>;
155
156	protected:
1675d1be	157	_Unordered_profile() noexcept
	158	{ _M_profile_construct(); }
	159
	160	_Unordered_profile(const _Unordered_profile&) noexcept
c50ff294	161	: _Unordered_profile() { }
c50ff294	162
1675d1be	163	_Unordered_profile(_Unordered_profile&& __other) noexcept
	164	: _Unordered_profile()
	165	{ _M_swap(__other); }
	166
	167	~_Unordered_profile()
	168	{ _M_profile_destruct(); }
	169
	170	_Unordered_profile&
	171	operator=(const _Unordered_profile&) noexcept
c50ff294	172	{
1675d1be	173	// Assignment just reset profiling.
5f70fed5	174	_M_profile_destruct();
1675d1be	175	_M_profile_construct();
c50ff294	176	}
	177
	178	_Unordered_profile&
1675d1be	179	operator=(_Unordered_profile&& __other) noexcept
	180	{
	181	// Take profiling of the moved instance...
	182	_M_swap(__other);
c50ff294	183
1675d1be	184	// ...and then reset other instance profiling.
	185	__other._M_profile_destruct();
	186	__other._M_profile_construct();
	187	}
	188
	189	void
	190	_M_profile_construct() noexcept
	191	{
	192	auto& __uc = _M_conjure();
	193	_M_size_info = __profcxx_hashtable_size_construct(__uc.bucket_count());
	194	_M_hashfunc_info = __profcxx_hash_func_construct();
	195	}
c50ff294	196
c50ff294	197	void
1675d1be	198	_M_profile_destruct() noexcept
c50ff294	199	{
1675d1be	200	auto& __uc = _M_conjure();
	201	__profcxx_hashtable_size_destruct(_M_size_info,
	202	__uc.bucket_count(), __uc.size());
	203	_M_size_info = 0;
	204
	205	if (!_M_hashfunc_info)
c50ff294	206	return;
	207
	208	_M_profile_destruct(__unique_keys());
1675d1be	209	_M_hashfunc_info = 0;
	210	}
	211
	212	void
	213	_M_swap(_Unordered_profile& __other) noexcept
	214	{
	215	std::swap(_M_size_info, __other._M_size_info);
	216	std::swap(_M_hashfunc_info, __other._M_hashfunc_info);
c50ff294	217	}
c50ff294	218
1675d1be	219	void
	220	_M_profile_resize(std::size_t __old_size)
	221	{
	222	auto __new_size = _M_conjure().bucket_count();
	223	if (__old_size != __new_size)
	224	__profcxx_hashtable_size_resize(_M_size_info, __old_size, __new_size);
	225	}
	226
	227	__gnu_profile::__container_size_info* _M_size_info;
	228	__gnu_profile::__hashfunc_info* _M_hashfunc_info;
	229
c50ff294	230	private:
	231	void
	232	_M_profile_destruct(std::true_type);
	233
	234	void
	235	_M_profile_destruct(std::false_type);
	236	};
	237
	238	template<typename _UnorderedCont, bool _Unique_keys>
	239	void
	240	_Unordered_profile<_UnorderedCont, _Unique_keys>::
	241	_M_profile_destruct(std::true_type)
	242	{
	243	auto& __uc = _M_conjure();
	244	std::size_t __hops = 0, __lc = 0, __chain = 0;
	245	auto __it = __uc.begin();
	246	while (__it != __uc.end())
	247	{
	248	auto __bkt = __get_bucket_index(__uc, __it._M_cur);
	249	auto __lit = __uc.begin(__bkt);
	250	auto __lend = __uc.end(__bkt);
	251	for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
	252	++__chain;
5f70fed5	253
c50ff294	254	if (__chain)
	255	{
	256	++__chain;
	257	__lc = __lc > __chain ? __lc : __chain;
	258	__hops += __chain * (__chain - 1) / 2;
	259	__chain = 0;
	260	}
	261	}
1675d1be	262
	263	__profcxx_hash_func_destruct(_M_hashfunc_info,
	264	__lc, __uc.size(), __hops);
c50ff294	265	}
	266
	267	template<typename _UnorderedCont, bool _Unique_keys>
	268	void
	269	_Unordered_profile<_UnorderedCont, _Unique_keys>::
	270	_M_profile_destruct(std::false_type)
	271	{
	272	auto& __uc = _M_conjure();
	273	std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0;
	274	auto __it = __uc.begin();
	275	while (__it != __uc.end())
	276	{
	277	auto __bkt = __get_bucket_index(__uc, __it._M_cur);
	278	auto __lit = __uc.begin(__bkt);
	279	auto __lend = __uc.end(__bkt);
	280	auto __pit = __it;
	281	++__unique_size;
	282	for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
	283	{
	284	if (!__are_equal(__uc, __pit._M_cur, __it._M_cur))
	285	{
	286	++__chain;
	287	++__unique_size;
	288	__pit = __it;
	289	}
	290	}
5f70fed5	291
c50ff294	292	if (__chain)
	293	{
	294	++__chain;
	295	__lc = __lc > __chain ? __lc : __chain;
	296	__hops += __chain * (__chain - 1) / 2;
	297	__chain = 0;
	298	}
	299	}
1675d1be	300
	301	__profcxx_hash_func_destruct(_M_hashfunc_info,
	302	__lc, __unique_size, __hops);
c50ff294	303	}
	304
	305	} // namespace __profile
	306	} // namespace std
	307
	308	#endif