1 // Copyright (c) 2016 The btcsuite developers
2 3 package wtxmgr
4 5 import "github.com/p9c/p9/pkg/chainhash"
6 7 type graphNode struct {
8 value *TxRecord
9 outEdges []*chainhash.Hash
10 inDegree int
11 }
12 13 type hashGraph map[chainhash.Hash]graphNode
14 15 func makeGraph(set map[chainhash.Hash]*TxRecord) hashGraph {
16 graph := make(hashGraph)
17 for _, rec := range set {
18 // Add a node for every transaction record. The output edges and input degree are set by iterating over each
19 // record's inputs below.
20 if _, ok := graph[rec.Hash]; !ok {
21 graph[rec.Hash] = graphNode{value: rec}
22 }
23 inputLoop:
24 for _, input := range rec.MsgTx.TxIn {
25 // Transaction inputs that reference transactions not included in the set do not create any (local) graph
26 // edges.
27 if _, ok := set[input.PreviousOutPoint.Hash]; !ok {
28 continue
29 }
30 inputNode := graph[input.PreviousOutPoint.Hash]
31 // Skip duplicate edges.
32 for _, outEdge := range inputNode.outEdges {
33 if *outEdge == input.PreviousOutPoint.Hash {
34 continue inputLoop
35 }
36 }
37 // Mark a directed edge from the previous transaction hash to this transaction record and increase the input
38 // degree for this record's node.
39 inputRec := inputNode.value
40 if inputRec == nil {
41 inputRec = set[input.PreviousOutPoint.Hash]
42 }
43 graph[input.PreviousOutPoint.Hash] = graphNode{
44 value: inputRec,
45 outEdges: append(inputNode.outEdges, &rec.Hash),
46 inDegree: inputNode.inDegree,
47 }
48 node := graph[rec.Hash]
49 graph[rec.Hash] = graphNode{
50 value: rec,
51 outEdges: node.outEdges,
52 inDegree: node.inDegree + 1,
53 }
54 }
55 }
56 return graph
57 }
58 59 // graphRoots returns the roots of the graph. That is, it returns the node's values for all nodes which contain an input
60 // degree of 0.
61 func graphRoots(graph hashGraph) []*TxRecord {
62 roots := make([]*TxRecord, 0, len(graph))
63 for _, node := range graph {
64 if node.inDegree == 0 {
65 roots = append(roots, node.value)
66 }
67 }
68 return roots
69 }
70 71 // dependencySort topologically sorts a set of transaction records by their dependency order. It is implemented using
72 // Kahn's algorithm.
73 func dependencySort(txs map[chainhash.Hash]*TxRecord) []*TxRecord {
74 graph := makeGraph(txs)
75 s := graphRoots(graph)
76 // If there are no edges (no transactions from the map reference each other), then Kahn's algorithm is unnecessary.
77 if len(s) == len(txs) {
78 return s
79 }
80 sorted := make([]*TxRecord, 0, len(txs))
81 for len(s) != 0 {
82 rec := s[0]
83 s = s[1:]
84 sorted = append(sorted, rec)
85 n := graph[rec.Hash]
86 for _, mHash := range n.outEdges {
87 m := graph[*mHash]
88 if m.inDegree != 0 {
89 m.inDegree--
90 graph[*mHash] = m
91 if m.inDegree == 0 {
92 s = append(s, m.value)
93 }
94 }
95 }
96 }
97 return sorted
98 }
99