pack-objects: rewrite add_descendants_to_write_order() iteratively
This removes the need to call this function recursively, shinking the
code size slightly and netting a small performance increase.
Signed-off-by: Dan McGee <dpmcgee@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 865a7d4..5b544bf 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -468,12 +468,43 @@
unsigned int *endp,
struct object_entry *e)
{
- struct object_entry *child;
-
- for (child = e->delta_child; child; child = child->delta_sibling)
- add_to_write_order(wo, endp, child);
- for (child = e->delta_child; child; child = child->delta_sibling)
- add_descendants_to_write_order(wo, endp, child);
+ int add_to_order = 1;
+ while (e) {
+ if (add_to_order) {
+ struct object_entry *s;
+ /* add this node... */
+ add_to_write_order(wo, endp, e);
+ /* all its siblings... */
+ for (s = e->delta_sibling; s; s = s->delta_sibling) {
+ add_to_write_order(wo, endp, s);
+ }
+ }
+ /* drop down a level to add left subtree nodes if possible */
+ if (e->delta_child) {
+ add_to_order = 1;
+ e = e->delta_child;
+ } else {
+ add_to_order = 0;
+ /* our sibling might have some children, it is next */
+ if (e->delta_sibling) {
+ e = e->delta_sibling;
+ continue;
+ }
+ /* go back to our parent node */
+ e = e->delta;
+ while (e && !e->delta_sibling) {
+ /* we're on the right side of a subtree, keep
+ * going up until we can go right again */
+ e = e->delta;
+ }
+ if (!e) {
+ /* done- we hit our original root node */
+ return;
+ }
+ /* pass it off to sibling at this level */
+ e = e->delta_sibling;
+ }
+ };
}
static void add_family_to_write_order(struct object_entry **wo,
@@ -484,7 +515,6 @@
for (root = e; root->delta; root = root->delta)
; /* nothing */
- add_to_write_order(wo, endp, root);
add_descendants_to_write_order(wo, endp, root);
}
