use parking_lot::RwLock;
use schnellru::{ByLength, LruMap};
use sp_runtime::traits::{Block as BlockT, Header, NumberFor, One};
const LRU_CACHE_SIZE: u32 = 5_000;
pub fn lowest_common_ancestor<Block: BlockT, T: HeaderMetadata<Block> + ?Sized>(
backend: &T,
id_one: Block::Hash,
id_two: Block::Hash,
) -> Result<HashAndNumber<Block>, T::Error> {
let mut header_one = backend.header_metadata(id_one)?;
if header_one.parent == id_two {
return Ok(HashAndNumber { hash: id_two, number: header_one.number - One::one() })
}
let mut header_two = backend.header_metadata(id_two)?;
if header_two.parent == id_one {
return Ok(HashAndNumber { hash: id_one, number: header_one.number })
}
let mut orig_header_one = header_one.clone();
let mut orig_header_two = header_two.clone();
while header_one.number > header_two.number {
let ancestor_one = backend.header_metadata(header_one.ancestor)?;
if ancestor_one.number >= header_two.number {
header_one = ancestor_one;
} else {
break
}
}
while header_one.number < header_two.number {
let ancestor_two = backend.header_metadata(header_two.ancestor)?;
if ancestor_two.number >= header_one.number {
header_two = ancestor_two;
} else {
break
}
}
while header_one.hash != header_two.hash {
if header_one.number > header_two.number {
header_one = backend.header_metadata(header_one.parent)?;
} else {
header_two = backend.header_metadata(header_two.parent)?;
}
}
if orig_header_one.number > header_one.number {
orig_header_one.ancestor = header_one.hash;
backend.insert_header_metadata(orig_header_one.hash, orig_header_one);
}
if orig_header_two.number > header_one.number {
orig_header_two.ancestor = header_one.hash;
backend.insert_header_metadata(orig_header_two.hash, orig_header_two);
}
Ok(HashAndNumber { hash: header_one.hash, number: header_one.number })
}
pub fn tree_route<Block: BlockT, T: HeaderMetadata<Block>>(
backend: &T,
from: Block::Hash,
to: Block::Hash,
) -> Result<TreeRoute<Block>, T::Error> {
let mut from = backend.header_metadata(from)?;
let mut to = backend.header_metadata(to)?;
let mut from_branch = Vec::new();
let mut to_branch = Vec::new();
while to.number > from.number {
to_branch.push(HashAndNumber { number: to.number, hash: to.hash });
to = backend.header_metadata(to.parent)?;
}
while from.number > to.number {
from_branch.push(HashAndNumber { number: from.number, hash: from.hash });
from = backend.header_metadata(from.parent)?;
}
while to.hash != from.hash {
to_branch.push(HashAndNumber { number: to.number, hash: to.hash });
to = backend.header_metadata(to.parent)?;
from_branch.push(HashAndNumber { number: from.number, hash: from.hash });
from = backend.header_metadata(from.parent)?;
}
let pivot = from_branch.len();
from_branch.push(HashAndNumber { number: to.number, hash: to.hash });
from_branch.extend(to_branch.into_iter().rev());
Ok(TreeRoute { route: from_branch, pivot })
}
#[derive(Debug, Clone)]
pub struct HashAndNumber<Block: BlockT> {
pub number: NumberFor<Block>,
pub hash: Block::Hash,
}
#[derive(Debug, Clone)]
pub struct TreeRoute<Block: BlockT> {
route: Vec<HashAndNumber<Block>>,
pivot: usize,
}
impl<Block: BlockT> TreeRoute<Block> {
pub fn new(route: Vec<HashAndNumber<Block>>, pivot: usize) -> Result<Self, String> {
if pivot < route.len() {
Ok(TreeRoute { route, pivot })
} else {
Err(format!(
"TreeRoute pivot ({}) should be less than route length ({})",
pivot,
route.len()
))
}
}
pub fn retracted(&self) -> &[HashAndNumber<Block>] {
&self.route[..self.pivot]
}
pub fn into_retracted(mut self) -> Vec<HashAndNumber<Block>> {
self.route.truncate(self.pivot);
self.route
}
pub fn common_block(&self) -> &HashAndNumber<Block> {
self.route.get(self.pivot).expect(
"tree-routes are computed between blocks; \
which are included in the route; \
thus it is never empty; qed",
)
}
pub fn enacted(&self) -> &[HashAndNumber<Block>] {
&self.route[self.pivot + 1..]
}
pub fn last(&self) -> Option<&HashAndNumber<Block>> {
self.route.last()
}
}
pub trait HeaderMetadata<Block: BlockT> {
type Error: std::error::Error;
fn header_metadata(
&self,
hash: Block::Hash,
) -> Result<CachedHeaderMetadata<Block>, Self::Error>;
fn insert_header_metadata(
&self,
hash: Block::Hash,
header_metadata: CachedHeaderMetadata<Block>,
);
fn remove_header_metadata(&self, hash: Block::Hash);
}
pub struct HeaderMetadataCache<Block: BlockT> {
cache: RwLock<LruMap<Block::Hash, CachedHeaderMetadata<Block>>>,
}
impl<Block: BlockT> HeaderMetadataCache<Block> {
pub fn new(capacity: u32) -> Self {
HeaderMetadataCache { cache: RwLock::new(LruMap::new(ByLength::new(capacity))) }
}
}
impl<Block: BlockT> Default for HeaderMetadataCache<Block> {
fn default() -> Self {
HeaderMetadataCache { cache: RwLock::new(LruMap::new(ByLength::new(LRU_CACHE_SIZE))) }
}
}
impl<Block: BlockT> HeaderMetadataCache<Block> {
pub fn header_metadata(&self, hash: Block::Hash) -> Option<CachedHeaderMetadata<Block>> {
self.cache.write().get(&hash).cloned()
}
pub fn insert_header_metadata(&self, hash: Block::Hash, metadata: CachedHeaderMetadata<Block>) {
self.cache.write().insert(hash, metadata);
}
pub fn remove_header_metadata(&self, hash: Block::Hash) {
self.cache.write().remove(&hash);
}
}
#[derive(Debug, Clone)]
pub struct CachedHeaderMetadata<Block: BlockT> {
pub hash: Block::Hash,
pub number: NumberFor<Block>,
pub parent: Block::Hash,
pub state_root: Block::Hash,
ancestor: Block::Hash,
}
impl<Block: BlockT> From<&Block::Header> for CachedHeaderMetadata<Block> {
fn from(header: &Block::Header) -> Self {
CachedHeaderMetadata {
hash: header.hash(),
number: *header.number(),
parent: *header.parent_hash(),
state_root: *header.state_root(),
ancestor: *header.parent_hash(),
}
}
}