SparseSet.ixx File

Generic sparse set data structure for efficient entity-keyed storage. More...

Included Headers

#include <cassert> #include <functional> #include <vector> #include <cstddef> #include <helios.ecs.types.TypeDefs> #include <helios.ecs.types.EntityHandle>

Namespaces Index

namespace	helios
namespace	ecs

Classes Index

class	SparseSetBase
	Abstract base class for type-erased sparse set access. More...
class	SparseSet<T>
	A generic sparse set providing O(1) insertion, lookup, and removal. More...
struct	Iterator
	Forward iterator for traversing the sparse set. More...
struct	ConstIterator
	Const forward iterator for traversing the sparse set. More...

Description

Generic sparse set data structure for efficient entity-keyed storage.

File Listing

The file content with the documentation metadata removed is:

1

5module;

6

7#include <cassert>

8#include <functional>

9#include <vector>

10#include <cstddef>

11

12export module helios.ecs.SparseSet;

13

14import helios.ecs.types.EntityHandle;

15import helios.ecs.types.TypeDefs;

16

17

18using namespace helios::ecs::types;

19export namespace helios::ecs {

20

31 class SparseSetBase {

32

33 public:

34

38 virtual ~SparseSetBase() = default;

39

48 virtual bool remove(EntityId id) = 0;

49

57 [[nodiscard]] virtual bool contains(EntityId id) const = 0;

58

66 [[nodiscard]] virtual void* raw(EntityId id) = 0;

67 };

68

69

75 constexpr auto Tombstone = EntityTombstone;

76

77

117 template <typename T>

118 class SparseSet : public SparseSetBase {

119

120

126 std::vector<size_t> sparse_;

127

133 std::vector<EntityId> denseToSparse_;

134

138 std::vector<T> storage_;

139

140 public:

141

145 SparseSet() = default;

146

152 explicit SparseSet(const size_t capacity) {

153 sparse_.reserve(capacity);

154 storage_.reserve(capacity);

155 denseToSparse_.reserve(capacity);

156 };

157

158

162 SparseSet(const SparseSet&) = delete;

163

167 SparseSet& operator=(const SparseSet&) = delete;

168

172 SparseSet(SparseSet&&) noexcept = default;

173

177 SparseSet& operator=(SparseSet&&) noexcept = default;

178

179

192 template <typename... Args>

193 [[nodiscard]] T* emplace(const EntityId idx, Args&& ...args) {

194

195 // already in use

196 if (idx < sparse_.size() && sparse_[idx] != Tombstone) {

197 return nullptr;

198 }

199

200 if (idx >= sparse_.size()) {

201 sparse_.resize(idx + 1, Tombstone);

202 }

203

204 const auto denseIndex = storage_.size();

205

206 denseToSparse_.push_back(idx);

207 storage_.emplace_back(std::forward<Args>(args)...);

208

209 sparse_[idx] = denseIndex;

210

211 return &storage_.back();

212 }

213

225 [[nodiscard]] T* insert(const EntityId idx, T&& obj) {

226

227 // already in use

228 if (idx < sparse_.size() && sparse_[idx] != Tombstone) {

229 return nullptr;

230 }

231

232 if (idx >= sparse_.size()) {

233 sparse_.resize(idx + 1, Tombstone);

234 }

235

236 const auto denseIndex = storage_.size();

237

238 denseToSparse_.push_back(idx);

239 storage_.emplace_back(std::move(obj));

240

241 sparse_[idx] = denseIndex;

242

243 return &storage_.back();

244 }

245

259 [[nodiscard]] bool remove(const EntityId idx) override {

260

261 if (idx >= sparse_.size() || sparse_[idx] == Tombstone) {

262 return false;

263 }

264

265 const auto denseIndex = sparse_[idx];

266 const auto sparseIdx = denseToSparse_[denseIndex];

267

268 assert(sparseIdx == idx && "Sparse index mismatch");

269

270 if (denseIndex != storage_.size() - 1) {

271 storage_[denseIndex] = std::move(storage_.back());

272 const auto newSparseIndex = denseToSparse_.back();

273 sparse_[newSparseIndex] = denseIndex;

274 denseToSparse_[denseIndex] = newSparseIndex;

275 }

276

277 storage_.pop_back();

278 denseToSparse_.pop_back();

279

280 sparse_[idx] = Tombstone;

281

282 return true;

283 }

284

292 [[nodiscard]] T* get(const EntityId idx) {

293

294 if (idx >= sparse_.size() || sparse_[idx] == Tombstone) {

295 return nullptr;

296 }

297

298 return &storage_[sparse_[idx]];

299 }

300

308 [[nodiscard]] const T* get(const EntityId idx) const {

309

310 if (idx >= sparse_.size() || sparse_[idx] == Tombstone) {

311 return nullptr;

312 }

313

314 return &storage_[sparse_[idx]];

315 }

316

317

325 [[nodiscard]] bool contains(const EntityId idx) const override {

326 return idx < sparse_.size() && sparse_[idx] != Tombstone;

327 }

328

332 [[nodiscard]] void* raw(const EntityId id) override {

333 T* ptr = get(id);

334 return static_cast<void*>(ptr);

335 }

336

337

344 struct Iterator {

345 using DataIt = typename std::vector<T>::iterator;

346 using IdIt = typename std::vector<EntityId>::iterator;

347

351 DataIt dataIt_;

352

356 IdIt idIt_;

357

358 using iterator_category = std::forward_iterator_tag;

359 using value_type = T;

360 using difference_type = std::ptrdiff_t;

361 using pointer = T*;

362 using reference = T&;

363

364 Iterator() = default;

365

366 Iterator(DataIt dataIt, IdIt idIt) : dataIt_(dataIt), idIt_(idIt) {}

367

368 reference operator*() const { return *dataIt_; }

369 pointer operator->() const { return &*dataIt_; }

370

376 [[nodiscard]] EntityId entityId() const { return *idIt_; }

377

378 [[nodiscard]] bool operator==(const Iterator& other) const { return dataIt_ == other.dataIt_;}

379 [[nodiscard]] bool operator!=(const Iterator& other) const { return dataIt_ != other.dataIt_;}

380

381 Iterator operator++(int) {

382 Iterator tmp = *this;

383 ++(*this);

384 return tmp;

385 }

386

387 Iterator& operator++() {

388 ++dataIt_; ++idIt_; return *this;

389 }

390 };

391

397 struct ConstIterator {

398 using DataIt = typename std::vector<T>::const_iterator;

399 using IdIt = typename std::vector<EntityId>::const_iterator;

400

404 DataIt dataIt_;

405

409 IdIt idIt_;

410

411 using iterator_category = std::forward_iterator_tag;

412 using value_type = T;

413 using difference_type = std::ptrdiff_t;

414 using pointer = const T*;

415 using reference = const T&;

416

417 ConstIterator() = default;

418

419 ConstIterator(DataIt dataIt, IdIt idIt) : dataIt_(dataIt), idIt_(idIt) {}

420

421 reference operator*() const { return *dataIt_; }

422 pointer operator->() const { return &*dataIt_; }

423

429 [[nodiscard]] EntityId entityId() const { return *idIt_; }

430

431 [[nodiscard]] bool operator==(const ConstIterator& other) const { return dataIt_ == other.dataIt_;}

432 [[nodiscard]] bool operator!=(const ConstIterator& other) const { return dataIt_ != other.dataIt_;}

433

434 ConstIterator operator++(int) {

435 ConstIterator tmp = *this;

436 ++(*this);

437 return tmp;

438 }

439

440 ConstIterator& operator++() {

441 ++dataIt_; ++idIt_; return *this;

442 }

443 };

444

450 [[nodiscard]] Iterator begin() {

451 return Iterator(storage_.begin(), denseToSparse_.begin());

452 }

453

459 [[nodiscard]] Iterator end() {

460 return Iterator(storage_.end(), denseToSparse_.end());

461 }

462

468 [[nodiscard]] ConstIterator begin() const {

469 return ConstIterator(storage_.begin(), denseToSparse_.begin());

470 }

471

477 [[nodiscard]] ConstIterator end() const {

478 return ConstIterator(storage_.end(), denseToSparse_.end());

479 }

480

481 };

482

483

484

485}

---

Generated via doxygen2docusaurus 2.0.0 by Doxygen 1.9.8.