optimize diffcore-delta by sorting hash entries.

diff --git a/tree-walk.c b/tree-walk.c
index 22f4550b6ca4d2cb185fc19f6be414a8a0874a60..8d4b67317f21508a105175686c7ec98a090ed9b5 100644 (file)
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -2,6 +2,44 @@
 #include "tree-walk.h"
 #include "tree.h"
 
+static const char *get_mode(const char *str, unsigned int *modep)
+{
+       unsigned char c;
+       unsigned int mode = 0;
+
+       while ((c = *str++) != ' ') {
+               if (c < '0' || c > '7')
+                       return NULL;
+               mode = (mode << 3) + (c - '0');
+       }
+       *modep = mode;
+       return str;
+}
+
+static void decode_tree_entry(struct tree_desc *desc, const void *buf, unsigned long size)
+{
+       const char *path;
+       unsigned int mode, len;
+
+       path = get_mode(buf, &mode);
+       if (!path)
+               die("corrupt tree file");
+       len = strlen(path) + 1;
+
+       /* Initialize the descriptor entry */
+       desc->entry.path = path;
+       desc->entry.mode = mode;
+       desc->entry.sha1 = (const unsigned char *)(path + len);
+}
+
+void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
+{
+       desc->buffer = buffer;
+       desc->size = size;
+       if (size)
+               decode_tree_entry(desc, buffer, size);
+}
+
 void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
 {
        unsigned long size = 0;
@@ -12,16 +50,15 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
                if (!buf)
                        die("unable to read tree %s", sha1_to_hex(sha1));
        }
-       desc->size = size;
-       desc->buf = buf;
+       init_tree_desc(desc, buf, size);
        return buf;
 }
 
 static int entry_compare(struct name_entry *a, struct name_entry *b)
 {
        return base_name_compare(
-                       a->path, a->pathlen, a->mode,
-                       b->path, b->pathlen, b->mode);
+                       a->path, tree_entry_len(a->path, a->sha1), a->mode,
+                       b->path, tree_entry_len(b->path, b->sha1), b->mode);
 }
 
 static void entry_clear(struct name_entry *a)
@@ -31,80 +68,33 @@ static void entry_clear(struct name_entry *a)
 
 static void entry_extract(struct tree_desc *t, struct name_entry *a)
 {
-       a->sha1 = tree_entry_extract(t, &a->path, &a->mode);
-       a->pathlen = strlen(a->path);
+       *a = t->entry;
 }
 
 void update_tree_entry(struct tree_desc *desc)
 {
-       const void *buf = desc->buf;
+       const void *buf = desc->buffer;
+       const unsigned char *end = desc->entry.sha1 + 20;
        unsigned long size = desc->size;
-       int len = strlen(buf) + 1 + 20;
+       unsigned long len = end - (const unsigned char *)buf;
 
        if (size < len)
                die("corrupt tree file");
-       desc->buf = (char *) buf + len;
-       desc->size = size - len;
-}
-
-static const char *get_mode(const char *str, unsigned int *modep)
-{
-       unsigned char c;
-       unsigned int mode = 0;
-
-       while ((c = *str++) != ' ') {
-               if (c < '0' || c > '7')
-                       return NULL;
-               mode = (mode << 3) + (c - '0');
-       }
-       *modep = mode;
-       return str;
-}
-
-const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)
-{
-       const void *tree = desc->buf;
-       unsigned long size = desc->size;
-       int len = strlen(tree)+1;
-       const unsigned char *sha1 = (unsigned char *) tree + len;
-       const char *path;
-       unsigned int mode;
-
-       path = get_mode(tree, &mode);
-       if (!path || size < len + 20)
-               die("corrupt tree file");
-       *pathp = path;
-       *modep = canon_mode(mode);
-       return sha1;
+       buf = end;
+       size -= len;
+       desc->buffer = buf;
+       desc->size = size;
+       if (size)
+               decode_tree_entry(desc, buf, size);
 }
 
 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
 {
-       const void *tree = desc->buf;
-       const char *path;
-       unsigned long len, size = desc->size;
-
-       if (!size)
+       if (!desc->size)
                return 0;
 
-       path = get_mode(tree, &entry->mode);
-       if (!path)
-               die("corrupt tree file");
-
-       entry->path = path;
-       len = strlen(path);
-       entry->pathlen = len;
-
-       path += len + 1;
-       entry->sha1 = (const unsigned char *) path;
-
-       path += 20;
-       len = path - (char *) tree;
-       if (len > size)
-               die("corrupt tree file");
-
-       desc->buf = path;
-       desc->size = size - len;
+       *entry = desc->entry;
+       update_tree_entry(desc);
        return 1;
 }
 
@@ -169,7 +159,7 @@ static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char
 
                sha1 = tree_entry_extract(t, &entry, mode);
                update_tree_entry(t);
-               entrylen = strlen(entry);
+               entrylen = tree_entry_len(entry, sha1);
                if (entrylen > namelen)
                        continue;
                cmp = memcmp(name, entry, entrylen);
@@ -198,14 +188,21 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch
 {
        int retval;
        void *tree;
+       unsigned long size;
        struct tree_desc t;
+       unsigned char root[20];
 
-       tree = read_object_with_reference(tree_sha1, tree_type, &t.size, NULL);
+       tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
        if (!tree)
                return -1;
-       t.buf = tree;
+
+       if (name[0] == '\0') {
+               hashcpy(sha1, root);
+               return 0;
+       }
+
+       init_tree_desc(&t, tree, size);
        retval = find_tree_entry(&t, name, sha1, mode);
        free(tree);
        return retval;
 }
-