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

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