1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
package packfile
import (
"sort"
"gopkg.in/src-d/go-git.v4/plumbing"
"gopkg.in/src-d/go-git.v4/plumbing/format/idxfile"
)
// Index is an in-memory representation of a packfile index.
// This uses idxfile.Idxfile under the hood to obtain indexes from .idx files
// or to store them.
type Index struct {
byHash map[plumbing.Hash]*idxfile.Entry
byOffset []*idxfile.Entry // sorted by their offset
}
// NewIndex creates a new empty index with the given size. Size is a hint and
// can be 0. It is recommended to set it to the number of objects to be indexed
// if it is known beforehand (e.g. reading from a packfile).
func NewIndex(size int) *Index {
return &Index{
byHash: make(map[plumbing.Hash]*idxfile.Entry, size),
byOffset: make([]*idxfile.Entry, 0, size),
}
}
// NewIndexFromIdxFile creates a new Index from an idxfile.IdxFile.
func NewIndexFromIdxFile(idxf *idxfile.Idxfile) *Index {
idx := &Index{
byHash: make(map[plumbing.Hash]*idxfile.Entry, idxf.ObjectCount),
byOffset: make([]*idxfile.Entry, 0, idxf.ObjectCount),
}
sorted := true
for i, e := range idxf.Entries {
idx.addUnsorted(e)
if i > 0 && idx.byOffset[i-1].Offset >= e.Offset {
sorted = false
}
}
// If the idxfile was loaded from a regular packfile index
// then it will already be in offset order, in which case we
// can avoid doing a relatively expensive idempotent sort.
if !sorted {
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{
Hash: h,
Offset: offset,
CRC32: crc32,
}
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) addUnsorted(e *idxfile.Entry) {
idx.byHash[e.Hash] = e
idx.byOffset = append(idx.byOffset, e)
}
// LookupHash looks an entry up by its hash. An idxfile.Entry is returned and
// a bool, which is true if it was found or false if it wasn't.
func (idx *Index) LookupHash(h plumbing.Hash) (*idxfile.Entry, bool) {
e, ok := idx.byHash[h]
return e, ok
}
// 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) {
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.
func (idx *Index) Size() int {
return len(idx.byHash)
}
// ToIdxFile converts the index to an idxfile.Idxfile, which can then be used
// to serialize.
func (idx *Index) ToIdxFile() *idxfile.Idxfile {
idxf := idxfile.NewIdxfile()
for _, e := range idx.byHash {
idxf.Entries = append(idxf.Entries, e)
}
return idxf
}
|
