Merge branch 'dm/pack-objects-update'

* dm/pack-objects-update:
pack-objects: don't traverse objects unnecessarily
pack-objects: rewrite add_descendants_to_write_order() iteratively
pack-objects: use unsigned int for counter and offset values
pack-objects: mark add_to_write_order() as inline

diff --combined builtin/pack-objects.c
index ba3705d1de0d91714be4c967a26ffd263e09878c,80ab6c39f91b30be90203da777fd8e3989abdc2c..824ecee20b94c471083ad8c7f697b39fbb7cb2b8
--- 1/builtin/pack-objects.c
--- 2/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@@ -454,8 -454,8 +454,8 @@@ static int mark_tagged(const char *path
        return 0;
  }
  
- static void add_to_write_order(struct object_entry **wo,
-                              int *endp,
+ static inline void add_to_write_order(struct object_entry **wo,
+                              unsigned int *endp,
                               struct object_entry *e)
  {
        if (e->filled)
@@@ -465,32 -465,62 +465,62 @@@
  }
  
  static void add_descendants_to_write_order(struct object_entry **wo,
-                                          int *endp,
+                                          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,
-                                     int *endp,
+                                     unsigned int *endp,
                                      struct object_entry *e)
  {
        struct object_entry *root;
  
        for (root = e; root->delta; root = root->delta)
                ; /* nothing */
-       add_to_write_order(wo, endp, root);
        add_descendants_to_write_order(wo, endp, root);
  }
  
  static struct object_entry **compute_write_order(void)
  {
-       int i, wo_end;
+       unsigned int i, wo_end, last_untagged;
  
        struct object_entry **wo = xmalloc(nr_objects * sizeof(*wo));
  
@@@ -506,8 -536,8 +536,8 @@@
         * Make sure delta_sibling is sorted in the original
         * recency order.
         */
-       for (i = nr_objects - 1; 0 <= i; i--) {
-               struct object_entry *e = &objects[i];
+       for (i = nr_objects; i > 0;) {
+               struct object_entry *e = &objects[--i];
                if (!e->delta)
                        continue;
                /* Mark me as the first child */
@@@ -521,7 -551,7 +551,7 @@@
        for_each_tag_ref(mark_tagged, NULL);
  
        /*
-        * Give the commits in the original recency order until
+        * Give the objects in the original recency order until
         * we see a tagged tip.
         */
        for (i = wo_end = 0; i < nr_objects; i++) {
@@@ -529,6 -559,7 +559,7 @@@
                        break;
                add_to_write_order(wo, &wo_end, &objects[i]);
        }
+       last_untagged = i;
  
        /*
         * Then fill all the tagged tips.
@@@ -541,7 -572,7 +572,7 @@@
        /*
         * And then all remaining commits and tags.
         */
-       for (i = 0; i < nr_objects; i++) {
+       for (i = last_untagged; i < nr_objects; i++) {
                if (objects[i].type != OBJ_COMMIT &&
                    objects[i].type != OBJ_TAG)
                        continue;
@@@ -551,7 -582,7 +582,7 @@@
        /*
         * And then all the trees.
         */
-       for (i = 0; i < nr_objects; i++) {
+       for (i = last_untagged; i < nr_objects; i++) {
                if (objects[i].type != OBJ_TREE)
                        continue;
                add_to_write_order(wo, &wo_end, &objects[i]);
@@@ -560,8 -591,13 +591,13 @@@
        /*
         * Finally all the rest in really tight order
         */
-       for (i = 0; i < nr_objects; i++)
-               add_family_to_write_order(wo, &wo_end, &objects[i]);
+       for (i = last_untagged; i < nr_objects; i++) {
+               if (!objects[i].filled)
+                       add_family_to_write_order(wo, &wo_end, &objects[i]);
+       }
+ 
+       if (wo_end != nr_objects)
+               die("ordered %u objects, expected %"PRIu32, wo_end, nr_objects);
  
        return wo;
  }
@@@ -804,10 -840,6 +840,10 @@@ static int add_object_entry(const unsig
                off_t offset = find_pack_entry_one(sha1, p);
                if (offset) {
                        if (!found_pack) {
 +                              if (!is_pack_valid(p)) {
 +                                      warning("packfile %s cannot be accessed", p->pack_name);
 +                                      continue;
 +                              }
                                found_offset = offset;
                                found_pack = p;
                        }
@@@ -2077,9 -2109,7 +2113,9 @@@ static void show_commit(struct commit *
        commit->object.flags |= OBJECT_ADDED;
  }
  
 -static void show_object(struct object *obj, const struct name_path *path, const char *last)
 +static void show_object(struct object *obj,
 +                      const struct name_path *path, const char *last,
 +                      void *data)
  {
        char *name = path_name(path, last);