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

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