mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
86 lines
2.5 KiB
Swift
86 lines
2.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
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
extension _HTable {
|
|
@usableFromInline
|
|
internal mutating func insertNew_Small(
|
|
swapper: (Bucket) -> Void,
|
|
) -> Bucket {
|
|
assert(isSmall)
|
|
if self.count > 0 {
|
|
// Scramble order by swapping the new item in the middle of the table.
|
|
swapper(Bucket(offset: self.count / 2))
|
|
}
|
|
let r = Bucket(offset: self.count)
|
|
unsafe _count &+= 1
|
|
_maxProbeLength = self.count
|
|
return r
|
|
}
|
|
|
|
|
|
@usableFromInline
|
|
internal mutating func insertNew_Large(
|
|
hashValue: Int,
|
|
hashGenerator: (Bucket) -> Int,
|
|
swapper: (Bucket) -> Void,
|
|
) -> Bucket {
|
|
assert(!isSmall)
|
|
assert(!isFull)
|
|
|
|
#if COLLECTIONS_NO_ROBIN_HOOD_HASHING
|
|
let ideal = idealBucket(forHashValue: hashValue)
|
|
let bitmap = self.bitmap
|
|
var actual = bitmap.collisionChainEnd(from: ideal)
|
|
if actual._offset >= self.bucketCount {
|
|
actual = bitmap.collisionChainEnd(from: Bucket(offset: 0))
|
|
}
|
|
bitmap.setOccupied(actual)
|
|
let probeLength = self.probeLength(from: ideal, to: actual)
|
|
_maxProbeLength = Swift.max(_maxProbeLength, probeLength)
|
|
_count &+= 1
|
|
return actual
|
|
#else
|
|
var b = idealBucket(forHashValue: hashValue)
|
|
var probeLength = 1
|
|
if bitmap.isOccupied(b) {
|
|
// Shortcut: In the first iteration, we're at the minimum possible probe
|
|
// length, so there is no possible way we'd replace the current item.
|
|
// There is no point hashing it.
|
|
self.wrapBucket(after: &b)
|
|
probeLength &+= 1
|
|
}
|
|
while bitmap.isOccupied(b) {
|
|
let oldHashValue = hashGenerator(b)
|
|
let oldProbeLength = self.probeLength(
|
|
forHashValue: oldHashValue,
|
|
in: b)
|
|
if probeLength > oldProbeLength {
|
|
swapper(b)
|
|
if probeLength > _maxProbeLength {
|
|
_maxProbeLength = probeLength
|
|
}
|
|
probeLength = oldProbeLength
|
|
}
|
|
self.wrapBucket(after: &b)
|
|
probeLength &+= 1
|
|
}
|
|
bitmap.setOccupied(b)
|
|
unsafe _count &+= 1
|
|
if probeLength > _maxProbeLength {
|
|
_maxProbeLength = probeLength
|
|
}
|
|
return b
|
|
#endif
|
|
}
|
|
}
|