-
Notifications
You must be signed in to change notification settings - Fork 137
/
queues.go
177 lines (159 loc) · 5.31 KB
/
queues.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
package runtime
import (
"container/heap"
"sync"
"github.com/pkg/errors"
"k8s.io/apimachinery/pkg/types"
"sigs.k8s.io/controller-runtime/pkg/client"
)
// PriorityQueue is an interface for any priority queue containing
// runtime.Objects.
type PriorityQueue interface {
// Push adds a copy of the provided client.Object to the priority queue.
// Returns true if the item was added to the queue, false if it already existed
// Pushing of nil objects have no effect
Push(client.Object) bool
// Pop removes the highest priority client.Object from the priority queue and
// returns it. Implementations MUST return nil if the priority queue is empty.
Pop() client.Object
// Peek returns the highest priority client.Object from the priority queue
// without removing it.
Peek() client.Object
// Depth returns the depth of the PriorityQueue.
Depth() int
}
// ObjectCompareFn is the signature for any function that can compare the
// relative priorities of two client.Objects. Implementations MUST return true
// when the first argument is of higher priority than the second and MUST return
// false otherwise. Implementors of such functions may safely assume that
// neither argument can ever be nil.
type ObjectPriorityFn func(client.Object, client.Object) bool
// priorityQueue is an implementation of the PriorityQueue interface. This
// encapsulates the low-level details of the priority queue implementation found
// at https://pkg.go.dev/container/heap and is also safe for concurrent use by
// multiple goroutines.
type priorityQueue struct {
// internalQueue is priorityQueue's underlying data structure. It implements
// heap.Interface.
internalQueue *internalPriorityQueue
// objectsByNamespaceName is used to deduplicate pushes of the same object
// to the queue, allowing Push() to be idempotent
objectsByNamespaceName map[types.NamespacedName]bool
// mu is a mutex used to ensure only a single goroutine is executing critical
// sections of code at any time.
mu sync.RWMutex
}
// NewPriorityQueue takes a function for comparing the relative priority of two
// client.Objects (which MUST return true when the first argument is of higher
// priority than the second and MUST return false otherwise) and, optionally,
// any number of client.Objects (which do NOT needs to be pre-ordered) and
// returns an implementation of the PriorityQueue interface that is safe for
// concurrent use by multiple goroutines. This function will also return an
// error if initialized with a nil comparison function or any nil
// runtime.Objects.
func NewPriorityQueue(
higherFn ObjectPriorityFn,
objects ...client.Object,
) (PriorityQueue, error) {
if higherFn == nil {
return nil, errors.New(
"the priority queue was initialized with a nil client.Object " +
"comparison function",
)
}
filteredObjs := []client.Object{}
objectsByNamespaceName := make(map[types.NamespacedName]bool)
// filter out duplicates and nils
for i, object := range objects {
if object == nil {
continue
}
key := types.NamespacedName{
Namespace: object.GetNamespace(),
Name: object.GetName(),
}
if objectsByNamespaceName[key] {
continue
}
objectsByNamespaceName[key] = true
filteredObjs = append(filteredObjs, objects[i])
}
internalQueue := &internalPriorityQueue{
objects: filteredObjs,
higherFn: higherFn,
}
heap.Init(internalQueue)
return &priorityQueue{
objectsByNamespaceName: objectsByNamespaceName,
internalQueue: internalQueue,
}, nil
}
func (p *priorityQueue) Push(item client.Object) bool {
p.mu.Lock()
defer p.mu.Unlock()
if item == nil {
return false
}
key := types.NamespacedName{
Namespace: item.GetNamespace(),
Name: item.GetName(),
}
if p.objectsByNamespaceName[key] {
return false
}
heap.Push(p.internalQueue, item.DeepCopyObject())
p.objectsByNamespaceName[key] = true
return true
}
func (p *priorityQueue) Pop() client.Object {
p.mu.Lock()
defer p.mu.Unlock()
if p.internalQueue.Len() == 0 {
return nil
}
obj := heap.Pop(p.internalQueue).(client.Object) // nolint: forcetypeassert
key := types.NamespacedName{
Namespace: obj.GetNamespace(),
Name: obj.GetName(),
}
delete(p.objectsByNamespaceName, key)
return obj
}
func (p *priorityQueue) Peek() client.Object {
p.mu.RLock()
defer p.mu.RUnlock()
n := len(p.internalQueue.objects)
if n == 0 {
return nil
}
return p.internalQueue.objects[0]
}
func (p *priorityQueue) Depth() int {
p.mu.RLock()
defer p.mu.RUnlock()
return p.internalQueue.Len()
}
// internalPriorityQueue is the underlying data structure for priorityQueue. It
// implements heap.Interface, which allows priorityQueue to offload ordering of
// its client.Objects by priority to the heap package.
type internalPriorityQueue struct {
objects []client.Object
higherFn ObjectPriorityFn
}
func (i *internalPriorityQueue) Len() int { return len(i.objects) }
func (i *internalPriorityQueue) Less(n, m int) bool {
return i.higherFn(i.objects[n], i.objects[m])
}
func (i *internalPriorityQueue) Swap(n, m int) {
i.objects[n], i.objects[m] = i.objects[m], i.objects[n]
}
func (i *internalPriorityQueue) Push(item any) {
i.objects = append(i.objects, item.(client.Object)) // nolint: forcetypeassert
}
func (i *internalPriorityQueue) Pop() any {
n := len(i.objects)
item := i.objects[n-1]
i.objects[n-1] = nil // avoid memory leak
i.objects = i.objects[:n-1]
return item
}