forked from kaspanet/kaspad
-
Notifications
You must be signed in to change notification settings - Fork 7
/
dagtraversalmanager.go
129 lines (112 loc) · 4.38 KB
/
dagtraversalmanager.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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package dagtraversalmanager
import (
"github.com/Hoosat-Oy/HTND/domain/consensus/model"
"github.com/Hoosat-Oy/HTND/domain/consensus/model/externalapi"
"github.com/pkg/errors"
)
// dagTraversalManager exposes methods for traversing blocks
// in the DAG
type dagTraversalManager struct {
databaseContext model.DBReader
dagTopologyManager model.DAGTopologyManager
ghostdagManager model.GHOSTDAGManager
ghostdagDataStore model.GHOSTDAGDataStore
reachabilityManager model.ReachabilityManager
daaWindowStore model.BlocksWithTrustedDataDAAWindowStore
genesisHash *externalapi.DomainHash
difficultyAdjustmentWindowSize int
windowHeapSliceStore model.WindowHeapSliceStore
}
// New instantiates a new DAGTraversalManager
func New(
databaseContext model.DBReader,
dagTopologyManager model.DAGTopologyManager,
ghostdagDataStore model.GHOSTDAGDataStore,
reachabilityManager model.ReachabilityManager,
ghostdagManager model.GHOSTDAGManager,
daaWindowStore model.BlocksWithTrustedDataDAAWindowStore,
windowHeapSliceStore model.WindowHeapSliceStore,
genesisHash *externalapi.DomainHash,
difficultyAdjustmentWindowSize int) model.DAGTraversalManager {
return &dagTraversalManager{
databaseContext: databaseContext,
dagTopologyManager: dagTopologyManager,
ghostdagDataStore: ghostdagDataStore,
reachabilityManager: reachabilityManager,
ghostdagManager: ghostdagManager,
daaWindowStore: daaWindowStore,
genesisHash: genesisHash,
difficultyAdjustmentWindowSize: difficultyAdjustmentWindowSize,
windowHeapSliceStore: windowHeapSliceStore,
}
}
func (dtm *dagTraversalManager) LowestChainBlockAboveOrEqualToBlueScore(stagingArea *model.StagingArea, highHash *externalapi.DomainHash, blueScore uint64) (*externalapi.DomainHash, error) {
highBlockGHOSTDAGData, err := dtm.ghostdagDataStore.Get(dtm.databaseContext, stagingArea, highHash, false)
if err != nil {
return nil, err
}
if highBlockGHOSTDAGData.BlueScore() < blueScore {
return nil, errors.Errorf("the given blue score %d is higher than block %s blue score of %d",
blueScore, highHash, highBlockGHOSTDAGData.BlueScore())
}
currentHash := highHash
currentBlockGHOSTDAGData := highBlockGHOSTDAGData
for !currentHash.Equal(dtm.genesisHash) {
selectedParentBlockGHOSTDAGData, err := dtm.ghostdagDataStore.Get(dtm.databaseContext, stagingArea,
currentBlockGHOSTDAGData.SelectedParent(), false)
if err != nil {
return nil, err
}
if selectedParentBlockGHOSTDAGData.BlueScore() < blueScore {
break
}
currentHash = currentBlockGHOSTDAGData.SelectedParent()
currentBlockGHOSTDAGData = selectedParentBlockGHOSTDAGData
}
return currentHash, nil
}
func (dtm *dagTraversalManager) CalculateChainPath(stagingArea *model.StagingArea,
fromBlockHash, toBlockHash *externalapi.DomainHash) (*externalapi.SelectedChainPath, error) {
// Walk down from fromBlockHash until we reach the common selected
// parent chain ancestor of fromBlockHash and toBlockHash. Note
// that this slice will be empty if fromBlockHash is the selected
// parent of toBlockHash
var removed []*externalapi.DomainHash
current := fromBlockHash
for {
isCurrentInTheSelectedParentChainOfNewVirtualSelectedParent, err :=
dtm.dagTopologyManager.IsInSelectedParentChainOf(stagingArea, current, toBlockHash)
if err != nil {
return nil, err
}
if isCurrentInTheSelectedParentChainOfNewVirtualSelectedParent {
break
}
removed = append(removed, current)
currentGHOSTDAGData, err := dtm.ghostdagDataStore.Get(dtm.databaseContext, stagingArea, current, false)
if err != nil {
return nil, err
}
current = currentGHOSTDAGData.SelectedParent()
}
commonAncestor := current
// Walk down from the toBlockHash to the common ancestor
var added []*externalapi.DomainHash
current = toBlockHash
for !current.Equal(commonAncestor) {
added = append(added, current)
currentGHOSTDAGData, err := dtm.ghostdagDataStore.Get(dtm.databaseContext, stagingArea, current, false)
if err != nil {
return nil, err
}
current = currentGHOSTDAGData.SelectedParent()
}
// Reverse the order of `added` so that it's sorted from low hash to high hash
for i, j := 0, len(added)-1; i < j; i, j = i+1, j-1 {
added[i], added[j] = added[j], added[i]
}
return &externalapi.SelectedChainPath{
Added: added,
Removed: removed,
}, nil
}