Remove hole
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
// (peerId, Message.Namespace, MessageHistoryHoleSpace, ClosedRange<MessageId.Id>)
private func removeInternal(peerId: PeerId, namespace: MessageId.Namespace, space: MessageHistoryHoleSpace, range: ClosedRange<MessageId.Id>, operations: inout [MessageHistoryIndexHoleOperationKey: [MessageHistoryIndexHoleOperation]]) {
var removedIndices = IndexSet()
var insertedIndices = IndexSet()
var removeKeys: [Int32] = []
var insertRanges = IndexSet()
func processRange(_ key: ValueBoxKey, _ value: ReadBuffer) {
let (upperId, keySpace) = decomposeKey(key)
assert(keySpace == space)
assert(upperId.peerId == peerId)
assert(upperId.namespace == namespace)
let lowerId = decodeValue(value: value, peerId: peerId, namespace: namespace)
let holeRange: ClosedRange<MessageId.Id> = lowerId.id ... upperId.id
if range.lowerBound <= holeRange.lowerBound && range.upperBound >= holeRange.upperBound {
// 完全包含在range内，可以直接移除
removeKeys.append(upperId.id)
} else if range.overlaps(holeRange) {
// 与range有部分交集
// 可以移除
// 同时还需要重新添加不在range的部分
removeKeys.append(upperId.id)
var holeIndices = IndexSet(integersIn: Int(holeRange.lowerBound) ... Int(holeRange.upperBound))
holeIndices.remove(integersIn: Int(range.lowerBound) ... Int(range.upperBound))
insertRanges.formUnion(holeIndices)
}
}
let lowerScanBound = max(0, range.lowerBound - 2)
self.valueBox.range(self.table, start: self.key(id: MessageId(peerId: peerId, namespace: namespace, id: lowerScanBound), space: space), end: self.key(id: MessageId(peerId: peerId, namespace: namespace, id: range.upperBound), space: space).successor, values: { key, value in
processRange(key, value)
return true
}, limit: 0)
self.valueBox.range(self.table, start: self.key(id: MessageId(peerId: peerId, namespace: namespace, id: range.upperBound), space: space), end: self.upperBound(peerId: peerId, namespace: namespace, space: space), values: { key, value in
processRange(key, value)
return true
}, limit: 1)
for id in removeKeys {
self.valueBox.remove(self.table, key: self.key(id: MessageId(peerId: peerId, namespace: namespace, id: id), space: space), secure: false)
}
for insertRange in insertRanges.rangeView {
// 注意closeRange: insertRange.lowerBound ... insertRange.upperBound - 1
let closedRange: ClosedRange<MessageId.Id> = Int32(insertRange.lowerBound) ... Int32(insertRange.upperBound - 1)
var lowerBound: Int32 = closedRange.lowerBound
// 注意insertRange的存储key: (id: MessageId(peerId: peerId, namespace: namespace, id: closedRange.upperBound), space: space)
// value: lowerBound
self.valueBox.set(self.table, key: self.key(id: MessageId(peerId: peerId, namespace: namespace, id: closedRange.upperBound), space: space), value: MemoryBuffer(memory: &lowerBound, capacity: 4, length: 4, freeWhenDone: false))
}
if !removeKeys.isEmpty {
addOperation(.remove(range), peerId: peerId, namespace: namespace, space: space, to: &operations)
}
}
addHole
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
75
76
private func addInternal(peerId: PeerId, namespace: MessageId.Namespace, space: MessageHistoryHoleSpace, range: ClosedRange<MessageId.Id>, operations: inout [MessageHistoryIndexHoleOperationKey: [MessageHistoryIndexHoleOperation]]) {
let clippedLowerBound = max(1, range.lowerBound)
let clippedUpperBound = min(Int32.max - 1, range.upperBound)
if clippedLowerBound > clippedUpperBound {
return
}
let clippedRange = clippedLowerBound ... clippedUpperBound
var removedIndices = IndexSet()
var insertedIndices = IndexSet()
var removeKeys: [Int32] = []
var insertRanges = IndexSet()
var alreadyMapped = false
func processRange(_ key: ValueBoxKey, _ value: ReadBuffer) {
let (upperId, keySpace) = decomposeKey(key)
assert(keySpace == space)
assert(upperId.peerId == peerId)
assert(upperId.namespace == namespace)
let lowerId = decodeValue(value: value, peerId: peerId, namespace: namespace)
let holeRange: ClosedRange<Int32> = lowerId.id ... upperId.id
if clippedRange.lowerBound >= holeRange.lowerBound && clippedRange.upperBound <= holeRange.upperBound {
// holeRange 完全落在 clippedRange内
// 不需要再添加
alreadyMapped = true
return
} else if clippedRange.overlaps(holeRange) || (holeRange.upperBound != Int32.max && clippedRange.lowerBound == holeRange.upperBound + 1) || clippedRange.upperBound == holeRange.lowerBound - 1 {
//与clippedRange有部分有交集，或与clippedRange完全没有交集
// 需要移除
// 并重新添加整个并集（holeRange, clippedRange）
removeKeys.append(upperId.id)
let unionRange: ClosedRange = min(clippedRange.lowerBound, holeRange.lowerBound) ... max(clippedRange.upperBound, holeRange.upperBound)
insertRanges.insert(integersIn: Int(unionRange.lowerBound) ... Int(unionRange.upperBound))
}
}
let lowerScanBound = max(0, clippedRange.lowerBound - 2)
self.valueBox.range(self.table, start: self.key(id: MessageId(peerId: peerId, namespace: namespace, id: lowerScanBound), space: space), end: self.key(id: MessageId(peerId: peerId, namespace: namespace, id: clippedRange.upperBound), space: space).successor, values: { key, value in
processRange(key, value)
if alreadyMapped {
return false
}
return true
}, limit: 0)
if !alreadyMapped {
self.valueBox.range(self.table, start: self.key(id: MessageId(peerId: peerId, namespace: namespace, id: clippedRange.upperBound), space: space), end: self.upperBound(peerId: peerId, namespace: namespace, space: space), values: { key, value in
processRange(key, value)
if alreadyMapped {
return false
}
return true
}, limit: 1)
}
if alreadyMapped {
return
}
insertRanges.insert(integersIn: Int(clippedRange.lowerBound) ... Int(clippedRange.upperBound))
insertedIndices.insert(integersIn: Int(clippedRange.lowerBound) ... Int(clippedRange.upperBound))
for id in removeKeys {
self.valueBox.remove(self.table, key: self.key(id: MessageId(peerId: peerId, namespace: namespace, id: id), space: space), secure: false)
}
for insertRange in insertRanges.rangeView {
let closedRange: ClosedRange<MessageId.Id> = Int32(insertRange.lowerBound) ... Int32(insertRange.upperBound - 1)
var lowerBound: Int32 = closedRange.lowerBound
self.valueBox.set(self.table, key: self.key(id: MessageId(peerId: peerId, namespace: namespace, id: closedRange.upperBound), space: space), value: MemoryBuffer(memory: &lowerBound, capacity: 4, length: 4, freeWhenDone: false))
}
addOperation(.insert(clippedRange), peerId: peerId, namespace: namespace, space: space, to: &operations)
}
add
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func add(peerId: PeerId, namespace: MessageId.Namespace, space: MessageHistoryHoleSpace, range: ClosedRange<MessageId.Id>, operations: inout [MessageHistoryIndexHoleOperationKey:
[MessageHistoryIndexHoleOperation]]) {
self.ensureInitialized(peerId: peerId)
self.addInternal(peerId: peerId, namespace: namespace, space: space, range: range, operations: &operations)
switch space {
case .everywhere:
if let namespaceHoleTags = self.seedConfiguration.messageHoles[peerId.namespace]?[namespace] {
for tag in namespaceHoleTags {
self.addInternal(peerId: peerId, namespace: namespace, space: .tag(tag), range: range, operations: &operations)
}
}
case .tag:
break
}
}
search for policy
```regulation expression HoleIndexTable.remove(peerId HoleIndexTable.add(peerId
addHole(peerId
removeHole(peerId ```