pack-objects: rewrite add_descendants_to_write_order() iteratively

[git.git] / builtin / pack-objects.c

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 865a7d471ac34587b6ea30f390da704b9277e5bd..5b544bf444a4c658470496a408aa01682c8f5580 100644 (file)
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -468,12 +468,43 @@ static void add_descendants_to_write_order(struct object_entry **wo,
                                           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 @@ static void add_family_to_write_order(struct object_entry **wo,
 
        for (root = e; root->delta; root = root->delta)
                ; /* nothing */
-       add_to_write_order(wo, endp, root);
        add_descendants_to_write_order(wo, endp, root);
 }