/
queue.go
69 lines (56 loc) · 1.54 KB
/
queue.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
package plugin
// Implementation of a metrics-based migration priority queue over vmPodStates
import (
"container/heap"
)
type migrationQueue []*vmPodState
///////////////////////
// package-local API //
///////////////////////
func (mq *migrationQueue) addOrUpdate(vm *vmPodState) {
if vm.MqIndex == -1 {
heap.Push(mq, vm)
} else {
heap.Fix(mq, vm.MqIndex)
}
}
func (mq migrationQueue) isNextInQueue(vm *vmPodState) bool {
// the documentation for heap.Pop says that it's equivalent to heap.Remove(h, 0). Therefore,
// checking whether something's the next pop target can just be done by checking if its index is
// zero.
return vm.MqIndex == 0
}
func (mq *migrationQueue) removeIfPresent(vm *vmPodState) {
if vm.MqIndex != -1 {
_ = heap.Remove(mq, vm.MqIndex)
vm.MqIndex = -1
}
}
//////////////////////////////////////
// container/heap.Interface methods //
//////////////////////////////////////
func (mq migrationQueue) Len() int { return len(mq) }
func (mq migrationQueue) Less(i, j int) bool {
return mq[i].isBetterMigrationTarget(mq[j])
}
func (mq migrationQueue) Swap(i, j int) {
mq[i], mq[j] = mq[j], mq[i]
mq[i].MqIndex = i
mq[j].MqIndex = j
}
func (mq *migrationQueue) Push(v any) {
n := len(*mq)
vm := v.(*vmPodState)
vm.MqIndex = n
*mq = append(*mq, vm)
}
func (mq *migrationQueue) Pop() any {
// Function body + comments taken from the example at https://pkg.go.dev/container/heap
old := *mq
n := len(old)
vm := old[n-1]
old[n-1] = nil // avoid memory leak
vm.MqIndex = -1 // for safety
*mq = old[0 : n-1]
return vm
}