-
Notifications
You must be signed in to change notification settings - Fork 1
/
future_covering_set.go
105 lines (89 loc) · 3.72 KB
/
future_covering_set.go
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package reachabilitymanager
import (
"github.com/BTCGhostdag/BTCD/domain/consensus/model"
"github.com/BTCGhostdag/BTCD/domain/consensus/model/externalapi"
)
// insertToFutureCoveringSet inserts the given block into this node's FutureCoveringSet
// while keeping it ordered by interval.
// If a block B ∈ node.FutureCoveringSet exists such that its interval
// contains block's interval, block need not be added. If block's
// interval contains B's interval, it replaces it.
//
// Notes:
// - Intervals never intersect unless one contains the other
// (this follows from the tree structure and the indexing rule).
// - Since node.FutureCoveringSet is kept ordered, a binary search can be
// used for insertion/queries.
// - Although reindexing may change a block's interval, the
// is-superset relation will by definition
// be always preserved.
func (rt *reachabilityManager) insertToFutureCoveringSet(stagingArea *model.StagingArea, node, futureNode *externalapi.DomainHash) error {
reachabilityData, err := rt.reachabilityDataForInsertion(stagingArea, node)
if err != nil {
return err
}
futureCoveringSet := reachabilityData.FutureCoveringSet()
ancestorIndex, ok, err := rt.findAncestorIndexOfNode(stagingArea, orderedTreeNodeSet(futureCoveringSet), futureNode)
if err != nil {
return err
}
var newSet []*externalapi.DomainHash
if !ok {
newSet = append([]*externalapi.DomainHash{futureNode}, futureCoveringSet...)
} else {
candidate := futureCoveringSet[ancestorIndex]
candidateIsAncestorOfFutureNode, err := rt.IsReachabilityTreeAncestorOf(stagingArea, candidate, futureNode)
if err != nil {
return err
}
if candidateIsAncestorOfFutureNode {
// candidate is an ancestor of futureNode, no need to insert
return nil
}
futureNodeIsAncestorOfCandidate, err := rt.IsReachabilityTreeAncestorOf(stagingArea, futureNode, candidate)
if err != nil {
return err
}
if futureNodeIsAncestorOfCandidate {
// futureNode is an ancestor of candidate, and can thus replace it
newSet := make([]*externalapi.DomainHash, len(futureCoveringSet))
copy(newSet, futureCoveringSet)
newSet[ancestorIndex] = futureNode
return rt.stageFutureCoveringSet(stagingArea, node, newSet)
}
// Insert futureNode in the correct index to maintain futureCoveringTreeNodeSet as
// a sorted-by-interval list.
// Note that ancestorIndex might be equal to len(futureCoveringTreeNodeSet)
left := futureCoveringSet[:ancestorIndex+1]
right := append([]*externalapi.DomainHash{futureNode}, futureCoveringSet[ancestorIndex+1:]...)
newSet = append(left, right...)
}
reachabilityData.SetFutureCoveringSet(newSet)
rt.stageData(stagingArea, node, reachabilityData)
return nil
}
// futureCoveringSetHasAncestorOf resolves whether the given node `other` is in the subtree of
// any node in this.FutureCoveringSet.
// See insertNode method for the complementary insertion behavior.
//
// Like the insert method, this method also relies on the fact that
// this.FutureCoveringSet is kept ordered by interval to efficiently perform a
// binary search over this.FutureCoveringSet and answer the query in
// O(log(|futureCoveringTreeNodeSet|)).
func (rt *reachabilityManager) futureCoveringSetHasAncestorOf(stagingArea *model.StagingArea,
this, other *externalapi.DomainHash) (bool, error) {
futureCoveringSet, err := rt.futureCoveringSet(stagingArea, this)
if err != nil {
return false, err
}
ancestorIndex, ok, err := rt.findAncestorIndexOfNode(stagingArea, orderedTreeNodeSet(futureCoveringSet), other)
if err != nil {
return false, err
}
if !ok {
// No candidate to contain other
return false, nil
}
candidate := futureCoveringSet[ancestorIndex]
return rt.IsReachabilityTreeAncestorOf(stagingArea, candidate, other)
}