Files

272 lines
8.7 KiB
Swift

//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2022 - 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
//
//===----------------------------------------------------------------------===//
// MARK: Node-level lookup operations
extension _HashNode {
@inlinable
internal func find(
_ level: _HashLevel, _ key: Key, _ hash: _Hash
) -> (descend: Bool, slot: _HashSlot)? {
unsafe read { unsafe $0.find(level, key, hash) }
}
}
extension _HashNode.UnsafeHandle {
@inlinable
internal func find(
_ level: _HashLevel, _ key: Key, _ hash: _Hash
) -> (descend: Bool, slot: _HashSlot)? {
guard unsafe !isCollisionNode else {
let r = unsafe _findInCollision(level, key, hash)
guard r.code == 0 else { return nil }
return (false, r.slot)
}
let bucket = hash[level]
if unsafe itemMap.contains(bucket) {
let slot = unsafe itemMap.slot(of: bucket)
guard unsafe self[item: slot].key == key else { return nil }
return (false, slot)
}
if unsafe childMap.contains(bucket) {
let slot = unsafe childMap.slot(of: bucket)
return (true, slot)
}
return nil
}
@inlinable @inline(never)
internal func _findInCollision(
_ level: _HashLevel, _ key: Key, _ hash: _Hash
) -> (code: Int, slot: _HashSlot) {
assert(unsafe isCollisionNode)
if !level.isAtBottom {
if unsafe hash != self.collisionHash { return (2, .zero) }
}
// Note: this searches the items in reverse insertion order.
guard let slot = unsafe reverseItems.firstIndex(where: { $0.key == key })
else { return (1, unsafe self.itemsEndSlot) }
return (0, unsafe _HashSlot(itemCount &- 1 &- slot))
}
}
/// Represents the results of a lookup operation within a single node of a hash
/// tree. This enumeration captures all of the different cases that need to be
/// covered if we wanted to insert a new item into the tree.
///
/// For simple read-only lookup operations (and removals) some of the cases are
/// equivalent: `.notFound`, .newCollision` and `expansion` all represent the
/// same logical outcome: the key we're looking for is not present in this
/// subtree.
@usableFromInline
@frozen
internal enum _FindResult {
/// The item we're looking for is stored directly in this node, at the
/// bucket / item slot identified in the payload.
///
/// If the current node is a collision node, then the bucket value is
/// set to `_Bucket.invalid`.
case found(_Bucket, _HashSlot)
/// The item we're looking for is not currently inside the subtree rooted at
/// this node.
///
/// If we wanted to insert it, then its correct slot is within this node
/// at the specified bucket / item slot. (Which is currently empty.)
///
/// When the node is a collision node, the `insertCollision` case is returned
/// instead of this one.
case insert(_Bucket, _HashSlot)
/// The item we're looking for is not currently inside the subtree rooted at
/// this collision node.
///
/// If we wanted to insert it, then it needs to be appended to the items
/// buffer.
case appendCollision
/// The item we're looking for is not currently inside the subtree rooted at
/// this node.
///
/// If we wanted to insert it, then it would need to be stored in this node
/// at the specified bucket / item slot. However, that bucket is already
/// occupied by another item, so the insertion would need to involve replacing
/// it with a new child node.
///
/// (This case is never returned if the current node is a collision node.)
case spawnChild(_Bucket, _HashSlot)
/// The item we're looking for is not in this subtree.
///
/// However, the item doesn't belong in this subtree at all. This is an
/// irregular case that can only happen with (compressed) hash collision nodes
/// whose (otherwise empty) ancestors got eliminated, so they appear further
/// up in the tree than what their (logical) level would indicate.
///
/// If we wanted to insert a new item with this key, then we'd need to create
/// (one or more) new parent nodes above this node, pushing this collision
/// node further down the tree. (This undoes the compression by expanding
/// the collision node's path, hence the name of the enum case.)
///
/// (This case is never returned if the current node is a regular node.)
case expansion
/// The item we're looking for is not directly stored in this node, but it
/// might be somewhere in the subtree rooted at the child at the given
/// bucket & slot.
///
/// (This case is never returned if the current node is a collision node.)
case descend(_Bucket, _HashSlot)
}
extension _HashNode {
@inlinable
internal func findForInsertion(
_ level: _HashLevel, _ key: Key, _ hash: _Hash
) -> _FindResult {
unsafe read { unsafe $0.findForInsertion(level, key, hash) }
}
}
extension _HashNode.UnsafeHandle {
@inlinable
internal func findForInsertion(
_ level: _HashLevel, _ key: Key, _ hash: _Hash
) -> _FindResult {
guard unsafe !isCollisionNode else {
let r = unsafe _findInCollision(level, key, hash)
if r.code == 0 {
return .found(.invalid, r.slot)
}
if r.code == 1 {
return .appendCollision
}
assert(r.code == 2)
return .expansion
}
let bucket = hash[level]
if unsafe itemMap.contains(bucket) {
let slot = unsafe itemMap.slot(of: bucket)
if unsafe self[item: slot].key == key {
return .found(bucket, slot)
}
return .spawnChild(bucket, slot)
}
if unsafe childMap.contains(bucket) {
let slot = unsafe childMap.slot(of: bucket)
return .descend(bucket, slot)
}
let slot = unsafe itemMap.slot(of: bucket)
return .insert(bucket, slot)
}
}
// MARK: Subtree-level lookup operations
extension _HashNode {
@inlinable
internal func get(_ level: _HashLevel, _ key: Key, _ hash: _Hash) -> Value? {
var node = unsafe unmanaged
var level = level
while true {
let r = unsafe UnsafeHandle.read(node) { unsafe $0.find(level, key, hash) }
guard let r = r else {
return nil
}
guard r.descend else {
return unsafe UnsafeHandle.read(node) { unsafe $0[item: r.slot].value }
}
unsafe node = node.unmanagedChild(at: r.slot)
level = level.descend()
}
}
}
extension _HashNode {
@inlinable
internal func containsKey(
_ level: _HashLevel, _ key: Key, _ hash: _Hash
) -> Bool {
var node = unsafe unmanaged
var level = level
while true {
let r = unsafe UnsafeHandle.read(node) { unsafe $0.find(level, key, hash) }
guard let r = r else { return false }
guard r.descend else { return true }
unsafe node = node.unmanagedChild(at: r.slot)
level = level.descend()
}
}
}
extension _HashNode {
@inlinable
internal func lookup(
_ level: _HashLevel, _ key: Key, _ hash: _Hash
) -> (node: _UnmanagedHashNode, slot: _HashSlot)? {
var node = unsafe unmanaged
var level = level
while true {
let r = unsafe UnsafeHandle.read(node) { unsafe $0.find(level, key, hash) }
guard let r = r else {
return nil
}
guard r.descend else {
return unsafe (node, r.slot)
}
unsafe node = node.unmanagedChild(at: r.slot)
level = level.descend()
}
}
}
extension _HashNode {
@inlinable
internal func position(
forKey key: Key, _ level: _HashLevel, _ hash: _Hash
) -> Int? {
guard let r = find(level, key, hash) else { return nil }
guard r.descend else { return r.slot.value }
return unsafe read { h in
let children = unsafe h.children
let p = unsafe children[r.slot.value]
.position(forKey: key, level.descend(), hash)
guard let p = p else { return nil }
let c = unsafe h.itemCount &+ p
return unsafe children[..<r.slot.value].reduce(into: c) { $0 &+= $1.count }
}
}
@inlinable
internal func item(position: Int) -> Element {
assert(position >= 0 && position < self.count)
return unsafe read {
var itemsToSkip = position
let itemCount = unsafe $0.itemCount
if itemsToSkip < itemCount {
return unsafe $0[item: _HashSlot(itemsToSkip)]
}
itemsToSkip -= itemCount
let children = unsafe $0.children
for i in children.indices {
if unsafe itemsToSkip < children[i].count {
return unsafe children[i].item(position: itemsToSkip)
}
unsafe itemsToSkip -= children[i].count
}
fatalError("Inconsistent tree")
}
}
}