Context Navigation

source: trunk/nv/stl/unordered_map.hh @ 431

Last change on this file since 431 was 431, checked in by epyon, 10 years ago
hash storage type string hash storage type several minor fixes more cleanups needed
File size: 11.8 KB

Rev	Line
[390]	1	// Copyright (C) 2015 ChaosForge Ltd
	2	// http://chaosforge.org/
	3	//
[395]	4	// This file is part of Nova libraries.
	5	// For conditions of distribution and use, see copying.txt file in root folder.
[390]	6
	7	/**
[395]	8	* @file unordered_map.hh
	9	* @author Kornel Kisielewicz epyon@chaosforge.org
	10	* @brief unordered_map
	11	*/
[390]	12
	13	#ifndef NV_STL_UNORDERED_MAP_HH
	14	#define NV_STL_UNORDERED_MAP_HH
	15
[395]	16	#include <nv/common.hh>
[390]	17	#include <nv/stl/container/hash_table.hh>
	18	#include <nv/stl/utility/pair.hh>
[408]	19	#include <nv/stl/functional/hash.hh>
	20	#include <nv/stl/functional/comparisons.hh>
	21	#include <nv/stl/memory.hh>
[390]	22
	23	namespace nv
	24	{
[403]	25
[390]	26	template <
[408]	27	typename T,
	28	typename IsEqual = equal_to<T>,
	29	bool IsEmpty = is_empty< IsEqual >::value
	30	>
	31	struct compare_policy;
	32
	33
	34	template < typename T >
	35	struct compare_policy< T, equal_to<T>, true >
	36	{
	37	constexpr bool compare( const T& t1, const T& t2 ) const
	38	{
	39	return t1 == t2;
	40	}
	41	equal_to<T> key_eq() const { return equal_to<T>(); }
	42	};
	43
	44	template < typename T, typename IsEqual >
	45	struct compare_policy< T, IsEqual, true > : private IsEqual
	46	{
	47	constexpr bool compare( const T& t1, const T& t2 ) const
	48	{
	49	return ( *this )( t1 == t2 );
	50	}
	51	IsEqual key_eq() const { return ( *this ); }
	52	};
	53
	54	template < typename T, typename IsEqual >
	55	struct compare_policy< T, IsEqual, false >
	56	{
	57	constexpr bool compare( const T& t1, const T& t2 ) const
	58	{
	59	return m_key_eq( t1 == t2 );
	60	}
	61	IsEqual key_eq() const { return m_key_eq; }
	62	private:
	63	IsEqual m_key_eq;
	64	};
	65
	66	template <
	67	typename T,
	68	typename H,
	69	typename Hasher = hash< T, H >,
	70	bool IsEmpty = is_empty< Hasher >::value
	71	>
	72	struct hash_policy;
	73
	74
	75	template < typename T, typename H >
	76	struct hash_policy< T, H, hash< T, H >, true >
	77	{
	78	constexpr H get_hash( const T& t ) const
	79	{
	80	return hash< T, H >::get( t );
	81	}
	82	hash< T, H > hash_function() const { return hash< T, H >(); }
	83	};
	84
	85	template < typename T, typename H, typename Hasher >
	86	struct hash_policy< T, H, Hasher, true > : private Hasher
	87	{
	88	constexpr H get_hash( const T& t ) const
	89	{
	90	return ( *this )( t );
	91	}
	92	hash< T, H > hash_function() const { return ( *this ); }
	93	};
	94
	95	template < typename T, typename H, typename Hasher >
	96	struct hash_policy< T, H, Hasher, false >
	97	{
	98	constexpr H get_hash( const T& t ) const
	99	{
	100	return m_hasher( t );
	101	}
	102	hash< T, H > hash_function() const { return m_hasher; }
	103	private:
	104	Hasher m_hasher;
	105	};
	106
	107	// Due to MSVC not being able to handle multiple empty bases, if both
	108	// hash and compare are empty, we will still get a 4-size structure.
	109	// We will optimize here, to assure that if either is empty, we will still
	110	// get an empty class
	111	template <
	112	typename T,
	113	typename H,
	114	typename IsEqual = equal_to< T >,
	115	typename Hasher = hash< T, H >,
	116	bool IsEqualIsEmpty = is_empty< IsEqual >::value,
	117	bool HasherIsEmpty = is_empty< Hasher >::value
	118	>
	119	struct hash_compare_policy;
	120
	121	template <
	122	typename T,
	123	typename H,
	124	typename IsEqual,
	125	typename Hasher,
	126	bool HasherIsEmpty
	127	>
	128	struct hash_compare_policy< T, H, IsEqual, Hasher, false, HasherIsEmpty >
	129	: hash_policy< T, H, Hasher, HasherIsEmpty >
	130	{
	131	constexpr bool compare( const T& t1, const T& t2 ) const
	132	{
	133	return m_key_eq( t1 == t2 );
	134	}
	135	IsEqual key_eq() const { return m_key_eq; }
	136	private:
	137	IsEqual m_key_eq;
	138	};
	139
	140	template <
	141	typename T,
	142	typename H,
	143	typename IsEqual,
	144	typename Hasher
	145	>
	146	struct hash_compare_policy< T, H, IsEqual, Hasher, true, false >
	147	: compare_policy< T, IsEqual, true >
	148	{
	149	constexpr H get_hash( const T& t ) const
	150	{
	151	return m_hasher( t );
	152	}
	153	hash< T, H > hash_function() const { return m_hasher; }
	154	private:
	155	Hasher m_hasher;
	156	};
	157
	158	template <
	159	typename T,
	160	typename H,
	161	typename Hasher,
	162	typename IsEqual
	163	>
	164	struct hash_compare_policy< T, H, IsEqual, Hasher, true, true >
	165	: hash_policy< T, H, Hasher, true >
	166	{
	167	constexpr bool compare( const T& t1, const T& t2 ) const
	168	{
	169	static_assert( is_trivial< IsEqual >::value, "There is something really wrong with your equality functor." );
	170	return IsEqual()( t1, t2 );
	171	}
	172	IsEqual key_eq() const { return IsEqual(); }
	173	};
	174
	175	template <
	176	typename Key,
	177	typename Value,
	178	typename Hash,
	179	typename IsEqual = equal_to< Key >,
	180	typename Hasher = hash< Key, Hash >
	181	>
	182	struct hash_table_stl_map_policy : hash_compare_policy< Key, Hash, IsEqual, Hasher >
	183	{
	184	typedef hash_compare_policy< Key, Hash, IsEqual, Hasher > base_type;
	185
	186	typedef hash_table_standard_entry< Key, Value, Hash, false > entry_type;
	187	typedef typename entry_type::key_type key_type;
	188	typedef typename entry_type::mapped_type mapped_type;
	189	typedef typename entry_type::hash_type hash_type;
	190	typedef typename entry_type::value_type value_type;
	191	typedef Key query_type;
	192
	193	constexpr bool entry_compare( const entry_type* entry, hash_type, const query_type& key ) const
	194	{
	195	return base_type::compare( entry_type::get_key( entry ), key );
	196	}
	197
	198	constexpr bool entry_compare( const entry_type* entry, hash_type, const value_type& value ) const
	199	{
	200	return base_type::compare( entry_type::get_key( entry ), entry_type::get_key( value ) );
	201	}
	202
	203	template < typename... Args >
	204	static void entry_construct( entry_type* entry, hash_type, Args&&... params )
	205	{
	206	construct_object( entry_type::get_value( entry ), ::nv::forward<Args>( params )... );
	207	}
	208
	209	static void entry_destroy( entry_type* entry )
	210	{
	211	destroy_object( entry_type::get_value( entry ) );
	212	}
	213
	214	constexpr hash_type get_entry_hash( const entry_type* entry ) const
	215	{
	216	return base_type::get_hash( entry_type::get_key( entry ) );
	217	}
	218	constexpr hash_type get_value_hash( const value_type& value ) const
	219	{
	220	return base_type::get_hash( entry_type::get_key( value ) );
	221	}
	222	};
	223
	224	template <
[390]	225	typename Key,
	226	typename T,
	227	typename Hash = hash< Key >,
[408]	228	typename KeyEqual = equal_to< Key >,
[431]	229	typename HashEntryPolicy = hash_table_stl_map_policy< Key, T, typename Hash::result_type, KeyEqual, Hash >
[390]	230	>
	231	class unordered_map
[408]	232	: public hash_table<
	233	HashEntryPolicy,
	234	hash_table_no_extra_types_policy,
	235	hash_table_prime_rehash_policy,
	236	HashEntryPolicy
	237	>
[390]	238	{
	239	public:
[408]	240	typedef hash_table<
	241	HashEntryPolicy,
	242	hash_table_no_extra_types_policy,
	243	hash_table_prime_rehash_policy,
	244	HashEntryPolicy
	245	> base_type;
[401]	246	typedef typename base_type::value_type value_type;
	247	typedef typename base_type::pointer pointer;
	248	typedef typename base_type::const_pointer const_pointer;
	249	typedef typename base_type::reference reference;
	250	typedef typename base_type::const_reference const_reference;
	251	typedef typename base_type::iterator iterator;
	252	typedef typename base_type::const_iterator const_iterator;
[390]	253	typedef typename base_type::size_type size_type;
[401]	254	typedef typename base_type::difference_type difference_type;
[390]	255	typedef typename base_type::key_type key_type;
	256	typedef typename base_type::mapped_type mapped_type;
	257	typedef typename base_type::node_type node_type;
	258	typedef typename base_type::insert_return_type insert_return_type;
	259	typedef Hash hasher;
	260	typedef KeyEqual key_equal;
	261
[408]	262	using base_type::base_type;
[390]	263
	264	mapped_type& operator[]( const key_type& key )
	265	{
	266	return ( *base_type::insert_key( key ).first ).second;
	267	}
	268
[408]	269	mapped_type& at( const key_type& key )
	270	{
	271	iterator it = base_type::find( key );
	272	NV_ASSERT_ALWAYS( it != base_type::end(), "Key not found in map!" );
	273	return *it;
	274	}
	275
	276	const mapped_type& at( const key_type& key ) const
	277	{
	278	const_iterator it = base_type::find( key );
	279	NV_ASSERT_ALWAYS( it != base_type::cend(), "Key not found in map!" );
	280	return *it;
	281	}
	282
	283	size_type count( const key_type& key ) const
	284	{
	285	return base_type::find( key ) == base_type::cend() ? 0 : 1;
	286	}
	287
	288	pair<iterator, iterator> equal_range( const key_type& key )
	289	{
	290	iterator it = base_type::find( key );
	291	return pair<iterator, iterator>( it, it == base_type::end() ? it : ++it );
	292	}
	293
	294	pair<const_iterator, const_iterator> equal_range( const key_type& key ) const
	295	{
	296	const_iterator it = base_type::find( key );
	297	return pair<const_iterator, const_iterator>( it, it == base_type::cend() ? it : ++it );
	298	}
	299
[390]	300	using base_type::insert;
[408]	301
	302	template < typename M >
	303	insert_return_type insert_or_assign( const key_type& k, M&& obj )
	304	{
	305	insert_return_type result = base_type::try_insert( k, nv::forward<M>( obj ) );
	306	if ( !result.second ) result.first->second = obj;
	307	return result;
	308	}
	309
	310	template < typename M >
	311	insert_return_type insert_or_assign( key_type&& k, M&& obj )
	312	{
	313	insert_return_type result = base_type::try_insert( nv::forward<key_type>( k ), nv::forward<M>( obj ) );
	314	if ( !result.second ) result.first->second = obj;
	315	return result;
	316	}
	317
[390]	318	// STL compatibility only, hint unused
	319	iterator insert( const_iterator, const value_type& value )
	320	{
	321	return base_type::insert( value ).first;
	322	}
	323
	324	};
	325
[431]	326	// TODO: remove and make a proper hashed map
	327	template <
	328	typename Key,
	329	typename T,
	330	typename Hasher = hash< Key, typename Key::value_type >,
	331	typename KeyEqual = equal_to< Key >,
	332	typename HashEntryPolicy = hash_table_stl_map_policy< Key, T, typename Key::value_type, KeyEqual, Hasher >
	333	>
	334	class hashed_table
	335	: public hash_table<
	336	HashEntryPolicy,
	337	hash_table_no_extra_types_policy,
	338	hash_table_prime_rehash_policy,
	339	HashEntryPolicy
	340	>
	341	{
	342	public:
	343	typedef hash_table<
	344	HashEntryPolicy,
	345	hash_table_no_extra_types_policy,
	346	hash_table_prime_rehash_policy,
	347	HashEntryPolicy
	348	> base_type;
	349	typedef typename base_type::value_type value_type;
	350	typedef typename base_type::pointer pointer;
	351	typedef typename base_type::const_pointer const_pointer;
	352	typedef typename base_type::reference reference;
	353	typedef typename base_type::const_reference const_reference;
	354	typedef typename base_type::iterator iterator;
	355	typedef typename base_type::const_iterator const_iterator;
	356	typedef typename base_type::size_type size_type;
	357	typedef typename base_type::difference_type difference_type;
	358	typedef typename base_type::key_type key_type;
	359	typedef typename base_type::mapped_type mapped_type;
	360	typedef typename base_type::node_type node_type;
	361	typedef typename base_type::insert_return_type insert_return_type;
	362	typedef Hasher hasher;
	363	typedef KeyEqual key_equal;
	364
	365	using base_type::base_type;
	366
	367	mapped_type& operator[]( const key_type& key )
	368	{
	369	return ( *base_type::insert_key( key ).first ).second;
	370	}
	371	};
	372
	373
[390]	374	}
	375
	376	#endif // NV_STL_UNORDERED_MAP_HH
	377

Note: See TracBrowser for help on using the repository browser.

Download in other formats: