Я всегда думал: «А зачем нужно писать свой copy-on-write? Ведь круто, когда есть структуры и они такие быстрые, что всё делают за тебя.»

Но все это не нужно, пока не начинаешь писать свои типы и не подсаживаешься на LinkedList’ы.

Что такое этот связанный список и какие у него преимущества?

Связанный список имеет несколько теоретических преимуществ по сравнению с вариантами непрерывного хранения, такими как Array:

• Связанные списки имеют временную сложность O (1) для вставки первых элементов. Массивы же имеют временную сложность O (n).

• Соответствие протоколам сбора Swift, таким как Sequence и Collection, предлагает множество полезных методов для довольно небольшого количества требований.

Связанный список (Linked List) — это последовательность элементов данных, в которой каждый элемент называется узлом (Node).

Есть два основных типа связанных списков:

Односвязные списки — это связанные списки, в которых каждый узел имеет ссылку только на следующий узел.

Двусвязные списки — это связанные списки, в которых каждый узел имеет ссылку на предыдущий и следующий узел.

Вам нужно отслеживать, где список начинается и где заканчивается. Обычно это делается с помощью указателей, называемых head и tail.

Вот так это всё выглядит:

public class Node<Value> {   public var value: Value   public var next: Node?        public init(value: Value, next: Node? = nil) {     self.value = value     self.next = next   } }  public struct LinkedList<Value> {   public var head: Node<Value>?   public var tail: Node<Value>?      public init() {}    public var isEmpty: Bool { head == nil } } 

Вау, прикольная структура данных! Она знает и предыдущий, и следующий элемент. Также в списке мы быстро можем добавить. Но есть проблема.

Так как наша Node’a является классом, а значит и reference type. Это значит, что для многих узлов у нас есть общая ячейка памяти и куча ссылок на них. Они могут расти и с большими размера за ними сложно наблюдать.

Как решить эту проблему? Поскольку LinkedList является структурой и поэтому должен использовать семантику значений. Внедрение своего COW решит эту проблему.

Сделать value type значений с помощью COW довольно просто. Прежде чем изменять содержимое связанного списка, вы хотим создать копию базового хранилища и обновить все ссылки (начальные и конечные) на новую копию.

private mutating func copyNodes() {   guard var oldNode = head else {       return   }   head = Node(value: oldNode.value)   var newNode = head      while let nextOldNode = oldNode.next {     newNode!.next = Node(value: nextOldNode.value)     newNode = newNode!.next     oldNode = nextOldNode   }   tail = newNode }

Этот метод заменит существующие узлы связанного списка вновь выделенными узлами с тем же значением. Здесь всё очень круто, кроме введения накладных расходов O (n) на каждый вызов изменения…

Оптимизируем COW

Накладные расходы O (n) при каждом вызове изменения недопустимы.

Есть два пути, которые помогают решить эту проблему. Первый — избегать копирования, когда у узлов только один владелец.

isKnownUniquelyReferenced

В стандартной библиотеке Swift существует функция isKnownUniquelyReferenced. Эта функция может использоваться, чтобы определить, имеет ли объект ровно одну ссылку на него.

И если добавить в начало функции copyNodes() код, то копировать дальше не надо:

private mutating func copyNodes(returningCopyOf node: Node<Value>?) -> Node<Value>? {   guard !isKnownUniquelyReferenced(&head) else { return nil   }   guard var oldNode = head else { return nil }   head = Node(value: oldNode.value)   var newNode = head   var nodeCopy: Node<Value>?   while let nextOldNode = oldNode.next {     if oldNode === node {       nodeCopy = newNode     }     newNode!.next = Node(value: nextOldNode.value)     newNode = newNode!.next     oldNode = nextOldNode }   return nodeCopy }

Этот метод имеет много общего с предыдущей реализацией. Основное отличие состоит в том, что он вернет вновь скопированный узел на основе переданного параметра.

Таким образом Copy-on-write не является чем-то далеким и подкапотным. А вполне управляемым и понятным.