diff options
author | Luke Shumaker <lukeshu@lukeshu.com> | 2022-07-15 20:27:50 -0600 |
---|---|---|
committer | Luke Shumaker <lukeshu@lukeshu.com> | 2022-07-27 23:33:25 -0600 |
commit | 3aed2695a3edfba7c5d95ab86b8854cc1b6dc6a8 (patch) | |
tree | 538c108ce8cc44535e3f30d9dabeaa0ff59cee84 /lib/btrfs/io3_btree.go | |
parent | 7b7968e2f0cff9da2e74100e3f4fbaa2c86f3980 (diff) |
add binary search tools to lib/slices
Diffstat (limited to 'lib/btrfs/io3_btree.go')
-rw-r--r-- | lib/btrfs/io3_btree.go | 46 |
1 files changed, 14 insertions, 32 deletions
diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index ca528d7..73f9804 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -433,19 +433,11 @@ func (fs *FS) treeSearch(treeRoot TreeRoot, fn func(Key, uint32) int) (TreePath, // // There may or may not be a value that returns '0'. // - // Implement this search as a binary search. - lastGood := -1 - firstBad := len(node.Data.BodyInternal) - for firstBad > lastGood+1 { - midpoint := (lastGood + firstBad) / 2 - direction := fn(node.Data.BodyInternal[midpoint].Key, math.MaxUint32) - if direction < 0 { - firstBad = midpoint - } else { - lastGood = midpoint - } - } - if lastGood < 0 { + // i.e. find the highest value that isn't too high. + lastGood, ok := slices.SearchHighest(node.Data.BodyInternal, func(kp KeyPointer) int { + return slices.Min(fn(kp.Key, math.MaxUint32), 0) // don't return >0; a key can't be "too low" + }) + if !ok { return TreePath{}, nil, iofs.ErrNotExist } path = path.Append(TreePathElem{ @@ -466,26 +458,16 @@ func (fs *FS) treeSearch(treeRoot TreeRoot, fn func(Key, uint32) int) (TreePath, // is returned. // // Implement this search as a binary search. - beg := 0 - end := len(node.Data.BodyLeaf) - for beg < end { - midpoint := (beg + end) / 2 - direction := fn( - node.Data.BodyLeaf[midpoint].Key, - node.Data.BodyLeaf[midpoint].BodySize) - switch { - case direction < 0: - end = midpoint - case direction > 0: - beg = midpoint + 1 - case direction == 0: - path = path.Append(TreePathElem{ - ItemIdx: midpoint, - }) - return path, node, nil - } + idx, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int { + return fn(item.Key, item.BodySize) + }) + if !ok { + return TreePath{}, nil, iofs.ErrNotExist } - return TreePath{}, nil, iofs.ErrNotExist + path = path.Append(TreePathElem{ + ItemIdx: idx, + }) + return path, node, nil } } } |