1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2023 - 2024 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
//
//===----------------------------------------------------------------------===//
extension Rope {
@inlinable
public mutating func append(_ item: __owned Element) {
_invalidateIndices()
if _root == nil {
_root = .createLeaf(_Item(item))
return
}
if let spawn = root.append(_Item(item)) {
_root = .createInner(children: root, spawn)
}
}
}
extension Rope._Node {
@inlinable
internal mutating func append(_ item: __owned _Item) -> Self? {
var item = item
if item.isUndersized, !self.isEmpty, self.lastItem.rebalance(nextNeighbor: &item) {
return nil
}
ensureUnique()
if height > 0 {
var summary = self.summary
let spawn = updateInner {
let p = $0.mutableChildPtr(at: $0.childCount - 1)
summary.subtract(p.pointee.summary)
let spawn = p.pointee.append(item)
summary.add(p.pointee.summary)
return spawn
}
self.summary = summary
guard let spawn = spawn else { return nil }
#if true // Compress existing nodes if possible.
updateInner {
let c = $0.mutableChildren
let s = c[c.count - 2].childCount + c[c.count - 1].childCount
if s <= Summary.maxNodeSize {
Self.redistributeChildren(&c[c.count - 2], &c[c.count - 1], to: s)
let removed = $0._removeChild(at: c.count - 1)
assert(removed.childCount == 0)
}
}
#endif
guard isFull else {
_appendNode(spawn)
return nil
}
var spawn2 = split(keeping: Summary.minNodeSize)
spawn2._appendNode(spawn)
return spawn2
}
guard isFull else {
_appendItem(item)
return nil
}
var spawn = split(keeping: Summary.minNodeSize)
spawn._appendItem(item)
return spawn
}
}
|
