mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
304 lines
8.4 KiB
Swift
304 lines
8.4 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 2021 - 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
|
|
|
|
@frozen
|
|
@usableFromInline
|
|
@unsafe
|
|
internal struct _UnsafeDequeSegments<Element: ~Copyable> {
|
|
@usableFromInline
|
|
internal let first: UnsafeBufferPointer<Element>
|
|
|
|
@usableFromInline
|
|
internal let second: UnsafeBufferPointer<Element>?
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal init(
|
|
_ first: UnsafeBufferPointer<Element>,
|
|
_ second: UnsafeBufferPointer<Element>? = nil
|
|
) {
|
|
unsafe self.first = first
|
|
unsafe self.second = second
|
|
assert(unsafe first.count > 0 || second == nil)
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal init(
|
|
start: UnsafePointer<Element>,
|
|
count: Int
|
|
) {
|
|
unsafe self.init(UnsafeBufferPointer(start: start, count: count))
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal init(
|
|
first start1: UnsafePointer<Element>,
|
|
count count1: Int,
|
|
second start2: UnsafePointer<Element>,
|
|
count count2: Int
|
|
) {
|
|
unsafe self.init(
|
|
UnsafeBufferPointer(start: start1, count: count1),
|
|
UnsafeBufferPointer(start: start2, count: count2))
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal var count: Int { unsafe first.count + (second?.count ?? 0) }
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
@safe
|
|
internal func isIdentical(to other: Self) -> Bool {
|
|
guard unsafe self.first._isIdentical(to: other.first) else { return false }
|
|
switch (unsafe self.second, unsafe other.second) {
|
|
case (nil, nil): return true
|
|
case let (a?, b?): return a._isIdentical(to: b)
|
|
default: return false
|
|
}
|
|
}
|
|
}
|
|
|
|
@frozen
|
|
@usableFromInline
|
|
@unsafe
|
|
internal struct _UnsafeMutableDequeSegments<Element: ~Copyable> {
|
|
@usableFromInline
|
|
internal let first: UnsafeMutableBufferPointer<Element>
|
|
|
|
@usableFromInline
|
|
internal let second: UnsafeMutableBufferPointer<Element>?
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal init() {
|
|
unsafe self.first = .init(start: nil, count: 0)
|
|
unsafe self.second = nil
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal init(
|
|
_ first: UnsafeMutableBufferPointer<Element>,
|
|
_ second: UnsafeMutableBufferPointer<Element>? = nil
|
|
) {
|
|
unsafe self.first = first
|
|
unsafe self.second = second?.count == 0 ? nil : second
|
|
assert(unsafe first.count > 0 || second == nil)
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal init(
|
|
start: UnsafeMutablePointer<Element>,
|
|
count: Int
|
|
) {
|
|
unsafe self.init(UnsafeMutableBufferPointer(start: start, count: count))
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal init(
|
|
first start1: UnsafeMutablePointer<Element>,
|
|
count count1: Int,
|
|
second start2: UnsafeMutablePointer<Element>,
|
|
count count2: Int
|
|
) {
|
|
unsafe self.init(
|
|
UnsafeMutableBufferPointer(start: start1, count: count1),
|
|
UnsafeMutableBufferPointer(start: start2, count: count2))
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal init(mutating buffer: _UnsafeDequeSegments<Element>) {
|
|
unsafe self.init(
|
|
.init(mutating: buffer.first),
|
|
buffer.second.map { unsafe .init(mutating: $0) })
|
|
}
|
|
}
|
|
|
|
extension _UnsafeMutableDequeSegments {
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal init(
|
|
_ first: UnsafeMutableBufferPointer<Element>.SubSequence,
|
|
_ second: UnsafeMutableBufferPointer<Element>? = nil
|
|
) {
|
|
unsafe self.init(UnsafeMutableBufferPointer(rebasing: first), second)
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal init(
|
|
_ first: UnsafeMutableBufferPointer<Element>,
|
|
_ second: UnsafeMutableBufferPointer<Element>.SubSequence
|
|
) {
|
|
unsafe self.init(first, UnsafeMutableBufferPointer(rebasing: second))
|
|
}
|
|
}
|
|
|
|
extension _UnsafeMutableDequeSegments where Element: ~Copyable {
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal var count: Int { unsafe first.count + (second?.count ?? 0) }
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal func prefix(_ n: Int) -> Self {
|
|
assert(n >= 0)
|
|
if unsafe n >= self.count {
|
|
return unsafe self
|
|
}
|
|
if unsafe n <= first.count {
|
|
return unsafe Self(first._extracting(first: n))
|
|
}
|
|
return unsafe Self(first, second!._extracting(first: n - first.count))
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal func suffix(_ n: Int) -> Self {
|
|
assert(n >= 0)
|
|
if unsafe n >= self.count {
|
|
return unsafe self
|
|
}
|
|
guard let second = unsafe second else {
|
|
return unsafe Self(first._extracting(last: n))
|
|
}
|
|
if n <= second.count {
|
|
return unsafe Self(second._extracting(last: n))
|
|
}
|
|
return unsafe Self(first._extracting(last: n - second.count), second)
|
|
}
|
|
}
|
|
|
|
extension _UnsafeMutableDequeSegments where Element: ~Copyable {
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
@unsafe
|
|
internal func deinitialize() {
|
|
unsafe first._deinitializeElements()
|
|
unsafe second?._deinitializeElements()
|
|
}
|
|
}
|
|
|
|
extension _UnsafeMutableDequeSegments {
|
|
@discardableResult
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal func initialize<I: IteratorProtocol>(
|
|
copyingPrefixOf iterator: inout I
|
|
) -> Int
|
|
where I.Element == Element {
|
|
var copied = 0
|
|
var gap = unsafe first
|
|
var wrapped = false
|
|
while true {
|
|
if copied == gap.count {
|
|
guard !wrapped, let second = unsafe second, second.count > 0 else { break }
|
|
unsafe gap = second
|
|
copied = 0
|
|
wrapped = true
|
|
}
|
|
guard let next = iterator.next() else { break }
|
|
unsafe (gap.baseAddress! + copied).initialize(to: next)
|
|
copied += 1
|
|
}
|
|
return wrapped ? unsafe first.count + copied : copied
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal func initialize<S: Sequence>(
|
|
fromSequencePrefix elements: __owned S
|
|
) -> (iterator: S.Iterator, count: Int)
|
|
where S.Element == Element {
|
|
guard unsafe second == nil || first.count >= elements.underestimatedCount else {
|
|
var it = elements.makeIterator()
|
|
let copied = unsafe initialize(copyingPrefixOf: &it)
|
|
return (it, copied)
|
|
}
|
|
// Note: Array._copyContents traps when not given enough space, so we
|
|
// need to check if we have enough contiguous space available above.
|
|
//
|
|
// FIXME: Add support for segmented (a.k.a. piecewise contiguous)
|
|
// collections to the stdlib.
|
|
var (it, copied) = unsafe elements._copyContents(initializing: first)
|
|
if unsafe copied == first.count, let second = unsafe second {
|
|
var i = 0
|
|
while i < second.count {
|
|
guard let next = it.next() else { break }
|
|
unsafe (second.baseAddress! + i).initialize(to: next)
|
|
i += 1
|
|
}
|
|
copied += i
|
|
}
|
|
return (it, copied)
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal func initialize(
|
|
copying elements: UnsafeBufferPointer<Element>
|
|
) {
|
|
assert(unsafe self.count == elements.count)
|
|
if let second = unsafe second {
|
|
let wrap = unsafe first.count
|
|
unsafe first.initializeAll(fromContentsOf: elements._extracting(first: wrap))
|
|
unsafe second.initializeAll(fromContentsOf: elements._extracting(last: second.count))
|
|
} else {
|
|
unsafe first.initializeAll(fromContentsOf: elements)
|
|
}
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal func initialize(
|
|
copying elements: UnsafeMutableBufferPointer<Element>
|
|
) {
|
|
unsafe self.initialize(copying: UnsafeBufferPointer(elements))
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal func initialize(
|
|
copying elements: __owned some Collection<Element>
|
|
) {
|
|
assert(unsafe self.count == elements.count)
|
|
if let second = unsafe second {
|
|
let wrap = unsafe elements.index(elements.startIndex, offsetBy: first.count)
|
|
unsafe first.initializeAll(fromContentsOf: elements[..<wrap])
|
|
unsafe second.initializeAll(fromContentsOf: elements[wrap...])
|
|
} else {
|
|
unsafe first.initializeAll(fromContentsOf: elements)
|
|
}
|
|
}
|
|
|
|
@_alwaysEmitIntoClient
|
|
@_transparent
|
|
internal func reassign<C: Collection>(
|
|
copying elements: C
|
|
) where C.Element == Element {
|
|
assert(unsafe elements.count == self.count)
|
|
unsafe deinitialize()
|
|
unsafe initialize(copying: elements)
|
|
}
|
|
}
|