blob: 07787c44c9ed1430d43d79e90eb5f63796f30297 (
plain)
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
|
package structr
// elem represents an element
// in a doubly-linked list.
type elem[T any] struct {
next *elem[T]
prev *elem[T]
Value T
}
// list implements a doubly-linked list, where:
// - head = index 0 (i.e. the front)
// - tail = index n-1 (i.e. the back)
type list[T any] struct {
head *elem[T]
tail *elem[T]
len int
}
func list_acquire[T any](c *Cache[T]) *list[*result[T]] {
var l *list[*result[T]]
if len(c.llsPool) == 0 {
// Allocate new list.
l = new(list[*result[T]])
} else {
// Pop list from pool slice.
l = c.llsPool[len(c.llsPool)-1]
c.llsPool = c.llsPool[:len(c.llsPool)-1]
}
return l
}
func list_release[T any](c *Cache[T], l *list[*result[T]]) {
// Reset list.
l.head = nil
l.tail = nil
l.len = 0
// Release list to memory pool.
c.llsPool = append(c.llsPool, l)
}
// pushFront pushes new 'elem' to front of list.
func (l *list[T]) pushFront(elem *elem[T]) {
if l.len == 0 {
// Set new tail + head
l.head = elem
l.tail = elem
// Link elem to itself
elem.next = elem
elem.prev = elem
} else {
oldHead := l.head
// Link to old head
elem.next = oldHead
oldHead.prev = elem
// Link up to tail
elem.prev = l.tail
l.tail.next = elem
// Set new head
l.head = elem
}
// Incr count
l.len++
}
// moveFront calls remove() on elem, followed by pushFront().
func (l *list[T]) moveFront(elem *elem[T]) {
l.remove(elem)
l.pushFront(elem)
}
// remove removes the 'elem' from the list.
func (l *list[T]) remove(elem *elem[T]) {
if l.len <= 1 {
// Drop elem's links
elem.next = nil
elem.prev = nil
// Only elem in list
l.head = nil
l.tail = nil
l.len = 0
return
}
// Get surrounding elems
next := elem.next
prev := elem.prev
// Relink chain
next.prev = prev
prev.next = next
switch elem {
// Set new head
case l.head:
l.head = next
// Set new tail
case l.tail:
l.tail = prev
}
// Drop elem's links
elem.next = nil
elem.prev = nil
// Decr count
l.len--
}
// rangefn ranges all the elements in the list, passing each to fn.
func (l *list[T]) rangefn(fn func(*elem[T])) {
if fn == nil {
panic("nil fn")
}
elem := l.head
for i := 0; i < l.len; i++ {
fn(elem)
elem = elem.next
}
}
|
