-
-
Save RHavar/a2fe192e46a519965b01879eeade9874 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::collections::HashMap; | |
use std::collections::HashSet; | |
use std::cmp::Ordering; | |
#[derive(Debug, Clone)] | |
pub struct Transaction { | |
pub txid: String, | |
pub fee: u64, // in satoshis | |
pub size: u64, // bytes | |
pub fee_rate: f64, // for debugging | |
pub ancestor_size: u64, // in bytes | |
pub ancestor_fees: u64, | |
pub depends: Vec<String>, // references by txid | |
} | |
#[derive(Debug, Clone)] | |
pub struct TransactionCluster<'a> { | |
pub transactions: Vec<&'a Transaction> | |
} | |
impl<'a> TransactionCluster<'a> { | |
pub fn new(capacity: usize) -> TransactionCluster<'a> { | |
TransactionCluster { | |
transactions: Vec::with_capacity(capacity) | |
} | |
} | |
pub fn size(&self) -> u64 { | |
let mut sum = 0; | |
for transaction in &self.transactions { | |
sum += transaction.size; | |
} | |
sum | |
} | |
pub fn fee(&self) -> u64 { | |
let mut sum = 0; | |
for transaction in &self.transactions { | |
sum += transaction.fee; | |
} | |
sum | |
} | |
pub fn fee_rate(&self) -> f64 { | |
(self.fee() as f64) / (self.size() as f64) | |
} | |
pub fn txids_string(&self) -> String { | |
let mut res = "[".to_string(); | |
for transaction in &self.transactions { | |
res.push('"'); | |
res.push_str(transaction.txid.as_str()); | |
res.push_str("\","); | |
} | |
res.push(']'); | |
res | |
} | |
} | |
// pool is a txid -> transaction | |
pub fn process(pool: &HashMap<String, Transaction>) -> Vec<TransactionCluster> { | |
let mut transactions: Vec<&Transaction> = pool.values().collect(); | |
expand_transactions(&mut transactions, pool) | |
} | |
// Goes through `transactions` and if they have any dependencies, it expands them | |
// unless it has already seen that dependency. | |
// Requires a mutable reference to transactions, because it in-place sorts it | |
fn expand_transactions<'a>( | |
transactions: &mut Vec<&'a Transaction>, | |
pool: &'a HashMap<String, Transaction> | |
) -> Vec<TransactionCluster<'a>> { | |
transactions.sort_by(|a, b| sort_by_ancestoral_fee_rate(*a, *b)); | |
let mut expanded = vec!(); | |
let mut picked: HashSet<*const Transaction> = HashSet::new(); | |
for transaction in transactions { | |
let mut ancestors = expand_transaction(transaction, pool); | |
ancestors.transactions.retain(|&ancestor| picked.insert(ancestor)); | |
if !ancestors.transactions.is_empty() { | |
expanded.push(ancestors);; // no point adding an empty cluster | |
} | |
} | |
// now we need to resort | |
expanded.sort_by(|a, b| sort_by_fee_rate(a, b)); | |
expanded | |
} | |
// ancestor includes itself, this flattens! | |
fn expand_transaction<'a>( | |
transaction: &'a Transaction, | |
pool: &'a HashMap<String, Transaction> | |
) -> TransactionCluster<'a> { // must includes the current transaction! | |
let mut deps = Vec::with_capacity(transaction.depends.len()); | |
// Push transactions one layer deep | |
for txid in &transaction.depends { | |
let dep = pool.get(txid); | |
match dep { | |
None => println!("Could not find {} in pool", txid), | |
Some(t) => { | |
deps.push(t); | |
} | |
} | |
} | |
let expanded = expand_transactions(&mut deps, pool); | |
// Now we're going to flatten this, to make a result... | |
let mut result = TransactionCluster::new(deps.len() + 1); | |
for cluster in expanded { | |
for transaction in cluster.transactions { | |
result.transactions.push(transaction) | |
} | |
} | |
result.transactions.push(transaction); | |
result | |
} | |
fn sort_by_ancestoral_fee_rate(a: &Transaction, b: &Transaction) -> Ordering { | |
let fee_rate_a = a.ancestor_fees / a.ancestor_size; | |
let fee_rate_b = b.ancestor_fees / b.ancestor_size; | |
// Note we are comparing b against a, to get the exact reverse (high fee shit should be first) | |
fee_rate_b.partial_cmp(&fee_rate_a).unwrap_or(Ordering::Equal) | |
} | |
fn sort_by_fee_rate(a: &TransactionCluster, b: &TransactionCluster) -> Ordering { | |
// Note we are comparing b against a, to get the exact reverse (high fee shit should be first) | |
b.fee_rate().partial_cmp(&a.fee_rate()).unwrap_or(Ordering::Equal) | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@15MariamS