Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Strict index invalidation using a mutation counter #7

Open
lorentey opened this issue Mar 7, 2016 · 0 comments
Open

Strict index invalidation using a mutation counter #7

lorentey opened this issue Mar 7, 2016 · 0 comments
Milestone

Comments

@lorentey
Copy link
Collaborator

lorentey commented Mar 7, 2016

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant