-
Notifications
You must be signed in to change notification settings - Fork 649
/
window.go
119 lines (100 loc) · 2.74 KB
/
window.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
// Copyright (C) 2019-2021, Ava Labs, Inc. All rights reserved.
// See the file LICENSE for licensing terms.
package window
import (
"sync"
"time"
"github.com/ava-labs/avalanchego/utils/timer/mockable"
)
// Window is an interface which represents a sliding window of elements.
type Window struct {
// mocked clock for unit testing
clock *mockable.Clock
// time-to-live for elements in the window
ttl time.Duration
// max amount of elements allowed in the window
maxSize int
// mutex for synchronization
lock sync.Mutex
// elements in the window
window []node
// head/tail pointers to mark occupied parts of the window
head, tail int
// how many elements are currently in the window
size int
}
// Config exposes parameters for Window
type Config struct {
Clock *mockable.Clock
MaxSize int
TTL time.Duration
}
// New returns an instance of window
func New(config Config) *Window {
return &Window{
clock: config.Clock,
ttl: config.TTL,
maxSize: config.MaxSize,
window: make([]node, config.MaxSize),
}
}
// Add adds an element to a window and also evicts any elements if they've been
// present in the window beyond the configured time-to-live
func (w *Window) Add(value interface{}) {
w.lock.Lock()
defer w.lock.Unlock()
w.removeStaleNodes()
if w.size >= w.maxSize {
w.removeOldestNode()
}
// add the new block id
w.window[w.tail] = node{
value: value,
entryTime: w.clock.Time(),
}
w.tail = (w.tail + 1) % len(w.window)
w.size++
}
// Oldest returns the oldest element in the window.
func (w *Window) Oldest() (interface{}, bool) {
w.lock.Lock()
defer w.lock.Unlock()
w.removeStaleNodes()
if w.size == 0 {
return nil, false
}
// fetch the oldest element
return w.window[w.head].value, true
}
// Length returns the number of elements in the window.
func (w *Window) Length() int {
w.lock.Lock()
defer w.lock.Unlock()
w.removeStaleNodes()
return w.size
}
// removeStaleNodes removes any nodes beyond the configured ttl of a window node.
func (w *Window) removeStaleNodes() {
// If we're beyond the expiry threshold, removeStaleNodes this node from our
// window. Nodes are guaranteed to be strictly increasing in entry time,
// so we can break this loop once we find the first non-stale one.
for w.size > 0 {
if w.clock.Time().Sub(w.window[w.head].entryTime) <= w.ttl {
break
}
w.removeOldestNode()
}
}
// Removes the oldest element.
// Doesn't actually remove anything, just marks that location in memory
// as available to overwrite.
func (w *Window) removeOldestNode() {
w.window[w.head].value = nil // mark for garbage collection
w.head = (w.head + 1) % len(w.window)
w.size--
}
// helper struct to represent elements in the window
type node struct {
value interface{}
entryTime time.Time
}