aboutsummaryrefslogtreecommitdiffstats
path: root/storage/filesystem/dotgit
diff options
context:
space:
mode:
Diffstat (limited to 'storage/filesystem/dotgit')
-rw-r--r--storage/filesystem/dotgit/dotgit.go77
-rw-r--r--storage/filesystem/dotgit/dotgit_test.go35
2 files changed, 109 insertions, 3 deletions
diff --git a/storage/filesystem/dotgit/dotgit.go b/storage/filesystem/dotgit/dotgit.go
index 3840ea7..6c386f7 100644
--- a/storage/filesystem/dotgit/dotgit.go
+++ b/storage/filesystem/dotgit/dotgit.go
@@ -3,12 +3,14 @@ package dotgit
import (
"bufio"
+ "bytes"
"errors"
"fmt"
"io"
stdioutil "io/ioutil"
"os"
"path/filepath"
+ "sort"
"strings"
"time"
@@ -88,7 +90,7 @@ type DotGit struct {
incomingChecked bool
incomingDirName string
- objectList []plumbing.Hash
+ objectList []plumbing.Hash // sorted
objectMap map[plumbing.Hash]struct{}
packList []plumbing.Hash
packMap map[plumbing.Hash]struct{}
@@ -336,6 +338,53 @@ func (d *DotGit) NewObject() (*ObjectWriter, error) {
return newObjectWriter(d.fs)
}
+// ObjectsWithPrefix returns the hashes of objects that have the given prefix.
+func (d *DotGit) ObjectsWithPrefix(prefix []byte) ([]plumbing.Hash, error) {
+ // Handle edge cases.
+ if len(prefix) < 1 {
+ return d.Objects()
+ } else if len(prefix) > len(plumbing.ZeroHash) {
+ return nil, nil
+ }
+
+ if d.options.ExclusiveAccess {
+ err := d.genObjectList()
+ if err != nil {
+ return nil, err
+ }
+
+ // Rely on d.objectList being sorted.
+ // Figure out the half-open interval defined by the prefix.
+ first := sort.Search(len(d.objectList), func(i int) bool {
+ // Same as plumbing.HashSlice.Less.
+ return bytes.Compare(d.objectList[i][:], prefix) >= 0
+ })
+ lim := len(d.objectList)
+ if limPrefix, overflow := incBytes(prefix); !overflow {
+ lim = sort.Search(len(d.objectList), func(i int) bool {
+ // Same as plumbing.HashSlice.Less.
+ return bytes.Compare(d.objectList[i][:], limPrefix) >= 0
+ })
+ }
+ return d.objectList[first:lim], nil
+ }
+
+ // This is the slow path.
+ var objects []plumbing.Hash
+ var n int
+ err := d.ForEachObjectHash(func(hash plumbing.Hash) error {
+ n++
+ if bytes.HasPrefix(hash[:], prefix) {
+ objects = append(objects, hash)
+ }
+ return nil
+ })
+ if err != nil {
+ return nil, err
+ }
+ return objects, nil
+}
+
// Objects returns a slice with the hashes of objects found under the
// .git/objects/ directory.
func (d *DotGit) Objects() ([]plumbing.Hash, error) {
@@ -427,12 +476,17 @@ func (d *DotGit) genObjectList() error {
}
d.objectMap = make(map[plumbing.Hash]struct{})
- return d.forEachObjectHash(func(h plumbing.Hash) error {
+ populate := func(h plumbing.Hash) error {
d.objectList = append(d.objectList, h)
d.objectMap[h] = struct{}{}
return nil
- })
+ }
+ if err := d.forEachObjectHash(populate); err != nil {
+ return err
+ }
+ plumbing.HashesSort(d.objectList)
+ return nil
}
func (d *DotGit) hasObject(h plumbing.Hash) error {
@@ -1115,3 +1169,20 @@ func isNum(b byte) bool {
func isHexAlpha(b byte) bool {
return b >= 'a' && b <= 'f' || b >= 'A' && b <= 'F'
}
+
+// incBytes increments a byte slice, which involves incrementing the
+// right-most byte, and following carry leftward.
+// It makes a copy so that the provided slice's underlying array is not modified.
+// If the overall operation overflows (e.g. incBytes(0xff, 0xff)), the second return parameter indicates that.
+func incBytes(in []byte) (out []byte, overflow bool) {
+ out = make([]byte, len(in))
+ copy(out, in)
+ for i := len(out) - 1; i >= 0; i-- {
+ out[i]++
+ if out[i] != 0 {
+ return // Didn't overflow.
+ }
+ }
+ overflow = true
+ return
+}
diff --git a/storage/filesystem/dotgit/dotgit_test.go b/storage/filesystem/dotgit/dotgit_test.go
index 0a72aa6..237605f 100644
--- a/storage/filesystem/dotgit/dotgit_test.go
+++ b/storage/filesystem/dotgit/dotgit_test.go
@@ -2,6 +2,7 @@ package dotgit
import (
"bufio"
+ "encoding/hex"
"io/ioutil"
"os"
"path/filepath"
@@ -591,6 +592,7 @@ func (s *SuiteDotGit) TestObjects(c *C) {
dir := New(fs)
testObjects(c, fs, dir)
+ testObjectsWithPrefix(c, fs, dir)
}
func (s *SuiteDotGit) TestObjectsExclusive(c *C) {
@@ -598,6 +600,7 @@ func (s *SuiteDotGit) TestObjectsExclusive(c *C) {
dir := NewWithOptions(fs, Options{ExclusiveAccess: true})
testObjects(c, fs, dir)
+ testObjectsWithPrefix(c, fs, dir)
}
func testObjects(c *C, fs billy.Filesystem, dir *DotGit) {
@@ -609,6 +612,20 @@ func testObjects(c *C, fs billy.Filesystem, dir *DotGit) {
c.Assert(hashes[2].String(), Equals, "03db8e1fbe133a480f2867aac478fd866686d69e")
}
+func testObjectsWithPrefix(c *C, fs billy.Filesystem, dir *DotGit) {
+ prefix, _ := hex.DecodeString("01d5")
+ hashes, err := dir.ObjectsWithPrefix(prefix)
+ c.Assert(err, IsNil)
+ c.Assert(hashes, HasLen, 1)
+ c.Assert(hashes[0].String(), Equals, "01d5fa556c33743006de7e76e67a2dfcd994ca04")
+
+ // Empty prefix should yield all objects.
+ // (subset of testObjects)
+ hashes, err = dir.ObjectsWithPrefix(nil)
+ c.Assert(err, IsNil)
+ c.Assert(hashes, HasLen, 187)
+}
+
func (s *SuiteDotGit) TestObjectsNoFolder(c *C) {
tmp, err := ioutil.TempDir("", "dot-git")
c.Assert(err, IsNil)
@@ -835,3 +852,21 @@ type norwfs struct {
func (f *norwfs) Capabilities() billy.Capability {
return billy.Capabilities(f.Filesystem) &^ billy.ReadAndWriteCapability
}
+
+func (s *SuiteDotGit) TestIncBytes(c *C) {
+ tests := []struct {
+ in []byte
+ out []byte
+ overflow bool
+ }{
+ {[]byte{0}, []byte{1}, false},
+ {[]byte{0xff}, []byte{0}, true},
+ {[]byte{7, 0xff}, []byte{8, 0}, false},
+ {[]byte{0xff, 0xff}, []byte{0, 0}, true},
+ }
+ for _, test := range tests {
+ out, overflow := incBytes(test.in)
+ c.Assert(out, DeepEquals, test.out)
+ c.Assert(overflow, Equals, test.overflow)
+ }
+}