This is an archive of the discontinued Mercurial Phabricator instance.

radixbuf: initial boilerplate
ClosedPublic

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

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
12–13 ↗(On Diff #3209)

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
12–13 ↗(On Diff #3209)

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
This revision was automatically updated to reflect the committed changes.