Code

index-pack: eliminate recursion in find_unresolved_deltas
authorNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Sat, 14 Jan 2012 12:19:54 +0000 (19:19 +0700)
committerJunio C Hamano <gitster@pobox.com>
Mon, 16 Jan 2012 22:28:27 +0000 (14:28 -0800)
commit2baad220138b10582c55ef942466f2b8df18944f
tree5f180470742903211bdce7e6139762deebf9dde2
parent941ba8db57f2d075aee48b002ee30686288cb502
index-pack: eliminate recursion in find_unresolved_deltas

Current find_unresolved_deltas() links all bases together in a form of
tree, using struct base_data, with prev_base pointer to point to
parent node. Then it traverses down from parent to children in
recursive manner with all base_data allocated on stack.

To eliminate recursion, we simply need to put all on heap
(parse_pack_objects and fix_unresolved_deltas). After that, it's
simple non-recursive depth-first traversal loop. 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.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
builtin/index-pack.c