Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Generational slots: reject stale handles after reuse

Last updated: 3 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A generational slot store hands callers a handle containing an owning-store identity, a slot number, and that slot's generation. Removal marks the slot empty, increments its generation, and puts its number on a free list. A later insertion may reuse the same physical slot, but the earlier handle no longer matches its new generation. Looking up an old or foreign handle raises instead of returning another incident. The implementation uses a private empty marker so None can itself be stored as a value. Handles are immutable dataclass values, and the store identity is compared by object identity. This is a single-process model; handles are not serialized or valid after a store is reconstructed.

Operational case

Insert pump-47 and retain its handle. Remove it, then insert valve-19. The second incident reuses the freed array position, yet its generation differs, so the old pump handle fails lookup and the new valve handle succeeds. A handle from another store also fails even if slot and generation happen to match. Without generations, recycling slot zero would let a stale caller silently read valve-19 as though it were pump-47. The example's unbounded Python integer generations avoid wraparound in ordinary execution, while fixed-width production implementations need an explicit overflow policy.

Working Python program

python
from dataclasses import dataclass


_EMPTY = object()


@dataclass(frozen=True)
class IncidentHandle:
    owner: object
    slot: int
    generation: int


class IncidentSlotStore:
    def __init__(self):
        self.owner = object()
        self.values = []
        self.generations = []
        self.free = []

    def insert(self, incident):
        if self.free:
            slot = self.free.pop()
            self.values[slot] = incident
        else:
            slot = len(self.values)
            self.values.append(incident)
            self.generations.append(0)
        return IncidentHandle(self.owner, slot, self.generations[slot])

    def get(self, handle):
        if (handle.owner is not self.owner or not 0 <= handle.slot < len(self.values)
                or handle.generation != self.generations[handle.slot]
                or self.values[handle.slot] is _EMPTY):
            raise KeyError("stale or foreign incident handle")
        return self.values[handle.slot]

    def remove(self, handle):
        incident = self.get(handle)
        self.values[handle.slot] = _EMPTY
        self.generations[handle.slot] += 1
        self.free.append(handle.slot)
        return incident


if __name__ == "__main__":
    store = IncidentSlotStore()
    old_handle = store.insert("pump-47")
    store.remove(old_handle)
    new_handle = store.insert("valve-19")
    print("same-slot=", old_handle.slot == new_handle.slot, sep="")
    print("new=", store.get(new_handle), sep="")
    try:
        store.get(old_handle)
    except KeyError:
        print("old=stale")

Output

Output
same-slot=True
new=valve-19
old=stale

Time, space, and tradeoff

Insertion, lookup, and removal take O(1) list operations in the normal model; free-list push and pop are O(1), and memory is O(S) for S slots ever allocated until an explicit compaction design is added. Removed slots are reused, but the backing arrays do not shrink. A handle stores three fields, including an owner token, so it costs more than a raw integer index. Operations on Python's growing generation integers have bit-length cost beyond a fixed-width model. This design prevents stale-slot aliasing within one live store, but does not provide thread synchronization, durable IDs, garbage collection, or a safe strategy for serialized handles crossing process lifetimes.

Common Mistakes

  • Do not reuse a slot without advancing its generation.
  • Do not accept a handle from a different store instance.
  • Do not use None as an empty marker when None is a valid stored value.
  • Do not serialize this in-memory owner token as a durable identity.

Connected lessons

Compare its invariant with LFU caches: evict by frequency, then recency, Expiry heaps: invalidate stale TTL records on replacement, D-ary heaps: trade shallower ascent for wider extraction, then run the retention and dispatch audit and operation quiz.

Checkpoint arenas: reclaim a region by lifetime extends the storage ownership comparison.

Slab slots: reuse fixed-size pages with generation checks extends the storage ownership comparison.

data structures
range-query-structures
Storage details