Swift - Array
[TOC]
Array是我們?nèi)粘４蚪坏婪浅６嗟囊粋€(gè)集合，下面我們就來(lái)研究一下它。
1. Array 的創(chuàng)建
1.1 初始化一個(gè)數(shù)組
Swift 中有很多創(chuàng)建Array的方式：
// 通過(guò)字面量初始化一個(gè)Int類型的Array
var numbers = [1, 2, 3, 4, 5]
// 通過(guò)字面量初始化一個(gè)String類型的Array
var strArray = ["element1", "element2", "element3", "element4",]
// 初始化一個(gè)Any類型的空Array，此處必須指定類型，否則會(huì)報(bào)編譯錯(cuò)誤
var emptyArray = Array<Any>()
var emptyArray1: [Any] = Array()
var emptyArray2: Array<Any> = Array()
var emptyArray3 = [Any]()
// 當(dāng)然為了防止訪問(wèn)越界我們也可以這樣初始化指定長(zhǎng)度和初始值的數(shù)組
var array = Array(repeating: 0, count: 10)
print(array[0])
以上代碼提供了數(shù)組的基本初始化方法。
- 可以通過(guò)字面量初始化
- 可以初始化空數(shù)組
- 可以初始化指定大小和初始值的數(shù)組
1.2 初始化數(shù)組的底層實(shí)現(xiàn)（SIL）
那么數(shù)組在底層是如何創(chuàng)建的呢？下面我們通過(guò)sil代碼進(jìn)行查看：
var numbers = [1, 2, 3, 4, 5]
在sil代碼中可以看到：
- 調(diào)用了
_allocateUninitializedArray函數(shù)初始了長(zhǎng)度為5，類型為Int的數(shù)組 - 然后為初始的數(shù)據(jù)，也就是個(gè)元組，取出里面的兩個(gè)指針賦值到%7和%8
- 根據(jù)%8的地址依次偏移，存儲(chǔ)數(shù)組中的元素
- 最后將%7的指針存儲(chǔ)到%3，也就是
numbers
其實(shí)這段代碼很好理解，但是有一個(gè)疑問(wèn)，大家都說(shuō)Array是一個(gè)值類型，那么我們剛才其實(shí)看到了alloc的調(diào)用，那么這是為什么呢？我們一步Swift源碼Swift 5.3.1中一探究竟。
1.3 源碼探索
1.3.1 _allocateUninitializedArray
首先我們搜索一下_allocateUninitializedArray方法，可以在ArrayShared.swift文件中找到。
在源碼中我們可以看到：
- 根據(jù)
count的不同做了不同的初始化 - 如果大于0會(huì)調(diào)用
allocWithTailElems_1初始化一個(gè)bufferObject - 然后調(diào)用
_adoptStorage初始一個(gè)元組 - 如果不大于0則調(diào)用
_allocateUninitialized初始化一個(gè)元組 - 最后返回這個(gè)元組
為了更好的跟代碼，我們?cè)?code>Debug調(diào)試一下：
繼續(xù)跟下去就到了這里：
很熟悉的創(chuàng)建HeapObject的代碼，接下來(lái)調(diào)用的是一個(gè)Array的函數(shù)，我我們跟一下：
1.3.2 _adoptStorage
在這個(gè)方法中我們可以看到：
- 首先創(chuàng)建了一個(gè)
_ContiguousArrayBuffer類型的變量 - 然后返回了一個(gè)元組
- 元組的第一個(gè)元素是一個(gè)
Array的實(shí)例對(duì)象 - 第二個(gè)元素是第一個(gè)元素的地址
- 元組的第一個(gè)元素是一個(gè)
所以在sil代碼中，%7和%8對(duì)應(yīng)的就是元組中的兩個(gè)值。%7是Array的地址，%8是原生首地址的地址。
1.3.3 _ContiguousArrayBuffer
_ContiguousArrayBuffer也是個(gè)結(jié)構(gòu)體。
1.4 Array 的內(nèi)存布局
下面我們來(lái)看看Array的內(nèi)存布局，從_adoptStorage方法繼續(xù)向上翻就可以看到Array這個(gè)結(jié)構(gòu)體中只有一個(gè)_buffer的成員變量。
下面我回到_ContiguousArrayBuffer中繼續(xù)探索，在該結(jié)構(gòu)體的最后，我們可以看到_storage屬性的定義。
在其初始化的時(shí)候也都能看到對(duì)_storage的初始化：
_storage的類型是__ContiguousArrayStorageBase，下面我們就研究一下__ContiguousArrayStorageBase
1.4.1 __ContiguousArrayStorageBase
__ContiguousArrayStorageBase是一個(gè)類，定義在SwiftNativeNSArray.swift文件中：
這里面有一個(gè)成員屬性，回到_ContiguousArrayBuffer中可以看到如下代碼：
這里面初始化了countAndCapacity。
1.4.2 _ArrayBody
下面我們來(lái)看看_ArrayBody是什么，在ArrayBody.swift文件中我們可以看到如下代碼：
我們可以看到_ArrayBody是一個(gè)結(jié)構(gòu)體，里面有一個(gè)_SwiftArrayBodyStorage類型的屬性。
搜索一下_SwiftArrayBodyStorage可以在GlobalObjects.h文件中找到其定義：
struct _SwiftArrayBodyStorage {
__swift_intptr_t count;
__swift_uintptr_t _capacityAndFlags;
};
可以看到_SwiftArrayBodyStorage是一個(gè)結(jié)構(gòu)體，里面定義了兩個(gè)成員變量。
1.4.3 內(nèi)存布局總結(jié)
經(jīng)過(guò)上面的一番探索我們總結(jié)一下Array的內(nèi)存布局：
struct Array----->struct _ContiguousArrayBuffer----->class __ContiguousArrayStorageBase----->包含一個(gè)屬性類型是struct ArrayBody----->包含一個(gè)屬性struct _SwiftArrayBodyStorage----->包含兩個(gè)屬性count和_capacityAndFlags
這里最主要的就是__ContigousArrayStorageBase，因?yàn)榍懊娑际侵殿愋汀?/p>
1.4.4 通過(guò)lldb驗(yàn)證以上結(jié)論
下面我們通過(guò)lldb打印一下：
1.4.5 _capacityAndFlags
乍一看_capacityAndFlags的值好像是count的兩倍，下面我們通過(guò)源碼來(lái)看一看：
@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))
}
以上是_ArrayBody的初始化代碼，我們可以看到對(duì)_capacityAndFlags賦值的時(shí)候是將capacity的值左移1位 在或（|）上(elementTypeIsBridgedVerbatim ? 1 : 0)。
/// Is the Element type bitwise-compatible with some Objective-C
/// class? The answer is---in principle---statically-knowable, but
/// I don't expect to be able to get this information to the
/// optimizer before 1.0 ships, so we store it in a bit here to
/// avoid the cost of calls into the runtime that compute the
/// answer.
@inlinable
internal var elementTypeIsBridgedVerbatim: Bool {
get {
return (_capacityAndFlags & 0x1) != 0
}
set {
_capacityAndFlags
= newValue ? _capacityAndFlags | 1 : _capacityAndFlags & ~1
}
}
elementTypeIsBridgedVerbatim是一個(gè)計(jì)算屬性，看看是否當(dāng)兼容Objective-C的時(shí)候是1，否則是0，這里我們并沒(méi)有兼容OC所以使用0。
那么調(diào)用的時(shí)候傳值是怎么傳的呢？這個(gè)屬性是__ContiguousArrayStorageBase中的countAndCapacity，初始化是在_ContiguousArrayBuffer中初始化的：
// 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)
}
這里的capacity也是調(diào)用處傳過(guò)來(lái)的，調(diào)用點(diǎn)也在_ContiguousArrayBuffer中：
@inlinable
internal init(count: Int, storage: _ContiguousArrayStorage<Element>) {
_storage = storage
_initStorageHeader(count: count, capacity: count)
}
可以看到這個(gè)capacity的值就是count，所以說(shuō)_capacityAndFlags也是個(gè)按位存儲(chǔ)的變量，通過(guò)計(jì)算得出capacity，并不是這存儲(chǔ)capacity，根據(jù)變量的名稱我們也可以知道該變量并不是只存儲(chǔ)一個(gè)值的。
1.4.6 metadata
在lldb調(diào)試的時(shí)候，我們發(fā)現(xiàn)存儲(chǔ)metadata的地址很大，那么怎么怎么回事呢？我們通過(guò)cat address命令查看一下（需要安裝插件），Xcode默認(rèn)不帶這個(gè)命令：
那么這個(gè)InitialAllocationPool是什么呢？我們?nèi)ピ创a中看看，可以在Metadata.cpp中找到：
下面我們測(cè)試一下，初始化一個(gè)數(shù)組：
可以看到調(diào)用堆棧確實(shí)調(diào)用了。但其實(shí)不同的創(chuàng)建方式，這個(gè)位置的內(nèi)容是不一樣的：
其實(shí)這么大的地址就是靜態(tài)變量（這里也應(yīng)該是Metadata），嘗試了幾次，如果初始化一個(gè)空數(shù)組就是_swiftEmptyArrayStorage，有值的時(shí)候就是InitialAllocationPool，并沒(méi)有過(guò)多測(cè)試，不知道具體準(zhǔn)不準(zhǔn)確。
2. 數(shù)組的拼接
2.1 數(shù)組的擴(kuò)容
一個(gè)數(shù)組初始完成后，我們會(huì)需要往里面添加數(shù)據(jù)，也就是append操作，涉及到append就存在擴(kuò)容的問(wèn)題，那么Swift中的Array是如何擴(kuò)容的呢？
我們直接找到append方法：
我們可以看到，擴(kuò)容時(shí)調(diào)用的_reserveCapacityAssumingUniqueBuffer方法，如果全局搜索會(huì)有好幾個(gè)_reserveCapacityAssumingUniqueBuffer方法，經(jīng)過(guò)測(cè)試實(shí)際是調(diào)用的Array.Swift文件中的。
這里也很簡(jiǎn)單，判斷oldCount + 1 > _buffer.capacity就擴(kuò)容。
接下來(lái)我們找到_createNewBuffer方法，也在Array.Swift文件中。
擴(kuò)容的時(shí)候調(diào)用的是_growArrayCapacity(oldCapacity:minimumCapacity: growForAppend:)方法，在ArrayShared.swift文件中：
@inlinable
internal func _growArrayCapacity(_ capacity: Int) -> Int {
return capacity * 2
}
@_alwaysEmitIntoClient
internal func _growArrayCapacity(
oldCapacity: Int, minimumCapacity: Int, growForAppend: Bool
) -> Int {
if growForAppend {
if oldCapacity < minimumCapacity {
// When appending to an array, grow exponentially.
return Swift.max(minimumCapacity, _growArrayCapacity(oldCapacity))
}
return oldCapacity
}
// If not for append, just use the specified capacity, ignoring oldCapacity.
// This means that we "shrink" the buffer in case minimumCapacity is less
// than oldCapacity.
return minimumCapacity
}
_growArrayCapacity(oldCapacity:minimumCapacity: growForAppend:)方法中：
- 首先會(huì)判斷使其擴(kuò)容的是不是
append方法 - 如果是判斷
oldCapacity是否小于minimumCapacity - 如果不是返回
oldCapacity - 如果是取出
oldCapacity的兩倍和minimumCapacity中的大值進(jìn)行返回
這個(gè)minimumCapacity的值在這條調(diào)用堆棧上是oldCount + 1，growForAppend的值為true可以在_reserveCapacityAssumingUniqueBuffer方法中看到。
所以基本可以認(rèn)為數(shù)組的擴(kuò)容時(shí)之前的兩倍。
擴(kuò)容時(shí)對(duì)于就元素的的處理，如果原始緩沖區(qū)是唯一的，我們可以移動(dòng)元素，而不是復(fù)制。如果不是就需要復(fù)制元素。
回到我們的代碼中，通過(guò)lldb調(diào)試一下：
append后數(shù)組的地址就已經(jīng)改變了。
讀取兩段地址：
_capacityAndFlags的值分別是0xa和0x14。
右移1位分別是5和10。
2.1 Array的拷貝
首先我們看看下面這段代碼：
var numbers = [1, 2, 3, 4, 5]
var tmpArray = numbers
我們看到這里只調(diào)用了copy_addr，下面我們看看copy_addr的作用是什么：
可以看到這里面就是一個(gè)值的拷貝，在這里就是把numbers里面存儲(chǔ)的內(nèi)容（這里是一個(gè)指針）拷貝一份到tmpArray中。
那么這里就存在一個(gè)問(wèn)題了，Array在底層是一個(gè)結(jié)構(gòu)體，在Swift中結(jié)構(gòu)體是一個(gè)值類型，那么也就意味著當(dāng)前我們改變numbers或者tmpArray不會(huì)影響另外一個(gè)里面的值。
var numbers = [1, 2, 3, 4, 5]
var tmpArray = numbers
tmpArray[0] = 2
print(numbers)
print(tmpArray)
我們可以看到確實(shí)沒(méi)有影響到另一個(gè)。但是numbers里面存儲(chǔ)的是地址，當(dāng)初我們?cè)谔剿?a href="http://www.itdecent.cn/p/d02ef86bbf79" target="_blank">值類型和引用類型的時(shí)候，當(dāng)值類型內(nèi)嵌套引用類型的時(shí)候，改變值類型中的引用類型的值，會(huì)影響到拷貝的另一個(gè)值類型，這點(diǎn)就不一樣了，還是上面的代碼，我們通過(guò)lldb調(diào)試看一看：
我們可以看到給tmpArray修改值后，其存儲(chǔ)的值已經(jīng)改變了，那么修改的時(shí)候發(fā)生可什么呢？下面我們?cè)诳纯?code>Sil代碼：
下面我們到源碼中看看：
在Array.swift中我們可以看到subscript方法有get和_modify兩個(gè)方法。在_modify里面會(huì)調(diào)用_makeMutableAndUnique方法，下面我們就看看這個(gè)方法：
這里會(huì)調(diào)用_createNewBuffer方法，這就是我們?cè)跀?shù)組拼接的時(shí)候介紹的這個(gè)方法：
這里會(huì)創(chuàng)建一個(gè)新的buffer賦值給_buffer
3. 總結(jié)
至此我們對(duì) Swift 中數(shù)組的介紹就結(jié)束，下面總結(jié)一下：
- Swift中的數(shù)組本質(zhì)是個(gè)結(jié)構(gòu)體，里面的結(jié)構(gòu)如下圖：
- 因?yàn)槭墙Y(jié)構(gòu)體，所以我們認(rèn)為數(shù)組是值類型
- 數(shù)組空間的擴(kuò)容時(shí)原來(lái)容量的兩倍，目前沒(méi)有發(fā)現(xiàn)有最大容量限制
- 數(shù)組的拷貝是寫(xiě)時(shí)復(fù)制機(jī)制，只有修改的時(shí)候才會(huì)修改
- 首先拷貝的時(shí)候是拷貝數(shù)組的地址
- 當(dāng)需要修改任一指向同一空間的數(shù)組的時(shí)候創(chuàng)建一個(gè)新的
buffer來(lái)存儲(chǔ)里面的元素
