[PATCH 4 of 4] revlog: support writing generaldelta revlogs

[Sune Foldager]

On 06-05-2011 22:34, Benoit Boissinot wrote:
> On Fri, May 6, 2011 at 10:26 PM, Sune Foldager<cryo at cyanite.org>  wrote:
>> On Fri, May 06, 2011 at 02:19:12 +0200, Peter Arrenbrecht wrote:
>>>
>>> On May 6, 2011 2:11 PM, "Benoit Boissinot"<bboissin at gmail.com>  wrote:
>>
>> [...snip...]
>>
>>>> I have some code on my laptop which depends on the dagutil module from
>>>
>>> Peter.
>>>
>>> Which is in main now.
>>
>> I think a somewhat simpler, greedy algorithm might work with a good result,
>> before or after generaldelta:
>>
>> 1. While there are revs left to bundle:
>> 2. Take the highest rev, and follow the deltachain backwards until we reach
>>    a rev we expect the receiver to have, or one he does't have and we are
>>    not going to bundle.
>> 3. In the latter case, do a delta against something he has, e.g.
>>    p1(lowest_rev_in_bundle).
>> 4. Reverse the chain we built, and bundle it. All deltas can be taken
>>    directly from the revlog.
>> 5. Goto 1.
>>
>> That should be pretty optimal, I think. I'll implement a scheme like that.
>
> I used a postorder, which works pretty nicely (similar to shrink-revlog):
> http://paste.pocoo.org/show/384245/

Alright, a postorder approach is definitely good.. however it doesn't 
take into account deltaparents. My simple algorithm above is, as it 
turns out, too simple as well. I think we need the beeeeeeeeest of both 
worlds*, so a postorder-prefering-deltaparents. I have something in mind :).

Sune

*) Brodie [who is not 10, btw], may ignore this part of the mail.