Skip to content

Commit 32fe91e

Browse files
committed
progress
1 parent 20f0149 commit 32fe91e

11 files changed

Lines changed: 71 additions & 1179 deletions

File tree

‎include/react/Group.h‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -65,9 +65,9 @@ class TransactionStatus
6565

6666
public:
6767
// Default ctor
68-
inline TransactionStatus() :
68+
TransactionStatus() :
6969
statePtr_( StateT::Create() )
70-
{}
70+
{ }
7171

7272
// Move ctor
7373
TransactionStatus(TransactionStatus&& other) :
@@ -91,7 +91,7 @@ class TransactionStatus
9191
TransactionStatus(const TransactionStatus&) = delete;
9292
TransactionStatus& operator=(const TransactionStatus&) = delete;
9393

94-
inline void Wait()
94+
void Wait()
9595
{
9696
assert(statePtr_.Get() != nullptr);
9797
statePtr_->Wait();

‎include/react/common/Containers.h‎

Lines changed: 65 additions & 202 deletions
Original file line numberDiff line numberDiff line change
@@ -14,59 +14,41 @@
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
///////////////////////////////////////////////////////////////////////////////////////////////////
4825
template <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+
5433
public:
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-
137125
private:
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

Comments
 (0)