mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
Don’t just append new items to the end of storage — it misleads clients into assuming that the containers preserve insertion order, when they most certainly don’t do that. Instead, insert new items into the middle of storage, using an extra swap.
88 lines
2.5 KiB
Swift
88 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
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#if compiler(>=6.2)
|
|
extension _HTable {
|
|
@usableFromInline
|
|
internal mutating func insertNew_Small(
|
|
swapper: (Bucket) -> Void,
|
|
) -> Bucket {
|
|
assert(isSmall)
|
|
if _count > 0 {
|
|
// Scramble order by swapping the new item in the middle of the table.
|
|
swapper(Bucket(offset: _count / 2))
|
|
}
|
|
let r = Bucket(offset: _count)
|
|
_count &+= 1
|
|
_maxProbeLength = _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.firstUnoccupiedBucket(from: ideal)
|
|
if actual._offset >= self.bucketCount {
|
|
actual = bitmap.firstUnoccupiedBucket(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)
|
|
_count &+= 1
|
|
if probeLength > _maxProbeLength {
|
|
_maxProbeLength = probeLength
|
|
}
|
|
return b
|
|
#endif
|
|
}
|
|
}
|
|
#endif
|