mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
125 lines
3.0 KiB
Swift
125 lines
3.0 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 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
|
|
|
|
#if compiler(>=6.2)
|
|
extension _HTable {
|
|
@usableFromInline
|
|
@frozen
|
|
package struct Bitmap: ~Copyable, ~Escapable {
|
|
@usableFromInline
|
|
package typealias Bucket = _HTable.Bucket
|
|
|
|
@_alwaysEmitIntoClient
|
|
package let _words: UnsafeMutableBufferPointer<Word>
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_lifetime(borrow table)
|
|
package init(table: borrowing _HTable) {
|
|
self._words = .init(start: table._bitmap, count: table.wordCount)
|
|
}
|
|
}
|
|
}
|
|
|
|
extension _HTable.Bitmap {
|
|
@_transparent
|
|
@inlinable
|
|
package func isValid(_ bucket: Bucket) -> Bool {
|
|
bucket.word < _words.count
|
|
}
|
|
|
|
@_transparent
|
|
@inlinable
|
|
package func isOccupied(_ bucket: Bucket) -> Bool {
|
|
assert(isValid(bucket))
|
|
return _words[bucket.word].contains(bucket.bit)
|
|
}
|
|
|
|
@_transparent
|
|
@inlinable
|
|
package func setOccupied(_ bucket: Bucket) {
|
|
assert(isValid(bucket))
|
|
_words[bucket.word].set(bucket.bit)
|
|
}
|
|
|
|
@_transparent
|
|
@inlinable
|
|
package func clearOccupied(_ bucket: Bucket) {
|
|
assert(isValid(bucket))
|
|
_words[bucket.word].clear(bucket.bit)
|
|
}
|
|
|
|
@_transparent
|
|
@inlinable
|
|
package func clearAll() {
|
|
_words.update(repeating: .empty)
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
package func occupiedCount() -> Int {
|
|
var c = 0
|
|
for i in 0 ..< _words.count {
|
|
c += _words[i].count
|
|
}
|
|
return c
|
|
}
|
|
|
|
@inlinable
|
|
package func firstOccupiedBucket(from start: Bucket) -> Bucket? {
|
|
assert(isValid(start))
|
|
|
|
var word = start.word
|
|
var bits = _words[word]
|
|
bits.removeAll(upTo: start.bit)
|
|
|
|
while true {
|
|
if let bit = bits.firstMember {
|
|
return Bucket(word: word, bit: bit)
|
|
}
|
|
word &+= 1
|
|
if word >= _words.count {
|
|
return nil
|
|
}
|
|
bits = _words[word]
|
|
}
|
|
}
|
|
|
|
/// Note: If the bitmap has fewer than Word.capacity bits, then this may
|
|
/// report an unoccupied bit beyond the end of its actual size.
|
|
@inlinable
|
|
package func firstUnoccupiedBucket(from start: Bucket) -> Bucket {
|
|
assert(isValid(start))
|
|
var word = start.word
|
|
var bits = _words[word]
|
|
bits.insertAll(upTo: start.bit)
|
|
var wrapped = false
|
|
while true {
|
|
bits.formComplement()
|
|
if let bit = bits.firstMember {
|
|
return Bucket(word: word, bit: bit)
|
|
}
|
|
word &+= 1
|
|
if word >= _words.count {
|
|
precondition(!wrapped, "Corrupt hash table")
|
|
wrapped = true
|
|
word = 0
|
|
}
|
|
bits = _words[word]
|
|
}
|
|
}
|
|
}
|
|
#endif
|