attaswift/BTree

Strict index invalidation using a mutation counter

lorentey opened this issue · 0 comments

Most mutations are supposed to invalidate all existing indices, but BTreeIndex only detects invalidation when a mutation deallocates a node that was weakly referenced by the index, or when a slot on the index's path becomes out of bounds.

Make index invalidation strict by storing a mutation count in each node, and making indices verify that the count hasn't changed. The root node needs to be updated for most mutations, so it would be enough to compare its mutation count with the one stored in the index.

Incrementing the mutation count can be done in makeUnique/makeChildUnique, whenever an existing node is reused.

This work could prepare for a potential change that replaces weak references in indices with unowned(unsafe) ones, making indices faster.