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
|
package hashmap
import (
"sync/atomic"
"unsafe"
)
type store[Key comparable, Value any] struct {
keyShifts uintptr // Pointer size - log2 of array size, to be used as index in the data array
count atomic.Uintptr // count of filled elements in the slice
array unsafe.Pointer // pointer to slice data array
index []*ListElement[Key, Value] // storage for the slice for the garbage collector to not clean it up
}
// item returns the item for the given hashed key.
func (s *store[Key, Value]) item(hashedKey uintptr) *ListElement[Key, Value] {
index := hashedKey >> s.keyShifts
ptr := (*unsafe.Pointer)(unsafe.Pointer(uintptr(s.array) + index*intSizeBytes))
item := (*ListElement[Key, Value])(atomic.LoadPointer(ptr))
return item
}
// adds an item to the index if needed and returns the new item counter if it changed, otherwise 0.
func (s *store[Key, Value]) addItem(item *ListElement[Key, Value]) uintptr {
index := item.keyHash >> s.keyShifts
ptr := (*unsafe.Pointer)(unsafe.Pointer(uintptr(s.array) + index*intSizeBytes))
for { // loop until the smallest key hash is in the index
element := (*ListElement[Key, Value])(atomic.LoadPointer(ptr)) // get the current item in the index
if element == nil { // no item yet at this index
if atomic.CompareAndSwapPointer(ptr, nil, unsafe.Pointer(item)) {
return s.count.Add(1)
}
continue // a new item was inserted concurrently, retry
}
if item.keyHash < element.keyHash {
// the new item is the smallest for this index?
if !atomic.CompareAndSwapPointer(ptr, unsafe.Pointer(element), unsafe.Pointer(item)) {
continue // a new item was inserted concurrently, retry
}
}
return 0
}
}
|
