diff --git a/rust/indexes/Cargo.toml b/rust/indexes/Cargo.toml
new file mode 100644
--- /dev/null
+++ b/rust/indexes/Cargo.toml
@@ -0,0 +1,14 @@
+[package]
+name = "indexes"
+version = "0.1.0"
+
+[profile.release]
+lto = true
+
+[lib]
+name = "indexes"
+crate-type = ["cdylib"]
+
+[dependencies]
+radixbuf = { path = "../radixbuf" }
+error-chain = "0.11"
diff --git a/rust/indexes/src/errors.rs b/rust/indexes/src/errors.rs
new file mode 100644
--- /dev/null
+++ b/rust/indexes/src/errors.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.
+
+error_chain! {
+ foreign_links {
+ Radix(::radixbuf::errors::Error);
+ }
+
+ errors {
+ IndexCorrupted {
+ description("corrupted index")
+ }
+ }
+}
diff --git a/rust/indexes/src/lib.rs b/rust/indexes/src/lib.rs
new file mode 100644
--- /dev/null
+++ b/rust/indexes/src/lib.rs
@@ -0,0 +1,11 @@
+// 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.
+
+#[macro_use]
+extern crate error_chain;
+extern crate radixbuf;
+
+pub mod errors;
+pub mod nodemap;
diff --git a/rust/indexes/src/nodemap.rs b/rust/indexes/src/nodemap.rs
new file mode 100644
--- /dev/null
+++ b/rust/indexes/src/nodemap.rs
@@ -0,0 +1,247 @@
+// 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::u32;
+use errors::{Result, ResultExt, ErrorKind};
+use radixbuf::radix::{radix_lookup, radix_prefix_lookup, radix_lookup_unchecked, radix_insert};
+use radixbuf::key::KeyId;
+use radixbuf::errors as rerrors;
+
+/// An index for node to rev lookups.
+///
+/// The index depends entirely on an append-only changelog.i source
+/// of truth. It does not support in-memory overrides, which could be
+/// implemented at a higher level.
+///
+/// ```text
+///
+/// changelog
+/// +------------+
+/// | ... | node | < rev 0 \
+/// +------------+ |
+/// | ... | node | < rev 1 |> included in the main (on-disk) index
+/// +------------+ |
+/// | .......... | ... /
+/// +------------+
+/// | ... | node | < next_index_rev \
+/// +------------+ |
+/// | ... | node | < next_index_rev + 1 | will be built on-demand
+/// +------------+ |> in the side (in-memory)
+/// | .......... | ... | index
+/// +------------+ |
+/// | ... | node | < next_changelog_rev - 1 /
+/// +------------+
+/// < next_changelog_rev
+/// ```
+///
+/// The main index is an immutable, periodically-rebuilt, on-disk radix buffer
+/// with an extra metadata about what's the next revision unknown to the index.
+/// The side index covers remaining revisions in changelog, built on-demand and
+/// is in-memory only. The side index is usually much smaller than the main index
+/// so it can be built quickly.
+///
+/// ```
+/// main index side index
+/// +---------------------+ +----------------------+
+/// | next_index_rev: u32 | | (small radix buffer) |
+/// +---------------------+ +----------------------+
+/// | | (in-memory only)
+/// |(large radix buffer) |
+/// | |
+/// +---------------------+
+/// (backed by filesystem)
+/// ```
+///
+/// Having the side index allows us to make the main index immutable for most
+/// of the time even if the source of truth has changed. It's possible to update
+/// the main index in-place. But that requires extra efforts to deal with possible
+/// filesystem issues like locking, or unexpected poweroff.
+pub struct NodeRevMap<C, I> {
+ changelog: C,
+ main_index: I, // Immutable main index
+ side_index: Vec<u32>, // Mutable side index
+}
+
+const MAIN_RADIX_OFFSET: u32 = 1;
+const SIDE_RADIX_OFFSET: u32 = 0;
+
+const CHANGELOG_ENTRY_SIZE: u64 = 64;
+
+impl<C, I> NodeRevMap<C, I>
+where
+ C: AsRef<[u8]>,
+ I: AsRef<[u32]>,
+{
+ /// Initialize NodeMap from a non-inlined version of changelog.i and an incomplete index.
+ pub fn new(changelog: C, main_index: I) -> Result<Self> {
+ // Sanity check if the index is corrupted or not.
+
+ // The index must contain at least 17 elements. index[0] tracks the last rev the index has.
+ // index[1..17] is the root radix node.
+ if main_index.as_ref().len() < 17 {
+ bail!(ErrorKind::IndexCorrupted);
+ }
+
+ // Check if the index is behind and build incrementally
+ let next_rev = u32::from_be(main_index.as_ref()[0]);
+ let end_rev = changelog_next_rev(&changelog);
+
+ if next_rev > end_rev {
+ // next_rev cannot be larger than what changelog has.
+ bail!(ErrorKind::IndexCorrupted);
+ } else if next_rev > 0 {
+ // Sanity check: if the last node stored in the index does not match the changelog,
+ // the index is broken and needs rebuilt. That could happen if strip happens.
+ let rev: KeyId = (next_rev - 1).into();
+ let node = rev_to_node(&changelog, rev)?;
+ if let Ok(Some(id)) = radix_lookup_unchecked(&main_index, MAIN_RADIX_OFFSET, &node) {
+ if id != rev {
+ bail!(ErrorKind::IndexCorrupted);
+ }
+ } else {
+ bail!(ErrorKind::IndexCorrupted);
+ }
+ }
+
+ // Build side_index for the revisions not in the main index
+ let mut side_index = vec![0u32; 16];
+ build(
+ &changelog,
+ &mut side_index,
+ SIDE_RADIX_OFFSET,
+ next_rev,
+ end_rev,
+ )?;
+
+ Ok(NodeRevMap {
+ changelog,
+ main_index,
+ side_index,
+ })
+ }
+
+ /// Convert hex prefix to node.
+ pub fn hex_prefix_to_node<T: AsRef<[u8]>>(&self, hex_prefix: T) -> Result<Option<&[u8]>> {
+ let bin_prefix = match hex_to_bin_base16(hex_prefix) {
+ Some(v) => v,
+ None => return Ok(None),
+ };
+ let iter = bin_prefix.iter().cloned();
+ let cl = &self.changelog;
+ let main_res = radix_prefix_lookup(
+ &self.main_index,
+ MAIN_RADIX_OFFSET,
+ iter.clone(),
+ rev_to_node,
+ cl,
+ )?;
+ let side_res =
+ radix_prefix_lookup(&self.side_index, SIDE_RADIX_OFFSET, iter, rev_to_node, cl)?;
+ match (main_res, side_res) {
+ (Some(_), Some(_)) => {
+ let err: rerrors::Error = rerrors::ErrorKind::AmbiguousPrefix.into();
+ Err(err.into())
+ }
+ (Some(rev), None) |
+ (None, Some(rev)) => Ok(Some(rev_to_node(&self.changelog, rev)?)),
+ _ => Ok(None),
+ }
+ }
+
+ /// Convert node to rev.
+ pub fn node_to_rev<T: AsRef<[u8]>>(&self, node: T) -> Result<Option<u32>> {
+ let cl = &self.changelog;
+ if let Some(rev) = radix_lookup(&self.main_index, 1, &node, rev_to_node, cl)? {
+ Ok(Some(rev.into()))
+ } else if let Some(rev) = radix_lookup(&self.side_index, 0, &node, rev_to_node, cl)? {
+ Ok(Some(rev.into()))
+ } else {
+ Ok(None)
+ }
+ }
+
+ /// How many revisions the side index has.
+ pub fn lag(&self) -> u32 {
+ let next_rev = u32::from_be(self.main_index.as_ref()[0]);
+ let end_rev = changelog_next_rev(&self.changelog);
+ end_rev - next_rev
+ }
+
+ /// Incrementally build the main index based on the existing one.
+ /// Note: this will memcpy the immutable main index so the new buffer
+ /// could be written and resized.
+ pub fn build_incrementally(&self) -> Result<Vec<u32>> {
+ // Copy the main index since we need to modify it.
+ let mut index = self.main_index.as_ref().to_vec();
+ let end_rev = changelog_next_rev(&self.changelog);
+ let next_rev = u32::from_be(index[0]);
+ build(
+ &self.changelog,
+ &mut index,
+ MAIN_RADIX_OFFSET,
+ next_rev,
+ end_rev,
+ )?;
+ index[0] = end_rev.to_be();
+ Ok(index)
+ }
+}
+
+/// Return the minimal revision number the changelog does not have.
+fn changelog_next_rev<T: AsRef<[u8]>>(changelog: &T) -> u32 {
+ let changelog = changelog.as_ref();
+ let rev = changelog.len() as u64 / CHANGELOG_ENTRY_SIZE;
+ if rev > u32::MAX as u64 {
+ panic!("rev exceeds 32 bit integers")
+ }
+ rev as u32
+}
+
+/// Read the given range of revisions (from `start_rev` (inclusive) to
+/// `end_rev` (exclusive)) from changelog. Insert them to the radix
+/// index.
+fn build<T>(changelog: &T, index: &mut Vec<u32>, radix_offset: u32, start_rev: u32, end_rev: u32)
+ -> Result<()>
+where
+ T: AsRef<[u8]>,
+{
+ // Reserve the approximate size needed for the index - 28 bytes for each revision.
+ // See D1291 for a table of number of revisions and index sizes.
+ index.reserve(7 * (end_rev - start_rev) as usize);
+ for i in start_rev..end_rev {
+ let res = radix_insert(index, radix_offset, i.into(), rev_to_node, changelog);
+ res.chain_err(|| ErrorKind::IndexCorrupted)?;
+ }
+ Ok(())
+}
+
+/// Helper method similar to `radixbuf::key::FixedKey::read`, but takes a revision number instead.
+fn rev_to_node<K: AsRef<[u8]>>(changelog: &K, rev: KeyId) -> rerrors::Result<&[u8]> {
+ let buf = changelog.as_ref();
+ let rev_usize: usize = rev.into();
+ let start_pos = rev_usize * 64 + 32;
+ let end_pos = start_pos + 20;
+ if buf.len() < end_pos {
+ Err(rerrors::ErrorKind::InvalidKeyId(rev).into())
+ } else {
+ Ok(&buf[start_pos..end_pos])
+ }
+}
+
+/// Convert hex base16 sequence to binary base16 sequence.
+fn hex_to_bin_base16<T: AsRef<[u8]>>(base16: T) -> Option<Vec<u8>> {
+ let base16 = base16.as_ref();
+ let len = base16.len();
+ let mut result = vec![0u8; len];
+ for (i, &ch) in base16.iter().enumerate() {
+ result[i] = match ch {
+ 97...102 => ch - 87, // a...f
+ 65...70 => ch - 55, // A...F
+ 48...57 => ch - 48, // 0..9
+ _ => return None,
+ }
+ }
+ Some(result)
+}