mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
271 lines
11 KiB
Swift
271 lines
11 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 {
|
|
@inlinable
|
|
internal func symmetricDifference<Value2>(
|
|
_ level: _HashLevel,
|
|
_ other: _HashNode<Key, Value2>
|
|
) -> _HashNode<Key, Void>.Builder? {
|
|
guard self.count > 0 else {
|
|
return .init(level, other.mapValuesToVoid())
|
|
}
|
|
guard other.count > 0 else { return nil }
|
|
return _symmetricDifference(level, other)
|
|
}
|
|
|
|
@inlinable
|
|
internal func _symmetricDifference<Value2>(
|
|
_ level: _HashLevel,
|
|
_ other: _HashNode<Key, Value2>
|
|
) -> _HashNode<Key, Void>.Builder {
|
|
typealias VoidNode = _HashNode<Key, Void>
|
|
|
|
assert(self.count > 0 && other.count > 0)
|
|
|
|
if self.raw.storage === other.raw.storage {
|
|
return .empty(level)
|
|
}
|
|
if self.isCollisionNode || other.isCollisionNode {
|
|
return _symmetricDifference_slow(level, other)
|
|
}
|
|
|
|
return unsafe self.read { l in
|
|
unsafe other.read { r in
|
|
var result: VoidNode.Builder = .empty(level)
|
|
|
|
for (bucket, lslot) in unsafe l.itemMap {
|
|
let lp = unsafe l.itemPtr(at: lslot)
|
|
if unsafe r.itemMap.contains(bucket) {
|
|
let rslot = unsafe r.itemMap.slot(of: bucket)
|
|
let rp = unsafe r.itemPtr(at: rslot)
|
|
if unsafe lp.pointee.key != rp.pointee.key {
|
|
let h1 = unsafe _Hash(lp.pointee.key)
|
|
let h2 = unsafe _Hash(rp.pointee.key)
|
|
let child = unsafe VoidNode.build(
|
|
level: level.descend(),
|
|
item1: (lp.pointee.key, ()), h1,
|
|
item2: { unsafe $0.initialize(to: (rp.pointee.key, ())) }, h2)
|
|
unsafe result.addNewChildNode(level, child.top, at: bucket)
|
|
}
|
|
}
|
|
else if unsafe r.childMap.contains(bucket) {
|
|
let rslot = unsafe r.childMap.slot(of: bucket)
|
|
let rp = unsafe r.childPtr(at: rslot)
|
|
let h = unsafe _Hash(lp.pointee.key)
|
|
let child = unsafe rp.pointee
|
|
.removing(level.descend(), lp.pointee.key, h)?.replacement
|
|
if let child = child {
|
|
let child = child.mapValuesToVoid()
|
|
unsafe result.addNewChildBranch(level, child, at: bucket)
|
|
}
|
|
else {
|
|
var child2 = unsafe rp.pointee
|
|
.mapValuesToVoid(
|
|
copy: true, extraBytes: VoidNode.spaceForNewItem)
|
|
let r = unsafe child2.insert(level.descend(), (lp.pointee.key, ()), h)
|
|
assert(unsafe r.inserted)
|
|
unsafe result.addNewChildNode(level, child2, at: bucket)
|
|
}
|
|
}
|
|
else {
|
|
unsafe result.addNewItem(level, (lp.pointee.key, ()), at: bucket)
|
|
}
|
|
}
|
|
|
|
for (bucket, lslot) in unsafe l.childMap {
|
|
let lp = unsafe l.childPtr(at: lslot)
|
|
if unsafe r.itemMap.contains(bucket) {
|
|
let rslot = unsafe r.itemMap.slot(of: bucket)
|
|
let rp = unsafe r.itemPtr(at: rslot)
|
|
let h = unsafe _Hash(rp.pointee.key)
|
|
let child = unsafe lp.pointee
|
|
.mapValuesToVoid()
|
|
.removing(level.descend(), rp.pointee.key, h)?.replacement
|
|
if let child = child {
|
|
unsafe result.addNewChildBranch(level, child, at: bucket)
|
|
}
|
|
else {
|
|
var child2 = unsafe lp.pointee.mapValuesToVoid(
|
|
copy: true, extraBytes: VoidNode.spaceForNewItem)
|
|
let r2 = unsafe child2.insert(level.descend(), (rp.pointee.key, ()), h)
|
|
assert(unsafe r2.inserted)
|
|
unsafe result.addNewChildNode(level, child2, at: bucket)
|
|
}
|
|
}
|
|
else if unsafe r.childMap.contains(bucket) {
|
|
let rslot = unsafe r.childMap.slot(of: bucket)
|
|
let b = unsafe l[child: lslot]._symmetricDifference(
|
|
level.descend(), r[child: rslot])
|
|
unsafe result.addNewChildBranch(level, b, at: bucket)
|
|
}
|
|
else {
|
|
unsafe result.addNewChildNode(
|
|
level, lp.pointee.mapValuesToVoid(), at: bucket)
|
|
}
|
|
}
|
|
|
|
let seen = unsafe l.itemMap.union(l.childMap)
|
|
for (bucket, rslot) in unsafe r.itemMap {
|
|
guard !seen.contains(bucket) else { continue }
|
|
unsafe result.addNewItem(level, (r[item: rslot].key, ()), at: bucket)
|
|
}
|
|
for (bucket, rslot) in unsafe r.childMap {
|
|
guard !seen.contains(bucket) else { continue }
|
|
unsafe result.addNewChildNode(
|
|
level, r[child: rslot].mapValuesToVoid(), at: bucket)
|
|
}
|
|
return result
|
|
}
|
|
}
|
|
}
|
|
|
|
@inlinable @inline(never)
|
|
internal func _symmetricDifference_slow<Value2>(
|
|
_ level: _HashLevel,
|
|
_ other: _HashNode<Key, Value2>
|
|
) -> _HashNode<Key, Void>.Builder {
|
|
switch (self.isCollisionNode, other.isCollisionNode) {
|
|
case (true, true):
|
|
return self._symmetricDifference_slow_both(level, other)
|
|
case (true, false):
|
|
return self._symmetricDifference_slow_left(level, other)
|
|
case (false, _):
|
|
return other._symmetricDifference_slow_left(level, self)
|
|
}
|
|
}
|
|
|
|
@inlinable
|
|
internal func _symmetricDifference_slow_both<Value2>(
|
|
_ level: _HashLevel,
|
|
_ other: _HashNode<Key, Value2>
|
|
) -> _HashNode<Key, Void>.Builder {
|
|
typealias VoidNode = _HashNode<Key, Void>
|
|
return unsafe read { l in
|
|
unsafe other.read { r in
|
|
guard unsafe l.collisionHash == r.collisionHash else {
|
|
let node = unsafe VoidNode.build(
|
|
level: level,
|
|
child1: self.mapValuesToVoid(), l.collisionHash,
|
|
child2: other.mapValuesToVoid(), r.collisionHash)
|
|
return .node(level, node)
|
|
}
|
|
var result: VoidNode.Builder = .empty(level)
|
|
let ritems = unsafe r.reverseItems
|
|
for ls: _HashSlot in stride(from: .zero, to: unsafe l.itemsEndSlot, by: 1) {
|
|
let lp = unsafe l.itemPtr(at: ls)
|
|
let include = unsafe !ritems.contains(where: { unsafe $0.key == lp.pointee.key })
|
|
if include {
|
|
unsafe result.addNewCollision(level, (lp.pointee.key, ()), l.collisionHash)
|
|
}
|
|
}
|
|
// FIXME: Consider remembering slots of shared items in r by
|
|
// caching them in a bitset.
|
|
let litems = unsafe l.reverseItems
|
|
for rs: _HashSlot in stride(from: .zero, to: unsafe r.itemsEndSlot, by: 1) {
|
|
let rp = unsafe r.itemPtr(at: rs)
|
|
let include = unsafe !litems.contains(where: { unsafe $0.key == rp.pointee.key })
|
|
if include {
|
|
unsafe result.addNewCollision(level, (rp.pointee.key, ()), r.collisionHash)
|
|
}
|
|
}
|
|
return result
|
|
}
|
|
}
|
|
}
|
|
|
|
@inlinable
|
|
internal func _symmetricDifference_slow_left<Value2>(
|
|
_ level: _HashLevel,
|
|
_ other: _HashNode<Key, Value2>
|
|
) -> _HashNode<Key, Void>.Builder {
|
|
typealias VoidNode = _HashNode<Key, Void>
|
|
// `self` is a collision node on a compressed path. The other tree might
|
|
// have the same set of collisions, just expanded a bit deeper.
|
|
return unsafe read { l in
|
|
unsafe other.read { r in
|
|
assert(unsafe l.isCollisionNode && !r.isCollisionNode)
|
|
let bucket = unsafe l.collisionHash[level]
|
|
if unsafe r.itemMap.contains(bucket) {
|
|
let rslot = unsafe r.itemMap.slot(of: bucket)
|
|
let rp = unsafe r.itemPtr(at: rslot)
|
|
let rh = unsafe _Hash(rp.pointee.key)
|
|
guard unsafe rh == l.collisionHash else {
|
|
var copy = other.mapValuesToVoid(
|
|
copy: true, extraBytes: VoidNode.spaceForSpawningChild)
|
|
let item = unsafe copy.removeItem(at: bucket, rslot)
|
|
let child = unsafe VoidNode.build(
|
|
level: level.descend(),
|
|
item1: { unsafe $0.initialize(to: (item.key, ())) }, rh,
|
|
child2: self.mapValuesToVoid(), l.collisionHash)
|
|
unsafe copy.insertChild(child.top, bucket)
|
|
return .node(level, copy)
|
|
}
|
|
let litems = unsafe l.reverseItems
|
|
if let li = unsafe litems.firstIndex(where: { unsafe $0.key == rp.pointee.key }) {
|
|
if unsafe l.itemCount == 2 {
|
|
var node = other.mapValuesToVoid(copy: true)
|
|
unsafe node.replaceItem(
|
|
at: bucket, rslot,
|
|
with: (litems[1 &- li].key, ()))
|
|
return .node(level, node)
|
|
}
|
|
let lslot = _HashSlot(litems.count &- 1 &- li)
|
|
var child = self.mapValuesToVoid(copy: true)
|
|
_ = unsafe child.removeItem(at: .invalid, lslot)
|
|
if other.hasSingletonItem {
|
|
// Compression
|
|
return .collisionNode(level, child)
|
|
}
|
|
var node = other.mapValuesToVoid(
|
|
copy: true, extraBytes: VoidNode.spaceForSpawningChild)
|
|
_ = unsafe node.removeItem(at: bucket, rslot)
|
|
unsafe node.insertChild(child, bucket)
|
|
return .node(level, node)
|
|
}
|
|
if other.hasSingletonItem {
|
|
// Compression
|
|
var copy = self.mapValuesToVoid(
|
|
copy: true, extraBytes: VoidNode.spaceForNewItem)
|
|
_ = unsafe copy.ensureUniqueAndAppendCollision(
|
|
isUnique: true,
|
|
(r[item: .zero].key, ()))
|
|
return .collisionNode(level, copy)
|
|
}
|
|
var node = other.mapValuesToVoid(
|
|
copy: true, extraBytes: VoidNode.spaceForSpawningChild)
|
|
let item = unsafe node.removeItem(at: bucket, rslot)
|
|
var child = self.mapValuesToVoid(
|
|
copy: true, extraBytes: VoidNode.spaceForNewItem)
|
|
_ = unsafe child.ensureUniqueAndAppendCollision(
|
|
isUnique: true, (item.key, ()))
|
|
unsafe node.insertChild(child, bucket)
|
|
return .node(level, node)
|
|
}
|
|
if unsafe r.childMap.contains(bucket) {
|
|
let rslot = unsafe r.childMap.slot(of: bucket)
|
|
let rp = unsafe r.childPtr(at: rslot)
|
|
let child = unsafe rp.pointee._symmetricDifference(level.descend(), self)
|
|
return unsafe other
|
|
.mapValuesToVoid()
|
|
.replacingChild(level, at: bucket, rslot, with: child)
|
|
}
|
|
var node = other
|
|
.mapValuesToVoid(copy: true, extraBytes: VoidNode.spaceForNewChild)
|
|
unsafe node.insertChild(self.mapValuesToVoid(), bucket)
|
|
return .node(level, node)
|
|
}
|
|
}
|
|
}
|
|
}
|