[PATCH 28/32] narrow-tree: add oldest_narrow_base()

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

This function helps solve another problem at client. Because
upload-narrow-base receives commits. What if they don't have those
commits because they are created locally?

The solution is to find the oldest commits that still have the same
narrow base (trees outside narrow tree) and use those commits with
hope that the server side also have them.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 narrow-tree.c |   48 ++++++++++++++++++++++++++++++++++++++++++++++++
 narrow-tree.h |    1 +
 2 files changed, 49 insertions(+), 0 deletions(-)

diff --git a/narrow-tree.c b/narrow-tree.c
index 4a16647..f1b8902 100644
--- a/narrow-tree.c
+++ b/narrow-tree.c
@@ -150,3 +150,51 @@ int same_narrow_base(const unsigned char *t1, const unsigned char *t2, const cha
 	free(buf2);
 	return !desc1.size && !desc2.size;
 }
+
+int oldest_narrow_base(const unsigned char *sha1, unsigned char *newsha1)
+{
+	enum object_type type;
+	unsigned long size;
+	char *buf, *bufptr;
+	unsigned char base[20], newbase[20], parent[20];
+
+	buf = read_sha1_file(sha1, &type, &size);
+	if (!buf || type != OBJ_COMMIT) {
+		if (buf)
+			free(buf);
+		error("Not a commit %s", sha1_to_hex(sha1));
+		return 1;
+	}
+	get_sha1_hex(buf+5, base);
+	hashcpy(newsha1, sha1);
+
+	while (1) {
+		bufptr = buf + 46;	/* "tree " + "hex sha1" + "\n" */
+		if (!memcmp(bufptr, "parent ", 7)) {
+
+			/* more than one parent, a merge */
+			if (!memcmp(bufptr + 48, "parent ", 7))
+				break;
+
+			free(buf);
+			get_sha1_hex(bufptr + 7, parent);
+			buf = read_sha1_file(parent, &type, &size);
+			if (!buf ||type != OBJ_COMMIT) {
+				if (buf)
+					free(buf);
+				error("Not a commit %s", sha1_to_hex(sha1));
+				return 1;
+			}
+			get_sha1_hex(buf+5, newbase);
+			if (!same_narrow_base(base, newbase, get_narrow_prefix()))
+				break;
+
+			hashcpy(newsha1, parent);
+			/* keep searching */
+		}
+		else		/* root commit */
+			break;
+	}
+	free(buf);
+	return 0;
+}
diff --git a/narrow-tree.h b/narrow-tree.h
index 8756094..78d6f39 100644
--- a/narrow-tree.h
+++ b/narrow-tree.h
@@ -2,3 +2,4 @@ extern int check_narrow_prefix();
 extern int join_narrow_tree(const unsigned char *base, unsigned char *newsha1,
 			    const unsigned char *subtree_sha1, const char *prefix);
 int same_narrow_base(const unsigned char *t1, const unsigned char *t2, const char *prefix);
+int oldest_narrow_base(const unsigned char *sha1, unsigned char *newsha1);
-- 
1.7.1.rc1.69.g24c2f7