Adding Elements
internal func _unsafeInsertNew(_ element: __owned Element) {
_internalInvariant(count + 1 <= capacity)
let hashValue = self.hashValue(for: element)
if _isDebugAssertConfiguration() {
// In debug builds, perform a full lookup and trap if we detect duplicate
// elements -- these imply that the Element type violates Hashable
// requirements. This is generally more costly than a direct insertion,
// because we'll need to compare elements in case of hash collisions.
let (bucket, found) = find(element, hashValue: hashValue)
guard !found else {
ELEMENT_TYPE_OF_SET_VIOLATES_HASHABLE_REQUIREMENTS(Element.self)
}
hashTable.insert(bucket)
uncheckedInitialize(at: bucket, to: element)
} else {
let bucket = hashTable.insertNew(hashValue: hashValue)
uncheckedInitialize(at: bucket, to: element)
}
_storage._count &+= 1
}
最终走到了_unsafeInsertNew 的 _unsafeInsertNew 方法里。
最后做了三件事:
- 修改标记位,对应位置已经被占用了
- 把插入的元素移动到指定的内存位置
-
count 增加 1
reserveCapacity
@inline(__always)
internal mutating func ensureUnique(isUnique: Bool, capacity: Int) -> Bool {
if _fastPath(capacity <= self.capacity && isUnique) {
return false
}
if isUnique {
resize(capacity: capacity)
return true
}
if capacity <= self.capacity {
copy()
return false
}
copyAndResize(capacity: capacity)
return true
}
internal mutating func reserveCapacity(_ capacity: Int, isUnique: Bool) {
_ = ensureUnique(isUnique: isUnique, capacity: capacity)
}
这里有两个操作,copy 和resize 。
resize 操作会把分配的内存变大,所有元素需要被重新插入一次,叫做rehashed 。
被重新插入一次以后,位置会和原来的不一样。并不是说,resize 之后,新增的内存部分是空的。
remove
最后会走到uncheckedRemove 操作。
@inlinable
@inline(__always)
internal mutating func uncheckedRemove(
at bucket: Bucket,
isUnique: Bool) -> Element {
_internalInvariant(hashTable.isOccupied(bucket))
let rehashed = ensureUnique(isUnique: isUnique, capacity: capacity)
_internalInvariant(!rehashed)
let old = (_elements + bucket.offset).move()
_delete(at: bucket)
return old
}

不知道这里的 age 是什么操作。
|
请发表评论