Files

224 lines
5.7 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
//
//===----------------------------------------------------------------------===//
#if !COLLECTIONS_SINGLE_MODULE
import InternalCollectionsUtilities
#endif
/// A set of `_Bucket` values, represented by a 32-bit wide bitset.
@usableFromInline
@frozen
internal struct _Bitmap {
@usableFromInline
internal typealias Value = UInt32
@usableFromInline
internal var _value: Value
@inlinable @inline(__always)
init(_value: Value) {
self._value = _value
}
@inlinable @inline(__always)
init(bitPattern: Int) {
self._value = Value(bitPattern)
}
@inlinable @inline(__always)
internal init(_ bucket: _Bucket) {
assert(bucket.value < Self.capacity)
_value = (1 &<< bucket.value)
}
@inlinable @inline(__always)
internal init(_ bucket1: _Bucket, _ bucket2: _Bucket) {
assert(bucket1.value < Self.capacity && bucket2.value < Self.capacity)
assert(bucket1 != bucket2)
_value = (1 &<< bucket1.value) | (1 &<< bucket2.value)
}
@inlinable
internal init(upTo bucket: _Bucket) {
assert(bucket.value < Self.capacity)
_value = (1 &<< bucket.value) &- 1
}
}
extension _Bitmap: Equatable {
@inlinable @inline(__always)
internal static func ==(left: Self, right: Self) -> Bool {
left._value == right._value
}
}
extension _Bitmap: CustomStringConvertible {
@usableFromInline
internal var description: String {
let b = String(_value, radix: 2)
let bits = String(repeating: "0", count: _Bitmap.capacity - b.count) + b
return "\(String(bits.reversed())) (\(_value))"
}
}
extension _Bitmap {
@inlinable @inline(__always)
internal static var empty: Self { .init(_value: 0) }
@inlinable @inline(__always)
internal static var capacity: Int { Value.bitWidth }
@inlinable @inline(__always)
internal static var bitWidth: Int { capacity.trailingZeroBitCount }
@inlinable @inline(__always)
internal var count: Int { _value.nonzeroBitCount }
@inlinable @inline(__always)
internal var capacity: Int { Value.bitWidth }
@inlinable @inline(__always)
internal var isEmpty: Bool { _value == 0 }
@inlinable @inline(__always)
internal var hasExactlyOneMember: Bool {
_value != 0 && _value & (_value &- 1) == 0
}
@inlinable @inline(__always)
internal var first: _Bucket? {
guard !isEmpty else { return nil }
return _Bucket(
_value: UInt8(truncatingIfNeeded: _value.trailingZeroBitCount))
}
@inlinable @inline(__always)
internal mutating func popFirst() -> _Bucket? {
guard let bucket = first else { return nil }
_value &= _value &- 1 // Clear lowest nonzero bit.
return bucket
}
}
extension _Bitmap {
@inlinable @inline(__always)
internal func contains(_ bucket: _Bucket) -> Bool {
assert(bucket.value < capacity)
return _value & (1 &<< bucket.value) != 0
}
@inlinable @inline(__always)
internal mutating func insert(_ bucket: _Bucket) {
assert(bucket.value < capacity)
_value |= (1 &<< bucket.value)
}
@inlinable @inline(__always)
internal func inserting(_ bucket: _Bucket) -> _Bitmap {
assert(bucket.value < capacity)
return _Bitmap(_value: _value | (1 &<< bucket.value))
}
@inlinable @inline(__always)
internal mutating func remove(_ bucket: _Bucket) {
assert(bucket.value < capacity)
_value &= ~(1 &<< bucket.value)
}
@inlinable @inline(__always)
internal func removing(_ bucket: _Bucket) -> _Bitmap {
assert(bucket.value < capacity)
return _Bitmap(_value: _value & ~(1 &<< bucket.value))
}
@inlinable @inline(__always)
internal func slot(of bucket: _Bucket) -> _HashSlot {
_HashSlot(_value._rank(ofBit: bucket.value))
}
@inlinable @inline(__always)
internal func bucket(at slot: _HashSlot) -> _Bucket {
_Bucket(_value._bit(ranked: slot.value)!)
}
}
extension _Bitmap {
@inlinable @inline(__always)
internal func isSubset(of other: Self) -> Bool {
_value & ~other._value == 0
}
@inlinable @inline(__always)
internal func isDisjoint(with other: Self) -> Bool {
_value & other._value == 0
}
@inlinable @inline(__always)
internal func union(_ other: Self) -> Self {
Self(_value: _value | other._value)
}
@inlinable @inline(__always)
internal func intersection(_ other: Self) -> Self {
Self(_value: _value & other._value)
}
@inlinable @inline(__always)
internal func symmetricDifference(_ other: Self) -> Self {
Self(_value: _value ^ other._value)
}
@inlinable @inline(__always)
internal func subtracting(_ other: Self) -> Self {
Self(_value: _value & ~other._value)
}
}
extension _Bitmap: Sequence {
@usableFromInline
internal typealias Element = (bucket: _Bucket, slot: _HashSlot)
@usableFromInline
@frozen
internal struct Iterator: IteratorProtocol {
@usableFromInline
internal var bitmap: _Bitmap
@usableFromInline
internal var slot: _HashSlot
@inlinable
internal init(_ bitmap: _Bitmap) {
self.bitmap = bitmap
self.slot = .zero
}
/// Return the index of the lowest set bit in this word,
/// and also destructively clear it.
@inlinable
internal mutating func next() -> Element? {
guard let bucket = bitmap.popFirst() else { return nil }
defer { slot = slot.next() }
return (bucket, slot)
}
}
@inlinable
internal var underestimatedCount: Int { count }
@inlinable
internal func makeIterator() -> Iterator {
Iterator(self)
}
}