apple / swift-collections

Commonly used data structures for Swift
Apache License 2.0
3.55k stars 270 forks source link

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

Open vsviridov123 opened 2 months ago

vsviridov123 commented 2 months ago

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

Checklist

Expected behavior

Offset calculates with children’s depth for slots before founded slot.