Index: /trunk/nv/ecs/ecs.hh =================================================================== --- /trunk/nv/ecs/ecs.hh (revision 529) +++ /trunk/nv/ecs/ecs.hh (revision 530) @@ -17,4 +17,7 @@ #include #include +#include +#include +#include #include @@ -25,103 +28,6 @@ { - template < - typename Handle = handle<>, - typename Index = sint32 - > - class index_table - { - public: - typedef Handle handle_type; - typedef Index index_type; - - index_table() {} - index_table( uint32 reserve ) - { - m_indexes.reserve( reserve ); - } - - index_type insert( handle_type 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_type h ) const - { - if ( h.is_nil() || h.index() >= m_indexes.size() ) return false; - return m_indexes[h.index()] >= 0; - } - - index_type get( handle_type h ) const - { - if ( h.is_nil() || h.index() >= m_indexes.size() ) return -1; - return m_indexes[h.index()]; - } - - index_type remove_swap( handle_type h ) - { - if ( h.is_nil() || h.index() >= m_indexes.size() || m_indexes[h.index()] == -1 ) - return -1; - handle_type swap_handle = m_handles.back(); - index_type dead_eindex = m_indexes[h.index()]; - if ( dead_eindex != static_cast( m_handles.size() - 1 ) ) - { - m_handles[unsigned( dead_eindex )] = swap_handle; - m_indexes[swap_handle.index()] = dead_eindex; - } - m_handles.pop_back(); - m_indexes[h.index()] = -1; - return dead_eindex; - } - - index_type remove_swap( index_type dead_eindex ) - { - if ( size_t( dead_eindex ) >= m_handles.size() ) return -1; - handle_type h = m_handles[ dead_eindex ]; - handle_type swap_handle = m_handles.back(); - if ( dead_eindex != static_cast( m_handles.size() - 1 ) ) - { - m_handles[unsigned( dead_eindex )] = swap_handle; - m_indexes[swap_handle.index()] = dead_eindex; - } - m_handles.pop_back(); - m_indexes[ h.index() ] = -1; - return dead_eindex; - } - - - void clear() - { - m_handles.clear(); - m_indexes.clear(); - } - - handle_type 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 ), -1 ); - } - } - - vector< handle_type > m_handles; - vector< index_type > m_indexes; - }; - - - - template < typename Handle = handle<>, typename Time = f32 > + + template < typename Handle, typename Time = f32 > class ecs { @@ -202,5 +108,5 @@ bool queue( const message& m ) { - push_event( m ); + m_pqueue.push( m ); return true; } @@ -214,5 +120,4 @@ } - handle_type create() { @@ -224,8 +129,8 @@ if ( dtime == time_type(0) ) return; m_time += dtime; - while ( !m_queue.empty() && m_queue.front().time <= m_time ) - { - message msg = m_queue.front(); - pop_event(); + while ( !m_pqueue.empty() && m_pqueue.top().time <= m_time ) + { + message msg = m_pqueue.top(); + m_pqueue.pop(); dispatch( msg ); } @@ -238,9 +143,9 @@ { time_type before = m_time; - if ( !m_queue.empty() ) - { - message msg = m_queue.front(); + if ( !m_pqueue.empty() ) + { + message msg = m_pqueue.top(); m_time = msg.time; - pop_event(); + m_pqueue.pop(); dispatch( msg ); if ( before != m_time ) @@ -255,15 +160,15 @@ bool events_pending() const { - return !m_queue.empty(); + return !m_pqueue.empty(); } const message& top_event() const { - return m_queue.front(); + return m_pqueue.top(); } void reset_events() { - m_queue.clear(); + m_pqueue.clear(); m_time = time_type(0); } @@ -302,15 +207,4 @@ protected: - void push_event( const message& msg ) - { - m_queue.push_back( msg ); - push_heap( m_queue.begin(), m_queue.end(), m_compare ); - } - - void pop_event() - { - pop_heap( m_queue.begin(), m_queue.end(), m_compare ); - m_queue.pop_back(); - } handle_manager< handle_type > m_handles; @@ -319,19 +213,18 @@ hash_store< thash64, component_interface* > m_component_map; time_type m_time = time_type(0); - vector< message > m_queue; - message_compare_type m_compare; + priority_queue< message, vector< message >, message_compare_type > m_pqueue; }; - template < typename ECS, typename COMPONENT > - class component : public ECS::component_interface + template < typename Ecs, typename Component > + class component : public Ecs::component_interface { public: - typedef ECS ecs_type; + typedef Ecs ecs_type; typedef typename ecs_type::message message_type; typedef typename ecs_type::handle_type handle_type; typedef typename ecs_type::time_type time_type; typedef index_table< handle_type > index_table_type; - typedef COMPONENT value_type; - typedef COMPONENT component_type; + typedef Component value_type; + typedef Component component_type; typedef vector< value_type > storage_type; typedef typename index_table_type::index_type index_type; @@ -461,9 +354,9 @@ }; - template < typename ECS > - class receiver : public ECS::receiver_interface + template < typename Ecs > + class receiver : public Ecs::receiver_interface { public: - typedef ECS ecs_type; + typedef Ecs ecs_type; typedef typename ecs_type::message message_type; typedef typename ecs_type::handle_type handle_type; Index: /trunk/nv/engine/particle_group.hh =================================================================== --- /trunk/nv/engine/particle_group.hh (revision 529) +++ /trunk/nv/engine/particle_group.hh (revision 530) @@ -12,4 +12,5 @@ #include #include +#include #include Index: /trunk/nv/fmod/fmod_audio.hh =================================================================== --- /trunk/nv/fmod/fmod_audio.hh (revision 529) +++ /trunk/nv/fmod/fmod_audio.hh (revision 530) @@ -1,3 +1,3 @@ -// Copyright (C) 2012-2015 ChaosForge Ltd +// Copyright (C) 2012-2017 ChaosForge Ltd // http://chaosforge.org/ // @@ -16,4 +16,5 @@ #include #include +#include namespace nv Index: /trunk/nv/gl/gl_context.hh =================================================================== --- /trunk/nv/gl/gl_context.hh (revision 529) +++ /trunk/nv/gl/gl_context.hh (revision 530) @@ -15,4 +15,5 @@ #include +#include namespace nv Index: /trunk/nv/gl/gl_device.hh =================================================================== --- /trunk/nv/gl/gl_device.hh (revision 529) +++ /trunk/nv/gl/gl_device.hh (revision 530) @@ -1,3 +1,3 @@ -// Copyright (C) 2012-2015 ChaosForge Ltd +// Copyright (C) 2012-2017 ChaosForge Ltd // http://chaosforge.org/ // @@ -15,4 +15,5 @@ #include +#include namespace nv Index: /trunk/nv/gui/gui_environment.hh =================================================================== --- /trunk/nv/gui/gui_environment.hh (revision 529) +++ /trunk/nv/gui/gui_environment.hh (revision 530) @@ -1,3 +1,3 @@ -// Copyright (C) 2012-2015 ChaosForge Ltd +// Copyright (C) 2012-2017 ChaosForge Ltd // http://chaosforge.org/ // @@ -14,4 +14,5 @@ #define NV_GUI_ENVIRONMENT_HH +#include #include #include Index: /trunk/nv/sdl/sdl_audio.hh =================================================================== --- /trunk/nv/sdl/sdl_audio.hh (revision 529) +++ /trunk/nv/sdl/sdl_audio.hh (revision 530) @@ -16,4 +16,5 @@ #include #include +#include namespace nv Index: /trunk/nv/stl/handle.hh =================================================================== --- /trunk/nv/stl/handle.hh (revision 529) +++ /trunk/nv/stl/handle.hh (revision 530) @@ -1,3 +1,3 @@ -// Copyright (C) 2014-2015 ChaosForge Ltd +// Copyright (C) 2014-2017 ChaosForge Ltd // http://chaosforge.org/ // @@ -15,4 +15,5 @@ #include #include +#include namespace nv @@ -56,421 +57,5 @@ }; - 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, typename INDEX = sint32 > - class handle_manager - { - typedef INDEX index_type; - static const index_type NONE = index_type(-1); - static const index_type USED = index_type(-2); - public: - - typedef HANDLE handle_type; - typedef typename HANDLE::value_type value_type; - - handle_manager() : m_first_free( NONE ), m_last_free( NONE ) {} - - handle_type create_handle() - { - typedef handle_operator hop; - value_type i = get_free_entry(); - m_entries[i].counter++; - NV_ASSERT( m_entries[i].counter != 0, "Out of handles!" ); - m_entries[i].next_free = USED; - return hop::create( i, m_entries[i].counter ); - } - - void free_handle( handle_type h ) - { - value_type index = h.index(); - NV_ASSERT( m_entries[index].next_free == USED, "Unused handle freed!" ); - NV_ASSERT( m_entries[index].counter == handle_operator::get_counter( h ), "Handle corruption!" ); - m_entries[index].next_free = NONE; - if ( m_last_free == NONE ) - { - m_first_free = m_last_free = static_cast( index ); - return; - } - m_entries[static_cast( m_last_free ) ].next_free = static_cast( index ); - m_last_free = static_cast( index ); - } - - bool is_valid( handle_type h ) const - { - typedef handle_operator 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 ); - } - - void clear() - { - m_first_free = NONE; - m_last_free = NONE; - m_entries.clear(); - } - - private: - struct index_entry - { - value_type counter; - index_type next_free; - - index_entry() : counter( 0 ), next_free( NONE ) {} - }; - - value_type get_free_entry() - { - if ( m_first_free != NONE ) - { - value_type result = static_cast( m_first_free ); - m_first_free = m_entries[result].next_free; - m_entries[result].next_free = USED; - if ( m_first_free == NONE ) m_last_free = NONE; - return result; - } - m_entries.emplace_back(); - return value_type( m_entries.size() - 1 ); - } - - index_type m_first_free; - 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_type; - typedef TINDEX index_type; - packed_index_table() {} - packed_index_table( uint32 reserve ) - { - m_indexes.reserve( reserve ); - } - - index_type insert( handle_type 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_type h ) - { - if ( h.is_nil() || h.index() >= m_indexes.size() ) return false; - return m_indexes[h.index()] >= 0; - } - - index_type get( handle_type h ) - { - if ( h.is_nil() || h.index() >= m_indexes.size() ) return -1; - return m_indexes[h.index()]; - } - - index_type get( handle_type h ) const - { - if ( h.is_nil() || h.index() >= m_indexes.size() ) return -1; - return m_indexes[h.index()]; - } - - index_type remove_swap( handle_type h ) - { - if ( h.is_nil() || h.index() >= m_indexes.size() || m_indexes[h.index()] == -1 ) - return -1; - handle_type swap_handle = m_handles.back(); - index_type dead_eindex = m_indexes[h.index()]; - if ( dead_eindex != static_cast( 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_type 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 ), -1 ); - } - } - - vector< handle_type > m_handles; - vector< index_type > m_indexes; - }; - - template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 > - class packed_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; - - packed_indexed_array() {} - packed_indexed_array( uint32 reserve ) - { - m_data.reserve( reserve ); - m_indexes.reserve( reserve ); - } - - T* insert( handle h ) - { - /*index_type i = */m_index.insert( h ); - //NV_ASSERT( i == m_data.size(), "Fail!" ); - m_data.emplace_back(); - return &( m_data.back() ); - } - - bool exists( handle h ) - { - return m_index.exists( h ); - } - - T* get( handle h ) - { - index_type i = m_index.get(h); - return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr; - } - - const T* get( handle h ) const - { - index_type i = m_index.get( h ); - return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr; - } - - void remove( handle h ) - { - index_type dead_eindex = m_index.remove_swap( h ); - if ( dead_eindex == -1 ) return; - if ( dead_eindex != static_cast( m_data.size() - 1 ) ) - { - m_data[unsigned( dead_eindex )] = move( m_data.back() ); - } - m_data.pop_back(); - } - - void clear() - { - m_index.clear(); - m_data.clear(); - } - - 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]; } - 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: - 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 ); - } - - 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_handles.size() ); - if ( i >= size ) - { - if ( size == 0 ) size = 1; - while ( i >= size ) size = size * 2; - m_data.resize( static_cast( size ) ); - m_handles.resize( static_cast( size ) ); - } - } - - vector< T > m_data; - vector< handle > m_handles; - }; - - - template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 > - class handle_store - { - 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; - - 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; - }; - } Index: /trunk/nv/stl/handle_manager.hh =================================================================== --- /trunk/nv/stl/handle_manager.hh (revision 530) +++ /trunk/nv/stl/handle_manager.hh (revision 530) @@ -0,0 +1,122 @@ +// Copyright (C) 2014-2017 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of Nova libraries. +// For conditions of distribution and use, +// see copying.txt file in root folder. + +/** +* @file handle_manager.hh +* @author Kornel Kisielewicz +*/ + +#ifndef NV_STL_HANDLE_MANAGER_HH +#define NV_STL_HANDLE_MANAGER_HH + +#include +#include +#include + +namespace nv +{ + + template < typename Handle > + class handle_operator + { + public: + typedef typename Handle handle_type; + typedef typename handle_type::value_type value_type; + + static handle_type create( value_type index, value_type counter ) + { + return handle_type( index, counter ); + } + static value_type get_counter( const handle_type& h ) { return h.m_counter; } + static value_type get_index( const handle_type& h ) { return h.m_index; } + }; + + template < typename Handle, typename Index = sint32 > + class handle_manager + { + typedef Index index_type; + static const index_type NONE = index_type( -1 ); + static const index_type USED = index_type( -2 ); + public: + + typedef Handle handle_type; + typedef typename handle_type::value_type value_type; + + handle_manager() : m_first_free( NONE ), m_last_free( NONE ) {} + + handle_type create_handle() + { + typedef handle_operator hop; + value_type i = get_free_entry(); + m_entries[i].counter++; + NV_ASSERT( m_entries[i].counter != 0, "Out of handles!" ); + m_entries[i].next_free = USED; + return hop::create( i, m_entries[i].counter ); + } + + void free_handle( handle_type h ) + { + value_type index = h.index(); + NV_ASSERT( m_entries[index].next_free == USED, "Unused handle freed!" ); + NV_ASSERT( m_entries[index].counter == handle_operator::get_counter( h ), "Handle corruption!" ); + m_entries[index].next_free = NONE; + if ( m_last_free == NONE ) + { + m_first_free = m_last_free = static_cast( index ); + return; + } + m_entries[static_cast( m_last_free )].next_free = static_cast( index ); + m_last_free = static_cast( index ); + } + + bool is_valid( handle_type h ) const + { + typedef handle_operator 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 ); + } + + void clear() + { + m_first_free = NONE; + m_last_free = NONE; + m_entries.clear(); + } + + private: + struct index_entry + { + value_type counter; + index_type next_free; + + index_entry() : counter( 0 ), next_free( NONE ) {} + }; + + value_type get_free_entry() + { + if ( m_first_free != NONE ) + { + value_type result = static_cast( m_first_free ); + m_first_free = m_entries[result].next_free; + m_entries[result].next_free = USED; + if ( m_first_free == NONE ) m_last_free = NONE; + return result; + } + m_entries.emplace_back(); + return value_type( m_entries.size() - 1 ); + } + + index_type m_first_free; + index_type m_last_free; + vector< index_entry > m_entries; + }; + +} + +#endif // NV_STL_HANDLE_MANAGER_HH Index: /trunk/nv/stl/handle_store.hh =================================================================== --- /trunk/nv/stl/handle_store.hh (revision 530) +++ /trunk/nv/stl/handle_store.hh (revision 530) @@ -0,0 +1,263 @@ +// Copyright (C) 2014-2017 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of Nova libraries. +// For conditions of distribution and use, +// see copying.txt file in root folder. + +/** +* @file handle_store.hh +* @author Kornel Kisielewicz +*/ + +#ifndef NV_STL_HANDLE_STORE_HH +#define NV_STL_HANDLE_STORE_HH + +#include +#include +#include +#include + +namespace nv +{ + + template < typename T, typename Handle = handle<>, typename Index = sint32 > + class packed_indexed_array + { + public: + typedef Handle handle_type; + typedef Index index_type; + typedef T value_type; + typedef vector< value_type > storage_type; + typedef typename storage_type::iterator iterator; + typedef typename storage_type::const_iterator const_iterator; + typedef typename storage_type::reference reference; + typedef typename storage_type::const_reference const_reference; + + packed_indexed_array() {} + packed_indexed_array( uint32 reserve ) + { + m_data.reserve( reserve ); + m_indexes.reserve( reserve ); + } + + T* insert( handle_type h ) + { + /*index_type i = */m_index.insert( h ); + //NV_ASSERT( i == m_data.size(), "Fail!" ); + m_data.emplace_back(); + return &( m_data.back() ); + } + + bool exists( handle_type h ) + { + return m_index.exists( h ); + } + + T* get( handle_type h ) + { + index_type i = m_index.get( h ); + return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr; + } + + const T* get( handle_type h ) const + { + index_type i = m_index.get( h ); + return i >= 0 ? &( m_data[unsigned( i )] ) : nullptr; + } + + void remove( handle_type h ) + { + index_type dead_eindex = m_index.remove_swap( h ); + if ( dead_eindex == -1 ) return; + if ( dead_eindex != static_cast( m_data.size() - 1 ) ) + { + m_data[unsigned( dead_eindex )] = move( m_data.back() ); + } + m_data.pop_back(); + } + + void clear() + { + m_index.clear(); + m_data.clear(); + } + + handle_type get_handle( index_type i ) const { return m_index.get_handle( 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: + storage_type m_data; + index_table< handle_type, index_type > 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 ); + } + + 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_handles.size() ); + if ( i >= size ) + { + if ( size == 0 ) size = 1; + while ( i >= size ) size = size * 2; + m_data.resize( static_cast( size ) ); + m_handles.resize( static_cast( size ) ); + } + } + + vector< T > m_data; + vector< handle > m_handles; + }; + + + template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 > + class handle_store + { + 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; + + 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; + }; + +} + +#endif // NV_STL_HANDLE_STORE_HH Index: /trunk/nv/stl/hash_store.hh =================================================================== --- /trunk/nv/stl/hash_store.hh (revision 529) +++ /trunk/nv/stl/hash_store.hh (revision 530) @@ -1,3 +1,3 @@ -// Copyright (C) 2015 ChaosForge Ltd +// Copyright (C) 2015-2017 ChaosForge Ltd // http://chaosforge.org/ // Index: /trunk/nv/stl/index_table.hh =================================================================== --- /trunk/nv/stl/index_table.hh (revision 530) +++ /trunk/nv/stl/index_table.hh (revision 530) @@ -0,0 +1,120 @@ +// Copyright (C) 2017-2017 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of Nova libraries. +// For conditions of distribution and use, +// see copying.txt file in root folder. + +/** + * @file index_table.hh + * @author Kornel Kisielewicz + */ + +#ifndef NV_STL_INDEX_TABLE_HH +#define NV_STL_INDEX_TABLE_HH + +#include +#include + +namespace nv +{ + + template < + typename Handle, + typename Index = sint32 + > + class index_table + { + public: + typedef Handle handle_type; + typedef Index index_type; + + index_table() {} + index_table( uint32 reserve ) + { + m_indexes.reserve( reserve ); + } + + index_type insert( handle_type 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_type h ) const + { + if ( h.is_nil() || h.index() >= m_indexes.size() ) return false; + return m_indexes[h.index()] >= 0; + } + + index_type get( handle_type h ) const + { + if ( h.is_nil() || h.index() >= m_indexes.size() ) return -1; + return m_indexes[h.index()]; + } + + index_type remove_swap( handle_type h ) + { + if ( h.is_nil() || h.index() >= m_indexes.size() || m_indexes[h.index()] == -1 ) + return -1; + handle_type swap_handle = m_handles.back(); + index_type dead_eindex = m_indexes[h.index()]; + if ( dead_eindex != static_cast( m_handles.size() - 1 ) ) + { + m_handles[unsigned( dead_eindex )] = swap_handle; + m_indexes[swap_handle.index()] = dead_eindex; + } + m_handles.pop_back(); + m_indexes[h.index()] = -1; + return dead_eindex; + } + + index_type remove_swap( index_type dead_eindex ) + { + if ( size_t( dead_eindex ) >= m_handles.size() ) return -1; + handle_type h = m_handles[dead_eindex]; + handle_type swap_handle = m_handles.back(); + if ( dead_eindex != static_cast( m_handles.size() - 1 ) ) + { + m_handles[unsigned( dead_eindex )] = swap_handle; + m_indexes[swap_handle.index()] = dead_eindex; + } + m_handles.pop_back(); + m_indexes[h.index()] = -1; + return dead_eindex; + } + + + void clear() + { + m_handles.clear(); + m_indexes.clear(); + } + + handle_type 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 ), -1 ); + } + } + + vector< handle_type > m_handles; + vector< index_type > m_indexes; + }; + +} + +#endif // NV_STL_INDEX_TABLE_HH Index: /trunk/nv/stl/priority_queue.hh =================================================================== --- /trunk/nv/stl/priority_queue.hh (revision 529) +++ /trunk/nv/stl/priority_queue.hh (revision 530) @@ -14,4 +14,5 @@ #define NV_STL_PRIORITY_QUEUE_HH +#include #include @@ -111,4 +112,9 @@ } + void clear() + { + m_data.clear(); + } + void swap( this_type& rhs ) {