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

Line
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
12	#ifndef NV_CORE_HANDLE_HH
13	#define NV_CORE_HANDLE_HH
14
15	#include <nv/core/common.hh>
16	#include <nv/core/array.hh>
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	typedef TAG tag_type;
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
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);}
41
42	bool is_nil() const { return m_index == 0 && m_counter == 0; }
43	bool is_valid() const { return !is_nil(); }
44	T index() const { return m_index; }
45	size_t hash() const { return std::hash<T>()( T( m_counter << IBITS \| m_index ) ); }
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 ) {}
51	template < typename H >
52	friend class handle_operator;
53	};
54
55	template < typename HANDLE >
56	class handle_operator
57	{
58	public:
59	typedef typename HANDLE::value_type value_type;
60
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	};
68
69
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	{
82	typedef handle_operator<HANDLE> hop;
83	value_type i = get_free_entry();
84	m_entries[i].index = index;
85	m_entries[i].counter++;
86	return hop::create( i, m_entries[i].counter );
87	}
88
89	void free_handle( handle h )
90	{
91	m_entries[ h.index() ].index = -1;
92	m_entries[ h.index() ].next_free = -1;
93	if ( m_last_free == -1 )
94	{
95	m_first_free = m_last_free = h.index();
96	return;
97	}
98	m_entries[ (unsigned)m_last_free ].next_free = h.index();
99	m_last_free = h.index();
100	}
101
102	void swap_indices( handle h1, handle h2 )
103	{
104	std::swap( m_entries[ h1.index() ].index, m_entries[ h2.index() ].index );
105	}
106
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
116	sint32 get_index( handle h ) const
117	{
118	typedef handle_operator<HANDLE> hop;
119	return m_entries[ h.index() ].counter == hop::get_counter(h) ? m_entries[ h.index() ].index : -1;
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
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;
162
163	packed_indexed_array() {}
164	packed_indexed_array( uint32 reserve )
165	{
166	m_data.reserve( reserve );
167	m_indexes.reserve( reserve );
168	}
169
170	T* insert( handle h )
171	{
172	resize_indexes_to( (index_type) h.index() );
173	m_indexes[ h.index() ] = (index_type) m_data.size();
174	m_handles.push_back( h );
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() ];
189	return i >= 0 ? &(m_data[ (unsigned)i ]) : nullptr;
190	}
191
192	void remove( handle h )
193	{
194	if ( h.is_nil() \|\| h.index() >= m_indexes.size() \|\| m_indexes[h.index()] == -1 )
195	return;
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	{
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;
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;
236	m_indexes.resize( (size_t)size, -1 );
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
246	template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
247	class entity_store
248	{
249	public:
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;
258
259	entity_store() {}
260
261	explicit entity_store( uint32 reserve )
262	{
263	m_handles.reserve( reserve );
264	m_data.reserve( reserve );
265	}
266
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
274	bool is_valid( handle h )
275	{
276	return m_indexes.is_valid(h);
277	}
278
279	const value_type* get( handle h ) const
280	{
281	if ( h.is_nil() ) return nullptr;
282	sint32 eindex = m_indexes.get_index( h );
283	return eindex >= 0 ? &(m_data[ (unsigned)eindex ]) : nullptr;
284	}
285
286	value_type* get( handle h )
287	{
288	if ( h.is_nil() ) return nullptr;
289	sint32 eindex = m_indexes.get_index( h );
290	return eindex >= 0 ? &(m_data[ (unsigned)eindex ]) : nullptr;
291	}
292
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	{
299	m_data[ (unsigned)dead_eindex ] = m_data.back();
300	m_handles[ (unsigned)dead_eindex ] = m_handles.back();
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	}
307
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]; }
311	size_t size() const { return m_data.size(); }
312
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
321	private:
322	std::vector< handle > m_handles;
323	storage m_data;
324	index_store< handle, TINDEX > m_indexes;
325	};
326
327	}
328
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	};
344	}
345
346	#endif // NV_CORE_HANDLE_HH

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

Download in other formats: