-
Notifications
You must be signed in to change notification settings - Fork 1
/
ordered_tree_node_set.go
62 lines (52 loc) · 1.73 KB
/
ordered_tree_node_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
package reachabilitymanager
import (
"github.com/BTCGhostdag/BTCD/domain/consensus/model"
"github.com/BTCGhostdag/BTCD/domain/consensus/model/externalapi"
)
// orderedTreeNodeSet is an ordered set of model.DomainHash ordered by the respectful intervals.
// Note that this type does not validate order validity. It's the
// responsibility of the caller to construct instances of this
// type properly.
type orderedTreeNodeSet []*externalapi.DomainHash
// findAncestorOfNode finds the reachability tree ancestor of `node`
// among the nodes in `tns`.
func (rt *reachabilityManager) findAncestorOfNode(stagingArea *model.StagingArea, tns orderedTreeNodeSet, node *externalapi.DomainHash) (*externalapi.DomainHash, bool) {
ancestorIndex, ok, err := rt.findAncestorIndexOfNode(stagingArea, tns, node)
if err != nil {
return nil, false
}
if !ok {
return nil, false
}
return tns[ancestorIndex], true
}
// findAncestorIndexOfNode finds the index of the reachability tree
// ancestor of `node` among the nodes in `tns`. It does so by finding
// the index of the block with the maximum start that is below the
// given block.
func (rt *reachabilityManager) findAncestorIndexOfNode(stagingArea *model.StagingArea, tns orderedTreeNodeSet,
node *externalapi.DomainHash) (int, bool, error) {
blockInterval, err := rt.interval(stagingArea, node)
if err != nil {
return 0, false, err
}
end := blockInterval.End
low := 0
high := len(tns)
for low < high {
middle := (low + high) / 2
middleInterval, err := rt.interval(stagingArea, tns[middle])
if err != nil {
return 0, false, err
}
if end < middleInterval.Start {
high = middle
} else {
low = middle + 1
}
}
if low == 0 {
return 0, false, nil
}
return low - 1, true, nil
}