Context Navigation

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

Last change on this file since 323 was 323, checked in by epyon, 11 years ago
nova now compiles again under all three compilers with -Winsane and no warnings
File size: 8.5 KB

Rev	Line
[270]	1	// Copyright (C) 2014 ChaosForge Ltd
	2	// http://chaosforge.org/
	3	//
	4	// This file is part of NV Libraries.
	5	// For conditions of distribution and use, see copyright notice in nv.hh
	6
	7	/**
	8	* @file handle.hh
	9	* @author Kornel Kisielewicz
	10	*/
	11
[319]	12	#ifndef NV_CORE_HANDLE_HH
	13	#define NV_CORE_HANDLE_HH
[270]	14
[319]	15	#include <nv/core/common.hh>
	16	#include <nv/core/array.hh>
[270]	17
	18	namespace nv
	19	{
	20
	21	template <
	22	typename T = uint32,
	23	unsigned IBITS = 16,
	24	unsigned CBITS = 16,
	25	typename TAG = void
	26	>
	27	class handle
	28	{
	29	public:
	30	typedef T value_type;
	31	static const int INDEX_BITS = IBITS;
	32	static const int COUNTER_BITS = IBITS;
	33	static const T MAX_INDEX = (1 << IBITS) - 1;
	34	static const T MAX_COUNTER = (1 << CBITS) - 1;
	35
	36	handle() : m_index(0), m_counter(0) {}
	37
[273]	38	inline bool operator==(const handle& rhs) const {return m_index == rhs.m_index && m_counter == rhs.m_counter; }
	39	inline bool operator!=(const handle& rhs) const {return !(*this == rhs);}
[270]	40
	41	bool is_nil() const { return m_index == 0 && m_counter == 0; }
	42	bool is_valid() const { return !is_nil(); }
[273]	43	T index() const { return m_index; }
[323]	44	size_t hash() const { return std::hash<T>()( T( m_counter << IBITS \| m_index ) ); }
[270]	45	protected:
	46	T m_index : IBITS;
	47	T m_counter : CBITS;
	48
	49	handle( T a_index, T a_counter ) : m_index( a_index ), m_counter( a_counter ) {}
	50	template < typename H, typename I >
	51	friend class index_store;
	52	};
	53
[273]	54
	55
[270]	56	template < typename HANDLE, typename TINDEX = sint32 >
	57	class index_store
	58	{
	59	public:
	60	typedef HANDLE handle;
	61	typedef TINDEX index_type;
	62	typedef typename HANDLE::value_type value_type;
	63
	64	index_store() : m_first_free(-1), m_last_free(-1) {}
	65
	66	handle create_handle( index_type index )
	67	{
	68	value_type i = get_free_entry();
	69	m_entries[i].index = index;
	70	m_entries[i].counter++;
	71	return handle( i, m_entries[i].counter );
	72	}
	73
	74	void free_handle( handle h )
	75	{
	76	m_entries[ h.m_index ].index = -1;
	77	m_entries[ h.m_index ].next_free = -1;
	78	if ( m_last_free == -1 )
	79	{
	80	m_first_free = m_last_free = h.m_index;
	81	return;
	82	}
[323]	83	m_entries[ (unsigned)m_last_free ].next_free = h.m_index;
[270]	84	m_last_free = h.m_index;
	85	}
	86
	87	void swap_indices( handle h1, handle h2 )
	88	{
	89	std::swap( m_entries[ h1.m_index ].index, m_entries[ h2.m_index ].index );
	90	}
	91
	92	sint32 get_index( handle h ) const
	93	{
	94	return m_entries[ h.m_index ].counter == h.m_counter ? m_entries[ h.m_index ].index : -1;
	95	}
	96	private:
	97	struct index_entry
	98	{
	99	index_type index;
	100	value_type counter;
	101	index_type next_free;
	102
	103	index_entry() : index(0), counter(0), next_free(-1) {}
	104	};
	105
	106	value_type get_free_entry()
	107	{
	108	if ( m_first_free != -1 )
	109	{
	110	value_type result = (value_type)m_first_free;
	111	m_first_free = m_entries[result].next_free;
	112	m_entries[result].next_free = -1;
	113	if ( m_first_free == -1 ) m_last_free = -1;
	114	return result;
	115	}
	116	m_entries.emplace_back();
	117	return value_type( m_entries.size() - 1 );
	118	}
	119
	120	index_type m_first_free;
	121	index_type m_last_free;
	122	std::vector< index_entry > m_entries;
	123	};
	124
[274]	125	template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
	126	class packed_indexed_array
	127	{
	128	public:
	129	typedef HANDLE handle;
	130	typedef TINDEX index_type;
	131	typedef std::vector< T > storage;
	132	typedef T value_type;
	133	typedef typename storage::iterator iterator;
	134	typedef typename storage::const_iterator const_iterator;
	135	typedef typename storage::reference reference;
	136	typedef typename storage::const_reference const_reference;
[273]	137
[274]	138	packed_indexed_array() {}
	139	packed_indexed_array( uint32 reserve )
	140	{
	141	m_data.reserve( reserve );
	142	m_indexes.reserve( reserve );
	143	}
[273]	144
[274]	145	T* insert( handle h )
	146	{
[323]	147	resize_indexes_to( (index_type) h.index() );
	148	m_indexes[ h.index() ] = (index_type) m_data.size();
[295]	149	m_handles.push_back( h );
[274]	150	m_data.emplace_back();
	151	return &(m_data.back());
	152	}
	153
	154	bool exists( handle h )
	155	{
	156	if ( h.is_nil() \|\| h.index() >= m_indexes.size() ) return false;
	157	return m_indexes[ h.index() ] >= 0;
	158	}
	159
	160	T* get( handle h )
	161	{
	162	if ( h.is_nil() \|\| h.index() >= m_indexes.size() ) return nullptr;
	163	index_type i = m_indexes[ h.index() ];
[323]	164	return i >= 0 ? &(m_data[ (unsigned)i ]) : nullptr;
[274]	165	}
	166
	167	void remove( handle h )
	168	{
	169	handle swap_handle = m_handles.back();
	170	sint32 dead_eindex = m_indexes[ h.index() ];
	171	if ( dead_eindex != (sint32)m_data.size()-1 )
	172	{
[323]	173	m_data[ (unsigned)dead_eindex ] = m_data.back();
	174	m_handles[ (unsigned)dead_eindex ] = swap_handle;
	175	m_indexes[ swap_handle.index() ] = dead_eindex;
[274]	176	}
	177	m_data.pop_back();
	178	m_handles.pop_back();
	179	m_indexes[ h.index() ] = -1;
	180	}
	181
	182	void clear()
	183	{
	184	m_data.clear();
	185	m_handles.clear();
	186	m_indexes.clear();
	187	}
	188
	189	const value_type& operator[] ( index_type i ) const { return m_data[i]; }
	190	value_type& operator[] ( index_type i ) { return m_data[i]; }
	191	size_t size() const { return m_data.size(); }
	192
	193	iterator begin() { return m_data.begin(); }
	194	const_iterator begin() const { return m_data.cbegin(); }
	195	const_iterator cbegin() const { return m_data.cbegin(); }
	196
	197	iterator end() { return m_data.end(); }
	198	const_iterator end() const { return m_data.cend(); }
	199	const_iterator cend() const { return m_data.cend(); }
	200
	201	private:
	202	void resize_indexes_to( index_type i )
	203	{
	204	index_type size = (index_type)m_indexes.size();
	205	if ( i >= size )
	206	{
	207	if ( size == 0 ) size = 1;
	208	while ( i >= size ) size = size * 2;
[323]	209	m_indexes.resize( (size_t)size, -1 );
[274]	210	}
	211	}
	212
	213	std::vector< T > m_data;
	214	std::vector< handle > m_handles;
	215	std::vector< index_type > m_indexes;
	216	};
	217
	218
[271]	219	template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
	220	class entity_store
	221	{
	222	public:
[272]	223	typedef HANDLE handle;
	224	typedef TINDEX index_type;
	225	typedef std::vector< T > storage;
	226	typedef T value_type;
	227	typedef typename storage::iterator iterator;
	228	typedef typename storage::const_iterator const_iterator;
	229	typedef typename storage::reference reference;
	230	typedef typename storage::const_reference const_reference;
[270]	231
[271]	232	entity_store() {}
[273]	233
	234	explicit entity_store( uint32 reserve )
	235	{
	236	m_handles.reserve( reserve );
	237	m_data.reserve( reserve );
	238	}
	239
[271]	240	handle create()
	241	{
	242	m_data.emplace_back();
	243	m_handles.push_back( m_indexes.create_handle( sint32( m_data.size() - 1 ) ) );
	244	return m_handles.back();
	245	}
[273]	246
[287]	247	const value_type* get( handle h ) const
	248	{
	249	if ( h.is_nil() ) return nullptr;
	250	sint32 eindex = m_indexes.get_index( h );
[323]	251	return eindex >= 0 ? &(m_data[ (unsigned)eindex ]) : nullptr;
[287]	252	}
	253
[271]	254	value_type* get( handle h )
	255	{
	256	if ( h.is_nil() ) return nullptr;
	257	sint32 eindex = m_indexes.get_index( h );
[323]	258	return eindex >= 0 ? &(m_data[ (unsigned)eindex ]) : nullptr;
[271]	259	}
[273]	260
[271]	261	void destroy( handle e )
	262	{
	263	handle swap_handle = m_handles.back();
	264	sint32 dead_eindex = m_indexes.get_index( e );
	265	if ( dead_eindex != (sint32)m_data.size()-1 )
	266	{
[323]	267	m_data[ (unsigned)dead_eindex ] = m_data.back();
	268	m_handles[ (unsigned)dead_eindex ] = m_handles.back();
[271]	269	}
	270	m_data.pop_back();
	271	m_handles.pop_back();
	272	m_indexes.swap_indices( e, swap_handle );
	273	m_indexes.free_handle( e );
	274	}
[272]	275
[323]	276	handle get_handle( index_type i ) const { return m_handles[(unsigned)i]; }
	277	const value_type& operator[] ( index_type i ) const { return m_data[(unsigned)i]; }
	278	value_type& operator[] ( index_type i ) { return m_data[(unsigned)i]; }
[274]	279	size_t size() const { return m_data.size(); }
	280
[272]	281	iterator begin() { return m_data.begin(); }
	282	const_iterator begin() const { return m_data.cbegin(); }
	283	const_iterator cbegin() const { return m_data.cbegin(); }
	284
	285	iterator end() { return m_data.end(); }
	286	const_iterator end() const { return m_data.cend(); }
	287	const_iterator cend() const { return m_data.cend(); }
	288
[271]	289	private:
	290	std::vector< handle > m_handles;
[272]	291	storage m_data;
[271]	292	index_store< handle, TINDEX > m_indexes;
	293	};
	294
[273]	295	}
[271]	296
[273]	297	namespace std
	298	{
	299	template <
	300	typename T,
	301	unsigned IBITS,
	302	unsigned CBITS,
	303	typename TAG
	304	>
	305	struct hash<nv::handle<T,IBITS,CBITS,TAG>>
	306	{
	307	size_t operator()(const nv::handle<T,IBITS,CBITS,TAG>& h) const
	308	{
	309	return h.hash();
	310	}
	311	};
[270]	312	}
	313
[319]	314	#endif // NV_CORE_HANDLE_HH

Note: See TracBrowser for help on using the repository browser.

Download in other formats: