This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7792

rust-nodemap: abstracting the indexing
ClosedPublic

Authored by gracinet on Jan 6 2020, 2:25 PM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHG220d4d2e3185: rust-nodemap: abstracting the indexing
Summary

In the forthcoming mutable implementation, we'll have to visit
node trees that are more complex than a single slice, although
the algorithm will still be expressed in simple indexing terms.

We still refrain using #[inline] indications as being
premature optimizations, but we strongly hope the compiler will
indeed inline most of the glue.

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

gracinet created this revision.Jan 6 2020, 2:25 PM
gracinet updated this revision to Diff 19135.Jan 10 2020, 10:03 AM
gracinet updated this revision to Diff 19325.Jan 15 2020, 6:47 PM
kevincox accepted this revision.Jan 16 2020, 5:10 AM
kevincox added inline comments.
rust/hg-core/src/revlog/nodemap.rs
240

I don't think this variable helps readability. I would just repeat self.len().

241

I would add a self.is_empty() helper. It's good practice for anything that has a .len().

gracinet updated this revision to Diff 19632.Jan 27 2020, 10:49 AM
gracinet marked 2 inline comments as done.Jan 27 2020, 10:53 AM
gracinet added inline comments.
rust/hg-core/src/revlog/nodemap.rs
241

Sure

gracinet marked an inline comment as done.Jan 27 2020, 2:13 PM
gracinet added a commit: rHG220d4d2e3185: rust-nodemap: abstracting the indexing.
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG220d4d2e3185: rust-nodemap: abstracting the indexing (authored by gracinet). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/revlog/nodemap.rs (24 lines)

Diff 19632

rust/hg-core/src/revlog/nodemap.rs

//! Following existing implicit conventions, the "nodemap" terminology //! Following existing implicit conventions, the "nodemap" terminology
//! is used in a more abstract context. //! is used in a more abstract context.
use super::{ use super::{
Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex, Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex,
}; };
use std::fmt; use std::fmt;
use std::ops::Deref; use std::ops::Deref;
use std::ops::Index;
#[derive(Debug, PartialEq)] #[derive(Debug, PartialEq)]
pub enum NodeMapError { pub enum NodeMapError {
MultipleResults, MultipleResults,
InvalidNodePrefix(NodeError), InvalidNodePrefix(NodeError),
/// A `Revision` stored in the nodemap could not be found in the index /// A `Revision` stored in the nodemap could not be found in the index
RevisionNotInIndex(Revision), RevisionNotInIndex(Revision),
} }
} }
} }
/// A 16-radix tree with the root block at the end /// A 16-radix tree with the root block at the end
pub struct NodeTree { pub struct NodeTree {
readonly: Box<dyn Deref<Target = [Block]> + Send>, readonly: Box<dyn Deref<Target = [Block]> + Send>,
} }
impl Index<usize> for NodeTree {
type Output = Block;
fn index(&self, i: usize) -> &Block {
&self.readonly[i]
}
}
/// Return `None` unless the `Node` for `rev` has given prefix in `index`. /// Return `None` unless the `Node` for `rev` has given prefix in `index`.
fn has_prefix_or_none<'p>( fn has_prefix_or_none<'p>(
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef<'p>, prefix: NodePrefixRef<'p>,
rev: Revision, rev: Revision,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
idx.node(rev) idx.node(rev)
.ok_or_else(|| NodeMapError::RevisionNotInIndex(rev)) .ok_or_else(|| NodeMapError::RevisionNotInIndex(rev))
.map(|node| { .map(|node| {
if prefix.is_prefix_of(node) { if prefix.is_prefix_of(node) {
Some(rev) Some(rev)
} else { } else {
None None
} }
}) })
} }
impl NodeTree { impl NodeTree {
fn len(&self) -> usize {
self.readonly.len()
}
fn is_empty(&self) -> bool {
self.len() == 0
}
/// Main working method for `NodeTree` searches /// Main working method for `NodeTree` searches
/// ///
/// This partial implementation lacks special cases for NULL_REVISION /// This partial implementation lacks special cases for NULL_REVISION
fn lookup<'p>( fn lookup<'p>(
&self, &self,
prefix: NodePrefixRef<'p>, prefix: NodePrefixRef<'p>,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
let blocks: &[Block] = &*self.readonly; if self.is_empty() {
kevincoxUnsubmitted
Done

I don't think this variable helps readability. I would just repeat self.len().

kevincox: I don't think this variable helps readability. I would just repeat `self.len()`.
if blocks.is_empty() {
return Ok(None); return Ok(None);
kevincoxUnsubmitted
Done

I would add a self.is_empty() helper. It's good practice for anything that has a .len().

kevincox: I would add a `self.is_empty()` helper. It's good practice for anything that has a `.len()`.
gracinetAuthorUnsubmitted
Done

Sure

gracinet: Sure
} }
let mut visit = blocks.len() - 1; let mut visit = self.len() - 1;
for i in 0..prefix.len() { for i in 0..prefix.len() {
let nybble = prefix.get_nybble(i); let nybble = prefix.get_nybble(i);
match blocks[visit].get(nybble) { match self[visit].get(nybble) {
Element::None => return Ok(None), Element::None => return Ok(None),
Element::Rev(r) => return Ok(Some(r)), Element::Rev(r) => return Ok(Some(r)),
Element::Block(idx) => visit = idx, Element::Block(idx) => visit = idx,
} }
} }
Err(NodeMapError::MultipleResults) Err(NodeMapError::MultipleResults)
} }
} }