blob: 398f84ceb979b16a610f0c32342834dd796277a7 (
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
131
132
133
|
package structr
import (
"sync"
"unsafe"
)
var list_pool sync.Pool
// elem represents an elem
// in a doubly-linked list.
type list_elem struct {
next *list_elem
prev *list_elem
// data is a ptr to the
// value this linked list
// element is embedded-in.
data unsafe.Pointer
}
// list implements a doubly-linked list, where:
// - head = index 0 (i.e. the front)
// - tail = index n-1 (i.e. the back)
type list struct {
head *list_elem
tail *list_elem
len int
}
func list_acquire() *list {
// Acquire from pool.
v := list_pool.Get()
if v == nil {
v = new(list)
}
// Cast list value.
return v.(*list)
}
func list_release(l *list) {
// Reset list.
l.head = nil
l.tail = nil
l.len = 0
// Release to pool.
list_pool.Put(l)
}
func list_push_front(l *list, elem *list_elem) {
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++
}
func list_move_front(l *list, elem *list_elem) {
list_remove(l, elem)
list_push_front(l, elem)
}
func list_remove(l *list, elem *list_elem) {
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--
}
func list_rangefn(l *list, fn func(*list_elem)) {
if fn == nil {
panic("nil fn")
}
elem := l.head
for i := 0; i < l.len; i++ {
fn(elem)
elem = elem.next
}
}
|
