Subversion Repositories Kolibri OS

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

// Copyright (C) 2013 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

// .

/** @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 _Value, bool _Cache_hash_code>

    struct _Bucket_index_helper;

  template

    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

    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

    struct _Bucket_index_helper<_UnorderedCont,

				std::pair, false>

    {

      typedef std::pair _Value;

      static std::size_t

      bucket(const _UnorderedCont& __uc,

	     const __detail::_Hash_node<_Value, false>* __node)

      { return __uc.bucket(__node->_M_v.first); }

    };

  template

    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 _Value, bool _Cache_hash_code>

    struct _Equal_helper;

  template

    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 _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 _Key, typename _Mapped>

    struct _Equal_helper<_UnorderedCont, std::pair, true>

    {

      typedef std::pair _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 _Key, typename _Mapped>

    struct _Equal_helper<_UnorderedCont, std::pair, false>

    {

      typedef std::pair _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

    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

    class _Unordered_profile

    {

      _UnorderedCont&

      _M_conjure()

      { return *(static_cast<_UnorderedCont*>(this)); }

      using __unique_keys = std::integral_constant;

    protected:

      _Unordered_profile()

      {

	auto& __uc = _M_conjure();

        __profcxx_hashtable_construct(&__uc, __uc.bucket_count());

	__profcxx_hashtable_construct2(&__uc);

      }

      _Unordered_profile(const _Unordered_profile&)

	: _Unordered_profile() { }

      _Unordered_profile(_Unordered_profile&&)

	: _Unordered_profile() { }

      ~_Unordered_profile() noexcept

      {

	auto& __uc = _M_conjure();

        __profcxx_hashtable_destruct(&__uc, __uc.bucket_count(), __uc.size());

        _M_profile_destruct();

      }

      _Unordered_profile&

      operator=(const _Unordered_profile&) = default;

      _Unordered_profile&

      operator=(_Unordered_profile&&) = default;

      void

      _M_profile_destruct()

      {

	if (!__profcxx_inefficient_hash_is_on())

	  return;

	_M_profile_destruct(__unique_keys());

      }

    private:

      void

      _M_profile_destruct(std::true_type);

      void

      _M_profile_destruct(std::false_type);

    };

  template

    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_hashtable_destruct2(&__uc, __lc, __uc.size(), __hops);

    }

  template

    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_hashtable_destruct2(&__uc, __lc, __unique_size, __hops);

    }

} // namespace __profile

} // namespace std

#endif