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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
//===----------------------------------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
// MARK: Node-level removal operations
extension _HashNode.UnsafeHandle {
/// Remove and return the item at `slot`, increasing the amount of free
/// space available in the node.
///
/// `itemMap` must not yet reflect the removal at the time this
/// function is called. This method does not update `itemMap`.
@inlinable
internal func _removeItem<R>(
at slot: _HashSlot,
by remover: (UnsafeMutablePointer<Element>) -> R
) -> R {
assertMutable()
let c = itemCount
assert(slot.value < c)
let stride = MemoryLayout<Element>.stride
bytesFree &+= stride
let start = _memory
.advanced(by: byteCapacity &- stride &* c)
.assumingMemoryBound(to: Element.self)
let prefix = c &- 1 &- slot.value
let q = start + prefix
defer {
(start + 1).moveInitialize(from: start, count: prefix)
}
return remover(q)
}
/// Remove and return the child at `slot`, increasing the amount of free
/// space available in the node.
///
/// `childMap` must not yet reflect the removal at the time this
/// function is called. This method does not update `childMap`.
@inlinable
internal func _removeChild(at slot: _HashSlot) -> _HashNode {
assertMutable()
assert(!isCollisionNode)
let count = childCount
assert(slot.value < count)
bytesFree &+= MemoryLayout<_HashNode>.stride
let q = _childrenStart + slot.value
let child = q.move()
q.moveInitialize(from: q + 1, count: count &- 1 &- slot.value)
return child
}
}
extension _HashNode {
@inlinable
internal mutating func removeItem(
at bucket: _Bucket
) -> Element {
let slot = read { $0.itemMap.slot(of: bucket) }
return removeItem(at: bucket, slot, by: { $0.move() })
}
@inlinable
internal mutating func removeItem(
at bucket: _Bucket, _ slot: _HashSlot
) -> Element {
removeItem(at: bucket, slot, by: { $0.move() })
}
/// Remove the item at `slot`, increasing the amount of free
/// space available in the node.
///
/// The closure `remove` is called to perform the deinitialization of the
/// storage slot corresponding to the item to be removed.
@inlinable
internal mutating func removeItem<R>(
at bucket: _Bucket, _ slot: _HashSlot,
by remover: (UnsafeMutablePointer<Element>) -> R
) -> R {
defer { _invariantCheck() }
assert(count > 0)
count &-= 1
return update {
let old = $0._removeItem(at: slot, by: remover)
if $0.isCollisionNode {
assert(slot.value < $0.collisionCount)
$0.collisionCount &-= 1
} else {
assert($0.itemMap.contains(bucket))
assert($0.itemMap.slot(of: bucket) == slot)
$0.itemMap.remove(bucket)
}
return old
}
}
@inlinable
internal mutating func removeChild(
at bucket: _Bucket, _ slot: _HashSlot
) -> _HashNode {
assert(!isCollisionNode)
let child: _HashNode = update {
assert($0.childMap.contains(bucket))
assert($0.childMap.slot(of: bucket) == slot)
let child = $0._removeChild(at: slot)
$0.childMap.remove(bucket)
return child
}
assert(self.count >= child.count)
self.count &-= child.count
return child
}
@inlinable
internal mutating func removeSingletonItem() -> Element {
defer { _invariantCheck() }
assert(count == 1)
count = 0
return update {
assert($0.hasSingletonItem)
let old = $0._removeItem(at: .zero) { $0.move() }
$0.clear()
return old
}
}
@inlinable
internal mutating func removeSingletonChild() -> _HashNode {
defer { _invariantCheck() }
let child: _HashNode = update {
assert($0.hasSingletonChild)
let child = $0._removeChild(at: .zero)
$0.childMap = .empty
return child
}
assert(self.count == child.count)
self.count = 0
return child
}
}
|
