Files

256 lines
7.6 KiB
Swift

//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2021 - 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
//
//===----------------------------------------------------------------------===//
#if !COLLECTIONS_SINGLE_MODULE
import InternalCollectionsUtilities
#endif
extension BitSet {
@usableFromInline
internal typealias _UnsafeHandle = _UnsafeBitSet
}
extension _UnsafeBitSet {
@inline(__always)
internal func _isReachable(_ index: Index) -> Bool {
unsafe index == endIndex || contains(index.value)
}
}
extension _UnsafeBitSet {
internal func _emptySuffix() -> Int {
var i = wordCount - 1
while i >= 0, unsafe _words[i].isEmpty {
i -= 1
}
return wordCount - 1 - i
}
}
extension _UnsafeBitSet {
@inlinable
internal mutating func combineSharedPrefix(
with other: Self,
using function: (inout _Word, _Word) -> Void
) {
ensureMutable()
let c = Swift.min(self.wordCount, other.wordCount)
for w in 0 ..< c {
unsafe function(&self._mutableWords[w], other._words[w])
}
}
}
extension _UnsafeBitSet {
@_effects(releasenone)
internal mutating func formUnion(_ range: Range<UInt>) {
ensureMutable()
let l = Index(range.lowerBound)
let u = Index(range.upperBound)
assert(u.value <= capacity)
if l.word == u.word {
guard l.word < wordCount else { return }
let w = _Word(from: l.bit, to: u.bit)
unsafe _mutableWords[l.word].formUnion(w)
return
}
unsafe _mutableWords[l.word].formUnion(_Word(upTo: l.bit).complement())
for w in l.word + 1 ..< u.word {
unsafe _mutableWords[w] = .allBits
}
if u.word < wordCount {
unsafe _mutableWords[u.word].formUnion(_Word(upTo: u.bit))
}
}
@_effects(releasenone)
internal mutating func formIntersection(_ range: Range<UInt>) {
ensureMutable()
let l = Index(Swift.min(range.lowerBound, capacity))
let u = Index(Swift.min(range.upperBound, capacity))
for w in 0 ..< l.word {
unsafe _mutableWords[w] = .empty
}
if l.word == u.word {
guard l.word < wordCount else { return }
let w = _Word(from: l.bit, to: u.bit)
unsafe _mutableWords[l.word].formIntersection(w)
return
}
unsafe _mutableWords[l.word].formIntersection(_Word(upTo: l.bit).complement())
if u.word < wordCount {
unsafe _mutableWords[u.word].formIntersection(_Word(upTo: u.bit))
unsafe _mutableWords[(u.word + 1)...].update(repeating: .empty)
}
}
@_effects(releasenone)
internal mutating func formSymmetricDifference(_ range: Range<UInt>) {
ensureMutable()
let l = Index(range.lowerBound)
let u = Index(range.upperBound)
assert(u.value <= capacity)
if l.word == u.word {
guard l.word < wordCount else { return }
let w = _Word(from: l.bit, to: u.bit)
unsafe _mutableWords[l.word].formSymmetricDifference(w)
return
}
unsafe _mutableWords[l.word]
.formSymmetricDifference(_Word(upTo: l.bit).complement())
for w in l.word + 1 ..< u.word {
unsafe _mutableWords[w].formComplement()
}
if u.word < wordCount {
unsafe _mutableWords[u.word].formSymmetricDifference(_Word(upTo: u.bit))
}
}
@_effects(releasenone)
internal mutating func subtract(_ range: Range<UInt>) {
ensureMutable()
let l = Index(Swift.min(range.lowerBound, capacity))
let u = Index(Swift.min(range.upperBound, capacity))
if l.word == u.word {
guard l.word < wordCount else { return }
let w = _Word(from: l.bit, to: u.bit)
unsafe _mutableWords[l.word].subtract(w)
return
}
unsafe _mutableWords[l.word].subtract(_Word(upTo: l.bit).complement())
unsafe _mutableWords[(l.word + 1) ..< u.word].update(repeating: .empty)
if u.word < wordCount {
unsafe _mutableWords[u.word].subtract(_Word(upTo: u.bit))
}
}
@_effects(releasenone)
internal func isDisjoint(with range: Range<UInt>) -> Bool {
if unsafe self.isEmpty { return true }
let lower = Index(Swift.min(range.lowerBound, capacity))
let upper = Index(Swift.min(range.upperBound, capacity))
if lower == upper { return true }
if lower.word == upper.word {
guard lower.word < wordCount else { return true }
let w = _Word(from: lower.bit, to: upper.bit)
return unsafe _words[lower.word].intersection(w).isEmpty
}
let lw = _Word(upTo: lower.bit).complement()
guard unsafe _words[lower.word].intersection(lw).isEmpty else { return false }
for i in lower.word + 1 ..< upper.word {
guard unsafe _words[i].isEmpty else { return false }
}
if upper.word < wordCount {
let uw = _Word(upTo: upper.bit)
guard unsafe _words[upper.word].intersection(uw).isEmpty else { return false }
}
return true
}
@_effects(releasenone)
internal func isSubset(of range: Range<UInt>) -> Bool {
guard !range.isEmpty else { return unsafe isEmpty }
guard unsafe !_words.isEmpty else { return true }
let r = range.clamped(to: 0 ..< UInt(capacity))
let lower = Index(r.lowerBound)
let upper = Index(r.upperBound)
for w in 0 ..< lower.word {
guard unsafe _words[w].isEmpty else { return false }
}
guard lower.word < wordCount else { return true }
let lw = _Word(upTo: lower.bit)
guard unsafe _words[lower.word].intersection(lw).isEmpty else { return false }
guard upper.word < wordCount else { return true }
let hw = _Word(upTo: upper.bit).complement()
guard unsafe _words[upper.word].intersection(hw).isEmpty else { return false }
for w in upper.word + 1 ..< wordCount {
guard unsafe _words[w].isEmpty else { return false }
}
return true
}
@_effects(releasenone)
internal func isSuperset(of range: Range<UInt>) -> Bool {
guard !range.isEmpty else { return true }
let r = range.clamped(to: 0 ..< UInt(capacity))
guard r == range else { return false }
let lower = Index(range.lowerBound)
let upper = Index(range.upperBound)
if lower.word == upper.word {
let w = _Word(from: lower.bit, to: upper.bit)
return unsafe _words[lower.word].intersection(w) == w
}
let lw = _Word(upTo: lower.bit).complement()
guard unsafe _words[lower.word].intersection(lw) == lw else { return false }
for w in lower.word + 1 ..< upper.word {
guard unsafe _words[w].isFull else { return false }
}
guard upper.word < wordCount else { return true }
let uw = _Word(upTo: upper.bit)
return unsafe _words[upper.word].intersection(uw) == uw
}
@_effects(releasenone)
internal func isEqualSet(to range: Range<UInt>) -> Bool {
if range.isEmpty { return unsafe self.isEmpty }
let r = range.clamped(to: 0 ..< UInt(capacity))
guard r == range else { return false }
let lower = Index(range.lowerBound).split
let upper = Index(range.upperBound).endSplit
guard upper.word == wordCount &- 1 else { return false }
for w in 0 ..< lower.word {
guard unsafe _words[w].isEmpty else { return false }
}
if lower.word == upper.word {
let w = _Word(from: lower.bit, to: upper.bit)
return unsafe _words[lower.word] == w
}
let lw = _Word(upTo: lower.bit).complement()
guard unsafe _words[lower.word] == lw else { return false }
for w in lower.word + 1 ..< upper.word {
guard unsafe _words[w].isFull else { return false }
}
let uw = _Word(upTo: upper.bit)
return unsafe _words[upper.word] == uw
}
}