blob: f0ce9ad4da3efe6ad6b2882703f43200690089ef (
plain) (
blame)
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
|
// Copyright 2025 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package runtime
import (
"unsafe"
)
// The types in this file are exact copies of the types in list.go, but with
// unsafe.Pointer replaced with uintptr for use where write barriers must be
// avoided, such as uses of muintptr, puintptr, guintptr.
//
// Objects in these lists must be kept alive via another real reference.
// listHeadManual points to the head of an intrusive doubly-linked list of
// objects.
//
// Prior to use, you must call init to store the offset of listNodeManual fields.
//
// Every object in the list should be the same type.
type listHeadManual struct {
obj uintptr
initialized bool
nodeOffset uintptr
}
// init initializes the list head. off is the offset (via unsafe.Offsetof) of
// the listNodeManual field in the objects in the list.
func (head *listHeadManual) init(off uintptr) {
head.initialized = true
head.nodeOffset = off
}
// listNodeManual is the linked list node for objects in a listHeadManual list.
//
// listNodeManual must be stored as a field in objects placed in the linked list.
// The offset of the field is registered via listHeadManual.init.
//
// For example:
//
// type foo struct {
// val int
//
// node listNodeManual
// }
//
// var fooHead listHeadManual
// fooHead.init(unsafe.Offsetof(foo{}.node))
type listNodeManual struct {
prev uintptr
next uintptr
}
func (head *listHeadManual) getNode(p unsafe.Pointer) *listNodeManual {
if !head.initialized {
throw("runtime: uninitialized listHead")
}
if p == nil {
return nil
}
return (*listNodeManual)(unsafe.Add(p, head.nodeOffset))
}
// Returns true if the list is empty.
func (head *listHeadManual) empty() bool {
return head.obj == 0
}
// Returns the head of the list without removing it.
func (head *listHeadManual) head() unsafe.Pointer {
return unsafe.Pointer(head.obj)
}
// Push p onto the front of the list.
func (head *listHeadManual) push(p unsafe.Pointer) {
// p becomes the head of the list.
// ... so p's next is the current head.
pNode := head.getNode(p)
pNode.next = head.obj
// ... and the current head's prev is p.
if head.obj != 0 {
headNode := head.getNode(unsafe.Pointer(head.obj))
headNode.prev = uintptr(p)
}
head.obj = uintptr(p)
}
// Pop removes the head of the list.
func (head *listHeadManual) pop() unsafe.Pointer {
if head.obj == 0 {
return nil
}
// Return the head of the list.
p := unsafe.Pointer(head.obj)
// ... so the new head is p's next.
pNode := head.getNode(p)
head.obj = pNode.next
// p is no longer on the list. Clear next to remove unused references.
// N.B. as the head, prev must already be nil.
pNode.next = 0
// ... and the new head no longer has a prev.
if head.obj != 0 {
headNode := head.getNode(unsafe.Pointer(head.obj))
headNode.prev = 0
}
return p
}
// Remove p from the middle of the list.
func (head *listHeadManual) remove(p unsafe.Pointer) {
if unsafe.Pointer(head.obj) == p {
// Use pop to ensure head is updated when removing the head.
head.pop()
return
}
pNode := head.getNode(p)
prevNode := head.getNode(unsafe.Pointer(pNode.prev))
nextNode := head.getNode(unsafe.Pointer(pNode.next))
// Link prev to next.
if prevNode != nil {
prevNode.next = pNode.next
}
// Link next to prev.
if nextNode != nil {
nextNode.prev = pNode.prev
}
pNode.prev = 0
pNode.next = 0
}
|
