-
-
Notifications
You must be signed in to change notification settings - Fork 1.7k
/
cache.go
79 lines (65 loc) · 2 KB
/
cache.go
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
package filetree
import (
"github.com/sirupsen/logrus"
)
type TreeCacheKey struct {
bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop int
}
type TreeCache struct {
refTrees []*FileTree
cache map[TreeCacheKey]*FileTree
}
func (cache *TreeCache) Get(bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop int) *FileTree {
key := TreeCacheKey{bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop}
if value, exists := cache.cache[key]; exists {
return value
}
value := cache.buildTree(key)
cache.cache[key] = value
return value
}
func (cache *TreeCache) buildTree(key TreeCacheKey) *FileTree {
newTree := StackTreeRange(cache.refTrees, key.bottomTreeStart, key.bottomTreeStop)
for idx := key.topTreeStart; idx <= key.topTreeStop; idx++ {
err := newTree.CompareAndMark(cache.refTrees[idx])
if err != nil {
logrus.Errorf("unable to build tree: %+v", err)
}
}
return newTree
}
func (cache *TreeCache) Build() {
var bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop int
// case 1: layer compare (top tree SIZE is fixed (BUT floats forward), Bottom tree SIZE changes)
for selectIdx := 0; selectIdx < len(cache.refTrees); selectIdx++ {
bottomTreeStart = 0
topTreeStop = selectIdx
if selectIdx == 0 {
bottomTreeStop = selectIdx
topTreeStart = selectIdx
} else {
bottomTreeStop = selectIdx - 1
topTreeStart = selectIdx
}
cache.Get(bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop)
}
// case 2: aggregated compare (bottom tree is ENTIRELY fixed, top tree SIZE changes)
for selectIdx := 0; selectIdx < len(cache.refTrees); selectIdx++ {
bottomTreeStart = 0
topTreeStop = selectIdx
if selectIdx == 0 {
bottomTreeStop = selectIdx
topTreeStart = selectIdx
} else {
bottomTreeStop = 0
topTreeStart = 1
}
cache.Get(bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop)
}
}
func NewFileTreeCache(refTrees []*FileTree) TreeCache {
return TreeCache{
refTrees: refTrees,
cache: make(map[TreeCacheKey]*FileTree),
}
}