> 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 :-) I understood that the array we're searching over is an array of indexes into the MIDX in pack-pos order, so I understood what's written here. It might be easier for other readers if we just say that we're treating the elements of this array not as indexes into MIDX but as their corresponding (is-preferred-pack, pack number, offset) tuples. But I'm fine with retaining the existing wording too. The patch itself looks good.
