compat: Add simplified merge sort implementation from glibc

diff --git a/pack-check.c b/pack-check.c
index c168642c0c0d9479b1ccc8564ce6c80c9055ab00..d7dd62bb8346c4cac8dbd7334e999a450c21c5ab 100644 (file)
--- a/pack-check.c
+++ b/pack-check.c
@@ -1,6 +1,23 @@
 #include "cache.h"
 #include "pack.h"
 
+struct idx_entry
+{
+       const unsigned char *sha1;
+       off_t                offset;
+};
+
+static int compare_entries(const void *e1, const void *e2)
+{
+       const struct idx_entry *entry1 = e1;
+       const struct idx_entry *entry2 = e2;
+       if (entry1->offset < entry2->offset)
+               return -1;
+       if (entry1->offset > entry2->offset)
+               return 1;
+       return 0;
+}
+
 static int verify_packfile(struct packed_git *p,
                struct pack_window **w_curs)
 {
@@ -11,6 +28,7 @@ static int verify_packfile(struct packed_git *p,
        off_t offset = 0, pack_sig = p->pack_size - 20;
        uint32_t nr_objects, i;
        int err;
+       struct idx_entry *entries;
 
        /* Note that the pack header checks are actually performed by
         * use_pack when it first opens the pack file.  If anything
@@ -41,33 +59,38 @@ static int verify_packfile(struct packed_git *p,
         * we do not do scan-streaming check on the pack file.
         */
        nr_objects = p->num_objects;
+       entries = xmalloc(nr_objects * sizeof(*entries));
+       /* first sort entries by pack offset, since unpacking them is more efficient that way */
+       for (i = 0; i < nr_objects; i++) {
+               entries[i].sha1 = nth_packed_object_sha1(p, i);
+               if (!entries[i].sha1)
+                       die("internal error pack-check nth-packed-object");
+               entries[i].offset = find_pack_entry_one(entries[i].sha1, p);
+               if (!entries[i].offset)
+                       die("internal error pack-check find-pack-entry-one");
+       }
+       qsort(entries, nr_objects, sizeof(*entries), compare_entries);
+
        for (i = 0, err = 0; i < nr_objects; i++) {
-               const unsigned char *sha1;
                void *data;
                enum object_type type;
                unsigned long size;
-               off_t offset;
 
-               sha1 = nth_packed_object_sha1(p, i);
-               if (!sha1)
-                       die("internal error pack-check nth-packed-object");
-               offset = find_pack_entry_one(sha1, p);
-               if (!offset)
-                       die("internal error pack-check find-pack-entry-one");
-               data = unpack_entry(p, offset, &type, &size);
+               data = unpack_entry(p, entries[i].offset, &type, &size);
                if (!data) {
                        err = error("cannot unpack %s from %s",
-                                   sha1_to_hex(sha1), p->pack_name);
+                                   sha1_to_hex(entries[i].sha1), p->pack_name);
                        continue;
                }
-               if (check_sha1_signature(sha1, data, size, typename(type))) {
+               if (check_sha1_signature(entries[i].sha1, data, size, typename(type))) {
                        err = error("packed %s from %s is corrupt",
-                                   sha1_to_hex(sha1), p->pack_name);
+                                   sha1_to_hex(entries[i].sha1), p->pack_name);
                        free(data);
                        continue;
                }
                free(data);
        }
+       free(entries);
 
        return err;
 }
@@ -128,12 +151,17 @@ static void show_pack_info(struct packed_git *p)
 
 int verify_pack(struct packed_git *p, int verbose)
 {
-       off_t index_size = p->index_size;
-       const unsigned char *index_base = p->index_data;
+       off_t index_size;
+       const unsigned char *index_base;
        SHA_CTX ctx;
        unsigned char sha1[20];
        int ret;
 
+       if (open_pack_index(p))
+               return error("packfile %s index not opened", p->pack_name);
+       index_size = p->index_size;
+       index_base = p->index_data;
+
        ret = 0;
        /* Verify SHA1 sum of the index file */
        SHA1_Init(&ctx);