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
175
176
177
178
179
180
181
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2021 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
//
//===----------------------------------------------------------------------===//
/// This file is copied from swift-collections and should not be modified here.
/// Rather all changes should be made to swift-collections and copied back.
import Swift
extension _Deque {
struct _Storage {
internal typealias _Buffer = ManagedBufferPointer<_DequeBufferHeader, Element>
internal var _buffer: _Buffer
internal init(_buffer: _Buffer) {
self._buffer = _buffer
}
}
}
extension _Deque._Storage: CustomStringConvertible {
internal var description: String {
"Deque<\(Element.self)>._Storage\(_buffer.header)"
}
}
extension _Deque._Storage {
internal init() {
self.init(_buffer: _Buffer(unsafeBufferObject: _emptyDequeStorage))
}
internal init(_ object: _DequeBuffer<Element>) {
self.init(_buffer: _Buffer(unsafeBufferObject: object))
}
internal init(minimumCapacity: Int) {
let object = _DequeBuffer<Element>.create(
minimumCapacity: minimumCapacity,
makingHeaderWith: {
#if os(OpenBSD)
let capacity = minimumCapacity
#else
let capacity = $0.capacity
#endif
return _DequeBufferHeader(capacity: capacity, count: 0, startSlot: .zero)
})
self.init(_buffer: _Buffer(unsafeBufferObject: object))
}
}
extension _Deque._Storage {
#if COLLECTIONS_INTERNAL_CHECKS
internal func _checkInvariants() {
_buffer.withUnsafeMutablePointerToHeader { $0.pointee._checkInvariants() }
}
#else
internal func _checkInvariants() {}
#endif // COLLECTIONS_INTERNAL_CHECKS
}
extension _Deque._Storage {
internal var identity: AnyObject { _buffer.buffer }
internal var capacity: Int {
_buffer.withUnsafeMutablePointerToHeader { $0.pointee.capacity }
}
internal var count: Int {
_buffer.withUnsafeMutablePointerToHeader { $0.pointee.count }
}
internal var startSlot: _DequeSlot {
_buffer.withUnsafeMutablePointerToHeader { $0.pointee.startSlot
}
}
}
extension _Deque._Storage {
internal typealias Index = Int
internal typealias _UnsafeHandle = _Deque._UnsafeHandle
internal func read<R>(_ body: (_UnsafeHandle) throws -> R) rethrows -> R {
try _buffer.withUnsafeMutablePointers { header, elements in
let handle = _UnsafeHandle(header: header,
elements: elements,
isMutable: false)
return try body(handle)
}
}
internal func update<R>(_ body: (_UnsafeHandle) throws -> R) rethrows -> R {
try _buffer.withUnsafeMutablePointers { header, elements in
let handle = _UnsafeHandle(header: header,
elements: elements,
isMutable: true)
return try body(handle)
}
}
}
extension _Deque._Storage {
/// Return a boolean indicating whether this storage instance is known to have
/// a single unique reference. If this method returns true, then it is safe to
/// perform in-place mutations on the deque.
internal mutating func isUnique() -> Bool {
_buffer.isUniqueReference()
}
/// Ensure that this storage refers to a uniquely held buffer by copying
/// elements if necessary.
internal mutating func ensureUnique() {
if isUnique() { return }
self._makeUniqueCopy()
}
internal mutating func _makeUniqueCopy() {
self = self.read { $0.copyElements() }
}
/// The growth factor to use to increase storage size to make place for an
/// insertion.
internal static var growthFactor: Double { 1.5 }
internal func _growCapacity(
to minimumCapacity: Int,
linearly: Bool
) -> Int {
if linearly { return Swift.max(capacity, minimumCapacity) }
return Swift.max(Int((Self.growthFactor * Double(capacity)).rounded(.up)),
minimumCapacity)
}
/// Ensure that we have a uniquely referenced buffer with enough space to
/// store at least `minimumCapacity` elements.
///
/// - Parameter minimumCapacity: The minimum number of elements the buffer
/// needs to be able to hold on return.
///
/// - Parameter linearGrowth: If true, then don't use an exponential growth
/// factor when reallocating the buffer -- just allocate space for the
/// requested number of elements
internal mutating func ensureUnique(
minimumCapacity: Int,
linearGrowth: Bool = false
) {
let unique = isUnique()
if _slowPath(capacity < minimumCapacity || !unique) {
_ensureUnique(minimumCapacity: minimumCapacity, linearGrowth: linearGrowth)
}
}
internal mutating func _ensureUnique(
minimumCapacity: Int,
linearGrowth: Bool
) {
if capacity >= minimumCapacity {
assert(!self.isUnique())
self = self.read { $0.copyElements() }
} else if isUnique() {
let minimumCapacity = _growCapacity(to: minimumCapacity, linearly: linearGrowth)
self = self.update { source in
source.moveElements(minimumCapacity: minimumCapacity)
}
} else {
let minimumCapacity = _growCapacity(to: minimumCapacity, linearly: linearGrowth)
self = self.read { source in
source.copyElements(minimumCapacity: minimumCapacity)
}
}
}
}
|
