source: trunk/nv/core/handle.hh @ 347

// Copyright (C) 2014 ChaosForge Ltd
// http://chaosforge.org/
//
// This file is part of NV Libraries.
// For conditions of distribution and use, see copyright notice in nv.hh

/**
 * @file handle.hh
 * @author Kornel Kisielewicz
 */

#ifndef NV_CORE_HANDLE_HH
#define NV_CORE_HANDLE_HH

#include <nv/core/common.hh>
#include <nv/core/array.hh>

namespace nv
{

        template < 
                typename T = uint32, 
                unsigned IBITS = 16,
                unsigned CBITS = 16,
                typename TAG = void 
        >
        class handle
        {
        public:
                typedef T value_type;
                typedef TAG tag_type;
                static const int INDEX_BITS   = IBITS;
                static const int COUNTER_BITS = IBITS;
                static const T MAX_INDEX   = (1 << IBITS) - 1;
                static const T MAX_COUNTER = (1 << CBITS) - 1;

                handle() : m_index(0), m_counter(0) {}

                inline bool operator==(const handle& rhs) const {return m_index == rhs.m_index && m_counter == rhs.m_counter; }
                inline bool operator!=(const handle& rhs) const {return !(*this == rhs);}

                bool is_nil() const { return m_index == 0 && m_counter == 0; }
                bool is_valid() const { return !is_nil(); }
                T index() const { return m_index; }
                size_t hash() const { return std::hash<T>()( T( m_counter << IBITS | m_index ) ); }
        protected:
                T m_index   : IBITS;
                T m_counter : CBITS;

                handle( T a_index, T a_counter ) : m_index( a_index ), m_counter( a_counter ) {}
                template < typename H >
                friend class handle_operator;
        };

        template < typename HANDLE >
        class handle_operator
        {
        public:
                typedef typename HANDLE::value_type value_type;

                static HANDLE create( value_type index, value_type counter )
                {
                        return HANDLE( index, counter );
                }
                static value_type get_counter( const HANDLE& h ) { return h.m_counter; }
                static value_type get_index( const HANDLE& h ) { return h.m_index; }
        };

        template < typename HANDLE >
        class handle_manager
        {
                static const sint32 NONE = -1;
                static const sint32 USED = -2;
        public:

                typedef HANDLE handle;
                typedef typename HANDLE::value_type value_type;

                handle_manager() : m_first_free( NONE ), m_last_free( NONE ) {}

                handle create_handle()
                {
                        typedef handle_operator<HANDLE> hop;
                        value_type i = get_free_entry();
                        m_entries[i].counter++;
                        m_entries[i].next_free = USED;
                        return hop::create( i, m_entries[i].counter );
                }

                void free_handle( handle h )
                {
                        m_entries[h.index()].next_free = NONE;
                        if ( m_last_free == -1 )
                        {
                                m_first_free = m_last_free = h.index();
                                return;
                        }
                        m_entries[(unsigned)m_last_free].next_free = h.index();
                        m_last_free = h.index();
                }

                bool is_valid( handle h ) const
                {
                        typedef handle_operator<HANDLE> hop;
                        if ( h.is_nil() ) return false;
                        if ( h.index() >= m_entries.size() ) return false;
                        const index_entry& entry = m_entries[h.index()];
                        return entry.next_free == USED && entry.counter == hop::get_counter( h );
                }

        private:
                struct index_entry
                {
                        value_type counter;
                        sint32     next_free;

                        index_entry() : counter( 0 ), next_free( NONE ) {}
                };

                value_type get_free_entry()
                {
                        if ( m_first_free != -1 )
                        {
                                value_type result = (value_type)m_first_free;
                                m_first_free = m_entries[result].next_free;
                                m_entries[result].next_free = USED;
                                if ( m_first_free == -1 ) m_last_free = -1;
                                return result;
                        }
                        m_entries.emplace_back();
                        return value_type( m_entries.size() - 1 );
                }

                sint32 m_first_free;
                sint32 m_last_free;
                std::vector< index_entry > m_entries;
        };

        template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
        class packed_indexed_array
        {
        public:
                typedef HANDLE                   handle;
                typedef TINDEX                   index_type;
                typedef std::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;

                packed_indexed_array() {}
                packed_indexed_array( uint32 reserve )
                {
                        m_data.reserve( reserve );
                        m_indexes.reserve( reserve );
                }

                T* insert( handle h )
                {
                        resize_indexes_to( (index_type) h.index() );
                        m_indexes[ h.index() ] = (index_type) m_data.size();
                        m_handles.push_back( h );
                        m_data.emplace_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;             
                }

                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;
                }

                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;
                }

                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();
                        sint32 dead_eindex    = m_indexes[ h.index() ];
                        if ( dead_eindex != (sint32)m_data.size()-1 )
                        {
                                m_data[ (unsigned)dead_eindex ]    = 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;
                }

                void clear()
                {
                        m_data.clear();
                        m_handles.clear();
                        m_indexes.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_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( (size_t)size, -1 );
                        }
                }

                std::vector< T >          m_data;
                std::vector< handle >     m_handles;
                std::vector< index_type > m_indexes;
        };


        template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
        class handle_store
        {
        public:
                typedef HANDLE                   handle;
                typedef TINDEX                   index_type;
                typedef std::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;

                handle_store() {}

                explicit handle_store( uint32 reserve )
                {
                        m_data.reserve( reserve );
                }

                handle create()
                {
                        handle h = m_indexes.create_handle();
                        m_data.insert( h );
                        return h;
                }

                bool is_valid( handle h )
                {
                        return m_indexes.is_valid( h );
                }

                const value_type* get( handle h ) const
                {
                        return m_data.get( h );
                }

                value_type* get( handle h )
                {
                        return m_data.get( h );
                }

                void destroy( handle e )
                {
                        m_data.remove( e );
                        m_indexes.free_handle( e );
                }

                handle get_handle( index_type i ) const { return m_data.get_handle(i); }
                const value_type& operator[] ( index_type i ) const { return m_data[(unsigned)i]; }
                value_type& operator[] ( index_type i ) { return m_data[(unsigned)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:
                packed_indexed_array< T, handle, TINDEX > m_data;
                handle_manager< handle >                  m_indexes;
        };
        
}

namespace std
{
        template < 
                typename T, 
                unsigned IBITS,
                unsigned CBITS,
                typename TAG
        >
        struct hash<nv::handle<T,IBITS,CBITS,TAG>>
        {
                size_t operator()(const nv::handle<T,IBITS,CBITS,TAG>& h) const
                {
                        return h.hash();
                }
        };
}

#endif // NV_CORE_HANDLE_HH