mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
165 lines
5.1 KiB
Swift
165 lines
5.1 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 {
|
|
/// The minimum hash table scale.
|
|
@_alwaysEmitIntoClient
|
|
@safe
|
|
package static var minimumScale: UInt8 {
|
|
@_effects(readnone)
|
|
@_transparent
|
|
get {
|
|
4
|
|
}
|
|
}
|
|
|
|
/// The maximum hash table scale.
|
|
@_alwaysEmitIntoClient
|
|
@safe
|
|
package static var maximumScale: UInt8 {
|
|
@_effects(readnone)
|
|
@_transparent
|
|
get {
|
|
Swift.min(UInt8(truncatingIfNeeded: Int.bitWidth) &- 1, 56)
|
|
}
|
|
}
|
|
|
|
/// The maximum number of items for which we do not create a hash table.
|
|
@usableFromInline
|
|
@safe
|
|
package static var maximumUnhashedCount: Int {
|
|
@_effects(readnone)
|
|
get {
|
|
maximumCapacity(forScale: 0)
|
|
}
|
|
}
|
|
|
|
@inlinable
|
|
@inline(__always)
|
|
@safe
|
|
package static func wordCount(forScale scale: UInt8) -> Int {
|
|
guard scale > 0 else { return 0 }
|
|
let shift = Swift.max(UInt(scale), Word.wordShift) - Word.wordShift
|
|
return 1 &<< shift
|
|
}
|
|
|
|
// These specific parameters result in the following capacity ranges:
|
|
//
|
|
// Scale Capacity range
|
|
// 4 2 ... 14
|
|
// 5 4 ... 28
|
|
// 6 8 ... 56
|
|
// 7 16 ... 112
|
|
// 8 32 ... 224
|
|
// 9 64 ... 448
|
|
// 10 128 ... 896
|
|
// 11 256 ... 1792
|
|
// 12 512 ... 3584
|
|
// etc.
|
|
//
|
|
// Note how neighboring intervals overlap significantly, as far as two steps
|
|
// away. This provides hysteresis for storage capacities, preventing hash
|
|
// tables from repeatedly shrinking/growing when only a handful of items are
|
|
// added/removed in a loop.
|
|
|
|
/// The numerator of the maximum hash table load factor.
|
|
@_transparent
|
|
@safe
|
|
internal static var _maxLFNum: UInt { 7 }
|
|
|
|
/// The denominator of the maximum hash table load factor.
|
|
@_transparent
|
|
@safe
|
|
internal static var _maxLFDenom: UInt { 8 }
|
|
|
|
/// The numerator of the minimum hash table load factor.
|
|
@_transparent
|
|
@safe
|
|
internal static var _minLFNum: UInt { 1 }
|
|
|
|
/// The denominator of minimum hash table load factor.
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
@safe
|
|
internal static var _minLFDenom: UInt { 8 }
|
|
|
|
/// The minimum number of items that can be held in a hash table of the given scale.
|
|
@usableFromInline
|
|
@_effects(readnone)
|
|
@safe
|
|
package static func minimumCapacity(forScale scale: UInt8) -> Int {
|
|
guard scale >= minimumScale else { return 0 }
|
|
precondition(scale <= maximumScale)
|
|
let bucketCount: UInt = 1 &<< scale
|
|
return Int(bucketCount * _minLFNum / _minLFDenom)
|
|
}
|
|
|
|
/// The maximum number of items that can be held in a hash table of the given scale.
|
|
@usableFromInline
|
|
@_effects(readnone)
|
|
@safe
|
|
package static func maximumCapacity(forScale scale: UInt8) -> Int {
|
|
let scale = Swift.max(scale, minimumScale &- 1)
|
|
let bucketCount: UInt = 1 &<< scale
|
|
return Int(bucketCount * _maxLFNum / _maxLFDenom)
|
|
}
|
|
|
|
|
|
/// The minimum hash table scale that can hold the specified number of elements.
|
|
@usableFromInline
|
|
@_effects(readnone)
|
|
@safe
|
|
package static func minimumScale(forCapacity capacity: Int) -> UInt8 {
|
|
guard capacity > maximumUnhashedCount else { return 0 }
|
|
let capacity = UInt(truncatingIfNeeded: Swift.max(capacity, 1))
|
|
// Calculate the minimum number of entries we need to allocate to satisfy
|
|
// the maximum load factor.
|
|
let minimumEntries = Swift.max(
|
|
(capacity * _maxLFDenom + _maxLFNum - 1) / _maxLFNum, // (capacity / maxLoadFactor).rounded(.up)
|
|
capacity + 1)
|
|
// The actual number of entries we need to allocate is the lowest power of
|
|
// two greater than or equal to the minimum entry count. Calculate its
|
|
// exponent.
|
|
let scale = (Swift.max(minimumEntries, 2) - 1)._binaryLogarithm() + 1
|
|
assert(scale >= minimumScale && scale <= maximumScale)
|
|
// The scale is the exponent corresponding to the bucket count.
|
|
assert(self.maximumCapacity(forScale: UInt8(scale)) >= capacity)
|
|
return UInt8(truncatingIfNeeded: scale)
|
|
}
|
|
|
|
@usableFromInline
|
|
@_effects(readnone)
|
|
@safe
|
|
package static func dynamicStorageParameters(
|
|
minimumCapacity: Int
|
|
) -> (scale: UInt8, capacity: Int) {
|
|
let maximumUnhashedCount = self.maximumUnhashedCount
|
|
if minimumCapacity <= maximumUnhashedCount {
|
|
let c = Swift.min(
|
|
minimumCapacity._roundUpToPowerOfTwo(),
|
|
maximumUnhashedCount)
|
|
return (0, c)
|
|
}
|
|
let scale = minimumScale(forCapacity: minimumCapacity)
|
|
let capacity = maximumCapacity(forScale: scale)
|
|
assert(capacity >= minimumCapacity)
|
|
let storageCapacity: Int = 1 &<< scale
|
|
assert(capacity < storageCapacity) // We need at least one empty bucket.
|
|
return (scale, capacity)
|
|
}
|
|
}
|