On Tue, Mar 02, 2021 at 10:36:20AM -0800, Jonathan Tan wrote: > > midx_to_pack_pos() is the trickiest, since it needs to find an object's > > position in the psuedo-pack order, but that order can only be recovered > > in the .rev file itself. This mapping can be implemented with a binary > > search, but note that the thing we're binary searching over isn't an > > array, but rather a _permutation_. > > > > So, when comparing two items, it's helpful to keep in mind the > > difference. Instead of a traditional binary search, where you are > > comparing two things directly, here we're comparing a (pack, offset) > > tuple with an index into the multi-pack index. That index describes > > another (pack, offset) tuple, and it is _those_ two tuples that are > > compared. > > Well, the binary search is indeed over an array :-) :-). This might be more clearer as: ...isn't an array of values, but rather a permuted order of those values. > The patch itself looks good. Thanks. Taylor
