author | Nguyễn Thái Ngọc Duy <pclouds@gmail.com> | |
Sat, 14 Jan 2012 12:19:54 +0000 (19:19 +0700) | ||
committer | Junio C Hamano <gitster@pobox.com> | |
Mon, 16 Jan 2012 22:28:27 +0000 (14:28 -0800) | ||
commit | 2baad220138b10582c55ef942466f2b8df18944f | |
tree | 5f180470742903211bdce7e6139762deebf9dde2 | tree | snapshot |
parent | 941ba8db57f2d075aee48b002ee30686288cb502 | commit | diff |
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>
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 | diff | blob | history |