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

2012/1/10 Junio C Hamano <gitster@pobox.com>:

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.