Line data Source code
1 : #pragma once
2 : #include <cstdint>
3 : #include <utility>
4 : #include <vector>
5 :
6 : // =============================================================================
7 : // SoABase<Derived, IdType, Capacity, GenerationBits>
8 : //
9 : // CRTP base that provides all bookkeeping and methods for a fixed-capacity
10 : // SoA. The concrete struct (generated by DEFINE_SOA) only needs to:
11 : // 1. Declare named data arrays as plain members.
12 : // 2. Implement swap_elements(a, b) using those members.
13 : //
14 : // The user never sees this file. They interact only with the struct produced
15 : // by DEFINE_SOA and access fields directly:
16 : //
17 : // bc.position[i] — in solver loops (i = packed data index)
18 : // bc.position[bc.index_of(id)] — single-body access by stable ID
19 : // =============================================================================
20 :
21 : /**
22 : * @brief CRTP base for fixed-capacity Structure-of-Arrays containers.
23 : *
24 : * Provides stable versioned IDs, O(1) add/remove/lookup, and iteration helpers.
25 : * Concrete structs are generated via DEFINE_SOA; this base is not used
26 : * directly.
27 : *
28 : * @tparam Derived The generated concrete struct (CRTP pattern).
29 : * @tparam IdType Unsigned integer type for IDs (e.g. uint32_t).
30 : * @tparam Capacity Compile-time maximum number of live items.
31 : * @tparam GenerationBits Bits of IdType reserved for the generation counter.
32 : * Set to 0 to disable versioning entirely.
33 : */
34 : template <typename Derived, typename IdType, IdType Capacity,
35 : uint8_t GenerationBits>
36 : struct SoABase
37 : {
38 : // ── Compile-time helpers ─────────────────────────────────────────────────
39 :
40 : static constexpr uint8_t SLOT_BITS = sizeof(IdType) * 8 - GenerationBits;
41 :
42 : static constexpr IdType SLOT_MASK =
43 : (GenerationBits == 0) ? ~IdType(0)
44 : : ((IdType(1) << SLOT_BITS) - IdType(1));
45 :
46 : static constexpr IdType INVALID = ~IdType(0);
47 :
48 : static_assert(Capacity <= SLOT_MASK + IdType(1),
49 : "SoABase: Capacity exceeds the addressable slot range for the "
50 : "given GenerationBits.");
51 :
52 : // ── Bookkeeping ───────────────────────────────────────────────────────────
53 :
54 : IdType _size = 0;
55 : IdType _next_slot = 0;
56 : IdType _n_free = 0;
57 :
58 : IdType _data_index[Capacity]; ///< slot → packed data index (or INVALID)
59 : IdType _ids[Capacity]; ///< packed data index → full versioned ID
60 : IdType _free_slots[Capacity]; ///< recycled slot stack
61 : IdType _generation[Capacity]; ///< slot → generation counter
62 :
63 27 : SoABase()
64 27 : {
65 1755 : for (IdType i = 0; i < Capacity; ++i)
66 1728 : _generation[i] = 0;
67 27 : }
68 :
69 : // ── CRTP accessor ─────────────────────────────────────────────────────────
70 :
71 19 : Derived &self() { return *static_cast<Derived *>(this); }
72 : const Derived &self() const { return *static_cast<const Derived *>(this); }
73 :
74 : // ── add ───────────────────────────────────────────────────────────────────
75 :
76 : /**
77 : * @brief Allocate a new item and return its stable ID.
78 : *
79 : * All fields at the new packed slot are zero-initialised (the concrete
80 : * struct's arrays are value-initialised at construction; add() only
81 : * advances the bookkeeping, so callers should write fields immediately).
82 : *
83 : * @return Stable versioned ID. Store it to reference this item later.
84 : */
85 81 : IdType add()
86 : {
87 81 : IdType slot = (_n_free > 0) ? _free_slots[--_n_free] : _next_slot++;
88 81 : IdType data_idx = _size;
89 81 : IdType gen = _generation[slot];
90 81 : IdType id = make_id(slot, gen);
91 :
92 81 : _data_index[slot] = data_idx;
93 81 : _ids[data_idx] = id;
94 :
95 81 : ++_size;
96 81 : return id;
97 : }
98 :
99 : // ── emplace ───────────────────────────────────────────────────────────────
100 :
101 : /**
102 : * @brief Allocate a new item and immediately write fields via a callback.
103 : *
104 : * @tparam Fn Callable with signature `void(IdType id, Derived& self)`.
105 : * @param fn Called right after allocation with the new ID and the
106 : * collection.
107 : * @return Stable versioned ID.
108 : *
109 : * @par Example
110 : * @code
111 : * bc.emplace([&](uint32_t id, auto& c) {
112 : * uint32_t i = c.index_of(id);
113 : * c.position[i] = {0, 5, 0};
114 : * c.mass[i] = 2.0f;
115 : * });
116 : * @endcode
117 : */
118 : template <typename Fn>
119 2 : IdType emplace(Fn &&fn)
120 : {
121 2 : IdType id = add();
122 2 : fn(id, self());
123 2 : return id;
124 : }
125 :
126 : // ── add_n ─────────────────────────────────────────────────────────────────
127 :
128 : /**
129 : * @brief Bulk-allocate @p n items, calling @p on_added for each.
130 : *
131 : * @tparam Fn Callable with signature `void(IdType id)`.
132 : * @param n Number of items to allocate.
133 : * @param on_added Called once per new item.
134 : */
135 : template <typename Fn>
136 8 : void add_n(IdType n, Fn &&on_added)
137 : {
138 42 : for (IdType i = 0; i < n; ++i)
139 34 : on_added(add());
140 8 : }
141 :
142 : // ── remove ────────────────────────────────────────────────────────────────
143 :
144 : /**
145 : * @brief Remove an item in O(1) via swap-and-pop.
146 : *
147 : * The last live item slides into the freed slot; data order is NOT preserved.
148 : * Stale or already-removed IDs are silently ignored.
149 : *
150 : * @param id Stable ID returned by add() or emplace().
151 : */
152 18 : void remove(IdType id)
153 : {
154 18 : if (!_size)
155 1 : return;
156 :
157 17 : const IdType slot = slot_of(id);
158 17 : if (slot >= _next_slot)
159 0 : return;
160 :
161 17 : const IdType idx = _data_index[slot];
162 17 : if (idx >= _size)
163 0 : return;
164 :
165 : if constexpr (GenerationBits > 0)
166 17 : if (gen_of(_ids[idx]) != gen_of(id))
167 0 : return;
168 :
169 17 : const IdType last_idx = _size - 1;
170 17 : const IdType last_id = _ids[last_idx];
171 17 : const IdType last_slot = slot_of(last_id);
172 :
173 17 : self().swap_elements(idx, last_idx); // CRTP call into concrete struct
174 17 : _ids[idx] = _ids[last_idx];
175 :
176 17 : _data_index[last_slot] = idx;
177 17 : _data_index[slot] = INVALID;
178 :
179 : if constexpr (GenerationBits > 0)
180 17 : ++_generation[slot];
181 :
182 17 : _free_slots[_n_free++] = slot;
183 17 : --_size;
184 : }
185 :
186 : // ── index_of ─────────────────────────────────────────────────────────────
187 :
188 : /**
189 : * @brief Return the packed data index for a stable ID.
190 : *
191 : * Use this when you need to write or read a single item by ID outside
192 : * of a full iteration loop.
193 : *
194 : * No bounds-checking is performed. Call contains() first if the ID may be
195 : * stale.
196 : *
197 : * @param id Stable ID.
198 : * @return Packed array index in [0, count()).
199 : *
200 : * @par Example
201 : * @code
202 : * uint32_t i = bc.index_of(ball);
203 : * bc.position[i] = {1, 2, 3};
204 : * @endcode
205 : */
206 52 : IdType index_of(IdType id) const { return _data_index[slot_of(id)]; }
207 :
208 : // ── contains ──────────────────────────────────────────────────────────────
209 :
210 : /**
211 : * @brief Return true if @p id refers to a currently live item.
212 : *
213 : * @param id ID to test (may be stale or out-of-range).
214 : */
215 25 : bool contains(IdType id) const
216 : {
217 25 : const IdType slot = slot_of(id);
218 25 : if (slot >= _next_slot)
219 3 : return false;
220 22 : const IdType idx = _data_index[slot];
221 22 : if (idx >= _size)
222 2 : return false;
223 : if constexpr (GenerationBits > 0)
224 20 : return gen_of(_ids[idx]) == gen_of(id);
225 : return true;
226 : }
227 :
228 : // ── Iteration ─────────────────────────────────────────────────────────────
229 :
230 : /**
231 : * @brief Iterate over all live items by packed data index.
232 : *
233 : * @tparam Fn Callable with signature `void(IdType data_index)`.
234 : */
235 : template <typename Fn>
236 2 : void for_each_index(Fn &&fn)
237 : {
238 9 : for (IdType i = 0; i < _size; ++i)
239 7 : fn(i);
240 2 : }
241 :
242 : /// @copydoc for_each_index
243 : template <typename Fn>
244 : void for_each_index(Fn &&fn) const
245 : {
246 : for (IdType i = 0; i < _size; ++i)
247 : fn(i);
248 : }
249 :
250 : /**
251 : * @brief Iterate over all live items by stable versioned ID.
252 : *
253 : * @tparam Fn Callable with signature `void(IdType id)`.
254 : */
255 : template <typename Fn>
256 1 : void for_each_id(Fn &&fn)
257 : {
258 5 : for (IdType i = 0; i < _size; ++i)
259 4 : fn(_ids[i]);
260 1 : }
261 :
262 : /// @copydoc for_each_id
263 : template <typename Fn>
264 : void for_each_id(Fn &&fn) const
265 : {
266 : for (IdType i = 0; i < _size; ++i)
267 : fn(_ids[i]);
268 : }
269 :
270 : // ── Misc ──────────────────────────────────────────────────────────────────
271 :
272 : /// @brief Return the number of currently live items.
273 13 : IdType count() const { return _size; }
274 :
275 : /// @brief Return the compile-time maximum capacity.
276 : static constexpr IdType max_capacity() { return Capacity; }
277 :
278 : /**
279 : * @brief Remove all items. Generation counters are preserved so old IDs stay
280 : * stale.
281 : */
282 3 : void clear()
283 : {
284 3 : _size = 0;
285 3 : _n_free = 0;
286 3 : _next_slot = 0;
287 3 : }
288 :
289 : // ── ID helpers ────────────────────────────────────────────────────────────
290 :
291 111 : static constexpr IdType slot_of(IdType id) { return id & SLOT_MASK; }
292 74 : static constexpr IdType gen_of(IdType id) { return id >> SLOT_BITS; }
293 81 : static constexpr IdType make_id(IdType slot, IdType g)
294 : {
295 81 : return slot | (g << SLOT_BITS);
296 : }
297 : };
298 :
299 : // =============================================================================
300 : // DEFINE_SOA(Name, IdType, Capacity, GenBits, FIELDS_MACRO)
301 : // =============================================================================
302 :
303 : /**
304 : * @brief Define a named SoA struct with direct field access.
305 : *
306 : * Generates a struct where every field from FIELDS_MACRO becomes a plain
307 : * array member, giving clean `bc.position[i]` access in loops.
308 : *
309 : * @param Name Name of the generated struct (e.g. BodyCollection).
310 : * @param IdType Integer type for IDs (e.g. uint32_t).
311 : * @param Cap Compile-time max item count.
312 : * @param GenBits Bits reserved for the generation counter (0 = disabled).
313 : * @param FIELDS_MACRO X-macro listing fields as X(Type, name).
314 : *
315 : * @par Minimal example
316 : * @code
317 : * #define PARTICLE_FIELDS(X) \
318 : * X(vec3, position) \
319 : * X(vec3, velocity) \
320 : * X(float, mass)
321 : *
322 : * DEFINE_SOA(ParticleCollection, uint32_t, 1024, 8, PARTICLE_FIELDS)
323 : *
324 : * ParticleCollection pc;
325 : * uint32_t id = pc.add();
326 : * uint32_t i = pc.index_of(id);
327 : * pc.position[i] = {0, 5, 0};
328 : * pc.mass[i] = 1.0f;
329 : *
330 : * // Solver loop — same as the old struct-of-vectors style
331 : * for (uint32_t i = 0; i < pc.count(); ++i)
332 : * pc.position[i] += pc.velocity[i] * dt;
333 : *
334 : * pc.remove(id);
335 : * pc.contains(id); // false
336 : * @endcode
337 : */
338 : #define DEFINE_SOA(Name, IdType, Cap, GenBits, FIELDS_MACRO) \
339 : struct Name : SoABase<Name, IdType, Cap, GenBits> \
340 : { \
341 : /* Make Cap available as a plain name inside the struct body so that \
342 : DEFINE_SOA_ARRAY_ can use it as an array bound. Template parameters \
343 : of the base class are NOT directly in scope in the derived struct. */ \
344 : static constexpr IdType _cap = Cap; \
345 : \
346 : /* ── Named data arrays ── */ \
347 : FIELDS_MACRO(DEFINE_SOA_ARRAY_) \
348 : \
349 : /* ── swap_elements: called by SoABase::remove() via CRTP ── */ \
350 : void swap_elements(IdType _a, IdType _b) \
351 : { \
352 : using std::swap; \
353 : FIELDS_MACRO(DEFINE_SOA_SWAP_) \
354 : } \
355 : };
356 :
357 : // Per-field helpers consumed by DEFINE_SOA — not for direct use.
358 : // _cap is the constexpr injected above; it is in scope here because
359 : // DEFINE_SOA_ARRAY_ is always expanded inside the struct body.
360 : #define DEFINE_SOA_ARRAY_(T, name) T name[_cap];
361 : #define DEFINE_SOA_SWAP_(T, name) swap(name[_a], name[_b]);
362 :
363 : // =============================================================================
364 : // DEFINE_DYN_SOA(Name, IdType, GenBits, FIELDS_MACRO)
365 : // =============================================================================
366 :
367 : /**
368 : * @brief CRTP base for dynamically-allocated Structure-of-Arrays containers.
369 : *
370 : * Mirrors SoABase exactly, but all bookkeeping arrays are std::vector.
371 : * Capacity grows at runtime; call reserve() to pre-allocate.
372 : *
373 : * @tparam Derived The generated concrete struct.
374 : * @tparam IdType Unsigned integer type for IDs.
375 : * @tparam GenerationBits Bits reserved for the generation counter.
376 : */
377 : template <typename Derived, typename IdType, uint8_t GenerationBits>
378 : struct DynSoABase
379 : {
380 : static constexpr uint8_t SLOT_BITS = sizeof(IdType) * 8 - GenerationBits;
381 : static constexpr IdType SLOT_MASK =
382 : (GenerationBits == 0) ? ~IdType(0)
383 : : ((IdType(1) << SLOT_BITS) - IdType(1));
384 : static constexpr IdType INVALID = ~IdType(0);
385 :
386 : IdType _size = 0;
387 : IdType _next_slot = 0;
388 : IdType _n_free = 0;
389 :
390 : std::vector<IdType> _data_index;
391 : std::vector<IdType> _ids;
392 : std::vector<IdType> _free_slots;
393 : std::vector<IdType> _generation;
394 :
395 326 : explicit DynSoABase(IdType initial_capacity = 0)
396 326 : {
397 326 : if (initial_capacity > 0)
398 0 : _reserve_bookkeeping(initial_capacity);
399 326 : }
400 :
401 716 : Derived &self() { return *static_cast<Derived *>(this); }
402 : const Derived &self() const { return *static_cast<const Derived *>(this); }
403 :
404 : /**
405 : * @brief Pre-allocate space for @p n items in all arrays.
406 : *
407 : * Call before a burst of add() calls to avoid repeated reallocation.
408 : * After reserving, pointers returned by data arrays are stable until
409 : * capacity is exceeded again.
410 : */
411 1 : void reserve(IdType n)
412 : {
413 1 : _reserve_bookkeeping(n);
414 1 : self().reserve_data(n); // CRTP: each concrete struct reserves its vectors
415 1 : }
416 :
417 : /**
418 : * @brief Allocate a new item and return its stable ID.
419 : */
420 613 : IdType add()
421 : {
422 : IdType slot;
423 613 : if (_n_free > 0)
424 : {
425 1 : slot = _free_slots[--_n_free];
426 1 : _free_slots.pop_back();
427 : }
428 : else
429 : {
430 612 : slot = _next_slot++;
431 612 : _data_index.push_back(INVALID);
432 612 : _generation.push_back(0);
433 : }
434 :
435 613 : IdType data_idx = _size;
436 613 : IdType gen = _generation[slot];
437 613 : IdType id = make_id(slot, gen);
438 :
439 613 : _data_index[slot] = data_idx;
440 613 : _ids.push_back(id);
441 :
442 613 : self()
443 613 : .push_back_data(); // CRTP: push one zero-init element per field vector
444 613 : ++_size;
445 613 : return id;
446 : }
447 :
448 : template <typename Fn>
449 : IdType emplace(Fn &&fn)
450 : {
451 : IdType id = add();
452 : fn(id, self());
453 : return id;
454 : }
455 :
456 : template <typename Fn>
457 : void add_n(IdType n, Fn &&on_added)
458 : {
459 : reserve(_size + n);
460 : for (IdType i = 0; i < n; ++i)
461 : on_added(add());
462 : }
463 :
464 51 : void remove(IdType id)
465 : {
466 51 : if (!_size)
467 0 : return;
468 51 : const IdType slot = slot_of(id);
469 51 : if (slot >= _next_slot)
470 0 : return;
471 51 : const IdType idx = _data_index[slot];
472 51 : if (idx >= _size)
473 0 : return;
474 : if constexpr (GenerationBits > 0)
475 51 : if (gen_of(_ids[idx]) != gen_of(id))
476 0 : return;
477 :
478 51 : const IdType last_idx = _size - 1;
479 51 : const IdType last_slot = slot_of(_ids[last_idx]);
480 :
481 51 : self().swap_elements(idx, last_idx);
482 51 : _ids[idx] = _ids[last_idx];
483 :
484 51 : _data_index[last_slot] = idx;
485 51 : _data_index[slot] = INVALID;
486 : if constexpr (GenerationBits > 0)
487 51 : ++_generation[slot];
488 :
489 51 : self().pop_back_data(); // CRTP: pop_back every field vector
490 51 : _ids.pop_back();
491 51 : _free_slots.push_back(slot);
492 51 : ++_n_free;
493 51 : --_size;
494 : }
495 :
496 852 : IdType index_of(IdType id) const { return _data_index[slot_of(id)]; }
497 :
498 14 : bool contains(IdType id) const
499 : {
500 14 : const IdType slot = slot_of(id);
501 14 : if (slot >= _next_slot)
502 0 : return false;
503 14 : const IdType idx = _data_index[slot];
504 14 : if (idx >= _size)
505 2 : return false;
506 : if constexpr (GenerationBits > 0)
507 12 : return gen_of(_ids[idx]) == gen_of(id);
508 : return true;
509 : }
510 :
511 : template <typename Fn>
512 : void for_each_index(Fn &&fn)
513 : {
514 : for (IdType i = 0; i < _size; ++i)
515 : fn(i);
516 : }
517 : template <typename Fn>
518 : void for_each_index(Fn &&fn) const
519 : {
520 : for (IdType i = 0; i < _size; ++i)
521 : fn(i);
522 : }
523 : template <typename Fn>
524 : void for_each_id(Fn &&fn)
525 : {
526 : for (IdType i = 0; i < _size; ++i)
527 : fn(_ids[i]);
528 : }
529 : template <typename Fn>
530 : void for_each_id(Fn &&fn) const
531 : {
532 : for (IdType i = 0; i < _size; ++i)
533 : fn(_ids[i]);
534 : }
535 :
536 194275 : IdType count() const { return _size; }
537 :
538 : void clear()
539 : {
540 : self().clear_data();
541 : _ids.clear();
542 : _size = 0;
543 : _n_free = 0;
544 : _next_slot = 0;
545 : }
546 :
547 968 : static constexpr IdType slot_of(IdType id) { return id & SLOT_MASK; }
548 126 : static constexpr IdType gen_of(IdType id) { return id >> SLOT_BITS; }
549 613 : static constexpr IdType make_id(IdType s, IdType g)
550 : {
551 613 : return s | (g << SLOT_BITS);
552 : }
553 :
554 : private:
555 1 : void _reserve_bookkeeping(IdType n)
556 : {
557 1 : _data_index.reserve(n);
558 1 : _ids.reserve(n);
559 1 : _free_slots.reserve(n);
560 1 : _generation.reserve(n);
561 1 : }
562 : };
563 :
564 : /**
565 : * @brief Define a named dynamic SoA struct with direct field access.
566 : *
567 : * Same API as DEFINE_SOA, but capacity grows at runtime.
568 : * Fields become std::vector members; access is still `bc.position[i]`.
569 : *
570 : * @warning Pointers into field vectors are invalidated on reallocation.
571 : * Call bc.reserve(n) before a burst of bc.add() calls if you need
572 : * stable pointers (e.g. before constructing a view for a solver loop).
573 : *
574 : * @par Example
575 : * @code
576 : * DEFINE_DYN_SOA(ParticleCollection, uint32_t, 8, PARTICLE_FIELDS)
577 : *
578 : * ParticleCollection pc;
579 : * uint32_t id = pc.add();
580 : * pc.position[pc.index_of(id)] = {0, 5, 0};
581 : *
582 : * for (uint32_t i = 0; i < pc.count(); ++i)
583 : * pc.position[i] += pc.velocity[i] * dt;
584 : * @endcode
585 : */
586 : #define DEFINE_DYN_SOA(Name, IdType, GenBits, FIELDS_MACRO) \
587 : struct Name : DynSoABase<Name, IdType, GenBits> \
588 : { \
589 : /* ── Named field vectors ── */ \
590 : FIELDS_MACRO(DEFINE_DYN_SOA_VEC_) \
591 : \
592 : explicit Name(IdType initial_capacity = 0) \
593 : : DynSoABase<Name, IdType, GenBits>(initial_capacity) {} \
594 : \
595 : /* Called by DynSoABase::reserve() */ \
596 : void reserve_data(IdType n) { FIELDS_MACRO(DEFINE_DYN_SOA_RESERVE_) } \
597 : /* Called by DynSoABase::add() */ \
598 : void push_back_data() { FIELDS_MACRO(DEFINE_DYN_SOA_PUSH_) } \
599 : /* Called by DynSoABase::remove() */ \
600 : void pop_back_data() { FIELDS_MACRO(DEFINE_DYN_SOA_POP_) } \
601 : /* Called by DynSoABase::clear() */ \
602 : void clear_data() { FIELDS_MACRO(DEFINE_DYN_SOA_CLEAR_) } \
603 : /* Called by DynSoABase::remove() */ \
604 : void swap_elements(IdType _a, IdType _b) \
605 : { \
606 : using std::swap; \
607 : FIELDS_MACRO(DEFINE_SOA_SWAP_) \
608 : } \
609 : };
610 :
611 : // Per-field helpers for DEFINE_DYN_SOA — not for direct use.
612 : #define DEFINE_DYN_SOA_VEC_(T, name) std::vector<T> name;
613 : #define DEFINE_DYN_SOA_RESERVE_(T, name) name.reserve(n);
614 : #define DEFINE_DYN_SOA_PUSH_(T, name) name.push_back({});
615 : #define DEFINE_DYN_SOA_POP_(T, name) name.pop_back();
616 : #define DEFINE_DYN_SOA_CLEAR_(T, name) name.clear();
617 : // swap reuses DEFINE_SOA_SWAP_ — works for both vector and array indexing.
|
