Skip to content

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

Open
@martin9iden

Description

@martin9iden

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

  • 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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions