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
126
127
128
129
130
131
132
133
134
135
136
|
package packed
// packCandidateNode is one node in the candidate MRU order list.
type packCandidateNode struct {
packName string
prev *packCandidateNode
next *packCandidateNode
}
func (store *Store) reconcileMRU(candidates []packCandidate) {
store.mruMu.Lock()
defer store.mruMu.Unlock()
if store.mruNodeByPack == nil {
store.mruNodeByPack = make(map[string]*packCandidateNode, len(candidates))
}
present := make(map[string]struct{}, len(candidates))
for _, candidate := range candidates {
present[candidate.packName] = struct{}{}
}
ordered := make([]string, 0, len(candidates))
for node := store.mruHead; node != nil; node = node.next {
if _, ok := present[node.packName]; !ok {
continue
}
ordered = append(ordered, node.packName)
delete(present, node.packName)
}
for _, candidate := range candidates {
if _, ok := present[candidate.packName]; !ok {
continue
}
ordered = append(ordered, candidate.packName)
delete(present, candidate.packName)
}
store.mruHead = nil
store.mruTail = nil
store.mruNodeByPack = make(map[string]*packCandidateNode, len(ordered))
for _, packName := range ordered {
node := &packCandidateNode{
packName: packName,
prev: store.mruTail,
}
if store.mruTail != nil {
store.mruTail.next = node
}
if store.mruHead == nil {
store.mruHead = node
}
store.mruTail = node
store.mruNodeByPack[packName] = node
}
}
// touchCandidate moves one candidate to the front of the lookup order.
// This is done on a best-effort basis.
func (store *Store) touchCandidate(packName string) {
if !store.mruMu.TryLock() {
return
}
defer store.mruMu.Unlock()
node := store.mruNodeByPack[packName]
if node == nil || node == store.mruHead {
return
}
if node.prev != nil {
node.prev.next = node.next
}
if node.next != nil {
node.next.prev = node.prev
}
if store.mruTail == node {
store.mruTail = node.prev
}
node.prev = nil
node.next = store.mruHead
if store.mruHead != nil {
store.mruHead.prev = node
}
store.mruHead = node
if store.mruTail == nil {
store.mruTail = node
}
}
// firstCandidatePackName returns the current head pack name, or "" when none
// are available.
func (store *Store) firstCandidatePackName(snapshot *candidateSnapshot) string {
store.mruMu.RLock()
defer store.mruMu.RUnlock()
for node := store.mruHead; node != nil; node = node.next {
if _, ok := snapshot.candidateByPack[node.packName]; ok {
return node.packName
}
}
return ""
}
// nextCandidatePackName returns the pack name after currentPack in current MRU
// order, or "" at end / when currentPack is not present.
func (store *Store) nextCandidatePackName(currentPack string, snapshot *candidateSnapshot) string {
store.mruMu.RLock()
defer store.mruMu.RUnlock()
node := store.mruNodeByPack[currentPack]
if node == nil {
return ""
}
for node = node.next; node != nil; node = node.next {
if _, ok := snapshot.candidateByPack[node.packName]; ok {
return node.packName
}
}
return ""
}
|
