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

[Nguyen Thai Ngoc Duy <pclouds@gmail.com>]

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.
-- 
Duy