Files

114 lines
4.1 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
//
//===----------------------------------------------------------------------===//
extension _HashNode {
/// Returns true if `self` contains a disjoint set of keys than `other`.
/// Otherwise, returns false.
@inlinable @inline(never)
internal func isDisjoint<Value2>(
_ level: _HashLevel,
with other: _HashNode<Key, Value2>
) -> Bool {
if self.count == 0 || other.count == 0 { return true }
if self.raw.storage === other.raw.storage { return false }
if self.isCollisionNode {
return _isDisjointCollision(level, with: other)
}
if other.isCollisionNode {
return other._isDisjointCollision(level, with: self)
}
return unsafe self.read { l in
unsafe other.read { r in
let lmap = unsafe l.itemMap.union(l.childMap)
let rmap = unsafe r.itemMap.union(r.childMap)
if lmap.isDisjoint(with: rmap) { return true }
for (bucket, _) in unsafe l.itemMap.intersection(r.itemMap) {
let lslot = unsafe l.itemMap.slot(of: bucket)
let rslot = unsafe r.itemMap.slot(of: bucket)
guard unsafe l[item: lslot].key != r[item: rslot].key else { return false }
}
for (bucket, _) in unsafe l.itemMap.intersection(r.childMap) {
let lslot = unsafe l.itemMap.slot(of: bucket)
let hash = unsafe _Hash(l[item: lslot].key)
let rslot = unsafe r.childMap.slot(of: bucket)
let found = unsafe r[child: rslot].containsKey(
level.descend(),
l[item: lslot].key,
hash)
if found { return false }
}
for (bucket, _) in unsafe l.childMap.intersection(r.itemMap) {
let lslot = unsafe l.childMap.slot(of: bucket)
let rslot = unsafe r.itemMap.slot(of: bucket)
let hash = unsafe _Hash(r[item: rslot].key)
let found = unsafe l[child: lslot].containsKey(
level.descend(),
r[item: rslot].key,
hash)
if found { return false }
}
for (bucket, _) in unsafe l.childMap.intersection(r.childMap) {
let lslot = unsafe l.childMap.slot(of: bucket)
let rslot = unsafe r.childMap.slot(of: bucket)
guard
unsafe l[child: lslot].isDisjoint(level.descend(), with: r[child: rslot])
else { return false }
}
return true
}
}
}
@inlinable @inline(never)
internal func _isDisjointCollision<Value2>(
_ level: _HashLevel,
with other: _HashNode<Key, Value2>
) -> Bool {
assert(isCollisionNode)
if other.isCollisionNode {
return unsafe read { l in
unsafe other.read { r in
guard unsafe l.collisionHash == r.collisionHash else { return true }
let litems = unsafe l.reverseItems
let ritems = unsafe r.reverseItems
return unsafe litems.allSatisfy { li in
unsafe !ritems.contains { ri in li.key == ri.key }
}
}
}
}
// `self` is on a compressed path. Try descending down by one level.
assert(!level.isAtBottom)
let bucket = self.collisionHash[level]
return unsafe other.read { r in
if unsafe r.childMap.contains(bucket) {
let slot = unsafe r.childMap.slot(of: bucket)
return unsafe isDisjoint(level.descend(), with: r[child: slot])
}
if unsafe r.itemMap.contains(bucket) {
let rslot = unsafe r.itemMap.slot(of: bucket)
let p = unsafe r.itemPtr(at: rslot)
let hash = unsafe _Hash(p.pointee.key)
return unsafe read { l in
guard unsafe hash == l.collisionHash else { return true }
return unsafe !l.reverseItems.contains { unsafe $0.key == p.pointee.key }
}
}
return true
}
}
}