mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
114 lines
4.1 KiB
Swift
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
|
|
}
|
|
}
|
|
}
|