[PATCH 4/4] pack-objects: rewrite add_descendants_to_write_order() iteratively
- From
Dan McGee <dpmcgee@gmail.com>
- Date
- Oct 18, 2011, 05:21 UTC
- Message-ID
- <1318915284-6361-4-git-send-email-dpmcgee@gmail.com>
- In-Reply-To
- <1318915284-6361-1-git-send-email-dpmcgee@gmail.com>
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> --- builtin/pack-objects.c | 44 +++++++++++++++++++++++++++++++++++++------- 1 files changed, 37 insertions(+), 7 deletions(-)
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index d9fb202..9efd1a7 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); }
-- 1.7.7