Changeset 408


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
Location:
trunk/nv/stl
Files:
2 added
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/nv/stl/container/hash_table.hh

    r404 r408  
    2727        template <
    2828                typename HashEntryPolicy,
    29                 typename RangeHashPolicy,
    30                 typename RehashPolicy
     29                typename RehashPolicy,
     30                typename BaseClass
    3131        >
    32         class hash_table_storage : protected HashEntryPolicy
     32        class hash_table_storage : protected BaseClass
    3333        {
    3434        public:
    35                 typedef HashEntryPolicy                base_type;
    36                 typedef typename base_type::value_type value_type;
    37                 typedef typename base_type::entry_type entry_type;
    38                 typedef typename base_type::hash_type  hash_type;
     35                typedef HashEntryPolicy                      base_type;
     36                typedef typename HashEntryPolicy::value_type value_type;
     37                typedef typename HashEntryPolicy::entry_type entry_type;
     38                typedef typename HashEntryPolicy::hash_type  hash_type;
    3939
    4040                struct node_type : entry_type
    … …  
    4848                {
    4949                public:
    50                         typedef typename base_type::value_type                         value_type;
     50                        typedef typename HashEntryPolicy::value_type                   value_type;
    5151                        typedef conditional_t<IsConst, const value_type*, value_type*> pointer;
    5252                        typedef conditional_t<IsConst, const value_type&, value_type&> reference;
    … …  
    196196                        }
    197197                        return *this;
     198                }
     199
     200                size_type bucket_size( size_type n ) const
     201                {
     202                        if ( n >= m_bucket_count ) return 0;
     203                        node_type* current = m_buckets[n];
     204                        size_type result = 0;
     205                        while ( current )
     206                        {
     207                                ++result;
     208                                current = current->next;
     209                        }
     210                        return result;
    198211                }
    199212
    … …  
    261274                inline void max_load_factor( float ml ) { m_max_load_factor = ml; }
    262275
    263                 using base_type::hash_function;
    264                 using base_type::key_eq;
    265 
    266276                ~hash_table_storage()
    267277                {
    … …  
    269279                        free_buckets( m_buckets, m_bucket_count );
    270280                }
    271         public:
     281        protected:
    272282                inline iterator unconst( const_iterator i )                       const { return iterator( i.m_node, i.m_bucket ); }
    273283                inline iterator unlocalize( size_type n, const_local_iterator i ) const { return iterator( i.m_node, m_buckets + n ); }
    … …  
    277287                {
    278288                        node_type* node = alloc_node();
    279                         base_type::entry_construct( node, hash_code, nv::forward<Args>( args )... );
     289                        HashEntryPolicy::entry_construct( node, hash_code, nv::forward<Args>( args )... );
    280290                        node->next = m_buckets[index];
    281291                        m_buckets[index] = node;
    … …  
    309319                }
    310320
    311 
    312         protected:
    313321                void do_rehash( size_type new_count )
    314322                {
    … …  
    320328                                while ( ( current = m_buckets[i] ) != nullptr )
    321329                                {
    322                                         size_type new_index = bucket_index( base_type::get_entry_hash( current ), new_count );
     330                                        size_type new_index = bucket_index( HashEntryPolicy::get_entry_hash( current ), new_count );
    323331                                        m_buckets[i] = current->next;
    324332                                        current->next = new_buckets[new_index];
    … …  
    359367                size_type bucket_index( hash_type hash_code, size_t b_count ) const
    360368                {
    361                         return RangeHashPolicy::template get<hash_type>( hash_code, b_count );
     369                        return RehashPolicy::template get_index<hash_type>( hash_code, b_count );
    362370                }
    363371                node_type** allocate_buckets( size_type new_count )
    … …  
    382390                void free_node( node_type* node )
    383391                {
    384                         node->~node_type();
     392                        HashEntryPolicy::entry_destroy( node );
    385393                        nvfree( node );
    386394                }
    … …  
    410418        template <
    411419                typename HashEntryPolicy,
    412                 typename Storage = hash_table_storage<
    413                         HashEntryPolicy,
    414                         hash_table_range_mod_policy,
    415                         hash_table_prime_rehash_policy
    416                 >
     420                template < typename > class HashQueryPoilcy = hash_table_no_extra_types_policy,
     421                typename RehashPolicy = hash_table_prime_rehash_policy,
     422                typename SuperClass = empty_type
    417423        >
    418         class hash_table : public Storage
     424        class hash_table : public hash_table_storage< HashEntryPolicy, RehashPolicy, SuperClass >
    419425        {
     426                typedef hash_table_storage< HashEntryPolicy, RehashPolicy, SuperClass > base_type;
    420427        public:
    421                 typedef Storage                            base_type;
    422                 typedef typename base_type::key_type       key_type;
    423                 typedef typename base_type::value_type     value_type;
    424                 typedef typename base_type::entry_type     entry_type;
    425                 typedef typename base_type::hash_type      hash_type;
    426                 typedef typename base_type::mapped_type    mapped_type;
    427                 typedef size_t                             size_type;
    428                 typedef ptrdiff_t                          difference_type;
    429                 typedef value_type&                        reference;
    430                 typedef const value_type&                  const_reference;
    431                 typedef value_type*                        pointer;
    432                 typedef const value_type*                  const_pointer;
     428                typedef typename base_type::value_type        value_type;
     429                typedef typename base_type::entry_type        entry_type;
     430                typedef typename base_type::hash_type         hash_type;
     431                typedef typename HashEntryPolicy::query_type  query_type;
     432                typedef typename HashEntryPolicy::key_type    key_type;
     433                typedef typename HashEntryPolicy::mapped_type mapped_type;
     434                typedef size_t                                size_type;
     435                typedef ptrdiff_t                             difference_type;
     436                typedef value_type&                           reference;
     437                typedef const value_type&                     const_reference;
     438                typedef value_type*                           pointer;
     439                typedef const value_type*                     const_pointer;
    433440
    434441                typedef typename base_type::local_iterator       local_iterator;
    … …  
    439446                typedef pair< iterator, bool >                   insert_return_type;
    440447
    441         public:
    442                 explicit hash_table() {}
     448        public: // constructors
     449                hash_table() {}
    443450                explicit hash_table( size_type size ) : base_type( size ) {}
    444 
    445                 iterator       find( const key_type& key )
    446                 {
    447                         const hash_type c = base_type::get_hash( key );
    448                         size_type       b = base_type::get_bucket_index( c );
    449                         return do_find_node( b, c, key );
    450                 }
    451                 const_iterator find( const key_type& key ) const
    452                 {
    453                         const hash_type c = base_type::get_hash( key );
    454                         size_type       b = base_type::get_bucket_index( c );
    455                         return do_find_node( b, c, key );
    456                 }
    457 
    458 // TODO: implement
    459 //              template< typename... Args >
    460 //              insert_return_type emplace( Args&&... args )
    461 //              {
    462 //
    463 //              }
    464 
    465                 inline insert_return_type insert( value_type&& value )
    466                 {
    467                         const hash_type h = base_type::get_value_hash( value );
     451                hash_table( const hash_table& other ) = delete;
     452                hash_table( hash_table&& other ) = default;
     453                template< typename InputIterator >
     454                hash_table( InputIterator first, InputIterator last ) : base_type()
     455                {
     456                        insert( first, last );
     457                }
     458
     459        public: // assignements
     460
     461                hash_table& operator=( const hash_table& other ) = delete;
     462                hash_table& operator=( hash_table&& other ) = default;
     463
     464        public: // iterators
     465
     466                using base_type::begin;
     467                using base_type::cbegin;
     468                using base_type::end;
     469                using base_type::cend;
     470
     471        public: // capacity
     472
     473                using base_type::empty;
     474                using base_type::size;
     475                using base_type::max_size;
     476
     477        public: // modifiers
     478
     479                using base_type::clear;
     480
     481                inline insert_return_type insert( const value_type& value )
     482                {
     483                        const hash_type h = HashEntryPolicy::get_value_hash( value );
    468484                        size_type       b = base_type::get_bucket_index( h );
    469485                        iterator        r = do_find_node( b, h, value );
    … …  
    472488                        {
    473489                                if ( base_type::rehash_check( 1 ) ) b = base_type::get_bucket_index( h );
    474                                 return insert_return_type( base_type::insert( b, h, nv::forward( value ) ), true );
     490                                return insert_return_type( base_type::insert( b, h, value ), true );
    475491                        }
    476492
    … …  
    478494                }
    479495
    480 
    481                 inline insert_return_type insert( const value_type& value )
    482                 {
    483                         const hash_type h = base_type::get_value_hash( value );
     496                inline insert_return_type insert( value_type&& value )
     497                {
     498                        const hash_type h = HashEntryPolicy::get_value_hash( value );
    484499                        size_type       b = base_type::get_bucket_index( h );
    485500                        iterator        r = do_find_node( b, h, value );
    … …  
    488503                        {
    489504                                if ( base_type::rehash_check( 1 ) ) b = base_type::get_bucket_index( h );
    490                                 return insert_return_type( base_type::insert( b, h, value ), true );
     505                                return insert_return_type( base_type::insert( b, h, nv::forward( value ) ), true );
    491506                        }
    492507
    … …  
    511526                }
    512527
    513                 size_type erase( const key_type& key )
     528                size_type erase( const query_type& key )
     529                {
     530                        const hash_type c = HashEntryPolicy::get_hash( key );
     531                        size_type       b = base_type::get_bucket_index( c );
     532                        return do_erase( b, c, key );
     533                }
     534
     535                template < typename T >
     536                enable_if_t< HashQueryPoilcy<T>::value, size_type >
     537                erase( const T& key )
     538                {
     539                        const hash_type c = HashEntryPolicy::get_hash( key );
     540                        size_type       b = base_type::get_bucket_index( c );
     541                        return do_erase( b, c, key );
     542                }
     543
     544        public: // lookup
     545
     546                iterator       find( const query_type& key )
     547                {
     548                        const hash_type c = HashEntryPolicy::get_hash( key );
     549                        size_type       b = base_type::get_bucket_index( c );
     550                        return do_find_node( b, c, key );
     551                }
     552               
     553                const_iterator find( const query_type& key ) const
     554                {
     555                        const hash_type c = HashEntryPolicy::get_hash( key );
     556                        size_type       b = base_type::get_bucket_index( c );
     557                        return do_find_node( b, c, key );
     558                }
     559
     560                template < typename T >
     561                enable_if_t< HashQueryPoilcy<T>::value, iterator >
     562                find( const T& key )
     563                {
     564                        const hash_type c = HashEntryPolicy::get_hash( key );
     565                        size_type       b = base_type::get_bucket_index( c );
     566                        return do_find_node( b, c, key );
     567                }
     568
     569                template < typename T >
     570                enable_if_t< HashQueryPoilcy<T>::value, const_iterator >
     571                find( const T& key ) const
     572                {
     573                        const hash_type c = HashEntryPolicy::get_hash( key );
     574                        size_type       b = base_type::get_bucket_index( c );
     575                        return do_find_node( b, c, key );
     576                }
     577
     578        protected:
     579
     580                template < typename KeyConvertible >
     581                inline insert_return_type insert_key( const KeyConvertible& key )
     582                {
     583                        const hash_type h = HashEntryPolicy::get_hash( key );
     584                        size_type       b = base_type::get_bucket_index( h );
     585                        iterator        r = do_find_node( b, h, key );
     586
     587                        if ( r == this->end() )
     588                        {
     589                                if ( base_type::rehash_check( 1 ) ) b = base_type::get_bucket_index( h );
     590                                return insert_return_type( base_type::insert( b, h, key, mapped_type() ), true );
     591                        }
     592
     593                        return insert_return_type( r, false );
     594                }
     595
     596                template < typename KeyConvertible, typename M >
     597                inline insert_return_type try_insert( const KeyConvertible& key, M&& obj )
     598                {
     599                        const hash_type h = HashEntryPolicy::get_hash( key );
     600                        size_type       b = base_type::get_bucket_index( h );
     601                        iterator        r = do_find_node( b, h, key );
     602
     603                        if ( r == this->end() )
     604                        {
     605                                if ( base_type::rehash_check( 1 ) ) b = base_type::get_bucket_index( h );
     606                                return insert_return_type( base_type::insert( b, h, key, ::nv::forward< M >( obj ) ), true );
     607                        }
     608                        return insert_return_type( r, false );
     609                }
     610
     611                template < typename KeyConvertible, typename M >
     612                inline insert_return_type try_insert( KeyConvertible&& key, M&& obj )
     613                {
     614                        const hash_type h = HashEntryPolicy::get_hash( key );
     615                        size_type       b = base_type::get_bucket_index( h );
     616                        iterator        r = do_find_node( b, h, key );
     617
     618                        if ( r == this->end() )
     619                        {
     620                                if ( base_type::rehash_check( 1 ) ) b = base_type::get_bucket_index( h );
     621                                return insert_return_type( base_type::insert( b, h, ::nv::move(key), ::nv::forward< M >( obj ) ), true );
     622                        }
     623                        return insert_return_type( r, false );
     624                }
     625
     626                template < typename ComparableType >
     627                inline iterator do_find_node( size_type index, hash_type h, const ComparableType& query ) const
     628                {
     629                        const_local_iterator first = this->cbegin( index );
     630                        const_local_iterator last  = this->cend( index );
     631                        while ( first != last )
     632                        {
     633                                if ( HashEntryPolicy::entry_compare( first.entry(), h, query ) )
     634                                        return base_type::unlocalize( index, first );
     635                                ++first;
     636                        }
     637                        return base_type::unconst( this->cend() );
     638                }
     639
     640                template < typename ComparableType >
     641                inline size_type do_erase( size_type index, hash_type h, const ComparableType& query )
    514642                {
    515643                        // TODO : optimize for non-multi sets! (one key possible)
    516                         const hash_type c = base_type::get_hash( key );
    517                         size_type       b = base_type::get_bucket_index( c );
    518                         const_local_iterator i = this->cbegin( b );
     644                        const_local_iterator first = this->cbegin( index );
     645                        const_local_iterator last  = this->cend( index );
    519646                        size_type result = 0;
    520                         while ( i != this->cend( b ) )
    521                         {
    522                                 if ( base_type::entry_compare( i.entry(), c, key ) )
     647                        while ( first != last )
     648                        {
     649                                if ( HashEntryPolicy::entry_compare( first.entry(), h, query ) )
    523650                                {
    524                                         i = base_type::erase_local( b, i );
     651                                        first = base_type::erase_local( index, first );
    525652                                        ++result;
    526653                                }
    527654                                else
    528                                         ++i;
     655                                        ++first;
    529656                        }
    530657                        return result;
    531                 }
    532 
    533         protected:
    534 
    535                 inline insert_return_type insert_key( const key_type& key )
    536                 {
    537                         const hash_type h = base_type::get_hash( key );
    538                         size_type       b = base_type::get_bucket_index( h );
    539                         iterator        r = do_find_node( b, h, key );
    540 
    541                         if ( r == this->end() )
    542                         {
    543                                 if ( base_type::rehash_check( 1 ) ) b = base_type::get_bucket_index( h );
    544                                 return insert_return_type( base_type::insert( b, h, key ), true );
    545                         }
    546 
    547                         return insert_return_type( r, false );
    548                 }
    549 
    550                 template < typename ComparableType >
    551                 iterator do_find_node( size_type index, hash_type h, const ComparableType& query ) const
    552                 {
    553                         const_local_iterator first = this->cbegin( index );
    554                         const_local_iterator last  = this->cend( index );
    555                         while ( first != last )
    556                         {
    557                                 if ( base_type::entry_compare( first.entry(), h, query ) )
    558                                         return base_type::unlocalize( index, first );
    559                                 ++first;
    560                         }
    561                         return base_type::unconst( this->cend() );
    562658                }
    563659

  • trunk/nv/stl/container/hash_table_policy.hh

    r405 r408  
    1515
    1616#include <nv/common.hh>
    17 #include <nv/stl/functional/hash.hh>
    18 #include <nv/stl/functional/comparisons.hh>
    19 #include <nv/stl/memory.hh>
    20 #include <nv/stl/utility/pair.hh>
    2117
    2218namespace nv
    2319{
     20        template < typename T >
     21        struct hash_table_no_extra_types_policy : false_type{};
    2422
     23        template < typename Key, typename Mapped, typename Hash, bool StoreHash >
     24        struct hash_table_standard_entry;
    2525
    26         template <
    27                 typename T,
    28                 typename IsEqual = equal_to<T>,
    29                 bool IsEmpty = is_empty< IsEqual >::value
    30         >
    31         struct compare_policy;
     26        template < typename Key, typename Mapped, typename Hash >
     27        struct hash_table_standard_entry< Key, Mapped, Hash, false >
     28        {
     29                typedef hash_table_standard_entry< Key, Mapped, Hash, false > this_type;
     30                typedef Key         key_type;
     31                typedef Mapped      mapped_type;
     32                typedef Hash        hash_type;
     33                typedef pair< const key_type, mapped_type > value_type;
    3234
     35                value_type value;
    3336
    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>(); }
     37                static constexpr const key_type& get_key( const value_type& value ) { return value.first; }
     38                static constexpr const key_type& get_key( const this_type* entry ) { return entry->value.first; }
     39                static constexpr value_type* get_value( this_type* entry ) { return &(entry->value); }
    4240        };
    4341
    44         template < typename T, typename IsEqual >
    45         struct compare_policy< T, IsEqual, true > : private IsEqual
     42        template < typename Key, typename Mapped, typename Hash >
     43        struct hash_table_standard_entry< Key, Mapped, Hash, true >
    4644        {
    47                 constexpr bool compare( const T& t1, const T& t2 ) const
     45                typedef hash_table_standard_entry< Key, Mapped, Hash, true > this_type;
     46                typedef Key         key_type;
     47                typedef Mapped      mapped_type;
     48                typedef Hash        hash_type;
     49                typedef pair< const key_type, mapped_type > value_type;
     50
     51                value_type value;
     52                hash_type  hash_code;
     53
     54                static constexpr const key_type& get_key( const value_type& value ) { return value.first; }
     55                static constexpr const key_type& get_key( const this_type* entry ) { return entry->value.first; }
     56                static constexpr value_type* get_value( this_type* entry ) { return &( entry->value ); }
     57                static constexpr hash_type get_hash( const this_type* entry )
    4858                {
    49                         return (*this)( t1 == t2 );
     59                        return entry->hash_code;
    5060                }
    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
     61                static inline void set_hash( this_type* entry, hash_type hash_code )
    5862                {
    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_entry_stl_map : hash_compare_policy< Key, Hash, IsEqual, Hasher >
    183         {
    184                 typedef hash_compare_policy< Key, Hash, IsEqual, Hasher > base_type;
    185                 typedef pair< const Key, Value > value_type;
    186                 typedef Key        key_type;
    187                 typedef Hash       hash_type;
    188                 typedef Value      mapped_type;
    189 
    190                 struct entry_type
    191                 {
    192                         value_type value;
    193                 };
    194 
    195                 constexpr bool entry_compare( const entry_type* entry, hash_type, const key_type& key ) const
    196                 {
    197                         return base_type::compare( entry->value.first, key );
    198                 }
    199 
    200                 constexpr bool entry_compare( const entry_type* entry, hash_type, const value_type& value ) const
    201                 {
    202                         return base_type::compare( entry->value.first, value.first );
    203                 }
    204 
    205                 template < typename... Args >
    206                 inline void entry_construct( entry_type* entry, hash_type, Args&&... params ) const
    207                 {
    208                         construct_object( &(entry->value), ::nv::forward<Args>( params )... );
    209                 }
    210 
    211                 inline void entry_construct( entry_type* entry, hash_type, Key key ) const
    212                 {
    213                         construct_object( &( entry->value ), value_type( ::nv::move( key ), mapped_type() ) );
    214                 }
    215 
    216                 constexpr hash_type get_entry_hash( const entry_type* entry ) const
    217                 {
    218                         return base_type::get_hash( entry->value.first );
    219                 }
    220                 constexpr hash_type get_value_hash( const value_type& value ) const
    221                 {
    222                         return base_type::get_hash( value.first );
     63                        entry->hash_code = hash_code;
    22364                }
    22465        };
    22566
    226         template <
    227                 typename Key,
    228                 typename Value,
    229                 typename Hash,
    230                 typename IsEqual = equal_to< Key >,
    231                 typename Hasher = hash< Key, Hash >
    232         >
    233         struct hash_table_entry_stl_map_with_hash : hash_compare_policy< Key, Hash, IsEqual, Hasher >
     67        template < typename EntryType, bool StoreHash >
     68        struct hash_table_standard_entry_hasher;
     69
     70        template < typename EntryType >
     71        struct hash_table_standard_entry_hasher< EntryType, false >
    23472        {
    235                 typedef hash_compare_policy< Key, Hash, IsEqual, Hasher > base_type;
    236                 typedef pair< const Key, Value > value_type;
    237                 typedef Key        key_type;
    238                 typedef Hash       hash_type;
    239                 typedef Value      mapped_type;
     73                typedef typename EntryType::hash_type hash_type;
     74                typedef typename EntryType::key_type  key_type;
    24075
    241                 struct entry_type
     76                template < typename T >
     77                static constexpr hash_type get_hash( const T& value )
    24278                {
    243                         value_type value;
    244                         hash_type  hash_code;
    245                 };
     79                        return hash< T, hash_type >::get( value );
     80                }
     81                static constexpr hash_type get_hash( const EntryType* entry )
     82                {
     83                        return hash< key_type, hash_type >::get( EntryType::get_key( entry ) );
     84                }
     85                static inline void set_hash( EntryType*, hash_type ) {}
     86        };
    24687
    247                 constexpr bool entry_compare( const entry_type* entry, hash_type h, const key_type& key ) const
     88        template < typename EntryType >
     89        struct hash_table_standard_entry_hasher< EntryType, true >
     90        {
     91                typedef typename EntryType::hash_type hash_type;
     92
     93                template < typename T >
     94                static constexpr hash_type get_hash( const T& value )
    24895                {
    249                         return entry->hash_code == h && base_type::compare( entry->value.first, key );
     96                        return hash< T, hash_type >::get( value );
    25097                }
    251                 constexpr bool entry_compare( const entry_type* entry, hash_type h, const value_type& value ) const
     98                static constexpr hash_type get_hash( const EntryType* entry )
    25299                {
    253                         return entry->hash_code == h &&  base_type::compare( entry->value.first, value.first );
     100                        return EntryType::get_hash( entry );
    254101                }
     102                static inline void set_hash( EntryType* entry, hash_type hash_code )
     103                {
     104                        EntryType::set_hash( entry, hash_code );
     105                }
     106        };
    255107
    256                 template < typename... Args >
    257                 inline void entry_construct( entry_type* entry, hash_type hash_code, Args&&... params ) const
     108        template < typename EntryType, typename HasherType, bool UseKey, bool UseHash >
     109        struct hash_table_standard_compare;
     110
     111        template < typename EntryType, typename HasherType >
     112        struct hash_table_standard_compare< EntryType, HasherType, true, true >
     113        {
     114                template < typename T >
     115                static constexpr bool apply( const EntryType* entry, typename EntryType::hash_type h, const T& key )
    258116                {
    259                         construct_object( &( entry->value ), ::nv::forward<Args>( params )... );
    260                         entry->hash_code = hash_code;
     117                        return HasherType::get_hash( entry ) == h && EntryType::get_key( entry ) == key;
    261118                }
     119        };
    262120
    263                 inline void entry_construct( entry_type* entry, hash_type hash_code, Key key ) const
     121        template < typename EntryType, typename HasherType >
     122        struct hash_table_standard_compare< EntryType, HasherType, true, false >
     123        {
     124                template < typename T >
     125                static constexpr bool apply( const EntryType* entry, typename EntryType::hash_type, const T& key )
    264126                {
    265                         construct_object( &( entry->value ), value_type( ::nv::move( key ), mapped_type() ) );
    266                         entry->hash_code = hash_code;
     127                        return EntryType::get_key( entry ) == key;
    267128                }
     129        };
    268130
    269                 constexpr hash_type get_entry_hash( const entry_type* entry ) const
     131        template < typename EntryType, typename HasherType >
     132        struct hash_table_standard_compare< EntryType, HasherType, false, true >
     133        {
     134                template < typename T >
     135                static constexpr bool apply( const EntryType* entry, typename EntryType::hash_type h, const T& )
    270136                {
    271                         return entry->hash_code;
     137                        return HasherType::get_hash( entry ) == h;
    272138                }
    273                 constexpr hash_type get_value_hash( const value_type& value ) const
    274                 {
    275                         return base_type::get_hash( value.first );
    276                 }
    277 };
    278        
    279         struct hash_table_range_mod_policy
    280         {
    281                 template< typename H >
    282                 static size_t get( H h, size_t n ) { return h % n; }
    283139        };
     140
    284141
    285142        uint32 get_prime_larger_or_equal_to( uint32 value );
    … …  
    287144        struct hash_table_prime_rehash_policy
    288145        {
     146                template< typename H >
     147                static size_t get_index( H h, size_t n ) { return h % n; }
     148
    289149                static uint32 get_bucket_count( uint32 requested_count )
    290150                {

  • trunk/nv/stl/string.hh

    r407 r408  
    3434{
    3535
     36        template < typename Storage > class string_base;
     37        class string_view;
    3638
    3739        //      short_string< size_t >
    … …  
    6870                };
    6971
    70 
    71         }
    72 
    73         template < typename Storage > class string_base;
    74         class string_view;
     72                template < typename T, typename Enable = void >
     73                struct is_string_base_impl : false_type {};
     74                template < typename T >
     75                struct is_string_base_impl < T,
     76                        typename enable_if<
     77                        is_base_of< string_base< typename T::storage_type >, T >::value,
     78                        void >::type > : true_type{};
     79        }
    7580
    7681        // Stronger version
    … …  
    7883        //      struct is_string_base : is_template_base_of< T, string_base > {};
    7984
    80         template < typename T, typename Enable = void >
    81         struct is_string_base : false_type {};
    8285        template < typename T >
    83         struct is_string_base < T,
    84                 typename enable_if<
    85                 is_base_of< string_base< typename T::storage_type >, T >::value,
    86                 void >::type > : true_type{};
     86        struct is_string_base : detail::is_string_base_impl< T > {};
    8787
    8888        template < typename T >
    … …  
    147147                inline H get_hash() const
    148148                {
    149                         return hash_string< size_type >( this->data(), this->size() );
     149                        return hash_string< H >( this->data(), this->size() );
    150150                }
    151151
    … …  
    436436                        initialize( str, nvstrlen( str ) );
    437437                }
    438 
     438                inline const_string( const string_view& rhs )
     439                {
     440                        initialize( rhs.data(), rhs.size() );
     441                }
     442                template< size_t N >
     443                inline const_string( char( &s )[N] )
     444                {
     445                        initialize( s, N-1 );
     446                }
     447                template< size_t N >
     448                inline const_string( const char( &s )[N] )
     449                {
     450                        initialize( s, N - 1 );
     451                }
    439452                ~const_string()
    440453                {
    … …  
    509522                template< size_t N >
    510523                constexpr hashed_literal_string( char( &s )[N] )
    511                         : this_type( s, N - 1 ), m_hash( detail::fnv_hash<H>::hash( s, len-1 ) ) {}
     524                        : this_type( s, N - 1 ), m_hash( detail::fnv_hash<H>::hash( s, N - 1 ) ) {}
    512525                template< size_t N >
    513526                constexpr hashed_literal_string( const char( &s )[N] )
    514                         : this_type( s, N - 1 ), m_hash( detail::fnv_hash<H>::hash( s, len - 1 ) ) {}
     527                        : this_type( s, N - 1 ), m_hash( detail::fnv_hash<H>::hash( s, N - 1 ) ) {}
    515528
    516529                template < typename H2 >

  • 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 )

  • trunk/nv/stl/utility/pair.hh

    r404 r408  
    3030                        : first( f ), second( s ) {}
    3131
    32                 constexpr pair( first_type&& f, second_type&& s )
    33                         : first( ::nv::forward<first_type>( f ) ), second( ::nv::forward<second_type>( s ) ) {}
     32                template < typename U1, typename U2 >
     33                constexpr pair( U1&& f, U2&& s )
     34                        : first( ::nv::forward<U1>( f ) ), second( ::nv::forward<U2>( s ) ) {}
     35                template < typename U1, typename U2 >
     36                constexpr pair( const U1& f, U2&& s )
     37                        : first( f ), second( ::nv::forward<U2>( s ) ) {}
     38                template < typename U1, typename U2 >
     39                constexpr pair( U1&& f, const U2& s )
     40                        : first( ::nv::forward<U1>( f ) ), second( s ) {}
     41
    3442
    3543                pair( const pair& ) = default;
Note: See TracChangeset for help on using the changeset viewer.