source: trunk/nv/stl/unordered_map.hh

Last change on this file was 432, checked in by epyon, 10 years ago
  • dedicated hash_store used instead of unordered_map
File size: 9.6 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
23namespace 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_base<
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_base<
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}
327
328#endif // NV_STL_UNORDERED_MAP_HH
329
Note: See TracBrowser for help on using the repository browser.