1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2021 - 2024 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
//
//===----------------------------------------------------------------------===//
#if !COLLECTIONS_SINGLE_MODULE
import InternalCollectionsUtilities
#endif
/// A sorted collection of small nonnegative integers, implemented as an
/// uncompressed bitmap of as many bits as the value of the largest member.
///
/// Bit sets implement `SetAlgebra` and provide efficient implementations
/// for set operations based on standard binary logic operations.
///
/// See `BitArray` for an alternative form of the same underlying data
/// structure, treating it as a mutable random-access collection of `Bool`
/// values.
public struct BitSet {
@usableFromInline
internal var _storage: [_Word]
@usableFromInline
init(_rawStorage storage: [_Word]) {
self._storage = storage
_checkInvariants()
}
}
extension BitSet: Sendable {}
extension BitSet {
@inline(__always)
internal func _read<R>(
_ body: (_UnsafeHandle) throws -> R
) rethrows -> R {
try _storage.withUnsafeBufferPointer { words in
let handle = _UnsafeHandle(words: words, mutable: false)
return try body(handle)
}
}
@usableFromInline
internal var _capacity: UInt {
UInt(_storage.count) &* UInt(_Word.capacity)
}
internal mutating func _ensureCapacity(limit capacity: UInt) {
let desired = _UnsafeHandle.wordCount(forCapacity: capacity)
guard _storage.count < desired else { return }
_storage.append(
contentsOf: repeatElement(.empty, count: desired - _storage.count))
}
internal mutating func _ensureCapacity(forValue value: UInt) {
let desiredWord = _UnsafeHandle.Index(value).word
guard desiredWord >= _storage.count else { return }
_storage.append(
contentsOf:
repeatElement(.empty, count: desiredWord - _storage.count + 1))
}
internal mutating func _shrink() {
let suffix = _read { $0._emptySuffix() }
if suffix > 0 { _storage.removeLast(suffix) }
}
@inline(__always)
internal mutating func _update<R>(
_ body: (inout _UnsafeHandle) throws -> R
) rethrows -> R {
defer {
_checkInvariants()
}
return try _storage.withUnsafeMutableBufferPointer { words in
var handle = _UnsafeHandle(words: words, mutable: true)
return try body(&handle)
}
}
@inline(__always)
internal mutating func _updateThenShrink<R>(
_ body: (_ handle: inout _UnsafeHandle, _ shrink: inout Bool) throws -> R
) rethrows -> R {
var shrink = true
defer {
if shrink { _shrink() }
_checkInvariants()
}
return try _storage.withUnsafeMutableBufferPointer { words in
var handle = _UnsafeHandle(words: words, mutable: true)
return try body(&handle, &shrink)
}
}
}
|
