radixbuf: add read and write functions for keys

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


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

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

rFBHGX Facebook Mercurial Extensions
Automatic diff as part of commit; lint not applicable.
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.

noob question: why is into() needed here?


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?


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.

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:


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.


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).



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