[SortedCollections] Fix incorrect offset calculation in BTree.findAnyIndex#506
Merged
lorentey merged 2 commits intoapple:mainfrom Aug 18, 2025
Merged
[SortedCollections] Fix incorrect offset calculation in BTree.findAnyIndex#506lorentey merged 2 commits intoapple:mainfrom
lorentey merged 2 commits intoapple:mainfrom
Conversation
`findAnyIndex(forKey:)` miscomputed the global offset when a key was found in an internal B-tree node, due to missing child subtree counts in the calculation.
Member
|
@swift-ci test |
1 similar comment
Member
|
@swift-ci test |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This PR fixes an issue where
findAnyIndex(forKey:)could return anIndexwith an incorrect global offset when the matching key was found in an internal B-tree node. While the key lookup itself was correct, the reported offset undercounted the number of elements before the match.The root cause was that the offset calculation only added the number of preceding keys in the node but did not include the sizes of the preceding child subtrees, including the child at
keySlot, which in in-order traversal all come before the matching key.This PR ensures the calculation to also include the sizes of all child subtrees up to and including
handle[childAt: keySlot]when the match is found in an internal node. This ensuresIndex.offsetalways matches the true in-order position, keeping index-based operations consistent.Resolves #138, resolves #366
Checklist