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

Nguyen Thai Ngoc Duy [off-list ref] writes:

2012/1/10 Junio C Hamano [off-list ref]:

quoted

Nguyễn Thái Ngọc Duy  [off-list ref] writes:

quoted

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>

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.

If you have the current path (base to another that is recorded as a delta
to it to yet another that is recorded as a delta to that delitified
object) on the stack, it is obvious that as you have done with the objects
on the deeper end of the delta chain, the data that becomes unnecessary
will be gone by simply returning from the recursion, but if you "put all
on heap", you would have to do the same freeing as part of the hand-rolled
recursion. It is unclear if, where and how the patch takes care of that
in the above.

Other than that, I find the description very readable.

Thanks.