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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2018 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
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
/// Initializes a `Dictionary` from unique members.
///
/// Using a builder can be faster than inserting members into an empty
/// `Dictionary`.
@frozen
public // SPI(Foundation)
struct _DictionaryBuilder<Key: Hashable, Value> {
@usableFromInline
internal var _target: _NativeDictionary<Key, Value>
@usableFromInline
internal let _requestedCount: Int
@inlinable
public init(count: Int) {
_target = _NativeDictionary(capacity: count)
_requestedCount = count
}
@inlinable
public mutating func add(key newKey: Key, value: Value) {
_precondition(_target.count < _requestedCount,
"Can't add more members than promised")
_target._unsafeInsertNew(key: newKey, value: value)
}
@inlinable
public __consuming func take() -> Dictionary<Key, Value> {
_precondition(_target.count == _requestedCount,
"The number of members added does not match the promised count")
return Dictionary(_native: _target)
}
}
@available(*, unavailable)
extension _DictionaryBuilder: Sendable {}
extension Dictionary {
/// Creates a new dictionary with the specified capacity, then calls the given
/// closure to initialize its contents.
///
/// Foundation uses this initializer to bridge the contents of an NSDictionary
/// instance without allocating a pair of intermediary buffers. Pass the
/// required capacity and a closure that can initialize the dictionary's
/// elements. The closure must return `c`, the number of initialized elements
/// in both buffers, such that the elements in the range `0..<c` are
/// initialized and the elements in the range `c..<capacity` are
/// uninitialized.
///
/// The resulting dictionary has a `count` less than or equal to `c`.
/// If some of the initialized keys were duplicates, the actual count is less.
/// This cannot happen for any other reasons or if `allowingDuplicates` is false.
///
/// The buffers passed to the closure are only valid for the duration of the
/// call. After the closure returns, this initializer moves all initialized
/// elements into their correct buckets.
///
/// - Parameters:
/// - capacity: The capacity of the new dictionary.
/// - allowingDuplicates: If false, then the caller guarantees that all keys
/// are unique. This promise isn't verified -- if it turns out to be
/// false, then the resulting dictionary won't be valid.
/// - body: A closure that can initialize the dictionary's elements. This
/// closure must return the count of the initialized elements, starting at
/// the beginning of the buffer.
@_alwaysEmitIntoClient // Introduced in 5.1
public // SPI(Foundation)
init(
_unsafeUninitializedCapacity capacity: Int,
allowingDuplicates: Bool,
initializingWith initializer: (
_ keys: UnsafeMutableBufferPointer<Key>,
_ values: UnsafeMutableBufferPointer<Value>
) -> Int
) {
self.init(_native: _NativeDictionary(
_unsafeUninitializedCapacity: capacity,
allowingDuplicates: allowingDuplicates,
initializingWith: initializer))
}
}
extension _NativeDictionary {
@_alwaysEmitIntoClient // Introduced in 5.1
internal init(
_unsafeUninitializedCapacity capacity: Int,
allowingDuplicates: Bool,
initializingWith initializer: (
_ keys: UnsafeMutableBufferPointer<Key>,
_ values: UnsafeMutableBufferPointer<Value>
) -> Int
) {
self.init(capacity: capacity)
let initializedCount = initializer(
UnsafeMutableBufferPointer(start: _keys, count: capacity),
UnsafeMutableBufferPointer(start: _values, count: capacity))
_precondition(initializedCount >= 0 && initializedCount <= capacity)
_storage._count = initializedCount
// Hash initialized elements and move each of them into their correct
// buckets.
//
// - We have some number of unprocessed elements at the start of the
// key/value buffers -- buckets up to and including `bucket`. Everything
// in this region is either unprocessed or in use. There are no
// uninitialized entries in it.
//
// - Everything after `bucket` is either uninitialized or in use. This
// region works exactly like regular dictionary storage.
//
// - "in use" is tracked by the bitmap in `hashTable`, the same way it would
// be for a working Dictionary.
//
// Each iteration of the loop below processes an unprocessed element, and/or
// reduces the size of the unprocessed region, while ensuring the above
// invariants.
var bucket = _HashTable.Bucket(offset: initializedCount - 1)
while bucket.offset >= 0 {
if hashTable._isOccupied(bucket) {
// We've moved an element here in a previous iteration.
bucket.offset -= 1
continue
}
// Find the target bucket for this entry and mark it as in use.
let target: Bucket
if _isDebugAssertConfiguration() || allowingDuplicates {
let (b, found) = find(_keys[bucket.offset])
if found {
_internalInvariant(b != bucket)
_precondition(allowingDuplicates, "Duplicate keys found")
// Discard duplicate entry.
uncheckedDestroy(at: bucket)
_storage._count -= 1
bucket.offset -= 1
continue
}
hashTable.insert(b)
target = b
} else {
let hashValue = self.hashValue(for: _keys[bucket.offset])
target = hashTable.insertNew(hashValue: hashValue)
}
if target > bucket {
// The target is outside the unprocessed region. We can simply move the
// entry, leaving behind an uninitialized bucket.
moveEntry(from: bucket, to: target)
// Restore invariants by lowering the region boundary.
bucket.offset -= 1
} else if target == bucket {
// Already in place.
bucket.offset -= 1
} else {
// The target bucket is also in the unprocessed region. Swap the current
// item into place, then try again with the swapped-in value, so that we
// don't lose it.
swapEntry(target, with: bucket)
}
}
// When there are no more unprocessed entries, we're left with a valid
// Dictionary.
}
}
|
