Ignore:
Timestamp:
06/21/15 02:44:30 (10 years ago)
Author:
epyon
Message:
  • stl/hash_table and stl/hash_table_policy rewritten
  • stl/hash_map and stl/string_map added
  • stl/pair constructors enhanced
  • stl/const_string fixed
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/nv/stl/unordered_map.hh

    r403 r408  
    1717#include <nv/stl/container/hash_table.hh>
    1818#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>
    1922
    2023namespace nv
    … …  
    2225
    2326        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 <
    24225                typename Key,
    25226                typename T,
    26227                typename Hash = hash< Key >,
    27                 typename KeyEqual = equal_to< Key >
    28 //              typename Hash = hash<Key>(),
    29 //              typename Predicate = equal_to<Key>,
     228                typename KeyEqual = equal_to< Key >,
     229                typename HashEntryPolicy = hash_table_stl_map_policy< Key, T, size_t, KeyEqual, Hash >
    30230        >
    31231        class unordered_map
    32                 : public hash_table< hash_table_entry_stl_map< Key, T, size_t, KeyEqual, Hash > >
     232                : public hash_table<
     233                        HashEntryPolicy,
     234                        hash_table_no_extra_types_policy,
     235                        hash_table_prime_rehash_policy,
     236                        HashEntryPolicy
     237                >
    33238        {
    34239        public:
    35                 typedef hash_table< hash_table_entry_stl_map< Key, T, size_t, KeyEqual, Hash > > base_type;
    36                 typedef unordered_map< Key, T, Hash, KeyEqual >                                  this_type;
     240                typedef hash_table<
     241                        HashEntryPolicy,
     242                        hash_table_no_extra_types_policy,
     243                        hash_table_prime_rehash_policy,
     244                        HashEntryPolicy
     245                > base_type;
    37246                typedef typename base_type::value_type                                           value_type;
    38247                typedef typename base_type::pointer                                              pointer;
    … …  
    51260                typedef KeyEqual                                                                 key_equal;
    52261
    53                 unordered_map() : base_type() { }
    54                 explicit unordered_map( size_type bucket_count ) : base_type( bucket_count ) { }
     262                using base_type::base_type;
    55263
    56264                mapped_type& operator[]( const key_type& key )
    … …  
    59267                }
    60268
     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
    61300                using base_type::insert;
    62        
     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
    63318                // STL compatibility only, hint unused
    64319                iterator insert( const_iterator, const value_type& value )
Note: See TracChangeset for help on using the changeset viewer.