Swift Source Code: ContiguousArray

ContiguousArray

A contiguously stored array.

ContiguousArray<Element> is the fastest and simplest of the three(ContiguousArray, Array, ArraySlice) – use this when you need “C array” performance. The elements of a ContiguousArray are always stored contiguously in memory.

The ContiguousArray type is a specialized array that always stores its elements in a contiguous region of memory. This contrasts with Array, which can store its elements in either a contiguous region of memory or an NSArray instance if its Element type is a class or @objc protocol.

If your array’s Element type is a class or @objc protocol and you do not need to bridge the array to NSArray or pass the array to Objective-C APIs, using ContiguousArray may be more efficient and have more predictable performance than Array.

If the array’s Element type is a struct or enumeration, Array and ContiguousArray should have similar efficiency.

ContiguousArray 是对 _buffer: _ContiguousArrayBuffer<Element> 的一个封装.

_buffer 是一个对 _storage: __ContiguousArrayStorageBase的封装.

Types

ContiguousArray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@frozen
public struct ContiguousArray<Element>: _DestructorSafeContainer {
  @usableFromInline
  internal typealias _Buffer = _ContiguousArrayBuffer<Element>

  @usableFromInline
  internal var _buffer: _Buffer

  /// Initialization from an existing buffer does not have "array.init"
  /// semantics because the caller may retain an alias to buffer.
  @inlinable
  internal init(_buffer: _Buffer) {
    self._buffer = _buffer
  }
}

_ContiguousArrayBuffer: _ArrayBufferProtocol

1
2
3
4
5
6
@usableFromInline
@frozen
internal struct _ContiguousArrayBuffer<Element>: _ArrayBufferProtocol {
  @usableFromInline
  internal var _storage: __ContiguousArrayStorageBase
}

// __ContiguousArrayStorageBase supplies the implementation of the
// _NSArrayCore API (and thus, NSArray the API) for our
// _ContiguousArrayStorage. We can’t put this implementation
// directly on _ContiguousArrayStorage because generic classes can’t
// override Objective-C selectors.
//

ContiguousArrayStorageBase: SwiftNativeNSArrayWithContiguousStorage

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
/// Base class of the heap buffer backing arrays.  
///
/// NOTE: older runtimes called this _ContiguousArrayStorageBase. The
/// two must coexist, so it was renamed. The old name must not be used
/// in the new runtime.
// 大部分方法需要子类实现
@usableFromInline
@_fixed_layout
internal class __ContiguousArrayStorageBase: __SwiftNativeNSArrayWithContiguousStorage { 
  @Usablefrominline
  final var countAndCapacity: _ArrayBody

  @inlinable
  @nonobjc
  internal init(_doNotCallMeBase: ()) {
    _internalInvariantFailure("creating instance of __ContiguousArrayStorageBase")
  }
  
#if _runtime(_ObjC)
  internal override func withUnsafeBufferOfObjects<R>(
    _ body: (UnsafeBufferPointer<AnyObject>) throws -> R
  ) rethrows -> R {
    if let result = try _withVerbatimBridgedUnsafeBuffer(body) {
      return result
    }
    _internalInvariantFailure(
      "Can't use a buffer of non-verbatim-bridged elements as an NSArray")
  }

  /// If the stored type is bridged verbatim, invoke `body` on an
  /// `UnsafeBufferPointer` to the elements and return the result.
  /// Otherwise, return `nil`.
  internal func _withVerbatimBridgedUnsafeBuffer<R>(
    _ body: (UnsafeBufferPointer<AnyObject>) throws -> R
  ) rethrows -> R? {
    _internalInvariantFailure(
      "Concrete subclasses must implement _withVerbatimBridgedUnsafeBuffer")
  }

  internal func _getNonVerbatimBridgingBuffer() -> _BridgingBuffer {
    _internalInvariantFailure(
      "Concrete subclasses must implement _getNonVerbatimBridgingBuffer")
  }
  
  @objc(mutableCopyWithZone:)
  dynamic internal func mutableCopy(with _: _SwiftNSZone?) -> AnyObject {
    let arr = Array<AnyObject>(_ContiguousArrayBuffer(self))
    return _SwiftNSMutableArray(arr)
  }
  
  @objc(indexOfObjectIdenticalTo:)
  dynamic internal func index(ofObjectIdenticalTo object: AnyObject) -> Int {
    let arr = Array<AnyObject>(_ContiguousArrayBuffer(self))
    return arr.firstIndex { $0 === object } ?? NSNotFound
  }
#endif

@inlinable
  internal func canStoreElements(ofDynamicType _: Any.Type) -> Bool {
    _internalInvariantFailure(
      "Concrete subclasses must implement canStoreElements(ofDynamicType:)")
  }

  /// A type that every element in the array is.
  @inlinable
  internal var staticElementType: Any.Type {
    _internalInvariantFailure(
      "Concrete subclasses must implement staticElementType")
  }
  
  @inlinable
  deinit {
    _internalInvariant(
      self !== _emptyArrayStorage, "Deallocating empty array storage?!")
  }
}

}

// 直接对内存进行操作
@usableFromInline
@frozen
internal struct _ContiguousArrayBuffer<Element>: _ArrayBufferProtocol {
  @usableFromInline
  internal var _storage: __ContiguousArrayStorageBase

  /// Make a buffer with uninitialized elements.  After using this
  /// method, you must either initialize the `count` elements at the
  /// result's `.firstElementAddress` or set the result's `.count`
  /// to zero.
  @inlinable
  internal init(
    _uninitializedCount uninitializedCount: Int,
    minimumCapacity: Int
  ) {
    let realMinimumCapacity = Swift.max(uninitializedCount, minimumCapacity)
    if realMinimumCapacity == 0 {
      self = _ContiguousArrayBuffer<Element>()
    }
    else {
      // 初始化一个`_ContiguousArrayStorage<Element>`的实例,
      // 并在后面申请`realMinimumCapacity`大小的连续内存
      // 然后更新StorageHeader
      _storage = Builtin.allocWithTailElems_1(
         getContiguousArrayStorageType(for: Element.self),
         realMinimumCapacity._builtinWordValue, Element.self)

      let storageAddr = UnsafeMutableRawPointer(Builtin.bridgeToRawPointer(_storage))
      if let allocSize = _mallocSize(ofAllocation: storageAddr) {
        let endAddr = storageAddr + allocSize
        let realCapacity = endAddr.assumingMemoryBound(to: Element.self) - firstElementAddress
        _initStorageHeader(
          count: uninitializedCount, capacity: realCapacity)
      } else {
        _initStorageHeader(
          count: uninitializedCount, capacity: realMinimumCapacity)
      }
    }
  }

  /// Initialize the body part of our storage.
  ///
  /// - Warning: does not initialize elements
  @inlinable
  internal func _initStorageHeader(count: Int, capacity: Int) {
#if _runtime(_ObjC)
    let verbatim = _isBridgedVerbatimToObjectiveC(Element.self)
#else
    let verbatim = false
#endif
    // 赋值`_storage`中的`countAndCapacity`
    // We can initialize by assignment because _ArrayBody is a trivial type,
    // i.e. contains no references.
    _storage.countAndCapacity = _ArrayBody(
      count: count,
      capacity: capacity,
      elementTypeIsBridgedVerbatim: verbatim)
  }

@frozen
@usableFromInline
internal struct _ArrayBody {
  @usableFromInline
  internal var _storage: _SwiftArrayBodyStorage

  @inlinable
  internal init(
    count: Int, capacity: Int, elementTypeIsBridgedVerbatim: Bool = false
  ) {
    _internalInvariant(count >= 0)
    _internalInvariant(capacity >= 0)
    
    _storage = _SwiftArrayBodyStorage(
      count: count,
      _capacityAndFlags:
        (UInt(truncatingIfNeeded: capacity) &<< 1) |
        (elementTypeIsBridgedVerbatim ? 1 : 0))
  }


struct _SwiftArrayBodyStorage {
  __swift_intptr_t count;
  __swift_uintptr_t _capacityAndFlags;
};

// Swift Array 转换NSArray O(1)

SwiftNativeNSArrayWithContiguousStorage : SwiftNativeNSArray (NSArray)

__SwiftNativeNSArrayWithContiguousStorage (non-objc)

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
/// An `NSArray` with Swift-native reference counting and contiguous
/// storage.
///
/// NOTE: older runtimes called this
/// _SwiftNativeNSArrayWithContiguousStorage. The two must coexist, so
/// it was renamed. The old name must not be used in the new runtime.
@_fixed_layout
@usableFromInline
internal class __SwiftNativeNSArrayWithContiguousStorage
  : __SwiftNativeNSArray { // Provides NSArray inheritance and native refcounting

  @inlinable
  @nonobjc internal override init() { super.init() }

  @inlinable
  deinit {}

  // Operate on our contiguous storage
  internal func withUnsafeBufferOfObjects<R>(
    _ body: (UnsafeBufferPointer<AnyObject>) throws -> R
  ) rethrows -> R {
    _internalInvariantFailure(
      "Must override withUnsafeBufferOfObjects in derived classes")
  }
}

@_fixed_layout
@usableFromInline
internal class __SwiftNativeNSArray {
  @inlinable
  internal init() {}
  @inlinable
  deinit {}
}

// Empty shim version for non-objc platforms.
@usableFromInline
@_fixed_layout
internal class __SwiftNativeNSArrayWithContiguousStorage {
  @inlinable
  internal init() {}

  @inlinable
  deinit {}
}

__SwiftNativeNSArray

provides NSArray inheritance and native refcounting

1
2
3
4
5
6
7
8
@_fixed_layout
@usableFromInline
internal class __SwiftNativeNSArray {
  @inlinable
  internal init() {}
  @inlinable
  deinit {}
}

Functions

Copy on Write

以 append 为例:

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
/// Adds a new element at the end of the array.
///
/// Use this method to append a single element to the end of a mutable array.
///
///     var numbers = [1, 2, 3, 4, 5]
///     numbers.append(100)
///     print(numbers)
///     // Prints "[1, 2, 3, 4, 5, 100]"
///
/// Because arrays increase their allocated capacity using an exponential
/// strategy, appending a single element to an array is an O(1) operation
/// when averaged over many calls to the `append(_:)` method. When an array
/// has additional capacity and is not sharing its storage with another
/// instance, appending an element is O(1). When an array needs to
/// reallocate storage before appending or its storage is shared with
/// another copy, appending is O(*n*), where *n* is the length of the array.
///
/// - Parameter newElement: The element to append to the array.
///
/// - Complexity: O(1) on average, over many calls to `append(_:)` on the
///   same array.
@inlinable
@_semantics("array.append_element")
public mutating func append(_ newElement: __owned Element) {
  // Separating uniqueness check and capacity check allows hoisting the
  // uniqueness check out of a loop.
  _makeUniqueAndReserveCapacityIfNotUnique()
  let oldCount = _buffer.mutableCount
  _reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)
  _appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)
  _endMutation()
}

@inlinable
@_semantics("array.make_mutable")
internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {
  if _slowPath(!_buffer.beginCOWMutation()) {
    _createNewBuffer(bufferIsUnique: false,
                     minimumCapacity: count &+ 1,
                     growForAppend: true)
  }
}

/// Creates a new buffer, replacing the current buffer.
///
/// If `bufferIsUnique` is true, the buffer is assumed to be uniquely
/// referenced by this array and the elements are moved - instead of copied -
/// to the new buffer.
/// The `minimumCapacity` is the lower bound for the new capacity.
/// If `growForAppend` is true, the new capacity is calculated using
/// `_growArrayCapacity`.
@_alwaysEmitIntoClient
@inline(never)
internal mutating func _createNewBuffer(
  bufferIsUnique: Bool, minimumCapacity: Int, growForAppend: Bool
) {
  _internalInvariant(!bufferIsUnique || _buffer.isUniquelyReferenced())
  _buffer = _buffer._consumeAndCreateNew(bufferIsUnique: bufferIsUnique,
                                         minimumCapacity: minimumCapacity,
                                         growForAppend: growForAppend)
}

/// Creates and returns a new uniquely referenced buffer which is a copy of
/// this buffer.
///
/// If `bufferIsUnique` is true, the buffer is assumed to be uniquely
/// referenced and the elements are moved - instead of copied - to the new
/// buffer.
/// The `minimumCapacity` is the lower bound for the new capacity.
/// If `growForAppend` is true, the new capacity is calculated using
/// `_growArrayCapacity`, but at least kept at `minimumCapacity`.
///
/// This buffer is consumed, i.e. it's released.
@_alwaysEmitIntoClient
@inline(never)
@_semantics("optimize.sil.specialize.owned2guarantee.never")
internal __consuming func _consumeAndCreateNew(
  bufferIsUnique: Bool, minimumCapacity: Int, growForAppend: Bool
) -> _ArrayBuffer {
  let newCapacity = _growArrayCapacity(oldCapacity: capacity,
                                       minimumCapacity: minimumCapacity,
                                       growForAppend: growForAppend)
  let c = count
  _internalInvariant(newCapacity >= c)
  
  let newBuffer = _ContiguousArrayBuffer<Element>(
    _uninitializedCount: c, minimumCapacity: newCapacity)

  /// 当buffer is Unique, 直接不进行copy，操作数据
  if bufferIsUnique {
    // As an optimization, if the original buffer is unique, we can just move
    // the elements instead of copying.
    let dest = newBuffer.firstElementAddress
    dest.moveInitialize(from: mutableFirstElementAddress,
                        count: c)
    _native.mutableCount = 0
  } else {
    /// 进行复制
    _copyContents(
      subRange: 0..<c,
      initializing: newBuffer.mutableFirstElementAddress)
  }
  return _ArrayBuffer(_buffer: newBuffer, shiftedToStartIndex: 0)
}