| //===----------------------------------------------------------------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See http://swift.org/LICENSE.txt for license information |
| // See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| |
| import SwiftShims |
| |
| // General Mutable, Value-Type Collections |
| // ================================================= |
| // |
| // Basic copy-on-write (COW) requires a container's data to be copied |
| // into new storage before it is modified, to avoid changing the data |
| // of other containers that may share the data. There is one |
| // exception: when we know the container has the only reference to the |
| // data, we can elide the copy. This COW optimization is crucial for |
| // the performance of mutating algorithms. |
| // |
| // Some container elements (Characters in a String, key/value pairs in |
| // an open-addressing hash table) are not traversable with a fixed |
| // size offset, so incrementing/decrementing indices requires looking |
| // at the contents of the container. The current interface for |
| // incrementing/decrementing indices of a Collection is the usual ++i, |
| // --i. Therefore, for memory safety, the indices need to keep a |
| // reference to the container's underlying data so that it can be |
| // inspected. But having multiple outstanding references to the |
| // underlying data defeats the COW optimization. |
| // |
| // The way out is to count containers referencing the data separately |
| // from indices that reference the data. When deciding to elide the |
| // copy and modify the data directly---as long as we don't violate |
| // memory safety of any outstanding indices---we only need to be |
| // sure that no other containers are referencing the data. |
| // |
| // Implementation notes |
| // ==================== |
| // |
| // `Dictionary` uses two storage schemes: native storage and Cocoa storage. |
| // |
| // Native storage is a hash table with open addressing and linear probing. The |
| // bucket array forms a logical ring (e.g., a chain can wrap around the end of |
| // buckets array to the beginning of it). |
| // |
| // The logical bucket array is implemented as three arrays: Key, Value, and a |
| // bitmap that marks valid entries. An invalid entry marks the end of a chain. |
| // There is always at least one invalid entry among the buckets. `Dictionary` |
| // does not use tombstones. |
| // |
| // In addition to the native storage `Dictionary` can also wrap an |
| // `NSDictionary` in order to allow bridging `NSDictionary` to `Dictionary` in |
| // `O(1)`. |
| // |
| // Currently native storage uses a data structure like this:: |
| // |
| // Dictionary<K,V> (a struct) |
| // +----------------------------------------------+ |
| // | [ _VariantDictionaryStorage<K,V> (an enum) ] | |
| // +---|------------------------------------------+ |
| // / |
| // | |
| // V _NativeDictionaryStorageOwner<K,V> (a class) |
| // +-----------------------------------------------------------+ |
| // | [refcount#1] [ _NativeDictionaryStorage<K,V> (a struct) ] | |
| // +----------------|------------------------------------------+ |
| // | |
| // +--------------+ |
| // | |
| // V _NativeDictionaryStorageImpl<K,V> (a class) |
| // +-----------------------------------------+ |
| // | [refcount#2] [...element storage...] | |
| // +-----------------------------------------+ |
| // ^ |
| // +---+ |
| // | Dictionary<K,V>.Index (an enum) |
| // +-----|--------------------------------------------+ |
| // | | _NativeDictionaryIndex<K,V> (a struct) | |
| // | +---|------------------------------------------+ | |
| // | | [ _NativeDictionaryStorage<K,V> (a struct) ] | | |
| // | +----------------------------------------------+ | |
| // +--------------------------------------------------+ |
| // |
| // We would like to optimize by allocating the `_NativeDictionaryStorageOwner` |
| // /inside/ the `_NativeDictionaryStorageImpl`, and override the `dealloc` |
| // method of `_NativeDictionaryStorageOwner` to do nothing but release its |
| // reference. |
| // |
| // Dictionary<K,V> (a struct) |
| // +----------------------------------------------+ |
| // | [ _VariantDictionaryStorage<K,V> (an enum) ] | |
| // +---|------------------------------------------+ |
| // / |
| // | +---+ |
| // | V | _NativeDictionaryStorageImpl<K,V> (a class) |
| // +---|--------------|----------------------------------------------+ |
| // | | | | |
| // | | [refcount#2] | | |
| // | | | | |
| // | V | _NativeDictionaryStorageOwner<K,V> (a class) | |
| // | +----------------|------------------------------------------+ | |
| // | | [refcount#1] [ _NativeDictionaryStorage<K,V> (a struct) ] | | |
| // | +-----------------------------------------------------------+ | |
| // | | |
| // | [...element storage...] | |
| // +-----------------------------------------------------------------+ |
| // |
| // |
| // Cocoa storage uses a data structure like this:: |
| // |
| // Dictionary<K,V> (a struct) |
| // +----------------------------------------------+ |
| // | _VariantDictionaryStorage<K,V> (an enum) | |
| // | +----------------------------------------+ | |
| // | | [ _CocoaDictionaryStorage (a struct) ] | | |
| // | +---|------------------------------------+ | |
| // +-----|----------------------------------------+ |
| // | |
| // +---+ |
| // | |
| // V NSDictionary (a class) |
| // +--------------+ |
| // | [refcount#1] | |
| // +--------------+ |
| // ^ |
| // +-+ |
| // | Dictionary<K,V>.Index (an enum) |
| // +---|-----------------------------------+ |
| // | | _CocoaDictionaryIndex (a struct) | |
| // | +-|-----------------------------+ | |
| // | | * [ all keys ] [ next index ] | | |
| // | +-------------------------------+ | |
| // +---------------------------------------+ |
| // |
| // `_NativeDictionaryStorageOwner` is an `NSDictionary` subclass. It can |
| // be returned to Objective-C during bridging if both `Key` and `Value` |
| // bridge verbatim. |
| // |
| // Index Invalidation |
| // ------------------ |
| // |
| // Indexing a container, `c[i]`, uses the integral offset stored in the index |
| // to access the elements referenced by the container. The buffer referenced |
| // by the index is only used to increment and decrement the index. Most of the |
| // time, these two buffers will be identical, but they need not always be. For |
| // example, if one ensures that a `Dictionary` has sufficient capacity to avoid |
| // reallocation on the next element insertion, the following works :: |
| // |
| // var (i, found) = d.find(k) // i is associated with d's buffer |
| // if found { |
| // var e = d // now d is sharing its data with e |
| // e[newKey] = newValue // e now has a unique copy of the data |
| // return e[i] // use i to access e |
| // } |
| // |
| // The result should be a set of iterator invalidation rules familiar to anyone |
| // familiar with the C++ standard library. Note that because all accesses to a |
| // dictionary buffer are bounds-checked, this scheme never compromises memory |
| // safety. |
| // |
| // Bridging |
| // ======== |
| // |
| // Bridging `NSDictionary` to `Dictionary` |
| // --------------------------------------- |
| // |
| // `NSDictionary` bridges to `Dictionary<NSObject, AnyObject>` in `O(1)`, |
| // without memory allocation. |
| // |
| // Bridging `Dictionary` to `NSDictionary` |
| // --------------------------------------- |
| // |
| // `Dictionary<K, V>` bridges to `NSDictionary` iff both `K` and `V` are |
| // bridged. Otherwise, a runtime error is raised. |
| // |
| // * if both `K` and `V` are bridged verbatim, then `Dictionary<K, V>` bridges |
| // to `NSDictionary` in `O(1)`, without memory allocation. Access to |
| // elements does not cause memory allocation. |
| // |
| // * otherwise, `K` and/or `V` are unconditionally or conditionally bridged. |
| // In this case, `Dictionary<K, V>` is bridged to `NSDictionary` in `O(1)`, |
| // without memory allocation. Complete bridging is performed when the first |
| // access to elements happens. The bridged `NSDictionary` has a cache of |
| // pointers it returned, so that: |
| // - Every time keys or values are accessed on the bridged `NSDictionary`, |
| // new objects are not created. |
| // - Accessing the same element (key or value) multiple times will return |
| // the same pointer. |
| // |
| // Bridging `NSSet` to `Set` and vice versa |
| // ---------------------------------------- |
| // |
| // Bridging guarantees for `Set<Element>` are the same as for |
| // `Dictionary<Element, ()>`. |
| // |
| |
| /// This protocol is only used for compile-time checks that |
| /// every storage type implements all required operations. |
| internal protocol _HashStorage { |
| associatedtype Key |
| associatedtype Value |
| associatedtype Index |
| associatedtype SequenceElement |
| associatedtype SequenceElementWithoutLabels |
| var startIndex: Index { get } |
| var endIndex: Index { get } |
| |
| func index(after i: Index) -> Index |
| |
| func formIndex(after i: inout Index) |
| |
| func index(forKey key: Key) -> Index? |
| |
| func assertingGet(_ i: Index) -> SequenceElement |
| |
| func assertingGet(_ key: Key) -> Value |
| |
| func maybeGet(_ key: Key) -> Value? |
| |
| @discardableResult |
| mutating func updateValue(_ value: Value, forKey key: Key) -> Value? |
| |
| @discardableResult |
| mutating func insert( |
| _ value: Value, forKey key: Key |
| ) -> (inserted: Bool, memberAfterInsert: Value) |
| |
| @discardableResult |
| mutating func remove(at index: Index) -> SequenceElement |
| |
| @discardableResult |
| mutating func removeValue(forKey key: Key) -> Value? |
| |
| @discardableResult |
| mutating func removeAll(keepingCapacity keepCapacity: Bool) |
| |
| var count: Int { get } |
| |
| static func fromArray(_ elements: [SequenceElementWithoutLabels]) -> Self |
| } |
| |
| /// The inverse of the default hash table load factor. Factored out so that it |
| /// can be used in multiple places in the implementation and stay consistent. |
| /// Should not be used outside `Dictionary` implementation. |
| @_transparent |
| internal var _hashContainerDefaultMaxLoadFactorInverse: Double { |
| return 1.0 / 0.75 |
| } |
| |
| #if _runtime(_ObjC) |
| /// Call `[lhs isEqual: rhs]`. |
| /// |
| /// This function is part of the runtime because `Bool` type is bridged to |
| /// `ObjCBool`, which is in Foundation overlay. |
| @_silgen_name("swift_stdlib_NSObject_isEqual") |
| internal func _stdlib_NSObject_isEqual(_ lhs: AnyObject, _ rhs: AnyObject) -> Bool |
| #endif |
| |
| //===--- Hacks and workarounds --------------------------------------------===// |
| |
| /// Like `UnsafeMutablePointer<Unmanaged<AnyObject>>`, or `id |
| /// __unsafe_unretained *` in Objective-C ARC. |
| internal struct _UnmanagedAnyObjectArray { |
| /// Underlying pointer. |
| internal var value: UnsafeMutableRawPointer |
| |
| internal init(_ up: UnsafeMutablePointer<AnyObject>) { |
| self.value = UnsafeMutableRawPointer(up) |
| } |
| |
| internal init?(_ up: UnsafeMutablePointer<AnyObject>?) { |
| guard let unwrapped = up else { return nil } |
| self.init(unwrapped) |
| } |
| |
| internal subscript(i: Int) -> AnyObject { |
| get { |
| let unmanaged = value.load( |
| fromByteOffset: i * MemoryLayout<AnyObject>.stride, |
| as: Unmanaged<AnyObject>.self) |
| return unmanaged.takeUnretainedValue() |
| } |
| nonmutating set(newValue) { |
| let unmanaged = Unmanaged.passUnretained(newValue) |
| value.storeBytes(of: unmanaged, |
| toByteOffset: i * MemoryLayout<AnyObject>.stride, |
| as: Unmanaged<AnyObject>.self) |
| } |
| } |
| } |
| |
| //===--- APIs unique to Set<Element> --------------------------------------===// |
| |
| /// An unordered collection of unique elements. |
| /// |
| /// You use a set instead of an array when you need to test efficiently for |
| /// membership and you aren't concerned with the order of the elements in the |
| /// collection, or when you need to ensure that each element appears only once |
| /// in a collection. |
| /// |
| /// You can create a set with any element type that conforms to the `Hashable` |
| /// protocol. By default, most types in the standard library are hashable, |
| /// including strings, numeric and Boolean types, enumeration cases without |
| /// associated values, and even sets themselves. |
| /// |
| /// Swift makes it as easy to create a new set as to create a new array. Simply |
| /// assign an array literal to a variable or constant with the `Set` type |
| /// specified. |
| /// |
| /// let ingredients: Set = ["cocoa beans", "sugar", "cocoa butter", "salt"] |
| /// if ingredients.contains("sugar") { |
| /// print("No thanks, too sweet.") |
| /// } |
| /// // Prints "No thanks, too sweet." |
| /// |
| /// Set Operations |
| /// ============== |
| /// |
| /// Sets provide a suite of mathematical set operations. For example, you can |
| /// efficiently test a set for membership of an element or check its |
| /// intersection with another set: |
| /// |
| /// - Use the `contains(_:)` method to test whether a set contains a specific |
| /// element. |
| /// - Use the "equal to" operator (`==`) to test whether two sets contain the |
| /// same elements. |
| /// - Use the `isSubset(of:)` method to test whether a set contains all the |
| /// elements of another set or sequence. |
| /// - Use the `isSuperset(of:)` method to test whether all elements of a set |
| /// are contained in another set or sequence. |
| /// - Use the `isStrictSubset(of:)` and `isStrictSuperset(of:)` methods to test |
| /// whether a set is a subset or superset of, but not equal to, another set. |
| /// - Use the `isDisjoint(with:)` method to test whether a set has any elements |
| /// in common with another set. |
| /// |
| /// You can also combine, exclude, or subtract the elements of two sets: |
| /// |
| /// - Use the `union(_:)` method to create a new set with the elements of a set |
| /// and another set or sequence. |
| /// - Use the `intersection(_:)` method to create a new set with only the |
| /// elements common to a set and another set or sequence. |
| /// - Use the `symmetricDifference(_:)` method to create a new set with the |
| /// elements that are in either a set or another set or sequence, but not in |
| /// both. |
| /// - Use the `subtracting(_:)` method to create a new set with the elements of |
| /// a set that are not also in another set or sequence. |
| /// |
| /// You can modify a set in place by using these methods' mutating |
| /// counterparts: `formUnion(_:)`, `formIntersection(_:)`, |
| /// `formSymmetricDifference(_:)`, and `subtract(_:)`. |
| /// |
| /// Set operations are not limited to use with other sets. Instead, you can |
| /// perform set operations with another set, an array, or any other sequence |
| /// type. |
| /// |
| /// var primes: Set = [2, 3, 5, 7] |
| /// |
| /// // Tests whether primes is a subset of a Range<Int> |
| /// print(primes.isSubset(of: 0..<10)) |
| /// // Prints "true" |
| /// |
| /// // Performs an intersection with an Array<Int> |
| /// let favoriteNumbers = [5, 7, 15, 21] |
| /// print(primes.intersection(favoriteNumbers)) |
| /// // Prints "[5, 7]" |
| /// |
| /// Sequence and Collection Operations |
| /// ================================== |
| /// |
| /// In addition to the `Set` type's set operations, you can use any nonmutating |
| /// sequence or collection methods with a set. |
| /// |
| /// if primes.isEmpty { |
| /// print("No primes!") |
| /// } else { |
| /// print("We have \(primes.count) primes.") |
| /// } |
| /// // Prints "We have 4 primes." |
| /// |
| /// let primesSum = primes.reduce(0, +) |
| /// // 'primesSum' == 17 |
| /// |
| /// let primeStrings = primes.sorted().map(String.init) |
| /// // 'primeStrings' == ["2", "3", "5", "7"] |
| /// |
| /// You can iterate through a set's unordered elements with a `for`-`in` loop. |
| /// |
| /// for number in primes { |
| /// print(number) |
| /// } |
| /// // Prints "5" |
| /// // Prints "7" |
| /// // Prints "2" |
| /// // Prints "3" |
| /// |
| /// Many sequence and collection operations return an array or a type-erasing |
| /// collection wrapper instead of a set. To restore efficient set operations, |
| /// create a new set from the result. |
| /// |
| /// let morePrimes = primes.union([11, 13, 17, 19]) |
| /// |
| /// let laterPrimes = morePrimes.filter { $0 > 10 } |
| /// // 'laterPrimes' is of type Array<Int> |
| /// |
| /// let laterPrimesSet = Set(morePrimes.filter { $0 > 10 }) |
| /// // 'laterPrimesSet' is of type Set<Int> |
| /// |
| /// Bridging Between Set and NSSet |
| /// ============================== |
| /// |
| /// You can bridge between `Set` and `NSSet` using the `as` operator. For |
| /// bridging to be possible, the `Element` type of a set must be a class, an |
| /// `@objc` protocol (a protocol imported from Objective-C or marked with the |
| /// `@objc` attribute), or a type that bridges to a Foundation type. |
| /// |
| /// Bridging from `Set` to `NSSet` always takes O(1) time and space. When the |
| /// set's `Element` type is neither a class nor an `@objc` protocol, any |
| /// required bridging of elements occurs at the first access of each element, |
| /// so the first operation that uses the contents of the set (for example, a |
| /// membership test) can take O(N). |
| /// |
| /// Bridging from `NSSet` to `Set` first calls the `copy(with:)` method |
| /// (`- copyWithZone:` in Objective-C) on the set to get an immutable copy and |
| /// then performs additional Swift bookkeeping work that takes O(1) time. For |
| /// instances of `NSSet` that are already immutable, `copy(with:)` returns the |
| /// same set in constant time; otherwise, the copying performance is |
| /// unspecified. The instances of `NSSet` and `Set` share storage using the |
| /// same copy-on-write optimization that is used when two instances of `Set` |
| /// share storage. |
| /// |
| /// - SeeAlso: `Hashable` |
| @_fixed_layout |
| public struct Set<Element : Hashable> : |
| SetAlgebra, Hashable, Collection, ExpressibleByArrayLiteral { |
| |
| internal typealias _Self = Set<Element> |
| internal typealias _VariantStorage = _VariantSetStorage<Element> |
| internal typealias _NativeStorage = _NativeSetStorage<Element> |
| |
| /// The index type for subscripting the set. |
| public typealias Index = SetIndex<Element> |
| |
| internal var _variantStorage: _VariantStorage |
| |
| /// Creates a new, empty set with at least the specified number of elements' |
| /// worth of storage. |
| /// |
| /// Use this initializer to avoid repeated reallocations of a set's storage |
| /// if you know you'll be adding elements to the set after creation. The |
| /// actual capacity of the created set will be the smallest power of 2 that |
| /// is greater than or equal to `minimumCapacity`. |
| /// |
| /// - Parameter minimumCapacity: The minimum number of elements that the |
| /// newly created set should be able to store without reallocating its |
| /// storage. |
| public init(minimumCapacity: Int) { |
| _variantStorage = |
| _VariantStorage.native( |
| _NativeStorage.Owner(minimumCapacity: minimumCapacity)) |
| } |
| |
| /// Private initializer. |
| internal init(_nativeStorage: _NativeSetStorage<Element>) { |
| _variantStorage = _VariantStorage.native( |
| _NativeStorage.Owner(nativeStorage: _nativeStorage)) |
| } |
| |
| /// Private initializer. |
| internal init(_nativeStorageOwner: _NativeSetStorageOwner<Element>) { |
| _variantStorage = .native(_nativeStorageOwner) |
| } |
| |
| // |
| // All APIs below should dispatch to `_variantStorage`, without doing any |
| // additional processing. |
| // |
| |
| #if _runtime(_ObjC) |
| /// Private initializer used for bridging. |
| /// |
| /// Only use this initializer when both conditions are true: |
| /// |
| /// * it is statically known that the given `NSSet` is immutable; |
| /// * `Element` is bridged verbatim to Objective-C (i.e., |
| /// is a reference type). |
| public init(_immutableCocoaSet: _NSSet) { |
| _sanityCheck(_isBridgedVerbatimToObjectiveC(Element.self), |
| "Set can be backed by NSSet _variantStorage only when the member type can be bridged verbatim to Objective-C") |
| _variantStorage = _VariantSetStorage.cocoa( |
| _CocoaSetStorage(cocoaSet: _immutableCocoaSet)) |
| } |
| #endif |
| |
| /// The starting position for iterating members of the set. |
| /// |
| /// If the set is empty, `startIndex` is equal to `endIndex`. |
| public var startIndex: Index { |
| return _variantStorage.startIndex |
| } |
| |
| /// The "past the end" position for the set---that is, the position one |
| /// greater than the last valid subscript argument. |
| /// |
| /// If the set is empty, `endIndex` is equal to `startIndex`. |
| public var endIndex: Index { |
| return _variantStorage.endIndex |
| } |
| |
| // TODO: swift-3-indexing-model - add docs |
| public func index(after i: Index) -> Index { |
| return i.successor() |
| } |
| |
| // APINAMING: complexity docs are broadly missing in this file. |
| |
| /// Returns a Boolean value that indicates whether the given element exists |
| /// in the set. |
| /// |
| /// For example: |
| /// |
| /// let primes: Set = [2, 3, 5, 7] |
| /// let x = 5 |
| /// if primes.contains(x) { |
| /// print("\(x) is prime!") |
| /// } else { |
| /// print("\(x). Not prime.") |
| /// } |
| /// // Prints "5 is prime!" |
| /// |
| /// - Parameter member: An element to look for in the set. |
| /// - Returns: `true` if `member` exists in the set; otherwise, `false`. |
| public func contains(_ member: Element) -> Bool { |
| return _variantStorage.maybeGet(member) != nil |
| } |
| |
| /// Returns the index of the given element in the set, or `nil` if the |
| /// element is not a member of the set. |
| /// |
| /// - Parameter member: An element to search for in the set. |
| /// - Returns: The index of `member` if it exists in the set; otherwise, |
| /// `nil`. |
| public func index(of member: Element) -> Index? { |
| return _variantStorage.index(forKey: member) |
| } |
| |
| /// Inserts the given element in the set if it is not already present. |
| /// |
| /// If an element equal to `newMember` is already contained in the set, this |
| /// method has no effect. In the following example, a new element is |
| /// inserted into `classDays`, a set of days of the week. When an existing |
| /// element is inserted, the `classDays` set does not change. |
| /// |
| /// enum DayOfTheWeek: Int { |
| /// case sunday, monday, tuesday, wednesday, thursday, |
| /// friday, saturday |
| /// } |
| /// |
| /// var classDays: Set<DayOfTheWeek> = [.wednesday, .friday] |
| /// print(classDays.insert(.monday)) |
| /// // Prints "(true, .monday)" |
| /// print(classDays) |
| /// // Prints "[.friday, .wednesday, .monday]" |
| /// |
| /// print(classDays.insert(.friday)) |
| /// // Prints "(false, .friday)" |
| /// print(classDays) |
| /// // Prints "[.friday, .wednesday, .monday]" |
| /// |
| /// - Parameter newMember: An element to insert into the set. |
| /// - Returns: `(true, newMember)` if `newMember` was not contained in the |
| /// set. If an element equal to `newMember` was already contained in the |
| /// set, the method returns `(false, oldMember)`, where `oldMember` is the |
| /// element that was equal to `newMember`. In some cases, `oldMember` may |
| /// be distinguishable from `newMember` by identity comparison or some |
| /// other means. |
| @discardableResult |
| public mutating func insert( |
| _ newMember: Element |
| ) -> (inserted: Bool, memberAfterInsert: Element) { |
| return _variantStorage.insert(newMember, forKey: newMember) |
| } |
| |
| /// Inserts the given element into the set unconditionally. |
| /// |
| /// If an element equal to `newMember` is already contained in the set, |
| /// `newMember` replaces the existing element. In this example, an existing |
| /// element is inserted into `classDays`, a set of days of the week. |
| /// |
| /// enum DayOfTheWeek: Int { |
| /// case sunday, monday, tuesday, wednesday, thursday, |
| /// friday, saturday |
| /// } |
| /// |
| /// var classDays: Set<DayOfTheWeek> = [.monday, .wednesday, .friday] |
| /// print(classDays.update(with: .monday)) |
| /// // Prints "Optional(.monday)" |
| /// |
| /// - Parameter newMember: An element to insert into the set. |
| /// - Returns: An element equal to `newMember` if the set already contained |
| /// such a member; otherwise, `nil`. In some cases, the returned element |
| /// may be distinguishable from `newMember` by identity comparison or some |
| /// other means. |
| @discardableResult |
| public mutating func update(with newMember: Element) -> Element? { |
| return _variantStorage.updateValue(newMember, forKey: newMember) |
| } |
| |
| /// Removes the specified element from the set. |
| /// |
| /// For example: |
| /// |
| /// var ingredients: Set = ["cocoa beans", "sugar", "cocoa butter", "salt"] |
| /// let toRemove = "sugar" |
| /// if let removed = ingredients.remove(toRemove) { |
| /// print("The recipe is now \(removed)-free.") |
| /// } |
| /// // Prints "The recipe is now sugar-free." |
| /// |
| /// - Parameter member: The element to remove from the set. |
| /// - Returns: The value of the `member` parameter if it was a member of the |
| /// set; otherwise, `nil`. |
| @discardableResult |
| public mutating func remove(_ member: Element) -> Element? { |
| return _variantStorage.removeValue(forKey: member) |
| } |
| |
| /// Removes the element at the given index of the set. |
| /// |
| /// - Parameter position: The index of the member to remove. `position` must |
| /// be a valid index of the set, and must not be equal to the set's end |
| /// index. |
| /// - Returns: The element that was removed from the set. |
| @discardableResult |
| public mutating func remove(at position: Index) -> Element { |
| return _variantStorage.remove(at: position) |
| } |
| |
| /// Removes all members from the set. |
| /// |
| /// - Parameter keepingCapacity: If `true`, the set's storage capacity is |
| /// preserved; if `false`, the underlying storage is released. The |
| /// default is `false`. |
| public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) { |
| _variantStorage.removeAll(keepingCapacity: keepCapacity) |
| } |
| |
| /// Removes the first element of the set. |
| /// |
| /// Because a set is not an ordered collection, the "first" element may not |
| /// be the first element that was added to the set. The set must not be |
| /// empty. |
| /// |
| /// - Returns: A member of the set. |
| @discardableResult |
| public mutating func removeFirst() -> Element { |
| _precondition(!isEmpty, "can't removeFirst from an empty Set") |
| return remove(at: startIndex) |
| } |
| |
| /// The number of elements in the set. |
| public var count: Int { |
| return _variantStorage.count |
| } |
| |
| // |
| // `Sequence` conformance |
| // |
| |
| /// Accesses the member at the given position. |
| public subscript(position: Index) -> Element { |
| return _variantStorage.assertingGet(position) |
| } |
| |
| /// Returns an iterator over the members of the set. |
| @inline(__always) |
| public func makeIterator() -> SetIterator<Element> { |
| return _variantStorage.makeIterator() |
| } |
| |
| // |
| // `ExpressibleByArrayLiteral` conformance |
| // |
| /// Creates a set containing the elements of the given array literal. |
| /// |
| /// Do not call this initializer directly. It is used by the compiler when |
| /// you use an array literal. Instead, create a new set using an array |
| /// literal as its value by enclosing a comma-separated list of values in |
| /// square brackets. You can use an array literal anywhere a set is expected |
| /// by the type context. |
| /// |
| /// Here, a set of strings is created from an array literal holding only |
| /// strings. |
| /// |
| /// let ingredients: Set = ["cocoa beans", "sugar", "cocoa butter", "salt"] |
| /// if ingredients.isSuperset(of: ["sugar", "salt"]) { |
| /// print("Whatever it is, it's bound to be delicious!") |
| /// } |
| /// // Prints "Whatever it is, it's bound to be delicious!" |
| /// |
| /// - Parameter elements: A variadic list of elements of the new set. |
| public init(arrayLiteral elements: Element...) { |
| self.init(_nativeStorage: _NativeSetStorage.fromArray(elements)) |
| } |
| |
| // |
| // APIs below this comment should be implemented strictly in terms of |
| // *public* APIs above. `_variantStorage` should not be accessed directly. |
| // |
| // This separates concerns for testing. Tests for the following APIs need |
| // not to concern themselves with testing correctness of behavior of |
| // underlying storage (and different variants of it), only correctness of the |
| // API itself. |
| // |
| |
| /// Creates an empty set. |
| /// |
| /// This is equivalent to initializing with an empty array literal. For |
| /// example: |
| /// |
| /// var emptySet = Set<Int>() |
| /// print(emptySet.isEmpty) |
| /// // Prints "true" |
| /// |
| /// emptySet = [] |
| /// print(emptySet.isEmpty) |
| /// // Prints "true" |
| public init() { |
| self = Set<Element>(minimumCapacity: 0) |
| } |
| |
| /// Creates a new set from a finite sequence of items. |
| /// |
| /// Use this initializer to create a new set from an existing sequence, for |
| /// example, an array or a range. |
| /// |
| /// let validIndices = Set(0..<7).subtracting([2, 4, 5]) |
| /// print(validIndices) |
| /// // Prints "[6, 0, 1, 3]" |
| /// |
| /// This initializer can also be used to restore set methods after performing |
| /// sequence operations such as `filter(_:)` or `map(_:)` on a set. For |
| /// example, after filtering a set of prime numbers to remove any below 10, |
| /// you can create a new set by using this initializer. |
| /// |
| /// let primes: Set = [2, 3, 5, 7, 11, 13, 17, 19, 23] |
| /// let laterPrimes = Set(primes.lazy.filter { $0 > 10 }) |
| /// print(laterPrimes) |
| /// // Prints "[17, 19, 23, 11, 13]" |
| /// |
| /// - Parameter sequence: The elements to use as members of the new set. |
| public init<Source : Sequence>(_ sequence: Source) |
| where Source.Iterator.Element == Element { |
| self.init() |
| if let s = sequence as? Set<Element> { |
| // If this sequence is actually a native `Set`, then we can quickly |
| // adopt its native storage and let COW handle uniquing only |
| // if necessary. |
| switch s._variantStorage { |
| case .native(let owner): |
| _variantStorage = .native(owner) |
| case .cocoa(let owner): |
| _variantStorage = .cocoa(owner) |
| } |
| } else { |
| for item in sequence { |
| insert(item) |
| } |
| } |
| } |
| |
| /// Returns a Boolean value that indicates whether the set is a subset of the |
| /// given sequence. |
| /// |
| /// Set *A* is a subset of another set *B* if every member of *A* is also a |
| /// member of *B*. |
| /// |
| /// let employees = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let attendees: Set = ["Alicia", "Bethany", "Diana"] |
| /// print(attendees.isSubset(of: employees)) |
| /// // Prints "true" |
| /// |
| /// - Parameter possibleSuperset: A sequence of elements. `possibleSuperset` |
| /// must be finite. |
| /// - Returns: `true` if the set is a subset of `possibleSuperset`; |
| /// otherwise, `false`. |
| public func isSubset<S : Sequence>(of possibleSuperset: S) -> Bool |
| where S.Iterator.Element == Element { |
| // FIXME(performance): isEmpty fast path, here and elsewhere. |
| let other = Set(possibleSuperset) |
| return isSubset(of: other) |
| } |
| |
| /// Returns a Boolean value that indicates whether the set is a strict subset |
| /// of the given sequence. |
| /// |
| /// Set *A* is a strict subset of another set *B* if every member of *A* is |
| /// also a member of *B* and *B* contains at least one element that is not a |
| /// member of *A*. |
| /// |
| /// let employees = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let attendees: Set = ["Alicia", "Bethany", "Diana"] |
| /// print(attendees.isStrictSubset(of: employees)) |
| /// // Prints "true" |
| /// |
| /// // A set is never a strict subset of itself: |
| /// print(attendees.isStrictSubset(of: attendees)) |
| /// // Prints "false" |
| /// |
| /// - Parameter possibleStrictSuperset: A sequence of elements. |
| /// `possibleStrictSuperset` must be finite. |
| /// - Returns: `true` is the set is strict subset of |
| /// `possibleStrictSuperset`; otherwise, `false`. |
| public func isStrictSubset<S : Sequence>(of possibleStrictSuperset: S) -> Bool |
| where S.Iterator.Element == Element { |
| // FIXME: code duplication. |
| let other = Set(possibleStrictSuperset) |
| return isStrictSubset(of: other) |
| } |
| |
| /// Returns a Boolean value that indicates whether the set is a superset of |
| /// the given sequence. |
| /// |
| /// Set *A* is a superset of another set *B* if every member of *B* is also a |
| /// member of *A*. |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let attendees = ["Alicia", "Bethany", "Diana"] |
| /// print(employees.isSuperset(of: attendees)) |
| /// // Prints "true" |
| /// |
| /// - Parameter possibleSubset: A sequence of elements. `possibleSubset` must |
| /// be finite. |
| /// - Returns: `true` if the set is a superset of `possibleSubset`; |
| /// otherwise, `false`. |
| public func isSuperset<S : Sequence>(of possibleSubset: S) -> Bool |
| where S.Iterator.Element == Element { |
| // FIXME(performance): Don't build a set; just ask if every element is in |
| // `self`. |
| let other = Set(possibleSubset) |
| return other.isSubset(of: self) |
| } |
| |
| /// Returns a Boolean value that indicates whether the set is a strict |
| /// superset of the given sequence. |
| /// |
| /// Set *A* is a strict superset of another set *B* if every member of *B* is |
| /// also a member of *A* and *A* contains at least one element that is *not* |
| /// a member of *B*. |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let attendees = ["Alicia", "Bethany", "Diana"] |
| /// print(employees.isStrictSuperset(of: attendees)) |
| /// // Prints "true" |
| /// print(employees.isStrictSuperset(of: employees)) |
| /// // Prints "false" |
| /// |
| /// - Parameter possibleStrictSubset: A sequence of elements. |
| /// `possibleStrictSubset` must be finite. |
| /// - Returns: `true` if the set is a strict superset of |
| /// `possibleStrictSubset`; otherwise, `false`. |
| public func isStrictSuperset<S : Sequence>(of possibleStrictSubset: S) -> Bool |
| where S.Iterator.Element == Element { |
| let other = Set(possibleStrictSubset) |
| return other.isStrictSubset(of: self) |
| } |
| |
| /// Returns a Boolean value that indicates whether the set has no members in |
| /// common with the given sequence. |
| /// |
| /// For example: |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let visitors = ["Marcia", "Nathaniel", "Olivia"] |
| /// print(employees.isDisjoint(with: visitors)) |
| /// // Prints "true" |
| /// |
| /// - Parameter other: A sequence of elements. `other` must be finite. |
| /// - Returns: `true` if the set has no elements in common with `other`; |
| /// otherwise, `false`. |
| public func isDisjoint<S : Sequence>(with other: S) -> Bool |
| where S.Iterator.Element == Element { |
| // FIXME(performance): Don't need to build a set. |
| let otherSet = Set(other) |
| return isDisjoint(with: otherSet) |
| } |
| |
| /// Returns a new set with the elements of both this set and the given |
| /// sequence. |
| /// |
| /// For example: |
| /// |
| /// let attendees: Set = ["Alicia", "Bethany", "Diana"] |
| /// let visitors = ["Marcia", "Nathaniel"] |
| /// let attendeesAndVisitors = attendees.union(visitors) |
| /// print(attendeesAndVisitors) |
| /// // Prints "["Diana", "Nathaniel", "Bethany", "Alicia", "Marcia"]" |
| /// |
| /// If the set already contains one or more elements that are also in |
| /// `other`, the existing members are kept. If `other` contains multiple |
| /// instances of equivalent elements, only the first instance is kept. For |
| /// example: |
| /// |
| /// let initialIndices = Set(0..<5) |
| /// let expandedIndices = initialIndices.union([2, 3, 6, 6, 7, 7]) |
| /// print(expandedIndices) |
| /// // Prints "[2, 4, 6, 7, 0, 1, 3]" |
| /// |
| /// - Parameter other: A sequence of elements. `other` must be finite. |
| /// - Returns: A new set with the unique elements of this set and `other`. |
| public func union<S : Sequence>(_ other: S) -> Set<Element> |
| where S.Iterator.Element == Element { |
| var newSet = self |
| newSet.formUnion(other) |
| return newSet |
| } |
| |
| /// Inserts the elements of the given sequence into the set. |
| /// |
| /// If the set already contains one or more elements that are also in |
| /// `other`, the existing members are kept. If `other` contains multiple |
| /// instances of equivalent elements, only the first instance is kept. |
| /// |
| /// var attendees: Set = ["Alicia", "Bethany", "Diana"] |
| /// let visitors = ["Diana", ""Marcia", "Nathaniel"] |
| /// attendees.formUnion(visitors) |
| /// print(attendees) |
| /// // Prints "["Diana", "Nathaniel", "Bethany", "Alicia", "Marcia"]" |
| /// |
| /// - Parameter other: A sequence of elements. `other` must be finite. |
| public mutating func formUnion<S : Sequence>(_ other: S) |
| where S.Iterator.Element == Element { |
| for item in other { |
| insert(item) |
| } |
| } |
| |
| /// Returns a new set containing the elements of this set that do not occur |
| /// in the given sequence. |
| /// |
| /// For example: |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let neighbors = ["Bethany", "Eric", "Forlani", "Greta"] |
| /// let nonNeighbors = employees.subtracting(neighbors) |
| /// print(nonNeighbors) |
| /// // Prints "["Chris", "Diana", "Alicia"]" |
| /// |
| /// - Parameter other: A sequence of elements. `other` must be finite. |
| /// - Returns: A new set. |
| public func subtracting<S : Sequence>(_ other: S) -> Set<Element> |
| where S.Iterator.Element == Element { |
| return self._subtracting(other) |
| } |
| |
| internal func _subtracting<S : Sequence>(_ other: S) -> Set<Element> |
| where S.Iterator.Element == Element { |
| var newSet = self |
| newSet.subtract(other) |
| return newSet |
| } |
| |
| /// Removes the elements of the given sequence from the set. |
| /// |
| /// For example: |
| /// |
| /// var employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let neighbors = ["Bethany", "Eric", "Forlani", "Greta"] |
| /// employees.subtract(neighbors) |
| /// print(employees) |
| /// // Prints "["Chris", "Diana", "Alicia"]" |
| /// |
| /// - Parameter other: A sequence of elements. `other` must be finite. |
| public mutating func subtract<S : Sequence>(_ other: S) |
| where S.Iterator.Element == Element { |
| _subtract(other) |
| } |
| |
| internal mutating func _subtract<S : Sequence>(_ other: S) |
| where S.Iterator.Element == Element { |
| for item in other { |
| remove(item) |
| } |
| } |
| |
| /// Returns a new set with the elements that are common to both this set and |
| /// the given sequence. |
| /// |
| /// For example: |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let neighbors = ["Bethany", "Eric", "Forlani", "Greta"] |
| /// let bothNeighborsAndEmployees = employees.intersection(neighbors) |
| /// print(bothNeighborsAndEmployees) |
| /// // Prints "["Bethany", "Eric"]" |
| /// |
| /// - Parameter other: A sequence of elements. `other` must be finite. |
| /// - Returns: A new set. |
| public func intersection<S : Sequence>(_ other: S) -> Set<Element> |
| where S.Iterator.Element == Element { |
| let otherSet = Set(other) |
| return intersection(otherSet) |
| } |
| |
| /// Removes the elements of the set that aren't also in the given sequence. |
| /// |
| /// For example: |
| /// |
| /// var employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let neighbors = ["Bethany", "Eric", "Forlani", "Greta"] |
| /// employees.formIntersection(neighbors) |
| /// print(employees) |
| /// // Prints "["Bethany", "Eric"]" |
| /// |
| /// - Parameter other: A sequence of elements. `other` must be finite. |
| public mutating func formIntersection<S : Sequence>(_ other: S) |
| where S.Iterator.Element == Element { |
| // Because `intersect` needs to both modify and iterate over |
| // the left-hand side, the index may become invalidated during |
| // traversal so an intermediate set must be created. |
| // |
| // FIXME(performance): perform this operation at a lower level |
| // to avoid invalidating the index and avoiding a copy. |
| let result = self.intersection(other) |
| |
| // The result can only have fewer or the same number of elements. |
| // If no elements were removed, don't perform a reassignment |
| // as this may cause an unnecessary uniquing COW. |
| if result.count != count { |
| self = result |
| } |
| } |
| |
| /// Returns a new set with the elements that are either in this set or in the |
| /// given sequence, but not in both. |
| /// |
| /// For example: |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Diana", "Eric"] |
| /// let neighbors = ["Bethany", "Eric", "Forlani"] |
| /// let eitherNeighborsOrEmployees = employees.symmetricDifference(neighbors) |
| /// print(eitherNeighborsOrEmployees) |
| /// // Prints "["Diana", "Forlani", "Alicia"]" |
| /// |
| /// - Parameter other: A sequence of elements. `other` must be finite. |
| /// - Returns: A new set. |
| public func symmetricDifference<S : Sequence>(_ other: S) -> Set<Element> |
| where S.Iterator.Element == Element { |
| var newSet = self |
| newSet.formSymmetricDifference(other) |
| return newSet |
| } |
| |
| /// Replace this set with the elements contained in this set or the given |
| /// set, but not both. |
| /// |
| /// For example: |
| /// |
| /// var employees: Set = ["Alicia", "Bethany", "Diana", "Eric"] |
| /// let neighbors = ["Bethany", "Eric", "Forlani"] |
| /// employees.formSymmetricDifference(neighbors) |
| /// print(employees) |
| /// // Prints "["Diana", "Forlani", "Alicia"]" |
| /// |
| /// - Parameter other: A sequence of elements. `other` must be finite. |
| public mutating func formSymmetricDifference<S : Sequence>(_ other: S) |
| where S.Iterator.Element == Element { |
| let otherSet = Set(other) |
| formSymmetricDifference(otherSet) |
| } |
| |
| /// The hash value for the set. |
| /// |
| /// Two sets that are equal will always have equal hash values. |
| /// |
| /// Hash values are not guaranteed to be equal across different executions of |
| /// your program. Do not save hash values to use during a future execution. |
| public var hashValue: Int { |
| // FIXME: <rdar://problem/18915294> Cache Set<T> hashValue |
| var result: Int = _mixInt(0) |
| for member in self { |
| result ^= _mixInt(member.hashValue) |
| } |
| return result |
| } |
| |
| // |
| // `Sequence` conformance |
| // |
| |
| public func _customContainsEquatableElement(_ member: Element) -> Bool? { |
| return contains(member) |
| } |
| |
| public func _customIndexOfEquatableElement( |
| _ member: Element |
| ) -> Index?? { |
| return Optional(index(of: member)) |
| } |
| |
| // |
| // Collection conformance |
| // |
| |
| /// A Boolean value that indicates whether the set is empty. |
| public var isEmpty: Bool { |
| return count == 0 |
| } |
| |
| /// The first element of the set. |
| /// |
| /// The first element of the set is not necessarily the first element added |
| /// to the set. Don't expect any particular ordering of set elements. |
| /// |
| /// If the set is empty, the value of this property is `nil`. |
| public var first: Element? { |
| return count > 0 ? self[startIndex] : nil |
| } |
| } |
| |
| /// Check for both subset and equality relationship between |
| /// a set and some sequence (which may itself be a `Set`). |
| /// |
| /// (isSubset: lhs ⊂ rhs, isEqual: lhs ⊂ rhs and |lhs| = |rhs|) |
| internal func _compareSets<Element>(_ lhs: Set<Element>, _ rhs: Set<Element>) |
| -> (isSubset: Bool, isEqual: Bool) { |
| // FIXME(performance): performance could be better if we start by comparing |
| // counts. |
| for member in lhs { |
| if !rhs.contains(member) { |
| return (false, false) |
| } |
| } |
| return (true, lhs.count == rhs.count) |
| } |
| |
| extension Set { |
| /// Returns a Boolean value indicating whether two sets have equal elements. |
| /// |
| /// - Parameters: |
| /// - lhs: A set. |
| /// - rhs: Another set. |
| /// - Returns: `true` if the `lhs` and `rhs` have the same elements; otherwise, |
| /// `false`. |
| public static func == (lhs: Set<Element>, rhs: Set<Element>) -> Bool { |
| switch (lhs._variantStorage, rhs._variantStorage) { |
| case (.native(let lhsNativeOwner), .native(let rhsNativeOwner)): |
| let lhsNative = lhsNativeOwner.nativeStorage |
| let rhsNative = rhsNativeOwner.nativeStorage |
| |
| if lhsNativeOwner === rhsNativeOwner { |
| return true |
| } |
| |
| if lhsNative.count != rhsNative.count { |
| return false |
| } |
| |
| for member in lhs { |
| let (_, found) = |
| rhsNative._find(member, startBucket: rhsNative._bucket(member)) |
| if !found { |
| return false |
| } |
| } |
| return true |
| |
| case (_VariantSetStorage.cocoa(let lhsCocoa), |
| _VariantSetStorage.cocoa(let rhsCocoa)): |
| #if _runtime(_ObjC) |
| return _stdlib_NSObject_isEqual(lhsCocoa.cocoaSet, rhsCocoa.cocoaSet) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa set") |
| #endif |
| |
| case (_VariantSetStorage.native(let lhsNativeOwner), |
| _VariantSetStorage.cocoa(let rhsCocoa)): |
| #if _runtime(_ObjC) |
| let lhsNative = lhsNativeOwner.nativeStorage |
| |
| if lhsNative.count != rhsCocoa.count { |
| return false |
| } |
| |
| let endIndex = lhsNative.endIndex |
| var i = lhsNative.startIndex |
| while i != endIndex { |
| let key = lhsNative.assertingGet(i) |
| let bridgedKey: AnyObject = _bridgeAnythingToObjectiveC(key) |
| let optRhsValue: AnyObject? = rhsCocoa.maybeGet(bridgedKey) |
| if let rhsValue = optRhsValue { |
| if key == _forceBridgeFromObjectiveC(rhsValue, Element.self) { |
| i = i.successor() |
| continue |
| } |
| } |
| i = i.successor() |
| return false |
| } |
| return true |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa set") |
| #endif |
| |
| case (_VariantSetStorage.cocoa, _VariantSetStorage.native): |
| #if _runtime(_ObjC) |
| return rhs == lhs |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa set") |
| #endif |
| } |
| } |
| } |
| |
| extension Set : CustomStringConvertible, CustomDebugStringConvertible { |
| private func makeDescription(isDebug: Bool) -> String { |
| var result = isDebug ? "Set([" : "[" |
| var first = true |
| for member in self { |
| if first { |
| first = false |
| } else { |
| result += ", " |
| } |
| debugPrint(member, terminator: "", to: &result) |
| } |
| result += isDebug ? "])" : "]" |
| return result |
| } |
| |
| /// A string that represents the contents of the set. |
| public var description: String { |
| return makeDescription(isDebug: false) |
| } |
| |
| /// A string that represents the contents of the set, suitable for debugging. |
| public var debugDescription: String { |
| return makeDescription(isDebug: true) |
| } |
| } |
| |
| #if _runtime(_ObjC) |
| @_silgen_name("swift_stdlib_CFSetGetValues") |
| func _stdlib_CFSetGetValues(_ nss: _NSSet, _: UnsafeMutablePointer<AnyObject>) |
| |
| /// Equivalent to `NSSet.allObjects`, but does not leave objects on the |
| /// autorelease pool. |
| internal func _stdlib_NSSet_allObjects(_ nss: _NSSet) -> |
| _HeapBuffer<Int, AnyObject> { |
| let count = nss.count |
| let buffer = _HeapBuffer<Int, AnyObject>( |
| _HeapBufferStorage<Int, AnyObject>.self, count, count) |
| _stdlib_CFSetGetValues(nss, buffer.baseAddress) |
| return buffer |
| } |
| #endif |
| |
| //===--- Compiler conversion/casting entry points for Set<Element> --------===// |
| |
| func _impossible<T>(_:T.Type) -> T { |
| Builtin.unreachable() |
| } |
| |
| func _unsafeUpcast<T, U>(_ x: T, to: U.Type) -> U { |
| _sanityCheck(x is U) |
| return x as? U ?? _impossible(U.self) |
| } |
| |
| /// Perform a non-bridged upcast that always succeeds. |
| /// |
| /// - Precondition: `BaseValue` is a base class or base `@objc` |
| /// protocol (such as `AnyObject`) of `DerivedValue`. |
| public func _setUpCast<DerivedValue, BaseValue>(_ source: Set<DerivedValue>) |
| -> Set<BaseValue> { |
| var builder = _SetBuilder<BaseValue>(count: source.count) |
| for x in source { |
| builder.add(member: _unsafeUpcast(x, to: BaseValue.self)) |
| } |
| return builder.take() |
| } |
| |
| #if _runtime(_ObjC) |
| |
| /// Implements an unconditional upcast that involves bridging. |
| /// |
| /// The cast can fail if bridging fails. |
| /// |
| /// - Precondition: `SwiftValue` is bridged to Objective-C |
| /// and requires non-trivial bridging. |
| public func _setBridgeToObjectiveC<SwiftValue, ObjCValue>( |
| _ source: Set<SwiftValue> |
| ) -> Set<ObjCValue> { |
| _sanityCheck(_isClassOrObjCExistential(ObjCValue.self)) |
| _sanityCheck(!_isBridgedVerbatimToObjectiveC(SwiftValue.self)) |
| |
| var result = Set<ObjCValue>(minimumCapacity: source.count) |
| let valueBridgesDirectly = |
| _isBridgedVerbatimToObjectiveC(SwiftValue.self) == |
| _isBridgedVerbatimToObjectiveC(ObjCValue.self) |
| |
| for member in source { |
| var bridgedMember: ObjCValue |
| if valueBridgesDirectly { |
| bridgedMember = unsafeBitCast(member, to: ObjCValue.self) |
| } else { |
| let bridged: AnyObject = _bridgeAnythingToObjectiveC(member) |
| bridgedMember = unsafeBitCast(bridged, to: ObjCValue.self) |
| } |
| result.insert(bridgedMember) |
| } |
| return result |
| } |
| |
| #endif |
| |
| @_silgen_name("_swift_setDownCastIndirect") |
| public func _setDownCastIndirect<SourceValue, TargetValue>( |
| _ source: UnsafePointer<Set<SourceValue>>, |
| _ target: UnsafeMutablePointer<Set<TargetValue>>) { |
| target.initialize(to: _setDownCast(source.pointee)) |
| } |
| |
| /// Implements a forced downcast. This operation should have O(1) complexity. |
| /// |
| /// The cast can fail if bridging fails. The actual checks and bridging can be |
| /// deferred. |
| /// |
| /// - Precondition: `DerivedValue` is a subtype of `BaseValue` and both |
| /// are reference types. |
| public func _setDownCast<BaseValue, DerivedValue>(_ source: Set<BaseValue>) |
| -> Set<DerivedValue> { |
| |
| #if _runtime(_ObjC) |
| if _isClassOrObjCExistential(BaseValue.self) |
| && _isClassOrObjCExistential(DerivedValue.self) { |
| switch source._variantStorage { |
| case _VariantSetStorage.native(let nativeOwner): |
| return Set( |
| _immutableCocoaSet: |
| unsafeBitCast(nativeOwner, to: _NSSet.self)) |
| |
| case _VariantSetStorage.cocoa(let cocoaStorage): |
| return Set( |
| _immutableCocoaSet: |
| unsafeBitCast(cocoaStorage, to: _NSSet.self)) |
| } |
| } |
| #endif |
| return _setDownCastConditional(source)! |
| } |
| |
| @_silgen_name("_swift_setDownCastConditionalIndirect") |
| public func _setDownCastConditionalIndirect<SourceValue, TargetValue>( |
| _ source: UnsafePointer<Set<SourceValue>>, |
| _ target: UnsafeMutablePointer<Set<TargetValue>> |
| ) -> Bool { |
| if let result: Set<TargetValue> = _setDownCastConditional(source.pointee) { |
| target.initialize(to: result) |
| return true |
| } |
| return false |
| } |
| |
| /// Implements a conditional downcast. |
| /// |
| /// If the cast fails, the function returns `nil`. All checks should be |
| /// performed eagerly. |
| /// |
| /// - Precondition: `DerivedValue` is a subtype of `BaseValue` and both |
| /// are reference types. |
| public func _setDownCastConditional<BaseValue, DerivedValue>( |
| _ source: Set<BaseValue> |
| ) -> Set<DerivedValue>? { |
| return try? Set( |
| source.lazy.map { |
| try ($0 as? DerivedValue).unwrappedOrError() |
| }) |
| } |
| |
| #if _runtime(_ObjC) |
| |
| /// Implements an unconditional downcast that involves bridging. |
| /// |
| /// - Precondition: At least one of `SwiftValue` is a bridged value |
| /// type, and the corresponding `ObjCValue` is a reference type. |
| public func _setBridgeFromObjectiveC<ObjCValue, SwiftValue>( |
| _ source: Set<ObjCValue> |
| ) -> Set<SwiftValue> { |
| let result: Set<SwiftValue>? = _setBridgeFromObjectiveCConditional(source) |
| _precondition(result != nil, "This set cannot be bridged from Objective-C") |
| return result! |
| } |
| |
| /// Implements a conditional downcast that involves bridging. |
| /// |
| /// If the cast fails, the function returns `nil`. All checks should be |
| /// performed eagerly. |
| /// |
| /// - Precondition: At least one of `SwiftValue` is a bridged value |
| /// type, and the corresponding `ObjCValue` is a reference type. |
| public func _setBridgeFromObjectiveCConditional< |
| ObjCValue, SwiftValue |
| >( |
| _ source: Set<ObjCValue> |
| ) -> Set<SwiftValue>? { |
| _sanityCheck(_isClassOrObjCExistential(ObjCValue.self)) |
| _sanityCheck(!_isBridgedVerbatimToObjectiveC(SwiftValue.self)) |
| |
| let valueBridgesDirectly = |
| _isBridgedVerbatimToObjectiveC(SwiftValue.self) == |
| _isBridgedVerbatimToObjectiveC(ObjCValue.self) |
| |
| var result = Set<SwiftValue>(minimumCapacity: source.count) |
| for value in source { |
| // Downcast the value. |
| var resultValue: SwiftValue |
| if valueBridgesDirectly { |
| if let bridgedValue = value as? SwiftValue { |
| resultValue = bridgedValue |
| } else { |
| return nil |
| } |
| } else { |
| if let bridgedValue = _conditionallyBridgeFromObjectiveC( |
| _reinterpretCastToAnyObject(value), SwiftValue.self) { |
| resultValue = bridgedValue |
| } else { |
| return nil |
| } |
| } |
| result.insert(resultValue) |
| } |
| return result |
| } |
| |
| #endif |
| |
| //===--- APIs unique to Dictionary<Key, Value> ----------------------------===// |
| |
| /// A collection whose elements are key-value pairs. |
| /// |
| /// A dictionary is a type of hash table, providing fast access to the entries |
| /// it contains. Each entry in the table is identified using its key, which is |
| /// a hashable type such as a string or number. You use that key to retrieve |
| /// the corresponding value, which can be any object. In other languages, |
| /// similar data types are known as hashes or associated arrays. |
| /// |
| /// Create a new dictionary by using a dictionary literal. A dictionary literal |
| /// is a comma-separated list of key-value pairs, in which a colon separates |
| /// each key from its associated value, surrounded by square brackets. You can |
| /// assign a dictionary literal to a variable or constant or pass it to a |
| /// function that expects a dictionary. |
| /// |
| /// Here's how you would create a dictionary of HTTP response codes and their |
| /// related messages: |
| /// |
| /// var responseMessages = [200: "OK", |
| /// 403: "Access forbidden", |
| /// 404: "File not found", |
| /// 500: "Internal server error"] |
| /// |
| /// The `responseMessages` variable is inferred to have type `[Int: String]`. |
| /// The `Key` type of the dictionary is `Int`, and the `Value` type of the |
| /// dictionary is `String`. |
| /// |
| /// To create a dictionary with no key-value pairs, use an empty dictionary |
| /// literal (`[:]`). |
| /// |
| /// var emptyDict: [String: String] = [:] |
| /// |
| /// Any type that conforms to the `Hashable` protocol can be used as a |
| /// dictionary's `Key` type, including all of Swift's basic types. You can use |
| /// your own custom types as dictionary keys by making them conform to the |
| /// `Hashable` protocol. |
| /// |
| /// Getting and Setting Dictionary Values |
| /// ===================================== |
| /// |
| /// The most common way to access values in a dictionary is to use a key as a |
| /// subscript. Subscripting with a key takes the following form: |
| /// |
| /// print(responseMessages[200]) |
| /// // Prints "Optional("OK")" |
| /// |
| /// Subscripting a dictionary with a key returns an optional value, because a |
| /// dictionary might not hold a value for the key that you use in the |
| /// subscript. |
| /// |
| /// The next example uses key-based subscripting of the `responseMessages` |
| /// dictionary with two keys that exist in the dictionary and one that does |
| /// not. |
| /// |
| /// let httpResponseCodes = [200, 403, 301] |
| /// for code in httpResponseCodes { |
| /// if let message = responseMessages[code] { |
| /// print("Response \(code): \(message)") |
| /// } else { |
| /// print("Unknown response \(code)") |
| /// } |
| /// } |
| /// // Prints "Response 200: OK" |
| /// // Prints "Response 403: Access Forbidden" |
| /// // Prints "Unknown response 301" |
| /// |
| /// You can also update, modify, or remove keys and values from a dictionary |
| /// using the key-based subscript. To add a new key-value pair, assign a value |
| /// to a key that isn't yet a part of the dictionary. |
| /// |
| /// responseMessages[301] = "Moved permanently" |
| /// print(responseMessages[301]) |
| /// // Prints "Optional("Moved permanently")" |
| /// |
| /// Update an existing value by assigning a new value to a key that already |
| /// exists in the dictionary. If you assign `nil` to an existing key, the key |
| /// and its associated value are removed. The following example updates the |
| /// value for the `404` code to be simply "Not found" and removes the |
| /// key-value pair for the `500` code entirely. |
| /// |
| /// responseMessages[404] = "Not found" |
| /// responseMessages[500] = nil |
| /// print(responseMessages) |
| /// // Prints "[301: "Moved permanently", 200: "OK", 403: "Access forbidden", 404: "Not found"]" |
| /// |
| /// In a mutable `Dictionary` instance, you can modify in place a value that |
| /// you've accessed through a keyed subscript. The code sample below declares a |
| /// dictionary called `interestingNumbers` with string keys and values that |
| /// are integer arrays, then sorts each array in-place in descending order. |
| /// |
| /// var interestingNumbers = ["primes": [2, 3, 5, 7, 11, 13, 15], |
| /// "triangular": [1, 3, 6, 10, 15, 21, 28], |
| /// "hexagonal": [1, 6, 15, 28, 45, 66, 91]] |
| /// for key in interestingNumbers.keys { |
| /// interestingNumbers[key]?.sort(by: >) |
| /// } |
| /// |
| /// print(interestingNumbers["primes"]!) |
| /// // Prints "[15, 13, 11, 7, 5, 3, 2]" |
| /// |
| /// Iterating Over the Contents of a Dictionary |
| /// =========================================== |
| /// |
| /// Every dictionary is an unordered collection of key-value pairs. You can |
| /// iterate over a dictionary using a `for`-`in` loop, decomposing each |
| /// key-value pair into the elements of a tuple. |
| /// |
| /// let imagePaths = ["star": "/glyphs/star.png", |
| /// "portrait": "/images/content/portrait.jpg", |
| /// "spacer": "/images/shared/spacer.gif"] |
| /// |
| /// for (name, path) in imagePaths { |
| /// print("The path to '\(name)' is '\(path)'.") |
| /// } |
| /// // Prints "The path to 'star' is '/glyphs/star.png'." |
| /// // Prints "The path to 'portrait' is '/images/content/portrait.jpg'." |
| /// // Prints "The path to 'spacer' is '/images/shared/spacer.gif'." |
| /// |
| /// The order of key-value pairs in a dictionary is stable between mutations |
| /// but is otherwise unpredictable. If you need an ordered collection of |
| /// key-value pairs and don't need the fast key lookup that `Dictionary` |
| /// provides, see the `DictionaryLiteral` type for an alternative. |
| /// |
| /// You can search a dictionary's contents for a particular value using the |
| /// `contains(where:)` or `index(where:)` methods supplied by default |
| /// implementation. The following example checks to see if `imagePaths` contains |
| /// any paths in the `"/glyphs"` directory: |
| /// |
| /// let glyphIndex = imagePaths.index { $0.value.hasPrefix("/glyphs") } |
| /// if let index = glyphIndex { |
| /// print("The '\(imagesPaths[index].key)' image is a glyph.") |
| /// } else { |
| /// print("No glyphs found!") |
| /// } |
| /// // Prints "The 'star' image is a glyph.") |
| /// |
| /// Note that in this example, `imagePaths` is subscripted using a dictionary |
| /// index. Unlike the key-based subscript, the index-based subscript returns |
| /// the corresponding key-value pair as a non-optional tuple. |
| /// |
| /// print(imagePaths[glyphIndex!]) |
| /// // Prints "("star", "/glyphs/star.png")" |
| /// |
| /// A dictionary's indices stay valid across additions to the dictionary as |
| /// long as the dictionary has enough capacity to store the added values |
| /// without allocating more storage. When a dictionary outgrows its storage, |
| /// existing indices may be invalidated without any notification. |
| /// |
| /// When you know how many new values you're adding to a dictionary, use the |
| /// `init(minimumCapacity:)` initializer to allocate the correct amount of |
| /// storage. |
| /// |
| /// Bridging Between Dictionary and NSDictionary |
| /// ============================================ |
| /// |
| /// You can bridge between `Dictionary` and `NSDictionary` using the `as` |
| /// operator. For bridging to be possible, the `Key` and `Value` types of a |
| /// dictionary must be classes, `@objc` protocols, or types that bridge to |
| /// Foundation types. |
| /// |
| /// Bridging from `Dictionary` to `NSDictionary` always takes O(1) time and |
| /// space. When the dictionary's `Key` and `Value` types are neither classes |
| /// nor `@objc` protocols, any required bridging of elements occurs at the |
| /// first access of each element. For this reason, the first operation that |
| /// uses the contents of the dictionary may take O(*n*). |
| /// |
| /// Bridging from `NSDictionary` to `Dictionary` first calls the `copy(with:)` |
| /// method (`- copyWithZone:` in Objective-C) on the dictionary to get an |
| /// immutable copy and then performs additional Swift bookkeeping work that |
| /// takes O(1) time. For instances of `NSDictionary` that are already |
| /// immutable, `copy(with:)` usually returns the same dictionary in O(1) time; |
| /// otherwise, the copying performance is unspecified. The instances of |
| /// `NSDictionary` and `Dictionary` share storage using the same copy-on-write |
| /// optimization that is used when two instances of `Dictionary` share |
| /// storage. |
| /// |
| /// - SeeAlso: `Hashable` |
| @_fixed_layout |
| public struct Dictionary<Key : Hashable, Value> : |
| Collection, ExpressibleByDictionaryLiteral { |
| |
| internal typealias _Self = Dictionary<Key, Value> |
| internal typealias _VariantStorage = _VariantDictionaryStorage<Key, Value> |
| internal typealias _NativeStorage = _NativeDictionaryStorage<Key, Value> |
| |
| /// The element type of a dictionary: a tuple containing an individual |
| /// key-value pair. |
| public typealias Element = (key: Key, value: Value) |
| |
| /// The index type of a dictionary. |
| public typealias Index = DictionaryIndex<Key, Value> |
| |
| internal var _variantStorage: _VariantStorage |
| |
| /// Creates an empty dictionary. |
| public init() { |
| self = Dictionary<Key, Value>(minimumCapacity: 0) |
| } |
| |
| /// Creates a dictionary with at least the given number of elements worth of |
| /// storage. |
| /// |
| /// Use this initializer to avoid intermediate reallocations when you know |
| /// how many key-value pairs you are adding to a dictionary. The actual |
| /// capacity of the created dictionary is the smallest power of 2 that |
| /// is greater than or equal to `minimumCapacity`. |
| /// |
| /// - Parameter minimumCapacity: The minimum number of key-value pairs to |
| /// allocate storage for in the new dictionary. |
| public init(minimumCapacity: Int) { |
| _variantStorage = |
| .native(_NativeStorage.Owner(minimumCapacity: minimumCapacity)) |
| } |
| |
| internal init(_nativeStorage: _NativeDictionaryStorage<Key, Value>) { |
| _variantStorage = |
| .native(_NativeStorage.Owner(nativeStorage: _nativeStorage)) |
| } |
| |
| internal init( |
| _nativeStorageOwner: _NativeDictionaryStorageOwner<Key, Value> |
| ) { |
| _variantStorage = .native(_nativeStorageOwner) |
| } |
| |
| #if _runtime(_ObjC) |
| /// Private initializer used for bridging. |
| /// |
| /// Only use this initializer when both conditions are true: |
| /// |
| /// * it is statically known that the given `NSDictionary` is immutable; |
| /// * `Key` and `Value` are bridged verbatim to Objective-C (i.e., |
| /// are reference types). |
| public init(_immutableCocoaDictionary: _NSDictionary) { |
| _sanityCheck( |
| _isBridgedVerbatimToObjectiveC(Key.self) && |
| _isBridgedVerbatimToObjectiveC(Value.self), |
| "Dictionary can be backed by NSDictionary storage only when both key and value are bridged verbatim to Objective-C") |
| _variantStorage = .cocoa( |
| _CocoaDictionaryStorage(cocoaDictionary: _immutableCocoaDictionary)) |
| } |
| #endif |
| |
| // |
| // All APIs below should dispatch to `_variantStorage`, without doing any |
| // additional processing. |
| // |
| |
| /// The position of the first element in a nonempty dictionary. |
| /// |
| /// If the collection is empty, `startIndex` is equal to `endIndex`. |
| /// |
| /// - Complexity: Amortized O(1) if the dictionary does not wrap a bridged |
| /// `NSDictionary`. If the dictionary wraps a bridged `NSDictionary`, the |
| /// performance is unspecified. |
| public var startIndex: Index { |
| return _variantStorage.startIndex |
| } |
| |
| /// The dictionary's "past the end" position---that is, the position one |
| /// greater than the last valid subscript argument. |
| /// |
| /// If the collection is empty, `endIndex` is equal to `startIndex`. |
| /// |
| /// - Complexity: Amortized O(1) if the dictionary does not wrap a bridged |
| /// `NSDictionary`; otherwise, the performance is unspecified. |
| public var endIndex: Index { |
| return _variantStorage.endIndex |
| } |
| |
| // TODO: swift-3-indexing-model - add docs |
| public func index(after i: Index) -> Index { |
| return i.successor() |
| } |
| |
| /// Returns the index for the given key. |
| /// |
| /// If the given key is found in the dictionary, this method returns an index |
| /// into the dictionary that corresponds with the key-value pair. |
| /// |
| /// let countryCodes = ["BR": "Brazil", "GH": "Ghana", "JP": "Japan"] |
| /// let index = countryCodes.index(forKey: "JP") |
| /// |
| /// print("Country code for \(countryCodes[index!].value): '\(countryCodes[index!].key)'.") |
| /// // Prints "Country code for Japan: 'JP'." |
| /// |
| /// - Parameter key: The key to find in the dictionary. |
| /// - Returns: The index for `key` and its associated value if `key` is in |
| /// the dictionary; otherwise, `nil`. |
| @inline(__always) |
| public func index(forKey key: Key) -> Index? { |
| // Complexity: amortized O(1) for native storage, O(N) when wrapping an |
| // NSDictionary. |
| return _variantStorage.index(forKey: key) |
| } |
| |
| /// Accesses the key-value pair at the specified position. |
| /// |
| /// This subscript takes an index into the dictionary, instead of a key, and |
| /// returns the corresponding key-value pair as a tuple. When performing |
| /// collection-based operations that return an index into a dictionary, use |
| /// this subscript with the resulting value. |
| /// |
| /// For example, to find the key for a particular value in a dictionary, use |
| /// the `index(where:)` method. |
| /// |
| /// let countryCodes = ["BR": "Brazil", "GH": "Ghana", "JP": "Japan"] |
| /// if let index = countryCodes.index(where: { $0.value == "Japan" }) { |
| /// print(countryCodes[index]) |
| /// print("Japan's country code is '\(countryCodes[index].key)'.") |
| /// } else { |
| /// print("Didn't find 'Japan' as a value in the dictionary.") |
| /// } |
| /// // Prints "("JP", "Japan")" |
| /// // Prints "Japan's country code is 'JP'." |
| /// |
| /// - Parameter position: The position of the key-value pair to access. |
| /// `position` must be a valid index of the dictionary and not equal to |
| /// `endIndex`. |
| /// - Returns: A two-element tuple with the key and value corresponding to |
| /// `position`. |
| public subscript(position: Index) -> Element { |
| return _variantStorage.assertingGet(position) |
| } |
| |
| /// Accesses the value associated with the given key for reading and writing. |
| /// |
| /// This *key-based* subscript returns the value for the given key if the key |
| /// is found in the dictionary, or `nil` if the key is not found. |
| /// |
| /// The following example creates a new dictionary and prints the value of a |
| /// key found in the dictionary (`"Coral"`) and a key not found in the |
| /// dictionary (`"Cerise"`). |
| /// |
| /// var hues = ["Heliotrope": 296, "Coral": 16, "Aquamarine": 156] |
| /// print(hues["Coral"]) |
| /// // Prints "Optional(16)" |
| /// print(hues["Cerise"]) |
| /// // Prints "nil" |
| /// |
| /// When you assign a value for a key and that key already exists, the |
| /// dictionary overwrites the existing value. If the dictionary doesn't |
| /// contain the key, the key and value are added as a new key-value pair. |
| /// |
| /// Here, the value for the key `"Coral"` is updated from `16` to `18` and a |
| /// new key-value pair is added for the key `"Cerise"`. |
| /// |
| /// hues["Coral"] = 18 |
| /// print(hues["Coral"]) |
| /// // Prints "Optional(18)" |
| /// |
| /// hues["Cerise"] = 330 |
| /// print(hues["Cerise"]) |
| /// // Prints "Optional(330)" |
| /// |
| /// If you assign `nil` as the value for the given key, the dictionary |
| /// removes that key and its associated value. |
| /// |
| /// In the following example, the key-value pair for the key `"Aquamarine"` |
| /// is removed from the dictionary by assigning `nil` to the key-based |
| /// subscript. |
| /// |
| /// hues["Aquamarine"] = nil |
| /// print(hues) |
| /// // Prints "["Coral": 18, "Heliotrope": 296, "Cerise": 330]" |
| /// |
| /// - Parameter key: The key to find in the dictionary. |
| /// - Returns: The value associated with `key` if `key` is in the dictionary; |
| /// otherwise, `nil`. |
| public subscript(key: Key) -> Value? { |
| @inline(__always) |
| get { |
| return _variantStorage.maybeGet(key) |
| } |
| set(newValue) { |
| if let x = newValue { |
| // FIXME(performance): this loads and discards the old value. |
| _variantStorage.updateValue(x, forKey: key) |
| } |
| else { |
| // FIXME(performance): this loads and discards the old value. |
| removeValue(forKey: key) |
| } |
| } |
| } |
| |
| /// Updates the value stored in the dictionary for the given key, or adds a |
| /// new key-value pair if the key does not exist. |
| /// |
| /// Use this method instead of key-based subscripting when you need to know |
| /// whether the new value supplants the value of an existing key. If the |
| /// value of an existing key is updated, `updateValue(_:forKey:)` returns |
| /// the original value. |
| /// |
| /// var hues = ["Heliotrope": 296, "Coral": 16, "Aquamarine": 156] |
| /// |
| /// if let oldValue = hues.updateValue(18, forKey: "Coral") { |
| /// print("The old value of \(oldValue) was replaced with a new one.") |
| /// } |
| /// // Prints "The old value of 16 was replaced with a new one." |
| /// |
| /// If the given key is not present in the dictionary, this method adds the |
| /// key-value pair and returns `nil`. |
| /// |
| /// if let oldValue = hues.updateValue(330, forKey: "Cerise") { |
| /// print("The old value of \(oldValue) was replaced with a new one.") |
| /// } else { |
| /// print("No value was found in the dictionary for that key.") |
| /// } |
| /// // Prints "No value was found in the dictionary for that key." |
| /// |
| /// - Parameters: |
| /// - value: The new value to add to the dictionary. |
| /// - key: The key to associate with `value`. If `key` already exists in |
| /// the dictionary, `value` replaces the existing associated value. If |
| /// `key` isn't already a key of the dictionary, the `(key, value)` pair |
| /// is added. |
| /// - Returns: The value that was replaced, or `nil` if a new key-value pair |
| /// was added. |
| @discardableResult |
| public mutating func updateValue( |
| _ value: Value, forKey key: Key |
| ) -> Value? { |
| return _variantStorage.updateValue(value, forKey: key) |
| } |
| |
| /// Removes and returns the key-value pair at the specified index. |
| /// |
| /// Calling this method invalidates any existing indices for use with this |
| /// dictionary. |
| /// |
| /// - Parameter index: The position of the key-value pair to remove. `index` |
| /// must be a valid index of the dictionary, and must not equal the |
| /// dictionary's end index. |
| /// - Returns: The key-value pair that correspond to `index`. |
| /// |
| /// - Complexity: O(*n*), where *n* is the number of key-value pairs in the |
| /// dictionary. |
| @discardableResult |
| public mutating func remove(at index: Index) -> Element { |
| return _variantStorage.remove(at: index) |
| } |
| |
| /// Removes the given key and its associated value from the dictionary. |
| /// |
| /// If the key is found in the dictionary, this method returns the key's |
| /// associated value. On removal, this method invalidates all indices with |
| /// respect to the dictionary. |
| /// |
| /// var hues = ["Heliotrope": 296, "Coral": 16, "Aquamarine": 156] |
| /// if let value = hues.removeValue(forKey: "Coral") { |
| /// print("The value \(value) was removed.") |
| /// } |
| /// // Prints "The value 16 was removed." |
| /// |
| /// If the key isn't found in the dictionary, `removeValue(forKey:)` returns |
| /// `nil`. |
| /// |
| /// if let value = hues.removeValueForKey("Cerise") { |
| /// print("The value \(value) was removed.") |
| /// } else { |
| /// print("No value found for that key.") |
| /// } |
| /// // Prints "No value found for that key."" |
| /// |
| /// - Parameter key: The key to remove along with its associated value. |
| /// - Returns: The value that was removed, or `nil` if the key was not |
| /// present in the dictionary. |
| /// |
| /// - Complexity: O(*n*), where *n* is the number of key-value pairs in the |
| /// dictionary. |
| @discardableResult |
| public mutating func removeValue(forKey key: Key) -> Value? { |
| return _variantStorage.removeValue(forKey: key) |
| } |
| |
| /// Removes all key-value pairs from the dictionary. |
| /// |
| /// Calling this method invalidates all indices with respect to the |
| /// dictionary. |
| /// |
| /// - Parameter keepCapacity: Whether the dictionary should keep its |
| /// underlying storage. If you pass `true`, the operation preserves the |
| /// storage capacity that the collection has, otherwise the underlying |
| /// storage is released. The default is `false`. |
| /// |
| /// - Complexity: O(*n*), where *n* is the number of key-value pairs in the |
| /// dictionary. |
| public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) { |
| // The 'will not decrease' part in the documentation comment is worded very |
| // carefully. The capacity can increase if we replace Cocoa storage with |
| // native storage. |
| _variantStorage.removeAll(keepingCapacity: keepCapacity) |
| } |
| |
| /// The number of key-value pairs in the dictionary. |
| /// |
| /// - Complexity: O(1). |
| public var count: Int { |
| return _variantStorage.count |
| } |
| |
| // |
| // `Sequence` conformance |
| // |
| |
| /// Returns an iterator over the dictionary's key-value pairs. |
| /// |
| /// Iterating over a dictionary yields the key-value pairs as two-element |
| /// tuples. You can decompose the tuple in a `for`-`in` loop, which calls |
| /// `makeIterator()` behind the scenes, or when calling the iterator's |
| /// `next()` method directly. |
| /// |
| /// let hues = ["Heliotrope": 296, "Coral": 16, "Aquamarine": 156] |
| /// for (name, hueValue) in hues { |
| /// print("The hue of \(name) is \(hueValue).") |
| /// } |
| /// // Prints "The hue of Heliotrope is 296." |
| /// // Prints "The hue of Coral is 16." |
| /// // Prints "The hue of Aquamarine is 156." |
| /// |
| /// - Returns: An iterator over the dictionary with elements of type |
| /// `(key: Key, value: Value)`. |
| @inline(__always) |
| public func makeIterator() -> DictionaryIterator<Key, Value> { |
| return _variantStorage.makeIterator() |
| } |
| |
| // |
| // ExpressibleByDictionaryLiteral conformance |
| // |
| |
| /// Creates a dictionary initialized with a dictionary literal. |
| /// |
| /// Do not call this initializer directly. It is called by the compiler to |
| /// handle dictionary literals. To use a dictionary literal as the initial |
| /// value of a dictionary, enclose a comma-separated list of key-value pairs |
| /// in square brackets. |
| /// |
| /// For example, the code sample below creates a dictionary with string keys |
| /// and values. |
| /// |
| /// let countryCodes = ["BR": "Brazil", "GH": "Ghana", "JP": "Japan"] |
| /// print(countryCodes) |
| /// // Prints "["BR": "Brazil", "JP": "Japan", "GH": "Ghana"]" |
| /// |
| /// - Parameter elements: The key-value pairs that will make up the new |
| /// dictionary. Each key in `elements` must be unique. |
| /// |
| /// - SeeAlso: `ExpressibleByDictionaryLiteral` |
| @effects(readonly) |
| public init(dictionaryLiteral elements: (Key, Value)...) { |
| self.init(_nativeStorage: _NativeDictionaryStorage.fromArray(elements)) |
| } |
| |
| // |
| // APIs below this comment should be implemented strictly in terms of |
| // *public* APIs above. `_variantStorage` should not be accessed directly. |
| // |
| // This separates concerns for testing. Tests for the following APIs need |
| // not to concern themselves with testing correctness of behavior of |
| // underlying storage (and different variants of it), only correctness of the |
| // API itself. |
| // |
| |
| /// A collection containing just the keys of the dictionary. |
| /// |
| /// When iterated over, keys appear in this collection in the same order as they |
| /// occur in the dictionary's key-value pairs. Each key in the keys |
| /// collection has a unique value. |
| /// |
| /// let countryCodes = ["BR": "Brazil", "GH": "Ghana", "JP": "Japan"] |
| /// for k in countryCodes.keys { |
| /// print(k) |
| /// } |
| /// // Prints "BR" |
| /// // Prints "JP" |
| /// // Prints "GH" |
| public var keys: LazyMapCollection<Dictionary, Key> { |
| return self.lazy.map { $0.key } |
| } |
| |
| /// A collection containing just the values of the dictionary. |
| /// |
| /// When iterated over, values appear in this collection in the same order as they |
| /// occur in the dictionary's key-value pairs. |
| /// |
| /// let countryCodes = ["BR": "Brazil", "GH": "Ghana", "JP": "Japan"] |
| /// print(countryCodes) |
| /// // Prints "["BR": "Brazil", "JP": "Japan", "GH": "Ghana"]" |
| /// for v in countryCodes.values { |
| /// print(v) |
| /// } |
| /// // Prints "Brazil" |
| /// // Prints "Japan" |
| /// // Prints "Ghana" |
| public var values: LazyMapCollection<Dictionary, Value> { |
| return self.lazy.map { $0.value } |
| } |
| |
| // |
| // Collection conformance |
| // |
| |
| /// A Boolean value that indicates whether the dictionary is empty. (read |
| /// only) |
| /// |
| /// Dictionaries are empty when created with an initializer or an empty |
| /// dictionary literal. |
| /// |
| /// var frequencies: [String: Int] = [:] |
| /// print(frequencies.isEmpty) |
| /// // Prints "true" |
| public var isEmpty: Bool { |
| return count == 0 |
| } |
| |
| } |
| |
| extension Dictionary where Key : Equatable, Value : Equatable { |
| public static func == (lhs: [Key : Value], rhs: [Key : Value]) -> Bool { |
| switch (lhs._variantStorage, rhs._variantStorage) { |
| case (.native(let lhsNativeOwner), .native(let rhsNativeOwner)): |
| let lhsNative = lhsNativeOwner.nativeStorage |
| let rhsNative = rhsNativeOwner.nativeStorage |
| |
| if lhsNativeOwner === rhsNativeOwner { |
| return true |
| } |
| |
| if lhsNative.count != rhsNative.count { |
| return false |
| } |
| |
| for (k, v) in lhs { |
| let (pos, found) = rhsNative._find(k, startBucket: rhsNative._bucket(k)) |
| // FIXME: Can't write the simple code pending |
| // <rdar://problem/15484639> Refcounting bug |
| /* |
| if !found || rhs[pos].value != lhsElement.value { |
| return false |
| } |
| */ |
| if !found { |
| return false |
| } |
| if rhsNative.value(at: pos.offset) != v { |
| return false |
| } |
| } |
| return true |
| |
| case (.cocoa(let lhsCocoa), .cocoa(let rhsCocoa)): |
| #if _runtime(_ObjC) |
| return _stdlib_NSObject_isEqual( |
| lhsCocoa.cocoaDictionary, rhsCocoa.cocoaDictionary) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa dictionary") |
| #endif |
| |
| case (.native(let lhsNativeOwner), .cocoa(let rhsCocoa)): |
| #if _runtime(_ObjC) |
| let lhsNative = lhsNativeOwner.nativeStorage |
| |
| if lhsNative.count != rhsCocoa.count { |
| return false |
| } |
| |
| let endIndex = lhsNative.endIndex |
| var index = lhsNative.startIndex |
| while index != endIndex { |
| let (key, value) = lhsNative.assertingGet(index) |
| let optRhsValue: AnyObject? = |
| rhsCocoa.maybeGet(_bridgeAnythingToObjectiveC(key)) |
| // TODO: swift-3-indexing-model: change 'if' into 'guard'. |
| if let rhsValue = optRhsValue { |
| if value == _forceBridgeFromObjectiveC(rhsValue, Value.self) { |
| lhsNative.formIndex(after: &index) |
| continue |
| } |
| } |
| return false |
| } |
| return true |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa dictionary") |
| #endif |
| |
| case (.cocoa, .native): |
| #if _runtime(_ObjC) |
| return rhs == lhs |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa dictionary") |
| #endif |
| } |
| } |
| |
| public static func != (lhs: [Key : Value], rhs: [Key : Value]) -> Bool { |
| return !(lhs == rhs) |
| } |
| } |
| |
| extension Dictionary : CustomStringConvertible, CustomDebugStringConvertible { |
| internal func _makeDescription() -> String { |
| if count == 0 { |
| return "[:]" |
| } |
| |
| var result = "[" |
| var first = true |
| for (k, v) in self { |
| if first { |
| first = false |
| } else { |
| result += ", " |
| } |
| debugPrint(k, terminator: "", to: &result) |
| result += ": " |
| debugPrint(v, terminator: "", to: &result) |
| } |
| result += "]" |
| return result |
| } |
| |
| /// A string that represents the contents of the dictionary. |
| public var description: String { |
| return _makeDescription() |
| } |
| |
| /// A string that represents the contents of the dictionary, suitable for |
| /// debugging. |
| public var debugDescription: String { |
| return _makeDescription() |
| } |
| } |
| |
| #if _runtime(_ObjC) |
| /// Equivalent to `NSDictionary.allKeys`, but does not leave objects on the |
| /// autorelease pool. |
| internal func _stdlib_NSDictionary_allKeys(_ nsd: _NSDictionary) |
| -> _HeapBuffer<Int, AnyObject> { |
| let count = nsd.count |
| let buffer = _HeapBuffer<Int, AnyObject>( |
| _HeapBufferStorage<Int, AnyObject>.self, count, count) |
| |
| nsd.getObjects(nil, andKeys: buffer.baseAddress) |
| return buffer |
| } |
| #endif |
| |
| //===--- Compiler conversion/casting entry points for Dictionary<K, V> ----===// |
| |
| /// Perform a non-bridged upcast that always succeeds. |
| /// |
| /// - Precondition: `BaseKey` and `BaseValue` are base classes or base `@objc` |
| /// protocols (such as `AnyObject`) of `DerivedKey` and `DerivedValue`, |
| /// respectively. |
| public func _dictionaryUpCast<DerivedKey, DerivedValue, BaseKey, BaseValue>( |
| _ source: Dictionary<DerivedKey, DerivedValue> |
| ) -> Dictionary<BaseKey, BaseValue> { |
| var result = Dictionary<BaseKey, BaseValue>(minimumCapacity: source.count) |
| |
| for (k, v) in source { |
| result[_unsafeUpcast(k, to: BaseKey.self)] |
| = _unsafeUpcast(v, to: BaseValue.self) |
| } |
| return result |
| } |
| |
| #if _runtime(_ObjC) |
| |
| /// Implements an unconditional upcast that involves bridging. |
| /// |
| /// The cast can fail if bridging fails. |
| /// |
| /// - Precondition: `SwiftKey` and `SwiftValue` are bridged to Objective-C, |
| /// and at least one of them requires non-trivial bridging. |
| @inline(never) |
| @_semantics("stdlib_binary_only") |
| public func _dictionaryBridgeToObjectiveC< |
| SwiftKey, SwiftValue, ObjCKey, ObjCValue |
| >( |
| _ source: Dictionary<SwiftKey, SwiftValue> |
| ) -> Dictionary<ObjCKey, ObjCValue> { |
| |
| // Note: We force this function to stay in the swift dylib because |
| // it is not performance sensitive and keeping it in the dylib saves |
| // a new kilobytes for each specialization for all users of dictionary. |
| |
| _sanityCheck( |
| !_isBridgedVerbatimToObjectiveC(SwiftKey.self) || |
| !_isBridgedVerbatimToObjectiveC(SwiftValue.self)) |
| _sanityCheck( |
| _isClassOrObjCExistential(ObjCKey.self) || |
| _isClassOrObjCExistential(ObjCValue.self)) |
| |
| var result = Dictionary<ObjCKey, ObjCValue>(minimumCapacity: source.count) |
| let keyBridgesDirectly = |
| _isBridgedVerbatimToObjectiveC(SwiftKey.self) == |
| _isBridgedVerbatimToObjectiveC(ObjCKey.self) |
| let valueBridgesDirectly = |
| _isBridgedVerbatimToObjectiveC(SwiftValue.self) == |
| _isBridgedVerbatimToObjectiveC(ObjCValue.self) |
| for (key, value) in source { |
| // Bridge the key |
| var bridgedKey: ObjCKey |
| if keyBridgesDirectly { |
| bridgedKey = unsafeBitCast(key, to: ObjCKey.self) |
| } else { |
| let bridged: AnyObject = _bridgeAnythingToObjectiveC(key) |
| bridgedKey = unsafeBitCast(bridged, to: ObjCKey.self) |
| } |
| |
| // Bridge the value |
| var bridgedValue: ObjCValue |
| if valueBridgesDirectly { |
| bridgedValue = unsafeBitCast(value, to: ObjCValue.self) |
| } else { |
| let bridged: AnyObject? = _bridgeAnythingToObjectiveC(value) |
| bridgedValue = unsafeBitCast(bridged, to: ObjCValue.self) |
| } |
| |
| result[bridgedKey] = bridgedValue |
| } |
| |
| return result |
| } |
| #endif |
| |
| @_silgen_name("_swift_dictionaryDownCastIndirect") |
| public func _dictionaryDownCastIndirect<SourceKey, SourceValue, |
| TargetKey, TargetValue>( |
| _ source: UnsafePointer<Dictionary<SourceKey, SourceValue>>, |
| _ target: UnsafeMutablePointer<Dictionary<TargetKey, TargetValue>>) { |
| target.initialize(to: _dictionaryDownCast(source.pointee)) |
| } |
| |
| /// Implements a forced downcast. This operation should have O(1) complexity. |
| /// |
| /// The cast can fail if bridging fails. The actual checks and bridging can be |
| /// deferred. |
| /// |
| /// - Precondition: `DerivedKey` is a subtype of `BaseKey`, `DerivedValue` is |
| /// a subtype of `BaseValue`, and all of these types are reference types. |
| public func _dictionaryDownCast<BaseKey, BaseValue, DerivedKey, DerivedValue>( |
| _ source: Dictionary<BaseKey, BaseValue> |
| ) -> Dictionary<DerivedKey, DerivedValue> { |
| |
| #if _runtime(_ObjC) |
| if _isClassOrObjCExistential(BaseKey.self) |
| && _isClassOrObjCExistential(BaseValue.self) |
| && _isClassOrObjCExistential(DerivedKey.self) |
| && _isClassOrObjCExistential(DerivedValue.self) { |
| |
| switch source._variantStorage { |
| case .native(let nativeOwner): |
| // FIXME(performance): this introduces an indirection through Objective-C |
| // runtime, even though we access native storage. But we cannot |
| // unsafeBitCast the owner object, because that would change the generic |
| // arguments. |
| // |
| // One way to solve this is to add a third, read-only, representation to |
| // variant storage: like _NativeDictionaryStorageOwner, but it would |
| // perform casts when accessing elements. |
| // |
| // Note: it is safe to treat the storage as immutable here because |
| // Dictionary will not mutate storage with reference count greater than 1. |
| return Dictionary( |
| _immutableCocoaDictionary: |
| unsafeBitCast(nativeOwner, to: _NSDictionary.self)) |
| |
| case .cocoa(let cocoaStorage): |
| return Dictionary( |
| _immutableCocoaDictionary: |
| unsafeBitCast(cocoaStorage, to: _NSDictionary.self)) |
| } |
| } |
| #endif |
| return _dictionaryDownCastConditional(source)! |
| } |
| |
| @_silgen_name("_swift_dictionaryDownCastConditionalIndirect") |
| public func _dictionaryDownCastConditionalIndirect<SourceKey, SourceValue, |
| TargetKey, TargetValue>( |
| _ source: UnsafePointer<Dictionary<SourceKey, SourceValue>>, |
| _ target: UnsafeMutablePointer<Dictionary<TargetKey, TargetValue>> |
| ) -> Bool { |
| if let result: Dictionary<TargetKey, TargetValue> |
| = _dictionaryDownCastConditional(source.pointee) { |
| target.initialize(to: result) |
| return true |
| } |
| return false |
| } |
| |
| /// Implements a conditional downcast. |
| /// |
| /// If the cast fails, the function returns `nil`. All checks should be |
| /// performed eagerly. |
| /// |
| /// - Precondition: `DerivedKey` is a subtype of `BaseKey`, `DerivedValue` is |
| /// a subtype of `BaseValue`, and all of these types are reference types. |
| public func _dictionaryDownCastConditional< |
| BaseKey, BaseValue, DerivedKey, DerivedValue |
| >( |
| _ source: Dictionary<BaseKey, BaseValue> |
| ) -> Dictionary<DerivedKey, DerivedValue>? { |
| |
| var result = Dictionary<DerivedKey, DerivedValue>() |
| for (k, v) in source { |
| guard let k1 = k as? DerivedKey, let v1 = v as? DerivedValue |
| else { return nil } |
| result[k1] = v1 |
| } |
| return result |
| } |
| |
| #if _runtime(_ObjC) |
| /// Implements an unconditional downcast that involves bridging. |
| /// |
| /// - Precondition: At least one of `SwiftKey` or `SwiftValue` is a bridged value |
| /// type, and the corresponding `ObjCKey` or `ObjCValue` is a reference type. |
| public func _dictionaryBridgeFromObjectiveC< |
| ObjCKey, ObjCValue, SwiftKey, SwiftValue |
| >( |
| _ source: Dictionary<ObjCKey, ObjCValue> |
| ) -> Dictionary<SwiftKey, SwiftValue> { |
| let result: Dictionary<SwiftKey, SwiftValue>? = |
| _dictionaryBridgeFromObjectiveCConditional(source) |
| _precondition(result != nil, "dictionary cannot be bridged from Objective-C") |
| return result! |
| } |
| |
| /// Implements a conditional downcast that involves bridging. |
| /// |
| /// If the cast fails, the function returns `nil`. All checks should be |
| /// performed eagerly. |
| /// |
| /// - Precondition: At least one of `SwiftKey` or `SwiftValue` is a bridged value |
| /// type, and the corresponding `ObjCKey` or `ObjCValue` is a reference type. |
| public func _dictionaryBridgeFromObjectiveCConditional< |
| ObjCKey, ObjCValue, SwiftKey, SwiftValue |
| >( |
| _ source: Dictionary<ObjCKey, ObjCValue> |
| ) -> Dictionary<SwiftKey, SwiftValue>? { |
| _sanityCheck( |
| _isClassOrObjCExistential(ObjCKey.self) || |
| _isClassOrObjCExistential(ObjCValue.self)) |
| _sanityCheck( |
| !_isBridgedVerbatimToObjectiveC(SwiftKey.self) || |
| !_isBridgedVerbatimToObjectiveC(SwiftValue.self)) |
| |
| let keyBridgesDirectly = |
| _isBridgedVerbatimToObjectiveC(SwiftKey.self) == |
| _isBridgedVerbatimToObjectiveC(ObjCKey.self) |
| let valueBridgesDirectly = |
| _isBridgedVerbatimToObjectiveC(SwiftValue.self) == |
| _isBridgedVerbatimToObjectiveC(ObjCValue.self) |
| |
| var result = Dictionary<SwiftKey, SwiftValue>(minimumCapacity: source.count) |
| for (key, value) in source { |
| // Downcast the key. |
| var resultKey: SwiftKey |
| if keyBridgesDirectly { |
| if let bridgedKey = key as? SwiftKey { |
| resultKey = bridgedKey |
| } else { |
| return nil |
| } |
| } else { |
| if let bridgedKey = _conditionallyBridgeFromObjectiveC( |
| _reinterpretCastToAnyObject(key), SwiftKey.self) { |
| resultKey = bridgedKey |
| } else { |
| return nil |
| } |
| } |
| |
| // Downcast the value. |
| var resultValue: SwiftValue |
| if valueBridgesDirectly { |
| if let bridgedValue = value as? SwiftValue { |
| resultValue = bridgedValue |
| } else { |
| return nil |
| } |
| } else { |
| if let bridgedValue = _conditionallyBridgeFromObjectiveC( |
| _reinterpretCastToAnyObject(value), SwiftValue.self) { |
| resultValue = bridgedValue |
| } else { |
| return nil |
| } |
| } |
| |
| result[resultKey] = resultValue |
| } |
| return result |
| } |
| #endif |
| //===--- APIs templated for Dictionary and Set ----------------------------===// |
| |
| %{ |
| # Tuple items: |
| # Self: Class name |
| # |
| # a_self: Type name when using a generic noun |
| # |
| # TypeParametersDecl: Generic parameters appearing in top-level declarations |
| # |
| # TypeParameters: Generic parameters appearing in typealiases, etc. |
| # |
| # AnyTypeParameters: Generic parameters where all variables are AnyObject |
| # |
| # Sequence: The type of things appearing in the collection as a sequence |
| # e.g. dictionaries are a sequence of (Key, Value) pairs. |
| # AnySequenceType: The same as Sequence but everything is an AnyObject. |
| collections = [ |
| ('Set', |
| 'set', |
| 'Element : Hashable', |
| 'Element', |
| 'AnyObject', |
| 'Element', |
| 'AnyObject'), |
| |
| ('Dictionary', |
| 'dictionary', |
| 'Key : Hashable, Value', |
| 'Key, Value', |
| 'AnyObject, AnyObject', |
| '(key: Key, value: Value)', |
| '(AnyObject, AnyObject)'), |
| ] |
| }% |
| |
| /// Header part of the native storage. |
| internal struct _HashedContainerStorageHeader { |
| internal init(capacity: Int) { |
| self.capacity = capacity |
| } |
| |
| internal var capacity: Int |
| internal var count: Int = 0 |
| internal var maxLoadFactorInverse: Double = |
| _hashContainerDefaultMaxLoadFactorInverse |
| } |
| |
| % for (Self, a_self, TypeParametersDecl, TypeParameters, AnyTypeParameters, Sequence, AnySequenceType) in collections: |
| |
| /// An instance of this class has all `${Self}` data tail-allocated. |
| /// Enough bytes are allocated to hold the bitmap for marking valid entries, |
| /// keys, and values. The data layout starts with the bitmap, followed by the |
| /// keys, followed by the values. |
| final internal class _Native${Self}StorageImpl<${TypeParameters}> : |
| ManagedBuffer<_HashedContainerStorageHeader, UInt8> { |
| // Note: It is intended that ${TypeParameters} |
| // (without : Hashable) is used here - this storage must work |
| // with non-Hashable types. |
| |
| internal typealias BufferPointer = |
| ManagedBufferPointer<_HashedContainerStorageHeader, UInt8> |
| internal typealias StorageImpl = _Native${Self}StorageImpl |
| |
| %if Self == 'Set': # Set needs these to keep signatures simple. |
| internal typealias Key = ${TypeParameters} |
| %end |
| |
| /// Returns the bytes necessary to store a bit map of 'capacity' bytes and |
| /// padding to align the start to word alignment. |
| internal static func bytesForBitMap(capacity: Int) -> Int { |
| let numWords = _UnsafeBitMap.sizeInWords(forSizeInBits: capacity) |
| return numWords * MemoryLayout<UInt>.stride + MemoryLayout<UInt>.alignment |
| } |
| |
| /// Returns the bytes necessary to store 'capacity' keys and padding to align |
| /// the start to the alignment of the 'Key' type assuming a word aligned base |
| /// address. |
| internal static func bytesForKeys(capacity: Int) -> Int { |
| let padding = max(0, MemoryLayout<Key>.alignment - MemoryLayout<UInt>.alignment) |
| return MemoryLayout<Key>.stride * capacity + padding |
| } |
| |
| %if Self == 'Dictionary': |
| /// Returns the bytes necessary to store 'capacity' values and padding to |
| /// align the start to the alignment of the 'Value' type assuming a base |
| /// address aligned to the maximum of the alignment of the 'Key' type and the |
| /// alignment of a word. |
| internal static func bytesForValues(capacity: Int) -> Int { |
| let maxPrevAlignment = max(MemoryLayout<Key>.alignment, MemoryLayout<UInt>.alignment) |
| let padding = max(0, MemoryLayout<Value>.alignment - maxPrevAlignment) |
| return MemoryLayout<Value>.stride * capacity + padding |
| } |
| %end |
| |
| internal var buffer: BufferPointer { |
| return BufferPointer(self) |
| } |
| |
| // This API is unsafe and needs a `_fixLifetime` in the caller. |
| internal var _body: _HashedContainerStorageHeader { |
| unsafeAddress { |
| return UnsafePointer(buffer._headerPointer) |
| } |
| unsafeMutableAddress { |
| return buffer._headerPointer |
| } |
| } |
| |
| @_versioned |
| internal var _capacity: Int { |
| defer { _fixLifetime(self) } |
| return _body.capacity |
| } |
| |
| @_versioned |
| internal var _count: Int { |
| set { |
| defer { _fixLifetime(self) } |
| _body.count = newValue |
| } |
| get { |
| defer { _fixLifetime(self) } |
| return _body.count |
| } |
| } |
| |
| internal var _maxLoadFactorInverse: Double { |
| defer { _fixLifetime(self) } |
| return _body.maxLoadFactorInverse |
| } |
| |
| // This API is unsafe and needs a `_fixLifetime` in the caller. |
| internal |
| var _initializedHashtableEntriesBitMapStorage: UnsafeMutablePointer<UInt> { |
| return _roundUp(buffer._elementPointer, toAlignmentOf: UInt.self) |
| } |
| |
| // This API is unsafe and needs a `_fixLifetime` in the caller. |
| internal var _keys: UnsafeMutablePointer<Key> { |
| let bitMapSizeInBytes = |
| _unsafeMultiply( |
| _UnsafeBitMap.sizeInWords(forSizeInBits: _body.capacity), |
| MemoryLayout<UInt>.stride) |
| let start = |
| UnsafeMutableRawPointer(_initializedHashtableEntriesBitMapStorage) |
| + bitMapSizeInBytes |
| return _roundUp(start, toAlignmentOf: Key.self) |
| } |
| |
| %if Self == 'Dictionary': |
| // This API is unsafe and needs a `_fixLifetime` in the caller. |
| internal var _values: UnsafeMutablePointer<Value> { |
| let keysSizeInBytes = _unsafeMultiply(_body.capacity, MemoryLayout<Key>.stride) |
| let start = UnsafeMutableRawPointer(_keys) + keysSizeInBytes |
| return _roundUp(start, toAlignmentOf: Value.self) |
| } |
| %end |
| |
| /// Create a storage instance with room for 'capacity' entries and all entries |
| /// marked invalid. |
| internal class func create(capacity: Int) -> StorageImpl { |
| let requiredCapacity = |
| bytesForBitMap(capacity: capacity) + bytesForKeys(capacity: capacity) |
| %if Self == 'Dictionary': |
| + bytesForValues(capacity: capacity) |
| %end |
| |
| let r = super.create(minimumCapacity: requiredCapacity) { _ in |
| return _HashedContainerStorageHeader(capacity: capacity) |
| } |
| let storage = r as! StorageImpl |
| let initializedEntries = _UnsafeBitMap( |
| storage: storage._initializedHashtableEntriesBitMapStorage, |
| bitCount: capacity) |
| initializedEntries.initializeToZero() |
| return storage |
| } |
| |
| deinit { |
| let capacity = _capacity |
| let initializedEntries = _UnsafeBitMap( |
| storage: _initializedHashtableEntriesBitMapStorage, bitCount: capacity) |
| let keys = _keys |
| %if Self == 'Dictionary': |
| let values = _values |
| %end |
| |
| if !_isPOD(Key.self) { |
| for i in 0 ..< capacity { |
| if initializedEntries[i] { |
| (keys+i).deinitialize() |
| } |
| } |
| } |
| |
| %if Self == 'Dictionary': |
| if !_isPOD(Value.self) { |
| for i in 0 ..< capacity { |
| if initializedEntries[i] { |
| (values+i).deinitialize() |
| } |
| } |
| } |
| %end |
| buffer._headerPointer.deinitialize() |
| _fixLifetime(self) |
| } |
| } |
| |
| @_fixed_layout |
| public // @testable |
| struct _Native${Self}Storage<${TypeParametersDecl}> : |
| _HashStorage, CustomStringConvertible { |
| internal typealias Owner = _Native${Self}StorageOwner<${TypeParameters}> |
| internal typealias StorageImpl = _Native${Self}StorageImpl<${TypeParameters}> |
| internal typealias SequenceElement = ${Sequence} |
| %if Self == 'Set': |
| internal typealias SequenceElementWithoutLabels = Element |
| %else: |
| internal typealias SequenceElementWithoutLabels = (Key, Value) |
| %end |
| internal typealias Storage = _Native${Self}Storage<${TypeParameters}> |
| |
| %if Self == 'Set': # Set needs these to keep signatures simple. |
| internal typealias Key = ${TypeParameters} |
| internal typealias Value = ${TypeParameters} |
| %end |
| |
| internal let buffer: StorageImpl |
| |
| internal let initializedEntries: _UnsafeBitMap |
| internal let keys: UnsafeMutablePointer<Key> |
| %if Self == 'Dictionary': |
| internal let values: UnsafeMutablePointer<Value> |
| %end |
| |
| internal init(capacity: Int) { |
| buffer = StorageImpl.create(capacity: capacity) |
| initializedEntries = _UnsafeBitMap( |
| storage: buffer._initializedHashtableEntriesBitMapStorage, |
| bitCount: capacity) |
| keys = buffer._keys |
| %if Self == 'Dictionary': |
| values = buffer._values |
| %end |
| _fixLifetime(buffer) |
| } |
| |
| internal init(minimumCapacity: Int = 2) { |
| // Make sure there's a representable power of 2 >= minimumCapacity |
| _sanityCheck(minimumCapacity <= (Int.max >> 1) + 1) |
| |
| var capacity = 2 |
| while capacity < minimumCapacity { |
| capacity <<= 1 |
| } |
| |
| self = _Native${Self}Storage(capacity: capacity) |
| } |
| |
| @_transparent |
| public // @testable |
| var capacity: Int { |
| return buffer._capacity |
| } |
| |
| @_versioned |
| @_transparent |
| internal var count: Int { |
| get { |
| return buffer._count |
| } |
| nonmutating set(newValue) { |
| buffer._count = newValue |
| } |
| } |
| |
| @_transparent |
| internal var maxLoadFactorInverse: Double { |
| return buffer._maxLoadFactorInverse |
| } |
| |
| @_versioned |
| @inline(__always) |
| internal func key(at i: Int) -> Key { |
| _precondition(i >= 0 && i < capacity) |
| _sanityCheck(isInitializedEntry(at: i)) |
| |
| let res = (keys + i).pointee |
| _fixLifetime(self) |
| return res |
| } |
| |
| @_versioned |
| internal func isInitializedEntry(at i: Int) -> Bool { |
| _precondition(i >= 0 && i < capacity) |
| return initializedEntries[i] |
| } |
| |
| @_transparent |
| internal func destroyEntry(at i: Int) { |
| _sanityCheck(isInitializedEntry(at: i)) |
| (keys + i).deinitialize() |
| %if Self == 'Dictionary': |
| (values + i).deinitialize() |
| %end |
| initializedEntries[i] = false |
| _fixLifetime(self) |
| } |
| |
| %if Self == 'Set': |
| @_transparent |
| internal func initializeKey(_ k: Key, at i: Int) { |
| _sanityCheck(!isInitializedEntry(at: i)) |
| |
| (keys + i).initialize(to: k) |
| initializedEntries[i] = true |
| _fixLifetime(self) |
| } |
| |
| @_transparent |
| internal func moveInitializeEntry(from: Storage, at: Int, toEntryAt: Int) { |
| _sanityCheck(!isInitializedEntry(at: toEntryAt)) |
| (keys + toEntryAt).initialize(to: (from.keys + at).move()) |
| from.initializedEntries[at] = false |
| initializedEntries[toEntryAt] = true |
| } |
| |
| internal func setKey(_ key: Key, at i: Int) { |
| _precondition(i >= 0 && i < capacity) |
| _sanityCheck(isInitializedEntry(at: i)) |
| |
| (keys + i).pointee = key |
| _fixLifetime(self) |
| } |
| |
| %elif Self == 'Dictionary': |
| @_transparent |
| internal func initializeKey(_ k: Key, value v: Value, at i: Int) { |
| _sanityCheck(!isInitializedEntry(at: i)) |
| |
| (keys + i).initialize(to: k) |
| (values + i).initialize(to: v) |
| initializedEntries[i] = true |
| _fixLifetime(self) |
| } |
| |
| @_transparent |
| internal func moveInitializeEntry(from: Storage, at: Int, toEntryAt: Int) { |
| _sanityCheck(!isInitializedEntry(at: toEntryAt)) |
| (keys + toEntryAt).initialize(to: (from.keys + at).move()) |
| (values + toEntryAt).initialize(to: (from.values + at).move()) |
| from.initializedEntries[at] = false |
| initializedEntries[toEntryAt] = true |
| } |
| |
| @_versioned |
| @_transparent |
| internal func value(at i: Int) -> Value { |
| _sanityCheck(isInitializedEntry(at: i)) |
| |
| let res = (values + i).pointee |
| _fixLifetime(self) |
| return res |
| } |
| |
| @_transparent |
| internal func setKey(_ key: Key, value: Value, at i: Int) { |
| _sanityCheck(isInitializedEntry(at: i)) |
| (keys + i).pointee = key |
| (values + i).pointee = value |
| _fixLifetime(self) |
| } |
| |
| %end |
| |
| // |
| // Implementation details |
| // |
| |
| internal var _bucketMask: Int { |
| // The capacity is not negative, therefore subtracting 1 will not overflow. |
| return capacity &- 1 |
| } |
| |
| @_versioned |
| internal func _bucket(_ k: Key) -> Int { |
| return _squeezeHashValue(k.hashValue, 0..<capacity) |
| } |
| |
| @_versioned |
| internal func _index(after bucket: Int) -> Int { |
| // Bucket is within 0 and capacity. Therefore adding 1 does not overflow. |
| return (bucket &+ 1) & _bucketMask |
| } |
| |
| internal func _prev(_ bucket: Int) -> Int { |
| // Bucket is not negative. Therefore subtracting 1 does not overflow. |
| return (bucket &- 1) & _bucketMask |
| } |
| |
| /// Search for a given key starting from the specified bucket. |
| /// |
| /// If the key is not present, returns the position where it could be |
| /// inserted. |
| @_versioned |
| @inline(__always) |
| internal func _find(_ key: Key, startBucket: Int) |
| -> (pos: Index, found: Bool) { |
| |
| var bucket = startBucket |
| |
| // The invariant guarantees there's always a hole, so we just loop |
| // until we find one |
| while true { |
| let isHole = !isInitializedEntry(at: bucket) |
| if isHole { |
| return (Index(nativeStorage: self, offset: bucket), false) |
| } |
| if self.key(at: bucket) == key { |
| return (Index(nativeStorage: self, offset: bucket), true) |
| } |
| bucket = _index(after: bucket) |
| } |
| } |
| |
| @_transparent |
| internal static func minimumCapacity( |
| minimumCount: Int, |
| maxLoadFactorInverse: Double |
| ) -> Int { |
| // `minimumCount + 1` below ensures that we don't fill in the last hole |
| return max(Int(Double(minimumCount) * maxLoadFactorInverse), |
| minimumCount + 1) |
| } |
| |
| /// Storage should be uniquely referenced. |
| /// The `key` should not be present in the ${Self}. |
| /// This function does *not* update `count`. |
| |
| %if Self == 'Set': |
| |
| internal mutating func unsafeAddNew(key newKey: Element) { |
| let (i, found) = _find(newKey, startBucket: _bucket(newKey)) |
| _sanityCheck( |
| !found, "unsafeAddNew was called, but the key is already present") |
| initializeKey(newKey, at: i.offset) |
| } |
| |
| %elif Self == 'Dictionary': |
| |
| internal mutating func unsafeAddNew(key newKey: Key, value: Value) { |
| let (i, found) = _find(newKey, startBucket: _bucket(newKey)) |
| _sanityCheck( |
| !found, "unsafeAddNew was called, but the key is already present") |
| initializeKey(newKey, value: value, at: i.offset) |
| } |
| |
| %end |
| |
| /// A textual representation of `self`. |
| public // @testable |
| var description: String { |
| var result = "" |
| #if INTERNAL_CHECKS_ENABLED |
| for i in 0..<capacity { |
| if isInitializedEntry(at: i) { |
| let key = self.key(at: i) |
| result += "bucket \(i), ideal bucket = \(_bucket(key)), key = \(key)\n" |
| } else { |
| result += "bucket \(i), empty\n" |
| } |
| } |
| #endif |
| return result |
| } |
| |
| // |
| // _HashStorage conformance |
| // |
| |
| internal typealias Index = _Native${Self}Index<${TypeParameters}> |
| |
| @_versioned |
| internal var startIndex: Index { |
| return Index(nativeStorage: self, offset: -1).successor() |
| } |
| |
| @_versioned |
| internal var endIndex: Index { |
| return Index(nativeStorage: self, offset: capacity) |
| } |
| |
| @_versioned |
| internal func index(after i: Index) -> Index { |
| return i.successor() |
| } |
| |
| internal func formIndex(after i: inout Index) { |
| // FIXME: swift-3-indexing-model: optimize if possible. |
| i = i.successor() |
| } |
| |
| @_versioned |
| @inline(__always) |
| internal func index(forKey key: Key) -> Index? { |
| if count == 0 { |
| // Fast path that avoids computing the hash of the key. |
| return nil |
| } |
| let (i, found) = _find(key, startBucket: _bucket(key)) |
| return found ? i : nil |
| } |
| |
| internal func assertingGet(_ i: Index) -> SequenceElement { |
| _precondition( |
| isInitializedEntry(at: i.offset), |
| "attempting to access ${Self} elements using an invalid Index") |
| let key = self.key(at: i.offset) |
| %if Self == 'Set': |
| return key |
| %elif Self == 'Dictionary': |
| return (key, self.value(at: i.offset)) |
| %end |
| |
| } |
| |
| internal func assertingGet(_ key: Key) -> Value { |
| let (i, found) = _find(key, startBucket: _bucket(key)) |
| _precondition(found, "key not found") |
| %if Self == 'Set': |
| return self.key(at: i.offset) |
| %elif Self == 'Dictionary': |
| return self.value(at: i.offset) |
| %end |
| } |
| |
| @_versioned |
| @inline(__always) |
| internal func maybeGet(_ key: Key) -> Value? { |
| if count == 0 { |
| // Fast path that avoids computing the hash of the key. |
| return nil |
| } |
| |
| let (i, found) = _find(key, startBucket: _bucket(key)) |
| if found { |
| %if Self == 'Set': |
| return self.key(at: i.offset) |
| %elif Self == 'Dictionary': |
| return self.value(at: i.offset) |
| %end |
| } |
| return nil |
| } |
| |
| @discardableResult |
| internal mutating func updateValue(_ value: Value, forKey key: Key) -> Value? { |
| _sanityCheckFailure( |
| "don't call mutating methods on _Native${Self}Storage") |
| } |
| |
| @discardableResult |
| internal mutating func insert( |
| _ value: Value, forKey key: Key |
| ) -> (inserted: Bool, memberAfterInsert: Value) { |
| _sanityCheckFailure( |
| "don't call mutating methods on _Native${Self}Storage") |
| } |
| |
| @discardableResult |
| internal mutating func remove(at index: Index) -> SequenceElement { |
| _sanityCheckFailure( |
| "don't call mutating methods on _Native${Self}Storage") |
| } |
| |
| @discardableResult |
| internal mutating func removeValue(forKey key: Key) -> Value? { |
| _sanityCheckFailure( |
| "don't call mutating methods on _Native${Self}Storage") |
| } |
| |
| internal mutating func removeAll(keepingCapacity keepCapacity: Bool) { |
| _sanityCheckFailure( |
| "don't call mutating methods on _Native${Self}Storage") |
| } |
| |
| internal static func fromArray(_ elements: [SequenceElementWithoutLabels]) |
| -> _Native${Self}Storage<${TypeParameters}> { |
| |
| let requiredCapacity = |
| _Native${Self}Storage<${TypeParameters}>.minimumCapacity( |
| minimumCount: elements.count, |
| maxLoadFactorInverse: _hashContainerDefaultMaxLoadFactorInverse) |
| let nativeStorage = _Native${Self}Storage<${TypeParameters}>( |
| minimumCapacity: requiredCapacity) |
| |
| %if Self == 'Set': |
| |
| var count = 0 |
| for key in elements { |
| let (i, found) = |
| nativeStorage._find(key, startBucket: nativeStorage._bucket(key)) |
| if found { |
| continue |
| } |
| nativeStorage.initializeKey(key, at: i.offset) |
| count += 1 |
| } |
| nativeStorage.count = count |
| |
| %elif Self == 'Dictionary': |
| |
| for (key, value) in elements { |
| let (i, found) = |
| nativeStorage._find(key, startBucket: nativeStorage._bucket(key)) |
| _precondition(!found, "${Self} literal contains duplicate keys") |
| nativeStorage.initializeKey(key, value: value, at: i.offset) |
| } |
| nativeStorage.count = elements.count |
| |
| %end |
| |
| return nativeStorage |
| } |
| } |
| |
| #if _runtime(_ObjC) |
| /// Storage for bridged `${Self}` elements. We could have used |
| /// `${Self}<${AnyTypeParameters}>`, but `AnyObject` cannot be a Key because |
| /// it is not `Hashable`. |
| internal struct _BridgedNative${Self}Storage { |
| internal typealias StorageImpl = |
| _Native${Self}StorageImpl<${AnyTypeParameters}> |
| internal typealias SequenceElement = ${AnySequenceType} |
| |
| internal let buffer: StorageImpl |
| internal let initializedEntries: _UnsafeBitMap |
| internal let keys: UnsafeMutablePointer<AnyObject> |
| %if Self == 'Dictionary': |
| internal let values: UnsafeMutablePointer<AnyObject> |
| %end |
| |
| internal init(buffer: StorageImpl) { |
| self.buffer = buffer |
| initializedEntries = _UnsafeBitMap( |
| storage: buffer._initializedHashtableEntriesBitMapStorage, |
| bitCount: buffer._capacity) |
| keys = buffer._keys |
| %if Self == 'Dictionary': |
| values = buffer._values |
| %end |
| _fixLifetime(buffer) |
| } |
| |
| @_transparent |
| internal var capacity: Int { |
| let result = buffer._capacity |
| _fixLifetime(buffer) |
| return result |
| } |
| |
| @_versioned |
| internal func isInitializedEntry(at i: Int) -> Bool { |
| return initializedEntries[i] |
| } |
| |
| internal func key(at i: Int) -> AnyObject { |
| _precondition(i >= 0 && i < capacity) |
| _sanityCheck(isInitializedEntry(at: i)) |
| |
| let res = (keys + i).pointee |
| _fixLifetime(self) |
| return res |
| } |
| |
| internal func setKey(_ key: AnyObject, at i: Int) { |
| _precondition(i >= 0 && i < capacity) |
| _sanityCheck(isInitializedEntry(at: i)) |
| |
| (keys + i).pointee = key |
| _fixLifetime(self) |
| } |
| |
| %if Self == 'Set': |
| @_transparent |
| internal func initializeKey(_ k: AnyObject, at i: Int) { |
| _sanityCheck(!isInitializedEntry(at: i)) |
| |
| (keys + i).initialize(to: k) |
| initializedEntries[i] = true |
| _fixLifetime(self) |
| } |
| %elif Self == 'Dictionary': |
| @_transparent |
| internal func initializeKey(_ k: AnyObject, value v: AnyObject, at i: Int |
| ) { |
| _sanityCheck(!isInitializedEntry(at: i)) |
| |
| (keys + i).initialize(to: k) |
| (values + i).initialize(to: v) |
| initializedEntries[i] = true |
| _fixLifetime(self) |
| } |
| |
| @_transparent |
| internal func value(at i: Int) -> AnyObject { |
| _sanityCheck(isInitializedEntry(at: i)) |
| let res = (values + i).pointee |
| _fixLifetime(self) |
| return res |
| } |
| %end |
| |
| internal func assertingGet(_ i: Int) -> SequenceElement { |
| _precondition( |
| isInitializedEntry(at: i), |
| "attempting to access ${Self} elements using an invalid Index") |
| let key = self.key(at: i) |
| %if Self == 'Set': |
| return key |
| %elif Self == 'Dictionary': |
| return (key, self.value(at: i)) |
| %end |
| } |
| } |
| |
| final internal class _Native${Self}StorageKeyNSEnumerator< |
| ${TypeParametersDecl} |
| > |
| : _SwiftNativeNSEnumerator, _NSEnumerator { |
| |
| internal typealias NativeStorageOwner = |
| _Native${Self}StorageOwner<${TypeParameters}> |
| internal typealias Index = _Native${Self}Index<${TypeParameters}> |
| |
| internal override required init() { |
| _sanityCheckFailure("don't call this designated initializer") |
| } |
| |
| internal init(_ nativeStorageOwner: NativeStorageOwner) { |
| self.nativeStorageOwner = nativeStorageOwner |
| nextIndex = nativeStorageOwner.nativeStorage.startIndex |
| endIndex = nativeStorageOwner.nativeStorage.endIndex |
| } |
| |
| internal var nativeStorageOwner: NativeStorageOwner |
| internal var nextIndex: Index |
| internal var endIndex: Index |
| |
| // |
| // NSEnumerator implementation. |
| // |
| // Do not call any of these methods from the standard library! |
| // |
| |
| @objc |
| internal func nextObject() -> AnyObject? { |
| if nextIndex == endIndex { |
| return nil |
| } |
| let bridgedKey: AnyObject = nativeStorageOwner._getBridgedKey(nextIndex) |
| nativeStorageOwner.nativeStorage.formIndex(after: &nextIndex) |
| return bridgedKey |
| } |
| |
| @objc(countByEnumeratingWithState:objects:count:) |
| internal func countByEnumerating( |
| with state: UnsafeMutablePointer<_SwiftNSFastEnumerationState>, |
| objects: UnsafeMutablePointer<AnyObject>, |
| count: Int |
| ) -> Int { |
| var theState = state.pointee |
| if theState.state == 0 { |
| theState.state = 1 // Arbitrary non-zero value. |
| theState.itemsPtr = AutoreleasingUnsafeMutablePointer(objects) |
| theState.mutationsPtr = _fastEnumerationStorageMutationsPtr |
| } |
| |
| if nextIndex == endIndex { |
| state.pointee = theState |
| return 0 |
| } |
| |
| // Return only a single element so that code can start iterating via fast |
| // enumeration, terminate it, and continue via NSEnumerator. |
| let bridgedKey: AnyObject = nativeStorageOwner._getBridgedKey(nextIndex) |
| nativeStorageOwner.nativeStorage.formIndex(after: &nextIndex) |
| |
| let unmanagedObjects = _UnmanagedAnyObjectArray(objects) |
| unmanagedObjects[0] = bridgedKey |
| state.pointee = theState |
| return 1 |
| } |
| } |
| #endif |
| |
| /// This class is an artifact of the COW implementation. This class only |
| /// exists to keep separate retain counts separate for: |
| /// - `${Self}` and `NS${Self}`, |
| /// - `${Self}Index`. |
| /// |
| /// This is important because the uniqueness check for COW only cares about |
| /// retain counts of the first kind. |
| /// |
| /// Specifically, `${Self}` points to instances of this class. This class |
| /// is also a proper `NS${Self}` subclass, which is returned to Objective-C |
| /// during bridging. `${Self}Index` points directly to |
| /// `_Native${Self}Storage`. |
| final internal class _Native${Self}StorageOwner<${TypeParametersDecl}> |
| : _SwiftNativeNS${Self}, _NS${Self}Core { |
| |
| internal typealias NativeStorage = _Native${Self}Storage<${TypeParameters}> |
| #if _runtime(_ObjC) |
| internal typealias BridgedNativeStorage = _BridgedNative${Self}Storage |
| #endif |
| |
| %if Self == 'Set': |
| internal typealias Key = Element |
| internal typealias Value = Element |
| %end |
| |
| internal init(minimumCapacity: Int = 2) { |
| nativeStorage = NativeStorage(minimumCapacity: minimumCapacity) |
| super.init() |
| } |
| |
| internal init(nativeStorage: NativeStorage) { |
| self.nativeStorage = nativeStorage |
| super.init() |
| } |
| |
| // This stored property should be stored at offset zero. We perform atomic |
| // operations on it. |
| // |
| // Do not access this property directly. |
| internal var _heapBufferBridged_DoNotUse: AnyObject? = nil |
| |
| internal var nativeStorage: NativeStorage |
| |
| #if _runtime(_ObjC) |
| |
| %if Self == 'Set': |
| |
| // |
| // NSSet implementation. |
| // |
| // Do not call any of these methods from the standard library! Use only |
| // `nativeStorage`. |
| // |
| |
| @objc |
| internal required init(objects: UnsafePointer<AnyObject?>, count: Int) { |
| _sanityCheckFailure("don't call this designated initializer") |
| } |
| |
| @objc |
| internal func member(_ object: AnyObject) -> AnyObject? { |
| return bridgingObjectForKey(object) |
| } |
| |
| @objc |
| internal func objectEnumerator() -> _NSEnumerator { |
| return bridgingKeyEnumerator(()) |
| } |
| |
| @objc(copyWithZone:) |
| internal func copy(with zone: _SwiftNSZone?) -> AnyObject { |
| // Instances of this class should be visible outside of standard library as |
| // having `NSSet` type, which is immutable. |
| return self |
| } |
| |
| %elif Self == 'Dictionary': |
| // |
| // NSDictionary implementation. |
| // |
| // Do not call any of these methods from the standard library! Use only |
| // `nativeStorage`. |
| // |
| |
| @objc |
| internal required init( |
| objects: UnsafePointer<AnyObject?>, |
| forKeys: UnsafeRawPointer, |
| count: Int |
| ) { |
| _sanityCheckFailure("don't call this designated initializer") |
| } |
| |
| @objc(objectForKey:) |
| internal func objectFor(_ aKey: AnyObject) -> AnyObject? { |
| return bridgingObjectForKey(aKey) |
| } |
| |
| @objc |
| internal func keyEnumerator() -> _NSEnumerator { |
| return bridgingKeyEnumerator(()) |
| } |
| |
| @objc(copyWithZone:) |
| internal func copy(with zone: _SwiftNSZone?) -> AnyObject { |
| // Instances of this class should be visible outside of standard library as |
| // having `NSDictionary` type, which is immutable. |
| return self |
| } |
| |
| @objc |
| internal func getObjects( |
| _ objects: UnsafeMutablePointer<AnyObject>?, |
| andKeys keys: UnsafeMutablePointer<AnyObject>? |
| ) { |
| bridgedAllKeysAndValues(objects, keys) |
| } |
| %end |
| |
| /// Returns the pointer to the stored property, which contains bridged |
| /// ${Self} elements. |
| internal var _heapBufferBridgedPtr: UnsafeMutablePointer<AnyObject?> { |
| return _getUnsafePointerToStoredProperties(self).assumingMemoryBound( |
| to: Optional<AnyObject>.self) |
| } |
| |
| /// The storage for bridged ${Self} elements, if present. |
| internal var _bridgedBuffer: |
| BridgedNativeStorage.StorageImpl? { |
| get { |
| if let ref = _stdlib_atomicLoadARCRef(object: _heapBufferBridgedPtr) { |
| return unsafeDowncast(ref, to: BridgedNativeStorage.StorageImpl.self) |
| } |
| return nil |
| } |
| } |
| |
| /// Attach a storage for bridged ${Self} elements. |
| internal func _initializeHeapBufferBridged(_ newBuffer: AnyObject) { |
| _stdlib_atomicInitializeARCRef( |
| object: _heapBufferBridgedPtr, desired: newBuffer) |
| } |
| |
| /// Detach the storage of bridged ${Self} elements. |
| /// |
| /// Call this before mutating the ${Self} storage owned by this owner. |
| internal func deinitializeHeapBufferBridged() { |
| // Perform a non-atomic store because storage should be |
| // uniquely-referenced. |
| _heapBufferBridgedPtr.pointee = nil |
| } |
| |
| /// Returns the bridged ${Self} values. |
| internal var bridgedNativeStorage: BridgedNativeStorage { |
| return BridgedNativeStorage(buffer: _bridgedBuffer!) |
| } |
| |
| internal func _createBridgedNativeStorage(_ capacity: Int) -> |
| BridgedNativeStorage { |
| let buffer = BridgedNativeStorage.StorageImpl.create(capacity: capacity) |
| return BridgedNativeStorage(buffer: buffer) |
| } |
| |
| internal func bridgeEverything() { |
| if _fastPath(_bridgedBuffer != nil) { |
| return |
| } |
| |
| // Create storage for bridged data. |
| let bridged = _createBridgedNativeStorage(nativeStorage.capacity) |
| |
| // Bridge everything. |
| for i in 0..<nativeStorage.capacity { |
| if nativeStorage.isInitializedEntry(at: i) { |
| let key = _bridgeAnythingToObjectiveC(nativeStorage.key(at: i)) |
| %if Self == 'Set': |
| bridged.initializeKey(key, at: i) |
| %elif Self == 'Dictionary': |
| let val = _bridgeAnythingToObjectiveC(nativeStorage.value(at: i)) |
| bridged.initializeKey(key, value: val, at: i) |
| %end |
| } |
| } |
| |
| // Atomically put the bridged elements in place. |
| _initializeHeapBufferBridged(bridged.buffer) |
| } |
| |
| // |
| // Entry points for bridging ${Self} elements. In implementations of |
| // Foundation subclasses (NS${Self}, NSEnumerator), don't access any |
| // storage directly, use these functions. |
| // |
| internal func _getBridgedKey(_ i: _Native${Self}Index<${TypeParameters}>) -> |
| AnyObject { |
| if _fastPath(_isClassOrObjCExistential(Key.self)) { |
| %if Self == 'Set': |
| return _bridgeAnythingToObjectiveC(nativeStorage.assertingGet(i)) |
| %elif Self == 'Dictionary': |
| return _bridgeAnythingToObjectiveC(nativeStorage.assertingGet(i).0) |
| %end |
| } |
| bridgeEverything() |
| %if Self == 'Set': |
| return bridgedNativeStorage.assertingGet(i.offset) |
| %elif Self == 'Dictionary': |
| return bridgedNativeStorage.assertingGet(i.offset).0 |
| %end |
| } |
| |
| %if Self == 'Set': |
| |
| internal func _getBridgedValue(_ i: _Native${Self}Index<${TypeParameters}>) -> |
| AnyObject { |
| if _fastPath(_isClassOrObjCExistential(Value.self)) { |
| return _bridgeAnythingToObjectiveC(nativeStorage.assertingGet(i)) |
| } |
| bridgeEverything() |
| return bridgedNativeStorage.assertingGet(i.offset) |
| } |
| |
| %elif Self == 'Dictionary': |
| |
| internal func _getBridgedValue(_ i: _Native${Self}Index<${TypeParameters}>) |
| -> AnyObject { |
| if _fastPath(_isClassOrObjCExistential(Value.self)) { |
| return _bridgeAnythingToObjectiveC(nativeStorage.assertingGet(i).1) |
| } |
| bridgeEverything() |
| return bridgedNativeStorage.assertingGet(i.offset).1 |
| } |
| |
| internal func bridgedAllKeysAndValues( |
| _ objects: UnsafeMutablePointer<AnyObject>?, |
| _ keys: UnsafeMutablePointer<AnyObject>? |
| ) { |
| bridgeEverything() |
| // The user is expected to provide a buffer of the correct size |
| var i = 0 // Position in the input buffer |
| let capacity = bridgedNativeStorage.capacity |
| |
| if let unmanagedKeys = _UnmanagedAnyObjectArray(keys) { |
| if let unmanagedObjects = _UnmanagedAnyObjectArray(objects) { |
| // keys nonnull, objects nonnull |
| for position in 0..<capacity { |
| if bridgedNativeStorage.isInitializedEntry(at: position) { |
| unmanagedObjects[i] = bridgedNativeStorage.value(at: position) |
| unmanagedKeys[i] = bridgedNativeStorage.key(at: position) |
| i += 1 |
| } |
| } |
| } else { |
| // keys nonnull, objects null |
| for position in 0..<capacity { |
| if bridgedNativeStorage.isInitializedEntry(at: position) { |
| unmanagedKeys[i] = bridgedNativeStorage.key(at: position) |
| i += 1 |
| } |
| } |
| } |
| } else { |
| if let unmanagedObjects = _UnmanagedAnyObjectArray(objects) { |
| // keys null, objects nonnull |
| for position in 0..<capacity { |
| if bridgedNativeStorage.isInitializedEntry(at: position) { |
| unmanagedObjects[i] = bridgedNativeStorage.value(at: position) |
| i += 1 |
| } |
| } |
| } else { |
| // do nothing, both are null |
| } |
| } |
| } |
| |
| %end |
| |
| // |
| // ${Self} -> NS${Self} bridging |
| // |
| |
| @objc |
| internal var count: Int { |
| return nativeStorage.count |
| } |
| |
| internal func bridgingObjectForKey(_ aKey: AnyObject) |
| -> AnyObject? { |
| guard let nativeKey = _conditionallyBridgeFromObjectiveC(aKey, Key.self) |
| else { return nil } |
| |
| let (i, found) = nativeStorage._find( |
| nativeKey, startBucket: nativeStorage._bucket(nativeKey)) |
| if found { |
| return _getBridgedValue(i) |
| } |
| return nil |
| } |
| |
| internal func bridgingKeyEnumerator() -> _NSEnumerator { |
| return _Native${Self}StorageKeyNSEnumerator<${TypeParameters}>(self) |
| } |
| |
| @objc(countByEnumeratingWithState:objects:count:) |
| internal func countByEnumerating( |
| with state: UnsafeMutablePointer<_SwiftNSFastEnumerationState>, |
| objects: UnsafeMutablePointer<AnyObject>?, |
| count: Int |
| ) -> Int { |
| var theState = state.pointee |
| if theState.state == 0 { |
| theState.state = 1 // Arbitrary non-zero value. |
| theState.itemsPtr = AutoreleasingUnsafeMutablePointer(objects) |
| theState.mutationsPtr = _fastEnumerationStorageMutationsPtr |
| theState.extra.0 = CUnsignedLong(nativeStorage.startIndex.offset) |
| } |
| |
| // Test 'objects' rather than 'count' because (a) this is very rare anyway, |
| // and (b) the optimizer should then be able to optimize away the |
| // unwrapping check below. |
| if _slowPath(objects == nil) { |
| return 0 |
| } |
| |
| let unmanagedObjects = _UnmanagedAnyObjectArray(objects!) |
| var currIndex = _Native${Self}Index<${TypeParameters}>( |
| nativeStorage: nativeStorage, offset: Int(theState.extra.0)) |
| let endIndex = nativeStorage.endIndex |
| var stored = 0 |
| for i in 0..<count { |
| if (currIndex == endIndex) { |
| break |
| } |
| |
| let bridgedKey: AnyObject = _getBridgedKey(currIndex) |
| unmanagedObjects[i] = bridgedKey |
| stored += 1 |
| nativeStorage.formIndex(after: &currIndex) |
| } |
| theState.extra.0 = CUnsignedLong(currIndex.offset) |
| state.pointee = theState |
| return stored |
| } |
| #endif |
| } |
| |
| #if _runtime(_ObjC) |
| internal struct _Cocoa${Self}Storage : _HashStorage { |
| internal var cocoa${Self}: _NS${Self} |
| |
| internal typealias Index = _Cocoa${Self}Index |
| internal typealias SequenceElement = ${AnySequenceType} |
| internal typealias SequenceElementWithoutLabels = ${AnySequenceType} |
| |
| internal typealias Key = AnyObject |
| internal typealias Value = AnyObject |
| |
| internal var startIndex: Index { |
| return Index(cocoa${Self}, startIndex: ()) |
| } |
| |
| internal var endIndex: Index { |
| return Index(cocoa${Self}, endIndex: ()) |
| } |
| |
| @_versioned |
| internal func index(after i: Index) -> Index { |
| return i.successor() |
| } |
| |
| internal func formIndex(after i: inout Index) { |
| // FIXME: swift-3-indexing-model: optimize if possible. |
| i = i.successor() |
| } |
| |
| @_versioned |
| internal func index(forKey key: Key) -> Index? { |
| // Fast path that does not involve creating an array of all keys. In case |
| // the key is present, this lookup is a penalty for the slow path, but the |
| // potential savings are significant: we could skip a memory allocation and |
| // a linear search. |
| if maybeGet(key) == nil { |
| return nil |
| } |
| |
| %if Self == 'Set': |
| let allKeys = _stdlib_NSSet_allObjects(cocoaSet) |
| %elif Self == 'Dictionary': |
| let allKeys = _stdlib_NSDictionary_allKeys(cocoaDictionary) |
| %end |
| var keyIndex = -1 |
| for i in 0..<allKeys.value { |
| if _stdlib_NSObject_isEqual(key, allKeys[i]) { |
| keyIndex = i |
| break |
| } |
| } |
| _sanityCheck(keyIndex >= 0, |
| "key was found in fast path, but not found later?") |
| return Index(cocoa${Self}, allKeys, keyIndex) |
| } |
| |
| internal func assertingGet(_ i: Index) -> SequenceElement { |
| %if Self == 'Set': |
| let value: Value? = i.allKeys[i.currentKeyIndex] |
| _sanityCheck(value != nil, "item not found in underlying NS${Self}") |
| return value! |
| %elif Self == 'Dictionary': |
| let key: Key = i.allKeys[i.currentKeyIndex] |
| let value: Value = i.cocoaDictionary.objectFor(key)! |
| return (key, value) |
| %end |
| |
| } |
| |
| internal func assertingGet(_ key: Key) -> Value { |
| %if Self == 'Set': |
| let value: Value? = cocoa${Self}.member(key) |
| _precondition(value != nil, "member not found in underlying NS${Self}") |
| return value! |
| %elif Self == 'Dictionary': |
| let value: Value? = cocoa${Self}.objectFor(key) |
| _precondition(value != nil, "key not found in underlying NS${Self}") |
| return value! |
| %end |
| } |
| |
| @inline(__always) |
| internal func maybeGet(_ key: Key) -> Value? { |
| |
| %if Self == 'Set': |
| return cocoaSet.member(key) |
| %elif Self == 'Dictionary': |
| return cocoaDictionary.objectFor(key) |
| %end |
| |
| } |
| |
| @discardableResult |
| internal mutating func updateValue(_ value: Value, forKey key: Key) -> Value? { |
| _sanityCheckFailure("cannot mutate NS${Self}") |
| } |
| |
| @discardableResult |
| internal mutating func insert( |
| _ value: Value, forKey key: Key |
| ) -> (inserted: Bool, memberAfterInsert: Value) { |
| _sanityCheckFailure("cannot mutate NS${Self}") |
| } |
| |
| @discardableResult |
| internal mutating func remove(at index: Index) -> SequenceElement { |
| _sanityCheckFailure("cannot mutate NS${Self}") |
| } |
| |
| @discardableResult |
| internal mutating func removeValue(forKey key: Key) -> Value? { |
| _sanityCheckFailure("cannot mutate NS${Self}") |
| } |
| |
| internal mutating func removeAll(keepingCapacity keepCapacity: Bool) { |
| _sanityCheckFailure("cannot mutate NS${Self}") |
| } |
| |
| internal var count: Int { |
| return cocoa${Self}.count |
| } |
| |
| internal static func fromArray(_ elements: [SequenceElementWithoutLabels]) |
| -> _Cocoa${Self}Storage { |
| |
| _sanityCheckFailure("this function should never be called") |
| } |
| } |
| #else |
| internal struct _Cocoa${Self}Storage {} |
| #endif |
| |
| internal enum _Variant${Self}Storage<${TypeParametersDecl}> : _HashStorage { |
| |
| internal typealias NativeStorage = _Native${Self}Storage<${TypeParameters}> |
| internal typealias NativeStorageOwner = |
| _Native${Self}StorageOwner<${TypeParameters}> |
| internal typealias NativeIndex = _Native${Self}Index<${TypeParameters}> |
| internal typealias CocoaStorage = _Cocoa${Self}Storage |
| internal typealias SequenceElement = ${Sequence} |
| internal typealias SequenceElementWithoutLabels = ${Sequence} |
| internal typealias SelfType = _Variant${Self}Storage |
| |
| %if Self == 'Set': |
| internal typealias Key = ${TypeParameters} |
| internal typealias Value = ${TypeParameters} |
| %end |
| |
| case native(NativeStorageOwner) |
| case cocoa(CocoaStorage) |
| |
| @_versioned |
| @_transparent |
| internal var guaranteedNative: Bool { |
| return _canBeClass(Key.self) == 0 || _canBeClass(Value.self) == 0 |
| } |
| |
| internal mutating func isUniquelyReferenced() -> Bool { |
| if _fastPath(guaranteedNative) { |
| return _isUnique_native(&self) |
| } |
| |
| switch self { |
| case .native: |
| return _isUnique_native(&self) |
| case .cocoa: |
| // Don't consider Cocoa storage mutable, even if it is mutable and is |
| // uniquely referenced. |
| return false |
| } |
| } |
| |
| @_versioned |
| internal var asNative: NativeStorage { |
| switch self { |
| case .native(let owner): |
| return owner.nativeStorage |
| case .cocoa: |
| _sanityCheckFailure("internal error: not backed by native storage") |
| } |
| } |
| |
| #if _runtime(_ObjC) |
| internal var asCocoa: CocoaStorage { |
| switch self { |
| case .native: |
| _sanityCheckFailure("internal error: not backed by NS${Self}") |
| case .cocoa(let cocoaStorage): |
| return cocoaStorage |
| } |
| } |
| #endif |
| |
| /// Ensure this we hold a unique reference to a native storage |
| /// having at least `minimumCapacity` elements. |
| internal mutating func ensureUniqueNativeStorage(_ minimumCapacity: Int) |
| -> (reallocated: Bool, capacityChanged: Bool) { |
| switch self { |
| case .native: |
| let oldCapacity = asNative.capacity |
| if isUniquelyReferenced() && oldCapacity >= minimumCapacity { |
| #if _runtime(_ObjC) |
| // Clear the cache of bridged elements. |
| switch self { |
| case .native(let owner): |
| owner.deinitializeHeapBufferBridged() |
| case .cocoa: |
| _sanityCheckFailure("internal error: not backed by native storage") |
| } |
| #endif |
| return (reallocated: false, capacityChanged: false) |
| } |
| |
| let oldNativeStorage = asNative |
| let newNativeOwner = NativeStorageOwner(minimumCapacity: minimumCapacity) |
| var newNativeStorage = newNativeOwner.nativeStorage |
| let newCapacity = newNativeStorage.capacity |
| for i in 0..<oldCapacity { |
| if oldNativeStorage.isInitializedEntry(at: i) { |
| if oldCapacity == newCapacity { |
| let key = oldNativeStorage.key(at: i) |
| %if Self == 'Set': |
| newNativeStorage.initializeKey(key, at: i) |
| %elif Self == 'Dictionary': |
| let value = oldNativeStorage.value(at: i) |
| newNativeStorage.initializeKey(key, value: value , at: i) |
| %end |
| } else { |
| let key = oldNativeStorage.key(at: i) |
| %if Self == 'Set': |
| newNativeStorage.unsafeAddNew(key: key) |
| %elif Self == 'Dictionary': |
| newNativeStorage.unsafeAddNew( |
| key: key, |
| value: oldNativeStorage.value(at: i)) |
| %end |
| } |
| } |
| } |
| newNativeStorage.count = oldNativeStorage.count |
| |
| self = .native(newNativeOwner) |
| return (reallocated: true, |
| capacityChanged: oldCapacity != newNativeStorage.capacity) |
| |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| let cocoa${Self} = cocoaStorage.cocoa${Self} |
| let newNativeOwner = NativeStorageOwner(minimumCapacity: minimumCapacity) |
| var newNativeStorage = newNativeOwner.nativeStorage |
| let oldCocoaIterator = _Cocoa${Self}Iterator(cocoa${Self}) |
| %if Self == 'Set': |
| while let key = oldCocoaIterator.next() { |
| newNativeStorage.unsafeAddNew( |
| key: _forceBridgeFromObjectiveC(key, Value.self)) |
| } |
| |
| %elif Self == 'Dictionary': |
| |
| while let (key, value) = oldCocoaIterator.next() { |
| newNativeStorage.unsafeAddNew( |
| key: _forceBridgeFromObjectiveC(key, Key.self), |
| value: _forceBridgeFromObjectiveC(value, Value.self)) |
| } |
| |
| %end |
| newNativeStorage.count = cocoa${Self}.count |
| |
| self = .native(newNativeOwner) |
| return (reallocated: true, capacityChanged: true) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| #if _runtime(_ObjC) |
| @inline(never) |
| internal mutating func migrateDataToNativeStorage( |
| _ cocoaStorage: _Cocoa${Self}Storage |
| ) { |
| let minCapacity = NativeStorage.minimumCapacity( |
| minimumCount: cocoaStorage.count, |
| maxLoadFactorInverse: _hashContainerDefaultMaxLoadFactorInverse) |
| let allocated = ensureUniqueNativeStorage(minCapacity).reallocated |
| _sanityCheck(allocated, "failed to allocate native ${Self} storage") |
| } |
| #endif |
| |
| // |
| // _HashStorage conformance |
| // |
| |
| internal typealias Index = ${Self}Index<${TypeParameters}> |
| |
| internal var startIndex: Index { |
| if _fastPath(guaranteedNative) { |
| return ._native(asNative.startIndex) |
| } |
| |
| switch self { |
| case .native: |
| return ._native(asNative.startIndex) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| return ._cocoa(cocoaStorage.startIndex) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| internal var endIndex: Index { |
| if _fastPath(guaranteedNative) { |
| return ._native(asNative.endIndex) |
| } |
| |
| switch self { |
| case .native: |
| return ._native(asNative.endIndex) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| return ._cocoa(cocoaStorage.endIndex) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| @_versioned |
| func index(after i: Index) -> Index { |
| if _fastPath(guaranteedNative) { |
| return ._native(asNative.index(after: i._nativeIndex)) |
| } |
| |
| switch self { |
| case .native: |
| return ._native(asNative.index(after: i._nativeIndex)) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| return ._cocoa(cocoaStorage.index(after: i._cocoaIndex)) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| internal func formIndex(after i: inout Index) { |
| // FIXME: swift-3-indexing-model: optimize if possible. |
| i = index(after: i) |
| } |
| |
| @_versioned |
| @inline(__always) |
| internal func index(forKey key: Key) -> Index? { |
| if _fastPath(guaranteedNative) { |
| if let nativeIndex = asNative.index(forKey: key) { |
| return ._native(nativeIndex) |
| } |
| return nil |
| } |
| |
| switch self { |
| case .native: |
| if let nativeIndex = asNative.index(forKey: key) { |
| return ._native(nativeIndex) |
| } |
| return nil |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| let anyObjectKey: AnyObject = _bridgeAnythingToObjectiveC(key) |
| if let cocoaIndex = cocoaStorage.index(forKey: anyObjectKey) { |
| return ._cocoa(cocoaIndex) |
| } |
| return nil |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| internal func assertingGet(_ i: Index) -> SequenceElement { |
| if _fastPath(guaranteedNative) { |
| return asNative.assertingGet(i._nativeIndex) |
| } |
| |
| switch self { |
| case .native: |
| return asNative.assertingGet(i._nativeIndex) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| %if Self == 'Set': |
| let anyObjectValue: AnyObject = cocoaStorage.assertingGet(i._cocoaIndex) |
| let nativeValue = _forceBridgeFromObjectiveC(anyObjectValue, Value.self) |
| return nativeValue |
| %elif Self == 'Dictionary': |
| let (anyObjectKey, anyObjectValue) = |
| cocoaStorage.assertingGet(i._cocoaIndex) |
| let nativeKey = _forceBridgeFromObjectiveC(anyObjectKey, Key.self) |
| let nativeValue = _forceBridgeFromObjectiveC(anyObjectValue, Value.self) |
| return (nativeKey, nativeValue) |
| %end |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| internal func assertingGet(_ key: Key) -> Value { |
| if _fastPath(guaranteedNative) { |
| return asNative.assertingGet(key) |
| } |
| |
| switch self { |
| case .native: |
| return asNative.assertingGet(key) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| // FIXME: This assumes that Key and Value are bridged verbatim. |
| let anyObjectKey: AnyObject = _bridgeAnythingToObjectiveC(key) |
| let anyObjectValue: AnyObject = cocoaStorage.assertingGet(anyObjectKey) |
| return _forceBridgeFromObjectiveC(anyObjectValue, Value.self) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| #if _runtime(_ObjC) |
| @_versioned |
| @inline(never) |
| internal static func maybeGetFromCocoaStorage( |
| _ cocoaStorage : CocoaStorage, forKey key: Key |
| ) -> Value? { |
| let anyObjectKey: AnyObject = _bridgeAnythingToObjectiveC(key) |
| if let anyObjectValue = cocoaStorage.maybeGet(anyObjectKey) { |
| return _forceBridgeFromObjectiveC(anyObjectValue, Value.self) |
| } |
| return nil |
| } |
| #endif |
| |
| @_versioned |
| @inline(__always) |
| internal func maybeGet(_ key: Key) -> Value? { |
| if _fastPath(guaranteedNative) { |
| return asNative.maybeGet(key) |
| } |
| |
| switch self { |
| case .native: |
| return asNative.maybeGet(key) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| return SelfType.maybeGetFromCocoaStorage(cocoaStorage, forKey: key) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| internal mutating func nativeUpdateValue( |
| _ value: Value, forKey key: Key |
| ) -> Value? { |
| var (i, found) = asNative._find(key, startBucket: asNative._bucket(key)) |
| |
| let minCapacity = found |
| ? asNative.capacity |
| : NativeStorage.minimumCapacity( |
| minimumCount: asNative.count + 1, |
| maxLoadFactorInverse: asNative.maxLoadFactorInverse) |
| |
| let (_, capacityChanged) = ensureUniqueNativeStorage(minCapacity) |
| if capacityChanged { |
| i = asNative._find(key, startBucket: asNative._bucket(key)).pos |
| } |
| |
| %if Self == 'Set': |
| let oldValue: Value? = found ? asNative.key(at: i.offset) : nil |
| if found { |
| asNative.setKey(key, at: i.offset) |
| } else { |
| asNative.initializeKey(key, at: i.offset) |
| asNative.count += 1 |
| } |
| %elif Self == 'Dictionary': |
| let oldValue: Value? = found ? asNative.value(at: i.offset) : nil |
| if found { |
| asNative.setKey(key, value: value, at: i.offset) |
| } else { |
| asNative.initializeKey(key, value: value, at: i.offset) |
| asNative.count += 1 |
| } |
| %end |
| |
| return oldValue |
| } |
| |
| @discardableResult |
| internal mutating func updateValue( |
| _ value: Value, forKey key: Key |
| ) -> Value? { |
| |
| if _fastPath(guaranteedNative) { |
| return nativeUpdateValue(value, forKey: key) |
| } |
| |
| switch self { |
| case .native: |
| return nativeUpdateValue(value, forKey: key) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| migrateDataToNativeStorage(cocoaStorage) |
| return nativeUpdateValue(value, forKey: key) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| internal mutating func nativeInsert( |
| _ value: Value, forKey key: Key |
| ) -> (inserted: Bool, memberAfterInsert: Value) { |
| var (i, found) = asNative._find(key, startBucket: asNative._bucket(key)) |
| |
| if found { |
| %if Self == 'Set': |
| return (inserted: false, memberAfterInsert: asNative.key(at: i.offset)) |
| %elif Self == 'Dictionary': |
| return (inserted: false, memberAfterInsert: asNative.value(at: i.offset)) |
| %end |
| } |
| |
| let minCapacity = NativeStorage.minimumCapacity( |
| minimumCount: asNative.count + 1, |
| maxLoadFactorInverse: asNative.maxLoadFactorInverse) |
| |
| let (_, capacityChanged) = ensureUniqueNativeStorage(minCapacity) |
| if capacityChanged { |
| i = asNative._find(key, startBucket: asNative._bucket(key)).pos |
| } |
| |
| %if Self == 'Set': |
| asNative.initializeKey(key, at: i.offset) |
| asNative.count += 1 |
| %elif Self == 'Dictionary': |
| asNative.initializeKey(key, value: value, at: i.offset) |
| asNative.count += 1 |
| %end |
| |
| return (inserted: true, memberAfterInsert: value) |
| } |
| |
| @discardableResult |
| internal mutating func insert( |
| _ value: Value, forKey key: Key |
| ) -> (inserted: Bool, memberAfterInsert: Value) { |
| |
| if _fastPath(guaranteedNative) { |
| return nativeInsert(value, forKey: key) |
| } |
| |
| switch self { |
| case .native: |
| return nativeInsert(value, forKey: key) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| migrateDataToNativeStorage(cocoaStorage) |
| return nativeInsert(value, forKey: key) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| /// - parameter idealBucket: The ideal bucket for the element being deleted. |
| /// - parameter offset: The offset of the element that will be deleted. |
| /// Precondition: there should be an initialized entry at offset. |
| internal mutating func nativeDeleteImpl( |
| _ nativeStorage: NativeStorage, idealBucket: Int, offset: Int |
| ) { |
| _sanityCheck( |
| nativeStorage.isInitializedEntry(at: offset), "expected initialized entry") |
| |
| // remove the element |
| nativeStorage.destroyEntry(at: offset) |
| nativeStorage.count -= 1 |
| |
| // If we've put a hole in a chain of contiguous elements, some |
| // element after the hole may belong where the new hole is. |
| var hole = offset |
| |
| // Find the first bucket in the contiguous chain |
| var start = idealBucket |
| while nativeStorage.isInitializedEntry(at: nativeStorage._prev(start)) { |
| start = nativeStorage._prev(start) |
| } |
| |
| // Find the last bucket in the contiguous chain |
| var lastInChain = hole |
| var b = nativeStorage._index(after: lastInChain) |
| while nativeStorage.isInitializedEntry(at: b) { |
| lastInChain = b |
| b = nativeStorage._index(after: b) |
| } |
| |
| // Relocate out-of-place elements in the chain, repeating until |
| // none are found. |
| while hole != lastInChain { |
| // Walk backwards from the end of the chain looking for |
| // something out-of-place. |
| var b = lastInChain |
| while b != hole { |
| let idealBucket = nativeStorage._bucket(nativeStorage.key(at: b)) |
| |
| // Does this element belong between start and hole? We need |
| // two separate tests depending on whether [start, hole] wraps |
| // around the end of the buffer |
| let c0 = idealBucket >= start |
| let c1 = idealBucket <= hole |
| if start <= hole ? (c0 && c1) : (c0 || c1) { |
| break // Found it |
| } |
| b = nativeStorage._prev(b) |
| } |
| |
| if b == hole { // No out-of-place elements found; we're done adjusting |
| break |
| } |
| |
| // Move the found element into the hole |
| nativeStorage.moveInitializeEntry( |
| from: nativeStorage, |
| at: b, |
| toEntryAt: hole) |
| hole = b |
| } |
| } |
| |
| internal mutating func nativeRemoveObject(forKey key: Key) -> Value? { |
| var nativeStorage = asNative |
| var idealBucket = nativeStorage._bucket(key) |
| var (index, found) = nativeStorage._find(key, startBucket: idealBucket) |
| |
| // Fast path: if the key is not present, we will not mutate the set, |
| // so don't force unique storage. |
| if !found { |
| return nil |
| } |
| |
| let (reallocated, capacityChanged) = |
| ensureUniqueNativeStorage(nativeStorage.capacity) |
| if reallocated { |
| nativeStorage = asNative |
| } |
| if capacityChanged { |
| idealBucket = nativeStorage._bucket(key) |
| (index, found) = nativeStorage._find(key, startBucket: idealBucket) |
| _sanityCheck(found, "key was lost during storage migration") |
| } |
| %if Self == 'Set': |
| let oldValue = nativeStorage.key(at: index.offset) |
| %elif Self == 'Dictionary': |
| let oldValue = nativeStorage.value(at: index.offset) |
| %end |
| nativeDeleteImpl(nativeStorage, idealBucket: idealBucket, |
| offset: index.offset) |
| return oldValue |
| } |
| |
| internal mutating func nativeRemove( |
| at nativeIndex: NativeIndex |
| ) -> SequenceElement { |
| var nativeStorage = asNative |
| |
| // The provided index should be valid, so we will always mutating the |
| // set storage. Request unique storage. |
| let (reallocated, _) = ensureUniqueNativeStorage(nativeStorage.capacity) |
| if reallocated { |
| nativeStorage = asNative |
| } |
| |
| let result = nativeStorage.assertingGet(nativeIndex) |
| %if Self == 'Set': |
| let key = result |
| %elif Self == 'Dictionary': |
| let key = result.0 |
| %end |
| |
| nativeDeleteImpl(nativeStorage, idealBucket: nativeStorage._bucket(key), |
| offset: nativeIndex.offset) |
| return result |
| } |
| |
| @discardableResult |
| internal mutating func remove(at index: Index) -> SequenceElement { |
| if _fastPath(guaranteedNative) { |
| return nativeRemove(at: index._nativeIndex) |
| } |
| |
| switch self { |
| case .native: |
| return nativeRemove(at: index._nativeIndex) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| // We have to migrate the data first. But after we do so, the Cocoa |
| // index becomes useless, so get the key first. |
| // |
| // FIXME(performance): fuse data migration and element deletion into one |
| // operation. |
| let cocoaIndex = index._cocoaIndex |
| let anyObjectKey: AnyObject = |
| cocoaIndex.allKeys[cocoaIndex.currentKeyIndex] |
| migrateDataToNativeStorage(cocoaStorage) |
| let key = _forceBridgeFromObjectiveC(anyObjectKey, Key.self) |
| let value = nativeRemoveObject(forKey: key) |
| |
| %if Self == 'Set': |
| _sanityCheck(key == value, "bridging did not preserve equality") |
| return key |
| %elif Self == 'Dictionary': |
| return (key, value._unsafelyUnwrappedUnchecked) |
| %end |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| @discardableResult |
| internal mutating func removeValue(forKey key: Key) -> Value? { |
| if _fastPath(guaranteedNative) { |
| return nativeRemoveObject(forKey: key) |
| } |
| |
| switch self { |
| case .native: |
| return nativeRemoveObject(forKey: key) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| let anyObjectKey: AnyObject = _bridgeAnythingToObjectiveC(key) |
| if cocoaStorage.maybeGet(anyObjectKey) == nil { |
| return nil |
| } |
| migrateDataToNativeStorage(cocoaStorage) |
| return nativeRemoveObject(forKey: key) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| internal mutating func nativeRemoveAll() { |
| var nativeStorage = asNative |
| |
| // FIXME(performance): if the storage is non-uniquely referenced, we |
| // shouldn't be copying the elements into new storage and then immediately |
| // deleting the elements. We should detect that the storage is not uniquely |
| // referenced and allocate new empty storage of appropriate capacity. |
| |
| // We have already checked for the empty dictionary case, so we will always |
| // mutating the dictionary storage. Request unique storage. |
| let (reallocated, _) = ensureUniqueNativeStorage(nativeStorage.capacity) |
| if reallocated { |
| nativeStorage = asNative |
| } |
| |
| for b in 0..<nativeStorage.capacity { |
| if nativeStorage.isInitializedEntry(at: b) { |
| nativeStorage.destroyEntry(at: b) |
| } |
| } |
| nativeStorage.count = 0 |
| } |
| |
| internal mutating func removeAll(keepingCapacity keepCapacity: Bool) { |
| if count == 0 { |
| return |
| } |
| |
| if !keepCapacity { |
| self = .native(NativeStorage.Owner(minimumCapacity: 2)) |
| return |
| } |
| |
| if _fastPath(guaranteedNative) { |
| nativeRemoveAll() |
| return |
| } |
| |
| switch self { |
| case .native: |
| nativeRemoveAll() |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| self = .native(NativeStorage.Owner(minimumCapacity: cocoaStorage.count)) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| internal var count: Int { |
| if _fastPath(guaranteedNative) { |
| return asNative.count |
| } |
| |
| switch self { |
| case .native: |
| return asNative.count |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| return cocoaStorage.count |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| /// Returns an iterator over the `(Key, Value)` pairs. |
| /// |
| /// - Complexity: O(1). |
| @_versioned |
| @inline(__always) |
| internal func makeIterator() -> ${Self}Iterator<${TypeParameters}> { |
| switch self { |
| case .native(let owner): |
| return ._native( |
| start: asNative.startIndex, end: asNative.endIndex, owner: owner) |
| case .cocoa(let cocoaStorage): |
| #if _runtime(_ObjC) |
| return ._cocoa(_Cocoa${Self}Iterator(cocoaStorage.cocoa${Self})) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| |
| internal static func fromArray(_ elements: [SequenceElement]) |
| -> _Variant${Self}Storage<${TypeParameters}> { |
| |
| _sanityCheckFailure("this function should never be called") |
| } |
| } |
| |
| internal struct _Native${Self}Index<${TypeParametersDecl}> : |
| Comparable { |
| |
| internal typealias NativeStorage = _Native${Self}Storage<${TypeParameters}> |
| internal typealias NativeIndex = _Native${Self}Index<${TypeParameters}> |
| |
| // FIXME: swift-3-indexing-model: remove `nativeStorage`, we don't need it in |
| // the new model. |
| @_versioned |
| internal var nativeStorage: NativeStorage |
| internal var offset: Int |
| |
| @_versioned |
| internal init(nativeStorage: NativeStorage, offset: Int) { |
| self.nativeStorage = nativeStorage |
| self.offset = offset |
| } |
| |
| /// Returns the next consecutive value after `self`. |
| /// |
| /// - Precondition: The next value is representable. |
| internal func successor() -> NativeIndex { |
| // FIXME: swift-3-indexing-model: remove this method. |
| var i = offset + 1 |
| // FIXME: Can't write the simple code pending |
| // <rdar://problem/15484639> Refcounting bug |
| while i < nativeStorage.capacity /*&& !nativeStorage[i]*/ { |
| // FIXME: workaround for <rdar://problem/15484639> |
| if nativeStorage.isInitializedEntry(at: i) { |
| break |
| } |
| // end workaround |
| i += 1 |
| } |
| return NativeIndex(nativeStorage: nativeStorage, offset: i) |
| } |
| } |
| |
| extension _Native${Self}Index { |
| internal static func == ( |
| lhs: _Native${Self}Index<${TypeParameters}>, |
| rhs: _Native${Self}Index<${TypeParameters}> |
| ) -> Bool { |
| // FIXME: assert that lhs and rhs are from the same dictionary. |
| return lhs.offset == rhs.offset |
| } |
| |
| internal static func < ( |
| lhs: _Native${Self}Index<${TypeParameters}>, |
| rhs: _Native${Self}Index<${TypeParameters}> |
| ) -> Bool { |
| // FIXME: assert that lhs and rhs are from the same dictionary. |
| return lhs.offset < rhs.offset |
| } |
| // TODO: swift-3-indexing-model: forward all Comparable operations. |
| } |
| |
| #if _runtime(_ObjC) |
| @_versioned |
| internal struct _Cocoa${Self}Index : Comparable { |
| // Assumption: we rely on NSDictionary.getObjects when being |
| // repeatedly called on the same NSDictionary, returning items in the same |
| // order every time. |
| // Similarly, the same assumption holds for NSSet.allObjects. |
| |
| /// A reference to the NS${Self}, which owns members in `allObjects`, |
| /// or `allKeys`, for NSSet and NSDictionary respectively. |
| internal let cocoa${Self}: _NS${Self} |
| // FIXME: swift-3-indexing-model: try to remove the cocoa reference, but make |
| // sure that we have a safety check for accessing `allKeys`. Maybe move both |
| // into the dictionary/set itself. |
| |
| /// An unowned array of keys. |
| internal var allKeys: _HeapBuffer<Int, AnyObject> |
| |
| /// Index into `allKeys` |
| internal var currentKeyIndex: Int |
| |
| internal init(_ cocoa${Self}: _NS${Self}, startIndex: ()) { |
| self.cocoa${Self} = cocoa${Self} |
| %if Self == 'Set': |
| self.allKeys = _stdlib_NSSet_allObjects(cocoaSet) |
| %elif Self == 'Dictionary': |
| self.allKeys = _stdlib_NSDictionary_allKeys(cocoaDictionary) |
| %end |
| self.currentKeyIndex = 0 |
| } |
| |
| internal init(_ cocoa${Self}: _NS${Self}, endIndex: ()) { |
| self.cocoa${Self} = cocoa${Self} |
| %if Self == 'Set': |
| self.allKeys = _stdlib_NS${Self}_allObjects(cocoa${Self}) |
| %elif Self == 'Dictionary': |
| self.allKeys = _stdlib_NS${Self}_allKeys(cocoa${Self}) |
| %end |
| self.currentKeyIndex = allKeys.value |
| } |
| |
| internal init(_ cocoa${Self}: _NS${Self}, |
| _ allKeys: _HeapBuffer<Int, AnyObject>, |
| _ currentKeyIndex: Int |
| ) { |
| self.cocoa${Self} = cocoa${Self} |
| self.allKeys = allKeys |
| self.currentKeyIndex = currentKeyIndex |
| } |
| |
| /// Returns the next consecutive value after `self`. |
| /// |
| /// - Precondition: The next value is representable. |
| internal func successor() -> _Cocoa${Self}Index { |
| // FIXME: swift-3-indexing-model: remove this method. |
| _precondition( |
| currentKeyIndex < allKeys.value, "cannot increment endIndex") |
| return _Cocoa${Self}Index(cocoa${Self}, allKeys, currentKeyIndex + 1) |
| } |
| } |
| |
| extension _Cocoa${Self}Index { |
| internal static func == ( |
| lhs: _Cocoa${Self}Index, |
| rhs: _Cocoa${Self}Index |
| ) -> Bool { |
| _precondition(lhs.cocoa${Self} === rhs.cocoa${Self}, |
| "cannot compare indexes pointing to different ${Self}s") |
| _precondition(lhs.allKeys.value == rhs.allKeys.value, |
| "one or both of the indexes have been invalidated") |
| |
| return lhs.currentKeyIndex == rhs.currentKeyIndex |
| } |
| |
| internal static func < ( |
| lhs: _Cocoa${Self}Index, |
| rhs: _Cocoa${Self}Index |
| ) -> Bool { |
| _precondition(lhs.cocoa${Self} === rhs.cocoa${Self}, |
| "cannot compare indexes pointing to different ${Self}s") |
| _precondition(lhs.allKeys.value == rhs.allKeys.value, |
| "one or both of the indexes have been invalidated") |
| |
| return lhs.currentKeyIndex < rhs.currentKeyIndex |
| } |
| } |
| #else |
| internal struct _Cocoa${Self}Index {} |
| #endif |
| |
| internal enum ${Self}IndexRepresentation<${TypeParametersDecl}> { |
| typealias _Index = ${Self}Index<${TypeParameters}> |
| typealias _NativeIndex = _Index._NativeIndex |
| typealias _CocoaIndex = _Index._CocoaIndex |
| |
| case _native(_NativeIndex) |
| case _cocoa(_CocoaIndex) |
| } |
| |
| %{ |
| if Self == 'Set': |
| SubscriptingWithIndexDoc = """\ |
| /// Used to access the members in an instance of `Set<Element>`.""" |
| elif Self == 'Dictionary': |
| SubscriptingWithIndexDoc = """\ |
| /// Used to access the key-value pairs in an instance of |
| /// `Dictionary<Key, Value>`. |
| /// |
| /// Dictionary has two subscripting interfaces: |
| /// |
| /// 1. Subscripting with a key, yielding an optional value: |
| /// |
| /// v = d[k]! |
| /// |
| /// 2. Subscripting with an index, yielding a key-value pair: |
| /// |
| /// (k, v) = d[i]""" |
| }% |
| |
| ${SubscriptingWithIndexDoc} |
| public struct ${Self}Index<${TypeParametersDecl}> : |
| Comparable { |
| // FIXME(ABI)(compiler limitation): `DictionaryIndex` and `SetIndex` should |
| // be nested types. |
| |
| // Index for native storage is efficient. Index for bridged NS${Self} is |
| // not, because neither NSEnumerator nor fast enumeration support moving |
| // backwards. Even if they did, there is another issue: NSEnumerator does |
| // not support NSCopying, and fast enumeration does not document that it is |
| // safe to copy the state. So, we cannot implement Index that is a value |
| // type for bridged NS${Self} in terms of Cocoa enumeration facilities. |
| |
| internal typealias _NativeIndex = _Native${Self}Index<${TypeParameters}> |
| internal typealias _CocoaIndex = _Cocoa${Self}Index |
| |
| %if Self == 'Set': |
| internal typealias Key = ${TypeParameters} |
| internal typealias Value = ${TypeParameters} |
| %end |
| |
| internal var _value: ${Self}IndexRepresentation<${TypeParameters}> |
| |
| @_versioned |
| internal static func _native(_ index: _NativeIndex) -> ${Self}Index { |
| return ${Self}Index(_value: ._native(index)) |
| } |
| #if _runtime(_ObjC) |
| @_versioned |
| internal static func _cocoa(_ index: _CocoaIndex) -> ${Self}Index { |
| return ${Self}Index(_value: ._cocoa(index)) |
| } |
| #endif |
| |
| @_versioned |
| @_transparent |
| internal var _guaranteedNative: Bool { |
| return _canBeClass(Key.self) == 0 && _canBeClass(Value.self) == 0 |
| } |
| |
| @_transparent |
| internal var _nativeIndex: _NativeIndex { |
| switch _value { |
| case ._native(let nativeIndex): |
| return nativeIndex |
| case ._cocoa: |
| _sanityCheckFailure("internal error: does not contain a native index") |
| } |
| } |
| |
| #if _runtime(_ObjC) |
| @_transparent |
| internal var _cocoaIndex: _CocoaIndex { |
| switch _value { |
| case ._native: |
| _sanityCheckFailure("internal error: does not contain a Cocoa index") |
| case ._cocoa(let cocoaIndex): |
| return cocoaIndex |
| } |
| } |
| #endif |
| |
| /// Returns the next consecutive value after `self`. |
| /// |
| /// - Precondition: The next value is representable. |
| internal func successor() -> ${Self}Index<${TypeParameters}> { |
| if _fastPath(_guaranteedNative) { |
| return ._native(_nativeIndex.successor()) |
| } |
| |
| switch _value { |
| case ._native(let nativeIndex): |
| return ._native(nativeIndex.successor()) |
| case ._cocoa(let cocoaIndex): |
| #if _runtime(_ObjC) |
| return ._cocoa(cocoaIndex.successor()) |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| } |
| |
| extension ${Self}Index { |
| public static func == ( |
| lhs: ${Self}Index<${TypeParameters}>, |
| rhs: ${Self}Index<${TypeParameters}> |
| ) -> Bool { |
| if _fastPath(lhs._guaranteedNative) { |
| return lhs._nativeIndex == rhs._nativeIndex |
| } |
| |
| switch (lhs._value, rhs._value) { |
| case (._native(let lhsNative), ._native(let rhsNative)): |
| return lhsNative == rhsNative |
| case (._cocoa(let lhsCocoa), ._cocoa(let rhsCocoa)): |
| #if _runtime(_ObjC) |
| return lhsCocoa == rhsCocoa |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| default: |
| _preconditionFailure("comparing indexes from different sets") |
| } |
| } |
| |
| public static func < ( |
| lhs: ${Self}Index<${TypeParameters}>, |
| rhs: ${Self}Index<${TypeParameters}> |
| ) -> Bool { |
| if _fastPath(lhs._guaranteedNative) { |
| return lhs._nativeIndex < rhs._nativeIndex |
| } |
| |
| switch (lhs._value, rhs._value) { |
| case (._native(let lhsNative), ._native(let rhsNative)): |
| return lhsNative < rhsNative |
| case (._cocoa(let lhsCocoa), ._cocoa(let rhsCocoa)): |
| #if _runtime(_ObjC) |
| return lhsCocoa < rhsCocoa |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| default: |
| _preconditionFailure("comparing indexes from different sets") |
| } |
| } |
| } |
| |
| #if _runtime(_ObjC) |
| @_versioned |
| final internal class _Cocoa${Self}Iterator : IteratorProtocol { |
| internal typealias Element = ${AnySequenceType} |
| |
| // Cocoa ${Self} iterator has to be a class, otherwise we cannot |
| // guarantee that the fast enumeration struct is pinned to a certain memory |
| // location. |
| |
| // This stored property should be stored at offset zero. There's code below |
| // relying on this. |
| internal var _fastEnumerationState: _SwiftNSFastEnumerationState = |
| _makeSwiftNSFastEnumerationState() |
| |
| // This stored property should be stored right after `_fastEnumerationState`. |
| // There's code below relying on this. |
| internal var _fastEnumerationStackBuf = _CocoaFastEnumerationStackBuf() |
| |
| internal let cocoa${Self}: _NS${Self} |
| |
| internal var _fastEnumerationStatePtr: |
| UnsafeMutablePointer<_SwiftNSFastEnumerationState> { |
| return _getUnsafePointerToStoredProperties(self).assumingMemoryBound( |
| to: _SwiftNSFastEnumerationState.self) |
| } |
| |
| internal var _fastEnumerationStackBufPtr: |
| UnsafeMutablePointer<_CocoaFastEnumerationStackBuf> { |
| return UnsafeMutableRawPointer(_fastEnumerationStatePtr + 1) |
| .assumingMemoryBound(to: _CocoaFastEnumerationStackBuf.self) |
| } |
| |
| // These members have to be word-sized integers, they cannot be limited to |
| // Int8 just because our buffer holds 16 elements: fast enumeration is |
| // allowed to return inner pointers to the container, which can be much |
| // larger. |
| internal var itemIndex: Int = 0 |
| internal var itemCount: Int = 0 |
| |
| @_versioned |
| internal init(_ cocoa${Self}: _NS${Self}) { |
| self.cocoa${Self} = cocoa${Self} |
| } |
| |
| @_versioned |
| internal func next() -> Element? { |
| if itemIndex < 0 { |
| return nil |
| } |
| let cocoa${Self} = self.cocoa${Self} |
| if itemIndex == itemCount { |
| let stackBufCount = _fastEnumerationStackBuf.count |
| // We can't use `withUnsafeMutablePointer` here to get pointers to |
| // properties, because doing so might introduce a writeback buffer, but |
| // fast enumeration relies on the pointer identity of the enumeration |
| // state struct. |
| itemCount = cocoa${Self}.countByEnumerating( |
| with: _fastEnumerationStatePtr, |
| objects: UnsafeMutableRawPointer(_fastEnumerationStackBufPtr) |
| .assumingMemoryBound(to: AnyObject.self), |
| count: stackBufCount) |
| if itemCount == 0 { |
| itemIndex = -1 |
| return nil |
| } |
| itemIndex = 0 |
| } |
| let itemsPtrUP = |
| UnsafeMutableRawPointer(_fastEnumerationState.itemsPtr!) |
| .assumingMemoryBound(to: AnyObject.self) |
| let itemsPtr = _UnmanagedAnyObjectArray(itemsPtrUP) |
| let key: AnyObject = itemsPtr[itemIndex] |
| itemIndex += 1 |
| %if Self == 'Set': |
| return key |
| %elif Self == 'Dictionary': |
| let value: AnyObject = cocoa${Self}.objectFor(key)! |
| return (key, value) |
| %end |
| } |
| } |
| #else |
| final internal class _Cocoa${Self}Iterator {} |
| #endif |
| |
| internal enum ${Self}IteratorRepresentation<${TypeParametersDecl}> { |
| internal typealias _Iterator = ${Self}Iterator<${TypeParameters}> |
| internal typealias _NativeStorageOwner = |
| _Native${Self}StorageOwner<${TypeParameters}> |
| internal typealias _NativeIndex = _Iterator._NativeIndex |
| |
| // For native storage, we keep two indices to keep track of the iteration |
| // progress and the storage owner to make the storage non-uniquely |
| // referenced. |
| // |
| // While indices keep the storage alive, they don't affect reference count of |
| // the storage. Iterator is iterating over a frozen view of the collection |
| // state, so it should keep its own reference to the storage owner. |
| case _native( |
| start: _NativeIndex, end: _NativeIndex, owner: _NativeStorageOwner) |
| case _cocoa(_Cocoa${Self}Iterator) |
| } |
| |
| /// An iterator over the members of a `${Self}<${TypeParameters}>`. |
| public struct ${Self}Iterator<${TypeParametersDecl}> : IteratorProtocol { |
| // ${Self} has a separate IteratorProtocol and Index because of efficiency |
| // and implementability reasons. |
| // |
| // Index for native storage is efficient. Index for bridged NS${Self} is |
| // not. |
| // |
| // Even though fast enumeration is not suitable for implementing |
| // Index, which is multi-pass, it is suitable for implementing a |
| // IteratorProtocol, which is being consumed as iteration proceeds. |
| |
| internal typealias _NativeStorageOwner = |
| _Native${Self}StorageOwner<${TypeParameters}> |
| internal typealias _NativeIndex = _Native${Self}Index<${TypeParameters}> |
| |
| @_versioned |
| internal var _state: ${Self}IteratorRepresentation<${TypeParameters}> |
| |
| @_versioned |
| internal static func _native( |
| start: _NativeIndex, end: _NativeIndex, owner: _NativeStorageOwner |
| ) -> ${Self}Iterator { |
| return ${Self}Iterator( |
| _state: ._native(start: start, end: end, owner: owner)) |
| } |
| #if _runtime(_ObjC) |
| @_versioned |
| internal static func _cocoa( |
| _ iterator: _Cocoa${Self}Iterator |
| ) -> ${Self}Iterator{ |
| return ${Self}Iterator(_state: ._cocoa(iterator)) |
| } |
| #endif |
| |
| @_versioned |
| @_transparent |
| internal var _guaranteedNative: Bool { |
| %if Self == 'Set': |
| return _canBeClass(Element.self) == 0 |
| %elif Self == 'Dictionary': |
| return _canBeClass(Key.self) == 0 || _canBeClass(Value.self) == 0 |
| %end |
| } |
| |
| @_versioned |
| internal mutating func _nativeNext() -> ${Sequence}? { |
| switch _state { |
| case ._native(let startIndex, let endIndex, let owner): |
| if startIndex == endIndex { |
| return nil |
| } |
| let result = startIndex.nativeStorage.assertingGet(startIndex) |
| _state = |
| ._native(start: startIndex.successor(), end: endIndex, owner: owner) |
| return result |
| case ._cocoa: |
| _sanityCheckFailure("internal error: not backed by NS${Self}") |
| } |
| } |
| |
| /// Advances to the next element and returns it, or `nil` if no next element |
| /// exists. |
| /// |
| /// Once `nil` has been returned, all subsequent calls return `nil`. |
| @inline(__always) |
| public mutating func next() -> ${Sequence}? { |
| if _fastPath(_guaranteedNative) { |
| return _nativeNext() |
| } |
| |
| switch _state { |
| case ._native: |
| return _nativeNext() |
| case ._cocoa(let cocoaIterator): |
| #if _runtime(_ObjC) |
| %if Self == 'Set': |
| if let anyObjectElement = cocoaIterator.next() { |
| return _forceBridgeFromObjectiveC(anyObjectElement, Element.self) |
| } |
| %elif Self == 'Dictionary': |
| if let (anyObjectKey, anyObjectValue) = cocoaIterator.next() { |
| let nativeKey = _forceBridgeFromObjectiveC(anyObjectKey, Key.self) |
| let nativeValue = _forceBridgeFromObjectiveC(anyObjectValue, Value.self) |
| return (nativeKey, nativeValue) |
| } |
| %end |
| return nil |
| #else |
| _sanityCheckFailure("internal error: unexpected cocoa ${Self}") |
| #endif |
| } |
| } |
| } |
| |
| extension ${Self}Iterator : CustomReflectable { |
| /// A mirror that reflects the iterator. |
| public var customMirror: Mirror { |
| return Mirror( |
| self, |
| children: EmptyCollection<(label: String?, value: Any)>()) |
| } |
| } |
| |
| extension ${Self} : CustomReflectable { |
| /// A mirror that reflects the ${a_self}. |
| public var customMirror: Mirror { |
| %if Self == 'Set': |
| let style = Mirror.DisplayStyle.`set` |
| %elif Self == 'Dictionary': |
| let style = Mirror.DisplayStyle.dictionary |
| %end |
| return Mirror(self, unlabeledChildren: self, displayStyle: style) |
| } |
| } |
| |
| /// Initializes a `${Self}` from unique members. |
| /// |
| /// Using a builder can be faster than inserting members into an empty |
| /// `${Self}`. |
| public struct _${Self}Builder<${TypeParametersDecl}> { |
| %if Self == 'Set': |
| public typealias Key = ${TypeParameters} |
| public typealias Value = ${TypeParameters} |
| %end |
| |
| internal var _result: ${Self}<${TypeParameters}> |
| internal var _nativeStorage: _Native${Self}Storage<${TypeParameters}> |
| internal let _requestedCount: Int |
| internal var _actualCount: Int |
| |
| public init(count: Int) { |
| let requiredCapacity = |
| _Native${Self}Storage<${TypeParameters}>.minimumCapacity( |
| minimumCount: count, |
| maxLoadFactorInverse: _hashContainerDefaultMaxLoadFactorInverse) |
| _result = ${Self}<${TypeParameters}>(minimumCapacity: requiredCapacity) |
| _nativeStorage = _result._variantStorage.asNative |
| _requestedCount = count |
| _actualCount = 0 |
| } |
| |
| %if Self == 'Set': |
| public mutating func add(member newKey: Key) { |
| _nativeStorage.unsafeAddNew(key: newKey) |
| _actualCount += 1 |
| } |
| %elif Self == 'Dictionary': |
| public mutating func add(key newKey: Key, value: Value) { |
| _nativeStorage.unsafeAddNew(key: newKey, value: value) |
| _actualCount += 1 |
| } |
| %end |
| |
| public mutating func take() -> ${Self}<${TypeParameters}> { |
| _precondition(_actualCount >= 0, |
| "cannot take the result twice") |
| _precondition(_actualCount == _requestedCount, |
| "the number of members added does not match the promised count") |
| |
| // Finish building the `${Self}`. |
| _nativeStorage.count = _requestedCount |
| |
| // Prevent taking the result twice. |
| _actualCount = -1 |
| return _result |
| } |
| } |
| |
| extension ${Self} { |
| %if Self == 'Set': |
| /// Removes and returns the first element of the set. |
| /// |
| /// Because a set is not an ordered collection, the "first" element may not |
| /// be the first element that was added to the set. |
| /// |
| /// - Returns: A member of the set. If the set is empty, returns `nil`. |
| %elif Self == 'Dictionary': |
| /// Removes and returns the first key-value pair of the dictionary if the |
| /// dictionary isn't empty. |
| /// |
| /// The first element of the dictionary is not necessarily the first element |
| /// added. Don't expect any particular ordering of key-value pairs. |
| /// |
| /// - Returns: The first key-value pair of the dictionary if the dictionary |
| /// is not empty; otherwise, `nil`. |
| /// |
| /// - Complexity: Averages to O(1) over many calls to `popFirst()`. |
| %end |
| public mutating func popFirst() -> Element? { |
| guard !isEmpty else { return nil } |
| return remove(at: startIndex) |
| } |
| } |
| |
| //===--- Bridging ---------------------------------------------------------===// |
| |
| #if _runtime(_ObjC) |
| extension ${Self} { |
| public func _bridgeToObjectiveCImpl() -> _NS${Self}Core { |
| switch _variantStorage { |
| case _Variant${Self}Storage.native(let nativeOwner): |
| return nativeOwner as _Native${Self}StorageOwner<${TypeParameters}> |
| |
| case _Variant${Self}Storage.cocoa(let cocoaStorage): |
| return cocoaStorage.cocoa${Self} |
| } |
| } |
| |
| public static func _bridgeFromObjectiveCAdoptingNativeStorageOf( |
| _ s: AnyObject |
| ) -> ${Self}<${TypeParameters}>? { |
| if let nativeOwner = |
| s as AnyObject as? _Native${Self}StorageOwner<${TypeParameters}> { |
| // If `NS${Self}` is actually native storage of `${Self}` with key |
| // and value types that the requested ones match exactly, then just |
| // re-wrap the native storage. |
| return ${Self}<${TypeParameters}>(_nativeStorageOwner: nativeOwner) |
| } |
| // FIXME: what if `s` is native storage, but for different key/value type? |
| return nil |
| } |
| } |
| #endif |
| |
| %end |
| |
| extension Set { |
| /// Removes the elements of the given set from this set. |
| /// |
| /// For example: |
| /// |
| /// var employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let neighbors = ["Bethany", "Eric", "Forlani", "Greta"] |
| /// employees.subtract(neighbors) |
| /// print(employees) |
| /// // Prints "["Diana", "Chris", "Alicia"]" |
| /// |
| /// - Parameter other: Another set. |
| public mutating func subtract(_ other: Set<Element>) { |
| _subtract(other) |
| } |
| |
| /// Returns a Boolean value that indicates whether this set is a subset of the |
| /// given set. |
| /// |
| /// Set *A* is a subset of another set *B* if every member of *A* is also a |
| /// member of *B*. |
| /// |
| /// let employees = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let attendees: Set = ["Alicia", "Bethany", "Diana"] |
| /// print(attendees.isSubset(of: employees)) |
| /// // Prints "true" |
| /// |
| /// - Parameter other: A sequence of elements. `possibleSuperset` |
| /// must be finite. |
| /// - Returns: `true` if the set is a subset of `possibleSuperset`; |
| /// otherwise, `false`. |
| public func isSubset(of other: Set<Element>) -> Bool { |
| let (isSubset, isEqual) = _compareSets(self, other) |
| return isSubset || isEqual |
| } |
| |
| /// Returns a Boolean value that indicates whether this set is a superset of |
| /// the given set. |
| /// |
| /// Set *A* is a superset of another set *B* if every member of *B* is also a |
| /// member of *A*. |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let attendees: Set = ["Alicia", "Bethany", "Diana"] |
| /// print(employees.isSuperset(of: attendees)) |
| /// // Prints "true" |
| /// |
| /// - Parameter possibleSubset: Another set. |
| /// - Returns: `true` if the set is a superset of `possibleSubset`; |
| /// otherwise, `false`. |
| public func isSuperset(of other: Set<Element>) -> Bool { |
| return other.isSubset(of: self) |
| } |
| |
| /// Returns a Boolean value that indicates whether this set has no members in |
| /// common with the given set. |
| /// |
| /// For example: |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let visitors: Set = ["Marcia", "Nathaniel", "Olivia"] |
| /// print(employees.isDisjoint(with: visitors)) |
| /// // Prints "true" |
| /// |
| /// - Parameter other: Another set. |
| /// - Returns: `true` if the set has no elements in common with `other`; |
| /// otherwise, `false`. |
| public func isDisjoint(with other: Set<Element>) -> Bool { |
| for member in self { |
| if other.contains(member) { |
| return false |
| } |
| } |
| return true |
| } |
| |
| /// Returns a new set containing the elements of this set that do not occur |
| /// in the given set. |
| /// |
| /// For example: |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let neighbors: Set = ["Bethany", "Eric", "Forlani", "Greta"] |
| /// let nonNeighbors = employees.subtracting(neighbors) |
| /// print(nonNeighbors) |
| /// // Prints "["Diana", "Chris", "Alicia"]" |
| /// |
| /// - Parameter other: Another set. |
| /// - Returns: A new set. |
| public func subtracting(_ other: Set<Element>) -> Set<Element> { |
| return self._subtracting(other) |
| } |
| |
| /// Returns a Boolean value that indicates whether the set is a strict |
| /// superset of the given sequence. |
| /// |
| /// Set *A* is a strict superset of another set *B* if every member of *B* is |
| /// also a member of *A* and *A* contains at least one element that is *not* |
| /// a member of *B*. |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let attendees: Set = ["Alicia", "Bethany", "Diana"] |
| /// print(employees.isStrictSuperset(of: attendees)) |
| /// // Prints "true" |
| /// print(employees.isStrictSuperset(of: employees)) |
| /// // Prints "false" |
| /// |
| /// - Parameter possibleStrictSubset: Another set. |
| /// - Returns: `true` if the set is a strict superset of |
| /// `possibleStrictSubset`; otherwise, `false`. |
| public func isStrictSuperset(of other: Set<Element>) -> Bool { |
| return self.isSuperset(of: other) && self != other |
| } |
| |
| /// Returns a Boolean value that indicates whether the set is a strict subset |
| /// of the given sequence. |
| /// |
| /// Set *A* is a strict subset of another set *B* if every member of *A* is |
| /// also a member of *B* and *B* contains at least one element that is not a |
| /// member of *A*. |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let attendees: Set = ["Alicia", "Bethany", "Diana"] |
| /// print(attendees.isStrictSubset(of: employees)) |
| /// // Prints "true" |
| /// |
| /// // A set is never a strict subset of itself: |
| /// print(attendees.isStrictSubset(of: attendees)) |
| /// // Prints "false" |
| /// |
| /// - Parameter possibleStrictSuperset: Another set. |
| /// - Returns: `true` if the set is a strict subset of |
| /// `possibleStrictSuperset`; otherwise, `false`. |
| public func isStrictSubset(of other: Set<Element>) -> Bool { |
| return other.isStrictSuperset(of: self) |
| } |
| |
| /// Returns a new set with the elements that are common to both this set and |
| /// the given sequence. |
| /// |
| /// For example: |
| /// |
| /// let employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let neighbors: Set = ["Bethany", "Eric", "Forlani", "Greta"] |
| /// let bothNeighborsAndEmployees = employees.intersection(neighbors) |
| /// print(bothNeighborsAndEmployees) |
| /// // Prints "["Bethany", "Eric"]" |
| /// |
| /// - Parameter other: Another set. |
| /// - Returns: A new set. |
| public func intersection(_ other: Set<Element>) -> Set<Element> { |
| var newSet = Set<Element>() |
| for member in self { |
| if other.contains(member) { |
| newSet.insert(member) |
| } |
| } |
| return newSet |
| } |
| |
| /// Removes the elements of the set that are also in the given sequence and |
| /// adds the members of the sequence that are not already in the set. |
| /// |
| /// For example: |
| /// |
| /// var employees: Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"] |
| /// let neighbors: Set = ["Bethany", "Eric", "Forlani", "Greta"] |
| /// employees.formSymmetricDifference(neighbors) |
| /// print(employees) |
| /// // Prints "["Diana", "Chris", "Forlani", "Alicia", "Greta"]" |
| /// |
| /// - Parameter other: Another set. |
| public mutating func formSymmetricDifference(_ other: Set<Element>) { |
| for member in other { |
| if contains(member) { |
| remove(member) |
| } else { |
| insert(member) |
| } |
| } |
| } |
| } |
| |
| extension Set { |
| @available(*, unavailable, renamed: "remove(at:)") |
| public mutating func removeAtIndex(_ index: Index) -> Element { |
| Builtin.unreachable() |
| } |
| |
| @available(*, unavailable, renamed: "makeIterator()") |
| public func generate() -> SetIterator<Element> { |
| Builtin.unreachable() |
| } |
| |
| @available(*, unavailable, renamed: "index(of:)") |
| public func indexOf(_ member: Element) -> Index? { |
| Builtin.unreachable() |
| } |
| } |
| |
| extension Dictionary { |
| @available(*, unavailable, renamed: "remove(at:)") |
| public mutating func removeAtIndex(_ index: Index) -> Element { |
| Builtin.unreachable() |
| } |
| |
| @available(*, unavailable, renamed: "index(forKey:)") |
| public func indexForKey(_ key: Key) -> Index? { |
| Builtin.unreachable() |
| } |
| |
| @available(*, unavailable, renamed: "removeValue(forKey:)") |
| public mutating func removeValueForKey(_ key: Key) -> Value? { |
| Builtin.unreachable() |
| } |
| |
| @available(*, unavailable, renamed: "makeIterator()") |
| public func generate() -> DictionaryIterator<Key, Value> { |
| Builtin.unreachable() |
| } |
| } |