/
atomics.go
138 lines (115 loc) · 4 KB
/
atomics.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
// This is free and unencumbered software released into the public
// domain. For more information, see <http://unlicense.org> or the
// accompanying UNLICENSE file.
package history
import (
"sync/atomic"
"unsafe"
"github.com/nelsam/vidar/commander/text"
)
// node is an entry in a linked list.
type node struct {
// nextP *node - the next entry in the list.
nextP unsafe.Pointer
// the above should be kept first in the struct for byte alignment.
edit text.Edit
}
// next performs atomic incantations to load n.nextP, returning
// it as a *node.
func (n *node) next() *node {
return (*node)(atomic.LoadPointer(&n.nextP))
}
// setNext performs atomic incantations to set n.nextP to nn
func (n *node) setNext(nn *node) {
atomic.StorePointer(&n.nextP, unsafe.Pointer(nn))
}
// casNext performs atomic compare-and-swap operations to set
// n.nextP to nn, but only if it is currently equal to old.
// It returns whether or not n.nextP was equal to old.
func (n *node) casNext(old, nn *node) bool {
return atomic.CompareAndSwapPointer(&n.nextP, unsafe.Pointer(old), unsafe.Pointer(nn))
}
// A branch is an entry in a (non-binary) tree. The first child
// will be at next(); all other children will be at
// next().siblings().
type branch struct {
// prevP *branch - the parent node
prevP unsafe.Pointer
// nextP *branch - the first child node. Additional branching
// nodes should be accessed via this node's siblings.
nextP unsafe.Pointer
// siblingsP *[]*branch - the siblings of this node. Normal
// (i.e. non-branching) edits perform much better if next()
// directly returns a *node, but if we have a sibling() which
// also returns a *node we end up hitting double digits of
// milliseconds per thousand operations in heavily branching
// history. So we take the extra performance penalty of
// using a slice *only* on branching edits, to prevent the
// performance hit from being paid per child node.
siblingsP unsafe.Pointer
// the above should be kept first in the struct for byte alignment.
edit text.Edit
}
// prev performs atomic incantations to load b.prevP and return
// it as a *branch.
func (b *branch) prev() *branch {
return (*branch)(atomic.LoadPointer(&b.prevP))
}
// next performs atomic incantations to load the i'th child branch
// of b and return it as a *branch.
func (b *branch) next(i uint) *branch {
next := (*branch)(atomic.LoadPointer(&b.nextP))
if i == 0 || next == nil {
return next
}
sibIdx := i - 1
sibs := next.siblings()
if sibIdx >= uint(len(sibs)) {
return nil
}
return sibs[sibIdx]
}
// siblings performs atomic incantations to load b.siblingsP and
// return it as a []*branch.
func (b *branch) siblings() []*branch {
sibs := (*[]*branch)(atomic.LoadPointer(&b.siblingsP))
if sibs == nil {
return nil
}
return *sibs
}
// push adds e to the next empty child branch of b.
func (b *branch) push(e text.Edit) *branch {
next := &branch{edit: e, prevP: unsafe.Pointer(b)}
np := unsafe.Pointer(next)
done := atomic.CompareAndSwapPointer(&b.nextP, nil, np)
if !done {
fchild := b.next(0)
// We have to do _some_ kind of special case for nil; might as
// well just try it here.
fsib := []*branch{next}
done = atomic.CompareAndSwapPointer(&fchild.siblingsP, nil, unsafe.Pointer(&fsib))
for !done {
oldSibsP := (*[]*branch)(atomic.LoadPointer(&fchild.siblingsP))
sibs := append(*oldSibsP, next)
done = atomic.CompareAndSwapPointer(&fchild.siblingsP, unsafe.Pointer(oldSibsP), unsafe.Pointer(&sibs))
}
}
return next
}
// tree is a simple tree implementation to atomically store a branching
// history of text.Edit values.
type tree struct {
// trunkP *branch
trunkP unsafe.Pointer
// the above should be kept first in the struct for byte alignment.
}
// trunk performs atomic incantations to load t.trunkP and return it as
// a *branch.
func (t *tree) trunk() *branch {
return (*branch)(atomic.LoadPointer(&t.trunkP))
}
// setTrunk performs atomic incantations to set t.trunkP to b.
func (t *tree) setTrunk(b *branch) {
atomic.StorePointer(&t.trunkP, unsafe.Pointer(b))
}