Re: [PATCH v2 2/3] index-pack: eliminate recursion in find_unresolved_deltas

> 2012/1/10 Junio C Hamano <gitster@pobox.com>:
>> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>>
>>> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
>>
>> I find both the original and the updated code rather dense to read without
>> annotation, but from a cursory look all changes look good.
>
> Maybe I stared at it for too long it seems obvious to me (hence no
> further description in commit message). Let me describe it (and put in
> commit message later if it makes sense)
>
> Current code already links all bases together in a form of tree, using
> struct base_data, with prev_base pointer to point to parent node. The
> only problem is that struct base_data is all allocated on stack. So we
> need to put all on heap (parse_pack_objects and
> fix_unresolved_deltas). After that, it's simple depth-first traversal
> where each node also maintains its own state (ofs and ref indices to
> iterate over all children nodes).
>
> So we process one node:
>
>  - if it returns a new (child) node (a parent base), we link it to our
> tree, then process the new node.
>  - if it returns nothing, the node is done, free it. We go back to
> parent node and resume whatever it's doing.
>
> and do it until we have no nodes to process.