Context Navigation

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

Last change on this file since 319 was 319, checked in by epyon, 11 years ago
created core module and moved all free source files there took the opportunity to update all copyright lines and minor cleanup minor fixes not all examples are up to date
File size: 8.4 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	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
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);}
40
41	bool is_nil() const { return m_index == 0 && m_counter == 0; }
42	bool is_valid() const { return !is_nil(); }
43	T index() const { return m_index; }
44	size_t hash() const { return std::hash<T>()( m_counter << IBITS \| m_index ); }
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
54
55
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	}
83	m_entries[ m_last_free ].next_free = h.m_index;
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
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;
137
138	packed_indexed_array() {}
139	packed_indexed_array( uint32 reserve )
140	{
141	m_data.reserve( reserve );
142	m_indexes.reserve( reserve );
143	}
144
145	T* insert( handle h )
146	{
147	resize_indexes_to( h.index() );
148	m_indexes[ h.index() ] = m_data.size();
149	m_handles.push_back( h );
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() ];
164	return i >= 0 ? &(m_data[ i ]) : nullptr;
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	{
173	m_data[ dead_eindex ] = m_data.back();
174	m_handles[ dead_eindex ] = swap_handle;
175	m_indexes[ swap_handle.index() ] = dead_eindex;
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;
209	m_indexes.resize( size, -1 );
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
219	template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
220	class entity_store
221	{
222	public:
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;
231
232	entity_store() {}
233
234	explicit entity_store( uint32 reserve )
235	{
236	m_handles.reserve( reserve );
237	m_data.reserve( reserve );
238	}
239
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	}
246
247	const value_type* get( handle h ) const
248	{
249	if ( h.is_nil() ) return nullptr;
250	sint32 eindex = m_indexes.get_index( h );
251	return eindex >= 0 ? &(m_data[ eindex ]) : nullptr;
252	}
253
254	value_type* get( handle h )
255	{
256	if ( h.is_nil() ) return nullptr;
257	sint32 eindex = m_indexes.get_index( h );
258	return eindex >= 0 ? &(m_data[ eindex ]) : nullptr;
259	}
260
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	{
267	m_data[ dead_eindex ] = m_data.back();
268	m_handles[ dead_eindex ] = m_handles.back();
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	}
275
276	handle get_handle( index_type i ) const { return m_handles[i]; }
277	const value_type& operator[] ( index_type i ) const { return m_data[i]; }
278	value_type& operator[] ( index_type i ) { return m_data[i]; }
279	size_t size() const { return m_data.size(); }
280
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
289	private:
290	std::vector< handle > m_handles;
291	storage m_data;
292	index_store< handle, TINDEX > m_indexes;
293	};
294
295	}
296
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	};
312	}
313
314	#endif // NV_CORE_HANDLE_HH

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

Download in other formats: