Skip to content

Instantly share code, notes, and snippets.

@RHavar
Created October 27, 2016 04:26
Show Gist options
  • Save RHavar/a2fe192e46a519965b01879eeade9874 to your computer and use it in GitHub Desktop.
Save RHavar/a2fe192e46a519965b01879eeade9874 to your computer and use it in GitHub Desktop.
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)
}
@utopia238
Copy link

@utopia238
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment