Line data Source code
1 : #pragma once
2 : /**
3 : * @file ivc.hpp
4 : * @brief Index Vector Core (IVC) — stable ID management for Struct-of-Arrays collections.
5 : *
6 : * This is the SoA equivalent of siv::Vector. Instead of owning the data, it
7 : * only owns the two bookkeeping tables (indexes + metadata) that make IDs
8 : * stable across insertions and deletions. Your collection owns its own data
9 : * arrays and calls the IVC helpers to keep them in sync.
10 : *
11 : * ── Core idea ────────────────────────────────────────────────────────────────
12 : *
13 : * indexes[id] → data_index (stable ID → current position in arrays)
14 : * metadata[data_idx] → {rid, vid} (position → {its ID, validity counter})
15 : *
16 : * On erase(id):
17 : * 1. Increment metadata[data_idx].validity_id (invalidates all Handles)
18 : * 2. Swap-and-pop: move last element into the freed slot.
19 : * User does the same swap on their own data arrays, then pop_back.
20 : * 3. Decrement n_items.
21 : *
22 : * Free slots are reused automatically (metadata + indexes arrays grow
23 : * monotonically, never shrink).
24 : *
25 : * ── Usage ────────────────────────────────────────────────────────────────────
26 : *
27 : * struct BodyCollection {
28 : * IVC_CORE; // embeds ivc::Core _ivc
29 : * std::vector<vec3> position;
30 : * std::vector<quat> orientation;
31 : * // ...
32 : * };
33 : *
34 : * // --- Adding ---
35 : * ivc::ID id = ivc::add(bc._ivc); // reserve a stable ID
36 : * bc.position.push_back(p); // keep all arrays in sync
37 : * bc.orientation.push_back(q);
38 : *
39 : * // --- Accessing ---
40 : * size_t idx = ivc::index(bc._ivc, id);
41 : * bc.position[idx].x = 1.0f;
42 : *
43 : * // --- Handles (safe references) ---
44 : * ivc::Handle h = ivc::make_handle(bc._ivc, id);
45 : * if (h) { auto idx = h.index(); } // checks validity automatically
46 : *
47 : * // --- Erasing ---
48 : * ivc::erase(bc._ivc, id, [&](size_t a, size_t b) {
49 : * std::swap(bc.position[a], bc.position[b]);
50 : * std::swap(bc.orientation[a], bc.orientation[b]);
51 : * // ... every array in the collection
52 : * });
53 : * bc.position.pop_back(); // after erase, pop all arrays
54 : * bc.orientation.pop_back();
55 : *
56 : * ── Fixed-size arrays ────────────────────────────────────────────────────────
57 : *
58 : * If Capacity > 0 the bookkeeping tables are stack-allocated and no dynamic
59 : * allocation occurs. Your own data arrays must also be fixed-size then.
60 : * Use IVC_CORE_FIXED(N) in the struct and the same free functions work.
61 : *
62 : * struct BodyCollection {
63 : * IVC_CORE_FIXED(256);
64 : * vec3 position[256];
65 : * // ...
66 : * };
67 : */
68 :
69 : #include <cstdint>
70 : #include <cstddef>
71 : #include <cassert>
72 : #include <limits>
73 : #include <algorithm> // std::swap
74 : #include <vector>
75 :
76 : namespace ivc
77 : {
78 :
79 : // ─── Types ────────────────────────────────────────────────────────────────────
80 :
81 : using ID = uint64_t;
82 : static constexpr ID InvalidID = std::numeric_limits<ID>::max();
83 :
84 : struct Metadata {
85 : ID rid = 0; ///< reverse-ID: data_index → the ID that owns this slot
86 : ID validity_id = 0; ///< bumped on every erase; used to detect stale Handles
87 : };
88 :
89 : // ─── Core struct (two flavours) ───────────────────────────────────────────────
90 :
91 : /**
92 : * @brief Dynamic bookkeeping tables (heap-allocated, unlimited capacity).
93 : *
94 : * Embed via the IVC_CORE macro.
95 : */
96 : struct Core
97 : {
98 : size_t n_items = 0; ///< number of live items
99 : std::vector<ID> indexes; ///< indexes[id] → data_index
100 : std::vector<Metadata> metadata; ///< metadata[data_idx] → {rid, validity_id}
101 : };
102 :
103 : /**
104 : * @brief Fixed-size bookkeeping tables (stack-allocated, compile-time capacity).
105 : *
106 : * Embed via the IVC_CORE_FIXED(N) macro.
107 : * @tparam Capacity Maximum number of live items at any one time.
108 : */
109 : template<size_t Capacity>
110 : struct CoreFixed
111 : {
112 : size_t n_items = 0;
113 : size_t n_slots = 0; ///< total allocated slots (≥ n_items)
114 : ID indexes[Capacity] = {};
115 : Metadata metadata[Capacity] = {};
116 : };
117 :
118 : // ─── Handle ───────────────────────────────────────────────────────────────────
119 :
120 : /**
121 : * @brief A safe, stable reference to an item inside a Core-bearing collection.
122 : *
123 : * Stores (id, validity_id, Core*). Checking the handle re-reads the current
124 : * validity counter from the Core, so it automatically becomes invalid after
125 : * the item is erased.
126 : *
127 : * The handle does NOT know about your data arrays; call ivc::index(h) to get
128 : * the current data_index and then index into your arrays yourself.
129 : */
130 : struct Handle
131 : {
132 : ID id = InvalidID;
133 : ID validity_id = 0;
134 : Core* core = nullptr;
135 :
136 : /// True iff the item still exists in the collection.
137 10 : [[nodiscard]] bool isValid() const
138 : {
139 10 : return core
140 10 : && id < core->indexes.size()
141 20 : && core->metadata[core->indexes[id]].validity_id == validity_id;
142 : }
143 :
144 2 : explicit operator bool() const { return isValid(); }
145 :
146 : /// Current data_index. Only call when isValid() == true.
147 1 : [[nodiscard]] size_t index() const
148 : {
149 1 : assert(isValid());
150 1 : return static_cast<size_t>(core->indexes[id]);
151 : }
152 :
153 1 : [[nodiscard]] ID getID() const { return id; }
154 : };
155 :
156 : // ─── Internal helpers (not part of the public API) ───────────────────────────
157 :
158 : namespace detail
159 : {
160 : /** Obtain a free ID, reusing freed slots when available.
161 : * Grows the bookkeeping tables by one slot when needed.
162 : * Does NOT touch n_items. */
163 51 : inline ID get_free_id(Core& c)
164 : {
165 51 : if (c.metadata.size() > c.n_items)
166 : {
167 : // A previously freed slot is available; bump its validity_id so
168 : // any old handles to the same ID are invalidated immediately.
169 7 : ++c.metadata[c.n_items].validity_id;
170 7 : return c.metadata[c.n_items].rid;
171 : }
172 : // No free slot — allocate a brand-new one.
173 44 : const ID new_id = static_cast<ID>(c.n_items);
174 44 : c.metadata.push_back({new_id, 0});
175 44 : c.indexes.push_back(new_id);
176 44 : return new_id;
177 : }
178 :
179 : template<size_t Capacity>
180 5 : inline ID get_free_id(CoreFixed<Capacity>& c)
181 : {
182 5 : assert(c.n_items < Capacity && "CoreFixed capacity exceeded");
183 5 : if (c.n_slots > c.n_items)
184 : {
185 0 : ++c.metadata[c.n_items].validity_id;
186 0 : return c.metadata[c.n_items].rid;
187 : }
188 5 : const ID new_id = static_cast<ID>(c.n_items);
189 5 : c.indexes[new_id] = new_id;
190 5 : c.metadata[new_id] = {new_id, 0};
191 5 : ++c.n_slots;
192 5 : return new_id;
193 : }
194 :
195 : /** Core erase logic — works for both Core (dynamic) and CoreFixed (fixed). */
196 : template<typename TCore, typename TSwapFn>
197 20 : inline void erase_impl(TCore& c, ID id, TSwapFn&& swap_fn)
198 : {
199 20 : assert(c.n_items > 0 && "erase called on empty collection");
200 20 : const size_t data_idx = static_cast<size_t>(c.indexes[id]);
201 20 : const size_t last_idx = c.n_items - 1;
202 :
203 : // Invalidate the erased slot *before* the swap so that the
204 : // incremented validity_id ends up in the free-slot position.
205 20 : ++c.metadata[data_idx].validity_id;
206 :
207 20 : if (data_idx != last_idx)
208 : {
209 13 : const ID last_rid = c.metadata[last_idx].rid;
210 :
211 : // 1. User swaps their data arrays (swap-and-pop pattern).
212 13 : swap_fn(data_idx, last_idx);
213 :
214 : // 2. Update bookkeeping so the moved item is still reachable.
215 13 : std::swap(c.metadata[data_idx], c.metadata[last_idx]);
216 13 : std::swap(c.indexes[id], c.indexes[last_rid]);
217 : }
218 :
219 20 : --c.n_items;
220 : // NOTE: metadata and indexes arrays keep their allocated size;
221 : // the freed slot at position n_items is reused on next add().
222 : // Caller must pop_back on every SoA data array.
223 20 : }
224 : }
225 :
226 : // ─── Public API ───────────────────────────────────────────────────────────────
227 :
228 : // ----- reserve / capacity ----------------------------------------------------
229 :
230 : inline void reserve(Core& c, size_t n)
231 : {
232 : c.indexes.reserve(n);
233 : c.metadata.reserve(n);
234 : }
235 :
236 : template<size_t Capacity>
237 : inline void reserve(CoreFixed<Capacity>&, size_t) { /* no-op */ }
238 :
239 : // ----- add -------------------------------------------------------------------
240 :
241 : /**
242 : * @brief Register a new item and return its stable ID.
243 : *
244 : * After calling this, push_back (or assign at n_items-1) to EVERY data array
245 : * in your collection. The ID is valid immediately.
246 : */
247 51 : inline ID add(Core& c)
248 : {
249 51 : const ID id = detail::get_free_id(c);
250 51 : c.indexes[id] = static_cast<ID>(c.n_items);
251 51 : ++c.n_items;
252 51 : return id;
253 : }
254 :
255 : template<size_t Capacity>
256 5 : inline ID add(CoreFixed<Capacity>& c)
257 : {
258 5 : const ID id = detail::get_free_id(c);
259 5 : c.indexes[id] = static_cast<ID>(c.n_items);
260 5 : ++c.n_items;
261 5 : return id;
262 : }
263 :
264 : // ----- erase -----------------------------------------------------------------
265 :
266 : /**
267 : * @brief Erase the item with the given ID.
268 : *
269 : * @param c The Core embedded in your collection.
270 : * @param id Stable ID of the item to remove.
271 : * @param swap_fn Callable void(size_t a, size_t b) that swaps the
272 : * elements at indices a and b in ALL your SoA data arrays.
273 : *
274 : * After this call, pop_back on every data array in your collection.
275 : *
276 : * Example:
277 : * ivc::erase(bc._ivc, id, [&](size_t a, size_t b) {
278 : * std::swap(bc.position[a], bc.position[b]);
279 : * std::swap(bc.orientation[a], bc.orientation[b]);
280 : * std::swap(bc.mass[a], bc.mass[b]);
281 : * // ... every array
282 : * });
283 : * bc.position.pop_back();
284 : * bc.orientation.pop_back();
285 : * bc.mass.pop_back();
286 : */
287 : template<typename TSwapFn>
288 18 : inline void erase(Core& c, ID id, TSwapFn&& swap_fn)
289 : {
290 18 : detail::erase_impl(c, id, std::forward<TSwapFn>(swap_fn));
291 18 : }
292 :
293 : template<size_t Capacity, typename TSwapFn>
294 2 : inline void erase(CoreFixed<Capacity>& c, ID id, TSwapFn&& swap_fn)
295 : {
296 2 : detail::erase_impl(c, id, std::forward<TSwapFn>(swap_fn));
297 2 : }
298 :
299 : /** Convenience overload: erase via a Handle. */
300 : template<typename TSwapFn>
301 : inline void erase(Core& c, const Handle& h, TSwapFn&& swap_fn)
302 : {
303 : assert(h.core == &c && h.isValid());
304 : erase(c, h.id, std::forward<TSwapFn>(swap_fn));
305 : }
306 :
307 : // ----- index access ----------------------------------------------------------
308 :
309 : /** Returns the current data index for a live ID. */
310 21 : inline size_t index(const Core& c, ID id)
311 : {
312 21 : assert(id < c.indexes.size());
313 21 : return static_cast<size_t>(c.indexes[id]);
314 : }
315 :
316 : template<size_t Capacity>
317 3 : inline size_t index(const CoreFixed<Capacity>& c, ID id)
318 : {
319 3 : assert(id < c.n_slots);
320 3 : return static_cast<size_t>(c.indexes[id]);
321 : }
322 :
323 : /** Returns the current data index from a Handle (validity-checked). */
324 : inline size_t index(const Handle& h)
325 : {
326 : return h.index();
327 : }
328 :
329 : // ----- handles ---------------------------------------------------------------
330 :
331 : /** Create a Handle to an existing item. */
332 7 : inline Handle make_handle(Core& c, ID id)
333 : {
334 7 : assert(id < c.indexes.size() && c.indexes[id] < c.n_items);
335 7 : return {id, c.metadata[c.indexes[id]].validity_id, &c};
336 : }
337 :
338 : /** Check validity of an id + snapshot pair (e.g. stored externally). */
339 : inline bool is_valid(const Core& c, ID id, ID validity_id)
340 : {
341 : return id < c.indexes.size()
342 : && c.metadata[c.indexes[id]].validity_id == validity_id;
343 : }
344 :
345 : template<size_t Capacity>
346 2 : inline bool is_valid(const CoreFixed<Capacity>& c, ID id, ID validity_id)
347 : {
348 2 : return id < c.n_slots
349 2 : && c.metadata[c.indexes[id]].validity_id == validity_id;
350 : }
351 :
352 : // ----- utilities -------------------------------------------------------------
353 :
354 : /** The ID that would be returned by the NEXT call to add(). */
355 : inline ID next_id(const Core& c)
356 : {
357 : if (c.metadata.size() > c.n_items)
358 : return c.metadata[c.n_items].rid;
359 : return static_cast<ID>(c.n_items);
360 : }
361 :
362 : /**
363 : * @brief Clear all items and invalidate all existing IDs / handles.
364 : *
365 : * Bumps every validity_id so outstanding Handles become stale.
366 : * Caller must also clear() or resize(0) every SoA data array.
367 : */
368 2 : inline void clear(Core& c)
369 : {
370 2 : c.n_items = 0;
371 5 : for (auto& m : c.metadata)
372 3 : ++m.validity_id;
373 : // Caller: bc.position.clear(); bc.orientation.clear(); etc.
374 2 : }
375 :
376 : template<size_t Capacity>
377 : inline void clear(CoreFixed<Capacity>& c)
378 : {
379 : c.n_items = 0;
380 : for (size_t i = 0; i < c.n_slots; ++i)
381 : ++c.metadata[i].validity_id;
382 : }
383 :
384 : } // namespace ivc
385 :
386 : // ─── Convenience macros ───────────────────────────────────────────────────────
387 :
388 : /**
389 : * @brief Embed dynamic stable-ID bookkeeping into a SoA collection struct.
390 : *
391 : * The embedded member is named _ivc so all ivc:: free functions can be called
392 : * as ivc::add(myCollection._ivc).
393 : *
394 : * Usage:
395 : * struct BodyCollection {
396 : * IVC_CORE;
397 : * std::vector<vec3> position;
398 : * ...
399 : * };
400 : */
401 : #define IVC_CORE ::ivc::Core _ivc
402 :
403 : /**
404 : * @brief Embed fixed-size stable-ID bookkeeping (no heap allocation).
405 : *
406 : * @param N Maximum number of live items (compile-time constant).
407 : *
408 : * Usage:
409 : * struct BodyCollection {
410 : * IVC_CORE_FIXED(256);
411 : * vec3 position[256];
412 : * ...
413 : * };
414 : */
415 : #define IVC_CORE_FIXED(N) ::ivc::CoreFixed<(N)> _ivc
|
