blob: 764036d479722b47bd6e100fb2ccd55555692735 (
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
package structr
import (
"sync"
"unsafe"
)
// 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
}
var list_pool sync.Pool
// new_list returns a new prepared list.
func new_list() *list {
v := list_pool.Get()
if v == nil {
v = new(list)
}
list := v.(*list)
return list
}
// free_list releases the list.
func free_list(list *list) {
list.head = nil
list.tail = nil
list.len = 0
list_pool.Put(list)
}
// push_front will push the given elem to front (head) of list.
func (l *list) push_front(elem *list_elem) {
// Set new head.
oldHead := l.head
l.head = elem
if oldHead != nil {
// Link to old head
elem.next = oldHead
oldHead.prev = elem
} else {
// First in list.
l.tail = elem
}
// Incr count
l.len++
}
// push_back will push the given elem to back (tail) of list.
func (l *list) push_back(elem *list_elem) {
// Set new tail.
oldTail := l.tail
l.tail = elem
if oldTail != nil {
// Link to old tail
elem.prev = oldTail
oldTail.next = elem
} else {
// First in list.
l.head = elem
}
// Incr count
l.len++
}
// move_front will move given elem to front (head) of list.
// if it is already at front this call is a no-op.
func (l *list) move_front(elem *list_elem) {
if elem == l.head {
return
}
l.remove(elem)
l.push_front(elem)
}
// move_back will move given elem to back (tail) of list,
// if it is already at back this call is a no-op.
func (l *list) move_back(elem *list_elem) {
if elem == l.tail {
return
}
l.remove(elem)
l.push_back(elem)
}
// remove will remove given elem from list.
func (l *list) remove(elem *list_elem) {
// Get linked elems.
next := elem.next
prev := elem.prev
// Unset elem.
elem.next = nil
elem.prev = nil
switch {
// elem is ONLY one in list.
case next == nil && prev == nil:
l.head = nil
l.tail = nil
// elem is front in list.
case next != nil && prev == nil:
l.head = next
next.prev = nil
// elem is last in list.
case prev != nil && next == nil:
l.tail = prev
prev.next = nil
// elem in middle of list.
default:
next.prev = prev
prev.next = next
}
// Decr count
l.len--
}
// rangefn will range all elems in list, passing each to fn.
func (l *list) rangefn(fn func(*list_elem)) {
if fn == nil {
panic("nil fn")
}
for e := l.head; //
e != nil; //
{
n := e.next
fn(e)
e = n
}
}
|
