1414#include < algorithm>
1515#include < array>
1616#include < iterator>
17+ #include < memory>
1718#include < type_traits>
18- #include < vector>
1919
2020/* **************************************/ REACT_IMPL_BEGIN /* *************************************/
2121
22- // /////////////////////////////////////////////////////////////////////////////////////////////////
23- // / EnumFlags
24- // /////////////////////////////////////////////////////////////////////////////////////////////////
25- template <typename T>
26- class EnumFlags
27- {
28- public:
29- using FlagsT = typename std::underlying_type<T>::type;
30-
31- template <T x>
32- void Set () { flags_ |= 1 << x; }
33-
34- template <T x>
35- void Clear () { flags_ &= ~(1 << x); }
36-
37- template <T x>
38- bool Test () const { return (flags_ & (1 << x)) != 0 ; }
39-
40- private:
41- FlagsT flags_ = 0 ;
42- };
43-
44-
4522// /////////////////////////////////////////////////////////////////////////////////////////////////
4623// / IndexMap
4724// /////////////////////////////////////////////////////////////////////////////////////////////////
4825template <typename T>
49- class IndexMap
26+ class IndexedStorage
5027{
5128 static const size_t initial_capacity = 8 ;
5229 static const size_t grow_factor = 2 ;
5330
31+ using StorageType = typename std::aligned_storage<sizeof (T), alignof (T)>::type;
32+
5433public:
5534 using ValueType = T;
5635
57- IndexMap () = default ;
36+ IndexedStorage () = default ;
5837
59- IndexMap ( const IndexMap &) = default ;
60- IndexMap & operator =(const IndexMap &) = default ;
38+ IndexedStorage (IndexedStorage& &) = default ;
39+ IndexedStorage & operator =(IndexedStorage& &) = default ;
6140
62- IndexMap (IndexMap&&) = default ;
63- IndexMap& operator =(IndexMap&&) = default ;
41+ IndexedStorage (const IndexedStorage&) = delete ;
42+ IndexedStorage& operator =(const IndexedStorage&) = delete ;
43+
44+ ~IndexedStorage ()
45+ { Reset (); }
6446
6547 T& operator [](size_t index)
66- { return data_[index]; }
48+ { return reinterpret_cast <T&>( data_[index]) ; }
6749
6850 const T& operator [](size_t index) const
69- { return data_[index]; }
51+ { return reinterpret_cast <T&>( data_[index]) ; }
7052
7153 size_t Insert (T value)
7254 {
@@ -85,61 +67,73 @@ class IndexMap
8567 }
8668 }
8769
88- void Remove (size_t index)
70+ void Erase (size_t index)
8971 {
90- for (size_t index : freeIndices_)
91- data_[index].~T ();
72+ // If we erased something other than the last element, save in free index list.
73+ if (index != (size_ - 1 ))
74+ {
75+ freeIndices_[freeSize_++] = index;
76+ }
77+
78+ reinterpret_cast <T&>(data_[index]).~T ();
9279 --size_;
93- freeIndices_.push_back (index);
9480 }
9581
9682 void Clear ()
9783 {
98- // Sort free indexes so we can remove check for them in linear time
99- std::sort (freeIndices_. begin (), freeIndices_. end () );
84+ // Sort free indexes so we can remove check for them in linear time.
85+ std::sort (& freeIndices_[ 0 ], & freeIndices_[freeSize_] );
10086
101- const size_t totalSize = size_ + freeIndices_. size () ;
102- size_t i = 0 ;
87+ const size_t totalSize = size_ + freeSize_ ;
88+ size_t index = 0 ;
10389
104- // Skip over free indices
105- for (auto freeIndex : freeIndices_ )
90+ // Skip over free indices.
91+ for (size_t j = 0 ; j < freeSize_; ++j )
10692 {
107- for (; i < totalSize; ++i )
93+ for (; index < totalSize; ++index )
10894 {
109- if (i == freeIndex)
95+ if (j == freeIndex_)
96+ {
97+ ++index;
11098 break ;
99+ }
111100 else
112- data_[i].~T ();
101+ {
102+ data_[index].~T ();
103+ }
113104 }
114105 }
115106
116107 // Rest
117- for (; i < totalSize; ++i )
118- data_[i ].~T ();
108+ for (; index < totalSize; ++index )
109+ data_[index ].~T ();
119110
120111 size_ = 0 ;
121- freeIndices_. clear () ;
112+ freeList_ = 0 ;
122113 }
123114
124115 void Reset ()
125116 {
126117 Clear ();
127118
128- capacity_ = 0 ;
129- delete[] data_ ;
119+ data_. reset () ;
120+ freeIndices_. reset () ;
130121
131- freeIndices_. shrink_to_fit () ;
122+ capacity_ = 0 ;
132123 }
133124
134- ~IndexMap ()
135- { Reset (); }
136-
137125private:
126+ T& GetDataAt (size_t index)
127+ { return reinterpret_cast <T&>(data_[index]); }
128+
129+ T& GetDataAt (size_t index) const
130+ { return reinterpret_cast <T&>(data_[index]); }
131+
138132 bool IsAtFullCapacity () const
139133 { return capacity_ == size_; }
140134
141135 bool HasFreeIndices () const
142- { return !freeIndices_. empty () ; }
136+ { return freeSize_ > 0 ; }
143137
144138 size_t CalcNextCapacity () const
145139 { return capacity_ == 0 ? initial_capacity : capacity_ * grow_factor; }
@@ -148,20 +142,23 @@ class IndexMap
148142 {
149143 // Allocate new storage
150144 size_t newCapacity = CalcNextCapacity ();
151- T* newData = new T[newCapacity];
145+
146+ std::unique_ptr<StorageType[]> newData{ new StorageType[newCapacity] };
147+ std::unique_ptr<size_t []> newFreeList{ new size_t [newCapacity] };
152148
153149 // Move data to new storage
154- for (size_t i = 0 ; i < size_ ; ++i)
150+ for (size_t i = 0 ; i < capacity_ ; ++i)
155151 {
156- new (&newData[i]) T ( std::move (data_[i]));
157- data_[i].~T ();
152+ new (reinterpret_cast <T*>( &newData[i])) T{ std::move (reinterpret_cast <T&>( data_[i])) } ;
153+ reinterpret_cast <T&>( data_[i]) .~T ();
158154 }
159-
160- delete[] data_;
155+
156+ // Free list is empty if we are at max capacity anyway
161157
162158 // Use new storage
163- data_ = newData;
164- capacity_ = newCapacity;
159+ data_ = std::move (newData);
160+ freeIndices_ = std::move (newFreeList);
161+ capacity_ = newCapacity;
165162 }
166163
167164 size_t InsertAtBack (T&& value)
@@ -172,153 +169,19 @@ class IndexMap
172169
173170 size_t InsertAtFreeIndex (T&& value)
174171 {
175- size_t nextFreeIndex = freeIndices_.back ();
176- freeIndices_.pop_back ();
177-
172+ size_t nextFreeIndex = freeIndices_[--freeSize_];
178173 new (&data_[nextFreeIndex]) T (std::move (value));
179174 ++size_;
180175
181176 return nextFreeIndex;
182177 }
183178
184- T* data_ = nullptr ;
179+ std::unique_ptr<StorageType[]> data_;
180+ std::unique_ptr<size_t []> freeIndices_;
181+
185182 size_t size_ = 0 ;
183+ size_t freeSize_ = 0 ;
186184 size_t capacity_ = 0 ;
187-
188- std::vector<size_t > freeIndices_;
189- };
190-
191- // /////////////////////////////////////////////////////////////////////////////////////////////////
192- // / NodeVector
193- // /////////////////////////////////////////////////////////////////////////////////////////////////
194- template <typename TNode>
195- class NodeVector
196- {
197- private:
198- typedef std::vector<TNode*> DataT;
199-
200- public:
201- void Add (TNode& node)
202- {
203- data_.push_back (&node);
204- }
205-
206- void Remove (const TNode& node)
207- {
208- data_.erase (std::find (data_.begin (), data_.end (), &node));
209- }
210-
211- typedef typename DataT::iterator iterator;
212- typedef typename DataT::const_iterator const_iterator;
213-
214- iterator begin () { return data_.begin (); }
215- iterator end () { return data_.end (); }
216-
217- const_iterator begin () const { return data_.begin (); }
218- const_iterator end () const { return data_.end (); }
219-
220- private:
221- DataT data_;
222- };
223-
224- // /////////////////////////////////////////////////////////////////////////////////////////////////
225- // / NodeBuffer
226- // /////////////////////////////////////////////////////////////////////////////////////////////////
227- struct SplitTag {};
228-
229- template <typename T, size_t N>
230- class NodeBuffer
231- {
232- public:
233- using DataT = std::array<T*,N>;
234- using iterator = typename DataT::iterator;
235- using const_iterator = typename DataT::const_iterator;
236-
237- static const size_t split_size = N / 2 ;
238-
239- NodeBuffer () :
240- size_ ( 0 ),
241- front_ ( nodes_.begin() ),
242- back_ ( nodes_.begin() )
243- {}
244-
245- NodeBuffer (T* node) :
246- size_ ( 1 ),
247- front_ ( nodes_.begin() ),
248- back_ ( nodes_.begin() + 1 )
249- {
250- nodes_[0 ] = node;
251- }
252-
253- template <typename TInput>
254- NodeBuffer (TInput srcBegin, TInput srcEnd) :
255- size_ ( std::distance(srcBegin, srcEnd) ), // parentheses to allow narrowing conversion
256- front_ ( nodes_.begin() ),
257- back_ ( size_ != N ? nodes_.begin() + size_ : nodes_.begin() )
258- {
259- std::copy (srcBegin, srcEnd, front_);
260- }
261-
262- // Other must be full
263- NodeBuffer (NodeBuffer& other, SplitTag) :
264- size_ ( split_size ),
265- front_ ( nodes_.begin() ),
266- back_ ( nodes_.begin() )
267- {
268- for (auto i=0 ; i<split_size; i++)
269- *(back_++) = other.PopFront ();
270- }
271-
272- void PushFront (T* e)
273- {
274- size_++;
275- decrement (front_);
276- *front_ = e;
277- }
278-
279- void PushBack (T* e)
280- {
281- size_++;
282- *back_ = e;
283- increment (back_);
284- }
285-
286- T* PopFront ()
287- {
288- size_--;
289- auto t = *front_;
290- increment (front_);
291- return t;
292- }
293-
294- T* PopBack ()
295- {
296- size_--;
297- decrement (back_);
298- return *back_;
299- }
300-
301- bool IsFull () const { return size_ == N; }
302- bool IsEmpty () const { return size_ == 0 ; }
303-
304- private:
305- inline void increment (iterator& it)
306- {
307- if (++it == nodes_.end ())
308- it = nodes_.begin ();
309- }
310-
311- inline void decrement (iterator& it)
312- {
313- if (it == nodes_.begin ())
314- it = nodes_.end ();
315- --it;
316- }
317-
318- DataT nodes_;
319- size_t size_;
320- iterator front_;
321- iterator back_;
322185};
323186
324187/* ***************************************/ REACT_IMPL_END /* **************************************/
0 commit comments