forked from kubernetes/kubernetes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
timed_store.go
137 lines (120 loc) · 4.02 KB
/
timed_store.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
// Copyright 2014 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package utils
import (
"sort"
"time"
)
// A time-based buffer for ContainerStats. Holds information for a specific time period.
type TimedStore struct {
buffer []timedStoreData
age time.Duration
}
type timedStoreData struct {
timestamp time.Time
data interface{}
}
// Returns a new thread-compatible TimedStore.
func NewTimedStore(age time.Duration) *TimedStore {
return &TimedStore{
buffer: make([]timedStoreData, 0),
age: age,
}
}
// Adds an element to the start of the buffer (removing one from the end if necessary).
func (self *TimedStore) Add(timestamp time.Time, item interface{}) {
// Remove any elements before the eviction time.
evictTime := timestamp.Add(-self.age)
index := sort.Search(len(self.buffer), func(index int) bool {
return self.buffer[index].timestamp.After(evictTime)
})
if index < len(self.buffer) {
self.buffer = self.buffer[index:]
}
copied := item
self.buffer = append(self.buffer, timedStoreData{
timestamp: timestamp,
data: copied,
})
}
// Returns up to maxResult elements in the specified time period (inclusive).
// Results are from first to last. maxResults of -1 means no limit. When first
// and last are specified, maxResults is ignored.
func (self *TimedStore) InTimeRange(start, end time.Time, maxResults int) []interface{} {
// No stats, return empty.
if len(self.buffer) == 0 {
return []interface{}{}
}
// Return all results in a time range if specified.
if !start.IsZero() && !end.IsZero() {
maxResults = -1
}
// NOTE: Since we store the elments in descending timestamp order "start" will
// be a higher index than "end".
var startIndex int
if start.IsZero() {
// None specified, start at the beginning.
startIndex = len(self.buffer) - 1
} else {
// Start is the index before the elements smaller than it. We do this by
// finding the first element smaller than start and taking the index
// before that element
startIndex = sort.Search(len(self.buffer), func(index int) bool {
// buffer[index] < start
return self.getData(index).timestamp.Before(start)
}) - 1
// Check if start is after all the data we have.
if startIndex < 0 {
return []interface{}{}
}
}
var endIndex int
if end.IsZero() {
// None specified, end with the latest stats.
endIndex = 0
} else {
// End is the first index smaller than or equal to it (so, not larger).
endIndex = sort.Search(len(self.buffer), func(index int) bool {
// buffer[index] <= t -> !(buffer[index] > t)
return !self.getData(index).timestamp.After(end)
})
// Check if end is before all the data we have.
if endIndex == len(self.buffer) {
return []interface{}{}
}
}
// Trim to maxResults size.
numResults := startIndex - endIndex + 1
if maxResults != -1 && numResults > maxResults {
startIndex -= numResults - maxResults
numResults = maxResults
}
// Return in sorted timestamp order so from the "back" to "front".
result := make([]interface{}, numResults)
for i := 0; i < numResults; i++ {
result[i] = self.Get(startIndex - i)
}
return result
}
// Gets the element at the specified index. Note that elements are output in LIFO order.
func (self *TimedStore) Get(index int) interface{} {
return self.getData(index).data
}
// Gets the data at the specified index. Note that elements are output in LIFO order.
func (self *TimedStore) getData(index int) timedStoreData {
return self.buffer[len(self.buffer)-index-1]
}
func (self *TimedStore) Size() int {
return len(self.buffer)
}