[PATCH v2 6/6] pack-objects: move tree_depth into 'struct packing_data'

[Christian Couder]

This reduces the size of 'struct object_entry' and therefore
makes packing objects more efficient.

This also renames cmp_tree_depth() into tree_depth_compare(),
as it is more modern to have the name of the compare functions
end with "compare".

Signed-off-by: Christian Couder <chrisc...@tuxfamily.org>
---
 builtin/pack-objects.c | 20 ++++++++++++++++----
 delta-islands.c        | 27 ++++++++++++++++++---------
 pack-objects.h         |  4 +++-
 3 files changed, 37 insertions(+), 14 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 3d09742d91..da6dbb22d2 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2707,14 +2707,26 @@ static void show_object(struct object *obj, const char 
*name, void *data)
        if (use_delta_islands) {
                const char *p;
                unsigned depth = 0;
-               struct object_entry *ent;
+               uint32_t index_pos;
 
                for (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))
                        depth++;
 
-               ent = packlist_find(&to_pack, obj->oid.hash, NULL);
-               if (ent && depth > ent->tree_depth)
-                       ent->tree_depth = depth;
+               if (!to_pack.tree_depth) {
+                       to_pack.tree_depth = xcalloc(to_pack.nr_alloc, 
sizeof(*to_pack.tree_depth));
+                       to_pack.tree_depth_size = to_pack.nr_alloc;
+               } else if (to_pack.nr_objects > to_pack.tree_depth_size) {
+                       REALLOC_ARRAY(to_pack.tree_depth, to_pack.nr_alloc);
+                       memset(to_pack.tree_depth + to_pack.tree_depth_size, 0,
+                              (to_pack.nr_alloc - to_pack.tree_depth_size) * 
sizeof(*to_pack.tree_depth));
+                       to_pack.tree_depth_size = to_pack.nr_alloc;
+               }
+
+               if (packlist_find(&to_pack, obj->oid.hash, &index_pos)) {
+                       uint32_t i = to_pack.index[index_pos] - 1;
+                       if (depth > to_pack.tree_depth[i])
+                               to_pack.tree_depth[i] = depth;
+               }
        }
 }
 
diff --git a/delta-islands.c b/delta-islands.c
index f7902a64ad..e8e6ce3dc4 100644
--- a/delta-islands.c
+++ b/delta-islands.c
@@ -224,17 +224,23 @@ static void mark_remote_island_1(struct remote_island 
*rl, int is_core_island)
        island_counter++;
 }
 
-static int cmp_tree_depth(const void *va, const void *vb)
+struct tree_islands_todo {
+       struct object_entry *entry;
+       unsigned int depth;
+};
+
+static int tree_depth_compare(const void *a, const void *b)
 {
-       struct object_entry *a = *(struct object_entry **)va;
-       struct object_entry *b = *(struct object_entry **)vb;
-       return a->tree_depth - b->tree_depth;
+       const struct tree_islands_todo *todo_a = a;
+       const struct tree_islands_todo *todo_b = b;
+
+       return todo_a->depth - todo_b->depth;
 }
 
 void resolve_tree_islands(int progress, struct packing_data *to_pack)
 {
        struct progress *progress_state = NULL;
-       struct object_entry **todo;
+       struct tree_islands_todo *todo;
        int nr = 0;
        int i;
 
@@ -250,16 +256,19 @@ void resolve_tree_islands(int progress, struct 
packing_data *to_pack)
         */
        ALLOC_ARRAY(todo, to_pack->nr_objects);
        for (i = 0; i < to_pack->nr_objects; i++) {
-               if (oe_type(&to_pack->objects[i]) == OBJ_TREE)
-                       todo[nr++] = &to_pack->objects[i];
+               if (oe_type(&to_pack->objects[i]) == OBJ_TREE) {
+                       todo[nr].entry = &to_pack->objects[i];
+                       todo[nr].depth = to_pack->tree_depth[i];
+                       nr++;
+               }
        }
-       QSORT(todo, nr, cmp_tree_depth);
+       QSORT(todo, nr, tree_depth_compare);
 
        if (progress)
                progress_state = start_progress(_("Propagating island marks"), 
nr);
 
        for (i = 0; i < nr; i++) {
-               struct object_entry *ent = todo[i];
+               struct object_entry *ent = todo[i].entry;
                struct island_bitmap *root_marks;
                struct tree *tree;
                struct tree_desc desc;
diff --git a/pack-objects.h b/pack-objects.h
index 8eecd67991..522b09a31e 100644
--- a/pack-objects.h
+++ b/pack-objects.h
@@ -101,7 +101,6 @@ struct object_entry {
        unsigned no_try_delta:1;
        unsigned in_pack_type:TYPE_BITS; /* could be delta */
 
-       unsigned int tree_depth; /* should be repositioned for packing? */
        unsigned char layer;
 
        unsigned preferred_base:1; /*
@@ -145,6 +144,9 @@ struct packing_data {
        struct packed_git **in_pack;
 
        uintmax_t oe_size_limit;
+
+       unsigned int *tree_depth;
+       uint32_t tree_depth_size;
 };
 
 void prepare_packing_data(struct packing_data *pdata);
-- 
2.18.0.327.ga7d188ab43