Context Navigation

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

Last change on this file since 339 was 339, checked in by epyon, 11 years ago
handle - index_store/entity_store is_valid added handle - packed_indexed_array will silently ignore invalid removes
File size: 9.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;
[333]	31	typedef TAG tag_type;
[270]	32	static const int INDEX_BITS = IBITS;
	33	static const int COUNTER_BITS = IBITS;
	34	static const T MAX_INDEX = (1 << IBITS) - 1;
	35	static const T MAX_COUNTER = (1 << CBITS) - 1;
	36
	37	handle() : m_index(0), m_counter(0) {}
	38
[273]	39	inline bool operator==(const handle& rhs) const {return m_index == rhs.m_index && m_counter == rhs.m_counter; }
	40	inline bool operator!=(const handle& rhs) const {return !(*this == rhs);}
[270]	41
	42	bool is_nil() const { return m_index == 0 && m_counter == 0; }
	43	bool is_valid() const { return !is_nil(); }
[273]	44	T index() const { return m_index; }
[323]	45	size_t hash() const { return std::hash<T>()( T( m_counter << IBITS \| m_index ) ); }
[270]	46	protected:
	47	T m_index : IBITS;
	48	T m_counter : CBITS;
	49
	50	handle( T a_index, T a_counter ) : m_index( a_index ), m_counter( a_counter ) {}
[333]	51	template < typename H >
	52	friend class handle_operator;
[270]	53	};
	54
[333]	55	template < typename HANDLE >
	56	class handle_operator
	57	{
	58	public:
	59	typedef typename HANDLE::value_type value_type;
[273]	60
[333]	61	static HANDLE create( value_type index, value_type counter )
	62	{
	63	return HANDLE( index, counter );
	64	}
	65	static value_type get_counter( const HANDLE& h ) { return h.m_counter; }
	66	static value_type get_index( const HANDLE& h ) { return h.m_index; }
	67	};
[273]	68
[333]	69
[270]	70	template < typename HANDLE, typename TINDEX = sint32 >
	71	class index_store
	72	{
	73	public:
	74	typedef HANDLE handle;
	75	typedef TINDEX index_type;
	76	typedef typename HANDLE::value_type value_type;
	77
	78	index_store() : m_first_free(-1), m_last_free(-1) {}
	79
	80	handle create_handle( index_type index )
	81	{
[333]	82	typedef handle_operator<HANDLE> hop;
[270]	83	value_type i = get_free_entry();
	84	m_entries[i].index = index;
	85	m_entries[i].counter++;
[333]	86	return hop::create( i, m_entries[i].counter );
[270]	87	}
	88
	89	void free_handle( handle h )
	90	{
[333]	91	m_entries[ h.index() ].index = -1;
	92	m_entries[ h.index() ].next_free = -1;
[270]	93	if ( m_last_free == -1 )
	94	{
[333]	95	m_first_free = m_last_free = h.index();
[270]	96	return;
	97	}
[333]	98	m_entries[ (unsigned)m_last_free ].next_free = h.index();
	99	m_last_free = h.index();
[270]	100	}
	101
	102	void swap_indices( handle h1, handle h2 )
	103	{
[333]	104	std::swap( m_entries[ h1.index() ].index, m_entries[ h2.index() ].index );
[270]	105	}
	106
[339]	107	bool is_valid( handle h ) const
	108	{
	109	typedef handle_operator<HANDLE> hop;
	110	if ( h.is_nil() ) return false;
	111	if ( h.index() >= m_entries.size() ) return false;
	112	const index_entry& entry = m_entries[ h.index() ];
	113	return entry.index >= 0 && entry.counter == hop::get_counter(h);
	114	}
	115
[270]	116	sint32 get_index( handle h ) const
	117	{
[333]	118	typedef handle_operator<HANDLE> hop;
	119	return m_entries[ h.index() ].counter == hop::get_counter(h) ? m_entries[ h.index() ].index : -1;
[270]	120	}
	121	private:
	122	struct index_entry
	123	{
	124	index_type index;
	125	value_type counter;
	126	index_type next_free;
	127
	128	index_entry() : index(0), counter(0), next_free(-1) {}
	129	};
	130
	131	value_type get_free_entry()
	132	{
	133	if ( m_first_free != -1 )
	134	{
	135	value_type result = (value_type)m_first_free;
	136	m_first_free = m_entries[result].next_free;
	137	m_entries[result].next_free = -1;
	138	if ( m_first_free == -1 ) m_last_free = -1;
	139	return result;
	140	}
	141	m_entries.emplace_back();
	142	return value_type( m_entries.size() - 1 );
	143	}
	144
	145	index_type m_first_free;
	146	index_type m_last_free;
	147	std::vector< index_entry > m_entries;
	148	};
	149
[274]	150	template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
	151	class packed_indexed_array
	152	{
	153	public:
	154	typedef HANDLE handle;
	155	typedef TINDEX index_type;
	156	typedef std::vector< T > storage;
	157	typedef T value_type;
	158	typedef typename storage::iterator iterator;
	159	typedef typename storage::const_iterator const_iterator;
	160	typedef typename storage::reference reference;
	161	typedef typename storage::const_reference const_reference;
[273]	162
[274]	163	packed_indexed_array() {}
	164	packed_indexed_array( uint32 reserve )
	165	{
	166	m_data.reserve( reserve );
	167	m_indexes.reserve( reserve );
	168	}
[273]	169
[274]	170	T* insert( handle h )
	171	{
[323]	172	resize_indexes_to( (index_type) h.index() );
	173	m_indexes[ h.index() ] = (index_type) m_data.size();
[295]	174	m_handles.push_back( h );
[274]	175	m_data.emplace_back();
	176	return &(m_data.back());
	177	}
	178
	179	bool exists( handle h )
	180	{
	181	if ( h.is_nil() \|\| h.index() >= m_indexes.size() ) return false;
	182	return m_indexes[ h.index() ] >= 0;
	183	}
	184
	185	T* get( handle h )
	186	{
	187	if ( h.is_nil() \|\| h.index() >= m_indexes.size() ) return nullptr;
	188	index_type i = m_indexes[ h.index() ];
[323]	189	return i >= 0 ? &(m_data[ (unsigned)i ]) : nullptr;
[274]	190	}
	191
	192	void remove( handle h )
	193	{
[339]	194	if ( h.is_nil() \|\| h.index() >= m_indexes.size() \|\| m_indexes[h.index()] == -1 )
	195	return;
[274]	196	handle swap_handle = m_handles.back();
	197	sint32 dead_eindex = m_indexes[ h.index() ];
	198	if ( dead_eindex != (sint32)m_data.size()-1 )
	199	{
[323]	200	m_data[ (unsigned)dead_eindex ] = m_data.back();
	201	m_handles[ (unsigned)dead_eindex ] = swap_handle;
	202	m_indexes[ swap_handle.index() ] = dead_eindex;
[274]	203	}
	204	m_data.pop_back();
	205	m_handles.pop_back();
	206	m_indexes[ h.index() ] = -1;
	207	}
	208
	209	void clear()
	210	{
	211	m_data.clear();
	212	m_handles.clear();
	213	m_indexes.clear();
	214	}
	215
	216	const value_type& operator[] ( index_type i ) const { return m_data[i]; }
	217	value_type& operator[] ( index_type i ) { return m_data[i]; }
	218	size_t size() const { return m_data.size(); }
	219
	220	iterator begin() { return m_data.begin(); }
	221	const_iterator begin() const { return m_data.cbegin(); }
	222	const_iterator cbegin() const { return m_data.cbegin(); }
	223
	224	iterator end() { return m_data.end(); }
	225	const_iterator end() const { return m_data.cend(); }
	226	const_iterator cend() const { return m_data.cend(); }
	227
	228	private:
	229	void resize_indexes_to( index_type i )
	230	{
	231	index_type size = (index_type)m_indexes.size();
	232	if ( i >= size )
	233	{
	234	if ( size == 0 ) size = 1;
	235	while ( i >= size ) size = size * 2;
[323]	236	m_indexes.resize( (size_t)size, -1 );
[274]	237	}
	238	}
	239
	240	std::vector< T > m_data;
	241	std::vector< handle > m_handles;
	242	std::vector< index_type > m_indexes;
	243	};
	244
	245
[271]	246	template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
	247	class entity_store
	248	{
	249	public:
[272]	250	typedef HANDLE handle;
	251	typedef TINDEX index_type;
	252	typedef std::vector< T > storage;
	253	typedef T value_type;
	254	typedef typename storage::iterator iterator;
	255	typedef typename storage::const_iterator const_iterator;
	256	typedef typename storage::reference reference;
	257	typedef typename storage::const_reference const_reference;
[270]	258
[271]	259	entity_store() {}
[273]	260
	261	explicit entity_store( uint32 reserve )
	262	{
	263	m_handles.reserve( reserve );
	264	m_data.reserve( reserve );
	265	}
	266
[271]	267	handle create()
	268	{
	269	m_data.emplace_back();
	270	m_handles.push_back( m_indexes.create_handle( sint32( m_data.size() - 1 ) ) );
	271	return m_handles.back();
	272	}
[273]	273
[339]	274	bool is_valid( handle h )
	275	{
	276	return m_indexes.is_valid(h);
	277	}
	278
[287]	279	const value_type* get( handle h ) const
	280	{
	281	if ( h.is_nil() ) return nullptr;
	282	sint32 eindex = m_indexes.get_index( h );
[323]	283	return eindex >= 0 ? &(m_data[ (unsigned)eindex ]) : nullptr;
[287]	284	}
	285
[271]	286	value_type* get( handle h )
	287	{
	288	if ( h.is_nil() ) return nullptr;
	289	sint32 eindex = m_indexes.get_index( h );
[323]	290	return eindex >= 0 ? &(m_data[ (unsigned)eindex ]) : nullptr;
[271]	291	}
[273]	292
[271]	293	void destroy( handle e )
	294	{
	295	handle swap_handle = m_handles.back();
	296	sint32 dead_eindex = m_indexes.get_index( e );
	297	if ( dead_eindex != (sint32)m_data.size()-1 )
	298	{
[323]	299	m_data[ (unsigned)dead_eindex ] = m_data.back();
	300	m_handles[ (unsigned)dead_eindex ] = m_handles.back();
[271]	301	}
	302	m_data.pop_back();
	303	m_handles.pop_back();
	304	m_indexes.swap_indices( e, swap_handle );
	305	m_indexes.free_handle( e );
	306	}
[272]	307
[323]	308	handle get_handle( index_type i ) const { return m_handles[(unsigned)i]; }
	309	const value_type& operator[] ( index_type i ) const { return m_data[(unsigned)i]; }
	310	value_type& operator[] ( index_type i ) { return m_data[(unsigned)i]; }
[274]	311	size_t size() const { return m_data.size(); }
	312
[272]	313	iterator begin() { return m_data.begin(); }
	314	const_iterator begin() const { return m_data.cbegin(); }
	315	const_iterator cbegin() const { return m_data.cbegin(); }
	316
	317	iterator end() { return m_data.end(); }
	318	const_iterator end() const { return m_data.cend(); }
	319	const_iterator cend() const { return m_data.cend(); }
	320
[271]	321	private:
	322	std::vector< handle > m_handles;
[272]	323	storage m_data;
[271]	324	index_store< handle, TINDEX > m_indexes;
	325	};
	326
[273]	327	}
[271]	328
[273]	329	namespace std
	330	{
	331	template <
	332	typename T,
	333	unsigned IBITS,
	334	unsigned CBITS,
	335	typename TAG
	336	>
	337	struct hash<nv::handle<T,IBITS,CBITS,TAG>>
	338	{
	339	size_t operator()(const nv::handle<T,IBITS,CBITS,TAG>& h) const
	340	{
	341	return h.hash();
	342	}
	343	};
[270]	344	}
	345
[319]	346	#endif // NV_CORE_HANDLE_HH

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

Download in other formats: