diff options
Diffstat (limited to 'contrib/go/_std_1.25/src/unique/canonmap.go')
| -rw-r--r-- | contrib/go/_std_1.25/src/unique/canonmap.go | 385 |
1 files changed, 0 insertions, 385 deletions
diff --git a/contrib/go/_std_1.25/src/unique/canonmap.go b/contrib/go/_std_1.25/src/unique/canonmap.go deleted file mode 100644 index a3494eef997..00000000000 --- a/contrib/go/_std_1.25/src/unique/canonmap.go +++ /dev/null @@ -1,385 +0,0 @@ -// Copyright 2025 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package unique - -import ( - "internal/abi" - "internal/goarch" - "runtime" - "sync" - "sync/atomic" - "unsafe" - "weak" -) - -// canonMap is a map of T -> *T. The map controls the creation -// of a canonical *T, and elements of the map are automatically -// deleted when the canonical *T is no longer referenced. -type canonMap[T comparable] struct { - root atomic.Pointer[indirect[T]] - hash func(unsafe.Pointer, uintptr) uintptr - seed uintptr -} - -func newCanonMap[T comparable]() *canonMap[T] { - cm := new(canonMap[T]) - cm.root.Store(newIndirectNode[T](nil)) - - var m map[T]struct{} - mapType := abi.TypeOf(m).MapType() - cm.hash = mapType.Hasher - cm.seed = uintptr(runtime_rand()) - return cm -} - -func (m *canonMap[T]) Load(key T) *T { - hash := m.hash(abi.NoEscape(unsafe.Pointer(&key)), m.seed) - - i := m.root.Load() - hashShift := 8 * goarch.PtrSize - for hashShift != 0 { - hashShift -= nChildrenLog2 - - n := i.children[(hash>>hashShift)&nChildrenMask].Load() - if n == nil { - return nil - } - if n.isEntry { - v, _ := n.entry().lookup(key) - return v - } - i = n.indirect() - } - panic("unique.canonMap: ran out of hash bits while iterating") -} - -func (m *canonMap[T]) LoadOrStore(key T) *T { - hash := m.hash(abi.NoEscape(unsafe.Pointer(&key)), m.seed) - - var i *indirect[T] - var hashShift uint - var slot *atomic.Pointer[node[T]] - var n *node[T] - for { - // Find the key or a candidate location for insertion. - i = m.root.Load() - hashShift = 8 * goarch.PtrSize - haveInsertPoint := false - for hashShift != 0 { - hashShift -= nChildrenLog2 - - slot = &i.children[(hash>>hashShift)&nChildrenMask] - n = slot.Load() - if n == nil { - // We found a nil slot which is a candidate for insertion. - haveInsertPoint = true - break - } - if n.isEntry { - // We found an existing entry, which is as far as we can go. - // If it stays this way, we'll have to replace it with an - // indirect node. - if v, _ := n.entry().lookup(key); v != nil { - return v - } - haveInsertPoint = true - break - } - i = n.indirect() - } - if !haveInsertPoint { - panic("unique.canonMap: ran out of hash bits while iterating") - } - - // Grab the lock and double-check what we saw. - i.mu.Lock() - n = slot.Load() - if (n == nil || n.isEntry) && !i.dead.Load() { - // What we saw is still true, so we can continue with the insert. - break - } - // We have to start over. - i.mu.Unlock() - } - // N.B. This lock is held from when we broke out of the outer loop above. - // We specifically break this out so that we can use defer here safely. - // One option is to break this out into a new function instead, but - // there's so much local iteration state used below that this turns out - // to be cleaner. - defer i.mu.Unlock() - - var oldEntry *entry[T] - if n != nil { - oldEntry = n.entry() - if v, _ := oldEntry.lookup(key); v != nil { - // Easy case: by loading again, it turns out exactly what we wanted is here! - return v - } - } - newEntry, canon, wp := newEntryNode(key, hash) - // Prune dead pointers. This is to avoid O(n) lookups when we store the exact same - // value in the set but the cleanup hasn't run yet because it got delayed for some - // reason. - oldEntry = oldEntry.prune() - if oldEntry == nil { - // Easy case: create a new entry and store it. - slot.Store(&newEntry.node) - } else { - // We possibly need to expand the entry already there into one or more new nodes. - // - // Publish the node last, which will make both oldEntry and newEntry visible. We - // don't want readers to be able to observe that oldEntry isn't in the tree. - slot.Store(m.expand(oldEntry, newEntry, hash, hashShift, i)) - } - runtime.AddCleanup(canon, func(_ struct{}) { - m.cleanup(hash, wp) - }, struct{}{}) - return canon -} - -// expand takes oldEntry and newEntry whose hashes conflict from bit 64 down to hashShift and -// produces a subtree of indirect nodes to hold the two new entries. newHash is the hash of -// the value in the new entry. -func (m *canonMap[T]) expand(oldEntry, newEntry *entry[T], newHash uintptr, hashShift uint, parent *indirect[T]) *node[T] { - // Check for a hash collision. - oldHash := oldEntry.hash - if oldHash == newHash { - // Store the old entry in the new entry's overflow list, then store - // the new entry. - newEntry.overflow.Store(oldEntry) - return &newEntry.node - } - // We have to add an indirect node. Worse still, we may need to add more than one. - newIndirect := newIndirectNode(parent) - top := newIndirect - for { - if hashShift == 0 { - panic("unique.canonMap: ran out of hash bits while inserting") - } - hashShift -= nChildrenLog2 // hashShift is for the level parent is at. We need to go deeper. - oi := (oldHash >> hashShift) & nChildrenMask - ni := (newHash >> hashShift) & nChildrenMask - if oi != ni { - newIndirect.children[oi].Store(&oldEntry.node) - newIndirect.children[ni].Store(&newEntry.node) - break - } - nextIndirect := newIndirectNode(newIndirect) - newIndirect.children[oi].Store(&nextIndirect.node) - newIndirect = nextIndirect - } - return &top.node -} - -// cleanup deletes the entry corresponding to wp in the canon map, if it's -// still in the map. wp must have a Value method that returns nil by the -// time this function is called. hash must be the hash of the value that -// wp once pointed to (that is, the hash of *wp.Value()). -func (m *canonMap[T]) cleanup(hash uintptr, wp weak.Pointer[T]) { - var i *indirect[T] - var hashShift uint - var slot *atomic.Pointer[node[T]] - var n *node[T] - for { - // Find wp in the map by following hash. - i = m.root.Load() - hashShift = 8 * goarch.PtrSize - haveEntry := false - for hashShift != 0 { - hashShift -= nChildrenLog2 - - slot = &i.children[(hash>>hashShift)&nChildrenMask] - n = slot.Load() - if n == nil { - // We found a nil slot, already deleted. - return - } - if n.isEntry { - if !n.entry().hasWeakPointer(wp) { - // The weak pointer was already pruned. - return - } - haveEntry = true - break - } - i = n.indirect() - } - if !haveEntry { - panic("unique.canonMap: ran out of hash bits while iterating") - } - - // Grab the lock and double-check what we saw. - i.mu.Lock() - n = slot.Load() - if n != nil && n.isEntry { - // Prune the entry node without thinking too hard. If we do - // somebody else's work, such as someone trying to insert an - // entry with the same hash (probably the same value) then - // great, they'll back out without taking the lock. - newEntry := n.entry().prune() - if newEntry == nil { - slot.Store(nil) - } else { - slot.Store(&newEntry.node) - } - - // Delete interior nodes that are empty, up the tree. - // - // We'll hand-over-hand lock our way up the tree as we do this, - // since we need to delete each empty node's link in its parent, - // which requires the parents' lock. - for i.parent != nil && i.empty() { - if hashShift == 8*goarch.PtrSize { - panic("internal/sync.HashTrieMap: ran out of hash bits while iterating") - } - hashShift += nChildrenLog2 - - // Delete the current node in the parent. - parent := i.parent - parent.mu.Lock() - i.dead.Store(true) // Could be done outside of parent's lock. - parent.children[(hash>>hashShift)&nChildrenMask].Store(nil) - i.mu.Unlock() - i = parent - } - i.mu.Unlock() - return - } - // We have to start over. - i.mu.Unlock() - } -} - -// node is the header for a node. It's polymorphic and -// is actually either an entry or an indirect. -type node[T comparable] struct { - isEntry bool -} - -func (n *node[T]) entry() *entry[T] { - if !n.isEntry { - panic("called entry on non-entry node") - } - return (*entry[T])(unsafe.Pointer(n)) -} - -func (n *node[T]) indirect() *indirect[T] { - if n.isEntry { - panic("called indirect on entry node") - } - return (*indirect[T])(unsafe.Pointer(n)) -} - -const ( - // 16 children. This seems to be the sweet spot for - // load performance: any smaller and we lose out on - // 50% or more in CPU performance. Any larger and the - // returns are minuscule (~1% improvement for 32 children). - nChildrenLog2 = 4 - nChildren = 1 << nChildrenLog2 - nChildrenMask = nChildren - 1 -) - -// indirect is an internal node in the hash-trie. -type indirect[T comparable] struct { - node[T] - dead atomic.Bool - parent *indirect[T] - mu sync.Mutex // Protects mutation to children and any children that are entry nodes. - children [nChildren]atomic.Pointer[node[T]] -} - -func newIndirectNode[T comparable](parent *indirect[T]) *indirect[T] { - return &indirect[T]{node: node[T]{isEntry: false}, parent: parent} -} - -func (i *indirect[T]) empty() bool { - for j := range i.children { - if i.children[j].Load() != nil { - return false - } - } - return true -} - -// entry is a leaf node in the hash-trie. -type entry[T comparable] struct { - node[T] - overflow atomic.Pointer[entry[T]] // Overflow for hash collisions. - key weak.Pointer[T] - hash uintptr -} - -func newEntryNode[T comparable](key T, hash uintptr) (*entry[T], *T, weak.Pointer[T]) { - k := new(T) - *k = key - wp := weak.Make(k) - return &entry[T]{ - node: node[T]{isEntry: true}, - key: wp, - hash: hash, - }, k, wp -} - -// lookup finds the entry in the overflow chain that has the provided key. -// -// Returns the key's canonical pointer and the weak pointer for that canonical pointer. -func (e *entry[T]) lookup(key T) (*T, weak.Pointer[T]) { - for e != nil { - s := e.key.Value() - if s != nil && *s == key { - return s, e.key - } - e = e.overflow.Load() - } - return nil, weak.Pointer[T]{} -} - -// hasWeakPointer returns true if the provided weak pointer can be found in the overflow chain. -func (e *entry[T]) hasWeakPointer(wp weak.Pointer[T]) bool { - for e != nil { - if e.key == wp { - return true - } - e = e.overflow.Load() - } - return false -} - -// prune removes all entries in the overflow chain whose keys are nil. -// -// The caller must hold the lock on e's parent node. -func (e *entry[T]) prune() *entry[T] { - // Prune the head of the list. - for e != nil { - if e.key.Value() != nil { - break - } - e = e.overflow.Load() - } - if e == nil { - return nil - } - - // Prune individual nodes in the list. - newHead := e - i := &e.overflow - e = i.Load() - for e != nil { - if e.key.Value() != nil { - i = &e.overflow - } else { - i.Store(e.overflow.Load()) - } - e = e.overflow.Load() - } - return newHead -} - -// Pull in runtime.rand so that we don't need to take a dependency -// on math/rand/v2. -// -//go:linkname runtime_rand runtime.rand -func runtime_rand() uint64 |