From 008904aba6b28ea8b9bbb0f5a90987bd3a8a8772 Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Fri, 21 Jun 2024 20:09:09 +0000 Subject: [PATCH] internal/sync: relax value type constraint for HashTrieMap Currently the HashTrieMap requires both keys and values to be comparable, but it's actually OK if the value is not comparable. Some operations may fail, but others will not, and we can check comparability dynamically on map initialization. This makes the implementation substantially more flexible. Change-Id: Idc9c30dfa273d80ae4d46a9eefb5c155294408aa Reviewed-on: https://go-review.googlesource.com/c/go/+/594061 LUCI-TryBot-Result: Go LUCI Auto-Submit: Michael Knyszek Reviewed-by: David Chase --- src/internal/sync/hashtriemap.go | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-) diff --git a/src/internal/sync/hashtriemap.go b/src/internal/sync/hashtriemap.go index 81bbf4fea2..f386134930 100644 --- a/src/internal/sync/hashtriemap.go +++ b/src/internal/sync/hashtriemap.go @@ -15,7 +15,7 @@ import ( // is designed around frequent loads, but offers decent performance for stores // and deletes as well, especially if the map is larger. Its primary use-case is // the unique package, but can be used elsewhere as well. -type HashTrieMap[K, V comparable] struct { +type HashTrieMap[K comparable, V any] struct { root *indirect[K, V] keyHash hashFunc valEqual equalFunc @@ -23,7 +23,7 @@ type HashTrieMap[K, V comparable] struct { } // NewHashTrieMap creates a new HashTrieMap for the provided key and value. -func NewHashTrieMap[K, V comparable]() *HashTrieMap[K, V] { +func NewHashTrieMap[K comparable, V any]() *HashTrieMap[K, V] { var m map[K]V mapType := abi.TypeOf(m).MapType() ht := &HashTrieMap[K, V]{ @@ -174,10 +174,14 @@ func (ht *HashTrieMap[K, V]) expand(oldEntry, newEntry *entry[K, V], newHash uin } // CompareAndDelete deletes the entry for key if its value is equal to old. +// The value type must be comparable, otherwise this CompareAndDelete will panic. // // If there is no current value for key in the map, CompareAndDelete returns false // (even if the old value is the nil interface value). func (ht *HashTrieMap[K, V]) CompareAndDelete(key K, old V) (deleted bool) { + if ht.valEqual == nil { + panic("called CompareAndDelete when value is not of comparable type") + } hash := ht.keyHash(abi.NoEscape(unsafe.Pointer(&key)), ht.seed) // Find a node with the key and compare with it. n != nil if we found the node. @@ -322,7 +326,7 @@ const ( ) // indirect is an internal node in the hash-trie. -type indirect[K, V comparable] struct { +type indirect[K comparable, V any] struct { node[K, V] dead atomic.Bool mu Mutex // Protects mutation to children and any children that are entry nodes. @@ -330,7 +334,7 @@ type indirect[K, V comparable] struct { children [nChildren]atomic.Pointer[node[K, V]] } -func newIndirectNode[K, V comparable](parent *indirect[K, V]) *indirect[K, V] { +func newIndirectNode[K comparable, V any](parent *indirect[K, V]) *indirect[K, V] { return &indirect[K, V]{node: node[K, V]{isEntry: false}, parent: parent} } @@ -345,14 +349,14 @@ func (i *indirect[K, V]) empty() bool { } // entry is a leaf node in the hash-trie. -type entry[K, V comparable] struct { +type entry[K comparable, V any] struct { node[K, V] overflow atomic.Pointer[entry[K, V]] // Overflow for hash collisions. key K value V } -func newEntryNode[K, V comparable](key K, value V) *entry[K, V] { +func newEntryNode[K comparable, V any](key K, value V) *entry[K, V] { return &entry[K, V]{ node: node[K, V]{isEntry: true}, key: key, @@ -394,7 +398,7 @@ func (head *entry[K, V]) compareAndDelete(key K, value V, valEqual equalFunc) (* // node is the header for a node. It's polymorphic and // is actually either an entry or an indirect. -type node[K, V comparable] struct { +type node[K comparable, V any] struct { isEntry bool } -- 2.48.1