diff --git a/rust/radixbuf/src/errors.rs b/rust/radixbuf/src/errors.rs
--- a/rust/radixbuf/src/errors.rs
+++ b/rust/radixbuf/src/errors.rs
@@ -3,11 +3,17 @@
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
+use key::KeyId;
+
error_chain! {
foreign_links {
Io(::std::io::Error);
}
errors {
+ InvalidKeyId(key_id: KeyId) {
+ description("invalid key id")
+ display("{:?} cannot be resolved", key_id)
+ }
}
}
diff --git a/rust/radixbuf/src/key.rs b/rust/radixbuf/src/key.rs
new file mode 100644
--- /dev/null
+++ b/rust/radixbuf/src/key.rs
@@ -0,0 +1,179 @@
+// 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.
+
+//! Types and helper functions to convert a `KeyId` to a Key (`[u8]`). The radix index is
+//! responsible for the other direction - `[u8]` to `KeyId`. This mapping is to remove the
+//! need of storing full keys in the radix index.
+//!
+//! Typically, there is an append-only file which is the source of truth of some information.
+//! The `KeyId` could be offsets in that file.
+//!
+//! The radix index APIs only care about how to read a key, given a `KeyId`. It does not
+//! care about how to write a key. This is more flexible. For example, the source of truth
+//! file may have keys stored already before the index gets built. The `append` methods provided
+//! below are only for convenience.
+//!
+//! There could be cases where the `KeyId`s are not offsets, or the keys are not stored as-is.
+//! For example, `KeyId` could be mercurial revision numbers instead of offsets for non-inlined
+//! revlog .i files. The radix index has a limitation (to make the format slightly more compact)
+//! that one key cannot be the prefix of another different key. This could be guaranteed by using
+//! the fixed length key, or appending `'\0'` to strings that cannot have `'\0'`. But in case
+//! of variant-length binary key, some escaping is needed to avoid the prefix conflict. The
+//! escaping logic might be implemented as key read/write functions.
+
+use errors::{Result, ErrorKind};
+use traits::Resize;
+use vlqencoding::{VLQEncode, VLQDecode};
+use std::io::{Write, Cursor, Seek, SeekFrom};
+
+/// Integer that maps to a key (`[u8]`).
+#[derive(Debug, Eq, PartialEq, PartialOrd, Ord, Clone, Copy, Default)]
+pub struct KeyId(u32);
+
+macro_rules! impl_convert {
+ ($T: ty) => (
+ impl From<$T> for KeyId {
+ #[allow(unused_comparisons)]
+ #[inline]
+ fn from(v: $T) -> Self {
+ if v > 0xffff_ffff || v < 0 {
+ panic!("KeyId out of range")
+ }
+ KeyId(v as u32)
+ }
+ }
+
+ impl Into<$T> for KeyId {
+ #[inline]
+ fn into(self) -> $T { self.0 as $T }
+ }
+ )
+}
+
+impl_convert!(u32);
+impl_convert!(u64);
+
+// Make sure `usize` contains at least 4 bytes (`KeyId` size).
+const _SIZE_TEST: usize = 0xffff_ffff;
+impl_convert!(usize);
+
+/// Keys with fixed 20 bytes length.
+pub struct FixedKey;
+
+/// Keys with variant-length. Serialized as a VLQ-encoded length, followed by the actual key.
+pub struct VariantKey;
+
+impl FixedKey {
+ #[inline]
+ pub fn read<'a, K: AsRef<[u8]>>(key_buf: &'a K, key_id: KeyId) -> Result<&'a [u8]> {
+ let key_buf = key_buf.as_ref();
+ let start_pos: usize = key_id.into();
+ // LANG: Consider making 20 a type parameter once supported.
+ let end_pos = start_pos + 20;
+ if key_buf.len() < end_pos {
+ bail!(ErrorKind::InvalidKeyId(key_id));
+ }
+ Ok(&key_buf[start_pos..end_pos])
+ }
+
+ #[inline]
+ pub fn append<B: AsMut<[u8]> + Resize<u8>, K: AsRef<[u8]>>(key_buf: &mut B, key: &K) -> KeyId {
+ let key = key.as_ref();
+ assert_eq!(key.len(), 20);
+
+ let pos = key_buf.as_mut().len();
+ key_buf.resize(pos + 20, 0);
+ let key_buf = key_buf.as_mut();
+ key_buf[pos..pos + 20].copy_from_slice(key);
+ pos.into()
+ }
+}
+
+impl VariantKey {
+ #[inline]
+ pub fn read<'a, K: AsRef<[u8]>>(key_buf: &'a K, key_id: KeyId) -> Result<&'a [u8]> {
+ let key_buf = key_buf.as_ref();
+ let mut reader = Cursor::new(key_buf);
+ reader.seek(SeekFrom::Start(key_id.into()))?;
+ let key_len: usize = reader.read_vlq()?;
+
+ let start_pos = reader.seek(SeekFrom::Current(0))? as usize;
+ let end_pos = start_pos + key_len;
+ if key_buf.len() < end_pos {
+ bail!(ErrorKind::InvalidKeyId(key_id))
+ }
+ Ok(&key_buf[start_pos as usize..end_pos as usize])
+ }
+
+ #[inline]
+ pub fn append<B: AsMut<[u8]> + Resize<u8>, K: AsRef<[u8]>>(key_buf: &mut B, key: &K) -> KeyId {
+ let key = key.as_ref();
+ // PERF: the Vec allocation may be avoided with a more complex implementation.
+ // Most of the time, key length could be encoded in 2-byte VLQ. Pre-allocate 2 bytes.
+ let mut buf = Vec::<u8>::with_capacity(key.len() + 2);
+ buf.write_vlq(key.len()).expect("write len");
+ buf.write_all(key).expect("write key");
+
+ let pos = key_buf.as_mut().len();
+ key_buf.resize(pos + buf.len(), 0);
+ let key_buf = key_buf.as_mut();
+ key_buf[pos..pos + buf.len()].copy_from_slice(&buf[..]);
+ (pos as u64).into()
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use rand::{thread_rng, Rng};
+
+ #[test]
+ fn test_variant_key_round_trip() {
+ let mut rng = thread_rng();
+ let mut buf = Vec::<u8>::new();
+ let keys: Vec<Vec<u8>> = (0..1000usize)
+ .map(|i| {
+ rng.gen_ascii_chars()
+ .take(i % 40)
+ .map(|ch| ch as u8)
+ .collect()
+ })
+ .collect();
+ let key_ids: Vec<KeyId> = keys.iter()
+ .map(|key| VariantKey::append(&mut buf, key))
+ .collect();
+ let keys_retrieved: Vec<Vec<u8>> = key_ids
+ .iter()
+ .map(|&id| VariantKey::read(&buf, id).unwrap().to_vec())
+ .collect();
+ assert_eq!(keys, keys_retrieved);
+ }
+
+ #[test]
+ fn test_fixed_key_round_trip() {
+ let mut rng = thread_rng();
+ let mut buf = Vec::<u8>::new();
+ let keys: Vec<[u8; 20]> = (0..1000usize)
+ .map(|_| {
+ let mut bytes = [0u8; 20];
+ rng.fill_bytes(&mut bytes);
+ bytes
+ })
+ .collect();
+ let key_ids: Vec<KeyId> = keys.iter()
+ .map(|key| FixedKey::append(&mut buf, key))
+ .collect();
+ assert_eq!(buf.len(), 1000 * 20);
+ let keys_retrieved: Vec<[u8; 20]> = key_ids
+ .iter()
+ .map(|&id| {
+ let mut bytes = [0u8; 20];
+ bytes.copy_from_slice(FixedKey::read(&buf, id).unwrap());
+ bytes
+ })
+ .collect();
+ assert_eq!(keys, keys_retrieved);
+ }
+}
diff --git a/rust/radixbuf/src/lib.rs b/rust/radixbuf/src/lib.rs
--- a/rust/radixbuf/src/lib.rs
+++ b/rust/radixbuf/src/lib.rs
@@ -20,3 +20,5 @@
pub mod errors;
pub mod base16;
+pub mod key;
+pub mod traits;
diff --git a/rust/radixbuf/src/traits.rs b/rust/radixbuf/src/traits.rs
new file mode 100644
--- /dev/null
+++ b/rust/radixbuf/src/traits.rs
@@ -0,0 +1,16 @@
+// 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.
+
+//! Traits that makes the API more flexible.
+
+/// Support `resize` in-place. Used for appending new nodes.
+pub trait Resize<T> {
+ fn resize(&mut self, new_len: usize, value: T);
+}
+
+impl<T: Copy> Resize<T> for Vec<T> {
+ #[inline]
+ fn resize(&mut self, new_len: usize, value: T) { Vec::resize(self, new_len, value) }
+}