mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
171 lines
5.5 KiB
Swift
171 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
|
|
|
|
#if compiler(>=6.2)
|
|
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
|
|
}
|
|
}
|
|
#endif
|