swift-collections
swift-collections copied to clipboard
Incorrect calculating offset for _BTree.findAnyIndex(forKey: Key)
Incorrect calculating offset for _BTree.findAnyIndex(forKey: Key) (347 line)
Hi, i use SortedDictionary for my project and I may found an error. In function _Btree.findAnyIndex. If there is a slot equal to key, offset does not take into account children’s depth for slots before founded slot.
let keySlot = handle.startSlot(forKey: key)
offset += keySlot
if keySlot < handle.elementCount && handle[keyAt: keySlot] == key {
return Index(
node: .passUnretained(storage),
slot: keySlot,
childSlots: childSlots,
offset: offset,
forTree: self
)
}
Information
- Package version: main branch
- Platform version: 17.0
- Swift version: 5.9
Checklist
- [x] If possible, I've reproduced the issue using the
main
branch of this package. - [ ] I've searched for existing GitHub issues.
Expected behavior
Offset calculates with children’s depth for slots before founded slot.