forked from ethereum/go-ethereum
-
Notifications
You must be signed in to change notification settings - Fork 61
/
order_tx_list.go
289 lines (257 loc) · 9.75 KB
/
order_tx_list.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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
// Copyright 2016 The go-ethereum Authors
// This file is part of the go-ethereum library.
//
// The go-ethereum library is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// The go-ethereum library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
package core
import (
"container/heap"
"sort"
"github.com/XinFinOrg/XDPoSChain/core/types"
)
// txSortedMap is a nonce->transaction hash map with a heap based index to allow
// iterating over the contents in a nonce-incrementing way.
type ordertxSortedMap struct {
items map[uint64]*types.OrderTransaction // Hash map storing the transaction data
index *nonceHeap // Heap of nonces of all the stored transactions (non-strict mode)
cache types.OrderTransactions // Cache of the transactions already sorted
}
// newTxSortedMap creates a new nonce-sorted transaction map.
func newOrderTxSortedMap() *ordertxSortedMap {
return &ordertxSortedMap{
items: make(map[uint64]*types.OrderTransaction),
index: new(nonceHeap),
}
}
// Get retrieves the current transactions associated with the given nonce.
func (m *ordertxSortedMap) Get(nonce uint64) *types.OrderTransaction {
return m.items[nonce]
}
// Put inserts a new transaction into the map, also updating the map's nonce
// index. If a transaction already exists with the same nonce, it's overwritten.
func (m *ordertxSortedMap) Put(tx *types.OrderTransaction) {
nonce := tx.Nonce()
if m.items[nonce] == nil {
heap.Push(m.index, nonce)
}
m.items[nonce], m.cache = tx, nil
}
// Forward removes all transactions from the map with a nonce lower than the
// provided threshold. Every removed transaction is returned for any post-removal
// maintenance.
func (m *ordertxSortedMap) Forward(threshold uint64) types.OrderTransactions {
var removed types.OrderTransactions
// Pop off heap items until the threshold is reached
for m.index.Len() > 0 && (*m.index)[0] < threshold {
nonce := heap.Pop(m.index).(uint64)
removed = append(removed, m.items[nonce])
delete(m.items, nonce)
}
// If we had a cached order, shift the front
if m.cache != nil {
m.cache = m.cache[len(removed):]
}
return removed
}
// Filter iterates over the list of transactions and removes all of them for which
// the specified function evaluates to true.
func (m *ordertxSortedMap) Filter(filter func(*types.OrderTransaction) bool) types.OrderTransactions {
var removed types.OrderTransactions
// Collect all the transactions to filter out
for nonce, tx := range m.items {
if filter(tx) {
removed = append(removed, tx)
delete(m.items, nonce)
}
}
// If transactions were removed, the heap and cache are ruined
if len(removed) > 0 {
*m.index = make([]uint64, 0, len(m.items))
for nonce := range m.items {
*m.index = append(*m.index, nonce)
}
heap.Init(m.index)
m.cache = nil
}
return removed
}
// Cap places a hard limit on the number of items, returning all transactions
// exceeding that limit.
func (m *ordertxSortedMap) Cap(threshold int) types.OrderTransactions {
// Short circuit if the number of items is under the limit
if len(m.items) <= threshold {
return nil
}
// Otherwise gather and drop the highest nonce'd transactions
var drops types.OrderTransactions
sort.Sort(*m.index)
for size := len(m.items); size > threshold; size-- {
drops = append(drops, m.items[(*m.index)[size-1]])
delete(m.items, (*m.index)[size-1])
}
*m.index = (*m.index)[:threshold]
heap.Init(m.index)
// If we had a cache, shift the back
if m.cache != nil {
m.cache = m.cache[:len(m.cache)-len(drops)]
}
return drops
}
// Remove deletes a transaction from the maintained map, returning whether the
// transaction was found.
func (m *ordertxSortedMap) Remove(nonce uint64) bool {
// Short circuit if no transaction is present
_, ok := m.items[nonce]
if !ok {
return false
}
// Otherwise delete the transaction and fix the heap index
for i := 0; i < m.index.Len(); i++ {
if (*m.index)[i] == nonce {
heap.Remove(m.index, i)
break
}
}
delete(m.items, nonce)
m.cache = nil
return true
}
// Ready retrieves a sequentially increasing list of transactions starting at the
// provided nonce that is ready for processing. The returned transactions will be
// removed from the list.
//
// Note, all transactions with nonces lower than start will also be returned to
// prevent getting into and invalid state. This is not something that should ever
// happen but better to be self correcting than failing!
func (m *ordertxSortedMap) Ready(start uint64) types.OrderTransactions {
// Short circuit if no transactions are available
if m.index.Len() == 0 || (*m.index)[0] > start {
return nil
}
// Otherwise start accumulating incremental transactions
var ready types.OrderTransactions
for next := (*m.index)[0]; m.index.Len() > 0 && (*m.index)[0] == next; next++ {
ready = append(ready, m.items[next])
delete(m.items, next)
heap.Pop(m.index)
}
m.cache = nil
return ready
}
// Len returns the length of the transaction map.
func (m *ordertxSortedMap) Len() int {
return len(m.items)
}
// Flatten creates a nonce-sorted slice of transactions based on the loosely
// sorted internal representation. The result of the sorting is cached in case
// it's requested again before any modifications are made to the contents.
func (m *ordertxSortedMap) Flatten() types.OrderTransactions {
// If the sorting was not cached yet, create and cache it
if m.cache == nil {
m.cache = make(types.OrderTransactions, 0, len(m.items))
for _, tx := range m.items {
m.cache = append(m.cache, tx)
}
sort.Sort(types.OrderTxByNonce(m.cache))
}
// Copy the cache to prevent accidental modifications
txs := make(types.OrderTransactions, len(m.cache))
copy(txs, m.cache)
return txs
}
// txList is a "list" of transactions belonging to an account, sorted by account
// nonce. The same type can be used both for storing contiguous transactions for
// the executable/pending queue; and for storing gapped transactions for the non-
// executable/future queue, with minor behavioral changes.
type ordertxList struct {
strict bool // Whether nonces are strictly continuous or not
txs *ordertxSortedMap // Heap indexed sorted hash map of the transactions
}
// newTxList create a new transaction list for maintaining nonce-indexable fast,
// gapped, sortable transaction lists.
func newOrderTxList(strict bool) *ordertxList {
return &ordertxList{
strict: strict,
txs: newOrderTxSortedMap(),
}
}
// Overlaps returns whether the transaction specified has the same nonce as one
// already contained within the list.
func (l *ordertxList) Overlaps(tx *types.OrderTransaction) bool {
return l.txs.Get(tx.Nonce()) != nil
}
// Add tries to insert a new transaction into the list, returning whether the
// transaction was accepted, and if yes, any previous transaction it replaced.
//
// If the new transaction is accepted into the list, the lists' cost and gas
// thresholds are also potentially updated.
func (l *ordertxList) Add(tx *types.OrderTransaction) (bool, *types.OrderTransaction) {
// If there's an older better transaction, abort
old := l.txs.Get(tx.Nonce())
if old != nil {
l.txs.Put(tx)
return true, old
}
l.txs.Put(tx)
return true, nil
}
// Forward removes all transactions from the list with a nonce lower than the
// provided threshold. Every removed transaction is returned for any post-removal
// maintenance.
func (l *ordertxList) Forward(threshold uint64) types.OrderTransactions {
return l.txs.Forward(threshold)
}
// Cap places a hard limit on the number of items, returning all transactions
// exceeding that limit.
func (l *ordertxList) Cap(threshold int) types.OrderTransactions {
return l.txs.Cap(threshold)
}
// Remove deletes a transaction from the maintained list, returning whether the
// transaction was found, and also returning any transaction invalidated due to
// the deletion (strict mode only).
func (l *ordertxList) Remove(tx *types.OrderTransaction) (bool, types.OrderTransactions) {
// Remove the transaction from the set
nonce := tx.Nonce()
if removed := l.txs.Remove(nonce); !removed {
return false, nil
}
// In strict mode, filter out non-executable transactions
if l.strict {
return true, l.txs.Filter(func(tx *types.OrderTransaction) bool { return tx.Nonce() > nonce })
}
return true, nil
}
// Ready retrieves a sequentially increasing list of transactions starting at the
// provided nonce that is ready for processing. The returned transactions will be
// removed from the list.
//
// Note, all transactions with nonces lower than start will also be returned to
// prevent getting into and invalid state. This is not something that should ever
// happen but better to be self correcting than failing!
func (l *ordertxList) Ready(start uint64) types.OrderTransactions {
return l.txs.Ready(start)
}
// Len returns the length of the transaction list.
func (l *ordertxList) Len() int {
return l.txs.Len()
}
// Empty returns whether the list of transactions is empty or not.
func (l *ordertxList) Empty() bool {
return l.Len() == 0
}
// Flatten creates a nonce-sorted slice of transactions based on the loosely
// sorted internal representation. The result of the sorting is cached in case
// it's requested again before any modifications are made to the contents.
func (l *ordertxList) Flatten() types.OrderTransactions {
return l.txs.Flatten()
}