[PATCH 8/9] pv4_tree_desc: avoid lookup_object() when possible

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

pv4_tree_desc_from_entry() cuts out SHA-1 index lookups when
possible. This patch provides a new set of lookup functions that avoid
looking up object hash table.

We maintain an object pointer array and use SHA-1 table as
key. Because we know index in SHA-1 table in v4 trees, we can skip
binary search and go straight to the object.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache.h        |  1 +
 packv4-parse.c | 33 +++++++++++++++++++++++++++++++++
 packv4-parse.h | 12 ++++++++++++
 sha1_file.c    |  1 +
 4 files changed, 47 insertions(+)

diff --git a/cache.h b/cache.h
index 5028ded..da65063 100644
--- a/cache.h
+++ b/cache.h
@@ -1035,6 +1035,7 @@ extern struct packed_git {
 	struct packv4_dict *ident_dict;
 	off_t ident_dict_end;
 	struct packv4_dict *path_dict;
+	struct object **objs;
 	time_t mtime;
 	int pack_fd;
 	unsigned pack_local:1,
diff --git a/packv4-parse.c b/packv4-parse.c
index 4354ee3..6f6152c 100644
--- a/packv4-parse.c
+++ b/packv4-parse.c
@@ -11,6 +11,10 @@
 #include "cache.h"
 #include "packv4-parse.h"
 #include "varint.h"
+#include "commit.h"
+#include "tree.h"
+#include "blob.h"
+#include "tag.h"
 
 int packv4_available;
 
@@ -815,3 +819,32 @@ int pv4_tree_entry(struct pv4_tree_desc *desc)
 	}
 	return !decode_entries(desc, desc->obj_offset, desc->start++, 1);
 }
+
+static struct object **get_packed_objs(struct pv4_tree_desc *desc)
+{
+	if (!desc->p || !desc->sha1_index)
+		return NULL;
+	if (desc->p->version >= 4 && !desc->p->objs)
+		desc->p->objs =
+			xmalloc(sizeof(struct object *) * desc->p->num_objects);
+	return desc->p->objs;
+}
+
+#define DEFINE_LOOKUP(TYPE)					\
+struct TYPE *pv4_lookup_##TYPE(struct pv4_tree_desc *desc)	\
+{								\
+	struct object **objs = get_packed_objs(desc);		\
+	if (!objs)						\
+		return lookup_##TYPE(desc->v2.entry.sha1);	\
+	objs += desc->sha1_index - 1;				\
+	if (!*objs)						\
+		*objs = (struct object *)			\
+			lookup_##TYPE(desc->v2.entry.sha1);	\
+	return (struct TYPE *)objs[0];				\
+}
+
+DEFINE_LOOKUP(object)
+DEFINE_LOOKUP(commit)
+DEFINE_LOOKUP(tree)
+DEFINE_LOOKUP(blob)
+DEFINE_LOOKUP(tag)
diff --git a/packv4-parse.h b/packv4-parse.h
index 874f57c..3bf69bc 100644
--- a/packv4-parse.h
+++ b/packv4-parse.h
@@ -3,6 +3,12 @@
 
 #include "tree-walk.h"
 
+struct object;
+struct commit;
+struct tree;
+struct blob;
+struct tag;
+
 struct packv4_dict {
 	const unsigned char *data;
 	unsigned int nb_entries;
@@ -58,4 +64,10 @@ void pv4_release_tree_desc(struct pv4_tree_desc *desc);
 
 int pv4_tree_entry(struct pv4_tree_desc *desc);
 
+struct object *pv4_lookup_object(struct pv4_tree_desc *desc);
+struct commit *pv4_lookup_commit(struct pv4_tree_desc *desc);
+struct tree   *pv4_lookup_tree(struct pv4_tree_desc *desc);
+struct blob   *pv4_lookup_blob(struct pv4_tree_desc *desc);
+struct tag    *pv4_lookup_tag(struct pv4_tree_desc *desc);
+
 #endif
diff --git a/sha1_file.c b/sha1_file.c
index 4744132..88a6273 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -773,6 +773,7 @@ void free_pack_by_name(const char *pack_name)
 			*pp = p->next;
 			if (last_found_pack == p)
 				last_found_pack = NULL;
+			free(p->objs);
 			free(p);
 			return;
 		}
-- 
1.8.2.83.gc99314b