Generational Indices

In the previous lesson, we solved the problem of index invalidation by implementing stable addressing. By using tombstones (m_alive) instead of shifting memory, we ensured that index 5 always points to the same physical slot in RAM.

To keep our memory usage efficient, we implemented a free list. This allows us to recycle the slots of deleted players. If you delete the player at index 5, that slot is marked as available. The next time you add a player, the system puts the new data into index 5.

This efficiency introduces a new problem.

When we reuse a slot that previously held a different entity, we create the ABA problem.

1. Slot 5 holds "Alice". An external system like a Scoreboard holds a reference to index 5.
2. We delete Alice. Slot 5 becomes a tombstone.
3. We add "Bob". The system reuses the empty slot 5 for Bob.

Now, the scoreboard still holds index 5. It thinks that is the index for Alice, but it is actually pointing at Bob.

To solve the ABA problem, we need to add a dimension of time to our addressing.

We don't just want to point to "Slot 5". We want to point to "Slot 5, allocation number 1". When Bob takes over Slot 5, he becomes "Slot 5, allocation number 2". When a system asks us for data, we provide both the index and allocation number - a small struct typically called a handle. When they later make a request to change some data, their request includes the handle to identify what entity they want to update.

In our previous example, the Scoreboard wouldn't just use index 5 to access the slot - they'd use the handle (5, 1). Our system will see that index 5 is actually at version 2. We will know immediately: slot 5 does not have the person you think.

This technique is called generational indices

The Handle Structure

A handle is a simple structure containing the index (where the data is) and the generation (the version of the data).

1struct PlayerID {
2  int index;
3  int generation;
4};

Implementing Generations in SoA

We need to add a m_generations column to our PlayerStorage. This vector stores the current generation of each slot.

• When a player is added to a fresh slot, that slot is generation 0.
• When a player is deleted, we increment the generation of that slot.

Let's refactor PlayerStorage to support this:

1// ...
2
3struct PlayerID {
4  int index;
5  int generation;
6};
7
8// ...
9
10class PlayerStorage {
11public:
12  std::vector<int> m_generations;  // Version control
13  // ...
14
15  // AddPlayer now returns a handle to the added player
16  PlayerID AddPlayer(
17    int id, int score, float hp, std::string name
18  ) {
19    if (m_next_free_slot != -1) {
20      int index = m_next_free_slot;
21      m_next_free_slot = m_ids[index];
22
23      m_ids[index] = id;
24      m_scores[index] = score;
25      m_health[index] = hp;
26      m_names[index] = std::move(name);
27      m_alive[index] = 1;
28      
29      // Current generation is safe to use as long as it was
30      // incremented when erasing the previous player
31      return PlayerID{index, generation};
32    } else {
33      // No free slots available, push to the to the end instead
34      int index = static_cast<int>(m_ids.size());
35
36      m_ids.push_back(id);
37      m_scores.push_back(score);
38      m_health.push_back(hp);
39      m_names.push_back(std::move(name));
40      m_alive.push_back(1);
41      
42      // Initialize new slot generation
43      m_generations.push_back(0);
44      return PlayerID{index, 0};
45    }
46  }
47  
48  void EraseAt(size_t index) {
49    if (index >= m_ids.size() || m_alive[index] == 0) return;
50    m_alive[index] = 0;
51    m_ids[index] = m_next_free_slot;
52    m_next_free_slot = index;
53    
54    // This invalidates all existing handles pointing to this slot 
55    m_generations[index]++; 
56  }
57};

Validating Access

Now we can implement truly safe access functions. When external code wants to identify a player within our system, it provides a PlayerID handle, which we can check the generation of before taking action.

Below, we apply this to the Erase() method, but any function our system provides to let the outside world access our update our players would use similar techniques:

1// ...
2
3class PlayerStorage {
4public:
5  // ...
6  
7  // Returns true on success
8  bool Erase(PlayerID id) {
9    // Bounds check
10    if (id.index < 0 || id.index >= m_ids.size()) return false;
11    // Generation Check
12    if (m_generations[id.index] != id.generation) return false;
13    
14    // All good - proceed with deletion
15    m_alive[id.index] = 0;
16    m_ids[id.index] = m_next_free_slot;
17    m_next_free_slot = id.index;
18    m_generations[id.index]++;
19    
20    return true;
21  }
22};

We've can add generation checks to all of our functions, but we still have these PlayerRef proxies which contain references. If someone requests a PlayerRef from our system, saves it, and then uses it again later, those references may have become stale.

There are several ways we can deal with this. The two most common are simply enforcing usage discipline as best we can, or to invert control.

Usage Discipline

The most common approach is simply discipline. We treat PlayerRef the same way we would treat things like an iterator, or views that include iterators. The Rule: Store Handles, Use Refs.

Remember, our proxy is just another type - we can structure it any way we want. We can replace our raw data access with getters and setters that contain custom logic, and those functions can even call back to the PlayerStorage if needed.

We can also use the preprocessor to ensure all these additional checks only happen in development builds. In release mode, they can be removed, returning us to our small, zero-cost abstraction:

1#if defined(_DEBUG)
2  #define ENABLE_GENERATION_CHECKS 1
3#endif
4
5struct PlayerRef {
6  // In Debug: Accessors check validity
7  // In Release: Accessors are simple inlined pointer dereferences
8  int& id() { Validate(); return *m_id_ptr; }
9  int& score() { Validate(); return *m_score_ptr; }
10  float& health() { Validate(); return *m_health_ptr; }
11  std::string& name() { Validate(); return *m_name_ptr; }
12  
13private:
14  // Pointers to the actual data in the PlayerStorage's vectors
15  int* m_id_ptr;
16  int* m_score_ptr;
17  float* m_health_ptr;
18  std::string* m_name_ptr;
19  
20  // In Debug: Add additional fields to support validation checks
21#if ENABLE_GENERATION_CHECKS
22  const int* m_current_generation_ptr;
23  int m_expected_generation;
24#endif
25
26  // In Debug: Run validation checks on all data access
27  // In Release: This compiles away to nothing
28  inline void Validate() const {
29#if ENABLE_GENERATION_CHECKS
30    if (*m_current_generation_ptr != m_expected_generation) {
31      throw std::runtime_error("Stale PlayerRef Access");
32    }
33#endif
34  }
35  
36  friend class PlayerStorage;
37  
38  PlayerRef(
39    int* id_p, int* score_p,
40    float* health_p, std::string* name_p,
41    const int* current_gen_p, int expected_gen
42  ) : m_id_ptr(id_p), m_score_ptr(score_p),
43      m_health_ptr(health_p), m_name_ptr(name_p)
44      // In Debug: Construct additional fields
45#if ENABLE_GENERATION_CHECKS
46      , m_current_generation_ptr(current_gen_p)
47      , m_expected_generation(expected_gen)
48#endif
49    {}
50};

Inverting Control

We can also prevent retention by inverting control. Rather than providing an object for consumers to apply logic to outside of our system, they can instead provide the logic to our system, and we control how it is applied. That might look something like this:

1// Usage example
2storage.Modify(some_player_handle, [](PlayerRef p) {
3  p.health -= 10;
4  p.score += 100;
5});

We could implement it like this:

1class PlayerStorage {
2public:
3  // ...
4  
5  // Instead of returning Ref, accept a visitor
6  // Return true if the modification was successful
7  bool Modify(PlayerID id, auto&& visitor) {
8    // 1. Validate Handle (Bounds + Generation)
9    if (id.index >= size() || 
10        m_generations[id.index] != id.generation || 
11        m_alive[id.index] == 0
12    ) {
13      return false; // Handle invalid
14    }
15
16    // 2. Create the View
17    PlayerRef ref {
18      m_ids[id.index], m_scores[id.index], 
19      m_health[id.index], m_names[id.index] 
20    };
21
22    // 3. Apply the provided logic
23    visitor(ref);
24    
25    return true;
26  }
27};

In this pattern, we also often provide a ForEach() function to replace iteration, further reinforcing that we don't expect PlayerRef proxies to be stored outside of our system. Consumers provide the logic, and our system applies the function to all of our entities:

1storage.ForEach([](PlayerRef p) {
2  std::cout << p.name << '\n';
3});

In this lesson, we fully addressed the problem of address stability by implementing generational indices and handles.

This involves adding a version number (m_generations) to every slot, letting us distinguish between "Slot 5 (Alice)" and "Slot 5 (Bob)".

To interact with the system, we provide consumers with handles that encapsulated the {Index, Generation} pair into a PlayerID struct, providing a safe, persistent reference to our entities.

This pattern - generational indices into a structure of arrays - gives us a stable, high-performance foundation to build on.