Question: Visiting each key during mutations
adamsch1 opened this issue · 2 comments
Not an issue but a question. Oh and thanks for releasing a really excellent project. Great code!
Ideally I'd like to iterate through the entire trie, say a few hundred keys at a time. However iterators are invalidated after a mutation, so I was thinking of just recording the last few keys one visited then pick up where you left off. What do you think? You might get unlucky and get your key deleted so I was thinking of keeping a random set from the last iteration. It doesn't matter for me if you visit a key twice.
Any other ideas?
It's difficult to walk down the hat-trie while mutating it.
The main problem is the hash nodes which can be either rehashed when we insert a value or be burst into multiple hash nodes if they become too big. Both operations will invalidate all the iterators in the hash node.
If you keep a random set of iterators, I'm not sure how you'll be able to determine which ones are still valid.
One way would be to potentially save the parent trie node of a hash node and start again from there after a mutation. Or temporarily disable the rehash and burst while we iterate and mutate (and force it in some way after).
I appreciate your response Tessil. Ya the best thing I can think of is to maintain a random sample of keys and then on the next walk continue from one of those keys on the hopes that it's not deleted. Seems about the best one can do. I will close this issue and do appreciate your response and repo.