forked from alphadose/haxmap
-
Notifications
You must be signed in to change notification settings - Fork 0
/
list.go
144 lines (132 loc) · 3.89 KB
/
list.go
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
package haxmap
import (
"sync/atomic"
)
// mark a node for being deleted, also used as list_head
// the search() function skips nodes with `keyHash = marked`
const marked = ^uintptr(0)
// Below implementation is a lock-free linked list based on https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf by Timothy L. Harris
// Performance improvements suggested in https://arxiv.org/pdf/2010.15755.pdf were also added
// newListHead returns the new head of any list
func newListHead[K hashable, V any]() *element[K, V] {
e := &element[K, V]{marked, *new(K), atomic.Pointer[element[K, V]]{}, atomic.Pointer[V]{}}
e.nextPtr.Store(nil)
e.value.Store(new(V))
return e
}
// a single node in the list
type element[K hashable, V any] struct {
keyHash uintptr
key K
// The next element in the list. If this pointer has the marked flag set it means THIS element, not the next one, is deleted.
nextPtr atomic.Pointer[element[K, V]]
value atomic.Pointer[V]
}
// next returns the next element
// this also deletes all marked elements while traversing the list
func (self *element[K, V]) next() *element[K, V] {
for nextElement := self.nextPtr.Load(); nextElement != nil; {
// if our next element contains marked that means WE are deleted, and we can just return the next-next element
if nextElement.keyHash == marked {
return nextElement.next()
}
// if our next element is itself deleted (by the same criteria) then we will just replace
// it with its next() (which should be the first node behind it that isn't itself deleted) and then check again
if nextElement.isDeleted() {
self.nextPtr.CompareAndSwap(nextElement, nextElement.next())
nextElement = self.nextPtr.Load()
} else {
return nextElement
}
}
return nil
}
// addBefore inserts an element before the specified element
func (self *element[K, V]) addBefore(t uintptr, allocatedElement, before *element[K, V]) bool {
if self.next() != before {
return false
}
allocatedElement.nextPtr.Store(before)
return self.nextPtr.CompareAndSwap(before, allocatedElement)
}
// inject updates an existing value in the list if present or adds a new entry
func (self *element[K, V]) inject(c uintptr, key K, value *V) (elem *element[K, V], created bool) {
var alloc, left, curr, right *element[K, V]
for {
left, curr, right = self.search(c, key)
if curr != nil {
curr.value.Store(value)
return curr, false
}
if left != nil {
if alloc == nil {
alloc = &element[K, V]{keyHash: c, key: key}
alloc.value.Store(value)
}
if left.addBefore(c, alloc, right) {
return alloc, true
}
}
}
}
// search for an element in the list and return left_element, searched_element and right_element respectively
func (self *element[K, V]) search(c uintptr, key K) (*element[K, V], *element[K, V], *element[K, V]) {
var (
left, right *element[K, V]
curr = self
)
for {
if curr == nil {
return left, curr, right
}
right = curr.next()
if curr.keyHash != marked {
if c < curr.keyHash {
right = curr
curr = nil
return left, curr, right
} else if c == curr.keyHash && key == curr.key {
return left, curr, right
}
}
left = curr
curr = left.next()
right = nil
}
}
// remove removes the current node
func (self *element[K, V]) remove() bool {
for {
if self.next() == nil {
return false
}
if self.add(marked) {
self.next()
return true
}
}
}
// if current element is deleted
func (self *element[K, V]) isDeleted() bool {
next := self.nextPtr.Load()
if next == nil {
return false
}
if next.keyHash == marked {
return true
}
return false
}
func (self *element[K, V]) add(c uintptr) bool {
alloc := &element[K, V]{keyHash: c}
for {
// If we are deleted then we do not allow adding new children.
if self.isDeleted() {
return false
}
// If we succeed in adding before our perceived next, just return true.
if self.addBefore(c, alloc, self.next()) {
return true
}
}
}