-
Notifications
You must be signed in to change notification settings - Fork 0
/
pointer_set.go
258 lines (232 loc) · 6.43 KB
/
pointer_set.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
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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
package nogc
import (
"github.com/moontrade/nogc/hash"
"unsafe"
)
// PointerSet is a hashset that uses the robinhood algorithm. This
// implementation is not concurrent safe.
type PointerSet struct {
// items are the slots of the hashmap for items.
items uintptr
end uintptr
size uintptr
// Number of keys in the PointerSet.
count uintptr
// When any item's distance gets too large, Grow the PointerSet.
// Defaults to 10.
maxDistance int32
growBy int32
// Number of hash slots to Grow by
growthFactor float32
}
// Item represents an entry in the PointerSet.
type pointerSetItem struct {
key uintptr
distance int32 // How far item is from its best position.
}
// pointerSetHash uses the fnv hashing algorithm for 32bit integers.
// fnv was chosen for its consistent low collision rate even with tight monotonic numbers (WASM)
// and for its performance. Other potential candidates are wyhash, metro, and adler32. Each of these
// have optimized 32bit version in hash.go in this package.
//go:inline
var pointerSetHash = hash.FNV32a
//func pointerSetHash(v uint32) uint32 {
// return fnv32(v)
//}
// NewPointerSet returns a new robinhood hashmap.
//goland:noinspection ALL
func NewPointerSet(size uintptr) PointerSet {
items := AllocZeroed(unsafe.Sizeof(pointerSetItem{}) * size)
Zero(unsafe.Pointer(items), unsafe.Sizeof(pointerSetItem{})*uintptr(size))
return PointerSet{
items: uintptr(items),
size: uintptr(size),
end: uintptr(items) + (uintptr(size) * unsafe.Sizeof(pointerSetItem{})),
maxDistance: 10,
growBy: 64,
growthFactor: 2.0,
}
}
//goland:noinspection GoVetUnsafePointer
func (ps *PointerSet) Close() error {
if ps == nil {
return nil
}
if ps.items == 0 {
return nil
}
Free(Pointer(ps.items))
ps.items = 0
return nil
}
// Reset clears PointerSet, where already allocated memory will be reused.
//goland:noinspection ALL
func (ps *PointerSet) Reset() {
Zero(unsafe.Pointer(ps.items), unsafe.Sizeof(pointerSetItem{})*ps.size)
ps.count = 0
}
//goland:noinspection GoVetUnsafePointer
func (ps *PointerSet) isCollision(key uintptr) bool {
return *(*uintptr)(unsafe.Pointer(
ps.items + (uintptr(pointerSetHash(uint32(key))%uint32(ps.size)) * unsafe.Sizeof(pointerSetItem{})))) != 0
}
// Has returns whether the key exists in the Add.
//goland:noinspection ALL
func (ps *PointerSet) Has(key uintptr) bool {
var (
idx = ps.items + (uintptr(pointerSetHash(uint32(key))%uint32(ps.size)) * unsafe.Sizeof(pointerSetItem{}))
idxStart = idx
)
for {
entry := *(*uintptr)(unsafe.Pointer(idx))
if entry == 0 {
return false
}
if entry == key {
return true
}
idx += unsafe.Sizeof(pointerSetItem{})
if idx >= ps.end {
idx = ps.items
}
// Went all the way around?
if idx == idxStart {
return false
}
}
}
func (ps *PointerSet) Set(key uintptr) (bool, bool) {
return ps.Add(key, 0)
}
// Add inserts or updates a key into the PointerSet. The returned
// wasNew will be true if the mutation was on a newly seen, inserted
// key, and wasNew will be false if the mutation was an update to an
// existing key.
//goland:noinspection GoVetUnsafePointer
func (ps *PointerSet) Add(key uintptr, depth int) (bool, bool) {
var (
idx = ps.items + (uintptr(pointerSetHash(uint32(key))%uint32(ps.size)) * unsafe.Sizeof(pointerSetItem{}))
idxStart = idx
incoming = pointerSetItem{key, 0}
)
for {
entry := (*pointerSetItem)(unsafe.Pointer(idx))
if entry.key == 0 {
*(*pointerSetItem)(unsafe.Pointer(idx)) = incoming
ps.count++
return true, true
}
if entry.key == incoming.key {
entry.distance = incoming.distance
return false, true
}
// Swap if the incoming item is further from its best idx.
if entry.distance < incoming.distance {
incoming, *(*pointerSetItem)(unsafe.Pointer(idx)) = *(*pointerSetItem)(unsafe.Pointer(idx)), incoming
}
// One step further away from best idx.
incoming.distance++
idx += unsafe.Sizeof(pointerSetItem{})
if idx >= ps.end {
idx = ps.items
}
// Grow if distances become big or we went all the way around.
if incoming.distance > ps.maxDistance || idx == idxStart {
if depth > 5 {
return false, false
}
if !ps.Grow() {
return false, false
}
return ps.Add(incoming.key, depth+1)
}
}
}
// Delete removes a key from the PointerSet.
//goland:noinspection GoVetUnsafePointer
func (ps *PointerSet) Delete(key uintptr) (uintptr, bool) {
if key == 0 {
return 0, false
}
var (
idx = ps.items + (uintptr(pointerSetHash(uint32(key))%uint32(ps.size)) * unsafe.Sizeof(pointerSetItem{}))
idxStart = idx
)
for {
entry := (*pointerSetItem)(unsafe.Pointer(idx))
if entry.key == 0 {
return 0, false
}
if entry.key == key {
break // Found the item.
}
idx += unsafe.Sizeof(pointerSetItem{})
if idx >= ps.end {
idx = ps.items
}
if idx == idxStart {
return 0, false
}
}
// Left-shift succeeding items in the linear chain.
for {
next := idx + unsafe.Sizeof(pointerSetItem{})
if next >= ps.end {
next = ps.items
}
// Went all the way around?
if next == idx {
break
}
f := (*pointerSetItem)(unsafe.Pointer(next))
if f.key == 0 || f.distance <= 0 {
break
}
f.distance--
*(*pointerSetItem)(unsafe.Pointer(idx)) = *f
idx = next
}
// Clear entry
*(*pointerSetItem)(unsafe.Pointer(idx)) = pointerSetItem{}
ps.count--
return idxStart, true
}
//goland:noinspection GoVetUnsafePointer
func (ps *PointerSet) Grow() bool {
// Calculate new size
// ps.size + 128
if ps.growthFactor <= 1.0 {
ps.growthFactor = 2.0
}
//newSize := ps.size + 32 // uintptr(float32(ps.size) * ps.growthFactor)
newSize := uintptr(float32(ps.size) * ps.growthFactor)
//if gc_TRACE {
// println("PointerSet.Grow", "newSize", uint(newSize), "oldSize", uint(ps.size))
//}
// Allocate new items table
items := uintptr(AllocZeroed(newSize * unsafe.Sizeof(pointerSetItem{})))
// Calculate end
itemsEnd := items + (newSize * unsafe.Sizeof(pointerSetItem{}))
// Init next structure
next := PointerSet{
items: items,
size: newSize,
end: itemsEnd,
count: 0,
growthFactor: ps.growthFactor,
maxDistance: ps.maxDistance,
}
// Add all entries from old to next
var success bool
for i := ps.items; i < ps.end; i += unsafe.Sizeof(pointerSetItem{}) {
if _, success = next.Add(*(*uintptr)(unsafe.Pointer(i)), 0); !success {
return false
}
}
// Free old items
Free(Pointer(ps.items))
ps.items = 0
// Update to next
*ps = next
return true
}