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
|
package ttlcache
import (
"container/heap"
"container/list"
)
// expirationQueue stores items that are ordered by their expiration
// timestamps. The 0th item is closest to its expiration.
type expirationQueue[K comparable, V any] []*list.Element
// newExpirationQueue creates and initializes a new expiration queue.
func newExpirationQueue[K comparable, V any]() expirationQueue[K, V] {
q := make(expirationQueue[K, V], 0)
heap.Init(&q)
return q
}
// isEmpty checks if the queue is empty.
func (q expirationQueue[K, V]) isEmpty() bool {
return q.Len() == 0
}
// update updates an existing item's value and position in the queue.
func (q *expirationQueue[K, V]) update(elem *list.Element) {
heap.Fix(q, elem.Value.(*Item[K, V]).queueIndex)
}
// push pushes a new item into the queue and updates the order of its
// elements.
func (q *expirationQueue[K, V]) push(elem *list.Element) {
heap.Push(q, elem)
}
// remove removes an item from the queue and updates the order of its
// elements.
func (q *expirationQueue[K, V]) remove(elem *list.Element) {
heap.Remove(q, elem.Value.(*Item[K, V]).queueIndex)
}
// Len returns the total number of items in the queue.
func (q expirationQueue[K, V]) Len() int {
return len(q)
}
// Less checks if the item at the i position expires sooner than
// the one at the j position.
func (q expirationQueue[K, V]) Less(i, j int) bool {
item1, item2 := q[i].Value.(*Item[K, V]), q[j].Value.(*Item[K, V])
if item1.expiresAt.IsZero() {
return false
}
if item2.expiresAt.IsZero() {
return true
}
return item1.expiresAt.Before(item2.expiresAt)
}
// Swap switches the places of two queue items.
func (q expirationQueue[K, V]) Swap(i, j int) {
q[i], q[j] = q[j], q[i]
q[i].Value.(*Item[K, V]).queueIndex = i
q[j].Value.(*Item[K, V]).queueIndex = j
}
// Push appends a new item to the item slice.
func (q *expirationQueue[K, V]) Push(x interface{}) {
elem := x.(*list.Element)
elem.Value.(*Item[K, V]).queueIndex = len(*q)
*q = append(*q, elem)
}
// Pop removes and returns the last item.
func (q *expirationQueue[K, V]) Pop() interface{} {
old := *q
i := len(old) - 1
elem := old[i]
elem.Value.(*Item[K, V]).queueIndex = -1
old[i] = nil // avoid memory leak
*q = old[:i]
return elem
}
|
