diff options
Diffstat (limited to 'core/types')
-rw-r--r-- | core/types/transaction.go | 27 | ||||
-rw-r--r-- | core/types/transaction_test.go | 7 |
2 files changed, 13 insertions, 21 deletions
diff --git a/core/types/transaction.go b/core/types/transaction.go index d369d7772..af48e4d07 100644 --- a/core/types/transaction.go +++ b/core/types/transaction.go @@ -24,7 +24,6 @@ import ( "fmt" "io" "math/big" - "sort" "sync/atomic" "github.com/ethereum/go-ethereum/common" @@ -439,37 +438,29 @@ func (s *TxByPrice) Pop() interface{} { // sender accounts and sorts them by nonce. After the account nonce ordering is // satisfied, the results are merged back together by price, always comparing only // the head transaction from each account. This is done via a heap to keep it fast. -func SortByPriceAndNonce(txs []*Transaction) { - // Separate the transactions by account and sort by nonce - byNonce := make(map[common.Address][]*Transaction) - for _, tx := range txs { - acc, _ := tx.From() // we only sort valid txs so this cannot fail - byNonce[acc] = append(byNonce[acc], tx) - } - for _, accTxs := range byNonce { - sort.Sort(TxByNonce(accTxs)) - } +func SortByPriceAndNonce(txs map[common.Address]Transactions) Transactions { // Initialize a price based heap with the head transactions - byPrice := make(TxByPrice, 0, len(byNonce)) - for acc, accTxs := range byNonce { + byPrice := make(TxByPrice, 0, len(txs)) + for acc, accTxs := range txs { byPrice = append(byPrice, accTxs[0]) - byNonce[acc] = accTxs[1:] + txs[acc] = accTxs[1:] } heap.Init(&byPrice) // Merge by replacing the best with the next from the same account - txs = txs[:0] + var sorted Transactions for len(byPrice) > 0 { // Retrieve the next best transaction by price best := heap.Pop(&byPrice).(*Transaction) // Push in its place the next transaction from the same account acc, _ := best.From() // we only sort valid txs so this cannot fail - if accTxs, ok := byNonce[acc]; ok && len(accTxs) > 0 { + if accTxs, ok := txs[acc]; ok && len(accTxs) > 0 { heap.Push(&byPrice, accTxs[0]) - byNonce[acc] = accTxs[1:] + txs[acc] = accTxs[1:] } // Accumulate the best priced transaction - txs = append(txs, best) + sorted = append(sorted, best) } + return sorted } diff --git a/core/types/transaction_test.go b/core/types/transaction_test.go index 62420e71f..c6e6e3790 100644 --- a/core/types/transaction_test.go +++ b/core/types/transaction_test.go @@ -128,15 +128,16 @@ func TestTransactionPriceNonceSort(t *testing.T) { keys[i], _ = crypto.GenerateKey() } // Generate a batch of transactions with overlapping values, but shifted nonces - txs := []*Transaction{} + groups := map[common.Address]Transactions{} for start, key := range keys { + addr := crypto.PubkeyToAddress(key.PublicKey) for i := 0; i < 25; i++ { tx, _ := NewTransaction(uint64(start+i), common.Address{}, big.NewInt(100), big.NewInt(100), big.NewInt(int64(start+i)), nil).SignECDSA(key) - txs = append(txs, tx) + groups[addr] = append(groups[addr], tx) } } // Sort the transactions and cross check the nonce ordering - SortByPriceAndNonce(txs) + txs := SortByPriceAndNonce(groups) for i, txi := range txs { fromi, _ := txi.From() |