forked from decred/dcrd
-
Notifications
You must be signed in to change notification settings - Fork 0
/
txpriorityqueue.go
162 lines (140 loc) · 5.23 KB
/
txpriorityqueue.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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
// Copyright (c) 2014-2016 The btcsuite developers
// Copyright (c) 2015-2022 The Decred developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.
package mining
import (
"container/heap"
"github.com/decred/dcrd/blockchain/stake/v5"
)
// txPrioItem houses a transaction along with extra information that allows the
// transaction to be prioritized and track dependencies on other transactions
// which have not been mined into a block yet.
type txPrioItem struct {
txDesc *TxDesc
txType stake.TxType
autoRevocation bool
fee int64
priority float64
feePerKB float64
}
// txPriorityQueueLessFunc describes a function that can be used as a compare
// function for a transaction priority queue (txPriorityQueue).
type txPriorityQueueLessFunc func(*txPriorityQueue, int, int) bool
// txPriorityQueue implements a priority queue of txPrioItem elements that
// supports an arbitrary compare function as defined by txPriorityQueueLessFunc.
type txPriorityQueue struct {
lessFunc txPriorityQueueLessFunc
items []*txPrioItem
}
// Len returns the number of items in the priority queue. It is part of the
// heap.Interface implementation.
func (pq *txPriorityQueue) Len() int {
return len(pq.items)
}
// Less returns whether the item in the priority queue with index i should sort
// before the item with index j by deferring to the assigned less function. It
// is part of the heap.Interface implementation.
func (pq *txPriorityQueue) Less(i, j int) bool {
return pq.lessFunc(pq, i, j)
}
// Swap swaps the items at the passed indices in the priority queue. It is
// part of the heap.Interface implementation.
func (pq *txPriorityQueue) Swap(i, j int) {
pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
}
// Push pushes the passed item onto the priority queue. It is part of the
// heap.Interface implementation.
func (pq *txPriorityQueue) Push(x interface{}) {
pq.items = append(pq.items, x.(*txPrioItem))
}
// Pop removes the highest priority item (according to Less) from the priority
// queue and returns it. It is part of the heap.Interface implementation.
func (pq *txPriorityQueue) Pop() interface{} {
n := len(pq.items)
item := pq.items[n-1]
pq.items[n-1] = nil
pq.items = pq.items[0 : n-1]
return item
}
// SetLessFunc sets the compare function for the priority queue to the provided
// function. It also invokes heap.Init on the priority queue using the new
// function so it can immediately be used with heap.Push/Pop.
func (pq *txPriorityQueue) SetLessFunc(lessFunc txPriorityQueueLessFunc) {
pq.lessFunc = lessFunc
heap.Init(pq)
}
// stakePriority is an integer that is used to sort stake transactions
// by importance when they enter the min heap for block construction. The
// priority is:
// - 3 is for votes (highest)
// - 2 for automatic revocations
// - 1 for tickets
// - 0 for regular transactions and revocations (lowest)
type stakePriority int
const (
regOrRevocPriority stakePriority = iota
ticketPriority
autoRevocPriority
votePriority
)
// stakePriority assigns a stake priority based on a transaction type.
func txStakePriority(txType stake.TxType, autoRevocation bool) stakePriority {
prio := regOrRevocPriority
switch {
case txType == stake.TxTypeSSGen:
prio = votePriority
case txType == stake.TxTypeSSRtx && autoRevocation:
prio = autoRevocPriority
case txType == stake.TxTypeSStx:
prio = ticketPriority
}
return prio
}
// compareStakePriority compares the stake priority of two transactions.
// It uses votes > tickets > regular transactions or revocations. It
// returns 1 if i > j, 0 if i == j, and -1 if i < j in terms of stake
// priority.
func compareStakePriority(i, j *txPrioItem) int {
iStakePriority := txStakePriority(i.txType, i.autoRevocation)
jStakePriority := txStakePriority(j.txType, j.autoRevocation)
if iStakePriority > jStakePriority {
return 1
}
if iStakePriority < jStakePriority {
return -1
}
return 0
}
// txPQByStakeAndFee sorts a txPriorityQueue by stake priority, followed by
// fees per kilobyte, and then transaction priority.
func txPQByStakeAndFee(pq *txPriorityQueue, i, j int) bool {
// Sort by stake priority, continue if they're the same stake priority.
cmp := compareStakePriority(pq.items[i], pq.items[j])
if cmp == 1 {
return true
}
if cmp == -1 {
return false
}
// Using > here so that pop gives the highest fee item as opposed
// to the lowest. Sort by fee first, then priority.
if pq.items[i].feePerKB == pq.items[j].feePerKB {
return pq.items[i].priority > pq.items[j].priority
}
// The stake priorities are equal, so return based on fees
// per KB.
return pq.items[i].feePerKB > pq.items[j].feePerKB
}
// newTxPriorityQueue returns a new transaction priority queue that reserves the
// passed amount of space for the elements. The new priority queue uses the
// less than function lessFunc to sort the items in the min heap. The priority
// queue can grow larger than the reserved space, but extra copies of the
// underlying array can be avoided by reserving a sane value.
func newTxPriorityQueue(reserve int, lessFunc func(*txPriorityQueue, int, int) bool) *txPriorityQueue {
pq := &txPriorityQueue{
items: make([]*txPrioItem, 0, reserve),
}
pq.SetLessFunc(lessFunc)
return pq
}