Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
809 lines (738 sloc) 23.9 KB
//===----------------------------------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
/// A wrapper around __RawDictionaryStorage that provides most of the
/// implementation of Dictionary.
@usableFromInline
@_fixed_layout
internal struct _NativeDictionary<Key: Hashable, Value> {
@usableFromInline
internal typealias Element = (key: Key, value: Value)
/// See this comments on __RawDictionaryStorage and its subclasses to
/// understand why we store an untyped storage here.
@usableFromInline
internal var _storage: __RawDictionaryStorage
/// Constructs an instance from the empty singleton.
@inlinable
internal init() {
self._storage = __RawDictionaryStorage.empty
}
/// Constructs a dictionary adopting the given storage.
@inlinable
internal init(_ storage: __owned __RawDictionaryStorage) {
self._storage = storage
}
@inlinable
internal init(capacity: Int) {
if capacity == 0 {
self._storage = __RawDictionaryStorage.empty
} else {
self._storage = _DictionaryStorage<Key, Value>.allocate(capacity: capacity)
}
}
#if _runtime(_ObjC)
@inlinable
internal init(_ cocoa: __owned __CocoaDictionary) {
self.init(cocoa, capacity: cocoa.count)
}
@inlinable
internal init(_ cocoa: __owned __CocoaDictionary, capacity: Int) {
if capacity == 0 {
self._storage = __RawDictionaryStorage.empty
} else {
_internalInvariant(cocoa.count <= capacity)
self._storage =
_DictionaryStorage<Key, Value>.convert(cocoa, capacity: capacity)
for (key, value) in cocoa {
insertNew(
key: _forceBridgeFromObjectiveC(key, Key.self),
value: _forceBridgeFromObjectiveC(value, Value.self))
}
}
}
#endif
}
extension _NativeDictionary { // Primitive fields
@usableFromInline
internal typealias Bucket = _HashTable.Bucket
@inlinable
internal var capacity: Int {
@inline(__always)
get {
return _assumeNonNegative(_storage._capacity)
}
}
@inlinable
internal var hashTable: _HashTable {
@inline(__always) get {
return _storage._hashTable
}
}
@inlinable
internal var age: Int32 {
@inline(__always) get {
return _storage._age
}
}
// This API is unsafe and needs a `_fixLifetime` in the caller.
@inlinable
internal var _keys: UnsafeMutablePointer<Key> {
return _storage._rawKeys.assumingMemoryBound(to: Key.self)
}
@inlinable
internal var _values: UnsafeMutablePointer<Value> {
return _storage._rawValues.assumingMemoryBound(to: Value.self)
}
@inlinable
@inline(__always)
internal func invalidateIndices() {
_storage._age &+= 1
}
}
extension _NativeDictionary { // Low-level unchecked operations
@inlinable
@inline(__always)
internal func uncheckedKey(at bucket: Bucket) -> Key {
defer { _fixLifetime(self) }
_internalInvariant(hashTable.isOccupied(bucket))
return _keys[bucket.offset]
}
@inlinable
@inline(__always)
internal func uncheckedValue(at bucket: Bucket) -> Value {
defer { _fixLifetime(self) }
_internalInvariant(hashTable.isOccupied(bucket))
return _values[bucket.offset]
}
@inlinable // FIXME(inline-always) was usableFromInline
@inline(__always)
internal func uncheckedInitialize(
at bucket: Bucket,
toKey key: __owned Key,
value: __owned Value) {
defer { _fixLifetime(self) }
_internalInvariant(hashTable.isValid(bucket))
(_keys + bucket.offset).initialize(to: key)
(_values + bucket.offset).initialize(to: value)
}
@inlinable // FIXME(inline-always) was usableFromInline
@inline(__always)
internal func uncheckedDestroy(at bucket: Bucket) {
defer { _fixLifetime(self) }
_internalInvariant(hashTable.isValid(bucket))
(_keys + bucket.offset).deinitialize(count: 1)
(_values + bucket.offset).deinitialize(count: 1)
}
}
extension _NativeDictionary { // Low-level lookup operations
@inlinable
@inline(__always)
internal func hashValue(for key: Key) -> Int {
return key._rawHashValue(seed: _storage._seed)
}
@inlinable
@inline(__always)
internal func find(_ key: Key) -> (bucket: Bucket, found: Bool) {
return find(key, hashValue: self.hashValue(for: key))
}
/// Search for a given element, assuming it has the specified hash value.
///
/// If the element is not present in this set, return the position where it
/// could be inserted.
@inlinable
@inline(__always)
internal func find(
_ key: Key,
hashValue: Int
) -> (bucket: Bucket, found: Bool) {
let hashTable = self.hashTable
var bucket = hashTable.idealBucket(forHashValue: hashValue)
while hashTable._isOccupied(bucket) {
if uncheckedKey(at: bucket) == key {
return (bucket, true)
}
bucket = hashTable.bucket(wrappedAfter: bucket)
}
return (bucket, false)
}
}
extension _NativeDictionary { // ensureUnique
@inlinable
internal mutating func resize(capacity: Int) {
let capacity = Swift.max(capacity, self.capacity)
let newStorage = _DictionaryStorage<Key, Value>.resize(
original: _storage,
capacity: capacity,
move: true)
let result = _NativeDictionary(newStorage)
if count > 0 {
for bucket in hashTable {
let key = (_keys + bucket.offset).move()
let value = (_values + bucket.offset).move()
result._unsafeInsertNew(key: key, value: value)
}
// Clear out old storage, ensuring that its deinit won't overrelease the
// elements we've just moved out.
_storage._hashTable.clear()
_storage._count = 0
}
_storage = result._storage
}
@inlinable
@_semantics("optimize.sil.specialize.generic.size.never")
internal mutating func copyAndResize(capacity: Int) {
let capacity = Swift.max(capacity, self.capacity)
let newStorage = _DictionaryStorage<Key, Value>.resize(
original: _storage,
capacity: capacity,
move: false)
let result = _NativeDictionary(newStorage)
if count > 0 {
for bucket in hashTable {
result._unsafeInsertNew(
key: self.uncheckedKey(at: bucket),
value: self.uncheckedValue(at: bucket))
}
}
_storage = result._storage
}
@inlinable
@_semantics("optimize.sil.specialize.generic.size.never")
internal mutating func copy() {
let newStorage = _DictionaryStorage<Key, Value>.copy(original: _storage)
_internalInvariant(newStorage._scale == _storage._scale)
_internalInvariant(newStorage._age == _storage._age)
_internalInvariant(newStorage._seed == _storage._seed)
let result = _NativeDictionary(newStorage)
if count > 0 {
result.hashTable.copyContents(of: hashTable)
result._storage._count = self.count
for bucket in hashTable {
let key = uncheckedKey(at: bucket)
let value = uncheckedValue(at: bucket)
result.uncheckedInitialize(at: bucket, toKey: key, value: value)
}
}
_storage = result._storage
}
/// Ensure storage of self is uniquely held and can hold at least `capacity`
/// elements. Returns true iff contents were rehashed.
@inlinable
@_semantics("optimize.sil.specialize.generic.size.never")
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)
}
}
extension _NativeDictionary {
@inlinable
@inline(__always)
func validatedBucket(for index: _HashTable.Index) -> Bucket {
_precondition(hashTable.isOccupied(index.bucket) && index.age == age,
"Attempting to access Dictionary elements using an invalid index")
return index.bucket
}
@inlinable
@inline(__always)
func validatedBucket(for index: Dictionary<Key, Value>.Index) -> Bucket {
#if _runtime(_ObjC)
guard index._isNative else {
index._cocoaPath()
// Accept Cocoa indices as long as they contain a key that exists in this
// dictionary, and the address of their Cocoa object generates the same
// age.
let cocoa = index._asCocoa
if cocoa.age == self.age {
let key = _forceBridgeFromObjectiveC(cocoa.key, Key.self)
let (bucket, found) = find(key)
if found {
return bucket
}
}
_preconditionFailure(
"Attempting to access Dictionary elements using an invalid index")
}
#endif
return validatedBucket(for: index._asNative)
}
}
extension _NativeDictionary: _DictionaryBuffer {
@usableFromInline
internal typealias Index = Dictionary<Key, Value>.Index
@inlinable
internal var startIndex: Index {
let bucket = hashTable.startBucket
return Index(_native: _HashTable.Index(bucket: bucket, age: age))
}
@inlinable
internal var endIndex: Index {
let bucket = hashTable.endBucket
return Index(_native: _HashTable.Index(bucket: bucket, age: age))
}
@inlinable
internal func index(after index: Index) -> Index {
#if _runtime(_ObjC)
guard _fastPath(index._isNative) else {
let _ = validatedBucket(for: index)
let i = index._asCocoa
return Index(_cocoa: i.dictionary.index(after: i))
}
#endif
let bucket = validatedBucket(for: index._asNative)
let next = hashTable.occupiedBucket(after: bucket)
return Index(_native: _HashTable.Index(bucket: next, age: age))
}
@inlinable
internal func index(forKey key: Key) -> Index? {
if count == 0 {
// Fast path that avoids computing the hash of the key.
return nil
}
let (bucket, found) = find(key)
guard found else { return nil }
return Index(_native: _HashTable.Index(bucket: bucket, age: age))
}
@inlinable
internal var count: Int {
@inline(__always) get {
return _assumeNonNegative(_storage._count)
}
}
@inlinable
@inline(__always)
func contains(_ key: Key) -> Bool {
return find(key).found
}
@inlinable
@inline(__always)
func lookup(_ key: Key) -> Value? {
if count == 0 {
// Fast path that avoids computing the hash of the key.
return nil
}
let (bucket, found) = self.find(key)
guard found else { return nil }
return self.uncheckedValue(at: bucket)
}
@inlinable
@inline(__always)
func lookup(_ index: Index) -> (key: Key, value: Value) {
let bucket = validatedBucket(for: index)
let key = self.uncheckedKey(at: bucket)
let value = self.uncheckedValue(at: bucket)
return (key, value)
}
@inlinable
@inline(__always)
func key(at index: Index) -> Key {
let bucket = validatedBucket(for: index)
return self.uncheckedKey(at: bucket)
}
@inlinable
@inline(__always)
func value(at index: Index) -> Value {
let bucket = validatedBucket(for: index)
return self.uncheckedValue(at: bucket)
}
}
extension _NativeDictionary {
@inlinable
subscript(key: Key, isUnique isUnique: Bool) -> Value? {
@inline(__always)
get {
// Dummy definition; don't use.
return lookup(key)
}
@inline(__always)
_modify {
let (bucket, found) = mutatingFind(key, isUnique: isUnique)
if found {
// Move the old value out of storage, wrapping it into an optional
// before yielding it.
var value: Value? = (_values + bucket.offset).move()
defer {
// This is in a defer block because yield might throw, and we need to
// preserve Dictionary's storage invariants when that happens.
if let value = value {
// **Mutation.** Initialize storage to new value.
(_values + bucket.offset).initialize(to: value)
} else {
// **Removal.** We've already deinitialized the value; deinitialize
// the key too and register the removal.
(_keys + bucket.offset).deinitialize(count: 1)
_delete(at: bucket)
}
}
yield &value
} else {
var value: Value? = nil
defer {
// This is in a defer block because yield might throw, and we need to
// preserve Dictionary invariants when that happens.
if let value = value {
// **Insertion.** Insert the new entry at the correct place. Note
// that `mutatingFind` already ensured that we have enough capacity.
_insert(at: bucket, key: key, value: value)
}
}
yield &value
}
}
}
}
// This function has a highly visible name to make it stand out in stack traces.
@usableFromInline
@inline(never)
internal func KEY_TYPE_OF_DICTIONARY_VIOLATES_HASHABLE_REQUIREMENTS(
_ keyType: Any.Type
) -> Never {
_assertionFailure(
"Fatal error",
"""
Duplicate keys of type '\(keyType)' were found in a Dictionary.
This usually means either that the type violates Hashable's requirements, or
that members of such a dictionary were mutated after insertion.
""",
flags: _fatalErrorFlags())
}
extension _NativeDictionary { // Insertions
/// Insert a new element into uniquely held storage.
/// Storage must be uniquely referenced with adequate capacity.
/// The `key` must not be already present in the Dictionary.
@inlinable
internal func _unsafeInsertNew(key: __owned Key, value: __owned Value) {
_internalInvariant(count + 1 <= capacity)
let hashValue = self.hashValue(for: key)
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(key, hashValue: hashValue)
guard !found else {
KEY_TYPE_OF_DICTIONARY_VIOLATES_HASHABLE_REQUIREMENTS(Key.self)
}
hashTable.insert(bucket)
uncheckedInitialize(at: bucket, toKey: key, value: value)
} else {
let bucket = hashTable.insertNew(hashValue: hashValue)
uncheckedInitialize(at: bucket, toKey: key, value: value)
}
_storage._count &+= 1
}
/// Insert a new entry into uniquely held storage.
/// Storage must be uniquely referenced.
/// The `key` must not be already present in the Dictionary.
@inlinable
internal mutating func insertNew(key: __owned Key, value: __owned Value) {
_ = ensureUnique(isUnique: true, capacity: count + 1)
_unsafeInsertNew(key: key, value: value)
}
/// Same as find(_:), except assume a corresponding key/value pair will be
/// inserted if it doesn't already exist, and mutated if it does exist. When
/// this function returns, the storage is guaranteed to be native, uniquely
/// held, and with enough capacity for a single insertion (if the key isn't
/// already in the dictionary.)
@inlinable
internal mutating func mutatingFind(
_ key: Key,
isUnique: Bool
) -> (bucket: Bucket, found: Bool) {
let (bucket, found) = find(key)
// Prepare storage.
// If `key` isn't in the dictionary yet, assume that this access will end
// up inserting it. (If we guess wrong, we might needlessly expand
// storage; that's fine.) Otherwise this can only be a removal or an
// in-place mutation.
let rehashed = ensureUnique(
isUnique: isUnique,
capacity: count + (found ? 0 : 1))
guard rehashed else { return (bucket, found) }
let (b, f) = find(key)
if f != found {
KEY_TYPE_OF_DICTIONARY_VIOLATES_HASHABLE_REQUIREMENTS(Key.self)
}
return (b, found)
}
@inlinable
internal func _insert(
at bucket: Bucket,
key: __owned Key,
value: __owned Value) {
_internalInvariant(count < capacity)
hashTable.insert(bucket)
uncheckedInitialize(at: bucket, toKey: key, value: value)
_storage._count += 1
}
@inlinable
internal mutating func updateValue(
_ value: __owned Value,
forKey key: Key,
isUnique: Bool
) -> Value? {
let (bucket, found) = mutatingFind(key, isUnique: isUnique)
if found {
let oldValue = (_values + bucket.offset).move()
(_values + bucket.offset).initialize(to: value)
return oldValue
}
_insert(at: bucket, key: key, value: value)
return nil
}
@inlinable
internal mutating func setValue(
_ value: __owned Value,
forKey key: Key,
isUnique: Bool
) {
let (bucket, found) = mutatingFind(key, isUnique: isUnique)
if found {
(_values + bucket.offset).pointee = value
} else {
_insert(at: bucket, key: key, value: value)
}
}
}
extension _NativeDictionary {
@inlinable
@inline(__always)
internal mutating func swapValuesAt(
_ a: Bucket,
_ b: Bucket,
isUnique: Bool
) {
let rehashed = ensureUnique(isUnique: isUnique, capacity: capacity)
_internalInvariant(!rehashed)
_internalInvariant(hashTable.isOccupied(a) && hashTable.isOccupied(b))
let value = (_values + a.offset).move()
(_values + a.offset).moveInitialize(from: _values + b.offset, count: 1)
(_values + b.offset).initialize(to: value)
}
}
extension _NativeDictionary where Value: Equatable {
@inlinable
@inline(__always)
func isEqual(to other: _NativeDictionary) -> Bool {
if self._storage === other._storage { return true }
if self.count != other.count { return false }
for (key, value) in self {
let (bucket, found) = other.find(key)
guard found, other.uncheckedValue(at: bucket) == value else {
return false
}
}
return true
}
#if _runtime(_ObjC)
@inlinable
func isEqual(to other: __CocoaDictionary) -> Bool {
if self.count != other.count { return false }
defer { _fixLifetime(self) }
for bucket in self.hashTable {
let key = self.uncheckedKey(at: bucket)
let value = self.uncheckedValue(at: bucket)
guard
let cocoaValue = other.lookup(_bridgeAnythingToObjectiveC(key)),
value == _forceBridgeFromObjectiveC(cocoaValue, Value.self)
else {
return false
}
}
return true
}
#endif
}
extension _NativeDictionary: _HashTableDelegate {
@inlinable
@inline(__always)
internal func hashValue(at bucket: Bucket) -> Int {
return hashValue(for: uncheckedKey(at: bucket))
}
@inlinable
@inline(__always)
internal func moveEntry(from source: Bucket, to target: Bucket) {
_internalInvariant(hashTable.isValid(source))
_internalInvariant(hashTable.isValid(target))
(_keys + target.offset)
.moveInitialize(from: _keys + source.offset, count: 1)
(_values + target.offset)
.moveInitialize(from: _values + source.offset, count: 1)
}
@inlinable
@inline(__always)
internal func swapEntry(_ left: Bucket, with right: Bucket) {
_internalInvariant(hashTable.isValid(left))
_internalInvariant(hashTable.isValid(right))
swap(&_keys[left.offset], &_keys[right.offset])
swap(&_values[left.offset], &_values[right.offset])
}
}
extension _NativeDictionary { // Deletion
@inlinable
@_effects(releasenone)
@_semantics("optimize.sil.specialize.generic.size.never")
internal func _delete(at bucket: Bucket) {
hashTable.delete(at: bucket, with: self)
_storage._count -= 1
_internalInvariant(_storage._count >= 0)
invalidateIndices()
}
@inlinable
@_semantics("optimize.sil.specialize.generic.size.never")
internal mutating func uncheckedRemove(
at bucket: Bucket,
isUnique: Bool
) -> Element {
_internalInvariant(hashTable.isOccupied(bucket))
let rehashed = ensureUnique(isUnique: isUnique, capacity: capacity)
_internalInvariant(!rehashed)
let oldKey = (_keys + bucket.offset).move()
let oldValue = (_values + bucket.offset).move()
_delete(at: bucket)
return (oldKey, oldValue)
}
@usableFromInline
internal mutating func removeAll(isUnique: Bool) {
guard isUnique else {
let scale = self._storage._scale
_storage = _DictionaryStorage<Key, Value>.allocate(
scale: scale,
age: nil,
seed: nil)
return
}
for bucket in hashTable {
(_keys + bucket.offset).deinitialize(count: 1)
(_values + bucket.offset).deinitialize(count: 1)
}
hashTable.clear()
_storage._count = 0
invalidateIndices()
}
}
extension _NativeDictionary { // High-level operations
@inlinable
internal func mapValues<T>(
_ transform: (Value) throws -> T
) rethrows -> _NativeDictionary<Key, T> {
let resultStorage = _DictionaryStorage<Key, T>.copy(original: _storage)
_internalInvariant(resultStorage._seed == _storage._seed)
let result = _NativeDictionary<Key, T>(resultStorage)
// Because the current and new buffer have the same scale and seed, we can
// initialize to the same locations in the new buffer, skipping hash value
// recalculations.
for bucket in hashTable {
let key = self.uncheckedKey(at: bucket)
let value = self.uncheckedValue(at: bucket)
try result._insert(at: bucket, key: key, value: transform(value))
}
return result
}
@inlinable
internal mutating func merge<S: Sequence>(
_ keysAndValues: __owned S,
isUnique: Bool,
uniquingKeysWith combine: (Value, Value) throws -> Value
) rethrows where S.Element == (Key, Value) {
var isUnique = isUnique
for (key, value) in keysAndValues {
let (bucket, found) = mutatingFind(key, isUnique: isUnique)
isUnique = true
if found {
do {
let newValue = try combine(uncheckedValue(at: bucket), value)
_values[bucket.offset] = newValue
} catch _MergeError.keyCollision {
fatalError("Duplicate values for key: '\(key)'")
}
} else {
_insert(at: bucket, key: key, value: value)
}
}
}
@inlinable
@inline(__always)
internal init<S: Sequence>(
grouping values: __owned S,
by keyForValue: (S.Element) throws -> Key
) rethrows where Value == [S.Element] {
self.init()
for value in values {
let key = try keyForValue(value)
let (bucket, found) = mutatingFind(key, isUnique: true)
if found {
_values[bucket.offset].append(value)
} else {
_insert(at: bucket, key: key, value: [value])
}
}
}
}
extension _NativeDictionary: Sequence {
@usableFromInline
@_fixed_layout
internal struct Iterator {
// The iterator is iterating over a frozen view of the collection state, so
// it keeps its own reference to the dictionary.
@usableFromInline
internal let base: _NativeDictionary
@usableFromInline
internal var iterator: _HashTable.Iterator
@inlinable
@inline(__always)
init(_ base: __owned _NativeDictionary) {
self.base = base
self.iterator = base.hashTable.makeIterator()
}
}
@inlinable
internal __consuming func makeIterator() -> Iterator {
return Iterator(self)
}
}
extension _NativeDictionary.Iterator: IteratorProtocol {
@usableFromInline
internal typealias Element = (key: Key, value: Value)
@inlinable
@inline(__always)
internal mutating func nextKey() -> Key? {
guard let index = iterator.next() else { return nil }
return base.uncheckedKey(at: index)
}
@inlinable
@inline(__always)
internal mutating func nextValue() -> Value? {
guard let index = iterator.next() else { return nil }
return base.uncheckedValue(at: index)
}
@inlinable
@inline(__always)
internal mutating func next() -> Element? {
guard let index = iterator.next() else { return nil }
let key = base.uncheckedKey(at: index)
let value = base.uncheckedValue(at: index)
return (key, value)
}
}