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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2022 - 2024 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
//
//===----------------------------------------------------------------------===//
@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)
}
}
}
|
