mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
8dda2274bc
# Motivation For AsyncStream we created a custom internal Deque implementation to use for the buffering. This implementation was relatively bare-bones compared to the one in swift-collections. Furthermore, it lacked some methods that we need to implement the new `AsyncStream` APIs that support producer backpressure. # Modification This PR copies over the Deque implementation of swift-collections and makes it internal and non-inlinable. # Result We now have a fully functional Deque.
106 lines
4.4 KiB
Swift
106 lines
4.4 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift.org open source project
|
|
//
|
|
// Copyright (c) 2021 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
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
/// This file is copied from swift-collections and should not be modified here.
|
|
/// Rather all changes should be made to swift-collections and copied back.
|
|
|
|
import Swift
|
|
|
|
/// A collection implementing a double-ended queue. `Deque` (pronounced "deck")
|
|
/// implements an ordered random-access collection that supports efficient
|
|
/// insertions and removals from both ends.
|
|
///
|
|
/// var colors: Deque = ["red", "yellow", "blue"]
|
|
///
|
|
/// Deques implement the same indexing semantics as arrays: they use integer
|
|
/// indices, and the first element of a nonempty deque is always at index zero.
|
|
/// Like arrays, deques conform to `RangeReplaceableCollection`,
|
|
/// `MutableCollection` and `RandomAccessCollection`, providing a familiar
|
|
/// interface for manipulating their contents:
|
|
///
|
|
/// print(colors[1]) // "yellow"
|
|
/// print(colors[3]) // Runtime error: Index out of range
|
|
///
|
|
/// colors.insert("green", at: 1)
|
|
/// // ["red", "green", "yellow", "blue"]
|
|
///
|
|
/// colors.remove(at: 2) // "yellow"
|
|
/// // ["red", "green", "blue"]
|
|
///
|
|
/// Like all variable-size collections on the standard library, `Deque`
|
|
/// implements value semantics: each deque has an independent value that
|
|
/// includes the values of its elements. Modifying one deque does not affect any
|
|
/// others:
|
|
///
|
|
/// var copy = deque
|
|
/// copy[1] = "violet"
|
|
/// print(copy) // ["red", "violet", "blue"]
|
|
/// print(deque) // ["red", "green", "blue"]
|
|
///
|
|
/// This is implemented with the copy-on-write optimization. Multiple copies of
|
|
/// a deque share the same underlying storage until you modify one of the
|
|
/// copies. When that happens, the deque being modified replaces its storage
|
|
/// with a uniquely owned copy of itself, which is then modified in place.
|
|
///
|
|
/// `Deque` stores its elements in a circular buffer, which allows efficient
|
|
/// insertions and removals at both ends of the collection; however, this comes
|
|
/// at the cost of potentially discontiguous storage. In contrast, `Array` is
|
|
/// (usually) backed by a contiguous buffer, where new data can be efficiently
|
|
/// appended to the end, but inserting at the front is relatively slow, as
|
|
/// existing elements need to be shifted to make room.
|
|
///
|
|
/// This difference in implementation means that while the interface of a deque
|
|
/// is very similar to an array, the operations have different performance
|
|
/// characteristics. Mutations near the front are expected to be significantly
|
|
/// faster in deques, but arrays may measure slightly faster for general
|
|
/// random-access lookups.
|
|
///
|
|
/// Deques provide a handful of additional operations that make it easier to
|
|
/// insert and remove elements at the front. This includes queue operations such
|
|
/// as `popFirst` and `prepend`, including the ability to directly prepend a
|
|
/// sequence of elements:
|
|
///
|
|
/// colors.append("green")
|
|
/// colors.prepend("orange")
|
|
/// // colors: ["orange", "red", "blue", "yellow", "green"]
|
|
///
|
|
/// colors.popLast() // "green"
|
|
/// colors.popFirst() // "orange"
|
|
/// // colors: ["red", "blue", "yellow"]
|
|
///
|
|
/// colors.prepend(contentsOf: ["purple", "teal"])
|
|
/// // colors: ["purple", "teal", "red", "blue", "yellow"]
|
|
///
|
|
/// Unlike arrays, deques do not currently provide direct unsafe access to their
|
|
/// underlying storage. They also lack a `capacity` property -- the size of the
|
|
/// storage buffer at any given point is an unstable implementation detail that
|
|
/// should not affect application logic. (However, deques do provide a
|
|
/// `reserveCapacity` method.)
|
|
struct _Deque<Element> {
|
|
internal typealias _Slot = _DequeSlot
|
|
|
|
internal var _storage: _Storage
|
|
|
|
internal init(_storage: _Storage) {
|
|
self._storage = _storage
|
|
}
|
|
|
|
/// Creates and empty deque with preallocated space for at least the specified
|
|
/// number of elements.
|
|
///
|
|
/// - Parameter minimumCapacity: The minimum number of elements that the
|
|
/// newly created deque should be able to store without reallocating its
|
|
/// storage buffer.
|
|
init(minimumCapacity: Int) {
|
|
self._storage = _Storage(minimumCapacity: minimumCapacity)
|
|
}
|
|
}
|