radixbuf: add read and write functions for keys
ClosedPublic

Authored by quark on Nov 15 2017, 8:55 PM.

Details

Reviewers
durham
Group Reviewers
Restricted Project
Commits
rFBHGXc18ab4236680: radixbuf: add read and write functions for keys
Summary

Keys are [u8] stored in a plain buffer. This diff adds functions to read
and write two kinds of keys - fixed sized (20 bytes) and variant-length
ones. The latter uses VLQ encoding to store key length.

Applications could implement other functions. For example, Mercurial could
use revision numbers instead of offsets to refer to commit hashes.

The read functions will be used in the main radix tree logic.

Test Plan

cargo test --lib

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
quark created this revision.Nov 15 2017, 8:55 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 15 2017, 8:55 PM
durham accepted this revision.Nov 29 2017, 6:27 PM
durham added a subscriber: durham.
durham added inline comments.
rust/radixbuf/src/key.rs
107

noob question: why is into() needed here?

117

You just do + 8 here because that's the maximum length of a vlq encoded integer? Should that be a constant somewhere in the vlq library?

124

Would key_buf.len() be equivalent to pos + buf.len() here? Probably doesn't matter, but want to make sure I understand.

This revision is now accepted and ready to land.Nov 29 2017, 6:27 PM
quark added a subscriber: mbthomas.Nov 29 2017, 9:50 PM
quark added inline comments.
rust/radixbuf/src/key.rs
107

ErrorKind is a different type from Error. The latter is expected by Err. There is no implicit conversion in Rust.

I noticed @mbthomas was using the bail! macro. This line could be simplified to:

bail!(ErrorKind::InvalidKeyId(key_id))

I plan to do a codemod and absorb the changes if it's simple or add a new commit if it cannot be absorbed cleanly.

117

8 may not be a best number here. I was thinking from some malloc implementation details (which may be incorrect). The smallest unit of C malloc might be 8 bytes. i.e. the following code probably won't cause segfault:

char *p = malloc(1);
p[7] = 'c';

The VLQ library does not do pre-allocation (to support stream read/write). So it just does read(1 byte) or write(1 byte) at a time. That might seem inefficient but heap allocation is much more expensive there (removing Vec from vlq code results in 3x speedup).

124

Yes.

quark updated this revision to Diff 4449.Dec 14 2017, 9:21 PM
This revision was automatically updated to reflect the committed changes.