This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1219

radixbuf: add serialization support for linked nodes
AbandonedPublic

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

Details

Reviewers
None
Group Reviewers
Restricted Project
Summary

The radixlink [1] used "linked list of integers" as its value type. That is
important for the obsstore usecase. For example, with "obsoleted node" as
the index key, "obsmarker offset" as the index value. One key could map to
multiple (but not too many) values.

Value types in radixbuf depends heavily on serialization. So let's add a
"LinkedNode" type with serialization support.

[1]: https://www.mercurial-scm.org/pipermail/mercurial-devel/2017-June/099184.html

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:12 PM
quark edited the summary of this revision. (Show Details)Oct 23 2017, 4:47 PM
quark edited the test plan for this revision. (Show Details)
quark abandoned this revision.Oct 23 2017, 11:59 PM

Seems better to implement the "Linked List" in Radix Index layer.

Revision Contents
Changeset List

Diff 3069

rust/radixbuf/src/serialize.rs

fn read_from<R: Read>(r: &mut R) -> io::Result<Self> { fn read_from<R: Read>(r: &mut R) -> io::Result<Self> {
let len: usize = r.read_vlq()?; let len: usize = r.read_vlq()?;
let mut buf = vec![0u8; len]; let mut buf = vec![0u8; len];
r.read_exact(&mut buf)?; r.read_exact(&mut buf)?;
Ok(VariantBytes(buf)) Ok(VariantBytes(buf))
} }
} }
#[derive(Debug, PartialEq, Clone)]
pub struct LinkedNode<T>(T, Offset<LinkedNode<T>>);
impl<T> LinkedNode<T> {
pub fn new(value: T, offset: Offset<LinkedNode<T>>) -> Self { LinkedNode(value, offset) }
}
impl<T: Serialize> Serialize for LinkedNode<T> {
fn write_to<W: Write>(&self, w: &mut W) -> io::Result<()> {
self.0.write_to(w)?;
self.1.write_to(w)
}
fn read_from<R: Read>(r: &mut R) -> io::Result<Self> {
let value: T = T::read_from(r)?;
let offset = Offset::read_from(r)?;
Ok(LinkedNode::new(value, offset))
}
}
impl<T: FixedSizedSerialize> FixedSizedSerialize for LinkedNode<T> {}
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)
} }
fn shrink(&self) -> Box<Iterator<Item = Self>> { unimplemented!() } fn shrink(&self) -> Box<Iterator<Item = Self>> { unimplemented!() }
} }
impl Arbitrary for VariantBytes { impl Arbitrary for VariantBytes {
fn arbitrary<G: Gen>(gen: &mut G) -> Self { VariantBytes::new(Vec::<u8>::arbitrary(gen)) } fn arbitrary<G: Gen>(gen: &mut G) -> Self { VariantBytes::new(Vec::<u8>::arbitrary(gen)) }
fn shrink(&self) -> Box<Iterator<Item = Self>> { unimplemented!() } fn shrink(&self) -> Box<Iterator<Item = Self>> { unimplemented!() }
} }
impl<T: Arbitrary> Arbitrary for LinkedNode<T> {
fn arbitrary<G: Gen>(gen: &mut G) -> Self {
LinkedNode::new(T::arbitrary(gen), unsafe {
Offset::from_raw(u64::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());
} }
fn test_round_trip_u32(v: Vec<u32>) -> bool { fn test_round_trip_u32(v: Vec<u32>) -> bool {
check_round_trip(v) check_round_trip(v)
} }
fn test_round_trip_u64(v: Vec<u64>) -> bool { fn test_round_trip_u64(v: Vec<u64>) -> bool {
check_round_trip(v) check_round_trip(v)
} }
fn test_round_trip_linkednode_variantbytes(v: Vec<LinkedNode<VariantBytes>>) -> bool {
check_round_trip(v)
}
fn test_round_trip_linkednode_u32(v: Vec<LinkedNode<u32>>) -> bool {
check_round_trip(v)
}
} }
#[test] #[test]
fn test_rewrite() { fn test_rewrite() {
let mut buf = Buffer(Rc::new(RefCell::new(Cursor::new(vec![])))); let mut buf = Buffer(Rc::new(RefCell::new(Cursor::new(vec![]))));
let offsets: Vec<Offset<u32>> = (200..203u32).map(|i| buf.push(&i).unwrap()).collect(); let offsets: Vec<Offset<u32>> = (200..203u32).map(|i| buf.push(&i).unwrap()).collect();
buf.rewrite(offsets[1], &400u32).expect("rewrite"); buf.rewrite(offsets[1], &400u32).expect("rewrite");
assert_eq!(buf.retrieve::<u32>(offsets[0]).unwrap(), 200); assert_eq!(buf.retrieve::<u32>(offsets[0]).unwrap(), 200);
assert_eq!(buf.retrieve::<u32>(offsets[1]).unwrap(), 400); assert_eq!(buf.retrieve::<u32>(offsets[1]).unwrap(), 400);
assert_eq!(buf.retrieve::<u32>(offsets[2]).unwrap(), 202); assert_eq!(buf.retrieve::<u32>(offsets[2]).unwrap(), 202);
} }
} }