blob: 1c931fd51c0dc342899b96a237f3a1b60d026dcd (
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
package structr
import (
"os"
"unsafe"
"codeberg.org/gruf/go-mempool"
)
// 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 mempool.UnsafePool
// new_list returns a new prepared list.
func new_list() *list {
if ptr := list_pool.Get(); ptr != nil {
return (*list)(ptr)
}
return new(list)
}
// free_list releases the list.
func free_list(list *list) {
if list.head != nil ||
list.tail != nil ||
list.len != 0 {
msg := assert("list not in use")
os.Stderr.WriteString(msg + "\n")
return
}
ptr := unsafe.Pointer(list)
list_pool.Put(ptr)
}
// 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)
}
// insert will insert given element at given location in list.
func (l *list) insert(elem *list_elem, at *list_elem) {
if elem == at {
return
}
// Set new 'next'.
oldNext := at.next
at.next = elem
// Link to 'at'.
elem.prev = at
if oldNext == nil {
// Set new tail
l.tail = elem
} else {
// Link to 'prev'.
oldNext.prev = elem
elem.next = oldNext
}
// Incr
// count
l.len++
}
// 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 {
case next == nil:
if prev == nil {
// next == nil && prev == nil
//
// elem is ONLY one in list.
l.head = nil
l.tail = nil
} else {
// next == nil && prev != nil
//
// elem is last in list.
l.tail = prev
prev.next = nil
}
case prev == nil:
// next != nil && prev == nil
//
// elem is front in list.
l.head = next
next.prev = nil
// elem in middle of list.
default:
next.prev = prev
prev.next = next
}
// Decr
// count
l.len--
}
|
