mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
134 lines
3.4 KiB
Swift
134 lines
3.4 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 2022 - 2026 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
// SPDX-License-Identifier: Apache-2.0 WITH Swift-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
@usableFromInline
|
|
@frozen
|
|
internal struct _HashTreeIterator {
|
|
@usableFromInline
|
|
internal struct _Opaque {
|
|
internal var ancestorSlots: _AncestorHashSlots
|
|
internal var ancestorNodes: _HashStack<_UnmanagedHashNode>
|
|
internal var level: _HashLevel
|
|
internal var isAtEnd: Bool
|
|
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal init(_ root: _UnmanagedHashNode) {
|
|
self.ancestorSlots = .empty
|
|
self.ancestorNodes = _HashStack(filledWith: root)
|
|
self.level = .top
|
|
self.isAtEnd = false
|
|
}
|
|
}
|
|
|
|
@usableFromInline
|
|
internal let root: _RawHashStorage
|
|
|
|
@usableFromInline
|
|
internal var node: _UnmanagedHashNode
|
|
|
|
@usableFromInline
|
|
internal var slot: _HashSlot
|
|
|
|
@usableFromInline
|
|
internal var endSlot: _HashSlot
|
|
|
|
@usableFromInline
|
|
internal var _o: _Opaque
|
|
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal init(root: __shared _RawHashNode) {
|
|
self.root = root.storage
|
|
self.node = root.unmanaged
|
|
self.slot = .zero
|
|
self.endSlot = node.itemsEndSlot
|
|
self._o = _Opaque(self.node)
|
|
|
|
if node.hasItems { return }
|
|
if node.hasChildren {
|
|
_descendToLeftmostItem(ofChildAtSlot: .zero)
|
|
} else {
|
|
self._o.isAtEnd = true
|
|
}
|
|
}
|
|
}
|
|
|
|
extension _HashTreeIterator: IteratorProtocol {
|
|
@inlinable
|
|
internal mutating func next(
|
|
) -> (node: _UnmanagedHashNode, slot: _HashSlot)? {
|
|
guard slot < endSlot else {
|
|
return _next()
|
|
}
|
|
defer { slot = slot.next() }
|
|
return (node, slot)
|
|
}
|
|
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal mutating func _next(
|
|
) -> (node: _UnmanagedHashNode, slot: _HashSlot)? {
|
|
if _o.isAtEnd { return nil }
|
|
if node.hasChildren {
|
|
_descendToLeftmostItem(ofChildAtSlot: .zero)
|
|
slot = slot.next()
|
|
return (node, .zero)
|
|
}
|
|
while !_o.level.isAtRoot {
|
|
let nextChild = _ascend().next()
|
|
if nextChild < node.childrenEndSlot {
|
|
_descendToLeftmostItem(ofChildAtSlot: nextChild)
|
|
slot = slot.next()
|
|
return (node, .zero)
|
|
}
|
|
}
|
|
// At end
|
|
endSlot = node.itemsEndSlot
|
|
slot = endSlot
|
|
_o.isAtEnd = true
|
|
return nil
|
|
}
|
|
}
|
|
|
|
extension _HashTreeIterator {
|
|
internal mutating func _descend(toChildSlot childSlot: _HashSlot) {
|
|
assert(childSlot < node.childrenEndSlot)
|
|
_o.ancestorSlots[_o.level] = childSlot
|
|
_o.ancestorNodes.push(node)
|
|
_o.level = _o.level.descend()
|
|
node = node.unmanagedChild(at: childSlot)
|
|
slot = .zero
|
|
endSlot = node.itemsEndSlot
|
|
}
|
|
|
|
internal mutating func _ascend() -> _HashSlot {
|
|
assert(!_o.level.isAtRoot)
|
|
node = _o.ancestorNodes.pop()
|
|
_o.level = _o.level.ascend()
|
|
let childSlot = _o.ancestorSlots[_o.level]
|
|
_o.ancestorSlots.clear(_o.level)
|
|
return childSlot
|
|
}
|
|
|
|
internal mutating func _descendToLeftmostItem(
|
|
ofChildAtSlot childSlot: _HashSlot
|
|
) {
|
|
_descend(toChildSlot: childSlot)
|
|
while endSlot == .zero {
|
|
assert(node.hasChildren)
|
|
_descend(toChildSlot: .zero)
|
|
}
|
|
}
|
|
}
|