Merge pull request #846 from dsymonds/compact

packfile: improve Index memory representation to be more compact

1 files changed, 43 insertions, 10 deletions

diff --git a/plumbing/format/packfile/index.go b/plumbing/format/packfile/index.go
index 2c5f98f..7d8f2ad 100644
--- a/plumbing/format/packfile/index.go
+++ b/plumbing/format/packfile/index.go
@@ -1,6 +1,8 @@
 package packfile
 
 import (
+	"sort"
+
 	"gopkg.in/src-d/go-git.v4/plumbing"
 	"gopkg.in/src-d/go-git.v4/plumbing/format/idxfile"
 )
@@ -10,7 +12,7 @@ import (
 // or to store them.
 type Index struct {
 	byHash   map[plumbing.Hash]*idxfile.Entry
-	byOffset map[uint64]*idxfile.Entry
+	byOffset []*idxfile.Entry // sorted by their offset
 }
 
 // NewIndex creates a new empty index with the given size. Size is a hint and
@@ -19,7 +21,7 @@ type Index struct {
 func NewIndex(size int) *Index {
 	return &Index{
 		byHash:   make(map[plumbing.Hash]*idxfile.Entry, size),
-		byOffset: make(map[uint64]*idxfile.Entry, size),
+		byOffset: make([]*idxfile.Entry, 0, size),
 	}
 }
 
@@ -27,28 +29,54 @@ func NewIndex(size int) *Index {
 func NewIndexFromIdxFile(idxf *idxfile.Idxfile) *Index {
 	idx := &Index{
 		byHash:   make(map[plumbing.Hash]*idxfile.Entry, idxf.ObjectCount),
-		byOffset: make(map[uint64]*idxfile.Entry, idxf.ObjectCount),
+		byOffset: make([]*idxfile.Entry, 0, idxf.ObjectCount),
 	}
 	for _, e := range idxf.Entries {
-		idx.add(e)
+		idx.addUnsorted(e)
 	}
+	sort.Sort(orderByOffset(idx.byOffset))
 
 	return idx
 }
 
+// orderByOffset is a sort.Interface adapter that arranges
+// a slice of entries by their offset.
+type orderByOffset []*idxfile.Entry
+
+func (o orderByOffset) Len() int           { return len(o) }
+func (o orderByOffset) Less(i, j int) bool { return o[i].Offset < o[j].Offset }
+func (o orderByOffset) Swap(i, j int)      { o[i], o[j] = o[j], o[i] }
+
 // Add adds a new Entry with the given values to the index.
 func (idx *Index) Add(h plumbing.Hash, offset uint64, crc32 uint32) {
-	e := idxfile.Entry{
+	e := &idxfile.Entry{
 		Hash:   h,
 		Offset: offset,
 		CRC32:  crc32,
 	}
-	idx.add(&e)
+	idx.byHash[e.Hash] = e
+
+	// Find the right position in byOffset.
+	// Look for the first position whose offset is *greater* than e.Offset.
+	i := sort.Search(len(idx.byOffset), func(i int) bool {
+		return idx.byOffset[i].Offset > offset
+	})
+	if i == len(idx.byOffset) {
+		// Simple case: add it to the end.
+		idx.byOffset = append(idx.byOffset, e)
+		return
+	}
+	// Harder case: shift existing entries down by one to make room.
+	// Append a nil entry first so we can use existing capacity in case
+	// the index was carefully preallocated.
+	idx.byOffset = append(idx.byOffset, nil)
+	copy(idx.byOffset[i+1:], idx.byOffset[i:len(idx.byOffset)-1])
+	idx.byOffset[i] = e
 }
 
-func (idx *Index) add(e *idxfile.Entry) {
+func (idx *Index) addUnsorted(e *idxfile.Entry) {
 	idx.byHash[e.Hash] = e
-	idx.byOffset[e.Offset] = e
+	idx.byOffset = append(idx.byOffset, e)
 }
 
 // LookupHash looks an entry up by its hash. An idxfile.Entry is returned and
@@ -61,8 +89,13 @@ func (idx *Index) LookupHash(h plumbing.Hash) (*idxfile.Entry, bool) {
 // LookupHash looks an entry up by its offset in the packfile. An idxfile.Entry
 // is returned and a bool, which is true if it was found or false if it wasn't.
 func (idx *Index) LookupOffset(offset uint64) (*idxfile.Entry, bool) {
-	e, ok := idx.byOffset[offset]
-	return e, ok
+	i := sort.Search(len(idx.byOffset), func(i int) bool {
+		return idx.byOffset[i].Offset >= offset
+	})
+	if i >= len(idx.byOffset) || idx.byOffset[i].Offset != offset {
+		return nil, false // not present
+	}
+	return idx.byOffset[i], true
 }
 
 // Size returns the number of entries in the index.