1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
// Copyright 2025 Steven Le Rouzic
//
// SPDX-License-Identifier: BSD-3-Clause
#include "asl/base/integers.hpp"
#include "asl/base/meta.hpp"
#include "asl/containers/chunked_buffer.hpp"
#include "asl/memory/allocator.hpp"
namespace asl
{
// @Todo Uniquely represented for the handle?
// @Todo niche for handles
template<
int kIndexBits_,
int kGenBits_,
typename UserType_ = empty,
int kUserBits_ = 0
>
requires (kIndexBits_ > 0 && kGenBits_ > 0 && kUserBits_ >= 0)
struct index_pool_config
{
static constexpr bool kHasUser = !same_as<UserType_, empty>;
using UserType = UserType_;
using PrimitiveUserType = smallest_unsigned_integer_type_for_width<size_of<UserType> * 8>;
static_assert(trivially_copy_constructible<UserType>);
static_assert(trivially_destructible<UserType>);
static_assert(size_of<UserType> == size_of<PrimitiveUserType>, "UserType should be of size 1, 2 or 4");
static constexpr int kUserBits = []() static -> int {
if constexpr (!kHasUser) { return 0; };
return kUserBits_ == 0 ? size_of<UserType> * 8 : kUserBits_;
}();
static_assert(kUserBits <= size_of<UserType> * 8);
static constexpr int kIndexBits = kIndexBits_;
static constexpr int kGenBits = kGenBits_;
static_assert(kIndexBits + kGenBits + kUserBits <= 63);
using HandleType = smallest_unsigned_integer_type_for_width<kIndexBits + kGenBits + kUserBits + 1>;
static constexpr int kGenShift = kIndexBits;
static constexpr int kUserShift = kIndexBits + kGenBits;
static constexpr HandleType kValidMask = HandleType{1} << (size_of<HandleType> * 8 - 1);
static constexpr HandleType kIndexMask = (HandleType{1} << kIndexBits) - 1;
static constexpr HandleType kGenMask = ((HandleType{1} << kGenBits) - 1) << kGenShift;
static constexpr HandleType kUserMask = ((HandleType{1} << kUserBits) - 1) << kUserShift;
};
template<
int kIndexBits_,
int kGenBits_,
typename UserType_ = empty,
int kUserBits_ = 0
>
class index_pool_handle
{
public:
using config = index_pool_config<kIndexBits_, kGenBits_, UserType_, kUserBits_>;
private:
config::HandleType m_handle{};
public:
constexpr index_pool_handle() = default;
constexpr index_pool_handle(uint64_t index, uint64_t gen)
requires (!config::kHasUser)
: m_handle{static_cast<config::HandleType>(
config::kValidMask |
(index & config::kIndexMask) |
((gen << config::kGenShift) & config::kGenMask))}
{
ASL_ASSERT((index & uint64_t{config::kIndexMask}) == index);
ASL_ASSERT((gen & (uint64_t{config::kGenMask} >> config::kGenShift)) == gen);
}
constexpr index_pool_handle(uint64_t index, uint64_t gen, config::UserType user)
requires config::kHasUser
: m_handle{static_cast<config::HandleType>(
config::kValidMask |
(index & config::kIndexMask) |
((gen << config::kGenShift) & config::kGenMask) |
((static_cast<config::HandleType>(bit_cast<typename config::PrimitiveUserType>(user)) << config::kUserShift) & config::kUserMask))}
{
ASL_ASSERT((index & uint64_t{config::kIndexMask}) == index);
ASL_ASSERT((gen & (uint64_t{config::kGenMask} >> config::kGenShift)) == gen);
ASL_ASSERT((bit_cast<typename config::PrimitiveUserType>(user) & (uint64_t{config::kUserMask} >> config::kUserShift)) == bit_cast<typename config::PrimitiveUserType>(user));
}
constexpr bool is_valid(this index_pool_handle self)
{
return self.m_handle & config::kValidMask;
}
constexpr uint64_t index(this index_pool_handle self)
{
return self.m_handle & config::kIndexMask;
}
constexpr uint64_t gen(this index_pool_handle self)
{
return (self.m_handle & config::kGenMask) >> config::kGenShift;
}
constexpr config::UserType user(this index_pool_handle self)
{
return bit_cast<typename config::UserType>(static_cast<config::PrimitiveUserType>(
((self.m_handle & config::kUserMask) >> config::kUserShift)));
}
constexpr bool operator==(this index_pool_handle self, index_pool_handle other) = default;
};
template<
int kIndexBits_,
int kGenBits_,
typename UserType_ = empty,
int kUserBits_ = 0,
typename Payload = empty,
allocator Allocator = DefaultAllocator
>
class IndexPool
{
public:
using handle = index_pool_handle<kIndexBits_, kGenBits_, UserType_, kUserBits_>;
private:
using config = handle::config;
static constexpr bool kHasPayload = !same_as<Payload, empty>;
// @Todo Remove need for default constructible & trivially destructible for payload
// Use union in slot to store the variants
// @Todo Use dummy user type with inactive handle type -> no need to set user data when allocating handle
static_assert(default_constructible<Payload>);
static_assert(copy_constructible<Payload>);
static_assert(trivially_destructible<Payload>);
struct Slot
{
bool is_end_of_list : 1;
bool is_active : 1;
handle handle;
ASL_NO_UNIQUE_ADDRESS Payload payload;
};
chunked_buffer<Slot, 256, Allocator> m_slots;
// We only use the index, this is essentially the head of the linked
// list to the first available slot.
// Then the index of each slot points to the next available one.
handle m_first_available;
static constexpr handle make_handle(uint64_t index, uint64_t gen, [[maybe_unused]] config::UserType user_data)
{
if constexpr (config::kHasUser)
{
return handle(index, gen, user_data);
}
else
{
return handle(index, gen);
}
};
void allocate_new_slot(config::UserType user)
{
// @Todo Check that we don't go past capacity.
const auto new_index = static_cast<uint64_t>(m_slots.size());
const handle new_handle = make_handle(new_index, 0, user);
m_slots.push(Slot{
.is_end_of_list = true,
.is_active = false,
.handle = new_handle,
.payload = Payload{}
});
m_first_available = new_handle;
}
handle acquire_handle(const Payload& payload, config::UserType user)
{
if (!m_first_available.is_valid())
{
allocate_new_slot(user);
}
ASL_ASSERT(m_first_available.is_valid());
auto index = static_cast<isize_t>(m_first_available.index());
Slot& slot = m_slots[index];
ASL_ASSERT(!slot.is_active);
m_first_available = slot.is_end_of_line ? handle{} : slot.handle;
slot.is_active = true;
slot.payload = payload;
return make_handle(index, slot.handle.gen(), user);
}
public:
IndexPool() requires default_constructible<Allocator> = default;
explicit IndexPool(Allocator allocator) : m_slots{std::move(allocator)} {}
handle acquire(const Payload& payload)
{
return acquire_handle(payload);
}
};
} // namespace asl
|
