forked from Onyx-Protocol/Onyx
-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort.go
81 lines (71 loc) · 1.48 KB
/
sort.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
package protocol
import "chain/protocol/bc"
func topSort(txs []*bc.Tx) []*bc.Tx {
if len(txs) == 1 {
return txs
}
nodes := make(map[bc.Hash]*bc.Tx)
for _, tx := range txs {
nodes[tx.Hash] = tx
}
incomingEdges := make(map[bc.Hash]int)
children := make(map[bc.Hash][]bc.Hash)
for node, tx := range nodes {
for _, in := range tx.Inputs {
if in.IsIssuance() {
continue
}
if prev := in.Outpoint().Hash; nodes[prev] != nil {
if children[prev] == nil {
children[prev] = make([]bc.Hash, 0, 1)
}
children[prev] = append(children[prev], node)
incomingEdges[node]++
}
}
}
var s []bc.Hash
for node := range nodes {
if incomingEdges[node] == 0 {
s = append(s, node)
}
}
// https://en.wikipedia.org/wiki/Topological_sorting#Algorithms
var l []*bc.Tx
for len(s) > 0 {
n := s[0]
s = s[1:]
l = append(l, nodes[n])
for _, m := range children[n] {
incomingEdges[m]--
if incomingEdges[m] == 0 {
delete(incomingEdges, m)
s = append(s, m)
}
}
}
if len(incomingEdges) > 0 { // should be impossible
panic("cyclical tx ordering")
}
return l
}
func isTopSorted(txs []*bc.Tx) bool {
exists := make(map[bc.Hash]bool)
seen := make(map[bc.Hash]bool)
for _, tx := range txs {
exists[tx.Hash] = true
}
for _, tx := range txs {
for _, in := range tx.Inputs {
if in.IsIssuance() {
continue
}
h := in.Outpoint().Hash
if exists[h] && !seen[h] {
return false
}
}
seen[tx.Hash] = true
}
return true
}