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

Last change on this file since 364 was 364, checked in by epyon, 10 years ago
  • fixed compilation on clang
  • cleared all clang warnings (except fix_me's)
File size: 9.1 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
18namespace 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        template < typename HANDLE, typename INDEX = sint32 >
70        class handle_manager
71        {
72                typedef INDEX index_type;
73                static const index_type NONE = index_type(-1);
74                static const index_type USED = index_type(-2);
75        public:
76
77                typedef HANDLE handle;
78                typedef typename HANDLE::value_type value_type;
79
80                handle_manager() : m_first_free( NONE ), m_last_free( NONE ) {}
81
82                handle create_handle()
83                {
84                        typedef handle_operator<HANDLE> hop;
85                        value_type i = get_free_entry();
86                        m_entries[i].counter++;
87                        NV_ASSERT( m_entries[i].counter != 0, "Out of handles!" );
88                        m_entries[i].next_free = USED;
89                        return hop::create( i, m_entries[i].counter );
90                }
91
92                void free_handle( handle h )
93                {
94                        value_type index = h.index();
95                        typedef handle_operator<HANDLE> hop;
96                        NV_ASSERT( m_entries[index].next_free == USED, "Unused handle freed!" );
97                        NV_ASSERT( m_entries[index].counter == hop::get_counter( h ), "Handle corruption!" );
98                        m_entries[index].next_free = NONE;
99                        if ( m_last_free == NONE )
100                        {
101                                m_first_free = m_last_free = (index_type)index;
102                                return;
103                        }
104                        m_entries[(value_type)m_last_free].next_free = (index_type)index;
105                        m_last_free = (index_type)index;
106                }
107
108                bool is_valid( handle h ) const
109                {
110                        typedef handle_operator<HANDLE> hop;
111                        if ( h.is_nil() ) return false;
112                        if ( h.index() >= m_entries.size() ) return false;
113                        const index_entry& entry = m_entries[h.index()];
114                        return entry.next_free == USED && entry.counter == hop::get_counter( h );
115                }
116
117        private:
118                struct index_entry
119                {
120                        value_type counter;
121                        index_type next_free;
122
123                        index_entry() : counter( 0 ), next_free( NONE ) {}
124                };
125
126                value_type get_free_entry()
127                {
128                        if ( m_first_free != NONE )
129                        {
130                                value_type result = (value_type)m_first_free;
131                                m_first_free = m_entries[result].next_free;
132                                m_entries[result].next_free = USED;
133                                if ( m_first_free == NONE ) m_last_free = NONE;
134                                return result;
135                        }
136                        m_entries.emplace_back();
137                        return value_type( m_entries.size() - 1 );
138                }
139
140                index_type m_first_free;
141                index_type m_last_free;
142                std::vector< index_entry > m_entries;
143        };
144
145        template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
146        class packed_indexed_array
147        {
148        public:
149                typedef HANDLE                   handle;
150                typedef TINDEX                   index_type;
151                typedef std::vector< T >         storage;
152                typedef T                        value_type;
153                typedef typename storage::iterator        iterator;
154                typedef typename storage::const_iterator  const_iterator;
155                typedef typename storage::reference       reference;
156                typedef typename storage::const_reference const_reference;
157
158                packed_indexed_array() {}
159                packed_indexed_array( uint32 reserve )
160                {
161                        m_data.reserve( reserve );
162                        m_indexes.reserve( reserve );
163                }
164
165                T* insert( handle h )
166                {
167                        resize_indexes_to( (index_type) h.index() );
168                        m_indexes[ h.index() ] = (index_type) m_data.size();
169                        m_handles.push_back( h );
170                        m_data.emplace_back();
171                        return &(m_data.back());
172                }
173
174                bool exists( handle h )
175                {
176                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return false;
177                        return m_indexes[ h.index() ] >= 0;             
178                }
179
180                T* get( handle h )
181                {
182                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return nullptr;
183                        index_type i = m_indexes[ h.index() ];
184                        return i >= 0 ? &(m_data[ (unsigned)i ]) : nullptr;
185                }
186
187                const T* get( handle h ) const
188                {
189                        if ( h.is_nil() || h.index() >= m_indexes.size() ) return nullptr;
190                        index_type i = m_indexes[h.index()];
191                        return i >= 0 ? &( m_data[(unsigned)i] ) : nullptr;
192                }
193
194                void remove( handle h )
195                {
196                        if ( h.is_nil() || h.index() >= m_indexes.size() || m_indexes[h.index()] == -1 )
197                                return;
198                        handle swap_handle    = m_handles.back();
199                        sint32 dead_eindex    = m_indexes[ h.index() ];
200                        if ( dead_eindex != (sint32)m_data.size()-1 )
201                        {
202                                m_data[ (unsigned)dead_eindex ]    = m_data.back();
203                                m_handles[ (unsigned)dead_eindex ] = swap_handle;
204                                m_indexes[ swap_handle.index() ]   = dead_eindex;
205                        }
206                        m_data.pop_back();
207                        m_handles.pop_back();
208                        m_indexes[ h.index() ] = -1;
209                }
210
211                void clear()
212                {
213                        m_data.clear();
214                        m_handles.clear();
215                        m_indexes.clear();
216                }
217
218                handle get_handle( index_type i ) const { return m_handles[(unsigned)i]; }
219
220                const value_type& operator[] ( index_type i ) const { return m_data[i]; }
221                value_type& operator[] ( index_type i ) { return m_data[i]; }
222                size_t size() const { return m_data.size(); }
223
224                iterator        begin()        { return m_data.begin(); }
225                const_iterator  begin()  const { return m_data.cbegin(); }
226                const_iterator  cbegin() const { return m_data.cbegin(); }
227
228                iterator        end()        { return m_data.end(); }
229                const_iterator  end()  const { return m_data.cend(); }
230                const_iterator  cend() const { return m_data.cend(); }
231
232        private:
233                void resize_indexes_to( index_type i )
234                {
235                        index_type size = (index_type)m_indexes.size();
236                        if ( i >= size )
237                        {
238                                if ( size == 0 ) size = 1;
239                                while ( i >= size ) size = size * 2;
240                                m_indexes.resize( (size_t)size, -1 );
241                        }
242                }
243
244                std::vector< T >          m_data;
245                std::vector< handle >     m_handles;
246                std::vector< index_type > m_indexes;
247        };
248
249
250        template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
251        class handle_store
252        {
253        public:
254                typedef HANDLE                   handle;
255                typedef TINDEX                   index_type;
256                typedef std::vector< T >         storage;
257                typedef T                        value_type;
258                typedef typename storage::iterator        iterator;
259                typedef typename storage::const_iterator  const_iterator;
260                typedef typename storage::reference       reference;
261                typedef typename storage::const_reference const_reference;
262
263                handle_store() {}
264
265                explicit handle_store( uint32 reserve )
266                {
267                        m_data.reserve( reserve );
268                }
269
270                handle create()
271                {
272                        handle h = m_indexes.create_handle();
273                        m_data.insert( h );
274                        return h;
275                }
276
277                bool is_valid( handle h )
278                {
279                        return m_indexes.is_valid( h );
280                }
281
282                const value_type* get( handle h ) const
283                {
284                        return m_data.get( h );
285                }
286
287                value_type* get( handle h )
288                {
289                        return m_data.get( h );
290                }
291
292                void destroy( handle e )
293                {
294                        m_data.remove( e );
295                        m_indexes.free_handle( e );
296                }
297
298                handle get_handle( index_type i ) const { return m_data.get_handle(i); }
299                const value_type& operator[] ( index_type i ) const { return m_data[(unsigned)i]; }
300                value_type& operator[] ( index_type i ) { return m_data[(unsigned)i]; }
301                size_t size() const { return m_data.size(); }
302
303                iterator        begin() { return m_data.begin(); }
304                const_iterator  begin()  const { return m_data.cbegin(); }
305                const_iterator  cbegin() const { return m_data.cbegin(); }
306
307                iterator        end() { return m_data.end(); }
308                const_iterator  end()  const { return m_data.cend(); }
309                const_iterator  cend() const { return m_data.cend(); }
310
311        private:
312                packed_indexed_array< T, handle, TINDEX > m_data;
313                handle_manager< handle >                  m_indexes;
314        };
315       
316}
317
318namespace std
319{
320        template <
321                typename T,
322                unsigned IBITS,
323                unsigned CBITS,
324                typename TAG
325        >
326        struct hash<nv::handle<T,IBITS,CBITS,TAG>>
327        {
328                size_t operator()(const nv::handle<T,IBITS,CBITS,TAG>& h) const
329                {
330                        return h.hash();
331                }
332        };
333}
334
335#endif // NV_CORE_HANDLE_HH
Note: See TracBrowser for help on using the repository browser.