swift-collections icon indicating copy to clipboard operation
swift-collections copied to clipboard

Incorrect calculating offset for _BTree.findAnyIndex(forKey: Key)

Open vsviridov123 opened this issue 3 months ago • 0 comments

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.

vsviridov123 avatar Mar 13 '24 11:03 vsviridov123