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

56 virtual void clear() = 0;

57

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

66

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

75 };

76

77

83 constexpr auto Tombstone = EntityTombstone;

84

85

125 template <typename T>

126 class SparseSet : public SparseSetBase {

127

128

134 std::vector<size_t> sparse_;

135

141 std::vector<EntityId> denseToSparse_;

142

146 std::vector<T> storage_;

147

148 public:

149

153 SparseSet() = default;

154

160 explicit SparseSet(const size_t capacity) {

161 sparse_.reserve(capacity);

162 storage_.reserve(capacity);

163 denseToSparse_.reserve(capacity);

164 };

165

169 SparseSet(const SparseSet&) = delete;

170

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

175

179 SparseSet(SparseSet&&) noexcept = default;

180

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

185

186

199 template <typename... Args>

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

201

202 // already in use

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

204 return nullptr;

205 }

206

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

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

209 }

210

211 const auto denseIndex = storage_.size();

212

213 denseToSparse_.push_back(idx);

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

215

216 sparse_[idx] = denseIndex;

217

218 return &storage_.back();

219 }

220

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

233

234 // already in use

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

236 return nullptr;

237 }

238

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

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

241 }

242

243 const auto denseIndex = storage_.size();

244

245 denseToSparse_.push_back(idx);

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

247

248 sparse_[idx] = denseIndex;

249

250 return &storage_.back();

251 }

252

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

267

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

269 return false;

270 }

271

272 const auto denseIndex = sparse_[idx];

273 const auto sparseIdx = denseToSparse_[denseIndex];

274

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

276

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

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

279 const auto newSparseIndex = denseToSparse_.back();

280 sparse_[newSparseIndex] = denseIndex;

281 denseToSparse_[denseIndex] = newSparseIndex;

282 }

283

284 storage_.pop_back();

285 denseToSparse_.pop_back();

286

287 sparse_[idx] = Tombstone;

288

289 return true;

290 }

291

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

300

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

302 return nullptr;

303 }

304

305 return &storage_[sparse_[idx]];

306 }

307

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

316

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

318 return nullptr;

319 }

320

321 return &storage_[sparse_[idx]];

322 }

323

324

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

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

334 }

335

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

340 T* ptr = get(id);

341 return static_cast<void*>(ptr);

342 }

343

347 void clear() override {

348 sparse_.clear();

349 denseToSparse_.clear();

350 storage_.clear();

351 }

352

353

360 struct Iterator {

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

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

363

367 DataIt dataIt_;

368

372 IdIt idIt_;

373

374 using iterator_category = std::forward_iterator_tag;

375 using value_type = T;

376 using difference_type = std::ptrdiff_t;

377 using pointer = T*;

378 using reference = T&;

379

380 Iterator() = default;

381

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

383

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

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

386

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

393

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

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

396

397 Iterator operator++(int) {

398 Iterator tmp = *this;

399 ++(*this);

400 return tmp;

401 }

402

403 Iterator& operator++() {

404 ++dataIt_; ++idIt_; return *this;

405 }

406 };

407

413 struct ConstIterator {

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

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

416

420 DataIt dataIt_;

421

425 IdIt idIt_;

426

427 using iterator_category = std::forward_iterator_tag;

428 using value_type = T;

429 using difference_type = std::ptrdiff_t;

430 using pointer = const T*;

431 using reference = const T&;

432

433 ConstIterator() = default;

434

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

436

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

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

439

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

446

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

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

449

450 ConstIterator operator++(int) {

451 ConstIterator tmp = *this;

452 ++(*this);

453 return tmp;

454 }

455

456 ConstIterator& operator++() {

457 ++dataIt_; ++idIt_; return *this;

458 }

459 };

460

466 [[nodiscard]] Iterator begin() {

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

468 }

469

475 [[nodiscard]] Iterator end() {

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

477 }

478

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

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

486 }

487

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

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

495 }

496

497 };

498

499

500

501}

---

Generated via doxygen2docusaurus 2.0.0 by Doxygen 1.9.8.