Files
Karoy Lorentey 537bf9cbfb Drop support for Swift 6.0 and 6.1
This allows the use of Span types without `#if compiler` guards.
2026-09-21 13:34:39 -07:00

169 lines
5.5 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
extension _HTable {
package func maxOccupiedRun() -> Int {
if isSmall { return self.count }
var maxOccupiedRun = 0
var it = self.makeBucketIterator()
var first = true
var wrap = 0
while let next = it.nextOccupiedRegion() {
if first, next.lowerBound.offset == 0 {
wrap = next._offsets.count
}
first = false
var c = next._offsets.count
if next.upperBound == self.endBucket {
c += wrap
}
maxOccupiedRun = max(maxOccupiedRun, c)
}
return maxOccupiedRun
}
package var _bitmapDescription: String {
let multiline = self.endBucket.offset > Word.capacity
var str = ""
if !self.isSmall {
let lastWord = self.endBucket.bit > 0 ? self.endBucket.word : self.endBucket.word - 1
var it = self.makeBucketIterator()
while !it.isAtEnd {
if it.currentBucket.isOnWordBoundary {
if multiline {
str += "\n "
str += it.currentBucket.word == lastWord ? "└╴" : "├╴"
str += "[" + String(it.currentBucket.offset)._lpad(8, with: "0") + "] "
} else {
str += " "
}
} else if it.currentBucket.bit % 8 == 0 {
str += "∙"
}
str.append(it.isOccupied ? "■" : "□")
it.advanceToNextBit()
}
}
return str
}
package func describe(
bitmap: Bool = false,
) -> String {
let bitmapDesc = bitmap ? self._bitmapDescription : ""
let multiline = bitmapDesc.unicodeScalars.contains("\n")
var s = "⌗ \(scale == 0 ? "small" : "large@\(scale)")"
s += "\(multiline ? "" : bitmapDesc) "
s += "\(count)/\(capacity)/\(bucketCount), "
s += "maxProbeLength: \(_maxProbeLength), "
s += "maxOccupiedRun: \(maxOccupiedRun())"
if !self.isSmall, multiline {
s += bitmapDesc
}
return s
}
package var description: String {
describe()
}
package func checkInvariants(
failureHandler: (String) -> Void,
hashGenerator: (Bucket) -> Int
) {
#if DEBUG
if self.count > self.capacity {
failureHandler("Count exceeds capacity (count: \(count), capacity: \(capacity))")
}
if self.capacity > self.storageCapacity {
failureHandler("Capacity exceeds storage capacity (capacity: \(capacity), storage: \(self.storageCapacity))")
}
if isSmall {
if self.capacity > _HTable.maximumUnhashedCount {
failureHandler("Oversized small table (capacity: \(self.capacity)")
}
if _maxProbeLength != self.count {
failureHandler(
"Invalid max probe length for small table (count: \(self.count), mpl: \(self._maxProbeLength)")
}
return
}
// large
let c = bitmap.occupiedCount()
if c != self.count {
failureHandler("Count does not match bitmap count (count: \(self.count), bitmap: \(c))")
}
guard c > 0 else { return }
// Start iterating from the first empty bucket, wrapping around once
var it = self.makeBucketIterator()
it.advanceToUnoccupied()
if it.isAtEnd {
failureHandler("No unoccupied bucket in large hash table")
return
}
var end: Bucket? = nil
var maxProbeLength = 0
while true {
it.wrapToOccupied()
if end == nil {
it = makeBucketIterator(from: it.currentBucket) // Reset wrapped state
end = it.currentBucket
} else if end == it.currentBucket {
break
}
let chainStart = it.currentBucket
#if !COLLECTIONS_NO_ROBIN_HOOD_HASHING
var probeLength = 1
#endif
while it.isOccupied {
let hash = hashGenerator(it.currentBucket)
let ideal = self.idealBucket(forHashValue: hash)
if (chainStart <= it.currentBucket
? ideal < chainStart || ideal > it.currentBucket
: ideal > it.currentBucket && ideal < chainStart) {
failureHandler("Unreachable item: not on the correct chain (bucket: \(it.currentBucket), ideal: \(ideal)")
}
let pl = self.probeLength(from: ideal, to: it.currentBucket)
if pl > _maxProbeLength {
failureHandler("Unreachable item: probe length exceeds max (bucket: \(it.currentBucket), probeLength: \(pl), maxProbeLength: \(_maxProbeLength)")
}
maxProbeLength = Swift.max(pl, maxProbeLength)
#if !COLLECTIONS_NO_ROBIN_HOOD_HASHING
// No item in ideal ..< current should have a shorter probe length than
// the current item would have in that position.
if pl > probeLength {
failureHandler(
"Item is misplaced in its chain (bucket: \(it.currentBucket), probeLength: \(pl) > \(probeLength))"
)
}
probeLength = Swift.min(pl, probeLength) + 1
#endif
it.wrapToNextBit()
}
}
if maxProbeLength > _maxProbeLength {
// Note: the actual mpl can be lower than the estimate, due to removals.
failureHandler(
"Bad maximum probe length (stored: \(_maxProbeLength), actual: \(maxProbeLength))")
}
#endif
}
}