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
// Copyright 2015-2018 Parity Technologies (UK) Ltd. // This file is part of Parity. // Parity is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // Parity 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 General Public License for more details. // You should have received a copy of the GNU General Public License // along with Parity. If not, see <http://www.gnu.org/licenses/>. //! A transactions ordering abstraction. use std::{cmp, fmt}; use pool::Transaction; /// Represents a decision what to do with /// a new transaction that tries to enter the pool. #[derive(Debug, Clone, Copy, PartialEq, Eq)] pub enum Choice { /// New transaction should be rejected /// (i.e. the old transaction that occupies the same spot /// is better). RejectNew, /// The old transaction should be dropped /// in favour of the new one. ReplaceOld, /// The new transaction should be inserted /// and both (old and new) should stay in the pool. InsertNew, } /// Describes a reason why the `Score` of transactions /// should be updated. /// The `Scoring` implementations can use this information /// to update the `Score` table more efficiently. #[derive(Debug, Clone, Copy, PartialEq, Eq)] pub enum Change<T = ()> { /// New transaction has been inserted at given index. /// The Score at that index is initialized with default value /// and needs to be filled in. InsertedAt(usize), /// The transaction has been removed at given index and other transactions /// shifted to it's place. /// The scores were removed and shifted as well. /// For simple scoring algorithms no action is required here. RemovedAt(usize), /// The transaction at given index has replaced a previous transaction. /// The score at that index needs to be update (it contains value from previous transaction). ReplacedAt(usize), /// Given number of stalled transactions has been culled from the beginning. /// The scores has been removed from the beginning as well. /// For simple scoring algorithms no action is required here. Culled(usize), /// Custom event to update the score triggered outside of the pool. /// Handling this event is up to scoring implementation. Event(T), } /// A transaction ordering. /// /// The implementation should decide on order of transactions in the pool. /// Each transaction should also get assigned a `Score` which is used to later /// prioritize transactions in the pending set. /// /// Implementation notes: /// - Returned `Score`s should match ordering of `compare` method. /// - `compare` will be called only within a context of transactions from the same sender. /// - `choose` may be called even if `compare` returns `Ordering::Equal` /// - `should_replace` is used to decide if new transaction should push out an old transaction already in the queue. /// - `Score`s and `compare` should align with `Ready` implementation. /// /// Example: Natural ordering of Ethereum transactions. /// - `compare`: compares transaction `nonce` () /// - `choose`: compares transactions `gasPrice` (decides if old transaction should be replaced) /// - `update_scores`: score defined as `gasPrice` if `n==0` and `max(scores[n-1], gasPrice)` if `n>0` /// - `should_replace`: compares `gasPrice` (decides if transaction from a different sender is more valuable) /// pub trait Scoring<T>: fmt::Debug { /// A score of a transaction. type Score: cmp::Ord + Clone + Default + fmt::Debug; /// Custom scoring update event type. type Event: fmt::Debug; /// Decides on ordering of `T`s from a particular sender. fn compare(&self, old: &T, other: &T) -> cmp::Ordering; /// Decides how to deal with two transactions from a sender that seem to occupy the same slot in the queue. fn choose(&self, old: &T, new: &T) -> Choice; /// Updates the transaction scores given a list of transactions and a change to previous scoring. /// NOTE: you can safely assume that both slices have the same length. /// (i.e. score at index `i` represents transaction at the same index) fn update_scores(&self, txs: &[Transaction<T>], scores: &mut [Self::Score], change: Change<Self::Event>); /// Decides if `new` should push out `old` transaction from the pool. /// /// NOTE returning `InsertNew` here can lead to some transactions being accepted above pool limits. fn should_replace(&self, old: &T, new: &T) -> Choice; /// Decides if the transaction should ignore per-sender limit in the pool. /// /// If you return `true` for given transaction it's going to be accepted even though /// the per-sender limit is exceeded. fn should_ignore_sender_limit(&self, _new: &T) -> bool { false } } /// A score with a reference to the transaction. #[derive(Debug)] pub struct ScoreWithRef<T, S> { /// Score pub score: S, /// Shared transaction pub transaction: Transaction<T>, } impl<T, S> ScoreWithRef<T, S> { /// Creates a new `ScoreWithRef` pub fn new(score: S, transaction: Transaction<T>) -> Self { ScoreWithRef { score, transaction } } } impl<T, S: Clone> Clone for ScoreWithRef<T, S> { fn clone(&self) -> Self { ScoreWithRef { score: self.score.clone(), transaction: self.transaction.clone(), } } } impl<S: cmp::Ord, T> Ord for ScoreWithRef<T, S> { fn cmp(&self, other: &Self) -> cmp::Ordering { other.score.cmp(&self.score) .then(other.transaction.insertion_id.cmp(&self.transaction.insertion_id)) } } impl<S: cmp::Ord, T> PartialOrd for ScoreWithRef<T, S> { fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> { Some(self.cmp(other)) } } impl<S: cmp::Ord, T> PartialEq for ScoreWithRef<T, S> { fn eq(&self, other: &Self) -> bool { self.score == other.score && self.transaction.insertion_id == other.transaction.insertion_id } } impl<S: cmp::Ord, T> Eq for ScoreWithRef<T, S> {}