-
Notifications
You must be signed in to change notification settings - Fork 155
/
kahnsort.go
116 lines (100 loc) · 2.85 KB
/
kahnsort.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
// Copyright (c) 2016 The btcsuite developers
// Copyright (c) 2016 The Decred developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.
package udb
import (
"github.com/decred/dcrd/chaincfg/chainhash"
)
type graphNode struct {
value *TxRecord
outEdges []*chainhash.Hash
inDegree int
}
type hashGraph map[chainhash.Hash]graphNode
func makeGraph(set map[chainhash.Hash]*TxRecord) hashGraph {
graph := make(hashGraph)
for _, rec := range set {
// Add a node for every transaction record. The output edges
// and input degree are set by iterating over each record's
// inputs below.
if _, ok := graph[rec.Hash]; !ok {
graph[rec.Hash] = graphNode{value: rec}
}
inputLoop:
for _, input := range rec.MsgTx.TxIn {
// Transaction inputs that reference transactions not
// included in the set do not create any (local) graph
// edges.
if _, ok := set[input.PreviousOutPoint.Hash]; !ok {
continue
}
inputNode := graph[input.PreviousOutPoint.Hash]
// Skip duplicate edges.
for _, outEdge := range inputNode.outEdges {
if *outEdge == input.PreviousOutPoint.Hash {
continue inputLoop
}
}
// Mark a directed edge from the previous transaction
// hash to this transaction record and increase the
// input degree for this record's node.
inputRec := inputNode.value
if inputRec == nil {
inputRec = set[input.PreviousOutPoint.Hash]
}
graph[input.PreviousOutPoint.Hash] = graphNode{
value: inputRec,
outEdges: append(inputNode.outEdges, &rec.Hash),
inDegree: inputNode.inDegree,
}
node := graph[rec.Hash]
graph[rec.Hash] = graphNode{
value: rec,
outEdges: node.outEdges,
inDegree: node.inDegree + 1,
}
}
}
return graph
}
// graphRoots returns the roots of the graph. That is, it returns the node's
// values for all nodes which contain an input degree of 0.
func graphRoots(graph hashGraph) []*TxRecord {
roots := make([]*TxRecord, 0, len(graph))
for _, node := range graph {
if node.inDegree == 0 {
roots = append(roots, node.value)
}
}
return roots
}
// dependencySort topologically sorts a set of transaction records by their
// dependency order. It is implemented using Kahn's algorithm.
func dependencySort(txs map[chainhash.Hash]*TxRecord) []*TxRecord {
graph := makeGraph(txs)
s := graphRoots(graph)
// If there are no edges (no transactions from the map reference each
// other), then Kahn's algorithm is unnecessary.
if len(s) == len(txs) {
return s
}
sorted := make([]*TxRecord, 0, len(txs))
for len(s) != 0 {
rec := s[0]
s = s[1:]
sorted = append(sorted, rec)
n := graph[rec.Hash]
for _, mHash := range n.outEdges {
m := graph[*mHash]
if m.inDegree != 0 {
m.inDegree--
graph[*mHash] = m
if m.inDegree == 0 {
s = append(s, m.value)
}
}
}
}
return sorted
}