Changeset 495 for trunk


Ignore:
Timestamp:
05/24/16 19:28:23 (9 years ago)
Author:
epyon
Message:
  • packed_index_table and unpacked_index_array added
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/nv/stl/handle.hh

    r479 r495  
    143143                index_type m_last_free;
    144144                vector< index_entry > m_entries;
     145        };
     146
     147        template < typename HANDLE = handle<>, typename TINDEX = sint32 >
     148        class packed_index_table
     149        {
     150        public:
     151                typedef HANDLE              handle;
     152                typedef TINDEX              index_type;
     153                packed_index_table() {}
     154                packed_index_table( uint32 reserve )
     155                {
     156                        m_indexes.reserve( reserve );
     157                }
     158
     159                index_type insert( handle h )
     160                {
     161                        NV_ASSERT( !exists( h ), "Reinserting handle!" );
     162                        resize_indexes_to( index_type( h.index() ) );
     163                        index_type lindex = m_handles.size();
     164                        m_indexes[h.index()] = index_type( lindex );
     165                        m_handles.push_back( h );
     166                        return lindex;
     167                }
     168
     169                bool exists( handle h )
     170                {
     171                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return false;
     172                        return m_indexes[h.index()] >= 0;
     173                }
     174
     175                index_type get( handle h )
     176                {
     177                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return -1;
     178                        return m_indexes[h.index()];
     179                }
     180
     181                index_type get( handle h ) const
     182                {
     183                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return -1;
     184                        return m_indexes[h.index()];
     185                }
     186
     187                index_type remove_swap( handle h )
     188                {
     189                        if ( h.is_nil() || h.index() >= m_indexes.size() || m_indexes[h.index()] == -1 )
     190                                return -1;
     191                        handle     swap_handle = m_handles.back();
     192                        index_type dead_eindex = m_indexes[h.index()];
     193                        if ( dead_eindex != static_cast<index_type>( m_handles.size() - 1 ) )
     194                        {
     195//                              m_data[unsigned( dead_eindex )] = move( m_data.back() );
     196                                m_handles[unsigned( dead_eindex )] = swap_handle;
     197                                m_indexes[swap_handle.index()] = dead_eindex;
     198                        }
     199//                      m_data.pop_back();
     200                        m_handles.pop_back();
     201                        m_indexes[h.index()] = -1;
     202                        return dead_eindex;
     203                }
     204
     205                void clear()
     206                {
     207                        m_handles.clear();
     208                        m_indexes.clear();
     209                }
     210
     211                handle get_handle( index_type i ) const { return m_handles[unsigned( i )]; }
     212
     213                size_t size() const { return m_handles.size(); }
     214
     215        private:
     216                void resize_indexes_to( index_type i )
     217                {
     218                        index_type size = index_type( m_indexes.size() );
     219                        if ( i >= size )
     220                        {
     221                                if ( size == 0 ) size = 1;
     222                                while ( i >= size ) size = size * 2;
     223                                m_indexes.resize( static_cast<size_t>( size ), -1 );
     224                        }
     225                }
     226
     227                vector< handle >     m_handles;
     228                vector< index_type > m_indexes;
    145229        };
    146230
    … …  
    167251                T* insert( handle h )
    168252                {
    169                         NV_ASSERT( !exists( h ), "Reinserting handle!" );
    170                         resize_indexes_to( index_type( h.index() ) );
    171                         m_indexes[ h.index() ] = index_type( m_data.size() );
    172                         m_handles.push_back( h );
     253                        /*index_type i = */m_index.insert( h );
     254                        //NV_ASSERT( i == m_data.size(), "Fail!" );
    173255                        m_data.emplace_back();
    174                         return &(m_data.back());
     256                        return &( m_data.back() );
    175257                }
    176258
    177259                bool exists( handle h )
    178260                {
    179                         if ( h.is_nil() || h.index() >= m_indexes.size() ) return false;
    180                         return m_indexes[ h.index() ] >= 0;             
     261                        return m_index.exists( h );
    181262                }
    182263
    183264                T* get( handle h )
    184265                {
    185                         if ( h.is_nil() || h.index() >= m_indexes.size() ) return nullptr;
    186                         index_type i = m_indexes[ h.index() ];
    187                         return i >= 0 ? &(m_data[ unsigned( i ) ]) : nullptr;
     266                        index_type i = m_index.get(h);
     267                        return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr;
    188268                }
    189269
    190270                const T* get( handle h ) const
    191271                {
    192                         if ( h.is_nil() || h.index() >= m_indexes.size() ) return nullptr;
    193                         index_type i = m_indexes[h.index()];
    194                         return i >= 0 ? &( m_data[ unsigned( i )] ) : nullptr;
     272                        index_type i = m_index.get( h );
     273                        return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr;
    195274                }
    196275
    197276                void remove( handle h )
    198277                {
    199                         if ( h.is_nil() || h.index() >= m_indexes.size() || m_indexes[h.index()] == -1 )
    200                                 return;
    201                         handle     swap_handle    = m_handles.back();
    202                         index_type dead_eindex    = m_indexes[ h.index() ];
    203                         if ( dead_eindex != static_cast<index_type>( m_data.size()-1 ) )
    204                         {
    205                                 m_data[ unsigned( dead_eindex ) ]   = move( m_data.back() );
    206                                 m_handles[unsigned( dead_eindex ) ] = swap_handle;
    207                                 m_indexes[ swap_handle.index() ]    = dead_eindex;
     278                        index_type dead_eindex = m_index.remove_swap( h );
     279                        if ( dead_eindex == -1 ) return;
     280                        if ( dead_eindex != static_cast<index_type>( m_data.size() - 1 ) )
     281                        {
     282                                m_data[unsigned( dead_eindex )] = move( m_data.back() );
    208283                        }
    209284                        m_data.pop_back();
    210                         m_handles.pop_back();
    211                         m_indexes[ h.index() ] = -1;
    212285                }
    213286
    214287                void clear()
    215288                {
     289                        m_index.clear();
    216290                        m_data.clear();
    217                         m_handles.clear();
    218                         m_indexes.clear();
    219                 }
    220 
    221                 handle get_handle( index_type i ) const { return m_handles[unsigned(i)]; }
     291                }
     292
     293                handle get_handle( index_type i ) const { return m_index.get_handle( i ); }
    222294
    223295                const value_type& operator[] ( index_type i ) const { return m_data[i]; }
    … …  
    225297                size_t size() const { return m_data.size(); }
    226298
    227                 iterator        begin()        { return m_data.begin(); }
     299                iterator        begin() { return m_data.begin(); }
    228300                const_iterator  begin()  const { return m_data.cbegin(); }
    229301                const_iterator  cbegin() const { return m_data.cbegin(); }
    230302
    231                 iterator        end()        { return m_data.end(); }
     303                iterator        end() { return m_data.end(); }
    232304                const_iterator  end()  const { return m_data.cend(); }
    233305                const_iterator  cend() const { return m_data.cend(); }
    234306
    235307        private:
    236                 void resize_indexes_to( index_type i )
     308                vector< T >                          m_data;
     309                packed_index_table< HANDLE, TINDEX > m_index;
     310        };
     311       
     312        template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
     313        class unpacked_indexed_array
     314        {
     315        public:
     316                typedef HANDLE              handle;
     317                typedef TINDEX              index_type;
     318                typedef vector< T >         storage;
     319                typedef T                   value_type;
     320                typedef typename storage::iterator        iterator;
     321                typedef typename storage::const_iterator  const_iterator;
     322                typedef typename storage::reference       reference;
     323                typedef typename storage::const_reference const_reference;
     324
     325                unpacked_indexed_array() {}
     326                unpacked_indexed_array( uint32 reserve )
     327                {
     328                        m_data.reserve( reserve );
     329                        m_indexes.reserve( reserve );
     330                }
     331
     332                T* insert( handle h )
     333                {
     334                        NV_ASSERT( !exists( h ), "Reinserting handle!" );
     335                        resize_to( index_type( h.index() ) );
     336                        m_handles[ h.index() ] = h;
     337                        return &( m_data[h.index()] );
     338                }
     339
     340                bool exists( handle h )
     341                {
     342                        if ( h.is_nil() || h.index() >= m_data.size() ) return false;
     343                        return m_handles[h.index()].is_valid();
     344                }
     345
     346                T* get( handle h )
     347                {
     348                        if ( h.is_nil() || h.index() >= m_data.size() ) return nullptr;
     349                        index_type i = h.index();
     350                        return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr;
     351                }
     352
     353                const T* get( handle h ) const
     354                {
     355                        if ( h.is_nil() || h.index() >= m_data.size() ) return nullptr;
     356                        index_type i = h.index();
     357                        return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr;
     358                }
     359
     360                void remove( handle h )
     361                {
     362                        m_handles[ h.index() ] = handle();
     363                }
     364
     365                void clear()
     366                {
     367                        m_data.clear();
     368                        m_handles.clear();
     369                }
     370
     371                handle get_handle( index_type i ) const { return m_handles[unsigned( i )]; }
     372
     373                const value_type& operator[] ( index_type i ) const { return m_data[i]; }
     374                value_type& operator[] ( index_type i ) { return m_data[i]; }
     375                size_t size() const { return m_data.size(); }
     376
     377                iterator        begin() { return m_data.begin(); }
     378                const_iterator  begin()  const { return m_data.cbegin(); }
     379                const_iterator  cbegin() const { return m_data.cbegin(); }
     380
     381                iterator        end() { return m_data.end(); }
     382                const_iterator  end()  const { return m_data.cend(); }
     383                const_iterator  cend() const { return m_data.cend(); }
     384
     385        private:
     386                void resize_to( index_type i )
    237387                {
    238388                        index_type size = index_type( m_indexes.size() );
    … …  
    241391                                if ( size == 0 ) size = 1;
    242392                                while ( i >= size ) size = size * 2;
    243                                 m_indexes.resize( static_cast<size_t>( size ), -1 );
     393                                m_data.resize( static_cast<size_t>( size ) );
     394                                m_handles.resize( static_cast<size_t>( size ) );
    244395                        }
    245396                }
    … …  
    247398                vector< T >          m_data;
    248399                vector< handle >     m_handles;
    249                 vector< index_type > m_indexes;
    250400        };
    251401
Note: See TracChangeset for help on using the changeset viewer.