( )⚙ D11932 rhg: Use binary search in manifest lookup

This is an archive of the discontinued Mercurial Phabricator instance.

rhg: Use binary search in manifest lookup
ClosedPublic

Authored by SimonSapin on Dec 16 2021, 12:13 PM.

Details

Summary

… instead of linear scan, when looking for a single entry based on its path.
Manifest entries are sorted by path, but are variable-size so we can’t use
the standard library’s [T]::binary_search. We can still jump to a byte
index and then look around for entry boundaries.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

SimonSapin created this revision.Dec 16 2021, 12:13 PM
Alphare accepted this revision.Dec 17 2021, 6:09 AM
This revision is now accepted and ready to land.Dec 17 2021, 6:09 AM
This revision was automatically updated to reflect the committed changes.