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
137
138
139
140
141
|
package fzf
import "sync"
// Chunk is a list of Items whose size has the upper limit of chunkSize
type Chunk struct {
items [chunkSize]Item
count int
}
// ItemBuilder is a closure type that builds Item object from byte array
type ItemBuilder func(*Item, []byte) bool
// ChunkList is a list of Chunks
type ChunkList struct {
chunks []*Chunk
mutex sync.Mutex
trans ItemBuilder
cache *ChunkCache
}
// NewChunkList returns a new ChunkList
func NewChunkList(cache *ChunkCache, trans ItemBuilder) *ChunkList {
return &ChunkList{
chunks: []*Chunk{},
mutex: sync.Mutex{},
trans: trans,
cache: cache}
}
func (c *Chunk) push(trans ItemBuilder, data []byte) bool {
if trans(&c.items[c.count], data) {
c.count++
return true
}
return false
}
// IsFull returns true if the Chunk is full
func (c *Chunk) IsFull() bool {
return c.count == chunkSize
}
func (c *Chunk) lastIndex(minValue int32) int32 {
if c.count == 0 {
return minValue
}
return c.items[c.count-1].Index() + 1 // Exclusive
}
func (cl *ChunkList) lastChunk() *Chunk {
return cl.chunks[len(cl.chunks)-1]
}
// CountItems returns the total number of Items
func CountItems(cs []*Chunk) int {
if len(cs) == 0 {
return 0
}
if len(cs) == 1 {
return cs[0].count
}
// First chunk might not be full due to --tail=N
return cs[0].count + chunkSize*(len(cs)-2) + cs[len(cs)-1].count
}
// Push adds the item to the list
func (cl *ChunkList) Push(data []byte) bool {
cl.mutex.Lock()
if len(cl.chunks) == 0 || cl.lastChunk().IsFull() {
cl.chunks = append(cl.chunks, &Chunk{})
}
ret := cl.lastChunk().push(cl.trans, data)
cl.mutex.Unlock()
return ret
}
// Clear clears the data
func (cl *ChunkList) Clear() {
cl.mutex.Lock()
cl.chunks = nil
cl.mutex.Unlock()
}
// Snapshot returns immutable snapshot of the ChunkList
func (cl *ChunkList) Snapshot(tail int) ([]*Chunk, int, bool) {
cl.mutex.Lock()
changed := false
if tail > 0 && CountItems(cl.chunks) > tail {
changed = true
// Find the number of chunks to keep
numChunks := 0
for left, i := tail, len(cl.chunks)-1; left > 0 && i >= 0; i-- {
numChunks++
left -= cl.chunks[i].count
}
// Copy the chunks to keep
ret := make([]*Chunk, numChunks)
minIndex := len(cl.chunks) - numChunks
cl.cache.retire(cl.chunks[:minIndex]...)
copy(ret, cl.chunks[minIndex:])
for left, i := tail, len(ret)-1; i >= 0; i-- {
chunk := ret[i]
if chunk.count > left {
newChunk := *chunk
newChunk.count = left
oldCount := chunk.count
for i := 0; i < left; i++ {
newChunk.items[i] = chunk.items[oldCount-left+i]
}
ret[i] = &newChunk
cl.cache.retire(chunk)
break
}
left -= chunk.count
}
cl.chunks = ret
}
ret := make([]*Chunk, len(cl.chunks))
copy(ret, cl.chunks)
// Duplicate the first and the last chunk
if cnt := len(ret); cnt > 0 {
if tail > 0 && cnt > 1 {
newChunk := *ret[0]
ret[0] = &newChunk
}
newChunk := *ret[cnt-1]
ret[cnt-1] = &newChunk
}
cl.mutex.Unlock()
return ret, CountItems(ret), changed
}
|
