mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
555 lines
22 KiB
Swift
555 lines
22 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 2019 - 2026 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
// SPDX-License-Identifier: Apache-2.0 WITH Swift-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
/// An unordered collection of unique keys and associated values, optimized for
|
|
/// mutating shared copies and comparing different snapshots of the same
|
|
/// collection.
|
|
///
|
|
/// `TreeDictionary` has the same functionality as a standard
|
|
/// `Dictionary`, and it largely implements the same APIs: both are hashed
|
|
/// collection types with convenient and efficient ways to look up the value
|
|
/// associated with a particular key, and both types are unordered, meaning that
|
|
/// neither type provides any guarantees about the ordering of their items.
|
|
///
|
|
/// However, `TreeDictionary` is optimizing specifically for use cases
|
|
/// that need to mutate shared copies or to compare a dictionary value to one of
|
|
/// its older snapshots. To use a term from functional programming,
|
|
/// `TreeDictionary` implements a _persistent data structure_.
|
|
///
|
|
/// The standard `Dictionary` stores its members in a single, flat hash table,
|
|
/// and it implements value semantics with all-or-nothing copy-on-write
|
|
/// behavior: every time a shared copy of a dictionary is mutated, the mutation
|
|
/// needs to make a full copy of the dictionary's storage.
|
|
/// `TreeDictionary` takes a different approach: it organizes its members
|
|
/// into a tree structure, the nodes of which can be freely shared across
|
|
/// collection values. When mutating a shared copy of a dictionary value,
|
|
/// `TreeDictionary` is able to simply link the unchanged parts of the
|
|
/// tree directly into the result, saving both time and memory.
|
|
///
|
|
/// This structural sharing also makes it more efficient to compare mutated
|
|
/// dictionaries values to earlier versions of themselves. When comparing or
|
|
/// combining dictionaries, parts that are shared across both inputs can
|
|
/// typically be handled in constant time, leading to a dramatic performance
|
|
/// boost when the two inputs are still largely unchanged:
|
|
///
|
|
/// var d = TreeDictionary(
|
|
/// uniqueKeysWithValues: (0 ..< 10_000).map { ($0, 2 * $0) })
|
|
/// let copy = d
|
|
/// d[20_000] = 42 // Expected to be an O(log(n)) operation
|
|
/// let diff = d.keys.subtracting(copy.keys) // Also O(log(n))!
|
|
/// // `diff` now holds the single item 20_000.
|
|
///
|
|
/// The tree structure also eliminates the need to reserve capacity in advance:
|
|
/// `TreeDictionary` creates, destroys and resizes individual nodes as
|
|
/// needed, always consuming just enough memory to store its contents. As of
|
|
/// Swift 5.9, the standard collection types never shrink their storage, so
|
|
/// temporary storage spikes can linger as unused but still allocated memory
|
|
/// long after the collection has shrunk back to its usual size.
|
|
///
|
|
/// Of course, switching to a tree structure comes with some trade offs. In
|
|
/// particular, inserting new items, removing existing ones, and iterating over
|
|
/// a `TreeDictionary` is expected to be a constant factor slower than a
|
|
/// standard `Dictionary` -- allocating/deallocating nodes isn't free, and
|
|
/// navigating the tree structure requires more pointer dereferences than
|
|
/// accessing a flat hash table. However the algorithmic improvements above
|
|
/// usually more than make up for this, as long as the use case can make use of
|
|
/// them.
|
|
@frozen // Not really -- this package is not at all ABI stable
|
|
public struct TreeDictionary<Key: Hashable, Value> {
|
|
@usableFromInline
|
|
internal typealias _Node = _HashNode<Key, Value>
|
|
|
|
@usableFromInline
|
|
internal typealias _UnsafeHandle = _Node.UnsafeHandle
|
|
|
|
@usableFromInline
|
|
var _root: _Node
|
|
|
|
/// The version number of this instance, used for quick index validation.
|
|
/// This is initialized to a (very weakly) random value and it gets
|
|
/// incremented on every mutation that needs to invalidate indices.
|
|
@usableFromInline
|
|
var _version: UInt
|
|
|
|
@inlinable
|
|
internal init(_root: _Node, version: UInt) {
|
|
self._root = _root
|
|
self._version = version
|
|
}
|
|
|
|
@inlinable
|
|
internal init(_new: _Node) {
|
|
self.init(_root: _new, version: _new.initialVersionNumber)
|
|
}
|
|
}
|
|
|
|
extension TreeDictionary {
|
|
/// 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: TreeDictionary = ["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]"
|
|
///
|
|
/// Updating the value of an existing key only modifies the value: it does not
|
|
/// change the key that is stored in the dictionary. (In some cases, equal
|
|
/// keys may be distinguishable from each other by identity comparison or
|
|
/// some other means.)
|
|
///
|
|
/// Removing or updating an existing key-value pair or inserting a new
|
|
/// key-value pair invalidates all indices in the dictionary. Removing a
|
|
/// key that doesn't exist does not invalidate any indices.
|
|
///
|
|
/// - Parameter key: The key to find in the dictionary.
|
|
///
|
|
/// - Returns: The value associated with `key` if `key` is in the dictionary;
|
|
/// otherwise, `nil`.
|
|
///
|
|
/// - Complexity: Looking up the value for a key is expected to traverse
|
|
/// O(log(`count`)) tree nodes and to do at most O(1) hashing/comparison
|
|
/// operations on the `Element` type, as long as `Element` properly
|
|
/// implements hashing.
|
|
///
|
|
/// Updating the dictionary through this subscript is expected to copy at
|
|
/// most O(log(`count`)) existing members.
|
|
@inlinable
|
|
public subscript(key: Key) -> Value? {
|
|
get {
|
|
_root.get(.top, key, _Hash(key))
|
|
}
|
|
set {
|
|
if let value = newValue {
|
|
_updateValue(value, forKey: key)
|
|
_invalidateIndices()
|
|
} else {
|
|
removeValue(forKey: key)
|
|
}
|
|
}
|
|
@inline(__always) // https://github.com/apple/swift-collections/issues/164
|
|
_modify {
|
|
_invalidateIndices()
|
|
var state = _root.prepareValueUpdate(key, _Hash(key))
|
|
defer {
|
|
_root.finalizeValueUpdate(state)
|
|
}
|
|
yield &state.value
|
|
}
|
|
}
|
|
|
|
/// Accesses the value with the given key. If the dictionary doesn't contain
|
|
/// the given key, accesses the provided default value as if the key and
|
|
/// default value existed in the dictionary.
|
|
///
|
|
/// Use this subscript when you want either the value for a particular key
|
|
/// or, when that key is not present in the dictionary, a default value. This
|
|
/// example uses the subscript with a message to use in case an HTTP response
|
|
/// code isn't recognized:
|
|
///
|
|
/// var responseMessages: TreeDictionary = [
|
|
/// 200: "OK",
|
|
/// 403: "Access forbidden",
|
|
/// 404: "File not found",
|
|
/// 500: "Internal server error"]
|
|
///
|
|
/// let httpResponseCodes = [200, 403, 301]
|
|
/// for code in httpResponseCodes {
|
|
/// let message = responseMessages[code, default: "Unknown response"]
|
|
/// print("Response \(code): \(message)")
|
|
/// }
|
|
/// // Prints "Response 200: OK"
|
|
/// // Prints "Response 403: Access forbidden"
|
|
/// // Prints "Response 301: Unknown response"
|
|
///
|
|
/// When a dictionary's `Value` type has value semantics, you can use this
|
|
/// subscript to perform in-place operations on values in the dictionary.
|
|
/// The following example uses this subscript while counting the occurrences
|
|
/// of each letter in a string:
|
|
///
|
|
/// let message = "Hello, Elle!"
|
|
/// var letterCounts: TreeDictionary<Character, Int> = [:]
|
|
/// for letter in message {
|
|
/// letterCounts[letter, default: 0] += 1
|
|
/// }
|
|
/// // letterCounts == ["H": 1, "e": 2, "l": 4, "o": 1, ...]
|
|
///
|
|
/// When `letterCounts[letter, defaultValue: 0] += 1` is executed with a
|
|
/// value of `letter` that isn't already a key in `letterCounts`, the
|
|
/// specified default value (`0`) is returned from the subscript,
|
|
/// incremented, and then added to the dictionary under that key.
|
|
///
|
|
/// Updating the value of an existing key only modifies the value: it does not
|
|
/// change the key that is stored in the dictionary. (In some cases, equal
|
|
/// keys may be distinguishable from each other by identity comparison or
|
|
/// some other means.)
|
|
///
|
|
/// Calling this method invalidates all existing indices in the dictionary.
|
|
///
|
|
/// - Note: Do not use this subscript to modify dictionary values if the
|
|
/// dictionary's `Value` type is a class. In that case, the default value
|
|
/// and key are not written back to the dictionary after an operation. (For
|
|
/// a variant of this operation that supports this usecase, see
|
|
/// `updateValue(forKey:default:_:)`.)
|
|
///
|
|
/// - Parameters:
|
|
/// - key: The key the look up in the dictionary.
|
|
/// - defaultValue: The default value to use if `key` doesn't exist in the
|
|
/// dictionary.
|
|
///
|
|
/// - Returns: The value associated with `key` in the dictionary; otherwise,
|
|
/// `defaultValue`.
|
|
///
|
|
/// - Complexity: Looking up the value for a key is expected to do at most
|
|
/// O(1) hashing/comparison operations on the `Element` type, as long as
|
|
/// `Element` properly implements hashing.
|
|
///
|
|
/// Updating the dictionary through this subscript is expected to copy at
|
|
/// most O(log(`count`)) existing members.
|
|
@inlinable
|
|
public subscript(
|
|
key: Key,
|
|
default defaultValue: @autoclosure () -> Value
|
|
) -> Value {
|
|
get {
|
|
_root.get(.top, key, _Hash(key)) ?? defaultValue()
|
|
}
|
|
set {
|
|
_updateValue(newValue, forKey: key)
|
|
_invalidateIndices()
|
|
}
|
|
@inline(__always) // https://github.com/apple/swift-collections/issues/164
|
|
_modify {
|
|
_invalidateIndices()
|
|
var state = _root.prepareDefaultedValueUpdate(
|
|
.top, key, defaultValue, _Hash(key))
|
|
defer {
|
|
_root.finalizeDefaultedValueUpdate(state)
|
|
}
|
|
yield &state.item.value
|
|
}
|
|
}
|
|
|
|
/// 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. If the
|
|
/// key is not found, then this method returns `nil`.
|
|
///
|
|
/// - 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`.
|
|
///
|
|
/// - Complexity: This operation is expected to perform O(1) hashing and
|
|
/// comparison operations on average, provided that `Element` implements
|
|
/// high-quality hashing.
|
|
@inlinable
|
|
public func index(forKey key: Key) -> Index? {
|
|
guard let path = _root.path(to: key, _Hash(key))
|
|
else { return nil }
|
|
return Index(_root: _root.unmanaged, version: _version, path: path)
|
|
}
|
|
|
|
/// Updates the value stored in the dictionary for the given key, or appends 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: TreeDictionary = [
|
|
/// "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 appends 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."
|
|
///
|
|
/// Updating the value of an existing key only modifies the value: it does not
|
|
/// change the key that is stored in the dictionary. (In some cases, equal
|
|
/// keys may be distinguishable from each other by identity comparison or
|
|
/// some other means.)
|
|
///
|
|
/// Calling this method invalidates all existing indices in the dictionary.
|
|
///
|
|
/// - 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.
|
|
///
|
|
/// - Complexity: This operation is expected to copy at most O(log(`count`))
|
|
/// existing members and to perform at most O(1) hashing/comparison
|
|
/// operations on the `Element` type, as long as `Element` properly
|
|
/// implements hashing.
|
|
@inlinable
|
|
@discardableResult
|
|
public mutating func updateValue(
|
|
_ value: __owned Value, forKey key: Key
|
|
) -> Value? {
|
|
defer { _fixLifetime(self) }
|
|
let hash = _Hash(key)
|
|
let r = _root.updateValue(.top, forKey: key, hash) {
|
|
$0.initialize(to: (key, value))
|
|
}
|
|
_invalidateIndices()
|
|
if r.inserted { return nil }
|
|
return _UnsafeHandle.update(r.leaf) {
|
|
let p = $0.itemPtr(at: r.slot)
|
|
let old = p.pointee.value
|
|
p.pointee.value = value
|
|
return old
|
|
}
|
|
}
|
|
|
|
@inlinable
|
|
@discardableResult
|
|
internal mutating func _updateValue(
|
|
_ value: __owned Value, forKey key: Key
|
|
) -> Bool {
|
|
defer { _fixLifetime(self) }
|
|
let hash = _Hash(key)
|
|
let r = _root.updateValue(.top, forKey: key, hash) {
|
|
$0.initialize(to: (key, value))
|
|
}
|
|
if r.inserted { return true }
|
|
_UnsafeHandle.update(r.leaf) {
|
|
$0[item: r.slot].value = value
|
|
}
|
|
return false
|
|
}
|
|
|
|
/// Calls `body` to directly update the current value of `key` in the
|
|
/// dictionary.
|
|
///
|
|
/// You can use this method to perform in-place operations on values in the
|
|
/// dictionary, whether or not `Value` has value semantics. The following
|
|
/// example uses this method while counting the occurrences of each letter
|
|
/// in a string:
|
|
///
|
|
/// let message = "Hello, Elle!"
|
|
/// var letterCounts: TreeDictionary<Character, Int> = [:]
|
|
/// for letter in message {
|
|
/// letterCounts.updateValue(forKey: letter) { count in
|
|
/// if count == nil {
|
|
/// count = 1
|
|
/// } else
|
|
/// count! += 1
|
|
/// }
|
|
/// }
|
|
/// }
|
|
/// // letterCounts == ["H": 1, "e": 2, "l": 4, "o": 1, ...]
|
|
///
|
|
/// Updating the value of an existing key only modifies the value: it does not
|
|
/// change the key that is stored in the dictionary. (In some cases, equal
|
|
/// keys may be distinguishable from each other by identity comparison or
|
|
/// some other means.)
|
|
///
|
|
/// Removing or updating an existing key-value pair or inserting a new
|
|
/// key-value pair invalidates all indices in the dictionary. Removing a
|
|
/// key that doesn't exist does not invalidate any indices.
|
|
///
|
|
/// - Parameters:
|
|
/// - key: The key whose value to look up.
|
|
/// - body: A function that performs an in-place mutation on the dictionary
|
|
/// value. If `key` exists in the dictionary, then `body` is called with
|
|
/// its current value; otherwise `body` is passed `nil`.
|
|
///
|
|
/// - Returns: The return value of `body`.
|
|
///
|
|
/// - Complexity: In addition to calling `body`, this operation is expected
|
|
/// to copy at most O(log(`count`)) existing members and to perform at
|
|
/// most O(1) hashing/comparison operations on the `Element` type, as long
|
|
/// as `Element` properly implements hashing.
|
|
@inlinable @inline(__always)
|
|
public mutating func updateValue<R>(
|
|
forKey key: Key,
|
|
with body: (inout Value?) throws -> R
|
|
) rethrows -> R {
|
|
try body(&self[key])
|
|
}
|
|
|
|
/// Ensures that the specified key exists in the dictionary (by inserting one
|
|
/// with the supplied default value if necessary), then calls `body` to update
|
|
/// it in place.
|
|
///
|
|
/// You can use this method to perform in-place operations on values in the
|
|
/// dictionary, whether or not `Value` has value semantics. The following
|
|
/// example uses this method while counting the occurrences of each letter
|
|
/// in a string:
|
|
///
|
|
/// let message = "Hello, Elle!"
|
|
/// var letterCounts: TreeDictionary<Character, Int> = [:]
|
|
/// for letter in message {
|
|
/// letterCounts.updateValue(forKey: letter, default: 0) { count in
|
|
/// count += 1
|
|
/// }
|
|
/// }
|
|
/// // letterCounts == ["H": 1, "e": 2, "l": 4, "o": 1, ...]
|
|
///
|
|
/// Updating the value of an existing key only modifies the value: it does not
|
|
/// change the key that is stored in the dictionary. (In some cases, equal
|
|
/// keys may be distinguishable from each other by identity comparison or
|
|
/// some other means.)
|
|
///
|
|
/// Calling this method invalidates all existing indices in the dictionary.
|
|
///
|
|
/// - Parameters:
|
|
/// - key: The key to look up (or insert). If `key` does not already exist
|
|
/// in the dictionary, it is inserted with the supplied default value.
|
|
/// - defaultValue: The default value to insert if `key` doesn't exist in
|
|
/// the dictionary.
|
|
/// - body: A function that performs an in-place mutation on the dictionary
|
|
/// value.
|
|
///
|
|
/// - Returns: The return value of `body`.
|
|
///
|
|
/// - Complexity: In addition to calling `body`, this operation is expected
|
|
/// to copy at most O(log(`count`)) existing members and to perform at
|
|
/// most O(1) hashing/comparison operations on the `Element` type, as long
|
|
/// as `Element` properly implements hashing.
|
|
@inlinable
|
|
public mutating func updateValue<R>(
|
|
forKey key: Key,
|
|
default defaultValue: @autoclosure () -> Value,
|
|
with body: (inout Value) throws -> R
|
|
) rethrows -> R {
|
|
defer { _fixLifetime(self) }
|
|
let hash = _Hash(key)
|
|
let r = _root.updateValue(.top, forKey: key, hash) {
|
|
$0.initialize(to: (key, defaultValue()))
|
|
}
|
|
return try _UnsafeHandle.update(r.leaf) {
|
|
try body(&$0[item: r.slot].value)
|
|
}
|
|
}
|
|
|
|
/// 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, and invalidates all previously returned indices.
|
|
///
|
|
/// var hues: TreeDictionary = [
|
|
/// "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`. Removing a key that isn't in the dictionary does not invalidate
|
|
/// any indices.
|
|
///
|
|
/// if let value = hues.removeValue(forKey: "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: In addition to calling `body`, this operation is expected
|
|
/// to copy at most O(log(`count`)) existing members and to perform at
|
|
/// most O(1) hashing/comparison operations on the `Element` type, as long
|
|
/// as `Element` properly implements hashing.
|
|
@inlinable
|
|
@discardableResult
|
|
public mutating func removeValue(forKey key: Key) -> Value? {
|
|
guard let r = _root.remove(.top, key, _Hash(key)) else { return nil }
|
|
_invalidateIndices()
|
|
assert(r.remainder == nil)
|
|
_invariantCheck()
|
|
return r.removed.value
|
|
}
|
|
|
|
/// Removes and returns the key-value pair at the specified index.
|
|
///
|
|
/// Calling this method invalidates all existing indices in the dictionary.
|
|
///
|
|
/// - Parameter index: The position of the element to remove. `index` must be
|
|
/// a valid index of the dictionary that is not equal to `endIndex`.
|
|
///
|
|
/// - Returns: The removed key-value pair.
|
|
///
|
|
/// - Complexity: This operation is expected to copy at most O(log(`count`))
|
|
/// existing members and to perform at most O(1) hashing/comparison
|
|
/// operations on the `Element` type, as long as `Element` properly
|
|
/// implements hashing.
|
|
@inlinable
|
|
public mutating func remove(at index: Index) -> Element {
|
|
precondition(_isValid(index), "Invalid index")
|
|
precondition(index._path._isItem, "Cannot remove item at end index")
|
|
_invalidateIndices()
|
|
let r = _root.remove(.top, at: index._path)
|
|
assert(r.remainder == nil)
|
|
return r.removed
|
|
}
|
|
}
|
|
|