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