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
|
//===----------------------------------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
/// The storage header in a hash tree node. This includes data about the
/// current size and capacity of the node's storage region, as well as
/// information about the currently occupied hash table buckets.
@usableFromInline
@frozen
internal struct _HashNodeHeader {
@usableFromInline
internal var itemMap: _Bitmap
@usableFromInline
internal var childMap: _Bitmap
@usableFromInline
internal var _byteCapacity: UInt32
@usableFromInline
internal var _bytesFree: UInt32
@inlinable
internal init(byteCapacity: Int) {
assert(byteCapacity >= 0 && byteCapacity <= UInt32.max)
self.itemMap = .empty
self.childMap = .empty
self._byteCapacity = UInt32(truncatingIfNeeded: byteCapacity)
self._bytesFree = self._byteCapacity
}
}
extension _HashNodeHeader {
@inlinable @inline(__always)
internal var byteCapacity: Int {
get { Int(truncatingIfNeeded: _byteCapacity) }
}
@inlinable
internal var bytesFree: Int {
@inline(__always)
get { Int(truncatingIfNeeded: _bytesFree) }
set {
assert(newValue >= 0 && newValue <= UInt32.max)
_bytesFree = UInt32(truncatingIfNeeded: newValue)
}
}
}
extension _HashNodeHeader {
@inlinable @inline(__always)
internal var isEmpty: Bool {
return itemMap.isEmpty && childMap.isEmpty
}
@inlinable @inline(__always)
internal var isCollisionNode: Bool {
!itemMap.isDisjoint(with: childMap)
}
@inlinable @inline(__always)
internal var hasChildren: Bool {
itemMap != childMap && !childMap.isEmpty
}
@inlinable @inline(__always)
internal var hasItems: Bool {
!itemMap.isEmpty
}
@inlinable
internal var childCount: Int {
itemMap == childMap ? 0 : childMap.count
}
@inlinable
internal var itemCount: Int {
(itemMap == childMap
? Int(truncatingIfNeeded: itemMap._value)
: itemMap.count)
}
@inlinable
internal var hasSingletonChild: Bool {
itemMap.isEmpty && childMap.hasExactlyOneMember
}
@inlinable
internal var hasSingletonItem: Bool {
if itemMap == childMap {
return itemMap._value == 1
}
return childMap.isEmpty && itemMap.hasExactlyOneMember
}
@inlinable @inline(__always)
internal var childrenEndSlot: _HashSlot {
_HashSlot(childCount)
}
@inlinable @inline(__always)
internal var itemsEndSlot: _HashSlot {
_HashSlot(itemCount)
}
@inlinable
internal var collisionCount: Int {
get {
assert(isCollisionNode)
return Int(truncatingIfNeeded: itemMap._value)
}
set {
assert(isCollisionNode || childMap.isEmpty)
assert(newValue > 0 && newValue < _Bitmap.Value.max)
itemMap._value = _Bitmap.Value(truncatingIfNeeded: newValue)
childMap = itemMap
}
}
}
extension _HashNodeHeader {
@inlinable
internal mutating func clear() {
itemMap = .empty
childMap = .empty
bytesFree = byteCapacity
}
}
|
