This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1218

radixbuf: add serialization support for keys (byte arrays)
AbandonedPublic

Authored by quark on Oct 23 2017, 4:12 PM.
Tags
None
Subscribers
durin42

Details

Reviewers
None
Group Reviewers
Restricted Project
Summary

The radix tree index is intended to be compact. Often, the keys in the index
exists in another file (or called "buffer"). Therefore storing full keys in
the index itself is a waste of space. We can store offsets instead.

This patch implements serialization for a byte array (either fixed 20-byte,
or has a variable length). So we can convert between byte arrays and
offsets.

For cases where we know the mapping already (ex. revlog has a node <->
revision number) mapping, we can "abuse" the serialize interface to return
revision numbers instead of actual buffer offsets and leave "write_to"
unimplemented.

Test Plan

cargo test

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

quark created this revision.Oct 23 2017, 4:12 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptOct 23 2017, 4:12 PM
quark added a subscriber: durin42.Oct 23 2017, 4:13 PM
quark abandoned this revision.Nov 2 2017, 2:48 PM

This is actually over-engineering. D1292 series does not need serialize support.

Revision Contents
Changeset List

Diff 3068

rust/radixbuf/src/serialize.rs

//! Simple serialization that converts between T and an offset //! Simple serialization that converts between T and an offset
use std::cell::RefCell; use std::cell::RefCell;
use std::io::{self, Read, Write, Seek, SeekFrom, ErrorKind}; use std::io::{self, Read, Write, Seek, SeekFrom, ErrorKind};
use std::marker::PhantomData; use std::marker::PhantomData;
use std::mem::transmute; use std::mem::transmute;
use std::ops::DerefMut; use std::ops::DerefMut;
use std::rc::Rc; use std::rc::Rc;
use vlqencoding::{VLQEncode, VLQDecode};
/// Minimal serializable abstraction. /// Minimal serializable abstraction.
pub trait Serialize: Sized { pub trait Serialize: Sized {
fn write_to<W: Write>(&self, w: &mut W) -> io::Result<()>; fn write_to<W: Write>(&self, w: &mut W) -> io::Result<()>;
fn read_from<R: Read>(r: &mut R) -> io::Result<Self>; fn read_from<R: Read>(r: &mut R) -> io::Result<Self>;
} }
/// Indicates a type will be serialized into fixed number of bytes. /// Indicates a type will be serialized into fixed number of bytes.
let mut cur = self.0.try_borrow_mut().or( let mut cur = self.0.try_borrow_mut().or(
Err(ErrorKind::ConnectionRefused), Err(ErrorKind::ConnectionRefused),
)?; )?;
cur.seek(SeekFrom::Start(pos.0 as u64))?; cur.seek(SeekFrom::Start(pos.0 as u64))?;
S::read_from(cur.deref_mut()) S::read_from(cur.deref_mut())
} }
} }
#[derive(Debug, PartialEq, Copy, Clone)]
pub struct TwentyBytes([u8; 20]);
impl TwentyBytes {
pub fn new(bytes: [u8; 20]) -> Self { TwentyBytes(bytes) }
}
impl Serialize for TwentyBytes {
fn write_to<W: Write>(&self, w: &mut W) -> io::Result<()> { w.write_all(&self.0) }
fn read_from<R: Read>(r: &mut R) -> io::Result<Self> {
let mut buf = [0u8; 20];
r.read_exact(&mut buf)?;
Ok(TwentyBytes(buf))
}
}
impl FixedSizedSerialize for TwentyBytes {}
#[derive(Debug, PartialEq, Clone)]
pub struct VariantBytes(Vec<u8>);
impl VariantBytes {
pub fn new(bytes: Vec<u8>) -> Self { VariantBytes(bytes) }
}
impl Serialize for VariantBytes {
fn write_to<W: Write>(&self, w: &mut W) -> io::Result<()> {
w.write_vlq(self.0.len())?;
w.write_all(&self.0)
}
fn read_from<R: Read>(r: &mut R) -> io::Result<Self> {
let len: usize = r.read_vlq()?;
let mut buf = vec![0u8; len];
r.read_exact(&mut buf)?;
Ok(VariantBytes(buf))
}
}
macro_rules! impl_serialize_unsigned { macro_rules! impl_serialize_unsigned {
($T: ty, $S: expr) => { ($T: ty, $S: expr) => {
impl Serialize for $T { impl Serialize for $T {
fn write_to<W: Write>(&self, w: &mut W) -> io::Result<()> { fn write_to<W: Write>(&self, w: &mut W) -> io::Result<()> {
let buf: [u8; $S] = unsafe { transmute(self.to_be()) }; let buf: [u8; $S] = unsafe { transmute(self.to_be()) };
w.write_all(&buf) w.write_all(&buf)
} }
impl_serialize_unsigned!(u8, 1); impl_serialize_unsigned!(u8, 1);
impl_serialize_unsigned!(u16, 2); impl_serialize_unsigned!(u16, 2);
impl_serialize_unsigned!(u32, 4); impl_serialize_unsigned!(u32, 4);
impl_serialize_unsigned!(u64, 8); impl_serialize_unsigned!(u64, 8);
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use quickcheck::{Arbitrary, Gen};
use serialize::*; use serialize::*;
use std::boxed::Box; use std::boxed::Box;
use std::cell::RefCell; use std::cell::RefCell;
use std::fmt::Debug; use std::fmt::Debug;
use std::io::Cursor; use std::io::Cursor;
use std::rc::Rc; use std::rc::Rc;
impl Arbitrary for TwentyBytes {
fn arbitrary<G: Gen>(gen: &mut G) -> Self {
let x = u64::arbitrary(gen);
let y = u64::arbitrary(gen);
let z = u32::arbitrary(gen);
TwentyBytes::new(
[
((z >> 24) & 0xff) as u8,
((z >> 16) & 0xff) as u8,
((z >> 8) & 0xff) as u8,
((z >> 0) & 0xff) as u8,
((y >> 56) & 0xff) as u8,
((y >> 48) & 0xff) as u8,
((y >> 40) & 0xff) as u8,
((y >> 32) & 0xff) as u8,
((y >> 24) & 0xff) as u8,
((y >> 16) & 0xff) as u8,
((y >> 8) & 0xff) as u8,
((y >> 0) & 0xff) as u8,
((x >> 56) & 0xff) as u8,
((x >> 48) & 0xff) as u8,
((x >> 40) & 0xff) as u8,
((x >> 32) & 0xff) as u8,
((x >> 24) & 0xff) as u8,
((x >> 16) & 0xff) as u8,
((x >> 8) & 0xff) as u8,
((x >> 0) & 0xff) as u8,
],
)
}
fn shrink(&self) -> Box<Iterator<Item = Self>> { unimplemented!() }
}
impl Arbitrary for VariantBytes {
fn arbitrary<G: Gen>(gen: &mut G) -> Self { VariantBytes::new(Vec::<u8>::arbitrary(gen)) }
fn shrink(&self) -> Box<Iterator<Item = Self>> { unimplemented!() }
}
fn check_round_trip<T: Serialize + Clone + PartialEq + Debug>(keys: Vec<T>) -> bool { fn check_round_trip<T: Serialize + Clone + PartialEq + Debug>(keys: Vec<T>) -> bool {
let mut buf = Buffer(Rc::new(RefCell::new(Cursor::new(vec![])))); let mut buf = Buffer(Rc::new(RefCell::new(Cursor::new(vec![]))));
let mut offsets: Vec<Offset<T>> = vec![]; let mut offsets: Vec<Offset<T>> = vec![];
// Push keys // Push keys
for k in keys.iter() { for k in keys.iter() {
offsets.push(buf.push(k).unwrap()); offsets.push(buf.push(k).unwrap());
} }
// Check keys // Check keys
offsets.iter().enumerate().all(|(i, offset)| { offsets.iter().enumerate().all(|(i, offset)| {
(buf.retrieve::<T>(offset.clone())).unwrap() == keys[i] (buf.retrieve::<T>(offset.clone())).unwrap() == keys[i]
}) })
} }
quickcheck! { quickcheck! {
fn test_round_trip_twentybytes(v: Vec<TwentyBytes>) -> bool {
check_round_trip(v)
}
fn test_round_trip_variantbytes(v: Vec<VariantBytes>) -> bool {
check_round_trip(v)
}
fn test_round_trip_u8(v: Vec<u8>) -> bool { fn test_round_trip_u8(v: Vec<u8>) -> bool {
check_round_trip(v) check_round_trip(v)
} }
fn test_round_trip_u16(v: Vec<u16>) -> bool { fn test_round_trip_u16(v: Vec<u16>) -> bool {
check_round_trip(v) check_round_trip(v)
} }