libstdc++: Optimize operations on small size hashtable [PR 68303]

When hasher is identified as slow and the number of elements is limited in the
container use a brute-force loop on those elements to look for a given key using
the key_equal functor. For the moment the default threshold to consider the
container as small is 20.

libstdc++-v3/ChangeLog:

	PR libstdc++/68303
	* include/bits/hashtable_policy.h
	(_Hashtable_hash_traits<_Hash>): New.
	(_Hash_code_base<>::_M_hash_code(const _Hash_node_value<>&)): New.
	(_Hashtable_base<>::_M_key_equals): New.
	(_Hashtable_base<>::_M_equals): Use latter.
	(_Hashtable_base<>::_M_key_equals_tr): New.
	(_Hashtable_base<>::_M_equals_tr): Use latter.
	* include/bits/hashtable.h
	(_Hashtable<>::__small_size_threshold()): New, use _Hashtable_hash_traits.
	(_Hashtable<>::find): Loop through elements to look for key if size is lower
	than __small_size_threshold().
	(_Hashtable<>::_M_emplace(true_type, _Args&&...)): Likewise.
	(_Hashtable<>::_M_insert_unique(_Kt&&, _Args&&, const _NodeGenerator&)): Likewise.
	(_Hashtable<>::_M_compute_hash_code(const_iterator, const key_type&)): New.
	(_Hashtable<>::_M_emplace(const_iterator, false_type, _Args&&...)): Use latter.
	(_Hashtable<>::_M_find_before_node(const key_type&)): New.
	(_Hashtable<>::_M_erase(true_type, const key_type&)): Use latter.
	(_Hashtable<>::_M_erase(false_type, const key_type&)): Likewise.
	* src/c++11/hashtable_c++0x.cc: Include <bits/functional_hash.h>.
	* testsuite/util/testsuite_performance.h
	(report_performance): Use 9 width to display memory.
	* testsuite/performance/23_containers/insert_erase/unordered_small_size.cc:
	New performance test case.

0 files changed, 0 insertions, 0 deletions