-
Notifications
You must be signed in to change notification settings - Fork 0
/
map.go
91 lines (83 loc) · 1.54 KB
/
map.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
package identity
import (
"hash"
"hash/maphash"
"slices"
)
type Map[K hashEqualer[K], V any] struct {
orig map[uint64]*[]mapKV[K, V]
len int
h *maphash.Hash
}
type hashEqualer[K any] interface {
Equals(K) bool
WriteHash(hash.Hash)
}
type mapKV[K hashEqualer[K], V any] struct {
key K
value V
}
func NewMap[K hashEqualer[K], V any]() *Map[K, V] {
return &Map[K, V]{
orig: map[uint64]*[]mapKV[K, V]{},
h: new(maphash.Hash),
}
}
func (m *Map[K, V]) Get(key K) (val V, ok bool) {
kvs, ok := m.orig[m.hash(key)]
if !ok {
return
}
i := slices.IndexFunc(*kvs, func(kv mapKV[K, V]) bool {
return kv.key.Equals(key)
})
if i == -1 {
return val, false
}
return (*kvs)[i].value, true
}
func (m *Map[_, _]) Len() int {
return m.len
}
func (m *Map[K, V]) Set(key K, val V) {
hash := m.hash(key)
entry, ok := m.orig[hash]
if !ok {
kvs := make([]mapKV[K, V], 0, 1)
entry = &kvs
m.orig[hash] = entry
}
i := slices.IndexFunc(*entry, func(kv mapKV[K, V]) bool {
return kv.key.Equals(key)
})
if i == -1 {
kvs := append(*entry, mapKV[K, V]{key: key, value: val})
*entry = kvs
m.len++
} else {
(*entry)[i].value = val
}
}
func (m *Map[K, V]) Delete(key K) {
hash := m.hash(key)
entry, ok := m.orig[hash]
if !ok {
return
}
l := len(*entry)
*entry = slices.DeleteFunc(*entry, func(kv mapKV[K, V]) bool {
return kv.key.Equals(key)
})
if len(*entry) != l {
m.len--
}
if len(*entry) == 0 {
delete(m.orig, hash)
}
}
func (m *Map[K, _]) hash(key K) uint64 {
h := m.h
h.Reset()
key.WriteHash(h)
return h.Sum64()
}