/
mem_only_run_log.go
208 lines (170 loc) · 4.63 KB
/
mem_only_run_log.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
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
package jobfile
import (
"fmt"
"sort"
"time"
)
/*
This is an impl of RunLog that is not backed by a file. In order to
avoid running out of memory, it has a max length, after which it starts
throwing out the oldest entries.
*/
type memOnlyRunLog struct {
/*
We need to support method Get, which returns entries in
descending start-time order. We also need to support method
Put, which will usually be called in ASCENDING start-time order.
Moreover, Put will be called more frequently than Get.
Will keep a list of entries in ascending start-time order,
which means that Put will usually run in constant-time.
*/
entries []*RunLogEntry
}
func (self *memOnlyRunLog) String() string {
return fmt.Sprintf(
"MemRunLog{maxLen: %v}",
cap(self.entries),
)
}
func NewMemOnlyRunLog(maxLen int) RunLog {
if maxLen <= 0 {
panic("maxLen must be > 0")
}
log := memOnlyRunLog{
entries: make([]*RunLogEntry, 0, maxLen),
}
return &log
}
func (self *memOnlyRunLog) MaxLen() int {
return cap(self.entries)
}
func (self *memOnlyRunLog) Put(newEntry RunLogEntry) error {
/*
If the entries array would be too long after inserting the new
entry, we need to remove an entry first. We remove the oldest
entry.
Remember: self.entries is sorted in ascending order.
*/
// assertions
if cap(self.entries) == 0 {
panic("Capacity is 0")
}
if len(self.entries)+1 > cap(self.entries) {
// if the new entry is older than any other, do nothing
if newEntry.Time.Before(self.entries[0].Time) {
return nil
} else {
// remove oldest entry
copy(self.entries, self.entries[1:])
self.entries = self.entries[:len(self.entries)-1]
}
}
// add the entry
self.entries = append(self.entries, &newEntry)
// make sure the array is sorted
for i := len(self.entries) - 1; i >= 1; i-- {
if newEntry.Time.Before(self.entries[i-1].Time) {
// swap
self.entries[i-1], self.entries[i] =
self.entries[i], self.entries[i-1]
} else {
break
}
}
return nil
}
func reverseEntryArray(array []*RunLogEntry) []*RunLogEntry {
result := make([]*RunLogEntry, len(array))
i := 0
for j := len(array) - 1; j >= 0; j-- {
result[i] = array[j]
i++
}
return result
}
func (self *memOnlyRunLog) GetFromTime(maxTime time.Time,
timeArr ...time.Time) ([]*RunLogEntry, error) {
/*
Let [e_0, ..., e_n] be the (ascending-ordered) list of entries
(self.entries).
We must return a descending-ordered sublist of entries
[e_j, ..., e_i] (j <= i) s.t.
- e_j.Time < to
- e_(j+1).Time >= to
- e_i.Time >= from
- e_(i-1).Time < from
*/
if len(timeArr) > 1 {
panic("Too many args.")
}
if len(self.entries) == 0 {
return []*RunLogEntry{}, nil
}
var minTime time.Time
if len(timeArr) >= 1 {
minTime = timeArr[0]
} else {
// set *minTime* to just before the earliest entry's start time
minTime = self.entries[0].Time.Add(-time.Second)
}
if maxTime.Before(minTime) {
panic("maxTime is before minTime")
}
// do binary search to find beginning of range
startIdx := sort.Search(len(self.entries), func(i int) bool {
return !self.entries[i].Time.Before(maxTime)
})
if startIdx == len(self.entries) {
return []*RunLogEntry{}, nil
}
// do binary search to find end of range
endIdx := sort.Search(len(self.entries), func(i int) bool {
return self.entries[i].Time.After(minTime)
})
// return in reverse order
return reverseEntryArray(self.entries[endIdx : startIdx+1]), nil
}
func (self *memOnlyRunLog) GetFromIndex(minIdx int, idxArr ...int) (
[]*RunLogEntry, error) {
/*
Remember: self.entries is sorted in ascending order. But we
must return in descending order.
*/
if len(idxArr) > 1 {
panic("Too many args.")
}
var maxIdx int
if len(idxArr) >= 1 {
maxIdx = idxArr[0]
} else {
maxIdx = len(self.entries)
}
if minIdx > maxIdx {
panic("minIdx > maxIdx")
}
if minIdx >= len(self.entries) {
panic(fmt.Sprintf("Invalid 'minIdx' index: %v", minIdx))
}
if maxIdx > len(self.entries) {
panic(fmt.Sprintf("Invalid 'maxIdx' index: %v", maxIdx))
}
/*
self.entries is sorted in ascending order. We must return in
descending order.
self.entries: 0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
If from == 1 and to == 3 => (5, 7)
If from == 0 and to == 3 => (5, 8)
*/
// find entries
actualTo := len(self.entries) - minIdx
actualFrom := len(self.entries) - maxIdx
// reverse them
return reverseEntryArray(self.entries[actualFrom:actualTo]), nil
}
func (self *memOnlyRunLog) GetAll() ([]*RunLogEntry, error) {
return reverseEntryArray(self.entries), nil
}
func (self *memOnlyRunLog) Len() int {
return len(self.entries)
}