Changeset 495

Timestamp:

05/24/16 19:28:23 (9 years ago)

Author:

epyon

Message:

• packed_index_table and unpacked_index_array added

File:

• trunk/nv/stl/handle.hh (modified) (5 diffs)

trunk/nv/stl/handle.hh

@@ -143 +143 @@
                 index_type m_last_free;
                 vector< index_entry > m_entries;
+        };
+
+        template < typename HANDLE = handle<>, typename TINDEX = sint32 >
+        class packed_index_table
+        {
+        public:
+                typedef HANDLE              handle;
+                typedef TINDEX              index_type;
+                packed_index_table() {}
+                packed_index_table( uint32 reserve )
+                {
+                        m_indexes.reserve( reserve );
+                }
+
+                index_type insert( handle h )
+                {
+                        NV_ASSERT( !exists( h ), "Reinserting handle!" );
+                        resize_indexes_to( index_type( h.index() ) );
+                        index_type lindex = m_handles.size();
+                        m_indexes[h.index()] = index_type( lindex );
+                        m_handles.push_back( h );
+                        return lindex;
+                }
+
+                bool exists( handle h )
+                {
+                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return false;
+                        return m_indexes[h.index()] >= 0;
+                }
+
+                index_type get( handle h )
+                {
+                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return -1;
+                        return m_indexes[h.index()];
+                }
+
+                index_type get( handle h ) const
+                {
+                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return -1;
+                        return m_indexes[h.index()];
+                }
+
+                index_type remove_swap( handle h )
+                {
+                        if ( h.is_nil() || h.index() >= m_indexes.size() || m_indexes[h.index()] == -1 )
+                                return -1;
+                        handle     swap_handle = m_handles.back();
+                        index_type dead_eindex = m_indexes[h.index()];
+                        if ( dead_eindex != static_cast<index_type>( m_handles.size() - 1 ) )
+                        {
+//                              m_data[unsigned( dead_eindex )] = move( m_data.back() );
+                                m_handles[unsigned( dead_eindex )] = swap_handle;
+                                m_indexes[swap_handle.index()] = dead_eindex;
+                        }
+//                      m_data.pop_back();
+                        m_handles.pop_back();
+                        m_indexes[h.index()] = -1;
+                        return dead_eindex;
+                }
+
+                void clear()
+                {
+                        m_handles.clear();
+                        m_indexes.clear();
+                }
+
+                handle get_handle( index_type i ) const { return m_handles[unsigned( i )]; }
+
+                size_t size() const { return m_handles.size(); }
+
+        private:
+                void resize_indexes_to( index_type i )
+                {
+                        index_type size = index_type( m_indexes.size() );
+                        if ( i >= size )
+                        {
+                                if ( size == 0 ) size = 1;
+                                while ( i >= size ) size = size * 2;
+                                m_indexes.resize( static_cast<size_t>( size ), -1 );
+                        }
+                }
+
+                vector< handle >     m_handles;
+                vector< index_type > m_indexes;
         };
 
@@ -167 +251 @@
                 T* insert( handle h )
                 {
-                        NV_ASSERT( !exists( h ), "Reinserting handle!" );
-                        resize_indexes_to( index_type( h.index() ) );
-                        m_indexes[ h.index() ] = index_type( m_data.size() );
-                        m_handles.push_back( h );
+                        /*index_type i = */m_index.insert( h );
+                        //NV_ASSERT( i == m_data.size(), "Fail!" );
                         m_data.emplace_back();
-                        return &(m_data.back());
+                        return &( m_data.back() );
                 }
 
                 bool exists( handle h )
                 {
-                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return false;
-                        return m_indexes[ h.index() ] >= 0;             
+                        return m_index.exists( h );
                 }
 
                 T* get( handle h )
                 {
-                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return nullptr;
-                        index_type i = m_indexes[ h.index() ];
-                        return i >= 0 ? &(m_data[ unsigned( i ) ]) : nullptr;
+                        index_type i = m_index.get(h);
+                        return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr;
                 }
 
                 const T* get( handle h ) const
                 {
-                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return nullptr;
-                        index_type i = m_indexes[h.index()];
-                        return i >= 0 ? &( m_data[ unsigned( i )] ) : nullptr;
+                        index_type i = m_index.get( h );
+                        return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr;
                 }
 
                 void remove( handle h )
                 {
-                        if ( h.is_nil() || h.index() >= m_indexes.size() || m_indexes[h.index()] == -1 ) 
-                                return;
-                        handle     swap_handle    = m_handles.back();
-                        index_type dead_eindex    = m_indexes[ h.index() ];
-                        if ( dead_eindex != static_cast<index_type>( m_data.size()-1 ) )
-                        {
-                                m_data[ unsigned( dead_eindex ) ]   = move( m_data.back() );
-                                m_handles[unsigned( dead_eindex ) ] = swap_handle;
-                                m_indexes[ swap_handle.index() ]    = dead_eindex;
+                        index_type dead_eindex = m_index.remove_swap( h );
+                        if ( dead_eindex == -1 ) return;
+                        if ( dead_eindex != static_cast<index_type>( m_data.size() - 1 ) )
+                        {
+                                m_data[unsigned( dead_eindex )] = move( m_data.back() );
                         }
                         m_data.pop_back();
-                        m_handles.pop_back();
-                        m_indexes[ h.index() ] = -1;
                 }
 
                 void clear()
                 {
+                        m_index.clear();
                         m_data.clear();
-                        m_handles.clear();
-                        m_indexes.clear();
-                }
-
-                handle get_handle( index_type i ) const { return m_handles[unsigned(i)]; }
+                }
+
+                handle get_handle( index_type i ) const { return m_index.get_handle( i ); }
 
                 const value_type& operator[] ( index_type i ) const { return m_data[i]; }
@@ -225 +297 @@
                 size_t size() const { return m_data.size(); }
 
-                iterator        begin()        { return m_data.begin(); }
+                iterator        begin() { return m_data.begin(); }
                 const_iterator  begin()  const { return m_data.cbegin(); }
                 const_iterator  cbegin() const { return m_data.cbegin(); }
 
-                iterator        end()        { return m_data.end(); }
+                iterator        end() { return m_data.end(); }
                 const_iterator  end()  const { return m_data.cend(); }
                 const_iterator  cend() const { return m_data.cend(); }
 
         private:
-                void resize_indexes_to( index_type i )
+                vector< T >                          m_data;
+                packed_index_table< HANDLE, TINDEX > m_index;
+        };
+        
+        template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
+        class unpacked_indexed_array
+        {
+        public:
+                typedef HANDLE              handle;
+                typedef TINDEX              index_type;
+                typedef vector< T >         storage;
+                typedef T                   value_type;
+                typedef typename storage::iterator        iterator;
+                typedef typename storage::const_iterator  const_iterator;
+                typedef typename storage::reference       reference;
+                typedef typename storage::const_reference const_reference;
+
+                unpacked_indexed_array() {}
+                unpacked_indexed_array( uint32 reserve )
+                {
+                        m_data.reserve( reserve );
+                        m_indexes.reserve( reserve );
+                }
+
+                T* insert( handle h )
+                {
+                        NV_ASSERT( !exists( h ), "Reinserting handle!" );
+                        resize_to( index_type( h.index() ) );
+                        m_handles[ h.index() ] = h;
+                        return &( m_data[h.index()] );
+                }
+
+                bool exists( handle h )
+                {
+                        if ( h.is_nil() || h.index() >= m_data.size() ) return false;
+                        return m_handles[h.index()].is_valid();
+                }
+
+                T* get( handle h )
+                {
+                        if ( h.is_nil() || h.index() >= m_data.size() ) return nullptr;
+                        index_type i = h.index();
+                        return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr;
+                }
+
+                const T* get( handle h ) const
+                {
+                        if ( h.is_nil() || h.index() >= m_data.size() ) return nullptr;
+                        index_type i = h.index();
+                        return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr;
+                }
+
+                void remove( handle h )
+                {
+                        m_handles[ h.index() ] = handle();
+                }
+
+                void clear()
+                {
+                        m_data.clear();
+                        m_handles.clear();
+                }
+
+                handle get_handle( index_type i ) const { return m_handles[unsigned( i )]; }
+
+                const value_type& operator[] ( index_type i ) const { return m_data[i]; }
+                value_type& operator[] ( index_type i ) { return m_data[i]; }
+                size_t size() const { return m_data.size(); }
+
+                iterator        begin() { return m_data.begin(); }
+                const_iterator  begin()  const { return m_data.cbegin(); }
+                const_iterator  cbegin() const { return m_data.cbegin(); }
+
+                iterator        end() { return m_data.end(); }
+                const_iterator  end()  const { return m_data.cend(); }
+                const_iterator  cend() const { return m_data.cend(); }
+
+        private:
+                void resize_to( index_type i )
                 {
                         index_type size = index_type( m_indexes.size() );
@@ -241 +391 @@
                                 if ( size == 0 ) size = 1;
                                 while ( i >= size ) size = size * 2;
-                                m_indexes.resize( static_cast<size_t>( size ), -1 );
+                                m_data.resize( static_cast<size_t>( size ) );
+                                m_handles.resize( static_cast<size_t>( size ) );
                         }
                 }
@@ -247 +398 @@
                 vector< T >          m_data;
                 vector< handle >     m_handles;
-                vector< index_type > m_indexes;
         };