mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
893 lines
28 KiB
Swift
893 lines
28 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
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
/// A non-owning, mutable construct representing a path to an item or child node
|
|
/// within a hash tree (or the virtual slot addressing the end of the
|
|
/// items or children region within a node).
|
|
///
|
|
/// Path values provide mutating methods to freely navigate around in the tree,
|
|
/// including basics such as descending into a child node, ascending to a
|
|
/// parent or selecting a particular item within the current node; as well as
|
|
/// more complicated methods such as finding the next/previous item in a
|
|
/// preorder walk of the tree.
|
|
///
|
|
/// Paths are, for the most part, represented by a series of slot values
|
|
/// identifying a particular branch within each level in the tree up to and
|
|
/// including the final node on the path.
|
|
///
|
|
/// However, to speed up common operations, path values also include a single
|
|
/// `_UnmanagedHashNode` reference to their final node. This reference does not
|
|
/// keep the targeted node alive -- it is the use site's responsibility to
|
|
/// ensure that the path is still valid before calling most of its operations.
|
|
///
|
|
/// Note: paths only have a direct reference to their final node. This means
|
|
/// that ascending to the parent node requires following the path from the root
|
|
/// node down. (Paths could also store references to every node alongside them
|
|
/// in a fixed-size array; this would speed up walking over the tree, but it
|
|
/// would considerably embiggen the size of the path construct.)
|
|
@usableFromInline
|
|
@frozen
|
|
internal struct _UnsafePath {
|
|
@usableFromInline
|
|
internal var ancestors: _AncestorHashSlots
|
|
|
|
@usableFromInline
|
|
internal var node: _UnmanagedHashNode
|
|
|
|
@usableFromInline
|
|
internal var nodeSlot: _HashSlot
|
|
|
|
@usableFromInline
|
|
internal var level: _HashLevel
|
|
|
|
@usableFromInline
|
|
internal var _isItem: Bool
|
|
|
|
@inlinable
|
|
internal init(root: __shared _RawHashNode) {
|
|
self.level = .top
|
|
self.ancestors = .empty
|
|
self.node = root.unmanaged
|
|
self.nodeSlot = .zero
|
|
self._isItem = root.storage.header.hasItems
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath {
|
|
internal init(
|
|
_ level: _HashLevel,
|
|
_ ancestors: _AncestorHashSlots,
|
|
_ node: _UnmanagedHashNode,
|
|
childSlot: _HashSlot
|
|
) {
|
|
assert(childSlot < node.childrenEndSlot)
|
|
self.level = level
|
|
self.ancestors = ancestors
|
|
self.node = node
|
|
self.nodeSlot = childSlot
|
|
self._isItem = false
|
|
}
|
|
|
|
@inlinable
|
|
internal init(
|
|
_ level: _HashLevel,
|
|
_ ancestors: _AncestorHashSlots,
|
|
_ node: _UnmanagedHashNode,
|
|
itemSlot: _HashSlot
|
|
) {
|
|
assert(itemSlot < node.itemsEndSlot)
|
|
self.level = level
|
|
self.ancestors = ancestors
|
|
self.node = node
|
|
self.nodeSlot = itemSlot
|
|
self._isItem = true
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath: Equatable {
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal static func ==(left: Self, right: Self) -> Bool {
|
|
// Note: we don't compare nodes (node equality should follow from the rest)
|
|
left.level == right.level
|
|
&& left.ancestors == right.ancestors
|
|
&& left.nodeSlot == right.nodeSlot
|
|
&& left._isItem == right._isItem
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath: Hashable {
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal func hash(into hasher: inout Hasher) {
|
|
// Note: we don't hash nodes, as they aren't compared by ==, either.
|
|
hasher.combine(ancestors.path)
|
|
hasher.combine(nodeSlot)
|
|
hasher.combine(level._shift)
|
|
hasher.combine(_isItem)
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath: Comparable {
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal static func <(left: Self, right: Self) -> Bool {
|
|
// This implements a total ordering across paths based on the slot
|
|
// sequences they contain, corresponding to a preorder walk of the tree.
|
|
//
|
|
// Paths addressing items within a node are ordered before paths addressing
|
|
// a child node within the same node.
|
|
|
|
var level: _HashLevel = .top
|
|
while level < left.level, level < right.level {
|
|
let l = left.ancestors[level]
|
|
let r = right.ancestors[level]
|
|
guard l == r else { return l < r }
|
|
level = level.descend()
|
|
}
|
|
assert(level < left.level || !left.ancestors.hasDataBelow(level))
|
|
assert(level < right.level || !right.ancestors.hasDataBelow(level))
|
|
if level < right.level {
|
|
guard !left._isItem else { return true }
|
|
let l = left.nodeSlot
|
|
let r = right.ancestors[level]
|
|
return l < r
|
|
}
|
|
if level < left.level {
|
|
guard !right._isItem else { return false }
|
|
let l = left.ancestors[level]
|
|
let r = right.nodeSlot
|
|
return l < r
|
|
}
|
|
guard left._isItem == right._isItem else { return left._isItem }
|
|
return left.nodeSlot < right.nodeSlot
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath: CustomStringConvertible {
|
|
@usableFromInline
|
|
internal var description: String {
|
|
var d = "@"
|
|
var l: _HashLevel = .top
|
|
while l < self.level {
|
|
d += ".\(self.ancestors[l])"
|
|
l = l.descend()
|
|
}
|
|
if isPlaceholder {
|
|
d += ".end[\(self.nodeSlot)]"
|
|
} else if isOnItem {
|
|
d += "[\(self.nodeSlot)]"
|
|
} else if isOnChild {
|
|
d += ".\(self.nodeSlot)"
|
|
} else if isOnNodeEnd {
|
|
d += ".end(\(self.nodeSlot))"
|
|
}
|
|
return d
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath {
|
|
/// Returns true if this path addresses an item in the tree; otherwise returns
|
|
/// false.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable @inline(__always)
|
|
internal var isOnItem: Bool {
|
|
// Note: this may be true even if nodeSlot == itemCount (insertion paths).
|
|
_isItem
|
|
}
|
|
|
|
/// Returns true if this path addresses the position following a node's last
|
|
/// valid item. Such paths can represent the place of an item that might be
|
|
/// inserted later; they do not occur while simply iterating over existing
|
|
/// items.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable
|
|
internal var isPlaceholder: Bool {
|
|
_isItem && nodeSlot.value == node.itemCount
|
|
}
|
|
|
|
/// Returns true if this path addresses a node in the tree; otherwise returns
|
|
/// false.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable
|
|
internal var isOnChild: Bool {
|
|
!_isItem && nodeSlot.value < node.childCount
|
|
}
|
|
|
|
/// Returns true if this path addresses an empty slot within a node in a tree;
|
|
/// otherwise returns false.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable
|
|
internal var isOnNodeEnd: Bool {
|
|
!_isItem && nodeSlot.value == node.childCount
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath {
|
|
/// Returns an unmanaged reference to the child node this path is currently
|
|
/// addressing.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable
|
|
internal var currentChild: _UnmanagedHashNode {
|
|
assert(isOnChild)
|
|
return node.unmanagedChild(at: nodeSlot)
|
|
}
|
|
|
|
/// Returns the chid slot in this path corresponding to the specified level.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable
|
|
internal func childSlot(at level: _HashLevel) -> _HashSlot {
|
|
assert(level < self.level)
|
|
return ancestors[level]
|
|
}
|
|
/// Returns the slot of the currently addressed item.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable @inline(__always)
|
|
internal var currentItemSlot: _HashSlot {
|
|
assert(isOnItem)
|
|
return nodeSlot
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath {
|
|
/// Positions this path on the item with the specified slot within its
|
|
/// current node.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable
|
|
internal mutating func selectItem(at slot: _HashSlot) {
|
|
// As a special exception, this allows slot to equal the item count.
|
|
// This can happen for paths that address the position a new item might be
|
|
// inserted later.
|
|
assert(slot <= node.itemsEndSlot)
|
|
nodeSlot = slot
|
|
_isItem = true
|
|
}
|
|
|
|
/// Positions this path on the child with the specified slot within its
|
|
/// current node, without descending into it.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable
|
|
internal mutating func selectChild(at slot: _HashSlot) {
|
|
// As a special exception, this allows slot to equal the child count.
|
|
// This is equivalent to a call to `selectEnd()`.
|
|
assert(slot <= node.childrenEndSlot)
|
|
nodeSlot = slot
|
|
_isItem = false
|
|
}
|
|
|
|
/// Positions this path on the empty slot at the end of its current node.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal mutating func selectEnd() {
|
|
nodeSlot = node.childrenEndSlot
|
|
_isItem = false
|
|
}
|
|
|
|
/// Descend onto the first path within the currently selected child.
|
|
/// (Either the first item if it exists, or the first child. If the child
|
|
/// is an empty node (which should not happen in a valid hash tree), then this
|
|
/// selects the empty slot at the end of it.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable
|
|
internal mutating func descend() {
|
|
self.node = currentChild
|
|
self.ancestors[level] = nodeSlot
|
|
self.nodeSlot = .zero
|
|
self._isItem = node.hasItems
|
|
self.level = level.descend()
|
|
}
|
|
|
|
/// Descend onto the first path within the currently selected child.
|
|
/// (Either the first item if it exists, or the first child. If the child
|
|
/// is an empty node (which should not happen in a valid hash tree), then this
|
|
/// selects the empty slot at the end of it.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@inlinable
|
|
internal mutating func descendToChild(
|
|
_ child: _UnmanagedHashNode, at slot: _HashSlot
|
|
) {
|
|
assert(slot < node.childrenEndSlot)
|
|
assert(child == node.unmanagedChild(at: slot))
|
|
self.node = child
|
|
self.ancestors[level] = slot
|
|
self.nodeSlot = .zero
|
|
self._isItem = node.hasItems
|
|
self.level = level.descend()
|
|
}
|
|
|
|
internal mutating func ascend(
|
|
to ancestor: _UnmanagedHashNode, at level: _HashLevel
|
|
) {
|
|
guard level != self.level else { return }
|
|
assert(level < self.level)
|
|
self.level = level
|
|
self.node = ancestor
|
|
self.nodeSlot = ancestors[level]
|
|
self.ancestors.clear(atOrBelow: level)
|
|
self._isItem = false
|
|
}
|
|
|
|
/// Ascend to the nearest ancestor for which the `test` predicate returns
|
|
/// true. Because paths do not contain references to every node on them,
|
|
/// you need to manually supply a valid reference to the root node. This
|
|
/// method visits every node between the root and the current final node on
|
|
/// the path.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
internal mutating func ascendToNearestAncestor(
|
|
under root: _RawHashNode,
|
|
where test: (_UnmanagedHashNode, _HashSlot) -> Bool
|
|
) -> Bool {
|
|
if self.level.isAtRoot { return false }
|
|
var best: _UnsafePath? = nil
|
|
var n = root.unmanaged
|
|
var l: _HashLevel = .top
|
|
while l < self.level {
|
|
let slot = self.ancestors[l]
|
|
if test(n, slot) {
|
|
best = _UnsafePath(
|
|
l, self.ancestors.truncating(to: l), n, childSlot: slot)
|
|
}
|
|
n = n.unmanagedChild(at: slot)
|
|
l = l.descend()
|
|
}
|
|
guard let best = best else { return false }
|
|
self = best
|
|
return true
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath {
|
|
/// Given a path that is on an item, advance it to the next item within its
|
|
/// current node, and return true. If there is no next item, position the path
|
|
/// on the first child, and return false. If there is no children, position
|
|
/// the path on the node's end position, and return false.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
mutating func selectNextItem() -> Bool {
|
|
assert(isOnItem)
|
|
nodeSlot = nodeSlot.next()
|
|
if nodeSlot < node.itemsEndSlot { return true }
|
|
nodeSlot = .zero
|
|
_isItem = false
|
|
return false
|
|
}
|
|
|
|
/// Given a path that is on a child node, advance it to the next child within
|
|
/// its current node, and return true. If there is no next child, position
|
|
/// the path on the node's end position, and return false.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
mutating func selectNextChild() -> Bool {
|
|
assert(!isOnItem)
|
|
let childrenEndSlot = node.childrenEndSlot
|
|
guard nodeSlot < childrenEndSlot else { return false }
|
|
nodeSlot = nodeSlot.next()
|
|
return nodeSlot < childrenEndSlot
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath {
|
|
/// If this path addresses a child node, descend into the leftmost item
|
|
/// within the subtree under it (i.e., the first item that would be visited
|
|
/// by a preorder walk within that subtree). Do nothing if the path addresses
|
|
/// an item or the end position.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal mutating func descendToLeftMostItem() {
|
|
while isOnChild {
|
|
descend()
|
|
}
|
|
}
|
|
|
|
/// Given a path addressing a child node, descend into the rightmost item
|
|
/// within the subtree under it (i.e., the last item that would be visited
|
|
/// by a preorder walk within that subtree). Do nothing if the path addresses
|
|
/// an item or the end position.
|
|
///
|
|
/// - Note: It is undefined behavior to call this on a path that is no longer
|
|
/// valid.
|
|
internal mutating func descendToRightMostItem() {
|
|
assert(isOnChild)
|
|
while true {
|
|
descend()
|
|
let childrenEndSlot = node.childrenEndSlot
|
|
guard childrenEndSlot > .zero else { break }
|
|
selectChild(at: childrenEndSlot.previous())
|
|
}
|
|
let itemsEndSlot = node.itemsEndSlot
|
|
assert(itemsEndSlot > .zero)
|
|
selectItem(at: itemsEndSlot.previous())
|
|
}
|
|
|
|
/// Find the next item in a preorder walk in the tree following the currently
|
|
/// addressed item, and return true. Return false and do nothing if the
|
|
/// path does not currently address an item.
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal mutating func findSuccessorItem(under root: _RawHashNode) -> Bool {
|
|
guard isOnItem else { return false }
|
|
if selectNextItem() { return true }
|
|
if node.hasChildren {
|
|
descendToLeftMostItem()
|
|
assert(isOnItem)
|
|
return true
|
|
}
|
|
if ascendToNearestAncestor(
|
|
under: root, where: { $1.next() < $0.childrenEndSlot }
|
|
) {
|
|
let r = selectNextChild()
|
|
assert(r)
|
|
descendToLeftMostItem()
|
|
assert(isOnItem)
|
|
return true
|
|
}
|
|
self = _UnsafePath(root: root)
|
|
self.selectEnd()
|
|
return true
|
|
}
|
|
|
|
/// Find the previous item in a preorder walk in the tree preceding the
|
|
/// currently addressed position, and return true.
|
|
/// Return false if there is no previous item.
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal mutating func findPredecessorItem(under root: _RawHashNode) -> Bool {
|
|
switch (isOnItem, nodeSlot > .zero) {
|
|
case (true, true):
|
|
selectItem(at: nodeSlot.previous())
|
|
return true
|
|
case (false, true):
|
|
selectChild(at: nodeSlot.previous())
|
|
descendToRightMostItem()
|
|
return true
|
|
case (false, false):
|
|
if node.hasItems {
|
|
selectItem(at: node.itemsEndSlot.previous())
|
|
return true
|
|
}
|
|
case (true, false):
|
|
break
|
|
}
|
|
guard
|
|
ascendToNearestAncestor(
|
|
under: root,
|
|
where: { $0.hasItems || $1 > .zero })
|
|
else { return false }
|
|
|
|
if nodeSlot > .zero {
|
|
selectChild(at: nodeSlot.previous())
|
|
descendToRightMostItem()
|
|
return true
|
|
}
|
|
if node.hasItems {
|
|
selectItem(at: node.itemsEndSlot.previous())
|
|
return true
|
|
}
|
|
return false
|
|
}
|
|
}
|
|
|
|
extension _RawHashNode {
|
|
/// Return the integer position of the item addressed by the given path
|
|
/// within a preorder walk of the tree. If the path addresses the end
|
|
/// position, then return the number of items in the tree.
|
|
///
|
|
/// This method must only be called on the root node.
|
|
internal func preorderPosition(
|
|
_ level: _HashLevel, of path: _UnsafePath
|
|
) -> Int {
|
|
if path.isOnNodeEnd { return count }
|
|
assert(path.isOnItem)
|
|
if level < path.level {
|
|
let childSlot = path.childSlot(at: level)
|
|
return read {
|
|
let prefix = $0.children[..<childSlot.value]
|
|
.reduce($0.itemCount) { $0 + $1.count }
|
|
let positionWithinChild = $0[child: childSlot]
|
|
.preorderPosition(level.descend(), of: path)
|
|
return prefix + positionWithinChild
|
|
}
|
|
}
|
|
assert(path.level == level)
|
|
return path.nodeSlot.value
|
|
}
|
|
}
|
|
|
|
extension _UnsafePath {
|
|
/// Set the path to the item at the specified position in a preorder walk
|
|
/// of the subtree rooted at the current node.
|
|
///
|
|
/// - Returns: `(found, remaining)`, where found is true if the item was
|
|
/// successfully found, and false otherwise. If `found` is false then
|
|
/// `remaining` is the number of items that still need to be skipped to
|
|
/// find the correct item (outside this subtree).
|
|
/// If `found` is true, then `remaining` is zero.
|
|
internal mutating func findItemAtPreorderPosition(
|
|
_ position: Int
|
|
) -> (found: Bool, remaining: Int) {
|
|
assert(position >= 0)
|
|
let top = node
|
|
let topLevel = level
|
|
var stop = false
|
|
var remaining = position
|
|
while !stop {
|
|
let itemCount = node.itemCount
|
|
if remaining < itemCount {
|
|
selectItem(at: _HashSlot(remaining))
|
|
return (true, 0)
|
|
}
|
|
remaining -= itemCount
|
|
node.read {
|
|
let children = $0.children
|
|
for i in children.indices {
|
|
let c = children[i].count
|
|
if remaining < c {
|
|
descendToChild(children[i].unmanaged, at: _HashSlot(i))
|
|
return
|
|
}
|
|
remaining &-= c
|
|
}
|
|
stop = true
|
|
}
|
|
}
|
|
ascend(to: top, at: topLevel)
|
|
selectEnd()
|
|
return (false, remaining)
|
|
}
|
|
}
|
|
|
|
extension _RawHashNode {
|
|
/// Return the number of steps between two paths within a preorder walk of the
|
|
/// tree. The two paths must not address a child node.
|
|
///
|
|
/// This method must only be called on the root node.
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal func distance(
|
|
_ level: _HashLevel, from start: _UnsafePath, to end: _UnsafePath
|
|
) -> Int {
|
|
assert(level.isAtRoot)
|
|
if start.isOnNodeEnd {
|
|
// Shortcut: distance from end.
|
|
return preorderPosition(level, of: end) - count
|
|
}
|
|
if end.isOnNodeEnd {
|
|
// Shortcut: distance to end.
|
|
return count - preorderPosition(level, of: start)
|
|
}
|
|
assert(start.isOnItem)
|
|
assert(end.isOnItem)
|
|
if start.level == end.level, start.ancestors == end.ancestors {
|
|
// Shortcut: the paths are under the same node.
|
|
precondition(start.node == end.node, "Internal index validation error")
|
|
return start.currentItemSlot.distance(to: end.currentItemSlot)
|
|
}
|
|
if
|
|
start.level < end.level,
|
|
start.ancestors.isEqual(to: end.ancestors, upTo: start.level)
|
|
{
|
|
// Shortcut: start's node is an ancestor of end's position.
|
|
return start.node._distance(
|
|
start.level, fromItemAt: start.currentItemSlot, to: end)
|
|
}
|
|
if start.ancestors.isEqual(to: end.ancestors, upTo: end.level) {
|
|
// Shortcut: end's node is an ancestor of start's position.
|
|
return -end.node._distance(
|
|
end.level, fromItemAt: end.currentItemSlot, to: start)
|
|
}
|
|
// No shortcuts -- the two paths are in different subtrees.
|
|
// Start descending from the root to look for the closest common
|
|
// ancestor.
|
|
if start < end {
|
|
return _distance(level, from: start, to: end)
|
|
}
|
|
return -_distance(level, from: end, to: start)
|
|
}
|
|
|
|
internal func _distance(
|
|
_ level: _HashLevel, from start: _UnsafePath, to end: _UnsafePath
|
|
) -> Int {
|
|
assert(start < end)
|
|
assert(level < start.level)
|
|
assert(level < end.level)
|
|
let slot1 = start.childSlot(at: level)
|
|
let slot2 = end.childSlot(at: level)
|
|
if slot1 == slot2 {
|
|
return read {
|
|
$0[child: slot1]._distance(level.descend(), from: start, to: end)
|
|
}
|
|
}
|
|
return read {
|
|
let children = $0.children
|
|
let d1 = children[slot1.value]
|
|
.preorderPosition(level.descend(), of: start)
|
|
let d2 = children[slot1.value &+ 1 ..< slot2.value]
|
|
.reduce(0) { $0 + $1.count }
|
|
let d3 = children[slot2.value]
|
|
.preorderPosition(level.descend(), of: end)
|
|
return (children[slot1.value].count - d1) + d2 + d3
|
|
}
|
|
}
|
|
}
|
|
|
|
extension _UnmanagedHashNode {
|
|
internal func _distance(
|
|
_ level: _HashLevel, fromItemAt start: _HashSlot, to end: _UnsafePath
|
|
) -> Int {
|
|
read {
|
|
assert(start < $0.itemsEndSlot)
|
|
assert(level < end.level)
|
|
let childSlot = end.childSlot(at: level)
|
|
let children = $0.children
|
|
let prefix = children[..<childSlot.value]
|
|
.reduce($0.itemCount - start.value) { $0 + $1.count }
|
|
let positionWithinChild = children[childSlot.value]
|
|
.preorderPosition(level.descend(), of: end)
|
|
return prefix + positionWithinChild
|
|
}
|
|
}
|
|
}
|
|
|
|
extension _HashNode {
|
|
/// Return the path to the given key in this tree if it exists; otherwise
|
|
/// return nil.
|
|
@inlinable
|
|
internal func path(
|
|
to key: Key, _ hash: _Hash
|
|
) -> _UnsafePath? {
|
|
var node = unmanaged
|
|
var level: _HashLevel = .top
|
|
var ancestors: _AncestorHashSlots = .empty
|
|
while true {
|
|
let r = UnsafeHandle.read(node) { $0.find(level, key, hash) }
|
|
guard let r = r else { break }
|
|
guard r.descend else {
|
|
return _UnsafePath(level, ancestors, node, itemSlot: r.slot)
|
|
}
|
|
node = node.unmanagedChild(at: r.slot)
|
|
ancestors[level] = r.slot
|
|
level = level.descend()
|
|
}
|
|
return nil
|
|
}
|
|
}
|
|
|
|
extension _RawHashNode {
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal func seek(
|
|
_ level: _HashLevel,
|
|
_ path: inout _UnsafePath,
|
|
offsetBy distance: Int,
|
|
limitedBy limit: _UnsafePath
|
|
) -> (found: Bool, limited: Bool) {
|
|
assert(level.isAtRoot)
|
|
if (distance > 0 && limit < path) || (distance < 0 && limit > path) {
|
|
return (seek(level, &path, offsetBy: distance), false)
|
|
}
|
|
var d = distance
|
|
guard self._seek(level, &path, offsetBy: &d) else {
|
|
path = limit
|
|
return (distance >= 0 && d == 0 && limit.isOnNodeEnd, true)
|
|
}
|
|
let found = (
|
|
distance == 0
|
|
|| (distance > 0 && path <= limit)
|
|
|| (distance < 0 && path >= limit))
|
|
return (found, true)
|
|
}
|
|
|
|
@usableFromInline
|
|
@_effects(releasenone)
|
|
internal func seek(
|
|
_ level: _HashLevel,
|
|
_ path: inout _UnsafePath,
|
|
offsetBy distance: Int
|
|
) -> Bool {
|
|
var d = distance
|
|
if self._seek(level, &path, offsetBy: &d) {
|
|
return true
|
|
}
|
|
if distance > 0, d == 0 { // endIndex
|
|
return true
|
|
}
|
|
return false
|
|
}
|
|
|
|
internal func _seek(
|
|
_ level: _HashLevel,
|
|
_ path: inout _UnsafePath,
|
|
offsetBy distance: inout Int
|
|
) -> Bool {
|
|
// This is a bit complicated, because we only have a direct reference to the
|
|
// final node on the path, and we want to avoid having to descend
|
|
// from the root down if the target item stays within the original node's
|
|
// subtree. So we first figure out the subtree situation, and only start the
|
|
// recursion if the target is outside of it.
|
|
assert(level.isAtRoot)
|
|
assert(path.isOnItem || path.isOnNodeEnd)
|
|
guard distance != 0 else { return true }
|
|
if distance > 0 {
|
|
if !path.isOnItem { return false }
|
|
// Try a local search within the subtree starting at the current node.
|
|
let slot = path.currentItemSlot
|
|
let r = path.findItemAtPreorderPosition(distance &+ slot.value)
|
|
if r.found {
|
|
assert(r.remaining == 0)
|
|
return true
|
|
}
|
|
assert(r.remaining >= 0 && r.remaining <= distance)
|
|
distance = r.remaining
|
|
|
|
// Fall back to recursively descending from the root.
|
|
return _seekForward(level, by: &distance, fromSubtree: &path)
|
|
}
|
|
// distance < 0
|
|
if !path.isOnNodeEnd {
|
|
// Shortcut: see if the destination item is within the same node.
|
|
// (Doing this here allows us to avoid having to descend from the root
|
|
// down only to figure this out.)
|
|
let slot = path.nodeSlot
|
|
distance &+= slot.value
|
|
if distance >= 0 {
|
|
path.selectItem(at: _HashSlot(distance))
|
|
distance = 0
|
|
return true
|
|
}
|
|
}
|
|
// Otherwise we need to visit ancestor nodes to find the item at the right
|
|
// position. We also do this when we start from the end index -- there
|
|
// will be no recursion in that case anyway.
|
|
return _seekBackward(level, by: &distance, fromSubtree: &path)
|
|
}
|
|
|
|
/// Find the item at the given positive distance from the last item within the
|
|
/// subtree rooted at the current node in `path`.
|
|
internal func _seekForward(
|
|
_ level: _HashLevel,
|
|
by distance: inout Int,
|
|
fromSubtree path: inout _UnsafePath
|
|
) -> Bool {
|
|
assert(distance >= 0)
|
|
assert(level <= path.level)
|
|
guard level < path.level else {
|
|
path.selectEnd()
|
|
return false
|
|
}
|
|
return read {
|
|
let children = $0.children
|
|
var i = path.childSlot(at: level).value
|
|
if children[i]._seekForward(
|
|
level.descend(), by: &distance, fromSubtree: &path
|
|
) {
|
|
assert(distance == 0)
|
|
return true
|
|
}
|
|
path.ascend(to: unmanaged, at: level)
|
|
i &+= 1
|
|
while i < children.endIndex {
|
|
let c = children[i].count
|
|
if distance < c {
|
|
path.descendToChild(children[i].unmanaged, at: _HashSlot(i))
|
|
let r = path.findItemAtPreorderPosition(distance)
|
|
precondition(r.found, "Internal inconsistency: invalid node counts")
|
|
assert(r.remaining == 0)
|
|
distance = 0
|
|
return true
|
|
}
|
|
distance &-= c
|
|
i &+= 1
|
|
}
|
|
path.selectEnd()
|
|
return false
|
|
}
|
|
}
|
|
|
|
/// Find the item at the given negative distance from the first item within the
|
|
/// subtree rooted at the current node in `path`.
|
|
internal func _seekBackward(
|
|
_ level: _HashLevel,
|
|
by distance: inout Int,
|
|
fromSubtree path: inout _UnsafePath
|
|
) -> Bool {
|
|
assert(distance < 0)
|
|
assert(level <= path.level)
|
|
|
|
return read {
|
|
let children = $0.children
|
|
var slot: _HashSlot
|
|
if level < path.level {
|
|
// We need to descend to the end of the path before we can start the
|
|
// search for real.
|
|
slot = path.childSlot(at: level)
|
|
if children[slot.value]._seekBackward(
|
|
level.descend(), by: &distance, fromSubtree: &path
|
|
) {
|
|
// A deeper level has found the target item.
|
|
assert(distance == 0)
|
|
return true
|
|
}
|
|
// No luck yet -- ascend to this node and look through preceding data.
|
|
path.ascend(to: unmanaged, at: level)
|
|
} else if path.isOnNodeEnd {
|
|
// When we start from the root's end (the end index), we don't need
|
|
// to descend before starting to look at previous children.
|
|
assert(level.isAtRoot && path.node == self.unmanaged)
|
|
slot = path.node.childrenEndSlot
|
|
} else { // level == path.level
|
|
// The outermost caller has already gone as far back as possible
|
|
// within the original subtree. Return a level higher to actually
|
|
// start the rest of the search.
|
|
return false
|
|
}
|
|
|
|
// Look through all preceding children for the target item.
|
|
while slot > .zero {
|
|
slot = slot.previous()
|
|
let c = children[slot.value].count
|
|
if c + distance >= 0 {
|
|
path.descendToChild(children[slot.value].unmanaged, at: slot)
|
|
let r = path.findItemAtPreorderPosition(c + distance)
|
|
precondition(r.found, "Internal inconsistency: invalid node counts")
|
|
distance = 0
|
|
return true
|
|
}
|
|
distance += c
|
|
}
|
|
// See if the target is hiding somewhere in our immediate items.
|
|
distance &+= $0.itemCount
|
|
if distance >= 0 {
|
|
path.selectItem(at: _HashSlot(distance))
|
|
distance = 0
|
|
return true
|
|
}
|
|
// No joy -- we need to continue searching a level higher.
|
|
assert(distance < 0)
|
|
return false
|
|
}
|
|
}
|
|
}
|
|
|