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>

1 files changed, 37 insertions, 7 deletions

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 865a7d471a..5b544bf444 100644
--- 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);
 }