//===----------------------------------------------------------------------===// // // 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