shithub: furgit

Download patch

ref: 22f7dcbf39e064de83ba56ed2aaf20bd64b239aa
parent: 15913e07963cb12ee3ef9384a17b378d932d9fdd
author: Runxi Yu <runxiyu@umich.edu>
date: Mon Mar 30 02:00:15 EDT 2026 

object/tree: Why wasn't I binary searching for remove


--- a/object/tree/entry.go
+++ b/object/tree/entry.go
@@ -17,11 +17,8 @@
 }
 
 func (tree *Tree) entry(name []byte, searchIsTree bool) *TreeEntry {
-	index, ok := slices.BinarySearchFunc(tree.Entries, treeEntrySearch{
-		name:   name,
-		isTree: searchIsTree,
-	}, func(entry TreeEntry, search treeEntrySearch) int {
-		return TreeEntryNameCompare(entry.Name, entry.Mode, search.name, search.isTree)
+	index, ok := slices.BinarySearchFunc(tree.Entries, name, func(entry TreeEntry, name []byte) int {
+		return TreeEntryNameCompare(entry.Name, entry.Mode, name, searchIsTree)
 	})
 	if !ok {
 		return nil
@@ -35,7 +32,26 @@
 	return entry
 }
 
-type treeEntrySearch struct {
-	name   []byte
-	isTree bool
+func (tree *Tree) entryIndex(name []byte) (int, bool) {
+	index, ok := tree.entryIndexWithMode(name, true)
+	if ok {
+		return index, true
+	}
+
+	return tree.entryIndexWithMode(name, false)
+}
+
+func (tree *Tree) entryIndexWithMode(name []byte, searchIsTree bool) (int, bool) {
+	index, ok := slices.BinarySearchFunc(tree.Entries, name, func(entry TreeEntry, name []byte) int {
+		return TreeEntryNameCompare(entry.Name, entry.Mode, name, searchIsTree)
+	})
+	if !ok {
+		return 0, false
+	}
+
+	if !bytes.Equal(tree.Entries[index].Name, name) {
+		return 0, false
+	}
+
+	return index, true
 }
--- a/object/tree/insert.go
+++ b/object/tree/insert.go
@@ -15,11 +15,8 @@
 
 	newEntry.Name = append([]byte(nil), newEntry.Name...)
 
-	insertAt, _ := slices.BinarySearchFunc(tree.Entries, treeEntrySearch{
-		name:   newEntry.Name,
-		isTree: newEntry.Mode == FileModeDir,
-	}, func(entry TreeEntry, search treeEntrySearch) int {
-		return TreeEntryNameCompare(entry.Name, entry.Mode, search.name, search.isTree)
+	insertAt, _ := slices.BinarySearchFunc(tree.Entries, newEntry.Name, func(entry TreeEntry, name []byte) int {
+		return TreeEntryNameCompare(entry.Name, entry.Mode, name, newEntry.Mode == FileModeDir)
 	})
 	tree.Entries = slices.Insert(tree.Entries, insertAt, newEntry)
 
--- a/object/tree/lookup.go
+++ b/object/tree/lookup.go
@@ -9,9 +9,10 @@
 		return nil
 	}
 
-	if e := tree.entry(name, true); e != nil {
-		return e
+	index, ok := tree.entryIndex(name)
+	if !ok {
+		return nil
 	}
 
-	return tree.entry(name, false)
+	return &tree.Entries[index]
 }
--- a/object/tree/remove.go
+++ b/object/tree/remove.go
@@ -1,7 +1,6 @@
 package tree
 
 import (
-	"bytes"
 	"fmt"
 	"slices"
 )
@@ -12,14 +11,12 @@
 		return fmt.Errorf("object: tree: entry %q not found", name)
 	}
 
-	index := slices.IndexFunc(tree.Entries, func(entry TreeEntry) bool {
-		return bytes.Equal(entry.Name, name)
-	})
-	if index >= 0 {
-		tree.Entries = slices.Delete(tree.Entries, index, index+1)
-
-		return nil
+	index, ok := tree.entryIndex(name)
+	if !ok {
+		return fmt.Errorf("object: tree: entry %q not found", name)
 	}
 
-	return fmt.Errorf("object: tree: entry %q not found", name)
+	tree.Entries = slices.Delete(tree.Entries, index, index+1)
+
+	return nil
 }
-- 
⑨