This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1289

radixbuf: initial boilerplate
ClosedPublic

Authored by quark on Nov 2 2017, 2:45 PM.
Tags
None
Subscribers
jsgf

Details

Reviewers
jsgf
durham
Group Reviewers
Restricted Project
Commits
rFBHGX5c8a6bd3d751: radixbuf: initial boilerplate
Summary

This is an implementation of the radix tree in Rust that converts [u8] to
integers. It is intended to be used as a basic building block for efficient
source-control related key-value lookups. For example, to convert a commit
hash to an internal number (ex. revision number).

The file format is quite similar to the C radix tree implementation in
mercurial/cext/revlog.c, with some improvements:

  • Not coupled with CPython APIs
  • Not coupled with revlog or revision numbers
  • Not coupled with malloc / realloc so the abstraction managing the buffer could be more flexible
  • Support variant-length keys
  • Explicitly use little-endian so the format is platform-independent
Test Plan

cargo test --lib

Diff Detail

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

Event Timeline

quark created this revision.Nov 2 2017, 2:45 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 2 2017, 2:45 PM
jsgf requested changes to this revision.Nov 2 2017, 3:54 PM
jsgf added a subscriber: jsgf.
jsgf added inline comments.
rust/radix204/src/constants.rs
8 ↗(On Diff #3209)

Why not define this next to where the type is defined? Or even part of the type itself, so you can use KeyId::MAX.

9 ↗(On Diff #3209)

This seems super-brittle. What if we ever wanted a different size hash, or some kind of other per-key metadata (like what kind of entity its a reference to)?

rust/radix204/src/types.rs
13–14

Why not use newtypes for these? Ie

#[derive(Debug, Eq, Partialeq, ...)]
pub struct KeyId(u32);

Then you can control how they get used, they'll print distinctively in debug output, etc.

This revision now requires changes to proceed.Nov 2 2017, 3:54 PM
quark added inline comments.Nov 2 2017, 6:35 PM
rust/radix204/src/constants.rs
8 ↗(On Diff #3209)

They were defined in types.rs until I thought types was not an accurate word for them.

9 ↗(On Diff #3209)

I was using it as a constant somewhere. Since both const fn (ideally mem::size_of) and associated consts are unstable. Now that I scan the code base it does not have to be a constant. I'll make it a function.

rust/radix204/src/types.rs
13–14

Was doing that until I found I need to redefine lots of proxy methods. But that is actually cleaner since required methods are explicitly listed. Will change.

quark edited the summary of this revision. (Show Details)Nov 3 2017, 2:17 AM
quark updated this revision to Diff 3249.
quark edited the summary of this revision. (Show Details)Nov 6 2017, 2:10 PM
quark edited the test plan for this revision. (Show Details)
quark updated this revision to Diff 3294.
quark edited the summary of this revision. (Show Details)Nov 11 2017, 1:33 AM
quark retitled this revision from radix204: initial boilerplate to radix20: initial boilerplate.
quark updated this revision to Diff 3417.
quark edited the summary of this revision. (Show Details)Nov 15 2017, 8:55 PM
quark retitled this revision from radix20: initial boilerplate to radixbuf: initial boilerplate.
quark updated this revision to Diff 3543.
durham accepted this revision.Nov 29 2017, 4:43 PM
Closed by commit rFBHGX5c8a6bd3d751: radixbuf: initial boilerplate (authored by quark). · Explain WhyDec 15 2017, 2:34 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 3294

rust/radix204/Cargo.toml

  • This file was added.
[package]
name = "radix204"
version = "0.1.0"
[dependencies]
error-chain = "0.11"
[dev-dependencies]
quickcheck = "0.4"
rand = "0.3"
rand_derive = "0.3"
rustc-test = "0.2"

rust/radix204/README.md

  • This file was added.
# radix204
20-byte to 4-byte mapping using a radix tree stored on plain buffers.
There are 2 plain buffers:
- KeyBuffer: store 20-bytes keys and look them up using their offsets, read-only to the library.
- RadixBuffer: store radix tree nodes and key offsets, managed, read-write by the library.
`radix204` was designed for some specific use-cases efficiently. So it does not have some generic interface, like:
- Storing extra values
- Deletion
- Variant-length keys
- Long offset (64-bit integer) support
Applications may want to change KeyBuffer format so a `Key` is followed by a `Value` that the application cares about. The `Value` could be a complex structure that includes a deletion flag or a link to another `Value` (linked list).
Variant-length keys and long offsets could in theory be added at the cost of introducing many type parameters (especially around the iterator interface), and double the storage size.

rust/radix204/src/errors.rs

  • This file was added.
// Copyright 2017 Facebook, Inc.
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
use types::KeyId;
error_chain! {
errors {
OffsetOverflow(offset: usize) {
description("offset overflow")
display("offset {} is out of range", offset)
}
}
}

rust/radix204/src/lib.rs

  • This file was added.
// Copyright 2017 Facebook, Inc.
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
#[cfg(test)]
extern crate test;
#[macro_use]
extern crate error_chain;
#[cfg(test)]
#[macro_use]
extern crate quickcheck;
#[cfg(test)]
extern crate rand;
#[cfg(test)]
#[macro_use]
extern crate rand_derive;
pub mod types;
pub mod errors;

rust/radix204/src/types.rs

  • This file was added.
// Copyright 2017 Facebook, Inc.
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
use std::borrow::Borrow;
use std::cell::RefCell;
use std::rc::Rc;
use std::ops::Deref;
use std::convert::{From, Into};
use errors::{Result, ErrorKind};
pub type Shared<B> = Rc<RefCell<B>>;
jsgfUnsubmitted
Not Done

Why not use newtypes for these? Ie

#[derive(Debug, Eq, Partialeq, ...)]
pub struct KeyId(u32);

Then you can control how they get used, they'll print distinctively in debug output, etc.

jsgf: Why not use newtypes for these? Ie ``` #[derive(Debug, Eq, Partialeq, ...)] pub struct KeyId…
quarkAuthorUnsubmitted
Not Done

Was doing that until I found I need to redefine lots of proxy methods. But that is actually cleaner since required methods are explicitly listed. Will change.

quark: Was doing that until I found I need to redefine lots of proxy methods. But that is actually…
#[cfg(not(test))]
#[derive(Debug, Eq, PartialEq, PartialOrd, Ord, Clone, Copy, Default, Hash)]
pub struct Key([u8; 20]);
#[cfg(test)]
#[derive(Debug, Eq, PartialEq, PartialOrd, Ord, Clone, Copy, Default, Hash, Rand)]
pub struct Key([u8; 20]);
impl Key {
#[inline]
pub fn fixed_len() -> usize { 20 }
}
impl<T: Borrow<[u8; 20]>> From<T> for Key {
#[inline]
fn from(v: T) -> Self { Key(*v.borrow()) }
}
impl Deref for Key {
type Target = [u8; 20];
#[inline]
fn deref(&self) -> &Self::Target { &self.0 }
}
#[derive(Debug, Eq, PartialEq, PartialOrd, Ord, Clone, Copy, Default)]
pub struct KeyId(u32);
#[derive(Debug, Eq, PartialEq, PartialOrd, Ord, Clone, Copy, Default)]
pub struct Offset(u32);
macro_rules! impl_u32_type {
($T: ident) => (
impl $T {
#[inline]
pub fn to_usize(&self) -> usize { self.0 as usize }
}
impl From<u32> for $T {
#[inline]
fn from(v: u32) -> Self { $T(v) }
}
impl Into<u32> for $T {
#[inline]
fn into(self) -> u32 { self.0 }
}
)
}
impl_u32_type!(KeyId);
impl_u32_type!(Offset);
impl KeyId {
/// The LSB of Offset is reserved to indicate whether it is a KeyId or not
#[inline]
pub fn to_encoded_offset(&self) -> Result<Offset> {
if self.0 as usize > 0x7fff_ffff {
return Err(ErrorKind::OffsetOverflow(self.0 as usize).into())
}
Ok((self.0 << 1 | 1).into())
}
}