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

Line
1	// Copyright (C) 2015 ChaosForge Ltd
2	// http://chaosforge.org/
3	//
4	// This file is part of Nova libraries.
5	// For conditions of distribution and use, see copying.txt file in root folder.
6
7	/**
8	* @file unordered_map.hh
9	* @author Kornel Kisielewicz epyon@chaosforge.org
10	* @brief unordered_map
11	*/
12
13	#ifndef NV_STL_UNORDERED_MAP_HH
14	#define NV_STL_UNORDERED_MAP_HH
15
16	#include <nv/common.hh>
17	#include <nv/stl/container/hash_table.hh>
18	#include <nv/stl/utility/pair.hh>
19	#include <nv/stl/functional/hash.hh>
20	#include <nv/stl/functional/comparisons.hh>
21	#include <nv/stl/memory.hh>
22
23	namespace nv
24	{
25
26	template <
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 <
225	typename Key,
226	typename T,
227	typename Hash = hash< Key >,
228	typename KeyEqual = equal_to< Key >,
229	typename HashEntryPolicy = hash_table_stl_map_policy< Key, T, typename Hash::result_type, KeyEqual, Hash >
230	>
231	class unordered_map
232	: public hash_table<
233	HashEntryPolicy,
234	hash_table_no_extra_types_policy,
235	hash_table_prime_rehash_policy,
236	HashEntryPolicy
237	>
238	{
239	public:
240	typedef hash_table<
241	HashEntryPolicy,
242	hash_table_no_extra_types_policy,
243	hash_table_prime_rehash_policy,
244	HashEntryPolicy
245	> base_type;
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;
253	typedef typename base_type::size_type size_type;
254	typedef typename base_type::difference_type difference_type;
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
262	using base_type::base_type;
263
264	mapped_type& operator[]( const key_type& key )
265	{
266	return ( *base_type::insert_key( key ).first ).second;
267	}
268
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
300	using base_type::insert;
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
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
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
374	}
375
376	#endif // NV_STL_UNORDERED_MAP_HH
377

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

Download in other formats: